基于SIFT特征點結合ICP的點云配準方法

荊 路,武 斌,方錫祿

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

1 引 言

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

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

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

2 配準流程

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

圖1 點云配準流程

3 相關算法原理

3.1 初始配準

3.1.1 SIFT特征檢測算法

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

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

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

(1)

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

(2)

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

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

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

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

(3)

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

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

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

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

3.1.2 點云FPFH特征描述

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

圖2 FPFH計算原理

計算FPFH特征的步驟如下:

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

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

(4)

3.1.3 SAC-IA算法

SAC-IA算法步驟如下:

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

(2)對采樣點的對應點進行查找:依據采樣點的FPFH特征,從目標點云N中查找與該特征相似的點,從而將其作為目標點云N中與待配準點云M中的采樣點相對應的點。

(5)

其中,ml表示預先設定的值;li表示第i組對應點經過變換之后的距離差。最后為了使誤差函數取得最小值,則需要從所有的變換中找出一組最優的變換,從而進行初始配準。

3.2 精配準

3.2.1 ICP算法

經過初始配準之后,縮小了點云之間的旋轉和平移誤差,使得源點云和目標點云具有了較好的初始位置,然后在初始配準的基礎上采用ICP配準算法進行精配準,從而避免ICP算法對點云初始位置依賴的問題,進一步提高配準精度,使精配準后的結果達到預設的收斂條件。ICP算法步驟如下:

(1)從目標點云Q中搜索與源點云P中的點pi相應的最近點pi′,從而構成對應點對。

(2)根據對應點對,求出點云Q和P之間的變換關系R和T。

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

(4)求出均方誤差:

(5)當dm-dm+1小于預設的域值或者達到預設的迭代次數時,則迭代結束；反之重新迭代。

4 實 驗

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

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

圖3 bunny初始點云

圖4 bunny點云SIFT特征點

如圖5所示為bunny使用ICP算法迭代5次、10次、15次、20次時的配準結果。如圖6所示為bunny使用文獻[11]方法迭代5次、7次、10次時的配準結果。

圖5 ICP算法配準bunny結果

圖6 文獻[11]方法配準bunny結果

如下圖7所示為bunny使用本文方法迭代5次、7次、10次時的配準結果。

圖7 本文方法配準bunny結果

如表1所示,為bunny配準誤差和用時統計結果。

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

表1 bunny配準統計結果

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

圖8 椅子初始點云

圖9 椅子點云SIFT特征點

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

圖10 ICP算法配準椅子結果

如圖11所示為椅子點云使用文獻[11]方法迭代5次、7次、10次時的配準結果。

圖11 文獻[11]方法配準椅子結果

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

圖12 本文方法配準椅子結果

如表2所示,為椅子點云配準誤差和時間統計結果。

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

表2 椅子點云配準統計結果

5 結 語

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