摘  要： 為了提高實(shí)體反求的效率,，提出一種點(diǎn)云簡化方法,。該方法通過建立點(diǎn)云的柵格化拓?fù)潢P(guān)系，有效地收集每個測量點(diǎn)的鄰域點(diǎn),，并在鄰域內(nèi)建立局部坐標(biāo)系,。同時，擬合局部拋物面估算各個測量點(diǎn)的曲率值,，并根據(jù)曲率變化收集形狀特征點(diǎn),。最后,，依據(jù)鄰域內(nèi)形狀特征點(diǎn)的分布狀況，對點(diǎn)云實(shí)施簡化,。該簡化方法充分地保留了原始點(diǎn)云的形狀特征,，同時刪除了大量的冗余點(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)的個數(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ù)據(jù),，提高了點(diǎn)云簡化的效率,。
1 點(diǎn)云拓?fù)潢P(guān)系的建立
　本文以沒有任何拓?fù)湫畔⒌纳y點(diǎn)集為處理對象，首先建立散亂點(diǎn)的拓?fù)溧徑P(guān)系，為避免在整個點(diǎn)集中尋找每個測點(diǎn)的K-近鄰(K為測量點(diǎn)的鄰域點(diǎn)數(shù),，根據(jù)后續(xù)鄰域曲面擬合的一般取為10～20),。具體方法是：采用包圍盒法[6]中空間柵格的劃分策略，首先根據(jù)測點(diǎn)分布,，形成一個與坐標(biāo)軸平行的長方體包圍盒,，并將包圍盒沿x、y,、z軸劃分成m×n×l個小立方體柵格,，柵格寬度λ可根據(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ù)每一個數(shù)據(jù)點(diǎn)的x、y,、z坐標(biāo)值將該數(shù)據(jù)點(diǎn)的序號追加到相應(yīng)的柵格中,，通過設(shè)置一個動態(tài)鏈表，記錄數(shù)據(jù)點(diǎn)所在的坐標(biāo)值和該點(diǎn)所在柵格的索引位置,，從而建立起散亂點(diǎn)的空間拓?fù)潢P(guān)系,，完成點(diǎn)云數(shù)據(jù)的空間柵格劃分。每個測量點(diǎn)的K鄰近可以由其所在柵格及其鄰近的上,、下,、左、右,、前,、后共27個立方體柵格中查找，根據(jù)其空間距離大小順序?qū)⑧徑c(diǎn)的動態(tài)鏈表索引號存儲在與測量點(diǎn)對應(yīng)的數(shù)組中,。從而建立起每個數(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è)置一個閾值,，以此來決定刪除或保留的點(diǎn)。這種方法雖然對點(diǎn)云的數(shù)量進(jìn)行了一定量的簡化,，但會削弱特征,，引起整個形狀改變，且會在某些曲面形狀變化較緩?fù)瑫r又具有重要工程意義的區(qū)域(如平面與曲面的過渡區(qū))造成過度簡化,。因此,，簡化過程最好能減少因簡化導(dǎo)致的形狀缺失及形狀改變，盡可能地保留其特征細(xì)節(jié),。
　為此,，本文首先在每個測量點(diǎn)的鄰域內(nèi)擬合拋物面，估算出每一個測量點(diǎn)的曲率,，然后對曲面過渡區(qū),、特征棱線和高曲率區(qū)的特征區(qū)數(shù)據(jù)點(diǎn)進(jìn)行標(biāo)記。特征區(qū)數(shù)據(jù)點(diǎn)即為曲率極值點(diǎn)(測量點(diǎn)的兩個主曲率(K1和K2)中任何一個沿著對應(yīng)的主方向上為極值),。曲率極值點(diǎn)可以采用如下方法收集：首先為各數(shù)據(jù)點(diǎn)的平均曲率H設(shè)定一個閾值,，如果某點(diǎn)的平均曲率大于閾值，則作為候選特征點(diǎn),，實(shí)際特征點(diǎn)在候選特征點(diǎn)內(nèi)產(chǎn)生,。只要候選特征點(diǎn)中某一點(diǎn)的兩個主曲率中任何一個沿對應(yīng)的主方向?yàn)闃O值，那么就可以將該點(diǎn)定義為特征點(diǎn),。選取一候選點(diǎn)X沿最小曲率方向m1,，找到左右兩個鄰接點(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)左右兩個鄰接點(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)行平均曲率排序,，得出一個曲率均值,，然后根據(jù)簡化的比例，通過交互對這個曲率均值進(jìn)行適當(dāng)調(diào)整,，調(diào)整后的曲率值即作為曲率初始閾值,。把大于這個初始曲率閾值的標(biāo)識為特殊點(diǎn)，然后統(tǒng)計(jì)各個測量點(diǎn)在其K鄰域內(nèi)特殊點(diǎn)所占比率,，給定一個初始簡化距離閾值,，用初始簡化距離閾值除以特殊點(diǎn)密度與1的差的絕對值就可以確定這個特定測量點(diǎn)鄰域的簡化距離閾值,。最后按簡化距離閾值對數(shù)據(jù)點(diǎn)進(jìn)行簡化,，即將鄰域點(diǎn)中小于這個簡化距離的點(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個點(diǎn)，圖2(b)為提取的特征點(diǎn),，共有8 497個,，圖2(c)為簡化后點(diǎn)云，共有22 134個，簡化率為40%,；圖3(a)為零件2原始點(diǎn)云,，共有67 874個點(diǎn)，圖3(b)為提取的特征點(diǎn),，共有7 934個,，圖3(c)為簡化后點(diǎn)云，共有37 653個,，簡化率為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)在各個測量點(diǎn)鄰域內(nèi)的分布情況對點(diǎn)云進(jìn)行簡化,。該方法針對點(diǎn)云表面的形狀特征,，有選擇性地對點(diǎn)云進(jìn)行了簡化，在曲率較大或尖銳棱邊處極大地保留了點(diǎn)云的原始特征,，使得最終的點(diǎn)云簡化不會造成形狀特征的缺失,，同時又刪除了大量的冗余數(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é)報，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é)報,，2004,，38(1)：62-65.
[8] 李江雄，柯映林.基于特征的復(fù)雜曲面反求建模技術(shù)研究[J].機(jī)械工程學(xué)報,，2000,，36(5)：18-25.
[9] 朱心雄.自由曲線曲面造型技術(shù)[M].北京：科學(xué)出版社,，2000.