一種新的基于SVM和主動(dòng)學(xué)習(xí)的圖像檢索方法

彭晏飛，尚永剛,王德建

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

1 引言

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

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

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

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

2 支持向量機(jī)

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

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

Figure 1 Support vector machine圖1 支持向量機(jī)

支持向量機(jī)算法的描述如下：

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

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

i=1,2,…,l

(1)

其中，ξi≥0,Φ是將訓(xùn)練數(shù)據(jù)xi映射到高維空間的映射函數(shù)，C是對(duì)分類錯(cuò)誤的懲罰因子，ξi是松弛項(xiàng)，w是用于決定最優(yōu)分類面方向的權(quán)向量。該最優(yōu)問題可用如下的對(duì)偶形式解決，即：

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

(2)

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

(3)

3 本文算法

3.1 預(yù)備知識(shí)

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

Figure 2 Sample relationship圖2 樣本關(guān)系

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

首先作以下定義：

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

(4)

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

(5)

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

(6)

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

(7)

3.2 “V”刪除法

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

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

本文從樣本與分類面及樣本與樣本之間的關(guān)系出發(fā)，提出一種以樣本夾角為基礎(chǔ)的“V”型刪除法。與傳統(tǒng)的樣本縮減策略不同的是，該方法不僅可以刪除大量距離分類面遠(yuǎn)的樣本，而且可以刪除與訓(xùn)練樣本近的部分樣本，從而得到更優(yōu)的縮減樣本集，并且算法簡(jiǎn)單、易行。

為減少運(yùn)算時(shí)間，在運(yùn)用“V”型刪除法之前先對(duì)未標(biāo)記樣本集進(jìn)行預(yù)處理。因?yàn)樵赟VM中，對(duì)分類面有影響的主要有支持向量，所以首先對(duì)樣本集做預(yù)處理，保留到最優(yōu)分類面距離小于2/w的樣本，這樣則可以大大縮短計(jì)算時(shí)間。

假設(shè)當(dāng)前最優(yōu)訓(xùn)練樣本集為F={f1,f2,…,fl}，經(jīng)過預(yù)處理的縮減樣本集Ul-1={ul-1,1,ul-1,2,…,ul-1,p}。

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

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

3.3 最優(yōu)選擇法

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

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

假設(shè)當(dāng)前最優(yōu)訓(xùn)練樣本集為F={f1,f2,…,fl}，縮減樣本集Ul={ul,1,ul,2,…,ul,k}。

則最優(yōu)選擇法的具體步驟如下：

步驟2從樣本集Ul中選取同時(shí)滿足|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個(gè)最優(yōu)的訓(xùn)練樣本;否則，從Ul′中選擇到Fl+1和F中所有樣本的距離和最大的樣本為可能最優(yōu)的訓(xùn)練樣本，記為fl,2，加入Fl+1←fl,2，返回步驟2。

步驟4不斷重復(fù)以上步驟直到樣本集Ul′為空集，此時(shí)Fl+1={fl,1,fl,2,…,fl,n}，則fl,n即為第l+1個(gè)最優(yōu)的訓(xùn)練樣本，記為fl+1，則此時(shí)最優(yōu)訓(xùn)練樣本集F={f1,f2,…,fl,fl+1}。

3.4 本文基于SVM和主動(dòng)學(xué)習(xí)的檢索方法

基于以上思路，提出一種新的基于SVM和主動(dòng)學(xué)習(xí)的圖像檢索方法，具體步驟如下：

輸入:查詢圖像Q，圖像數(shù)據(jù)庫DB。

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

步驟1通過計(jì)算Q與未標(biāo)注樣本U之間的距離進(jìn)行相似性排序，輸出一個(gè)結(jié)果集。若用戶滿意該結(jié)果，則算法結(jié)束；否則轉(zhuǎn)到步驟2。

步驟2對(duì)結(jié)果集樣本進(jìn)行標(biāo)注(相關(guān)、不相關(guān))，相關(guān)圖像加入樣本集V+,不相關(guān)圖像加入樣本集V-，訓(xùn)練集為V=V+∪V-。在V上訓(xùn)練SVM分類器，得到分類器h1。利用h1對(duì)未標(biāo)注樣本進(jìn)行分類，得到正、負(fù)類樣本集U+、U-，U-V=U+∪U-。

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

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

步驟5同理，從U-中得到前K/2個(gè)最優(yōu)訓(xùn)練樣本的樣本集F-，則用于用戶標(biāo)注的訓(xùn)練結(jié)果集F=F+∪F-;然后將訓(xùn)練結(jié)果加入訓(xùn)練樣本集V←F，剩余樣本集U←U-V，返回步驟2。

4 實(shí)驗(yàn)及結(jié)果

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

隨機(jī)從每個(gè)類別中選取5幅圖像，總共50幅圖像用于查詢。實(shí)驗(yàn)中以平均查準(zhǔn)率為評(píng)價(jià)標(biāo)準(zhǔn)來反映算法的檢索性能。設(shè)s為查詢結(jié)果中檢索到的所有相關(guān)圖像數(shù)目，u為檢索到的不相關(guān)圖像數(shù)目，則查準(zhǔn)率可以表示為：

(8)

為驗(yàn)證本文圖像檢索方法性能，在VS2010平臺(tái)進(jìn)行實(shí)驗(yàn)，圖3和圖4是在相同檢索條件下經(jīng)過兩次反饋后的圖像檢索結(jié)果，從檢索結(jié)果中可以看到本文算法不僅具有很好的檢索性能，而且獲得的檢索結(jié)果具有更好的序列性。

Figure 3 Retrieval results of traditional method圖3 傳統(tǒng)方法檢索結(jié)果

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

為更好說明本文算法的可靠性，實(shí)驗(yàn)以查準(zhǔn)率為對(duì)比標(biāo)準(zhǔn)，將傳統(tǒng)的基于SVM和主動(dòng)學(xué)習(xí)的圖像檢索方法與本文的方法進(jìn)行了詳細(xì)的對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)對(duì)比結(jié)果如表1和表2及圖5和圖6所示。

Table 1 Retrieval performance of traditional SVM active learning method表1 傳統(tǒng)SVM主動(dòng)學(xué)習(xí)檢索性能 %

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

Figure 5 Average precision rate of Top20圖5 Top20的平均查準(zhǔn)率

Figure 6 Average precision rate of Top40圖6 Top40的平均查準(zhǔn)率

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

5 結(jié)束語

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

[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)

附中文參考文獻(xiàn)：

[1] 吳洪, 盧漢清, 馬頌德. 基于內(nèi)容圖像檢索中相關(guān)訓(xùn)練技術(shù)的回顧[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(12):1969-1979.

[2] 李向陽, 莊越挺, 潘云鶴. 基于內(nèi)容的圖像檢索技術(shù)與系統(tǒng) [J]. 計(jì)算機(jī)研究與發(fā)展, 2001, 38(3):344-352.

[5] 龍軍，殷建平，祝恩，等. 主動(dòng)學(xué)習(xí)研究綜述 [J]. 計(jì)算機(jī)研究與發(fā)展，2008,45(Suppl):300-304.

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

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

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

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