一种新的基于矢量量化的图像检索算法

冀　鑫　冀小平

(太原理工大学信息工程学院　山西 太原 030024)



一种新的基于矢量量化的图像检索算法

冀鑫冀小平

(太原理工大学信息工程学院山西 太原 030024)

针对目前基于颜色的图像检索算法在颜色特征提取的不足，提出一种新的颜色特征提取算法。利用LBG算法对HSI空间的颜色信息矢量量化，然后统计图像中各个码字出现的频数，形成颜色直方图。这样在提取颜色特征过程中，尽可能地降低图像原有特征失真。同时通过设定门限值，多次实验比较查全率和查准率，找到较为满意的门限值，使检索算法更加完善。实验结果表明，该算法能有效地提高图像检索精准度。

HSI空间图像特征矢量量化门限值

0　引　言

随着信息技术的发展，生活中不断地生成大量的图片，它们都是无序的、无索引的。目前，我们面临的一个问题就是如何从这些海量的图片里快速而准确地检索到我们想要查询的图片。因此，基于内容的图像检索成为了当下一个研究的热点。基于CBIR[1]技术主要依据图像所具有颜色(灰度)、纹理、形状、空间关系等特征[2]，提取这些特征，然后对这些特征进行相似度对比，并对图库中图像进行排序，从而实现图像检索的目的。本文在特征提取时选取的是对颜色特征的提取，针对目前基于颜色的图像检索算法在提取特征过程中损失较多原有颜色信息的问题，提出有别于其他算法的一种新的矢量量化算法。首先，RGB颜色空间转化到HSI颜色空间，利用LBG算法对查询图像矢量量化，形成码书，并统计查询图像各个码字出现的频数，形成颜色直方图；其次，按照查询图像的码书对图库集中的图像一一量化，统计每幅图像各个码字出现频数，得到颜色直方图；最后，计算颜色直方图距离Di，距离小于等于门限值I的图片返回排序，大于门限值的则舍弃。检索流程如图1所示。

图1　检索流程图

1　矢量量化的图像检索

1.1前期图像处理

本文采用的颜色模型是HSI模型，主要考虑到这种颜色模型更能反映人的视觉对颜色的感觉。它是由Munseu提出的一种颜色模型，其中H为色调，S为饱和度，I为亮度或强度。

直接用MATLAB读入图像的保存形式是由RGB三个参量保存。一幅256×256的彩色图像用RGB表示为256×256×3的三维矩阵，这样后期对图像的空间转换和矢量量化整体的运算量是非常大的，而且可行性不够高，对检索效率是不利的。因此，首先得对图像进行简单地压缩，适当地舍弃图像本身存在的冗余的颜色信息是必要的。压缩过程直接用到的是容易在MATLAB7.11.0(R2010b)中实现的平均压缩。所谓平均压缩，就是对一幅图像均匀地分块，然后对每一块的RGB三个参量分别进行平均运算，将点数适当减少，再生成新的图像的过程。公式表示：

MATLAB7.11.0(R2010b)仿真结果如图2、图3所示。

图2　256×256图片　　　图3　64×64图片

压缩完成以后，再对图像进行颜色空间转换。对任何[0,1]范围内的R、G、B值转换为HIS模型的计算公式如下：

(1)

其中：

(2)

1.2矢量量化及LBG算法

矢量量化是从k维欧几里德空间Rk映射到其一个有限子集C的过程，即：Rk→C，其中C={Y1,Y2,…,Yi,…,YN|Yi∈Rk}称为码书，N为码书长度[3]。映射关系应满足：Q(X|X∈Rk)=Yi，其中X=(x1，x2，…，xk)为Rk中的k维矢量，Yl=(yl1,yl2,…,ylk)为码书C中的码字，并且满足：d(X,Yl)=min(d(X,Yi))，其中d(X,Yi)为矢量X与码字Yi之间的失真度。因而只要输入一个矢量X必然能在码书C中找到合适的码字Yi与它对应,使该码字与输入矢量X的失真度达到码书中所有码字最小。

LBG算法是一种最优的矢量量化码书设计算法，是由Linde等[4]在1980年首次提出来的。该算法具有最佳矢量量化器设计的最佳划分和最佳码书的优点，是Lloyd算法在矢量空间的应用，具有清晰的物理概念、算法严密和容易实现等特点[5]。LBG算法的收敛速度和收敛的可能性，决定了最终形成码书的质量，关键是对初始码书的形成有很大的依赖性。针对LBG算法初始码书设计的问题，陈善学等[6]提出了改进的PNN算法， 黎洪松等[7]提出了分离平均法，设法找到一种脱离随机性的初始码书涉及方法，这些算法都在一定程度上改善了本身LBG算法的不足。

1.3算法描述

1.3.1生成查询图像码书

本文选取的查询图像是大小为256×256的jpg格式的金针花图像。先按照1.1节的方法将256×256的图像平均压缩成64×64的图像同时转换颜色空间，完成对图像前期的处理，然后再进行生成码书的过程。

1) 获取查询图像的初始码书。设定码书长度N=32。MATLAB中读入图像是由RGB形式保存，转换为HIS模型，形成3×4096矩阵。在仿真实验中，将训练样本(3×4096矩阵)通过随机函数(randn)选择32个样本作为初始码书。

2) 进行迭代训练。每次迭代中，每一个训练矢量Xi=(Hi,Si,Ii)(i=1,2,3)(注：每一点HSI三个参量作为一个训练矢量)与码书中的各个码字Yj(j=1,2,…，32)相比较，找到与该训练矢量最相近的一个码字Yk，并把所有与Yk最相近的训练矢量归为一类，这样一共有32类，这一步也叫划分胞腔过程[8]。然后求出每个胞腔中训练矢量与其对应在码书中最相近的码字Yk的距离平方之和，得到此次划分胞腔进行迭代的平均失真Ln。若此次划分的平均失真Ln与上次划分的平均失真Ln-1之间的相对误差εn符合设定的失真误差ε，则停止划分，否则求出各胞腔的中心矢量作为新的迭代码书，重新划分胞腔。本文失真相对误差为ε=0.0001。查询图像的码书生成过程如图4所示。

图4　LBG算法形成查询图像码书

1.3.2形成颜色直方图

颜色直方图是一种通过概率统计方法准确地将图像信息反映到可计算的数学模型上。在仿真实验过程中，利用计算机软件统计图像中各个像素点出现的频数，形成颜色直方图，这样将抽象的图像信息转化为直观的颜色直方图。考虑到颜色直方图具有旋转、尺度与平移不变性等优良特点[9]，且方法简单比较容易实现，因此在提取图像颜色特征时经常用到。

本文用LBG算法来实现图像的颜色量化，得到查询图像的码书，统计查询图像中各个码字出现的频数，并用直方图形式直观地表达出来，就完成了对图像颜色特征的提取。其中直方图的横坐标为码书中码字编号(1,2,…,32)，直方图的纵坐标为图片矢量量化后，统计得出码字的频数。在MATLAB7.11.0(R2010b)中仿真图3提取出的颜色直方图如图5所示。

图5　查询图像颜色直方图

从图像检索图库中选取8张图作为图像训练集，对8幅图像按照查询图像码书进行量化，统计每幅图像每个码字的频数。然后8幅图像对应的8个颜色直方图，这样就完成对图库训练集中图片的颜色特征提取。

1.3.3相似度计算

提取图像颜色特征之后，接着需要考虑的问题就是对图像相似度的计算。颜色直方图检索算法的相似度计算本质上其实就是颜色直方图距离的计算[10]。单单针对一种颜色特征的距离度量方法有许多种。我们常用的有欧拉距离、直方图相交距、二次式距离、马氏距离等。当图像特征的各分量之间是正交的而且是无关联的，同时各维度的权重相同，这时我们计算两个特征向量X和Y之间距离通常用欧拉距离[11]。公式为：

(3)

本文在计算距离时，采用了一种简单的而且能够从最后运算数据中直观地看到查询图像与图库中图像的特征距离。具体方法为：查询图像经过特征提取获得特征向量X，对8幅图像提取特征得到8个特征向量，逐一与向量X计算距离。例如8幅图中一幅提取出来的特征向量Y，距离公式为：

(4)

图6　检索结果

2　实验结果与分析

查准率(precision)为检索到的与查询图像相似的图像数目与已检索出的图像数目之比。查全率 (recall)为检索到的与查询图像相似的图像数目与所有图库集相似图像数目之比。查准率用来判断检索的精准度，而衡量检索的全面性是用查全率来判定的。通常我们用这两个数据来认定检索方法是否有效。查准率和查全率两者越高说明检索方法越有效。然而查准率和查全率是互斥的，当追求较高的查准率时，查全率会降低，而当要求查全率较高时，我们必须降低查准率。因此通过改变检索算法的某些参量，目的是使查准率和查全率二者实现一个良好的均衡。本文通过设置门限值I来找到实现查准率和查全率均衡的合适的门限值。由于经过计算最终得到的特征距离Di是0到1的一维数组，所以分别将门限值I设置为 0.1、0.2、0.4、0.5、0.6、0.8。当距离Di>I时，图库集中对应的图像将不返回，认为与查询图像无关，只有当距离Di≤I时，所对应的图像返回，认为这些图像与查询图像相关。

本实验对植物、动物、风景分别进行检索，从而来检测该算法的检索性能，为了达到算法性能评价的可靠性，植物类选取了花100幅图片(其中花的种类不同，花的形状不同，花的颜色不同)，动物类同样选取了100幅图片，风景类也选取了100幅图片进行试验。在MATLAB7.11.0(R2010b)中应用该算法实际仿真，通过代入不同的门限值参数，观察并计算不同门限值下的各类图像的查全率和查准率，最后计算出平均的查全率和平均查全率。从最后计算出的结果中，得出最适合本算法的门限值。仿真实验数据统计见表1所示。

表1　不同门限值下对应各类别检索结果

考虑到图库集中的图像都是与查询图像相关，所以查全率P=返回数/100，查准率P=相关图像/返回数。计算出查全率和查准率见表2所示。

表2　不同门限值下各类别查全率和查准率

计算不同门限值下的平均查准率(Averprecision)和平均查全率(Averrecall)公式如下：

(5)

平均查全率和平均查准率如表3所示。

表3　平均查全率和平均查准率

将计算出的平均查全率和平均查准率绘制折线图分析实验数据，折线图如图7所示。

图7　平均查全率和平均查准率比较

从图7中可以看出不同的门限值下，应用本算法检索图像计算出的平均查全率和平均查准率是变化的。当门限值增大时，平均查全率随着增大而平均查准率反而随着减小；当门限值减小时，平均查全率随着减小而平均查准率反而增大。因此，门限值和平均查全率成正比，跟平均查准率成反比[12]。从图中还可以看出，门限值对平均查全率的影响要大于对平均查准率的影响。同时，当门限值I=0.6时，无论从平均查准率还是平均查全率来讲都是比较满意。

本文还将提出的新算法与传统颜色直方图算法和文献[13]检索算法进行了对比。通过计算平均查全率和平均查准率，绘制曲线，如图8所示，显然本算法要优于其他两种算法。主要原因是LBG算法在量化时按照查询图像来生成码书，在检索不同的图像时，查询图像码书是按照查询图像变化而变化的。因此，提取出的颜色特征更能体现出查询图像本身存在的颜色信息。

图8　平均检索性能比较

3　结　语

本文针对图像检索，提出了一种新的基于矢量量化的图像检索算法，并在MATLAB7.11.0(R2010b)中仿真分析实验结果，证实了本算法的可行性和可靠性。采用HSI模型更加接近人的视觉感觉，利用LBG算法量化提取特征，确保提取出颜色特征的可靠性，加入门限值来平衡查全率和查准率的关系，找到适合本算法的最佳门限值，使算法更加完善。下一步研究工作的首要方向就是将本算法结合其他图像特征来实现检索目标。

[1] 孙思,赵姗,魏从刚.基于视觉点特征的图像检索技术研究[J].计算机科学,2013,40(6A):196-198.

[2] 焦蓬蓬,郭依正,刘丽娟,等.灰度共生矩阵纹理特征提取的Matlab实现[J].计算机技术与发展,2012,22(11):169-171,175.

[3] 裴慧.DCT域矢量量化图像压缩编码算法研究[D].哈尔滨:哈尔滨工业大学,2005.

[4]Linpe,BuzoA,GrayRM.Analgorithmforvectorquantizerdesign[J].IEEETransonlorn,1980,28(1):84-95.

[5] 孙中伟.双正交变换及矢量量化应用研究[D].天津:天津大学,2009.

[6] 陈善学,张艳,吴立彬.用于LBG初始码书设计的改进PNN算法[J].重庆邮电大学学报:自然科学版,2012,24(1):50-53.

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

[8] 陈学青,罗航哉,薛向阳,等.基于格矢量量化和倒排文件的快速图像检索方法[J].电子学报,2000,28(8):94-96.

[9] 成琳,陈俊杰,相洁.图像颜色特征提取技术的研究与应用[J].计算机工程与设计,2009,30(14):3451-3454.

[10]VasukiA,VanathiPT.Areviewofvectorquantizationtechniques[J].IEEEPotentials,2006(4):39-47.

[11]SwainM,BallardD.Indexingviacolorhistograms[J].IEEETransInternationalJournalofComputerVision,1990(1):390-393.

[12] 赵睛.基于颜色的图像检索研究[D].太原:太原理工大学,2009.

[13] 李雪艳,冀小平.基于分块颜色特征和相关反馈的图像检索技术[J].电视技术,2013,37(7):29-32.

ANEWIMAGERETRIEVALALGORITHMBASEDONVECTORQUANTIFICATION

JiXinJiXiaoping

(School of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,Shanxi,China)

Weputforwardanewcolourfeatureextractionalgorithmfortheshortcomingofpresentcolour-basedimageretrievalalgorithmincolourfeatureextraction.First,thealgorithmusesLBGalgorithmtocarryoutvectorquantificationoncolourinformationinHSIspace,andthencountstheappearancefrequencyofeachcodewordintheimagetoformcolourhistogram.Sointheprocessofcolourfeatureextractionthedistortionoforiginalimagefeaturescanbereducedasfaraspossible.Meanwhile,bysettingthethresholdvaluewecomparedtherecallandprecisionratesthroughacoupleoftheexperimentsuntilasatisfiedthresholdvaluewasfound,thusmadetheretrievalmethodmoreperfect.Experimentalresultsshowedthatthenewalgorithmcouldeffectivelyimprovetheaccuracyofimageretrieval.

HSIspaceImagefeatureVectorquantificationThresholdvalue

2014-08-22。冀鑫，硕士生，主研领域：图像处理。冀小平，副教授。

TP391.9

ADOI:10.3969/j.issn.1000-386x.2016.03.051