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

, ,

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

0 概述

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

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

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

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

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

本文主要介紹在圖像質(zhì)量評價中SSIM的公式化表示,及其對特征匹配的適用性。已知參考圖像Ix,通過對目標(biāo)圖像Iy與Ix間的相似性進行度量,以對Xy的圖像質(zhì)量進行評價。SSIM分別從圖像Ix和Iy中提取成對圖像分塊x和y,計算式(1)的相似性度量值S;然后,對整個圖像的分塊得分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間的相似性測量函數(shù)。

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

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

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

(6)

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

2 本文方法

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

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

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

(7)

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

(8)

(9)

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

(10)

2.2 相似性度量

原始的SSIM定義為亮度均值l、對比度方差c和結(jié)果相關(guān)性s3種相似性函數(shù)的積,如式(11)所示。這三者共同的乘積對這些統(tǒng)計數(shù)據(jù)的任何畸變均具有敏感性,這有利于圖像評價,但在特征匹配中則缺乏魯棒性。從魯棒性的角度出發(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分離到加性項內(nèi)。這些權(quán)值基于相似性函數(shù)的數(shù)值范圍而確定,如式(16)所示。

(16)

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

2.3 顯式特征映射

(17)

(18)

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

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

3.1 關(guān)鍵點匹配

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

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

本節(jié)實驗統(tǒng)一使用式(11)相似性度量S=Sorg對不同類型的子特征結(jié)構(gòu)(如圖1所示)進行評估。以張量結(jié)構(gòu)為基礎(chǔ),與其他子特征結(jié)構(gòu)進行比較,結(jié)果如圖2所示。橫軸和縱軸的坐標(biāo)分別表示2種比較方法對每個圖像分塊的平均精度;點“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),但均超過了向量結(jié)構(gòu)和元素結(jié)構(gòu),后兩者則完全沒有考慮到SIFT特征的結(jié)構(gòu)性。這一結(jié)果證明了將特征結(jié)構(gòu)納入相似性度量是一種有效的手段。立方體結(jié)構(gòu)利用了這種結(jié)構(gòu)特性,對于相似性度量形成具有一致性的子特征比較重要,在張量結(jié)構(gòu)中,沿著各自維度的子特征具有一致性,而立方體結(jié)構(gòu)則在子特征中混合了所有的3個維度。

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

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

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

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

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

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

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

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

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

表1 不同方法的平均相似性度量計算時間 ns

3.2 圖像檢索

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

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

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

4 結(jié)束語

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

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

[2] 高洪波,王洪玉,劉曉凱.一種基于分層學(xué)習(xí)的關(guān)鍵點匹配算法[J].電子與信息學(xué)報,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].計算機學(xué)報,2016,29(2):317-323.

[6] 鄭 倩,盧振泰,陳 超.基于鄰域信息和高斯加權(quán)卡方距離的脊椎MR圖像分割[J].中國生物醫(yī)學(xué)工程學(xué)報,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)再確認中基于推土機距離的關(guān)聯(lián)度建立[J].華中科技大學(xué)學(xué)報(自然科學(xué)版),2015,22(3):435-439.

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

[10] 卞程飛,張 健,吳 娜.基于可移動窗口和擴散距離的立體匹配算法[J].系統(tǒng)仿真學(xué)報,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ì)量評價方法[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.