基于分塊小波微粒群混合的圖像智能檢索

羅濤華,沈顯君

(1.武漢工業學院 計算機與信息工程系,湖北 武漢 430023;2.華中師范大學 計算機科學系,湖北 武漢 430079)

近年來,包括圖像在內的各種多媒體數據的數量正以驚人的速度增長,如何提供一個有效的算法來快速、準確地查詢這些具有豐富內涵的圖像信息成為當今檢索領域的研究熱點和難點之一.基于內容的圖像檢索CBIR(content based image retrieval)技術已成為解決這一問題的關鍵技術之一.該技術往往通過提取、比較圖像的特定特征而完成檢索.這些特征主要通過圖像像素的顏色分布[1]、圖像中物體的性質[2]、圖像的紋理[3]等表現出來.由于顏色旋轉、標度的不變性以及尺寸、方向的不敏感性等天然特性,使其成為圖像檢索系統中運用最為廣泛的特征之一.本文中分析當前基于直方圖的圖像檢索系統有限的有效性,將直方圖算法與小波分塊技術相結合,提出基于分塊小波變換的圖像檢索算法.小波變換能夠將圖像分解成若干具有不同頻率的子圖像,以提取整圖像的主要結構信息和細節信息,同時,圖像的空間特征通過分塊小波直方圖法進行描述,以增強檢索性能.

實驗證實,分塊小波圖像檢索算法雖然比直方圖算法的檢索準確率有了較大提高,但在執行速度上卻明顯變慢,因此,需要引入某種優化算法來加快其搜索速度.粒子群是近年來優化算法領域中強大的競爭者,它將圖像檢索描述為一個組合優化問題,而適應度函數則描述為圖像的相似性度量函數.適應度函數結合分塊圖像小波變換信息和顏色子直方圖中的歐氏距離來計算.據此,本文中提出一種新的檢索策略：將分塊小波技術和微粒群算法與一般的基于顏色直方圖的圖像檢索算法相結合,得到基于微粒群和分塊小波變換的圖像檢索新算法.

1 基于直方圖的相似度搜索

(1)

其中ri、gi、bi分別是紅色、綠色和藍色的第i個顏色值.直方圖描述了樣品在一組相鄰間隙內的分布.為了建立直方圖,圖像的每個像素均被作為能夠產生相對頻率矢量的取樣點[4].在RGBn顏色空間中,圖像I的顏色直方圖是矢量： H(I)=(hc1(L),hc2(L),…,hci(L),…)

(2)

(3)

其中,Ed表示的是圖像G和圖像S之間的歐氏距離,Ed越小,相似度就越大;gi是圖像G的顏色直方圖信息;si是圖像S的顏色直方圖信息;L為顏色級數.

我們稱上述方法為顏色直方圖圖像相似度檢索法(ContentHistogram-BasedImageRetrieval),簡稱為CHIR算法.此算法的核心思想是將圖像看成是一個整體,首先計算圖像的直方圖信息;然后通過歐氏距離公式對兩幅圖像的直方圖信息進行差值計算,得到兩幅圖像間的距離,距離越小,表示兩幅圖像相似度越高,反之也成立;最后按照距離從小到大的順序(也就是相似度從大到小的順序)顯示搜索結果.用CHIR算法進行多個算例的仿真實驗,得出各算例的圖像檢索率主要在0.4～1.0之間變化.檢索率是圖像檢索準確度的評價準則之一,其計量方法為η=nrelevant/Ngroup(nrelevant為搜索后特定組中檢索出的相似圖像數,Ngroup為當前組中的相似圖像的總數).該算法檢索率變化范圍較大,因為其只考慮到整幅圖像的直方圖信息,而不考慮空間位置等其他信息,導致檢索準確率低.

2 分塊小波直方圖算法

傳統的顏色直方圖只記錄顏色信息,因其稀疏、容易受噪音影響,故檢索精確度大打折扣,因此,一些直方圖信息類似的圖像其外觀可能有天壤之別.另外,顏色直方圖不包含任何空間信息,導致算法的性能較低.針對這一問題,我們將分塊小波技術和直方圖算法相結合,在一定程度上提高檢索結果.

小波是將數據分成不同頻率成分、然后使用與其標度匹配的分辨率對每個成分進行解讀的數學函數.如果進行了多尺度小波變換,即可獲得低頻率、高頻率成分.借助于這些低頻率、高頻率矢量,即可測得相似度,從而了解各層次的結構[5].

圖像相似度測量使用的是分塊小波直方圖法(BlockingWavelet-HistogramImageRetrieval),簡稱BWHIR算法.該方法將分塊小波與顏色直方圖的歐氏距離相結合.具體地說就是將原始圖像分割成N個小塊,分別對每個子塊進行小波分解,取出分解后的低頻信息部分,然后對每個子塊中的低頻部分分別計算子直方圖值,將原始圖像與待比較的圖像按子塊進行直方圖歐氏距離比較,最后計算各個子塊距離的平均值,即為兩幅圖像之間的分塊小波距離值,距離值越小表示兩幅圖像越相似,反之,兩幅圖像越不相似[6].圖1是一幅圖像的2×2小波分解.

圖1 2×2小波分解

在圖1中,LL1是圖像低頻率成分,LH1、HL1和HH1是高頻率成分.LH1是一般圖像水平方向低通、垂直方向高通的細節信號;HL1是一般圖像水平方向高通、垂直方向低通的細節信號,HH1是圖像對角線方向的細節信號.Sim(G,S)是兩個圖像的相似度測量.

(4)

兩個圖像的相似度測量值取各小塊相似度測量值的平均值,可以將其視為是涉及圖像檢索適應度的問題,并通過方程進行定義：

(5)

式中f(x)是是適應度函數,2n是分塊圖像的尺寸,Sim(i)表示第i個子塊的子直方圖距離.仿真實驗中用BWHIR算法對CHIR算法中所有算例進行檢索發現,其檢索率在[0.92,1.0]之間變化,比CHIR的[0.4,1.0]變化范圍明顯變小,且同組算例圖像的搜索效率均有較大提高.

3 分塊小波變換和微粒群混合算法

盡管BWHIR算法比CHIR算法具有更優越的效率,但是它們需一個個地將查詢圖與候選圖進行比較,因此在本質上屬于枚舉算法.如果圖像數據庫龐大,那么枚舉算法的運行效率則讓人無法容忍,因此需要尋找更加高效的圖像檢索法.研究發現結合微粒群算法能提供可行解.

3.1微粒群算法微粒群PSO(particleswarmoptimization)是一種基于群體智能理論的迭代優化算法.系統初始化為一組隨機解,并由目標函數為之確定一個適應值,每個粒子根據自己和其他粒子的飛行經驗在解空間中進行迭代搜索.假設在—個n維的搜索空間中,有m個粒子組成—個群體,其中第i個粒子的當前位置可以描述為Xi=(xi1,xi2,…,xin),將Xi代入一個目標函數就可以算出其適應值.第i個粒子的速度可表示為Vi=(vi1,vi2,…,vin);第i個粒子的個體最優值可表示為Pi=(pi1,pi2,…,pin);群體目前找到的最優值記為Pg=(pg1,pg2,…,pgn).每個粒子根據如下的公式來更新自己的速度和位置：

(6～7)

w(t)=(wini-wend)(Tmax-t)/Tmax+wend

(8)

其中T指的是當前迭代,Tmax是當前迭代的最大值,wini為初始慣性權重(一般取值0.9),wend為運行終止時的慣性權重(一般取值0.1).

從上述進化方程可以看出,在每次迭代中,粒子通過跟蹤自己搜索到的最好的解和整個粒子群經歷過的最好位置來不斷更新自己在解空間的位置和速度,從而產生下一代群體,這種特有的記憶使其可以動態跟蹤當前的搜索情況調整其搜索策略[8].因此從原理上可以把粒子群算法和圖像庫相似性搜索問題相結合,只需要根據進化算法,對圖像庫中的一部分圖像實行智能的選擇,代替每幅圖像依次進行匹配的方法,從而適當加快算法的執行速度.

3.2分塊小波與微粒群混合算法設計將檢索問題的可行解概念化為在圖像數據庫中飛行的粒子,其行為由搜索和共享群中圖像匹配信息的最佳適應度法則支配.粒子在數據庫中搜索圖像,并將數據庫中的候選圖像與搜得的圖像進行比較,其過程是粒子在解空間中的移動.圖像的序列號表示粒子的位置;粒子的速度描述在檢索過程中搜索到的兩個圖像之間位置的變化.

第i個粒子之前的最佳位置是該粒子已經搜索到了最佳匹配圖像序列號時的位置.最佳粒子的位置是目前為止整個粒子群在圖像數據庫中搜索到了最佳匹配圖像的序列號時的位置.即使粒子的速度受PSO最佳法則的影響不斷更新,但是其需要的是一個整數,因為粒子的位置也是整數.我們將該算法稱之為基于粒子群優化與分塊小波直方圖圖像檢索法,簡稱為BWPSOIR算法.

該算法的核心思想是用微粒群算法對圖像庫的搜索策略進行優化,將微粒群算法與小波分塊算法相結合,實現智能搜索的目的.首先對微粒群的初始位置和速度進行初始化,其過程為：(1)用一個字符串數組char *image[N]來存放圖像庫中所有圖像的名稱,這樣就可以將圖像i(i=0,1,2,…,N-1)作為微粒變量來考慮,從而設定群體規模N;(2)對任意微粒i的第j維,在[0,N-1]內服從均勻分布產生位置xij;(3)對任意i,j,在[0,Vmax],Vmax為設定的最大速度,一般取常數(3)內服從均勻分布產生速度vij.然后通過群體中微粒的相互作用和競爭產生的群體智能指導優化搜索,它特有的記憶使其可以動態跟蹤當前的搜索情況調整其搜索策略,當達到結束條件(通常為足夠好的適應值)或達到一個預設最大代數(Gmax),則搜索結束.

算法設計的具體步驟為：(1) 輸入待搜索的原始圖像的名稱,計算其小波分塊直方圖信息;

(2) 初始隨機選擇n個圖像為初始解Xi=(xi1,xi2,…,xin),并對其速度Vi=(vi1,vi2,…,vin)進行初始化;

(3) 根據式(4)和式(5)計算圖像庫中每個圖像的適應值,即分別計算初始解中各幅圖像與輸入圖像的距離;

(4) 對每個微粒(圖像),將其適應值與所經歷過的最好位置Pi的適應值進行比較,取優作為當前的最好位置;

(5) 對每個微粒,將其適應值與全局所經歷的最好位置Pg的適應值進行比較,取優作為當前的全局最好位置;

(6) 根據(6)、(7)和(8)式對微粒的速度和位置進行進化;

(7) 如未達到結束條件(通常為足夠好的適應值或一個預設最大代數),則返回步驟(3);達到則結束.

4 實驗結果及分析

為了評估上述3種方法的有效性,我們借助于哥倫比亞侯選圖像圖書館(COIL-12,為一開放的網上圖像數據庫)、MATLAB7.0.6和Microsoft Visual C++6.0模擬軟件進行最佳匹配圖像檢索實驗,同時記錄每組圖像的匹配檢索結果和算法的運行時間,算法的性能主要用圖像搜索準確率和檢索時間來度量.我們將下載的20 000張圖像進行分析整理形成試驗用圖像庫,并根據圖像的相似程度不同將它們分成100組,每組200張,組編號為obj1～obj100,每組中的待匹配圖片按位置順序依次編號為1～200,每個查詢圖像隨機從試驗用圖像數據庫中抽取,每個圖像被分成尺寸為16×16的小塊 .

因為算例數組太多,我們抽取3組(其中汽車、貓、小豬的樣品各取200)顯示檢索的圖像結果.圖2、圖4和圖6是隨機從第一組、第二組和第三組圖像中抽取出來的3個查詢圖像.圖3、圖5和圖7是通過BWPSOIR算法獲得的5個最佳匹配圖像(匹配度從大到小).

圖2 第一組的查詢圖

圖3 第一組的最佳匹配圖像

圖4 第二組的查詢圖

圖5 第二組的最佳匹配圖像

圖6 第三組的查詢圖

圖7 第三組的最佳匹配圖像

通過對記錄的3種算法同組最佳匹配圖像檢索結果分析可知,BWPSOIR算法和BWHIR算法所得到的結果圖像與輸入的原始圖像更相似,而用CHIR算法進行最佳匹配圖像檢索則容易陷入直方圖與輸入圖像相似的干擾圖像中,往往得不到正確的圖像結果.

表1記錄了上述3種方法在圖像數據庫中檢索相同查詢圖像時的檢索效率和所用的檢索時間.

表1 檢索效率和檢索時間

通過對表1中的數據結果進行比較分析可知,在進行最佳匹配圖像檢索時,CHIR算法速度最快、檢索效率最低;BWHIR算法速度最慢,需要用多出CHIR算法幾倍的時間,而檢索效率幾乎與BWPSOIR算法一樣好;BWPSOIR算法速度介于前兩種算法之間、但檢索效率最高.

5 結束語

本文中提出了一個結合分塊圖像小波直方圖和粒子群優化的新型圖像檢索方法.通過對粒子的速度和位置進行定義,將圖像檢索描述為一種組合優化問題,將自適應性粒子優化用于基于內容的圖像檢索,同時,粒子的重量由其自適應性確定.試驗結果顯示,該算法引入小波技術提高了特征提取的有效性;采用分塊技術提高了圖像檢索性能;結合微粒群算法進行智能搜索加快了算法的執行速度.因此,BWPSOIR算法既解決了檢索的準確率,同時又較好地完善了檢索的速度問題,從而為大型圖像數據庫的智能圖像檢索問題提供了解決方案.

參考文獻：

[1] Maurice Clerc,Kennedy James.The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[2] Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources[C].Proceedings of the IEEE Congress on Evolutionary Computation, 2001:81-86.

[3] 汪祖媛,梁棟,李斌.基于樹狀小波分解的紋理圖像檢索[J].中國圖象圖形學報,2001,6(11):1065-1069.

[4] Xie Chao, Wei Chengjian, xu Jun. Evolutionary wavelet-based similarity search in image databases[C]. IEEE Int Workshop VLSI Design & Video Tech,2005,(28/30):385-388.

[5] 史燕.基于小波變換的圖像檢索技術研究[D]. 西北大學,2006.

[6] 朱曉華.基于微粒群和小波變換的圖像檢索算法研究[D].華中師范大學,2008.

[7] Shi Y, Eberhart R.Empirical study of particle swarm optimization[C].Proceedings of the IEEE Congress on Evolutionary Computation,1999:1945-1950.

[8] Angeline P J.Evolutionary optimization versus particle swarm optimization: philosophy and performance difference[J]. Proceedings of the 7th International Conference on Evolutionary Programming Conference,Lecture Notes in computer Science,2003,3(1):601-610.