摘  要: 相似度量是图像检索的关键,EMD是一种有效的度量距离,但其计算比较复杂,而且依赖于基本距离的选择。采用Lloyd聚类算法对图像进行高斯混合建模,并以聚类失真作为基本距离,提出了两种近似EMD的方法计算相似度。实验结果验证了该方法的有效性,其检索效率与EMD方法接近,而且计算复杂度比EMD方法低,基本距离的选择不敏感。 

　　关键词: 图像检索; 劳埃德聚类; 推土机距离; 最小元素法; 伏格尔法 

　　 

　　随着数码设备的普及和互联网的兴起,每天都将产生海量数字图像。为了有效地存储、管理图像数据库,需要对图像库进行索引,按特定的需求检索图像。以往的图像检索模式是基于文本的,采用关键字的方法,需要大量的人工注释,而且注释内容也存在很大的主观差异性,往往不能反映图像的本质内容。基于内容的图像检索(CBIR)克服了传统方法的缺陷,直接利用图像的内容如颜色、纹理、形状、空间关系等进行检索。特征提取和相似度量是CBIR的两个关键步骤,特征提取是用颜色等特征按一定的方式概括图像内容,从而获得图像的特征分布。相似度量是计算特征分布间的距离,并以此作为图像间的相似度。常用的相似度量有Minkowski距离度量、直方图相交度量、Jeffrey散度度量、K-L散度度量等^[1]。 

　　EMD(Earth Mover's Distance)是一种反映计算机视觉感知相似性的距离度量,被广泛用于计算机视觉、模式识别、机器学习等领域。图像特征分布聚类后得到称为签名(Signature)的聚类中心及相应的权值。EMD考虑了不同签名的重要性,使总的签名间距离最小。EMD方法可以计算具有不同签名个数的图像间距离,是一种多对多的匹配方法,所以能计算部分匹配。如果签名间的距离即基本距离(Ground Distance)是一种度量(metric),那么EMD也是一种度量。但EMD计算比较复杂,不同应用需根据要求选择有效的基本距离^[2]。本文提出两种近似EMD方法(最小元素法(MFM)和Vogel法)计算图像间的相似度,其计算复杂度比EMD方法低。在本文图像检索框架下,两种近似EMD的方法对基本距离的选择不敏感。 

　　本文首先采用Lloyd聚类算法^[3]对图像进行高斯混合建模,并以Lloyd聚类失真作为基本距离,然后提出两种近似EMD的方法计算图像间的相似度,最后根据图像间的相似度大小返回检索结果。 

1 图像检索框架 

　　图像检索首先要提取图像特征向量,对图像进行建模,然后度量图像间的相似度,最后根据相似度大小返回检索结果。 

1.1图像建模 

　　高斯混合模型具有良好的统计特性,被广泛用于统计模式识别、统计信号处理等领域。 

    高斯混合模型的概率密度函数为: 

     

式中,x是k维特征向量,L是高斯混合成份个数,wi表示第i个高斯混合成份的权值且∑w_i=1,第i个高斯混合成份表示为: 

     

式中,u_i、Σ_i分别是高斯混合成份的均值向量、协方差矩阵。 

　　本文采用Lloyd聚类算法对图像进行高斯混合建模,估计其参数。算法步骤如下: 

　　(1) 初始化:初始化高斯混合成份{g_m,m=1,…,L},记迭代次数为n、初始失真为D₀和阈值为T。 

　　(2) 寻找最小失真,满足: 

　　

式中,k_m是特征向量x_i聚类到混合成份g_m的个数,N是特征向量总数。 

　　(4) 如果|D_n-1-D_n|/D_n-1

　　d(x_i,g_m)是特征向量x_i与高斯混合成份g_m间的距离,采用参考文献[3]所用的平方误差失真SED(Squared Error Distortion)和量化错匹失真QMD(Quantizer Mismatch Distortion)度量: 

　　

　　对图像进行Lloyd聚类后,图库中的每一幅图像可以用高斯混合成份表示,得到高斯混合成份参数。完成图像高斯混合建模后,下一步是度量图像间的相似度。 

1.2 EMD相似度量 

　　EMD度量是Rubner等人提出的一种相似度量,它把运筹学的运输问题引入到图像检索中,采用最优化求解最小运输成本的方法来度量图像间的相似性^[1]。 

　　EMD度量的数学模型描述^[4]:设某产品有m个产地A₁,…,A_m,供应量分别为w_a1,…,w_am;n个销地B₁,…,B_n的需求量分别为w_b1,…,w_bn;产品从产地A_i运输到销地B_j的单位运价为d_ij,求怎样分配从产地A_i到销地B_j的运输量f_ij,才能使总运输成本最小。图1是m=3、n=2的EMD模型。

 

 

    目标函数为: 

   

式(15)中的分母是规范化因子。 

　　在图像检索中,利用EMD计算图像间相似度时,d_ij对应图像高斯混合成份间的距离(在参考文献[2]中称为基本距离),可以通过d_SED或d_QMD来计算;w_ai、w_bj对应图像高斯混合成份的权值。 

2 近似EMD方法 

　　EMD方法的数学模型是一个线性规划问题,参考文献[2]采用的是单纯形法求解,其计算复杂度为O(n³log n),其中,n是图像高斯混合成份个数。在图像检索中,w_ai、w_bj分别对应高斯混合成份的权值,公式(12)、公式(13)变为等式,而且有: 

     

则EMD方法简化为产销平衡问题,f_ij有m×n个决策变量,m+n个约束条件,而且满足公式(16),f_ij系数矩阵的值小于等于m+n-1。考虑到在图像检索中,权值系数矩阵f_ij的特殊性,可以通过表上作业法^[4]计算f_ij。本文采用最小元素法(MFM)和近似EMD的Vogel法,这两种方法类似Kruskal最小生成树聚类算法^[5],符合计算机视觉中的感知相似性。由最小生成树性质可知f_ij非零元素个数为m+n-1。 

　　在图像检索中,表上作业法的产销平衡表和运价表如表1和表2所示,分别对应权值分配表和高斯混合成份间的距离表。下面详述这两种近似EMD方法。 

 

 

 

2.1最小元素法(MFM) 

　　在产销平衡表中,尽量满足运价表中最小元素d_ij对应的f_ij,算法步骤如下: 

　　(1) 初始化产销平衡表,f_ij←0。 

　　(2) 在运价表中找出最小元素d_ij。 

　　(3) 在产销平衡表中,找出d_ij对应的f_ij,f_ij←min{w_ai,w_bj},如果w_ai>w_bj,在运价表中划去d_ij所在的第j列,w_ai ←(w_ai-w_bj);否则在运价表中划去d_ij所在的第i行,w_bj←(w_bj-w_ai)。 

　　(4) 返回第(2)步,直至运价表中所有元素被划去。 

　　规范化m=n,第(3)步最差的情况是交叉地划去运价表中的行、列,划去行后查找最小元素d_ij循环(i²-i)次,再划去列后查找最小元素d_ij循环i²次,则算法最多的循环次数为: 

     

    上述算法的计算复杂度为O(n³)。 

2.2 Vogel法 

　　在产销平衡表中,尽量满足运价表中行(列)最小、次小元素差额最大的最小元素d_ij对应的f_ij,算法步骤如下: 

　　(1) 初始化产销平衡表,f_ij←0。 

　　(2) 在运价表中,找出行(列)最小元素与次小元素之差最大所在的行(列),得该行(列)的最小元素d_ij。 

　　(3) 在产销平衡表中,找出d_ij对应的f_ij,f_ij←min{w_ai, w_bj},如果w_ai>w_bj,在运价表中划去d_ij所在的第j列,w_ai←(w_ai-w_bj);否则在运价表中划去d_ij所在的第i行,w_bj←(w_bj-w_ai)。 

　　(4) 返回第(2)步,直至运价表中所有元素被划去。 

　　类似最小元素法,规范化m=n,第(3)步最差的情况是交叉地划去运价表中的行、列,划去行后查找最小、次小元素差额最大的最小元素d_ij循环[i+(i-1)+1](i-1)+[(i-1)+(i-2)+1]i=4(i²-i)次,再划去列后查找最小次小元素差额最大的最小元素d_ij循环[i+( i-1)+1]2i=4i²次,那么算法最多的循环次数为: 

   

    上述算法的计算复杂度为O(n³)。 

　　根据最小元素法和Vogel法计算f_ij,则图像A、B间的相似度定义为: 

     

3实验结果与分析 

　　本文实验采用Corel图像库,从中选取非洲、海滩、建筑、汽车、恐龙、大象、花、马、雪山、食物共10类,每类100幅图像。将图像从RGB颜色空间转化到CIE-Luv颜色空间^[6],考虑到像素间的空间关系,把图像划分为不相交的8×8子块^[7],提取颜色和纹理特征^[8]。利用Lloyd聚类算法[3]对图像特征向量进行高斯混合建模,以及利用EMD、MFM、Vogel三种方法度量图像间的相似性。检索效率采用查准率-查全率^[9]评价,查准率是返回的相关图像数与总的返回图像数的比例,查全率是返回图像数与图库总数的比例。三种方法的效率比较如图 2所示,在两种基本距离下,MFM法和Vogel法检索效率与EMD法接近。图 3、图 4、图5分别是以各自图中的第一幅图像作为例子以利用EMD、MFM、Vogel方法检索返回的前20幅图像。 

 

 

 

 

 

　　从图2可以看出,EMD-QMD与EMD-SED检索效率接近。本文图像检索框架对基本距离的选择不敏感,而L₁ (Manhattan距离)与L₂(欧氏距离)在图像检索中的效率相似^[10],可以采用计算更为简单的L₁作为基本距离。当采用SED度量时,EMD、MFM、Vogel方法实际上变成了二次距离,类似Mahalanobis距离,不同的Mahalanobis距离的加权矩阵是其协方差矩阵^[10],本文只是在加权时采用不同的策略。三种相似度量算法权值分配的策略分别是:EMD是从整体高斯混合考虑,使加权距离最小;MFM考虑局部高斯混合成份间的距离最小,使行(列)最小元素优先;Vogel也是从局部高斯混合成份考虑,只是采用的是行(列)最小与次小元素差额距离最大的最小元素优先,而且Vogel更接近EMD。 

　　EMD是一种有效的相似度量,本文把原EMD模型简化为产销平衡问题,提出两种权值分配方法近似EMD应用于图像检索时,能达到与EMD接近的检索效率,而且对基本距离的选择不敏感。最小元素法、Vogel法在权值分配时,采用最小元素优先,即最相似优先,比EMD法更符合人的感知,而且计算复杂度从原来的O(n³log n)降到O(n³),在一些实时计算要求较高的情况下,最小元素法更能体现其优势。鉴于EMD在计算机视觉、模式识别、机器学习的广泛应用,最小元素法、Vogel法也可以应用于相关的领域,如图像分类、识别、分割、聚类等。 

参考文献 

[1] RUBNER Y, PUZICHA J, TOMASI C, et al. Empirical evaluation of dissimilarity measures for color and     texture.Computer Vision and Image Understanding, 2001,(84):25-43. 

[2] AIYER A, PYUNB K, HUANG Y, et al. Lloyd clustering of gauss mixture models f-or image compression and classification. Signal Processing: Image Communication, 2005,(20):459-485. 

[3] 孙麟平. 运筹学[M]. 北京:科学出版社,2005. 

[4] THEODORIDIS S, KOUTROUMBAS K. Pattern recognition. 2nd ed.[S. l.]:Academic Press, 2003. 

[5] WYSZECKI G, STILES W S. Color science: Concepts and methods, quantitative data and formulae. 2nd ed. Wiley, 2000. 

[6] JEONG S, WON C S, GRAY R M. Image retrieval using color histograms generated by gauss mixture vector quantization. Computer Vision and Image Understanding, 2004,(94):44-66. 

[7] LIAPIS S, TZIRITAS G. Color and texture image retrieval using chromaticity histo-grams and wavelet frames. IEEE Trans. Multimedia, 2004,6:676-686. 

[8] SMITH J R, CHANG S F. Tools and techniques for color image retrieval. In: Proc. of SPIE: Storage and Retrieval for Image and Video Database, 1996:426-437. 

[9] ANDROUTSOS D, PLATANIOTIS K N, VENETSANOPOULOS A N. A novel vect-or based approach to color     image retrieval using a vector angular-based distance  

measure. Computer Vision and Image Understanding, 1999, 75(1/2):46-58. 

[10] ZHANG D, LU G. Evaluation of similarity measurement for image retrieval. IEEE Int. Conf. Neural Networks and Signal Processing, 2003,(2):928-931.