改進(jìn)ICP算法在點(diǎn)云精確配準(zhǔn)中的應(yīng)用

2014-03-27 23:28:35李艷芳

中華建設(shè)科技 2014年1期

【摘要】逆向工程技術(shù)作為產(chǎn)品設(shè)計(jì)制作的一種手段，由于它的獨(dú)特魅力，引起世界各國(guó)學(xué)術(shù)界和工業(yè)界的關(guān)注和高度重視。點(diǎn)云配準(zhǔn)問(wèn)題作為三維模型重建中的一個(gè)重要研究部分，已經(jīng)得到越來(lái)越多的關(guān)注與研究，雖然當(dāng)前存在著多種點(diǎn)云配準(zhǔn)方法，但都存在一定的缺陷，在其存在的算法方面還存在著一些不足，對(duì)此國(guó)內(nèi)外許多專(zhuān)家都在不斷的努力，尋求更大的突破。本文對(duì)目前應(yīng)用比較廣泛的點(diǎn)云數(shù)據(jù)配準(zhǔn)算法進(jìn)行了深入細(xì)致的研究，最終實(shí)現(xiàn)了對(duì)原有的傳統(tǒng)ICP算法進(jìn)行了成功改進(jìn)，使得改進(jìn)后的ICP的算法在點(diǎn)云配準(zhǔn)方面比傳統(tǒng)ICP算法具有更好的配準(zhǔn)效果。

【關(guān)鍵詞】逆向工程技術(shù)；點(diǎn)云配準(zhǔn)；ICP；特征點(diǎn)；三維模型重建

1. 引言

在測(cè)量工程的實(shí)際應(yīng)用中，很難通過(guò)一次測(cè)量，完成物體完整表面的數(shù)據(jù)采集，往往所采集到的這些點(diǎn)云數(shù)據(jù)還存在著一定的旋轉(zhuǎn)和平移錯(cuò)位，因此，通常會(huì)把物體表面分成多個(gè)局部的相互重疊的子區(qū)域，從不同的方向和視角進(jìn)行測(cè)量，從而得到不同角度的、只覆蓋物體部分表面的點(diǎn)云數(shù)據(jù) [1]。

2. 點(diǎn)云數(shù)據(jù)的獲取以及特性

（1）三維空間數(shù)據(jù)的特性?！皵?shù)據(jù)”是指未經(jīng)過(guò)加工的源數(shù)據(jù)或原始數(shù)據(jù)，點(diǎn)云數(shù)據(jù)的獲取必須要通過(guò)測(cè)量手段、技術(shù)和方法，空間數(shù)據(jù)是指那些與地理分布有關(guān)的，反映現(xiàn)實(shí)世界各種現(xiàn)象以及其各種變化的數(shù)據(jù)[3]。由于三維信息存在著不確定性，而且它們會(huì)隨著時(shí)間的變化而發(fā)生變化，因此三維空間數(shù)據(jù)的管理是已經(jīng)非常復(fù)雜的事情，三維空間數(shù)據(jù)有三個(gè)特性，分別是時(shí)間特性、空間特性和尺度特性。

圖1三維坐標(biāo)變換示意圖（2）三維空間數(shù)據(jù)的獲取技術(shù)。三維空間信息的獲取，實(shí)質(zhì)上就是空間定位數(shù)據(jù)采集技術(shù)，目前有如下幾種方式：天文測(cè)量技術(shù)、羅盤(pán)測(cè)量技術(shù)、大地測(cè)量觀(guān)測(cè)技術(shù)、慣性測(cè)量技術(shù)和衛(wèi)星定位技術(shù)等。

3. 點(diǎn)云數(shù)據(jù)的配準(zhǔn)算法

3.1點(diǎn)云配準(zhǔn)的原理。

3.1.1在逆向工程的研究中，通常可以將分塊測(cè)量采集到的點(diǎn)云數(shù)據(jù)點(diǎn)集看作一個(gè)剛體，在這個(gè)基礎(chǔ)上，空間點(diǎn)云配準(zhǔn)的過(guò)程可以看成是在六自由度的無(wú)限連續(xù)參數(shù)空間內(nèi)，對(duì)空間點(diǎn)云的整體搜素問(wèn)題，因此空間點(diǎn)云配準(zhǔn)的求解過(guò)程又可以歸納總結(jié)為相應(yīng)的旋轉(zhuǎn)矩陣T的求解問(wèn)題[4]。

3.1.2假定同一個(gè)點(diǎn)，在o-x-y-z 坐標(biāo)系中的定義為p（x，y，z），在坐標(biāo)系O-X-Y-Z 中的定義為p'（x'，y'，z'）。而剛體坐標(biāo)變換所描述的就是該點(diǎn)分別在兩個(gè)坐標(biāo)系中不同的兩種定義之間的關(guān)系問(wèn)題，如圖1所示。

3.1.3圖1中所描述的坐標(biāo)變換問(wèn)題是由存在于三個(gè)歐拉旋轉(zhuǎn)角θ，ψ，φ（0θπ，0ψ2π，0φ2π）中的坐標(biāo)旋轉(zhuǎn)以及在三個(gè)坐標(biāo)軸方向的三個(gè)分量xt =（o-O）x、yt =（o-O）y、zt =（o-O）z上的平移來(lái)共同決定的。該坐標(biāo)轉(zhuǎn)換問(wèn)題的轉(zhuǎn)換過(guò)程可以通過(guò)齊次矩陣T來(lái)描述：

T（θ，ψ，φ，xt，yt，zt ）= r11r12r13xt

r21r22r23yt

r31r32r33zt

0001 （1）

式中，旋轉(zhuǎn)張量R的分量可用θ，ψ，的函數(shù)來(lái)進(jìn)行表達(dá)，即：

R（θ，ψ，φ）= r11r12r13

r13r22r23

r31r32r33= （2）

cosψcosφ-cosθsinψsinφ-cosψsinφ-cosθsinψcosφsinθsinψ

sinψcosφ+cosθcosψsinφ-sinψsinφ+cosθcosψcosφ-sinθcosψ

sinθsinφsinθcosφcosθ

3.1.4在上述計(jì)算中，我們給定六個(gè)剛體變換參數(shù)，分別為θ，ψ，φ，xt，yt，zt ，通過(guò)這六個(gè)剛體變換參數(shù)來(lái)求解變換矩陣T，而在齊次矩陣的三維點(diǎn)P=[x，y，z，1] 的計(jì)算上，就只需要做矩陣相乘的運(yùn)算即可，可列等式：

p'=[T]p

從而得到

p'= x'

1=T（θ，ψ，φ，xt，yt，zt ）p= r11r12r13xt

r21r22r23yt

r31r32r33zt

0001 x

1 （3）

通過(guò)上述運(yùn)算就可以得到其在O-X-Y-Z 坐標(biāo)系中所對(duì)應(yīng)的新位置。 P'= [x'，y'，z'，1 ]

3.2經(jīng)典ICP算法。ICP算法對(duì)它的實(shí)用對(duì)象要求并不嚴(yán)格，可以是點(diǎn)、曲線(xiàn)、隱式曲面、參數(shù)曲面等，其應(yīng)用的關(guān)鍵是找點(diǎn)對(duì)，從理論上來(lái)看，當(dāng)兩個(gè)數(shù)據(jù)點(diǎn)集完全匹配的時(shí)候，目標(biāo)函數(shù)應(yīng)該為零[5]，但在實(shí)際應(yīng)用中，點(diǎn)云數(shù)據(jù)無(wú)法避免的存在著噪聲，所以?xún)善c(diǎn)云之間并不總是能夠達(dá)到理論上的匹配，因此當(dāng)存在噪聲和誤差時(shí)，我們往往認(rèn)為當(dāng)目標(biāo)函數(shù)最小的時(shí)候，能獲得最佳配準(zhǔn)解[6]。

F（R，T）=∑[RPi+T-P'i]2=min的求解過(guò)程實(shí)際上是一個(gè)高度的非線(xiàn)性求解問(wèn)題。其實(shí)，并不存在一個(gè)關(guān)于P'i 的非常清楚的定義，因此我們需要一個(gè)與之非常接近的點(diǎn)，而這個(gè)點(diǎn)在空間點(diǎn)集 {qi}中可以找到，我們稱(chēng)這個(gè)最接近P'i 的點(diǎn)為 NearestPt（pi），當(dāng)利用來(lái)代替 P'i時(shí)，就可以將式（2）中的等式修改為：

F（R，T） =∑[Rpi+T-NearestPt（pi）]2=min （4）

其中， NearestPt（pi）表示的是點(diǎn)集 {qi}中，通過(guò)Euclidean距離搜索出來(lái)的的最靠近{pi} 的一個(gè)點(diǎn)。

4. 改進(jìn)ICP算法

4.1由于傳統(tǒng)ICP點(diǎn)云配準(zhǔn)算法對(duì)點(diǎn)云配準(zhǔn)的初始位置要求非常嚴(yán)格，點(diǎn)云的初始位姿不能相差太大，否則在計(jì)算中會(huì)比較容易陷入局部最小解，但是在實(shí)際掃描中，不管是從儀器方面還是從技術(shù)方面來(lái)說(shuō)，都并不能保證所有點(diǎn)云都有符合傳統(tǒng)ICP點(diǎn)云配準(zhǔn)算法對(duì)點(diǎn)云所要求的位姿[7]，因此，本文提出的算法是在傳統(tǒng)ICP點(diǎn)云配準(zhǔn)算法的基礎(chǔ)上，首先采取三個(gè)基準(zhǔn)的的坐標(biāo)變換來(lái)提高點(diǎn)云數(shù)據(jù)的初始位置精度，然后進(jìn)行ICP算法的配準(zhǔn)。

4.2三點(diǎn)幾何坐標(biāo)變換方法為：首先根據(jù)點(diǎn)云數(shù)據(jù)的曲率特征，給出三個(gè)主方向最貼近的點(diǎn)作為測(cè)量基準(zhǔn)點(diǎn)，這三個(gè)測(cè)量基準(zhǔn)點(diǎn)的第一次測(cè)量坐標(biāo)表示為 P1、 P2和 P3，當(dāng)進(jìn)行第二次測(cè)量時(shí)，這三個(gè)基準(zhǔn)點(diǎn)的坐標(biāo)變換為q1 、q2 和 q3 ，則上面所描述的剛體變換就可以通過(guò)三個(gè)步驟來(lái)進(jìn)行實(shí)現(xiàn)：

4.2.1首先將 P1變換為q1：

4.2.2然后在只考慮方向的情況下，將矢量（p2-p1）變換為矢量（q2 -q1 ）。

4.2.3最后進(jìn)行的變換是，將包含 P1、P2 和 P3這三個(gè)點(diǎn)的平面轉(zhuǎn)換到包含三點(diǎn)q1 、q2 和 q3 的平面。

以上所述可以用算法表示為：

Step1：做三個(gè)矢量（p2-p1）、（p3-p1）、（q2 -q1 ）與（q3 -q1 ）之間的計(jì)算；

Step2：設(shè)定兩個(gè)值，令V1 =p2-p1，W1= q2 -q1；

Step3：作矢量V3 與 W3

V3=V1×（p3-p1）

W3=W1×（q3-q1 ）（5）

Step4：作矢量V2與 W2

V2=V3×V1

W2=W3×V2 （6）

很容易看出，上述三個(gè)矢量V1 、V2 與 V3可以構(gòu)成右手正交系，而另外三個(gè)矢量W1 、 W2與W3 也同樣可以構(gòu)成右手正交系。

Step5：作單位矢量

v1=V11|V1|， v2=V21|V2|， v3=V31|V3|

W1=W11|W1|， W2=W21|W2|， W3=W31|W3| （7）

Step6：把系統(tǒng) [v]中的任一點(diǎn)Pi 變換到系統(tǒng)[w] 中，這種變換可以表示為下列變換關(guān)系式：

P'i =Pi R+T （8）

Step7：由于[v] 和 [w]都是單位矢量矩陣，因此可以表示出[w]=[v]R ，于是所求的關(guān)于[w] 系統(tǒng)的旋轉(zhuǎn)矩陣就相應(yīng)的可以表示為：

R=[v]-1 [w] （9）

Step8：使 P'l=ql和Pl=pl ，把這兩個(gè)方程代入上述式中，可以得到平移矩陣T ；

T=q1-p1 [v]-1 [w] （10）

Step9：最后可以將方程改寫(xiě)為：

P'=P[v]-1 [w]- P1[v]-1 [w] +q1 （11）

下圖2給出的是三點(diǎn)坐標(biāo)變換示意圖：

實(shí)驗(yàn)?zāi)Ｐ?，點(diǎn)數(shù)：2513/3200如下圖3是實(shí)驗(yàn)原始點(diǎn)云，圖4是初始配準(zhǔn)后的點(diǎn)云數(shù)據(jù)結(jié)果圖，圖5是改進(jìn)ICP算法精確配準(zhǔn)后的點(diǎn)云數(shù)據(jù)結(jié)果圖，可以看出，經(jīng)過(guò)基于三個(gè)基準(zhǔn)點(diǎn)進(jìn)行初始配準(zhǔn)后的點(diǎn)云數(shù)據(jù)的精確配準(zhǔn)生成的效果圖要比傳統(tǒng)ICP算法的精度高。此模型的目的是為了對(duì)改進(jìn)ICP算法作出進(jìn)一步驗(yàn)證。

6. 總結(jié)與展望

6.1本文對(duì)測(cè)量點(diǎn)云數(shù)據(jù)的獲取，數(shù)據(jù)特性以及獲取方式進(jìn)行了簡(jiǎn)要的說(shuō)明，論述了點(diǎn)云數(shù)據(jù)的配準(zhǔn)過(guò)程，提出一種改進(jìn)點(diǎn)云配準(zhǔn)算法，使得改進(jìn)后的ICP的算法在點(diǎn)云配準(zhǔn)方面比傳統(tǒng)ICP算法具有更好的配準(zhǔn)效果。并通過(guò)實(shí)驗(yàn)證明，改進(jìn)后的ICP算法具有比原來(lái)傳統(tǒng)的ICP算法更快的配準(zhǔn)速度、更高的配準(zhǔn)精度、以及更小的誤差率，從而驗(yàn)證了配準(zhǔn)效果和算法穩(wěn)定性。

6.2但是由于本文的研究時(shí)間有限，并且資料方面存在這一些不足的地方，因此還存在的一些缺陷，要從根本上解決點(diǎn)云數(shù)據(jù)配準(zhǔn)所存在的問(wèn)題，還迫切需要更多、更深入的研究。

參考文獻(xiàn)

[1]劉大杰，陶本藻.實(shí)用測(cè)量數(shù)據(jù)處理方法[M].北京：測(cè)繪出版社，2000：79～81.

[2]王霄，劉會(huì)霞，梁佳洪等.逆向工程技術(shù)及其應(yīng)用[M].化學(xué)工業(yè)出版社，2009，30～32.

[3]李清泉，楊必勝，史文中等.三維空間數(shù)據(jù)的實(shí)時(shí)獲取、建模與可視化[M].武漢大學(xué)出版社，2003，2～13.

[4]BeslP J， MckayN D. A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239～256.

[5]ALTH，BRASS P，GODAU M，ETAL. Computing the Hausdorff distance of geometric patterns and shapes[J].Discrete and Computational Geometry，Special Issue-The Goodman-Pollack-Festschrift，2003.65～76.

[6]Rosen holm D，Torelegard K.Three-dimensional absolute orientation of stereo models using digital elevation models. Photo-grammetric Engineering and Remote Sensing， 1988， 54（10）：1385～1389.

[7]BlaisG，LevineM D.Registeringmultiview range data to create 3D computer graphics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1995， 17（8）： 820～824.

[8]LI Q，Griffiths J G.Iterative closest geometric objects registration[J].Computers and Mathematics with Applications，2000，40（10）：1171～1188.

[9]張學(xué)昌，習(xí)俊通，嚴(yán)雋琪.基于點(diǎn)云數(shù)據(jù)的復(fù)雜型面數(shù)字化檢測(cè)技術(shù)研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11（5）：727～731.

[10]Chen Y， Medioni G. Object modeling by registration of multiple range images[A]. In： Proceeding of the 1991 IEEE International Conference on Robotics and Automation [C]， Sacramento， CA，USA， 1991： 2724～2729.

[11]Rusinkiewicz S， Levoy M. Efficient variants of the ICP algorithm In 3D Digital Imaging and Modeling[C]. IEEE Computer Society Press，2001，145～152.

[12]Johnson A， E，Kang S B.Registration and Integration of Textured 3D Data[J].Image and Vision Computing，1999，17：135～147.

[13]戴靜蘭，陳志楊，葉修梓. ICP算法在點(diǎn)云配準(zhǔn)中的應(yīng)用[J].中國(guó)圖像圖形學(xué)報(bào)，2007，12（3）：517～521.

[14]張愛(ài)武，宋小鵬. 基于VTK的室外場(chǎng)景三維重建[D].首都師范大學(xué)，碩士學(xué)位論文，2006.5.15.

[文章編號(hào)]1619-2737（2014）01-03-267

[作者簡(jiǎn)介] 李艷芳，工作單位：武漢航道學(xué)校，職稱(chēng)：助理講師，職務(wù)：航道工程教研室教師，研究方向：3“S”。