融合圖特征的多機(jī)器人柵格地圖拼接方法

黃小杭，曾 碧，劉建圻，汪明慧

廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

對(duì)未知環(huán)境構(gòu)建地圖是移動(dòng)機(jī)器人技術(shù)中的一項(xiàng)基本挑戰(zhàn)，而地圖的構(gòu)建通常需要對(duì)機(jī)器人位姿的精確估計(jì)，因此目前移動(dòng)機(jī)器人主要通過(guò)同步定位與建圖（simultaneous localization and mapping，SLAM）技術(shù)[1-2]構(gòu)建環(huán)境地圖，目前已有多種較為成熟的單機(jī)器人SLAM算法[3-5]，而在大規(guī)模未知環(huán)境中，單機(jī)器人的地圖構(gòu)建精度、效率和魯棒性都存在限制，在過(guò)去的十年中，多機(jī)器人協(xié)作已經(jīng)成為了目前研究的熱點(diǎn)，多機(jī)器人的引入有助于突破上述單機(jī)器人SLAM算法存在的限制。在機(jī)器人SLAM算法中，其地圖類型可分為特征地圖、拓?fù)涞貓D和柵格地圖[1-2]，其中柵格地圖可直觀地表達(dá)真實(shí)環(huán)境的結(jié)構(gòu)，存儲(chǔ)方便，并在精確定位與導(dǎo)航方面更具優(yōu)勢(shì)。

在多機(jī)器人SLAM中，各機(jī)器人在構(gòu)建各自的局部地圖之后，如何拼接局部地圖并確定各機(jī)器人之間的相對(duì)位姿是個(gè)熱點(diǎn)問(wèn)題。

Konolige等人指出，機(jī)器人地圖拼接問(wèn)題是一個(gè)有意義且具有挑戰(zhàn)性的問(wèn)題，但是它并沒(méi)有像SLAM等其他機(jī)器人問(wèn)題一樣受到關(guān)注[6]。

其中基于優(yōu)化和特征匹配的方法是較為主流的思路。Carpin和Brik將地圖匹配問(wèn)題建模為優(yōu)化問(wèn)題，然后通過(guò)隨機(jī)搜索算法進(jìn)行求解[7-8]。在他們的后續(xù)工作中通過(guò)使用刪除異常點(diǎn)的機(jī)制和更復(fù)雜的方法來(lái)優(yōu)化搜索來(lái)提高先前工作的性能[9]。Carpin提出了一種使用Hough變換對(duì)搜索空間建模的方法，并將其分解為平移和旋轉(zhuǎn)估計(jì)，以合并多機(jī)器人系統(tǒng)中的占據(jù)柵格地圖[10]，該方法拼接速度快，但由于Hough變換存在參數(shù)離散化現(xiàn)象，且匹配效果容易受到地圖噪聲影響，魯棒性較差。

對(duì)于基于特征匹配的拼接方法，其中利用SIFT（scale-invariant feature transform）[11-13]、SURF（speeded up robust features）[14]、PCA-SIFT（principal component analysis-based SIFT）[15]、ORB（oriented fast and rotated brief）[16]等圖像特征，將地圖視為圖像，此時(shí)柵格地圖拼接可視為圖像配準(zhǔn)的一種特殊情況。由于室內(nèi)環(huán)境的自相似性，與一般的圖像相比，柵格地圖提供的特征較少，僅適用于重疊率較大的地圖，這些方法容易受到局部最小值的影響，尤其是在沒(méi)有準(zhǔn)確的初值估計(jì)的情況下。

地圖拼接問(wèn)題目前主要面臨以下挑戰(zhàn)：

（1）柵格地圖的拼接需要較大的重疊區(qū)域。

（2）由于SLAM算法本身存在累積誤差和觀測(cè)噪聲，因此構(gòu)建的地圖往往存在一定的非剛性形變。

（3）需要考慮地圖拼接的處理時(shí)間，尤其是對(duì)于大型地圖，其計(jì)算會(huì)非常密集，因此會(huì)阻礙某些同時(shí)運(yùn)行的具有實(shí)時(shí)需求的程序，例如機(jī)器人定位和導(dǎo)航程序。

針對(duì)上述問(wèn)題，本文提出通過(guò)融合圖特征的柵格地圖拼接方法，所提出的方法基于ORB特征點(diǎn)，通過(guò)建立關(guān)特征點(diǎn)之間的中值K近鄰圖來(lái)表征局部關(guān)系，建立最優(yōu)傳輸模型并求解最優(yōu)特征點(diǎn)匹配，實(shí)現(xiàn)柵格地圖魯棒的配準(zhǔn)和拼接。本文方法具備較高的拼接精度，可拼接重疊度較低的地圖，且具備一定抗非剛性形變干擾的能力，在本文實(shí)驗(yàn)中，本文方法也展現(xiàn)出了較快的計(jì)算速度，尤其是在面對(duì)大規(guī)模場(chǎng)景。

1 柵格地圖拼接的問(wèn)題描述

移動(dòng)機(jī)器人創(chuàng)建的柵格地圖，通過(guò)將環(huán)境劃分為等分辨率的平面柵格，這些柵格通過(guò)矩陣形式存儲(chǔ)于計(jì)算機(jī)中，可視為圖像。假設(shè)系統(tǒng)中存在兩臺(tái)機(jī)器人A和B，其構(gòu)建的柵格地圖表示為圖像IA和IB，其中對(duì)于所有像素pij∈I都存在三種可能的狀態(tài)：占據(jù)、空閑和未知。其中未知狀態(tài)主要受機(jī)器人自身觀測(cè)影響而非真實(shí)世界的描述，因此本文將空閑和未知的狀態(tài)均歸為“其他”狀態(tài)，此時(shí)待處理的柵格地圖可二值化為兩個(gè)狀態(tài)：占據(jù)pij=1或其他pij=0，定義兩臺(tái)機(jī)器人的柵格地圖點(diǎn)集數(shù)據(jù)為：

且兩者存在重疊區(qū)域即A?B≠?，柵格地圖拼接問(wèn)題即求解A到B的剛體變換T={R,t}。其中R∈SO(2)為旋轉(zhuǎn)矩陣，t∈?2為平移向量：

經(jīng)過(guò)變換后點(diǎn)集A與點(diǎn)集B的重疊部分配準(zhǔn)，即可進(jìn)一步將柵格地圖拼接表示為如下的最小化問(wèn)題：

2 融合圖特征的柵格地圖拼接方法

2.1 ORB特征提取與粗匹配

本文采用ORB[17]特征。ORB是一種FAST特征點(diǎn)檢測(cè)和BRIEF特征描述符融合的圖像特征提取算法，其具有較高精度，較小的計(jì)算量，以及良好的旋轉(zhuǎn)不變性和尺度不變性。

ORB特征提取和粗匹配步驟如下：

步驟1利用高斯濾波器對(duì)待匹配的柵格地圖進(jìn)行適當(dāng)?shù)哪：?，使二值圖像的邊緣產(chǎn)生連續(xù)平滑的梯度，本文使用尺寸為3×3，標(biāo)準(zhǔn)差σ=1的高斯卷積核。

步驟2提取兩張地圖圖像中具有方向信息的多尺度FAST特征點(diǎn)并采用非極大抑制算法去除Harris響應(yīng)低的FAST特征點(diǎn)，得。

步驟3以FAST特征點(diǎn)的方向?yàn)榛鶞?zhǔn)，提取BRIEF特征描述子。

步驟4利用FLANN（fast library for approximate nearest neighbors）庫(kù)[18]的多探針局部敏感哈希（localitysensetive Hashing，LSH）算法快速搜索兩個(gè)特征點(diǎn)集中距離最近的匹配點(diǎn)對(duì)，同時(shí)引入Lowe[11]所提出比率測(cè)試方法，剔除不合理的特征點(diǎn)，得到匹配點(diǎn)對(duì)，。

經(jīng)過(guò)ORB特征的提取與粗匹配，提前剔除較為明顯的誤匹配點(diǎn)，降低后續(xù)算法的計(jì)算規(guī)模。

2.2 中值K近鄰圖的構(gòu)建

為了度量粗匹配結(jié)果的幾何關(guān)系合理程度，用于優(yōu)化匹配結(jié)果，本文受到Aguilar等人[19]提出的圖變換匹配（graph transformation matching，GTM）的啟發(fā)，通過(guò)對(duì)每張地圖中粗匹配后的特征點(diǎn)構(gòu)建中值K近鄰圖，即每個(gè)特征點(diǎn)和其滿足中值約束條件的最近的K個(gè)特征點(diǎn)建立近鄰圖的邊，本文以點(diǎn)集構(gòu)建中值K近鄰圖Gp=(Vp,Ep)為例，首先定義一個(gè)頂點(diǎn)vi對(duì)應(yīng)于每個(gè)點(diǎn)pi，即Vp={v1,v2,…,vnm}，無(wú)向邊(vi,vj)連接著與pi距離最近的K個(gè)鄰居pj，并且‖pi-pj‖≤η，其中，η為所有頂點(diǎn)對(duì)之間的距離的中間數(shù)，即：

K最近鄰條件可表達(dá)其局部幾何結(jié)構(gòu)，而中值約束主要在于過(guò)濾由于偏遠(yuǎn)點(diǎn)引起的結(jié)構(gòu)變形。對(duì)待拼接的兩張地圖特征點(diǎn)分別構(gòu)建中值K近鄰圖Gp=(Vp,Ep)和Gq=(Vq,Eq)，本文K值取10。

2.3 最優(yōu)傳輸模型優(yōu)化對(duì)應(yīng)關(guān)系

2.3.1 最優(yōu)傳輸模型構(gòu)建

為了融合特征描述子和中值K近鄰圖的特征，優(yōu)化特征點(diǎn)間的對(duì)應(yīng)關(guān)系，和傳統(tǒng)特征點(diǎn)匹配方法不同，本文將ORB特征點(diǎn)之間的匹配問(wèn)題轉(zhuǎn)換為Gp和Gq的圖匹配問(wèn)題，由此可將該圖匹配問(wèn)題轉(zhuǎn)換為指派問(wèn)題，假設(shè)通過(guò)粗匹配后待匹配點(diǎn)集為，經(jīng)過(guò)粗匹配后np=nq,為不失一般性，該指派問(wèn)題可松弛為最優(yōu)傳輸問(wèn)題[20]并表達(dá)為求一個(gè)軟匹配矩陣P,即可建立最優(yōu)傳輸模型：

其中，μp和υq表示特征點(diǎn)的總質(zhì)量，即特征點(diǎn)的權(quán)重之和。傳輸代價(jià)矩陣為特征點(diǎn)pi到qc(j)的傳輸成本，在本文中，特征點(diǎn)權(quán)重相等，每個(gè)特征點(diǎn)質(zhì)量可設(shè)為1，即：

式（5）中對(duì)集合的線性約束確保Vp傳遞到Vq的質(zhì)量保持一致，即從集合Vp轉(zhuǎn)移質(zhì)量到Vq后，系統(tǒng)的總質(zhì)量保持不變，這就要求此優(yōu)化問(wèn)題中Vp和Vq必須具有相同質(zhì)量，并且每個(gè)節(jié)點(diǎn)始終以一個(gè)質(zhì)量單位傳輸，這種情況需要保證最終匹配結(jié)果中節(jié)點(diǎn)數(shù)量np=nq，在實(shí)踐中可知，由于粗匹配結(jié)果中存在無(wú)法正確匹配的點(diǎn)對(duì)（即離群值），因此傳輸?shù)馁|(zhì)量不一定保持一致。為了移除離群值，同時(shí)滿足最優(yōu)傳輸問(wèn)題的質(zhì)量約束，本文引入兩個(gè)增廣節(jié)點(diǎn)gp∈Vp和gq∈Vq，用于放置離群值的質(zhì)量。定義α為離群值權(quán)重，用于估計(jì)上述最優(yōu)傳輸模型中的離群值。增廣節(jié)點(diǎn)的引入使得式（5）增加了如下約束：

其中：

式（8）的參數(shù)ω只與離群值的數(shù)量有關(guān)，可控制離群值篩選的嚴(yán)格程度。為了在求解上述最優(yōu)傳輸問(wèn)題的過(guò)程中將離群值吸引至增廣節(jié)點(diǎn)gp和gq，需要在代價(jià)矩陣C中增加關(guān)于增廣節(jié)點(diǎn)傳輸代價(jià)，本文選用C中行或者列的最小值作為其他節(jié)點(diǎn)到增廣節(jié)點(diǎn)的傳輸代價(jià)。在求解該最優(yōu)傳輸問(wèn)題后，所有與增廣節(jié)點(diǎn)匹配的節(jié)點(diǎn)可以認(rèn)為是離群值，通過(guò)從P中刪除與增廣節(jié)點(diǎn)有關(guān)的行和列來(lái)獲得最終的對(duì)應(yīng)關(guān)系，示意圖如圖1所示。

圖1 增廣節(jié)點(diǎn)去除離群值示意圖Fig.1 Using additional nodes to remove outliers

2.3.2 最優(yōu)傳輸代價(jià)矩陣構(gòu)建

式（5）中的傳輸代價(jià)矩陣C主要由兩個(gè)部分組成：由Vp和Vq的ORB特征描述子之間的歸一化漢明距離構(gòu)成的節(jié)點(diǎn)到節(jié)點(diǎn)的相異性矩陣S和表示圖Gp和Gq結(jié)構(gòu)相異性矩陣R組成，將代價(jià)映射至[0,1)范圍內(nèi)傳輸代價(jià)矩陣可定義為：

其中對(duì)于節(jié)點(diǎn)結(jié)構(gòu)相異性矩陣R構(gòu)建，本文對(duì)待匹配柵格地圖做如下假設(shè)：待匹配柵格地圖占據(jù)點(diǎn)之間的關(guān)系約束是保持一致的，因此第一張柵格地圖特征點(diǎn)的相鄰點(diǎn)對(duì)應(yīng)于第二張地圖的特征點(diǎn)的相鄰點(diǎn)，若所有對(duì)應(yīng)關(guān)系正確，該對(duì)節(jié)點(diǎn)的鄰接結(jié)構(gòu)應(yīng)保持一致，非正確對(duì)應(yīng)的匹配點(diǎn)將導(dǎo)致兩圖增加節(jié)點(diǎn)間結(jié)構(gòu)相異性。根據(jù)這個(gè)假設(shè)，本文通過(guò)計(jì)算節(jié)點(diǎn)結(jié)構(gòu)相異性矩陣Rij=來(lái)度量中值K近鄰圖的結(jié)構(gòu)相似度，其中Ap和Aq分別為Gp和Gq的鄰接矩陣。

2.3.3 最優(yōu)傳輸模型求解

待匹配特征點(diǎn)的數(shù)量大約在100～2 000這個(gè)數(shù)量級(jí)，若要求式（5）精確解，可利用網(wǎng)絡(luò)流求解器求解，然而其時(shí)間復(fù)雜度為O(n3)（其中n與np和nq成正比），時(shí)間復(fù)雜度較高，因此本文Sinkhorn算法[21]近似求解該最優(yōu)傳輸問(wèn)題，其時(shí)間復(fù)雜度為O((np+1)×(nq+1))。對(duì)式（5）熵正則化：

其中：

步驟1初始化；

步驟2計(jì)算；

步驟3計(jì)算P=diag(a)Kdiag(b)并代入式（10）計(jì)算Sinkhorn距離ds；

步驟4重復(fù)步驟2和步驟3，直到兩次迭代的ds之差小于終止條件閾值eps，解得。

2.4 計(jì)算拼接結(jié)果

2.4.1 變換估計(jì)

利用上述方法給出的特征點(diǎn)的對(duì)應(yīng)關(guān)系，通過(guò)最小二乘法求解式（3）可估計(jì)柵格地圖IA到柵格地圖IB像素之間的剛體變換{R,t}，為了實(shí)現(xiàn)較為魯棒的變換估計(jì)，采用隨機(jī)采樣一致性（random sample consensus，RANSAC）算法估計(jì)剛體變換參數(shù)。相對(duì)于傳統(tǒng)基于特征點(diǎn)匹配的柵格地圖拼接算法而言，本文的特征點(diǎn)匹配關(guān)系已經(jīng)過(guò)優(yōu)化，RANSAC算法僅需較少的迭代次數(shù)即可估計(jì)精確的剛體變換參數(shù)。

2.4.2 地圖拼接

創(chuàng)建空白柵格地圖IW，柵格地圖IA變換為柵格地圖T(IA)，其對(duì)應(yīng)像素為：

柵格地圖T(IA)和IB均置于空白柵格地圖IW，本文采用文獻(xiàn)[13]中的融合函數(shù)融合對(duì)應(yīng)像素：

其中，x、y分別為柵格地圖均為柵格地圖的像素值。拼接結(jié)果為：

2.5 融合圖特征的柵格地圖拼接實(shí)現(xiàn)

融合圖特征的柵格地圖拼接方法的具體實(shí)現(xiàn)步驟如下：

步驟1輸入兩張柵格地圖圖像IA和IB，提取ORB特征并粗匹配。

步驟2構(gòu)建每張柵格地圖特征點(diǎn)的中值K近鄰圖。首先建立特征點(diǎn)的K維樹（KD-Tree），查找每個(gè)特征點(diǎn)最近的K個(gè)鄰居特征點(diǎn)，然后在鄰居中篩選出滿足中值約束的鄰居特征點(diǎn)建立無(wú)向邊，構(gòu)建中值K近鄰圖鄰接矩陣Ap和Aq。

步驟3構(gòu)建最優(yōu)傳輸代價(jià)矩陣C。分別計(jì)算節(jié)點(diǎn)相異性矩陣R和圖結(jié)構(gòu)相異性矩陣S,代入式（9）計(jì)算最優(yōu)傳輸代價(jià)矩陣C,將C中行或者列的最小值作為其他節(jié)點(diǎn)到增廣節(jié)點(diǎn)的傳輸代價(jià)。設(shè)置最優(yōu)傳輸權(quán)重向量μp和υq,其中特征點(diǎn)節(jié)點(diǎn)的權(quán)重為均為1，增廣節(jié)點(diǎn)的權(quán)重由式（8）給出。

步驟4將節(jié)點(diǎn)權(quán)重μp和υq,代價(jià)矩陣C和熵正則化系數(shù)λ和終止條件閾值eps代入Sinkhorn-Knopp算法中迭代求解軟匹配矩陣P,取P每行（或列）最大值的行列索引為節(jié)點(diǎn)匹配結(jié)果，去除增廣節(jié)點(diǎn)所匹配的節(jié)點(diǎn)后，得到優(yōu)化后的特征點(diǎn)之間的對(duì)應(yīng)關(guān)系。

步驟5將特征點(diǎn)對(duì)應(yīng)關(guān)系代入式（3）并通過(guò)RANSAC算法估計(jì)剛體變換參數(shù){R,t}，創(chuàng)建空白柵格地圖IW，地圖IA通過(guò)式（12）變換后，再通過(guò)式（13）所述的融合函數(shù)進(jìn)行像素融合，最后得到拼接結(jié)果IW。

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

3.1 實(shí)驗(yàn)平臺(tái)、數(shù)據(jù)集與評(píng)估指標(biāo)

本文方法在一臺(tái)主頻2.5 GHz四核CPU，內(nèi)存8 GB的筆記本電腦上完成所有實(shí)驗(yàn)程序的運(yùn)行。為了驗(yàn)證本文方法的可行性和性能，并分析所述參數(shù)對(duì)算法性能的影響，本文主要在TUMindoor數(shù)據(jù)集[22]和多機(jī)器人采集的柵格地圖數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

其中TUMindoor數(shù)據(jù)集采用精度為0.1 m的柵格地圖經(jīng)過(guò)人工按一定重疊率裁切，而本文采集的數(shù)據(jù)集采用圖2所示的兩臺(tái)搭載2D激光雷達(dá)的微型輪式機(jī)器人分別通過(guò)Gmapping算法建立柵格地圖，所用數(shù)據(jù)的具體參數(shù)如表1，其中T-前綴為TUMindoor數(shù)據(jù)集，R-前綴為通過(guò)多機(jī)器人采集的柵格地圖數(shù)據(jù)集。

這里對(duì)本文所提出的算法從以下三個(gè)方面進(jìn)行評(píng)估：

（1）針對(duì)特征點(diǎn)匹配結(jié)果，評(píng)估算法得出的匹配數(shù)，該匹配數(shù)由RANSAC算法估計(jì)，匹配數(shù)可在一定程度上評(píng)估特征匹配算法的魯棒性：當(dāng)匹配數(shù)過(guò)低時(shí)，經(jīng)過(guò)RANSAC算法估計(jì)符合剛體變換規(guī)律的特征點(diǎn)較少，故魯棒性較低；當(dāng)匹配數(shù)足夠多時(shí)，魯棒性會(huì)相對(duì)較好，但過(guò)多的匹配數(shù)往往會(huì)引入假匹配點(diǎn)對(duì)和額外的計(jì)算量，影響配準(zhǔn)精度和運(yùn)行耗時(shí)。可結(jié)合后續(xù)指標(biāo)進(jìn)一步評(píng)估。

（3）針對(duì)算法實(shí)時(shí)性的評(píng)估，采用算法運(yùn)行耗時(shí)對(duì)比的方式評(píng)估。

3.2 分析實(shí)驗(yàn)

本文方法的匹配數(shù)主要受離群值權(quán)重ω和正則化系數(shù)λ影響，在R-ESAC509數(shù)據(jù)集中，其參數(shù)取值與匹配數(shù)的關(guān)系如圖3所示。

圖3 參數(shù)ω 和λ 對(duì)匹配數(shù)的影響Fig.3 Effect of parameters ω and λ on number of matches

可以看出，離群值權(quán)重ω取值越大，算法對(duì)離群值過(guò)濾越嚴(yán)格，若該值過(guò)大會(huì)導(dǎo)致將正確的匹配歸入離群值。熵正則化系數(shù)λ越大，算法會(huì)盡可能地傾向均勻分配，而該值越小則越傾向于尋找代價(jià)最小的匹配，本文的代價(jià)矩陣中增廣節(jié)點(diǎn)的匹配代價(jià)最小，因此該值越小過(guò)濾離群值的效果越強(qiáng)。在后續(xù)實(shí)驗(yàn)中，本文選用參數(shù)ω=0.02,λ=5。

Sinkhorn-Knopp算法迭代過(guò)程中各數(shù)據(jù)集的Sinkhorn距離收斂曲線如圖4。Sinkhorn距離可在4～6輪迭代實(shí)現(xiàn)收斂，在工程實(shí)現(xiàn)上，直接設(shè)定合適的迭代次數(shù)而免去Sinkhorn距離的計(jì)算可降低迭代計(jì)算量。

圖4 各數(shù)據(jù)集的Sinkhorn距離收斂曲線Fig.4 Sinkhorn distance convergence curves for each dataset

3.3 對(duì)比實(shí)驗(yàn)

本文方法將分別與基于SIFT方法和基于ORB方法進(jìn)行對(duì)比，其中魯棒配準(zhǔn)算法均采用RANSAC方法。對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表2。圖5為地圖拼接實(shí)驗(yàn)對(duì)比，圖6為特征匹配結(jié)果對(duì)比柵格地圖。

對(duì)于匹配數(shù)，基于ORB的拼接方法擁有最高的匹配數(shù)，但引入了較多冗余匹配，增加了一定額外計(jì)算量。本文算法由于剔除了誤差較大的離群值、優(yōu)化了特征點(diǎn)之間的對(duì)應(yīng)關(guān)系，整體匹配數(shù)略少，但相對(duì)于基于SIFT的匹配方法匹配數(shù)量仍然可觀，本文算法同時(shí)也具有較高的匹配魯棒性。

對(duì)于角度誤差和平移誤差，本文算法在TUMindoor數(shù)據(jù)集和多機(jī)器人建圖數(shù)據(jù)集均表現(xiàn)出較高的拼接精度和魯棒性，而基于SIFT的拼接方法在重疊率較低且重疊部分紋理不明顯的R-ESAC509中出現(xiàn)配準(zhǔn)失誤，而基于ORB的拼接方法在數(shù)據(jù)集R-ESAC507和R-ESAC509中也出現(xiàn)較明顯的角度誤差。

對(duì)于運(yùn)行耗時(shí)，本文算法的平均耗時(shí)最短，基于ORB的拼接方法耗時(shí)與本文接近，基于SIFT的拼接方法平均耗時(shí)最長(zhǎng)。盡管在本文算法中最優(yōu)傳輸模型的求解部分引入了較多的計(jì)算量，但由于該部分如Sinkhorn-Knopp算法主要以矩陣運(yùn)算為主，且迭代收斂速度快，利用基礎(chǔ)線性代數(shù)子程序庫(kù)（basic linear algebra subprograms，BLAS）或GPU并行計(jì)算可較為容易地有效提升相關(guān)運(yùn)算速度。在本文實(shí)驗(yàn)中僅使用了CPU和BLAS庫(kù)。

表2 對(duì)比實(shí)驗(yàn)結(jié)果Table 2 Results of comparison experiment

圖5 柵格地圖拼接結(jié)果對(duì)比Fig.5 Comparison of results of grid map stitching

圖6 特征匹配結(jié)果對(duì)比Fig.6 Comparison of feature matching results

4 結(jié)論

針對(duì)基于特征匹配的柵格地圖拼接方法面臨的地圖特征較少并存在自相似性，依賴柵格地圖較大重疊區(qū)域、柵格地圖存在非剛性形變等問(wèn)題，本文提出的融合圖特征的柵格地圖拼接方法，所提出的方法基于ORB特征點(diǎn)，通過(guò)建立關(guān)特征點(diǎn)之間的中值K近鄰圖來(lái)表征局部關(guān)系，并通過(guò)最優(yōu)傳輸模型求解最優(yōu)特征點(diǎn)匹配，實(shí)現(xiàn)柵格地圖的配準(zhǔn)和拼接。本文方法具備較高的拼接精度，可拼接重疊度較低的地圖，且具備一定抗非剛性形變干擾的能力，在本文實(shí)驗(yàn)中，充分分析了相關(guān)參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響，同時(shí)本文方法分別與基于SIFT的拼接方法和基于ORB的拼接方法進(jìn)行了對(duì)比，本文方法展現(xiàn)出了較快的計(jì)算速度和較高的精度和魯棒性。