李雅梅 蘇 龍

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

0 引 言

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

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

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

1 柵格地圖模型建立

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

(1)

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

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

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

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

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

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

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

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

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

2 改進PCA-SIFT特征點提取

2.1 非線性金字塔特征點檢測

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

(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為控制擴散的對比參數(shù)。非線性函數(shù)沒有解析解，這里使用AOS算法[17]對式(2)進行求解，離散化式(2)為：

(5)

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

(6)

式中：τ為任意時間步長。非線性金字塔的圖像可以描述成：

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

(7)

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

圖1 FAST角點檢測

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

2.2 特征點描述符的建立

特定點描述符的建立步驟：

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

(8)

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

(9)

θ=atan2(m01,m10)

(10)

式中：θ為特征點的主方向。

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

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

M=M-mean(M)

(11)

covM=MTM

(12)

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

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

dPCA-SIFT=H×N

(13)

3 特征柵格地圖融合

3.1 特征點匹配

3.2 選擇最佳的匹配點

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

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

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

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

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

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

3.3 柵格地圖融合

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

在進行柵格地圖融合前，先新建一個柵格地圖P，尺寸由地圖T(B)和地圖A決定。地圖T(B)是根據(jù)地圖B由剛體變換得到，對應(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重疊處像素值相同，則像素點值為x；若A、B重疊處像素值不同且B像素值等于背景像素值，則像素點值為x；若A、B重疊處像素值不同且A像素值等于背景像素值，則像素點值為y。

4 實驗結(jié)果

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

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

圖3為使用本文算法，三組柵格地圖拼接結(jié)果。圖3(a)中兩幅柵格地圖雖高度重疊，但在地圖邊緣位置有尺寸差異，致使拼接地圖邊緣出現(xiàn)重影，如方框區(qū)域。圖2(b)中兩幅中等重疊柵格地圖尺寸一致，拼接效果良好，并未出現(xiàn)明顯重影，如圖3(b)所示。圖2(c)中兩幅低重疊柵格地，成功進行拼接，且拼接質(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算和本文算法進行柵格地圖拼接得到的數(shù)據(jù)。在本實驗中，基于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算法。本文算法特征點檢測使用FAST算法，僅比較相鄰像素點的大小，特征點提取速度優(yōu)于另外三種算法，描述符使用PCA算法降維為36維，故整體匹配速度超過其他算法。

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

(a) 基于SIFT算法

(b) 基于PCA-SIFT算法

(c) 基于SURF算法

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

5 結(jié) 語

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