符保龍，張愛科

（柳州職業(yè)技術(shù)學(xué)院，廣西柳州 545006）

基于改進(jìn)布谷鳥搜索算法的相關(guān)反饋圖像檢索

符保龍，張愛科

（柳州職業(yè)技術(shù)學(xué)院，廣西柳州 545006）

由于視覺低層特征與高層語義間存在“語義鴻溝”，基于內(nèi)容的檢索算法難以找到滿足用戶要求的圖像，為了提高圖像檢索準(zhǔn)確率，提出一種基于布谷鳥搜索算法的相關(guān)反饋圖像檢索方法（MCS）。首先分別提取圖像的顏色、紋理、形狀特征。然后根據(jù)用戶的反饋信息，采用布谷鳥搜索算法動(dòng)態(tài)調(diào)整特征的權(quán)值，從而建立滿足用戶實(shí)際偏好的圖像相似度模型。最后采用仿真實(shí)驗(yàn)測試MCS的有效性。結(jié)果表明，相對于遺傳算法、粒子群算法以及傳統(tǒng)圖像檢索算法，MCS算法不僅提高了圖像檢索準(zhǔn)確度，同時(shí)加快了圖像檢索效率，更好地滿足圖像檢索要求。

圖像檢索;相關(guān)反饋;特征權(quán)值;布谷鳥搜索算法

隨著數(shù)字圖像技術(shù)和網(wǎng)絡(luò)技術(shù)發(fā)展，圖像數(shù)據(jù)呈幾何級(jí)猛增，從海量圖像數(shù)據(jù)中快速、準(zhǔn)確檢索出用戶需要的信息顯得日益重要，因此圖像檢索成為當(dāng)前研究的熱點(diǎn)［1］。

傳統(tǒng)圖像檢索方式是利用人工檢索方式，該方法工作量大、耗時(shí)多，而且結(jié)果具有主觀性，檢索結(jié)果往往差強(qiáng)人意［2］。隨后，出現(xiàn)了基于內(nèi)容的圖像檢索（CBIR）技術(shù)，其主要通過顏色、紋理、形狀特征等描述圖像內(nèi)容，然后根據(jù)特征信息搜索用戶感興趣的圖像［3］。由于圖像檢索系統(tǒng)的最終用戶是人，而CBIR系統(tǒng)得到初始檢索結(jié)果往往不能很好地滿足用戶要求，出現(xiàn)“語義鴻溝”的問題［4］。為了解決“語義鴻溝”問題，有學(xué)者把相關(guān)反饋（Relevance Feedback）技術(shù)引入到CBIR系統(tǒng)中，根據(jù)用戶的反饋信息來提高系統(tǒng)的檢索性能［5］。對于一幅圖像，單一特征只能描述圖像內(nèi)容的部分信息，因此，通常提取多種圖像特征進(jìn)行圖像檢索［6］。在多特征的相關(guān)反饋檢索過程中，為了反映不同用戶的不同需求，需要對各特征的權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整，保證圖像檢索逐步向用戶感興趣的方向發(fā)展，出現(xiàn)了基于遺傳算法、粒子群算法對圖像的特征權(quán)值動(dòng)態(tài)調(diào)整，提高了圖像檢索精度，檢索結(jié)果更加符合用戶要求［7－8］。但是遺傳算法、粒子群算法均存在各自的缺陷，易陷入局部最優(yōu)，因此當(dāng)特征權(quán)值選擇結(jié)果不是全局最優(yōu)時(shí)，圖像檢索效率和精度就相應(yīng)較低［9］。

為了提高圖像檢索精度和效率，針對圖像特征權(quán)值調(diào)整問題，提出一種改進(jìn)布谷鳥搜索的相關(guān)反饋圖像檢索算法（MCS），在用戶反饋過程中，通過全局搜索能力強(qiáng)的MCS動(dòng)態(tài)調(diào)整圖像特征權(quán)值，并通過仿真對比實(shí)驗(yàn)，證明該模型具有較好的有效性和優(yōu)越性。

1 改進(jìn)布谷鳥搜索算法和圖像特征

1.1 改進(jìn)布谷鳥搜索算法

布谷鳥搜索（Cuckoo Search，CS）算法模擬布谷鳥種群的寄生繁衍策略，并結(jié)合了鳥類及果蠅特殊的Levy flight模式，全局搜索能力強(qiáng)，適合用于多目標(biāo)優(yōu)化問題求解［10］。為了模擬布谷鳥的尋巢行為，CS設(shè)定了3個(gè)規(guī)則，具體為:

1）布谷鳥一次下一個(gè)蛋，代表待求解問題的一種解決方案，并隨機(jī)放在一個(gè)鳥巢中進(jìn)行孵化。

2）一部分鳥巢放著優(yōu)質(zhì)蛋，即好的解決方案，這些鳥巢將被保留到下一代。

3）可利用鳥巢的數(shù)量是固定的，布谷鳥蛋被寄主鳥發(fā)現(xiàn)的概率為Pa∈（0，1），一旦某個(gè)鳥巢被發(fā)現(xiàn)，寄主鳥就丟棄鳥蛋或者鳥巢，尋找新的鳥巢，以免影響尋找最優(yōu)問題的解。

在這3個(gè)規(guī)則基礎(chǔ)上，設(shè)x（t）i為第i個(gè)鳥巢在第t代的鳥巢位置，L（λ）表示隨機(jī)搜索路徑，那么布谷鳥尋巢的路徑和位置更新公式為

式中:?表示步長控制量;⊕表示點(diǎn)對點(diǎn)乘法。

位置更新后，隨機(jī)產(chǎn)生一個(gè)［0，1］的數(shù)r，如果r＞Pa，那么x（t+1）i就進(jìn)行隨機(jī)改變，反之不變，最后保留測試值較好的一組鳥巢位置y（t+1）i，此時(shí)仍把記為x（t+1）i。

1.2 圖像特征及相似度模型

為了從多個(gè)角度描述圖像，提取多個(gè)可以反映圖像信息的特征，即:顏色、紋理、形狀。

定義1:給定一幅圖像D，則圖像的三元組模型為

式中:F={fi}表示一組特征集合;fi表示第i個(gè)特征;R={rij}特征fi的具體表示形式。

rij定義為

定義2:對于一個(gè)圖像檢索系統(tǒng)，圖像相似度模型用于量化圖像和圖像之間的距離，采用歐幾里得距離定義圖像之間的相似度。設(shè)Q為查詢圖像，I為被查詢圖像，那么式中:drij（Q，I）表示在特征fi的第j個(gè)分量上的距離;wfi表示特征fi的權(quán)值;dfi（Q，I）表示兩幅圖像在特征fi上的距離。

在反饋過程中，利用布谷鳥搜索算法修改式（4）中的wfi，使得圖像特征權(quán)值更加接近用戶的需求，以提高圖像的檢索精度，并減少反饋次數(shù)，提高圖像檢索效率。

2 基于MCS的相關(guān)反饋圖像檢索算法

2.1 鳥巢位置的編碼

為了便于解碼，采用二進(jìn)制方式表示對鳥巢位置進(jìn)行編碼，設(shè)共有n個(gè)圖像特征，那么特征權(quán)值向量為:W=［w1，w2，…，wn］，這些特征組成一個(gè)鳥巢位置:C=［c1，c2，…，cn］，那么鳥巢位置的位置與權(quán)值轉(zhuǎn)關(guān)系為

2.2 鳥巢位置優(yōu)劣衡量標(biāo)準(zhǔn)

鳥巢被保留概率主要通過位置優(yōu)劣來決定，采用圖像檢索結(jié)果的查全率和查準(zhǔn)率作為鳥巢位置優(yōu)劣衡量標(biāo)準(zhǔn)，即

式中:c為鳥巢位置;R（q，c）為查全率;P（q，c）為查準(zhǔn)率;q為查詢圖像。

R（q，c）和P（q，c）定義為

2.3 圖像檢索算法的工作流程

步驟1:收集圖像數(shù)據(jù)，并對圖像預(yù)處理，消除圖像中的噪聲。

步驟2:分別提取圖像的紋理、顏色、形狀特征，并轉(zhuǎn)化成相應(yīng)的特征向量，同時(shí)對特征進(jìn)行歸一化處理。

步驟3:對圖像特征賦初始權(quán)值。

步驟4:根據(jù)式（4）計(jì)算查詢圖像Q與查詢庫中每一幅圖像的D（Q，I）值，根據(jù)距離進(jìn)行排序，輸出前n幅圖像。

2）根據(jù)式（7）對鳥巢位置優(yōu)劣進(jìn)行評(píng)價(jià)，找到當(dāng)前最優(yōu)鳥巢x（0）b。

3）根據(jù)Levy flight對其他鳥巢進(jìn)行更新，得到一組新的鳥巢位置，并根據(jù)式（7）對鳥巢位置優(yōu)劣進(jìn)行評(píng)價(jià)。

7）將最優(yōu)鳥巢位置進(jìn)行解碼，輸出圖像特征的最優(yōu)權(quán)值，并根據(jù)自動(dòng)凋整好的特征權(quán)值跳轉(zhuǎn)步驟3）。

3 仿真實(shí)驗(yàn)

3.1 仿真數(shù)據(jù)

為了檢驗(yàn)MCS相關(guān)反饋圖像檢索算法性能，采用Corel－1000 database圖像庫中的圖像進(jìn)行仿真測試。Corel－1000 database其包含10類圖像，每類100幅，共有1 000幅圖像。在Intel Dual 2.8 GHz CPU，3 Gbyte RAM，操作系統(tǒng)Windows XP的環(huán)境中，采用C++實(shí)現(xiàn)圖像檢索算法。采用檢測確準(zhǔn)度（Perf）作為算法的性能評(píng)價(jià)標(biāo)準(zhǔn)，Perf定義為

式中:P表示查全率;R表示查準(zhǔn)率;α =0.7;β=0.3。

3.2 結(jié)果與分析

3.2.1 與傳統(tǒng)檢索算法性能對比

采用單一顏色特征檢索算法（Color）、單一紋理特征檢索算法（Shape）、固定權(quán)值的多特征檢索算法（Trad），這些算法均采用相關(guān)反饋技術(shù)。從Corel－1000 database中的每一類圖像中，隨機(jī)選擇20圖像組成測試的圖像數(shù)據(jù)庫，共200幅圖像，檢測結(jié)果如表1和圖1所示。

表1 MCS與傳統(tǒng)算法的反饋次數(shù)對比

圖1 不同算法的檢索性能對比

從圖1和表1可知，在所有圖像檢索算法中，MCS算法性能最優(yōu)，同時(shí)由圖1和表1的對比結(jié)果可以得到如下結(jié)論:

1）采用單一特征（顏色或紋理）對圖像進(jìn)行檢測，它們的檢測確準(zhǔn)度比較低，查詢結(jié)果不理想，這主要是由于單一特征無法全面、準(zhǔn)確描述圖像信息，從而難以找到滿足用戶要求的圖像。

2）相對于單一特征算法，傳統(tǒng)多特征檢索方法（Trad）的檢測準(zhǔn)確度較高，然而檢索過程中，反饋次數(shù)比較多，反饋次數(shù)波動(dòng)較大，對圖像檢索效率產(chǎn)生不利影響，這主要由于采用固定權(quán)值方法，權(quán)值的確定具有主觀性、盲目性，不能描述每一種特征對檢索圖像的貢獻(xiàn)。

3）MCS算法的檢索準(zhǔn)確度要高于對比算法Color、Shape和Trad，而且反饋次數(shù)要少于傳統(tǒng)多特征檢索算法，這主要是由于采用MCS算法對特征進(jìn)行了選擇，給出了更加準(zhǔn)確、客觀的圖像特征權(quán)重，使得相似度模型較為符合用戶的實(shí)際需求，從而提高了圖像檢索的精度和效率。

3.2.2 與遺傳算法、粒子群算的性能對比

為了說明基于MCS的圖像檢索算法優(yōu)越性，采用遺傳算法（GA）、粒子群算法（PSO）優(yōu)化圖像特征權(quán)值的相關(guān)反饋檢索方法進(jìn)行對比實(shí)驗(yàn)。對于相同的數(shù)據(jù)集，GA、PSO檢索結(jié)果如圖2所示。從圖2可知，相對于GA，PSO算法，MCS算法的檢索準(zhǔn)確度更高，這表明，采用MCS算法對圖像特征權(quán)值進(jìn)行確定，得到的權(quán)值更能夠反映特征對檢索結(jié)果的影響程度，權(quán)值更加科學(xué)、合理，得到更加滿意的檢索效果。

為了對比GA，PSO，MCS算法檢索效率，統(tǒng)計(jì)每類圖像的平均反饋次數(shù)，結(jié)果如表2所示。從表2可知，MCS算法的平均反饋次數(shù)只要3次，要明顯低于GA，PSO算法5次，圖像檢索效率大幅度提高了，可以建立圖像相似度模型較好地滿足用戶實(shí)際偏好，更好地滿足圖像檢索的實(shí)時(shí)、在線要求。

圖2 與GA，PSO算法的性能對比

表2 MCS，GA，PSO的反饋次對比

4 結(jié)束語

針對當(dāng)前圖像檢索算法存在的檢索精度低、效率低的難題，提出一種改進(jìn)布谷鳥的相關(guān)反饋圖像檢索方法。首先分別提取顏色、紋理和形狀等3種圖像特征，克服單一特征無法準(zhǔn)確描述圖像信息的不足，然后將全局搜索能力強(qiáng)的布谷鳥搜索算法引入到圖像相關(guān)反饋技術(shù)中，根據(jù)用戶反饋信息，動(dòng)態(tài)調(diào)整圖像特征權(quán)值，對圖像相似度模型進(jìn)行不斷修正，使圖像檢索向用戶感興趣的方向發(fā)展，減少反饋次數(shù)。仿真結(jié)果表明，相對于傳統(tǒng)檢索算法以及GA，PSO算法，MCS算法不僅提高了圖像檢索準(zhǔn)確率，同時(shí)加快了圖像檢索速度，可以更好地滿足用戶的需求。

:

［1］WU Hong，LU Hanqing，MA Dongde.A survey of relevance feedback techniques in content － based image retrival［J］.Chinese Journal of Computer，2005，28（12）:1303－1314.

［2］HAN D，SONKA M，BAYOUTH J，et al.Optimal multiple－seams search for image resizing with smoothness and shape prior［J］.The Visual Computer，2010，26（6）:749－759.

［3］龍清.基于顏色特征的電視圖像檢索［J］.電視技術(shù)，2012，36（8）:68－71.

［4］龔淼，付正，張尤賽.綜合BTC顏色矩和灰度共生矩陣的圖像檢索算法［J］.電視技術(shù)，2012，36（11）:30－34.

［5］JIANG Shuhong，HEN Bingfa.Method of image retrieval based on integrating low level feature with relevance feedback［J］.Machine Building and Automation，2009，38（3）:51－53.

［6］張振花，李波，鄧偉文.基于粒子群算法的圖像相關(guān)反饋研究［J］.系統(tǒng)仿真學(xué)報(bào)，2012，24（1）:126－130.

［7］BAI Xue，LIU Wanjun.Research of image retrieval based on color［C］//Proc.Forum on Computer Science Technology and Applications.New York:IEEE Press，2009:283－286.

［8］LIANG Jingmin.Image retrieval based on genetic FCM algorithm and support vector machines［J］.Computer Engineering and Applications，2009，45（20）:165－168.

［9］CUI Wencheng，SHAO Hong.Automatic feature weight assignment based on genetic algorithm for image retrieva1［J］.Computer Engineering and Applications，2008，44（2）:106－108.

［10］王凡，賀興時(shí)，王燕，等.基于CS算法的Markov模型及收斂性分析［J］.計(jì)算機(jī)工程，2012，38（11）:180－182.

Relevance Feedback Image Retrieval Based on Modified Cuckoo Search Algorithm

FU Baolong，ZHANG Aike

（Liuzhou Vocational Technological College，Guangxi Liuzhou 545006，China）

Traditional retrieval algorithm is difficult to satisfy with the user’s requirements because of“semantic gap”between visual low－level features and high－level semantic，in order to improve the accuracy of the image retrieval，a relevance feedback image retrieval method based on modified cuckoo search algorithm（MCS）is proposed in this paper.Firstly，the color and texture of image are extracted，and then the cuckoo search algorithm is used to dynamically adjust the feature weights according to the feedback information of users，and the image similarity model is built to meet user actual preferences.Finally，the simulation experiments are carried out to test the performance of MCS.The results show that，compared with the genetic algorithm，particle swarm algorithm and traditional image retrieval algorithms，the proposed algorithm not only has improved the accuracy of image retrieval，and fastened the image retrieval speed，it can better meet the needs of image retrieval.

image retrieval;relevance feedback;feature weight;cuckoo search algorithm

TN911.73;TP391

A

【本文獻(xiàn)信息】符保龍，張愛科.基于改進(jìn)布谷鳥搜索算法的相關(guān)反饋圖像檢索［J］.電視技術(shù)，2014，38（3）.

廣西教育廳科研項(xiàng)目（201106LX 745;201204LX593）

符保龍（1978— ），碩士，副教授，研究方向?yàn)樾畔z索、數(shù)據(jù)挖掘等;

張愛科（1973— ），女，碩士，副教授，研究方向?yàn)樾畔z索、數(shù)據(jù)挖掘、智能計(jì)算等。

責(zé)任編輯:時(shí) 雯

2013－04－07