基于擴(kuò)展結(jié)構(gòu)相似性的特征匹配方法

, ,

(1.重慶工程學(xué)院 科技處,重慶 400056; 2.重慶市數(shù)字影視與新媒體工程技術(shù)研究中心,重慶 400056)

0 概述

從圖像和視頻中提取特征進(jìn)行匹配或比較,是計(jì)算機(jī)視覺(jué)處理的基本過(guò)程,可應(yīng)用于關(guān)鍵點(diǎn)匹配[1-2]、信息檢索[3]和信息分類[4]等方面。近些年,特征匹配也廣泛應(yīng)用于場(chǎng)景解析或通過(guò)SIFT flow進(jìn)行的光流估計(jì)中。相似性度量方法基于特征之間的相似性實(shí)現(xiàn)特征匹配,隨著特征提取方法的發(fā)展,相似性度量方法的研究成為熱點(diǎn)。

歐式距離是最常用的相似性度量方法,其計(jì)算特征向量在歐式空間的二范數(shù)距離[5]。然而,取決特征提取方法的差異性,特征向量并非遍及整個(gè)歐氏空間分布,而是局限于該特征相應(yīng)提取方法內(nèi)在約束的子空間。因此,通過(guò)利用特征的內(nèi)在特性,歐式距離之外的相似性度量方法被提出。衍生自統(tǒng)計(jì)學(xué)卡方檢驗(yàn)的卡方距離[6]是一種常用的基于直方圖特征的度量方法,其也可利用核函數(shù)進(jìn)行處理[7]。為了解決運(yùn)輸?shù)膬?yōu)化問(wèn)題,文獻(xiàn)[8]提出推土機(jī)距離以對(duì)直方圖特征之間的相異性進(jìn)行有效的度量,但該方法需要耗費(fèi)極大的計(jì)算成本。歐式距離和卡方距離僅僅由直方圖相應(yīng)組中的差分所組成,推土機(jī)距離則考慮到直方圖的組間關(guān)系。擴(kuò)散距離度量方法也應(yīng)用這樣的跨組距離思想,其基于直方圖特征的結(jié)構(gòu)而非一個(gè)簡(jiǎn)單的向量[9-10]。

作為與特征匹配相近的領(lǐng)域,圖像質(zhì)量評(píng)價(jià)要求圖像間相似性度量方法應(yīng)與人類感知相近。而歐式距離與人類感知不相容,并不適用于圖像相似性度量。研究人員根據(jù)人類視覺(jué)系統(tǒng)提出了結(jié)構(gòu)相似性(Structural Similarity,SSIM)度量[11-12]。與人類的視覺(jué)過(guò)程相同,該方法通過(guò)利用圖像分塊間的結(jié)構(gòu)特征,對(duì)參考圖像與其畸變圖像之間的相似性進(jìn)行度量。但SSIM度量方法局限于結(jié)構(gòu)化陣列形式,魯棒性較差,而特征匹配則對(duì)魯棒性要求較高。

針對(duì)上述問(wèn)題,本文不局限于非負(fù)數(shù)的直方圖形式,提出一種多維向量結(jié)構(gòu)的相似性度量方法——擴(kuò)展結(jié)構(gòu)相似性(Extended Structural Similarity,ESSIM)。在網(wǎng)格空間中提取局部基元特征的三階張量,并將該種特征結(jié)構(gòu)應(yīng)用于相似性度量中,以提高其魯棒性并保留SSIM的辨識(shí)能力。

1 結(jié)構(gòu)相似性

本文主要介紹在圖像質(zhì)量評(píng)價(jià)中SSIM的公式化表示,及其對(duì)特征匹配的適用性。已知參考圖像Ix,通過(guò)對(duì)目標(biāo)圖像Iy與Ix間的相似性進(jìn)行度量,以對(duì)Xy的圖像質(zhì)量進(jìn)行評(píng)價(jià)。SSIM分別從圖像Ix和Iy中提取成對(duì)圖像分塊x和y,計(jì)算式(1)的相似性度量值S;然后,對(duì)整個(gè)圖像的分塊得分S求平均,得到圖像Ix和Iy間的相似度。

S(x,y)=l(x,y)c(x,y)s(x,y)

(1)

l(x,y)=k(u(x),u(y))

(2)

c(x,y)=k(q(x),q(y))

(3)

(4)

(5)

在式(1)～式(5)中,u(x)和q(x)分別為圖像塊x和y中像素的均值和標(biāo)準(zhǔn)偏差函數(shù),k(a,b)為標(biāo)量a和b間的相似性測(cè)量函數(shù)。

函數(shù)l、c和s分別對(duì)圖像分塊中的亮度、對(duì)比度和結(jié)構(gòu)信息的相似度進(jìn)行測(cè)量。與跨組距離類似,結(jié)構(gòu)相似度s(x,y)提取像素間的相關(guān)系數(shù),其對(duì)于像素間的仿射關(guān)系(yi=αxi+β,(α>0))總是給出最大相似性得分(即等于1),所以對(duì)像素變化的魯棒性過(guò)高,不能給出令人滿意的相似性度量結(jié)果。對(duì)其進(jìn)行補(bǔ)償,引入相似度l和c,以捕捉亮度變化(偏差β)和對(duì)比度變化(比例α),這些度量方式均與人類感知系統(tǒng)相關(guān)。

同時(shí),作為歐氏空間中的一種簡(jiǎn)單的相似性度量方式,點(diǎn)積可以進(jìn)行式(6)所示的分解。

xTy=D{q(x)q(y)s(x,y)+u(x)u(y)}

(6)

與式(1)形式不同,但具有相關(guān)性,即亮度和對(duì)比度相似性分別退化為簡(jiǎn)單積u(x)u(y)和q(x)q(y)?？梢钥闯?亮度相似性被分離為一種加法形式,這種公式化表示存在于SSIM變體中[13]。因此,基于式(1)和式(4)的比較,可以得出SSIM的出色性能很大程度上基于式(5)的處理。

2 本文方法

本文基于SSIM度量,提出一種新的用于特征匹配的相似性度量方法。最簡(jiǎn)單的方式是直接將特征向量x和y輸入式(1)中進(jìn)行匹配評(píng)價(jià)。這種方法的效果并不好,盡管特征匹配與圖像質(zhì)量評(píng)價(jià)都建立于相似性度量之上,但對(duì)魯棒性的需求標(biāo)準(zhǔn)不同。SSIM通過(guò)對(duì)圖像細(xì)微變化的有效表達(dá),廣泛應(yīng)用于對(duì)目標(biāo)圖像的失真度測(cè)量;特征匹配要求對(duì)目標(biāo)圖像本身進(jìn)行辨識(shí),同時(shí)對(duì)畸變具有較高的魯棒性。因此,本文結(jié)合SSIM的優(yōu)勢(shì)和特征匹配的要求,提出一種擴(kuò)展結(jié)構(gòu)相似性(Extended Structural Similarity,ESSIM)的特征相似性度量方法,其不僅保留了SSIM的辨識(shí)能力,同時(shí)提高了SSIM所缺少的魯棒性。

傳統(tǒng)方法假設(shè)特征為直方圖形式,本文則將特征公式化到結(jié)構(gòu)化形式,如三階張量。本文提出的方法利用固有的特征結(jié)構(gòu),并改進(jìn)相似性度量函數(shù)以提高特征魯棒性。

2.1 特征結(jié)構(gòu)

(7)

圖1 子特征結(jié)構(gòu)示意圖

(8)

(9)

4)元素/立方體:在最小結(jié)構(gòu)的情況下,本文將每個(gè)特征元素xijk設(shè)為子特征,則得出相似性度量如式(10)所示。

(10)

2.2 相似性度量

原始的SSIM定義為亮度均值l、對(duì)比度方差c和結(jié)果相關(guān)性s3種相似性函數(shù)的積,如式(11)所示。這三者共同的乘積對(duì)這些統(tǒng)計(jì)數(shù)據(jù)的任何畸變均具有敏感性,這有利于圖像評(píng)價(jià),但在特征匹配中則缺乏魯棒性。從魯棒性的角度出發(fā),本文提出了式(11)的幾種SSIM度量的變體,如式(12)～式(15)所示。

原始形式:

Sorg=l×c×s

(11)

分離l:

S+l=wll+ws(c×s)

(12)

分離c:

S+c=wcc+ws(l×s)

(13)

分離s:

S+s=wss+wl(l×c)

(14)

全相加:

Sadd=wll+wcc+wss

(15)

式中引入權(quán)值,以平衡加和形式。式(12)與式(6)結(jié)構(gòu)相同,將相似性的亮度均值l分離到加性項(xiàng)內(nèi)。這些權(quán)值基于相似性函數(shù)的數(shù)值范圍而確定,如式(16)所示。

(16)

如果擾動(dòng)孤立地出現(xiàn)在l、c和s3項(xiàng)中,則全相加形式Sadd可最大限度地抑制其對(duì)最終相似性度量的影響。因此,本文使用張量結(jié)構(gòu)(式(9))的全相加相似性度量方法(式(15)),其通過(guò)加和形式提高魯棒性,并且有利于特征映射進(jìn)行降維處理。

2.3 顯式特征映射

(17)

(18)

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

本文實(shí)驗(yàn)首先通過(guò)關(guān)鍵點(diǎn)匹配對(duì)本文方法的性能進(jìn)行分析,然后應(yīng)用于圖像檢索。

3.1 關(guān)鍵點(diǎn)匹配

本節(jié)實(shí)驗(yàn)測(cè)試本文方法對(duì)局部描述子特征的關(guān)鍵點(diǎn)匹配的性能。局部描述子通常利用局部空間布局公式化一個(gè)結(jié)構(gòu)化張量。本文使用SIFT的三階張量空間布局8(I)×4(J)×4(k);對(duì)Mikolajczyk & Schmid數(shù)據(jù)集進(jìn)行實(shí)驗(yàn);該數(shù)據(jù)集包括8個(gè)圖像集,每個(gè)集合由1個(gè)參考圖像和5個(gè)從不同角度和尺寸捕捉到的畸變圖像。本文基于平均精度,即正確匹配的描述子對(duì)的比例對(duì)性能進(jìn)行評(píng)價(jià)。

3.1.1 特征結(jié)構(gòu)

本節(jié)實(shí)驗(yàn)統(tǒng)一使用式(11)相似性度量S=Sorg對(duì)不同類型的子特征結(jié)構(gòu)(如圖1所示)進(jìn)行評(píng)估。以張量結(jié)構(gòu)為基礎(chǔ),與其他子特征結(jié)構(gòu)進(jìn)行比較,結(jié)果如圖2所示。橫軸和縱軸的坐標(biāo)分別表示2種比較方法對(duì)每個(gè)圖像分塊的平均精度;點(diǎn)“O”落在坐標(biāo)系的上半部分表示縱軸結(jié)構(gòu)的性能較好,反之橫軸結(jié)構(gòu)性能較好;所有的縱軸均表示張量結(jié)構(gòu)。

如圖2所示,張量結(jié)構(gòu)的性能優(yōu)于其他類型的結(jié)構(gòu);尤其是其性能顯著優(yōu)于向量結(jié)構(gòu)。雖然矩陣結(jié)構(gòu)性能低于張量結(jié)構(gòu),但均超過(guò)了向量結(jié)構(gòu)和元素結(jié)構(gòu),后兩者則完全沒(méi)有考慮到SIFT特征的結(jié)構(gòu)性。這一結(jié)果證明了將特征結(jié)構(gòu)納入相似性度量是一種有效的手段。立方體結(jié)構(gòu)利用了這種結(jié)構(gòu)特性,對(duì)于相似性度量形成具有一致性的子特征比較重要,在張量結(jié)構(gòu)中,沿著各自維度的子特征具有一致性,而立方體結(jié)構(gòu)則在子特征中混合了所有的3個(gè)維度。

圖2 子特征結(jié)構(gòu)性能比較

3.1.2 相似性度量函數(shù)

本節(jié)實(shí)驗(yàn)主要分析張量結(jié)構(gòu)情況時(shí),各相似性度量形式S。在實(shí)驗(yàn)中,將不同類型的相似性度量函數(shù)(式(10)～式(15))與本文主要關(guān)注的Sadd進(jìn)行了比較,結(jié)果如圖3所示。由圖3(a)可以看出,Sadd的性能明顯優(yōu)于Sorg,所以將原始的SSIM公式Sorg展開(kāi)到相加形式,在提高性能表現(xiàn)的同時(shí)也增加了魯棒性。由圖3(b)～圖3(c)可以看出,S+l、S+c和S+s3種加和形式的性能大致相當(dāng),但仍比Sadd稍遜一籌,并且Sadd生成的顯式特征映射的維數(shù)最低,計(jì)算效率優(yōu)于其他加和形式。所以,在接下來(lái)的實(shí)驗(yàn)中,均取Sadd形式,同時(shí)權(quán)值設(shè)置為{wl,wc,ws}={2,2,1}。

圖3 不同相似性度量函數(shù)性能比較

3.1.3 本文方法與其他方法比較

本節(jié)實(shí)驗(yàn)將本文方法與歐式距離、卡方距離、擴(kuò)散距離和推土機(jī)距離度量的傳統(tǒng)方法進(jìn)行比較;除歐式距離,其他傳統(tǒng)方法均基于直方圖形式。關(guān)鍵點(diǎn)匹配結(jié)果如圖4所示,其中縱軸均表示本文方法。

圖4 不同方法關(guān)鍵點(diǎn)匹配結(jié)果

由圖4可以看出,本文方法的性能優(yōu)于其他方法。實(shí)驗(yàn)結(jié)果表明:基于本文特征結(jié)構(gòu)方法的性能優(yōu)于傳統(tǒng)直方圖形式;與圖4(c)擴(kuò)散距離相比較,基于SSIM的度量適用于對(duì)跨組相似度的提取。

為了進(jìn)一步說(shuō)明本文方法的性能,下文比較各方法相似性度量的計(jì)算時(shí)間。實(shí)驗(yàn)以Matlab(版本為2014b)為平臺(tái),利用Matlab mex-C混編文件實(shí)現(xiàn);處理器為英特爾Xeon 3.4 GHz;操作系統(tǒng)為64位Windows7。實(shí)驗(yàn)比較每個(gè)樣本對(duì)的平均計(jì)算時(shí)間,結(jié)果如表1所示。從表1可以看出,本文方法利用點(diǎn)積形式的顯式特征映射,顯著加快計(jì)算時(shí)間;計(jì)算時(shí)間比歐式距離度量之外的其他方法大幅度降低。

表1 不同方法的平均相似性度量計(jì)算時(shí)間 ns

3.2 圖像檢索

圖像檢索為特征匹配的重要應(yīng)用,本部分實(shí)驗(yàn)進(jìn)一步對(duì)本文方法圖像檢索性能進(jìn)行測(cè)試。3.1節(jié)的關(guān)鍵點(diǎn)匹配是對(duì)同一個(gè)目標(biāo)的參考圖像和畸變圖像進(jìn)行比較;與此不同,圖像檢索對(duì)不同目標(biāo)、不同圖像間的相似性進(jìn)行度量,這就要求對(duì)畸變具有較高的魯棒性,并對(duì)相似性度量在目標(biāo)識(shí)別方面的性能進(jìn)行評(píng)價(jià)。

本節(jié)實(shí)驗(yàn)通過(guò)DoG檢測(cè)器提取SIFT特征,對(duì)建筑物數(shù)據(jù)集進(jìn)行檢索實(shí)驗(yàn),并與傳統(tǒng)方法進(jìn)行比較。各方法的圖像檢索準(zhǔn)確率如表2所示,可以看出,本文方法的圖像檢索準(zhǔn)確率較其他傳統(tǒng)方法明顯提高,達(dá)到81.5%,表明本文的相似性度量能夠有效進(jìn)行目標(biāo)辨識(shí)。

表2 不同方法圖像檢索準(zhǔn)確率比較 %

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

本文提出一種以測(cè)量成對(duì)結(jié)構(gòu)化特征間的相似性方法用于特征匹配。提取局部基元特征的三階張量,將該內(nèi)在結(jié)構(gòu)特征與在圖像質(zhì)量評(píng)價(jià)中廣泛應(yīng)用的SSIM相結(jié)合,提出具有高魯棒性的相似性度量方法——擴(kuò)展結(jié)構(gòu)相似性度量。同時(shí),本文利用顯式特征映射,將特征作為點(diǎn)積嵌入,以顯著提高相似性度量的處理速度。實(shí)驗(yàn)結(jié)果表明,本文方法在特征匹配的應(yīng)用中具有良好的性能,同時(shí)具有較高的計(jì)算效率。

[1] 張宇仁.圖匹配算法及其在月面圖片關(guān)鍵點(diǎn)匹配中的應(yīng)用[D].北京:中國(guó)科學(xué)院大學(xué),2016.

[2] 高洪波,王洪玉,劉曉凱.一種基于分層學(xué)習(xí)的關(guān)鍵點(diǎn)匹配算法[J].電子與信息學(xué)報(bào),2013,35(11):2751-2757.

[3] BALA A,KAUR T.Local texton XOR patterns:a new feature descriptor for content-based image retrieval[J].Engineering Science & Technology International Journal,2015,19(1):101-112.

[4] AKATA Z,PERRONNIN F,HARCHAOUI Z.Good practice in large-scale learning for image classification[J].IEEE Transactions on Software Engineering,2014,36(3):507-520.

[5] 劉相濱,鄒北驥,孫家廣.基于邊界跟蹤的快速歐式距離變換算法[J].計(jì)算機(jī)學(xué)報(bào),2016,29(2):317-323.

[6] 鄭 倩,盧振泰,陳 超.基于鄰域信息和高斯加權(quán)卡方距離的脊椎MR圖像分割[J].中國(guó)生物醫(yī)學(xué)工程學(xué)報(bào),2011,30(3):357-362.

[7] DALIRI M R.Chi-square distance kernel of the gaits for the diagnosis of Parkinson’s disease[J].Biomedical Signal Processing & Control,2013,8(1):66-70.

[8] 韓 華,曹 偉,龔 濤.目標(biāo)再確認(rèn)中基于推土機(jī)距離的關(guān)聯(lián)度建立[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,22(3):435-439.

[9] 貢 超,蔣建國(guó),齊美彬.基于擴(kuò)散距離的SURF特征圖像匹配算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,22(4):449-478.

[10] 卞程飛,張 健,吳 娜.基于可移動(dòng)窗口和擴(kuò)散距離的立體匹配算法[J].系統(tǒng)仿真學(xué)報(bào),2014,26(9):2130-2135.

[11] WANG Z,BOVIK A C,SIMONCLLI E P.Image quality assessment:from error visibility to structural similarity[J].IEEE Transactions on Image Processing,2004,13(4):600-612.

[12] 袁艷春,劉云鵬,高宏偉.基于邊緣結(jié)構(gòu)相似性的圖像質(zhì)量評(píng)價(jià)方法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(9):2870-2873.

[13] BRUNET D,VRSCAY E R,WANG Z.On the mathe-matical properties of the structural similarity index[J].IEEE Transactions on Image Processing,2012,21(4):1488-1499.

[14] WU X,TANG Y,BU W.Offline text-independent writer identification based on scale invariant feature transform[J].IEEE Transactions on Information Forensics & Security,2014,9(3):526-536.

[15] 賈世杰.基于內(nèi)容的商品圖像分類方法研究[D].大連:大連理工大學(xué),2013.