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

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


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

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

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