綜合顏色塊的直方圖圖像檢索算法

孫延維， 雷建軍*， 蘇 丹

(1.湖北第二師范學院 基礎教育信息技術服務湖北省協同創新中心， 武漢 430205；2.重慶郵電大學 計算機科學與技術學院， 重慶 400065)

?

綜合顏色塊的直方圖圖像檢索算法

孫延維1， 雷建軍1*， 蘇 丹2

(1.湖北第二師范學院 基礎教育信息技術服務湖北省協同創新中心， 武漢 430205；2.重慶郵電大學 計算機科學與技術學院， 重慶 400065)

為了進一步提高基于顏色直方圖的圖像檢索算法的效率，本文提出一種尋找圖像中最大顏色塊、提取其局部直方圖，并與原直方圖綜合的新算法.該算法在保留原算法的同時，添加了色彩的空間分布特征，從而降低檢索結果對顏色的絕對依賴.仿真實驗結果表明，本文算法具有較好的查準率和查全率，對色塊明顯的圖像檢索效果尤其顯著.

圖像檢索； 顏色直方圖； 顏色塊； 特征向量

伴隨著數字信息化和因特網技術的普及，數字圖像資源的增長速度越來越快.要對大規模的并且正在不斷增加的圖像集進行人工的自由文本描述就顯得力不從心，不能適應網絡多媒體信息檢索的要求.90年代以后，基于內容的圖像檢索(CBIR)技術應運而生，從圖像自身內容信息的角度來檢索圖像庫[1-2].圖像特征的提取與描述是該技術的基礎，目前主要采用圖像的底層視覺特征(如顏色、紋理、形狀)描述圖像內容信息[3].

顏色作為最穩定的視覺特征，一直是圖像檢索使用的主要特征之一.其中顏色直方圖更是以計算簡單且具有旋轉、平移不變性等優點，成為圖像檢索應用最為廣泛的顏色特征[4].但其最大的缺點就是缺少顏色空間分布信息.研究者對如何描述顏色空間信息做了大量的研究.文獻[5-6]將顏色特征與其它低級視覺特征，如紋理、邊緣特征以及空間屬性相結合，以提高檢索性能.但加入紋理等特征之后，會不可避免地破壞原有算法的變形、旋轉、縮放不變性.文獻[7]對簡單的分塊方法做了改進，突出圖像中間的主體部分和充分限制背景的范圍，提出了新的分割方法，對每個區域提取顏色特征的同時對中央區域賦予較大的權值.由于圖像分割本身就是一個難題，分割結果很難精確，故檢索效果并不理想.文獻[8] 結合顏色在圖像中的散布情況，綜合顏色的統計特征與空間分布特征來描述圖像內容，提出了一種新的顏色量化方法.但在實驗中，當采用不同的相似性度量方法時，對檢索效果影響較大.文獻[9]突破了傳統依據圖像亮度信息尋找感興趣點的檢索算法，發明了一種新的基于拐點的興趣點提取方法.由于提取方法不夠準確，且沒有考慮圖像局部相關性，故檢索效果一般.

本文作者注意到導致傳統直方圖檢索算法效率不高的情形中，圖像中大片色塊的大小以及色塊中包含的顏色種類差異也很大.如果采用顏色直方圖比較兩幅圖的相似性，只是在同一灰度值色彩的數量之間進行比較，沒有反映出顏色在空間分布的不同，因此造成空間信息的丟失.如果能夠找到圖像中最大的色塊，并記下色塊所在的位置，提取色塊的局部顏色直方圖，就能間接反映色彩的空間信息，從而增強分辨能力，提高檢索效率.改進后的算法是從色彩中尋找空間信息，為了在改進的同時能夠兼顧原有算法效率，將傳統直方圖的特征向量和最大色塊的局部特征向量合并在一起得到原始圖像的一個綜合的空間顏色特征向量.當在直方圖中引入最大色塊的局部直方圖時，能夠在一定程度上反映表征一幅圖像主題顏色形成的色區域形狀特點，從而降低檢索結果對顏色的絕對依賴，提高分辨能力.本文利用這一特點，對傳統的顏色直方圖檢索算法進行了改進，添加了算法區分空間分布差異的能力，同時保留了原算法的有效性，使得新算法的檢索性能有了較大的提高.

1 算法介紹

1.1 基于直方圖的圖像檢索

顏色特征是圖像檢索中應用最廣泛的視覺特征，目前有很多基于顏色特征的圖像檢索算法，顏色直方圖是一種重要的基于顏色特征進行的圖像檢索方法.對于一幅圖像I，其顏色由L級組成，每一種顏色值為ci(i=1，2，…，L).在整幅圖像中，每一種顏色出現的頻數記為h(ci)=(顏色為ci的像素個數)/(圖像的I像素總數)，則一組像素統計值h(ci)就是該圖像的顏色直方圖.記為：H(I)=〈h(c1)，…，h(cL)〉.

假設P和Q表示要進行比較的兩幅圖像，檢索時利用公式(1)計算兩幅圖的相似性：

(1)

d(H(P)，H(Q))即兩幅圖的歐式距離，d越小，兩幅圖相似性越大.另外一種常用的度量相似性的算法見公式(2).

(2)

d值越接近1，兩幅圖像越相似.傳統的顏色直方圖只統計了關于某一種顏色值的數量特征，可以反映圖像的部分內容；但丟失了色彩在圖像中形成的具體形狀，因而造成空間信息的缺失.本文針對這一問題，在傳統的顏色直方圖上進行了適當的改進，有效地改善了基于顏色特征的查詢效果.具體算法見下面的描述.

1.2 算法改進

1.2.1 算法描述 圖像中，除了某一種顏色值的數量特征可以表征該幅圖的特點之外，面積較大的顏色塊也是不容忽視的顏色特征.大的顏色塊通常包含了豐富的顏色信息，而且與圖像要表達主題具有很大的關聯性.找出圖像中最大的一個顏色塊，提取其局部顏色直方圖，然后局部顏色直方圖與該圖像的傳統直方圖合并在一起，得到原始圖像的一個綜合的空間顏色直方圖.

1.2.2 整體算法流程 ①圖像中最基礎、最常見的是RGB顏色空間，由于RGB顏色空間具有不均勻、不正交和不直觀等缺點，因此首先，將圖像的顏色值從RGB空間轉化到能正確表達人們實際感知的HSV空間，RGB到HSV空間的轉換過程可參考文獻[10].然后根據矢量量化算法對原始的圖像進行量化處理，得到一幅量化圖像，即像素點陣列.

②利用Canny檢測算子提取出原始圖像的彩色邊緣輪廓，得到圖像的邊緣矩陣.找出邊緣矩陣中最大的0矩陣記為F1，提取F1的局部顏色特征，將其與圖像傳統直方圖F2合并在一起，得到綜合的空間顏色直方圖：H(F)=(H(F1)，H(F2)).

③利用公式(1)計算兩幅的相似性，用本文中形成的綜合空間顏色直方圖代替傳統的顏色直方圖.

1.2.3 0，1矩陣中查找最大0矩陣算法 1)初始化0、1矩陣SFinal，最大面積max=0，最大塊矩陣的左上角坐標點的橫坐標row=0，縱坐標col=0，長度length=0，寬度width=0;

2)獲取SFinal矩陣的行數m，列數n;

3)初始化n+1個0元素數組b，n個0元素的數組l，n個0元素的數組r;

4)初始化i=0;

5)初始化j=0;

6)如果SFinal(i，j)==0，b[j]=b[j]+1，否則b[j]=0;

7)j=j+1，轉6)，直到j等于n;

8)初始化j=0;

9)找出以b[j]為矩陣高的左邊界l[j]，右邊界r[j];

10)j=j+1，轉8，直到j等于n;

11)初始化j=0;

12)如果r[j]-l[j]+1) *b[j]>max，max=r[j]-l[j]+1) *b[j]，Max=b(j)*(r(j)-l(j)+1)，row=i-b(j)+1，col=l(j)，length=r(j)-l(j)+1，width=b(j);

13)j=j+1，轉11)，直到j等于n;

14)i=i+1，轉4)，直到i=m．

1.2.4 算法執行效率分析 假定圖像顏色個數為m，像素點的個數為n，由圖像得到像素點矩陣的時間復雜度為O(n)，利用Canny檢測算子提取圖像的邊緣矩陣所耗時間為3n2，計算綜合直方圖的時間復雜度為O(n)，計算圖形的相似性時間復雜度為O(m)，整個算法的時間復雜度為O(n2+m).相對于傳統的直方圖算法的時間復雜度O(n+m)，時間開銷增加了，這里多出的時間開銷主要是用于找出圖像的最大色塊，這個步驟在本論文的算法中是至關重要的.本論文算法的空間開銷與圖像的最大色塊的顏色個數有關系，假定這個值為k，則整個算法的空間開銷為m+k，這較傳統算法空間開銷主要是增加了存儲最大色塊的直方圖數據，這里k是小于m的，故本算法的空間復雜度為O(m).

2 實驗結果與分析

為了驗證本文算法的工作性能，建立了由20 000幅圖像組成的圖像庫，其中包括大炮、高鐵、古橋、花、熊、貓、食物、海灘、建筑、山10類圖像(每類2000幅)，如表1所示.采用傳統直方圖與本文提出的CHP算法進行了實驗，兩幅圖的相似性度量采用公式(1).

對檢索算法的性能評估比較通用的兩個準則是查準率(Precision)和查全率(Recall).查準率P定義為檢索出的圖像中相關圖像的數目占的比例，查全率R定義為檢索出的相關圖像的數目占數據庫中所有相關的圖像數目的比例.查全率反映系統檢索相關圖像的能力，而查準率則反映系統拒絕無關圖像的能力.但是查準率和查全率這兩個評價標準往往是互相制約的，如果希望檢索系統有較高的查準率，那么只能犧牲查全率作為代價；反之也是這樣.因此，可以按照情況在這兩個評價標準中找到權衡.

表1 測試圖像庫包含的圖像集語義類

圖1 傳統顏色直方圖法的查詢結果Fig.1 The query results of the traditional color histogram

圖2 改進的算法的檢索結果Fig.2 The query results of the improved algorithm

圖1和圖2分別給出了CHP算法與傳統顏色直方圖算法的檢索結果.其中，顯示圖像的左上角為查詢實例圖像，其余20幅圖像是查詢結果，不難看出，傳統顏色直方圖的查準率為6/21，而改進后的CHP算法的查準率為11/21，查準率由29%提高到50%，檢索的準確率有了很明顯地提高.本文根據檢索出的不同圖像數目分別做了實驗，對21、45、60、75、90、105、120共7種情況進行了試驗，可以得到CHP算法與傳統直方圖算法查準率的比較以及性能提高程度，性能提高公式為(P(H*)-P(H))/P(H).如表2所示.

表2 兩種直方圖檢索結果的查準率對比

為進一步驗證本算法的有效性，從每類圖像隨機抽取10幅作為查詢實例圖像，共構成100次查詢，每次選取返回的前21幅圖像作為檢索結果.對每類圖像計算其10次查詢結果的查準率平均值、查全率平均值作為最終的平均查準率和平均查全率，如圖3和圖4分別所示.

由圖3和圖4可以看出熊的查準率和查全率提高的幅度最大，原因在于這類圖像選自動漫圖像.動漫圖像的特點是線條輪廓清晰、大的色塊相對明顯，經過線條提取之后很容易找到最大的顏色塊.顏色塊中包含了豐富且能表征該幅圖的顏色信息，如果采用傳統直方圖只能進行色彩總量的比較，很容易和其他色彩總量相似但是空間分布并不相似的圖像造成混淆，如果采用本文算法則能夠反映出代表這種分布的特征，從而可以很好的區別這類圖片，提高檢索效率.

圖3 兩種方法的平均查準率對比Fig.3 The comparison of average precision ratio for different methods

圖4 兩種方法的平均查全率對比Fig.4 The comparison of average recall ratio for different methods

3 結束語

基于內容的圖像檢索是當前多媒體檢索的熱門話題，是直接采用圖像內容來實現圖像信息檢索的一門技術.其發展與研究涉及到語義特征、多維索引、用戶接口、系統設計等眾多學科分支.如何有效準確的表達圖像特征是基于內容的圖像檢索技術的核心問題.由前述實驗結果分析可見，本文提出的主要綜合空間直方圖方法改進了原有算法易丟失空間信息的不足，檢索性能得到提高，非常適用于塊狀明顯圖像的檢索，這主要是因為主要綜合空間直方圖融合了能夠在一定程度上反映空間分布的局部顏色特征，具有了反映色彩空間分布信息的能力.同時，新算法保留了圖像的傳統直方圖特征，且不破壞原算法旋轉、縮放不變性的優點，因此具有較好的檢索效果.

[1] Rui Y， Huang T S， Chang S F. Image retrieval: Current techniques， promising directions， and open issues[J]. Journal of Visual Communication and Image Representation， 1999， 10(1): 39-62．

[2] 黃祥林，沈蘭蓀.基于內容的圖像檢索技術研究[J].電子學報， 2002， 30(7)：1065-1071．

[3] Yoo H W， Jung S H， Jang D S， et al. Extraction of major object features using VQ clustering for content-based image retrieval[J]. Pattern Recognition， 2002， 35(5): 1115-1126．

[4] Swain M J， Ballard D H. Color indexing [J]. International Journal of Computer Vision， 1991， 7(1): 11-32．

[5] Liu G H， Li Z Y， Zhang L， et al. Image retrieval based on micro-structure descriptor[J]. Pattern Recognition， 2011， 44(9): 2123-2133．

[6] Liu G H， Zhang L， Hou Y K， et al. Image retrieval based on multi-texton histogram[J]. Pattern Recognition， 2010， 43(7): 2380-2389．

[7] Stricker M A， Dimai A. Color indexing with weak spatial constraints[C]//Electronic Imaging: Science & Technology. San Jose, CA, USA: International Society for Optics and Photonics， 1996: 29-40．

[8] 黃元元，劉寧鐘.一種新的基于顏色特征的圖像檢索方法[J].小型微型計算機系統， 2012， 33(3)：609-613．

[9] Stottinger J，Sebe N，Gevers T，et al. Color interest points for image retrieval[C]//Proc of the 12th Computer Vision Winter Workshop，ST. Lambrecht, Austria, 2007:83-90．

[10] Smith J R. Integrated spatial and feature image systems: Retrieval， analysis and compression [D]. New York: Columbia University， 1997．

Histogram image retrieval integrated with color lump

SUN Yanwei1， LEI Jianjun1， SU Dan2

(1.Collaborative Innovation Center in Hubei Province on Fundamental Education and IT Services，Hubei University of Education， Wuhan 430205;2.School of Computer Science， Chongqing University of Posts and Telecommunications， Chongqing 400065)

To further enhance the efficiency of color histogram-based image retrieval algorithm， this paper presents a new algorithm which looks for maximum color lump， extracts its local histogram， and integrates with the original histogram. The algorithm adds spatial distribution characteristics of color while retaining the original algorithm， thus reducing absolute dependence on the color for retrieval results. The simulation results show that this algorithm has better precision and recall and has especially remarkable effect for image retrieval of apparent color lump．

image retrieval; color histogram; color lump; feature vector

2014-09-17.

湖北省教育廳科學研究計劃重點項目(D20113006)；湖北省自然科學基金項目(2013CFB012)；湖北省高等學校青年教師深入企業行動計劃項目(XD2012435).

1000-1190(2015)02-0201-05

TP391

A

*通訊聯系人.E-mail:leijianjun@hue.edu.cn.