王鑫，李璐，王曉芳

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

2.解放軍陸軍軍官學(xué)院計(jì)算機(jī)教研室，合肥 230031

基于Nystr?m譜聚類的詞典學(xué)習(xí)

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

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

2.解放軍陸軍軍官學(xué)院計(jì)算機(jī)教研室，合肥 230031

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

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

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

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

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

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

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

1 BOVW模型

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

2 譜聚類

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

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

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

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

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

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

對(duì)A進(jìn)行特征分解，A=VAΣAVTA，ΣA包含A的特征值，VA為矩陣A特征值對(duì)應(yīng)的特征向量。基于Nystr?m方法，矩陣Sd有如下近似低秩分解：

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

圖3 不同視覺詞典大小對(duì)識(shí)別性能的影響

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

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

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

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

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

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

5 結(jié)論

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

安徽省教育廳自然科學(xué)項(xiàng)目（No.KJ2013B067，No.KJ2012B034）。

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

2014-01-13

2014-02-28

1002-8331（2014）06-0112-06