圖像特征點匹配算法的研究

林　汀

（北京信息科技大學(xué)光電測試技術(shù)北京市重點實驗室，北京100192）

?

圖像特征點匹配算法的研究

林汀

（北京信息科技大學(xué)光電測試技術(shù)北京市重點實驗室，北京100192）

摘要：特征點匹配是計算機視覺領(lǐng)域的一個重要課題，針對ORB算法在特征點匹配基本上沒有尺度不變性，與SURF理論算法相結(jié)合，提出基于算法組合的改進算法SUORB。首先生成多尺度空間，并在多尺度空間里檢測穩(wěn)定的極值點，以便提取出的特征點具有尺度不變信息;然后使用ORB描述符來描述特征點，生成旋轉(zhuǎn)不變性的二進制描述符;最后實現(xiàn)特征點匹配。實驗結(jié)果表明，SUORB有效地解決ORB的缺陷，在圖像尺度變化時，SUORB匹配算法比ORB匹配算法的準(zhǔn)確度明顯提高;同時SUORB和ORB兩種算法的匹配速度很接近。

關(guān)鍵詞：特征點；匹配；尺度空間；組合算法

0　引言

圖像特征點匹配在目標(biāo)跟蹤、圖像拼接、模式識別等領(lǐng)域有著廣泛的應(yīng)用[1-2]。David G．Lowe 2004年提出的SIFT（Scale-Invariant Feature Transform，尺度不變特征變換）特征點匹配算法具備尺度和旋轉(zhuǎn)不變性特性，匹配準(zhǔn)確性較高[3]，但是計算量較大，運算時間較長。針對這一不足之處，SURF（Speeded-Up Robust Features，快速魯棒特征）算法應(yīng)運而生。SURF算法不僅具備SIFT算法在尺度和旋轉(zhuǎn)不變性方面的優(yōu)勢[4]，而且由于其采用盒式濾波器與原圖像卷積的計算方式，比SIFT算法相比，速度有了較大提升。

ORB算法相對于SIFT算法更滿足實時性的要求，該算法比SIFT快上百倍[4]，比SURF快一個數(shù)量級。大多數(shù)國內(nèi)外人士基于ORB算法的優(yōu)勢展開了一系列研究，例如任結(jié)在復(fù)雜環(huán)境中利用ORB的快速性檢測運動目標(biāo)[5]，文獻[6-7]利用隨機采樣一致性方法對ORB進行改進等等。本文針對ORB算法的不足之處，利用SURF和ORB組合生成改進算法，并將其定義為SUORB（Speed-Up ORiented Brief，快速方向描述符）。改進后的組合算法SUORB在匹配速度方面與ORB算法相當(dāng)，而匹配的準(zhǔn)確度與ORB算法相比有很大提高，彌補了ORB算法在圖像尺度發(fā)生變化時的不足。

1 ORB特征點匹配算法

1.1特征點提取

（1）特征點的檢測

FAST檢測特征點:以某像素點為圓心，在其圓形區(qū)域內(nèi)，比較中心點和圓周上各像素點灰度值的差值，通過差值判斷該中心點為特征點[8-10]。

圖1　FAST特征點檢測示意圖

FAST具體計算過程：

由圖1所示，以p點為中心點，比較P點與以P點為圓心3個像素為半徑的鄰域內(nèi)圓周上各像素灰度值的差值，若差值的絕對值大于某個閾值數(shù)εd，記錄圓周上像素點的個數(shù)[11]。角點響應(yīng)函數(shù)N為：

I（p）表示中心像素點的灰度值，I（i）表示該圓形鄰域內(nèi)第i個像素點的灰度值，取N0為閾值，N0定為12[12]。當(dāng)N＞N0時，認(rèn)為p點為角點[13]。

（2）求取特征點質(zhì)心方向

ORB采用角點定向方法——灰度質(zhì)心法來計算特征點方向，求取特征點的質(zhì)心坐標(biāo)，將特征點坐標(biāo)設(shè)為起點，質(zhì)心坐標(biāo)設(shè)為終點，構(gòu)造向量，該向量表示此處特征點的方向，其中特征點質(zhì)心坐標(biāo)由鄰域矩求得[14]。鄰域矩由式（2）定義。

其中，0階矩（M00）為物體的質(zhì)量；（M10，M01）代表1階矩，f（x，y）為灰度值[15]，質(zhì)心坐標(biāo)如式（3）所示。

特征點與質(zhì)心的夾角定義為FAST特征點的方向，由式（4）所示：

1.2特征點的描述

ORB算法利用BRIEF二進制碼串的形式描述特征點，其核心思想是圍繞關(guān)鍵點選擇n個點對，把這n個點對組合起來作為描述子。n可為128，256，512等。這里，假設(shè)n=4，則4個點分別標(biāo)記為：P1（x，y）、P2（x，y）、P3（x，y）、P4（x，y）、點P的τ準(zhǔn)則如式（5）所示。

P點在x方向上的像素灰度值，記為p（x）。對點對進行操作。例如：

則最終的描述子為1011。

BRIEF方法生成的二進制描述子[16]如式（7）所示。

式（7）得到的描述子不具有方向性，通過求取描述子的質(zhì)心方向，來獲得描述子的方向[17-18]。

描述子向量由式（8）所示，式（8）生成了相關(guān)性較大的描述子向量點對，從而加大了匹配難度。解決方法是利用貪婪窮舉思想對測試點對進行約束，減小點對之間的相關(guān)性[19]。貪婪窮舉算法的思路是利用5×5的子窗口內(nèi)像素灰度平均值來代替31×31窗口內(nèi)的所有點對[20]，具體步驟如圖2所示。

圖2　ORB算子獲取描述子流程圖

1.3特征點匹配

由于生成的特征點描述子為二進制碼串形式，因此使用漢明距離對特征點匹配較為簡單。匹配點與非匹配點的漢明距離有著明顯的不同，以此設(shè)定閾值，實現(xiàn)匹配。

2通過算法組合改進ORB

由于ORB算法中基于FAST算子檢測到的特征點不具備尺度不變信息，因而在后續(xù)的特征點匹配中產(chǎn)生一定的誤匹配；而SURF算法在提取特征點時，建立多尺度空間，保證了特征點的尺度不變性特征[22]。因此，本文基于SURF和ORB組合算法組合的思路展開研究，將組合算法定義為SUORB。

2.1尺度空間檢測極值點

要在尺度空間中檢測極值點，首先要建立具有多尺度空間的圖像金字塔；SURF算法利用尺度逐漸遞增的盒式濾波器與原圖像卷積創(chuàng)建圖像金字塔生成多尺度空間，該算法與SIFT算法在建立圖像金字塔的過程有所不同[23-24]。

圖3　SIFT與SURF建立金字塔對比圖

SURF算法將金字塔分為多個組（Octave），每組包含若干層（Level），兩層之間的最小尺度變化量由l0表示；每組中的若干層代表了一系列響應(yīng)圖，響應(yīng)圖是同一輸入圖像與逐漸遞增的模板序列卷積的結(jié)果，盒式濾波的模板尺寸大約為最小尺度變化量的3倍左右[25]；若l0為3，則該盒式濾波模板尺寸為9×9；若l0為5，則該盒式濾波模板尺寸為15×15，若l0為7，則該盒式濾波模板尺寸為21×21；若l0為9，則該盒式濾波模板尺寸為27×27[26]。第二組濾波器的尺寸分別為5×15、27× 27、39×39、51×51，第三組濾波器的尺寸分別為27×27、51×51、75×75、99×99，如圖4所示。

圖4　遞增的盒式濾波器

圖5　濾波器尺寸和尺度關(guān)系示意圖

2.2提取穩(wěn)定的極值點

為了提取穩(wěn)定的特征點，需要在某一尺度下提取極值點，SURF算法采用式（9）來判斷極值點，其中Dxx、Dyy、Dxy分別代表高斯函數(shù)在（x，y）處的二階偏導(dǎo)數(shù)；當(dāng)det（Happrox）的值為正時，可以認(rèn)定該點為極值點[27]。

其中ω為權(quán)重系數(shù)，根據(jù)經(jīng)驗一般取為ω=0.9接著利用非極大值抑制的方法，在3×3×3的立體鄰域中比較26個像素點的灰度值；若某一個像素點的灰度值大于或小于剩余像素點的灰度值，認(rèn)定該點為特征點[28]。

本文基于SURF算法建立圖像金字塔，在尺度空間中檢測極值點，并在不同的尺度下提取極值點，采用非極大值抑制的方法提取特征點；然后，利用1.1.2小節(jié)中介紹的ORB角點定向方法，為特征點定義質(zhì)心方向，最后采用BRIEF二進制碼串的形式對特征點進行描述。

3　實驗結(jié)果分析

本文使用Visual Studio 2010進行編程，計算機系統(tǒng)是Windows7[Intel Core Duo CPU2.20 GHz，2G內(nèi)存]。

3.1尺度不變性對比實驗

為了驗證本文提出的SUORB算法能夠有效彌補ORB算法在尺度不變性方面的不足，采用尺度發(fā)生變化的一組測試圖像進行實驗對比，下圖所示的是盤古圖像的實驗結(jié)果。圖6（a）的匹配效果比較雜亂，原因是ORB算法缺少尺度不變性信息，從而導(dǎo)致誤匹配程度較高。圖6（b）的結(jié)果表明利用本文提出的基于算法組合的SUORB方法，得到了相對理想的效果。

（a）ORB算法匹配效果　?。╞）SUORB算法匹配效果圖6　ORB和SUROB算法匹配效果對比圖

如表1所示，采集了6組實驗數(shù)據(jù)，比較兩種算法的匹配準(zhǔn)確率。

表1　 ORB和SUORB算法的準(zhǔn)確率

由表1可知，當(dāng)圖像尺度發(fā)生變化時，SUORB算法的匹配準(zhǔn)確率（Ransac表示的是消除誤匹配后匹配點個數(shù)與消除誤匹配前匹配點個數(shù)的比值）高于ORB算法。

由圖7可知，SUORB算法的匹配效果要優(yōu)于ORB算法，證明了SUORB算法在尺度不變性方面的優(yōu)勢。

圖7　兩種算法準(zhǔn)確度對比

3.2計算時間對比實驗

為了驗證SUORB算法的實用性，還需要針對各算法的匹配時間作對比實驗。選取上述實驗中10組測試圖像，統(tǒng)計各算法的匹配時間，如表2所示。

表2　 ORB和SUORB算法的匹配時間

由表2可知，當(dāng)ORB算法與SUORB算法的匹配點數(shù)相同時，SUORB平均匹配時間約為1286.9ms，比ORB的匹配時間長約387ms，可認(rèn)為SUORB與ORB的運算速度很相近，表明本文提出的算法SUORB的快速優(yōu)越性。

4　結(jié)語

本文結(jié)合SURF思想對ORB進行改進，提出的SUORB算法有效地解決了ORB不具備尺度不變性的缺陷，同時保留了ORB快速性的優(yōu)點。通過實驗分析得出以下結(jié)論:

（1）在圖像尺度發(fā)生變化時，SUORB可以有效地、準(zhǔn)確地進行特征點匹配，其平均匹配準(zhǔn)確度相比于ORB有顯著提高。

（2）SUORB平均匹配時間與ORB的運算速度很相近，表明了SUORB的快速優(yōu)越性。

參考文獻：

[1]張紅源，陳自力.圖像匹配經(jīng)典算法及其改進方法研究[J].兵工自動化，2008，09:91-94.

[2]趙亮亮.一種基于左右視線的立體圖像匹配算法[J].計算機仿真，2010，03:220-223.

[3]時磊，謝曉方，喬勇軍.基于SURF算法的人臉跟蹤技術(shù)研究[J].計算機仿真，2010，12:227-231.

[4]周軍太，龍永紅.一種改進SURF算法的圖像配準(zhǔn)[J].湖南工業(yè)大學(xué)學(xué)報，2011，02:95-99.

[5]任結(jié)，周余，于耀，都思丹，王自強.基于ORB自然特征的AR實時系統(tǒng)實現(xiàn)[J].計算機應(yīng)用研究，2012，09:3594-3596.

[6]李小紅，謝成明，賈易臻，張國富.基于ORB特征的快速目標(biāo)檢測算法[J].電子測量與儀器學(xué)報，2013，05:455-460.

[7]張云生，鄒崢嶸.基于改進ORB算法的遙感圖像自動配準(zhǔn)方法[J].國土資源遙感，2013，03:20-24.

[8]劉銘.基于ORB算法的雙目視覺測量與跟蹤研究[D].哈爾濱工業(yè)大學(xué)，2014.

[9]謝成明.基于ORB特征的目標(biāo)檢測與跟蹤的研究[D].合肥工業(yè)大學(xué)，2013.

[10]索春寶，楊東清，劉云鵬.多種角度比較SIFT、SURF、BRISK、ORB、FREAK算法[J].北京測繪，2014，04:23-26+22.

[11]張萬華.基于區(qū)域SURF的圖像匹配算法研究[D].華東理工大學(xué)，2011.

[12]石雅筍.改進的SURF圖像配準(zhǔn)算法研究[D].電子科技大學(xué)，2011.

[13]陳藝蝦，孫權(quán)森，徐煥宇，耿蕾蕾. SURF算法和RANSAC算法相結(jié)合的遙感圖像匹配方法[J].計算機科學(xué)與探索，2012，09:822-828.

[14]國飛飛.基于SURF算法的多幅圖像三維模型重建方法研究[D].北京理工大學(xué)，2011.

[15]馮嘉. SIFT算法的研究和改進[D].吉林大學(xué)，2010.

[16]汪淑夢.基于改進的SIFT算法的圖像配準(zhǔn)技術(shù)的研究與實現(xiàn)[D].中國地質(zhì)大學(xué)（北京），2013.

[17]李耀云.基于SIFT算法的雙目立體視覺定位研究[D].太原理工大學(xué)，2013.

[18]張寧麗，馬燕，李順寶，徐衍魯，程瑋. FKPCA-SIFT算法在圖像匹配中的應(yīng)用[J].電視技術(shù)，2015，07:21-24+42.

[19]傅衛(wèi)平，秦川，劉佳，楊世強，王雯.基于SIFT算法的圖像目標(biāo)匹配與定位[J].儀器儀表學(xué)報，2011，01:163-169.

[20]丁尤蓉，王敬東，邱玉嬌，俞海波.基于自適應(yīng)閾值的FAST特征點提取算法[J].指揮控制與仿真，2013，02:47-53.

[21]薛金龍.基于角點的圖像特征提取與匹配算法研究[D].大連理工大學(xué)，2014.

[22]Roberts L G, Machine Perception Of Three-Dimensional Solids [C]. In Optical and Electroptical Information Processing, Cambridge: MIT Press, 1965:159-197

[23]Aloimonos J, Weiss I,Bandopadhay A. Active Vision [J]. International Journal Of Computer Vision,1988,1（4）:333-356.

[24]ZHANG WeiLong,LIU LeiBo,YIN ShouYi,ZHOU RenYan,CAI ShanShan,WEI ShaoJun. An Efficient VLSI Architecture Of Speeded-Up Robust Feature Extraction For High Resolution And High Frame Rate Video[J]. Science China（Information Sciences）,2013,07:136-149.

[25]QIN Yue-ming, CAO Zhi-guo,Wen Zhuo, YU Zheng-hong. Robust Key Point Descriptor For Multi-Spectral Image Matching[J]. Journal of Systems Engineering and Electronics,2014,04:681-687.

Research on Feature Points Matching Algorithm of Sequence Image

LIN Ting
（Key Laboratory of Optoelectronic Measurement Technology，Beijing Information Science & Technology University，Beijing 100192）

Abstract：Feature point matching is an important subject in computer vision field, for the lack of scale invariance characteristics of ORB algorithm, proposes an improved method based on the combination of SURF and ORB, which name is SUORB. Firstly，builds the scale spaces，in which the stable extreme points are detected in order to get the feature points with scale invariance information. Then, describes the feature points by the ORB descriptors with rotation invariance. Finally, Hamming distance is used to finish the final matching task. The experimental results show that SUORB has solved the deficiencies that ORB has little scale invariance. SUORB improves the matching accuracy, compared to ORB when images have scale changes. At the same time，the matching speeds of SUORB and ORB are almost the same.

Keywords：Feature Points; Matching; Multi Scale Space; the Combination of Algorithms

收稿日期：2016-01-12修稿日期：2016-02-26

作者簡介：林?。?990-），男，北京人，碩士研究生，研究方向為機器視覺

文章編號：1007-1423（2016）10-0028-05

DOI：10.3969/j.issn.1007-1423.2016.10.007

基金項目：國家自然科學(xué)基金項目（No.51475047）、教育部“長江學(xué)者與創(chuàng)新團隊”發(fā)展計劃資助項目（No.IRT1212）、北京市屬高等學(xué)校創(chuàng)新團隊建設(shè)提升計劃項目（No.IDHT20130518）