荊 路,武 斌,方錫祿

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

1 引 言

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

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

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

2 配準(zhǔn)流程

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

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

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

3.1 初始配準(zhǔn)

3.1.1 SIFT特征檢測(cè)算法

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

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

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

(1)

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

(2)

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

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

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

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

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

3.1.2 點(diǎn)云FPFH特征描述

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

圖2 FPFH計(jì)算原理

計(jì)算FPFH特征的步驟如下:

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

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

(4)

3.1.3 SAC-IA算法

SAC-IA算法步驟如下:

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

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

(5)

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

3.2 精配準(zhǔn)

3.2.1 ICP算法

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

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

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

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

(4)求出均方誤差:

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

4 實(shí) 驗(yàn)

本文實(shí)驗(yàn)的硬件環(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、開(kāi)源點(diǎn)云庫(kù)PCL1.8.0。首先采用的點(diǎn)云模型為斯坦福大學(xué)點(diǎn)云庫(kù)的bunny點(diǎn)云模型。為了驗(yàn)證本文方法的有效性,分別與ICP算法和文獻(xiàn)[11]方法進(jìn)行對(duì)比分析,對(duì)bunny點(diǎn)云模型進(jìn)行配準(zhǔn)實(shí)驗(yàn)。同時(shí),以歐式適合度評(píng)分作為配準(zhǔn)誤差評(píng)判指標(biāo),歐式適合度評(píng)分表示輸出點(diǎn)云到最近目標(biāo)點(diǎn)云對(duì)應(yīng)點(diǎn)對(duì)的距離平方和,距離平方和越小說(shuō)明說(shuō)明重合度越好、配準(zhǔn)精度越高,并把配準(zhǔn)所用時(shí)間進(jìn)行比較,以衡量配準(zhǔn)的效率。

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

圖3 bunny初始點(diǎn)云

圖4 bunny點(diǎn)云SIFT特征點(diǎn)

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

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

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

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

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

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

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

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

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

圖8 椅子初始點(diǎn)云

圖9 椅子點(diǎn)云SIFT特征點(diǎn)

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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