改進(jìn)ICP算法的點(diǎn)云配準(zhǔn)

邱世聰 羅意

（江西理工大學(xué)建筑與測(cè)繪工程學(xué)院，江西贛州 341000）

改進(jìn)ICP算法的點(diǎn)云配準(zhǔn)

邱世聰 羅意

（江西理工大學(xué)建筑與測(cè)繪工程學(xué)院，江西贛州 341000）

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

點(diǎn)云配準(zhǔn)；法向量估計(jì)；不變特征；ICP算法；八叉樹(shù)

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

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

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

1 改進(jìn)的點(diǎn)云配準(zhǔn)算法

1.1 點(diǎn)云初始配準(zhǔn)

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

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

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

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

1.2 點(diǎn)云的精確配準(zhǔn)

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

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

2 實(shí)例驗(yàn)證

圖1 龜模型配準(zhǔn)對(duì)比圖

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

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

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

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

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

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

3 結(jié)論

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

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

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

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

［4］周春艷，李勇，皺崢嶸.三維點(diǎn)云ICP算法改進(jìn)研究［J］.計(jì)算機(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-近鄰搜索的點(diǎn)云初始配準(zhǔn)［J］.測(cè)繪科學(xué)，2013（2）：93-95.

［9］鐘瑩，張蒙.給予改進(jìn)ICP算法的點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)［J］.中國(guó)圖像圖形學(xué)報(bào)，2007（3）：517-521.

［10］朱德海，郭浩，蘇偉.點(diǎn)云庫(kù)PCL學(xué)習(xí)教程［M］.北京：北京航空航天大學(xué)出版社，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)境的影響往往沒(méi)有較好的初始位置。因此，為了滿足后續(xù)精確配準(zhǔn)的要求，首先需要對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行初始配準(zhǔn)。