朱桂林，張棟良，陳輝
（上海電力學院 自動化工程學院，上海市電站自動化技術重點實驗室， 上海 200090）
摘要：針對同一物體不同視角下獲得的三維點云數據，提出一種基于改進特征點對選取的三維點云配準方法。在歐氏距離的基礎上選取與目標點最近的三點均值為對應點，并應用鄰域比值法來剔除錯誤點，結合Kd tree提高搜索速度，實現最終點云配準。實驗結果表明，該方法具有可行性，相比傳統ICP算法，其匹配精度和效率明顯提升。
關鍵詞：點云配準；ICP算法；最近點選取；錯誤點剔除
中圖分類號：TP391文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.01.022
引用格式：朱桂林，張棟良，陳輝. 基于改進特征點對選取的三維點云配準［J］.微型機與應用，2017,36（1）：73-75.
0引言
利用激光掃描儀對建筑物進行掃描，得到其點云信息，從而建立物體的三維模型，成為當下研究的熱點［1］。但在實際操作中往往受到各種限制，無法一次性精準地獲得待測物體的全部點云信息。為了在后期重建過程中得到較為完整的三維模型，實際測量中需要對待測物體進行多角度、多次數的測量并且通過點云配準將獲得的點云數據變換到同一坐標中［2］。
針對點云配準過程，迭代最近點算法（Iterative Closest Point，ICP）［3］是目前比較經典的配準方法。其優點是對初始點云形狀要求低，配準過程簡單，結果相對收斂。但是該算法也存在著一些不足，如：要求待配準兩片點云的數據為包含關系，兩片點云中的數據點滿足一一對應關系；其次隨著點云數量的增加計算代價也相應增加；最后在對應點尋找過程中，僅僅假設兩片點云中歐氏距離最近的點為所求的對應點，由于這種假設過于理想化，在實際操作過程中可能會出現錯誤的對應點，使配準陷入局部最小值導致配準失敗。針對傳統ICP算法的不足，國內外學者在配準策略、配準元素、錯誤點剔除以及誤差度量等方面對算法進行了改進與優化，使傳統ICP算法在性能方面得到提高［47］。
本文在三維點云配準過程中分以下兩步：
?。?）提出了一種改進的特征點對選取方法，過程采用Kd tree查找最近點以提高搜索效率。對于原始點云中的一點，尋找其在目標點云中歐氏距離最近的三點并計算三點的平均值，以此作為對應點，然后利用鄰域比值的方法來剔除誤匹配點，提高匹配精度，最后結合四元法［89］求取旋轉矩陣R及平移向量T。
?。?）根據計算得到的初始矩陣R及平移向量T，利用ICP算法對兩片點云進行配準。
1算法過程
1.1對應點對選取和剔除錯誤點對
?。?）對應點對求取
利用Kd tree計算點集P中任一點pi(i=1,2，...)在目標點集Q中與其歐氏距離最近的三個點q1、q2、q3，分別計算三點x、y、z的均值構成新的坐標(=())，pi與構成對應點對(pi)。
?。?）錯誤點對剔除
點集采集過程中不可避免地引入噪聲點，因此在對應點的計算過程中可能會產生錯誤對應點對，本文采用鄰域點集比值法來檢驗對應點對是否符合標準，并剔除錯誤點對。由對應關系可知，如果兩個點是對應點則其在各自δ鄰域內所包含的點數應該近似相等。實驗過程中在點云P和點云Q內分別計算pi與以δ為半徑所構成鄰域內點的個數m和n。若mn=γ(0.9≤γ≤1.1)，保留對應點對，否則剔除。如下圖1。
1.2四元數法求配準矩陣R和T
對于原始點云數據,在求取旋轉矩陣R和平移向量T時，采用四元數法，其計算過程如下：
?。?） 分別計算點集{pi}和點集{qi}的質心：
?。?）求K的特征值并且求解最大特征值所對應的單位特征向量d,d=［d1d2d3d4］T
?。?）求解旋轉矩陣R
![YZ(QHR3[]()%R4LGTGRR75O.png](http://files.chinaaet.com/images/2017/03/02/6362407783596167248132463.png "YZ(QHR3[]()%R4LGTGRR75O.png")
?。?）根據R與T的對應關系求取平移向量T
T=μq－Rμp（7）
1.3改進ICP算法的配準過程
ICP算法在本質上是使用最小二乘的方法對待配準的點云數據進行最優匹配。計算過程中重復進行選擇對應關系點對，計算最優旋轉矩陣R和平移矢量T,直到滿足正確的收斂精度函數E并使E達到最小值。
式中,Pi為原數據的初始點集；Qi為Pi對應目標數據點集的最近點；R為3×3旋轉矩陣；T為3×1平移矢量。
配準過程具體如下：
?。?） 讀取初始點云并在初始點云中選取點集pi；
?。?） 利用Kd tree對點集p中任一點pi計算其在點集q內歐氏距離最近的三個點q1、q2、q3，并計算，過程對應點對(pi)；
（3）采用鄰域點集比值法剔除不符合條件的對應點；
?。?）采用四元數法計算旋轉矩陣R和平移矢量T；
?。?）迭代終止判斷：若ek－ek+1<ε，則終止迭代，否則重復（2）~（5）直至結果滿足收斂條件。其中ε表示大于零的閾值。
2實驗論證
本實驗采用的實驗數據來自斯坦福兔子（Stanford Bunny），分別選取不同視角下的兩組點云數據作為原始點云和目標點云，兩片點云的數量分別為35 947和30 379。實驗平臺為：CPU 2.70 GHz，內存4 GB，Windows7 32位操作系統；算法在MATLAB 2011b環境中實現，實驗選取的ε=0.005。
實驗過程中為了進一步驗證本文方法的可行性，減少中間誤差，在與傳統ICP算法比較過程中，本文分別從迭代次數和迭代點云數量兩方面（即更改迭代次數以及更改點云數量）進行驗證。
2.1迭代次數
為消除實驗過程中次數對結果的影響，對于Stanford Bunny操作過程中分別選取迭代次數為5次、10次以及15次作為一組參照進行對比驗證，實驗結果如表1。表1不同迭代次數下兩種方法配準效果原始數據點云圖ICP配準效果圖本文配準方法效果圖迭代次數5次10次15次從表1可得出，在使用相同的初始點云數據情況下：（1）迭代次數相同時，本文所采用的改進ICP算法所得出的配準效果明顯優于傳統ICP算法；（2）隨著迭代次數增加，傳統ICP算法配準效果逐級優化，但是采用改進算法所得到的配準圖像逐級優化效果更加明顯。
為了進一步比較改進算法相對于傳統ICP算法的優勢，在基于不同迭代次數情況下分別從配準時間以及配準誤差兩個方面進行列表對比，本文采用均方根誤差［10］（Root Mean Square，RMS）來表示配準誤差，對比情況如表2。
從表2可以看出，在同一迭代次數下改進算法與傳統ICP算法相比在配準誤差以及配準時間上都得到了明顯優化，這種優化隨著迭代次數的增加變得更加明顯，例如迭代次數為5時，傳統ICP算法配準時間為240.37 s，配準誤差為0.122 4，而改進的ICP算法配準時間為22.70 s，配準誤差為0.066 0；當迭代次數為15時，傳統ICP算法配準時間為610.45 s，配準誤差為0.037 6，此時改進ICP算法配準時間僅為40.89 s，配準誤差為0.002 4。綜上，無論是在同一迭代次數的橫向對比還是在不同迭代次數的縱向對比中，本文采用的配準方法在配準效果、配準時間以及配準誤差上都要明顯優于傳統ICP算法。
2.2迭代點云數量
為了消除點云數量對兩種方法產生的誤差，本文在基于Bunny數據基礎上，選取初始點云數量分別為400點、3 600點、6 400點以及32 400點，并在迭代次數同為15次的基礎上進行對比驗證，結果如表3。
根據表3，在初始點云數較少的情況下，改進方法與傳統ICP方法相比在配準時間和配準誤差上均有進步，但差別并不明顯，如在點云數為400點時二者配準時間相差為0.05 s，在小數點后精確5位的情況下配準誤差同為0.089 79。但是隨著點云數量的增加，改進的ICP算法與傳統ICP算法相比具有明顯優勢，例如當初始點云數量為6 400時，傳統ICP算法配準時間為16.00 s，配準誤差為0.046 38，而改進ICP算法配準時間僅為2.40 s，配準誤差為0.037 35；當初始點云數量為32 400時，改進算法優勢更為突出。由表3數據分析可知，在不同點云數量下改進的ICP方法與傳統ICP算法相比，無論是在配準時間還是在配準誤差上都具有明顯改進，并且隨著初始點云數量的增加，本文改進方法的優勢彰顯得更為明顯。
3結論
本文針對三維點云數據配準耗時長、精度低兩方面的不足進行了相應改進，提出了一種改進特征點對選取方法，通過在經典點云Standford Bunny數據集上與采用傳統ICP算法的配準結果相比，在配準時間和配準精度上都有明顯提高。本文對點云數據配準的優化，對后續點云網格化以及場景重建提供了算法基礎。
參考文獻
?。?］ TANG P B,HUBER D， AKINCI B， et al.Automatic reconstruction of asbuilt building information models from laserscanned point clouds:a review of related techniques［J］.Automation in Construction,2010,19(7):829-843.
［2］ 韓寶昌，曹俊杰，蘇志勛.一種區域層次上的自動點云配準算法［J］.計算機輔助設計與圖形學學報, 2015，27(2):313-
319.
?。?］ BESL P J, MCKAY N D. Method for registration of 3D shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992，14(2):239-256.
?。?］ Guo Yu, BENNAMOUN M, SHOEL F, et al.3D object recognition in cluttered scenes with local surface features: a survey［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014,36(11):2270-2287.
［5］ 楊小青, 楊秋翔，楊劍.基于法向量改進的ICP算法［J］.計算機工程與設計, 2016， 37(1):169-173.
［6］ 許斌, 李忠科，呂培軍，等.基于特征的點云精確配準算法［J］.計算機應用與軟件, 2013,30(11):112-115.
?。?］ 張曉娟,李忠科，王先澤,等.基于特征點和改進ICP的三維點云數據配準算法［J］.傳感器與微系統, 2012，31(9):116118.
?。?］ KUIPERS J B. Quaternions and rotation sequences［M］.Sofia: Coral Press,2000:127-143.
?。?］ HORN B K P.Closed-form solution of absolute orientation using unit quaternions［J］.Optical Society of America, 1987,4(4):629-642.
?。?0］ EGGERT D W, LORUSSO A.Estimating 3D rigid body transformations a comparison of four major algorithms［J］.Machine Vision and Applications, 1997,9(5):272-290.