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

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

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

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

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

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

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

1.1 提取特征點(diǎn)

SURF 算法采用Hessian 矩陣行列式來(lái)檢測(cè)特征點(diǎn),每一個(gè)像素點(diǎn)都可以求出一個(gè)Hessian 矩陣：

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

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

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

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

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

圖1 尺度空間對(duì)比

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

圖2 極值點(diǎn)檢測(cè)

1.3 確定特征點(diǎn)方向

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

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

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

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

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

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

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

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

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

2.1 基于局部熵的SURF 算法特征點(diǎn)檢測(cè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 光照條件下魯棒性比較

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

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

圖6 光照變化匹配效果圖

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

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

3.2 模糊條件下魯棒性比較

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

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

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

圖7 模糊變化匹配效果圖

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

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

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

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

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

圖8 JPEG 壓縮魯棒性效果圖

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

4 總結(jié)

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