顏色密度直方圖檢索方法

王小玲，毛宏燕

1(上海立信會計金融學院 信息管理學院，上海 201620) 2(華東師范大學 上海高可信計算重點實驗室，上海 200062)

1 引 言

由于數字媒體的爆炸式增長和圖像的廣泛應用，圖像檢索技術獲得了長足的發展.基于內容的圖像檢索(CBIR)技術利用顏色、紋理以及形狀或者組合特征，與目標圖像進行比較.顏色特征一直是圖像檢索系統中最重要的描述符之一.顏色直方圖(Color Histogram CH)方法自提出以來，以其旋轉，縮放魯棒性優點一直被廣泛采用[1].然而，由于它只考慮顏色的總量，不能區分具有相同顏色數量但不同顏色分布的圖像.

為了將圖像的顏色信息和空間結構信息進行結合，許多研究試圖從不同角度挖掘顏色的空間特征，提出了各種改進算法.大致可分為兩類：1)從圖像內顏色分布特點出發建立直方圖.如較早的顏色相干矢量(CVV)[2]改進方法，它從顏色在圖像中的自然分布著手，根據像素連通量的大小，把直方圖分成兩部分：相干的和非相干的，擺脫了全局顏色的約束.文獻[3，4]通過k-均值聚類獲取聚類圖，然后統計基于空間位置分布的顏色直方圖.文獻[5]借助紋理、文獻[6，7]依靠邊緣提取顏色直方圖，達到了間接反映顏色的空間特征的目的.2)基于分塊的顏色直方圖.這類改進算法在建立直方圖之前，先對圖像以不同方式分割，將圖像的全局區域顏色特征劃分成幾個局部區域的顏色特征，從而反映空間位置信息.如文獻[8-11]將圖像分割為若干塊，分別計算不同權重區域的顏色特征，利用每個塊的顏色直方圖搜索圖像.這些改進人為劃分區域，破壞了直方圖算法原有的優點，而且區域的權重分配一直是一個難題，固定權值[11]或者通過反復實驗得到的權值[12]缺乏靈活性，會影響檢索結果的準確性.文獻[13，14]提出利用顏色分布熵計算色彩的空間分布分散程度，以此作為分塊加權系數.

本文提出了一種新的顏色密度的直方圖(Color Density Histogram CDH).通過計算主要色彩的顏色密度，反映圖像中占主導地位的顏色的色彩空間分布特點.實驗結果證明，本文提出的CDH方法增強了傳統直方圖區分顏色空間分布差異的能力，提高了檢索性能，達到了滿意的效果.

第2節介紹了CDH的基本算法.第3節給出了圖像相似性度量算法.實驗在第4節中討論.

2 算法描述

顏色直方圖定義如下：給定顏色空間C，圖像I的歸一化顏色直方圖H是:

HC(I)={N(I，Ci)|i∈[1，…，n]}

(1)

N(Ii，Ci)是落入Ci的顏色數量之和，i是顏色空間C的色彩等級.顯見，顏色直方圖只依賴于顏色總量而完全丟失顏色空間分布信息.如圖1(a)、圖1(b)，由于像素總量相同，傳統顏色直方圖無法區分這兩種情形.

圖1 傳統直方圖失效情形

事實上，人們經常會使用“集中”與“分散”這樣的詞語區分圖1(a)和圖1(b)兩種情形.如果能在直方圖中，反映這種空間分布特點，就可以提高直方圖檢索性能.本文提出顏色密度直方圖方法解決這一問題.給出顏色密度的定義：

ρc(I)={N(I，Ci)/Ai|i∈[1，…，n]}

(2)

其中，Ai是色彩等級為i的顏色在圖像中所形成的區域的外接矩形的面積.那么，N(I，Ci)/Ai就是該區域的顏色i的密度，它能夠反映顏色i的空間分布特點.ρc越趨于1，圖像中色彩i的離散程度越小，也就是顏色分布越集中.反之，離散程度越大、越分散.這些像素形成的區域的外接矩形在圖2中標出，其四個頂點的坐標分別是top_left，top_right，bottom_left 與 bottom_right，在圖2(a)中標出.

圖2 外接矩形示意圖

顯見圖2(a)與圖2(b)顏色密度的差異較大，可以作為區分二者的主要特征.有兩種常見的多邊形的外接矩形計算方法[15].一種是最小綁定矩形(Minimum Bounding Rectangle，簡稱MBR)，即以多邊形頂點中的最大、最小坐標確定的矩形.另外一種是最小面積外接矩形(Minimum Area Bounding Rectangle，簡稱MABR).本文的色彩密度計算精度要求不高，因此采用MBR方法，有利于提高計算速度.

根據獲取的外接矩形的頂點坐標top_left，top_right，bottom_left與bottom_right，計算顏色i所形成的區域的外接矩形面積：

Ai=(top_right-top_left)*(bottom_right-bottom_left)

(3)

至此，我們獲得了顏色空間C下圖像I的特征描述：fC(I)={N(I，Ci)，ρ(I，Ci)|i∈[1，…，n]}.

下面給出算法的主要步驟：

1)對顏色空間的每個像素值i，Seti=1，對其他像素值，Seti=0，完成二值化.

2)計算i=1像素數目N.

3)計算i=1所形成的區域的外接矩形面積Area.

4)計算顏色i的密度：N/Area.

3 相似性度量

在色彩空間C，基于獲得的特征向量{N(I，Ci)，ρ(I，Ci)|i∈[1，…，n]}，采用歐氏距離構造相似性度量公式(4)如下：

(4)

從公式(4)易知，對查詢圖像Q的某個顏色i而言，即使其數量較少，但只要數據庫圖像I的顏色分量i與其顏色密度趨勢一致，就在相似性度量中與那些數量較多的顏色具有相近的重要性.然而事實上，我們知道，人眼在比較圖像相似度時，更多是關注那些主要顏色，對于數量較少的顏色并不敏感.顏色直方圖對形如圖1(a)的檢索效果是最好的.為了保留這種優勢，本文提取圖像中數量較多的若干顏色代表一幅圖像的主要色彩.做到既考慮主要色彩，又考慮顏色分布特點，從而減少那些數量較少的顏色對檢索性能的干擾.

4 實驗與分析

4.1 算法評價

查準率(Precision)和查全率(Recall)是普遍采用的兩個檢索性能評價準則，分別代表檢索的速度和成功率.記{Relevant}是與查詢圖像相關的圖像，{Retrieved}是系統檢索出的圖像.則既相關又被檢索出的圖像記為：{Relevant}∩{Retrieved}.

查準率(Precision)是檢索到的圖像中與查詢相關的圖像所占百分比，其定義如式(5)所示：

(5)

查準率反映系統拒絕無關圖像的能力.

查全率(Recall)是與查詢圖像相關且被實際檢索出的圖像的百分比，其定義如式(6)所示：

(6)

查全率反映系統檢索相關圖像的能力.查準率和查全率越高，說明算法的檢索性能越好.

4.2 HSV顏色空間及其量化

由于RGB彩色圖像的顏色特征維數過高，本文采用與人眼視覺特征更加一致的HSV(Hue Saturation Value)顏色空間，并采用文獻[16]的方法，將其量化為72種顏色，既可以滿足肉眼分辨色彩的要求，又可以降低直方圖的計算量，提高檢索效率.

從RGB顏色空間到HSV顏色空間的轉換具體公式如式(7)-式(9)所示：

(7)

(8)

v=max

(9)

其中，max=max(R，G，B)，min=min(R，G，B)r，g，b∈[0，1]，h∈[0，360]，s∈[0，1]，v∈[0，1].

量化公式：

G=9H+3S+V

(10)

根據式(10)，G∈[0，71]，即HSV色彩空間被量化為一個72bin的空間.

4.3 實驗數據庫

本文采用Corel-1000數據庫，該數據庫主要有原始部落、海灘、公共汽車、花朵、恐龍、建筑等共計10個類別的彩色圖像，每類100幅.

4.4 實驗結果與分析

為了驗證算法的有效性，本文對1000幅圖像，在HSV空間，與傳統直方圖和文獻[8]算法進行比較試驗.傳統直方圖度量采用歐氏距離，顏色密度直方圖采用公式(4)計算.按照第3節的分析結果，實驗取前10，20，30，40，50，60，72個主要色彩，其前40幅圖像的查全率性能比較如圖3所示.顯見，在本文采用的數據庫上，取前20個數量最大的顏色檢索性能最好，本文因此采用這種方案.

圖3 不同主顏色數目查全率比較

從圖4可見，與傳統直方圖和文獻[8]算法相比，本文提出的顏色密度直方圖檢索效果顯著提高：顏色直方圖檢索出10幅相關圖像，文獻[8]檢索出13幅相關圖像，CDH檢索到18幅相關圖像，且相關圖像排序靠前.如果進一步嚴格區分，CDH且檢索到了14幅含有紀念碑形狀的圖片，而文獻[8]與CH分別均檢索到4幅和5幅(圖4內使用黑色矩形框框出).這表明，本文提出的算法抓住了顏色的空間分布特點，較好地排除了數據庫中海灘圖像類別內的100幅圖像對檢索結果的干擾，表達了紀念碑這部分對象的空間分布特點，提高了檢索性能.

圖4 HSV空間CH(a)與文獻[8](b)，CDH(c)檢索實例

圖5給出了HSV顏色空間下，CDH與CH、文獻[8]的檢索性能比較.圖像庫中相似圖像總數為100.CDH在這3種算法中，檢索性能最優，其平均查準率較CH提高21%，平均查全率提高25%.

圖5 HSV空間檢索性能比較

傳統直方圖檢索方法依賴像素數量這一單一指標度量相似度，本文引入其所形成的外接矩形面積這一指標，增加了算法區分度.理論上存在顏色密度值相近而實際分布存在差異的情況.我們知道，同類對象其形狀外觀具有一定的穩定性，因此這些色彩所形成的面積也具有穩定性.不同類圖像出現面積相似的概率隨之降低.在本文所選擇的數據庫內，以花朵類中的紅色花朵(17幅)與公共汽車類的紅色公交車(33幅)作比較，二者共同的特點是紅色占主要部分，圖6給出了其72bin顏色密度直方圖比較，顯見這兩類圖像自身存在一定的差異.

圖6 不同類別圖像的CDH比較

另外，本文采用的是前20個較大顏色分量，而不是所有色彩，也削弱了可能出現的顏色密度相似的分量在相似性比較中的地位.

上述兩個因素，增加了本算法的可行性.

5 結 論

顏色直方圖因具有圖像旋轉、縮放不變性優點，在圖像檢索中被廣泛采用.但由于無法識別空間分布差異，導致性能下降.本文從顏色在圖像內的自然分布狀態出發，尋找能夠反映空間分布的信息，使用顏色密度反映這種差異，提出顏色密度直方圖，可以較好地改善上述不足.實驗結果表明.該算法在保留傳統顏色直方圖優點的同時，可以顯著提高檢索性能.