一种颜色量化的图象检索方法

一种颜色量化的图象检索方法摘要：颜色量化是进行图像处理和图像分析的重要技术之一，可以被广泛地应用到图象检索、图像压缩和图像分割中。文章提出了一种新的颜色量化方法。该方法先在HSV空间量化颜色成32种代表性颜色，取量化后的颜色中心作为谱聚类中心，再使用谱聚类进行再次聚类量化。然后颜色归一化，进行相似度计算。该方法结合了HSV量化的速度快和谱聚类适合各种数据集的优点。实验结果表明，该方法的检索精度要高于传统的仅基于颜色量化算法的检索结果。关键词：颜色量化，基于内容的图像检索，谱聚类，相似度中图分类号：TP391.4文献标识码：A文章编号：AnimageretrivalwaybasedoncolorquantizationAbstractColorquantizationisanimportanttechnologyaboutimageprocessingandimageanalysis,widelyappliedtotheimageretrieval,imagecompressionandimagesegmentation.Thepaperproposeanewmethodofquantifyingthecolor.itcompresscolorspaceto32kindsofrepresentativecolorsintheHSVcolorspace,usesthecolorcenterofquantifyingasspectral-clusteringcenter,andquantifythecolorsbyusingspectral-clustering.Thennormalizethecolordatasandhavethesimilaritycaculation.ThemethodcombinesthespeedofHSVmethodwiththeadaptionofspectral-clusteringtothedifferentdatasets.Theexperimentresultsshowthatthemethod'sretrievalprecisionishigherthanthetraditionalmethodonlyusingcolorquantizationapproach.KeywordsColorquantization,ContentBasedImageRetrieval(CBIR),spectral-clustering,similarity1引言随着多媒体和网络技术的迅速发展，基于颜色特征的图像检索引起了人们的足够重视。如果统计色彩空间的所有颜色必然会造成颜色直方图的维数过高和色彩冗余，因此需要在颜色空间内对颜色量化以降低直方图的计算量。目前常用的颜色量化方法大体可以分为分割算法和聚类算法2类．代表性的分割算法有频度序列法[1]、八叉树法[2]、HSV颜色量化算法等，频度序列法和八叉树法基本思想是将图像中出现频率最高的K种色彩作为调色板，然后将其余颜色按最小距离准则映射到调色板中．此类方法重构图像的层次感较丰富，但会丢失出现频率小的色彩，而无法保留细节，使局部模糊．曹莉华,张磊等考虑到HSV空间与人的视觉感知很接近，提出了基于HSV空间的72色和36色颜色量化方法。目前有许多算法都在HSV颜色量化上做改进。这些方法计算简单，速度快，但会丢失颜色信息，凡被量化到同一级的颜色均被视为无差别，而在各量化区间分界处附近忽视了颜色的相似性和连续性。聚类算法则先选择若干聚类中心，然后按某种准则对颜色进行迭代聚合，直到合适的分类为止．典型的有K均值聚类算法[3]、FCM聚类算法[4]、学习向量法[5]等．聚类算法为近似最优算法，但需迭代运算，计算量大，而且量化结果往往依赖于初始聚类中心的选取．另外，聚类算法容易将相近的色彩合并，而破坏色彩的层次感，且这些算法都是建立在凸球形的样本空间上。当样本空间不为凸时，算法会陷入局部最优。为了能在任意形状的样本空间上聚类，且收敛于全局最优解，研究学者最近开始利用谱方法来聚类。谱方法聚类是由数据点间相似关系建立矩阵，获取该矩阵的前个特征向量，并且用它们来聚类不同的数据点。谷瑞金[7]等提出基于谱聚类的两阶段颜色量化算法，先利用高效的二分K均值聚类进行粗略量化，然后使用基于加权距离的谱聚类进行再次量化，效果不错，但聚类时间太长。本文使用HSV颜色模型，给出了一种将三维颜色空间非均匀量化为32种代表颜色的方法，实现对颜色的初次量化；然后取量化后的颜色中心作为谱聚类中心，再利用谱聚类进行再次量化。再对量化后的颜色归一化，计算相似度。由于HSV量化速度快，实现简单，谱聚类适合各种数据集，使得新方法在运算速度和量化质量上都取得了不错的结果。2HSV空间中颜色的非均匀量化RGB颜色空间与人跟的感知差异很大，例如：距离为50的(0，0．0)与(50，0，0)两种颜色认为是同一黑色，而距离为50的(200，150，0)和(150，200，0)则认为是两种差异很大的颜色(黄色和绿色)。文中在处理颜色特征时采用了HSV颜色模型（见图1），该摸型较好的符合人眼的感知特性。实验表明：增加颜色直方图的维数可以有效地提高检索的精度，但当维数增加到一定程度时，检索的精度提高很小而且可能下降。因此在保持一定精度的前提下，可以通过减少颜色的维数来达到节省特征存储空间的目的。根据HSV空间的特性，在降低直方图的维数并保留足够的颜色信息前提下，对HSV空间进行非均匀量化得到32种代表颜色。首先将图象中每一象素的r，g，b值转换为h，s，v值(h∈[0，360)，s∈[0，1]，v∈[0，1])，具体的颜色量化和编码方法如下：(1)对于V20％的颜色认为是黑色。Code=1。(2)对于S10％且V20％的颜色按亮度V划分为四种灰度。分别为：深灰[20％，50％)、浅灰[50％，80％)和白色[80％，1]。Code=2，3，4。(3)其它颜色认为是彩色，将其划分为28种彩色。Code=5，632。(a)对色度H[0，360)划分为赤、橙、黄、绿、青、兰、紫7种彩色。门限分别为：（20，45，75，165．200，270，360。H=1，2，3，4，5．6，7。(b)对于亮度V划分为：暗色[20％，50％)和明色[50％，100％]。V=0，1。(c)对于饱和度s划分为：谈色[10％，45％]和浓色[45％，100％]。S=0，1。按照上面的方法将颜色空间共划分为4+7x2x2=32种颜色，并统计每种颜色的个数。每种颜色记为Hi（hh，si，vi）i=1，232。这32种代表色的量化、编码方法有效地压缩了颜色特征并较好的符台人服对颜色的感知特性。3使用谱聚类再次量化将32种颜色分别取量化后的平均值，如V20%时，取H=180，S=0.5，V=0.1，对H归一化得H=0.5；如V=0.5&&V=1.0&&S=0.45&&S=1.0&&H=270&&H=360，取V=0.75，S=0.725，H=0.875。然后对32种颜色值进行加权距离的谱聚类量化。谱聚类算法本质上是利用亲密矩阵的特征向量进行聚类。先给出一个定义：定义亲密矩阵：图G=(V，E)为加权无向图，节点i和j间的距离为d(i，j)，则A=2exp((,)/)dij为相似度，其中，d(i，j)可为各种距离度量。由Aij组成的对称矩阵A称为亲密矩阵。谱聚类算法的思路如下：首先根据某种度量计算亲密矩阵A，根据不同的准则构造拉普拉斯矩阵L，然后计算L的本征值和本征向量，由最大的c个本征值所对应的本征向量构成矩阵；最后，可假定矩阵每一行为c维空间中的数据点，采用普通的聚类算法对数据集进行聚类。亲密矩阵是谱聚类的关键。对于距离，一般采用欧氏距离。基于加权谱聚类的颜色量化算法如下：(1)计算颜色中心间的亲密矩阵A：iiA=0，当ij时，2exp((,)/)ijAdij，222(,)()()()ijijijdijhhssvv，iH（,,iiihsv）i=1，232；(2)计算拉普拉斯矩阵L，1122LDAD，其中D是对角化矩阵，其对角元素1niiikkdA；(3)计算L的最大的32个本征值(132,...,)和相应的本征向量(132,...,)，按照本征值的大小顺序将的本征向量组成矩阵S；(4)对矩阵中的每一行进行单位化处理，即将行向量转变为单位向量，得到矩阵'S；(5)将'S中的每一行视为R空间中的一个点，使用K均值算法，划分为c个簇。如果'S矩阵中的第i行属于第j个簇，则iH也属于第j个簇，其包含的数目也包含在第j个簇里，统计每个簇包含点的数目。其中c可以根据需要取值。c个簇也就是最后的c种量化颜色集。谱聚类算法适合各种形状的数据集，划分的簇和人的视觉理解更为吻合。但是亲密矩阵的计算和特征分解计算复杂度很高，如单纯使用谱聚类对所有的像素点进行聚类，是不现实的。这也是量化颜色划分为两个阶段的主要原因。4相似度度量先将量化后的C种颜色归一化。iN表示第i种颜色包含的象素数，Total=1ciiN，归一化后，iH=iN/Total，1()1ciHi，i=1，2c。根据直方图相交的相似性计算方法，任意两个c维的颜色直方图pH，qH的相似度pqS为：pqS=1min((),())cpqiHiHi，11()()1ccpqiiHiHi。其中，()pHi表示在颜色直方图p中属于颜色i的概率，()qHi表示在颜色直方图q中属于颜色i的概率。pqS为1时，两幅图象完全相似；为0时，完全不相似。5实验结果为了证实本文介绍的检索方法的有效性，对上述算法我们结合一个花卉图像库进行了检索实验，并与只基于HSV非均匀颜色量化的检索方法进行了比较，输出与样本图象相似的原始图象。图1.基于HSV颜色量化检索结果图图2.基于本文方法检索结果图Fig.1RetrievalresultsbasedonHSVFig.2RetrievalresultsbasedonHSVandspectral-clustering图1是HSV量化为32颜色进行检索结果；图2是在32种颜色基础上先保留Code=1，2，3，4四种颜色，对余下28种颜色进行谱聚类为4种颜色，总共八种颜色进行检索。因为前四种颜色多为背景颜色，所以保留了下来。我们输出了与样本图像最相似的16幅图像，按输出位置由左到右，再由上至下的顺序与样本图像的相似度依次递减。从输出的结果来看，利用本文介绍的方法检索输出的结果比基于HSV颜色量化的结果更符合人眼的视觉感受。因为所选样本图象的背景与目标差距大，而本文方法使背景和目标颜色可以分开计算，加权值更能突出目标颜色，所以检索效果要好些。但是只基于HSV量化的检索时间稍快。速度和精度不可能兼得，有时只能用一个换取另一个更好。6结论基于HSV量化和谱聚类，提出了一种新的颜色量化方法。HSV量化颜色简单，速度快；谱聚类适合各种数据集，量化质量高。两者结合考虑了速度和精度，使新算法在运算速度和量化质量上都有不错的结果。下一步的重点是如何是使用带加权距离的谱聚类应用到图象检索中，以及考虑颜色的空间分布信息。References:[1]ScheundersP．Ageneticapproachtowardsoptimalcolorimagequantization[J]．ImageProceing，1996，7(5)：1031—1034．[2]GerrautzM。PurgathoferW．Asimplemethodforcolorquantization：octreequantization[C].ProcofICG’98，1998，8(6)：219—230[3]ArthurR，WeeksG．ColorsegmentationintheHIScolorspaceusingthek-meansalgorithm[J]．SPIE，1997，9(6)：143—154．[4]LimYW，LeeSU．Onthecolorimage