文档介绍：华中科技大学博士学位论文
摘要
面对数字建模中数以万计的测量数据,最近点查询、正交区域查询、球域查询等基本
操作对数据处理算法的计算效率有很大影响。为了提高这些操作的效率,定义了有界 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)方法。
数据分割是物体识别、自动导航、反求工程等任务中的必要处理步骤。即使是对仅仅
包含多面体的场景,分割问题也没有完全解决。本文分析了不同边界处的微分特性,指出
I
华中科技大学博士学位论文
仅依靠一点与其相邻点的法矢或曲率的变化难以完成数据分割任务。提出了一种散乱点分
割方法 GCRR(Gaussian map, Clustering, region Recognition, and region Rectification)。该方
法采用 CMS(cell mean shift)算法对输入数据的高斯图进行聚类。提出了基于奇异值分解
的维数分析方法将高斯球上的聚类分成点形、线形和面形的聚类。每个聚类对应 R3 中的一
个点集。通过对应面形聚类的高斯映射的定向分析,识别了双曲面和椭圆面。采用点-平
面距离函数区分了凸面和凹面。通过区域调整消除了边界附近因法矢估计误差而产生的区
域。给出了 GCRR 方法的复杂度分析、在仿真和实测数据上的实验结果。
最后,开发了数字建模系统 MIMDFM(Measurment, Integrated Modeling, and Design For
Manufacturing plex parts),对所提出的理论和方法进行了编程实现,通过几个实际
零件的数字建模过程验证了该系统的有效性。
关键词: 数字建模; 空间查询; 微分信息估计; 拼合; 分割
II
华中科技大学博士学位论文
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 s