邱世聰 羅意

（江西理工大學建筑與測繪工程學院，江西贛州 341000）

改進ICP算法的點云配準

邱世聰 羅意

（江西理工大學建筑與測繪工程學院，江西贛州 341000）

針對傳統(tǒng)ICP算法所存在的對初始點云位置要求高、算法效率低等局限性，本文對算法進行研究改進，改進結(jié)合K-近鄰搜索和法向量估計，采用組建不變角度作為不變特征求解旋轉(zhuǎn)矩陣和平移向量實現(xiàn)初配準，利用基于八叉樹的ICP算法進行精配準。研究表明，改進算法能提高配準精度，縮短配準時間，優(yōu)勢明顯。

點云配準；法向量估計；不變特征；ICP算法；八叉樹

三維激光掃描技術(shù)是目前用于測繪學科的一項高新技術(shù)，該技術(shù)具有非接觸性、快速性、實時獲取的數(shù)據(jù)具有精度高等特點，因此被廣泛應(yīng)用于文物保護、數(shù)字城市、變形監(jiān)測、逆向工程等領(lǐng)域［1-3］。由于實際測量工作中常常受三維激光掃描儀自身、掃描目標的復(fù)雜程度及周圍環(huán)境的影響，需要進行多次設(shè)站掃描以獲得完整的數(shù)據(jù)，由于不同測站掃描的點云數(shù)據(jù)所在的坐標系統(tǒng)不同，因此需要對不同測站的點云數(shù)據(jù)進行配準，即將不同坐標系的點云數(shù)據(jù)轉(zhuǎn)換到相同的坐標系下以獲得同一基準［4］。

目前，國內(nèi)外的學者在點云配準方面做了許多研究，由Besl等提出的迭代最近點算法（Iterative Closest Points，ICP）應(yīng)用最為廣泛，許多學者也對此算法做出了不同的改進［5-7］。最近點迭代算法本質(zhì)上是基于最小二乘法的最優(yōu)匹配算法，算法重復(fù)進行確定對應(yīng)點集解算出最優(yōu)剛體變換，直到滿足某個表示正確匹配的收斂準則［8］。ICP算法存在的局限性主要有兩方面：①該算法要求2個點集有較好的相對初始位置以避免陷入局部最優(yōu)解［9］；②搜尋匹配點對的時間較長［10］。

本文基于上述ICP算法存在的不足，提出了一種改進算法，此算法主要進行以下兩方面的改進：①根據(jù)ICP算法對點云初始位置的要求，避免陷入局部最優(yōu)解，結(jié)合K-近鄰搜索和法向量估計，通過構(gòu)造不變角度作為不變特征求解旋轉(zhuǎn)矩陣和平移向量對點云進行初始配準；②針對ICP算法處理工作量大及搜索效率低下等缺點，通過求取內(nèi)點點集來減少搜索工作量，同時利用Octree結(jié)構(gòu)來加快點云配準的搜索速率，并利用配準點云中點對的距離關(guān)系剔除錯誤點，以提高配準精度。

1 改進的點云配準算法

1.1 點云初始配準

ICP算法是逼近迭代算法，需要兩點集有較大范圍的重合區(qū)域，以滿足精確配準的收斂精度要求。實際測量過程中獲得的兩視角點云由于目標物體的復(fù)雜程度、掃

本文通過局部表面擬合的方法估計法向量［8］。在點云表面處處光滑的情況下，可以用平面很好地擬合出任意點的局部鄰域，因此，對掃描點云數(shù)據(jù)中的任意點p，當搜索到距離點P最近的K個鄰近點，然后解算出K個鄰近點的局部平面P。對點云數(shù)據(jù)中的任意一點p進行法向量估計等價于對點p與其K個鄰近點擬合成的局部平面P的切平面進行法向量的求解。本文通過鄰域協(xié)方差分析法求得點云數(shù)據(jù)中各個點的法向量。原理如下：

任意一點P與其K近鄰域點得到協(xié)方差陣：

式（1）中，p0為K近鄰域的質(zhì)心，點P的法向量為協(xié)方差矩陣CV最小特征值對應(yīng)的特征向量。

1.2 點云的精確配準

按照上述方法進行初配準后，兩點云已經(jīng)大致取得了良好的配準位置，但是還需要進行精確配準，以達到點云配準的精度要求。鑒于初配準已得到較好的結(jié)果，為進一步提高配準精度，對于目標點集中的點pi以及其在參考點集中的最近點qj設(shè)定一個閾值δ，若dist（pi，qj）＜δ，即兩點之間的距離小于閾值，則將pi作為內(nèi)點，否則認為其降低配準精度而作為外點去除，用得到的內(nèi)點點集計算配準參數(shù)。首次迭代時將初始配準的誤差值設(shè)定為閾值δ，首次迭代后的配準誤差值作為第2次迭代的閾值δ，之后上一次迭代后的配準誤差值作為下一次迭代的閾值δ。如此反復(fù)進行迭代，直到配準誤差滿足終止條件時結(jié)束。此外，改進算法利用Octree結(jié)構(gòu)代替原傳統(tǒng)ICP算法里的查找部分來搜尋最近點，這樣可以大大提高點云最近點的搜索速度，從而降低點云配準的時間。

通過最近點距離搜索得到的點對中依然存在影響配準精度的錯誤點，改進算法通過求取對應(yīng)點對的方向向量夾角來判斷對應(yīng)點對是否正確。由于在初始配準中已經(jīng)求取了點云數(shù)據(jù)中所有點的法向量且將法向量方向的指向調(diào)整到點云曲面的同一側(cè)，所以在這里只需要將各點法向量轉(zhuǎn)化為單位向量，并求取各對應(yīng)點對法向量夾角。經(jīng)上述方法進行初配準后，兩點云基本重合，正確的對應(yīng)點對應(yīng)滿足點對法方向向量夾角小于某一閾值β，因此若夾角大于設(shè)定的閾值β，則認為是錯誤的點對，并將其剔除以避免錯誤的點對參加配準，從而提高點云配準精度。

2 實例驗證

圖1 龜模型配準對比圖

為了驗證改進算法的有效性，本文利用Rigel VZ-6000三維激光掃描儀采集的點云數(shù)據(jù)進行了實驗。實驗平臺為CPU主頻2.6GHz，內(nèi)存4GB的Windows10系統(tǒng)。在本次三維模型重建中用到的點云處理軟件是GeomagicStudio2012，在Microsoft Visual Studio 2010環(huán)境下利用C++語言編程設(shè)計、采用PCL 1.7.2版本點云庫［11］、CMAKE 3.0跨平臺編譯工具來實現(xiàn)算法。

由于采集的數(shù)據(jù)中具有噪聲，首先將點云數(shù)據(jù)進行去躁，而且為了提高配準效率對去躁后的點云數(shù)據(jù)，在保留其特征的前提下進行了采樣等一系列預(yù)處理。

在點云配準過程中，按照上述初始配準的算法步驟，實現(xiàn)視點點云數(shù)據(jù)的K-鄰域搜索、法向量及不變特征的求取，本文采用4鄰域。

本文通過搜索不變特征來組成匹配點對，由最小二乘擬合計算旋轉(zhuǎn)矩陣及平移向量，此次初始配準選取四鄰域且進行了3次旋轉(zhuǎn)平移。初配準后的兩視角點云大致重合能夠滿足ICP算法對點云初始位置要求，而且為后續(xù)的點云精配準提供了良好的環(huán)境。

在PCL點云庫的環(huán)境下按照前面描述的精配準策略進行實現(xiàn)，為了驗證本文所采用精配準方法的有效性，分別按照傳統(tǒng)ICP算法、初始配準+傳統(tǒng)ICP算法和初始配準+改進ICP算法進行驗證，結(jié)果如圖1所示。

從配準效果圖可以看出，由于傳統(tǒng)ICP算法沒有進行初始配準獲得較好的精配準位置，導(dǎo)致迭代收斂到局部最優(yōu)解，配準失敗。而后面2次試驗對點云進行了初始配準，使得配準成功，但是從初始配準+傳統(tǒng)ICP算法、初始配準+改進ICP算法可以看出在點云輪廓邊緣位置的配準上傳統(tǒng)ICP算法的效果沒有改進ICP算法好，這是由于在傳統(tǒng)ICP算法中沒有加入錯誤點對的去除條件，使得在同樣的迭代收斂條件下，配準效果沒有改進ICP算法好。同時，在配準時間及配準誤差上，改進ICP算法都在傳統(tǒng)ICP算法基礎(chǔ)上有所提高。

3 結(jié)論

本文針對ICP算法存在的一些不足，提出了一種初始配準加精確配準的配準策略，在初始配準中通過點對之間不變特征的匹配完成點云數(shù)據(jù)的大致配準，在精確配準ICP算法中通過加入八叉樹結(jié)構(gòu)及求取內(nèi)點點集來加快對應(yīng)點對的搜索，提高配準效率。同時，利用配準點對之間的限制關(guān)系來去除錯誤點對提高配準精度。驗證結(jié)果證明，本文配準策略及其改進方法能夠很好地解決ICP算法存在的一些缺陷，并且有效提高配準效率及精度，滿足配準要求。

［1］程效軍，賈東鋒，程小龍.海量點云數(shù)據(jù)處理理論與技術(shù)［M］.上海：同濟大學出版社，2014.

［2］楊現(xiàn)輝，王惠南.ICP算法在3D點云配準中的應(yīng)用研究［J］.計算機仿真，2010（8）：235-237.

［3］鄭德華.ICP算法及其在建筑物掃描點云數(shù)據(jù)配準中的應(yīng)用［J］.測繪科學，2011（3）：86-91.

［4］周春艷，李勇，皺崢嶸.三維點云ICP算法改進研究［J］.計算機技術(shù)與發(fā)展，2011（8）：75-77.

［5］F Su.The research of optical 3D measuring precision influencing factor in reverse engineering［J］.Applied Mechanics&Materials，2010（33）：157-162.

［6］S Du，N Zheng，S Ying，et al.Affine iterative closest point algorithm for point set registration［J］.Pattern Recognition Letters，2010（9）：791-799.

［7］LE Walizer，JF Peters.A bounding box search algorithm for DEM simulation［J］.Computer Physics Communications，2011 （2）：281-288.

［8］邢正全，鄧喀中，薛繼群.基于K-近鄰搜索的點云初始配準［J］.測繪科學，2013（2）：93-95.

［9］鐘瑩，張蒙.給予改進ICP算法的點云自動配準技術(shù)［J］.中國圖像圖形學報，2007（3）：517-521.

［10］朱德海，郭浩，蘇偉.點云庫PCL學習教程［M］.北京：北京航空航天大學出版社，2012.

［11］PJ Besl，ND Mckay.A method for registration of 3-D shapes［C］//IEEE Transactions on Pattern Analysis and Machine Intelligence，1992（2）：239-256.

Point Cloud Registration Based on Improved ICP Algorithm

Qiu ShicongLuo Yi
（School of Architectural and Surveying&Mapping Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000）

In order to overcome the problem of requiring high quality initial point cloud position and low registration efficiency existing in the traditional iterative closest point(ICP)method,this paper developed an improved ICP algorithm.The improved algorithm combines K-nearest neighbor search and normal estimation,and set the invariant angle as invariant feature to achieve rotation matrix and the translation vector to realize initial registration,then the ICP algorithm based on Octree was used for accurate registration.The experimental results showed that the improved algorithm had obvious advantages for improving the registration accuracy and shortening the registration time.

point cloud registration；normal estimation；invariant feature；ICP algorithm；Octree

TP391.7

A

1003-5168（2017）04-0040-03

2017-03-07

邱世聰（1993-），男，碩士，研究方向：三維激光掃描數(shù)據(jù)處理。描儀自身及周圍環(huán)境的影響往往沒有較好的初始位置。因此，為了滿足后續(xù)精確配準的要求，首先需要對點云數(shù)據(jù)進行初始配準。