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

李雅梅 蘇 龍

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

0 引 言

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

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

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

1 柵格地圖模型建立

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

(1)

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

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

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

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

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

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

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

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

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

2 改進PCA-SIFT特征點提取

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

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

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

圖1 FAST角點檢測

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

2.2 特征點描述符的建立

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

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

(8)

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

(9)

θ=atan2(m01,m10)

(10)

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

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

計算M矩陣的協方差：

M=M-mean(M)

(11)

covM=MTM

(12)

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

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

dPCA-SIFT=H×N

(13)

3 特征柵格地圖融合

3.1 特征點匹配

3.2 選擇最佳的匹配點

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

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

(2) 利用假定的內點估算一個合適的數學模型，計算模型參數。

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

(4) 重復步驟(1)、步驟(2)，經過N次迭代次數后，選取最優解，最優解應是包含內點最多的。

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

3.3 柵格地圖融合

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

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

(14)

柵格地圖P中的像素融合結果為：

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

(15)

式中：h( )為融合函數，其融合規則為：

(16)

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

4 實驗結果

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

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

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

(a) 高重疊百分比地圖

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

(c) 低重合百分比地圖圖2 待拼接柵格地圖

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

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

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

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

表1 高重疊柵格地圖匹配數據

表2 中等重疊地圖拼接匹配數據

表3 低重疊地圖拼接匹配數據

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

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

(a) 基于SIFT算法

(b) 基于PCA-SIFT算法

(c) 基于SURF算法

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

5 結 語

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