數據點云預處理技術研究

齊秀麗

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

在逆向工程中,采集實體表面數據是完成實體模型數字化的第一步.數據采集具有多幅性、實物的多樣性和數據采集要求的多樣性等特點.可根據實體的材質、表面尺寸、表面是否封閉等特征來選擇適當的測量儀器和測量方法,進行數據采集.

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

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

1 數據配準

采用多種測量儀,對實體表面進行多角度的多次測量,從而使得測得的數據點云不具備序結構,于是需要對原始數據點云做配準處理.比較成功的辦法為數據配準的ICP算法.

1.1 兩幅距離圖像配準到同一坐標系的ICP算法[2]

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

1.2 多幅距離圖像配準到同一坐標系的ICP算法[2]

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

1.3 多幅距離圖像配準到同一坐標系的改良ICP算法[2]

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

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

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

相對來說,視點云為無序散亂點云而進行配準,再利用配準后的點云重建曲面,所得曲面能極大的與原測量實體表面保持拓撲一致.

2 數據整合與優化

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

(1)基于雕刻的方法.相比之下,人們更愿意將數據點云處理成多邊形網格模型,因為其具有形狀簡單、容易處理、能夠以任意精度逼近任一曲面等特點,而且易被分割成三角形,所以人們首先將點云Belaunay三角化,然后按照規則找出與目標一致的三角面片,從而得到三角形網格模型,如Boissonnat的方法,Crust算法,基于α-Shape的方法等等.

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

(3)基于細分空間的方法.如數據處理中比較傳統的包圍盒法.

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

為了使從點云重建得到的三角網格曲面能夠進行正確的后繼處理,在CAD中得到實際應用,必須保證這個重建出來的網格曲面是拓撲正確的,即重建曲面與被采樣物體表面是拓撲同胚的.Amenta和Bern、Petitjean和Boyer Adamy,Giesen和John用不同的思路對此進行了研究,也有很好的算法產生.但是,如果重建曲面與被采樣物體表面的拓撲結構差別較大,則會衍生出運算量很大的線性規劃問題,有時甚至無解.

3 面對散亂數據點集,基于數學期望的數據點云預處理

3.1 設{Pi|i=1,2,…}為原始數據點集.將其投影到一個網格平面上.含有數據點的網格點則稱為黑點,所有的黑點構成平面區域記為Ω.

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

3.2 在ω的每一個網格黑點中,進行數據簡化.

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

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

分別計算這兩個隨機變量的數學期望 Eξ和Eη[3],記 m=Eξ,n=Eη.取初始點為 Q0(m,n).

對于當前網格內的數據點 P,若|PQ0|>λ,則去除該點;若|PQ0|≤λ,則保留該數據點.

對Ω內的每一個網格點,作如上處理,可以精簡數據點,而且保留了數據密集處的數據點.

3.3 根據網格點權值的定義,選出適當的網格點為初始點 Q′0.

對于權值最大的點 Q0,以其為心,以(P)為半徑 ,作鄰域 N°(Q0,(P)),考察該鄰域內的所有數據點{Pi|i=1,2,…,t},記數據點 Pi的坐標為(mi,ni).

按照3.2討論隨機變量ξ、η,分別計算這兩個隨機變量的數學期望 Eξ和 Eη,記 m=Eξ,n=Eη.取初始點為 Q′0(m,n).

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

在當前點滿足 d(Qk-1,Qk)>2,或者時,則終止過程.

如上,可建立起一個點列{Qk},即為預處理之后的數據點云.該點云已將分布較稀疏部分的數據點精簡掉,并按照數學期望意義下數據密集的位置對點云進行了預處理.

[1]鐘綱,楊勛年,汪國昭.平面無序點集曲線重建的跟蹤算法 [J].軟件學報,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]魏宗舒,等.概率論與數理統計教程 [Z].北京:高等教育出版社,2000.