一種新的基于矢量量化的圖像檢索算法

冀　鑫　冀小平

(太原理工大學信息工程學院　山西 太原 030024)

?

一種新的基于矢量量化的圖像檢索算法

冀鑫冀小平

(太原理工大學信息工程學院山西 太原 030024)

針對目前基于顏色的圖像檢索算法在顏色特征提取的不足，提出一種新的顏色特征提取算法。利用LBG算法對HSI空間的顏色信息矢量量化，然后統(tǒng)計圖像中各個碼字出現(xiàn)的頻數(shù)，形成顏色直方圖。這樣在提取顏色特征過程中，盡可能地降低圖像原有特征失真。同時通過設定門限值，多次實驗比較查全率和查準率，找到較為滿意的門限值，使檢索算法更加完善。實驗結(jié)果表明，該算法能有效地提高圖像檢索精準度。

HSI空間圖像特征矢量量化門限值

0　引　言

隨著信息技術(shù)的發(fā)展，生活中不斷地生成大量的圖片，它們都是無序的、無索引的。目前，我們面臨的一個問題就是如何從這些海量的圖片里快速而準確地檢索到我們想要查詢的圖片。因此，基于內(nèi)容的圖像檢索成為了當下一個研究的熱點?；贑BIR[1]技術(shù)主要依據(jù)圖像所具有顏色(灰度)、紋理、形狀、空間關(guān)系等特征[2]，提取這些特征，然后對這些特征進行相似度對比，并對圖庫中圖像進行排序，從而實現(xiàn)圖像檢索的目的。本文在特征提取時選取的是對顏色特征的提取，針對目前基于顏色的圖像檢索算法在提取特征過程中損失較多原有顏色信息的問題，提出有別于其他算法的一種新的矢量量化算法。首先，RGB顏色空間轉(zhuǎn)化到HSI顏色空間，利用LBG算法對查詢圖像矢量量化，形成碼書，并統(tǒng)計查詢圖像各個碼字出現(xiàn)的頻數(shù)，形成顏色直方圖；其次，按照查詢圖像的碼書對圖庫集中的圖像一一量化，統(tǒng)計每幅圖像各個碼字出現(xiàn)頻數(shù)，得到顏色直方圖；最后，計算顏色直方圖距離Di，距離小于等于門限值I的圖片返回排序，大于門限值的則舍棄。檢索流程如圖1所示。

圖1　檢索流程圖

1　矢量量化的圖像檢索

1.1前期圖像處理

本文采用的顏色模型是HSI模型，主要考慮到這種顏色模型更能反映人的視覺對顏色的感覺。它是由Munseu提出的一種顏色模型，其中H為色調(diào)，S為飽和度，I為亮度或強度。

直接用MATLAB讀入圖像的保存形式是由RGB三個參量保存。一幅256×256的彩色圖像用RGB表示為256×256×3的三維矩陣，這樣后期對圖像的空間轉(zhuǎn)換和矢量量化整體的運算量是非常大的，而且可行性不夠高，對檢索效率是不利的。因此，首先得對圖像進行簡單地壓縮，適當?shù)厣釛増D像本身存在的冗余的顏色信息是必要的。壓縮過程直接用到的是容易在MATLAB7.11.0(R2010b)中實現(xiàn)的平均壓縮。所謂平均壓縮，就是對一幅圖像均勻地分塊，然后對每一塊的RGB三個參量分別進行平均運算，將點數(shù)適當減少，再生成新的圖像的過程。公式表示：

MATLAB7.11.0(R2010b)仿真結(jié)果如圖2、圖3所示。

圖2　256×256圖片　　　圖3　64×64圖片

壓縮完成以后，再對圖像進行顏色空間轉(zhuǎn)換。對任何[0,1]范圍內(nèi)的R、G、B值轉(zhuǎn)換為HIS模型的計算公式如下：

(1)

其中：

(2)

1.2矢量量化及LBG算法

矢量量化是從k維歐幾里德空間Rk映射到其一個有限子集C的過程，即：Rk→C，其中C={Y1,Y2,…,Yi,…,YN|Yi∈Rk}稱為碼書，N為碼書長度[3]。映射關(guān)系應滿足：Q(X|X∈Rk)=Yi，其中X=(x1，x2，…，xk)為Rk中的k維矢量，Yl=(yl1,yl2,…,ylk)為碼書C中的碼字，并且滿足：d(X,Yl)=min(d(X,Yi))，其中d(X,Yi)為矢量X與碼字Yi之間的失真度。因而只要輸入一個矢量X必然能在碼書C中找到合適的碼字Yi與它對應,使該碼字與輸入矢量X的失真度達到碼書中所有碼字最小。

LBG算法是一種最優(yōu)的矢量量化碼書設計算法，是由Linde等[4]在1980年首次提出來的。該算法具有最佳矢量量化器設計的最佳劃分和最佳碼書的優(yōu)點，是Lloyd算法在矢量空間的應用，具有清晰的物理概念、算法嚴密和容易實現(xiàn)等特點[5]。LBG算法的收斂速度和收斂的可能性，決定了最終形成碼書的質(zhì)量，關(guān)鍵是對初始碼書的形成有很大的依賴性。針對LBG算法初始碼書設計的問題，陳善學等[6]提出了改進的PNN算法， 黎洪松等[7]提出了分離平均法，設法找到一種脫離隨機性的初始碼書涉及方法，這些算法都在一定程度上改善了本身LBG算法的不足。

1.3算法描述

1.3.1生成查詢圖像碼書

本文選取的查詢圖像是大小為256×256的jpg格式的金針花圖像。先按照1.1節(jié)的方法將256×256的圖像平均壓縮成64×64的圖像同時轉(zhuǎn)換顏色空間，完成對圖像前期的處理，然后再進行生成碼書的過程。

1) 獲取查詢圖像的初始碼書。設定碼書長度N=32。MATLAB中讀入圖像是由RGB形式保存，轉(zhuǎn)換為HIS模型，形成3×4096矩陣。在仿真實驗中，將訓練樣本(3×4096矩陣)通過隨機函數(shù)(randn)選擇32個樣本作為初始碼書。

2) 進行迭代訓練。每次迭代中，每一個訓練矢量Xi=(Hi,Si,Ii)(i=1,2,3)(注：每一點HSI三個參量作為一個訓練矢量)與碼書中的各個碼字Yj(j=1,2,…，32)相比較，找到與該訓練矢量最相近的一個碼字Yk，并把所有與Yk最相近的訓練矢量歸為一類，這樣一共有32類，這一步也叫劃分胞腔過程[8]。然后求出每個胞腔中訓練矢量與其對應在碼書中最相近的碼字Yk的距離平方之和，得到此次劃分胞腔進行迭代的平均失真Ln。若此次劃分的平均失真Ln與上次劃分的平均失真Ln-1之間的相對誤差εn符合設定的失真誤差ε，則停止劃分，否則求出各胞腔的中心矢量作為新的迭代碼書，重新劃分胞腔。本文失真相對誤差為ε=0.0001。查詢圖像的碼書生成過程如圖4所示。

圖4　LBG算法形成查詢圖像碼書

1.3.2形成顏色直方圖

顏色直方圖是一種通過概率統(tǒng)計方法準確地將圖像信息反映到可計算的數(shù)學模型上。在仿真實驗過程中，利用計算機軟件統(tǒng)計圖像中各個像素點出現(xiàn)的頻數(shù)，形成顏色直方圖，這樣將抽象的圖像信息轉(zhuǎn)化為直觀的顏色直方圖?？紤]到顏色直方圖具有旋轉(zhuǎn)、尺度與平移不變性等優(yōu)良特點[9]，且方法簡單比較容易實現(xiàn)，因此在提取圖像顏色特征時經(jīng)常用到。

本文用LBG算法來實現(xiàn)圖像的顏色量化，得到查詢圖像的碼書，統(tǒng)計查詢圖像中各個碼字出現(xiàn)的頻數(shù)，并用直方圖形式直觀地表達出來，就完成了對圖像顏色特征的提取。其中直方圖的橫坐標為碼書中碼字編號(1,2,…,32)，直方圖的縱坐標為圖片矢量量化后，統(tǒng)計得出碼字的頻數(shù)。在MATLAB7.11.0(R2010b)中仿真圖3提取出的顏色直方圖如圖5所示。

圖5　查詢圖像顏色直方圖

從圖像檢索圖庫中選取8張圖作為圖像訓練集，對8幅圖像按照查詢圖像碼書進行量化，統(tǒng)計每幅圖像每個碼字的頻數(shù)。然后8幅圖像對應的8個顏色直方圖，這樣就完成對圖庫訓練集中圖片的顏色特征提取。

1.3.3相似度計算

提取圖像顏色特征之后，接著需要考慮的問題就是對圖像相似度的計算。顏色直方圖檢索算法的相似度計算本質(zhì)上其實就是顏色直方圖距離的計算[10]。單單針對一種顏色特征的距離度量方法有許多種。我們常用的有歐拉距離、直方圖相交距、二次式距離、馬氏距離等。當圖像特征的各分量之間是正交的而且是無關(guān)聯(lián)的，同時各維度的權(quán)重相同，這時我們計算兩個特征向量X和Y之間距離通常用歐拉距離[11]。公式為：

(3)

本文在計算距離時，采用了一種簡單的而且能夠從最后運算數(shù)據(jù)中直觀地看到查詢圖像與圖庫中圖像的特征距離。具體方法為：查詢圖像經(jīng)過特征提取獲得特征向量X，對8幅圖像提取特征得到8個特征向量，逐一與向量X計算距離。例如8幅圖中一幅提取出來的特征向量Y，距離公式為：

(4)

圖6　檢索結(jié)果

2　實驗結(jié)果與分析

查準率(precision)為檢索到的與查詢圖像相似的圖像數(shù)目與已檢索出的圖像數(shù)目之比。查全率 (recall)為檢索到的與查詢圖像相似的圖像數(shù)目與所有圖庫集相似圖像數(shù)目之比。查準率用來判斷檢索的精準度，而衡量檢索的全面性是用查全率來判定的。通常我們用這兩個數(shù)據(jù)來認定檢索方法是否有效。查準率和查全率兩者越高說明檢索方法越有效。然而查準率和查全率是互斥的，當追求較高的查準率時，查全率會降低，而當要求查全率較高時，我們必須降低查準率。因此通過改變檢索算法的某些參量，目的是使查準率和查全率二者實現(xiàn)一個良好的均衡。本文通過設置門限值I來找到實現(xiàn)查準率和查全率均衡的合適的門限值。由于經(jīng)過計算最終得到的特征距離Di是0到1的一維數(shù)組，所以分別將門限值I設置為 0.1、0.2、0.4、0.5、0.6、0.8。當距離Di>I時，圖庫集中對應的圖像將不返回，認為與查詢圖像無關(guān)，只有當距離Di≤I時，所對應的圖像返回，認為這些圖像與查詢圖像相關(guān)。

本實驗對植物、動物、風景分別進行檢索，從而來檢測該算法的檢索性能，為了達到算法性能評價的可靠性，植物類選取了花100幅圖片(其中花的種類不同，花的形狀不同，花的顏色不同)，動物類同樣選取了100幅圖片，風景類也選取了100幅圖片進行試驗。在MATLAB7.11.0(R2010b)中應用該算法實際仿真，通過代入不同的門限值參數(shù)，觀察并計算不同門限值下的各類圖像的查全率和查準率，最后計算出平均的查全率和平均查全率。從最后計算出的結(jié)果中，得出最適合本算法的門限值。仿真實驗數(shù)據(jù)統(tǒng)計見表1所示。

表1　不同門限值下對應各類別檢索結(jié)果

考慮到圖庫集中的圖像都是與查詢圖像相關(guān)，所以查全率P=返回數(shù)/100，查準率P=相關(guān)圖像/返回數(shù)。計算出查全率和查準率見表2所示。

表2　不同門限值下各類別查全率和查準率

計算不同門限值下的平均查準率(Averprecision)和平均查全率(Averrecall)公式如下：

(5)

平均查全率和平均查準率如表3所示。

表3　平均查全率和平均查準率

將計算出的平均查全率和平均查準率繪制折線圖分析實驗數(shù)據(jù)，折線圖如圖7所示。

圖7　平均查全率和平均查準率比較

從圖7中可以看出不同的門限值下，應用本算法檢索圖像計算出的平均查全率和平均查準率是變化的。當門限值增大時，平均查全率隨著增大而平均查準率反而隨著減??；當門限值減小時，平均查全率隨著減小而平均查準率反而增大。因此，門限值和平均查全率成正比，跟平均查準率成反比[12]。從圖中還可以看出，門限值對平均查全率的影響要大于對平均查準率的影響。同時，當門限值I=0.6時，無論從平均查準率還是平均查全率來講都是比較滿意。

本文還將提出的新算法與傳統(tǒng)顏色直方圖算法和文獻[13]檢索算法進行了對比。通過計算平均查全率和平均查準率，繪制曲線，如圖8所示，顯然本算法要優(yōu)于其他兩種算法。主要原因是LBG算法在量化時按照查詢圖像來生成碼書，在檢索不同的圖像時，查詢圖像碼書是按照查詢圖像變化而變化的。因此，提取出的顏色特征更能體現(xiàn)出查詢圖像本身存在的顏色信息。

圖8　平均檢索性能比較

3　結(jié)　語

本文針對圖像檢索，提出了一種新的基于矢量量化的圖像檢索算法，并在MATLAB7.11.0(R2010b)中仿真分析實驗結(jié)果，證實了本算法的可行性和可靠性。采用HSI模型更加接近人的視覺感覺，利用LBG算法量化提取特征，確保提取出顏色特征的可靠性，加入門限值來平衡查全率和查準率的關(guān)系，找到適合本算法的最佳門限值，使算法更加完善。下一步研究工作的首要方向就是將本算法結(jié)合其他圖像特征來實現(xiàn)檢索目標。

[1] 孫思,趙姍,魏從剛.基于視覺點特征的圖像檢索技術(shù)研究[J].計算機科學,2013,40(6A):196-198.

[2] 焦蓬蓬,郭依正,劉麗娟,等.灰度共生矩陣紋理特征提取的Matlab實現(xiàn)[J].計算機技術(shù)與發(fā)展,2012,22(11):169-171,175.

[3] 裴慧.DCT域矢量量化圖像壓縮編碼算法研究[D].哈爾濱:哈爾濱工業(yè)大學,2005.

[4]Linpe,BuzoA,GrayRM.Analgorithmforvectorquantizerdesign[J].IEEETransonlorn,1980,28(1):84-95.

[5] 孫中偉.雙正交變換及矢量量化應用研究[D].天津:天津大學,2009.

[6] 陳善學,張艷,吳立彬.用于LBG初始碼書設計的改進PNN算法[J].重慶郵電大學學報:自然科學版,2012,24(1):50-53.

[7] 黎洪松,劉洪偉.新的學習矢量量化初始碼書算法[J].北京郵電大學學報,2006,29(4):33-35.

[8] 陳學青,羅航哉,薛向陽,等.基于格矢量量化和倒排文件的快速圖像檢索方法[J].電子學報,2000,28(8):94-96.

[9] 成琳,陳俊杰,相潔.圖像顏色特征提取技術(shù)的研究與應用[J].計算機工程與設計,2009,30(14):3451-3454.

[10]VasukiA,VanathiPT.Areviewofvectorquantizationtechniques[J].IEEEPotentials,2006(4):39-47.

[11]SwainM,BallardD.Indexingviacolorhistograms[J].IEEETransInternationalJournalofComputerVision,1990(1):390-393.

[12] 趙睛.基于顏色的圖像檢索研究[D].太原:太原理工大學,2009.

[13] 李雪艷,冀小平.基于分塊顏色特征和相關(guān)反饋的圖像檢索技術(shù)[J].電視技術(shù),2013,37(7):29-32.

ANEWIMAGERETRIEVALALGORITHMBASEDONVECTORQUANTIFICATION

JiXinJiXiaoping

(School of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,Shanxi,China)

Weputforwardanewcolourfeatureextractionalgorithmfortheshortcomingofpresentcolour-basedimageretrievalalgorithmincolourfeatureextraction.First,thealgorithmusesLBGalgorithmtocarryoutvectorquantificationoncolourinformationinHSIspace,andthencountstheappearancefrequencyofeachcodewordintheimagetoformcolourhistogram.Sointheprocessofcolourfeatureextractionthedistortionoforiginalimagefeaturescanbereducedasfaraspossible.Meanwhile,bysettingthethresholdvaluewecomparedtherecallandprecisionratesthroughacoupleoftheexperimentsuntilasatisfiedthresholdvaluewasfound,thusmadetheretrievalmethodmoreperfect.Experimentalresultsshowedthatthenewalgorithmcouldeffectivelyimprovetheaccuracyofimageretrieval.

HSIspaceImagefeatureVectorquantificationThresholdvalue

2014-08-22。冀鑫，碩士生，主研領域：圖像處理。冀小平，副教授。

TP391.9

ADOI:10.3969/j.issn.1000-386x.2016.03.051