摘  要： 為了提高實體反求的效率，提出一種點云簡化方法。該方法通過建立點云的柵格化拓撲關系，有效地收集每個測量點的鄰域點，并在鄰域內建立局部坐標系。同時，擬合局部拋物面估算各個測量點的曲率值，并根據曲率變化收集形狀特征點。最后，依據鄰域內形狀特征點的分布狀況，對點云實施簡化。該簡化方法充分地保留了原始點云的形狀特征，同時刪除了大量的冗余點，具有一定的先進性，為反求工程的曲面重構提供了良好的基礎。
關鍵詞： 反求工程；點云；曲率；特征點提取

　隨著反求工程技術的發展，物體表面數據的采集方法越來越多樣化，在引入了激光及其他光源技術后，三維測量設備得到了長足的進步，但其測量數據過于龐大，影響了后續的曲面重構處理的速度與效率，因此對點云進行簡化非常必要。近年來，人們對三維數據的精簡進行了大量地研究，CHEN Y H[1]等人將點云數據三角網格化，通過一種向量加權算法來減少三角形數量，達到點云簡化的目的；Fujimoto和Kariya[2]在1993年提出一種保證減少數據點的誤差處于給定公差范圍內的方法；Hoppe[3]和Eck[4]等人采用的PM(Progressive Meshes)算法根據子區域的連續性來簡化點云；張麗艷[5]在用Riemann圖建立數據點間鄰近關系的基礎上，提出按簡化后點的個數、點的密度閾值以及刪除一點引起的法向誤差的閾值三種準則對點云進行簡化。以上幾種方法對于表面不復雜、曲率變化不大的點云數據精簡很有效，但對于曲率變化大、附加特征多的表面點云數據難以直接應用。針對以上方法的不足，本文提出一種新的數據精簡方法。該方法根據物體形狀盡可能多地保留了特征區域的數據，克服了數據表面曲率變化大對實物反求造成的影響，同時又刪除了大量冗余數據，提高了點云簡化的效率。
1 點云拓撲關系的建立
　本文以沒有任何拓撲信息的散亂點集為處理對象，首先建立散亂點的拓撲鄰近關系，為避免在整個點集中尋找每個測點的K-近鄰(K為測量點的鄰域點數，根據后續鄰域曲面擬合的一般取為10～20)。具體方法是：采用包圍盒法[6]中空間柵格的劃分策略，首先根據測點分布，形成一個與坐標軸平行的長方體包圍盒，并將包圍盒沿x、y、z軸劃分成m×n×l個小立方體柵格，柵格寬度λ可根據實際點云的分布情況進行設置，一般設為點云分布密度的K倍。點云分布密度采用如下方法估算：在點云中隨機取出N點，計算離點Pi最近點的距離di，則分布密度為：；再根據每一個數據點的x、y、z坐標值將該數據點的序號追加到相應的柵格中，通過設置一個動態鏈表，記錄數據點所在的坐標值和該點所在柵格的索引位置，從而建立起散亂點的空間拓撲關系，完成點云數據的空間柵格劃分。每個測量點的K鄰近可以由其所在柵格及其鄰近的上、下、左、右、前、后共27個立方體柵格中查找，根據其空間距離大小順序將鄰近點的動態鏈表索引號存儲在與測量點對應的數組中。從而建立起每個數據點的鄰域關系。
2 局部基面參數化
2.1 擬合微切平面
　用局部的擬合曲面來估算曲率，首先需要對點云進行參數化。由于點云是散亂分布的，沒有一定的特殊模式排列，所以點云的參數化十分困難。本文提出了一種簡單的參數化方法，即建立局部微切平面，把散亂的點云投影到微切平面上，利用投影點來建立坐標系。微切平面方程可由平面的法矢量和平面上的一點表示，即：


　其中，K1、m1分別表示最小曲率及其方向，K2、m2分別表示最大曲率及其方向，K為高斯曲率，H為平均曲率。
4 點云簡化
　一般點云簡化的基本要求是既能縮減規模、消除冗余的點，又能保持整體形狀、突出關鍵特征。傳統的點云簡化算法往往依據點云表面數據的平坦程度來設置一個閾值，以此來決定刪除或保留的點。這種方法雖然對點云的數量進行了一定量的簡化，但會削弱特征，引起整個形狀改變，且會在某些曲面形狀變化較緩同時又具有重要工程意義的區域(如平面與曲面的過渡區)造成過度簡化。因此，簡化過程最好能減少因簡化導致的形狀缺失及形狀改變，盡可能地保留其特征細節。
　為此，本文首先在每個測量點的鄰域內擬合拋物面，估算出每一個測量點的曲率，然后對曲面過渡區、特征棱線和高曲率區的特征區數據點進行標記。特征區數據點即為曲率極值點(測量點的兩個主曲率(K1和K2)中任何一個沿著對應的主方向上為極值)。曲率極值點可以采用如下方法收集：首先為各數據點的平均曲率H設定一個閾值，如果某點的平均曲率大于閾值，則作為候選特征點，實際特征點在候選特征點內產生。只要候選特征點中某一點的兩個主曲率中任何一個沿對應的主方向為極值，那么就可以將該點定義為特征點。選取一候選點X沿最小曲率方向m1，找到左右兩個鄰接點X11、X1r，如果K1(X)≤K(X11)、K1(X)≤K(X1r)(其中，K(X11)、K(X1r)分別為點X11、X1r沿最小曲率方向m1的曲率值)，則該點就是實際的邊界點；否則，沿最大曲率方向m2，找到該點左右兩個鄰接點X21、X2r，若K2(X)≥K(X21)、K2(X)≥K(X2r)，則X也可以作為邊界點。對所有的候選特征點進行以上判斷，就可以收集到特征點集。

　對所收集到的曲率極值點進行平均曲率排序，得出一個曲率均值，然后根據簡化的比例，通過交互對這個曲率均值進行適當調整，調整后的曲率值即作為曲率初始閾值。把大于這個初始曲率閾值的標識為特殊點，然后統計各個測量點在其K鄰域內特殊點所占比率，給定一個初始簡化距離閾值，用初始簡化距離閾值除以特殊點密度與1的差的絕對值就可以確定這個特定測量點鄰域的簡化距離閾值。最后按簡化距離閾值對數據點進行簡化，即將鄰域點中小于這個簡化距離的點刪除。
5 應用實例
　為了評估本文算法的性能，在Pentium4、1.60 GHz、512 MB內存計算機上運行，用C++語言在VC++6編譯器上結合OpenGL庫分別對零件1及零件2的點云模型進行了簡化處理，圖2、圖3為點云簡化的效果圖，表1為計算結果。圖2、圖3均突出了特征點的提取，保證了曲率變化較大區域的保留，這說明在表達形狀方面，本文的簡化算法具有一定的準確性。圖2(a)為零件1的原始點云圖，共有37 320個點，圖2(b)為提取的特征點，共有8 497個，圖2(c)為簡化后點云，共有22 134個，簡化率為40%；圖3(a)為零件2原始點云，共有67 874個點，圖3(b)為提取的特征點，共有7 934個，圖3(c)為簡化后點云，共有37 653個，簡化率為44%。由圖2、圖3可以看出，簡化點云不存在簡化后點云的局部過密或局部過稀的情況，而且依然保留了原始點云的基本特征，沒有出現形狀的缺失，對于曲率變化較大區域特征區域表達依然清楚。由表1可看出，對比參考文獻[5]，本文簡化的方法在精確度方面具有一定的優勢。

　本文提出了一種點云簡化算法，該方法首先采用包圍盒法建立點云的空間拓撲關系；然后在此基礎上建立點云的鄰域，并在鄰域內擬合切平面，利用鄰域點在切平面上的投影點建立局部坐標；之后結合局部坐標擬合局部拋物面并計算曲率值，依據曲率變化的特征收集特征點，并依據特征點在各個測量點鄰域內的分布情況對點云進行簡化。該方法針對點云表面的形狀特征，有選擇性地對點云進行了簡化，在曲率較大或尖銳棱邊處極大地保留了點云的原始特征，使得最終的點云簡化不會造成形狀特征的缺失，同時又刪除了大量的冗余數據，有效地對原始點云進行了精簡。應用實例表明，本文提出的算法具有較高的效率，達到了預期的效果。
參考文獻
[1] CHEN Y H， NG C T， WANG Y Z. Data reduction in integrated reverse engineering and rapid prototyping [J]. International Journal of Computer Integrated Manufacturing， 1999，12(2)：97-103.
[2] FUJIMOTO M， KARIYA K. An improved method for digitized data reduction for computer integrated manufacturing[C]. International Conference on Industrial Electronics Control Instrumentation and Automation， 1992：896-901.
[3] HOPPE H. Progressive meshes[J]. Computer Graphics， 1996， 30：99-108.
[4] ECK M， DE D T， DUCHANP T. Multiresolution analysis of arbitrary meshes[C]. Proceeding of SIGGRAPH Computer Graphics， 1995：82-90.
[5] 張麗艷，周儒榮，蔡煒斌，等.海量測量數據簡化技術研究[J].計算機輔助設計與圖形學學報，2001，11(13)：1019-1023.
[6] SUN W， BRADLEY C， ZHANG Y F， et al. Cloud data modeling employing a unified， non-redundant triangular mesh [J]. Computer Aided Design， 2001，33(3)：183-193.
[7] 胡鑫，習俊通，金燁.反求工程中散亂點云數據的自動分割與曲面重構[J].上海交通大學學報，2004，38(1)：62-65.
[8] 李江雄，柯映林.基于特征的復雜曲面反求建模技術研究[J].機械工程學報，2000，36(5)：18-25.
[9] 朱心雄.自由曲線曲面造型技術[M].北京：科學出版社，2000.