国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2019-09-19 00:56王飛鵬王云標(biāo)
關(guān)鍵詞:離群鄰域曲率

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

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

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

針對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)的同時(shí)并不降低配準(zhǔn)的精度。相較于同樣利用表面特征如線、面等的改進(jìn)算法,本方法只需要點(diǎn)云對象有一定的曲率特征(凸出、凹陷、拐角、邊線等等),因而適應(yīng)性更為廣泛。同時(shí),本方法還具有良好的擴(kuò)展性,很容易移植到其他ICP改進(jìn)方法上以獲得綜合的優(yōu)點(diǎn)。

1 背景知識

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

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é)的重要研究課題之一。在這個(gè)方面,同樣產(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)。這個(gè)方法既繼承了傳統(tǒng)方法中擬合二次曲面模型并求極值的方法[19],又避免了計(jì)算全部點(diǎn),提高了計(jì)算效率。Zhang等[17]提出一種估計(jì)鄰域點(diǎn)的法向量,而后利用歐拉公式將主曲率求解問題轉(zhuǎn)化成最小二乘問題的方法。這些方法對本算法中高斯曲率的計(jì)算有直接的指導(dǎo)意義。

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

本算法分為兩個(gè)關(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)算時(shí)間較長;而小的鄰域上計(jì)算出的高斯曲率其數(shù)值相對大,而穩(wěn)定性稍差,運(yùn)算時(shí)間較短。在實(shí)際配準(zhǔn)場景中,一般鄰域半徑的選擇應(yīng)能基本覆蓋表面的彎曲特征。圖1給出高斯曲率在Budda模型上的分布(由藍(lán)到紅表示其高斯曲率由小到大),點(diǎn)的鄰域設(shè)為 0.001而點(diǎn)與點(diǎn)之間的間隔約為0.000 3。同時(shí)可以看出,高斯曲率較大的地方在于角、凹陷等彎曲特征比較明顯的區(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個(gè)點(diǎn)云數(shù)據(jù)的關(guān)鍵點(diǎn)上應(yīng)用ICP,不僅能顯著提高ICP運(yùn)行速度,而且使整個(gè)算法有更強(qiáng)的健壯性。 同時(shí),由于這些關(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)。同時(shí),通過在不同采樣率下本算法與ICP執(zhí)行時(shí)間的比較,驗(yàn)證本算法對ICP在執(zhí)行時(shí)間方面的提升。 盡管本文算法是對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)行時(shí)間及配準(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í)間上更為快速。本組實(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)行時(shí)間及配準(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最終獲得一個(gè)次優(yōu)的結(jié)果,而本方法則達(dá)到更好的效果,這說明本方法能更好地處理大量離群點(diǎn)和噪聲場景下的配準(zhǔn)問題。從表1中也可以看出,存在噪聲和離群點(diǎn)情況下,本方法要比ICP更加健壯。

從表1運(yùn)行時(shí)間來看,本方法比ICP有顯著提高,而這種提高隨著配準(zhǔn)點(diǎn)云數(shù)據(jù)量的增加越來越明顯(這一點(diǎn)會在圖4所示實(shí)驗(yàn)中進(jìn)一步說明)。同時(shí),噪聲和離群點(diǎn)的增加并不會影響本方法的運(yùn)行時(shí)間。在配準(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個(gè)點(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)行時(shí)間表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ù)量的同時(shí)并不會使得配準(zhǔn)之后的精度下降。同時(shí),相較于ICP而言本方法更關(guān)注關(guān)鍵點(diǎn)在配準(zhǔn)中的作用,這個(gè)特點(diǎn)能一定程度上改善ICP陷入局部最優(yōu)的缺點(diǎn)。 在運(yùn)行效率方面,由于ICP的特性,每次迭代源點(diǎn)云中的每一個(gè)點(diǎn)都需要訪問目標(biāo)點(diǎn)云中最近的點(diǎn)。而本文引入的高斯曲率對2個(gè)點(diǎn)云中的點(diǎn)則只需一次計(jì)算,計(jì)算之后過濾出的關(guān)鍵點(diǎn)只有相對原始數(shù)據(jù)來說非常少的一部分。而這部分的迭代由于其數(shù)量非常少,其運(yùn)行速度非???。因此,隨著數(shù)據(jù)量增大,本方法獲得的運(yùn)算時(shí)間效率的提升會越來越明顯。

此外,相較于同樣使用物體表面特征(線、面)的ICP改進(jìn)算法來說,本方法計(jì)算過程中不需顯式地提取特征而且適用場景更加廣泛。同時(shí),本方法提出的是對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)行效率和健壯性。

猜你喜歡
離群鄰域曲率
一種基于鄰域粒度熵的離群點(diǎn)檢測算法
基于混合變鄰域的自動(dòng)化滴灌輪灌分組算法
一類具有消失χ 曲率的(α,β)-度量?
兒童青少年散瞳前后眼壓及角膜曲率的變化
含例鄰域邏輯的薩奎斯特對應(yīng)理論
面向復(fù)雜曲率變化的智能車路徑跟蹤控制
尖銳特征曲面點(diǎn)云模型各向異性鄰域搜索
一種相似度剪枝的離群點(diǎn)檢測算法
從數(shù)學(xué)的角度初步看離群點(diǎn)檢測算法
不同曲率牛頓環(huán)條紋干涉級次的選取