基于“滑移”主方向自適應采樣的ICP算法優化研究

姜曉通 戴 寧 張長東 崔海華 閆國棟 孫玉春

1.南京航空航天大學，南京，210016 2.北京大學口腔醫學院，北京，100081

0 引言

在生物醫學、文物保護、工業檢測、大型復雜氣動物理模型的再設計等領域，都需要獲得物體表面的點云數據。目前的光學掃描儀可以在數秒內獲得數十萬至上百萬個點數據。但在點云數據的獲取過程中，受測量原理以及被測物體表面形狀的影響，物體表面的完整數據往往需要通過多個視角、不同角度的測量完成。對不同視角的測量數據，需要將其統一到同一個全局坐標系下，從而恢復物體原有的表面形態。將各個數據統一到同一個坐標系下完成點云數據配準是獲得物體表面完整形態的關鍵技術之一。

點云配準作為實現上述功能的實現技術之一，一般可分為兩個步驟：粗配準和精確配準。粗配準將不同視角獲得的點云數據統一到同一坐標系下，常用的方法有轉臺法［1］、標簽法［2］和曲率特征法［3］。粗配準一般很難滿足高精度多視角拼合的要求，主要為精確配準提供初始位置。精確配準在粗配準的基礎上進一步使點云間的距離誤差達到最小，經融合最終得到一個完整的物體表面點云數據。目前國內外最常用的精確配準方法是由Besl等［4］提出的迭代最近點（iterative closest point，ICP）算法。國內外很多學者都對ICP算法進行了擴展研究，其研究重點主要是對ICP算法的精度和速度進行改進。Chen等［5］在ICP的基礎上提出利用點的切平面來逼近點云，將點與點之間的距離轉換為點到切平面之間的距離的方法，該方法迭代次數少，精度高，但配準速度較慢。Johnson等［6］使用特征提取策略去除沒有啟發信息的平面點來提高配準速度，但該方法無法達到較高的配準精度。王磊等［7］引入特征點的方法實現點云的配準，但其實質上這些特征點是一種標簽點，影響了物體表面點云的完整性。在實際的ICP配準過程中，由于忽略了數據本身的特點，上述ICP配準算法經常不能達到理想的效果。

ICP算法的最終目的在于計算匹配點云間準確的坐標變換矩陣，而計算準確的坐標變換矩陣的關鍵在于匹配點集的確定。但目前對于ICP處理前的數據點集的重疊區域計算、采樣策略確定等前處理研究的文獻較少。本文重點研究了ICP算法前處理數據的采樣策略，并在此基礎上提出一種新的三點插值確定匹配點的方法。首先利用最小歐氏距離確定初始的重疊區域，利用一種基于協方差矩陣的方法對點云重疊區域進行采樣，并在迭代的不同階段采用不同的“滑移”方向的采樣組合，有效地避免了迭代陷入局部極值，保證了算法的幾何穩定性。在確定匹配點時，利用匹配點的拓撲信息來改善匹配點集的質量，從而實現點云的精確配準。最后通過實驗證明了本文算法的有效性。

1 點云采樣

1.1 重疊區域分析

重疊區域的選擇在點云采樣中具有重要地位。重疊區域的準確確定不僅有利于提高采樣的準確性，而且有利于提高配準的速度。因為重疊區域是配準的關鍵區域，只有在重疊區域進行采樣，才能確保采樣的準確性。在確定重疊區域的同時，需要識別邊界區域，去除邊界點。邊界點的存在會使得在邊界區域存在大量的錯誤對應點，從而造成迭代不收斂的情況。如圖1所示，兩條短劃線段之間部分為實際的重疊區域，兩條點劃線段之間部分為計算的重疊區域，實線段的兩端點是在邊界處的匹配點對，大量這樣的匹配點對的存在會造成整體的不收斂。在對重疊區域進行分析時，本文利用點到點集的最小歐式距離來進行重疊區域分析，同時利用重疊點的拓撲信息來識別邊界點。

圖1 未識別邊界的配準結果

1.2 基于協方差矩陣重疊區域的采樣

在確定匹配點集之前，需對待配準的點云的重疊區域進行采樣，采樣可以在兩片點云或一片點云上進行，Rusinkiewicz等［8］從精度和速度兩個方面對兩種采樣方式進行了比較，當兩片點云相距“較遠”或重疊區域很小時，從兩片點云上都采樣對配準速度略有提高，但精度上卻沒有太大的改進。

采樣的方法很多，如均勻采樣法［9］、隨機采樣法［10］和法矢采樣法［8］。上述三種采樣方法都存在不同程度的采樣不準確而影響迭代精度的缺點。Gelfand等［11］提出了一種基于協方差矩陣的方法，此方法有效地保證了采樣的有效性，從而提高了ICP算法的幾何穩定性。該算法先計算每一個模型的“滑移”主方向。圖2所示為各個模型的“滑移”主方向，模型沿著自己的“滑移”主方向平移或旋轉，都會讓該模型產生一個“復本”，這種在“滑移”主方向上的無約束的平移或旋轉會導致迭代的不穩定。為了保證ICP算法的穩定性，需要對該方向上的平移或旋轉加以約束，對該方向的運動具有較強約束的點進行采樣，從而保證迭代的穩定性。設點集 P ＝ ｛p1，p1，…，pk｝，n1，n1，…，nk為各點所對應的單位法矢，則將各點及對應的單位法矢組合成一個協方差矩陣C如下：

圖2 模型的“滑移”主方向

其中，C是一個6×6矩陣，該矩陣的六個向量對應了該模型旋轉或平移的一個方向，其中矩陣具有較小特征值的特征向量對應了該模型的“滑移”主方向。設C的六個特征向量分別為x1，x2，…，x6；v1，v2，…，vk為各配準點對應的一個1×6的向量。對每一個向量，｜xivk｜與點vk對向量xi所對應的方向上的旋轉或平移的穩定性貢獻的大小成正比。因此，在“滑移”方向上，｜xivk｜值較大的點是需要的采樣點。圖3所示為利用上述方法所得到的不同模型的“滑移”主方向上對旋轉或平移的穩定性貢獻較大的采樣點。

1.3 采取不同的采樣策略

改進前后的配準結果對比如圖4所示。在實際配準中，若全都采用“滑移”方向上對迭代穩定性貢獻較大的采樣點，則會存在局部配準不精確的現象，如圖4b所示，“滑移”方向的采樣點組成的區域配準得較好，但非“滑移”方向采樣點組成的區域卻存在少量局部區域配準不精確的情況，其原因在于由于采樣點的局限性，使得模型在“主方向”上陷入局部極值。為了讓點云在重疊區域能夠達到最優的全局配準，避免上述情況的出現，在迭代的不同階段，本文采用不同的“滑移”方向的采樣組合。在迭代的過程中，設定一個迭代結束閾值t，以采樣點為基礎計算配準誤差，具體采樣策略如下：

圖3 不同模型“滑移”主方向對迭代穩定性貢獻較大的采樣點

圖4 改進前與改進后配準結果對比

（1）當配準誤差大于λ1t（例如λ1＝1.5）時，采用“滑移”主方向（特征值較小的特征向量對應的方向）上對穩定性貢獻較大的點進行配準。由于“滑移”主方向上對配準穩定性貢獻較大的點能夠有效地限制迭代過程中的“滑移”，這樣在配準初期既可以將兩配準模型較快地配準到一個相對理想的位置，加快配準的速度，又能夠避免在配準初期因為在特征不明顯的區域采樣過多的點而導致迭代陷入局部極限。

（2）當配準誤差小于等于λ1t時，在策略（1）的基礎上增加特征值較小的特征向量所對應的方向上對穩定性貢獻較大的點來進行配準，這樣既可以保證配準的穩定性，又能夠避免迭代在模型的“主方向”上陷入局部極值。

（3）當配準誤差小于等于λ2t（1＜λ2＜λ1）時，配準精度已接近要求的精度，此時在重疊區域對模型進行均勻采樣，對整個重疊區域的配準誤差進行“容差分配”，從而保證點云在重疊區域能夠達到最優的全局配準。其配準結果如圖4c所示，可以看出，此采樣策略能夠滿足精度要求。

2 基于法矢三點插值法確定匹配點

確定匹配點是ICP算法的核心。目前最常用的方法主要有三種［12］，如圖5所示。

圖5 三種確定匹配點的方法（p為采樣點，q為對應的匹配點）

“點到最近點”的方法雖然計算簡便、直觀、穩定，但因為在所確定的匹配點集中存在大量的錯誤對應點，算法迭代緩慢，且極易陷入局部極值。“點到視點投影點”的方法因為省去了搜索對應點步驟，可以極大地提高配準速度，但卻無法達到較高的拼接精度。“點到切平面垂足點”的方法在三種方法中精度最高，迭代次數少，且不易陷入局部極值，但速度較慢。應用最為廣泛的算法為點到切平面垂足點算法。本文提出一種基于法矢的三點插值的方法確定匹配點，此方法通過尋找三個最近點來插值出一個對應點，能夠在很大程度上減少錯誤對應點的存在，不易陷入局部極值，同時由于在重疊區域分析時已經識別并去除了邊界點，從而排除了邊界點的影響，在實際配準中能夠得到很好的配準精度（圖6）。然后在協方差采樣的基礎上進行隨機采樣，在保證采樣準確的同時減少采樣點的數量以及在尋找最近點的過程中利用k－d tree來確保配準的效率。其確定配準點算法的過程如下：

圖6 三點插值法確定匹配點

設采樣點為p，匹配點為q，np和nq分別為兩點的法矢，dmean為點云中點和點之間的平均距離。

（1）確定采樣點。確定每個采樣點p的三個最近點q1、q2、q3，并計算該采樣點到這三個點的距離d1、d2、d3。如｜d2－d1｜＞λdmean或｜d3－d1｜＞λ dmean或｜d3－d2｜＞λdmean，則舍去該采樣點，反之留下該采樣點。

（2）插值出匹配點。設dsum＝d1＋d2＋d3，d′1＝dsum／d1，d′2＝dsum／d2，d′3＝ dsum／d3，則 有d′sun＝d′1＋d′2＋d′3，λ1＝d′1／d′sun，λ2＝d′2／d′sun，λ3＝d′3／d′sun。插值匹配點q＝λ1q1＋λ2q2＋λ3q3。

（3）判斷匹配點對的法矢一致性。nq1、nq2、nq3分別為q1、q2、q3的單位法矢，np、nq1、nq2、nq3的計算可轉換為求協方差矩陣的最小特征值對應的特征向量問題，則插值點q的法矢為nq＝λ1nq1＋λ2nq2＋λ3nq3。若｜np·nq｜＜u，例如u＝0.9，則舍棄該匹配點，否則留下該匹配點。

3 求解優化迭代矩陣

匹配點確定后，利用最小二乘法迭代求解最優變換矩陣，通常可采用以下四種方法：單位四元數法、奇異值分解法、正交矩陣法和對偶四元數法。Eggert等［13］從精度和穩定性方面對這四種方法做了比較，指出這四種方法的性能相差很小。本文擬采用奇異值分解法來求解最優矩陣。

本文運用前處理優化后的ICP算法進行精確配準，設兩片點云為P、Q，主要步驟如下（偽代碼表示）：

4 實例與分析

4.1 實例比較

圖7 利用經典ICP，Rapidform2006，Geomagic Studio 12以及本文算法匹配結果

表1 不同算法點云配準精度比較 mm

4.2 結果分析

從實例對比中可以看出，本文所采用的基于協方差矩陣的采樣能夠避免迭代陷入局部極值的現象，算法具有較高的幾何穩定性。在基于協方差矩陣采樣的基礎上，提出了基于法矢三點插值的方法確定匹配點，能夠在很大程度上去除錯誤的匹配點對，從而達到較高的配準精度。

5 結語

散亂點云精確配準技術是獲得被測物體完整模型的一個關鍵步驟。針對這一問題，本文在已有相關理論的基礎上，重點研究ICP算法迭代過程中的采樣點策略，同時提出一種新的確定匹配點的方法，以及如何在此基礎上提高ICP算法的精度及速度。實例表明本文算法對點云數據的配準具有較好的精度，同時具有較高的可靠性和穩定性，能夠避免局部極值現象的出現。本文算法在精度以及穩定性上取得了較好的結果，后續研究的重點將在模型的適應性上對算法進行改進，同時將引入并行計算與智能匹配策略，使之能夠適應海量數據模型的配準。

［1］謝則曉，張國成，張國雄.線結構光測量數據的自動拼合方法［J］.中國機械工程，2005，16（9）：775－778.Xie Zexiao，Zhang Chengguo，Zhang Guoxiong.An Automatic Registration Method for the Data Patches Obtained by Structured－light Sensons［J］.China Mechanical Engineering，2005，16（9）：775－778.

［2］羅先波，鐘約先，李仁舉.三維掃描系統中的數據配準技術［J］.清華大學學報，2004，44（8）：1104－1106.Luo Xianbo，Zhong Yuexian，Li Renju.Data Registration in 3－D Scanning Systems［J］.J.Tsinghua Univ.，2004，44（8）：1104－1106.

［3］朱延婿，周來水，張麗艷.散亂點云數據配準算法［J］.計算機輔助設計與圖形學學報，2006，18（4）：475－481.Zhu Yanxu，Zhou Laishui，Zhang Liyan.Registration of Scattered Cloud Data［J］.Journal of Computer－aided Design ＆ Computer Graphics，2006，18（4）：475－481.

［4］Besl P J，McKay N D.A Method for Registration of 3－D Shapes［J］.IEEE Transactions on Pattern A－nalysis and Machine Intelligence，1992，14（2）：239－256.

［5］Chen Y，Medioni G.Object Modeling by Registration of Multiple Range Images［J］.Image and Vision Computing，1992，10（3）：145－155.

［6］Johnson A，Hebert M.Surface Registration by Matching Oriented Points［C］／／Proceedings of International Conference on Recent Advances in 3－Digital Imaging and Modeling.Ottawa，1997：121－128.

［7］王磊，邢淵.反向工程中數據點云的拼合［J］.模具技術，2004（1）：47－49.Wang Lei，Xing Yuan.The Merge of Date Point Could in Reverse Engineering［J］.Die and Mould Technology，2004（1）：47－49.

［8］Rusinkiewiez S.Levoy M.Efficient Variants of the ICP Algorithm［C］／／Proceeding of the 3rd International Conference on 3DDigital Imaging and Modeling.Quebec，2001：145－152.

［9］Masuda T.Generation of Geometric Model by Registration and Integration of Multiple Range Images［C］／／Proceedings of the 3rd International Conference on 3DDigital Imaging and Modeling.Quebec，2001：254－261.

［10］Masuda T，Yokoya N.A Robust Method for RegIstration and Segmentation of Multiple Range ImaGes［J］.Computer Vision and Image Uniderstanding，1995，61（3）：295－307.

［11］Gelfand N，Ikemoto L，Rusinkiewicz S，et al.Geometrically Stable Sampling for the ICP Algorithm［C］.／／Proceedings of the 4th International Conference on 3DDigital Imaging and Modeling.Banff，2003：260－267.

［12］謝則曉，徐尚.三維點云數據拼接中ICP及其改進算法綜述［J］.中國海洋大學學報，2010，40（1）：99－103.Xie Zexiao，Xu Shang.A Survey on the ICP Algorithm and Its Variants in Registration of 3DPoint Clouds［J］.Periodical of Ocean University of China，2010，40（1）：99－103.

［13］Eggert D W，Lorusso A，Fisher R B.Estimating 3－D Rigid Body Transformations：a Comparison of Four Major Algorithms［J］.Machine Vision and Applications，1997，9（5／6）：272－290.