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

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

　　?

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

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

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

1 圖像檢索框架?

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

1.1圖像建模?

　　高斯混合模型具有良好的統(tǒng)計(jì)特性,被廣泛用于統(tǒng)計(jì)模式識(shí)別、統(tǒng)計(jì)信號(hào)處理等領(lǐng)域。?

??? 高斯混合模型的概率密度函數(shù)為:?

?????

式中,x是k維特征向量,L是高斯混合成份個(gè)數(shù),wi表示第i個(gè)高斯混合成份的權(quán)值且∑w_i=1,第i個(gè)高斯混合成份表示為:?

?????

式中,u_i、Σ_i分別是高斯混合成份的均值向量、協(xié)方差矩陣。?

　　本文采用Lloyd聚類算法對圖像進(jìn)行高斯混合建模,估計(jì)其參數(shù)。算法步驟如下:?

　　(1) 初始化:初始化高斯混合成份{g_m,m=1,…,L},記迭代次數(shù)為n、初始失真為D₀和閾值為T。?

　　(2) 尋找最小失真,滿足:?

式中,k_m是特征向量x_i聚類到混合成份g_m的個(gè)數(shù),N是特征向量總數(shù)。?

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

　　d(x_i,g_m)是特征向量x_i與高斯混合成份g_m間的距離,采用參考文獻(xiàn)[3]所用的平方誤差失真SED(Squared Error Distortion)和量化錯(cuò)匹失真QMD(Quantizer Mismatch Distortion)度量:?

　　對圖像進(jìn)行Lloyd聚類后,圖庫中的每一幅圖像可以用高斯混合成份表示,得到高斯混合成份參數(shù)。完成圖像高斯混合建模后,下一步是度量圖像間的相似度。?

1.2 EMD相似度量?

　　EMD度量是Rubner等人提出的一種相似度量,它把運(yùn)籌學(xué)的運(yùn)輸問題引入到圖像檢索中,采用最優(yōu)化求解最小運(yùn)輸成本的方法來度量圖像間的相似性^[1]。?

　　EMD度量的數(shù)學(xué)模型描述^[4]:設(shè)某產(chǎn)品有m個(gè)產(chǎn)地A₁,…,A_m,供應(yīng)量分別為w_a1,…,w_am;n個(gè)銷地B₁,…,B_n的需求量分別為w_b1,…,w_bn;產(chǎn)品從產(chǎn)地A_i運(yùn)輸?shù)戒N地B_j的單位運(yùn)價(jià)為d_ij,求怎樣分配從產(chǎn)地A_i到銷地B_j的運(yùn)輸量f_ij,才能使總運(yùn)輸成本最小。圖1是m=3、n=2的EMD模型。

?

?

??? 目標(biāo)函數(shù)為:?

???

式(15)中的分母是規(guī)范化因子。?

　　在圖像檢索中,利用EMD計(jì)算圖像間相似度時(shí),d_ij對應(yīng)圖像高斯混合成份間的距離(在參考文獻(xiàn)[2]中稱為基本距離),可以通過d_SED或d_QMD來計(jì)算;w_ai、w_bj對應(yīng)圖像高斯混合成份的權(quán)值。?

2 近似EMD方法?

　　EMD方法的數(shù)學(xué)模型是一個(gè)線性規(guī)劃問題,參考文獻(xiàn)[2]采用的是單純形法求解,其計(jì)算復(fù)雜度為O(n³log n),其中,n是圖像高斯混合成份個(gè)數(shù)。在圖像檢索中,w_ai、w_bj分別對應(yīng)高斯混合成份的權(quán)值,公式(12)、公式(13)變?yōu)榈仁?而且有:?

?????

則EMD方法簡化為產(chǎn)銷平衡問題,f_ij有m×n個(gè)決策變量,m+n個(gè)約束條件,而且滿足公式(16),f_ij系數(shù)矩陣的值小于等于m+n-1?？紤]到在圖像檢索中,權(quán)值系數(shù)矩陣f_ij的特殊性,可以通過表上作業(yè)法^[4]計(jì)算f_ij。本文采用最小元素法(MFM)和近似EMD的Vogel法,這兩種方法類似Kruskal最小生成樹聚類算法^[5],符合計(jì)算機(jī)視覺中的感知相似性。由最小生成樹性質(zhì)可知f_ij非零元素個(gè)數(shù)為m+n-1。?

　　在圖像檢索中,表上作業(yè)法的產(chǎn)銷平衡表和運(yùn)價(jià)表如表1和表2所示,分別對應(yīng)權(quán)值分配表和高斯混合成份間的距離表。下面詳述這兩種近似EMD方法。?

?

?

?

2.1最小元素法(MFM)?

　　在產(chǎn)銷平衡表中,盡量滿足運(yùn)價(jià)表中最小元素d_ij對應(yīng)的f_ij,算法步驟如下:?

　　(1) 初始化產(chǎn)銷平衡表,f_ij←0。?

　　(2) 在運(yùn)價(jià)表中找出最小元素d_ij。?

　　(3) 在產(chǎn)銷平衡表中,找出d_ij對應(yīng)的f_ij,f_ij←min{w_ai,w_bj},如果w_ai>w_bj,在運(yùn)價(jià)表中劃去d_ij所在的第j列,w_ai ←(w_ai-w_bj);否則在運(yùn)價(jià)表中劃去d_ij所在的第i行,w_bj←(w_bj-w_ai)。?

　　(4) 返回第(2)步,直至運(yùn)價(jià)表中所有元素被劃去。?

　　規(guī)范化m=n,第(3)步最差的情況是交叉地劃去運(yùn)價(jià)表中的行、列,劃去行后查找最小元素d_ij循環(huán)(i²-i)次,再劃去列后查找最小元素d_ij循環(huán)i²次,則算法最多的循環(huán)次數(shù)為:?

?????

??? 上述算法的計(jì)算復(fù)雜度為O(n³)。?

2.2 Vogel法?

　　在產(chǎn)銷平衡表中,盡量滿足運(yùn)價(jià)表中行(列)最小、次小元素差額最大的最小元素d_ij對應(yīng)的f_ij,算法步驟如下:?

　　(1) 初始化產(chǎn)銷平衡表,f_ij←0。?

　　(2) 在運(yùn)價(jià)表中,找出行(列)最小元素與次小元素之差最大所在的行(列),得該行(列)的最小元素d_ij。?

　　(3) 在產(chǎn)銷平衡表中,找出d_ij對應(yīng)的f_ij,f_ij←min{w_ai, w_bj},如果w_ai>w_bj,在運(yùn)價(jià)表中劃去d_ij所在的第j列,w_ai←(w_ai-w_bj);否則在運(yùn)價(jià)表中劃去d_ij所在的第i行,w_bj←(w_bj-w_ai)。?

　　(4) 返回第(2)步,直至運(yùn)價(jià)表中所有元素被劃去。?

　　類似最小元素法,規(guī)范化m=n,第(3)步最差的情況是交叉地劃去運(yùn)價(jià)表中的行、列,劃去行后查找最小、次小元素差額最大的最小元素d_ij循環(huán)[i+(i-1)+1](i-1)+[(i-1)+(i-2)+1]i=4(i²-i)次,再劃去列后查找最小次小元素差額最大的最小元素d_ij循環(huán)[i+( i-1)+1]2i=4i²次,那么算法最多的循環(huán)次數(shù)為:?

???

??? 上述算法的計(jì)算復(fù)雜度為O(n³)。?

　　根據(jù)最小元素法和Vogel法計(jì)算f_ij,則圖像A、B間的相似度定義為:?

?????

3實(shí)驗(yàn)結(jié)果與分析?

　　本文實(shí)驗(yàn)采用Corel圖像庫,從中選取非洲、海灘、建筑、汽車、恐龍、大象、花、馬、雪山、食物共10類,每類100幅圖像。將圖像從RGB顏色空間轉(zhuǎn)化到CIE-Luv顏色空間^[6],考慮到像素間的空間關(guān)系,把圖像劃分為不相交的8×8子塊^[7],提取顏色和紋理特征^[8]。利用Lloyd聚類算法[3]對圖像特征向量進(jìn)行高斯混合建模,以及利用EMD、MFM、Vogel三種方法度量圖像間的相似性。檢索效率采用查準(zhǔn)率-查全率^[9]評價(jià),查準(zhǔn)率是返回的相關(guān)圖像數(shù)與總的返回圖像數(shù)的比例,查全率是返回圖像數(shù)與圖庫總數(shù)的比例。三種方法的效率比較如圖 2所示,在兩種基本距離下,MFM法和Vogel法檢索效率與EMD法接近。圖 3、圖 4、圖5分別是以各自圖中的第一幅圖像作為例子以利用EMD、MFM、Vogel方法檢索返回的前20幅圖像。?

?

?

?

?

?

　　從圖2可以看出,EMD-QMD與EMD-SED檢索效率接近。本文圖像檢索框架對基本距離的選擇不敏感,而L₁ (Manhattan距離)與L₂(歐氏距離)在圖像檢索中的效率相似^[10],可以采用計(jì)算更為簡單的L₁作為基本距離。當(dāng)采用SED度量時(shí),EMD、MFM、Vogel方法實(shí)際上變成了二次距離,類似Mahalanobis距離,不同的Mahalanobis距離的加權(quán)矩陣是其協(xié)方差矩陣^[10],本文只是在加權(quán)時(shí)采用不同的策略。三種相似度量算法權(quán)值分配的策略分別是:EMD是從整體高斯混合考慮,使加權(quán)距離最小;MFM考慮局部高斯混合成份間的距離最小,使行(列)最小元素優(yōu)先;Vogel也是從局部高斯混合成份考慮,只是采用的是行(列)最小與次小元素差額距離最大的最小元素優(yōu)先,而且Vogel更接近EMD。?

　　EMD是一種有效的相似度量,本文把原EMD模型簡化為產(chǎn)銷平衡問題,提出兩種權(quán)值分配方法近似EMD應(yīng)用于圖像檢索時(shí),能達(dá)到與EMD接近的檢索效率,而且對基本距離的選擇不敏感。最小元素法、Vogel法在權(quán)值分配時(shí),采用最小元素優(yōu)先,即最相似優(yōu)先,比EMD法更符合人的感知,而且計(jì)算復(fù)雜度從原來的O(n³log n)降到O(n³),在一些實(shí)時(shí)計(jì)算要求較高的情況下,最小元素法更能體現(xiàn)其優(yōu)勢。鑒于EMD在計(jì)算機(jī)視覺、模式識(shí)別、機(jī)器學(xué)習(xí)的廣泛應(yīng)用,最小元素法、Vogel法也可以應(yīng)用于相關(guān)的領(lǐng)域,如圖像分類、識(shí)別、分割、聚類等。?

參考文獻(xiàn)?

[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] 孫麟平. 運(yùn)籌學(xué)[M]. 北京:科學(xué)出版社,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.?