成對(duì)點(diǎn)云對(duì)應(yīng)關(guān)系優(yōu)化的點(diǎn)云配準(zhǔn)算法

梁 宏

(江西理工大學(xué) 土木與測(cè)繪工程學(xué)院, 江西 贛州 341000)

三維點(diǎn)云配準(zhǔn)問題是計(jì)算機(jī)視覺[1]、逆向工程[2]和三維重建[3]等領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，在三維物體的激光掃描測(cè)量中，為了完整地表示該物體詳細(xì)信息需要從不同角度對(duì)物體進(jìn)行掃描，因此必須對(duì)多組點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)來得到完整的點(diǎn)云。本質(zhì)上是通過計(jì)算基準(zhǔn)幀與非基準(zhǔn)幀的變換矩陣，把非基準(zhǔn)幀的坐標(biāo)系轉(zhuǎn)換到基準(zhǔn)幀的坐標(biāo)系下。

快速精確的點(diǎn)云配準(zhǔn)是三維建模研究的熱點(diǎn)和重點(diǎn)，目前已有多種解決點(diǎn)云配準(zhǔn)問題的算法。Besl等[4]提出了迭代最近點(diǎn)算法(ICP)，它是目前應(yīng)用最廣最為經(jīng)典的配準(zhǔn)算法，中外學(xué)者提出了一系列改進(jìn)[5-7]，這些算法在點(diǎn)云變換的幅度較小時(shí)配準(zhǔn)精度較高，但是對(duì)配準(zhǔn)初始條件要求較高,否則容易陷入局部最優(yōu)。因此，研究學(xué)者大多先采用初始配準(zhǔn)獲得良好的初始配準(zhǔn)位置，再采用ICP算法進(jìn)行精確配準(zhǔn)。目前，通過掃描對(duì)象表面的局部幾何特征尋找點(diǎn)云間點(diǎn)與點(diǎn)對(duì)應(yīng)關(guān)系是目前點(diǎn)云配準(zhǔn)的研究熱點(diǎn)之一。常用的 3D特征描述子有旋轉(zhuǎn)圖像(spin image)[8]、點(diǎn)特征直方圖(PFH)及改進(jìn)的快速點(diǎn)特征直方圖(FPFH)[9-10]、旋轉(zhuǎn)投影統(tǒng)計(jì)(RoPs)[11]等，但對(duì)于稠密的點(diǎn)云，計(jì)算每個(gè)點(diǎn)的特征描述子常與特征點(diǎn)相結(jié)合。陸軍等[12]根據(jù)不同鄰域半徑估算的法向量的方向偏差選擇特征點(diǎn)，并依據(jù)點(diǎn)云多法向量鄰域特征進(jìn)行配準(zhǔn)；舒程珣等[13]將點(diǎn)云轉(zhuǎn)化為深度圖像，再利用卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行配準(zhǔn)；胡修祥等[14]結(jié)合 NARF 特征點(diǎn)與 FPFH 特征描述子獲得良好的初始位置，再利用 3D-NDT 進(jìn)行精確配準(zhǔn)；曾繁軒等[15]提出了基于曲率特征結(jié)合ICP的配準(zhǔn)算法。這些方法描述性強(qiáng)，但是穩(wěn)健性較差，易出現(xiàn)錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì)，且計(jì)算復(fù)雜，配準(zhǔn)效率低。

基于以上情況，為了提高點(diǎn)云配準(zhǔn)的精度和效率，提出一種基于成對(duì)點(diǎn)云點(diǎn)云對(duì)應(yīng)關(guān)系優(yōu)化的快速點(diǎn)云配準(zhǔn)方法，通過建立點(diǎn)云的對(duì)應(yīng)關(guān)系，對(duì)對(duì)應(yīng)關(guān)系進(jìn)行優(yōu)化，通過交替優(yōu)化的方式來求解點(diǎn)云的變化姿態(tài)，從而實(shí)現(xiàn)對(duì)點(diǎn)云的配準(zhǔn)。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本文算法配準(zhǔn)精度較高，速度較快。

1 基于成對(duì)點(diǎn)云對(duì)應(yīng)關(guān)系優(yōu)化的點(diǎn)云配準(zhǔn)

1.1 問題提出

給兩個(gè)曲面點(diǎn)云A、B，目的是找到一個(gè)剛性變換矩陣T，使得A、B兩個(gè)點(diǎn)云能夠完美對(duì)齊。采用一種針對(duì)A、B對(duì)應(yīng)關(guān)系進(jìn)行穩(wěn)健的優(yōu)化。這些對(duì)應(yīng)關(guān)系通過執(zhí)行FPFH特征匹配來建立優(yōu)化。但是，在優(yōu)化過程中不會(huì)重新計(jì)算點(diǎn)與點(diǎn)的對(duì)應(yīng)關(guān)系，因此這種優(yōu)化必須要處理一些錯(cuò)誤或者虛假的對(duì)應(yīng)關(guān)系，如圖1所示。

圖1 一對(duì)有對(duì)應(yīng)關(guān)系的表面點(diǎn)云

1.2 對(duì)應(yīng)關(guān)系優(yōu)化

為了生成初始的對(duì)應(yīng)點(diǎn)集L，使用了快速特征點(diǎn)直方圖(FPFH)，選擇該特征是因?yàn)樗梢栽?.01 s內(nèi)計(jì)算出來，并且可以在廣泛的數(shù)據(jù)集中提供良好的匹配精度。定義F(A)={F(a),a∈A}，其中F(A)是針對(duì)a點(diǎn)計(jì)算的FPFH特征，同理定義F(B)={F(b),b∈B}。采用最近鄰搜索查找初始的對(duì)應(yīng)點(diǎn)集，即對(duì)于每個(gè)點(diǎn)a，在F(B)中找到F(a)的最近鄰點(diǎn)，對(duì)于每個(gè)點(diǎn)b，在F(A)中找到F(b)的最近鄰點(diǎn)，組成初始對(duì)應(yīng)點(diǎn)集L1。僅僅只通過最近鄰點(diǎn)來生成初始點(diǎn)集，此時(shí)L1的誤差非常高。采用兩次優(yōu)化來削弱誤差。首先，特征優(yōu)化原則，即對(duì)應(yīng)點(diǎn)(a,b)需滿足a的最近點(diǎn)是b并且b的最近鄰點(diǎn)是a，此時(shí)對(duì)應(yīng)點(diǎn)就滿足了距離最近原則，優(yōu)化后得到的點(diǎn)集記為L2；其次對(duì)應(yīng)優(yōu)化原則，即參考點(diǎn)云特征點(diǎn)之間的L2范數(shù)與待配準(zhǔn)點(diǎn)云對(duì)應(yīng)點(diǎn)之間的L2范數(shù)之比需滿足以下關(guān)系：

(1)

式中，λ=0.9，對(duì)應(yīng)點(diǎn)滿足這個(gè)關(guān)系之后就認(rèn)為這兩個(gè)對(duì)應(yīng)點(diǎn)是完全對(duì)應(yīng)的，通過優(yōu)化之后得到的點(diǎn)集記為L3。

1.3 優(yōu)化原理

給定一組表面點(diǎn)云{Qi},i=1,2,3,…,n，估計(jì)一組轉(zhuǎn)換姿態(tài)T組成一個(gè)矩陣，使這個(gè)矩陣將這些點(diǎn)云在全局坐標(biāo)系中對(duì)齊。首先為重疊區(qū)域每對(duì)點(diǎn)云(Pi,Qi)經(jīng)過對(duì)應(yīng)點(diǎn)優(yōu)化后構(gòu)造一組候選對(duì)應(yīng)關(guān)系rij,i

(2)

該函數(shù)要實(shí)現(xiàn)對(duì)錯(cuò)誤的點(diǎn)云對(duì)應(yīng)關(guān)系進(jìn)行優(yōu)化，令Kp,q為對(duì)應(yīng)關(guān)系上的處理函數(shù)，此時(shí)要求解的目標(biāo)函數(shù)變?yōu)?/p>

(3)

式中，

(4)

為了使得加入的處理函數(shù)不會(huì)影響點(diǎn)云轉(zhuǎn)換姿態(tài)T，因此，令函數(shù)對(duì)變量函數(shù)求導(dǎo)后為0，即

(5)

解得

(6)

為了求解該函數(shù)的最小化問題，采用交替優(yōu)化來解決該問題。首先對(duì)函數(shù)進(jìn)行優(yōu)化，根據(jù)式(4)、式(5)進(jìn)行優(yōu)化，為了簡化該問題，實(shí)際應(yīng)用時(shí)令μ=1。當(dāng)把Kp,q優(yōu)化完成之后，接下來對(duì)所有的變換姿態(tài)T進(jìn)行最小化。

首先根據(jù)最小L2范數(shù)的原則，使得成對(duì)點(diǎn)云滿足它們之間對(duì)應(yīng)距離最小，通過把變換姿態(tài)線性化成6個(gè)分量τ=(ωi,ti)=(αi,βi,γi,Δxi,Δyi,Δzi)，其中ω、t分別為旋轉(zhuǎn)分量和平移分量。把T通過τ的局部線性函數(shù)可近似表示為

(7)

此時(shí)目標(biāo)函數(shù)(2)只跟Ti有關(guān)系，然后通過高斯牛頓迭代法求解非線性模型的回歸參數(shù)，可得到

(8)

式中，Jr為雅可比矩陣，其中的元素為目標(biāo)函數(shù)對(duì)Ti的一階偏導(dǎo)數(shù)；r為殘差。

可以通過非齊次線性方程組的求解方法解出τ，此時(shí)得到了點(diǎn)云姿態(tài)的6個(gè)分量。最后通過Eigen庫把這6個(gè)分量轉(zhuǎn)化成一個(gè)4×4的變換矩陣，再隨機(jī)選擇幾組點(diǎn)云，檢驗(yàn)這幾組點(diǎn)云是否能夠完美對(duì)齊。

1.4 復(fù)雜度分析

該優(yōu)化方法一共只有兩次循環(huán)，而且每次只更新轉(zhuǎn)換的矩陣和殘差。其中，建立兩個(gè)點(diǎn)云的線性關(guān)系只需執(zhí)行一次。在進(jìn)行迭代之前，需要一次性建立兩個(gè)點(diǎn)云的k-d樹，通過優(yōu)化的最近鄰搜索，增加搜索的速度。其他的計(jì)算復(fù)雜度與優(yōu)化算法的迭代次數(shù)有關(guān)?；趉-d樹結(jié)構(gòu)，為Pi個(gè)點(diǎn)建立對(duì)應(yīng)關(guān)系的復(fù)雜度為O(lgPi);為Pi個(gè)點(diǎn)更新殘差的復(fù)雜度為O(lgPi)。假設(shè)最大迭代次數(shù)為n,則針對(duì)循環(huán)過程中一對(duì)點(diǎn)云的姿態(tài)優(yōu)化算法?？山o出表1所示的復(fù)雜度分析結(jié)果。

表1 復(fù)雜度分析結(jié)果

2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文方法的有效性，實(shí)驗(yàn)采用公開4個(gè)數(shù)據(jù)集進(jìn)行測(cè)試和驗(yàn)證，并且采用三維掃描儀實(shí)地采集的點(diǎn)云數(shù)據(jù)模型進(jìn)行測(cè)試。剛體優(yōu)化的算法采用C++語言編寫，在Visual Studio 2017的開發(fā)環(huán)境下編譯。所有程序均運(yùn)行在一臺(tái)內(nèi)存為32 G，主頻為3.6 GHz的四核臺(tái)式電腦上。

2.1 實(shí)驗(yàn)對(duì)比

該算法的時(shí)間和精度驗(yàn)證通過對(duì)點(diǎn)云進(jìn)行一系列的控制實(shí)驗(yàn)。為了進(jìn)行控制實(shí)驗(yàn)，使用公開的數(shù)據(jù)集中的Bunny、Angel、Lion、Statue點(diǎn)云數(shù)據(jù)模型和實(shí)地采集到的數(shù)據(jù)Room模型。為了進(jìn)一步比較本文算法與其他配準(zhǔn)算法的配準(zhǔn)性能，對(duì)5組點(diǎn)云采用不同算法進(jìn)行20次配準(zhǔn)，得到了平均配準(zhǔn)誤差和配準(zhǔn)時(shí)間,如表2所示。由表2的實(shí)驗(yàn)結(jié)果可知，通過4種算法在5種不同的模型上進(jìn)行實(shí)驗(yàn)得到了點(diǎn)云匹配的標(biāo)注差(RMSE)。通過4種配準(zhǔn)算法在不同模型上配準(zhǔn)需要的時(shí)間t上可以看出，本文算法運(yùn)行效率是在PCL-ICP以及Scale-ICP算法之上的。跟ICP算法相比，本文算法耗時(shí)降低了約60%；跟Scale-ICP算法相比，本文算法耗時(shí)降低了50%；跟Sparse-ICP算法相比，本文算法耗時(shí)降低了20%左右,同時(shí)配準(zhǔn)的精度與它們相當(dāng)。Lion配準(zhǔn)圖如圖2所示。

為了驗(yàn)證本文算法是否解決了已收斂到局部最優(yōu)的問題，改變點(diǎn)云初始狀態(tài)，通過旋轉(zhuǎn)與平移改變配準(zhǔn)點(diǎn)云的初始位置，結(jié)果如圖3所示。進(jìn)行了兩組實(shí)驗(yàn)，在PCL方法中，對(duì)其進(jìn)行了初始化，在理想情況下時(shí)，本文算法可以相當(dāng)于這些局部修正方法的精度。但是當(dāng)初始位置偏離過大(旋轉(zhuǎn)20 °或者平移點(diǎn)云直徑的10%)時(shí)，局部方法的精度會(huì)降低。相反，本文算法在所有條件下都具有相同的精度。

表2 不同算法點(diǎn)云配準(zhǔn)對(duì)比

圖2 Lion配準(zhǔn)圖

圖3 局部收斂性對(duì)比結(jié)果

2.2 重疊度與魯棒性分析

為了驗(yàn)證本文算法在不同的重疊度下的點(diǎn)云配準(zhǔn)精度，對(duì)UWA數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)集總共包含188個(gè)成對(duì)測(cè)試。結(jié)果如圖4所示，現(xiàn)有的配準(zhǔn)算法在此數(shù)據(jù)集的性能較差。本文算法實(shí)現(xiàn)了85%的精確率，與GoICP和OpenCV相當(dāng)(分別為82%和78%),PCL和Super4PCS的精確度都低于50%。

算法的魯棒性是衡量算法在有噪聲或異常的情況下是否能夠進(jìn)行精確匹配，利用公開的Angel數(shù)據(jù)驗(yàn)證該方法在不同噪聲水平下的魯棒性。實(shí)驗(yàn)中，將3組不同的均勻噪聲：①σ=0無噪聲；②σ=0.002 5的隨機(jī)噪聲；③σ=0.005的隨機(jī)噪聲隨機(jī)的加入到Angel模型中。為了消除隨機(jī)性，該方法在不同的噪聲水平進(jìn)行了15次蒙特卡洛獨(dú)立測(cè)試，并記錄了各種方法的運(yùn)行時(shí)間和配準(zhǔn)誤差。表3給出了各種方法在加入了隨機(jī)噪聲后的配準(zhǔn)結(jié)果。

圖4 測(cè)試結(jié)果

表3 不同噪聲下各種點(diǎn)云配準(zhǔn)方法結(jié)果

3 結(jié)論

首先通過FPFH生成初始點(diǎn)集，根據(jù)最鄰近原則對(duì)點(diǎn)集進(jìn)行篩選生成初始的對(duì)應(yīng)關(guān)系，在根據(jù)L2范數(shù)比值去除錯(cuò)誤的對(duì)應(yīng)關(guān)系，實(shí)現(xiàn)點(diǎn)云的精確配準(zhǔn)。選取了幾個(gè)代表性的點(diǎn)云模型進(jìn)行試驗(yàn)得出以下結(jié)論：

1)提出的成對(duì)點(diǎn)云對(duì)應(yīng)關(guān)系優(yōu)化的配準(zhǔn)算法能夠使旋轉(zhuǎn)角度較大、初始距離較遠(yuǎn)的兩點(diǎn)云配準(zhǔn)時(shí)不易收斂到局部最優(yōu)，能夠?qū)崿F(xiàn)全局配準(zhǔn)

2)本文算法對(duì)比其他算法，在確保精度的同時(shí)，在迭代次數(shù)與配準(zhǔn)時(shí)間上更具有優(yōu)勢(shì)，同時(shí)對(duì)噪聲大、重疊度低點(diǎn)云配準(zhǔn)也具有較好的效果。

今后考慮在點(diǎn)云對(duì)應(yīng)點(diǎn)尋找前添加對(duì)點(diǎn)云顏色紋理特征的尋找，提高點(diǎn)云匹配的精度，從而提升對(duì)應(yīng)點(diǎn)集的精確性，最終提高配準(zhǔn)速度。