一種基于區(qū)域綜合特征的圖像檢索算法

王小龍,沈新寧,杜建洪

(復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院,上海200433)

一種基于區(qū)域綜合特征的圖像檢索算法

王小龍,沈新寧,杜建洪

(復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院,上海200433)

針對(duì)基于內(nèi)容的圖像檢索所面臨的圖像低級(jí)視覺特征和高級(jí)語義之間的語義鴻溝問題,提出一種基于區(qū)域的圖像檢索算法。在LUV顏色空間中使用K均值聚類算法進(jìn)行圖像分割,提取分割后各區(qū)域的顏色、形狀和區(qū)域自相關(guān)特征構(gòu)成區(qū)域的綜合特征,采用二次型距離相似性度量方法完成圖像之間相似性的計(jì)算。實(shí)驗(yàn)結(jié)果表明,該算法具有較好的圖像檢索性能,與MIRROR中各算法相比,使用平均歸一化修正檢索等級(jí)得到的檢索性能提高了12% ～47.8%。

基于區(qū)域的圖像檢索;語義鴻溝;區(qū)域自相關(guān)特征;圖像分割;二次型距離相似性度量;平均歸一化修正檢索等級(jí)

1 概述

隨著信息技術(shù)及多媒體技術(shù)的快速發(fā)展,越來越多的圖像出現(xiàn)并成為人們?nèi)粘Ｉ畹囊徊糠帧榱藦臄?shù)量繁多的圖像中快速準(zhǔn)確地找出所需要的圖像,基于內(nèi)容的圖像檢索(Content-based Image Retrieval,CBIR)由于其突出的表現(xiàn)受到了人們?cè)絹碓綇V泛的關(guān)注。早期CBIR技術(shù)的研究焦點(diǎn)主要在于提取圖像的有效全局視覺特征(顏色、形狀、紋理等),如文獻(xiàn)［1-2］,盡管這些研究奠定了CBIR的基礎(chǔ),但其檢索性能卻不盡如人意,其瓶頸在于這些全局的低級(jí)視覺特征和圖像的高級(jí)語義之間存在鴻溝,即“語義鴻溝”(semantic gap)。

圖像注釋(image annotation)、基于區(qū)域的圖像檢索(Region-based Image Retrieval,RBIR)和相關(guān)反饋(Relevant Feedback,RF)是目前減小語義鴻溝的3種主要途徑。RBIR通過把圖像分割為若干目標(biāo)區(qū)域,然后提取各目標(biāo)區(qū)域的局部特征來描述和檢索圖像,區(qū)域級(jí)別上的圖像描述也更加符合人的視覺感知系統(tǒng)［3］,當(dāng)前的大多數(shù)CBIR算法采用基于區(qū)域的方法,如Simplicity［4］,SRBIR［5］等。在RBIR技術(shù)中,圖像分割、區(qū)域特征提取以及基于區(qū)域特征的相似性度量一直是研究人員所面臨的3個(gè)主要問題,文獻(xiàn)［6-7］對(duì)此進(jìn)行了深入探究并取得了一定進(jìn)展。

本文致力于RBIR的區(qū)域特征提取和相似性度量方面,提出一種基于區(qū)域綜合特征的圖像檢索算法,首先采用顏色聚類的分割方法將圖像分割成不同的區(qū)域,然后提取各區(qū)域的顏色、形狀和本文新定義的區(qū)域自相關(guān)圖(auto region-correlogram)特征作為綜合特征在區(qū)域?qū)用嫔蠈?duì)圖像進(jìn)行表示,最后使用本文提出的二次型距離相似性度量(Quadratic Distance Similarity Measure,QDSM)計(jì)算圖像之間的相似性。

2 圖像分割

自動(dòng)圖像分割是一項(xiàng)困難的任務(wù),雖然目前已經(jīng)出現(xiàn)了很多的圖像分割算法,比如 JSEG分割［6］、GFCM分割［7］等,但它仍然是當(dāng)前乃至未來計(jì)算機(jī)視覺領(lǐng)域所面臨的基本問題。

本文采用K均值聚類算法在LUV顏色空間中對(duì)彩色圖像進(jìn)行分割。算法將所有像素的LUV顏色矢量作為待分類數(shù)據(jù)并使用K均值算法進(jìn)行聚類,得到的每個(gè)類別都對(duì)應(yīng)著圖像中的一個(gè)區(qū)域。另外,針對(duì)K均值算法聚類數(shù)目k的選取問題,本文采用了文獻(xiàn)［8］介紹的一種快速而簡單的稱為爬山法的邏輯判定方法。針對(duì)K均值算法對(duì)初始聚類中心選取敏感的缺點(diǎn),采用了基于均值-標(biāo)準(zhǔn)差的高效高精度的初始聚類中心選取方法［9］。圖1為使用本文的分割算法對(duì)2幅圖像進(jìn)行分割的示例(左邊為彩色原圖像,右邊為分割后得到的區(qū)域灰度圖像),分割結(jié)果較好的體現(xiàn)了人對(duì)2幅圖像中不同區(qū)域的視覺感知。

圖1 Corel 1K圖像庫中2幅圖像的分割效果示例

3 區(qū)域特征提取

區(qū)域特征提取用于對(duì)分割得到的圖像各區(qū)域的內(nèi)容進(jìn)行表示,在RBIR中常用的區(qū)域特征仍然是顏色、紋理、形狀以及空間位置等,只是這些特征是在圖像的區(qū)域?qū)用嫔线M(jìn)行的提取與表示。本文提出了一種新的區(qū)域特征——區(qū)域自相關(guān)特征,并結(jié)合區(qū)域的顏色和形狀特征構(gòu)成區(qū)域綜合特征對(duì)圖像的區(qū)域內(nèi)容進(jìn)行表示。

3.1 區(qū)域顏色特征

區(qū)域顏色特征以分割后各區(qū)域像素的一階矩和二階協(xié)方差矩統(tǒng)計(jì)特征來表示。

(1)LUV顏色平均值特征(一階矩)

采用區(qū)域中所有像素的LUV顏色平均值作為該區(qū)域的一階矩統(tǒng)計(jì)特征,該特征表示為{(l,u,v)}。

(2)二階協(xié)方差矩特征

類似Tuzel等［10］提出的區(qū)域協(xié)方差特征描述符,區(qū)域中的每個(gè)像素首先被表示為一個(gè)9維的特征矢量:

其中,L,U,V為LUV空間的3個(gè)顏色分量;I為彩色圖像的亮度分量,一階和二階導(dǎo)數(shù)分別根據(jù)算子［-1,0,1］T和［-1,2,-1］T計(jì)算得到。區(qū)域的二階矩統(tǒng)計(jì)特征是該區(qū)域中所有像素的F(x,y)的9個(gè)分量之間的協(xié)方差,是一個(gè)9×9的矩陣,考慮到其對(duì)稱性,可以僅使用位于矩陣上三角的45個(gè)數(shù)據(jù)來表示該特征,記為{(c1,c2,…,c45)}。

例如，西電捷通案中，北京高院法官就采這一理論。他們認(rèn)為合法售出的“實(shí)施專利方法的專用設(shè)備”、“制造專利產(chǎn)品的專用設(shè)備、元件或部件”并不會(huì)導(dǎo)致權(quán)利用盡。

3.2 區(qū)域形狀特征

區(qū)域形狀特征以區(qū)域形狀的大小來表示,通過區(qū)域的面積百分比來計(jì)算。區(qū)域面積百分比是指該區(qū)域面積在整幅圖像中所占的比例,可用區(qū)域中的像素總數(shù)與圖像像素總數(shù)的百分比表示,將該特征記為{p}。

3.3 區(qū)域自相關(guān)特征

區(qū)域自相關(guān)特征采用區(qū)域自相關(guān)圖來表示。首先對(duì)圖像中的每個(gè)像素按照?qǐng)D像分割后該像素所屬的區(qū)域號(hào)進(jìn)行標(biāo)記,得到區(qū)域標(biāo)記圖像,然后采用自相關(guān)圖算法［2］提取該區(qū)域標(biāo)記圖像的區(qū)域自相關(guān)特征,稱為區(qū)域自相關(guān)圖(auto region-correlogram)。該特征反映了圖像各區(qū)域的像素自身的空間相關(guān)信息,表示在給定屬于某一區(qū)域的任一像素時(shí),在一定距離范圍內(nèi)出現(xiàn)的另一像素也屬于該區(qū)域的概率,記為{s}。

3.4 圖像表示

圖像內(nèi)容可以用所有區(qū)域的顏色、形狀和自相關(guān)特征的集合表示,假設(shè)分割后的圖像共有N個(gè)區(qū)域,則圖像特征可表示為:

4 二次型距離相似性度量(QDSM)

在RBIR系統(tǒng)中,圖像之間的相似性要由兩個(gè)層次上的度量來計(jì)算［11］。第一層為區(qū)域?qū)?regionlevel),采用區(qū)域的低級(jí)特征來度量區(qū)域之間的相似性;第二層為圖像層(image-level),度量兩幅可能包含不同區(qū)域數(shù)目的圖像之間的整體相似性?；谠搩蓪佣攘坷碚?本文提出了一種新的二次型距離相似性度量方法QDSM,它能夠融合所有分割區(qū)域的特征,使得整個(gè)圖像的信息都可以充分利用,且適用于圖像中分割區(qū)域數(shù)不同的情況。

設(shè){(li,ui,vi),(ci1,ci2,…,ci45)}和{(lj,uj, vj),(cj1,cj2,…,cj45)}分別為區(qū)域i和區(qū)域j的一階矩和二階協(xié)方差矩統(tǒng)計(jì)特征,簡記為 Mi={M1i, M2i}和Mj={M1j,M2j},Ci和Cj分別表示根據(jù)協(xié)方差矩陣的對(duì)稱性由M2i和M2j擴(kuò)展得到的區(qū)域i和區(qū)域j的協(xié)方差矩陣,則區(qū)域相似性距離定義為:

其中,dis1(i,j)和dis2(i,j)分別表示使用一階矩統(tǒng)計(jì)特征和二階協(xié)方差矩統(tǒng)計(jì)特征度量得到的區(qū)域相似性距離,兩者通過權(quán)重因子γ相結(jié)合構(gòu)成最終的區(qū)域相似性距離dis(i,j)。dis1(i,j)采用歐氏距離進(jìn)行度量,而協(xié)方差矩并不隸屬于歐式空間,不適合使用歐氏距離進(jìn)行度量,故dis2(i,j)采用文獻(xiàn)［12］提出的方法進(jìn)行計(jì)算。{λk(Ci,Cj)}k=1,2,…,9為Ci和Cj的廣義特征值,通過式(6)來計(jì)算。

若FP= {{(li,ui,vi),(ci1,ci2,…,ci45),pi, si},i=1,2,…,M}和FQ={{(lj,uj,vj),(cj1, cj2,…,cj45),qj,tj},j=1,2,…,N}分別表示圖像P和Q的特征,M和N為圖像的區(qū)域個(gè)數(shù),記p= (p1,p2,…,pM)T,q=(q1,q2,…,qN)T,s=(s1, s2,…,sM)T,t=(t1,t2,…,tN)T,則圖像P和Q的整體相似性定義為:

其中,式(8)、式(9)為本文所定義的二次型距離相似性度量(QDSM),D1,D2通過加權(quán)因子β相結(jié)合構(gòu)成最終的圖像相似性距離D。S11,S22,S12是3個(gè)相似性系數(shù)矩陣,aik,bjl,cij分別為其對(duì)應(yīng)的矩陣元素,分別通過式(10)～式(12)計(jì)算得到。aik是圖像P中的區(qū)域iP和區(qū)域kP之間的相似性系數(shù),bjl是圖像Q中的區(qū)域jQ和區(qū)域lQ之間的相似性系數(shù),cij是圖像P中的區(qū)域iP和圖像Q中的區(qū)域jQ之間的相似性系數(shù),μ為各指數(shù)項(xiàng)的乘數(shù)因子。

將式(8)、式(9)稱為二次型距離相似性度量QDSM是因?yàn)樗蛡鹘y(tǒng)的二次型直方圖距離度量(Quadratic Histogram Distance Measure,QHDM)之間的相似性,傳統(tǒng)的QHDM定義如下:

其中,h1和h2分別為傳統(tǒng)的直方圖特征矢量;A為系數(shù)矩陣。對(duì)比式(8)、式(9)和式(13),可見本文所定義的QDSM(式(8)、式(9))其實(shí)為QHDM (式(13))的擴(kuò)展式,當(dāng) S11,S22和 S12三者相等時(shí)式(8)、式(9)就轉(zhuǎn)化為式(13)。另外,式(13)中要求h1和h2具有相同的維數(shù),而式(8)、式(9)中的p和q,s和t則不具有該限制。

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

本文對(duì)檢索算法性能的度量采用的是平均歸一化修正檢索等級(jí)(Average Normalized Modified Retrieval Rank,ANMRR)［13］。實(shí)驗(yàn)所采用的測試圖像集為Corel 1K圖像庫(http://wang.ist.psu.edu/docs /related.shtml),圖像分辨率為384×256或256×384,共有1 000幅彩色圖像,應(yīng)用本文提出的K均值聚類分割算法共得到2 696個(gè)對(duì)象區(qū)域,平均每幅圖像有2.696個(gè)區(qū)域,表示每幅圖像平均需要2.696× (3+45+1+1)≈135維的特征矢量。

文獻(xiàn)［14］在Corel 1K圖像庫中定義了20幅問詢圖像及其視覺相似的圖像相關(guān)集,這些圖像相關(guān)集中的圖像數(shù)從8幅到100幅不等,具體定義可參考其所開發(fā)的MIRROE圖像檢索系統(tǒng)(http://aacus.ee.cityu.edu.hk/～corel1k/)。根據(jù)文獻(xiàn)［14］已得出的數(shù)據(jù),MIRROE系統(tǒng)中各種檢索算法在Corel 1K數(shù)據(jù)庫中的ANMRR數(shù)據(jù)對(duì)比如表1所示,其中顏色結(jié)構(gòu)描述符(Color Structure Descriptor,CSD)獲得了最佳的檢索性能(ANMRR的值越小,代表檢索算法的性能越好)。

表1 MIRROR系統(tǒng)在Corel 1K圖像庫中的檢索結(jié)果

本文的問詢圖像選自MIRROR中定義的20幅問詢圖像,且采用了與MIRROR完全相同的實(shí)驗(yàn)過程,以便將本文算法的檢索結(jié)果和MIRROR中各種算法已得到的檢索結(jié)果(如表1所示)進(jìn)行比較。實(shí)驗(yàn)分別使用本文的基于區(qū)域綜合特征的圖像檢索算法和文獻(xiàn)［2］提出的顏色自相關(guān)圖圖像檢索算法ACC(Auto Color-Correlogram)對(duì)問詢圖像進(jìn)行檢索,得到20幅問詢圖像的NMRR及ANMRR結(jié)果如表2所示。其中,ACC算法、本文算法的ANMRR分別為0.379 4,0.285 6。

表2 ACC算法和本文算法的檢索結(jié)果

顏色自相關(guān)圖算法ACC是一種利用顏色自身空間相關(guān)信息的全局特征圖像檢索算法,之所以將其和本文的RBIR算法進(jìn)行對(duì)比是因?yàn)锳CC算法是一種具有代表性的全局特征圖像檢索算法。由表2可見,本文的基于區(qū)域的圖像檢索算法相較于ACC算法在檢索性能上有明顯優(yōu)勢(shì),其ANMRR比ACC算法下降了0.093 8,檢索性能提高了24.7%。相比于MIRROR中各種已經(jīng)過驗(yàn)證的算法(如表1所示),本文 RBIR的檢索性能也是最優(yōu)的,使用ANMRR度量得到的檢索性能有12%～47.8%的提高。圖2顯示的是各種檢索算法的ANMRR柱狀圖表示。

圖2 各檢索算法的ANMRR對(duì)比

另外,為對(duì)比ACC算法和RBIR算法的計(jì)算復(fù)雜度,本文計(jì)算得到了2種算法對(duì)100次問詢的檢索時(shí)間和平均每次問詢的檢索時(shí)間如表3所示(實(shí)驗(yàn)的系統(tǒng)測試環(huán)境為:Intel Core i5-3210M CPU, 2.5 GHz,2GB RAM,Windows 7操作系統(tǒng);程序開發(fā)工具為Matlab)。

表3 ACC算法和本文算法檢索時(shí)間對(duì)比 s

在算法計(jì)算時(shí)間方面,由表3可見ACC算法相比本文RBIR算法有明顯優(yōu)勢(shì),這是由于RBIR算法中圖像分割步驟通常會(huì)耗費(fèi)大量時(shí)間(本文中每幅圖像的平均分割時(shí)間為2.536 s),使得RBIR算法較傳統(tǒng)的基于全局特征的CBIR算法耗時(shí)更長,快速有效的圖像分割算法也一直是RBIR檢索中面臨的重要問題,有待研究人員做出進(jìn)一步的努力。

6 結(jié)束語

基于區(qū)域的圖像檢索(RBIR)是當(dāng)前CBIR技術(shù)的研究熱點(diǎn),它能夠在一定程度上減小CBIR中的語義鴻溝。本文提出了一種新的基于區(qū)域的圖像檢索算法,在區(qū)域?qū)用嫔鲜褂镁C合特征對(duì)圖像內(nèi)容進(jìn)行表示,并采用新的二次型距離相似性度量QDSM來計(jì)算圖像之間的整體相似性,實(shí)驗(yàn)證明了該算法的有效性。另外,本文的二次型距離相似性度量融合了所有分割區(qū)域的特征,使得整個(gè)圖像的信息都可以充分利用,且適用于圖像中分割區(qū)域數(shù)不同的情況,因此該相似性度量方法可以廣泛應(yīng)用于RBIR系統(tǒng)中。

［1］ Stricker M A,Orengo M.Similarity of Color Images［C］//Proceedings of IEEE ISOP'95.［S.1.］:IEEE Press,1995:381-392.

［2］ Huang J,Kumar S R,Mitra M,et al.Image Indexing Using Color Correlograms［C］//Proceedings of IEEE Computer Society Conference on ComputerVision and Pattern Recognition.San Juan,USA:［s.n.］,1997:762-768.

［3］ Jing F,Li M,Zhang L,et al.Learning in Region-based Image Retrieval［C］//Proceedings of the 2nd International Conference on Image and Video Retrieval.Berlin,Germany:Springer,2003:206-215.

［4］ Wang J Z,Li J,Wiederhold G.SIMPLIcity:Semanticssensitive Integrated Matching for Picture Libraries［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,23(9):947-963.

［5］ Rajam I F,Valli S.SRBIR:Semantic Region Based Image Retrieval by Extracting the Dominant Region and Semantic Learning［J］.Journal of Computer Science, 2011,7(3):400-408.

［6］ Deng Y,Manjunath B.Unsupervised Segmentation of Color-texture Regions in Images and Video［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(8):800-810.

［7］ Zhao F,Jiao L,Liu H.Kernel Generalized Fuzzy C-means Clustering with Spatial Information for Image Segmentation［J］.Digital Signal Processing,2013,23(1):184-199.

［8］ 劉 丹,高世臣.K-均值算法聚類數(shù)的確定［J］.硅谷, 2011,(6):38-39.

［9］ 張文君,顧行發(fā),陳良富,等.基于均值-標(biāo)準(zhǔn)差的K均值初始聚類中心選取算法［J］.遙感學(xué)報(bào),2006, 10(5):715-721.

［10］ Tuzel O,Porikli F,Meer P.Region Covariance:A Fast Descriptor for Detection and Classification［C］//Proceedings of the 9th European Conference on Computer Vision.Berlin,Germany:Springer,2006:589-600.

［11］ Liu Y,Zhang D,Lu G,et al.A Survey of Content-based Image Retrieval with High-level Semantics［J］.Pattern Recognition,2007,40(1):262-282.

［12］ F?rstner W,Moonen B.A Metric for Covariance Matrices［D］.Stuttgart,Germany:Dept.of Geodesy and Geoinformatics,Stuttgart University,1999.

［13］ Saad M H,Saleh H I,Konbor H,et al.Image Retrieval Based on Integration Between YCbCr Color Histogram and Texture Feature［J］.International Journal of Computer Theory and Engineering,2011,3(5):479-483.

［14］ Wong K M,Cheung K W,Po L M.MIRROR:An Interactive Content Based Image Retrieval System［C］// Proceedings of IEEE International Symposium on Circuits and Systems.［S.1.］:IEEE Press,2005:1541-1544.

編輯 索書志

An Image Retrieval Algorithm Based on Region Integrating Features

WANG Xiaolong,SHEN Xinning,DU Jianhong
(School of Information Science and Technology,Fudan University,Shanghai 200433,China)

This paper presents a novel Region-based Image Retrieval(RBIR)method to reduce the semantic gap between low-level visual feature and high-level semantic of images in the content-based Image retrieval area.K-means clustering algorithm is used in the LUV color space for image segmentation.The color and shape feature in each region as well as the region auto-correlation feature are extracted as the integrating features of each region.And this paper defines a new Quadratic Distance Similarity Measure(QDSM)to calculate the similarity between different images.Experimental results show that the novel RBIR method using integrating features increases the retrieval performance by 12% ～47.8% compared with the traditional methods under Average Normalized Modified Retrieval Rank(ANMRR)metric.

Region-based Image Retrieval(RBIR);semantic gap;region auto-correlation feature;image segmentation; Quadratic Distance Similarity Measure(QDSM);Average Normalized Modified Retrieval Rank(ANMRR)

1000-3428(2014)11-0229-04

A

TP391.41

10.3969/j.issn.1000-3428.2014.11.045

王小龍(1989-),男,碩士,主研方向:圖像處理;沈新寧,碩士;杜建洪,副教授。

2013-10-18

2013-12-27E-mail:11210720077@fudan.edu.cn

中文引用格式:王小龍,沈新寧,杜建洪.一種基于區(qū)域綜合特征的圖像檢索算法［J］.計(jì)算機(jī)工程,2014,40(11):229-232.

英文引用格式:Wang Xiaolong,Shen Xinning,Du Jianhong.An Image Retrieval Algorithm Based on Region Integrating Features［J］.Computer Engineering,2014,40(11):229-232.