一種基于高斯曲率的ICP改進(jìn)算法*

王飛鵬，肖 俊，王 穎，王云標(biāo)

(中國科學(xué)院大學(xué)人工智能技術(shù)學(xué)院，北京 100049)

隨著計(jì)算機(jī)技術(shù)的發(fā)展，三維建模技術(shù)在工程建模、數(shù)字城市、文物保護(hù)和自動駕駛等領(lǐng)域的應(yīng)用日益廣泛。而如何獲取完整的物體表面信息則是其中最為基礎(chǔ)的課題之一。由于點(diǎn)云采集設(shè)備有限的視角、物體的遮擋以及采集環(huán)境等限制，通常來說，需要多角度、多批次采集才能獲取物體完整的表面信息。點(diǎn)云配準(zhǔn)則是把這些多批次、多角度獲取到的點(diǎn)云數(shù)據(jù)整合到同一個視角中去的過程。從數(shù)學(xué)角度講，每個點(diǎn)云數(shù)據(jù)都有其自身的坐標(biāo)系。點(diǎn)云配準(zhǔn)需要解決的問題則是通過坐標(biāo)系變換，將這些不同坐標(biāo)系的點(diǎn)云數(shù)據(jù)轉(zhuǎn)換到同一個坐標(biāo)系下。

作為計(jì)算機(jī)視覺的基本問題之一，點(diǎn)云配準(zhǔn)研究在過去的二三十年里取得了豐碩的成果[1]。其中，最為常用的點(diǎn)云配準(zhǔn)算法是ICP算法(iterative closest point)[2]。ICP算法采用迭代最優(yōu)化的思想，每次迭代追求目標(biāo)點(diǎn)云與源點(diǎn)云之間距離最小，最終算法收斂到一個當(dāng)前最優(yōu)狀態(tài)。這種算法思想簡單，容易實(shí)現(xiàn)，獲得結(jié)果的精度高。然而，在初始位置不理想的情況下，這種算法獲得的當(dāng)前最優(yōu)結(jié)果有可能只是局部最優(yōu)而非全局最優(yōu)。而且，這種方法也容易受到噪聲和離群點(diǎn)的影響，最終導(dǎo)致配準(zhǔn)失敗。同時，由于每次迭代都需要計(jì)算2個點(diǎn)云之間的最近點(diǎn)，因而計(jì)算復(fù)雜度較高。這些缺點(diǎn)很大程度上限制了ICP的應(yīng)用場景。為改善這些缺點(diǎn)，一大批方法被提出[1,3-10]。 其中，Masuda等[5]，Godin[6]及Weik[7]提出的基于下采樣的方法有效改善了ICP的運(yùn)行效率，卻導(dǎo)致配準(zhǔn)的精度下降。Bosse和Zlot[11]，Gelfand等[10]及Segal等[9]分別引入點(diǎn)到線、點(diǎn)到面和面到面的距離替代ICP中點(diǎn)到點(diǎn)的距離以改善其效率。然而，這些方法都需要配準(zhǔn)點(diǎn)云對象有比較明顯的線面特征(如室內(nèi)場景)。Yang等[8]引入分支限界的思想提出一種獲得全局最優(yōu)的ICP改進(jìn)算法，改善了局部最優(yōu)的缺點(diǎn)；但在實(shí)驗(yàn)中，運(yùn)算時間過長，效率過低。

針對ICP運(yùn)行效率低下和易受噪聲與離群點(diǎn)影響的缺點(diǎn)，本文提出一種基于高斯曲率的改進(jìn)算法。該方法利用高斯曲率不僅過濾掉大量配準(zhǔn)非關(guān)鍵點(diǎn)，提高了ICP算法運(yùn)行效率；而且也過濾掉大部分的噪聲點(diǎn)和離群點(diǎn)，增強(qiáng)了算法的健壯性。特別地，本方法獲得上述優(yōu)點(diǎn)的同時并不降低配準(zhǔn)的精度。相較于同樣利用表面特征如線、面等的改進(jìn)算法，本方法只需要點(diǎn)云對象有一定的曲率特征(凸出、凹陷、拐角、邊線等等)，因而適應(yīng)性更為廣泛。同時，本方法還具有良好的擴(kuò)展性，很容易移植到其他ICP改進(jìn)方法上以獲得綜合的優(yōu)點(diǎn)。

1 背景知識

在剛體變換中，點(diǎn)云配準(zhǔn)是指求2個點(diǎn)云之間的旋轉(zhuǎn)矩陣和平移向量，將源點(diǎn)云變換到與目標(biāo)點(diǎn)云相同的坐標(biāo)系下的過程。整個過程表示為

Pt=RPs+t，

(1)

式中：Pt為目標(biāo)點(diǎn)云，Ps為源點(diǎn)云，R代表旋轉(zhuǎn)矩陣，t代表平移向量。經(jīng)典的ICP算法通過不斷迭代減小兩點(diǎn)云變換后的誤差，直到收斂。其目標(biāo)函數(shù)為

(2)

作為基本的幾何量之一，曲率描述曲面表面的彎曲程度。其中，高斯曲率在物體表面曲率中有著特殊地位。根據(jù)高斯絕妙定理，高斯曲率是內(nèi)稟的。這意味著高斯曲率在保距變換中保持不變。記曲面第一和第二基本形式分別為和, 則高斯曲率可以表示成

(3)

表面曲率是計(jì)算機(jī)視覺和計(jì)算機(jī)圖形學(xué)的重要研究課題之一。在這個方面，同樣產(chǎn)生了大量關(guān)于曲率計(jì)算的成果[12-17]。 馬驪溟等[18]提出一種計(jì)算散亂點(diǎn)云高斯曲率的方法。此方法根據(jù)最小二乘法求出點(diǎn)鄰域內(nèi)的曲面模型，然后再利用梯度法搜索曲面上高斯曲率極值點(diǎn)。接著將該點(diǎn)作為搜索曲率極值點(diǎn)的初始點(diǎn)，并沿著主曲率方向搜索該點(diǎn)鄰域其余主方向上的極值點(diǎn)。這個方法既繼承了傳統(tǒng)方法中擬合二次曲面模型并求極值的方法[19]，又避免了計(jì)算全部點(diǎn)，提高了計(jì)算效率。Zhang等[17]提出一種估計(jì)鄰域點(diǎn)的法向量，而后利用歐拉公式將主曲率求解問題轉(zhuǎn)化成最小二乘問題的方法。這些方法對本算法中高斯曲率的計(jì)算有直接的指導(dǎo)意義。

2 基于高斯曲率的ICP優(yōu)化配準(zhǔn)算法

本算法分為兩個關(guān)鍵步驟。第一步，求取高斯曲率并根據(jù)高斯曲率過濾配準(zhǔn)非關(guān)鍵點(diǎn)。第二步，在配準(zhǔn)關(guān)鍵點(diǎn)上應(yīng)用ICP算法，獲得配準(zhǔn)結(jié)果。關(guān)于高斯曲率的估計(jì)方法有很多，其中Zhang等[17]提出的算法，原理清晰，效率高且結(jié)果較為精確。本文將以此算法為例介紹高斯曲率的計(jì)算過程。

(4)

式中：α為向量N與向量pqi之間的夾角；β為向量N與向量Mi之間的夾角； |pqi|為p與qi之間的歐氏距離。

2) 根據(jù)歐拉公式，法曲率與主曲率有以下關(guān)系

(5)

其中：i=1,2,…,m，k1和k2是主曲率；θi+θ為點(diǎn)p過qi的法截線的切線與主方向的夾角。

3) 令Ui=k1cos2(θi+θ)+k2sin2(θi+θ)。最終，求主曲率的問題可以轉(zhuǎn)化成求解方程(6)所示的最小二乘問題。求解此最小二乘問題以獲得主曲率k1與k2，而k1×k2即為高斯曲率[20]。

(6)

從以上計(jì)算過程可以看出，在點(diǎn)云數(shù)據(jù)中，點(diǎn)的高斯曲率定義于其鄰域上。一般而言，在大的鄰域上計(jì)算出的高斯曲率其數(shù)值相對小，比較穩(wěn)定，但運(yùn)算時間較長；而小的鄰域上計(jì)算出的高斯曲率其數(shù)值相對大，而穩(wěn)定性稍差，運(yùn)算時間較短。在實(shí)際配準(zhǔn)場景中，一般鄰域半徑的選擇應(yīng)能基本覆蓋表面的彎曲特征。圖1給出高斯曲率在Budda模型上的分布(由藍(lán)到紅表示其高斯曲率由小到大)，點(diǎn)的鄰域設(shè)為 0.001而點(diǎn)與點(diǎn)之間的間隔約為0.000 3。同時可以看出，高斯曲率較大的地方在于角、凹陷等彎曲特征比較明顯的區(qū)域。而這些區(qū)域則是點(diǎn)云配準(zhǔn)的關(guān)鍵區(qū)域。

圖1 Buddha模型表面的高斯曲率分布圖Fig.1 Distribution of Gaussian curvature on the surface of Buddha model

在獲取高斯曲率之后，設(shè)置閾值過濾高斯曲率過高和過低的點(diǎn)。過低的點(diǎn)，一般位于平坦的面上，對配準(zhǔn)貢獻(xiàn)不大；而過高的點(diǎn)，則是噪聲點(diǎn)或離群點(diǎn)，對配準(zhǔn)有害。

經(jīng)過高斯曲率過濾之后，剩余的點(diǎn)只有原來很少的一部分。這些剩余的點(diǎn)被認(rèn)為是物體表面的關(guān)鍵點(diǎn)。在2個點(diǎn)云數(shù)據(jù)的關(guān)鍵點(diǎn)上應(yīng)用ICP，不僅能顯著提高ICP運(yùn)行速度，而且使整個算法有更強(qiáng)的健壯性。 同時，由于這些關(guān)鍵點(diǎn)在過濾之后依然保持原來的密度，這樣應(yīng)用ICP之后，并不會因?yàn)檫^濾而導(dǎo)致配準(zhǔn)精度下降。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)說明

根據(jù)引入高斯曲率的目的，本文將從以下方面評估本方法的有效性和健壯性：不同大小的點(diǎn)云數(shù)據(jù)、不同的噪聲情況和離群點(diǎn)情況。第1部分實(shí)驗(yàn)中，使用公共數(shù)據(jù)集中的Standford Bunny、Armadillo以及 Buddha模型評估本算法的有效性；使用Standford Bunny分別在100%的離群點(diǎn)和100%的高斯噪聲環(huán)境下進(jìn)行實(shí)驗(yàn)，以評估本方法的抗噪聲和離群點(diǎn)的能力。 第2部分實(shí)驗(yàn)中，使用實(shí)際采集的工程數(shù)據(jù)驗(yàn)證本算法對ICP算法健壯性的改進(jìn)。同時，通過在不同采樣率下本算法與ICP執(zhí)行時間的比較，驗(yàn)證本算法對ICP在執(zhí)行時間方面的提升。 盡管本文算法是對ICP的改進(jìn)算法，為了描述方便，以下將經(jīng)典的ICP稱為ICP，而將本文提出的改進(jìn)算法稱為本方法。

本文所有實(shí)驗(yàn)以C++來實(shí)現(xiàn)，運(yùn)行在I5-3 320 M CPU, 8 G內(nèi)存的PC機(jī)上。第1部分實(shí)驗(yàn)所使用的數(shù)據(jù)來自于佐治亞理工學(xué)院提供的公共數(shù)據(jù)集。第2部分實(shí)驗(yàn)使用的工程數(shù)據(jù)掃描于北京香山公園的一處建筑，掃描儀器為Leica P30地面激光掃描儀。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 公共數(shù)據(jù)實(shí)驗(yàn)

第1組實(shí)驗(yàn)評估在一般條件下，與ICP相比，本方法的運(yùn)行效率及配準(zhǔn)精度。其結(jié)果如圖2所示，運(yùn)行時間及配準(zhǔn)精度記錄于表1前3行。從圖2可以看出，本方法與ICP都能獲得較好的結(jié)果。 從表1也可以看出：以均方根誤差(root mean square error, RMSE)衡量配準(zhǔn)精度，對于圖2的實(shí)驗(yàn)，本方法與ICP取得結(jié)果精度相當(dāng)，但本方法在運(yùn)行時間上更為快速。本組實(shí)驗(yàn)表明，在保證精度的前提下，本方法確實(shí)獲得了效率上的較大提升。

圖2 本方法在公共數(shù)據(jù)集下的表現(xiàn)Fig.2 Results of the proposed method on the public models

圖3 本方法在離群點(diǎn)和噪聲情況下的表現(xiàn)Fig.3 Results of the proposed method under the outlier and noise circumstance

第2組實(shí)驗(yàn)評估在重噪聲和離群點(diǎn)的條件下，與ICP相比，本方法抗噪聲及離群點(diǎn)的能力。其結(jié)果如圖3所示(其中，左、中、右分別為初始位置、ICP算法結(jié)果和本方法結(jié)果)，運(yùn)行時間及配準(zhǔn)精度記錄于表1后2行。圖3(a)實(shí)驗(yàn)中添加100%離群點(diǎn)，圖3 (b) 實(shí)驗(yàn)中添加100%標(biāo)準(zhǔn)方差為5倍點(diǎn)間距的高斯噪聲。可以看出，在添加100%的離群點(diǎn)情況下ICP并不能給出正確的匹配結(jié)果，本方法給出的結(jié)果卻仍然非常精細(xì)；在添加100%的高斯噪聲情況下，ICP最終獲得一個次優(yōu)的結(jié)果，而本方法則達(dá)到更好的效果，這說明本方法能更好地處理大量離群點(diǎn)和噪聲場景下的配準(zhǔn)問題。從表1中也可以看出，存在噪聲和離群點(diǎn)情況下，本方法要比ICP更加健壯。

從表1運(yùn)行時間來看，本方法比ICP有顯著提高，而這種提高隨著配準(zhǔn)點(diǎn)云數(shù)據(jù)量的增加越來越明顯(這一點(diǎn)會在圖4所示實(shí)驗(yàn)中進(jìn)一步說明)。同時，噪聲和離群點(diǎn)的增加并不會影響本方法的運(yùn)行時間。在配準(zhǔn)精度方面，本方法在重噪聲及離群點(diǎn)的情況下，依然保持了較高的配準(zhǔn)質(zhì)量。這一點(diǎn)，相較于ICP來說有非常大的改進(jìn)。

圖4 本方法與ICP在建筑物數(shù)據(jù)下配準(zhǔn)效果對比Fig.4 Results of the proposed method and ICP on the building model

3.2.2 工程數(shù)據(jù)實(shí)驗(yàn)

本部分實(shí)驗(yàn)使用實(shí)際工程數(shù)據(jù)以驗(yàn)證本方法對ICP健壯性及運(yùn)行效率的改進(jìn)。 在圖4中，圖4 (a)～圖4 (d)給出本方法對實(shí)際工程數(shù)據(jù)配準(zhǔn)各階段的結(jié)果；圖4 (e)為直接使用ICP對原始數(shù)據(jù)進(jìn)行配準(zhǔn)的結(jié)果；圖4 (f)給出將ICP的配準(zhǔn)結(jié)果作用于表面配準(zhǔn)關(guān)鍵點(diǎn)上的效果。從最終結(jié)果圖4 (d)可以看出，本方法能較好地配準(zhǔn)原始數(shù)據(jù)，而在圖4 (e)中可以看出在拱門邊緣、中間靠上的匾額處明顯出現(xiàn)配準(zhǔn)不一致的邊緣凸起。與圖4 (c)的對比，能清晰地看到圖4 (f)中2個點(diǎn)云數(shù)據(jù)上出現(xiàn)比較明顯的偏差。該組實(shí)驗(yàn)表明本方法更注重點(diǎn)云中的關(guān)鍵點(diǎn)在配準(zhǔn)中的作用，從而提高了ICP的健壯性。

本文使用圖4 (a)中所示的原始數(shù)據(jù)進(jìn)行不同比例的隨機(jī)下采樣并進(jìn)行實(shí)驗(yàn)，以評估對于不同大小的點(diǎn)云數(shù)據(jù)本方法對ICP運(yùn)行效率方面的提升。結(jié)果如表2所示?？梢钥闯鲭S著數(shù)據(jù)量的提升，本方法對ICP的效率提升越來越明顯。這也驗(yàn)證了本方法提取配準(zhǔn)關(guān)鍵點(diǎn)以提高ICP運(yùn)行效率的有效性。

表2 不同采樣率下的運(yùn)行時間表Table 2 Time consumption at different sampling rates

3.3 算法分析

本文提出的方法顯著地提高了ICP的運(yùn)行速度，增強(qiáng)了ICP在噪聲點(diǎn)和離群點(diǎn)情況下的健壯性。不同于基于一致性[21]及法向量[3,5]等下采樣策略，本方法在減少運(yùn)算數(shù)據(jù)量的同時并不會使得配準(zhǔn)之后的精度下降。同時，相較于ICP而言本方法更關(guān)注關(guān)鍵點(diǎn)在配準(zhǔn)中的作用，這個特點(diǎn)能一定程度上改善ICP陷入局部最優(yōu)的缺點(diǎn)。 在運(yùn)行效率方面，由于ICP的特性，每次迭代源點(diǎn)云中的每一個點(diǎn)都需要訪問目標(biāo)點(diǎn)云中最近的點(diǎn)。而本文引入的高斯曲率對2個點(diǎn)云中的點(diǎn)則只需一次計(jì)算，計(jì)算之后過濾出的關(guān)鍵點(diǎn)只有相對原始數(shù)據(jù)來說非常少的一部分。而這部分的迭代由于其數(shù)量非常少，其運(yùn)行速度非?？?。因此，隨著數(shù)據(jù)量增大，本方法獲得的運(yùn)算時間效率的提升會越來越明顯。

此外，相較于同樣使用物體表面特征(線、面)的ICP改進(jìn)算法來說，本方法計(jì)算過程中不需顯式地提取特征而且適用場景更加廣泛。同時，本方法提出的是對ICP算法前序處理的改進(jìn)，這種改進(jìn)可以很方便地移植到ICP其他的改進(jìn)算法(如Sparse-ICP和Go-ICP)上，以改善其效率和健壯性。

然而，由于本方法利用物體表面的高斯曲率特征以提取配準(zhǔn)關(guān)鍵點(diǎn)，而高斯曲率的估計(jì)依賴于點(diǎn)鄰域的定義。因此為了獲得更明顯的關(guān)鍵點(diǎn)，需要設(shè)置合適的鄰域以及高斯曲率閾值。這與ICP相比需要額外的工作。此外，如果物體表面的曲率特征過于復(fù)雜(如圖4 (a) 的上半部分)，則本方法將退化為ICP方法。

4 總結(jié)

本文提出一種基于高斯曲率的ICP改進(jìn)方法。從實(shí)驗(yàn)結(jié)果來看，本方法實(shí)現(xiàn)了對ICP的以下改進(jìn)：第一，本方法在保證精度的情況下，實(shí)現(xiàn)了算法效率的明顯提升，而這種提升在大數(shù)據(jù)量的場景下會特別明顯；第二，在重噪聲和離群點(diǎn)的條件下，本方法表現(xiàn)出很強(qiáng)的抗噪性和離群點(diǎn)耐受性；第三，本方法對配準(zhǔn)場景具有廣泛的適用性而且可以很容易移植到ICP其他改進(jìn)算法上去，以提高其運(yùn)行效率和健壯性。