基于改進布谷鳥搜索算法的相關反饋圖像檢索

符保龍，張愛科

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

基于改進布谷鳥搜索算法的相關反饋圖像檢索

符保龍，張愛科

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

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

圖像檢索;相關反饋;特征權值;布谷鳥搜索算法

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

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

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

1 改進布谷鳥搜索算法和圖像特征

1.1 改進布谷鳥搜索算法

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

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

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

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

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

式中:?表示步長控制量;⊕表示點對點乘法。

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

1.2 圖像特征及相似度模型

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

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

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

rij定義為

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

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

2 基于MCS的相關反饋圖像檢索算法

2.1 鳥巢位置的編碼

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

2.2 鳥巢位置優(yōu)劣衡量標準

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

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

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

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

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

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

步驟3:對圖像特征賦初始權值。

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

2）根據(jù)式（7）對鳥巢位置優(yōu)劣進行評價，找到當前最優(yōu)鳥巢x（0）b。

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

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

3 仿真實驗

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

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

式中:P表示查全率;R表示查準率;α =0.7;β=0.3。

3.2 結果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

:

［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］.電視技術，2012，36（8）:68－71.

［4］龔淼，付正，張尤賽.綜合BTC顏色矩和灰度共生矩陣的圖像檢索算法［J］.電視技術，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］張振花，李波，鄧偉文.基于粒子群算法的圖像相關反饋研究［J］.系統(tǒng)仿真學報，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］王凡，賀興時，王燕，等.基于CS算法的Markov模型及收斂性分析［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

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

廣西教育廳科研項目（201106LX 745;201204LX593）

符保龍（1978— ），碩士，副教授，研究方向為信息檢索、數(shù)據(jù)挖掘等;

張愛科（1973— ），女，碩士，副教授，研究方向為信息檢索、數(shù)據(jù)挖掘、智能計算等。

責任編輯:時 雯

2013－04－07