林　汀

（北京信息科技大學(xué)光電測(cè)試技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京100192）

?

圖像特征點(diǎn)匹配算法的研究

林汀

（北京信息科技大學(xué)光電測(cè)試技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京100192）

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

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

0　引言

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

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

1 ORB特征點(diǎn)匹配算法

1.1特征點(diǎn)提取

（1）特征點(diǎn)的檢測(cè)

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

圖1　FAST特征點(diǎn)檢測(cè)示意圖

FAST具體計(jì)算過程：

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

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

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

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

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

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

1.2特征點(diǎn)的描述

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

P點(diǎn)在x方向上的像素灰度值，記為p（x）。對(duì)點(diǎn)對(duì)進(jìn)行操作。例如：

則最終的描述子為1011。

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

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

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

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

1.3特征點(diǎn)匹配

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

2通過算法組合改進(jìn)ORB

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

2.1尺度空間檢測(cè)極值點(diǎn)

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

圖3　SIFT與SURF建立金字塔對(duì)比圖

SURF算法將金字塔分為多個(gè)組（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)定的極值點(diǎn)

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

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

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

3　實(shí)驗(yàn)結(jié)果分析

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

3.1尺度不變性對(duì)比實(shí)驗(yàn)

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

（a）ORB算法匹配效果　　（b）SUORB算法匹配效果圖6　ORB和SUROB算法匹配效果對(duì)比圖

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

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

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

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

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

3.2計(jì)算時(shí)間對(duì)比實(shí)驗(yàn)

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

表2　 ORB和SUORB算法的匹配時(shí)間

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

4　結(jié)語

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7]張?jiān)粕?，鄒崢嶸.基于改進(jìn)ORB算法的遙感圖像自動(dòng)配準(zhǔn)方法[J].國土資源遙感，2013，03:20-24.

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

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

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

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

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

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

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

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

[16]汪淑夢(mèng).基于改進(jìn)的SIFT算法的圖像配準(zhǔn)技術(shù)的研究與實(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)平，秦川，劉佳，楊世強(qiáng)，王雯.基于SIFT算法的圖像目標(biāo)匹配與定位[J].儀器儀表學(xué)報(bào)，2011，01:163-169.

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

[21]薛金龍.基于角點(diǎn)的圖像特征提取與匹配算法研究[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

作者簡(jiǎn)介：林?。?990-），男，北京人，碩士研究生，研究方向?yàn)闄C(jī)器視覺

文章編號(hào)：1007-1423（2016）10-0028-05

DOI：10.3969/j.issn.1007-1423.2016.10.007

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