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

陳雪松,陳秀芳,畢 波,唐錦萍

1(東北石油大學(xué) 電氣信息工程學(xué)院,大慶 163318)

2(海南醫(yī)學(xué)院 公共衛(wèi)生學(xué)院,海口 571101)

3(黑龍江大學(xué) 數(shù)據(jù)科學(xué)與技術(shù)學(xué)院,哈爾濱 150080)

圖像匹配[1]是計算機(jī)視覺中的重要研究技術(shù)之一,是一種圖像處理技術(shù).目前,圖像匹配的兩種主流方法可以分為：基于像素灰度[2]的圖像匹配和基于特征[3]的圖像匹配.前者就是逐像素地把一個實時圖像窗口的灰度矩陣與參考圖像的所有可能的窗口灰度矩陣按某種相似性度量方法進(jìn)行搜索比較的匹配方法,包括絕對誤差和算法SAD (Sum of Absolute Differences)[4]、誤差平方和算法SSD (Sum of Squared Differences)[5]、歸一化積相關(guān)算法NCC (Normalized Cross Correlation)[6]等,但是該類匹配算法計算量較大,且對噪聲敏感,導(dǎo)致匹配效果很差；基于特征的匹配方法是在原始圖像中提取特征,然后用相似性度量和一些約束條件確定幾何變換,最后將該變換作用于待匹配圖像,包括SUSAN(Small Univalve Segment Assimilating Nucleus)角點檢測[7]、Harris 角點檢測[8]等方法.現(xiàn)有的基于特征的匹配方法雖然可以解決旋轉(zhuǎn)、平移等問題,但是,當(dāng)存在復(fù)雜變化時,如：大尺度、光照、模糊等,都會使得上述方法失效.2004年,Low 提出了一種尺度不變特征變換算法SIFT (Scale Invariant Feature Transform)[9,10],該算法對尺-度、旋轉(zhuǎn)、縮放、仿射變換等具有不變性,而且有很好的穩(wěn)定性和魯棒性,但是SIFT 算法復(fù)雜度較高,計算量很大,需要耗費較長時間完成特征描述和匹配.因此,Bay 等針對SIFT 算法的不足提出了改進(jìn)算法SURF (Speeded Up Robust Features),SURF[11,12]算法具有良好的魯棒性,速度也比SIFT 提高了3 倍左右.但是由于目前的SURF 算法存在錯誤匹配的問題,使得匹配結(jié)果的準(zhǔn)確度有所降低,速度也會由于不穩(wěn)定特征點及誤匹配對的存在而大大減慢,本文基于SURF 提出了一種優(yōu)化算法,并通過Matlab語言進(jìn)行了算法的實現(xiàn),分析其在光照、模糊、JPEG壓縮變化下的魯棒性.

1 傳統(tǒng)SURF 算法特征檢測與匹配

1.1 提取特征點

SURF 算法采用Hessian 矩陣行列式來檢測特征點,每一個像素點都可以求出一個Hessian 矩陣：

其中,L(x,δ)是經(jīng)過高斯濾波器、二階微分在點X=(x,y)處和圖像I的卷積.Lxx(x,δ)、Lyy(x,δ)有類似的含義.為了提高運(yùn)算速度,SURF 使用盒式濾波器(box filter)來近似高斯濾波器,卷積運(yùn)算后的值分別為Dxx、Dyy、Dxy,因此,Hessian 矩陣的行列式最終簡化為：

其中,det(H)表示點X附近區(qū)域的盒式濾波響應(yīng)值,用它檢測極值點.為了平衡因使用盒式濾波器近似所帶來的誤差,在Dxy上乘了一個加權(quán)系數(shù)ω,ω一般取值為0.9.因此每個像素的Hessian 矩陣判別式的近似值為：

盒式濾波器對圖像的濾波轉(zhuǎn)化成計算圖像上不同區(qū)域間像素和的加減運(yùn)算問題,只需要簡單幾次查找積分圖就可以完成.

1.2 在尺度空間中實現(xiàn)特征點定位

為了獲得不同尺度的采樣點,需要構(gòu)建圖像的尺度空間,在尺度空間上提取特征點.SURF 的尺度空間是由O組L層組成,同一組間不同層間使用相同尺寸的濾波器,但是濾波器的模糊系數(shù)逐漸增大.如圖1所示,圖1(a)是傳統(tǒng)方式建立的金字塔結(jié)構(gòu)；圖1(b)是SURF 算法的金字塔結(jié)構(gòu),它使原始圖像保持不變而只改變?yōu)V波器大小.

圖1 尺度空間對比

SURF 特征點的定位是在不同尺度特征點的響應(yīng)圖像上采用鄰域非極大值抑制,將每個像素點與二維圖像空間和尺度空間鄰域內(nèi)的26 個點進(jìn)行比較,選出特征點候選點；再利用三維線性插值法對候選點進(jìn)行定位,獲得亞像素級別的特征點,由此完成特征點的提取.具體過程如圖2所示.

圖2 極值點檢測

1.3 確定特征點方向

為了滿足旋轉(zhuǎn)不變性,必須確定特征點的主方向.具體做法是統(tǒng)計特征點領(lǐng)域內(nèi)的Haar 小波特征,即在特征點的領(lǐng)域內(nèi),統(tǒng)計60 度扇形內(nèi)所有點的水平Haar小波特征和垂直Haar 小波特征總和,這樣一個扇形就得到了一個響應(yīng)值.將響應(yīng)值分別加起來,形成矢量,選擇其中最長的矢量方向,作為最終特征點的主方向.該過程的示意圖如圖3所示.

圖3 特征點主方向

1.4 構(gòu)建特征描述子實現(xiàn)匹配

特征點確定之后,就要根據(jù)特征點構(gòu)建描述子.具體做法是在特征點周圍取一個4×4 的矩形區(qū)域塊,所取得矩形區(qū)域方向是沿著特征點的主方向.每個子區(qū)域統(tǒng)計25 個像素的水平方向和垂直方向的Haar 小波特征.把Haar 小波值作為每個子塊區(qū)域的特征向量,所以一共有4×4×4=64 維向量作為SURF 特征的描述子.具體過程見圖4.

根據(jù)描述子進(jìn)行特征匹配,傳統(tǒng)SURF 是通過計算兩個特征點間的歐式距離來確定匹配度,實現(xiàn)匹配,歐氏距離越短,代表兩個特征點的匹配度越好.

2 改進(jìn)的SURF 算法

SURF 算法分為特征檢測和特征匹配兩個階段,在特征檢測階段,由于存在錯誤檢測,使得一些誤點被檢測為特征點,降低匹配精度.在匹配階段,錯誤的匹配對的存在,使得匹配精度降低的同時,增加了計算量.本文針對這兩個階段對SURF 算法進(jìn)行了改進(jìn),在特征點檢測階段,引入圖像的局部二維熵[13,14],從降低冗余信息出發(fā),實現(xiàn)對不穩(wěn)定特征點的剔除.在匹配階段,引用曼哈頓距離[15]代替?zhèn)鹘y(tǒng)的歐式距離,降低復(fù)雜度,減少計算量,并引入最近鄰和次近鄰[16]的概念實現(xiàn)特征匹配.改進(jìn)算法和原始SURF 算法圖像特征匹配流程圖如圖5所示.

圖4 構(gòu)建特征描述子

圖5 改進(jìn)SURF 算法和原算法特征匹配對比流程圖

2.1 基于局部熵的SURF 算法特征點檢測

圖像熵[17],一種特征的統(tǒng)計形式,反映了圖像中包含平均信息量的多少,當(dāng)圖像為純色圖時(純白或者純黑圖),圖像就只包含一種灰度值,此時熵最小,H=0,認(rèn)為圖像的信息量為0.當(dāng)圖像包含多個灰度值時,也就是說圖像每個像素的灰度值都不一樣,此時熵最大,H=lgN,認(rèn)為圖像息量最大.因此我們可以認(rèn)為圖像的熵H越大,圖像包含的像素灰度越豐富,灰度分布越均勻,圖像的包含的目標(biāo)越多,其信息量越大,反之亦然.目前,圖像信息熵已經(jīng)廣泛用于顯著性區(qū)域提取、圖像分割等.圖像的一維熵表示圖像中灰度分布的聚集特征所包含的信息量,但是卻不能反映圖像灰度分布的空間特征,為了表征這種空間特征,在一維熵的基礎(chǔ)上引入能夠反映灰度分布空間特征的特征量來組成圖像的二維熵.選擇圖像的鄰域灰度均值作為灰度分布的空間特征量,與圖像的像素灰度組成特征二元組,記為(i,j),其中i表示像素的灰度值(0 ≤i≤ 255),j表示領(lǐng)域灰度均值(0 ≤j≤ 255)：

式(4)能反映某像素位置上的灰度值與其周圍像素灰度分布的綜合特征,f(i,j)為特征二元組(i,j)出現(xiàn)的頻數(shù),N為圖像的尺度.定義離散的圖像二維熵為：

想要建立圖像特征點的局部二維熵[18],可以在特征點所包含信息量的前提下,突出反映該像素位置的灰度信息,以及其鄰域內(nèi)灰度分布的綜合特征.由圖像局部熵的特性,本文根據(jù)采樣點的局部二維熵來刻畫特征點的獨特性,檢測真正屬于特征的采樣點.特征點的局部鄰域二維熵越大,其與鄰域像素灰度值相差越大,即攜帶的信息量越大,特征點則更穩(wěn)定.具體策略如下：

(1)選擇某一采樣點的局部鄰域(本文用3×3 鄰域),計算該點鄰域二維熵,統(tǒng)計所有SURF 提取出的采樣點的局部鄰域二維熵.

(2)設(shè)置合適的閾值,當(dāng)采樣點的二維熵值大于閾值T1且小于閾值T2時,則認(rèn)為該點是特征點,否則剔除該點,實現(xiàn)特征點的篩選.

具體做法是根據(jù)二維熵定義計算待匹配圖和參考圖特征點位置的二維熵值,假設(shè)為Q,判斷其與閾值[T1,T2]的關(guān)系,若QT2,則認(rèn)為該點不是穩(wěn)定的點,予以刪除.通過遍歷圖像中的所有采樣點的二維熵值,得出大部分的熵值都在[2,4.5]之間,當(dāng)取值小于2 或者大于6 時,則難以剔除不穩(wěn)定的特征點,故本文選取T1=2,T2=4.5,選取閾值范圍內(nèi)的點,有效剔除一部分不穩(wěn)定的點.

2.2 基于曼哈頓距離的SURF 匹配算法

在匹配階段,SURF 算法是通過計算一幅圖像中所有特征點與另外一幅圖像中所有特征點之間的歐氏距離來實現(xiàn).SURF 特征描述符是64 維,遍歷計算所有對應(yīng)點的歐式距離,導(dǎo)致匹配階段的計算效率極低,為了減少計算量,本文從兩個方面來提高匹配階段的效率：

(1)用曼哈頓距離代替歐式距離,作為衡量特征點描述符相似度的標(biāo)準(zhǔn),減少了計算量.

(2)引入最近鄰與次近鄰比,減少特征點相似性比較過程中的次數(shù),降低時間復(fù)雜度.

2.2.1 曼哈頓距離代替歐式距離

n維點X=(x1,x2,x3,…,xn)與Y=(y1,y2,y3,…,yn)之間的歐式距離定義為：

二者的曼哈頓距離定義為：通過驗證我們可以知道,D1≥D0,而且根據(jù)定義不難看出D1的計算比D0簡單,SURF 的描述符是64 維的,對于每個特征點,需要計算64 次歐式距離,包含64次減法,64 次平方,64 次加法和一次開方；對于曼哈頓距離的計算則需要64 次減法,64 次絕對值運(yùn)算和63次加法運(yùn)算.顯然,曼哈頓距離比歐式距離少了開方運(yùn)算,極大地減少了計算量.

2.2.2 采用最近鄰次近鄰的特征匹配

為了排除因為圖像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點,引入最近鄰距離與次近鄰距離比進(jìn)行匹配：求取一幅圖像中的一個SURF 關(guān)鍵點X1,并找出其與另一幅圖像中某一特征點X2的曼哈頓距離,求其最近鄰C1和次近鄰C2,得出C1和C2的比值,記為 α,若該比值大于給定的匹配閾值T3而小于閾值T4,則認(rèn)為X1和X2是一對正確匹配對,否則認(rèn)為X1在待匹配圖像中沒有匹配點.對當(dāng)前圖像中的其他特征點重復(fù)X1尋找匹配點的過程,直到找到所有的匹配對,匹配過程完成.對于匹配閾值的選取,由于α的取值范圍為[0,1],本文通過多次對存在光照變化、模糊變化、JPEG 壓縮變化的兩幅圖進(jìn)行匹配,發(fā)現(xiàn)α取值在[0.3,0.75]時匹配效果最佳,小于0.3 時,很少有匹配點,大于0.75 時,則保留大量的錯誤匹配點,因此本文匹配閾值取T3=0.3,T4=0.75,保留閾值范圍內(nèi)的點,實現(xiàn)有效剔除一部分誤匹配對.

3 實驗結(jié)果與分析

為了驗證本文改進(jìn)算法的魯棒性,將Mikolajczyk[19]圖像庫中的數(shù)據(jù)作為測試數(shù)據(jù),采用計算機(jī)為i5 處理器,4 GB 內(nèi)存,進(jìn)行程序開發(fā),實驗驗證；本文用到了數(shù)據(jù)庫中的leuven、trees、ubc 圖像,分別在光照、模糊和JPEG 壓縮等條件下,對SURF 算法、BRISK 算法、Harris 算法與本文算法在匹配準(zhǔn)確率和時間上進(jìn)行比較分析,給出了算法的定量評估結(jié)果.

3.1 光照條件下魯棒性比較

不同光照下,圖像的某些特征會被弱化,本實驗通過將原圖與數(shù)據(jù)集中亮度變化最大的圖進(jìn)行匹配,觀察結(jié)果.光照變化匹配結(jié)果如圖6所示,數(shù)據(jù)分析如表1所示.其中,正確率=(正確匹配對數(shù)/總的匹配對數(shù)).

由匹配圖可知,SURF、BRISK、Harris 算法在進(jìn)行光照變化的匹配時,都有無序匹配對的存在,改進(jìn)后的算法相比于其他算法有更好的匹配效果,不存在無序匹配連線對.

圖6 光照變化匹配效果圖

表1 圖像光照變化匹配結(jié)果分析

分析表中數(shù)據(jù)易知,由于leuven 圖像光照變化較大,使得算法在待匹配圖中檢測到較少的特征點.SURF算法在特征檢測階段沒有剔除不穩(wěn)定點,BRISK、Harris及改進(jìn)后的算法對光照變化條件下的圖像能有效檢測特征點,并在特征點檢測階段剔除部分不穩(wěn)定的點；在匹配階段各個算法均對誤匹配點進(jìn)行了剔除.觀察數(shù)據(jù)可知本文算法與SURF、BRISK、Harris 相比,速度加快的同時正確率也得到了提高.

3.2 模糊條件下魯棒性比較

圖像模糊處理后,分辨率會降低,特征點的識別度也會隨之下降,本實驗用數(shù)據(jù)集中模糊度最高的的圖像與原圖匹配,實驗結(jié)果如圖7所示,數(shù)據(jù)分析如表2所示.其中,正確率=(正確匹配對數(shù)/總的匹配對數(shù)).

從匹配結(jié)果中可以看出,對于模糊條件下的匹配,SURF、BRISK、Harris 算法匹配效果都變得有些無序,本文改進(jìn)的算法,表現(xiàn)出更好的優(yōu)勢,幾乎不存在無序匹配對,直觀上來看匹配效果達(dá)到最好.

分析表2中的數(shù)據(jù),由數(shù)據(jù)可知,在對模糊圖像進(jìn)行特征檢測時,由于trees 圖像模糊度較大,在待匹配圖中檢測到的特征點數(shù)目較少.觀察數(shù)據(jù)可知SURF算法在特征點檢測階段沒有進(jìn)行誤點的剔除,BRISK、Harris 和本文改進(jìn)后的算法對模糊條件下的圖像進(jìn)行匹配時,能有效檢測特征點并在特征點檢測階段剔除部分不穩(wěn)定的特征點,在匹配階段,各算法都剔除部分誤匹配點.本文算法在速度上相比于SURF 有所加快,與BRISK、Harris 算法幾乎相當(dāng),正確率比SURF 算法高出將近20%,比BRISK、Harris 稍高,因此可以看出在處理模糊變化的圖像時,本文算法有更好的魯棒性.

圖7 模糊變化匹配效果圖

表2 圖像模糊變化匹配結(jié)果分析

3.3 JPEG 壓縮條件下魯棒性比較

對圖像進(jìn)行JPEG 壓縮,會使得圖像信息發(fā)生變化,JPEG 壓縮屬于有損壓縮,去掉了視角的冗余信息和數(shù)據(jù)本身的冗余信息,對壓縮處理最嚴(yán)重的圖像與原圖匹配,各個算法結(jié)果如圖8所示.數(shù)據(jù)分析總結(jié)如表3所示.其中,正確率=(正確匹配對數(shù)/總的匹配對數(shù)).

觀察匹配結(jié)果圖,對于JPEG 壓縮條件下的圖像匹配,幾種算法都達(dá)到良好的效果,SURF 和BRISK 存在少量錯誤無序匹配,Harris 相比之下無序?qū)?shù)較多,改進(jìn)后的算法幾乎無無序匹配對,匹配效果達(dá)到最好.

分析數(shù)據(jù)如表3所示,由數(shù)據(jù)可知,SURF 在特征點檢測階段沒有進(jìn)行不穩(wěn)定點的剔除,BRISK、Harris和改進(jìn)后的算法對JPEG 條件下的圖像匹配能有效檢測特征點并剔除部分誤點,由于JPEG 壓縮改變了圖像的信息,因此改進(jìn)算法采用局部熵對誤點進(jìn)行剔除時,能剔除更多無效的點；在匹配階段各個算法都進(jìn)行了誤匹配點的剔除.可以看到改進(jìn)后的算法與其他算法相比,正確率得到提高的同時,也減少了計算量.

圖8 JPEG 壓縮魯棒性效果圖

表3 JPEG 壓縮變化下的匹配結(jié)果分析

4 總結(jié)

本文在傳統(tǒng)SURF 算法圖像匹配的基礎(chǔ)上,提出了一種改進(jìn)算法,特征提取階段,結(jié)合了局部二維熵,用于剔除誤點；特征匹配階段,用曼哈頓距離代替歐式距離,降低計算復(fù)雜度,并引入了最近鄰和次近鄰比實現(xiàn)匹配.實驗結(jié)果表明,改進(jìn)后的算法能夠有效剔除誤點,減少誤匹配,降低匹配時間,與傳統(tǒng)算法相比,本文算法有很好的魯棒性和準(zhǔn)確率.