李 蘭 謝勤嵐

(中南民族大學(xué)生物醫(yī)學(xué)工程學(xué)院 武漢 430074)

一種改進(jìn)Harris-SIFT算子的圖像匹配算法*

李 蘭 謝勤嵐

(中南民族大學(xué)生物醫(yī)學(xué)工程學(xué)院 武漢 430074)

SIFT特征是一種性能良好的檢測(cè)局部的特征,被廣泛應(yīng)用于圖像匹配。針對(duì)SIFT算法的數(shù)據(jù)處理量大、運(yùn)行速度慢、時(shí)間復(fù)雜度高等問(wèn)題,提出了一種基于角點(diǎn)精確定位、降低特征維度、增強(qiáng)近似最近鄰匹配法的改進(jìn)算法。實(shí)驗(yàn)的結(jié)果證明,改進(jìn)后的算法提高了算法的運(yùn)行速度和匹配精確度。

SIFT; Harris; 圖像匹配

Class Number TP391

1 引言

圖像匹配是利用圖像處理方法將兩幅圖像相同的區(qū)域進(jìn)行匹配[1],它是圖像處理領(lǐng)域的一個(gè)重要應(yīng)用技術(shù),在計(jì)算機(jī)視覺(jué)、醫(yī)學(xué)圖像分析、模式識(shí)別等多方面都有著廣泛的應(yīng)用價(jià)值。在實(shí)際應(yīng)用中,由于處在不同條件下,匹配的圖像之間往往存在著尺度、噪聲、亮暗、旋轉(zhuǎn)等差異,這給圖像匹配算法帶來(lái)了不少難題。而基于局部特征的算法只考慮特征信息,具有較強(qiáng)的抗噪聲、形變能力和計(jì)算量小、魯棒性高的優(yōu)點(diǎn)[2],因此被廣泛應(yīng)用于各個(gè)行業(yè)中。到目前為止,已經(jīng)有大量的局部特征算法被提出。文獻(xiàn)[3～4]對(duì)幾種有代表性的局部特征進(jìn)行了性能評(píng)估,通過(guò)實(shí)驗(yàn)表明SIFT是性能最為魯棒的局部特征算法。

SIFT算法由D.G.Lowe[5～7]于1999年提出,SIFT特征[5～7]是一種性能良好的局部特征,被廣泛應(yīng)用于圖像匹配中,但SIFT特征點(diǎn)有128維描述符,所以存在數(shù)據(jù)處理量大、運(yùn)行速度慢、時(shí)間復(fù)雜度高的問(wèn)題[6]。

本文結(jié)合Harris角點(diǎn)檢測(cè)[7]和SIFT特征描述算子的優(yōu)點(diǎn),利用Forsnter算子思想對(duì)角點(diǎn)進(jìn)行精確定位,然后改進(jìn)SIFT算法描述子,用36維特征描述符代替128維特征描述符,進(jìn)行特征描述。最后利用增強(qiáng)型近似最近鄰匹配方法對(duì)描述子進(jìn)行匹配,達(dá)到圖像匹配的目的。

2 改進(jìn)的Harris角點(diǎn)檢測(cè)算法

Forsnter算子[8]是攝影測(cè)量中經(jīng)典的興趣點(diǎn)定位算子,具有精度高、速度快等特點(diǎn),其基本思想是：通過(guò)獲得角點(diǎn),以該點(diǎn)為中心建立最佳窗口,對(duì)最佳窗口內(nèi)的每個(gè)像素的邊緣直線(垂直于梯度方向)進(jìn)行加權(quán)中心化,得到角點(diǎn)的精確坐標(biāo)。

利用Harris算子[9～10]提出的角點(diǎn)作為Forsnter算子的最佳窗口中心點(diǎn),在窗口內(nèi)進(jìn)行加權(quán)中心化,精確定位角點(diǎn)坐標(biāo)的具體計(jì)算原理如下：

最佳窗口內(nèi)任一像素(x,y)的邊緣直線l的方程可以表示為

p=x·cosθ+y·sinθ

(1)

式(1)中,p為原點(diǎn)(最佳窗口的左上角像素)到直線l的距離,θ為梯度角,tanθ=gy/gx,gx、gy為該點(diǎn)的robert梯度。設(shè)角點(diǎn)坐標(biāo)為(x0,y0),式(2)中,v是點(diǎn)(x,y)到直線l的垂直距離,則可列出如下關(guān)系式：

p+v=x0·cosθ+y0·sinθ

(2)

(3)

式(3)中,將原點(diǎn)到邊緣的直線的距離視為觀測(cè)值,而邊緣直線的方向保持不變,權(quán)w(x,y)是梯度模的平方,因此,權(quán)的實(shí)質(zhì)即是該邊緣尺度。對(duì)式(3)進(jìn)行法化,得到法方程：

(4)

對(duì)式(4)求解,即可得到精確角點(diǎn)坐標(biāo)(x0,y0)。

3 改進(jìn)的SIFT算法

3.1 用36維特征描述子代替原128維特征描述子

將關(guān)鍵點(diǎn)周圍16×16區(qū)域改為15×15區(qū)域[11],在該區(qū)域上采樣計(jì)算方向,將每個(gè)5×5的區(qū)域方向投影到8個(gè)方向,如圖1所示

對(duì)于每個(gè)種子的8個(gè)方向的梯度方向直方圖的累加值s1、s2、…、s8[4～6],如圖2(a)所示,可以用4個(gè)方向v1,v2,v3,v4來(lái)表示為圖2(b)所示。它們之間的關(guān)系是：

(5)

改進(jìn)后的特征描述子維數(shù)為

相比原來(lái)的特征描述子128維,維數(shù)降低不少。將描述每個(gè)種子的累加值的數(shù)量由8個(gè)降為4個(gè),由于4個(gè)累加值仍然包含了8個(gè)累加值中所有信息,故并不影響對(duì)特征點(diǎn)信息的描述?；诖诉@種改進(jìn)大大的節(jié)約了計(jì)算時(shí)間,提高算法的實(shí)時(shí)性。

3.2 用增強(qiáng)型近似最近鄰匹配方法進(jìn)行匹配

由于最近鄰匹配法[2]是一種單向的操作,可能會(huì)產(chǎn)生錯(cuò)誤的匹配點(diǎn)。增強(qiáng)型最近鄰匹配雙向法流程圖如圖3所示。

將最近鄰匹配法單向判定改為增強(qiáng)型最近鄰匹配法雙向判定后,對(duì)可能存在的匹配點(diǎn)對(duì)進(jìn)行反向的確認(rèn),實(shí)現(xiàn)正反雙向判定,提高了匹配的正確率。

4 實(shí)驗(yàn)和結(jié)果

為了驗(yàn)證本文改進(jìn)的算法的圖像配準(zhǔn)速度和效果,本文設(shè)計(jì)了幾個(gè)實(shí)驗(yàn)來(lái)與原始Harris-sift算法來(lái)進(jìn)行比較。實(shí)驗(yàn)平臺(tái)為Pentium(R) Dual-Core E6700 處理器, 3.20GHz,內(nèi)存為4G的PC機(jī),Window 7 64位操作系統(tǒng),編程環(huán)境為VS2012+OpenCv2.4.8。實(shí)驗(yàn)結(jié)果從特征點(diǎn)個(gè)數(shù)、匹配點(diǎn)對(duì)、特征點(diǎn)對(duì)、特征點(diǎn)匹配時(shí)間、算法運(yùn)行總時(shí)間以及正確匹配率5個(gè)方面對(duì)改進(jìn)算法與原算法進(jìn)行對(duì)比。

圖4和圖5是圖像的匹配實(shí)驗(yàn)結(jié)果,對(duì)比可以看出,SIFT算法提取出來(lái)的點(diǎn)不是角點(diǎn),不能反映圖像的視覺(jué)角點(diǎn),而本文算法結(jié)合改進(jìn)的Harris-sift算法提取的特征描述點(diǎn)都是角點(diǎn),并降低了特征提取的復(fù)雜度,大大提高了原SIFT算法的匹配率和速度。

表1 圖像匹配比較數(shù)據(jù)

表1是實(shí)驗(yàn)得到的數(shù)據(jù),通過(guò)分析表1中的實(shí)驗(yàn)數(shù)據(jù)和匹配結(jié)果可以發(fā)現(xiàn),改進(jìn)的算法用Forsnter算子思想對(duì)Harris角點(diǎn)進(jìn)行精定位,提高了圖像特征點(diǎn)提取的精確度。然后用36維的特征描述符對(duì)特征點(diǎn)進(jìn)行描述,大大節(jié)約了匹配時(shí)間,用增強(qiáng)型近似最近鄰匹配方法進(jìn)行匹配,提高了算法的匹配率。

5 結(jié)語(yǔ)

本文針對(duì)SIFT算法存在數(shù)據(jù)處理量大、運(yùn)行速度慢、時(shí)間復(fù)雜度高的問(wèn)題,提出改進(jìn)的Harris-sift的圖像匹配算法。該算法采用Forsnter算子獲取Harris角點(diǎn)精確定位,然后改進(jìn)SIFT算子,對(duì)其描述符進(jìn)行降維,并在匹配過(guò)程中采用雙向匹配法,提高了特征點(diǎn)的匹配率和匹配速度。實(shí)驗(yàn)表明,本文的改進(jìn)算法準(zhǔn)確率更高,運(yùn)算速度更快。但本文改進(jìn)算法也有不足之處,在將sift算子由128維改為36維后,會(huì)降低算法的正確匹配率,雖然改進(jìn)的算法整體上提高了特征點(diǎn)正確匹配率,因此對(duì)該算法還需要進(jìn)行進(jìn)一步研究,如何在降維的同時(shí)提高正確匹配率,這是下一步工作的重點(diǎn)。

[1] 岡薩雷斯.數(shù)字圖像處理[M].北京：電子工業(yè)出版社,2003.

[2] 王永明,王貴錦. 圖像局部不變性特征與描述[M].北京：國(guó)防工業(yè)出版社,2010.

[3] 曾凡永,顧愛(ài)輝,等.幾種特征點(diǎn)提取算子的分析和比較[J].現(xiàn)代測(cè)繪,2015(3):15-18.

[4] Mikolajczyk K, Tuytelaars T, Schmid C.仿射區(qū)域描述子的比較[J].國(guó)際計(jì)算機(jī)視覺(jué)雜志,2005,65(1/2):43-72.

[5] D.Lowe.尺度不變特征點(diǎn)中獨(dú)特的圖像特征點(diǎn)[J].國(guó)際計(jì)算機(jī)視覺(jué)雜志,2004,60,(2):91-110.

[6] D.Lowe. 局部尺度不變特征點(diǎn)的物體識(shí)別[J].國(guó)際計(jì)算機(jī)視覺(jué)雜志,1999:1150-1157.

[7] Lowe D.開(kāi)源SIFT庫(kù).Lowe D. OpenSIFT-An open-source SIFT library[EB/OL].

[8] 李鵬程,曾毓敏,張琴.基于改進(jìn)Harris的圖像拼接算法[J].南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版). 2014(09): 43-48.

[9] 張艷,張志成.混合Forstner算法和SIFT灰度圖像特征點(diǎn)提取[J].科技通報(bào).2012(10):64-70.

[10] 毛雁明,蘭美輝.角點(diǎn)檢測(cè)方法研究.[J].現(xiàn)代計(jì)算機(jī)：下半月版,2008(10):86-88.

[11] 楊松,邵龍?zhí)?宋維波,等.一種基于SIFT特征的快速圖像匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(7):186-189.

An Improved Image Matching Algorithm Based on Harris-SIFT

LI Lan XIE Qinlan

(College of Biomedical Engineering, South-Central University for Nationalities, Wuhan 430074)

SIFT features are a kind of local features with high performance, which are applied widely in the image matching field. However, there are some disadvantages about SIFT algorithm, such as, a large volume of data processing, low running speed, high time complexity and so on. Based on these disadvantages, the paper proposes an improved image matching algorithm based on Harris and SIFT. Experimental results prove that the improved algorithm has higher matching accuracy and less matching time.

SIFT, Harris, image matching

2016年10月25日,

2016年11月28日

李蘭,女,碩士研究生,研究方向：醫(yī)學(xué)圖像處理。謝勤嵐,男,博士,教授,研究方向：智能信號(hào)與圖處理,電子系統(tǒng)集成技術(shù),生物醫(yī)學(xué)系統(tǒng)辨識(shí),建模與仿真,生物信息學(xué),智能控制理論等。

TP391

10.3969/j.issn.1672-9730.2017.04.009