荊 路,武 斌,方錫祿

(天津城建大學(xué)計算機與信息工程學(xué)院,天津 300384)

1 引 言

近年來隨著激光技術(shù)的快速發(fā)展,激光雷達(dá)正不斷應(yīng)用到各種領(lǐng)域,例如智能駕駛、電力巡線、三維重建以及隧道變形監(jiān)測等[1-4]。然而,當(dāng)進(jìn)行實際測量時,由于受到測量環(huán)境和儀器設(shè)備等因素的影響,采集到的每幀點云數(shù)據(jù)僅僅包含所測物體的部分點云信息。因此,為了獲取所測物體完整的點云數(shù)據(jù),往往需要對物體進(jìn)行多站點多視角測量,并通過配準(zhǔn)把不同視角測得的點云數(shù)據(jù)變換到同一坐標(biāo)系下。

點云配準(zhǔn)通常分為兩步:初始配準(zhǔn)和精配準(zhǔn)。初始配準(zhǔn)中基于特征的配準(zhǔn)算法是目前主要的研究方向,如紋理[5]和角點[6]等。在精配準(zhǔn)階段,Besl等[7]提出的ICP(iterative closest point)算法是目前最經(jīng)典的算法,但是此算法對點云初始位置要求高,否則容易陷入局部最優(yōu),而且存在迭代速度慢、耗時長的問題[8]。為了解決ICP算法存在的問題,許多學(xué)者對該算法作了改進(jìn)和創(chuàng)新,而且也提出了一些新的算法。Yang等[9]提出Scale-ICP算法,與ICP算法相比,此算法雖然在配準(zhǔn)精度和迭代速度方面都有一定的改進(jìn),但對迭代過程依賴性較強,導(dǎo)致算法收斂緩慢。文獻(xiàn)[10]提出一種利用K-D樹對ICP配準(zhǔn)算法進(jìn)行優(yōu)化的方法,但是當(dāng)配準(zhǔn)海量點云數(shù)據(jù)時,此方法的配準(zhǔn)效率無法完全滿足應(yīng)用要求,還需不斷改善搜索策略。趙明富[11]融合了采樣一致性算法與ICP算法,雖然在一定程度上解決了ICP算法依賴初值的問題,但當(dāng)點云數(shù)據(jù)量較大時,配準(zhǔn)效率較低。文獻(xiàn)[12]提出一種依據(jù)高斯混合模型來擬合點云模型的方法,雖然保證了配準(zhǔn)精度,但同時犧牲了配準(zhǔn)效率。王暢等[13]提出一種依據(jù)點云結(jié)構(gòu)特征進(jìn)行配準(zhǔn)的方法,雖然該算法使配準(zhǔn)速度有一定的提高,但是當(dāng)點云數(shù)據(jù)點不完整或者交叉數(shù)據(jù)點不夠時,可能會造成配準(zhǔn)結(jié)果失效。

基于以上研究現(xiàn)狀,針對ICP算法對點云初始位置依賴性強且迭代速度慢的問題,本文提出一種基于SIFT(scale invariant feature transform)特征點結(jié)合ICP的點云配準(zhǔn)方法。該方法依據(jù)SIFT特征檢測算法以實現(xiàn)初始配準(zhǔn)時特征點對的匹配,然后在初始配準(zhǔn)的基礎(chǔ)上再使用ICP算法進(jìn)行精配準(zhǔn)。

2 配準(zhǔn)流程

本文配準(zhǔn)方法的流程如圖1所示。首先利用SIFT算法提取待配準(zhǔn)和目標(biāo)點云的特征點；接著計算特征點的FPFH(fast point feature histogram)特征；然后依據(jù)特征點的FPFH特征利用SAC-IA(sample consensus intial alignment)算法求出變換矩陣,從而完成初始配準(zhǔn)；最后在初始配準(zhǔn)的基礎(chǔ)上利用ICP算法對初始配準(zhǔn)的結(jié)果進(jìn)一步優(yōu)化,完成精配準(zhǔn)。

圖1 點云配準(zhǔn)流程

3 相關(guān)算法原理

3.1 初始配準(zhǔn)

3.1.1 SIFT特征檢測算法

SIFT算法是Lowe D G在1999年提出的一種局部特征描述算法,并在2004年對其進(jìn)行了完善[14],該特征對亮度變化、噪聲、旋轉(zhuǎn)和平移等因素保持較好的不變性。SIFT算法步驟簡介如下:

(1)生成尺度空間。圖像的尺度空間定義為:

L(x,y,σ)=G(x,y,σ)?I(x,y)

(1)

其中,G(x,y,σ)是尺度可變高斯函數(shù)：

(2)

式中,σ表示尺度空間因子,反應(yīng)了圖像的模糊程度;(x,y)表示像素的坐標(biāo)。

(2)在尺度空間上檢測極值點。構(gòu)造高斯差分(DoG,Difference of Guassian)函數(shù),即：

D(x,y,σ)=[G(x,y,kσ)-G(x,y,σ)]?I(x,y)

=L(x,y,kσ)-L(x,y,σ)

(3)

其中,k表示兩個相鄰高斯尺度空間的比例因子,通過該函數(shù)可以有效檢測尺度空間中的特征點。當(dāng)檢測極值點時,把尺度空間中的每個像素點與26個像素點作比較,這26個像素點分別為上下相鄰尺度的18個和同尺度相鄰的8個,然后判斷該像素點的DoG算子在這26個領(lǐng)域中是否取得極小值或者極大值,若取得極小值或者極大值那么該點即為特征點。

(3)對極值點進(jìn)行篩選。通過曲線擬合DoG函數(shù)以剔除不符合要求的點,從而獲得穩(wěn)定的極值點,即特征點。

(4)求取特征點的主方向。計算特征點鄰域內(nèi)各個像素點的梯度,并把10°作為一個單位,采用直方圖統(tǒng)計梯度方向,定義特征點的主方向為直方圖中最大值對應(yīng)的方向。

(5)建立一個包函尺度、位置和方向信息的描述符,通過該描述符對特征點進(jìn)行描述。

3.1.2 點云FPFH特征描述

FPFH算法是一種基于局部特征描述的算法,它是通過對點特征直方圖(Point Feature Histograms,PFH)[15]改進(jìn)得到的,關(guān)于PFH的詳細(xì)介紹可參考文獻(xiàn)[15]。相比較PFH而言,FPFH由于沒有計算全互聯(lián)Mq的所有鄰近點,因而使得算法的計算量降低,把復(fù)雜度由Ο(k2)降低到Ο(k),FPFH的計算原理如圖2所示。

圖2 FPFH計算原理

計算FPFH特征的步驟如下:

(1)計算出每個待計算點Mq與其所有領(lǐng)域點之間的相對關(guān)系,從而建立簡化的點特征直方圖(Simplified Point Feature Histogram,SPFH),并記為S(Mq)。

(2)根據(jù)上述(1)步計算得到的k個領(lǐng)域點的SPFH特征計算FPFH特征,記為F(Mq),表示為:

(4)

3.1.3 SAC-IA算法

SAC-IA算法步驟如下:

(1)對采樣點進(jìn)行選取:依據(jù)預(yù)先設(shè)置的距離閾值d從待配準(zhǔn)點云M中選取采樣點,要使得d小于采樣點兩兩間距,從而保證各采樣點的FPFH特征均不相同。

(2)對采樣點的對應(yīng)點進(jìn)行查找:依據(jù)采樣點的FPFH特征,從目標(biāo)點云N中查找與該特征相似的點,從而將其作為目標(biāo)點云N中與待配準(zhǔn)點云M中的采樣點相對應(yīng)的點。

(5)

其中,ml表示預(yù)先設(shè)定的值;li表示第i組對應(yīng)點經(jīng)過變換之后的距離差。最后為了使誤差函數(shù)取得最小值,則需要從所有的變換中找出一組最優(yōu)的變換,從而進(jìn)行初始配準(zhǔn)。

3.2 精配準(zhǔn)

3.2.1 ICP算法

經(jīng)過初始配準(zhǔn)之后,縮小了點云之間的旋轉(zhuǎn)和平移誤差,使得源點云和目標(biāo)點云具有了較好的初始位置,然后在初始配準(zhǔn)的基礎(chǔ)上采用ICP配準(zhǔn)算法進(jìn)行精配準(zhǔn),從而避免ICP算法對點云初始位置依賴的問題,進(jìn)一步提高配準(zhǔn)精度,使精配準(zhǔn)后的結(jié)果達(dá)到預(yù)設(shè)的收斂條件。ICP算法步驟如下:

(1)從目標(biāo)點云Q中搜索與源點云P中的點pi相應(yīng)的最近點pi′,從而構(gòu)成對應(yīng)點對。

(2)根據(jù)對應(yīng)點對,求出點云Q和P之間的變換關(guān)系R和T。

(3)更新源點云P,求出P′=Rpi+T。

(4)求出均方誤差:

(5)當(dāng)dm-dm+1小于預(yù)設(shè)的域值或者達(dá)到預(yù)設(shè)的迭代次數(shù)時,則迭代結(jié)束；反之重新迭代。

4 實 驗

本文實驗的硬件環(huán)境為Inter(R)Core(TM)i7-8750H CPU @2.20Hz處理器,8.00GB內(nèi)存；系統(tǒng)環(huán)境為64位win10操作系統(tǒng)；軟件環(huán)境為Visual Studio2013、開源點云庫PCL1.8.0。首先采用的點云模型為斯坦福大學(xué)點云庫的bunny點云模型。為了驗證本文方法的有效性,分別與ICP算法和文獻(xiàn)[11]方法進(jìn)行對比分析,對bunny點云模型進(jìn)行配準(zhǔn)實驗。同時,以歐式適合度評分作為配準(zhǔn)誤差評判指標(biāo),歐式適合度評分表示輸出點云到最近目標(biāo)點云對應(yīng)點對的距離平方和,距離平方和越小說明說明重合度越好、配準(zhǔn)精度越高,并把配準(zhǔn)所用時間進(jìn)行比較,以衡量配準(zhǔn)的效率。

如圖3所示為bunny初始點云,圖4為利用SIFT算法提取bunny點云特征點的結(jié)果。

圖3 bunny初始點云

圖4 bunny點云SIFT特征點

如圖5所示為bunny使用ICP算法迭代5次、10次、15次、20次時的配準(zhǔn)結(jié)果。如圖6所示為bunny使用文獻(xiàn)[11]方法迭代5次、7次、10次時的配準(zhǔn)結(jié)果。

圖5 ICP算法配準(zhǔn)bunny結(jié)果

圖6 文獻(xiàn)[11]方法配準(zhǔn)bunny結(jié)果

如下圖7所示為bunny使用本文方法迭代5次、7次、10次時的配準(zhǔn)結(jié)果。

圖7 本文方法配準(zhǔn)bunny結(jié)果

如表1所示,為bunny配準(zhǔn)誤差和用時統(tǒng)計結(jié)果。

通過上述結(jié)果可以看出,在使用ICP算法配準(zhǔn)情況下,當(dāng)?shù)螖?shù)較少時,點云模型的頭部、尾部、腳掌及耳朵等多處部位出現(xiàn)了明顯配準(zhǔn)偏差,隨著迭代次數(shù)的增加,雖然配準(zhǔn)效果不斷改善,但配準(zhǔn)用時更長,配準(zhǔn)效率明顯下降。對比直接使用ICP算法,隨著迭代次數(shù)的增加,本文方法的配準(zhǔn)精度更高、配準(zhǔn)用時更少。同時,與文獻(xiàn)[11]方法相比,雖然本文方法的配準(zhǔn)效率有所降低,但配準(zhǔn)精度得到了提高。

表1 bunny配準(zhǔn)統(tǒng)計結(jié)果

為了進(jìn)一步分析本文方法的普適性,以采集的椅子點云數(shù)據(jù)進(jìn)行上述實驗。如圖8所示為椅子初始點云,圖9為利用SIFT算法提取椅子點云特征點的結(jié)果。

圖8 椅子初始點云

圖9 椅子點云SIFT特征點

如圖10所示為椅子點云使用ICP算法迭代5次、10次、15次、20次時的配準(zhǔn)結(jié)果。

圖10 ICP算法配準(zhǔn)椅子結(jié)果

如圖11所示為椅子點云使用文獻(xiàn)[11]方法迭代5次、7次、10次時的配準(zhǔn)結(jié)果。

圖11 文獻(xiàn)[11]方法配準(zhǔn)椅子結(jié)果

如圖12所示為椅子點云使用本文方法迭代5次、7次、10次時的配準(zhǔn)結(jié)果。

圖12 本文方法配準(zhǔn)椅子結(jié)果

如表2所示,為椅子點云配準(zhǔn)誤差和時間統(tǒng)計結(jié)果。

通過對椅子點云配準(zhǔn)的結(jié)果可以得出,與ICP算法相比,本文方法在迭代次數(shù)較少時便取得了較高的配準(zhǔn)精度,并且隨著迭代次數(shù)的增加,配準(zhǔn)效率相對更高、誤差收斂得更快。同時與文獻(xiàn)[11]方法相比,雖然降低了效率,但配準(zhǔn)精度更高。

表2 椅子點云配準(zhǔn)統(tǒng)計結(jié)果

5 結(jié) 語

由于ICP算法存在對點云初始位置依賴性強且迭代速度慢的問題,本文提出了一種基于SIFT特征點結(jié)合ICP的點云配準(zhǔn)方法。對點云模型使用SIFT算法提取特征點,并計算出特征點的FPFH特征,依據(jù)該特征并利用SAC-IA算法完成初始配準(zhǔn),從而使兩片點云具有一個較好的初始位置,最后再利用ICP算法對兩片點云進(jìn)行精配準(zhǔn)以進(jìn)一步優(yōu)化配準(zhǔn)結(jié)果。實驗表明,該方法能夠有效避免ICP算法依賴初始位置的問題,加快了迭代速度,提高了配準(zhǔn)精度與效率。由于在三維重建過程中點云數(shù)據(jù)配準(zhǔn)是十分關(guān)鍵的一步,配準(zhǔn)的成功與否會對后續(xù)的重建結(jié)果造成直接影響,因此,本文的配準(zhǔn)方法為后期點云模型重建提供了一定程度的參考。但是,需要注意的是,提取點云SIFT特征點時仍需消耗一定的時間,這是該方法日后需要優(yōu)化的地方,同時,該方法中某些參數(shù)的閾值設(shè)置問題還需進(jìn)一步優(yōu)化,這些問題將在未來科研中繼續(xù)改進(jìn)。