結合尺度不變特征的Super 4PCS點云配準方法

魯鐵定，袁志聰，鄭坤

(1.東華理工大學，南昌 330013；2.流域生態與地理環境監測國家測繪地理信息局重點實驗室，南昌 330013)

0 引言

隨著三維激光掃描技術的快速發展，三維重建技術的應用越來越廣泛。點云配準是三維模型重建中的關鍵環節，點云配準按配準步驟可分為初配準和精配準[1]。初配準能夠很大程度上減小兩點云的旋轉和平移錯位，為精配準提供一個好的初始位置，提高配準精度和效率。常用的初配準[2-3]方法有主成分分析法、標簽法、中心重合法、4PCS算法[4-5]等。精配準是在初配準的基礎上對點云進行精確配準，使兩點云盡可能地重合，即兩點云的距離之和最小。應用最廣的精配準方法是由Besl和Mkcya提出的最近點迭代[6-7](ICP)算法。

近年來，Nicolas Mellado等[8-10]提出的Super 4PCS算法逐漸得到人們的關注。相對于4PCS算法，Super 4PCS算法利用智能索引極大地提高了點云初配準的速率[11]，同時Super 4PCS也存在一些不足，當點云本身具有堆成性時容易出現錯誤匹配等。Rongchun Zhang等[12]結合Super 4PCS算法與旋轉影像完成點云配準，利用旋轉影像對Super 4PCS算法進行了優化。

針對Super 4PCS算法的不足，本文通過結合3D-SIFT[13-14]算法與Super 4PCS算法進行點云配準，利用3D-SIFT算法提取特征點，將整片點云縮至特征點集，縮短點對提取時間，同時提高點對提取的準確率，最后設計了實驗，比分析了相關算法的配準性能。

1 Super 4PCS算法原理

1.1 4PCS算法原理

4PCS算法亦稱為四點魯棒快速匹配算法，是一種全局快速匹配算法，其原理為：假設點云P，Q分別為源點云和目標點云，4PCS算法以共面不共線的四點作為配準點基，首先在點云P中選取4個共面不共線的點作為點基(點基稱作C)，如圖1(a)所示，在P中選取的4點必須是P，Q重疊區域的點，然后在Q中利用點對間的距離與仿射不變性質尋找所有近似全等的點基集合D，D={D1，D2，D3，…，Dn}。由于目標點云中有很多點對并不符合要求，如圖1(b)所示，q′1q′2屬于錯誤匹配點對，q′1q′2與q3q4之間的角度不符合要求，利用C與Di進行剛體運動估計，得到二者的剛體變換Ti，即對P進行Ti變換后，Ti(P)與Q之間歐式距離平方和最小。

4PCS算法具有較好的配準精度，但是其時間復雜度達到了二次，效率不高。

圖1 點云與目標點云點基

1.2 Super 4PCS算法配準原理

在Super 4PCS[8]算法中，利用球體提取點對，大大提高了點對提取的效率。在點云Q中，以qi(i=1，2，…n)，為球心，半徑為r做球面，圖2(a)為二維表達形式，在Q中可做n個球面，形成球面集合，給定一誤差限ε，落在區間[r-ε，r+ε]上的點都符合要求，如圖2(a)中藍色點所示。將點云Q進行不斷剖分，以陣列存儲落在區間[r-ε，r+ε]上的點(圖2(b))，圖中藍色點為提取的點對，黑色點為不符合要求的點，點對提取之后，利用仿射不變性質在Q中提取與p1p2p3p4對應的q1q2q3q4，令p1p2為r1，p3p4為r2，記Q中對應r1的點對集合為S1，對應r2集合的點對為S2，對S1S2中任意點對，計算并存儲對應的方向向量。利用仿射不變性質都能求得一交點e(圖2(c))，根據方向向量以及角度θ，給定區間[r-ε，r+ε]，即可在Q中獲得唯一的四點，如圖2(d)所示。

2 改進Super 4PCS算法原理

2.1 3D-SIFT算法原理

尺度不變特征轉換特征提取算法(sale ivariant fature tansform，SIFT)最先應用在圖像處理中。3D-SIFT算法是由二維的SIFT[15]算法轉換而來的，利用點云的曲率值代替二維圖像的強度值，建立體素的尺度空間來提取特征點，3D-SIFT算法的主要原理[13]如下：

①建立點云的尺度空間。在三維點云空間中，通過體素柵格的方式建立點云體素金字塔，給定體素柵格的大小，求得體素所包含點云的重心，以其重心近似代替該體素內所包含的點云，可用公式表達為：

(1)

式中：Ii(x，y，z，σ)為第i個體素柵格點云數據的重心坐標；pk為第i個體素柵格中第k個點的三維坐標；n為第i個體素柵格中點的數量；Ii(x，y，z，σ)組成的集合為原點云在尺度下σ下的采樣點云。

圖2 Super 4PCS算法點基提取

②建立點云高斯差分尺度空間。在步驟①中構建了點云的體素金字塔，設金字塔共有m組，每組有S層，則第s層的尺度為：

(2)

式中：σ0為點云的初始尺度；σs為點云金字塔第s層的尺度。

計算每個高斯空間尺度下采樣點的高斯過濾響應值F，以及采樣點相鄰尺度的高斯差分值DOG。對采樣點及距離3σ鄰域范圍內的點進行曲率值高斯加權，高斯過濾響應值F和DOG高斯差分值的計算公式可表示為：

(3)

(4)

DOG=F-Fpre

(5)

式中：ρi為采樣點第i個近鄰點的曲率；wi的表達式如式(4)所示，d為采樣點到鄰域點的距離；σ為當前尺度空間的大小；式(5)中Fpre為上一尺度的高斯過濾響應值。

③檢測DOG尺度空間極值點。若某點的DOG值相比其鄰域范圍內的點的DOG值為極值，以及相鄰上下2個尺度鄰域范圍內的DOG相比仍為極值，確保其在點云空間與尺度空間均為極值點，則記該點為特征點。

2.2 結合SIFT特征點的Super 4PCS算法

Super 4PCS算法具有很快的配準速度，但當點云具有對稱性時(見算例2)，Super 4PCS算法點對識別易出錯，針對以上問題，提出了一種結合點云SIFT特征的Super 4PCS算法，其主要步驟可描述為：

①源點云與目標點云的SIFT特征提取，利用3D-SIFT算法能直接對點云進行特征點提取，將點云縮至特征點集，保留點云的主要成分，降低點云噪聲對配準結果的影響，更加凸顯點云的局部特征。

②以提取的SIFT特征點作為Super 4PCS算法的輸入點云，特征點是目標的特征部分，易于提取與識別，能提高Super 4PCS算法同名點對的識別度，不用遍歷原先整片點云，搜索源點云與目標點云的特征點即可，減少點對搜索的時間，使點對匹配更加準確。

③經過Super 4PCS算法點對提取后，在源點云中選取一定數量的采樣點，對采樣點進行剛體變換。以采樣點與目標點云中最近點距離之和作為評價分數值，選取評價分數值最小的剛體變換參數作為最終的變換參數，實現源點云與目標點云的配準。

④通過配準后同名點的均方根誤差來評價點云配準精度，公式為：

(6)

式中：Xi為源點云與目標點云的第i對同名點的坐標差值；n為對應點的個數。

本文算法的技術路線圖如圖3所示。

圖3 本文算法技術路線圖

3 實驗與分析

3.1 經典斯坦福兔子點云配準

為了驗證本文算法的性能，以標準斯坦福兔子作為實驗數據，對比分析SIFT算法、Super 4PCS算法以及本文算法的配準效果；相關結果如圖4所示(配準結果由Geomagic studio 2013軟件顯示)，黑色點云為源點云，藍色點云為目標點云。

圖4 斯坦福兔子點云配準結果

由圖4(a)可知，兩點云既存在平移位錯又存在旋轉位錯，直接利用ICP算法配準無法達到預期配準效果；圖4(b)為提取的同名特征點，可以看出斯坦福兔子的輪廓基本被提取出來。根據同名點可以直接估計出點云的剛體變換參數，配準結果如圖4(c)所示，可以看出兩點云基本重合，為ICP精確配準提供了一個良好的初始位置。圖4(d)為ICP精配準結果，經過ICP配準后，兩點云實現了精確配準。圖4(e)為Super 4PCS算法的配準結果，可看出配準后縮小了兩點云間的差距；圖4(f)為ICP精配準結果，精配準后，兩點云間的差距進一步縮小。圖4(g)為結合特征點的Super 4PCS算法配準結果，以提取的SIFT特征點作為輸入數據，再通過Super 4PCS算法求解剛體變換，可看出兩點云的旋轉和平移位錯基本消除，源點云與目標點云分布均勻。與其他兩種算法配準效果基本相當，圖4(h)為ICP精配準結果，可以看出源點云與目標點云已經完全重合在一起。從斯坦福兔子配準的視覺效果來看，3種算法配準結果基本相當。

表1給出了3種配準方法的速度與精度指標，從配準時間來看，由于SIFT算法需要先確定兩點云初始對應關系，初始對應關系確定后往往存在錯誤的對應關系，刪除錯誤的對應關系也要花費大量時間，增加了算法的時間復雜度，所以，SIFT算法配準速度最慢。Super 4PCS算法快于SIFT算法，耗時1.54 s；本文算法在特征提取等預處理階段需要花費一定時間，但后期具有更快的配準速度，僅花費0.3 s就完成了配準。本文算法配準后ICP精配準耗時2.50 s，Super 4PCS算法配準后ICP精配準耗時2.65 s，SIFT算法配準后ICP精配準耗時2.15 s；從配準精度來看，以均方根誤差作為評價指標，由于是標準的模型數據，3種方法配準精度都很高，都達到了mm級，SIFT算法利用抽樣一致性算法刪除了錯誤點對，配準精度最高；本文算法配準精度為2 mm，優于Super 4PCS算法配準精度。經過ICP精確配準后，三者的配準精度達到了10-5數量級，實現了源點云與目標點云的精確配準。

表1 斯坦福兔子配準結果

3.2 亭子點云配準

為了進一步驗證本文算法應用在實測數據上的性能，以實測的亭子為例，現分別用SIFT算法、Super 4PCS算法和結合2種算法的方法(S-Super 4PCS)對點云進行拼接，配準結果如圖5所示，黑色點云為源點云，藍色點云為目標點云。

圖5 亭子配準結果

如圖5(a)所示，源點云與目標點云存在很大的旋轉和平移位錯；圖5(b)為亭子出口的實景圖，作為配準結果的參照圖；圖5(c)為源點云與目標點云的SIFT同名特征點，3D-SIFT算法有效地提取了源點云與目標點云的特征部分，將整個點云數據集縮小至特征點集；圖5(d)為SIFT算法的配準結果，可看出亭子頂部仍然存在錯位，由于數據為實測的數據，不可避免的存在噪聲，且源點云與目標點云嚴格的同名點可能并不存在，導致其配準效果并不是太好；圖5(e)為SIFT算法配準結果亭子出口部位的放大圖，可看出亭子的臺階并沒有重合在一起；圖5(f)為Super 4PCS算法的配準結果，由于亭子點云本身具有對稱性，局部特征不明顯，出現了錯誤匹配的結果。圖中紅色框區域為亭子出口，經過Super 4PCS算法配準后，源點云亭子出口部位匹配到目標點云欄桿部位，在圖5(g)中可以看到紅色框中的黃色點云為一欄桿，并不是源點云亭子的出口；圖5(h)為結合3D-SIFT算法與Super 4PCS算法的配準結果，可以看出，經過本文方法配準后，兩點云的旋轉和平移位錯得到了改善，亭子頂端基本重合在一起，紅色框區域對應源點云與目標點云的亭子出口，實現了源點云與目標點云的正確拼接，特征點集減弱了噪聲的影響，凸顯了點云數據集的局部特征，提高了點對匹配的準確性；從圖5(i)的局部放大圖可看出，紅色框部分藍色點云與黃色點云對應為亭子出口的階梯，二者重合效果優于SIFT算法的配準結果；圖5(j)、圖5(k)、圖5(l)為3種方法配準后利用ICP精配準的結果，經過ICP配準后，源點云與目標點云的位錯在初配準上進一步得到改善，從視覺效果來看，結合SIFT算法與Super 4PCS算法的配準效果最優。

表2為3種配準方法對應的定量指標，從配準時間來看，本文算法后期配準耗時13.61 s，優于Super 4PCS算法的35.82 s，遠遠快于SIFT算法的配準速度；從配準精度來看，本文算法的配準精度為0.222 m，SIFT算法的配準精度為0.231 m，本文算法效果更好，Super 4PCS算法出現了錯誤配準結果；相比Super 4PCS算法而言，本文算法將點云縮至特征點集，減弱了噪聲對配準結果的影響，同時凸顯了點云的局部特征；本文算法初配準后，利用ICP算法對點云進行精確配準，耗時3.63 s，配準精度為2.6 cm，進一步縮小了點云間的差距。

通過實測數據配準結果表明，本文算法具有更好的配準性能，驗證了本文算法的可行性。

表2 亭子配準結果

4 結束語

點云配準是點云數據處理中的熱點問題，針對傳統的配準算法效率低等問題，本文提出一種結合SIFT特征的Super 4PCS點云配準方法，通過對源點云與目標點云進行特征提取，充分利用點云的局部特征，提高了Super 4PCS算法點對識別的準確性；將源點云與目標點云縮至特征點集，既保留了點云的主要成分，又縮短了點對的搜索時間，提高了算法的配準效率；通過實驗對比分析了SIFT算法、Super 4PCS算法以及本文算法在斯坦福兔子和實測點云數據上的配準性能，本文算法在前期特征提取需要花費一定時間，但后期具有更快的配準速度，總體性能更優，能為精配準提供一個良好的初始位置。