摘要：本文將相關(guān)反饋看成一個二分類問題，從反饋中固有的問題和用戶的需求為出發(fā)點，在傳統(tǒng)的移動查詢點的基礎(chǔ)上，提出了改進的基于受限隨機選擇和檢索結(jié)果集的圖像檢索相關(guān)反饋系統(tǒng)。實驗證明，該方法很好的解決了反饋中固有的小樣本問題和正負樣本不對稱的問題。同時，綜合利用用戶的反饋信息，在較少的反饋次數(shù)內(nèi)得到了較好的檢索準確率。

關(guān)鍵詞：相關(guān)反饋；SVM；受限隨機選擇；檢索結(jié)果集

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)14-20919-03

1 引言

對于基于內(nèi)容的圖像檢索而言，低層視覺特征（如顏色、紋理、形狀）與圖像的高層語義（如圖像描述的主題、對象，表達的情緒等）存在著很大的語義間隔，從高層語義的查詢概念到低層圖像特征的映射是一個必需完成而又非常困難的問題。而用戶又不可能像用檢索詞表達文本檢索的查詢概念那樣來組織圖像特征用以表達圖像查詢的概念。因此，必需引入相關(guān)反饋技術(shù)（Relevance Feedback RF）。

相關(guān)反饋是提高系統(tǒng)查詢效果的一種強有力的方法，它從用戶與查詢系統(tǒng)的實際交互過程中進行學(xué)習(xí)，發(fā)現(xiàn)并捕捉用戶的實際查詢意圖，并以此修改系統(tǒng)的查詢策略，從而得到與用戶實際需求盡可能相吻合的查詢結(jié)果。相關(guān)反饋機制從20世紀90年代中期被引入圖像檢索中以來，得到了很快的發(fā)展[1-3]。從最早的通過移動查詢向量和調(diào)整特征權(quán)值的方法到后來出現(xiàn)的判別式分析方法、密度估計方法、模式分類方法和機器學(xué)習(xí)的方法等等。其中有一些方法也取得了比較好的效果。RF實際上是可以看成是一個分類問題，因此很多經(jīng)典的分類算法都可以運用到RF中來。同時，RF分類也存在著自身的特點（問題），主要有以下三個方面：(1)小樣本問題；(2)正負樣本不對稱問題；(3)用戶的貪婪性：因此，采用任何一種分類算法來解決RF時必需要考慮到以上三個問題。本文基于以上問題，提出了一種改進的基于受限隨機選擇和檢索結(jié)果集[4]的相關(guān)反饋技術(shù)。受限隨機選擇的方法很好的解決了反饋中的小樣本問題和正負樣本不對稱的問題，而通過截取檢索結(jié)果集的方法在一定程度上提高了反饋的效率，更好的適應(yīng)了用戶的貪婪性。

2 SVM相關(guān)反饋

支持向量機[5]是最有效的分類技術(shù)之一，被廣泛地應(yīng)用到RF中。然而，RF固有的兩大問題在經(jīng)典的SVM中并沒有得到很好的考慮和解決。目前，已經(jīng)有很多人對RF中運用的SVM算法進行改進。本文從RF固有問題出發(fā)，提出了自己對利用SVM解決RF問題改進的算法。

SVM有較強的理論基礎(chǔ)和實踐經(jīng)驗，對小樣本有較好的分類性能，而小樣本正是CBIR中RF的一個重要特點，SVM因其通用性和出色的分類能力被廣泛地應(yīng)用到RF中。一個支持向量機就是一個預(yù)先定義好了函數(shù)形式的函數(shù)。訓(xùn)練一個支持向量機需要一個事先標記過的訓(xùn)練樣本集，SVM 將會試圖使函數(shù)符合這些樣本。SVM相關(guān)反饋基本思想如下：通過用戶對提供圖像的相關(guān)性的標注得到訓(xùn)練樣本集，尋找到將給定的屬于兩個類別（正負樣本類）的訓(xùn)練圖像分開的最優(yōu)分類面，然后以圖像庫做為測試樣本，輸出正樣本類中離超平面最遠的圖像作為檢索結(jié)果。本文將SVM方法作為分類器引入。

SVM的分類思想可描述為通過使各類之間距離最大確定超平面：

3 受限隨機選擇

在SVM分類中一個非常重要的問題就是訓(xùn)練樣本集獲取，由于RF中固有的小樣本問題，我們最開始獲得的訓(xùn)練樣本數(shù)目非常有限，這會導(dǎo)致分類器不穩(wěn)定、不可信賴，盡管有的方法通過累積前面反饋過程中的反饋圖像擴大訓(xùn)練樣本，但是其獲取的樣本信息量很少，分類性能不佳，用戶常常無法忍受。為了有效地解決這個問題，本文提出CRS方法來擴大負樣本（不相關(guān)圖像）的集合，這種方法既避免了隨機選擇的盲目性，又彌補了訓(xùn)練樣本中的負樣本類對整個負樣本類代表性差的缺點。因為受限隨機選擇的這些負樣本能夠比較好地反映圖像庫中所有的負樣本（不相關(guān)圖像）在特征空間的分布。具體思想如下：

(3)選擇范圍二次受限：確定好負樣本為離正樣本類最遠的一部分樣本并不足夠，因為如果單一的在此區(qū)域內(nèi)進行隨機選擇，顯然選擇出的負樣本對負樣本類的代表性還具有一定的盲目性。為了使各個距離程度上的負樣本類均會被選擇到，即保證在每個相似度層次樣本都有分布，將之前確定選擇范圍再分為L段（等距劃分）在此L段上再分別隨機選擇若干樣本?？梢哉J為，基于此思想上選擇的負樣本較隨機選擇而言對負樣本類具有較好的代表。

4 檢索結(jié)果集的選取

反饋算法在利用人機交互有效的彌補一次檢索準確率不高的缺點的同時，反復(fù)的距離計算和比較必然帶來檢索時間的負擔。一般認為用戶的耐心是有限的，且較一次檢索而言，反饋次數(shù)已經(jīng)給用戶帶來了一定的耐力考驗，因此，在不影響檢索精度的前提下，我們不希望用戶在每次反饋的時間上消耗過多的時間等待。出于以上考慮，本文在移動查詢點的基礎(chǔ)之上，結(jié)合用戶的反饋信息，采取部分結(jié)果做為檢索結(jié)果集（測試樣本），在該結(jié)果集上進行后續(xù)操作來完成檢索結(jié)果的更新。依據(jù)圖像庫的大小以及圖像特征維數(shù)確定檢索結(jié)果集的范圍上限為M。

5 系統(tǒng)算法描述

有了上面的知識準備，我們給出該系統(tǒng)的算法描述：

(1)輸入查詢向量，首次檢索，返回檢索結(jié)果；

(2)用戶依據(jù)自己的信息需求對顯示結(jié)果進行標注，根據(jù)用戶標注和受限隨機選擇確定擴大后的訓(xùn)練樣本集train;

(3)修改查詢向量Q1得到Q2。用Q2在全庫搜索，截取檢索結(jié)果的前M個并保存作為結(jié)果集，即測試樣本集test;

(4)根據(jù)訓(xùn)練樣本集train和測試樣本集test運用SVM，輸出保留上一輪的相關(guān)圖像，在其位序后輸出新出現(xiàn)的最相關(guān)圖像;

(5)結(jié)束條件：若顯示結(jié)果用戶滿意，則算法退出；否則返回(2)。

最后，考慮在系統(tǒng)實現(xiàn)時，因M個數(shù)有限使用SVM分類得到最相似類的基數(shù)n小于N時需將次相近類的前N-n個圖像補充顯示給用戶。

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

實驗在Brodatz標準紋理圖像庫中進行，圖1給出了3次反饋后的一組實例，分別采用傳統(tǒng)的移動查詢點、非受限隨機選擇的SVM反饋和本文方法，顯示數(shù)目為25，結(jié)果集M＝400。

從該對比結(jié)果可以大致看出：本文方法比單獨的移動查詢點和非受限隨機選擇結(jié)果都要好。

體現(xiàn)反饋系統(tǒng)的一個重要指標就是在較短的反饋次數(shù)內(nèi)得到較高的檢索精度（查準率和查全率）。為了體現(xiàn)本文系統(tǒng)的優(yōu)越性，將本文方法與傳統(tǒng)的移動查詢點反饋方法和非受限隨機選擇的反饋方法的前3次反饋的查準率與查全率做了比較，比較結(jié)果如表1所示（顯示數(shù)目為16）。

從表中實驗數(shù)據(jù)可以看出，與傳統(tǒng)的移動查詢點反饋方法和非受限隨機選擇的反饋方法相比較，本文的反饋方法的查準率與查全率有明顯提高，且前2次反饋基本上可以達到用戶的需求。且隨著顯示數(shù)目的增加，該方法的優(yōu)越性則更加明顯，因為顯示數(shù)目直接影響用戶標注樣本數(shù)即訓(xùn)練樣本數(shù)。但是考慮到用戶的標注疲勞，并不建議通過增加顯示數(shù)目的方式來增加訓(xùn)練樣本數(shù)。

如前所述，反饋時間也是用戶十分關(guān)心的一個問題，因此，本文對幾種反饋方法在不同顯示數(shù)目的前3次平均響應(yīng)時間也做了對比，對比結(jié)果如圖2所示。

由圖2可知：本文方法較移動查詢點方法和非受限隨機選擇的反饋方法，檢索時間并沒有明顯的增加。而從前面的實驗可以看出，本文算法在查準率和查全率上都有明顯的提高，因此，本文提出的反饋系統(tǒng)具有較好實驗效果。能在較短的反饋次數(shù)內(nèi)，以較快的速度輸出用戶期望的檢索結(jié)果。

7 結(jié)束語

相關(guān)反饋是彌補低層特征與高層語義之間的語義鴻溝，并提高檢索準確度的一個有效方法。相關(guān)反饋的目的使把用戶從要自己完成高層語義到低層特征映射的任務(wù)中解放出來。

RF過程可以看成是一個二分類問題，即如何根據(jù)用戶標注的正、負樣本類（相關(guān)圖像類、不相關(guān)圖像類）訓(xùn)練有效的分類器來完成整個數(shù)據(jù)集（圖像庫）上的分類。RF中固有的小樣本問題，即獲得的訓(xùn)練樣本的數(shù)目（通常不超過30個）比表示圖像的特征維數(shù)（通常上百維）少很多，訓(xùn)練得到的分類器存在性能不穩(wěn)定等問題。而且，用戶反饋的負樣本是上一次檢索結(jié)果中的圖像，一般比較接近正樣本類，這更限制了負樣本對負樣本類的代表性。因此，本文在首先隨機選擇擴大負樣本后，提出截取部分檢索結(jié)果作為檢索結(jié)果集，在結(jié)果集（測試樣本）中使用SVM方法并以系統(tǒng)交互過程的記憶為輔助得到最終結(jié)果的方法。較好地解決小樣本帶來的分類器性能不穩(wěn)定問題以及正負樣本不對稱問題。能夠以較少的反饋次數(shù)和較快的反饋時間返回用戶滿意的檢索結(jié)果，提高檢索精確度。

參考文獻：

[1] Zhou X S， Huang T S1. Relevance feedback in image retrieval: a comprehensive review[J]. 1 ACM Multimedia Systems Journal ，2003，8(6):536- 544.

[2] Rui Y， Huang T S1. Optimizing learning in image retrieval[C]. Proceedings of Computer Vision Pattern Recognition， HiltonHead Island， South Carolina， 2000: 236-243.

[3] Salton G. Automatic text processing: the transformation， analysis， and retrieval of information by computer [M]. [S.l.]: Addison-Wesley， 1988.

[4] 羅燁，湯進，羅斌. 一種基于檢索結(jié)果集的圖像檢索相關(guān)反饋算法[J]. 計算機工程與應(yīng)用，2007， 43(11):69-73.

[5] 周建新， 高科， 李錦濤， 張勇東， 唐勝. 圖像檢索中一種有效的SVM相關(guān)反饋算法[M]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報， 2007，19(4).

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文