一種改進(jìn)的圖像局部不變特征提取方法

譚躍生 鄭政宇 顧瑞春

一種改進(jìn)的圖像局部不變特征提取方法

譚躍生 鄭政宇 顧瑞春

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

針對(duì)傳統(tǒng)局部特征提取算法在提取特征點(diǎn)時(shí)效率不高，生成描述子需要計(jì)算主方向等問(wèn)題，結(jié)合SURF算法和RGT(Radial Gradient Transform)，在精度損失盡可能小的情況下提高局部不變特征提取速度，提出一種改進(jìn)的AR-SURF(加速?gòu)较騍URF)算法。該方法在特征檢測(cè)階段，在定位特征點(diǎn)時(shí)減少構(gòu)造尺度空間時(shí)所計(jì)算的響應(yīng)層個(gè)數(shù)，將求取對(duì)應(yīng)點(diǎn)響應(yīng)放在定位階段。在特征描述階段，取消確定主方向的過(guò)程，將特征點(diǎn)周圍區(qū)域的Haar小波響應(yīng)進(jìn)行RGT變換，然后將特征點(diǎn)周圍區(qū)域劃分為多個(gè)同心圓，并統(tǒng)計(jì)特征點(diǎn)周圍圓形區(qū)域內(nèi)的響應(yīng)結(jié)果，最后利用小波響應(yīng)結(jié)果得到旋轉(zhuǎn)不變的特征描述子。實(shí)驗(yàn)結(jié)果表明，AR-SURF算法節(jié)省了時(shí)空損耗，提升了定位速度，提取效果更好，更加合適于海量圖片處理。

Haar小波 徑向梯度變換 旋轉(zhuǎn)不變性

0 引 言

近年隨著互聯(lián)網(wǎng)的發(fā)展和海量圖片處理的需要，圖像局部特征提取算法的實(shí)時(shí)性的要求更加地彰顯出來(lái)。以跟蹤目標(biāo)為例，通常目標(biāo)跟蹤處理的對(duì)象是實(shí)時(shí)傳感器得到的一系列圖像，如果不能達(dá)到規(guī)定幀處理速率便不能保證處理數(shù)據(jù)的實(shí)時(shí)性和連貫性，但是現(xiàn)有的圖像局部特征提取領(lǐng)域的算法，在特征點(diǎn)定位和描述時(shí)需要大量的時(shí)間，不能滿足需求。在一定精度下，提升提取的速度，滿足海量圖片的實(shí)時(shí)性檢測(cè)，成為圖像特征提取的研究重點(diǎn)。

1 相關(guān)研究

局部特征建立在尺度空間的理論基礎(chǔ)上。一般來(lái)說(shuō)，局部特征的提取分為兩個(gè)步驟，即特征檢測(cè)階段和特征描述階段。特征檢測(cè)階段通過(guò)尺度空間確定出特征點(diǎn)所在位置、尺度等信息。特征描述階段則是構(gòu)建一個(gè)對(duì)各種變化因素不敏感的特征描述子來(lái)描述特征點(diǎn)以及周圍區(qū)域。利用這些特征就可以在各種因素的影響下依然很好地匹配圖像。

在局部特征檢測(cè)上常用檢測(cè)子有Harris角點(diǎn)[1]、HOG(Histogram of Oriented Gradient)[2]、LoG(Laplacian of Gaussian)和DoG(Difference of Gaussian)[3]、Fast-Hessian[4]、SUSAN算子[5]等。FAST算法[6]屬于計(jì)算較快的特征檢測(cè)算子，應(yīng)用于人臉識(shí)別，連續(xù)動(dòng)作檢測(cè)等方面，此算法采用檢測(cè)物體邊緣梯度變化，得到能夠表示物體輪廓的特征點(diǎn)，對(duì)旋轉(zhuǎn)、光照變化具有較強(qiáng)的魯棒性。但是缺乏在尺度變化上的處理，使得其只能適用于特定數(shù)據(jù)集。Lowe[7]結(jié)合LoG算子和尺度空間提出了尺度不變特征變換算法SIFT(Scale Invariant Feature Transform)，特點(diǎn)是利用不同尺度下的圖像構(gòu)成尺度空間，然后利用三維非極大抑制對(duì)相鄰尺度下的點(diǎn)篩選，得到魯棒性強(qiáng)的檢測(cè)算子。在尺度空間的框架下，出現(xiàn)了利用Harris-Laplace[8]等檢測(cè)算子的類SIFT算法，相比SIFT算法上進(jìn)一步提高了定位特征點(diǎn)的速度。典型的有2006年Bay等[9]提出的SURF算法，該算法基于Fast-Hessian和Haar小波響應(yīng)，改變SIFT算法的尺度空間構(gòu)建方式，并利用積分圖像對(duì)卷積過(guò)程進(jìn)行加速，降低在計(jì)算尺度空間時(shí)的復(fù)雜度，SURF算法能保證在旋轉(zhuǎn)、亮度變化、尺度變化等條件下也有很高的魯棒性，同時(shí)提升了速度。但是在應(yīng)用時(shí)，構(gòu)建尺度空間的效率依然是一個(gè)瓶頸，構(gòu)建的過(guò)程具有大量不必要的重復(fù)性計(jì)算，有待進(jìn)一步改進(jìn)。

現(xiàn)有的圖像局部特征描述子通過(guò)統(tǒng)計(jì)特征點(diǎn)位置周圍區(qū)域的特征來(lái)描述局部區(qū)域的變化構(gòu)建描述局部區(qū)域的描述子。例如SIFT算法統(tǒng)計(jì)方向梯度直方圖，首先統(tǒng)計(jì)周圍區(qū)域每個(gè)點(diǎn)的方向，得到此區(qū)域的主方向，然后參照主方向?qū)⒅車鷧^(qū)域劃為16個(gè)子區(qū)，統(tǒng)計(jì)子區(qū)基于主方向的8個(gè)梯度方向的直方圖，得到128維描述向量。SIFT描述子具有很強(qiáng)的抗噪聲能力和匹配誤差容錯(cuò)能力，是最經(jīng)典的局部不變特征描述子。分析SIFT算法的描述過(guò)程，主方向確定保證描述子的旋轉(zhuǎn)不變能力，但需計(jì)算周圍區(qū)域的特征，而旋轉(zhuǎn)后仍然周圍區(qū)域又需要一次計(jì)算，造成算法在時(shí)空間上的浪費(fèi)，很大程度上限制了算法速度的提升；描述子的構(gòu)建方式影響描述過(guò)程的計(jì)算量，維數(shù)的確定影響匹配時(shí)的精度和速度，128維特征向量難以滿足實(shí)時(shí)匹配的要求。多數(shù)文獻(xiàn)針對(duì)描述子的構(gòu)建過(guò)程進(jìn)行改進(jìn)。SURF描述子參考SIFT，利用Haar小波在特征點(diǎn)的尺度的響應(yīng)代替梯度方向直方圖，本質(zhì)上和SIFT描述子相同，且效率相近。GLOH、GDOH[10]等算法利用不同的子區(qū)劃分方式，減少描述子維數(shù)，而PCA-SIFT[11]算法利用主成份分析求得主要描述特征，可以將維數(shù)控制在20～40維，擁有較快的匹配速度，但是建立描述子的過(guò)程花費(fèi)了大量的時(shí)間，20維的特征也造成了信息的丟失。以上方法都有一定的效果，但是對(duì)求取主方向的改進(jìn)，卻很少有人提出。

針對(duì)以上問(wèn)題，本文提出一種改進(jìn)的局部特征提取算法(AR-SURF)，包括特征點(diǎn)提取和特征描述兩個(gè)部分的改進(jìn)。通過(guò)對(duì)特征點(diǎn)定位階段的過(guò)程進(jìn)行改進(jìn)，減少構(gòu)建尺度空間時(shí)的計(jì)算量，提高定位的速度。在特征點(diǎn)描述階段去掉類SIFT算法的確定主方向的過(guò)程，將特征點(diǎn)周圍區(qū)域的Haar小波響應(yīng)進(jìn)行RGT[12]變換，然后利用同心圓的區(qū)域劃分保證描述子的旋轉(zhuǎn)不變性，最后統(tǒng)計(jì)得到的變換后的響應(yīng)，構(gòu)成描述子。實(shí)驗(yàn)表明，本文的特征提取算法相較SURF算法速度有很大提升，且在旋轉(zhuǎn)變化、亮度變化和尺度變化下都有很好的效果。

2 基本理論

2.1 特征點(diǎn)檢測(cè)算法

一般局部特征提取算法的特征檢測(cè)階段細(xì)分為兩個(gè)部分，即建立尺度金字塔和關(guān)鍵點(diǎn)定位。需要對(duì)圖像建立尺度空間，在尺度空間中，每一個(gè)金字塔中的每一層都是圖像在當(dāng)前尺度下與相對(duì)應(yīng)尺度的高斯核函數(shù)卷積。

定義圖像I的Hessian 矩陣在尺度σ時(shí)如下：

(1)

其中，Lxx(x,σ)是高斯二階偏導(dǎo)數(shù)在x處與圖像I的卷積。

SURF算法構(gòu)造了一種9×9的盒型濾波器來(lái)近似二階高斯濾波，計(jì)算Dxx，Dyy，Dxy；每個(gè)像素點(diǎn)的計(jì)算完成后，就得到一幅圖像的響應(yīng)圖。利用不同尺寸的濾波器對(duì)同一幅圖像進(jìn)行濾波，得到其在不同尺度的響應(yīng)圖，進(jìn)一步構(gòu)成尺度空間。之后對(duì)尺度空間內(nèi)像素采用非極大抑制，即若某個(gè)像素點(diǎn)的Dxx×Dyy-Dxy×Dxy的值比其相鄰的的26個(gè)點(diǎn)大，則認(rèn)為該點(diǎn)為特征點(diǎn)。最后仿照SIFT[7]利用三維二次函數(shù)精確定位，并去除邊緣響應(yīng)點(diǎn)。文獻(xiàn)[9]證明，只要選取適當(dāng)?shù)膮?shù)，SURF算法不僅能夠大大提升算法速度，而且保持了較高的準(zhǔn)確性。實(shí)際運(yùn)算中，可以利用積分圖像快速求出卷積核。

2.2 特征點(diǎn)描述

大多數(shù)局部特征提取算法的特征點(diǎn)描述階段都分為兩個(gè)階段，即確定特征區(qū)域主方向和生成特征描述子。確定主方向的目的是為了使得特征點(diǎn)描述子具有旋轉(zhuǎn)不變性，應(yīng)對(duì)圖像的旋轉(zhuǎn)；描述子則是統(tǒng)計(jì)概括出特征點(diǎn)周圍所有點(diǎn)的性質(zhì)，用來(lái)描述特征點(diǎn)及其周圍點(diǎn)的描述因子，為之后的匹配提供依據(jù)。

以SURF為例，主方向的確定利用特征點(diǎn)周圍區(qū)域點(diǎn)的Haar小波響應(yīng)，具體做法為[9]：

1) 以6倍所在尺度s為半徑，圈定一個(gè)圓形區(qū)域，以1s為步長(zhǎng)，利用4s大小的Haar小波計(jì)算x，y兩個(gè)方向的小波響應(yīng)。得到小波響應(yīng)通常還要計(jì)算以特征點(diǎn)為中心的高斯加權(quán)，一般取σ=2s。

2) 設(shè)置一個(gè)大小為π/3的滑動(dòng)窗口，統(tǒng)計(jì)窗口內(nèi)的響應(yīng)總和，即局部方向矢量。將最長(zhǎng)的局部方向矢量作為對(duì)該特征點(diǎn)的主方向。

在構(gòu)建描述子階段，以特征點(diǎn)為中心，沿主方向劃分一個(gè)20s大小的方形區(qū)域。區(qū)域內(nèi)的點(diǎn)分配到4×4的子區(qū)域，而后計(jì)算5×5個(gè)像素點(diǎn)的歸一化Haar小波響應(yīng)。dx,dy分別為水平和垂直方向上的Haar小波響應(yīng)。最后統(tǒng)計(jì)每個(gè)子域的4個(gè)特征，最終得到64維的特征向量。

3 AR-SURF算法

AR-SURF改進(jìn)定位過(guò)程的方法，對(duì)特征點(diǎn)定位進(jìn)行優(yōu)化加速；改進(jìn)描述子構(gòu)建方式，優(yōu)化描述子構(gòu)建速度，配合積分圖像法，最終提高算法的整體運(yùn)行速度。

3.1 積分圖像法

積分圖像是計(jì)算的某一矩陣內(nèi)的像素和。積分圖像法可以對(duì)圖像預(yù)處理，得到圖像中每一個(gè)位置x的積分響應(yīng)，借助這些響應(yīng)可以幫助提高Haar小波響應(yīng)的計(jì)算速度。積分圖IΣ(x)在位置x=(x,y)T處的定義如下：

(2)

圖1 積分圖像原理

如圖1所示，計(jì)算矩形ABCD的響應(yīng)值，只需對(duì)4個(gè)頂點(diǎn)的響應(yīng)進(jìn)行四則運(yùn)算，就可以得到這幅圖像中的任意一個(gè)矩形區(qū)域內(nèi)的像素點(diǎn)的求和，并且求和算子獨(dú)立于矩形區(qū)域的大小，不受矩形大小的影響。

積分圖像算法的偽代碼如算法1所示。

算法1：積分圖像

Input：待積分圖像I

Output：積分后圖像Img

Begin

//得到圖像的大小參數(shù)

[h,w]=size(I);

//計(jì)算積分圖像

For i=1:h

For j=1:w

Im(i,j)=sum(I(1:i,1:j));

End

End

Return Im

End

3.2 特征點(diǎn)檢測(cè)

特征檢測(cè)階段最耗費(fèi)時(shí)間的環(huán)節(jié)是構(gòu)建尺度空間，每個(gè)尺度空間一般要建立4～5個(gè)尺度金字塔，而每個(gè)金字塔又要包含4～5層響應(yīng)。AR-SURF算法不計(jì)算尺度金字塔的首末層，僅對(duì)金字塔的中間層進(jìn)行濾波，得到中間層的濾波響應(yīng)如圖2所示，提升了構(gòu)建尺度空間的速度[4]。

圖2 AR-SURF中的4×4尺度空間

為了保證檢測(cè)結(jié)果的準(zhǔn)確性，AR-SURF算法比較檢測(cè)點(diǎn)周圍26個(gè)點(diǎn)的響應(yīng)大小。檢測(cè)的原理依據(jù)式(3)-式(5)。

Det(H)=DxxDyy-ω2DxyDxy

(3)

(4)

(5)

其中Det(H)為近似的Hessian矩陣的行列式值；Dxx、Dyy和Dxy則是濾波模板對(duì)高斯函數(shù)的近似，這里可以利用積分圖像對(duì)計(jì)算過(guò)程加速。Sig表示Laplace算子Dxx+Dyy的符號(hào)，主要用于區(qū)分特征點(diǎn)的亮暗。D定義為Fast-Hessian的特征點(diǎn)檢測(cè)依據(jù)，最后作為采樣點(diǎn)值存入尺度空間。如果Det(H)<0則直接賦0值；若Det(H)>0則存儲(chǔ)Sig和Det(H)的乘積，特征點(diǎn)的亮暗程度可在尺度空間中得到標(biāo)識(shí)。

由于沒(méi)有首末兩層，對(duì)于與首末兩層相鄰的點(diǎn)，AR-SURF將其比較過(guò)程分為兩個(gè)階段：

1) 如圖3所示，先進(jìn)行去掉首末兩層的比較，即鄰近首末兩層的點(diǎn)，只比較除去首末層之后剩余的17個(gè)點(diǎn)，并利用非極大抑制得到初次定位的點(diǎn)的坐標(biāo)、尺度等信息。

圖3 初次定位示意圖

2) 如圖4所示，在初次定位后的點(diǎn)的位置，分別求取對(duì)應(yīng)首層或者末層的相鄰9個(gè)點(diǎn)的響應(yīng)，然后比較初次定位點(diǎn)與這9個(gè)點(diǎn)的響應(yīng)的大小，采取非極大抑制，判斷是否為特征點(diǎn)。

圖4 二次定位示意圖

從上述過(guò)程可以看出，首末層需要的點(diǎn)只有之后第一次定位所得到點(diǎn)對(duì)應(yīng)的9個(gè)點(diǎn)，運(yùn)算量明顯是小于計(jì)算所有點(diǎn)響應(yīng)，由此AR-SURF算法可減少40%～50%的運(yùn)算量。其次，AR-SURF算法的二次定位特征點(diǎn)嚴(yán)格依照式(3)-式(5)進(jìn)行非極大抑制，得到的響應(yīng)點(diǎn)的位置與同樣采用這一原理的SURF相同。特征點(diǎn)位置計(jì)算算法如算法2所示。

算法2：特征點(diǎn)位置計(jì)算

Input：待處理圖像I

Output：特征點(diǎn)ip(x,y)的集合ipts

參數(shù)：金字塔個(gè)數(shù)Octave(默認(rèn)為4)、每個(gè)金字塔層數(shù)Scale(默認(rèn)為4)

Begin

1.初始化尺度空間

T(x,y,Octave,Scale)=0

2.第一次濾波

每個(gè)Octave的中間兩個(gè)Scale濾波，利用算法1加速

3.特征點(diǎn)初次定位

比較每個(gè)點(diǎn)在中間兩層相鄰的17個(gè)點(diǎn)的值，如果為極值，則記錄該點(diǎn)的位置

4.第二次定位

將初次定位的特征點(diǎn)對(duì)應(yīng)的在首層或者末層的相鄰點(diǎn)進(jìn)行濾波；

比較已知特征點(diǎn)與相鄰首末層點(diǎn)的值，若是極值則保留，否則排除

5.插值精確定位

End

3.3 特征點(diǎn)描述

特征點(diǎn)描述階段，確定主方向的過(guò)程造成整個(gè)特征點(diǎn)描述過(guò)程中需要要計(jì)算兩次特征點(diǎn)周圍區(qū)域的響應(yīng)，對(duì)計(jì)算速度影響很大。考慮到這個(gè)問(wèn)題，本文提出的AR-SURF算法把這個(gè)過(guò)程舍棄，利用旋轉(zhuǎn)不變的區(qū)域劃分方法和新的描述子來(lái)彌補(bǔ)沒(méi)有主方向造成的旋轉(zhuǎn)不變性喪失。

3.3.1 圖像的劃分

圖5 圖像劃分方式

傳統(tǒng)的圖像劃分方式基于笛卡兒坐標(biāo)系對(duì)區(qū)域劃分，不具備旋轉(zhuǎn)不變特性。AR-SURF依據(jù)極坐標(biāo)系，采用如圖5所示的劃分方式，將圖像劃分成若干個(gè)的同心圓環(huán)區(qū)域，每個(gè)圓環(huán)區(qū)域?qū)抴，為了增強(qiáng)魯棒性一般設(shè)定w為2s到4s，使每個(gè)圓環(huán)包含一定數(shù)量的像素點(diǎn)。圓環(huán)劃分方式的特點(diǎn)是當(dāng)圖像旋轉(zhuǎn)一定的角度時(shí)，每一個(gè)圓環(huán)所包含的圖像像素點(diǎn)不變，即具有旋轉(zhuǎn)不變的性質(zhì)，利用這一特點(diǎn)就能構(gòu)造旋轉(zhuǎn)不變的特征描述子。

3.3.2 特征描述方法

圖6 RGT旋轉(zhuǎn)原理

將特征點(diǎn)周圍劃分為圓環(huán)區(qū)域，則每個(gè)區(qū)域擁有可旋轉(zhuǎn)性，但是點(diǎn)的響應(yīng)依然參考沒(méi)有旋轉(zhuǎn)不變性的直角坐標(biāo)系，為解決這個(gè)問(wèn)題，考慮將響應(yīng)投影到旋轉(zhuǎn)不變的極坐標(biāo)系。AR-SURF算法采用基于RGT變換和Haar小波響應(yīng)的特征描述方法達(dá)到旋轉(zhuǎn)不變性。RGT變換的原理如圖6所示。

圖中圓形區(qū)域的中心點(diǎn)為c，p為圓周上任意一點(diǎn)。r和t為兩個(gè)正交的單位向量，其中r表示p點(diǎn)徑向方向的單位向量，t表示p點(diǎn)切向方向的單位向量。式(6)和式(7)[13]為r與t的計(jì)算公式，其中Rπ/2表示旋轉(zhuǎn)π/2的旋轉(zhuǎn)矩陣。

(6)

t=Rπ/2r

(7)

其中，g表示p點(diǎn)的梯度。將p點(diǎn)的梯度g投影到相互垂直的r和t兩個(gè)方向，即將梯度g分解兩個(gè)方向的向量之和(gTr)r+(gTt)t，得到g以r、t為基向量的坐標(biāo)(gTr,gTt)。文獻(xiàn)[14]證明了以r、t為基向量的坐標(biāo)系本身具有旋轉(zhuǎn)不變性，以此為基礎(chǔ)的響應(yīng)也具有旋轉(zhuǎn)不變性。

Haar小波是對(duì)梯度g在x與y方向的近似，由積分圖像計(jì)算得到，將Haar小波在兩個(gè)方向上的響應(yīng)分別分解成法向與徑向的響應(yīng)再合成，等同g在法向與徑向兩個(gè)方向的分解，即對(duì)Haar小波進(jìn)行RGT運(yùn)算。通過(guò)對(duì)Haar小波響應(yīng)運(yùn)用RGT算法，得到每個(gè)點(diǎn)所在位置的徑向與法向的特征響應(yīng)，這種響應(yīng)忽略每個(gè)位置本身的方向。結(jié)合RGT所得到的特征點(diǎn)周圍區(qū)域響應(yīng)信息與環(huán)形的分區(qū)方法，得到一種新的旋轉(zhuǎn)不變的特征描述子。特征描述的算法流程如算法3所示。

算法3：構(gòu)建特征描述子

Input：特征點(diǎn)位置ip(x,y,Octave,Scale)

Output：特征描述子Descriptor

Begin

1.獲取特征點(diǎn)周圍半徑12×Scale的區(qū)域iimg;

2.利用積分圖像計(jì)算每個(gè)點(diǎn)的x與y方向的Haar響應(yīng)

3.將每個(gè)點(diǎn)按本身對(duì)中心點(diǎn)的方向進(jìn)行旋轉(zhuǎn)，計(jì)算旋轉(zhuǎn)之后的響應(yīng)

4.將中心點(diǎn)周圍按照步長(zhǎng)為3劃分為8個(gè)同心圓區(qū)域

5.每個(gè)區(qū)域計(jì)算dx、dy、abs(dx)、abs(dy)的和，得到8×4=32維特征向量

End

3.4 AR-SURF算法流程

AR-SURF算法的整體流程如算法4所示。

算法4：

Input：待提取圖像I

Output：圖像特征向量集Descriptor

參數(shù)：M=4 尺度空間階數(shù)(Octave)

N=4 每階中尺度(Scale)的數(shù)量

S 特征點(diǎn)定位的閥值

//計(jì)算原始圖像的積分圖像

Call 算法1

Return Im

//定位極值點(diǎn)

Call算法2

Return ipts

//生成描述子

For i=1:length(ipts)

Call 算法3

Return Descriptor(i)

End

Return Descriptor

End

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

4.1 特征點(diǎn)定位時(shí)間比較

特征點(diǎn)提取時(shí)間分為兩個(gè)部分：(1) 特征點(diǎn)的定位時(shí)間；(2) 特征描述時(shí)間。特征點(diǎn)的定位時(shí)間分為四個(gè)階段：積分圖像、構(gòu)建尺度空間、粗定位、插值定位。統(tǒng)計(jì)SURF算法和AR-SURF在四種不同大小圖片中提取出特征點(diǎn)的時(shí)間，記錄多次提取求平均時(shí)間，得到如表1所示。可以看出AR-SURF在定位速度上有很大的提升，這是因?yàn)锳R-SURF保留了SURF算法的定位原理，減少構(gòu)建尺度空間所需運(yùn)算量，即每座金字塔中減少2層的計(jì)算，在尺度空間的構(gòu)建時(shí)間上節(jié)省近一半的時(shí)間。減少的兩層在后面的粗定位中，利用兩次定位的方式，針對(duì)每個(gè)待確定點(diǎn)周圍的點(diǎn)進(jìn)行運(yùn)算。相比計(jì)算整個(gè)尺度下所有點(diǎn)，計(jì)算待確定點(diǎn)周圍的點(diǎn)所需時(shí)間大幅減少，二次定位不會(huì)影響算法整體的加速。

表1 特征點(diǎn)定位比較

4.2 生成描述子時(shí)間比較

生成描述子的時(shí)間比較實(shí)驗(yàn)采用兩種算法針對(duì)四個(gè)不同大小的圖片進(jìn)行比較，圖中的特征點(diǎn)是由4.1節(jié)SURF算法得到，利用AR-SURF中的描述子生成算法計(jì)算得到描述子。由表2可以看出，在生成同樣個(gè)數(shù)的描述子的情況下，AR-SURF的速度提高了30%以上。這是由于AR-SURF省略通常SURF計(jì)算主方向的過(guò)程，改為對(duì)特征點(diǎn)周圍區(qū)域的Haar響應(yīng)計(jì)算RGT變換。SURF算法中對(duì)每個(gè)點(diǎn)都要計(jì)算兩次響應(yīng)值(確定主方向一次，旋轉(zhuǎn)后一次)變?yōu)橹恍栌?jì)算一次。需要注意的是計(jì)算RGT的時(shí)候因?yàn)槊總€(gè)點(diǎn)都需要得到本身的方向并旋轉(zhuǎn)，不能得到理想中50%的提速。

表2 生成描述子比較

結(jié)合特征點(diǎn)定位和描述兩個(gè)階段，得到如圖7所示，可以看出AR-SURF特征點(diǎn)提取的時(shí)間相較SURF提升近30%，而且對(duì)于大圖片速度提升效果呈增長(zhǎng)趨勢(shì)。

圖7 提取總時(shí)間比較

4.3 特征匹配效果實(shí)例

圖8給出四組特征匹配結(jié)果的實(shí)例，實(shí)驗(yàn)數(shù)據(jù)來(lái)自文獻(xiàn)[15]所用數(shù)據(jù)集，包括JPEG壓縮、模糊變化、亮度變化、尺度和旋轉(zhuǎn)變化。匹配算法依據(jù)向量的歐氏距離，計(jì)算得到最相似點(diǎn)與次相似點(diǎn)，如果兩點(diǎn)距離比值小于閥值(一般取0.65)，則記錄為匹配點(diǎn)。比較AR-SURF算法與SURF算法的描述子匹配效果。從圖中可以看出，AR-SURF的描述子匹配效果與SURF算法相近，同樣在四組圖片中得到了大量正確的匹配點(diǎn)。實(shí)驗(yàn)表明AR-SURF算法同樣對(duì)特征有很好的描述效果。

圖8 特征匹配實(shí)例

5 結(jié) 語(yǔ)

本文提出一種新的局部不變的特征提取算法AR-SURF，旨在盡可能少損失精度的情況下，提高圖像局部特征的提取速度。改進(jìn)特征檢測(cè)階段的定位流程，在不修改特征點(diǎn)定位原理的情況下，將減少構(gòu)建尺度空間時(shí)不必要的兩層尺度，減少特征點(diǎn)定位的時(shí)間。在生成特征描述子階段，創(chuàng)新地取消主方向確定過(guò)程，同時(shí)保證描述子的旋轉(zhuǎn)不變性，加快構(gòu)造速度，而更低的維數(shù)也能保證描述子匹配的速度。實(shí)驗(yàn)結(jié)果證明，AR-SURF相較于速度較快的SURF算法依然有明顯的速度優(yōu)勢(shì)，在亮度變化、模糊、壓縮下依然有很好的表現(xiàn)，在旋轉(zhuǎn)與尺度綜合變化不大的情況下也有很好的表現(xiàn)，適合應(yīng)用在實(shí)時(shí)圖像處理和海量圖片提取。下一步工作將利用更有效的匹配機(jī)制，發(fā)揮算法的速度優(yōu)勢(shì)，實(shí)現(xiàn)對(duì)圖片特征的實(shí)時(shí)提取和處理。

[1] Schmid C,Mohr R,Bauckhage C.Evaluation of interest point detectors[J].International Journal of computer vision,2000,37(2):151-172.

[2] Dalal N,Triggs B.Histograms of oriented gradients for human detection[C]//Computer Vision and Pattern Recognition,2005 CVPR,IEEE Computer Society Conference on,IEEE,2005,1:886-893.

[3] Lindeberg T.Scale-space theory:A basic tool for analyzing structures at different scales[J].Journal of applied statistics,1994,21(1-2):225-270.

[4] 韓冰,王永明,孫繼銀.加速的Fast Hessian多尺度斑點(diǎn)特征檢測(cè)[J].光學(xué)精密工程,2011,19(7):1686-1694.

[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] 郭莉莎,李俊山,朱英宏,等.基于多尺度FAST-9的圖像快速匹配算法[J].計(jì)算機(jī)工程,2012,38(12):208-210.

[7] Lowe D G.Distinctive image features from Scale-invariant keypoints[J].International journal of computer vision,2004,60(2):91-110.

[8] Mikolajczyk K,Schmid C.Scale & affine invariant interest point detectors[J].International journal of computer vision,2004,60(1):63-86.

[9] Bay H,Ess A,Tuytelaars T,et al.Speeded-up robust features (SURF)[J].Computer vision and image understanding,2008,110(3):346-359.

[10] 楊恒,王慶.一種新的局部不變特征檢測(cè)和描述算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(5):935-944.

[11] Ke Y,Sukthankar R.PCA-SIFT:A more distinctive representation for local image descriptors[C]//Computer Vision and Pattern Recognition,2004 CVPR 2004,Proceedings of the 2004 IEEE Computer Society Conference on,IEEE,2004,2:506-513.

[12] Takacs G,Chandrasekhar V,Tsai S,et al.Rotation-invariant fast features for large-Scale recognition and real-time tracking[J].Signal Processing:Image Communication,2013,28(4):334-344.

[13] Takacs G,Chandrasekhar V,Tsai S S,et al.Fast Computation of Rotation-Invariant Image Features by an Approximate Radial Gradient Transform[J].IEEE Transactions on Image Processing,2013,22(8):2970-2982.

[14] 湯彪,左崢嶸,李明.基于旋轉(zhuǎn)不變HOG特征的圖像匹配算法[EB/OL].北京:中國(guó)科技論文在線[2013-01-24].http://www.paper.edu.cn/releasepaper/content/201301-1025.

[15] 李婷婷,湯進(jìn),江波,等.迭代的圖變換匹配算法[J].中國(guó)圖象圖形學(xué)報(bào),2014,19(5):723-729.

AN IMPROVED METHOD FOR EXTRACTING IMAGE’S LOCAL INVARIANT FEATURE

Tan Yuesheng Zheng Zhengyu Gu Ruichun

(SchoolofInformationEngineering,InnerMongoliaUniversityofScienceandTechnology,Baotou014010,InnerMongolia,China)

For some disadvantages existing in traditional local feature extraction algorithm, such as the inefficiency when extracting feature points and the need to calculate principal direction when generating descriptor, etc., we propose in this paper an improved accelerated radial SURF algorithm by combining SURF algorithm and RGT (radial gradient transform) and speeding up the process of local invariant feature extraction in the circumstance of lesser precision loss as much as possible. In the step of feature detection, the algorithm decreases the number of response layers calculated in constructing the dimension space when locating the feature points, and places the course of corresponding point calculation in localisation phase. In the step of feature description, it cancels the process of determining principal direction, and conducts RGT transformation on Haar wavelet response in surrounding regions of feature point, then divides these regions into concentric circles and counts the response results within the surrounding circle regions of feature points as well, finally it uses these wavelet responding results to obtain the rotation-invariant feature descriptors. Experimental result demonstrates that AR-SURF algorithm saves the loss of time and space, increases the speed of localisation with better extraction effect, so it is more suitable for mass images processing.

Haar wavelet Radial gradient transform Rotational invariance

2014-11-28。國(guó)家自然科學(xué)基金項(xiàng)目(61462069)；內(nèi)蒙古自然科學(xué)基金項(xiàng)目(2014MS0622)；內(nèi)蒙古科技大學(xué)校內(nèi)基金項(xiàng)目(2011NCL054)。譚躍生，教授，主研領(lǐng)域：大規(guī)模圖像數(shù)據(jù)處理與挖掘。鄭政宇，碩士生。顧瑞春，講師。

TP393

A

10.3969/j.issn.1000-386x.2016.04.044