冀　鑫　冀小平

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

?

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

冀鑫冀小平

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

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

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

0　引　言

隨著信息技術(shù)的發(fā)展，生活中不斷地生成大量的圖片，它們都是無序的、無索引的。目前，我們面臨的一個問題就是如何從這些海量的圖片里快速而準(zhǔn)確地檢索到我們想要查詢的圖片。因此，基于內(nèi)容的圖像檢索成為了當(dāng)下一個研究的熱點(diǎn)。基于CBIR[1]技術(shù)主要依據(jù)圖像所具有顏色(灰度)、紋理、形狀、空間關(guān)系等特征[2]，提取這些特征，然后對這些特征進(jìn)行相似度對比，并對圖庫中圖像進(jìn)行排序，從而實(shí)現(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為亮度或強(qiáng)度。

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

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

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

壓縮完成以后，再對圖像進(jìn)行顏色空間轉(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)系應(yīng)滿足：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與它對應(yīng),使該碼字與輸入矢量X的失真度達(dá)到碼書中所有碼字最小。

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

1.3算法描述

1.3.1生成查詢圖像碼書

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

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

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

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

1.3.2形成顏色直方圖

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

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

圖5　查詢圖像顏色直方圖

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

1.3.3相似度計算

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

(3)

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

(4)

圖6　檢索結(jié)果

2　實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表2　不同門限值下各類別查全率和查準(zhǔn)率

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

(5)

平均查全率和平均查準(zhǔn)率如表3所示。

表3　平均查全率和平均查準(zhǔn)率

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

圖7　平均查全率和平均查準(zhǔn)率比較

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

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

圖8　平均檢索性能比較

3　結(jié)　語

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

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

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

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

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

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

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

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

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

[9] 成琳,陳俊杰,相潔.圖像顏色特征提取技術(shù)的研究與應(yīng)用[J].計算機(jī)工程與設(shè)計,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].太原:太原理工大學(xué),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。冀鑫，碩士生，主研領(lǐng)域：圖像處理。冀小平，副教授。

TP391.9

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