用于多視點云拼接的改進ICP算法①

陳金廣,郭秋夢,馬麗麗,徐步高

(西安工程大學 計算機科學學院,西安 710048)

1 引言

點云拼接在三維物體重建中有著廣泛的應用,如逆向工程、移動機器人、航天航空、指紋識別、計算機視覺等眾多領域.在對三維物體進行測量的過程中,掃描設備可能會受到視野上的限制,或是受到噪聲、光照等的影響,使得掃描設備在同一視角下無法獲取待測物體的全部點云信息.因此,需要從多視角對待測物體進行測量,從而重建出完整的三維物體模型.

目前使用最為廣泛的點云拼接算法是1992年Besl等[1]提出的迭代最近點算法(Iterative Closest Points,ICP),其目的是在兩片點云之間尋找距離最近的點,計算最優剛體變換矩陣,直到滿足某種度量準則下的最優匹配.Chen等在傳統的ICP算法的基礎上提出了一種新的點云拼接算法[2],該方法能夠提高算法的收斂速度,減少迭代耗時及迭代次數,兩者的不同之處在于前者提出的是將點與點之間的距離作為鄰近點,而后者則利用點與面之間的距離作為鄰近點.文獻[3]提出與圖像信息相結合的快速點云拼接方法,對平移和旋轉兩種變換分別求解.通過改進的ICP算法得到平移變換,而旋轉矩陣則是由拍攝圖像與幾何知識相結合而得到的.此方法大大降低了計算復雜度,但利用相機拍攝得到的圖像必須存在較大部分的重疊,否則需要通過人工操作提供匹配點,操作過程繁瑣.文獻[4]提出的動態分層匹配標識點算法,將帶標識點的點云分別建立最小包圍盒,通過4個方向進行分層搜索,以最后搜索到的標識點為頂點,建立動態矩陣,并記錄相應的標識點對,但此方法不僅費時而且增加了算法的復雜性.文獻[5]提出一種將三維激光掃描技術與測量技術相結合的研究思路,通過對點云數據進行處理、配準、拼接、去噪等步驟實現三維物體重建.

目前點云拼接技術按照拼接過程可以分為粗拼接和精確拼接,粗拼接是將不同坐標系下的點云數據統一到同一坐標系下,隨后進行配準,為精確拼接提供初始值;精確拼接則是通過ICP算法對坐標變換參數進行迭代優化,使拼接誤差最小,滿足所需的收斂精度.粗拼接一般可分為兩類,一類是借助輔助設備的拼接方法,包括轉臺法[6-8]、標識點法[9,10]、定標球法[11].轉臺法是使回轉臺傾斜一定的角度,通過旋轉待測物體來獲取測量數據,但此方法對測量設備的精度要求較高,且定位精度難以保證;標識點法是在不同的視圖中建立三個基準點,通過這三個基準點對齊三維測量數據,此方法的計算較為簡單,但是在尋找基準點時較為繁瑣,并且會影響其定位精度及測量的真實度.文獻[10]提出利用標識點對多視圖進行約束的高精度粗拼接算法,此方法是在掃描過程中構建標識點多視圖網格,并兩兩拼接,然后利用光束法平差技術優化此網格,得到全局控制點,并保存坐標系下的三維點云數據,最后將全局控制點與坐標系下的三維點云數據進行拼接,得到完整的三維模型.另一類是基于曲面特征的拼接方法,包括三點法、雙切曲線法等.三點法是Zhang等[12]通過兩片點云中的三個點所形成的平面來確定坐標變換參數,此方法的不足之處在于點云數量過多時計算效率下降,分辨率不高.雙切曲線法是由Wyngaerd等[13]人提取待測物體曲線的表面特征,通過匹配雙曲線之間對應點的關系來確立點云之間的關系,此方法操作簡單,但對于表面特征不明顯的待測物體效果欠佳.目前國內外關于點云的拼接算法力求改善拼接精度,許多學者針對對應點之間的搜索問題提出了不同的搜索策略,但一定程度上仍存在問題,比如點云表面曲率變化較大時,會導致平面投影點與真正的對應點之間存在較大的偏差,此偏差會直接影響兩片點云的拼接精度,另外在處理此偏差的過程中無疑增加了計算機的計算量等諸如此類的問題.也正是因為存在這樣的問題,故而需要對點云拼接算法進行改進.國內外的相關工作為本文的點云拼接算法研究提供了方向,本文算法致力于提高拼接精度,減少迭代次數及迭代耗時,因而提出了一種改進的ICP算法對多視點云進行拼接,通過多次實驗驗證了其正確性及有效性.

2 迭代最近點算法

針對點云的拼接問題,國內外的研究學者對此提出了很多解決方案,其中就有Besl提出的ICP算法,此算法是對目標點集P尋找與之存在一一對應關系的參考點集Q中距離最近的點構成的集合,建立點與點之間的映射關系,根據這種映射關系計算兩點集之間的變換參數,最終求出相應的平移向量和旋轉矩陣,直到滿足所需的收斂精度并達到點云拼接的目的為止.

ICP算法的實現[1]一般分為以下5個步驟:

(1)假設給定點云P為目標點云,用表示,點云數量為NP,給定點云Q為參考點云,用表示,點云數量為NQ,并滿足NP≤NQ.確定點云P、Q之間存在映射關系的對應點對,并構成集合,搜索方法主要包括點到點、點到切平面、K-D樹搜索、八叉樹搜索等.

(2)根據搜索到的對應點對集合求出初始旋轉矩陣T1和平移參數R1:

其中P1和Q0分別表示目標點集P和參考點云Q中的點.求取平移和旋轉參數最典型的方法有四元數法[14]和奇異值分解法[15]等.

(3)利用上述求得的平移和旋轉參數對Q1進行坐標轉換,得到新的變換點集Q2:

(4)重復步驟(2)和(3),進行迭代計算,其中m表示對應點對的個數:

(5)步驟(4)中得到的新的變換點集與參考點云,這兩個點集在配準轉換過程中能使目標函數最小:

i表示點云中的任意一點.當目標函數最小時停止迭代計算,得到均方誤差

假設給定迭代收斂閾值τ,且τ＞0,相鄰兩次迭代間的均方誤差時,停止迭代.若不滿足式(5),則重復步驟(4)重新迭代計算新的點集,直到滿足目標函數的要求為止.

3 改進的ICP算法

ICP算法是一種迭代計算的算法,具有較高的拼接匹配精度,但是ICP算法強調兩片待拼接的點云之間的數據點必須是一一對應的包含關系,ICP算法為目標點云中的每個點尋找在參考點云中對應的點,一一進行匹配,無疑增加了計算量.如果初始位姿較好,則能獲取較好的拼接精度和收斂速度,若點云的初始姿態較差將直接影響計算機的計算速度.若初始位置較差會影響目標點云尋找與之存在對應關系的參考點云中的點,在尋找對應點時會出現錯誤匹配,無形中增加了難度,因而也就難以保證算法精度及效率,對此部分做出改進后對應Step2,確定目標點云中的點的三維坐標并進行排序,將鄰域搜索轉化為局部搜索,從而提高計算機的計算速度.從上述過程可知,由于需要計算目標點云中每個點的對應點因而計算量較大,可能使整個迭代過程陷入局部最優而不是全局最優.另外此方法是對點云直接處理,無需進行特征點提取、分割等操作.

由于傳統的ICP算法是采用遍歷的方式來尋找兩片點云之間的對應關系,增大了計算機的計算量,降低了計算效率,針對傳統ICP算法的缺陷,本文提出的坐標軸法用以計算目標點云中的點及前后各n個點在坐標軸上的距離,加以閾值限制,取距離最近的k個點構成最近點集,減少了不必要的計算量,提高了計算效率.基本思想是確定一個點k的三維坐標Pk,創建三個索引表,以坐標遞增的順序存儲輸入點的三維坐標,從而將某個點的鄰域搜索轉化為局部搜索.另外點云模型中的點是均勻密集分布的,因而選擇坐標與Pk坐標相近的點組成搜索子集,其中在搜索最近點集時,設定約束搜索范圍的閾值,減少不必要的計算量,然后計算子集中的每個點到Pk的距離,并以遞增的順序排列,進而得到最近點集.以Pk為中心點進行最近點集搜索時,設置閾值以約束Pk點前后的搜索范圍,其中閾值的大小與掃描的點云距離有關.當閾值取值過小時,不能獲取全部有效的最近點,若閾值過大,則計算量仍然較大.經多次實驗,設置閾值為0.01.

改進后的ICP算法步驟如下:

Step1.尋找待拼接點云的特征點,并進行初始化,確立待測點云之間的對應關系;

Step2.

1)確定一個點Pk的三維坐標,然后創建三個索引表;

2)將輸入的三維坐標以坐標遞增的順序排列,并存入數組Px、Py、Pz中,從而將某個點的鄰域搜索轉化為局部搜索;

3)將Pk點作為候選點,計算數組 Px、Py、Pz中Pk點及前后各n個點在三維坐標軸上的歐式距離;

4)判斷歐式距離與給定閾值的關系,若歐式距離大于等于閾值則停止計算,將全部點存入到新數組Tx、Ty、Tz中,若小于閾值則返回到數組Px、Py、Pz中重新選取候選點;

Step3.求新數組Tx、Ty、Tz中三維坐標的交集,計算出最近點集及坐標變換矩陣,若誤差收斂則配準到參考點云,否則返回重新計算最近點.

改進的ICP算法流程圖如圖1.

4 實驗結果及分析

本文共進行了三組實驗,分別采用斯坦福點云數據庫中的Bunny模型、Dragon模型及一組由Kinect采集的三維人體點云數據,通過三組實驗驗證本文算法的有效性和正確性.

實驗1采用的是不同視角下的Bunny點云模型,分別為點云數量是40 256的bunny_000.pcd模型和點云數量是40 097的bunny_045.pcd模型,如圖2(a)、(b)所示.實驗先后采用傳統的ICP算法和改進的ICP算法進行點云拼接,得到拼接效果如圖2(c)、(d).由圖2(c)可知,采用傳統的ICP算法在拼接過程中出現較大程度上的錯位,尤其在Bunny的耳朵、后背以及整個軀體上,從圖中可以看出未能得出良好的拼接效果.經改進的ICP算法拼接后效果良好,從圖2(d)中可以看出Bunny的耳朵、腳部以及頭部較傳統ICP算法實現了完全的拼接,姿態良好,并且在尾部和后背部分較傳統ICP算法也有明顯的改進.

圖1 改進的ICP算法流程圖

圖2 Bunny點云拼接

實驗2選取的是點云數量較小的Dragon點云模型,圖3(a)、(b)的初始點云數量分別為19 318、30 492.圖3(c)是經傳統ICP算法拼接后的效果圖,可知Dragon點云在軀干和頭部的拼接較模糊,姿態差,拼接錯位.從圖3(d)中可以看出Dragon的軀干部分拼接良好,尤其是在腳部和頭部實現完全拼接,效果優良,另外在迭代時間上較傳統的ICP算法提高了19.11%.由此可以看出,經改進后的ICP算法在初始點云具有良好姿態的情況下,將拼接誤差大幅度降低,并且花費的迭代時間減少,可見改進后的算法減少了計算量,提高了拼接精度.

圖3 Dragon點云拼接

為進一步驗證本文算法的普適性,實驗3采用一組由Kinect采集的三維人體點云數據進行實驗.圖4(a)、(b)表示兩片未拼接的初始點云,點云數量分別為12 675、14 742.從圖4(c)看出未經改進的傳統ICP算法在拼接時頭部出現偏移,并且手臂部位與身體部位也出現重疊,姿態較差,拼接精度較低.經改進的ICP算法拼接后,頭部和手臂部分的拼接有了明顯的改善如圖4(d),在迭代耗時上也由原先的0.821 s降低至0.567 s,提高了44.8%.

將迭代耗時和均方誤差作為收斂效果的標準進行評價,均方誤差記為error,迭代耗時記為time,改進的ICP算法在最近點集的搜索上,設置一個閾值約束搜索范圍,避免了傳統ICP算法為目標點云中的每個點尋找參考點云中與之對應的點這一計算量較大的過程,取而代之的是將閾值范圍外的點剔除掉,從而減少了搜索的計算量.上述3組點云數據實驗結果如表1所示.從表中可看出,在迭代時間上提高了19.1%～47.4%,在均方誤差上也優于傳統ICP算法,從而驗證了本文算法的有效性.

圖4 三維人體點云拼接

表1 兩種算法拼接性能比較

5 結束語

點云拼接的拼接精度和拼接速度對三維重建有著至關重要的意義,因此對于傳統ICP算法在點云拼接上存在的缺陷,提出一種改進的ICP算法.首先是在選取特征點時,將閾值與坐標軸結合,設定約束候選點搜索范圍的閾值,獲得歐氏距離最近的點集,然后利用ICP算法對點云進行拼接.實驗結果表明在確保拼接精度的情況下迭代速度有明顯的提升,解決了傳統ICP算法在計算速度和迭代耗時上的問題,提高了算法的準確性和有效性,有較高的應用價值.雖然本文算法對于一般性點云數據的拼接取得了較傳統ICP算法拼接的良好效果,但仍有不足之處,未來將對一般性點云數據的拼接精度做進一步研究.

1 Besl PJ,McKay ND.A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239–256.[doi:10.1109/34.121791]

2 Chen Y,Medioni G.Object modeling by registration of multiple range images.Proceedings of 1991 IEEE International Conference on Robotics and Automation.Sacramento,CA,USA.1991.2724–2729.

3 王瑞巖,姜光,高全學.結合圖像信息的快速點云拼接算法.測繪學報,2016,45(1):96–102.

4 楊帆,白寶興,張振普,等.基于多視點云拼接算法研究.長春理工大學學報(自然科學版),2014,37(3):124–127.

5 索俊鋒,劉勇,蔣志勇,等.基于三維激光掃描點云數據的古建筑建模.測繪科學,2017,42(3):179–185.

6 周朗明,鄭順義,黃榮永.旋轉平臺點云數據的配準方法.測繪學報,2013,42(1):73–79.

7 馬敏杰,楊洋,范愛平,等.復雜建筑物三維激光掃描與室內外精細建模.測繪與空間地理信息,2015,38(1):111–113.

8 Wang GH,Hu ZY,Wu FC,et al.Implementation and experimental study on fast object modeling based on multiple structured stripes.Optics and Lasers in Engineering,2004,42(6):627–638.[doi:10.1016/j.optlaseng.2004.05.008]

9 李學軍,楊晟,李振舉,等.標識點快速提取與高精度單點匹配式定位算法.吉林大學學報(工學版),2014,44(4):1197–1202.

10 袁建英,王瓊,李柏林.利用標志點多視圖約束實現結構光掃描高精度粗拼接.計算機輔助設計與圖形學學報,2015,27(4):674–683.

11 李俊峰.大口徑深焦比Hindle球面鏡曲率半徑精確測量.電子測量與儀器學報,2014,28(12):1401–1407.

12 Zhang Y,Tao T,Mei XS,et al.An online spindle rotation error measurement system based on improved three point method.Proceedings of the 9th International Conference on Electronic Measurement &Instruments.Beijing,China.2009.651–656.

13 Wyngaerd JV,van Gool L,Kock R,et al.Invariant-based registration of surface patches.The Proceedings of the 7th IEEE International Conference on Computer Vision.Kerkyra,Greece.1999.301–306.

14 徐曉蘇,周峰,張濤,等.基于四元數自適應卡爾曼濾波的快速對準算法.中國慣性技術學報,2016,24(4):454–459.

15 張成,汪東,沈川,等.基于奇異值分解的可分離壓縮成像方法.計算機研究與發展,2016,52(12):2816–2823.[doi:10.7544/issn1000-1239.2016.20150414]