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

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


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

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

　本文提出了一種點(diǎ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è)測量點(diǎn)鄰域內(nèi)的分布情況對點(diǎn)云進(jìn)行簡化。該方法針對點(diǎn)云表面的形狀特征，有選擇性地對點(diǎn)云進(jìn)行了簡化，在曲率較大或尖銳棱邊處極大地保留了點(diǎn)云的原始特征，使得最終的點(diǎn)云簡化不會造成形狀特征的缺失，同時(shí)又刪除了大量的冗余數(shù)據(jù)，有效地對原始點(diǎn)云進(jì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] 張麗艷，周儒榮，蔡煒斌，等.海量測量數(shù)據(jù)簡化技術(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ù)的自動分割與曲面重構(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.