一種基于局部特征的柵格地圖拼接方法

李雅梅 蘇 龍

(遼寧工程技術(shù)大學(xué)電氣與控制工程學(xué)院 遼寧 葫蘆島 125105)

0 引 言

同步定位與地圖創(chuàng)建(Simultaneous Localization and Mapping, SLAM)算法[1]是實(shí)現(xiàn)機(jī)器人自主巡航的重要條件。在未知環(huán)境中，單個(gè)機(jī)器人的定位精度、地圖拼接速度和魯棒性都受到限制，多機(jī)器人協(xié)作SLAM是有效的解決方案。國(guó)內(nèi)外，很早就對(duì)單個(gè)機(jī)器人SLAM算法進(jìn)行了研究，但對(duì)于多機(jī)器人的SLAM算法研究較晚，很多技術(shù)有待改進(jìn)。SLAM算法可以創(chuàng)建多種不同形式的地圖，柵格地圖在實(shí)時(shí)環(huán)境中比其他種類的地圖更有助于機(jī)器人的定位導(dǎo)航。在多機(jī)器人協(xié)作系統(tǒng)中，需要將多個(gè)柵格地圖進(jìn)行拼接，以構(gòu)建全局地圖，因此圖像拼接是多機(jī)器人SLAM系統(tǒng)關(guān)鍵技術(shù)之一。

對(duì)多機(jī)器人柵格地圖拼接主要分為兩個(gè)技術(shù)方向：一是基于圖像像素信息[2-4]，通過不斷迭代計(jì)算圖像像素值的方差求取最小值，從而進(jìn)行特征點(diǎn)匹配，這種方法不僅效率極低，而且魯棒性很差；二是繼Lowe提出尺度不變特征變換算法[5-6](Scale Invariant Feature Transform，SIFT)后，先后出現(xiàn)的加速魯棒特性(speeded up robust features，SURF)算法[7-8]、Harris-SIFT算法[9]、GLOH算法[10]，上述算法雖精度較高，但是匹配速度較低、算法復(fù)雜度高。

針對(duì)現(xiàn)有柵格地圖拼接算法速度較慢、魯棒性差等缺點(diǎn)，本文提出一種基于局部特征的多機(jī)器人柵格地圖拼接方法，以提高拼接速度和精度。

1 柵格地圖模型建立

柵格地圖拼接的要點(diǎn)之一是快速精確地計(jì)算出剛體變換矩陣T={R，t}，那么把柵格圖像拼接問題轉(zhuǎn)換為柵格地圖對(duì)應(yīng)特征點(diǎn)匹配問題，則目標(biāo)函數(shù)為：

(1)

式中:Aa(i)和Bi為兩幅柵格地圖重疊部分，R為剛體變換矩陣，t為柵格地圖平移量。

對(duì)式(1)數(shù)學(xué)模型描述，常規(guī)基于PCA-SIFT算法[11]柵格圖像拼接的步驟如下：

① 選擇具有代表性的柵格地圖，構(gòu)建投影矩陣，并存儲(chǔ)；

② 先建立高斯金字塔，再建立高斯差分金字塔；

③ 在高斯差分金字塔中，尋找最優(yōu)的特征點(diǎn)；

④ 在高斯金字塔中，建立特征點(diǎn)的描述子，用描述子在投影矩陣上投影；

⑤ 特征點(diǎn)匹配，計(jì)算R和t的值，對(duì)B柵格地圖進(jìn)行旋轉(zhuǎn)平移，與柵格圖像A疊加拼接。

傳統(tǒng)基于PCA-SIFT算法對(duì)柵格地圖拼接時(shí)，第二步搭建高斯差分金字塔會(huì)致使柵格地圖邊緣模糊和特征點(diǎn)定位不準(zhǔn)確，降低描述符的魯棒性；在第三步中尋找特征點(diǎn)速度較慢，算法比較復(fù)雜；第五步中特征點(diǎn)匹配易出現(xiàn)錯(cuò)誤匹配點(diǎn)；第五步中柵格地圖直接疊加出現(xiàn)“鬼影”等缺點(diǎn)。

對(duì)此本文利用非線性擴(kuò)散濾波搭建金字塔；使用FAST算法[12]快速定位特征點(diǎn)；使用RANSAC(隨機(jī)采樣一致性)算法[13]尋找最優(yōu)特征匹配點(diǎn)；最后提出一種適合柵格地圖拼接規(guī)則對(duì)A、B柵格地圖拼接。

2 改進(jìn)PCA-SIFT特征點(diǎn)提取

2.1 非線性金字塔特征點(diǎn)檢測(cè)

(1) 非線性擴(kuò)散濾波金字塔建立。SIFT算法、SURF算法、ORB算法[18]等皆使用線性高斯濾波建立金字塔，高斯濾波會(huì)造成圖像邊緣模糊降低特征點(diǎn)檢測(cè)和描述符的魯棒性。柵格地圖紋理相對(duì)簡(jiǎn)單邊緣十分敏感，因此本文金字塔建立借鑒KAZE算法[17]的思想，建立非線性擴(kuò)散濾波金字塔，從而增加匹配算法的魯棒性。圖像亮度L的流動(dòng)函數(shù)擴(kuò)散度，可用非線性偏微方程表示為：

(2)

式中：div為散度函數(shù)；▽為柵格地圖的梯度算子；c(x,y,t)為傳導(dǎo)函數(shù)，表示為：

c(x,y,t)=g(|▽Lσ(x,y,t)|)

(3)

式中：▽Lσ為柵格地圖經(jīng)過高斯平滑后的梯度圖像。函數(shù)g()定義為：

(4)

式中：k為控制擴(kuò)散的對(duì)比參數(shù)。非線性函數(shù)沒有解析解，這里使用AOS算法[17]對(duì)式(2)進(jìn)行求解，離散化式(2)為：

(5)

式中：Al表示柵格地圖每一個(gè)維度上傳導(dǎo)性編碼矩陣，該方程解為：

(6)

式中：τ為任意時(shí)間步長(zhǎng)。非線性金字塔的圖像可以描述成：

Li+1=(I-(ti+1-ti)Al(Li))-1Li

(7)

(2) 特征點(diǎn)檢測(cè)。在非線性金字塔上任選像素點(diǎn)p為圓心，畫直徑為9個(gè)像素的圓，圓上有16個(gè)像素點(diǎn)，分別為p1,p2,…,p16。如圖1所示。

圖1 FAST角點(diǎn)檢測(cè)

設(shè)定閾值t。若在{p1,p2,…,pn}且n∈{1,2,3,…,16}中任何一個(gè)像素點(diǎn)與p做差的絕對(duì)值都大于t，則p點(diǎn)為特征點(diǎn)。本文中n取9，為了減少算法的復(fù)雜度，直接計(jì)算p1、p9與p的像素差值的絕對(duì)值，若大于t保留p；再計(jì)算p5、p13與p的像素差值的絕對(duì)值，若其中至少3個(gè)大于t保留p；最后計(jì)算其余11個(gè)像素點(diǎn)與p的像素差值的絕對(duì)值，若其中至少9個(gè)大于t，則p點(diǎn)為特征點(diǎn)。

2.2 特征點(diǎn)描述符的建立

特定點(diǎn)描述符的建立步驟：

(1) 尋找主方向。2.1節(jié)中檢測(cè)到的特征點(diǎn)P(x,y)為圓心，半徑為r的像素塊為M，像素塊的質(zhì)心O，特征點(diǎn)指向質(zhì)心的向量為PO。像素塊M的矩為：

(8)

式中：L(x,y)表示非線性金字塔中的像素值，x、y為像素點(diǎn)橫縱坐標(biāo)，r為像素塊M的半徑。像素塊M的質(zhì)點(diǎn)為：

(9)

θ=atan2(m01,m10)

(10)

式中：θ為特征點(diǎn)的主方向。

(2) 投影矩陣建立。選擇具有代表性柵格地圖作為訓(xùn)練樣本，按照2.1節(jié)算法檢測(cè)特征點(diǎn)。每一個(gè)特征點(diǎn)旋轉(zhuǎn)至與特征點(diǎn)主方向一致，以特征點(diǎn)為中心選擇一個(gè)41×41的區(qū)域快，并計(jì)算區(qū)域塊中非邊緣像素點(diǎn)的垂直和水平方向的梯度，則形成向量維數(shù)dim=(41-2)×(41-2)×2=3 042。若有i個(gè)特征點(diǎn)，則構(gòu)成矩陣M=i×3 042。

計(jì)算M矩陣的協(xié)方差：

M=M-mean(M)

(11)

covM=MTM

(12)

式中:mean(M)代表矩陣的平均值，covM為M的協(xié)方差矩陣。再計(jì)算協(xié)方差矩陣covM的特征值λ=(λ1，λ2，…，λp)和特征向量e={e1,e2,…,ep}。把特征向量按照特征值的從大到小的順序依次排列，然后選擇排列后的前n個(gè)特征值對(duì)應(yīng)的特征向量作為主成分分析的方向，構(gòu)建的投影矩陣N=n×3 024進(jìn)行存儲(chǔ)，本文中n取36。

(3) 描述符建立。按照2.1節(jié)算法尋找特征點(diǎn)，并旋轉(zhuǎn)特征點(diǎn)坐標(biāo)與特征點(diǎn)的主方向一直。以特征點(diǎn)為中心，選取41×41的窗口，并計(jì)算窗口中非邊緣區(qū)域的水平和垂直方向上的梯度，則生成了維數(shù)為3 042的描述子H。描述符H與投影矩陣N相乘，則生成了一個(gè)36維的PCA-SIFT描述符dPCA-SIFT。

dPCA-SIFT=H×N

(13)

3 特征柵格地圖融合

3.1 特征點(diǎn)匹配

3.2 選擇最佳的匹配點(diǎn)

在3.1節(jié)中，已對(duì)柵格地圖A和B的特征點(diǎn)進(jìn)行了匹配，但是其中有很多錯(cuò)誤匹配點(diǎn)。用RANSAC算法對(duì)匹配完成的特征描述子進(jìn)行篩選，優(yōu)選匹配點(diǎn)。具體步驟：

(1) 從樣本中隨機(jī)選擇點(diǎn)集，把這些點(diǎn)默認(rèn)為內(nèi)點(diǎn)。

(2) 利用假定的內(nèi)點(diǎn)估算一個(gè)合適的數(shù)學(xué)模型，計(jì)算模型參數(shù)。

(3) 設(shè)置一個(gè)閾值T，篩選處樣本集合中滿足模型的點(diǎn)，并把這些點(diǎn)放入內(nèi)點(diǎn)(Inliers)點(diǎn)集中，然后用新生成的點(diǎn)集來評(píng)估步驟(2)中估算模型。

(4) 重復(fù)步驟(1)、步驟(2)，經(jīng)過N次迭代次數(shù)后，選取最優(yōu)解，最優(yōu)解應(yīng)是包含內(nèi)點(diǎn)最多的。

(5) 用最優(yōu)解重新計(jì)算并確實(shí)最終的數(shù)學(xué)模型，把不滿足該模型的點(diǎn)剔除。

3.3 柵格地圖融合

圖像特征點(diǎn)匹配之后，柵格地圖的剛體變換關(guān)系也得到確定。若是直接把兩幅地圖進(jìn)行疊加拼接，會(huì)出現(xiàn)很嚴(yán)重的噪聲，不利于機(jī)器人根據(jù)柵格地圖進(jìn)行定位。

在進(jìn)行柵格地圖融合前，先新建一個(gè)柵格地圖P，尺寸由地圖T(B)和地圖A決定。地圖T(B)是根據(jù)地圖B由剛體變換得到，對(duì)應(yīng)像素為：

(14)

柵格地圖P中的像素融合結(jié)果為：

P(i,j)=h{A(i,j),T[B(i,j)]}

(15)

式中：h( )為融合函數(shù)，其融合規(guī)則為：

(16)

式中：α為柵格地圖像背景像素值，x、y分別為A、B像素值。若A、B重疊處像素值相同，則像素點(diǎn)值為x；若A、B重疊處像素值不同且B像素值等于背景像素值，則像素點(diǎn)值為x；若A、B重疊處像素值不同且A像素值等于背景像素值，則像素點(diǎn)值為y。

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

為了驗(yàn)證本文所提出算法的速度和精度，使用外國(guó)學(xué)者提供的柵格地圖公開數(shù)據(jù)集對(duì)本文算法進(jìn)行測(cè)試，同時(shí)與基于SIFT算法、PCA-SIFT和SURF進(jìn)行對(duì)比。

為了證明本算法具有很好的魯棒性，從Fr079公開數(shù)據(jù)集中選擇三組具有不同重疊百分比的柵格地圖。第一組為高重疊百分比柵格地圖；第二組為中等重疊百分比柵格地圖；第三組為低重疊百分比柵格地圖，如圖2所示。

圖3為使用本文算法，三組柵格地圖拼接結(jié)果。圖3(a)中兩幅柵格地圖雖高度重疊，但在地圖邊緣位置有尺寸差異，致使拼接地圖邊緣出現(xiàn)重影，如方框區(qū)域。圖2(b)中兩幅中等重疊柵格地圖尺寸一致，拼接效果良好，并未出現(xiàn)明顯重影，如圖3(b)所示。圖2(c)中兩幅低重疊柵格地，成功進(jìn)行拼接，且拼接質(zhì)量很好，如圖3(b)所示。

(a) 高重疊百分比地圖

(b) 中等重疊百分比地圖

(c) 低重合百分比地圖圖2 待拼接?xùn)鸥竦貓D

(a) 高重疊百分比柵格地圖拼接結(jié)果

(b) 中等重疊百分比柵格地圖拼接結(jié)果

(c) 低等重疊百分比柵格地圖拼接結(jié)果圖3 兩幅柵格地圖拼接結(jié)果

表1、表2和表3分別為高中低三組不同重疊百分比柵格地圖，在基于SIFT算法、PCA-SIFT算法、SURF算和本文算法進(jìn)行柵格地圖拼接得到的數(shù)據(jù)。在本實(shí)驗(yàn)中，基于SIFT算法、基于PCA-SIFT算法和本文的算法的匹配閾值都設(shè)為0.6。

表1 高重疊柵格地圖匹配數(shù)據(jù)

表2 中等重疊地圖拼接匹配數(shù)據(jù)

表3 低重疊地圖拼接匹配數(shù)據(jù)

由表1-表3可知，本文算法在高中低三種不同重疊百分比柵格地圖匹配速度均高于其他算法。PCA-SIFT算法描述符的維度比SIFT算法低，故匹配速度優(yōu)于SIFT算法。SURF算法金字塔搭建、描述符建立復(fù)雜度相較于SIFT算法低，描述符維度僅為SIFT算法描述符的一半，故匹配速度快于SIFT算法；PCA-SIFT描述符維度比SURF算法描述符低，但描述符建立較為復(fù)雜，故匹配速度不及SURF算法。本文算法特征點(diǎn)檢測(cè)使用FAST算法，僅比較相鄰像素點(diǎn)的大小，特征點(diǎn)提取速度優(yōu)于另外三種算法，描述符使用PCA算法降維為36維，故整體匹配速度超過其他算法。

表1-表3中匹配點(diǎn)數(shù)是經(jīng)過RANSAC算法優(yōu)選的最佳匹配點(diǎn)，單從特征點(diǎn)數(shù)和匹配點(diǎn)數(shù)比較，本文算法相較于另外兩種算法并無明顯優(yōu)勢(shì)，但SIFT算法、PCA -SIFT算法和SURF算法經(jīng)過RANSAC算法優(yōu)選匹配點(diǎn)后仍有很多假匹配點(diǎn)。圖4為四種算法在高重疊百分比柵格地圖特征點(diǎn)匹配的結(jié)果，連接線代表相互匹配特征點(diǎn)。僅從視覺角度觀察，(a)-(c)圖中有很多錯(cuò)誤匹配點(diǎn)，(d)中無錯(cuò)誤匹配點(diǎn)。由(a)和(b)可看出，匹配特征點(diǎn)分布不均勻，匹配集中某一特定區(qū)域，會(huì)影響拼接效果。(c)中，雖匹配特征點(diǎn)相對(duì)分散，但數(shù)量較少。(d)中，匹配點(diǎn)不僅均勻分布，而且在數(shù)量上遠(yuǎn)超過其他算法。

(a) 基于SIFT算法

(b) 基于PCA-SIFT算法

(c) 基于SURF算法

(d) 本文算法圖4 高重疊百分比柵格地圖配準(zhǔn)結(jié)果比較

5 結(jié) 語(yǔ)

本文提出了一種基于局部特征的柵格地圖拼接方法。利用擴(kuò)散濾波算法搭建非線性金字塔；使用FAST算法快速定位特征點(diǎn)；用改進(jìn)PCA-SIFT算法生成36維的特征描述子并進(jìn)行匹配；用RANSAC算法優(yōu)選匹配特征點(diǎn)；用一種適合柵格地圖的融合方法進(jìn)行地圖融合。本文方法和其他圖像匹配算法在公開數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明：本文的算法雖然在特征點(diǎn)的選擇數(shù)量、特征點(diǎn)的匹配和拼接速度上都有很大的優(yōu)勢(shì)，但當(dāng)柵格地圖尺寸不一致時(shí)，會(huì)在地圖邊緣出現(xiàn)重影。