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

1.南京航空航天大學(xué)，南京，210016 2.北京大學(xué)口腔醫(yī)學(xué)院，北京，100081

0 引言

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

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

ICP算法的最終目的在于計算匹配點云間準(zhǔn)確的坐標(biāo)變換矩陣，而計算準(zhǔn)確的坐標(biāo)變換矩陣的關(guān)鍵在于匹配點集的確定。但目前對于ICP處理前的數(shù)據(jù)點集的重疊區(qū)域計算、采樣策略確定等前處理研究的文獻較少。本文重點研究了ICP算法前處理數(shù)據(jù)的采樣策略，并在此基礎(chǔ)上提出一種新的三點插值確定匹配點的方法。首先利用最小歐氏距離確定初始的重疊區(qū)域，利用一種基于協(xié)方差矩陣的方法對點云重疊區(qū)域進行采樣，并在迭代的不同階段采用不同的“滑移”方向的采樣組合，有效地避免了迭代陷入局部極值，保證了算法的幾何穩(wěn)定性。在確定匹配點時，利用匹配點的拓?fù)湫畔砀纳破ヅ潼c集的質(zhì)量，從而實現(xiàn)點云的精確配準(zhǔn)。最后通過實驗證明了本文算法的有效性。

1 點云采樣

1.1 重疊區(qū)域分析

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

圖1 未識別邊界的配準(zhǔn)結(jié)果

1.2 基于協(xié)方差矩陣重疊區(qū)域的采樣

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

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

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

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

1.3 采取不同的采樣策略

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

圖3 不同模型“滑移”主方向?qū)Φ€(wěn)定性貢獻較大的采樣點

圖4 改進前與改進后配準(zhǔn)結(jié)果對比

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

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

（3）當(dāng)配準(zhǔn)誤差小于等于λ2t（1＜λ2＜λ1）時，配準(zhǔn)精度已接近要求的精度，此時在重疊區(qū)域?qū)δＰ瓦M行均勻采樣，對整個重疊區(qū)域的配準(zhǔn)誤差進行“容差分配”，從而保證點云在重疊區(qū)域能夠達到最優(yōu)的全局配準(zhǔn)。其配準(zhǔn)結(jié)果如圖4c所示，可以看出，此采樣策略能夠滿足精度要求。

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

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

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

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

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

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

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

（2）插值出匹配點。設(shè)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的計算可轉(zhuǎn)換為求協(xié)方差矩陣的最小特征值對應(yīng)的特征向量問題，則插值點q的法矢為nq＝λ1nq1＋λ2nq2＋λ3nq3。若｜np·nq｜＜u，例如u＝0.9，則舍棄該匹配點，否則留下該匹配點。

3 求解優(yōu)化迭代矩陣

匹配點確定后，利用最小二乘法迭代求解最優(yōu)變換矩陣，通?？刹捎靡韵滤姆N方法：單位四元數(shù)法、奇異值分解法、正交矩陣法和對偶四元數(shù)法。Eggert等［13］從精度和穩(wěn)定性方面對這四種方法做了比較，指出這四種方法的性能相差很小。本文擬采用奇異值分解法來求解最優(yōu)矩陣。

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

4 實例與分析

4.1 實例比較

圖7 利用經(jīng)典ICP，Rapidform2006，Geomagic Studio 12以及本文算法匹配結(jié)果

表1 不同算法點云配準(zhǔn)精度比較 mm

4.2 結(jié)果分析

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

5 結(jié)語

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

［1］謝則曉，張國成，張國雄.線結(jié)構(gòu)光測量數(shù)據(jù)的自動拼合方法［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］羅先波，鐘約先，李仁舉.三維掃描系統(tǒng)中的數(shù)據(jù)配準(zhǔn)技術(shù)［J］.清華大學(xué)學(xué)報，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］朱延婿，周來水，張麗艷.散亂點云數(shù)據(jù)配準(zhǔn)算法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，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］王磊，邢淵.反向工程中數(shù)據(jù)點云的拼合［J］.模具技術(shù)，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］謝則曉，徐尚.三維點云數(shù)據(jù)拼接中ICP及其改進算法綜述［J］.中國海洋大學(xué)學(xué)報，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，F(xiàn)isher 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.