逆向工程中散乱点云预处理相关算法研究

摘要

逆向工程技术是近年来发展起来的一种新的工程设计技术，以其独特的优势逐渐渗透到了各类产品行业，成为现代产品设计的主流技术。逆向工程主要包括三个部分：三维数据测量、数据预处理和模型重建。其中，数据预处理是逆向工程设计中的关键环节，其处理的效果和效率直接影响模型重建的精度和效率。本文针对散乱点云数据，主要研究了数据预处理中K近邻点的搜索、边界特征点的提取和数据精简算法，对提高三维重建的效率和质量具有非常重要的意义。
　　 本文充分调研和深入分析了现有算法，并对其中存在的问题加以改进，以期能够为三维重建提供更准确的特征信息。本文完成的工作主要有以下几个方面：
　　 (1)分析了两种常用的散乱点云几何拓扑关系的组织结构：八叉树和K-D树，并给出了八义树的相关算法。在数据的组织结构上，本文使用八叉树划分法，并根据立方体内所包含的最大数据点个数来决定该立方体是否继续进行划分，可有效避免基于边长的八叉树划分法中边长的不易确定性。
　　 (2)研究了两大类典型的K近邻点搜索算法，讨论了其搜索的准确性和完整性，并深入分析了搜索过程中的各种无效搜索情形。在此基础上，设计了一种基于八义树结构的剪枝式分层快速搜索算法，其特点是既能通过分层搜索确保搜索的准确性和完整性，又能通过剪枝策略提高搜索效率。实验表明，本文算法与全局搜索算法和仅分层搜索算法相比，搜索效率有显著性的提高。
　　 (3)在研究了几类典型的边界点提取算法各自优缺点的基础上，针对现有算法计算量较大和易产生误判的问题进行改进，通过对采样点的K近邻点的分布特性进行深入分析，设计了两种散乱点云边界点的快速提取算法：基于拉力的作用与基于参考平面的算法。实验表明，这两种算法都能快速、有效地提取散乱点云的边界点，在提取的精度和效率上优于文献算法。并通过理论上的分析来说明本文算法能够有效地简化计算过程，在不影响提取精度的前提下加快了提取的速度。
　　 (4)研究了几种常用的散乱点云精简算法，针对部分算法未考虑几何特征点和边界点的丢失问题，设计了一种曲率精简算法。实验表明，算法能够较好地保留曲面的几何特征点，并在平坦区域删除较多的点，同时对边界点进行了保护。与相关文献算法相比，本文算法能较好地解决阈值的设定问题。