一种基于区域综合特征的图像检索算法

王小龙,沈新宁,杜建洪

(复旦大学信息科学与工程学院,上海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.