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

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


　其中,，K1,、m1分別表示最小曲率及其方向，K2,、m2分別表示最大曲率及其方向,，K為高斯曲率，H為平均曲率,。
4 點云簡化
　一般點云簡化的基本要求是既能縮減規(guī)模,、消除冗余的點,，又能保持整體形狀、突出關(guān)鍵特征,。傳統(tǒng)的點云簡化算法往往依據(jù)點云表面數(shù)據(jù)的平坦程度來設(shè)置一個閾值,，以此來決定刪除或保留的點。這種方法雖然對點云的數(shù)量進(jìn)行了一定量的簡化,，但會削弱特征,，引起整個形狀改變，且會在某些曲面形狀變化較緩?fù)瑫r又具有重要工程意義的區(qū)域(如平面與曲面的過渡區(qū))造成過度簡化,。因此,，簡化過程最好能減少因簡化導(dǎo)致的形狀缺失及形狀改變，盡可能地保留其特征細(xì)節(jié),。
　為此,，本文首先在每個測量點的鄰域內(nèi)擬合拋物面，估算出每一個測量點的曲率,，然后對曲面過渡區(qū),、特征棱線和高曲率區(qū)的特征區(qū)數(shù)據(jù)點進(jìn)行標(biāo)記。特征區(qū)數(shù)據(jù)點即為曲率極值點(測量點的兩個主曲率(K1和K2)中任何一個沿著對應(yīng)的主方向上為極值),。曲率極值點可以采用如下方法收集：首先為各數(shù)據(jù)點的平均曲率H設(shè)定一個閾值,，如果某點的平均曲率大于閾值，則作為候選特征點,，實際特征點在候選特征點內(nèi)產(chǎn)生,。只要候選特征點中某一點的兩個主曲率中任何一個沿對應(yīng)的主方向為極值，那么就可以將該點定義為特征點,。選取一候選點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也可以作為邊界點,。對所有的候選特征點進(jìn)行以上判斷,，就可以收集到特征點集。

　對所收集到的曲率極值點進(jìn)行平均曲率排序,，得出一個曲率均值，然后根據(jù)簡化的比例,，通過交互對這個曲率均值進(jìn)行適當(dāng)調(diào)整,，調(diào)整后的曲率值即作為曲率初始閾值。把大于這個初始曲率閾值的標(biāo)識為特殊點,，然后統(tǒng)計各個測量點在其K鄰域內(nèi)特殊點所占比率,，給定一個初始簡化距離閾值，用初始簡化距離閾值除以特殊點密度與1的差的絕對值就可以確定這個特定測量點鄰域的簡化距離閾值,。最后按簡化距離閾值對數(shù)據(jù)點進(jìn)行簡化,，即將鄰域點中小于這個簡化距離的點刪除。
5 應(yīng)用實例
　為了評估本文算法的性能,，在Pentium4,、1.60 GHz、512 MB內(nèi)存計算機(jī)上運行,，用C++語言在VC++6編譯器上結(jié)合OpenGL庫分別對零件1及零件2的點云模型進(jìn)行了簡化處理,，圖2、圖3為點云簡化的效果圖,，表1為計算結(jié)果,。圖2、圖3均突出了特征點的提取,，保證了曲率變化較大區(qū)域的保留,，這說明在表達(dá)形狀方面，本文的簡化算法具有一定的準(zhǔn)確性,。圖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可以看出,，簡化點云不存在簡化后點云的局部過密或局部過稀的情況,，而且依然保留了原始點云的基本特征，沒有出現(xiàn)形狀的缺失,，對于曲率變化較大區(qū)域特征區(qū)域表達(dá)依然清楚,。由表1可看出，對比參考文獻(xiàn)[5],，本文簡化的方法在精確度方面具有一定的優(yōu)勢,。

　本文提出了一種點云簡化算法，該方法首先采用包圍盒法建立點云的空間拓?fù)潢P(guān)系,；然后在此基礎(chǔ)上建立點云的鄰域,，并在鄰域內(nèi)擬合切平面，利用鄰域點在切平面上的投影點建立局部坐標(biāo),；之后結(jié)合局部坐標(biāo)擬合局部拋物面并計算曲率值,，依據(jù)曲率變化的特征收集特征點，并依據(jù)特征點在各個測量點鄰域內(nèi)的分布情況對點云進(jìn)行簡化,。該方法針對點云表面的形狀特征,，有選擇性地對點云進(jìn)行了簡化，在曲率較大或尖銳棱邊處極大地保留了點云的原始特征,，使得最終的點云簡化不會造成形狀特征的缺失,，同時又刪除了大量的冗余數(shù)據(jù)，有效地對原始點云進(jìn)行了精簡,。應(yīng)用實例表明,，本文提出的算法具有較高的效率，達(dá)到了預(yù)期的效果,。
參考文獻(xiàn)
[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] 張麗艷，周儒榮,，蔡煒斌,，等.海量測量數(shù)據(jù)簡化技術(shù)研究[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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] 胡鑫，習(xí)俊通,，金燁.反求工程中散亂點云數(shù)據(jù)的自動分割與曲面重構(gòu)[J].上海交通大學(xué)學(xué)報,，2004，38(1)：62-65.
[8] 李江雄,，柯映林.基于特征的復(fù)雜曲面反求建模技術(shù)研究[J].機(jī)械工程學(xué)報,，2000，36(5)：18-25.
[9] 朱心雄.自由曲線曲面造型技術(shù)[M].北京：科學(xué)出版社,，2000.