數(shù)據(jù)點(diǎn)云預(yù)處理技術(shù)研究

齊秀麗

(綏化學(xué)院數(shù)學(xué)與信息科學(xué)系,黑龍江綏化 152061)

在逆向工程中,采集實(shí)體表面數(shù)據(jù)是完成實(shí)體模型數(shù)字化的第一步.數(shù)據(jù)采集具有多幅性、實(shí)物的多樣性和數(shù)據(jù)采集要求的多樣性等特點(diǎn).可根據(jù)實(shí)體的材質(zhì)、表面尺寸、表面是否封閉等特征來選擇適當(dāng)?shù)臏y量儀器和測量方法,進(jìn)行數(shù)據(jù)采集.

在逆向工程中,對(duì)數(shù)據(jù)點(diǎn)云的預(yù)處理是完成實(shí)體模型數(shù)字化的第二個(gè)步驟.利用測量儀器,可得到關(guān)于被測實(shí)體表面的大量數(shù)據(jù),但是由測量儀器和測量人員都會(huì)帶來誤差,使得所得數(shù)據(jù)不能全部準(zhǔn)確位于被測實(shí)體表面;另一方面,因測量設(shè)備本身的局限性,所以測量時(shí)需要采用多種測量儀對(duì)實(shí)體表面進(jìn)行多角度的多次測量,從而使得測得的點(diǎn)云數(shù)據(jù)不具備序結(jié)構(gòu).以上這些因素都需要研究者對(duì)原始數(shù)據(jù)點(diǎn)云進(jìn)行簡化、分類聚合和數(shù)據(jù)配準(zhǔn)等預(yù)處理.

目前比較經(jīng)常被采用的方法是:首先,可根據(jù)被測實(shí)體的表面特征,將其分成不同的部分,使每一部分具有自己的曲面特征 (如初等解析曲面中的平面、球面、柱面、錐面、圓環(huán)面,或者為B樣條曲面、NURBS曲面,又或者為自由曲面等).這樣,數(shù)據(jù)點(diǎn)云就按照原被測體的幾何特征而被分成不同的數(shù)據(jù)塊,對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行曲面、曲線重建相對(duì)容易.另外,還可對(duì)點(diǎn)云作數(shù)據(jù)配準(zhǔn),把經(jīng)過多次、多種測量的數(shù)據(jù)從其自身局部坐標(biāo)系,通過平移和旋轉(zhuǎn)的方法配準(zhǔn)到一個(gè)全局坐標(biāo)系當(dāng)中.此外,點(diǎn)云中原始數(shù)據(jù)太多并不利于重建,故需對(duì)其進(jìn)行精簡.數(shù)據(jù)精簡的方法主要包括:減少多邊形網(wǎng)格中多邊形的數(shù)量;使用傳統(tǒng)的采樣方法;使用網(wǎng)格方法.

1 數(shù)據(jù)配準(zhǔn)

采用多種測量儀,對(duì)實(shí)體表面進(jìn)行多角度的多次測量,從而使得測得的數(shù)據(jù)點(diǎn)云不具備序結(jié)構(gòu),于是需要對(duì)原始數(shù)據(jù)點(diǎn)云做配準(zhǔn)處理.比較成功的辦法為數(shù)據(jù)配準(zhǔn)的ICP算法.

1.1 兩幅距離圖像配準(zhǔn)到同一坐標(biāo)系的ICP算法[2]

設(shè)兩組數(shù)據(jù)點(diǎn)云是利用數(shù)據(jù)采集設(shè)備從二個(gè)視點(diǎn)位置測量實(shí)體表面而得到的,這兩組數(shù)據(jù)之間必然有大量重疊區(qū)域.首先,從重疊區(qū)域中確定幾對(duì)對(duì)應(yīng)點(diǎn),對(duì)一組數(shù)據(jù)點(diǎn)云做剛體運(yùn)動(dòng)處理,以使得選定的幾組對(duì)應(yīng)點(diǎn)之間的距離變小,直到滿足收斂條件終止迭代.如果在計(jì)算過程中,距離不能在迭代時(shí)遞減,可以調(diào)整對(duì)應(yīng)點(diǎn)的選取方法.已經(jīng)證明,這個(gè)迭代過程可以收斂到局部最小值點(diǎn);但是,它能否收斂到全局最小值點(diǎn),則依賴于兩幅距離圖像的初始位置.根據(jù)選擇對(duì)應(yīng)點(diǎn)的方法的不同,以及在計(jì)算過程中所采用的優(yōu)化方法的不同.另外,這個(gè)方法能夠使得最小二乘意義下的距離收斂到局部最小值,但未必能收斂到全局最小值.

1.2 多幅距離圖像配準(zhǔn)到同一坐標(biāo)系的ICP算法[2]

如有多幅距離圖像,任意選兩幅進(jìn)行配準(zhǔn),可得到一個(gè)新的數(shù)據(jù)點(diǎn)云,然后在其余的里面選擇一個(gè)與上面得到的新數(shù)據(jù)點(diǎn)云配準(zhǔn),如此做下去,可得到一幅低精度圖像 (數(shù)據(jù)點(diǎn)云),精度低由誤差積累造成的.

1.3 多幅距離圖像配準(zhǔn)到同一坐標(biāo)系的改良ICP算法[2]

在多幅距離圖像中先選定兩幅,首先計(jì)算出被測體表面在第一幅距離圖像中某給定點(diǎn)處的法線(Chen,Medioni),求出該法線與第二幅距離圖像所表示的曲面交點(diǎn)處的切平面,求得第一幅圖像選定點(diǎn)在這個(gè)切平面上的投影點(diǎn),與之形成對(duì)應(yīng),找到所有的對(duì)應(yīng)點(diǎn)即可.這是前面ICP算法1.2的改良方法.

事實(shí)上,多幅距離圖像中可以任取一幅作為初始圖像,將其余圖像按上面的改良方法配準(zhǔn)到這幅初始圖像所在的坐標(biāo)系中,這次的迭代過程在配準(zhǔn)矩陣近乎于單位矩陣的條件下終止.

另外,還有很多非常好的配準(zhǔn)方法.如Pulli的漸近式配準(zhǔn)法,適用于數(shù)據(jù)點(diǎn)云十分龐大的情形;還有Turk和Levoy將距離圖像的點(diǎn)云連接而將其網(wǎng)格化,得到被測實(shí)體表面的網(wǎng)格模型,再將不同幅網(wǎng)格模型相互配準(zhǔn)而成一幅具有幾何特征的實(shí)體的網(wǎng)格表示.這些雖然在速度和準(zhǔn)確性上占有優(yōu)勢,但是在保留圖像特征方面也有不盡人意之處,而且在解決曲面拼接、求交、延拓和過渡等問題時(shí)的效果也不夠理想.

相對(duì)來說,視點(diǎn)云為無序散亂點(diǎn)云而進(jìn)行配準(zhǔn),再利用配準(zhǔn)后的點(diǎn)云重建曲面,所得曲面能極大的與原測量實(shí)體表面保持拓?fù)湟恢?

2 數(shù)據(jù)整合與優(yōu)化

隨著三維掃描技術(shù)的發(fā)展,能夠十分容易的獲得包含大量數(shù)據(jù)的點(diǎn)云.但由于誤差的存在,又由于沒有必要的直接用海量的原始數(shù)據(jù)點(diǎn)云進(jìn)行曲線曲面重建,所以需要對(duì)于數(shù)據(jù)點(diǎn)云進(jìn)行整合.數(shù)據(jù)整合的方法主要包括以下幾類[1]:

(1)基于雕刻的方法.相比之下,人們更愿意將數(shù)據(jù)點(diǎn)云處理成多邊形網(wǎng)格模型,因?yàn)槠渚哂行螤詈唵?、容易處理、能夠以任意精度逼近任一曲面等特點(diǎn),而且易被分割成三角形,所以人們首先將點(diǎn)云Belaunay三角化,然后按照規(guī)則找出與目標(biāo)一致的三角面片,從而得到三角形網(wǎng)格模型,如Boissonnat的方法,Crust算法,基于α-Shape的方法等等.

(2)跟蹤等值線的方法.如Happe提出的算法.

(3)基于細(xì)分空間的方法.如數(shù)據(jù)處理中比較傳統(tǒng)的包圍盒法.

(4)區(qū)域增長的方法.先構(gòu)造一個(gè)種子三角面片,將其三邊加入活動(dòng)鏈表進(jìn)行處理,對(duì)每一條活動(dòng)邊,按某規(guī)則在點(diǎn)云中為其尋找新點(diǎn)與之構(gòu)成三角形,以新產(chǎn)生的邊替代原活動(dòng)邊,將其加入鏈表,繼續(xù)尋找新點(diǎn).這種方法往往需要借助于事先確定的參數(shù),這種人為的因素對(duì)算法的可靠性有很大的影響.

為了使從點(diǎn)云重建得到的三角網(wǎng)格曲面能夠進(jìn)行正確的后繼處理,在CAD中得到實(shí)際應(yīng)用,必須保證這個(gè)重建出來的網(wǎng)格曲面是拓?fù)湔_的,即重建曲面與被采樣物體表面是拓?fù)渫叩?Amenta和Bern、Petitjean和Boyer Adamy,Giesen和John用不同的思路對(duì)此進(jìn)行了研究,也有很好的算法產(chǎn)生.但是,如果重建曲面與被采樣物體表面的拓?fù)浣Y(jié)構(gòu)差別較大,則會(huì)衍生出運(yùn)算量很大的線性規(guī)劃問題,有時(shí)甚至無解.

3 面對(duì)散亂數(shù)據(jù)點(diǎn)集,基于數(shù)學(xué)期望的數(shù)據(jù)點(diǎn)云預(yù)處理

3.1 設(shè){Pi|i=1,2,…}為原始數(shù)據(jù)點(diǎn)集.將其投影到一個(gè)網(wǎng)格平面上.含有數(shù)據(jù)點(diǎn)的網(wǎng)格點(diǎn)則稱為黑點(diǎn),所有的黑點(diǎn)構(gòu)成平面區(qū)域記為Ω.

定義1 平面上兩個(gè)網(wǎng)格點(diǎn) P(i,j),Q(m,n)的距離 d(P,Q)=|i-m|+|j-n|.

3.2 在ω的每一個(gè)網(wǎng)格黑點(diǎn)中,進(jìn)行數(shù)據(jù)簡化.

定義3 設(shè)隨機(jī)變量ξ的所有可能取值為mj,1≤j≤t.

定義4 設(shè)隨機(jī)變量η的所有可能取值為nj,1≤j≤t,

分別計(jì)算這兩個(gè)隨機(jī)變量的數(shù)學(xué)期望 Eξ和Eη[3],記 m=Eξ,n=Eη.取初始點(diǎn)為 Q0(m,n).

對(duì)于當(dāng)前網(wǎng)格內(nèi)的數(shù)據(jù)點(diǎn) P,若|PQ0|>λ,則去除該點(diǎn);若|PQ0|≤λ,則保留該數(shù)據(jù)點(diǎn).

對(duì)Ω內(nèi)的每一個(gè)網(wǎng)格點(diǎn),作如上處理,可以精簡數(shù)據(jù)點(diǎn),而且保留了數(shù)據(jù)密集處的數(shù)據(jù)點(diǎn).

3.3 根據(jù)網(wǎng)格點(diǎn)權(quán)值的定義,選出適當(dāng)?shù)木W(wǎng)格點(diǎn)為初始點(diǎn) Q′0.

對(duì)于權(quán)值最大的點(diǎn) Q0,以其為心,以(P)為半徑 ,作鄰域 N°(Q0,(P)),考察該鄰域內(nèi)的所有數(shù)據(jù)點(diǎn){Pi|i=1,2,…,t},記數(shù)據(jù)點(diǎn) Pi的坐標(biāo)為(mi,ni).

按照3.2討論隨機(jī)變量ξ、η,分別計(jì)算這兩個(gè)隨機(jī)變量的數(shù)學(xué)期望 Eξ和 Eη,記 m=Eξ,n=Eη.取初始點(diǎn)為 Q′0(m,n).

3.4 按照參考文獻(xiàn)[1]的方法選擇方向,建立點(diǎn) Q′0處的局部坐標(biāo)系,對(duì)于當(dāng)前點(diǎn) Qk,作以 Qk為圓心,以r為半徑的圓,在圓內(nèi)考察與 U的夾角小于90°的數(shù)據(jù)點(diǎn)Pi(即為圓內(nèi)的點(diǎn)).規(guī)定θi為兩個(gè)特殊方向的夾角.取 I1和 I2,加入調(diào)節(jié)因子η,而構(gòu)造 I1+ηI2.要選取適合k,而使得 I1+ηI2=min,從而確定出方向,選取下一個(gè)點(diǎn) Qk+1.

在當(dāng)前點(diǎn)滿足 d(Qk-1,Qk)>2,或者時(shí),則終止過程.

如上,可建立起一個(gè)點(diǎn)列{Qk},即為預(yù)處理之后的數(shù)據(jù)點(diǎn)云.該點(diǎn)云已將分布較稀疏部分的數(shù)據(jù)點(diǎn)精簡掉,并按照數(shù)學(xué)期望意義下數(shù)據(jù)密集的位置對(duì)點(diǎn)云進(jìn)行了預(yù)處理.

[1]鐘綱,楊勛年,汪國昭.平面無序點(diǎn)集曲線重建的跟蹤算法 [J].軟件學(xué)報(bào),2002,13(11):2188-2193.

[2]Besl P.J and McKay N.D.A method for registration of 3D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence,VOL(14),No.(2),239-256,1992.

[3]魏宗舒,等.概率論與數(shù)理統(tǒng)計(jì)教程 [Z].北京:高等教育出版社,2000.