結(jié)合SURF算法和單應(yīng)性矩陣的無人機(jī)影像匹配

王曉紅，鄧仕雄，何志偉，曹留霞，閆星光

(1. 貴州大學(xué)林學(xué)院，貴州 貴陽 550025； 2. 貴州大學(xué)礦業(yè)學(xué)院，貴州 貴陽 550025)

無人機(jī)(UAV)是一種動力驅(qū)動、無人駕駛、可重復(fù)使用的航空器的簡稱[1]，具有機(jī)動、靈活、高效、低成本等特點(diǎn)，在國土、水利、農(nóng)業(yè)、林業(yè)、城市規(guī)劃等行業(yè)中起到不可估量的作用。與航天遙感影像及傳統(tǒng)航空遙感影像相比，無人機(jī)影像數(shù)據(jù)獲取簡單、空間分辨率高、信息量大，但影像的重疊度高、覆蓋區(qū)域范圍小，單張影像往往難以覆蓋目標(biāo)區(qū)域，因此影像鑲嵌是無人機(jī)影像處理的前期重要工作。而配準(zhǔn)與融合是無人機(jī)影像拼接的前提，匹配的效果對后續(xù)的影像處理具有較大的影響，因此提高特征匹配數(shù)及匹配效果很有必要。

圖像匹配的本質(zhì)是在不同的圖像上通過算法實(shí)現(xiàn)同名點(diǎn)的提取，其中基于圖像局部特征的匹配較為常見。David Lowe[2-3]在1999年提出了尺度不變特征轉(zhuǎn)換(SIFT)算法，之后對該算法進(jìn)行了優(yōu)化。SIFT算法對旋轉(zhuǎn)、尺度、光照等具有較好的不變性，但SIFT時(shí)間、算法復(fù)雜度較高，很難達(dá)到實(shí)時(shí)匹配。2006年Herbert Bay等[4]提出了加速特征提取算法(speed up robust features,SURF)，該算法是在SIFT算法的基礎(chǔ)上改進(jìn)而來，是對高斯差分的簡化，引入積分圖像的概念，將卷積運(yùn)算轉(zhuǎn)化為幾個簡單的加減運(yùn)算，降低了算法維度，在加快了程序運(yùn)行速度的同時(shí)具有更好的穩(wěn)健性。國內(nèi)外基于SIFT、SURF算法的改進(jìn)也有大量研究，文獻(xiàn)[5—6]通過降維較大程度上減小了算法的時(shí)間復(fù)雜度，提高了實(shí)現(xiàn)效率。楊亮等在克服傳統(tǒng)特征匹配算法噪聲及圖像灰度非線性變換的不足中，通過梯度直方圖構(gòu)造描述符并通過降維來降低時(shí)間復(fù)雜度[7]。馮亦東等基于傳統(tǒng)圖像特征信息量少且匹配低的情況，利用SURF算法結(jié)合FLANN搜索圖像獲得了較好的匹配效果[8]。文獻(xiàn)[9]通過改進(jìn)RANSAC算法利用特征點(diǎn)計(jì)算出基礎(chǔ)矩陣，使匹配效果得到明顯提高。同時(shí)部分學(xué)者將SIFT、SURF算法引用或改進(jìn)后應(yīng)用到圖像的拼接中[10-12]。基于上述研究，常規(guī)算法在無人機(jī)遙感影像匹配方面較少，且特征匹配約束條件單一，由于影像局部區(qū)域往往只能獲取少量或無法獲取特征點(diǎn)，這就造成影像的局部區(qū)域匹配十分困難。本文基于SURF算法對無人機(jī)影像進(jìn)行特征提取，在快速近視最近鄰查找(FLANN)快速搜索算法基礎(chǔ)上，結(jié)合K最近鄰(KNN)[13]篩選掉更多誤匹配點(diǎn)，使用單應(yīng)性矩陣的隨機(jī)抽樣一致性(RANSAC)[14]算法的多重約束得到更好的匹配效果，獲得更優(yōu)的匹配集。

1 影像匹配關(guān)鍵技術(shù)

1.1 SURF算法匹配原理及過程

(1) SURF是對積分圖像進(jìn)行操作，采用盒子濾波器計(jì)算每個像素點(diǎn)的Hessian矩陣行列式，僅需要幾次加減運(yùn)算且運(yùn)算量與盒子濾波器大小無關(guān)，因此能夠快速地構(gòu)成SURF不同尺度的金字塔。積分圖像每個像元的值是原圖像對應(yīng)位置所有左上角元素之和，計(jì)算公式如下

(1)

(2) SURF算法采用對高斯差分近似進(jìn)行特征點(diǎn)檢測，連續(xù)函數(shù)f(x,y)的二階微分Hessian矩陣

(2)

同時(shí)利用式(3)的值來判斷點(diǎn)是否為極值點(diǎn)，在非連續(xù)空間上，為了求得矩陣4個元素，因高斯核可以構(gòu)造出不同的尺度響應(yīng)圖像，SURF算法采用二階標(biāo)準(zhǔn)高斯核函數(shù)對圖像卷積，在尺度σ下對應(yīng)的點(diǎn)(x,y)處對應(yīng)的Hessian矩陣采用式(4)計(jì)算，其行列式的局部最大值可以確定特征點(diǎn)的位置及尺度[15]。

(3)

(4)

式中，Lxx是標(biāo)準(zhǔn)高斯函數(shù)G(x,y,σ)的二階偏導(dǎo)與圖像在點(diǎn)(x,y)處卷積后的結(jié)果

(5)

同理可得Lxy、Lyy，即可求出Hessian矩陣的值，由于是對原矩陣的近似，因此在計(jì)算盒子濾波響應(yīng)時(shí)，需要對模板盒子進(jìn)行歸一化處理。

(3) 構(gòu)建尺度空間在尺度域及空間域找到極值點(diǎn)，SURF算法采用原圖像，大小不變，通過變化模板大小對原圖像進(jìn)行濾波，從而構(gòu)建出尺度金字塔，把響應(yīng)圖像分成多組，每組由多層組成，各組采用逐漸增大的濾波器尺寸進(jìn)行處理，其中相鄰層間的尺度比例由高斯二階微分模板決定，一般濾波器尺寸如下

FilterSize=3(2octave×interval+1)

(6)

式中，octave表示影像所在組；interval表示影像所在層。將每個像素在相鄰尺度域及空間鄰域內(nèi)的像素作出比較，如果是極大值或極小值，則將其保留作為候選特征點(diǎn)，同時(shí)排除響應(yīng)值小于Hessian矩陣行列式閾值的特征點(diǎn)。

1.2 基于多重約束條件的影像特征匹配

特征匹配一般以歐氏距離為度量，選擇固定閾值、最近鄰或最近鄰距離比率(NNDR)為匹配策略，簡單的約束條件一般難以達(dá)到滿意的效果。針對影像的復(fù)雜情況，本文采用多重約束條件使特征點(diǎn)搜索范圍更加精確。

1.2.1 同名點(diǎn)極線解算

極線約束是一種點(diǎn)對直線的約束而非點(diǎn)對點(diǎn)，它將對應(yīng)點(diǎn)匹配從整幅圖尋找轉(zhuǎn)為在一條直線上尋找對應(yīng)的點(diǎn)。三維空間中一點(diǎn)P(X,Y,Z)，投影到兩個不同的平面L1、L2，投影點(diǎn)分別為PL、PR，3個點(diǎn)在三維空間內(nèi)構(gòu)成一個平面S，平面S與面L1的交線過PL點(diǎn)，稱之為對應(yīng)于PR的極線。同理S與L2的交線對應(yīng)PL的極線，即對應(yīng)于左邊圖像點(diǎn)的極線在右邊圖像上，右邊圖像點(diǎn)的極線與之相反，如圖1所示。

圖1 極線約束原理

由極線原理圖可以看出，極線約束就是同一個點(diǎn)在兩幅圖上的映射，已知左圖映射點(diǎn)PL,則右圖映射點(diǎn)PR一定在相對于PL的極線上，這樣可以減少影像待匹配的點(diǎn)數(shù)量。基礎(chǔ)矩陣F將點(diǎn)PL映射到另一個視角中的極線上，假如三維向量x、x′存放相關(guān)點(diǎn)，F(xiàn)為一個3階且秩為2的基礎(chǔ)矩陣，則滿足

x′TFx=0

(7)

1.2.2 基礎(chǔ)矩陣和單應(yīng)性矩陣的解算

在約束匹配的過程中，使用基礎(chǔ)矩陣或單應(yīng)性矩陣的RANSAC算法去除誤匹配點(diǎn)對，基本矩陣是秩為2、自由度為7的3×3矩陣。其中

Fe=0
FTe′=0

(8)

假設(shè)兩幅圖之間是透視變換，則單應(yīng)性矩陣(即透視變換矩陣)每次需要4對匹配點(diǎn)來計(jì)算H，然后選出內(nèi)點(diǎn)個數(shù)最多作為最后的結(jié)果，其計(jì)算距離方法如下

(9)

矩陣F和H的關(guān)系如式(10)所示，但通常由于極線約束估計(jì)不準(zhǔn)確使得兩矩陣的估計(jì)存在偏差，使得二者之和不等于零，可以設(shè)定閾值來判定矩陣是否準(zhǔn)確。

HTF+FTH=0

(10)

1.2.3RANSAC精匹配

采用RANSAC算法在一組包含“外點(diǎn)”的數(shù)據(jù)集中不斷迭代尋找最優(yōu)參數(shù)模型，其實(shí)質(zhì)是尋找一個最佳單應(yīng)性矩陣H，矩陣大小為3×3，找到最優(yōu)參數(shù)矩陣時(shí)滿足矩陣的特征點(diǎn)最多，由于矩陣H有8個未知參數(shù)，因此需要至少包含4組匹配點(diǎn)對

(11)

式中，(x,y)表示目標(biāo)圖像角點(diǎn)位置；(x′,y′)為場景圖像角點(diǎn)位置；s為尺度參數(shù)。該算法隨機(jī)從匹配數(shù)據(jù)集中抽取4對點(diǎn)并要求相互之間不共線，計(jì)算出單應(yīng)性矩陣H，利用該模型去檢測所有數(shù)據(jù)，如果該模型最優(yōu)，則應(yīng)滿足該模型的點(diǎn)個數(shù)與投影誤差(即代價(jià)函數(shù))最小

(12)

RANSAC參數(shù)估計(jì)內(nèi)涵：給定N個數(shù)據(jù)點(diǎn)組成集合W，假設(shè)集合W中大多數(shù)點(diǎn)可以通過模型產(chǎn)生，且最少通過n個點(diǎn)(n

2 試驗(yàn)過程及分析

本文基于SURF算法，首先進(jìn)行無人機(jī)影像特征點(diǎn)提取，引入多重特征約束條件控制約束力度，逐步過濾掉錯誤匹配的特征點(diǎn)使匹配效果更佳。利用3種算法對分辨率為380×380、400×300的兩組數(shù)據(jù)(山地)進(jìn)行前2次試驗(yàn)之后改進(jìn)算法實(shí)現(xiàn)試驗(yàn)3，并分析匹配效果、運(yùn)行時(shí)間及匹配精度。本次試驗(yàn)運(yùn)行環(huán)境為Inter(R) Xeon(R) CPU E5-1607 0@3.00 GHz，運(yùn)行內(nèi)存為8 GB的工作站。基于VS2013的OpenCV2.4.10圖像處理視覺庫，Windows 7系統(tǒng)作為開發(fā)平臺，無人機(jī)影像部分參數(shù)見表1。試驗(yàn)數(shù)據(jù)如圖2所示，可以看出影像對1左右影像變形較大,影像對2地形起伏大。圖3為兩組影像對的特征點(diǎn)檢測，其中影像對1特征點(diǎn)數(shù)為877、936，影像對1特征檢測數(shù)為490、313。

表1 無人機(jī)影像部分參數(shù)

2.1 算例過程

2.1.1 基于FLANN快速搜索的SURF算法匹配

試驗(yàn)1：基于SURF算法結(jié)合FLANN快速搜索的特征匹配。圖4為兩組影像對匹配結(jié)果，其中影像對1匹配數(shù)為187，耗時(shí)1 844.76 ms，影像對2匹配數(shù)為59，耗時(shí)970.722 ms。

圖2 影像對

圖3 兩組影像對SURF特征點(diǎn)檢測

圖4 影像對SURF+FLANN匹配效果

2.1.2 基于SURF算法和基礎(chǔ)矩陣的約束匹配

試驗(yàn)2：基于基礎(chǔ)矩陣的極線約束特征匹配，并用RANSAC方法計(jì)算出基本矩陣，在挖掘更多特征點(diǎn)的同時(shí)通過極線約束篩選掉錯誤特征點(diǎn)，使得內(nèi)點(diǎn)更純凈。該算法實(shí)現(xiàn)影像對1耗時(shí)2 472.21 ms,特征匹配對494，影像對2耗時(shí)1 274.34 ms,特征匹配對212，匹配效果如圖5所示。從圖中可以看出引入極線約束的特征匹配在增加特征點(diǎn)的同時(shí)提高了匹配量，匹配效果得到明顯提高，同時(shí)圖中存在少量的誤匹配。

圖5 兩組影像SURF+FLANN+基礎(chǔ)矩陣匹配效果

2.1.3 基于SURF算法的單應(yīng)性矩陣映射匹配

試驗(yàn)3：使用單應(yīng)性矩陣的方法去除誤匹配點(diǎn)對更加嚴(yán)格，得到的結(jié)果更加精確，試驗(yàn)基于SURF算法，結(jié)合FLANN快速搜索并用KNN算法篩選匹配點(diǎn)，使用單應(yīng)性矩陣的RANSAC算法去除誤匹配點(diǎn)后，得到了更好的匹配效果，如圖6所示，匹配更精確。改進(jìn)后的算法影像對1耗時(shí)2 307.7 ms，匹配上470對，影像對2耗時(shí)1 344.13 ms，匹配上194對。

圖6 改進(jìn)后兩組影像匹配效果

2.2 試驗(yàn)結(jié)果分析

試驗(yàn)首先基于SURF算法對兩組無人機(jī)影像進(jìn)行關(guān)鍵點(diǎn)檢測，結(jié)合FLANN快速搜索算法做出匹配，匹配效果較好，但特征點(diǎn)較少。通過改進(jìn)算法在FLANN基礎(chǔ)上結(jié)合KNN篩選掉更多誤匹配點(diǎn)，使用單應(yīng)性矩陣的RANSAC算法得到更好的匹配效果。3組試驗(yàn)在兩組數(shù)據(jù)中匹配對數(shù)、耗時(shí)及正確率見表2。

表2 兩組影像匹配對、耗時(shí)及正確率

從表中可以看出引入極線約束的匹配數(shù)是基于SURF和FLANN算法的匹配量的約3～5倍，但極線約束后的匹配同時(shí)還存在少量的極線交叉導(dǎo)致匹配錯誤。3組試驗(yàn)匹配率相差不大，影像對1匹配率分別為89.8%、93.1%、95.1%，影像對2匹配率分別為88.1%、90.1%、93.8%，但兩組影像在試驗(yàn)1中能夠匹配到的特征點(diǎn)太少，因此利用該算法一般難以滿足影像間的匹配，特別是地形起伏較大區(qū)域，如影像對2在試驗(yàn)1中局部區(qū)域甚至沒有特征點(diǎn)。由于單應(yīng)性矩陣比基礎(chǔ)矩陣更嚴(yán)格，造成匹配量上基礎(chǔ)矩陣稍低，但精度要比基于基礎(chǔ)矩陣的特征匹配高。在耗時(shí)上，由于試驗(yàn)1算法復(fù)雜度相對后兩種算法要低，考慮的參數(shù)要少，因此兩組影像在試驗(yàn)1中速度較快，而試驗(yàn)2、試驗(yàn)3兩種算法時(shí)間復(fù)雜度相差不大，改進(jìn)后的算法相對于前兩個試驗(yàn)在耗時(shí)得到控制的同時(shí)而獲取了更多精度較高的匹配集。

3 結(jié) 語

本文針對無人機(jī)影像受拍攝條件影響或區(qū)域環(huán)境復(fù)雜造成的匹配效果不佳，局部區(qū)域沒有特征點(diǎn)造成的匹配難度大，為了避免傳統(tǒng)約束條件單一的不足而在SURF算法的基礎(chǔ)上基于FLANN快速搜索結(jié)合KNN算法并引入單應(yīng)性矩陣，同時(shí)與基于基礎(chǔ)矩陣的極線約束條件及常規(guī)的算法作了對比。試驗(yàn)證明，基于多重約束條件的特征匹配獲得了較好的匹配效果，在獲取大量特征點(diǎn)的同時(shí)獲得了更多優(yōu)質(zhì)匹配集，該算法適合無人機(jī)影像的匹配。