由粗到細的點云配準算法*

趙夫群

(1.咸陽師范學院 教育科學學院，陜西 咸陽 712000; 2.西北大學 信息科學與技術學院，陜西 西安710127)

0 引 言

點云配準就是為兩個點集求解最優空間變換，使其能夠達到最佳配準的過程。由于多個點云的配準可以通過兩個點云的配準來實現，因此通常所說的點云配準都是指兩個點云的配準。點云配準已經在3D重建、醫學研究、目標識別以及顱面復原等領域[1～6]得到了廣泛的應用。

目前，應用最為廣泛的點云配準算法是由Besl P J等人[7]提出的迭代最近點 (iterative closest point,ICP) 算法，該算法簡單，易于理解和實現，但對兩個點云的初始位置要求較高，且要求兩個點云具有包含關系。因此，國內外學者提出了很多改進的ICP算法: Zhu J等人[8]提出了一種基于雙向距離的仿射ICP算法，提高了算法的配準精度和抗噪性；Han J等人[9]提出了一種基于分層搜索方案、預警機制和啟發式逃生方案的加強ICP算法，能夠快速準確地實現點云配準； Du S等人[10]提出了概率ICP算法，提高了算法的收斂速度和抗噪性； Du S等人[11]提出了尺度迭代最近點(scaling iterative closest point,SICP)算法，解決了點云的尺度配準問題； Zhao L等人[12]提出了皺紋—感知點云配準方法，實現了大尺度的點云配準；周文振等人[13]提出了一種基于K—means聚類的改進ICP算法，實現了精確的室內地圖配準。但上述算法未解決算法收斂區間和精度之間的矛盾。

為此，本文提出一種由粗到細的點云配準算法。在粗配準階段，采用尺度參數可變的點云配準算法，可以解決點云配準中收斂區間與配準精度之間的矛盾。在細配準階段，通過設置旋轉角約束和動態迭代系數來改進ICP算法，可以解決由旋轉角變化過大引起的配準效果不佳的問題，并提高算法的迭代收斂速度。

1 粗配準

在粗配準階段，首先采用大尺度參數測度函數作為配準測度函數，并逐漸減小尺度參數，使得算法在結束時能夠獲得足夠精確的配準參數。

1.1 測度函數

E(Tr)=∑σ(d(Tr(mi),dj)),

i=1,…,NM,j=1,…,ND

(1)

式中mi和dj分別為點云M和D中的三維坐標點，Tr(mi)為對點mi進行空間變換，d(Tr(mi),dj)為Tr(mi)和dj之間的歐氏距離。函數σ定義為:當t=0時，σ(t)=1;否則，σ(t)=0。

對式 (1)求最大值max(E(Tr))即可實現點云配準。為了式 (1) 尋優求解，采用高斯核函數對其進行平滑，并采用平滑后的函數作為點云配準的測度函數。該高斯核函數的定義為ρh(t)=exp(-t2/s2),s為尺度參數。那么平滑后的計數函數為

i=1,…,NM，j=1,…,ND

(2)

式(2)即為點云配準的測度函數。只要尺度參數s選取合適，平滑后的計數函數Eh(Tr)即為原計數函數E(Tr)的近似。本文通過BFGS(Broyden-Fletcher-Goldfarb Shanno)擬牛頓優化算法搜索其全局極大值，從而確定點云配準的最優參數，實現點云粗配準。

1.2 變尺度配準算法

主要思想為：在算法的起始階段，采用大尺度參數測度函數作為點云配準的測度函數，以免算法陷入局部極??；隨著優化過程的推進，逐漸減小尺度參數，可在算法結束時獲得精確的配準參數。具體步驟為：

1)設置初值：尺度參數s0，迭代次數k=1，初始剛體變換q0=(R0,t0)，R0為旋轉矩陣，t0為平移矢量；

2)利用BFGS進行目標函數的極大值搜索；

3)通過目標函數的極大值位置獲得剛體配準的參數Rk和tk；

4)若滿足終止條件則令剛體變換的最終旋轉矩陣為R*=Rk，平移矢量為t*=tk，算法結束;否則,轉步驟(5)；

(3)

6)執行k=k+1操作，轉步驟(2)。

2 細配準

細配準采用改進的ICP算法實現，在ICP算法中加入角度約束和動態迭代系數，以解決由旋轉角變化過大引起的配準效果不佳的問題，并提高算法的收斂速度。

2.1 ICP算法

s.t.RTR=In,det(R)=1

(4)

式中R為旋轉矩陣;t為平移矩陣。

ICP算法基本步驟如下：

1)根據第k步的已知剛體變換Rk和tk，將點云M進行Rkmi+tk變換，并建立兩個點云M和D間的相關性ck+1(i)，其數學描述為

i=1,…,NM

(5)

2)計算點集M和D的剛體變換，其數學描述為

(6)

2.2 改進的ICP算法

ICP算法的改進過程分2個步驟:加入旋轉角約束和加入動態迭代系數。

定義旋轉矩陣R為R=RxRyRz且

(7)

式中θx,θy,θz為旋轉角，令θxb,θyb,θzb為旋轉角均值；Δθx,Δθy,Δθz為旋轉角偏差；θxb-Δθx,θyb-Δθy,θzb-Δθz為旋轉角的下界；θxb+Δθx,θyb+Δθy,θzb+Δθz為旋轉角上界。

加入旋轉角約束后，M和D的配準問題可描述為

(8)

在算法中加入動態迭代系數h。通常，動態迭代系數h取大于等于0的整數，當h不同時，算法的收斂速度也不同，根據不同h值對應的迭代收斂曲線可知,隨著動態迭代系數h的增大，算法的收斂速度越來越快，但當h增大到一定的程度，收斂曲線會出現振蕩，當h=4時，算法不再收斂。因此，要為h設定取值范圍，根據實驗經驗，建議其取值范圍在1～4之間。

在ICP算法中加入動態迭代系數h的步驟如下：

1)計算剛體變換矢量q=[R|t]T以及qk的相鄰2次迭代的變化量Δqk；

2)由剛體變換矢量Δqk更新基本ICP算法中的Mk共h次，即執行Mk=Δqk(Mk)共h次。

加入旋轉角約束和動態迭代系數后，該改進ICP算法的具體步驟如下：

1)給定剛體變換初值q0=[R0,t0]T，R0為初始旋轉矩陣，t0為初始平移矢量，令M0=R0M+t0，迭代次數k=0，動態迭代系數h=0；

2)估計旋轉角θx,θy,θz的邊界，即θx∈[θxb-Δθx,θxb+Δθx],θy∈[θyb-Δθy,θyb+Δθy]和θz∈[θzb-Δθz,θzb+Δθz]；

3)利用式(5)建立點云M和D相關性ck(i)；

4)利用奇異值分解(singular value decomposition,SVD)的方法計算旋轉矩陣Rk+1和平移矢量tk+1，則qk+1=[Rk+1,tk+1]T;

5)計算qk+1的相鄰兩次迭代的變化量Δqk+1;

6)利用式(8)計算Mk+1=Rk+1M+tk+1;

7)判斷均方根(root mean square,RMS)誤差，若RMSk+1-RMSk>ε，則執行h=h+1操作;否則執行h=0操作RMS定義為

(9)

8)判斷動態迭代系數h，若h>0，則通過執行Mk+1=Δqk+1(Mk+1)共h次來更新點集Mk+1；

9)若滿足|RMSk+1-RMSk|<ε或k>Stepmax則算法終止;否則,轉到步驟(10)，ε為預設的閾值，Stepmax為最大迭代次數;

10)令k=k+1，并轉步驟(2)。

3 實驗結果與分析

點云配準的實驗數據源于Stanford 3D Scanning Repository，如圖1所示。

圖1 待配準的點云

基于本文配準算法，首先采用變尺度點云配準算法實現粗配準，然后分別采用ICP 算法和提出的改進ICP 算法實現細配準、配準結果如圖2所示，算法的匹配點數、匹配誤差、迭代次數和耗時等運行參數如表1所示。

圖2 配準結果

點云類型點云大小算法配準點數配準誤差迭代次數耗時/s兔子20128,20048粗配準ICP改進ICP5566671297940.05960.02890.01353222103.22.11.1龍20920,17418粗配準ICP改進ICP5017611389070.06580.02990.01653524133.62.41.3

在采用改進ICP算法的細配準過程中，旋轉角偏差取值為Δθx=Δθy=Δθz=10°，動態迭代系數取值為h=3。

從圖3的配準結果來看，變尺度的點云粗配準算法可以將兩個點云初步對齊；ICP算法和改進ICP算法可將兩個點云進一步對齊，但改進ICP算法比ICP算法的配準誤差更小，具有更高的配準精度。

從表1可見，改進ICP算法比ICP算法具有更多的配準點數、更低的配準誤差、更少的迭代次數和耗時。與ICP算法相比，改進ICP算法配準精度和速度均提高了約50 %，是一種精度更高、速度更快的點云配準算法。因此，提出的由粗到細的點云配準算法是一種有效的點云配準算法。

4 結 論

本文由粗到細的點云配準算法解決了算法中收斂區間與配準精度之間的矛盾和旋轉角變化過大引起的配準效果不佳的問題，是一種精度高、速度快的點云配準算法。該算法具有一定的抗噪性，但未考慮尺度各異的點云配準問題。在今后的研究中，還要綜合考慮點云配準中更多的影響因素，如噪聲因素、尺度因素、外點的干擾因素等，設計更加合理有效的配準算法，進一步提高點云配準的精度、速度、魯棒性和抗噪性，擴大點云配準技術的應用領域。