基于Nystr?m譜聚類的詞典學習

王鑫，李璐，王曉芳

1.安徽建筑大學數(shù)理系，合肥 230601

2.解放軍陸軍軍官學院計算機教研室，合肥 230031

基于Nystr?m譜聚類的詞典學習

王鑫1，李璐1，王曉芳2

1.安徽建筑大學數(shù)理系，合肥 230601

2.解放軍陸軍軍官學院計算機教研室，合肥 230031

構(gòu)建視覺詞典是BOVW模型中關(guān)鍵的一個步驟，目前大多數(shù)視覺詞典是基于K-means聚類方式構(gòu)建。然而由于K-means聚類的局限性以及樣本空間結(jié)構(gòu)的復(fù)雜性與高維性，這種方式構(gòu)建的視覺詞典往往區(qū)分性能較差。在譜聚類的框架下，提出一種區(qū)分性能更強的視覺詞典學習算法，為了減少特征在量化過程中區(qū)分性能的降低以及譜聚類固有的存儲計算問題，算法根據(jù)訓練樣本的類別標簽對訓練數(shù)據(jù)進行劃分，基于Nystr?m譜聚類得到各子樣本數(shù)據(jù)集的中心并得到最終的視覺詞典。在Scene-15數(shù)據(jù)集上的實驗結(jié)果驗證了算法的正確性和有效性。特別當訓練樣本有限時，采用該算法生成的視覺詞典性能較優(yōu)。

圖像分類；視覺詞袋模型；視覺詞典；譜聚類

近年來，視覺詞袋模型（BOVW）技術(shù)廣泛地應(yīng)用于計算機視覺特別是圖像分類、圖像檢索、目標檢測等領(lǐng)域，并取得很大的成功。BOVW的思想來源于詞袋模型。詞袋模型（BOW）源于自然語言處理領(lǐng)域，通過統(tǒng)計每個文檔中詞項出現(xiàn)的頻率，將文檔表示為稀疏的詞項向量，其中每一個元素為字典中的單詞，其值表示該詞項在文檔中出現(xiàn)的頻率，進而文檔可以被描述為詞項的歸一化直方圖。

BOVW借鑒了上述思想，用一組無序的圖像局部特征集合來表示圖像，這種方法計算量小并且易于理解，在計算機視覺領(lǐng)域中受到越來越多的關(guān)注。BOVW通過視覺詞典將圖像底層局部特征表示為直方圖空間中具有固定長度的特征向量，其中視覺詞典的區(qū)分性能決定著模型的質(zhì)量，視覺詞典的大小決定著模型的復(fù)雜度。由此可見，在BOVW中視覺詞典的構(gòu)建具有重要的意義，影響著圖像最終的分類與識別性能。在理想情況下，希望BOVW模型中的視覺單詞與自然語言中的詞項一樣具有明確的語義信息，但實際情況并非如此，并且視覺詞典的性能受到諸如特征提取方式、聚類方法、視覺詞典大小以及距離測度等多方面的影響。

從本質(zhì)上講，視覺詞典的構(gòu)建其實是對特征空間的一種劃分，將同一子空間中的特征用一個或多個視覺單詞表示。目前，視覺詞典的構(gòu)建主要有如下兩種方式：第一，基于標注的方法；第二，基于數(shù)據(jù)驅(qū)動的方法。第一種方法中，圖像分割和圖像區(qū)域標注等監(jiān)督學習算法被引入其中，通過對劃分的圖像塊賦予有意的標簽如天空、水、植物等構(gòu)建詞典，這方法工作量大、主觀性強，限制了其在實際中的應(yīng)用。第二種方法目前被廣泛應(yīng)用，多種非監(jiān)督聚類算法被應(yīng)用于構(gòu)建視覺詞典，其中使用最頻繁的是K-means算法[1-3]，mean-shift[4]，層次K-means[5]及Gaussian Mixture Models[6]（GMM）等。K-means聚類算法簡單，但是其有自身的局限性：（1）對于初始聚類中心敏感。對于小規(guī)模視覺詞典的構(gòu)建，可以設(shè)置不同的聚類中心多次運行尋找最佳聚類中心，但是對于大規(guī)模視覺詞典的構(gòu)建，反復(fù)多次運行K-means算法極為浪費時間。（2）K-means算法本身存在樣本需要服從高斯分布的隱形假設(shè)，很少考慮樣本數(shù)據(jù)的真實分布情況。當圖像具有同質(zhì)結(jié)構(gòu)特性時如紋理圖像，特征空間趨于高斯分布，采用K-means聚類方式生成的視覺詞典具有很好的區(qū)分性能。但對于自然場景圖像以及結(jié)構(gòu)更加復(fù)雜的真實圖像，采用這種方式生成的視覺詞典性能較差。（3）K-means聚類具有密度敏感性。特征的空間分布表現(xiàn)出一定的長尾特性，大量低區(qū)分性能的特征出現(xiàn)頻率較高，而少量高區(qū)分性能的頻率出現(xiàn)頻率較低，特別是在圖像分類與場景識別領(lǐng)域中，高頻率的特征往往表現(xiàn)為圖像的一般性結(jié)構(gòu)信息如邊緣、背景以及噪聲信息等，而具有較強區(qū)分性能的特征由于出現(xiàn)頻率較低而無法生成聚類中心，因此高區(qū)分性能的特征存在較大的量化誤差，帶來了信息的損失。從而導(dǎo)致視覺詞典區(qū)分性能的下降。

Yang，L[7]通過分類器訓練學習區(qū)分性能強的視覺詞典并用于物體識別；Moosmann基于Random Forest提出一種ERC-Forest[8]。Wang L[9]首先根據(jù)層次聚類構(gòu)建大規(guī)模視覺詞典，然后采用特征選擇的方式構(gòu)建規(guī)模適度、區(qū)分性能更強的視覺詞典。R.J.Lopez[10]根據(jù)最大化聚類精度和自適應(yīng)優(yōu)化準則構(gòu)建視覺詞典。Yadong Mu[11]基于Locality Sensitive Hashing和Random Forest思想提出一種Random Locality Sensitive Vocabulary（RLSV）的詞典構(gòu)建算法，算法不以聚類為基礎(chǔ)，而是通過隨機投影的方式生成多個視覺詞典并加以融合，實驗驗證了算法的有效性。雖然上述各方法均取得了不錯的效果，但在基于學習過程的分類方法中很少考慮到如何減少量化誤差以及樣本數(shù)據(jù)特性對圖像分類與識別的影響。在大規(guī)模圖像分類與識別中，圖像數(shù)據(jù)主要表現(xiàn)出兩個方面的特性：一是樣本數(shù)目越來越多，空間結(jié)構(gòu)越來越復(fù)雜；二是圖像局部特征描述子的維數(shù)越來越高，在特征空間中的分布極不均勻并具有流形結(jié)構(gòu)特性。在低維空間具有良好性能的聚類算法如K-means或GMM等都是建立在凸樣本空間上，當樣本空間不為凸時，算法會陷入局部最優(yōu)解，無法反映數(shù)據(jù)的全局一致性，因此基于傳統(tǒng)方法在高維特征空間聚類生成的視覺詞典并不能反映特征的真實分布情況，性能較差。

為了解決視覺詞典構(gòu)建過程的上述問題，提出一種基于譜聚類構(gòu)建視覺詞典的算法。譜聚類僅與樣本數(shù)據(jù)點的數(shù)目有關(guān)，而與維數(shù)無關(guān)，因此避免了高維特征向量造成的奇異性問題，并且能在任意形狀的樣本空間中收斂于全局最優(yōu)解。在研究相關(guān)算法的基礎(chǔ)上，本文提出一種基于Nystr?m譜聚類的詞典學習算法，算法充分利用譜聚類在高維、任意形狀特征空間中聚類的優(yōu)點，避免了高維特征向量造成的奇異性以及傳統(tǒng)聚類算法的不穩(wěn)定性。為了充分利用各類別的先驗信息并且減少長尾特性帶來的影響以及解決譜聚類中的存儲計算問題，算法根據(jù)樣本的類別標簽對圖像特征空間進行劃分，在各類子空間中分別生成聚類中心，一定程度上減小了量化過程帶來的誤差并且增加了詞典的語義信息。并且在各類子空間譜聚類的過程中使用Nystr?m低秩矩陣近似進一步減小了算法中的存儲以及計算問題，最后生成區(qū)別性能更強、規(guī)模更加緊湊的視覺詞典。

1 BOVW模型

BOVW模型在圖像分類、場景識別等領(lǐng)域取得了一定的成功，Sivic.J[12]首次提出BOVW模型的概念并成功用于視頻檢索。Fei-Fei等[13]在BOVW模型的基礎(chǔ)上利用LDA模型和PLSA模型完成圖像的場景分類。Lazebnik等[14]提出一種空間金字塔匹配方法用于自然圖像的分類與識別，算法在BOVW模型的基礎(chǔ)上包含了圖像的幾何空間信息。BOVW模型用于圖像分類與識別主要包括以下步驟：特征提取，構(gòu)建視覺詞典，特征編碼及分類器設(shè)計。（1）特征提取。Mikolajczyk和Schmid[15]對常見的幾種圖像局部特征進行了實驗對比，驗證了SIFT特征相比于其他局部特征具有較好的光照、旋轉(zhuǎn)、尺度以及仿射不變性，取得最好的實驗性能。（2）構(gòu)建視覺詞典。通過對訓練集圖像中的SIFT特征進行聚類生成視覺詞典，其中每一個聚類中心稱為一個視覺單詞。（3）特征編碼。對每幅圖像中提取的每一個特征，將其賦值于視覺詞典中最近的一個或者多個視覺單詞。（4）分類器設(shè)計。將歸一化后的表示目標圖像的特征向量用于訓練分類器，根據(jù)生成的訓練器在測試圖像中進行分類與識別。

2 譜聚類

為了能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解，學者提出譜聚類算法。譜聚類算法的思想來源于譜圖劃分理論，將聚類問題看成一個無向圖的多路劃分問題，定義一個圖劃分判據(jù)，如Shi和Malik[16]提出的一個有效的圖劃分判據(jù)---規(guī)范切判據(jù)，最優(yōu)化這一判據(jù)，使得同一類內(nèi)的點具有較高的相似性，不同類的點具有較低的相似性。由于圖劃分問題的組合本質(zhì)，求圖劃分判據(jù)最優(yōu)解是一個NP難題，一個行之有效的方法是考慮問題的連續(xù)放松形式，這樣便可將原問題轉(zhuǎn)換成求圖的Laplacian矩陣譜分解問題，這類方法統(tǒng)稱為譜聚類。

對于給定的樣本點x1，x2，…，xn，譜聚類算法計算樣本點間相似性矩陣S=[sij]∈Rn×n，其中sij≥0表示樣本點xi和xj之間的相似度，再根據(jù)相似信息將樣本點劃分為k個簇。代表算法有Ng等提出的基于規(guī)范化拉普拉斯矩陣的譜聚類（標準譜聚類算法），算法步驟如下：首先計算相似矩陣S及其標準拉普拉斯矩陣L。

D為度矩陣，對角線元素取值如式（3），非對角線上的元素取值為0。然后計算矩陣L的k個尾特征向量V= (v1，v2，…，vn)，將V的每一行看成一個樣本數(shù)據(jù)點使用K-means得到聚類結(jié)果。

譜聚類直接分析樣本數(shù)據(jù)點間的相似矩陣來達到聚類的目的，但是計算與存儲數(shù)據(jù)點之間的相似度矩陣及前k個Laplacian矩陣特征值對應(yīng)的特征向量，阻礙了其在大規(guī)模數(shù)據(jù)中的應(yīng)用。緩解這種問題一個有效的方法是利用Nystr?m方法進行低秩矩陣近似[17]。

3 基于Nystr?m譜聚類構(gòu)建視覺詞典

Williams[18]將Nystr?m方法應(yīng)用于核矩陣加速運算。Fowlkes[19]等在譜聚類中使用Nystr?m近似算法來避免計算整個相似矩陣并應(yīng)用于圖像分割中，Nystr?m方法每次從核矩陣中選擇m列，然后利用被選列和剩余列之間的關(guān)系構(gòu)造整個矩陣的低秩近似。本文首先根據(jù)訓練樣本的類別信息對訓練樣本集進行劃分得到樣本子集合C1…Cn，然后對各樣本子集Ci基于Nystr?m方法進行譜聚類，分別得到每個樣本集合的若干聚類中心V1…Vn，最后由聚類中心構(gòu)造樣本空間并采用譜聚類生成最終的視覺詞典。

對A進行特征分解，A=VAΣAVTA，ΣA包含A的特征值，VA為矩陣A特征值對應(yīng)的特征向量?；贜ystr?m方法，矩陣Sd有如下近似低秩分解：

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

本實驗采用圖像分類與識別領(lǐng)域中最常用的標準數(shù)據(jù)集Scene-15，采用文獻[13]中的方式提取每幅圖像的特征，以8像素為步長，在16×16大小的像素塊內(nèi)提取稠密SIFT特征。為了包含圖像的空間信息，采用空間金字塔匹配核，空間金字塔總層數(shù)為3，大小分別為1×1，2×2，4×4。如果沒有特別說明，采用文獻[21]所提出的局部受限軟賦值編碼方式。采用圖像分類通用的方法從圖像集中隨機選取10組訓練圖像集和測試圖像集，每次實驗的結(jié)果是數(shù)據(jù)集中所有類別圖像分類正確率的平均值。采用一對多的方式構(gòu)造多類分類器，采用直方圖交作為SVM分類器的核函數(shù)。

在Nystr?m譜聚類構(gòu)建視覺詞典的過程中，隨機采樣數(shù)目l和尺度參數(shù)δ具有重要的意義，其中l(wèi)決定了特征分解的時間復(fù)雜度，很大程度上影響著算法的時間復(fù)雜度。而δ在構(gòu)建相似度矩陣時具有重要的意義，很大程度上決定了譜聚類的質(zhì)量，影響著視覺詞典的性能。為了驗證l和δ對分類性能的影響，實驗中分別取l為1 000，1 500，2 000，2 500，3 000，4 000，δ取20，30，40和50（最終視覺詞典的大小為500、訓練樣本個數(shù)為30），實驗結(jié)果如圖1所示。

圖1 不同采樣數(shù)目和尺度參數(shù)對詞典性能的影響

從圖1中可以看出當δ取30的時候，對于不同大小的采樣數(shù)目實驗均取得了不錯的識別正確率；當δ取50時，其對應(yīng)的圖像分類正確率幾乎都是最低。從圖中還可以看出當l足夠大時，圖像分類正確率趨于穩(wěn)定，并且隨著采樣數(shù)目l的增加，圖像分類正確率有所降低。為了取得最優(yōu)的分類識別效果，后續(xù)實驗中l(wèi)取2 500，δ取30。

以上實驗驗證了基于Nystr?m譜聚類算法的有效性以及將該方法引入視覺詞典構(gòu)建的可行性。在BOVW模型中，大多數(shù)視覺詞典是基于K-means聚類方式構(gòu)建。本章分別基于K-means聚類算法和本文算法構(gòu)建視覺詞典并從不同方面比較詞典對識別性能的影響。

首先分析不同訓練樣本數(shù)目構(gòu)建視覺詞典對分類性能的影響。從Scene-15每類場景圖像中分別隨機選擇10，20，30，40，50，60張圖像作為訓練樣本，剩余的全部作為測試樣本，實驗比較結(jié)果如圖2所示。實驗結(jié)果表明，圖像識別正確率隨著訓練樣本數(shù)目逐漸增加并且當訓練樣本數(shù)目一定的時候，基于本文算法構(gòu)建的視覺詞典從識別正確率上完勝基于K-means算法。特別是當訓練樣本不足時（小于40），基于譜聚類生成的視覺單詞區(qū)分性能較強，識別正確率遠高于K-means算法。當訓練樣本數(shù)目為30時，采用本文算法圖像識別正確率達到（72.81%），高于訓練樣本數(shù)目為50、采用K-means算法構(gòu)建詞典的圖像識別正確率。

圖2 不同訓練樣本數(shù)目對詞典性能的影響

圖3反映了不同大小視覺詞典對圖像識別正確率的影響。當視覺詞典的長度過小時（K=200），采用兩種方法構(gòu)建視覺詞典所獲得圖像識別正確率均是最低，而視覺詞典的長度比較大時（K=1 500），所獲得圖像分類正確率幾乎都是最高，不難看出隨著視覺詞典長度的增加，圖像的識別正確率都有所增加。但對基于K-means方式構(gòu)建的視覺詞典，當詞典的大小從1 000增加到1 500時，圖像分類正確率幾乎沒有變化，可以認為在此過程中沒有生成更具區(qū)分性能的視覺單詞，僅僅增加了算法的復(fù)雜性；而采用譜聚類算法時，由于最終的特征空間是由各圖像類的特征空間均勻構(gòu)成，當詞典的大小同樣從1 000增加到1 500時，圖像分類正確率仍然有所增加。從圖中可以看出，采用譜聚類構(gòu)建視覺詞典時，其尺度為500所獲得的圖像識別正確率已經(jīng)稍勝于尺度大小為800、基于K-means算法所構(gòu)建的視覺詞典。

圖3 不同視覺詞典大小對識別性能的影響

圖4 不同算法的分類混淆矩陣

在基于BOVW模型中，構(gòu)建視覺詞典的指導(dǎo)原則之一就是其長度大小。當視覺詞典過小時視覺詞典的區(qū)分性能過低，不同的語義特征可能標記為相同的視覺單詞；當視覺詞典過大時，一方面所生成的視覺詞典對噪聲比較敏感，降低了圖像分類與識別的性能，另一方面所生成特征向量的高維性會引起“維度災(zāi)難”等相關(guān)問題，增加了算法的復(fù)雜性。從圖可以看出，當基于譜聚類構(gòu)建視覺詞典時，當其大小取500時便可獲得相對不錯的分類性能，后續(xù)實驗中取K=500。

圖2和圖3給出的是平均識別正確率，這種方式?jīng)]有給出各子類具體的識別情況。為了給出不同類別的識別正確率，采用分類混淆矩陣進行衡量。其分類混淆矩陣如圖4（a）、（b）所示，其中（a）表示采用本文方法構(gòu)建視覺詞典的分類結(jié)果，（b）表示采用傳統(tǒng)K-means聚類構(gòu)建視覺詞典的分類結(jié)果。圖中X軸表示圖像類別信息，Y軸表示測試圖像經(jīng)過分類器預(yù)測之后的類別，第i行j列的值表示第i類圖像被分類為第j類圖像的數(shù)目，因此混淆矩陣對角線上的值表示每類場景的分類準確率，圖中背景顏色越深，分類正確率越高。從圖4（a）中可以看出，在15個類別中有7個類別的識別正確率超過了85%，識別正確率最高的類別為MITforest（94.4%），識別正確率最低的類別為bedroom（50.2%），而在圖4（b）中，僅有5個類別的識別正確率超過85%，識別正確率最高的類別為MITforest（92.3%），分類正確率最低的類別為kitchen（48.6%）。圖4（b）中分類正確率最低的4個類別分別是kitchen（48.6%）、bedroom（51.3%）、industrial（52.4%）以及MITopencountry（55.8%）。這些場景錯分率比較高，主要原因是沒有考慮到類別的信息以及K-means聚類算法的局限性，生成的視覺詞典相對于某些類別具有較弱的區(qū)分性能。而在譜聚類構(gòu)建視覺詞典中，除了bedroom類別，其他3類的分類正確率均有所提高，分類正確率分別為kitchen（49.3%），industrial（54.1%），MITopencountry（56.7%）。

為了進一步驗證基于本文算法構(gòu)建視覺詞典的有效性，本文在不同視覺詞典構(gòu)建方法與特征編碼方法的情況下比較圖像分類與識別的正確率，其中訓練樣本個數(shù)均為30，視覺詞典大小均為500。為了表示方便，采用本文算法生成的視覺詞典記為SCV，傳統(tǒng)K-means方法生成的視覺詞典記為KMV。編碼方式分別為硬賦值（Hard-C），軟賦值[22]（Soft-C），稀疏編碼[23]（SC），局部受限軟賦值（LSC）以及LLC[24]，實驗結(jié)果如圖5所示。

圖5 不同算法在Scene-15圖像集上的分類性能比較

由實驗結(jié)果可知，在Scene-15場景圖像識別中對于相同的編碼方式結(jié)合本文方法構(gòu)建的視覺詞典均取得了較高的分類正確率并且具有較好的穩(wěn)定性。與文獻[22-23]相比，本文算法既考慮了圖像的底層特征信息，又考慮了各類類別信息，特別是考慮到實際樣本特征空間的非凸性與復(fù)雜性，因而可以更好地實現(xiàn)圖像場景建模，構(gòu)建區(qū)分性能更高、更具穩(wěn)定性的視覺詞典。

5 結(jié)論

在BOVW模型中，視覺詞典的構(gòu)建一般采用K-means等聚類方法，考慮到實際樣本空間的結(jié)構(gòu)復(fù)雜性與高維性，本文嘗試采用譜聚類算法構(gòu)建視覺詞典。為了減小量化誤差并緩解譜聚類在實際應(yīng)用中的瓶頸問題——相似矩陣的存儲以及矩陣特征分解，本文首先根據(jù)樣本的類別信息對數(shù)據(jù)樣本空間進行分割，然后對于得到的各子空間分別采用Nystr?m低秩矩陣近似的方法進行譜聚類。Scene-15場景分類實驗驗證了本文所提算法的有效性和魯棒性，從大量實驗中發(fā)現(xiàn)當訓練樣本有限時，采用本算法構(gòu)建視覺詞典用于圖像分類與識別可以取得不錯的正確率。然而本文算法仍存在不足之處，為了將譜聚類算法用于視覺詞典的構(gòu)建中，需要對樣本空間進行兩次譜聚類或者特征選擇才能生成最終的視覺詞典，當樣本規(guī)模比較大時，算法具有比較高的時間復(fù)雜度和空間復(fù)雜度。因此，本文下一步的主要工作是解決譜聚類在構(gòu)建視覺詞典時的時間復(fù)雜度和空間復(fù)雜度問題，并將其應(yīng)用于大規(guī)模的圖像分類與識別任務(wù)中。

[1]Csurka G，Dance C，F(xiàn)an L，et al.Visual categorization with bags of keypoints[C]//Workshop on Statistical Learning in Computer Vision，ECCV，2004：1-22.

[2]Li T，Mei T，Kweon I S.Learning optimal compact codebook for efficient object categorization[C]//IEEE Workshop on Applications of Computer Vision，WACV 2008，2008：1-6.

[3]Winn J，Criminisi A，Minka T.Object categorization by learned universal visual dictionary[C]//Tenth IEEE International Conference on Computer Vision，ICCV 2005，2005：1800-1807.

[4]Jurie F，Triggs B.Creating efficient codebooks for visual recognition[C]//Tenth IEEE International Conference on Computer Vision，ICCV 2005，2005：604-610.

[5]Nister D，Stewenius H.Scalable recognition with a vocabulary tree[C]//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006：2161-2168.

[6]Dorko G，Schmid C，Lear P.Object class recognition using discriminative local features，technical report RR-5497[R]. 2005.

[7]Yang L，Jin R，Sukthankar R，et al.Unifying discriminative visual codebook generation with classifier training for object category recognition[C]//IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2008，2008：1-8.

[8]Moosmann F，Nowak E，Jurie F.Randomized clustering forests for image classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（9）：1632-1646.

[9]Wang L.Toward a discriminative codebook：codeword selection across muti-resolution[C]//IEEE Conference on Computer Vision and Pattern Recognition，CVPR’07，2007：1-8.

[10]López-Sastre R J，Tuytelaars T，Acevedo-Rodríguez F J，et al.Towards a more discriminative and semantic visual vocabulary[J].Computer Vision and Image Understanding，2011，115（3）：415-425.

[11]Mu Y，Sun J，Han T X，et al.Randomized locality sensitive vocabularies for bag-of-features model[C]//Computer Vision-ECCV2010.BerlinHeidelberg：Springer，2010：748-761.

[12]Sivic J，Zisserman A.Video Google：a text retrieval approach to object matching in videos[C]//Ninth IEEE International Conference on Computer Vision，2003：1470-1477.

[13]Fei-Fei L，Perona P.A bayesian hierarchical model for learning natural scene categories[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，CVPR 2005，2005：524-531.

[14]Lazebnik S，Schmid C，Ponce J.Beyond bags of features：spatial pyramid matching for recognizing natural scene categories[C]//IEEEComputer Society Conference on Computer Vision and Pattern Recognition，2006：2169-2178.

[15]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[16]Shi J，Malik J.Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

[17]Williams C K I，Rasmussen C E，Scwaighofer A，et al. Observations on the Nystr?m method for Gaussian process prediction[R].University of Edinburgh and University College London，London，UK，2002.

[18]Williams C，Seeger M.Using the Nystr?m method to speed up kernel machines[C]//Advances in Neural Information Processing Systems，2001.

[19]Fowlkes C，Belongie S，Chung F，et al.Spectral grouping using the Nystr?m method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.

[20]Li M，Lian X C，Kwok J T，et al.Time and space efficient spectral clustering via column sampling[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2011：2297-2304.

[21]Liu L，Wang L，Liu X.In defense of soft-assignment coding[C]//2011 IEEE International Conference on Computer Vision（ICCV），2011：2486-2493.

[22]van Gemert J C，Geusebroek J M，Veenman C J，et al. Kernel codebooks for scene categorization[C]//Computer Vision-ECCV 2008.Berlin Heidelberg：Springer，2008：696-709.

[23]Yang J，Yu K，Gong Y，et al.Linear spatial pyramid matching using sparse coding for image classification[C]// IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2009，2009：1794-1801.

[24]Wang J，Yang J，Yu K，et al.Locality-constrained linear coding for image classification[C]//2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2010：3360-3367.

[25]Chen W Y，Song Y，Bai H，et al.Parallel spectral clustering in distributed systems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（3）：568-586.

WANG Xin1,LI Lu1,WANG Xiaofang2

1.Department of Mathematics and Physics,Anhui Jianzhu University,Hefei 230601,China
2.Department of Computer,Army Officer Academy of PLA,Hefei 230031,China

Construction of visual vocabulary is a crucial step in popular Bag-of-Visual-Words（BOVW）model.Currently, K-means clustering is generally applied to constructing the visual vocabulary.However,the visual dictionary tends to be of low discrimination due to limitation of K-means clustering and complexity of high dimensional spatial structure of samples. Under the frame of spectral clustering,a dictionary learning algorithm with stronger discriminative capability is proposed. In order to reduce degradation of descriptors discriminative power during quantization and the inherent problems of storage and calculation in spectral clustering,the training samples are divided into sub-sample sets according to the label information of category.Centers of each data set are obtained based on spectral clustering with Nystr?m algorithm and then the final compact visual dictionary is generated.Experimental results in Scene-15 dataset verify the correctness and effectiveness of the proposed algorithm.Especially when the training samples are limited,the visual dictionary via the algorithm can obtain better performance.

image classification;bag of visual words;visual vocabulary;spectral clustering

A

TP391

10.3778/j.issn.1002-8331.1401-0173

WANG Xin,LI Lu,WANG Xiaofang.Dictionary learning based on spectral clustering with Nystr?m.Computer Engineering and Applications,2014,50（6）：112-117.

安徽省教育廳自然科學項目（No.KJ2013B067，No.KJ2012B034）。

王鑫（1980—），女，講師，主要研究方向：數(shù)字圖像處理；李璐（1980—），女，講師，主要研究方向：數(shù)字圖像處理；王曉芳（1976—），女，講師，主要研究方向：數(shù)字圖像處理。

2014-01-13

2014-02-28

1002-8331（2014）06-0112-06