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

王小龍,沈新寧,杜建洪

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

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

王小龍,沈新寧,杜建洪

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

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

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

1 概述

隨著信息技術及多媒體技術的快速發展,越來越多的圖像出現并成為人們日常生活的一部分。為了從數量繁多的圖像中快速準確地找出所需要的圖像,基于內容的圖像檢索(Content-based Image Retrieval,CBIR)由于其突出的表現受到了人們越來越廣泛的關注。早期CBIR技術的研究焦點主要在于提取圖像的有效全局視覺特征(顏色、形狀、紋理等),如文獻［1-2］,盡管這些研究奠定了CBIR的基礎,但其檢索性能卻不盡如人意,其瓶頸在于這些全局的低級視覺特征和圖像的高級語義之間存在鴻溝,即“語義鴻溝”(semantic gap)。

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

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

2 圖像分割

自動圖像分割是一項困難的任務,雖然目前已經出現了很多的圖像分割算法,比如 JSEG分割［6］、GFCM分割［7］等,但它仍然是當前乃至未來計算機視覺領域所面臨的基本問題。

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

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

3 區域特征提取

區域特征提取用于對分割得到的圖像各區域的內容進行表示,在RBIR中常用的區域特征仍然是顏色、紋理、形狀以及空間位置等,只是這些特征是在圖像的區域層面上進行的提取與表示。本文提出了一種新的區域特征——區域自相關特征,并結合區域的顏色和形狀特征構成區域綜合特征對圖像的區域內容進行表示。

3.1 區域顏色特征

區域顏色特征以分割后各區域像素的一階矩和二階協方差矩統計特征來表示。

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

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

(2)二階協方差矩特征

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

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

例如，西電捷通案中，北京高院法官就采這一理論。他們認為合法售出的“實施專利方法的專用設備”、“制造專利產品的專用設備、元件或部件”并不會導致權利用盡。

3.2 區域形狀特征

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

3.3 區域自相關特征

區域自相關特征采用區域自相關圖來表示。首先對圖像中的每個像素按照圖像分割后該像素所屬的區域號進行標記,得到區域標記圖像,然后采用自相關圖算法［2］提取該區域標記圖像的區域自相關特征,稱為區域自相關圖(auto region-correlogram)。該特征反映了圖像各區域的像素自身的空間相關信息,表示在給定屬于某一區域的任一像素時,在一定距離范圍內出現的另一像素也屬于該區域的概率,記為{s}。

3.4 圖像表示

圖像內容可以用所有區域的顏色、形狀和自相關特征的集合表示,假設分割后的圖像共有N個區域,則圖像特征可表示為:

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

在RBIR系統中,圖像之間的相似性要由兩個層次上的度量來計算［11］。第一層為區域層(regionlevel),采用區域的低級特征來度量區域之間的相似性;第二層為圖像層(image-level),度量兩幅可能包含不同區域數目的圖像之間的整體相似性。基于該兩層度量理論,本文提出了一種新的二次型距離相似性度量方法QDSM,它能夠融合所有分割區域的特征,使得整個圖像的信息都可以充分利用,且適用于圖像中分割區域數不同的情況。

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

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

若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為圖像的區域個數,記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通過加權因子β相結合構成最終的圖像相似性距離D。S11,S22,S12是3個相似性系數矩陣,aik,bjl,cij分別為其對應的矩陣元素,分別通過式(10)～式(12)計算得到。aik是圖像P中的區域iP和區域kP之間的相似性系數,bjl是圖像Q中的區域jQ和區域lQ之間的相似性系數,cij是圖像P中的區域iP和圖像Q中的區域jQ之間的相似性系數,μ為各指數項的乘數因子。

將式(8)、式(9)稱為二次型距離相似性度量QDSM是因為它和傳統的二次型直方圖距離度量(Quadratic Histogram Distance Measure,QHDM)之間的相似性,傳統的QHDM定義如下:

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

5 實驗結果與分析

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

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

表1 MIRROR系統在Corel 1K圖像庫中的檢索結果

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

表2 ACC算法和本文算法的檢索結果

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

圖2 各檢索算法的ANMRR對比

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

表3 ACC算法和本文算法檢索時間對比 s

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

6 結束語

基于區域的圖像檢索(RBIR)是當前CBIR技術的研究熱點,它能夠在一定程度上減小CBIR中的語義鴻溝。本文提出了一種新的基于區域的圖像檢索算法,在區域層面上使用綜合特征對圖像內容進行表示,并采用新的二次型距離相似性度量QDSM來計算圖像之間的整體相似性,實驗證明了該算法的有效性。另外,本文的二次型距離相似性度量融合了所有分割區域的特征,使得整個圖像的信息都可以充分利用,且適用于圖像中分割區域數不同的情況,因此該相似性度量方法可以廣泛應用于RBIR系統中。

［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-均值算法聚類數的確定［J］.硅谷, 2011,(6):38-39.

［9］ 張文君,顧行發,陳良富,等.基于均值-標準差的K均值初始聚類中心選取算法［J］.遙感學報,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

中文引用格式:王小龍,沈新寧,杜建洪.一種基于區域綜合特征的圖像檢索算法［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.