矢量量化用于顏色圖像檢索的改進(jìn)方法*

陳善學(xué),張 艷,尹雪嬌，彭 娟

(重慶郵電大學(xué) 移動通信安全技術(shù)實驗室，重慶 400065)

基于內(nèi)容的圖像檢索技術(shù)（CBIR）具有較高的查找效率和準(zhǔn)確度，近年來得到廣泛應(yīng)用。一幅圖像的底層特征主要包括顏色、紋理、形狀，而顏色特征[1]是圖像最廣泛的視覺特征。目前CBIR中顏色特征提取的形式主要方法有：顏色直方圖[2](Color Histogram)、顏色一致性矢量 (Color Coherence Vector)、顏色相關(guān)圖 (Color Correlogram)、其中顏色轉(zhuǎn)移矩陣(Color Transfer Moment)等。這些方法都有各自的優(yōu)缺點，顏色直方圖、顏色一致性矢量、顏色相關(guān)圖不能較好地描繪顏色的空間位置關(guān)系，顏色向量統(tǒng)計相似的圖像有可能內(nèi)容不相似，顏色轉(zhuǎn)移矩陣用于圖像檢索效率不高。因而本文在矢量量化[3]的基礎(chǔ)上，采用顏色直方圖和顏色轉(zhuǎn)移矩陣[4]相結(jié)合的方法進(jìn)行圖像檢索,兩者取長補短來達(dá)到檢索目的。基于顏色的量化可以在不同的顏色空間中進(jìn)行，最常用的顏色空間有 RGB、HSV、Luv及 Lab等色彩空間[5]。HSV空間的描述能力與人的視覺最為接近，因而本文選擇HSV為量化空間。

1 相關(guān)工作

1.1 矢量量化及LBG算法

矢量量化本質(zhì)上是一個聚類過程，而碼書設(shè)計[6]就是尋求將M個訓(xùn)練矢量分成N類的一種最佳方案。設(shè)M個k維數(shù)據(jù)組成的數(shù)據(jù)空間{Xij},其中i=1,…,M;j=1,…,k，矢量量化可以看做該k維歐幾里德空間Rk到包含 N個互相不重合（R1,R2,…,RN）子空間的有限子集 Y的映射。即Q:Rk→Y，其中在每一個子空間Rj中選出一個代表矢量記為Yj=(yj1,yj2,…,yjk)，將各個子空間的代表矢量集記為 Y={Yj；j=1,…,N}，通常將 Y稱為碼書(code book)，Yj稱為碼字(code word)，而 N是碼書大小。收端以Yj再現(xiàn) X 必然存在失真，滿足 d（X,Yi）=min(d（X,Yj）)，j=1,…,N。d（X,Yi）為矢量 X與碼字 Yi之間的失真測度。

LBG算法是一種直觀有效的矢量量化碼書設(shè)計算法，由 Linde、Buzo和 Gray[7]首先提出。LBG算法一般是先選取初始碼書，根據(jù)最鄰近原則得到新胞腔，然后根據(jù)質(zhì)心原則，通過量化、聚類、迭代由新胞腔得到新的碼書。通過某種限制條件結(jié)束迭代產(chǎn)生最終碼書。這種迭代過程雖然不能保證最后能得到最優(yōu)碼書，但每次迭代平均失真都能降低或保持不變，使得碼書性能得到提高。LBG對初始碼書的選取具有很大的依賴性，很多研究者對初始碼書的選取做了大量研究，Linde等人提出了一種類似于乘積碼技術(shù)的初始化技術(shù)，黎洪松等[8]提出的分離平均法，設(shè)法尋找一種脫離隨機性的初始碼書設(shè)計方法，陳善學(xué)等[9]提出一種基于矢量和值排序的分離平均算法。這些算法都在一定程度改善了LBG初始碼書性能。

1.2 基于矢量量化的顏色直方圖

本文采用基于矢量量化的聚類主顏色[10]提取法。首先選擇訓(xùn)練矢量和訓(xùn)練圖像，在圖像檢索庫中選取色彩迥異的18張圖片作為訓(xùn)練圖像集，并將每幅圖像的色度空間抽取出來，形成一幅灰度圖，選擇所有不重疊的相鄰4×4區(qū)域為訓(xùn)練矢量。利用抽取出來的H、S、V空間的訓(xùn)練矢量，按參考文獻(xiàn)[9]方法生成初始碼書。由于是基于三色數(shù)據(jù)的彩色圖像，可以獲得三色彩色圖像對應(yīng)的三本初始碼書的 3個索引特征矢量 Hi、Si、Vi，將它們合并表示為一個特征矢量C=(Hi,Si,Vi),i=1,2,…,k為碼書個數(shù)。對于圖像中的任意一個像素塊P∈G，它的值經(jīng)過聚類過程可轉(zhuǎn)化為C中的一個碼書Q(P)∈G,本文采用LBG算法對像素塊聚類，算法過程如下：

(1)設(shè)置初始碼書C0，設(shè)定疊代次數(shù) t=1。

(2)對于給定的碼書，Ct={c1t,…,ckt}，按下式尋找最優(yōu)的顏色像素塊空間劃分：

(這里Ri一是與碼字cit距離最鄰近的碼字的集合。

(3)按下式選擇每一個區(qū)域 Ri的質(zhì)心,cent(Ri)構(gòu)成新的碼書{c1t+1,…,ckt+1}，

其中，P(cj)為碼字cj在訓(xùn)練圖像集中出現(xiàn)的概率。

(4)按下式判斷迭代次數(shù)：

如果和上次疊代的平均失真統(tǒng)計量Dt間的差值小于預(yù)設(shè)閾值,則停止聚類過程。否則，返回到步驟(2)繼續(xù)迭代過程。

通過上述顏色聚類過程，可以獲得HSV空間的顏色矢量量化碼表C={c1,…,ck},相當(dāng)于圖像的一個查色表。根據(jù)矢量量化碼表，將彩色圖像中的每一個像素塊的顏色值歸結(jié)為其中的對應(yīng)碼字。通過統(tǒng)計矢量量化各碼字出現(xiàn)的頻率，可以得到彩色圖像的主顏色統(tǒng)計向量：

若以各碼字的索引號為橫坐標(biāo)，各碼字出現(xiàn)的頻率百分比作為縱坐標(biāo),則可以得到一個圖像塊的主顏色直方圖。

其中,h[ci]為圖像G中全體像素塊量化歸結(jié)為主顏色ci的比例值。

1.3 顏色轉(zhuǎn)移矩陣

顏色轉(zhuǎn)移矩陣法是一種建立在HSV量化顏色空間之上的刻畫顏色相對分布位置的方法。由前面的顏色直方圖得到圖像的顏色矢量量化碼表C={c1,…,ck}，共有k個碼字,表示有k種主色。彩色圖像的顏色轉(zhuǎn)移矩陣過程如下：

(1)將圖像分成m×n個小塊，每一小塊的大小都為s×t個像素塊。

(2)得出每一小塊的主值c，也就是該小塊中取得次數(shù)最多的那個碼字。這樣就形成—個二維主色矩陣，大小為 m×n，表示為 A={ci,j},其中 i=1,2,…,m;j=1,2,…,n。

(3)建立一個 k×k的矩陣 P(k為 c的取值個數(shù))，各元素初始值為0。將步驟(2)得到的矩陣A按Z字掃描順序進(jìn)行掃描，設(shè)ci,j和cp,q是掃描序列中的一對相繼出現(xiàn)的顏色(ci,j在 cp,q的前面)，則 P中相應(yīng)元素 P[ci,j,cp,q]自增1，如此反復(fù)，直到掃描完成。

(4)建立k×k的矩陣D，D中元素的計算公式如下：

矩陣D就是該圖像的顏色轉(zhuǎn)移矩陣。從上面的步驟可以看出，矩陣D中的每個元素都描述了圖像中不同顏色的相鄰關(guān)系及這種相鄰系在整幅圖像所有像素塊對中發(fā)生的比例,從而矩陣D能描述顏色的空間分布情況。

1.4 相似度度量[11]

1.4.1 顏色直方圖相似性度量

一般的直方圖度量方法是歐氏距離、矢量距離 (角度、幅度)、直方圖交集距離等。顏色直方圖相似性度量采用傳統(tǒng)的歐氏距離作為度量方法，歐氏距離就是同時作為顏色相似性度量的結(jié)果。歐氏距離的定義如下：

其中,HA、HB為兩圖幅圖像 A,B的主色直方圖，T代表轉(zhuǎn)置。

1.4.2 顏色轉(zhuǎn)移矩陣相似性度量

對于顏色轉(zhuǎn)移矩陣相似度度量，本文采用以下方法，設(shè)DA和DB分別表示兩幅圖像A、B的顏色轉(zhuǎn)移矩陣，相似度定義為：

1.4.3 復(fù)合相似度度量

由于顏色轉(zhuǎn)移矩陣彌補了顏色直方圖對顏色空間描述的不足，而顏色直方圖檢索效率較好，因而將兩者結(jié)合進(jìn)行圖像檢索可達(dá)到很好的效果。兩個相似度的取值在0～1之間，所以不需要歸一化處理。合成相似度定義如下：

其中(w1,w2∈[0,1],w1+w2=1)。將合成相似度結(jié)果按升序排列，相似度值越小的圖片與查詢圖片越相似。將排序結(jié)果按用戶需要返回即可。

2 本文算法

根據(jù)上文提出的相關(guān)工作，本文算法是通過顏色直方圖和顏色轉(zhuǎn)移矩陣相結(jié)合的方法進(jìn)行圖像檢索。算法過程如下：

(1)通過矢量量化方法把圖像量化為k種主顏色，得到一個查色表，在查色表的基礎(chǔ)上得到圖像庫中圖像的顏色直方圖 (1.2節(jié)詳細(xì)論述)。該方法通過圖像的k種主色進(jìn)行圖像檢索，減少了計算量。

(2)在查色表的基礎(chǔ)上得到圖像庫中圖像的顏色轉(zhuǎn)移矩陣(見1.3節(jié)詳細(xì)論述)。顏色轉(zhuǎn)移矩陣克服了顏色對圖像空間描述不足的缺點，結(jié)合顏色直方圖進(jìn)行圖像檢索，提高了檢索精度。

(3)通過1.4.1節(jié)論述的方法對顏色直方圖相似性度量，1.4.2節(jié)論述的方法對顏色轉(zhuǎn)移矩陣相似性度量，再通過1.4.3節(jié)論述的方法復(fù)合兩種相似度，由復(fù)合相似度進(jìn)行圖像檢索，返回相似圖像。

3 實驗結(jié)果分析

選用LI J[12]提供的圖像數(shù)據(jù)庫,選取其中420幅256×384或者 384×256的彩色圖像，圖像庫分為海灘、人物、恐龍、花朵、草原、山峰和汽車 7類，每類包含 60幅圖像。查準(zhǔn)率是對檢索系統(tǒng)精度的衡量，本文用查準(zhǔn)率對圖像性能進(jìn)行分析。

其中,a代表正確檢索出的相關(guān)圖像數(shù)目；b代表檢索出的無關(guān)圖像；c代表漏檢的相關(guān)圖像數(shù)目；A代表某分類所有相關(guān)圖像的集合，B代表檢索出的所有圖像的集合。

具體測試時，每種方法每個類別取6幅圖像作為例圖檢索，返回20幅圖像，然后再取6幅例圖的平均查準(zhǔn)率用來作為該方法該圖像類別的查準(zhǔn)率。實驗中比較了顏色檢索算法、矢量量化檢索算法和本文提出的顏色直方圖和顏色轉(zhuǎn)移矩陣結(jié)合算法，效果如圖1所示。

圖3 采用矢量量化檢索算法檢索的草原圖像結(jié)果

圖4 采用本文算法檢索的草原圖像結(jié)果

由于各語義類別圖像有很大不同，每個人對圖片的感受和理解也都不同，所以查詢準(zhǔn)確率有一定的波動。從以上仿真結(jié)果的對比分析以及7類檢索結(jié)果的整體效果中可以看出，本文算法用于圖像檢索比顏色檢索算法查準(zhǔn)率高出8%～30%，比矢量量化圖像檢索算法高1%～26%。因此，本文算法的圖像搜索效果要好于基于顏色檢索算法和基于矢量量化圖像檢索算法。由于篇幅關(guān)系，本文給出各種算法草原圖像的查詢結(jié)果,如圖2～圖4所示，其中第一張圖像為輸入圖像，后面的17張圖片為檢索圖像，相似度從左到右、從上到下由高到底排列。

[1]YAMADA A,KASUTANI E,OHTA M,et al.Visual program navigation system based on spatial distribution of color[C].Proc.of the IEEE International Conference on Consumer Electronics,2000.

[2]伯曉晨，劉建平.基于顏色直方圖的圖像檢索[J].中國圖像圖形學(xué)報，1999,4(1)：33-37.

[3]孫圣和,陸哲明.矢量量化技術(shù)及應(yīng)用[M].北京：科學(xué)出版社，2002.

[4]陳善學(xué).矢量量化技術(shù)及其在圖像信號處理中的應(yīng)用研究[D].電子科技大學(xué)，2009.

[5]章毓晉.圖像處理[M].北京：清華大學(xué)出版社，2006.

[6]徐皓淋,陳善學(xué).一種改進(jìn)的等誤差競爭學(xué)習(xí)矢量量化算法[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版)，2009,21(6):721-724.

[7]LINDE Y，BUZO A，GRAY R M.An algorithm for vector quantizer design[J].IEEE Trans on Corn，1980，28(1)：84-95.

[8]黎洪松，劉洪偉.新的學(xué)習(xí)矢量量化初始碼書算法[J].北京郵電大學(xué)學(xué)報，2006，29(4)：33-35.

[9]陳善學(xué).矢量量化的初始碼書算法[J].計算機工程與應(yīng)用,2010:46(11),26-28.

[10]SWAIN M,BALLARD D.Color indexing[J].International Journal of Computer Vision,1991,7(1):11-32.

[11]唐宏.圖像相似性模型、算法與應(yīng)用研究[D].上海：上海交通大學(xué),2006:18-63.

[12]LI J.Photography image database[EB/PL].[2005-08].http://www.stat.psu.edu/jiali/index.download.html.