基于以SURF改進(jìn)AKAZE的圖像匹配算法

趙柏山，鄭麗娟，陳 瑜

（1.沈陽(yáng)工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)110870；2.中國(guó)石油長(zhǎng)慶油田分公司第四采油廠，銀川750006）

1 引 言

圖像匹配是指通過(guò)一定的匹配算法在兩幅或多幅圖像之間識(shí)別同名點(diǎn)的過(guò)程，主要可分為基于圖像灰度信息與基于圖像特征信息匹配兩類。其中，基于特征的圖像匹配技術(shù)，以其具有魯棒性高、計(jì)算量小的優(yōu)勢(shì)取得快速的發(fā)展[1]。D. G. Lowe 于2004 年提出了尺度不變特征匹配算法（SIFT）[2]，該算法對(duì)圖像的旋轉(zhuǎn)、尺度變化等都是魯棒不變的，缺點(diǎn)是實(shí)時(shí)性差。H. Bay 等人于2006 年提出了加速魯棒特征算法（SURF）[3]，它依賴于圖像的高斯尺度空間分析，同時(shí)基于Hessian 矩陣[4]的行列式進(jìn)行特征點(diǎn)檢測(cè)，利用積分圖像、Haar 小波響應(yīng)提高檢測(cè)速度，采用Haar 小波變換增加魯棒性。SURF 特征不受旋轉(zhuǎn)和尺度的影響。與SIFT 相比，SURF 的主要優(yōu)點(diǎn)是計(jì)算成本低，但是在目前各種匹配算法當(dāng)中，其匹配速度比利用二進(jìn)制描述符進(jìn)行匹配的速度慢[5]。Alcantarilla 等人于2012 年提出了利用非線性擴(kuò)散濾波和非線性尺度空間的KAZE 特征[6]。KAZE 特征對(duì)旋轉(zhuǎn)、尺度、有限仿射變換具有不變性，不足之處是計(jì)算成本高。Alcantarilla 等人于2013 年提出了加速的KAZE（AKAZE）算法[7]，該算法也是基于非線性擴(kuò)散濾波的，但其使用FED 數(shù)學(xué)框架，從而動(dòng)態(tài)地加快了非線性尺度空間的計(jì)算速度, 并且利用改進(jìn)的局部差分二進(jìn)制（M-LDB）[8]描述符，使其速度較KAZE 有很大提高，盡管如此，仍提高得不夠理想。故此提出一種改進(jìn)方法，選擇將SURF 特征點(diǎn)檢測(cè)與AKAZE 特征點(diǎn)描述相結(jié)合，并利用漢明距離對(duì)圖像進(jìn)行粗匹配，利用RANSAC 算法[9]剔除誤匹配點(diǎn)，使得算法在匹配速度及一些變換圖像的魯棒性方面[10-11]有進(jìn)一步的提高。

2 AKAZE算法原理

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

AKAZE 算法以各向異性的非線性濾波來(lái)構(gòu)造尺度空間，非線性擴(kuò)散濾波通常采用偏微分方程進(jìn)行求解。經(jīng)典非線性擴(kuò)散方程如下：

式中，div 和? 分別為散度與梯度，L 為圖像的亮度,c(x,y,t)為傳導(dǎo)函數(shù)。時(shí)間t 是尺度參數(shù)，數(shù)值越大表示圖像形式越簡(jiǎn)單。

1) 構(gòu)建非線性尺度空間

AKAZE 算法構(gòu)建非線性尺度空間策略與經(jīng)典SIFT 算法類似，其組數(shù)為o，每組的層數(shù)為S。通過(guò)以下公式將組數(shù)索引和層數(shù)索引映射到對(duì)應(yīng)的尺度σ（像素）上[12]：

式中：M 是濾波圖像的總數(shù)。由于非線性擴(kuò)散濾波作用于時(shí)間序列上，需將以像素為單位的尺度參數(shù)σi映射到以時(shí)間為單位的尺度參數(shù)ti,公式如下：

接著利用FED 算法求解式(1)，即可得到非線性尺度圖像，其式如下：

式中，I 為單位矩陣，A(Li)為圖像Li的傳導(dǎo)矩陣,τ 為時(shí)間步長(zhǎng)，n 為顯式擴(kuò)散步數(shù)。

2) 定位特征點(diǎn)

尋找不同尺度歸一化后Hessian 矩陣的行列式的局部極大值點(diǎn)，把采樣點(diǎn)的響應(yīng)值與同尺度的8個(gè)鄰域點(diǎn)及相鄰尺度的2×9 個(gè)鄰域點(diǎn)比較判斷是否為最大值，然后將二維二次函數(shù)擬合到3×3 像素鄰域內(nèi)Hessian 響應(yīng)的行列式上，得到亞像素級(jí)精度的關(guān)鍵點(diǎn)的二維位置，如下式：

式中，σi，norm=σi/2σi，為對(duì)應(yīng)圖像組中歸一化尺度因子，Lxx和Lyy分別為二階橫向和縱向微分，Lxy為二階交叉微分。

3) 判斷特征點(diǎn)主方向

與SURF 算法相似，在梯度圖像上以特征點(diǎn)為中心，在半徑為6σ 范圍內(nèi)，取特征點(diǎn)鄰域的一階微分值Lx和Ly并對(duì)其進(jìn)行高斯加權(quán)，接著用π/3 的扇形繞原點(diǎn)旋轉(zhuǎn)并計(jì)算該扇形向量和，主方向即為扇形向量和中的最長(zhǎng)矢量方向。

2.2 特征點(diǎn)描述與匹配

二進(jìn)制描述符（如BRIEF、ORB 和BRISK）最近得到了廣泛的應(yīng)用，因?yàn)樗鼈兛梢詫?shí)現(xiàn)高效的計(jì)算和匹配。然而，這些二進(jìn)制描述符利用過(guò)度簡(jiǎn)化的信息，即用于二進(jìn)制測(cè)試的圖像塊內(nèi)的像素子集的原始強(qiáng)度，因此辨別能力不高。AKAZE 算法利用一種局部差分二進(jìn)制描述符（M-LDB）,該描述符遵循和BRIEF 相同的原理，但在區(qū)域平均值之間使用二進(jìn)制測(cè)試而不是單個(gè)像素，以獲得額外的魯棒性。

以任意給出的某圖像為例，LDB 將圖像分成n×n 個(gè)相等大小的網(wǎng)格單元并從每個(gè)網(wǎng)格單元中提取平均強(qiáng)度和一階梯度，如圖1(a)所示，用于計(jì)算直立的描述符；而M-LDB 描述符根據(jù)特征點(diǎn)主方向，將LDB 所劃分的網(wǎng)格單元做相應(yīng)旋轉(zhuǎn)使其旋轉(zhuǎn)到主方向上，如圖1(b)所示，然后計(jì)算每個(gè)網(wǎng)格的平均強(qiáng)度和梯度，各公式如下：

式中，m 為網(wǎng)格i 的總數(shù)，Iavg(i)為各網(wǎng)格單元的平均強(qiáng)度，dx(i)和dy(i)分別為網(wǎng)格i 區(qū)域的x 和y 方向的梯度。然后，LDB 分別比較成對(duì)網(wǎng)格單元之間的平均強(qiáng)度和梯度，根據(jù)比較結(jié)果，相應(yīng)地設(shè)為0 或者1。其公式如下：

利用M-LDB 算子生成結(jié)果的是由0 和1 組成的二進(jìn)制描述符，最終使用兩幅圖片特征點(diǎn)二進(jìn)制描述符的漢明距離進(jìn)行暴力匹配，生成匹配結(jié)果。

圖1 圍繞一個(gè)特征點(diǎn)的二進(jìn)制測(cè)試網(wǎng)格劃分

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

AKAZE 算法雖然利用了二進(jìn)制描述符，但由于特征點(diǎn)檢測(cè)部分是用非線性濾波來(lái)構(gòu)造尺度空間，因此匹配速度較慢。為提高匹配速度，現(xiàn)將SURF 特征點(diǎn)檢測(cè)與AKAZE 算法的M-LDB 描述符相結(jié)合，來(lái)實(shí)現(xiàn)圖像特征匹配。

3.1 基于Hessian矩陣的特征點(diǎn)檢測(cè)

利用Hessian 矩陣檢測(cè)特征點(diǎn)的方法是去計(jì)算圖像所有像素的Hessian 矩陣的行列式，極值點(diǎn)處就是圖像特征點(diǎn)所在的位置。

設(shè)圖像I 中有某點(diǎn)X=(x,y),則在該點(diǎn)處，尺度為σ 的Hessian 矩陣為：

式中，Lxx=(X,σ)是高斯濾波后的圖像點(diǎn)X 在x 方向上的二階導(dǎo)數(shù)，Lyy=(X,σ)和Lxy=(X,σ)具有相似的含義。在構(gòu)造Hessian 矩陣時(shí)應(yīng)先進(jìn)行高斯濾波，再計(jì)算二階導(dǎo)數(shù)。SURF 算法使用盒式濾波器來(lái)代替高斯函數(shù)，大大提高了運(yùn)算速度。近似處理的效果如圖2 所示。

圖2 對(duì)高斯函數(shù)的近似處理

其中，圖2(a)、(b)、(c)分別為沿x 方向、y 方向、xy方向的高斯二階微分算子, 即Lxx模板、Lyy模板、Lxy模板；圖2(d)、(e)、(f)分別為盒式濾波器Dxx模板、Dyy模板、Dxy模板。在盒式濾波器中，白色部分的權(quán)值為1，灰色部分的權(quán)值為0，Dxx和Dyy中黑色部分的權(quán)值為-2，Dxy中黑色部分的權(quán)值為-1。Dxx，Dyy和Dxy可通過(guò)積分圖像求得。可用以下公式來(lái)近似計(jì)算Hessian 矩陣的行列式：

式中，ω 為權(quán)值，被用來(lái)平衡因子近似所帶來(lái)的偏差，其值為0.9。據(jù)此即可利用公式(12)得到每個(gè)像素點(diǎn)的Hessian 矩陣的行列式值的近似值。

為了使檢測(cè)到的特征點(diǎn)具有尺度不變性，通過(guò)改變盒式濾波器模板的大小，對(duì)圖像進(jìn)行濾波，以產(chǎn)生多幅不同尺度的圖片；并通過(guò)公式(12)計(jì)算出不同尺度圖像下所有像素的Hessian 矩陣的行列式值。具體步驟為：首先取閾值，保留那些行列式值高的像素；然后將要檢測(cè)的像素與其鄰域的26 個(gè)像素點(diǎn)的行列式值做比較，去掉不是最大值的點(diǎn)；最后利用插值法來(lái)確定特征點(diǎn)的位置。

為獲得旋轉(zhuǎn)不變性，SURF 算法通過(guò)統(tǒng)計(jì)特征點(diǎn)鄰域內(nèi)的Haar 小波特征確定其主方向。首先以特征點(diǎn)為中心，計(jì)算特征點(diǎn)鄰域（如半徑為6s 的圓，s為該點(diǎn)所在尺度）內(nèi)的點(diǎn)在x,y 方向的Haar 小波響應(yīng)[13]，用它即可以檢測(cè)出x 方向和y 方向上的梯度。Haar 小波邊長(zhǎng)取4s，這樣每個(gè)扇形都得到了一個(gè)值。然后用60°扇形以一定間隔進(jìn)行旋轉(zhuǎn)，將60°范圍內(nèi)的響應(yīng)相加以形成新的矢量，歷遍整個(gè)圓形區(qū)域，選擇最長(zhǎng)矢量的方向?yàn)樵撎卣鼽c(diǎn)的主方向，如圖3 所示。

圖3 梯度坐標(biāo)系內(nèi)求方向

3.2 特征描述與匹配

在計(jì)算描述符之前，首先將不同尺度圖像以特征點(diǎn)為中心分成n×n 的小塊，并將圖像旋轉(zhuǎn)到主方向上，接著利用2.2 節(jié)所描述的AKAZE 特征描述方法來(lái)得到描述符，然后使用二進(jìn)制描述符的漢明距離進(jìn)行暴力匹配，得出匹配結(jié)果。在得出匹配結(jié)果之后，使用RANSAC 算法剔除誤匹配點(diǎn)，得到準(zhǔn)確率較高的匹配圖像。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

使用牛津數(shù)據(jù)集中的不同模糊程度圖像（blurbikes）、不同程度的JPEG 壓縮圖像（JPEG ubc）、不同光照強(qiáng)度圖像（light.Leuven）、不同視角下的圖像（viewpoint.graf）,每種圖像變換的程度由從小到大的6 張圖片組成，通過(guò)第一張圖片與其后的5張圖片匹配得出匹配結(jié)果，把它們定義為第1～5組，對(duì)比它們的匹配時(shí)間與正確率。其中匹配時(shí)間是通過(guò)取30 次匹配時(shí)間的平均值得出的，匹配正確率是取30 次匹配正確率的平均值得出的。

實(shí)驗(yàn)中，所用的電腦為Windows 10 系統(tǒng)，處理器為Intel（R）Core（TM）i5-3210M, 64 位操作系統(tǒng)，內(nèi)存為4.00GB，并使用Visual Stdio 2015 進(jìn)行實(shí)驗(yàn)。

4.2 各變化條件下圖像

匹配結(jié)果及分析

不同模糊程度的圖像的匹配時(shí)間與匹配正確率的對(duì)比情況如表1、表2 所示。

表1 不同模糊圖像匹配時(shí)間

表2 不同模糊圖像匹配正確率

從表1，表2 可以看出，在不同程度的圖像模糊條件下，在匹配速度方面，本算法比SURF 的匹配速度平均快了近3 倍，比AKAZE 算法快了近8 倍；在匹配準(zhǔn)確率方面，本文算法的正確率明顯比SURF算法高，比AKAZE 算法相比也有小幅度提高。

不同JPEG 壓縮圖像的匹配時(shí)間與匹配正確率對(duì)比情況如表3、表4 所示。

表3 不同JPEG壓縮圖像匹配時(shí)間

表4 不同JPEG壓縮圖像匹配正確率

從表3、表4 可以看出，在不同程度的圖像壓縮條件下，在匹配速度方面，本算法比SURF 的匹配速度平均快了2 倍多，比AKAZE 算法快了近7 倍；在匹配準(zhǔn)確率方面，本算法比SURF 算和AKAZE 算法都要更高。

不同光照強(qiáng)度圖像的匹配時(shí)間與匹配正確率對(duì)比情況如表5、表6 所示。

表5 不光照強(qiáng)度圖像匹配時(shí)間

表6 不光照強(qiáng)度圖像匹配正確率

從表5、表6 可以看出，在不同光照強(qiáng)度的圖像匹配中，在匹配速度方面，本算法比SURF 的匹配速度平均快了近3 倍，比AKAZE 算法快了7 倍多；在匹配正確率方面，本算法在光照強(qiáng)度變化較小時(shí)，比SURF 算法和AKAZE 算法都高，但是在光照強(qiáng)度變化較大時(shí)，正確率還有待提高。

不同視角圖像的匹配時(shí)間與匹配正確率對(duì)比情況如表7、表8 所示。

表7 不同視角圖像匹配時(shí)間

表8 不同視角圖像匹配正確率

從表7、表8 可以看出，在圖像的視角變化中，在匹配速度方面，本算法比SURF 的匹配速度平均快了2 倍多，比AKAZE 算法快了6 倍多；在匹配正確率方面，本文算法比SURF 算和AKAZE 算法都有明顯提高。

5 結(jié)束語(yǔ)

在提出的算法改進(jìn)中，將SURF 算法與AKAZE算法相結(jié)合，在SURF 特征點(diǎn)檢測(cè)部分采用盒式濾波器以代替高斯函數(shù)進(jìn)行濾波，提高了特征點(diǎn)檢測(cè)速度；而AKAZE 的特征點(diǎn)描述部分采用二進(jìn)制描述符，匹配時(shí)使用漢明距離，速度也很快。由此可見(jiàn)，兩者結(jié)合后，算法的匹配速度比SURF 算法和AKAZE 算法提高很多。在不同模糊程度、不同JPEG壓縮、不同視角下的圖像匹配中，改進(jìn)后的算法的匹配精度也比SURF 算法與AKAZE 算法更高。目前還存在著在不同光照強(qiáng)度下匹配精度較另外兩種算法為差的問(wèn)題，對(duì)此如何解決，也將成為后續(xù)研究的重點(diǎn)。