圖像匹配算法研究之surf算法

學海無涯GL 2012-09-11

展開全文

圖像匹配算法研究之surf算法

今天碰巧和朋友討論這個，才想起來好久沒碰，都生疏了，趁著暑假還有點閑時，先寫寫再說。有錯誤的地方希望大家指正。

SURF (Speeded Up 
Robust Feature) is a robust local feature detector, first presented by Herbert 
Bay et al. in 2006, that can be used in computer vision tasks like object 
recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor. 
The standard version of SURF is several times faster than SIFT and claimed by 
its authors to be more robust against different image transformations than SIFT. 
SURF is based on sums of 2D Haar wavelet responses and makes an efficient use of 
integral images.

上面這段文字的大體意思就是說：

SURF意指加速的具有魯棒性的特征，由Bay在2006年首次提出，這項技術可以應用于計算機視覺的物體識別以及3D重構中。SURF算子由SIFT算子改進而來，一般來說，標準的SURF算子比SIFT算子快好幾倍，并且在多幅圖片下具有更好的魯棒性。SURF最大的特征在于采用了harr特征以及積分圖像integral image的概念，這大大加快了程序的運行時間。

surf提出算法參見http://www.vision.ee./~surf/papers.html 有paper下載地址。

1、提取特征點

2、提取特征描述符

1. 特征點的提取

1）利用Hessian矩陣，計算特征值α

Hessian矩陣

其中Lxx(x, σ)是高斯濾波后圖像g(σ)的在x方向的二階導數,其他的Lyy(x, σ)、Lxy(x, σ)都是g(σ)的二階導數。

為了減小計算量，原文使用了一個簡單的方法，并利用了積分圖像的優勢（大大的減少計算量），方法其實很簡單就是在模糊的基礎上將原本的模塊近似下。

總所周知，一般計算圖像的二階導時，利用下面的公式d²f(x)/dx²=(f(x+1)-f(x))-(f(x)-f(x-1))=-2*f(x)+f(x+1)+f(x-1)。但是f(x)=g(h(x))【h(x)為圖像的灰度值，f(x)

是將h(x)高斯濾波處理的灰度函數】

圖一模板近似

以9X9濾波器為例，如上圖所示，左邊兩幅圖分別為灰度圖像在中心點（黑色點）處的二階導數d²f(x)/dx²和d²f(x)/dxdy的模板對應的值, 近似后變成右邊的兩幅圖，圖中灰色部分像素值為0。可是這樣計算特征值不是也很復雜么？當然，所以作者提供了一種新思路--使用積分圖像。

積分圖像，顧名思義，即指當前像素點所在位置距原點（0,0）所包圍面的所有灰度之和。

綠色的部分為當前像素點，紅色為積分區域。

這樣計算圖像中任意一塊矩形區域的灰度之和Sx只需要利用矩形4個頂點(Xi,Yi)(i=1,2,3,4 順序為從上之下，先左后右)的積分值S（x,y）即可。

Sx=S(X1,Y1)+S(X4,Y4)-S(X2,Y2)-S(X3,Y3)

至此，大家應該知道近似二階導數的高斯模板并引入積分圖像的好處了吧，只需要在函數定義之前計算各個坐標點的積分圖像，然后就能方便的求出hessian的特征值。

不過由于函數模板的近似，這里需要修正下特征值α的求解公式：

這里Dxx和Dxy就是根據圖一得到的，而Dyy和Dxx類似，只需要導致一下模板即可。

2）根據是否為領域極大值判斷特征點

這里要引入圖像堆的概念，說簡單點，就是一組大小相同的圖像，這些圖像都是根據不同大小高斯濾波二階導模板，如圖一所示得到的平滑后圖像Pi 。

按照模板大小從小到大將Pi沿z軸方向排布，這樣中間層的每個像素點的領域就為3X3X3（包括上下兩層）。若該點的特征值α為這27個點中的最大值，那么可以認為該點為Feature points--特征點（圖像依據這些特征點的匹配進行更多的操作，比如拼接，比較相似性等等）。

2.特征點的匹配

1）尋找特征向量

欲進行特征點的匹配，必須提取出特征點的特征向量再利用兩個向量的相似程度認為兩個點是否為兩幅圖像相互對應的點。

第一步.計算特征點的主方向

以特征點為圓心半徑為6像素建立圓領域，計算得出里面有109個像素點。計算這些點的harr特征harrx和harry.

那么該怎樣計算任意一點的harr特征值？

圖二 harr-like特征

選取edge features前兩個作為harrx和harry值，這個方向有些類似與梯度方向，不過這里的領域顯然更廣。至于計算么，依舊是利用積分圖像。

對這109個像素點分別求出各自的向量的方向angle=acrtan(harry/harrx) ，根據最近鄰原則將這些 angle劃分到60，120，...，300，360等6個值上。劃分在同一范圍上的像素點分別將他們的harrx和harry相加即可。不過為了體現相鄰像素點的更大影響，還需要考慮高斯權重系數。這樣得到最大的harrx和最大的harry,組成了主方向向量。

第二步.提取特征描述符

圖3.選取特征區域