汪 豪
(東華理工大學(xué)測繪工程學(xué)院,江西南昌 330013)
?
基于特征點(diǎn)的航測影像匹配算法研究
汪 豪
(東華理工大學(xué)測繪工程學(xué)院,江西南昌 330013)
在影像匹配算法中,快速有效的匹配算法是航空攝影測量的關(guān)鍵。基于特征點(diǎn)提取的影像匹配算法具有精度高、適用性廣的特點(diǎn),已經(jīng)逐漸成為影像匹配研究的主流。該研究分別在測試影像及航空影像中對(duì)FAST、Harris、SURF 3種快速的經(jīng)典特征點(diǎn)匹配算法進(jìn)行分析比較,探討各自的優(yōu)缺點(diǎn),為不同應(yīng)用情況中特征點(diǎn)匹配方法的選取提供借鑒。
影像匹配;特征點(diǎn)提取;航空影像;特征點(diǎn)匹配
影像匹配是通過一定的匹配算法對(duì)兩幅或多幅影像之間識(shí)別同名點(diǎn)的過程[1]。快速、有效、高精度的影像匹配算法可以為航空攝影測量提供重要的技術(shù)支持與保障。由于航空影像成像的自然場景比較復(fù)雜,并且容易受成像條件和環(huán)境誤差的影響,所以影像之間就存在著多種多樣的成像畸變,這就使得影像匹配始終是一個(gè)值得研究的課題。基于特征點(diǎn)的影像匹配定位精確,且匹配后的特征點(diǎn)坐標(biāo)可以直接用來計(jì)算影像之間的空間變換關(guān)系等優(yōu)點(diǎn),受到了眾多學(xué)者的關(guān)注和研究,并逐漸在實(shí)際工作中得到了廣泛應(yīng)用。筆者介紹了FAST[2]、Harris[3]、SURF[4]3種快速有效的特征點(diǎn)提取算法的原理,并且對(duì)它們匹配算法的提取速度、魯棒性及穩(wěn)定性進(jìn)行分析比較。
1.1 FAST算法FAST算法是于2006年由Edward Rosten 和 Tom Drummond提出的一種借鑒于SUSAN算法[5]的特征點(diǎn)提取算法。應(yīng)用到灰度圖像中,即判別有足夠多的像素點(diǎn)的灰度值小于該中心點(diǎn)的灰度值。如圖1所示,選取任意像素點(diǎn)p,將其像素值設(shè)為Ip,接著設(shè)定一個(gè)合適的閾值t,以其像素點(diǎn)為中心,半徑等于3的離散化的Bresenham圓周圍的16個(gè)像素點(diǎn)。在這16個(gè)像素組成的圓上有n個(gè)連續(xù)的像素點(diǎn),若它們的像素值比Ip+t大,或Ip-t小,則該點(diǎn)為一個(gè)角點(diǎn)。Edward Rosten等在實(shí)驗(yàn)給出的n參考值取12。
圖1 FAST角點(diǎn)提取示例
1.2 Harris算法Harris算法是于1988年由Chris Harris和Mike Stephens以Moravec算法[6]為基礎(chǔ)拓展出的一種特征點(diǎn)提取算法。以目標(biāo)像素點(diǎn)(x,y)為中心的二維高斯函數(shù)窗口,向任意方向移動(dòng)(u,v)后計(jì)算像素灰度變化,其表達(dá)式如下:
E(u,v)=∑x,yG(x,y)[I(x+u,y+v)-I(x,y)]2
(1)
由泰勒公式得到公式(2):
(2)
式中,Ix、Iy為x、y的方向梯度。
矩陣M是目標(biāo)像素點(diǎn)的自相關(guān)矩陣,它的2個(gè)特征值分別為λ1和λ2,這2個(gè)特征值與矩陣M的主曲率成正比。當(dāng)2個(gè)特征值均較小時(shí),表明目標(biāo)點(diǎn)附近區(qū)域?yàn)槠教箙^(qū)域;特征值一大一小時(shí),表明特征點(diǎn)位于邊緣上;只有當(dāng)2個(gè)特征值均比較大時(shí),沿任意方向的移動(dòng)均將導(dǎo)致灰度的劇烈變化。由此而得到Harris的角點(diǎn)響應(yīng)函數(shù)R:
R=det(M)-k[trace(m)]2
(3)
式中,det(M)=λ1λ2表示矩陣M的行列式;trace(M)=λ1+λ2表示矩陣的跡;k的取值范圍是0.04~0.06。當(dāng)目標(biāo)像素點(diǎn)的R值大于給定的閾值時(shí),該點(diǎn)像素點(diǎn)即可認(rèn)為是角點(diǎn)。實(shí)驗(yàn)中,系數(shù)k的經(jīng)驗(yàn)值一般取0.04,R值越大,表明該點(diǎn)越是角點(diǎn)。R值的大小與相應(yīng)的點(diǎn)的特征的關(guān)系如圖2。
圖2 Harris角點(diǎn)響應(yīng)準(zhǔn)則
1.3 SURF算法SURF算法是于2006年由Herbert Bay首次發(fā)表于ECCV,2008年正式發(fā)表在《Computer Vision and Image Understanding》,該算法是SIFT算法[7-8]的加速版。在圖像處理中,尺度空間被通常被表述為一個(gè)圖像金字塔,向下降采樣一般用高斯金字塔。SIFT算法中用差分高斯金字塔DOG代替高斯金字塔LOG來提高算法性能,SURF算法中則是使用方框?yàn)V波近似代替高斯濾波,然后使用積分圖像加速卷積,提高運(yùn)算速度,以較小的精度損失獲得更快的特征點(diǎn)檢測速度。
Hessian矩陣是SURF算法的核心,首先圖中某個(gè)像素點(diǎn)p(x,y)的Hessian矩陣為:
(4)
經(jīng)過高斯濾波后獲得與尺度無關(guān)的Hessian矩陣為:
(5)
以方框?yàn)V波近似代替高斯二階導(dǎo)數(shù)用積分圖像加速卷積后的近似表達(dá)式為:
detH=Dxx×Dyy-(0.9×Dxy)2
(6)
式中,Dxx、Dxy、Dyy是圖像中p點(diǎn)與方向?yàn)V波的卷積,0.9是作者給的一個(gè)經(jīng)驗(yàn)值。通過該方法為圖像中每個(gè)像素計(jì)算出其H行列式的決定值,并用這個(gè)值來判別特征點(diǎn)。
通過非極大抑制,對(duì)尺度空間中的每一個(gè)像素(每一階的首尾層除外),與該像素相鄰空間范圍內(nèi)進(jìn)行比較(即8個(gè)像素以及它相鄰尺度上、下層的9個(gè)相鄰像素點(diǎn),共26個(gè)),得到局部極大值和極小值點(diǎn)獲得特征點(diǎn)。然后進(jìn)行曲面擬合,獲得特征點(diǎn)的坐標(biāo)(x,y)以及尺度σ,便可以根據(jù)鄰域信息確定興趣點(diǎn)的主方向以及特征向量。
以每一個(gè)特征點(diǎn)為圓心,在6σ為半徑的圓形區(qū)域,統(tǒng)算x和y方向的上的小波響應(yīng),并以特征點(diǎn)為中心對(duì)這些響應(yīng)用高斯函數(shù)進(jìn)行加權(quán)處理。然后通過一個(gè)大小為π/3的扇形區(qū)域的滑動(dòng)窗口計(jì)算窗口內(nèi)x和y方向的響應(yīng)求和,轉(zhuǎn)動(dòng)搜尋整個(gè)圓形區(qū)域,取長度最長的矢量方向作為該特征點(diǎn)的主方向。
接著以一個(gè)特征點(diǎn)為中心,首先將坐標(biāo)軸旋轉(zhuǎn)到主方向,選取邊長為20σ正方形區(qū)域,將該區(qū)域劃分成4×4的子區(qū)域,對(duì)每個(gè)子區(qū)域內(nèi),計(jì)算25個(gè)空間像素點(diǎn)的小波響應(yīng),以特征點(diǎn)為中心進(jìn)行高斯函數(shù)加權(quán)處理,以加強(qiáng)魯棒性,統(tǒng)計(jì)每一個(gè)子區(qū)域的x、y方向上的Haar小波響應(yīng)dx、dy的和∑dx、∑dy,及其絕對(duì)值的和∑|dx|、∑|dy|。因此,在每一個(gè)子區(qū)域內(nèi)有一個(gè)4維向量V4=(dx,dy,∑dx,∑dy),則每個(gè)特征點(diǎn)區(qū)域有4×4×4=64維的特征描述向量,對(duì)其歸一化從而獲得具有旋轉(zhuǎn)、尺度和光照不變性的特征向量。
為了能更加客觀的比較出3種算法的性能,該研究進(jìn)行了測試圖檢測實(shí)驗(yàn)及實(shí)景圖匹配實(shí)驗(yàn),測試圖為分別進(jìn)行旋轉(zhuǎn)、平移、噪點(diǎn)、亮度變化的積木圖,實(shí)景圖匹配方法為最鄰近距離比值法。
該實(shí)驗(yàn)仿真環(huán)境為MATLAB2012b+OpenCV編程運(yùn)行,計(jì)算機(jī)配置為Intel Core i5-3230M 2.60GHz,4.00 GB RAM。操作系統(tǒng)為Microsoft Windows7專業(yè)版。
積木測試圖檢測實(shí)驗(yàn)結(jié)果見表1。
表1 積木圖檢測實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果
從表1可以看出,在特征點(diǎn)檢測中,F(xiàn)AST算法正如其名,檢測速度遠(yuǎn)超另外兩種算法,然而其受噪點(diǎn)影響明顯,抗旋轉(zhuǎn)性不強(qiáng);Harris算法在測試實(shí)驗(yàn)表現(xiàn)的中規(guī)中矩,在實(shí)驗(yàn)圖像上可以明顯看出特征點(diǎn)基本在各角點(diǎn)處;SURF算法的各項(xiàng)測試的穩(wěn)定性最強(qiáng),有著較強(qiáng)的旋轉(zhuǎn)不變,魯棒性強(qiáng)的特點(diǎn)。由于SURF算法的實(shí)現(xiàn)借助了OpenCV的運(yùn)行庫,可能會(huì)對(duì)其運(yùn)算處理上有一定的提速,在該組實(shí)驗(yàn)中僅供參考。
實(shí)景圖匹配實(shí)驗(yàn)使用的是九江城郊地區(qū)航空影像圖,航向重疊度60%,旁向重疊30%,航拍高度800 m,影像格式為jpeg,分辨率為3 744×5 616。實(shí)驗(yàn)結(jié)果見表2,圖3~5分別為FAST、Harris、SURF特征點(diǎn)匹配示意圖。
表2 實(shí)景圖測試實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果
通過實(shí)景圖測試實(shí)驗(yàn)可以看出,在實(shí)際航空影像中,F(xiàn)AST匹配時(shí)間為5.566 s,處理速度極快,比Harris算法和SURF算法要快很多倍,正確率為93.9%,魯棒性能一般,容易對(duì)相鄰的多個(gè)特征點(diǎn)進(jìn)行重復(fù)檢測,導(dǎo)致特征點(diǎn)局部密集,正確率相對(duì)較低。Harris算法所提取特征點(diǎn)的角點(diǎn)信息較為明顯,匹配時(shí)間為12.085 s,匹配速度一般,匹配正確率為94.4%,略微高于FAST算法。SURF算法匹配率為96.1%,有著最佳的匹配效果,可獲得大量特征點(diǎn),但其在匹配速度上有著明顯的劣勢(shì),匹配時(shí)間為21.651 s。
由于在航空攝影測量中,航空影像有著既定的技術(shù)質(zhì)量控制,圖像效果較為理想,弱化了FAST算法在圖像旋轉(zhuǎn),抗噪性較差的不足,當(dāng)需要實(shí)時(shí)高速,且匹配精度要求不苛刻的工作任務(wù)時(shí),是一個(gè)不錯(cuò)的選擇。Harris算法各項(xiàng)性能較為均衡,適合對(duì)有明顯角點(diǎn)信息的圖像匹配進(jìn)行處理。SURF雖然在匹配速度上并不理想,但各項(xiàng)性能都較為優(yōu)秀,有著較高的精度保障,當(dāng)工作任務(wù)對(duì)時(shí)間要求不高時(shí)建議使用該算法,以獲得最佳的匹配效果。
圖3 FAST匹配示意
圖4 Harris匹配示意
圖5 SURF匹配示意
該研究為了客觀評(píng)價(jià)出各匹配算法的性能,并未對(duì)匹配最佳效果的處理方案進(jìn)行選擇。在實(shí)際工作中,為了提高匹配工作的準(zhǔn)確度,在影像匹配前使用合適的影像處理方法,在特征點(diǎn)提取后使用選擇性能優(yōu)秀的匹配搜索方法,以及影像匹配后的誤差剔除方法,都是值得進(jìn)一步研究的方向。
[1] 張祖勛,張劍清. 數(shù)字?jǐn)z影測量學(xué)[M].武漢: 武漢大學(xué)出版社,1997.
[2] ROSTEN E, DRUMMOND T. Machine learning for high speed corner detection[J].Lecture Notes in Computer Science, 2006, 3951:430-443.
[3] HARRIS C, STEPHENS M. A Combined Comer and Edge Detector[C]//Proceedings of the 4th A levy Vision Conference.[s.n.], 1988: 147-151.
[4] BAY H, TUYTELAARS T, VAN GOOL L. SURF: speeded up robust feature[J]. Comput Vision Im Understanding, 2008, 110(3):346-359.
[5] SMITH S M, BRADY J M. SUSAN-A New Approach to Low Level Image Processing[J]. International Journal of Computer Vision, 1997, 23(1): 45-78.
[6] MORAVEC H P. Towards automatic visual obstacle avoidance[C]//Proceedings of International Joint Conference on Artificial Intelligence. Cambridge, MA, USA:[s.n.], 1977:584-590.
[7] LOWE D G. Object recognition from local scale-invariant features[C]//International Conference on Computer Vision.Corfu, Greece,1999:1150-1157.
[8] LOWE D G. Distinctive image features from scale-invariant key points[J]. International Journal of Computer Vision, 2004, 60(2):91-110.
The Research of Aerial Photography Matching Algorithm Based on Feature Points
WANG Hao
(Faculty of Geomatics,East China Institute of Technology, Nanchang, Jiangxi 330013)
In the image matching algorithm, fast and efficient matching algorithm is the key toaerial survey. The image matching algorithm based on feature point extraction has the characteristics of high precision, wide applicability, and becoming a mainstream in the research of image matching. Three kinds of rapid, classic feature point matching algorithms, including FAST, Harris, SURF in test image and aerial photography were compared and analyzed, the advantages and disadvantages were discussed, which can provide reference for selection of feature point matching method in various situation.
Image matching; Feature point extraction; Aerial photography; Feature points matching
汪豪(1988-),男,福建廈門人,碩士研究生,研究方向:地圖學(xué)與地理信息系統(tǒng)。
2014-12-18
S 126
A
0517-6611(2015)04-360-03