【作者】 刘宇；

【导师】 熊有伦；

【作者基本信息】 华中科技大学 ， 机械电子工程， 2008， 博士

【摘要】 面对数字建模中数以万计的测量数据,最近点查询、正交区域查询、球域查询等基本操作对数据处理算法的计算效率有很大影响。为了提高这些操作的效率,定义了有界k-d树。有界k-d树中数据的空间范围由根节点中的包围盒来进行限制。基于有界k-d树的查询算法在搜索中通过超平面不断划分包围盒来缩小搜索范围,同时递归地计算查询点到包围盒的距离。结合优先级队列,基于有界k-d树的最近点查询算法可拓展到搜索按距离远近排列的多个最近点。实测数据和不同维数的仿真数据的实验分析表明,基于有界k-d树的查询算法的计算效率优于传统的几种搜索算法。另外,还实现了球面数据的快速匀称划分。曲率和Darboux标架在数据拼合、数据分割等任务中得到了广泛的应用。然而从受噪声污染的散乱点准确地估计这些信息仍然十分困难。本文提出了一种从散乱坐标点拟合一般二次曲面,然后估计曲率张量的方法。引入TLS3L(total least squares on the three level sets)曲面拟合方法,实现了对散乱点的快速可靠的拟合。推导得出了任意隐式曲面曲率的计算公式和三维矢量形式的主方向。从理论上分析了拟合过程的有效性。与其他一些方法相比,该方法能够更可靠地从散乱点估计微分信息。数据拼合是航空摄影测量、工业检测、曲面建模等方面的重要研究课题。如何确定对应关系、提高拼合精度等都是数据拼合中仍有待解决的问题。本文提出了SCR(Signatures, Clusters, Refinement)方法对散乱点表示的任意曲面进行拼合。该方法通过匹配邻域标识来确定对应关系,根据三维欧拉群SE(3)中的聚类来估计刚体变换的初值,最后对刚体变换的初值迭代求精。所引入的邻域标识将曲面上一点周围的形状变化表示为特征空间中的一点,便于采用k-d树等数据结构加速对应点的搜索。根据从对应点组计算的刚体变换的聚类特性,提出PV(Parameter Voting)方法来估计刚体变换的初值。在对刚体变换初值的迭代求精的过程中,用局部曲面片代替离散点作为拼合的目标几何体,提出了ICS(Iterative Corresponding Surface)方法。数据分割是物体识别、自动导航、反求工程等任务中的必要处理步骤。即使是对仅仅包含多面体的场景,分割问题也没有完全解决。本文分析了不同边界处的微分特性,指出仅依靠一点与其相邻点的法矢或曲率的变化难以完成数据分割任务。提出了一种散乱点分割方法GCRR(Gaussian map, Clustering, region Recognition, and region Rectification)。该方法采用CMS(cell mean shift)算法对输入数据的高斯图进行聚类。提出了基于奇异值分解的维数分析方法将高斯球上的聚类分成点形、线形和面形的聚类。每个聚类对应R3中的一个点集。通过对应面形聚类的高斯映射的定向分析,识别了双曲面和椭圆面。采用点-平面距离函数区分了凸面和凹面。通过区域调整消除了边界附近因法矢估计误差而产生的区域。给出了GCRR方法的复杂度分析、在仿真和实测数据上的实验结果。最后,开发了数字建模系统MIMDFM(Measurment, Integrated Modeling, and Design For Manufacturing of complex parts),对所提出的理论和方法进行了编程实现,通过几个实际零件的数字建模过程验证了该系统的有效性。更多还原

【Abstract】 Facing tens of thousands of measurement data in the digital modeling, the time cost of a data processing algorithm depends greatly on some elementary operations, such as closest point query, orthogonal region query, spherical region query, and so on. In order to improve efficiencies of these operations, a bounded k-d tree is defined, in which the spatial range of the data is restricted by the bounded box of the root node. The query algorithm based on the bounded k-d tree reduces search areas by continually dividing bounded boxes in the searching process and calculates the distance from a query point to a bounded box recursively. Combined with a priority queue, the closest point query algorithm can be generalized to search multi-nearest-neighbors ordered by their distances to a query point. The experiments on both real and synthetic data sets show that the query algorithm based on the bounded k-d tree is computationally more efficient than some traditional algorithms. In addition, a method to fast and uniformly dividing spherical data is introduced.Curvatures and Darboux frames are used heavily in tasks such as registration and segmentation. However, it is still challenging to estimate these features from unorganized noised points with accuracy. A method is proposed to calculate these features from a general quadric surface fitted at each point. The TLS3L (total least squares on the three level sets) algorithm is introduced to permit fast and reliable fitting to the noisy input. Formulae about curvatures and three dimensional principal directions of an implicit surface are deduced. The efficiency of the fitting process is analyzed theoretically. Compared with several other methods, the proposed method estimates differential information more reliably.Registration is an important topic of research in aerial photogrammetry, industrial inspection, surface modeling, and so on. Problems of establishing correspondences and improving accuracy in registration are still open. A method called SCR (Signatures, Clusters, and Refinement) is proposed to match surfaces represented by unorganized points. The method establishes correspondences by matching neighborhood signatures, estimates initial rigid transformation according to clusters of the Euclidean group SE(3), and refines initial transformation parameters iteratively. The introduced neighborhood signatures encode the shape variance information near a point into vectors, and thus facilitate the usage of data structures, k-d trees for example, in establishing correspondences. Based on the clustering characteristic of rigid transformations computed from each correspondence point pair, the PV (Parameter Voting) method is proposed to estimate initial rigid transformation. In the refinement of initial transformation parameters, the ICS (Iterative Corresponding Surface) method is introduced by taking surface patches instead of coordinate points as geometric elements to be registered.Segmentation is a necessary intermediate process in tasks such as object recognition, autonomous navigation, reverse engineering, and so on. The segmentation problem is still unsolved even for simple scenes containing only polyhedral objects. Analyses of differential characteristics near borders between different surfaces indicate that the segmentation task is difficult to be accomplished by only comparing differences of normal vectors or curvatures between a point and its neighbors. A method called GCRR (Gaussian map, Clustering, region Recognition, and region Rectification) is proposed to segment unorganized points, in which the CMS (Cell Mean Shift) algorithm is used to cluster the Gaussian image of the input data. Based on the singular value decomposition, the dimensional analysis is introduced to classify clusters on the Gaussian sphere into point-, curve-, and area-form clusters, each of which is the Gaussian image of a set of points in R3. An orientation analysis of the Gaussian map to area-form clusters is applied to identify hyperbolic and elliptic regions. A signed point-to-plane distance function is used to identify points of convex and concave regions. A region rectification process is carried out to eliminate regions produced by errors in normal estimation near borders. Segmentation results of several real as well as synthetic point clouds, together with complexity analyses, are presented.At last, a digital modeling system called MIMDFM (Measurment, Integrated Modeling, and Design For Manufacturing of complex parts) is developed and the proposed algorithms have been implemented with programming in C++. The validity of the system has been verified in the process of building the digital models of serval real parts.更多还原