基于点云数据的逆向工程技术研究综述*

王鑫龙 孙文磊 张建杰 黄 勇 黄海博

(新疆大学机械工程学院，新疆 乌鲁木齐 830047)

随着现代制造业全球化与市场化，全球制造业市场竞争愈加激烈，产品生命周期越来越短，致使制造业企业不断追逐CAD/CAE/CAM/CNC等新技术，来提高产品设计与制造效率，缩短产品研发周期，保持企业竞争力。在企业不断追求产品快速设计与研发的过程中，逆向工程便应运而生。逆向工程，也称反求工程、反向工程和逆向设计，是以现有的先进产品设备的实物、样件、软件或影像作为研究对象，通过合适的测量方法获取实物或模型的离散点云数据，继而应用图形图像学、现代设计方法学、材料科学以及先进制造技术等学科知识进行点云数据处理、模型重构、系统性的分析、研究掌握其关键技术，从而演绎并得出该产品的几何模型、材料特性、组织结构、工艺路线、功能特性及技术规格等设计要素，进而研发制造出更为先进的同类产品的一系列技术和过程的总称[1-4]。逆向工程流程：通过测量获得产品的点云数据，然后利用专门的逆向工程软件或集成了逆向模块的正向CAD软件中进行点云理数据预处理、模型重构以及模型检测来生成高度还原的原产品CAD模型，而后在正向CAD软件中对重构CAD模型进行参数化修改及优化设计，最后利用优化后的CAD数据进行快速原型制造或快速模具制造完成新产品或模具的开发与制造。与传统正向工程相比，逆向工程具有更短的产品设计周期、更成熟的产品设计和更好的传承性等特点，可大大缩短产品研发制造周期，被广泛应用于产品的研发和改型设计、艺术品和考古文物等物体的仿制及修复、工业和地理信息测量等领域。本文就逆向工程中的点云数据测量、数据预处理和模型重建技术的研究做如下综述。

1 点云数据测量

点云数据测量是指通过测量设备把产品表面形状转化成离散的几何坐标数据，其实质就是将实物模型数字化，用点云数据来表示实物模型的几何特性。点云数据的精度直接影响到反求建模品质，获得与原始模型充分接近的点云数据是测量的关键。点云数据的测量根据获取方式不同分为接触式和非接触式两大类。接触式具有精度高、测量条件要求低、速度慢、不适应软质材料等特点。非接触式具有方便快捷、适应性强、精度较低、对测量环境要求高等特点。随着计算机、传感器和光电子等技术的迅猛发展，使得点云数据的测量技术得到空前的进步。如：基于主动式全景视觉传感器的全景点云数据获取设备[5]；基于数字散斑相关方法的视觉变形测量技术；获取结构信息的层切图像法等。图1较为详细地对点云数据测量方法进行了分类。

2 点云数据预处理

2.1 拓扑关系的建立

点云具有三维空间分布的不均匀性特点，所以本身不存在严格的数学表达模型，为对点云数据进行处理，首先就要建立点云的拓扑关系。建立点云拓扑关系最大的作用是加快搜寻速度，综合而言可分为两类：(1)Delaunay三角剖分法，包括利用点云Voronoi图进行三角剖分法和利用投影域的映射三角剖分法。(2)空间分块策略法，包括八叉树法、栅格法和k-dtree(k-dimensional tree)等。

对于建立拓扑关系后的点云数据处理，搜索操作是诸多点云数据处理方法的核心，k近邻域索引是搜索操作的典范。k近邻域索引是求出候选点的k个最近欧氏距离点，以构成点云的拓扑关系。如何提高k近邻域搜索的速度成为研究的重点与难点。Piegl等研究基于栅格的平面点集k近邻域搜索方法，该方法具有很好的适用性[6]。赵伟玲提出了一种改进的散乱点云k近邻快速搜索算法，把计算的范围扩大了一圈，只关心与k大小临近的三层数据，在保证准确性的前提下提高了搜索速度[7]。安雁艳等提出二次栅格化和优化拓展方向的快速k近邻搜索方法，该方法减小了搜索范围，提高搜索速率[8]。刘增义等利用k-d树建立散乱点云的空间拓扑关系,计算出每个数据点的k邻域。通过数据点k邻域构成的最小二乘平面的投影点角度差,根据角度差的最大值来判断该点是否为边界点，此法能够准确获取散乱点云上任意指定目标特征的边界[9]。

2.2 多视点云数据拼合

在测量过程中，由于受测量技术、周围环境、物体几何形状、定位以及夹具等原因的限制，通常需要对物体进行多视角测量，然后将不同视角的点云拼合成一个表达完整实物的点云。多视点云数据拼合的实质是寻求不同点云数据间的坐标转换，拼合方法有点位法、固定球法、优化匹配法、特征匹配法以及辅助装置法。点位法是采用对应的至少3个线性无关坐标点进行匹配对齐[10]。Sameh等提出的固定球法，即将点云数据三角化处理后进行球面拟合[11]。最优匹配法的基本思想是通过优化理论寻求目标数据与原始数据之间坐标转换矩阵，代表性的是基于迭代最近点(iterative closest point，ICP)算法的点云数据拼接对齐。由于ICP算法效率低、对初始值要求高、容易陷入局部收敛等缺陷，研究人员就改进ICP算法做了大量研究[12-13]。特征匹配法是通过提取点云数据的局部特征，来作为拼合的控制采样点，从而完成多视点云数据的拼合。Meng等提出了基于不变特征的点云数据拼接，该方法具有较高的定位速度和较小的定位误差速度[14]。吴琼提出利用采样点处曲率、采样点与邻域质心连线与法线的夹角、以采样点为顶点的三角形边长寻找全等三元素进行多视点云数据拼合的方法[15]。辅助装置法是利用外部精密机械设备与测量设备组合起来，形成一个整体的点云测量设备实现多视角的测量，通过辅助装置的运动状态反算出拼合所需的坐标变换矩阵，从而实现多视点云数据的拼合。Tamas等将具有6个自由度旋转平台和坐标扫描仪组合，通过设备旋转获得被测物体的整体点云数据，根据预先设定的角度与距离变化，实现点云数据的拼接[16]。张旭等通过提取辅助测量装置的位姿特征进行多视点云数据拼合，该方法可以匀化测量误差，弱化噪声的影响，简化匹配计算，但对于辅助装置的定位和组合还有待优化[17]。赖文敬等利用外部机械装置的运动求解多视点云数据拼合的旋转平移矩阵[18]。

2.3 滤波去噪

点云噪声主要是由于扫描的过程中外部环境、人为因素以及仪器本身等原因造成的，是不可避免的。点云数据中的噪声严重影响三维模型重构的精度和曲面拟合的质量，因此要对点云进行滤波处理，删除噪声点。滤波的实质是修正替代，去噪的实质是删除。对于有序点云常用滤波去噪方法有直接观察法、曲线检查法、高斯、平均、中值滤波法等。对于散乱点云数据常用的滤波去噪方法有双边滤波法、角度阈值、弦高差、平均曲率法、随机滤波法、小波包分析、自适应滤波、三边滤波法等。各滤波去噪方法的原理不同，各有优缺点，实际使用时，可根据点云质量和后序建模要求灵活选择或组合选用上述滤波方法。

虽然上述滤波去噪方法已较为成熟，但是目前还没有一个高效、通用、简洁的滤波去噪方法，对此不少学者做了大量研究。王科俊等结合滤波窗口在按行滑动时相邻窗口之间的递归关系和按列移动时相邻两行对应的辅助数组之间的递归关系,设计出了高效的均值滤波算法，减少了冗余操作[19]。高志国等以实际数据点到参考面的高程值作为判据，实现点云的滤波去噪，该方法能够适用各种特征，但滤波范围、时效还有待提高[20]。吴琼采用对点云模型的不同曲率特征区域采用不同滤波策略的滤波算法，对采样点进行各向异性滤波去噪[15]。陈崇帮提出了基于最优邻域的点云降噪算法，重新定义了降噪算法中的空间权重函数，从而加速点云进行的多边滤波去噪[21]。Clarenz等设计了一个离散的各向异性扩散的偏微分方程的各向异性点云数据滤波算法，通过解这个方程实现点云数据滤波[22]。

2.4 孔洞修复

由于测量设备景深、测量原理以及零件自身形状等因素的影响，点云数据中往往会出现孔洞的现象。孔洞的存在将直接影响到其后续的模型重建、实体化、快速成型等处理，因此需要对点云数据的孔洞修补。李绪武提出了通过多幅二维图片对三维点云数据进行缺陷修补的方法，可以准确、高效地完成点云孔洞区域的修补[1]。Cecile等以三角网格为基础通过计算径向基函数的参数化从新划分网格实现孔洞的修复，对间隙、重叠、T形接头和简单的孔有较好的修复效果[23]。程效军等提出一种采用推进式逐层求解法及最小凸包法的多值曲面修复的孔洞修复方法，该方法实现孔洞边界自动提取，能克服投影重叠和噪声干扰，精确提取孔洞边界[24]。Carr等采用基于径向基函数的隐式曲面实现孔洞修复，获得了良好的效果[25]。晏海平提出一种结合隐式曲面和最速下降法的孔洞修复方法，对孔洞边界的均匀化处理和孔洞的修复取得很好的效果[26]。Pernot在孔洞修复最小邻域范围内根据曲率变化率插入曲率网格进行孔洞修复，适用于孔洞较简单的点云[27]。谢倩茹等先利用波前法对孔洞进行初始修复，然后运用网格优化技术对修补孔洞网格顶点进行调整来实现孔洞的修复，修复后孔洞与周围网格自然过渡[28]。

综上所述，对点云孔洞进行修复大致思路分为两类：(1)通过另一角度或重复扫描的点云数据进行点云数据的孔洞修复，可以准确、高效的修复因测量等原因造成的孔洞。(2)利用孔洞边界点，通过径向基函数、B样条曲面拟合、隐式曲面以及曲率变化率插值等方法对孔洞边界点进行插值或拟合，实现孔洞的修复，可以修复任何原因所造成的点云孔洞，但其抗噪性和光滑性是该类方法的难点。

2.5 数据精简

由于点云数据的密集及散乱无序，在很大程度上增加了计算机处理的时间复杂度和空间复杂度，而且过于密集的点云数据还会影响后续重建曲面的光顺性。因此，对点云数据的精简是逆向工程数据预处理中的一个重要的步骤[29]。数据精简的原理是只对原始点云中的部分点进行了删除，而不产生新点。不同的点云数据采用不同的精简方法：针对散乱的点云采用包围盒法、均匀网格法、随机采样和曲率采样等；对于扫描线式点云采用最小距离法、角度偏差法和弦高差等；对于网格化点云采用等间距缩减、倍率缩减、顶点聚类、弦高差等；对于多边形点云采用等分布密度法、包围盒法等。

3 点云数据的模型重构

3.1 特征提取

点云特征是指能够表达实物模型信息的少量关键点或者由这些关键点连接成的曲线，如何快速、准确、自动完成特征提取成为了点云数据模型重构的研究核心之一。

柯映林等通过研究线性时间复杂度的空间分割和空间拓扑构型推理算法实现点云数据内外边界的提取，能较好地保持原来点云的特征，该方法稳定性好、效率及精度高[30]。Mian等提出了利用关键点质量排名来提取局部最优特征的方法，在投影的PCA子空间中提取特征点然后匹配找到点云中对应对象，该方法特征点和多尺度特征提取超过95%[31]。王晋疆等提出了基于点签名的特征点提取方法，该方法可以快速有效地提取到特征点，具有一定的抗噪性，但时间效率较低[32]。晏海平以采样点及其K邻域作拟合微切平面，将其向微切平面投影，根据邻域点集在采样点处的场力大小之和可以表示点集的平均作用来识别点云的边界特征点[26]。Lowe基于局部不变量描述符方法，提出了尺度不变特征转换(scale-invariant feature transform，SIFT)算法的特征提取方法，有效解决了由于部分遮挡、旋转缩放、仿射变换、尺度变换等引起点云变形等问题[33]。Pang等运用局部表面拟合多项式对点云进行局部曲面拟合，计算点云中每个采样点的主曲率和主方向，利用主曲率大小提取特征点[34]。随后很多研究人员对SIFT算法作出了改进，提高了SIFT算法的效率。程效军等通过切片分层将空间点云转换为不同层的平面切片点云，将切片点云转换成二值图像提取其轮廓特征点，基于轮廓特征点进行层与层之间的网格重构从而建立整个物体的模型[35]。刘立强根据点云的几何分布特性，通过计算重心点距与最远点距的大小进行边界提取，对于曲率变化较大的点云效果不佳[36]。顾园园等通过最大角度差进而识别出边界特征点的边界自动提取算法。该算法能够快速有效地识别出孔洞等边界特征点，但对噪声敏感度较高[37]。Pauly等采用变化的局部邻域半径，多尺度地对包含噪声信号的点云数据进行主成分计算来判定特征点[38]。高翔等对采样后的点云数据，建立k-d树进行索引。对采样点在搜索邻域内的邻近点建立最小二乘微切平面，利用投影到微切平面局部坐标系内的邻近点分布特性，判断边界特征点及其匹配特征，在不影响匹配效果的前提下，其方法可显著提高复杂形面边界特征的提取效率[39]。

综上所述，提取点云数据的特征通常利用点云数据本身或将点云数据投影到二维平面后的特征参数，如法向量、曲率、重心、点到邻域点的距离等，然后根据某种算法利用一种或多种特征参数的突变来提取点云数据的特征，然而突变的阈值缺乏统一、合适及准确的定义，特征提取的精度、效率及自动化程度仍有待进一步提高。

3.2 曲面重建

曲面重建是逆向工程中最复杂、最关键的步骤，就是运用相关的方法对预处理后的点云数据进行曲线曲面重建，将离散的测量数据重建出连续变化的曲面，并最终生成数字化模型，是进行后续结构设计、产品性能分析、生产制造等过程的基础，良好光顺性和高精度是重建曲面的难点。选取合适的方法提取点云数据的特征、拟合曲线曲面与编辑修改等对曲面重建至关重要。曲面重建的方法：依据点云数据与重建曲面之间关系，分为逼近法和插值法两大类；依据重建曲面的表达方式，分为网格重建、参数重建、隐式重建、变形重建和细分重建等；依据是否需要特征提取，分为非特征曲面重建与特征提取曲面重建，特征建模方法可以分为特征模板匹配法、特征元提取法和直接基于点云数据的特征处理方法，非特征曲面重建法核心是依据获取的主方向通过数值积分的方式对曲率线进行追踪；依据过程不同，分为直接通过点云数据构建曲面和通过含拓扑关系的点云数据构建曲面；依据重建曲面的表示形式，分为多项式插值法、最小能量法、NURBS法、Coons曲面、B样条曲面和BP神经网络法等。

4 逆向工程技术展望

逆向工程技术经过几十年的发展日趋成熟并得到广泛应用，综合国内外的研究现状，笔者认为逆向工程技术还需要在以下几个方面进行发展和完善:

(1)测量系统的柔性化和高效化。通过增加了测量系统的精度和可靠性，研究多视点云数据实时、自动拼合技术，构建具有高度柔性和适应性的点云数据测量系统。

(2)完善大型零部件的逆向工程技术。在大型零部件的点云数据的拼接在效率和精度、曲线拟合精度和拟合曲线光顺性仍有待进一步提高。

(3)数据预处理技术通用化。点云数据的预处理技术的研究中不同的研究人员开展研究的角度不同，切入点也不同，各个算法在精确度和速度方面还都有待提高，算法的通用性和相似性等问题还需要进一步的研究。适应任何数据对象的点云拓扑关系算法还没有得到完全有效的解决。对于散乱点云去噪，目前还没有一个通用、快速、简洁的方法。对于三维散乱点云，仍需研究一种既快速又能保持点云特征的点云精简方法。对点云数据的处理自动化程度还不够高，对处理过程中各类阈值的选取缺乏相应的标准。

(4)逆向工程技术集成化。通过对点云数据的柔性化采集、通用化预处理、自动化特征提取、智能化曲面重建以及与其他先进制造系统的集成等技术的研究，提高各技术和软件之间的集成化，提高逆向建模的自动化程度和通用性，开发出集点云数据采集、预处理、模型重建和正向设计等功能于一身的逆向工程系统。

[1]李绪武.基于三维扫描工程建模的面部整形点云数据处理方法研究[D].重庆:重庆大学,2013:2-5.

[2] 陈龙,张军洋,李赫林，等.面向材料反求的非均质体参数化模型构建[J].机械工程学报,2014,50(23):156-164.

[3]张德强,牛兴林,程杰,等. 汽车散热盖模具点云数据曲面逆向重构技术研究[J]. 机械设计与制造,2014(7):243-245.

[4]林祖胜. 基于CMM逆向工程的摆线齿轮磨损检测研究与应用[J]. 制造技术与机床,2016(4):94-97.

[5] 徐海涛,周静恺,林璐璐，等.基于ASODVS的全景点云数据获取技术的研究[J].计算机测量与控制,2014,22(7):2284-2287.

[6] Piegl Les A, Tiller Wayne. Algorithm for finding all k nearest neighbors[J].CAD Computer Aided Design,2002,34(2):167-172.

[7] 赵伟玲.三维点云的数据预处理和圆提取算法研究[D].哈尔滨:哈尔滨工程大学,2008:15-28.

[8] 安雁艳,杨秋翔,冯欣悦，等.点云数据的k近邻快速建立改进算法[J].计算机工程与设计,2014,35(12):4228-4232.

[9]刘增艺,江开勇,林俊义. 散乱点云特征边缘交互提取[J]. 计算机工程与应用,2016(6):186-190.

[10] 曹照均,李尚平,李冰.多基准下多视点云拼接对齐方法的研究[J].机械设计与制造,2014(4):54-56.

[11] Yamany Sameh M, Farag Aly A. Free-form surface registration using surface signatures[C]. Proceedings of the IEEE International Conference on Computer Vision,1999:1098-1104.

[12] 钟莹,张蒙.基于改进ICP算法的点云自动配准技术[J].控制工程,2014,21(1):37-40.

[13] Hans Martin Kjer, Jakob Wilm. Evaluation of surface registration algorithms for PET motion correction[D]. Denmark: Technical University of Denmark,2010:39-69.

[14] An Meng,Jiang Zhiguo, Zhao Danpei. High speed robust image registration and localization using optimized algorithm and its performances evaluation[J] Journal of Systems Engineering and Electronics,2010,21(3):520-526.

[15] 吴琼.三维点云模型数据的滤波算法与配准算法研究[D].秦皇岛:燕山大学,2014:25-31.

[16] Vardy Tamas, Martin Ralph R, Cox Jordan. Reverse engineering of geometric models An-introduction[J].CAD Computer Aided Design,1997,29(4):255-268.

[17] 张旭,张冉,张学昌.基于辅助装置的多视点云精确配准方法[J].计算机集成制造系统,2014,20(5):1029-1034.

[18] 赖文敬,鲍鸿,白玉磊，等.叶片三维轮廓测量点云数据高精度多角度融合[J].航空动力学报,2015,30(3):665-671.

[19] 王科俊,熊新炎,任桢.高效均值滤波算法[J].计算机应用研究,2010,27(2):434-438.

[20] 高志国,李长辉,宋杨.基于移动窗口的最小二乘曲面拟合算法及其应用[J].工程勘察,2014,42(11):60-63.

[21] 陈崇帮.基于最优领域的点云降噪算法研究[D].株洲:湖南工业大学,2014:25-38.

[22] Clarenz u, Rumpf M, Telea A. Fairing of point based surfaces[C].Computer Graphics International Conference,2004: 600-603.

[23] Piret Cecile, Remacle Jean Francois, Marchandise Emilie, et al. CAD and mesh repair with radial basis functions[C].Proc Int meshing Roundtable IMR,2011:419-436.

[24] 程效军,何桂珍.适用于多值曲面修复的空洞边界提取方法及应用[J].测绘学报,2012,41(6):831-837.

[25] Carr J C, Beatson R K R, Cherrie J B, et al. Reconstruction and representation of 3D objects with radial basis functions[C].Proc Annu Conf Graph Interact Tech SIGGRAPH,2001:67-76.

[26] 晏海平.散乱点云边界提取及孔洞修复算法研究[D].南昌:南昌大学,2014:17-43.

[27] Pernot Jean Philippe, Moraru George, Veron Philippe. Filling holes in meshes using a mechanical model to simulate the curvature variation minimization[J].Computer and Graphics， 2006,30(6):892-902.

[28] 谢倩茹,耿国华.三维模型孔洞修补方法的研究[J].计算机应用研究,2013,30(10): 3175-3177.

[29] Chen lei, Jiang Zhuangde, Li Bing, et al.Data reduction based on bi-directional point cloud slicing for reverse engineering[C]. Key Engineering Materials,2010:492-496.

[30] 柯映林,范树迁.基于点云的边界特征直接提取技术[J].机械工程学报,2004,40(9):116-120.

[31] Mian A, Bennamoun M, Owens R. On the repeatability and quality of keypoints for local feature-based 3D object retrieval from cluttered scenes[J]. Journal of Computer Vision, 2010, 89(2-3): 348-361.

[32] 王晋疆,陈阳,田庆国，等.一种基于点签名的散乱点云特征点检测方法[J].计算机工程,2014,10(7):174-178.

[33] Lowe David G. Distinctive image features from scale-invariant keypoints[J]. Journal of Computer Vision, 2004, 60(2): 91-110.

[34] Pang X F,Pang M Y,Song Z. Extracting feature curves on point Sets[J].International Journal of information Engineering and Electronic Bussiness,2011,3(3):1-7.

[35] 程效军,方芳.基于形态学的散乱点云轮廓特征线提取[J].同济大学学报,2014,42(11):1738-1743.

[36] 刘立强.散乱点云数据处理相关算法的研究[D].西安:西北大学,2010:29-38.

[37] 顾园园,姜晓峰,张量.曲面重构中带孔洞点云数据的边界提取算法[J].苏州大学学报,2008,28(2):56-61.

[38] Pauly Mark, Keiser Richard, Gross Markus. Multi-scale feature extraction on point-sampled surfaces[C].Computer Graphics Forum,2003,22(3):281-289.

[39]高翔,王华,陈关龙. 面向复杂形面匹配的边界特征提取方法[J]. 哈尔滨工业大学学报,2016(7):46-51.