一種多特征融合的特征匹配算法

李國祥,王繼軍,馬文斌

(1.廣西財(cái)經(jīng)學(xué)院 教務(wù)處, 廣西 南寧 530003; 2.廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004; 3.廣西財(cái)經(jīng)學(xué)院 信息與統(tǒng)計(jì)學(xué)院, 廣西 南寧 530003)

圖像匹配是機(jī)器視覺重要的組成部分,其主要作用是確定不同視角、光照等條件下的圖像空間對應(yīng)關(guān)系,廣泛地應(yīng)用于圖像檢索、目標(biāo)追蹤、遙感圖像處理等領(lǐng)域。圖像描述子是當(dāng)前主要的圖像匹配方法,通過對不同特征點(diǎn)描述子間的相似性測量,完成不同特征點(diǎn)之間的匹配。其中最著名的莫過于SIFT[1]算子,以及眾多在此基礎(chǔ)之上的各種改進(jìn)算法。

PCA-SIFT[2]選定為以特征點(diǎn)為中心的41×41矩形,計(jì)算區(qū)域內(nèi)水平、垂直方向的偏導(dǎo)數(shù),形成該特征點(diǎn)3 042維的特征向量,計(jì)算圖像所有特征向量的協(xié)方差矩陣,生成投影矩陣從而將特征向量降至K維,并顯著地提升了SIFT的匹配性能。speeded up robust features(SURF)[3-4]對SIFT進(jìn)行了有效改進(jìn),使用不同尺寸快速海森矩陣檢測關(guān)鍵點(diǎn),同時利用harr小波響應(yīng)生成64維描述符,大幅提升了特征計(jì)算速度。Affine SIFT[5]是一種具備完全的仿射和尺度不變性的特征提取算法,不過其較高的計(jì)算復(fù)雜度,導(dǎo)致難以滿足實(shí)時性的要求。另外還有各類基于核函數(shù)和混合核函數(shù)的特征描述子。BRIEF[6]提供了新的特征描述算法,當(dāng)完成了特征點(diǎn)定位后，在領(lǐng)域塊中隨機(jī)挑選點(diǎn)對比較亮度值生成256位的二進(jìn)制編碼,但不具備旋轉(zhuǎn)不變性。ORB[7]將特征點(diǎn)提取FAST算法和特征點(diǎn)描述BRIEF結(jié)合在一起,并改進(jìn)了原BRIEF的旋轉(zhuǎn)不變性,特征生成的速度大幅提升,但在尺度方面效果較差。

另外就是通過核函數(shù)的方式生成特征描述子。文獻(xiàn)[8]通過核函數(shù)將圖像映射至RKHS中的高維向量,通過向量內(nèi)積完成2幅圖像相似性的度量；文獻(xiàn)[9]建立核函數(shù)描述子以笛卡爾坐標(biāo)和極坐標(biāo),梯度模和梯度方向、梯度方向與極坐標(biāo)角度差等特征信息為基礎(chǔ),通過傅里葉級數(shù)擬合將其映射為特征向量,最后使用克羅內(nèi)克積形成新的特征向量。還有通過選擇余弦核函數(shù)作為KPCA的映射核[10],對原SIFT向量降維至55維。

伴隨著深度學(xué)習(xí)在語音識別、自然語言處理、計(jì)算機(jī)視覺、圖像與視頻分析、多媒體等諸多領(lǐng)域的應(yīng)用取得成功,學(xué)者們提出了眾多基于深度學(xué)習(xí)特征描述:DeepDesc[11]、TFeat[12]、LIFT[13],然而近年來的一些研究證明,并非深度學(xué)習(xí)特征完全優(yōu)于傳統(tǒng)特征描述,文獻(xiàn)[14-15]通過大量的標(biāo)準(zhǔn)化對比實(shí)驗(yàn),驗(yàn)證了深度學(xué)習(xí)可能沒有比簡單方法產(chǎn)生足夠的額外效果,同時深度學(xué)習(xí)方法對于計(jì)算環(huán)境要求較高,在一定程度上限制了適用范圍。

結(jié)合上述研究,本文回歸至原始特征優(yōu)化的層面,以廣泛使用的SIFT算子為出發(fā)點(diǎn),通過選擇有效的核函數(shù)和簡單易行的映射變換,構(gòu)建一種可以適應(yīng)復(fù)雜環(huán)境變換的特征描述子,大幅度降低特征維度。

1 圖像核函數(shù)的空間映射

在圖像識別領(lǐng)域,完備的圖像特征對于大規(guī)模數(shù)據(jù)集帶來了巨大存儲和計(jì)算成本,原高維度特征的有效編碼聚合,顯得尤為重要。如Hamming Embedding[16]將原SIFT特征與聚類中心中值相減,形成新的64位二進(jìn)制聚合編碼,特征間的相似性測量就變成了二進(jìn)制的或運(yùn)算；Fisher Vectors[17]統(tǒng)計(jì)視覺詞典與局部特征的差異,利用似然函數(shù)的梯度向量表達(dá)圖像等。聚合編碼本質(zhì)在于單純的特征點(diǎn)信息，一方面使得特征維度較高,另一方面特征點(diǎn)所具有的信息量并不含有典型可區(qū)分性信息,有時甚至是負(fù)面的,冗余的信息量對于識別匹配帶來誤判;通過特征聚合來生成簡單具有代表性的特征表達(dá)。還有就是利用特征向量自身的數(shù)理特點(diǎn),從中提取主成分。文獻(xiàn)[18]使用PCA和白化對100 k詞表直方圖直接進(jìn)行降維,效果顯著;在原始特征的編碼和降維基礎(chǔ)上,文獻(xiàn)[19]引入徑向基核函數(shù)將圖塊映射為梯度、顏色和形狀的特征描述；文獻(xiàn)[20]使用Von Mises核函數(shù)完成角度向量的映射,結(jié)合上述思想,本文同樣通過核函數(shù)實(shí)現(xiàn)特征空間映射、降低特征維度、保證點(diǎn)對的匹配精度。

設(shè)圖像的特征向量集X={x1,…,xN},xi∈Rd,‖xi‖=1,Φ(xi)是特征向量xi在高維空間的映射,i=1,2,…,N。令Φ(X)={φ(x1)φ(x2) …φ(xN)}T,引入核函數(shù):

K=Φ(X)Φ(X)T=

(1)

原始空間模型在高維空間映射后為:

Φ(X)Φ(X)Tμ=λμ

(2)

其中:μ為矩陣K的特征向量;λ為矩陣K的特征值;N為原始特征維度。左右兩邊同時乘以一個Φ(X)T后,有

(Φ(X)TΦ(X))Φ(X)Tμ=λΦ(X)Tμ

(3)

約簡后的特征即為原始特征在歸一化的前n個特征值對應(yīng)特征向量上的投影，即

λ1≥λ2≥…≥λn

(4)

從而使得在低維度線性不可分的特征向量在高維空間變成線性可分,而高維空間中向量內(nèi)積演變?yōu)楹撕瘮?shù)值。其中核函數(shù)及其參數(shù)的選擇便成為了關(guān)鍵問題,理論上矩陣K是對稱半正定的即可以作為核函數(shù),比如常用的徑向基核函數(shù)、多項(xiàng)式核函數(shù)等,而這些核函數(shù)的選擇和優(yōu)化有些需要樣本數(shù)據(jù)多元正態(tài)分布[21],有些時間和空間復(fù)雜度較高,有些選擇后的核函數(shù)其高維空間映射并非線性可分?？紤]到一些核函數(shù)描述子通常轉(zhuǎn)化為線性內(nèi)積的形式,直接采用最簡單的線性核函數(shù)，即

k(x,y)=xTy

(5)

為了驗(yàn)證線性內(nèi)積核的簡單有效,這里將其與常用的徑向基核函數(shù)[19]、余弦核函數(shù)[10]進(jìn)行對比,如圖1、圖2所示。

雖然徑向基核函數(shù)在仿射變換上的表現(xiàn)優(yōu)于其他核,但是其對于光照、模糊等變換魯棒性較弱,關(guān)鍵是它的時間復(fù)雜度是簡單線性核的近10倍,如要在大規(guī)模數(shù)據(jù)集中開展實(shí)時運(yùn)算則比較困難，見表1所列,而余弦核函數(shù)對于仿射變換明顯表現(xiàn)效果欠佳。

圖1 Graffiti的不同核函數(shù)匹配

圖2 Car的不同核函數(shù)匹配

表1 不同核函數(shù)的時間復(fù)雜度比較 s

2 集成的特征提取算法

文獻(xiàn)[22]提出了RootSIFT、可區(qū)分的查詢擴(kuò)展和特征擴(kuò)充3種簡單的提高圖像檢索精度的方法。在特征描述子層面上,利用Hellinger kernel代替標(biāo)準(zhǔn)的Euclidean Distance進(jìn)行SIFT特征點(diǎn)相似性測量,完成SIFT空間到RootSIFT的映射,該映射對于進(jìn)一步的圖像檢索分類效果有明顯的提升。通過與文獻(xiàn)[14]大量對比試驗(yàn)證明了其特征的穩(wěn)健性,因此為了形成可以有效應(yīng)對復(fù)雜變換的特征,本文將其與核函數(shù)相結(jié)合,集成為一個新的低維度穩(wěn)健特征向量，如圖3所示。

設(shè)x、y為特征向量且‖x‖=1,‖y‖=1,則兩者的歐式距離可以表示為:

D(x,y)2=‖x-y‖2=

‖x‖2+‖y‖2-2xTy

(6)

通過Hellinger映射:

(7)

對特征向量x、y取平方根,從而將相似性測量的Euclidean Distance映射至Hellinger Distance,將該過程稱為Root，即

(8)

圖3 集成特征的提取流程

由于通過線性核函數(shù)映射后的主成分包含負(fù)值,無法直接取平方根,這里將主成分最小值設(shè)為原點(diǎn),將主成分向量在數(shù)軸上平移,使其相對距離保持不變。之后取平方根并對特征向量進(jìn)行α中心化,仿照文獻(xiàn)[23]將該過程稱為Shift，即

(9)

最后進(jìn)行Power-law歸一化,Power-law廣泛地應(yīng)用于BOW特征編碼、聚合等的歸一化[17-18,24],并對于特征表達(dá)有明顯的提升。形成新的穩(wěn)健特征向量，即

x:=sign(x)|x|β

(10)

3 實(shí) 驗(yàn)

為了驗(yàn)證集成描述子的有效性,這里實(shí)驗(yàn)數(shù)據(jù)庫采用仿射、尺度等變換的Affine Covariant Regions Datasets以及復(fù)雜場景的Oxford Buliding。

(1) Affine Covariant Regions Datasets。該數(shù)據(jù)集中,本文選擇仿射變換的Graffiti、模糊變換的bikes、尺度旋轉(zhuǎn)變換的boat以及光照變換的cars 4類圖像作為匹配圖像。實(shí)驗(yàn)中首先使用最近鄰距離和次近鄰距離的比率作為特征點(diǎn)的初次選擇,閾值為0.8。其次使用幾何校驗(yàn)作為特征點(diǎn)的二次篩選。選擇傳統(tǒng)的SIFT和AS(Hessian Affine[25]SIFT)作為基本的特征描述子,在基本描述子基礎(chǔ)上,本文提出的算法KPCA(linear)+RSP(Root+Shift+PowerLaw)分別與PCA、余弦核KPCA進(jìn)行了對比實(shí)驗(yàn)，見表2所列。通過實(shí)驗(yàn)選取最優(yōu)參數(shù),α=0.95,β=1.2，令投影矩陣維度n=55,結(jié)果如圖4所示,其中柱狀圖表示正確匹配的特征點(diǎn)數(shù)。

表2 時間復(fù)雜度對比 s

圖4 Affine Covariant Regions Datasets 匹配點(diǎn)對數(shù)量圖

根據(jù)上述實(shí)驗(yàn)可以看出,除了仿射變換Graffiti中SIFT和AS匹配效果有明顯的差異外,其他3類圖像兩者效果基本相同,而且原始方法與RSP的集成,都在一定程度上提升了描述子的穩(wěn)健性,說明了RSP的處理方法顯著有效,本文所集成的線性核降維+RSP算法則略高于同類算法或與其持平,而非線性的余弦核函數(shù)匹配的特征點(diǎn)數(shù)量相對下降,且計(jì)算時間增加明顯。

(2) Oxford Buliding。為了驗(yàn)證各算法在復(fù)雜變換環(huán)境下,特征算子的魯棒性,選擇圖像檢索領(lǐng)域中經(jīng)常使用的Oxford Buliding數(shù)據(jù)集。該數(shù)據(jù)集包含10類建筑,并根據(jù)標(biāo)的物在圖像中的效果分別標(biāo)記為good、ok、junk和bad。鑒于對特征穩(wěn)健性的驗(yàn)證,實(shí)驗(yàn)中使用query作為原始圖像,僅和ok標(biāo)記圖片進(jìn)行匹配,ok標(biāo)記代表了標(biāo)的物在圖像中呈現(xiàn)度大于25%,包含了各種復(fù)雜的視覺、尺度等變換。junk是標(biāo)的物對象少于25%可見的圖像,對于圖像特征點(diǎn)匹配來說,即便人工標(biāo)注部分圖像也難以分辨。bad圖像則與標(biāo)的物不相關(guān)。為了應(yīng)對場景中的復(fù)雜仿射變換,實(shí)驗(yàn)中使用Hessian Affine SIFT作為特征提取算子,選擇數(shù)據(jù)集ok列表中前6副圖像,共計(jì)50副圖像作對比。

圖5 All Souls 類別中ok標(biāo)記圖像的匹配效果

表3 匹配準(zhǔn)確率對比表%

表4 時間復(fù)雜度對比表 s

通過對比可以發(fā)現(xiàn),相對于其他方法,AS+RSP和本文方法能夠在復(fù)雜變換的環(huán)境中保證特征點(diǎn)的匹配精度,證明了RSP的確能在一定程度上保證特征穩(wěn)健。而線性核KPCA與之結(jié)合,在僅增加簡單計(jì)算的基礎(chǔ)上,通過設(shè)置投影矩陣維度,使得特征維度由原來的128維約簡至55維,契合了大數(shù)據(jù)集時間和空間的實(shí)時性要求。AS、PCA和余弦核KPCA對于復(fù)雜變換表現(xiàn)不夠穩(wěn)定,部分特征出現(xiàn)局部最小值導(dǎo)致誤匹配增加。

4 結(jié) 論

特征描述子的提取作為匹配的重要內(nèi)容,除了要具備基本的仿射、尺度、旋轉(zhuǎn)等不變性外,還要能夠在復(fù)雜場景中保證相對的穩(wěn)定。本文結(jié)合當(dāng)前眾多文獻(xiàn)的研究方法,從簡單易行、特征維度的降低和特征穩(wěn)健3個方面,提出一種多特征融合的匹配算法。利用線性內(nèi)積核映射原特征至高維空間提取主成分,減少特征冗余,解決特征維度過高的問題;利用Root、Shift和PowerLaw,在Hellinger空間對主成分平移和歸一化,解決特征穩(wěn)健性的問題。實(shí)驗(yàn)證明,相對于其他同類算法,該方法的匹配精度得到一定的提高,且魯棒性較強(qiáng)。