摘? 要: 相似度量是圖像檢索" title="圖像檢索">圖像檢索的關鍵,EMD是一種有效的度量距離,但其計算比較復雜,而且依賴于基本距離的選擇。采用Lloyd聚類" title="聚類">聚類算法對圖像進行高斯" title="高斯">高斯混合建模,并以聚類失真作為基本距離,提出了兩種近似EMD的方法計算相似度。實驗結果驗證了該方法的有效性,其檢索效率與EMD方法接近,而且計算復雜度比EMD方法低,基本距離的選擇不敏感。?

　　關鍵詞: 圖像檢索; 勞埃德聚類; 推土機距離; 最小元素法; 伏格爾法?

　　?

　　隨著數碼設備的普及和互聯網的興起,每天都將產生海量數字圖像。為了有效地存儲、管理圖像數據庫,需要對圖像庫進行索引,按特定的需求檢索圖像。以往的圖像檢索模式是基于文本的,采用關鍵字的方法,需要大量的人工注釋,而且注釋內容也存在很大的主觀差異性,往往不能反映圖像的本質內容。基于內容的圖像檢索(CBIR)克服了傳統方法的缺陷,直接利用圖像的內容如顏色、紋理、形狀、空間關系等進行檢索。特征提取和相似度量是CBIR的兩個關鍵步驟,特征提取是用顏色等特征按一定的方式概括圖像內容,從而獲得圖像的特征分布。相似度量是計算特征分布間的距離,并以此作為圖像間的相似度。常用的相似度量有Minkowski距離度量、直方圖相交度量、Jeffrey散度度量、K-L散度度量等^[1]。?

　　EMD(Earth Mover's Distance)是一種反映計算機視覺感知相似性的距離度量,被廣泛用于計算機視覺、模式識別、機器學習等領域。圖像特征分布聚類后得到稱為簽名(Signature)的聚類中心及相應的權值" title="權值">權值。EMD考慮了不同簽名的重要性,使總的簽名間距離最小。EMD方法可以計算具有不同簽名個數的圖像間距離,是一種多對多的匹配方法,所以能計算部分匹配。如果簽名間的距離即基本距離(Ground Distance)是一種度量(metric),那么EMD也是一種度量。但EMD計算比較復雜,不同應用需根據要求選擇有效的基本距離^[2]。本文提出兩種近似EMD方法(最小元素法(MFM)和Vogel法)計算圖像間的相似度,其計算復雜度比EMD方法低。在本文圖像檢索框架下,兩種近似EMD的方法對基本距離的選擇不敏感。?

　　本文首先采用Lloyd聚類算法^[3]對圖像進行高斯混合建模,并以Lloyd聚類失真作為基本距離,然后提出兩種近似EMD的方法計算圖像間的相似度,最后根據圖像間的相似度大小返回檢索結果。?

1 圖像檢索框架?

　　圖像檢索首先要提取圖像特征向量" title="特征向量">特征向量,對圖像進行建模,然后度量圖像間的相似度,最后根據相似度大小返回檢索結果。?

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.