Foundation item: Supported by the National Natural Science Foundation of China(61472145)

基于邊緣切線流場的多尺度結(jié)構(gòu)張量圖像檢索算法*

張見威1黃達承1胡振朋1張菁2

(1.華南理工大學 計算機科學與工程學院, 廣東 廣州 510006； 2.大慶油田有限責任公司 第四采油廠, 黑龍江 大慶 163511)

摘要：為減小基于草圖的檢索技術(shù)中弱邊緣的影響并提高特征的平移不變性,提出了一種基于邊緣切線流場的多尺度結(jié)構(gòu)張量檢索算法.該算法采用邊緣切線流場取代梯度場,在顯著強邊緣上計算結(jié)構(gòu)張量以抑制弱邊緣的影響,并在多尺度分區(qū)架構(gòu)下進行結(jié)構(gòu)張量特征的提取以增強特征的平移不變性.實驗結(jié)果表明,與傳統(tǒng)的結(jié)構(gòu)張量方法相比,該算法有效地抑制了弱邊緣的影響,避免了使用圖像梯度方向描述圖像顯著邊緣方向的不穩(wěn)定性,增強了特征的平移不變性,提高了檢索性能.

關鍵詞：圖像檢索；線條草圖；結(jié)構(gòu)張量；邊緣切線流場

收稿日期：2014-10-28

基金項目：* 國家自然科學基金資助項目(61472145)

作者簡介：張見威(1969-),女,博士,副教授,主要從事圖像和視頻處理研究.E-mail: jwzhang@scut.edu.cn

文章編號：1000-565X(2015)05-0107-07

中圖分類號：TP391.3

doi:10.3969/j.issn.1000-565X.2015.05.017

基于內(nèi)容的圖像檢索(CBIR)技術(shù)利用圖像自身所蘊涵的豐富視覺特征進行檢索,能夠有效地避免文本標注的主觀歧義性.CBIR可分為基于樣圖的圖像檢索和基于草圖的圖像檢索(SBIR).SBIR技術(shù)使用簡單的沒有顏色和紋理的手繪線條圖像作為查詢的輸入,然后在大型圖像庫中檢索與手繪線條圖內(nèi)容相關的圖像.草圖能更好、更快地描述要搜索的場景和對象,而且草圖是檢索者對查詢圖像進行的抽象,這給圖像檢索技術(shù)賦予了高層語義.如何用數(shù)學描述草圖及圖像庫的圖像,以及如何基于抽象的數(shù)學描述來評價圖像庫的圖像與草圖的相似性是SBIR技術(shù)的難點.

SBIR方法主要分為3大類:基于特征提取的方法、基于邊界匹配的方法[1]和基于空間關系的方法[2],基于特征提取的方法是研究的熱點,這類方法按照特征提取的策略和特征向量的構(gòu)造方式可以分為基于全局特征的方法和基于局部特征的方法.許多SBIR方法是基于全局特征的.全局特征是用于捕捉一幅圖像的整體特性,它的提取并不需要事先進行對象的提取或圖像的分割,可以直接對整幅圖像進行提取.例如,一種常用的方法是把一幅圖像分成一些子圖,計算每個子圖的平均特征量,整幅圖像以一個向量的形式來描述,向量中每一個分量對應某一個位置的子圖.

1基于全局特征的SBIR算法

最早的QBIC系統(tǒng)[3]使用了基于全局特征的形狀描述,全局特征包括面積、似圓度、離心率、主軸方向和不變矩等.Chalechale等[4]提出了基于角分區(qū)的方法,并采用了傅里葉變換使特征具有旋轉(zhuǎn)不變性.Eitz等[5]對文獻[4]方法進行改進,提出了基于角徑向分區(qū)的方法.Springmann等[6]將ARP描述子與Keysers等[7]提出的圖像變形模型相結(jié)合,提出了一種ARP描述子的變種.這類方法的問題是當每個角分區(qū)數(shù)量少時,旋轉(zhuǎn)不變性會被削弱.另外,ARP描述子只簡單利用邊緣點數(shù)量信息,未利用邊緣的方向信息.Saavedra等[8]提出了一種基于邊界方向直方圖的全局描述子(HELO),該描述子應用了生物特征處理中計算指紋方向場的方法.該方法將圖像和草圖分成k×k個不重疊的方塊區(qū)域,通過計算每個區(qū)域的梯度創(chuàng)建一個有k個分區(qū)的角度直方圖,采用直方圖的L1距離度量相似性.常用的全局描述子還有邊緣直方圖描述子(EHD)[9-11]、梯度直方圖描述子(HOG)等.EHD僅利用了邊界方向類型的計數(shù)信息,沒有考慮邊界梯度響應的強度大小,具有該方向邊緣響應的全部像素點都被賦予同樣的權(quán)重.HOG描述子將圖像和線條草圖劃分成k×k個不重疊的方塊區(qū)域,計算每個分區(qū)的所有像素的梯度,進而確定每個分區(qū)中最強梯度的方向,該方法舍棄了梯度幅值小的像素點,保留了強梯度像素點,并構(gòu)建了梯度直方圖.HOG描述子也被用于人的行為檢測[12].Narayana等[13]使用紋理特征GLCM的能量、反差、熵作為評判草圖與圖像相似度的特征向量,但紋理特征不適用于線條稀疏的草圖,故檢索性能不好,此方法只能作為縮窄檢索范圍的預處理.Eitz等[14]將結(jié)構(gòu)張量作為描述子,取得了較好的檢索效果.

EHD、HOG、HELO及結(jié)構(gòu)張量描述子都是通過圖像區(qū)域中的主要梯度方向來表征圖像內(nèi)容中的線條方向,會不同程度地受到圖像中其他紋理梯度的影響,導致提取的方向不能對應用戶視覺感知的線條方向.此外,以上算子都不具有平移不變性.為此,文中提出了基于邊緣切線流場[15]的多尺度結(jié)構(gòu)張量檢索(ETFMSSTR)算法,在邊緣切線流場上計算結(jié)構(gòu)張量,并進行多尺度加權(quán),以降低非主要邊界的影響,并增強平移不變性.

2ETFMSSTR算法

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

相比于ARP、EHD和HOG特征,結(jié)構(gòu)張量特征在檢索性能上有很大的提高[14].EHD、HOG和HELO特征是在直方圖中統(tǒng)計不同的梯度方向,用直方圖分布來描述圖像或草圖.用戶在檢索時畫的線條是圖像主要場景或?qū)ο蟮倪吘?而圖像強梯度的方向正好垂直于邊緣,故匹配草圖的線條與圖像中主要場景或?qū)ο蟮倪吘?需要尋找一個方向來代表分區(qū)中的最主要梯度方向,結(jié)構(gòu)張量是以此為出發(fā)點的一種特征描述方法.

全局特征提取方法將圖像規(guī)則地劃分成M×N個分區(qū),使用一個張量來描述每個分區(qū)Cij的主要梯度方向.令x為一個單位向量,它表示一個分區(qū)中的最主要梯度方向,則

(1)

式中,guv為梯度.

將式(1)進行變換可得

(2)

式中,Gij是分區(qū)Cij中梯度張量積的和.使用拉普拉斯乘子計算式(2)的最大值,令(xTGijx)=0,可得

(3)

(4)

(5)

草圖和圖像的全局特征提取方法是一樣的,采用Sobel算子計算出每個像素點(u,v)∈Cij在水平和豎直方向上的梯度分量,從而得到梯度guv.草圖S和圖像I之間的相似度用所有位置對應的分區(qū)Cij之間的結(jié)構(gòu)張量的Frobenius距離和來表示,即

(6)

在此基礎上,可以對結(jié)構(gòu)張量特征進行優(yōu)化.因為檢索的依據(jù)是用戶手繪的稀疏草圖,并不是所有草圖分區(qū)都有內(nèi)容.因此,在檢索前先建立一幅二值的區(qū)域掩膜,用來標識沒有被用戶輸入的草圖覆蓋到的分區(qū),這些分區(qū)不參與計算,在相似性距離計算中可以忽略.帶有掩膜的結(jié)構(gòu)張量特征具有更好的檢索性能.由于結(jié)構(gòu)張量的計算是在梯度場中進行的,因此受到圖像中弱邊緣和紋理的影響,與手繪草圖結(jié)構(gòu)張量的相似度度量差別很大.為此,文中引入邊緣切線流場[15](ETF)代替原來的梯度場,以抑制弱邊界、紋理和噪聲對結(jié)構(gòu)張量的影響.

2.2邊緣切線流場

邊緣切線流場是用于輔助生成自然圖像的平滑連貫的線條畫版本.ETF是一個平滑的方向場,它能有效地保留圖像顯著邊緣的方向信息,從而獲取圖像重要的形狀信息,同時也抑制圖像噪聲對圖像顯著邊緣的影響.ETF的產(chǎn)生過程使用了一個非線性的向量模板去平滑由原圖像梯度產(chǎn)生的方向場,這個模板能夠保留顯著的邊緣方向,而弱邊緣方向?qū)⒈徽{(diào)整成在其鄰域中最顯著的邊緣方向.同時這個平滑過程亦需保留銳利的邊角,避免邊緣方向流的回旋效應和防止弱方向被無相關性的強方向的影響.算法的輸入為I的梯度圖像I、圖像梯度幅值、平滑濾波迭代次數(shù)Imax,輸出為邊緣切線流場t.

設要處理的自然圖像為I(X),其中X=(x,y)表示圖像中像素點的位置,像素點X的邊緣切線方向為t(X),可認為t(X)垂直于X位置上原圖像的梯度方向g(X)=I.ETF就是用t(X)作為曲線的切線方向,用其初始化ETF的邊緣方向流.設t0(X)是ETF中X的邊緣切線方向,t0(X)被初始化為I(X)的梯度方向的垂直方向,ti(x)=-I(y)和ti(y)=-I(x)表示在實現(xiàn)中取X的梯度I(X)方向逆時針旋轉(zhuǎn)90°的方向,normalize(ti)表示對ti(X)做歸一化處理得到單位向量,并記錄原來梯度I(X)的幅值(X).

為了產(chǎn)生一個緊致的、領域?qū)R的向量場,定義向量平滑模板如下：

wm(X,Y)wd(X,Y)

(7)

式中,Ω(X)表示像素X的一個鄰域,φ(X,Y)是一個符號函數(shù),k是向量歸一化的項,tcur(Z)是模板濾波前像素點Z位置上的邊緣切線的單位向量,ws是空間關系權(quán)重,wm是向量幅值權(quán)重,wd是方向關系權(quán)重.ws、wm的計算式分別為

(8)

(9)

(10)

wm和wd在保留重要邊緣特征方面起著重要的作用.符號函數(shù)φ(X,Y)是在對向量場進行模板平滑前用于對與tcur(X)的夾角大于90°的tcur(Y)進行方向反轉(zhuǎn),即

(11)

φ(X,Y)的作用在于引導向量場傾向于緊致對齊的,但同時也避免了回旋的方向流.

2.3ETFMSSTR算法描述

2.3.1邊緣切線流場-結(jié)構(gòu)張量

ETF產(chǎn)生的方向場更加平滑,在局部上能比較統(tǒng)一而且能趨向于一致的方向,不會產(chǎn)生局部向量回旋效應.因此,ETF更適用于圖像重要的顯著邊緣信息的提取,邊緣切線流場取代結(jié)構(gòu)張量中的梯度場,更能使結(jié)構(gòu)張量在描述主要邊緣上發(fā)揮作用.為此,文中提出了邊緣切線流場-結(jié)構(gòu)張量(ETFST)的全局特征,將ETF與結(jié)構(gòu)張量有機結(jié)合.ETFST的數(shù)學原理如下.

令x為一個單位向量,表示分區(qū)Cij中的最主要梯度方向,t(u,v)表示像素位置(u,v)的ETF流方向,則

(12)

將式(12)進行變換可得

(13)

s.t. xTx=1.

2.3.2多尺度特征提取方式

結(jié)構(gòu)張量特征的特點在于統(tǒng)計出圖像分區(qū)中最顯著線條的方向.如果分區(qū)劃分得太小,所提取的特征會不同程度地受到分區(qū)內(nèi)其他弱噪聲紋理梯度的影響;如果分區(qū)劃分得過大,不同邊緣交織所得到的特征信息對檢索不具有意義.另外,以固定分區(qū)劃分圖像,特征的平移不變性有限,一旦草圖在畫面中的平移量超過了一個分區(qū)大小,則導致檢索結(jié)果可能會完全不同.為此,文中提出了多尺度的特征提取方法.采用不同尺寸規(guī)格的分區(qū)方法來提取特征,用不同分區(qū)方式下計算所得相似度的加權(quán)綜合作為最終結(jié)果,用于評價草圖與圖像的相似度.多尺度的分區(qū)劃分方式如圖1所示,實線是小尺度的緊密的劃分方式,虛線是大尺度的稀疏的劃分方式.

圖1　多尺度的分區(qū)方式

文中將草圖S和圖像I之間的相似度用不同劃分方式下所有位置對應的分區(qū)Cij之間的結(jié)構(gòu)張量的Frobenius距離的加權(quán)和來表示,即

(14)

式中,wk為第k種區(qū)域劃分方式對相似度貢獻的權(quán)重,R為區(qū)域劃分方式的數(shù)量.文中根據(jù)經(jīng)驗取wk值.

2.3.3算法流程

ETFMSSTR算法的主要原理是在多尺度分區(qū)方式下在ETF向量流場上提取結(jié)構(gòu)張量特征,計算不同分區(qū)方式下結(jié)構(gòu)張量的距離,以它們的加權(quán)綜合作為最終相似度來檢索圖像.ETFMSSTR算法流程圖如圖2所示,主要包括以下步驟:

圖2　ETFMSSTR算法流程圖

(15)

對草圖S進行同樣的劃分.

(2)邊緣切線流場的生成.按照ETF生成方法,通過圖像I或草圖S的梯度圖像初始化ETF,使用式(7)的向量平滑模板對圖像I或草圖S進行迭代濾波,生成最終的邊緣切線流場.

F=(T(I,1),T(I,2),…,T(I,R))

(16)

該全局特征向量每個位置的分量對應著圖像在第k種區(qū)域劃分方式下位置(i,j)的子圖.

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

文中使用C++和OpenCV開源庫實現(xiàn)了結(jié)構(gòu)張量算法、ETFST算法和ETFMSST算法,3種算法的參數(shù)設置如表1所示,其中ETF算法的η=1、平滑模板大小為9、迭代次數(shù)為2,wk取經(jīng)驗值.

表1　3種算法的實驗參數(shù)值

使用文獻[16]所收集的31幅用戶手繪草圖作為ETFMSSTR算法的輸入,并在其1240幅測試基準圖像中進行檢索.部分實驗結(jié)果如圖3(a)所示.使用文獻[16]設計的測試基準對結(jié)構(gòu)張量算法、ETFST算法和多尺度ETFMSSTR算法進行測試評分,即收集手繪線條草圖,并讓志愿者對圖像與草圖的相似程度進行打分,從而選取一些圖像作為測試基準圖像,每個草圖對應著若干幅有相關度評級的圖像;然后利用圖像的評級進行計算從而得到評分,3種算法的基準得分分別為0.15171、0.19079、0.19211.可見,ETFST算法的檢索性能較結(jié)構(gòu)張量算法有了較大的提高,而ETFMSSTR算法的檢索性能又比ETFST算法有稍微的提高.

從圖3(a)可以看到:ETFMSSTR算法性能的提高得益于邊緣切線流場的3個限制條件、邊緣切線流場方向的平滑性和能表達圖像的最主要強邊緣方向;用結(jié)構(gòu)張量算法得到的檢索結(jié)果中,具有語義相似性的圖像明顯比ETFMSSTR算法的結(jié)果少.這是因為結(jié)構(gòu)張量只是在梯度方向的基礎上進行計算,不能抑制在用戶看來是噪聲的一些弱紋理梯度,而且梯度方向的描述不魯棒.

從圖3(a)中的用例可以看到,有一些檢索結(jié)果與草圖的語義相關性比較低,如用例5的檢索結(jié)果中,與“風帆”具有相同語義的結(jié)果在前7幅圖像中相對其他用例較少,這是由于用例5的草圖中線條內(nèi)容較少,而算法會根據(jù)草圖的內(nèi)容產(chǎn)生一個掩膜,這個掩膜在檢索運算中排除沒有線條內(nèi)容的區(qū)域,這些區(qū)域不參與特征計算,因而對于用例5,在圖像中參與相似性度量的區(qū)域相對較少,只要在這些參與運算的區(qū)域內(nèi)部的主要線條方向與草圖對應區(qū)域的線條方向相似,該圖像即被認為是相關的圖像.特別是用例5的第1幅相關圖像,圖像中間水面的線

圖3　ETFMSSTR算法和結(jié)構(gòu)向量算法的部分實驗結(jié)果

條幾乎與草圖是一致的,而水面上的石頭紋理也具有斜向下的強烈線條,故它被認為與“風帆”草圖相似性最高的圖像.因此,當用戶輸入的草圖線條極少時,ETFMSSTR算法的檢索結(jié)果中排名靠前的圖像很可能并不具有很強的相關性,這是因為草圖線條較少,掩膜排除的草圖區(qū)域太多,從而圖像中只有少量對應區(qū)域參與運算，而這些區(qū)域剛好與草圖的線條相似,并不是因為圖像與草圖整體相似.這也說明了ETFMSSTR算法缺乏語義性,只要是圖像在相同位置具有相同方向的強線條,則可能被認為是相似圖像.

全局方法與局部方法各有特點,分別對應不同的應用場景,在現(xiàn)實中都有重要的研究價值.全局方法針對用戶希望搜索與位置有一定相關性的場景,而局部方法針對用戶希望搜索與所畫草圖位置和大小不相關的場景.兩種方法對用戶意圖的理解不同,不具有強的可對比性,因此文中選取全局方法作為研究對象,并沒有與局部方法在測試基準中進行對比,只是在全局方法的范圍內(nèi)與目前較好的結(jié)構(gòu)張量全局方法進行比較.

4結(jié)論

對基于全局特征的檢索算法進行兩方面的改進,提出了基于邊緣切線流場的多尺度結(jié)構(gòu)張量檢索算法.該算法在邊緣切線流場上計算結(jié)構(gòu)張量,在多尺度分區(qū)形式下進行結(jié)構(gòu)張量特征提取,使得相似性度量中大尺度的分區(qū)形式具有較高的權(quán)重,從而更有效地避免噪聲紋理產(chǎn)生的梯度的影響.實驗結(jié)果表明,該算法有效地避免了使用圖像梯度方向來間接描述圖像顯著邊緣方向的不穩(wěn)定性,使得結(jié)構(gòu)張量能直接在顯著的強邊緣上進行計算,抑制了弱邊緣的影響,并且多尺度的提取方式在一定程度上增強了特征的平移不變性.

基于草圖的圖像檢索已經(jīng)成為熱門的研究領域,如何結(jié)合機器學習實現(xiàn)對草圖的高層語義理解,這將是今后研究的重點,如果檢索算法對圖像的語義分類有好的效果,則基于內(nèi)容的圖像檢索的性能也會得到提高.

參考文獻：

[1]Cao Y,Wang C H,Zhang L Q.Edgel index for large-scale sketch-based image search [C]∥Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs:IEEE,2011:761-768.

[2]Sousa P,Fonseca M J.Sketch-based retrieval of drawings using spatial proximity [J].Journal of Visual Languages and Computing,2010,21(2):69-80.

[3]Niblack C W,Barber R,Equitz W,et al.The QBIC project,querying images by content using color,texture and shape [C]∥Proceedings of 1993 Storage and Retrieval for Images and Video Databases.San Jose:International Society for Optical Engineering,1993:173-181.

[4]Chalechale A,Naghdy G,Mertins A.Sketch-based image matching using angular partitioning [J].IEEE Transactions on Systems,Man and Cybernetics,2005,35(1):28-41.

[5]Eitz M,Hildebrand K,Boubekeur T,et al.An evaluation of descriptors for large-scale image retrieval from sketched feature lines [J].Computers and Graphics,2010,34(5):482-498.

[6]Springmann M,Kabary I A,Schuldt H.Image retrieval at memory’s edge:known image search based on user-drawn sketches [C]∥Proceedings of the 19th ACM International Conference on Information and Knowledge Management.New York:ACM,2010:1465-1468.

[7]Keysers D,Deselaers T,Gollan C,et al.Deformation mo-dels for image recognition [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(8):1422-1435.

[8]Saavedra J M,Bustos B.An improved histogram of edge local orientations for sketch-based image retrieval [C]∥Procee-dingsof the 32nd DAGM Symposium.Berlin:Springer,2010:432-441.

[9]Manjunath B,Salembier P,Sikora T.Introduction to MPEG-7:multimedia content description interface [M].New York:John Wiley & Sons Inc,2002.

[10]Chalechale A.Content-based retrieval from image databases using sketched queries [D].New South Wales:School of Electrical,Computer and Telecommunications Engineering,University of Wollongong,2005.

[11]Shih J L,Chen L H.A new system for trademark segmentation and retrieval [J].Image and Vision Computing,2001,19(13):1011-1018.

[12]Dalal N,Triggs B.Histograms of oriented gradients for human detection [C]∥Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Re-cognition.Washington D C:IEEE,2005:886-893.

[13]Narayana M,Kulkarni S.Content based image retrieval using sketches [C]∥Proceedings of 2012 International Conference on Advances in Computing.Bangalore:Sprin-ger,2012:1117-1123.

[14]Eitz M,Hildebrand K,Boubekeur T,et al.A descriptor for large scale image retrieval based on sketched feature lines [C]∥Proceedings of EUROGRAPHICS Symposium on Sketch-Based Interfaces and Modeling.New York:ACM,2009:29-36.

[15]Kang H,Lee S,Chui C K.Coherent line drawing [C]∥Proceedings of the 5th International Symposium on Non-Photorealistic Animation and Rendering.New York:ACM,2007:43-50.

[16]Eitz M,Hildebrand K,Boubekeur T,et al.Sketch-based image retrieval:benchmark and bag-of-features descriptors [J].IEEE Transactions on Visualization and Computer Graphics,2011,17(11):1624-1636.

Multi-Scale Structure Tensor Image Retrieval Algorithm

Based on Edge Tangent Flow Field

ZhangJian-wei1HuangDa-cheng1HuZhen-peng1ZhangJing2

(1.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;

2.No.4 Oil Production Company,Daqing Oil Field Company Ltd.，Daqing 163511,Heilongjiang,China)

Abstract:In order to reduce the effects of weak edges and reinforce the shift invariance in sketch-based image retrieval(SBIR), a multi-scale structure tensor retrieval algorithm on the basis of edge tangent flow field is proposed. In this algorithm, edge tangent flow field is used as a substitute for the gradient map of image, and the structure tensor is calculated directly on remarkable strong edges to suppress the effects of weak edges. Besides, structure tensor feature is extracted in the form of multi-scale partition to enhance the shift invariance. Experimental results indicate that the proposed algorithm is superior to the existing structure tensor method because it helps suppress the effects of weak edges effectively, avoid instable significant edge of image described by image gradient direction, enhance the shift invariance of structure, and, thereby, improve the retrieval efficiency.

Key words: image retrieval;sketch;structure tensor;edge tangent flow field