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

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

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

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

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

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

1.1 SURF算法匹配原理及過程

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

(1)

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

(2)

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

(3)

(4)

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

(5)

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

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

FilterSize=3(2octave×interval+1)

(6)

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

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

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

1.2.1 同名點極線解算

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

圖1 極線約束原理

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

x′TFx=0

(7)

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

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

Fe=0
FTe′=0

(8)

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

(9)

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

HTF+FTH=0

(10)

1.2.3RANSAC精匹配

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

(11)

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

(12)

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

2 試驗過程及分析

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

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

2.1 算例過程

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

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

圖2 影像對

圖3 兩組影像對SURF特征點檢測

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

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

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

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

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

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

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

2.2 試驗結(jié)果分析

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

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

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

3 結(jié) 語

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