基于點云數據的逆向工程技術研究綜述*

王鑫龍 孫文磊 張建杰 黃 勇 黃海博

(新疆大學機械工程學院，新疆 烏魯木齊 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 孔洞修復

由于測量設備景深、測量原理以及零件自身形狀等因素的影響，點云數據中往往會出現孔洞的現象?？锥吹拇嬖趯⒅苯佑绊懙狡浜罄m的模型重建、實體化、快速成型等處理，因此需要對點云數據的孔洞修補。李緒武提出了通過多幅二維圖片對三維點云數據進行缺陷修補的方法，可以準確、高效地完成點云孔洞區域的修補[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.