無(wú)人機(jī)自主定位中的仿射二進(jìn)制特征匹配?

張含茜 石朝俠

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

隨著無(wú)人機(jī)在監(jiān)視、勘測(cè)、物流［1］等領(lǐng)域的廣泛的應(yīng)用，越來(lái)越多的科研工作者開(kāi)始對(duì)無(wú)人機(jī)自主定位技術(shù)進(jìn)行研究。在城市的空曠地區(qū)，基于民用GPS的無(wú)人機(jī)定位誤差約在10m左右，但在樓宇環(huán)境下，GPS信號(hào)受到遮擋、多徑效應(yīng)［2］的影響，定位誤差可以達(dá)到幾百米甚至幾千米。如圖1所示，這是上海陸家嘴金融貿(mào)易區(qū)某高樓下繞著高樓行走的真實(shí)軌跡（淺色）和GPS軌跡（深色）的對(duì)比。基于視覺(jué)的無(wú)人機(jī)定位系統(tǒng)則為解決上述問(wèn)題提供了廉價(jià)的解決方案。

局部特征對(duì)環(huán)境光照變化、尺度變化、局部遮擋和仿射變換具有較好的不變性，被越來(lái)越多地用于圖像定位匹配中。但SIFT（Scale-invariant feature transform，SIFT）、SURF（Speeded-Up Robust Features，SURF）這些用高維浮點(diǎn)數(shù)表示的局部圖像特征描述方法在計(jì)算時(shí)不僅會(huì)消耗大量的內(nèi)存，而且匹配的時(shí)間也會(huì)隨著數(shù)據(jù)量的增多急劇增加。因此，二進(jìn)制特征提取算子［3～5］，如 ORB（Oriented Brief，ORB）、BRIEF（Binary Robust Independent Elementary Features，BRIEF）、BRISK（Binary Robust In variant Scalable Keypoints，BRISK）等具有越來(lái)越高的研究?jī)r(jià)值。BRIEF特征描述子［3］是在特征點(diǎn)附近用貪婪算法隨機(jī)選取若干點(diǎn)對(duì)，并將這些點(diǎn)對(duì)的灰度值大小組成二進(jìn)制串，其缺點(diǎn)在于不具備旋轉(zhuǎn)不變性而且對(duì)噪聲敏感。在2011年，Rublee提出了ORB特征描述子［4］，他改進(jìn)了BRIEF算法［3］并采用 FAST（Features from accelerated segment test，F(xiàn)AST）［6］作為特征提取方法，使得 ORB能保證特征魯棒性的前提下將特征提取速度提高2個(gè)數(shù)量級(jí)。BRISK［5］也是基于BRIEF特征描述子改進(jìn)的，通過(guò)建立尺度空間來(lái)解決旋轉(zhuǎn)不變性等問(wèn)題，但在速度上遠(yuǎn)遠(yuǎn)不及ORB特征。因此，為了快速得到魯棒的仿射圖像匹配結(jié)果，本文提出的算法將基于ORB二進(jìn)制局部特征描述算子。

圖1 上海陸家嘴某高樓下行走軌跡（淺）和GPS軌跡（深）

城市定位中經(jīng)常會(huì)遇到仿射問(wèn)題，傳統(tǒng)的特征提取與匹配算法不適用高視角變換下的圖像匹配。在2011年，Guoshen.Yu針對(duì)SIFT算法不滿足完全仿射不變性的缺點(diǎn)提出了ASIFT算法，通過(guò)經(jīng)度和緯度角來(lái)描述相機(jī)位置并達(dá)到了很好的匹配效果，可是該算法所耗費(fèi)時(shí)間過(guò)長(zhǎng)。在2014年，侯毅等人提出了AORB（Affine-ORB，AORB）算法［16］，改進(jìn)了ORB算法的仿射性能，并相對(duì)于ASIFT算法速度提高了6倍，即便如此，AORB算法匹配圖像所耗時(shí)間仍然較長(zhǎng)。針對(duì)上述問(wèn)題，本文提出基于虛擬視角和中間圖像的快速仿射匹配算法。

近年來(lái)，有很多研究工作致力于通過(guò)圖像檢索和城市環(huán)境圖像匹配來(lái)解決定位問(wèn)題。Bayesian-fashion［7］方法實(shí)現(xiàn)了地面車(chē)在仿城市環(huán)境下的定位，基于圖像檢索的興趣點(diǎn)檢測(cè)（POI）算法［8～10］利用地標(biāo)建筑或是博物館來(lái)解決定位問(wèn)題。現(xiàn)在，越來(lái)越多的人開(kāi)始利用街景地圖數(shù)據(jù)［11～14］進(jìn)行定位。然而以上這些提及的方法都使用地面角度拍攝的圖像和街景數(shù)據(jù)進(jìn)行圖像匹配，并不適用于地面和空中圖像匹配的情況。

而絕大多數(shù)解決地面和空中圖像匹配的問(wèn)題的解決方案的實(shí)驗(yàn)環(huán)境與我們的不同，尤其是空中圖像獲取的高度方面。例如，在文［11～14］中，他們研究的問(wèn)題是針對(duì)衛(wèi)星地圖或是高空（幾百米）所獲取的空中圖片信息和地表圖像信息的定位。而不同的是，我們采用的是低空城市環(huán)境中，街景地圖數(shù)據(jù)和無(wú)人機(jī)采集的空中圖像，即街景地圖與無(wú)人機(jī)在地表以上10m～20m的距離高度所獲取的圖像匹配。

2 仿射攝像機(jī)模型

攝像機(jī)成像通常采用透視投影模型，其基本關(guān)系式為

其中，u為數(shù)字圖像，u0為一個(gè)理想化可以無(wú)限分割的平面，參數(shù)δ是轉(zhuǎn)換矩陣，參數(shù)A是由相機(jī)產(chǎn)生的映射矩陣。G1是高斯濾波，S1是基于網(wǎng)格的采樣。我們假設(shè)高斯核足夠大能滿足圖像采樣時(shí)不走樣，也就是 IS1G1Aδu0=G1Aδu0，其中 I為Shannon-Whitaker采樣插值操作。我們對(duì)上述模型進(jìn)行簡(jiǎn)化，更直觀的如圖2所示。

圖2 透視模型的幾何理解

在投影空間中，更為普遍的變換稱(chēng)為單應(yīng)性變換，單應(yīng)性變換僅保持圖像中點(diǎn)集的共線性和共線三點(diǎn)的簡(jiǎn)單比。單應(yīng)性采用齊次坐標(biāo)表示:

其中，H表示的是單應(yīng)性矩陣，x表示的是原坐標(biāo)系中齊次坐標(biāo)，x′表示單應(yīng)性變換后的坐標(biāo)系中的齊次坐標(biāo)。可見(jiàn)，單應(yīng)性變換包含了仿射變換。若采用單應(yīng)性矩陣的形式表示仿射變換:

其中，A是一個(gè)2×2的非奇異矩陣，d為二維平移矢量，平移單應(yīng)性矩陣HA有六個(gè)自由度，對(duì)應(yīng)于六個(gè)矩陣元素，可以由三組點(diǎn)對(duì)應(yīng)來(lái)計(jì)算。我們也可以將仿射矩陣A看作旋轉(zhuǎn)和非均勻縮放的復(fù)合，將A分解可得:

其中，λ＞0，RI是旋轉(zhuǎn)矩陣，?∈[0，2π)，Tt是傾斜度矩陣，也可以認(rèn)為是一個(gè)特征值為t和1的對(duì)角矩陣，其中t＞1。

3 基于搜索的虛擬視角生成

如果把相機(jī)所在位置看成是投影中心，那么地面圖像和空中圖像的可以看是射影變換中的仿射變換。

進(jìn)一步理解，如圖3所示，由相機(jī)光軸變換造成的仿射幾何理解。

圖3 仿射分解的幾何理解

其中，?和θ是旋轉(zhuǎn)角，t為傾斜度，ψ是相機(jī)光軸的旋轉(zhuǎn)參數(shù)，λ是相對(duì)應(yīng)的比例因子。假設(shè)相機(jī)的位置相對(duì)圖片π足夠遠(yuǎn)，即相機(jī)正面對(duì)著圖片π，則此時(shí)t=1，?=0，θ=0。類(lèi)似的，我們可以通過(guò)改變旋轉(zhuǎn)角的?和θ值來(lái)改變相機(jī)的光軸方向，我們分別把參數(shù)?和θ稱(chēng)為經(jīng)度和緯度。不同于Guoshen.Yu的模型［15］，本文設(shè)置的旋轉(zhuǎn)角的?集合為｛0，5，85，90，175，180，270，275｝。其中，子集｛0｝，｛180｝，｛90｝，｛270｝用于確定相機(jī)光軸方向，子集｛0，5｝，｛175，180｝，｛85，90｝，｛270，275｝用于生成模擬圖像。參數(shù)θ設(shè)置如表1所示。

表1 傾斜度t和緯度角θ之間的關(guān)系

為了找到相機(jī)光軸的方向，首先選擇了4對(duì)參數(shù)作為我們的模擬相機(jī)視角，它們分別是｛t=2，?=0｝、｛t=2，?=180｝、｛t=2，?=90｝、｛t=2，?=270｝，通過(guò)模擬相機(jī)光軸的4個(gè)位置來(lái)預(yù)判相機(jī)光軸所在角度，實(shí)驗(yàn)表明，這樣的4點(diǎn)采樣方法比Guoshen Yu提出的暴力匹配速度更快。更直觀的采樣如圖4，圖4上ABCD四個(gè)點(diǎn)分別對(duì)應(yīng)上述4個(gè)模擬視角，左圖為半球體正面透視圖，右圖為半球體俯視透視圖。

圖4 虛擬視角中θ和φ的部分采樣點(diǎn)

4 快速仿射匹配算法

Ethan Rublee等人在2011年提出了一種名為ORB的特征描述子算法［4］，它充分發(fā)揮了FAST和BRIEF這兩種算法實(shí)時(shí)性好的優(yōu)勢(shì)，分別利用它們進(jìn)行特征點(diǎn)檢測(cè)和特征描述能獲得魯棒的特征點(diǎn)和較短的匹配時(shí)間，但其仿射匹配能力較弱。在2014年，侯毅等提出了AORB（Affine-ORB，AORB）算法［16］，改進(jìn)了ORB算法的仿射性能，提高了速度，即便如此，AORB算法匹配圖像所耗時(shí)間仍然較長(zhǎng)。為了進(jìn)一步提高仿射匹配算法的速率，本文提出了一個(gè)基于虛擬視角的快速仿射匹配算法。設(shè)待匹配圖像分別為Ir和Iv，中間圖像為It，模擬圖像Is，算法流程如圖5所示，算法流程偽代碼如算法1所示。

圖5 快速仿射匹配算法流程圖

在圖像匹配時(shí)，通過(guò)RANSAC算法篩選誤匹配點(diǎn)的同時(shí)，我們可以獲得兩幅圖像的單應(yīng)性矩陣H，可以通過(guò)判別單應(yīng)性矩陣H來(lái)判斷圖像匹配的正確性。

因此，本文提出了一個(gè)單應(yīng)性矩陣評(píng)估函數(shù)E:

其中，A，B，C，O是通過(guò)單應(yīng)性矩陣H計(jì)算出的在映射圖上隨機(jī)的四點(diǎn)，λ、μ是兩個(gè)參數(shù)，若存在λ、μ使得λ+μ=1，則認(rèn)為該單應(yīng)性矩陣正確，否則我們認(rèn)為A，B，C不在一個(gè)平面，單應(yīng)性矩陣不正確，需要通過(guò)生成虛擬視覺(jué)解決匹配問(wèn)題。

算法1:快速仿射算法

輸入:地面獲得的圖像Ir和空中無(wú)人機(jī)拍攝的圖像Iv輸出:Ir和Iv匹配點(diǎn)對(duì)

1Fr=地面圖像Ir的ORB特征

2Fv=空中圖像Iv的ORB特征

3單應(yīng)性矩陣H=Fr和Fv的特征匹配+RANSAC

4 E=評(píng)估單應(yīng)性矩陣H

5 IF E滿足閾值條件

6 生成中間圖像It

7 中間圖像It和Iv進(jìn)行ORB特征匹配

8 消除錯(cuò)誤匹配

9 ELSE E不滿足閾值條件

10 生成虛擬視角模擬圖

11 對(duì)Ivision和Iv進(jìn)行ORB特征匹配并找出最優(yōu)匹配的角度T

12 對(duì)角度T附近生成虛擬視角模擬圖

13和Ir進(jìn)行ORB特征匹配

14輸出結(jié)果

圖6 錯(cuò)誤的單應(yīng)性矩陣生成的映射圖像

圖7 正確的單應(yīng)性矩陣生成的映射圖像

圖6 顯示了通過(guò)錯(cuò)誤的單應(yīng)性矩陣H生成的中間圖像，左邊的圖像為原圖像，中間的圖像為生成的中間圖像，右邊的圖像為待匹配圖像。可以發(fā)現(xiàn)，不正確的單應(yīng)性矩陣會(huì)導(dǎo)致原圖像上的點(diǎn)全部映射到一個(gè)點(diǎn)上或是一條直線，而非一個(gè)平面。圖7是通過(guò)正確的單應(yīng)性矩陣H生成的中間圖像。在視角變換較小的情況下，經(jīng)過(guò)RANSAC篩選的ORB特征描述子能夠生成可靠的映射匹配對(duì)，通過(guò)匹配中間圖像和待匹配的圖像Iv，我們能夠獲得更多可靠的匹配對(duì)。然而，ORB特征描述子對(duì)視角變換較大的圖像無(wú)能為力，針對(duì)高變換視角的變換圖像，我們采用了虛擬視角和ORB特征結(jié)合的方法。

為了更好地確定相機(jī)光軸的大致位置，我們通過(guò)匹配虛擬視角生成的4幅模擬圖像來(lái)確定。參數(shù)分別是傾斜度t=2°，?=0°、?=180°、?=90°、?=270°時(shí)的模擬圖像，即模擬相機(jī)分別從原始圖像的右方，左方，下方，前方四個(gè)方向進(jìn)行拍攝。

圖8 模擬相機(jī)光軸視角模擬圖

更直觀的，如圖8，我們模擬從上述右方，左方，下方，上方四個(gè)角度進(jìn)行相機(jī)光軸的模擬，并從左方和右方中選出一個(gè)最優(yōu)方向，并從下方和上方中選出另一個(gè)最優(yōu)方向，然后在兩個(gè)主方向附近用旋轉(zhuǎn)角的?的子集進(jìn)行進(jìn)一步的模擬。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文提出的算法的可靠性，我們使用了兩類(lèi)數(shù)據(jù)集來(lái)進(jìn)行驗(yàn)證。其中第一類(lèi)數(shù)據(jù)集來(lái)源于 Mikolajczyk［16］在 2005 年提出的標(biāo)準(zhǔn)仿射數(shù)據(jù)集，該數(shù)據(jù)集包含模糊變換、視覺(jué)變換、旋轉(zhuǎn)尺度變換、光照變換、JPEG壓縮變換五大變換；第二類(lèi)數(shù)據(jù)集包括地面圖像和空中圖像，以下簡(jiǎn)稱(chēng)地空?qǐng)D像數(shù)據(jù)集。地空?qǐng)D像數(shù)據(jù)集中的空中圖像數(shù)據(jù)是來(lái)源于裝備微型攝像頭的無(wú)人機(jī)（DJI Phantom 3 Standard）所拍攝的視頻流，總計(jì)426張，其中該無(wú)人機(jī)所配備的微型攝像機(jī)具有f/2.8的光圈，能夠錄制每秒30幀的2.7K高清視頻，能夠拍攝1200萬(wàn)像素的靜態(tài)照片，地面圖像數(shù)據(jù)是來(lái)源于百度地圖開(kāi)發(fā)者模式下的全景坐標(biāo)拾取工具所獲取的靜態(tài)全景地圖。更具體的，我們所用的空中圖像數(shù)據(jù)集來(lái)源于南京理工大學(xué)校園，通過(guò)人工操作無(wú)人機(jī)在距離地面15m左右的高空采集到的校園環(huán)境視頻流。在收集數(shù)據(jù)集的過(guò)程中，保持無(wú)人機(jī)上的微型攝像機(jī)總是面向建筑物。

5.2 標(biāo)準(zhǔn)仿射實(shí)驗(yàn)

為了更好地驗(yàn)證本文提出的算法的仿射效果，我們將采用Mikolajczyk在2005年提出的數(shù)據(jù)集［17］中的Viewpoint部分作為實(shí)驗(yàn)數(shù)據(jù)。具體數(shù)據(jù)說(shuō)明如表2所示。

圖9給出了在Mikolajczyk數(shù)據(jù)集Graf中的部分圖像示例以及經(jīng)過(guò)本文的算法運(yùn)行后生成的中間圖像。其中，左圖是Graf數(shù)據(jù)集中的第一幅，中間的圖像是左圖和右圖根據(jù)單應(yīng)性矩陣H生成的中間圖像，右圖是是Graf數(shù)據(jù)中的第三幅。很顯然，由于ORB特征描述子能夠支持小角度的仿射變換，所以經(jīng)過(guò)變換的中間圖像基本和右圖像相似。

表2 Graf和Wall實(shí)驗(yàn)數(shù)據(jù)說(shuō)明

圖9 標(biāo)準(zhǔn)仿射數(shù)據(jù)集部分示例以及相應(yīng)的中間圖像

圖10 是輸出匹配結(jié)果，上圖是通過(guò)生成中間圖片的方法得到的匹配對(duì)結(jié)果，下圖是根據(jù)虛擬視角生成的匹配結(jié)果。表3是標(biāo)準(zhǔn)仿射的匹配結(jié)果以及所用的時(shí)間。由實(shí)驗(yàn)結(jié)果可得，本文提出的算法在該數(shù)據(jù)集下不僅能夠產(chǎn)生足夠并且可靠的匹配對(duì)，還能使得仿射匹配的速度提高到平均1.2844s。

圖10 標(biāo)準(zhǔn)仿射數(shù)據(jù)集部分匹配結(jié)果圖

5.3 空中仿射圖片實(shí)驗(yàn)

在該實(shí)驗(yàn)中，我們使用第二類(lèi)自主采集的數(shù)據(jù)集，部分?jǐn)?shù)據(jù)集圖像如圖11所示。

表3 標(biāo)準(zhǔn)仿射數(shù)據(jù)集匹配結(jié)果

圖11 地空?qǐng)D片數(shù)據(jù)集部分示例

不同于傳統(tǒng)的匹配圖像，在本文的實(shí)驗(yàn)環(huán)境下，可以發(fā)現(xiàn)，空中獲取的圖像往往是地面獲取的圖像的一部分，如圖11。容易發(fā)現(xiàn)，地面圖像和空中圖像的視角差大約在30°～45°，且旋轉(zhuǎn)角度約在5°左右。

為了減少光線、時(shí)間、遮擋等因素對(duì)地空仿射造成的干擾，將參與匹配的圖像轉(zhuǎn)換為灰度圖像，即拋棄了RGB信息，其原因是RGB信息會(huì)對(duì)匹配結(jié)果不但不能提供可靠匹配，還會(huì)造成較大的干擾。因?yàn)樵诓煌募竟?jié)、光照下，同一個(gè)地點(diǎn)不同時(shí)間會(huì)得到不同的RGB信息，這種情況尤其體現(xiàn)在植被上，在夏季，植被多是濃密而茂盛的墨綠，而到秋季，植被漸漸干枯變黃，甚至到冬季，這些植被只剩下莖稈。

圖12是地空?qǐng)D像數(shù)據(jù)集中部分?jǐn)?shù)據(jù)的匹配結(jié)果，表4是從中隨機(jī)抽取的五對(duì)圖片集｛Pair1，Pair2，Pair3，Pair4，Pair5｝的匹配對(duì)的個(gè)數(shù)以及所耗費(fèi)的時(shí)間。可以從圖12和表4中看出，即便在有較多重復(fù)幾何結(jié)構(gòu)的環(huán)境下（如窗戶），本文提出的算法不僅能夠使每對(duì)圖像匹配時(shí)間達(dá)到平均1.5266s，還有足夠的可靠匹配對(duì)。

圖12 地空?qǐng)D片匹配結(jié)果示例

表4 地空?qǐng)D像匹配結(jié)果

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

在本節(jié)，我們將本文提出的算法與AORB、ASIFT等算法進(jìn)行多方面的對(duì)比。

圖13是標(biāo)準(zhǔn)仿射數(shù)據(jù)集特征匹配算法速率對(duì)比圖，水平方向分別代表3種特征匹配算法的對(duì)比以及10組標(biāo)準(zhǔn)仿射實(shí)驗(yàn)數(shù)據(jù)，豎直方向代表的是每組仿射圖像的匹配對(duì)數(shù)與所耗時(shí)間的比值。從中可以看出，在標(biāo)準(zhǔn)化仿射數(shù)據(jù)集中，本文提出仿射匹配算法的速度時(shí)間效率最高，遠(yuǎn)超ASIFT算法和AORB算法，速度最快達(dá)到每秒檢測(cè)1300多個(gè)可靠特征點(diǎn)。

圖13 標(biāo)準(zhǔn)仿射數(shù)據(jù)集特征匹配算法速率對(duì)比

圖14 是標(biāo)準(zhǔn)仿射數(shù)據(jù)集下匹配所消耗的時(shí)間對(duì)比圖，橫坐標(biāo)代表10組匹配圖像，縱坐標(biāo)表示所消耗的時(shí)間，單位為s。從中可以得出，ASIFT算法耗時(shí)最大，平均每次匹配要消耗65s左右的時(shí)間，而AORB算法相對(duì)ASIFT算法耗時(shí)較短，但每次匹配時(shí)間也約為10s左右，而本文提出的算法平均耗時(shí)1.5s，最快可以達(dá)到0.2s，最慢也只要2s即可完成匹配。

圖14 標(biāo)準(zhǔn)仿射數(shù)據(jù)集特征匹配算法時(shí)間消耗對(duì)比

圖15 地空?qǐng)D像數(shù)據(jù)集的仿射匹配結(jié)果對(duì)比

圖15 和圖16分別是地空?qǐng)D像數(shù)據(jù)集的匹配對(duì)數(shù)以及所耗時(shí)間的對(duì)比。圖15的橫坐標(biāo)表示每一個(gè)地空數(shù)據(jù)，縱坐標(biāo)表示其有效匹配點(diǎn)對(duì)。圖16是相應(yīng)時(shí)間消耗對(duì)比，單位為s。從圖15和圖16中可以看出，在地空?qǐng)D像數(shù)據(jù)集中，本文提出的算法能夠提供比ASIFT、AORB算法更多的匹配對(duì)數(shù)。而且在時(shí)間方面，本文提出的算法較ASIFT算法提高了30倍，相比于AORB算法提高了5倍。

圖16 地空?qǐng)D像數(shù)據(jù)集的仿射匹配時(shí)間消耗對(duì)比

6 結(jié)語(yǔ)

在本論文中，我們針對(duì)無(wú)人機(jī)在城市低空環(huán)境下的地空?qǐng)D像匹配問(wèn)題進(jìn)行了研究，并提出了基于ORB和虛擬視角的快速仿射算法。該算法能夠自適應(yīng)不同的仿射環(huán)境獲得足夠可靠的匹配對(duì)和達(dá)到更快的仿射匹配速度。當(dāng)匹配圖片的視角變化較小時(shí)，本文通過(guò)單應(yīng)性矩陣生成中間圖像來(lái)完成匹配；當(dāng)視角變化較大時(shí)，則是通過(guò)模擬相機(jī)視角選取模擬圖像來(lái)完成匹配。實(shí)驗(yàn)表明，在標(biāo)準(zhǔn)仿射數(shù)據(jù)集下，本文提出的算法不僅能夠生成足夠的可靠的匹配對(duì)，還在速度上達(dá)到了最快0.2s，最慢2s的穩(wěn)定時(shí)間花費(fèi)，該匹配速度超過(guò)了ASIFT約32倍，AORB約5倍。在地面和空中圖像匹配的復(fù)雜環(huán)境下，本文提出的算法能達(dá)到平均1.5s的匹配時(shí)間，不僅在速度上遠(yuǎn)超ASIFT，還生成更多的可靠的匹配對(duì)。

然而，在無(wú)人機(jī)自主定位的過(guò)程中，我們不僅要關(guān)注兩幅圖像之間的匹配結(jié)果，還要努力解決無(wú)人機(jī)在龐大街景地圖數(shù)據(jù)中的圖像檢索以及多幅候選圖像篩選的問(wèn)題。