一種改進的圖像局部不變特征提取方法

譚躍生 鄭政宇 顧瑞春

一種改進的圖像局部不變特征提取方法

譚躍生 鄭政宇 顧瑞春

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

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

Haar小波 徑向梯度變換 旋轉不變性

0 引 言

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

1 相關研究

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

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

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

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

2 基本理論

2.1 特征點檢測算法

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

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

(1)

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

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

2.2 特征點描述

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

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

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

2) 設置一個大小為π/3的滑動窗口，統(tǒng)計窗口內的響應總和，即局部方向矢量。將最長的局部方向矢量作為對該特征點的主方向。

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

3 AR-SURF算法

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

3.1 積分圖像法

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

(2)

圖1 積分圖像原理

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

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

算法1：積分圖像

Input：待積分圖像I

Output：積分后圖像Img

Begin

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

[h,w]=size(I);

//計算積分圖像

For i=1:h

For j=1:w

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

End

End

Return Im

End

3.2 特征點檢測

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

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

為了保證檢測結果的準確性，AR-SURF算法比較檢測點周圍26個點的響應大小。檢測的原理依據(jù)式(3)-式(5)。

Det(H)=DxxDyy-ω2DxyDxy

(3)

(4)

(5)

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

由于沒有首末兩層，對于與首末兩層相鄰的點，AR-SURF將其比較過程分為兩個階段：

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

圖3 初次定位示意圖

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

圖4 二次定位示意圖

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

算法2：特征點位置計算

Input：待處理圖像I

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

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

Begin

1.初始化尺度空間

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

2.第一次濾波

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

3.特征點初次定位

比較每個點在中間兩層相鄰的17個點的值，如果為極值，則記錄該點的位置

4.第二次定位

將初次定位的特征點對應的在首層或者末層的相鄰點進行濾波；

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

5.插值精確定位

End

3.3 特征點描述

特征點描述階段，確定主方向的過程造成整個特征點描述過程中需要要計算兩次特征點周圍區(qū)域的響應，對計算速度影響很大。考慮到這個問題，本文提出的AR-SURF算法把這個過程舍棄，利用旋轉不變的區(qū)域劃分方法和新的描述子來彌補沒有主方向造成的旋轉不變性喪失。

3.3.1 圖像的劃分

圖5 圖像劃分方式

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

3.3.2 特征描述方法

圖6 RGT旋轉原理

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

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

(6)

t=Rπ/2r

(7)

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

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

算法3：構建特征描述子

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

Output：特征描述子Descriptor

Begin

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

2.利用積分圖像計算每個點的x與y方向的Haar響應

3.將每個點按本身對中心點的方向進行旋轉，計算旋轉之后的響應

4.將中心點周圍按照步長為3劃分為8個同心圓區(qū)域

5.每個區(qū)域計算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 特征點定位的閥值

//計算原始圖像的積分圖像

Call 算法1

Return Im

//定位極值點

Call算法2

Return ipts

//生成描述子

For i=1:length(ipts)

Call 算法3

Return Descriptor(i)

End

Return Descriptor

End

4 實驗及結果分析

4.1 特征點定位時間比較

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

表1 特征點定位比較

4.2 生成描述子時間比較

生成描述子的時間比較實驗采用兩種算法針對四個不同大小的圖片進行比較，圖中的特征點是由4.1節(jié)SURF算法得到，利用AR-SURF中的描述子生成算法計算得到描述子。由表2可以看出，在生成同樣個數(shù)的描述子的情況下，AR-SURF的速度提高了30%以上。這是由于AR-SURF省略通常SURF計算主方向的過程，改為對特征點周圍區(qū)域的Haar響應計算RGT變換。SURF算法中對每個點都要計算兩次響應值(確定主方向一次，旋轉后一次)變?yōu)橹恍栌嬎阋淮巍Ｐ枰⒁獾氖怯嬎鉘GT的時候因為每個點都需要得到本身的方向并旋轉，不能得到理想中50%的提速。

表2 生成描述子比較

結合特征點定位和描述兩個階段，得到如圖7所示，可以看出AR-SURF特征點提取的時間相較SURF提升近30%，而且對于大圖片速度提升效果呈增長趨勢。

圖7 提取總時間比較

4.3 特征匹配效果實例

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

圖8 特征匹配實例

5 結 語

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

[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多尺度斑點特征檢測[J].光學精密工程,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].計算機工程,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] 楊恒,王慶.一種新的局部不變特征檢測和描述算法[J].計算機學報,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] 湯彪,左崢嶸,李明.基于旋轉不變HOG特征的圖像匹配算法[EB/OL].北京:中國科技論文在線[2013-01-24].http://www.paper.edu.cn/releasepaper/content/201301-1025.

[15] 李婷婷,湯進,江波,等.迭代的圖變換匹配算法[J].中國圖象圖形學報,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。國家自然科學基金項目(61462069)；內蒙古自然科學基金項目(2014MS0622)；內蒙古科技大學校內基金項目(2011NCL054)。譚躍生，教授，主研領域：大規(guī)模圖像數(shù)據(jù)處理與挖掘。鄭政宇，碩士生。顧瑞春，講師。

TP393

A

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