改進ICP算法在點云精確配準中的應用

【摘要】逆向工程技術作為產品設計制作的一種手段，由于它的獨特魅力，引起世界各國學術界和工業界的關注和高度重視。點云配準問題作為三維模型重建中的一個重要研究部分，已經得到越來越多的關注與研究，雖然當前存在著多種點云配準方法，但都存在一定的缺陷，在其存在的算法方面還存在著一些不足，對此國內外許多專家都在不斷的努力，尋求更大的突破。本文對目前應用比較廣泛的點云數據配準算法進行了深入細致的研究，最終實現了對原有的傳統ICP算法進行了成功改進，使得改進后的ICP的算法在點云配準方面比傳統ICP算法具有更好的配準效果。

【關鍵詞】逆向工程技術；點云配準；ICP；特征點；三維模型重建

1. 引言

在測量工程的實際應用中，很難通過一次測量，完成物體完整表面的數據采集，往往所采集到的這些點云數據還存在著一定的旋轉和平移錯位，因此，通常會把物體表面分成多個局部的相互重疊的子區域，從不同的方向和視角進行測量，從而得到不同角度的、只覆蓋物體部分表面的點云數據 [1]。

2. 點云數據的獲取以及特性

（1）三維空間數據的特性。“數據”是指未經過加工的源數據或原始數據，點云數據的獲取必須要通過測量手段、技術和方法，空間數據是指那些與地理分布有關的，反映現實世界各種現象以及其各種變化的數據[3]。由于三維信息存在著不確定性，而且它們會隨著時間的變化而發生變化，因此三維空間數據的管理是已經非常復雜的事情，三維空間數據有三個特性，分別是時間特性、空間特性和尺度特性。

圖1三維坐標變換示意圖（2）三維空間數據的獲取技術。三維空間信息的獲取，實質上就是空間定位數據采集技術，目前有如下幾種方式：天文測量技術、羅盤測量技術、大地測量觀測技術、慣性測量技術和衛星定位技術等。

3. 點云數據的配準算法

3.1點云配準的原理。

3.1.1在逆向工程的研究中，通常可以將分塊測量采集到的點云數據點集看作一個剛體，在這個基礎上，空間點云配準的過程可以看成是在六自由度的無限連續參數空間內，對空間點云的整體搜素問題，因此空間點云配準的求解過程又可以歸納總結為相應的旋轉矩陣T的求解問題[4]。

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

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

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

r21r22r23yt

r31r32r33zt

0001 （1）

式中，旋轉張量R的分量可用θ，ψ， 的函數來進行表達，即：

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在上述計算中，我們給定六個剛體變換參數，分別為θ，ψ，φ，xt，yt，zt ，通過這六個剛體變換參數來求解變換矩陣T，而在齊次矩陣的三維點P=[x，y，z，1] 的計算上，就只需要做矩陣相乘的運算即可，可列等式：

p'=[T]p

從而得到

p'= x'

y'

z'

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

r21r22r23yt

r31r32r33zt

0001 x

y

z

1 （3）

通過上述運算就可以得到其在O-X-Y-Z 坐標系中所對應的新位置 。 P'= [x'，y'，z'，1 ]

3.2經典ICP算法。ICP算法對它的實用對象要求并不嚴格，可以是點、曲線、隱式曲面、參數曲面等，其應用的關鍵是找點對，從理論上來看，當兩個數據點集完全匹配的時候，目標函數應該為零[5]，但在實際應用中，點云數據無法避免的存在著噪聲，所以兩片點云之間并不總是能夠達到理論上的匹配，因此當存在噪聲和誤差時，我們往往認為當目標函數最小的時候，能獲得最佳配準解[6]。

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

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

其中， NearestPt（pi）表示的是點集 {qi}中，通過Euclidean距離搜索出來的的最靠近{pi} 的一個點。

4. 改進ICP算法

4.1由于傳統ICP點云配準算法對點云配準的初始位置要求非常嚴格，點云的初始位姿不能相差太大，否則在計算中會比較容易陷入局部最小解，但是在實際掃描中，不管是從儀器方面還是從技術方面來說，都并不能保證所有點云都有符合傳統ICP點云配準算法對點云所要求的位姿[7]，因此，本文提出的算法是在傳統ICP點云配準算法的基礎上，首先采取三個基準的的坐標變換來提高點云數據的初始位置精度，然后進行ICP算法的配準。

4.2三點幾何坐標變換方法為：首先根據點云數據的曲率特征，給出三個主方向最貼近的點作為測量基準點，這三個測量基準點的第一次測量坐標表示為 P1、 P2和 P3，當進行第二次測量時，這三個基準點的坐標變換為q1 、q2 和 q3 ，則上面所描述的剛體變換就可以通過三個步驟來進行實現：

4.2.1首先將 P1變換為q1：

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

4.2.3最后進行的變換是，將包含 P1、P2 和 P3這三個點的平面轉換到包含三點q1 、q2 和 q3 的平面。

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

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

Step2： 設定兩個值，令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）

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

Step5： 作單位矢量

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

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

Step6： 把系統 [v]中的任一點Pi 變換到系統[w] 中，這種變換可以表示為下列變換關系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是單位矢量矩陣，因此可以表示出[w]=[v]R ，于是所求的關于[w] 系統的旋轉矩陣就相應的可以表示為：

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

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

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

Step9： 最后可以將方程改寫為：

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

下圖2給出的是三點坐標變換示意圖：

實驗模型，點數：2513/3200如下圖3是實驗原始點云，圖4是初始配準后的點云數據結果圖，圖5是改進ICP算法精確配準后的點云數據結果圖，可以看出，經過基于三個基準點進行初始配準后的點云數據的精確配準生成的效果圖要比傳統ICP算法的精度高。此模型的目的是為了對改進ICP算法作出進一步驗證。

6. 總結與展望

6.1本文對測量點云數據的獲取，數據特性以及獲取方式進行了簡要的說明，論述了點云數據的配準過程，提出一種改進點云配準算法，使得改進后的ICP的算法在點云配準方面比傳統ICP算法具有更好的配準效果。并通過實驗證明，改進后的ICP算法具有比原來傳統的ICP算法更快的配準速度、更高的配準精度、以及更小的誤差率，從而驗證了配準效果和算法穩定性。

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

參考文獻

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

[2]王霄，劉會霞，梁佳洪等.逆向工程技術及其應用[M].化學工業出版社，2009，30～32.

[3]李清泉，楊必勝，史文中等.三維空間數據的實時獲取、建模與可視化[M].武漢大學出版社，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]張學昌，習俊通，嚴雋琪.基于點云數據的復雜型面數字化檢測技術研究[J].計算機集成制造系統，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算法在點云配準中的應用[J].中國圖像圖形學報，2007，12（3）：517～521.

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

[文章編號]1619-2737（2014）01-03-267

[作者簡介] 李艷芳，工作單位：武漢航道學校，職稱：助理講師，職務：航道工程教研室教師，研究方向：3“S”。

4.2三點幾何坐標變換方法為：首先根據點云數據的曲率特征，給出三個主方向最貼近的點作為測量基準點，這三個測量基準點的第一次測量坐標表示為 P1、 P2和 P3，當進行第二次測量時，這三個基準點的坐標變換為q1 、q2 和 q3 ，則上面所描述的剛體變換就可以通過三個步驟來進行實現：

4.2.1首先將 P1變換為q1：

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

4.2.3最后進行的變換是，將包含 P1、P2 和 P3這三個點的平面轉換到包含三點q1 、q2 和 q3 的平面。

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

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

Step2： 設定兩個值，令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）

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

Step5： 作單位矢量

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

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

Step6： 把系統 [v]中的任一點Pi 變換到系統[w] 中，這種變換可以表示為下列變換關系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是單位矢量矩陣，因此可以表示出[w]=[v]R ，于是所求的關于[w] 系統的旋轉矩陣就相應的可以表示為：

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

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

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

Step9： 最后可以將方程改寫為：

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

下圖2給出的是三點坐標變換示意圖：

實驗模型，點數：2513/3200如下圖3是實驗原始點云，圖4是初始配準后的點云數據結果圖，圖5是改進ICP算法精確配準后的點云數據結果圖，可以看出，經過基于三個基準點進行初始配準后的點云數據的精確配準生成的效果圖要比傳統ICP算法的精度高。此模型的目的是為了對改進ICP算法作出進一步驗證。

6. 總結與展望

6.1本文對測量點云數據的獲取，數據特性以及獲取方式進行了簡要的說明，論述了點云數據的配準過程，提出一種改進點云配準算法，使得改進后的ICP的算法在點云配準方面比傳統ICP算法具有更好的配準效果。并通過實驗證明，改進后的ICP算法具有比原來傳統的ICP算法更快的配準速度、更高的配準精度、以及更小的誤差率，從而驗證了配準效果和算法穩定性。

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

參考文獻

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

[2]王霄，劉會霞，梁佳洪等.逆向工程技術及其應用[M].化學工業出版社，2009，30～32.

[3]李清泉，楊必勝，史文中等.三維空間數據的實時獲取、建模與可視化[M].武漢大學出版社，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]張學昌，習俊通，嚴雋琪.基于點云數據的復雜型面數字化檢測技術研究[J].計算機集成制造系統，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算法在點云配準中的應用[J].中國圖像圖形學報，2007，12（3）：517～521.

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

[文章編號]1619-2737（2014）01-03-267

[作者簡介] 李艷芳，工作單位：武漢航道學校，職稱：助理講師，職務：航道工程教研室教師，研究方向：3“S”。

4.2三點幾何坐標變換方法為：首先根據點云數據的曲率特征，給出三個主方向最貼近的點作為測量基準點，這三個測量基準點的第一次測量坐標表示為 P1、 P2和 P3，當進行第二次測量時，這三個基準點的坐標變換為q1 、q2 和 q3 ，則上面所描述的剛體變換就可以通過三個步驟來進行實現：

4.2.1首先將 P1變換為q1：

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

4.2.3最后進行的變換是，將包含 P1、P2 和 P3這三個點的平面轉換到包含三點q1 、q2 和 q3 的平面。

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

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

Step2： 設定兩個值，令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）

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

Step5： 作單位矢量

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

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

Step6： 把系統 [v]中的任一點Pi 變換到系統[w] 中，這種變換可以表示為下列變換關系式：

P'i =Pi R+T （8）

Step7： 由于[v] 和 [w]都是單位矢量矩陣，因此可以表示出[w]=[v]R ，于是所求的關于[w] 系統的旋轉矩陣就相應的可以表示為：

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

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

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

Step9： 最后可以將方程改寫為：

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

下圖2給出的是三點坐標變換示意圖：

實驗模型，點數：2513/3200如下圖3是實驗原始點云，圖4是初始配準后的點云數據結果圖，圖5是改進ICP算法精確配準后的點云數據結果圖，可以看出，經過基于三個基準點進行初始配準后的點云數據的精確配準生成的效果圖要比傳統ICP算法的精度高。此模型的目的是為了對改進ICP算法作出進一步驗證。

6. 總結與展望

6.1本文對測量點云數據的獲取，數據特性以及獲取方式進行了簡要的說明，論述了點云數據的配準過程，提出一種改進點云配準算法，使得改進后的ICP的算法在點云配準方面比傳統ICP算法具有更好的配準效果。并通過實驗證明，改進后的ICP算法具有比原來傳統的ICP算法更快的配準速度、更高的配準精度、以及更小的誤差率，從而驗證了配準效果和算法穩定性。

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

參考文獻

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

[2]王霄，劉會霞，梁佳洪等.逆向工程技術及其應用[M].化學工業出版社，2009，30～32.

[3]李清泉，楊必勝，史文中等.三維空間數據的實時獲取、建模與可視化[M].武漢大學出版社，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]張學昌，習俊通，嚴雋琪.基于點云數據的復雜型面數字化檢測技術研究[J].計算機集成制造系統，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算法在點云配準中的應用[J].中國圖像圖形學報，2007，12（3）：517～521.

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

[文章編號]1619-2737（2014）01-03-267

[作者簡介] 李艷芳，工作單位：武漢航道學校，職稱：助理講師，職務：航道工程教研室教師，研究方向：3“S”。