一種新的基于SVM和主動學習的圖像檢索方法

彭晏飛，尚永剛,王德建

(1.遼寧工程技術大學電子與信息工程學院，遼寧 葫蘆島 125105;2.渤海裝備遼河重工有限公司，遼寧 盤錦 124010)

1 引言

20世紀90年代中期，在文本檢索領域中提出的相關反饋技術RF(Relevance Feedback)[1]被引入到了基于內容的圖像檢索[2]過程中。隨著相關反饋的深入研究，許多學者將相關反饋看作模式識別中的有監督學習或分類問題[3]，利用成熟的機器學習理論，如神經網絡、支持向量機SVM(Support Vector Machine)[4]等，通過對訓練樣本集的學習，得出用戶查詢目的與圖像特征之間對應的模型，然后根據模型指導新一輪的檢索。由于支持向量機在解決小樣本、非線性及高維模式識別中表現出的諸多優勢，使其得到了廣泛的研究和應用。

SVM的引入很大程度上提高了圖像檢索的檢索性能，但如何快速、準確地構造SVM分類器成為了阻礙其發展的主要問題，其中如何選擇最優的訓練樣本成為了其重中之重。主動學習[5,6]算法則為該問題的解決提供了很好的方向，主動學習算法并不是隨機地選擇訓練樣本，而是在學習過程中選擇最有利于提高分類器性能的未標注樣本來訓練分類器，該方法能有效地減少評價樣本的數量和代價，充分利用最具信息的未標注樣本來達到快速學習的目的。近年來在圖像檢索中已提出了多種基于支持向量機的主動學習方法，但大多都存在一定的局限性，如：文獻[7]中提到了一種以樣本到分類面距離及訓練樣本集中樣本的余弦距離和為標準的樣本主動選擇方法。

但是，該方法需要引入平衡因子，而平衡因子的確定在每次實驗中都要根據實驗要求選擇合適的參數，缺乏一般性。文獻[8]提出了一種SVM-active主動反饋算法，并認為最接近分類邊界的圖像最具有信息度(Informative)，因此在每個反饋策略中選擇最接近SVM分類超平面的樣本作為訓練樣本。但是，此方法的訓練樣本特征存在冗余，不具有最大信息度。文獻[9]提出一種基于K-means聚類的主動反饋策略，該方法提高了反饋圖片的多樣性，但易受聚類中心和K值的影響，不易達到理想的結果。因此，如何選擇既具有最小冗余度，又保持圖片多樣性的反饋樣本作為訓練樣本成為了研究的首要問題。

針對上述問題，本文提出一種新的基于SVM和主動學習的圖像檢索方法，通過SVM和新的主動學習方法來構造更好的分類器，包括“V”型刪除法和最優選擇法。其中“V”型刪除法用于快速縮減樣本集，最優選擇法則是從縮減樣本集中選擇出既接近分類超平面又具有最小冗余度的最優反饋樣本構成訓練樣本集。在主動學習過程中沒有引入任何不確定性變量，從而使得訓練出的分類器既準確，又易于實現，可得到更好的檢索結果。

2 支持向量機

SVM算法是20世紀90年代中期在統計學習理論基礎上發展起來的一種機器學習方法，該方法可以很好地控制學習機器的推廣能力，因而在圖像檢索中可以有效地改善檢索結果。在每次訓練中對用戶標記的正例和反例樣本進行學習，建立SVM分類器作為模型，并根據該模型進行檢索，如圖1所示。

由于在大多數分類問題中，樣本集都不是線性可分的，所以本文直接研究樣本非線性分類情況。在此情況下，SVM會事先選擇一個核函數來將樣本的原特征空間映射到一個高維的特征空間，使得樣本特征在高維空間中線性可分。

Figure 1 Support vector machine圖1 支持向量機

支持向量機算法的描述如下：

記已標注的圖像訓練樣本集為T={(x1,y1),(x2,y2),…,(xl,yl)}∈(Rn×Y)l，其中xi∈Rn表示圖像特征，yi∈Y={+1,-1}(+1表示相關，-1表示不相關)，其中l表示訓練樣本集的樣本數，則分類超平面的構造即為解決下面的最優化問題：

s.t.yi(w·Φ(xi)+b)-1+ξi≥0,

i=1,2,…,l

(1)

其中，ξi≥0,Φ是將訓練數據xi映射到高維空間的映射函數，C是對分類錯誤的懲罰因子，ξi是松弛項，w是用于決定最優分類面方向的權向量。該最優問題可用如下的對偶形式解決，即：

0≤αi≤C,i=1,2,…,l

(2)

其中，α是Lagrange乘子，核函數K(xi,xj)表示(Φ(xi)·Φ(xj))，K有多種形式，如線性核函數、多項式核函數、徑向基核函數、Sigmoid核函數和復合核函數。求解可得最優分類面方程：

(3)

3 本文算法

3.1 預備知識

主動學習是一種人工交互的學習算法，該算法可以通過自動提供未標注樣本給訓練集來減輕人工負擔。其基本思想是選擇最具有信息度的樣本提供給用戶進行標注，即從未標記樣本集中選取最優樣本集來提高下一輪的檢索精度。一般情況下，主動學習方法由兩個獨立的部分組成：(f,g)，其中f代表學習器，g表示查詢函數，即從未標記樣本集中選取最具有信息度的樣本。所以，在主動學習中最重要的就是查詢函數g，該函數對主動學習算法的性能起到了主要作用。在各種主動學習算法中，兩種最常用的方法是基于不確定樣本標注法[10]和基于委員會投票方法[11]來選取要進行標記的樣本；在基于不確定樣本標注中要選擇進行標注的樣本是在分類中具有最小確定性的樣本，在基于委員會投票方法中，在已標記樣本集中訓練出分類委員會，然后將其運用到未標記樣本集中，并認為在分類中具有最高分類不一致性的樣本為最具有信息度的樣本。所以，本文中的主要任務就是尋找在每輪的反饋過程中可以獲取更好分類效果的樣本，這些樣本的選擇可以使我們以更少的反饋次數得到更好的查詢效果。

Figure 2 Sample relationship圖2 樣本關系

圖2中，f(x)=0為分類超平面，f(x)=1為正支撐平面，f(x)=-1為負支撐平面，A、B、C、D為位于分類超平面同一側的樣本，α為樣本B、C之間的夾角，β為樣本B、D之間的夾角，d(A,B)為樣本A、B之間的距離，d(A)為樣本A到對應的支撐平面的距離。

首先作以下定義：

定義1樣本距離：樣本xi、xj之間的距離定義為其歐氏距離，公式如下：

(4)

定義2分類距離：樣本到分類超平面距離。若分類超平面方程為f(x)，則樣本xi的分類距離公式為：

(5)

定義3樣本夾角：兩樣本間連線與分類超平面之間的夾角，其范圍為[0,π/2]。樣本xi、xj之間的夾角公式為：

(6)

定義4平均角：某一樣本與樣本集中其它樣本的樣本夾角的平均值。樣本xi的平均角公式為：

(7)

3.2 “V”刪除法

在圖像檢索中往往面臨著樣本集過大而導致檢索時間長、效率低的問題，如何有效縮減樣本集成為了提高檢索效率的重要研究方向。

傳統的樣本縮減策略僅僅是刪除了距離分類面遠的樣本，但對于冗余度較高的樣本卻沒有進行有效的處理。文獻[12]中提到了一種新的樣本縮減策略，但該算法運用C均值聚類算法，從而使得算法復雜度較高。

本文從樣本與分類面及樣本與樣本之間的關系出發，提出一種以樣本夾角為基礎的“V”型刪除法。與傳統的樣本縮減策略不同的是，該方法不僅可以刪除大量距離分類面遠的樣本，而且可以刪除與訓練樣本近的部分樣本，從而得到更優的縮減樣本集，并且算法簡單、易行。

為減少運算時間，在運用“V”型刪除法之前先對未標記樣本集進行預處理。因為在SVM中，對分類面有影響的主要有支持向量，所以首先對樣本集做預處理，保留到最優分類面距離小于2/w的樣本，這樣則可以大大縮短計算時間。

假設當前最優訓練樣本集為F={f1,f2,…,fl}，經過預處理的縮減樣本集Ul-1={ul-1,1,ul-1,2,…,ul-1,p}。

則“V”型刪除法的具體步驟如下：

步驟1利用公式(5)計算當前訓練樣本fl與Ul-1中所有樣本的分類距離，即d(fl)、d(ul-1,i),i=1,2,…,p。

3.3 最優選擇法

在SVM的構造中，訓練樣本的選取是一個亟待解決的問題。傳統的方法是選取距離分類面最近的樣本作為訓練樣本，如文獻[6,13]，但這種完全基于距離的選擇原則并不一定能使選擇的樣本具有多樣性，特別是在樣本集中的樣本屬于多個不同類別的情況下就不再可靠了。

針對以上問題，本文提出一種訓練樣本的最優選擇法。該方法所選擇出的訓練樣本不僅與分類面的距離較近，而且訓練樣本間具有較低的冗余度，從而保證了訓練樣本的多樣性，得到更優的分類器。

假設當前最優訓練樣本集為F={f1,f2,…,fl}，縮減樣本集Ul={ul,1,ul,2,…,ul,k}。

則最優選擇法的具體步驟如下：

步驟2從樣本集Ul中選取同時滿足|d(ul,i)|<|d(fl,1)|和〈ul,i,fl,1〉≥(π-〈fl,1,fj〉min)/2,j=1,2,…,l的樣本，加入集合Ul′。Ul′初始為空。其中〈fl,1,fj〉min表示fl,1與F中所有樣本的最小樣本夾角。

步驟3若Ul′為空集，則fl,1即為第l+1個最優的訓練樣本;否則，從Ul′中選擇到Fl+1和F中所有樣本的距離和最大的樣本為可能最優的訓練樣本，記為fl,2，加入Fl+1←fl,2，返回步驟2。

步驟4不斷重復以上步驟直到樣本集Ul′為空集，此時Fl+1={fl,1,fl,2,…,fl,n}，則fl,n即為第l+1個最優的訓練樣本，記為fl+1，則此時最優訓練樣本集F={f1,f2,…,fl,fl+1}。

3.4 本文基于SVM和主動學習的檢索方法

基于以上思路，提出一種新的基于SVM和主動學習的圖像檢索方法，具體步驟如下：

輸入:查詢圖像Q，圖像數據庫DB。

初始化：F=?，U←DB。

步驟1通過計算Q與未標注樣本U之間的距離進行相似性排序，輸出一個結果集。若用戶滿意該結果，則算法結束；否則轉到步驟2。

步驟2對結果集樣本進行標注(相關、不相關)，相關圖像加入樣本集V+,不相關圖像加入樣本集V-，訓練集為V=V+∪V-。在V上訓練SVM分類器，得到分類器h1。利用h1對未標注樣本進行分類，得到正、負類樣本集U+、U-，U-V=U+∪U-。

步驟3從U+∪V+中選取距離分類面最遠的N幅圖像為輸出結果，若用戶滿意，則算法結束；否則轉到步驟4。

步驟4假設每次需要標注的反饋樣本數為K,則從U+中首先選擇一個距離分類面最近的樣本為第一個最優反饋樣本，然后根據“V”型刪除法和最優選擇法得到前K/2個最優反饋樣本，即最優的訓練樣本集F+。

步驟5同理，從U-中得到前K/2個最優訓練樣本的樣本集F-，則用于用戶標注的訓練結果集F=F+∪F-;然后將訓練結果加入訓練樣本集V←F，剩余樣本集U←U-V，返回步驟2。

4 實驗及結果

為證明所提算法的有效性，本文實驗與傳統的基于SVM和主動學習的圖像檢索算法在同一圖像集上進行對比。實驗選用Corel圖像庫，選取10類圖像，包括：雪山、大海、建筑、汽車、花卉、大象、恐龍、食物、飛機、馬，每類100幅圖像，共計1 000幅圖像。

隨機從每個類別中選取5幅圖像，總共50幅圖像用于查詢。實驗中以平均查準率為評價標準來反映算法的檢索性能。設s為查詢結果中檢索到的所有相關圖像數目，u為檢索到的不相關圖像數目，則查準率可以表示為：

(8)

為驗證本文圖像檢索方法性能，在VS2010平臺進行實驗，圖3和圖4是在相同檢索條件下經過兩次反饋后的圖像檢索結果，從檢索結果中可以看到本文算法不僅具有很好的檢索性能，而且獲得的檢索結果具有更好的序列性。

Figure 3 Retrieval results of traditional method圖3 傳統方法檢索結果

Figure 4 Retrieval results of this paper圖4 本文方法檢索結果

為更好說明本文算法的可靠性，實驗以查準率為對比標準，將傳統的基于SVM和主動學習的圖像檢索方法與本文的方法進行了詳細的對比實驗，實驗對比結果如表1和表2及圖5和圖6所示。

Table 1 Retrieval performance of traditional SVM active learning method表1 傳統SVM主動學習檢索性能 %

Table 2 Retrieval performance of this paper method表2 本文算法檢索性能 %

Figure 5 Average precision rate of Top20圖5 Top20的平均查準率

Figure 6 Average precision rate of Top40圖6 Top40的平均查準率

上述表1和表2分別為傳統SVM主動學習算法和基于本文算法的圖像檢索實驗所得實驗數據，圖5和圖6則顯示了兩種方法在Top20和Top40的平均查準率。實驗結果表明，在相同檢索條件下與傳統基于SVM主動學習的圖像檢索相比，本文算法平均具有8%以上的性能提升。由對比實驗結果可知，本文提出的方法的確可以使得訓練樣本得到更好的選擇，獲得更好的分類器，從而較大幅度地提高檢索性能。

5 結束語

本文提出一種新的基于SVM和主動學習的圖像檢索方法，通過“V”型刪除法與最優選擇法的結合使用，使得選擇的訓練樣本不僅具有較大的信息度，而且訓練樣本之間具有很小的冗余度，從而可以擴大所覆蓋的樣本空間，得到更好的訓練結果。在研究本文算法的同時研究了其它的基于SVM主動學習的圖像檢索方法，發現本文方法不僅易于實現，而且算法中沒有引入其它輔助因子，因而無需討論閾值或最佳值的選取，使得檢索更加準確。最后通過實驗驗證了本文算法的可靠性和高效性。

[1] Wu Hong, Lu Han-qing, Ma Song-de. A survey of relevance feedback techniques in content-based image retrieval [J]. Chinese Journal of Computers, 2005, 28(12):1969-1979.(in Chinese)

[2] Li Xiang-yang,Zhuang Yue-ting,Pan Yun-he.The technique and systems of content-based image retrieval [J]. Journal of Computer Research and Development, 2001, 38(3):344-352.(in Chinese)

[3] Haykin S. Neural networks and learning machines[M]. 3rd ed. MA:Prentice-Hall, 2008.

[4] Zhang Lei, Lin Fu-zong, Zhang Bo. Support vector machine learning for image retrieval [C]∥Proc of IEEE International Conference on Image Processing, 2001:721-724.

[5] Long Jun, Yin Jian-ping, Zhu En, et al. A survey of active learning [J]. Journal of Computer Research and Development, 2008,45(Suppl):300-304. (in Chinese)

[6] Wu Wei-ning, Guo Mao-zu, Liu Yang. A method of active learning with optimal sampling strategy [C]∥Proc of CSAE’12, 2012:725-729.

[7] Xie Hong-Sheng,Zhang Hong.Active learning method based on support vector machine in content-based image retrieval [J]. Journal of Shandong Normal University(Natural Science), 2007,22(4)：46-48.(in Chinese)

[8] Tong S, Chang E. Support vector machine active learning for image retrieval [C]∥Proc of the 9th ACM International Conference on Multimedia, 2001:107-119.

[9] Zhang Yu-fang, Chen Zhuo, Xiong Zhong-yang, et al. Image retrieval method based on SVMs and active learning [J]. Computer Engineering and Applications, 2010, 46(24):193-196.(in Chinese)

[10] Cohn D A, Atlas L, Ladner R E. Improving generalization with active learning[J]. Machine Learning, 1994,15(2):201-221.

[11] Seung H S, Opper M, Sompolinsky H. Query by committee[C]∥Proc of the 5th Annual ACM Conference on Computational Learning Theory, 1992:287-294.

[12] Zhu Fang, Gu Jun-hua, Yang Xin-wei, et al. New reduction strategy of large-scale training sample set for SVM [J]. Journal of Computer Applications, 2009,29(10):2736-2740.(in Chinese)

[13] Feng Guo-he.Research on large scale SVM classification based on boundaryK-nearest [J]. Computer Engineering and Applications, 2009,45(23):15-17.(in Chinese)

附中文參考文獻：

[1] 吳洪, 盧漢清, 馬頌德. 基于內容圖像檢索中相關訓練技術的回顧[J]. 計算機學報, 2005, 28(12):1969-1979.

[2] 李向陽, 莊越挺, 潘云鶴. 基于內容的圖像檢索技術與系統 [J]. 計算機研究與發展, 2001, 38(3):344-352.

[5] 龍軍，殷建平，祝恩，等. 主動學習研究綜述 [J]. 計算機研究與發展，2008,45(Suppl):300-304.

[7] 解洪勝，張虹. 基于支持向量機的圖像檢索主動學習方法[J]. 山東師范大學學報(自然科學版)，2007,22(4)：46-48.

[9] 張玉芳, 陳卓, 熊忠陽，等. 一種基于SVM和主動學習的圖像檢索方法 [J]. 計算機工程與應用,2010, 46(24):193-196.

[12] 朱方，顧軍華，楊欣偉，等. 一種新的支持向量機大規模訓練樣本集縮減策略 [J].計算機應用，2009,29(10):2736-2740.

[13] 奉國和. 邊界K鄰近大樣本支持向量機分類[J].計算機工程與應用，2009,45(23)：15-17.