基于譜聚類和多示例學習的圖像檢索方法*

李展彭進業，2溫超

(1.西北大學信息科學與技術學院，陜西西安710069;2.西北工業大學電子信息學院，陜西西安710072)

傳統的基于內容的圖像檢索(CBIR)通過圖像特征度量整體相似性來實現［1］;而基于對象的圖像檢索(OBIR)只關心那些包含特定對象的圖像.由于OBIR更適應用戶檢索需求，因此已成為CBIR新的研究熱點［2］.

針對OBIR，一種方法是以“視覺詞袋”(BoW)模型為基礎，獲取圖像感興趣區域的尺度不變特征變換(SIFT)特征［3］，利用BoW模型進行圖像檢索.Zheng等［4］從文本檢索中得到啟示，提出基于視覺詞組的檢索方法.Philbin等［5］通過獲取局部幾何空間特征提高檢索性能.Wu等［6］利用多樣本多樹方法解決了特征檢測、提取和量化步驟中的信息損失問題.另一種方法基于多示例學習(MIL)框架，利用MIL實現圖像檢索.Dietterich等［7］在藥物活性預測的研究工作中，于1997年首次提出MIL的概念.傳統機器學習框架中訓練樣本與標記是一一對應的，而MIL問題中，訓練樣本包有多個示例，只有包具有標記.若包中有正示例，則標記為正，反之標記為負.如對圖像進行分割，將圖像與分割區域分別看作包和示例，包含有檢索對象的圖像標為正包，否則標為負包.利用已標記正負圖像學習分類器并進行檢索，則基于對象的圖像檢索就變成了多示例學習問題.Zhang和Rouhollah等［8-9］結合多樣性密度(DD)函數和期望最大值算法(EM)，利用EM-DD算法對圖像檢索進行研究.Chen等［10-11］提出了DD-SVM與MILES兩個經典MIL算法，通過構造空間，將多示例包非線性投影并嵌入到構造空間中，利用支持向量機(SVM)求解MIL問題.Wang等［12］受基于圖的半監督學習算法的啟發，提出了GMIL算法，該算法定義包含標記數據、半標記數據和未標記數據的代價函數，并對該代價函數進行迭代優化.Fu等［13］則利用交替迭代方法選擇示例，完成圖像檢索.

要實現高效的對象圖像檢索任務，需解決如下3個主要問題.(1)適合圖像檢索的特征和圖像檢索模型選擇問題;(2)圖像標注復雜度和檢測對象區域問題:要獲得帶有明確標記的訓練樣本和指定檢測對象區域，均依賴人工指定，效率不高;(3)檢索效率問題:檢索系統需實時反應用戶，并返回滿足查詢要求的圖像.基于BoW模型的方法中，SIFT特征獲取和匹配的時間復雜度都非常高，而且需要預先指定檢索對象區域，因此并不是最好的解決方法.本研究以多示例學習模型為基礎，設計了一種新的對象圖像檢索算法SCPMK-MIL(Spectral Clustering and Pyramid Matching Kernel for Muti-Instance Learning).該算法首先在正包示例集合內進行譜聚類(SC)，基于聚類中心點數最大原則選擇潛在正示例代表，將包內其它示例相似性視為多部分相似問題，分別使用徑向基函數(RBF)和金字塔核(PMK)度量相似性，然后利用SVM學習分類器模型并實現圖像檢索;相關反饋技術可以大大提高檢索性能［14］，因此最后進行相關反饋.

1 SCPMK-MIL算法

1.1 潛在正示例代表的選擇

假設要訓練一個針對對象z的MIL分類器，標注圖像集為L={(B1，y1)，(B2，y2)，…，(Bs，ys)}，其中，yi∈{－1，+1}，i=1，2，…，s，這里+1表示圖像中包含對象z，而－1表示不包含對象z.在集合L中，前m個包為正包，標記為yi=+1，后l個包為負包，標記為yi=－1，滿足s=m+l.未標注圖像集為U={Bs+1，Bs+2，…，Bs+p}，其中p為圖像集U中包的個數.設圖像Bi被分割成ni個區域，每個區域對應的視覺特征向量記作x ij∈Rd，d表示視覺特征向量的維數，則稱為MIL訓練包，x ij為包中示例.將yi=+1的包內示例排在一起，稱為正包示例集合，記作

式中，q表示正包中示例的總數

傳統的聚類算法，如k-means算法和EM算法，都是建立在凸球形的樣本空間上.當樣本空間不為凸時，算法會陷入局部最優.而譜聚類能在任意形狀的樣本空間上聚類，且收斂于全局最優解，因此本研究選擇譜聚類NJW算法［15］進行聚類，以獲取潛在正示例代表.

譜聚類算法的思想來源于譜圖劃分理論，假定將L+中每個示例看作圖中的頂點V，根據示例間的相似度將頂點間的邊A賦權重值w，這樣就得到一個基于示例相似度的無向加權圖G=(V，A).那么在圖G中，就可將聚類問題轉化為圖G的劃分問題.為了求解該劃分問題，可將問題轉化為Laplacian矩陣的譜分解，從而實現對圖劃分準則的逼近［16］.

譜聚類算法步驟為:首先根據給定的樣本數據集定義一個描述成對數據點相似度的親合矩陣，并計算拉普拉斯矩陣的特征值和特征向量，然后選擇合適的特征向量進行聚類.

定義1(親合矩陣W)給定集合L+中的任意兩個示例x i、x j，其權重定義為

式中，σ為事先指定參數.

定義2(度矩陣D)度矩陣D為對角陣，其對角元素值為親合矩陣W的行元素之和，其余元素為0.

定義3(規范Laplacian矩陣L)規范Laplacian矩陣定義為

式中I為單位矩陣.

文中采用聚類中心點數最大原則，即對正示例集合L+進行k聚類，計算聚類樣本的中心{o1，o2，…，ok}.統計每個聚類所包含的正示例點數{c1，c2，…，ck}，認為包含點數最多的聚類中心點為潛在正示例中心.選擇包Bi中和該聚類中心距離最近的示例作為包Bi的潛在正示例代表.

定義4(聚類中心O)對正包示例集合L+進行k聚類，獲得k個不相交的子圖Gj，j=1，2，…，k.示范函數I(·)判斷x i是否屬于子圖Gj，定義為

則聚類中心向量O中分量O j可由下式計算:

定義5(潛在正示例中心)統計子圖Gj的正示例點個數，假定點個數最大的子圖為Gh，則O h為潛在正示例中心.定義N(j)為統計子圖Gj的正示例個數函數，C為子圖Gj中所含示例點個數向量.C的分量Cj的計算公式為

若

則O h為潛在正示例中心.

定義6(潛在正示例代表)通過式(7)得到潛在正示例中心O h后，包Bi和O h距離最近的示例x ir稱為潛在正示例代表.其中，

基于以上定義與聚類中心點數最大原則，構造潛在正示例代表集合的算法1的步驟描述如下.

輸出:潛在正示例代表集合γ.

1)以L+為集合，用式(2)計算親合矩陣W.

2)利用公式(3)和(4)分別計算度矩陣D和規范Laplacian矩陣L.

3)計算矩陣L前k個最大特征值所對應的特征向量x1，x2，…，x k，構造矩陣X=［x1x2…x k］.

4)將矩陣X的行向量歸一化，轉變為單位向量，得到矩陣Y，其元素

5)將矩陣Y的每一行看作Rk空間中的一個點，使用k-means算法進行聚類，得到k個不相交的子圖Gj，j=1，2，…，k.

6)利用式(6)和(8)計算聚類中心和潛在正示例中心.

7)對?Bi∈B，利用式(9)計算潛在正示例代表x ir，進行如下操作:

(1)將x ir加入集合γ;

(2)從集合B中刪除Bi.

8)如果B非空，則跳轉本算法步驟7);否則，輸出γ，算法結束.

1.2 SCPMK-MIL核函數的計算

SIFT匹配問題是標準的多部分相似問題.針對SIFT相似問題，相應的核方法得到了廣泛的研究和應用.其中Kristen等［17］提出的金字塔核最為有效;其構造多解析直方圖，在直方圖金字塔基礎上，通過權重組合直方圖重疊值構造核函數.

文獻［17］定義核函數

式中，z1、z2為兩個SIFT特征，Hi(x)為投影的第i級直方圖，ψ(x)=［H0(x)，H1(x)，…，Hl－1(x)］，τ(·，·)為直方圖的重疊值.

由算法1得到正示例代表集合γ={γ1，γ2，…，γs+p}.SCPMK-MIL核函數定義為

式中:krbf為RBF核函數;kpmk為金字塔核函數;α為krbf對核函數K的影響因子，滿足1＞α＞0;集合E和F分別滿足E∪γi=Bi和F∪γj=Bj.

SCPMK-MIL核矩陣K元素Kij的計算方法為:利用算法1，獲取包集合B=L∪U的潛在正示例集合γ，對MIL中的包Bi和Bj分別去掉潛在正示例代表γi和γj，生成新集合E和F.利用公式(11)計算核矩陣K.構造核矩陣K和其元素Kij的算法2的具體步驟如下.

輸入:潛在正示例代表集合γ，集合B=L∪U，正比例系數α.

輸出:核矩陣K.

1)任取B中的兩個包Bi和Bj，令E=Bi－{γi}，F=Bj－{γj};

2)利用式(11)計算K(Bi，Bj)，并賦值給Kij;

3)如果未遍歷完B中所有包，則跳轉本算法步驟2);否則輸出K，算法結束.

1.3 SVM分類及相關反饋

SVM利用最大化margin思想，尋找保證正確分類情況下的最大間隔.其優化目標為

式中:{xi，yi}為訓練樣本(i=1，2，…，t)，t為訓練樣本總數;ω為分類面法向量;ξi為松弛變量;φ(·)為由低維到高維的映射函數;b為偏移量，b∈R;λ為懲罰因子，如λ=∞則為線性可分情況，否則為線性不可分情況.

利用拉格朗日和Wolfe對偶理論，優化問題變形為

式中，βi為拉格朗日乘子，此處核函數K用算法2計算.

式中:{x i，yi}∈L，x∈U.

基于SVM的相關反饋方法是一個交互式檢索過程.本研究在反饋時，用戶每次從檢索結果中標記正例和反例，以增加訓練圖像數，從而不斷調整在希爾伯特空間中的SVM超平面，直至達到反饋次數要求.

最后將本研究提出的SCPMK-MIL對象圖像檢索(算法3)步驟總結如下.

輸入:已標注圖像集L、測試圖像集U(即未標注圖像集)、k和α，反饋次數n，用戶反饋正負圖像個數h+和h－.

輸出:測試圖像集U的標記

1)構造MIL訓練包:對?Bi∈B，B=L∪U進行圖像分割，若分割為ni個區域，則相應的MIL訓練包記為，其中x ij∈Rd，表示相應的圖像特征(即包中示例).

6)用戶從集合R中選擇h+個圖像作為正例集合Z+，從集合S=U－R中選擇h－個圖像作為負例集合Z－，從而生成反饋訓練集Z=Z++Z－.

7)將反饋所得正負集合加入已標注圖像集L，令L=L∪Z，測試圖像集U=U－Z.若反饋次數未達到n次，則轉本算法步驟2);否則算法結束.

2 實驗結果與分析

2.1 圖像庫及實驗方法

選用SIVAL圖像集進行對比實驗(http:∥www.cs.wustl.edu/accio/)，該圖像集由1 500幅圖像組成，包含25類不同物體，每類60幅圖像.實驗中每幅圖像被預先分割成約30個不同區域，在每個區域提取其30維的顏色、紋理和近鄰的底層視覺特征，細節請參閱文獻［9］.實驗平臺為:AMD4200+處理器，1GDDR800內存，Windows XP操作系統，以及Matlab7.01仿真環境.

SVM的代碼來自LibSVM軟件包(http:∥www.csie.ntu.edu.tw/～cjlin/libsvm/)，采用“one-vsrest”處理多類問題，具體方法是:在每次實驗中，從每類圖像中隨機選取20幅作為潛在訓練集正例，其余1000幅作為待檢索圖像;每次實驗時，將某一類作為檢索目標，從該類的潛在訓練集正例中隨機選擇6幅生成正訓練包，再從其它類中隨機選擇6類，每類隨機選擇1幅不感興趣的圖像，生成負包，組成包含6個正包和6個負包的訓練集.金字塔核的代碼來自Grauman的主頁(http:∥www.cs.utexas.edu/～grauman/).算法2中RBF和PMK參數采用“2-fold交叉檢驗”的方法獲取.因為AUC值(即ROC曲線下的面積)能夠刻畫檢索結果排序的優劣，本研究采用它來評估算法的性能.

2.2 參數k和α對算法性能的影響

SCPMK-MIL算法中，譜聚類的聚類數k及核函數中的正比例系數α必須預先設置.為了驗證k和α對檢索精度的影響，設置k從1變化到9，步長為1;α從0.1變化到0.9，步長為0.1.基于GreenTeaBox類圖像，按照1.3節所述算法3進行實驗.圖1(a)為α=0.2時k對平均AUC值的影響.圖1(b)為k=5時，α對平均AUC值的影響.

圖1 在圖像GreenTeaBox上k和α對SCPMK-MIL算法性能的影響Fig.1 Effects of k andαon the performance of SCPMK-MIL algothrim for GreenTeaBox

如圖1(a)所示，當k從1增至9時，AUC值介于0.768到0.869之間，k=5時AUC值達到最大值0.869.由此可見，SCPMK-MIL算法的性能受k的影響較大.其主要原因是:在對象圖像檢索中，對象經常和幾個特定的其它物體具有特定的共生關系.圖2為GreenTeaBox的部分圖像，由圖可見GreenTea-Box通常和板凳、報紙、桌子、地面出現在同一幅圖像中.那么，在進行k=5聚類時，潛在正示例中心必然是GreenTeaBox對象特征的中心，因此利用k=5聚類獲取的潛在正示例代表進行檢索是可行的.如圖1(b)所示，當α從0.1增至0.9時，AUC值介于0.839到0.880之間，α=0.3時，達到最大值0.880，其波動在4.1%以內.可見在選擇合適的參數情況下，SCPMK-MIL算法具有很強的魯棒性.在α＜0.4的情況下，α值對SCPMK-MIL分類精度的影響較小，AUC值的變化在2.2%以內，這和筆者對MIL問題的理解是吻合的.MIL的核心問題在于正示例的不確定性，如果包內潛在正示例代表得到確認，則包正負性主要由正示例是否出現決定，其它的包內數據應只起輔助作用.也就是說在潛在正示例和其它示例信息可同時獲取的情況下，潛在正示例對包標記的影響大于包內其它示例的影響.在下面的實驗中，固定k=5，α=0.3.

圖2 部分GreenTeaBox圖像Fig.2 Some images of GreenTeaBox

2.3 對比實驗及分析

為了表示方便，下面的實驗結果中標號1到25分別代表SIVAL圖像集中的“FabricSoftenerBox”、“CheckeredScarf”、“FeltFlowerRug”、“CokeCan”、“WD40Can”、“AjaxOrange”、“DirtyRunningShoe”、“CandleWithHolder”、“GoldMedal”、“GreenTeaBox”、“CardboardBox”、“SpriteCan”、“SmileyFaceDoll”、“DirtyWorkGloves”、“StripedNoteBook”、“DataMiningBook”、“BlueScrunge”、“TranslucentBowl”、“RapBook”、“Apple”、“GlazedWoodPot”、“WoodRollingPin”、“JuliesPot”、“Banana”、“LargeSpoon”.首先比較相關反饋對搜索性能的影響，實驗使用6幅感興趣和6幅不感興趣的圖像進行初始檢索;為了保持正負類的均衡，在檢索結果中增加6幅感興趣和6幅不感興趣的圖像，進行一次相關反饋的檢索.比較結果如圖3所示.從圖3可以看出，使用相關反饋可以大大提高檢索的性能，24幅(12個正包和12個負包)的相關反饋方法獲取的AUC值比12幅(6個正包和6個負包)的AUC值提高了8%左右.其主要原因在于:在檢索完成后，通過相關反饋增大有效訓練集，提高了SVM分類器的精度和圖像檢索性能.

圖3 相關反饋對圖像檢索性能的影響Fig.3 Effect of relevant feedback on image retrieval

為了進一步驗證SCPMK-MIL算法的性能(設置k=5和α=0.3)，按照2.1節所述的實驗方法，將SCPMK-MIL和MILES［11］，ACCIO!［9］算法進行對比實驗，每個試驗重復30次，平均AUC值見表1，試驗采用一次相關反饋算法(增加12個正包和12個負包，形成24幅訓練包).為了驗證SCPMK-MIL算法的有效性，將其與半監督GMIL算法［12］進行了對比實驗，這里選擇的相關反饋圖像數等于已標注圖像數，隨著已標注的圖像數量的增加，30次隨機重復實驗的平均AUC值變化曲線如圖4所示(已標注圖像確保一半為正一半為負).

從表1可以看出，SCPMK-MIL算法總體上來說優于MILES和ACCIO!算法，主要原因是:(1)文中設計的譜聚類方法可以很好地獲取潛在正示例中心，辨別包內潛在正示例代表和其它示例;(2)融合RBF和PMK進行相似性計算可以平衡包內各示例對核相似性的影響，具有很強的可靠性與魯棒性;(3)利用相關反饋技術，通過用戶主動參與檢索評價，可以獲得較好的檢索性能.而MILES算法則是將每個包投影到示例構成的空間，利用新生成投影向量比較相似性，其性能很大程度上受包中示例空間分布的影響，因此在示例空間分布不理想的情況下，其性能表現不佳.ACCIO!算法是一種基于DD的算法，存在優化解陷入局部極值問題，因此最終分類結果也不精確.

表1 圖像集SIVAL上置信度為0.95的30次重復實驗平均AUC值Table 1 Average AUC values with the 95%-confidence intervals over 30 independent runs on SIVAL dataset

圖4 圖像集SIVAL上GMIL和SCPMK-MIL算法的性能對比Fig.4 Performance comparison between GMIL and SCPMKMIL algorithms for SIVAL dataset

3 結語

文中基于譜聚類和金字塔核，提出了一種新的MIL算法，稱為SCPMK-MIL算法，在MIL框架下實現對象圖像檢索.其優勢在于:(1)利用譜聚類方法在正示例空間聚類，獲取潛在正示例代表，從而可定位圖像中的潛在對象位置;(2)利用RBF和PMK度量潛在正示例代表和其它示例相似性，通過正比例系數平衡兩者相似性的影響，從而提高MIL算法的準確度;(3)利用相關反饋方法提高圖像檢索的性能，從而提高檢索用戶滿意度;(4)利用MIL訓練包的性質，用戶只需要對整個圖像給定標記，而不必對具體區域進行標注，簡化了訓練樣本的手工標注.基于SIVAL圖像庫的對比實驗結果表明，文中提出的方法是有效的.

［1］陳星星，張榮.基于多尺度相位特征的圖像檢索方法［J］.電子與信息學報，2009，31(5):1193-1196.Chen Xing-xing，Zhang Rong.A multi-scale phase feature based method for image retrieval［J］.Journal of Electronics＆Information Technology，2009，31(5):1193-1196.

［2］Datta R，Joshi D，Li J，et al.Image retrieval:ideas，influences，and trends of the new age［J］.ACM Computing Surveys，2008，40(2):1-65.

［3］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.

［4］Zheng Qing-fang，WangWei-qiang，GaoWen.Effective and efficient object-based image retrieval using visual phrases［C］∥Proceedings of the 14th ACM International Conference on Multimedia.Santa Barbara:ACM，2006:77-80.

［5］Philbin James，Chum Ondrej.Object retrieval with large vocabularies and fast spatialmatching［C］∥Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Minnesota:IEEE，2007:1-8.

［6］Wu Zhong，Ke Qi-fa.A multi-sample，multi-tree approach to bag-of-words image representation for image retrieval［C］∥Proceedings of 12th International Conference on Computer Vision.Kyoto:IEEE，2009:1992-1999.

［7］Dietterich TG，Lathrop R H，Lozano-Pérez T.Solving the multiple instance problem with axis-parallel rectangles［J］.Artificial Intelligence，1997，89(12):31-71.

［8］Zhang Qi，Sally A Goldman.Content-based image retrieval usingmultiple-instance learning［C］∥Proceedings of the 19th International Conference on Machine Learning.Sydney:IMLS，2002:682-689.

［9］Rouhollah Rahmani，Sally A Goldman.Localized contentbased image retrieval［C］∥Proceedings of the 7th ACM SIGMM International Workshop on Multimedia Information Retrieval.Singapore:ACM，2005:227-236.

［10］Chen Yi-xin，James Z Wang.Image categorization by learning and reasoning with regions［J］.Journal of Machine Learning Research，2004，5(8):913-939.

［11］Chen Yi-xin，Bi Jin-bo，JamesWang Z.MILES:multipleinstance learning via embedded instance selection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(12):1931-1947.

［12］Wang Chang-hu，Zhang Lei，Zhang Hong-jiang.Graph based multiple-instance learning for object-based image retrieval［C］∥Proceeding of the 1st ACM International Conference on Multimedia Information Retrieval.Vancouver:ACM，2008:156-163.

［13］Fu Zhou-yu，Antonio Robles-Kelly.An instance selection approach to multiple instance learning［C］∥Proceedings of the IEEEComputer Society Conference on Computer Vision and Pattern Recognition.Miami:IEEE，2009:911-918.

［14］羅斌，鄭愛華，湯進.基于模糊多類SVM的圖像檢索相關反饋［J］.華南理工大學學報:自然科學版，2008，36(9):107-112.Luo Bin，Zheng Ai-hua，Tang Jin.Relevance feedback of image retrieval based on multicalss fuzzy support vector machines［J］.Journal of South China University of Technology:Natural Science Edition，2008，36(9):107-112.

［15］Ng A Y，Jordan M I，Weiss Y.On spectral clustering:analysis and an algorithm［C］∥Proceedings in 14th Advances in Neural Information Processing Systems.Vancouver:NIPS，2001:849-856.

［16］Zhou D，BousquetO.Learning with local and global consistency［C］∥Proceedings in 16th Advances in Neural Information Processing Systems.Vancouver:NIPS，2004:321-328.

［17］Kristen Grauman，Trevor Darrell.The pyramid match kernel:efficient learning with sets of features［J］.Journal of Machine Learning Research，2007，8(5):725-760.