综合颜色块的直方图图像检索算法

孙延维， 雷建军*， 苏 丹

(1.湖北第二师范学院 基础教育信息技术服务湖北省协同创新中心， 武汉 430205；2.重庆邮电大学 计算机科学与技术学院， 重庆 400065)



综合颜色块的直方图图像检索算法

孙延维1， 雷建军1*， 苏 丹2

(1.湖北第二师范学院 基础教育信息技术服务湖北省协同创新中心， 武汉 430205；2.重庆邮电大学 计算机科学与技术学院， 重庆 400065)

为了进一步提高基于颜色直方图的图像检索算法的效率，本文提出一种寻找图像中最大颜色块、提取其局部直方图，并与原直方图综合的新算法.该算法在保留原算法的同时，添加了色彩的空间分布特征，从而降低检索结果对颜色的绝对依赖.仿真实验结果表明，本文算法具有较好的查准率和查全率，对色块明显的图像检索效果尤其显著.

图像检索； 颜色直方图； 颜色块； 特征向量

伴随着数字信息化和因特网技术的普及，数字图像资源的增长速度越来越快.要对大规模的并且正在不断增加的图像集进行人工的自由文本描述就显得力不从心，不能适应网络多媒体信息检索的要求.90年代以后，基于内容的图像检索(CBIR)技术应运而生，从图像自身内容信息的角度来检索图像库[1-2].图像特征的提取与描述是该技术的基础，目前主要采用图像的底层视觉特征(如颜色、纹理、形状)描述图像内容信息[3].

颜色作为最稳定的视觉特征，一直是图像检索使用的主要特征之一.其中颜色直方图更是以计算简单且具有旋转、平移不变性等优点，成为图像检索应用最为广泛的颜色特征[4].但其最大的缺点就是缺少颜色空间分布信息.研究者对如何描述颜色空间信息做了大量的研究.文献[5-6]将颜色特征与其它低级视觉特征，如纹理、边缘特征以及空间属性相结合，以提高检索性能.但加入纹理等特征之后，会不可避免地破坏原有算法的变形、旋转、缩放不变性.文献[7]对简单的分块方法做了改进，突出图像中间的主体部分和充分限制背景的范围，提出了新的分割方法，对每个区域提取颜色特征的同时对中央区域赋予较大的权值.由于图像分割本身就是一个难题，分割结果很难精确，故检索效果并不理想.文献[8] 结合颜色在图像中的散布情况，综合颜色的统计特征与空间分布特征来描述图像内容，提出了一种新的颜色量化方法.但在实验中，当采用不同的相似性度量方法时，对检索效果影响较大.文献[9]突破了传统依据图像亮度信息寻找感兴趣点的检索算法，发明了一种新的基于拐点的兴趣点提取方法.由于提取方法不够准确，且没有考虑图像局部相关性，故检索效果一般.

本文作者注意到导致传统直方图检索算法效率不高的情形中，图像中大片色块的大小以及色块中包含的颜色种类差异也很大.如果采用颜色直方图比较两幅图的相似性，只是在同一灰度值色彩的数量之间进行比较，没有反映出颜色在空间分布的不同，因此造成空间信息的丢失.如果能够找到图像中最大的色块，并记下色块所在的位置，提取色块的局部颜色直方图，就能间接反映色彩的空间信息，从而增强分辨能力，提高检索效率.改进后的算法是从色彩中寻找空间信息，为了在改进的同时能够兼顾原有算法效率，将传统直方图的特征向量和最大色块的局部特征向量合并在一起得到原始图像的一个综合的空间颜色特征向量.当在直方图中引入最大色块的局部直方图时，能够在一定程度上反映表征一幅图像主题颜色形成的色区域形状特点，从而降低检索结果对颜色的绝对依赖，提高分辨能力.本文利用这一特点，对传统的颜色直方图检索算法进行了改进，添加了算法区分空间分布差异的能力，同时保留了原算法的有效性，使得新算法的检索性能有了较大的提高.

1 算法介绍

1.1 基于直方图的图像检索

颜色特征是图像检索中应用最广泛的视觉特征，目前有很多基于颜色特征的图像检索算法，颜色直方图是一种重要的基于颜色特征进行的图像检索方法.对于一幅图像I，其颜色由L级组成，每一种颜色值为ci(i=1，2，…，L).在整幅图像中，每一种颜色出现的频数记为h(ci)=(颜色为ci的像素个数)/(图像的I像素总数)，则一组像素统计值h(ci)就是该图像的颜色直方图.记为：H(I)=〈h(c1)，…，h(cL)〉.

假设P和Q表示要进行比较的两幅图像，检索时利用公式(1)计算两幅图的相似性：

(1)

d(H(P)，H(Q))即两幅图的欧式距离，d越小，两幅图相似性越大.另外一种常用的度量相似性的算法见公式(2).

(2)

d值越接近1，两幅图像越相似.传统的颜色直方图只统计了关于某一种颜色值的数量特征，可以反映图像的部分内容；但丢失了色彩在图像中形成的具体形状，因而造成空间信息的缺失.本文针对这一问题，在传统的颜色直方图上进行了适当的改进，有效地改善了基于颜色特征的查询效果.具体算法见下面的描述.

1.2 算法改进

1.2.1 算法描述 图像中，除了某一种颜色值的数量特征可以表征该幅图的特点之外，面积较大的颜色块也是不容忽视的颜色特征.大的颜色块通常包含了丰富的颜色信息，而且与图像要表达主题具有很大的关联性.找出图像中最大的一个颜色块，提取其局部颜色直方图，然后局部颜色直方图与该图像的传统直方图合并在一起，得到原始图像的一个综合的空间颜色直方图.

1.2.2 整体算法流程 ①图像中最基础、最常见的是RGB颜色空间，由于RGB颜色空间具有不均匀、不正交和不直观等缺点，因此首先，将图像的颜色值从RGB空间转化到能正确表达人们实际感知的HSV空间，RGB到HSV空间的转换过程可参考文献[10].然后根据矢量量化算法对原始的图像进行量化处理，得到一幅量化图像，即像素点阵列.

②利用Canny检测算子提取出原始图像的彩色边缘轮廓，得到图像的边缘矩阵.找出边缘矩阵中最大的0矩阵记为F1，提取F1的局部颜色特征，将其与图像传统直方图F2合并在一起，得到综合的空间颜色直方图：H(F)=(H(F1)，H(F2)).

③利用公式(1)计算两幅的相似性，用本文中形成的综合空间颜色直方图代替传统的颜色直方图.

1.2.3 0，1矩阵中查找最大0矩阵算法 1)初始化0、1矩阵SFinal，最大面积max=0，最大块矩阵的左上角坐标点的横坐标row=0，纵坐标col=0，长度length=0，宽度width=0;

2)获取SFinal矩阵的行数m，列数n;

3)初始化n+1个0元素数组b，n个0元素的数组l，n个0元素的数组r;

4)初始化i=0;

5)初始化j=0;

6)如果SFinal(i，j)==0，b[j]=b[j]+1，否则b[j]=0;

7)j=j+1，转6)，直到j等于n;

8)初始化j=0;

9)找出以b[j]为矩阵高的左边界l[j]，右边界r[j];

10)j=j+1，转8，直到j等于n;

11)初始化j=0;

12)如果r[j]-l[j]+1) *b[j]>max，max=r[j]-l[j]+1) *b[j]，Max=b(j)*(r(j)-l(j)+1)，row=i-b(j)+1，col=l(j)，length=r(j)-l(j)+1，width=b(j);

13)j=j+1，转11)，直到j等于n;

14)i=i+1，转4)，直到i=m．

1.2.4 算法执行效率分析 假定图像颜色个数为m，像素点的个数为n，由图像得到像素点矩阵的时间复杂度为O(n)，利用Canny检测算子提取图像的边缘矩阵所耗时间为3n2，计算综合直方图的时间复杂度为O(n)，计算图形的相似性时间复杂度为O(m)，整个算法的时间复杂度为O(n2+m).相对于传统的直方图算法的时间复杂度O(n+m)，时间开销增加了，这里多出的时间开销主要是用于找出图像的最大色块，这个步骤在本论文的算法中是至关重要的.本论文算法的空间开销与图像的最大色块的颜色个数有关系，假定这个值为k，则整个算法的空间开销为m+k，这较传统算法空间开销主要是增加了存储最大色块的直方图数据，这里k是小于m的，故本算法的空间复杂度为O(m).

2 实验结果与分析

为了验证本文算法的工作性能，建立了由20 000幅图像组成的图像库，其中包括大炮、高铁、古桥、花、熊、猫、食物、海滩、建筑、山10类图像(每类2000幅)，如表1所示.采用传统直方图与本文提出的CHP算法进行了实验，两幅图的相似性度量采用公式(1).

对检索算法的性能评估比较通用的两个准则是查准率(Precision)和查全率(Recall).查准率P定义为检索出的图像中相关图像的数目占的比例，查全率R定义为检索出的相关图像的数目占数据库中所有相关的图像数目的比例.查全率反映系统检索相关图像的能力，而查准率则反映系统拒绝无关图像的能力.但是查准率和查全率这两个评价标准往往是互相制约的，如果希望检索系统有较高的查准率，那么只能牺牲查全率作为代价；反之也是这样.因此，可以按照情况在这两个评价标准中找到权衡.

表1 测试图像库包含的图像集语义类

图1 传统颜色直方图法的查询结果Fig.1 The query results of the traditional color histogram

图2 改进的算法的检索结果Fig.2 The query results of the improved algorithm

图1和图2分别给出了CHP算法与传统颜色直方图算法的检索结果.其中，显示图像的左上角为查询实例图像，其余20幅图像是查询结果，不难看出，传统颜色直方图的查准率为6/21，而改进后的CHP算法的查准率为11/21，查准率由29%提高到50%，检索的准确率有了很明显地提高.本文根据检索出的不同图像数目分别做了实验，对21、45、60、75、90、105、120共7种情况进行了试验，可以得到CHP算法与传统直方图算法查准率的比较以及性能提高程度，性能提高公式为(P(H*)-P(H))/P(H).如表2所示.

表2 两种直方图检索结果的查准率对比

为进一步验证本算法的有效性，从每类图像随机抽取10幅作为查询实例图像，共构成100次查询，每次选取返回的前21幅图像作为检索结果.对每类图像计算其10次查询结果的查准率平均值、查全率平均值作为最终的平均查准率和平均查全率，如图3和图4分别所示.

由图3和图4可以看出熊的查准率和查全率提高的幅度最大，原因在于这类图像选自动漫图像.动漫图像的特点是线条轮廓清晰、大的色块相对明显，经过线条提取之后很容易找到最大的颜色块.颜色块中包含了丰富且能表征该幅图的颜色信息，如果采用传统直方图只能进行色彩总量的比较，很容易和其他色彩总量相似但是空间分布并不相似的图像造成混淆，如果采用本文算法则能够反映出代表这种分布的特征，从而可以很好的区别这类图片，提高检索效率.

图3 两种方法的平均查准率对比Fig.3 The comparison of average precision ratio for different methods

图4 两种方法的平均查全率对比Fig.4 The comparison of average recall ratio for different methods

3 结束语

基于内容的图像检索是当前多媒体检索的热门话题，是直接采用图像内容来实现图像信息检索的一门技术.其发展与研究涉及到语义特征、多维索引、用户接口、系统设计等众多学科分支.如何有效准确的表达图像特征是基于内容的图像检索技术的核心问题.由前述实验结果分析可见，本文提出的主要综合空间直方图方法改进了原有算法易丢失空间信息的不足，检索性能得到提高，非常适用于块状明显图像的检索，这主要是因为主要综合空间直方图融合了能够在一定程度上反映空间分布的局部颜色特征，具有了反映色彩空间分布信息的能力.同时，新算法保留了图像的传统直方图特征，且不破坏原算法旋转、缩放不变性的优点，因此具有较好的检索效果.

[1] Rui Y， Huang T S， Chang S F. Image retrieval: Current techniques， promising directions， and open issues[J]. Journal of Visual Communication and Image Representation， 1999， 10(1): 39-62．

[2] 黄祥林，沈兰荪.基于内容的图像检索技术研究[J].电子学报， 2002， 30(7)：1065-1071．

[3] Yoo H W， Jung S H， Jang D S， et al. Extraction of major object features using VQ clustering for content-based image retrieval[J]. Pattern Recognition， 2002， 35(5): 1115-1126．

[4] Swain M J， Ballard D H. Color indexing [J]. International Journal of Computer Vision， 1991， 7(1): 11-32．

[5] Liu G H， Li Z Y， Zhang L， et al. Image retrieval based on micro-structure descriptor[J]. Pattern Recognition， 2011， 44(9): 2123-2133．

[6] Liu G H， Zhang L， Hou Y K， et al. Image retrieval based on multi-texton histogram[J]. Pattern Recognition， 2010， 43(7): 2380-2389．

[7] Stricker M A， Dimai A. Color indexing with weak spatial constraints[C]//Electronic Imaging: Science & Technology. San Jose, CA, USA: International Society for Optics and Photonics， 1996: 29-40．

[8] 黄元元，刘宁钟.一种新的基于颜色特征的图像检索方法[J].小型微型计算机系统， 2012， 33(3)：609-613．

[9] Stottinger J，Sebe N，Gevers T，et al. Color interest points for image retrieval[C]//Proc of the 12th Computer Vision Winter Workshop，ST. Lambrecht, Austria, 2007:83-90．

[10] Smith J R. Integrated spatial and feature image systems: Retrieval， analysis and compression [D]. New York: Columbia University， 1997．

Histogram image retrieval integrated with color lump

SUN Yanwei1， LEI Jianjun1， SU Dan2

(1.Collaborative Innovation Center in Hubei Province on Fundamental Education and IT Services，Hubei University of Education， Wuhan 430205;2.School of Computer Science， Chongqing University of Posts and Telecommunications， Chongqing 400065)

To further enhance the efficiency of color histogram-based image retrieval algorithm， this paper presents a new algorithm which looks for maximum color lump， extracts its local histogram， and integrates with the original histogram. The algorithm adds spatial distribution characteristics of color while retaining the original algorithm， thus reducing absolute dependence on the color for retrieval results. The simulation results show that this algorithm has better precision and recall and has especially remarkable effect for image retrieval of apparent color lump．

image retrieval; color histogram; color lump; feature vector

2014-09-17.

湖北省教育厅科学研究计划重点项目(D20113006)；湖北省自然科学基金项目(2013CFB012)；湖北省高等学校青年教师深入企业行动计划项目(XD2012435).

1000-1190(2015)02-0201-05

TP391

A

*通讯联系人.E-mail:leijianjun@hue.edu.cn.