矢量量化用于颜色图像检索的改进方法*

陈善学,张 艳,尹雪娇，彭 娟

(重庆邮电大学 移动通信安全技术实验室，重庆 400065)

基于内容的图像检索技术（CBIR）具有较高的查找效率和准确度，近年来得到广泛应用。一幅图像的底层特征主要包括颜色、纹理、形状，而颜色特征[1]是图像最广泛的视觉特征。目前CBIR中颜色特征提取的形式主要方法有：颜色直方图[2](Color Histogram)、颜色一致性矢量 (Color Coherence Vector)、颜色相关图 (Color Correlogram)、其中颜色转移矩阵(Color Transfer Moment)等。这些方法都有各自的优缺点，颜色直方图、颜色一致性矢量、颜色相关图不能较好地描绘颜色的空间位置关系，颜色向量统计相似的图像有可能内容不相似，颜色转移矩阵用于图像检索效率不高。因而本文在矢量量化[3]的基础上，采用颜色直方图和颜色转移矩阵[4]相结合的方法进行图像检索,两者取长补短来达到检索目的。基于颜色的量化可以在不同的颜色空间中进行，最常用的颜色空间有 RGB、HSV、Luv及 Lab等色彩空间[5]。HSV空间的描述能力与人的视觉最为接近，因而本文选择HSV为量化空间。

1 相关工作

1.1 矢量量化及LBG算法

矢量量化本质上是一个聚类过程，而码书设计[6]就是寻求将M个训练矢量分成N类的一种最佳方案。设M个k维数据组成的数据空间{Xij},其中i=1,…,M;j=1,…,k，矢量量化可以看做该k维欧几里德空间Rk到包含 N个互相不重合（R1,R2,…,RN）子空间的有限子集 Y的映射。即Q:Rk→Y，其中在每一个子空间Rj中选出一个代表矢量记为Yj=(yj1,yj2,…,yjk)，将各个子空间的代表矢量集记为 Y={Yj；j=1,…,N}，通常将 Y称为码书(code book)，Yj称为码字(code word)，而 N是码书大小。收端以Yj再现 X 必然存在失真，满足 d（X,Yi）=min(d（X,Yj）)，j=1,…,N。d（X,Yi）为矢量 X与码字 Yi之间的失真测度。

LBG算法是一种直观有效的矢量量化码书设计算法，由 Linde、Buzo和 Gray[7]首先提出。LBG算法一般是先选取初始码书，根据最邻近原则得到新胞腔，然后根据质心原则，通过量化、聚类、迭代由新胞腔得到新的码书。通过某种限制条件结束迭代产生最终码书。这种迭代过程虽然不能保证最后能得到最优码书，但每次迭代平均失真都能降低或保持不变，使得码书性能得到提高。LBG对初始码书的选取具有很大的依赖性，很多研究者对初始码书的选取做了大量研究，Linde等人提出了一种类似于乘积码技术的初始化技术，黎洪松等[8]提出的分离平均法，设法寻找一种脱离随机性的初始码书设计方法，陈善学等[9]提出一种基于矢量和值排序的分离平均算法。这些算法都在一定程度改善了LBG初始码书性能。

1.2 基于矢量量化的颜色直方图

本文采用基于矢量量化的聚类主颜色[10]提取法。首先选择训练矢量和训练图像，在图像检索库中选取色彩迥异的18张图片作为训练图像集，并将每幅图像的色度空间抽取出来，形成一幅灰度图，选择所有不重叠的相邻4×4区域为训练矢量。利用抽取出来的H、S、V空间的训练矢量，按参考文献[9]方法生成初始码书。由于是基于三色数据的彩色图像，可以获得三色彩色图像对应的三本初始码书的 3个索引特征矢量 Hi、Si、Vi，将它们合并表示为一个特征矢量C=(Hi,Si,Vi),i=1,2,…,k为码书个数。对于图像中的任意一个像素块P∈G，它的值经过聚类过程可转化为C中的一个码书Q(P)∈G,本文采用LBG算法对像素块聚类，算法过程如下：

(1)设置初始码书C0，设定叠代次数 t=1。

(2)对于给定的码书，Ct={c1t,…,ckt}，按下式寻找最优的颜色像素块空间划分：

(这里Ri一是与码字cit距离最邻近的码字的集合。

(3)按下式选择每一个区域 Ri的质心,cent(Ri)构成新的码书{c1t+1,…,ckt+1}，

其中，P(cj)为码字cj在训练图像集中出现的概率。

(4)按下式判断迭代次数：

如果和上次叠代的平均失真统计量Dt间的差值小于预设阈值,则停止聚类过程。否则，返回到步骤(2)继续迭代过程。

通过上述颜色聚类过程，可以获得HSV空间的颜色矢量量化码表C={c1,…,ck},相当于图像的一个查色表。根据矢量量化码表，将彩色图像中的每一个像素块的颜色值归结为其中的对应码字。通过统计矢量量化各码字出现的频率，可以得到彩色图像的主颜色统计向量：

若以各码字的索引号为横坐标，各码字出现的频率百分比作为纵坐标,则可以得到一个图像块的主颜色直方图。

其中,h[ci]为图像G中全体像素块量化归结为主颜色ci的比例值。

1.3 颜色转移矩阵

颜色转移矩阵法是一种建立在HSV量化颜色空间之上的刻画颜色相对分布位置的方法。由前面的颜色直方图得到图像的颜色矢量量化码表C={c1,…,ck}，共有k个码字,表示有k种主色。彩色图像的颜色转移矩阵过程如下：

(1)将图像分成m×n个小块，每一小块的大小都为s×t个像素块。

(2)得出每一小块的主值c，也就是该小块中取得次数最多的那个码字。这样就形成—个二维主色矩阵，大小为 m×n，表示为 A={ci,j},其中 i=1,2,…,m;j=1,2,…,n。

(3)建立一个 k×k的矩阵 P(k为 c的取值个数)，各元素初始值为0。将步骤(2)得到的矩阵A按Z字扫描顺序进行扫描，设ci,j和cp,q是扫描序列中的一对相继出现的颜色(ci,j在 cp,q的前面)，则 P中相应元素 P[ci,j,cp,q]自增1，如此反复，直到扫描完成。

(4)建立k×k的矩阵D，D中元素的计算公式如下：

矩阵D就是该图像的颜色转移矩阵。从上面的步骤可以看出，矩阵D中的每个元素都描述了图像中不同颜色的相邻关系及这种相邻系在整幅图像所有像素块对中发生的比例,从而矩阵D能描述颜色的空间分布情况。

1.4 相似度度量[11]

1.4.1 颜色直方图相似性度量

一般的直方图度量方法是欧氏距离、矢量距离 (角度、幅度)、直方图交集距离等。颜色直方图相似性度量采用传统的欧氏距离作为度量方法，欧氏距离就是同时作为颜色相似性度量的结果。欧氏距离的定义如下：

其中,HA、HB为两图幅图像 A,B的主色直方图，T代表转置。

1.4.2 颜色转移矩阵相似性度量

对于颜色转移矩阵相似度度量，本文采用以下方法，设DA和DB分别表示两幅图像A、B的颜色转移矩阵，相似度定义为：

1.4.3 复合相似度度量

由于颜色转移矩阵弥补了颜色直方图对颜色空间描述的不足，而颜色直方图检索效率较好，因而将两者结合进行图像检索可达到很好的效果。两个相似度的取值在0～1之间，所以不需要归一化处理。合成相似度定义如下：

其中(w1,w2∈[0,1],w1+w2=1)。将合成相似度结果按升序排列，相似度值越小的图片与查询图片越相似。将排序结果按用户需要返回即可。

2 本文算法

根据上文提出的相关工作，本文算法是通过颜色直方图和颜色转移矩阵相结合的方法进行图像检索。算法过程如下：

(1)通过矢量量化方法把图像量化为k种主颜色，得到一个查色表，在查色表的基础上得到图像库中图像的颜色直方图 (1.2节详细论述)。该方法通过图像的k种主色进行图像检索，减少了计算量。

(2)在查色表的基础上得到图像库中图像的颜色转移矩阵(见1.3节详细论述)。颜色转移矩阵克服了颜色对图像空间描述不足的缺点，结合颜色直方图进行图像检索，提高了检索精度。

(3)通过1.4.1节论述的方法对颜色直方图相似性度量，1.4.2节论述的方法对颜色转移矩阵相似性度量，再通过1.4.3节论述的方法复合两种相似度，由复合相似度进行图像检索，返回相似图像。

3 实验结果分析

选用LI J[12]提供的图像数据库,选取其中420幅256×384或者 384×256的彩色图像，图像库分为海滩、人物、恐龙、花朵、草原、山峰和汽车 7类，每类包含 60幅图像。查准率是对检索系统精度的衡量，本文用查准率对图像性能进行分析。

其中,a代表正确检索出的相关图像数目；b代表检索出的无关图像；c代表漏检的相关图像数目；A代表某分类所有相关图像的集合，B代表检索出的所有图像的集合。

具体测试时，每种方法每个类别取6幅图像作为例图检索，返回20幅图像，然后再取6幅例图的平均查准率用来作为该方法该图像类别的查准率。实验中比较了颜色检索算法、矢量量化检索算法和本文提出的颜色直方图和颜色转移矩阵结合算法，效果如图1所示。

图3 采用矢量量化检索算法检索的草原图像结果

图4 采用本文算法检索的草原图像结果

由于各语义类别图像有很大不同，每个人对图片的感受和理解也都不同，所以查询准确率有一定的波动。从以上仿真结果的对比分析以及7类检索结果的整体效果中可以看出，本文算法用于图像检索比颜色检索算法查准率高出8%～30%，比矢量量化图像检索算法高1%～26%。因此，本文算法的图像搜索效果要好于基于颜色检索算法和基于矢量量化图像检索算法。由于篇幅关系，本文给出各种算法草原图像的查询结果,如图2～图4所示，其中第一张图像为输入图像，后面的17张图片为检索图像，相似度从左到右、从上到下由高到底排列。

[1]YAMADA A,KASUTANI E,OHTA M,et al.Visual program navigation system based on spatial distribution of color[C].Proc.of the IEEE International Conference on Consumer Electronics,2000.

[2]伯晓晨，刘建平.基于颜色直方图的图像检索[J].中国图像图形学报，1999,4(1)：33-37.

[3]孙圣和,陆哲明.矢量量化技术及应用[M].北京：科学出版社，2002.

[4]陈善学.矢量量化技术及其在图像信号处理中的应用研究[D].电子科技大学，2009.

[5]章毓晋.图像处理[M].北京：清华大学出版社，2006.

[6]徐皓淋,陈善学.一种改进的等误差竞争学习矢量量化算法[J].重庆邮电大学学报(自然科学版)，2009,21(6):721-724.

[7]LINDE Y，BUZO A，GRAY R M.An algorithm for vector quantizer design[J].IEEE Trans on Corn，1980，28(1)：84-95.

[8]黎洪松，刘洪伟.新的学习矢量量化初始码书算法[J].北京邮电大学学报，2006，29(4)：33-35.

[9]陈善学.矢量量化的初始码书算法[J].计算机工程与应用,2010:46(11),26-28.

[10]SWAIN M,BALLARD D.Color indexing[J].International Journal of Computer Vision,1991,7(1):11-32.

[11]唐宏.图像相似性模型、算法与应用研究[D].上海：上海交通大学,2006:18-63.

[12]LI J.Photography image database[EB/PL].[2005-08].http://www.stat.psu.edu/jiali/index.download.html.