基于多示例學習的圖像檢索方法

◆陳濤

( 深圳職業技術學院教育技術與信息中心 廣東 518055 )

0 引言

近幾十年來，基于內容的圖像檢索技術成為研究熱點。用戶提交一個或幾個樣例圖像，檢索系統從圖像數據庫中選出一組相關圖像作為檢索結果返回給用戶[1]。在圖像檢索中，用戶感興趣的一般是圖像中的一個或幾個區域，而不是整幅圖像。用戶對圖像的一個區域感興趣，就認為該幅圖像為感興趣圖像。例如，一幅馬的圖像，除了具有“馬”的區域特征，可能它還包含有草叢、灌木等背景區域，只要圖像中含有一個“馬”特征的區域，就會被認為是感興趣圖像。圖像中的全部區域均不是“馬”特征區域，才會被認為是不感興趣圖像。圖像檢索問題與多示例學習的假設十分相似，能夠使用多示例學習框架來處理圖像檢索問題[2]。

多示例學習首先被Dietterichet等人[3]提出并用在藥物活性分子預測研究。它是一類處理粗糙標簽信息的學習算法，近來年，很多國內外學者致力于這方面的研究工作[4]。在多示例學習算法研究中，代表性算法有多樣性密度（DD）算法、ED-DD算法等。DD算法是Maron等人提出，通過在特征空間中尋找一個目標概念點，使得每個正包中至少有一個示例離該點較近，而負包中的示例均遠離該點。找到該點后，就可以把這個點作為參照點來判斷新包的標簽。DD算法使用梯度上升法求解目標函數。以每個示例作為一次搜索起點，在示例空間中執行搜索，一次搜索找到一個局部極大值。最后通過比較極值，得到全局最大值。它的缺點是需要多次搜索特征空間，計算時間開銷較大[5]。EM-DD算法是將期望最大(EM)算法與DD算法相結合來得到目標概念點。

1 基于多示例學習的圖像檢索方法實現

首先將每幅圖像分割成若干個區域，每個區域析取出一個9維的區域特征[6]，將圖像和區域分別看作為多示例學習中的包和示例，這樣，將圖像檢索問題轉換到多示例學習框架處理。多示例學習算法，本文采用EM-DD算法[7]。

在EM-DD算法中，包的標記由包中具有最大可能為正的示例決定，通過EM算法來估計每個包中對包的標記起決定作用的示例。令為帶有最大DD值的目標概念點，為第i個包，為包的標簽，有公式：

M-Step：對這些訓練示例求得公式(1)的最大值，得到新的概念點。

EM-DDE-Step算法通過 步將包中的多示例轉換成單示例代表包，降低了求解優化函數的復雜度和計算量。

相關反饋技術是通過用戶與檢索系統進行交互反饋，來提煉用戶所想的語義。系統從反饋的圖像標記中學習用戶的檢索需要，自動調整相似性度量標準，形成新的查詢，循環幾個輪次，直到用戶得到滿意的圖像。因而，它被融合到本文提出的圖像檢索方法，算法流程圖如圖1所示。

算法的實現描述如下：

輸出： 從未標簽圖像集U中返回相似度成績排名前k名的圖像

(1) 用戶選擇一組相關圖像和一組不相關圖像作為查詢圖像。

(2) 將每幅圖像分割成若干個區域，每個區域析取出一個 9維的區域特征。將圖像和區域分別看作為多示例學習中的包和示例。

(3) 使用 EM-DD多示例學習算法，求得特征空間中的目標概念點。

(4) 將未標簽圖像集U中的圖像與目標概念點的向量距離作為該圖像與檢索圖像的相似度成績。排名前k 幅圖像被作為檢索結果返回給用戶。

(5) 執行幾輪的用戶相關反饋，直到一組滿意的圖像集被返回給用戶。在返回圖像中，用戶標簽一些相關樣本作為正反饋，一些不相關樣本作為負反饋。為了減少用戶標注的工作量，用戶可以僅標注負類圖像（不感興趣類圖像），其余圖像被作為正類圖像，這些正類圖像和負類圖像被加入到上輪的圖像一起作為新的訓練集。在相關反饋過程中，不斷提煉用戶的高級語義概念，直至返回滿意的圖像給用戶，由用戶終止查詢過程。

圖1 算法流程圖

2 實驗結果與分析

實驗在Corel圖像集上進行。為了估算檢索算法的性能，我們做了3個實驗：第1個是圖像檢索一個樣例；第2個是與DD多示例學習圖像檢索方法的檢索有效性能比較；第3個是相關反饋技術對檢索精度的提高。

Corel圖像集為COREL 2000，來自：http://www.cs.olemiss.edu/～ychen/ddsvm.html。它有 20 類，每類有100幅圖像。類別分別為：非洲人和村莊、海灘、歷史建筑、公共汽車、恐龍、大象、花、馬、山和冰川、食物等。圖像分割采用文獻[] 的分割方法，每個圖像被分割成2-10個區域，每個區域用一個9維特征表示其顏色、紋理、形狀特征。

實驗1：圖像檢索的一個樣例。

設置一類圖像作為目標類，從目標類別圖像中隨機選擇3幅興趣圖像作為正類圖像；另外，從其它3類圖像中各隨機選擇1幅圖像，組成負類圖像。圖2給出了一個圖像檢索“馬”類圖像且沒有帶相關反饋技術的樣例，返回與查詢圖像相似概率高的前20幅圖像。從圖2的返回圖像看，方法取得了較好的檢索結果。

圖2 檢索“馬”類圖像的一個樣例

實驗2: 與DD多示例學習圖像檢索方法檢索效率性比較。

采用計算耗時來評測檢索的效率。計算耗時是指從用戶提交檢索圖像給系統到第一輪圖像返回之間的時間。實驗條件為Intel Core i5-4570 CPU 3.2GHz，3.2GHz和內存8GB的微機。圖像庫為Corel 2000，返回排序前20幅圖像。兩個方法的計算時間如表1所示：

表1 計算耗時比較（秒）

從表1可以看出，EM-DD方法相較DD方法，它的計算耗時大大減少，約為DD方法的1/3。這是因為：DD方法需要將所有正包的正示例作為一個初始點，來尋找局部極大值，最后比較這些局部極值點。這個過程耗時較長。而EM-DD方法，結合EM方法來尋找DD函數最大值，能快速收斂，減少耗時。

實驗3：相關反饋技術對方法的性能提高。

相關反饋技術能有效的提高檢索性能。圖3顯示了沒有帶相關反饋，帶1輪、2輪、3輪相關反饋的“精度-召回率”曲線：

圖3 帶相關反饋技術的“精度-召回率”曲線

從圖3可以看出，每輪相關反饋后的精度，均較上輪的檢索精度高。經過3輪的用戶反饋后，檢索精度得到了大幅提高。這是因為：一個是通過用戶相關反饋的標記，更多的標記圖像加入到學習中。另一個是通過負相關反饋，系統不斷的提煉用戶感興趣的圖像。

3 結束語

本文提出了一個基于多示例學習的圖像檢索方法。它有兩個特點：一是通過多示例學習框架來處理圖像檢索問題；二是通過相關反饋技術提煉用戶查詢圖像的語義概念，縮小語義概念與視覺特征表示之間的“語義鴻溝”。在Corel圖像集上的實驗表明，提出的方法具有較好的檢索性能。