基于“滑移”主方向自適應(yīng)采樣的ICP算法優(yōu)化研究

姜曉通 戴 寧 張長(zhǎng)東 崔海華 閆國(guó)棟 孫玉春

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

0 引言

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

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

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

1 點(diǎn)云采樣

1.1 重疊區(qū)域分析

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

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

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

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

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

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

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

1.3 采取不同的采樣策略

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

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

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

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

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

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

2 基于法矢三點(diǎn)插值法確定匹配點(diǎn)

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

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

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

圖6 三點(diǎn)插值法確定匹配點(diǎn)

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

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

（2）插值出匹配點(diǎn)。設(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。插值匹配點(diǎn)q＝λ1q1＋λ2q2＋λ3q3。

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

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

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

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

4 實(shí)例與分析

4.1 實(shí)例比較

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

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

4.2 結(jié)果分析

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

5 結(jié)語(yǔ)

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

［1］謝則曉，張國(guó)成，張國(guó)雄.線結(jié)構(gòu)光測(cè)量數(shù)據(jù)的自動(dòng)拼合方法［J］.中國(guó)機(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é)報(bào)，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］朱延婿，周來(lái)水，張麗艷.散亂點(diǎn)云數(shù)據(jù)配準(zhǔn)算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ù)點(diǎn)云的拼合［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］謝則曉，徐尚.三維點(diǎn)云數(shù)據(jù)拼接中ICP及其改進(jìn)算法綜述［J］.中國(guó)海洋大學(xué)學(xué)報(bào)，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.