基于特征點和改進ICP的三維點云數據配準算法*

張曉娟，李忠科，王先澤，呂培軍，王 勇

（1．第二炮兵工程學院指揮自動化系，陜西西安 710025;2．北京大學口腔醫學院，北京 100871）

0 引言

隨著激光掃描技術的發展，利用激光掃描儀可以在幾秒鐘之內直接得到被測物體表面的點云數據，在三維物體數字化過程中，由于受測量設備測量范圍的限制和被測物體外形的復雜性等，三維檢測一次只能得到物體某一部分表面的數據，要得到物體完整的形狀信息，需要從不同角度使用多次定位進行測量，而將各個視角得到的點集合并到一個統一的坐標系下，這就是點云數據的配準，實際上，配準就是求解在不同視角下三維坐標點之間的轉換關系，它是航空航天、醫學圖像處理、曲面質量檢測和虛擬現實等領域的一項關鍵技術，有著廣泛的應用。

1 初始配準

點云數據配準前進行預配準，以減少精確配準過程的收斂時間，初始配準可以使兩組點云數據盡可能的靠近，從而縮小2個模型之間的差異，提高配準精度。一個好的預配準必須達到兩點:1）預配準的效率要高;2）預配準后的結果要盡可能和模型接近。這樣才能有效簡化迭代過程并達到預期的目的。

預配準的算法有力矩主軸法、遺傳算法、三點對齊法、基于特征點法等。力矩主抽法對于數據的缺失比較敏感，需要的時間很長，在精度要求不高的情況下可以使用。遺傳算法的進化過程比較耗時，配準時間比較長。三點對齊法原理簡單，能夠快速實現預配準，但需要準確確定三基準點的對應關系。基于特征點的預配準［7］可以快速完成配準，但是它不能消除配準過程中出現的二義性，所以，特征點的錯誤選擇可能導致配準誤差增大，甚至造成配準失敗。

本文采用一種基于特征點的等曲率預配準方法，首先計算每個點的曲率，曲率信息和點的對應關系采用哈希表［8］來映射，然后通過對曲率信息進行量化，得到等曲率的特征點，最后利用這些特征點完成預配準，算法如圖1所示。

圖1 點云初始配準Fig 1 Point cloud primary registration

由算法流程圖可以看出:它首先采用點的曲率對點云數據進行簡化，將搜索比較過程限制在同曲率點的范圍內，有效減少了比較特征點的個數，大大簡化了原始配準的過程。

2 精細配準

經過預配準后，兩組點云數據已經比較靠近，2個模型之間的差異已經縮小了很多，這時候再用迭代方法進行精細配準，就能達到較好的配準結果。

2．1 ICP概述與算法描述

ICP算法其原意是迭代最近點匹配算法，后來被廣泛理解為迭代對應點（iterative corresponding point）它是相對比較穩定和魯棒的算法，具有一些顯著的優點，很容易和其他算法結合，且很容易修改算法的一些步驟解決不同的實際問題。

ICP算法重復進行“確定對應關系點集并計算最優剛體變換”，直到某個表示正確匹配的收斂準則得到滿足，其變換關系式和收斂準則為

式中 Pi和Qi為2個數據點集，R為旋轉矩陣，T為平移向量，e達到最小時滿足收斂準則，其實質是基于最小二乘法的最優匹配方法。

1、葉菜類蔬菜（如大白菜、白菜、菠菜、芹菜等）葉面追肥以尿素為主，噴施濃度0.3%～0.5%，每667m2噴灑75～100kg，全生育期共噴2～3次，也可噴施0.3%米醋溶液，每667m2噴50kg左右。

2．2 鄰近搜索的ICP改進算法

ICP算法雖然具有較好的精度，但由算法描述可知，它采用的是全局搜索，故計算量很大且運算時間很長，針對這一缺點，本文采用鄰近搜索的ICP算法，由于ICP算法最耗費時間的步驟是求解鄰近點對的過程，為了縮短對應點的搜索時間，將搜索范圍限制到局部數據，而且經過了預配準后，數據之間差異縮小了，從而大大減少了計算量和運算時間。求解2個不同視圖中數據點之間的變換，即坐標旋轉變換R和平移變換T，是點云數據配準的本質。

2．2．1 鄰近關系對應準則

鄰近搜索算法假設2個點集P和Q之間有鄰近對應關系，給出2個鄰近集合p'和q'，這2個集合分別是從P和Q數據集合直接定義得來的，假設一個數據集合的2個鄰近點在另一個數據集里有對應的最近點，鄰近關系的對應準則是（如圖2）:2個數據集合P和Q，qs是ps對應的最近點，C（pi）是pi的鄰近集合，C'（qs）是qs的鄰近集合

若ps∈C（pi），則qi∈C'（qs），即pi在Q中的最近點qi就能在qs的鄰近集合C'（qs）中找到。

2．2．2 鄰近算法描述

從點云數據的拓撲關系看，每個點有8個鄰近點（不包含邊緣點），故鄰近算法可以這樣描述:鄰近關系C是P圍繞pi一個3×3的區域，C'是Q中的n×n的區域，從左至右一行一行的掃描P中的點，這樣可以在pi的8個鄰近候選點搜索檢驗并最終找到ps，一旦ps確定找到，而ps又有已知的最近點qs，就可以在Q中以qs為中心的n×n的區域內進行pi的最近點的搜索，一般任何一個候選點都有已知屬于它自己的最近點。鄰近搜索算法流程如圖3。

圖2 鄰近關系準則Fig 2 Relation rule of neighborhood

圖3 鄰近搜索算法流程Fig 3 Flow chart of neighborhood search algorithm

下面的偽代碼簡要描述了鄰近搜索算法:

輸入:點云數據P和 Q，相對應的鄰近集合C（p）和C'（q）

輸出:P中每個點pi，在Q中都存在它的最近點的近似值qi

采用鄰近搜索法進行二次精細配準的主要步驟:

1）迭代初始化:使用預配準后兩組點云的位置作為新的初始位置，并且將統計的可匹配點對集合作為初始的配準點對集合。經過預配準之后的點云數據為

2）最近點計算:計算點云數據pi∈FP的對應點qi，使‖pi－pj‖→min。基于特征點的等曲率預配準方法縮小了模型之間的差異，大大降低了這一步的代價，降低了復雜度。

3）優化求解:采用最優化解析方法計算旋轉變換R和平移變換T，使得∑‖Rpi+T－qj‖→min。

4）進行變換:用得到的R和T對FP進行旋轉和平移變換。

5）迭代終止判定:如果最小二乘誤差小于一給定的閾值 ε（ε＞0），即滿足dk－dk+1＜ε時，迭代終止。

3 算法實驗

本實驗通過對實際測量的一牙齒模型在多個視角下的數據點云進行配準，驗證了該算法的有效性和可靠性。

取ε=0．000 000 2，在實際計算中，若選取的闞值使得匹配失敗，則可適當放松約束閾值重新匹配，圖4（a），（b）為牙齒模型的2個配準視圖，（c）為初次配準后效果圖，（d）為精細配準后效果圖，（e）為用ICP算法的配準效果。從圖中可以看出:二次配準比初次配準更加精確，因為僅用精確配準可能會使配準趨向一個錯誤的方向，導致無法實現良好的配準效果，而先使用預配準而后再使用精細配準不僅能大幅提高配準精度，而且可以保證配準方向的合理性。

圖4 牙齒模型的配準Fig 4 Registration of dental cast

實驗中，本文也對ICP算法和本文算法進行了比較，主要在算法運行時間方面進行比較。經過對牙模型4個視角的數據點云進行實驗，驗證了該算法也有較好的配準速度，由表1的分析可以看出:與ICP算法相比，本文算法的效率較高，在配準速度上有明顯的優勢，而且點云數據量越大，配準速度優勢越明顯（表1中點云3為點云1和點云2配準后的新點云，同理，點云5是點云3和點云4配準后的新點云）。

表1 點云數據的兩種配準算法時間比較Tab 1 Comparison of registration time of two algorithms

4 結論

因為基于特征點的等曲率配準算法與鄰近搜索的ICP算法是很獨立的算法，但本文采用預配準和精細配準的形式將它們結合起來，實例證明:該方法提高了配準的精度和速度，克服了ICP算法計算量大且存在可能無法收斂到全局最優解的缺陷，具有更高的可靠性和穩定性，有較高的實際應用價值。算法對處理的點云數據規模無特別限制。

［1］ Besl P J，McKay N D．A method for registration of 3D shapes［C］∥IEEE Transactions on Pattern Analysis and Machine Intelligence，Washington D C:IEEE Computer Society，1992，14（2）:239－256．

［2］ Menq C H，Yau H T，Lai G Y．Automated precision measurement of surface profile in CAD－directed inspection［J］．IEEE Transaction on Robotics and Automation，2002，8（2）:268 －278．

［3］ Rusinkiewicz S，Levoy M．Efficient variant of the ICP algorithm［C］∥ The Third International Conference on 3D Digital Image and Modeling，Quebec City，Canada，2001:145 －152．

［4］ Mitra N J，Gelfand N，Pottmann H，et al．Registration of point cloud data from a geometric optimization perspective［C］∥Euro Graphics Symposium on Geometry Processing，2004:23 －32．

［5］ Chua C S，Jarvis R．Point signatures:A new representation for 3D object recognition［J］．International Journal of Computer Vision，1997，25（1）:63 －85．

［6］ Ko K H，Maekawa T，Patrikalakis N M．An algorithm for optimal free－form object matching［J］．Computer－Aided Design，2003，35（10）:913－923．

［7］ 羅先波，鐘約先，李仁舉．三維掃描系統中的數據配準技術［J］．清華大學學報:自然科學版，2004，44（8）:1104 －1106．

［8］ Behzad K P，Behrooz K P．An open problem in matching sets of 3D lines［C］∥2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR），Kauai，Hawaii，2001:651－656．