基于樸素貝葉斯K近鄰的快速圖像分類算法

張旭，蔣建國，洪日昌*，杜躍

(1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，合肥230009;2.陸軍軍官學(xué)院 計算機教研室，合肥230031)

圖像分類是計算機視覺研究中的熱點內(nèi)容之一，在圖像標(biāo)注［1］、多媒體信息檢索［2］等領(lǐng)域均有廣泛的應(yīng)用.圖像分類技術(shù)大致分為以下兩大類:基于學(xué)習(xí)過程的圖像分類方法和非參數(shù)的圖像分類方法.目前，基于學(xué)習(xí)過程的分類方法仍是圖像分類與識別領(lǐng)域內(nèi)的主流，特別是隨著視覺詞袋模型(BoVW)［3］的提出與應(yīng)用，然而在實際情況中往往存在訓(xùn)練樣本不足以及過擬合等問題.而非參數(shù)的分類方法不需要參數(shù)學(xué)習(xí)的過程，能夠更合理地應(yīng)用于圖像類別較多的分類任務(wù)中并且避免了過擬合等問題，相比于基于學(xué)習(xí)過程的分類方法，基于非參數(shù)的分類算法更為簡潔.

盡管非參數(shù)的分類器存在上述優(yōu)點，但其分類性能低于基于學(xué)習(xí)過程的分類算法［4-7］.文獻(xiàn)［8］比較了非參數(shù)最近鄰(NN)方法與BoVW模型的圖像分類性能，實驗結(jié)果表明后者的分類正確率明顯優(yōu)于前者.而文獻(xiàn)［9］提出一種基于樸素貝葉斯最近鄰(NBNN)圖像分類算法，認(rèn)為基于非參數(shù)的最近鄰分類性能在實際應(yīng)用中被低估，導(dǎo)致其性能下降的原因有兩方面:一方面是算法中的特征量化引起量化誤差，另一方面是算法采用圖像與圖像之間的距離進(jìn)行分類決策.文獻(xiàn)［10］在 NBNN算法的基礎(chǔ)上提出一種 NBNN Kernel，并與BoVW模型相結(jié)合用于圖像分類.NBNN算法的成功之處主要在于采用了圖像-類別距離(I2C)度量方式，文獻(xiàn)［11］在此基礎(chǔ)上提出一種線性距離編碼的方法，采用圖像-類別距離將圖像的局部特征轉(zhuǎn)化為更具區(qū)分性能的距離向量.文獻(xiàn)［12］提出一種Local NBNN的分類算法，文獻(xiàn)［13］在此基礎(chǔ)上結(jié)合BoVW和Local NBNN方法的優(yōu)點提出一種位置區(qū)分性編碼方法，通過特征-類別距離而非K-means聚類將局部特征轉(zhuǎn)化為特征向量，從而避免了量化帶來的信息損失.Tommasi等［14］基于 NBNN分類器提出一種領(lǐng)域適應(yīng)學(xué)習(xí)算法，實驗結(jié)果進(jìn)一步證明了NBNN算法思想的有效性.Wang等［15］基于最近鄰分類提出一種加權(quán)I2C即圖像-類別距離學(xué)習(xí)方法，并采用空間劃分和Hubness Score的方法對圖像分類進(jìn)行加速，但這種方法模型復(fù)雜，特別是權(quán)重學(xué)習(xí)過程時間復(fù)雜度較高.

NBNN算法的主要思想是對測試圖像中的每個特征在各類訓(xùn)練圖像特征集中尋找其最近鄰并計算I2C距離，隨著圖像類別以及各類圖像數(shù)目的增加，算法運行速度較慢、內(nèi)存開銷高，影響了其在實際中的應(yīng)用，并且NBNN算法使用測試圖像的一個最近鄰特征用于決策分類.在基于稀疏編碼的圖像分類與物體識別中［16］，硬賦值編碼的性能已經(jīng)被證實低于局部受限軟賦值編碼，硬賦值編碼本質(zhì)上就是尋找一個最近鄰，而局域受限軟賦值編碼則是尋找鄰域內(nèi)的K近鄰，受此啟發(fā)本文采用特征的K近鄰用于分類決策.

一般情況下，一幅圖像包含了少量高區(qū)分性能的特征和大量低區(qū)分性能的特征，部分低區(qū)分性能的特征表現(xiàn)為圖像常規(guī)性的結(jié)構(gòu)信息和背景信息，這部分特征對圖像分類貢獻(xiàn)較小，但由于其數(shù)量較多，搜索最近鄰并計算I2C距離需要大量時間.因此，在NBNN算法中選擇高區(qū)分性能的特征用于分類決策可以有效減小近鄰搜索時間及內(nèi)存開銷，為應(yīng)用于大規(guī)模圖像分類任務(wù)提供了可能.

本文提出一種樸素貝葉斯K近鄰(NBKNN)分類算法，在充分利用NBNN算法思想的基礎(chǔ)上并非使用特征空間中的最近鄰特征而是K近鄰特征進(jìn)行決策分類，并且進(jìn)一步去除背景信息對分類性能的影響;為了提高算法運行速度、減少算法內(nèi)存開銷，在保證分類正確率的前提下，采用特征選擇的方式分別減少測試圖像以及訓(xùn)練圖像集中的特征數(shù)目，并且嘗試同時減少測試圖像與訓(xùn)練圖像集中的特征數(shù)目平衡分類正確率與分類時間之間的矛盾.

1 特征量化與圖像-類別距離度量

圖像分類算法中最常用的兩個過程導(dǎo)致了非參數(shù)方法分類性能的下降，這兩個過程分別是特征量化和圖像與圖像間的距離測度.

1.1 特征量化

在基于BoVW模型的圖像分類算法中，首先在訓(xùn)練樣本中提取大量的圖像特征，通過聚類構(gòu)建視覺詞典，聚類中心即是視覺詞典中的每個單詞，然后通過視覺詞典將圖像表示為直方圖空間中具有固定長度的特征向量，這種表示方式對基于SVM等的圖像分類方法是必須的.量化產(chǎn)生的視覺詞典帶來了信息損失，大量具有區(qū)分性能的特征被丟棄，但損失的信息在訓(xùn)練學(xué)習(xí)過程中可以得到一定程度的彌補，從而算法仍可獲得不錯的分類性能.然而如果將這種圖像表示方式用于最近鄰圖像分類算法中，由于非參數(shù)的分類方法中沒有訓(xùn)練學(xué)習(xí)的過程，損失的信息無法得到彌補，因此分類性能較差.

在量化過程中，特征空間中出現(xiàn)頻率低的特征往往具有較高的量化誤差，而出現(xiàn)頻率高的特征量化誤差較低.在大部分圖像中高頻特征往往表現(xiàn)為圖像的結(jié)構(gòu)性信息如邊緣和拐角，因此該類特征包含有用的信息較少，區(qū)分性能較差.而圖像中最具區(qū)分性能的特征出現(xiàn)頻率較低，位于特征空間中的低密度區(qū)域，在聚類過程中這部分區(qū)域往往無法生成聚類中心，即無法生成視覺單詞，因此聚類構(gòu)建視覺詞典的過程中將不可避免地出現(xiàn)量化誤差，導(dǎo)致區(qū)分性能下降，并且區(qū)分性能越高的特征經(jīng)量化之后其區(qū)分性能降低的程度越高.文獻(xiàn)［17］采用 p(d|C)/p(d|)描述了特征d區(qū)分類別C與其他類別的能力，經(jīng)過量化后特征d的區(qū)分性能描述為p(dquant|C)/p(dquant|)，在Caltech-101圖像集中的實驗證實了經(jīng)量化之后圖像集中特征的平均區(qū)分性能大約下降了60%.

1.2 圖像-類別距離度量化

在非參數(shù)的圖像分類中，量化操作是引起圖像分類性能下降的主要原因之一.文獻(xiàn)［18］提出一種基于最近鄰的圖像分類算法，算法使用了Geometric Blur特征并且避免了量化過程，但實驗結(jié)果仍然差強人意.文獻(xiàn)［9］認(rèn)為造成這種問題的主要原因是采用了圖像-圖像(I2I)的距離度量方式而非圖像-類別(I2C)的距離度量方式.I2I的距離度量方式是實現(xiàn)核方法的基礎(chǔ)，然而在基于I2I非參數(shù)的圖像分類方法中，僅當(dāng)訓(xùn)練樣本足夠多并且測試圖像(待分類圖像)與訓(xùn)練圖像非常相似時才能取得很好的分類效果.當(dāng)訓(xùn)練樣本數(shù)量較少并且類內(nèi)圖像變化較大時，這種距離度量方式極大地限制了圖像分類的泛化性能.在文字識別和紋理圖像分類等領(lǐng)域中，基于最近鄰的分類器具有較優(yōu)的分類性能，主要原因是相對于類別的復(fù)雜性各類具有數(shù)量較多的訓(xùn)練樣本.然而在實際情況中，相對于類別復(fù)雜度本文所獲得的訓(xùn)練樣本數(shù)目較低，特別是當(dāng)類別內(nèi)復(fù)雜性較高時，如同類別內(nèi)的物體具有不同的外觀形狀和表示形式，基于最近鄰的圖像分類效果較差.采用I2C的距離測度方式即同時利用類別C中所有圖像特征的分布可以獲得更好的分類效果和泛化性能［19］.文獻(xiàn)［20］證實了在服從樸素貝葉斯假設(shè)的條件下，在基于最近鄰的圖像分類方法中采用I2C的距離度量方式可獲得優(yōu)于I2I的分類性能.

2 樸素貝葉斯最近鄰分類

在滿足一定的假設(shè)條件下，基于樸素貝葉斯最近鄰分類器可以獲得近似最優(yōu)貝葉斯分類性能.問題描述如下:對于給定的待分類圖像Q(測試圖像)，根據(jù)訓(xùn)練圖像及其類別標(biāo)簽將其劃分到相應(yīng)的類別C中.根據(jù)最大后驗概率最小化分類誤差的原則，測試圖像Q按照式(1)被劃分為類別中.

假設(shè)類別C服從均勻分布，則根據(jù)貝葉斯公式，最大后驗概率等價于最大似然概率.式(1)可以改寫為

圖像Q的特征描述子分別記為 d1，d2，…，dn，假設(shè)di符合獨立同分布，則

對式(3)取對數(shù)運算(底數(shù)大于1)，則分類準(zhǔn)則如下:

p(di|C)可以通過Parzen窗核函數(shù)進(jìn)行估計:

式中，dC1，dC2，…，dCL為類別 C中所有訓(xùn)練圖像中的特征描述子，L為特征描述子的個數(shù);Kf為高斯核函數(shù)，其值非負(fù)并且和為1，如式(6)所示.隨著L的逐漸增大，函數(shù)的尺度參數(shù)σ逐漸減小，p^(di|C)最終趨于p(di|C)的真實分布.

基于最大后驗概率的樸素貝葉斯分類器需要計算每個特征d在類別C中的概率分布，雖然可以采用Parzen窗進(jìn)行估計，但是從每幅圖像中提取的局部特征數(shù)量巨大，特別是為了獲得更高的準(zhǔn)確率，需要盡可能多的dCj即類別C中所有圖像的局部特征，由于需要計算d和dCj之間的距離，因此算法的時間復(fù)雜度較高.考慮特征分布的特性，特征空間中大部分區(qū)分性能高的特征相對孤立，類別C內(nèi)各圖像局部特征的分布更是如此.因此隨著d與dCj之間距離的增加，式(5)中大部分Kf(di－)項是可以忽略的，僅小部分項(即與d距離足夠近的那一部分)起到?jīng)Q定性作用.因此，只需計算Kf(di－dCj)前K項即d在類別C中的K最近鄰特征，式(5)改寫為

原始NBNN算法中取K為1，即對檢索圖像中的特征在類別C中尋找其最近鄰用于分類決策，實驗取得不錯的分類性能.

3 樸素貝葉斯K近鄰分類

NBNN算法簡單有效、分類性能好，并且不需要額外訓(xùn)練學(xué)習(xí)的過程，避免了參數(shù)學(xué)習(xí)等帶來的相關(guān)問題.但算法運行速度較慢并僅利用最近鄰進(jìn)行分類識別，這方法類似于BoVW模型中的硬賦值編碼方式，盡管取得了不錯的分類效果，但沒有充分利用其他近鄰特征的信息.結(jié)合NBNN算法的原理和軟賦值編碼的思想，本文提出一種樸素貝葉斯K近鄰分類算法記為NBKNN算法，分類過程中利用了特征的K近鄰信息并去除背景信息對分類性能的影響，算法采用 FLANN［21］搜索近似K近鄰，提高了高維特征近鄰的搜索速度.

給定測試圖像Q以及訓(xùn)練圖像庫，定義圖像Q對于類別C的區(qū)分性能RC如下式所示，其中表示不是C的其他類別:

對式(8)取對數(shù)運算得

式(9)將圖像Q對類別C的區(qū)分性能轉(zhuǎn)化為圖像中局部特征對類別C的區(qū)別性能，因此分類決策可以表示為

原始 NBNN算法的時間復(fù)雜度為O(NQNClog(NTrNT))，其中NTr表示每類別中訓(xùn)練圖像的數(shù)目，NC表示訓(xùn)練圖像集中的類別數(shù)目，NQ和NT分別表示測試圖像和訓(xùn)練圖像中的特征數(shù)目，數(shù)量眾多的特征中很大一部分表征了圖像中的背景信息和噪聲信息，雖然這些特征對于分類沒有起到實質(zhì)性的作用，但卻在很大程度上影響著算法的運行速度.本文采用特征選擇的方式從測試圖像及訓(xùn)練圖像集中選擇區(qū)分性能高的特征用于分類識別，一方面提高了算法的運行速度，另一方面減少了算法的內(nèi)存開銷，為其應(yīng)用于規(guī)模更大的圖像庫中提供了可能.算法基于特征的統(tǒng)計分布性質(zhì)度量特征間的相關(guān)性并進(jìn)行特征選擇，計算公式如下所示:

式中，ui表示特征的均值;σi表示特征的方差.通過實驗發(fā)現(xiàn)，F(xiàn)i在一定程度上度量了特征的區(qū)分性能，其數(shù)值越高表明特征的區(qū)分性能越高，其數(shù)值越低則表明區(qū)分性能越低.結(jié)合上述分析，本文提出的快速NBKNN算法可以描述為:

1)提取測試圖像與C類訓(xùn)練圖像中的局部特征，分別記為di∈Q和dCi.

2)根據(jù)式(12)計算測試圖像和訓(xùn)練圖像集中特征的Fi值，保留前M個最大Fi值對應(yīng)的特征，其中測試圖像中的前M個特征記為dM.

3)對每個dM在類別C中搜索其K近鄰，分別記為{NC1，NC2，…，NCK}，在其他類別中搜索其最近鄰并計算其均值

4)計算dM到各類別K－1近鄰的距離之和，以及第K近鄰及的距離，分別記為

5)對每個dM在各類別C中計算TC，TC=D1－D2－ D3，最 終 的 分 類 決 策 為:C^=

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

4.1 實驗設(shè)置

為了驗證本文所提算法的有效性，選擇在Caltech-101圖像庫和Caltech-256圖像庫中進(jìn)行分類識別實驗，其中Caltech-101圖像庫包含了101種類型的圖像，如動物、家具、車輛、花朵等類別，每類圖像包含31～800張圖像.Caltech-256圖像庫包含了256種類型的圖像，每類包含至少80張圖像.相比于 Caltech-101圖像庫，Caltech-256圖像庫更具復(fù)雜性.實驗采取圖像分類領(lǐng)域中的一般性做法，將圖像集中的每類圖像隨機劃分為訓(xùn)練圖像集和測試圖像集.與基于學(xué)習(xí)的分類方法不同，非參數(shù)化的分類算法沒有學(xué)習(xí)的過程，因此不需要訓(xùn)練樣本訓(xùn)練分類器，但是為了便于比較與表述，仍使用訓(xùn)練樣本表示帶有類別標(biāo)簽的參考圖像，使用測試圖像表示檢索圖像.本文采用稠密SIFT特征表示圖像，提取特征的圖像塊大小為16×16，步長為8，實驗中限制所有圖像的長和寬不超過 300像素.特別地，本文采用FLANN進(jìn)行近似近鄰搜索，實驗中設(shè)置隨機KD-tree的個數(shù)為5.

4.2 Caltech-101圖像庫的實驗結(jié)果

4.2.1 近鄰個數(shù)K對分類性能的影響

首先衡量近鄰個數(shù)K對分類性能的影響，實驗中測試圖像與訓(xùn)練圖像均沒有經(jīng)過特征選擇操作.實驗結(jié)果如圖1所示，當(dāng)K取1時(不考慮背景信息的影響)本文算法退化為原始NBNN算法，圖像分類正確率為62.32%.當(dāng)K取10時，算法取得了最優(yōu)分類性能，圖像分類正確率達(dá)到65.18%，比原始 NBNN算法的正確率提高了2.86%.相比于原始NBNN算法，本算法在分類決策中充分利用了特征的K近鄰信息并且去除了背景信息對分類的影響，因此分類性能較優(yōu).從實驗結(jié)果還可以發(fā)現(xiàn)當(dāng)K在相對較小的范圍(5～20)中取值時，算法獲得了相對較好的分類效果.K值過小，圖像的分類性能較差;K值過大，分類性能并沒有顯著的提高，但在一定程度上增加了算法的復(fù)雜性.在文獻(xiàn)［16］提出的LLC中，當(dāng)最近鄰個數(shù)K為5時取得最佳效果，本文實驗結(jié)果與其具有一致性，在后續(xù)實驗中取K=10.

圖1 近鄰個數(shù)K對分類性能的影響Fig.1 Influence of number of nearest neighbors K for classification performance

表1給出了本文算法與其他一些分類算法的對比結(jié)果，從表中可以看出，在各種非參數(shù)化的分類算法中本文算法優(yōu)于 SPM-NN，GB-NN［8］，GB Vote NN［22］，SVM-KNN［18］以 及 NBNN1 算 法，NBNN1表示僅僅使用SIFT特征的原始NBNN算法;但算法分類性能低于 Local NBNN和NBNN5［9］，NBNN5不僅使用了 SIFT 特征描述子，而且還結(jié)合了亮度、顏色、形狀以及自相似描述子，因此能夠更豐富、更加魯棒地表示圖像信息;Local NBNN算法選擇局部近鄰特征用于分類決策.雖然上述算法獲取的分類性能較高，但也存在運行速度較慢、內(nèi)存開銷大等問題;表1中后4種算法是基于參數(shù)化分類算法的實驗結(jié)果，算法包含了學(xué)習(xí)的過程.從實驗結(jié)果可以看出，本文算法優(yōu)于 SPM［5］，LLC［16］，NBNN-Kernel［10］，但分類性能低于 SCSPM［6］及 LSC［7］，LSC 采用局部軟賦值編碼的思想，這種思想與本文算法相似，充分利用了各鄰域的信息，在一定程度上避免了量化過程中的信息損失，結(jié)合SVM分類器算法取得了較為理想的分類效果.雖然本文算法的分類性能低于ScSPM和LSC，但本算法不需要訓(xùn)練學(xué)習(xí)的過程，避免了學(xué)習(xí)過程中引起的諸多問題.

表1 不同算法在Caltech-101中的分類正確率比較Table1 Classification accuracy comparison on Caltech-101 of different algorithms

4.2.2 基于樸素貝葉斯K近鄰的快速分類算法

原始NBNN算法運行速度慢，文獻(xiàn)［9］給出在Caltech-101圖像庫中當(dāng)訓(xùn)練樣本個數(shù)為30時，采用NBNN算法對每張圖像進(jìn)行分類的平均時間約為140 s，當(dāng)每類測試圖像個數(shù)為15時，圖像庫共包含1 530張圖像(共102類)，對所有圖像進(jìn)行分類所需時間約為59 h.本文上述實驗中對每張圖像進(jìn)行分類的平均時間約為41 s，實驗使用一臺Core(TM)CPU 3.1 GHz，8 GB內(nèi)存的計算機.對測試圖像中的每個特征在訓(xùn)練圖像集中搜索其最近鄰并計算I2C距離占據(jù)著算法主要的運行時間，為了進(jìn)一步提高算法的運行速度并減少近鄰搜索中的內(nèi)存開銷，本文采用特征選擇的方式分別減少測試圖像、訓(xùn)練圖像，并嘗試同時減少二者中的特征數(shù)目，分析對分類性能的影響.

按照本文算法計算測試圖像和訓(xùn)練圖像集中各特征的Fi值并從大到小排序，分別保留測試圖像和訓(xùn)練圖像集中前90%，80%，…，10%的特征用于分類決策.NBNN主要的思想之一是采用I2C距離度量方式，因此需要提取訓(xùn)練圖像集合中每幅圖像的特征，并將所有圖像的特征融合為一個整體再進(jìn)行特征選擇.實驗結(jié)果如圖2和圖3所示，其中圖2給出了不同情況下圖像的平均分類正確率，圖3給了相應(yīng)情況下圖像的平均分類時間，其中并不包括圖像特征提取的時間.從實驗結(jié)果可以看出，隨著測試圖像和訓(xùn)練圖像集中特征的減少，圖像的分類正確率均出現(xiàn)不同程度的下降，而運行速度越來越快.當(dāng)選擇測試圖像90%和80%的特征用于分類決策時，圖像分類正確率分別為63.75%和62.34%，平均分類時間分別為38.52 s和37.26 s;選擇訓(xùn)練圖像集90%和80%的特征時，圖像分類正確率分別為64.14%和62.82%，平均分類時間分別為37.19 s和 33.41 s.上述方法在保證圖像分類正確率的情況下，有效地降低了分類時間，均優(yōu)于原始NBNN算法，特別是分類速度有了很大的提高.

圖2 Caltech-101中特征選擇對分類正確率的影響Fig.2 Influence of feature selection for classification accuracy in Caltech-101

圖3 Caltech-101中特征選擇對分類時間的影響Fig.3 Influence of feature selection for classification time in Caltech-101

從圖2可看出當(dāng)測試圖像和訓(xùn)練圖像集分別選擇相同特征數(shù)目百分比時，前者所獲得的分類正確率均小于后者，并且當(dāng)測試圖像和訓(xùn)練圖像集中的特征數(shù)目從100%降低到10%時，減少測試圖像特征數(shù)目所引起圖像分類正確率的下降多于訓(xùn)練圖像集所引起分類正確率的下降，由此可見，在基于NBNN思想的圖像分類中，減少測試圖像中的特征對分類正確率影響較大;從圖3可發(fā)現(xiàn)減少訓(xùn)練圖像集中的特征對分類時間影響較大，隨著訓(xùn)練圖像集中特征數(shù)目的減少，算法的運行速度越來越快，主要原因是減少各類訓(xùn)練圖像集(本實驗中共102類)中的特征數(shù)目很大程度上減少了FLANN中索引的創(chuàng)建時間及最近鄰搜索的時間.

以上分別通過特征選擇的方式有效地減少了測試圖像及訓(xùn)練圖像集中的特征密度并分析了對分類性能的影響.通過實驗結(jié)果可知，基于NBNN思想的圖像分類算法應(yīng)該盡可能地保留測試圖像中的特征信息，雖然測試圖像中包含了大量區(qū)分性能較低的特征，但是由于其數(shù)量較多，當(dāng)把它們看作一個整體時仍然具有較強的區(qū)分性能;而對于訓(xùn)練圖像集中的特征，應(yīng)盡可能地去除那些信息量少的特征以及噪聲點［23］.

基于上述實驗分析，為了進(jìn)一步提高算法的運行速度和減少算法的內(nèi)存開銷，嘗試同時在測試圖像和訓(xùn)練圖像集中進(jìn)行特征選擇.為了保證算法的分類正確率，分別選擇在測試圖像90%和80%特征的情況下，逐漸減少訓(xùn)練圖像集中的特征數(shù)目并比較圖像的分類正確率和分類時間.為了表示方便，記原始測試圖像與訓(xùn)練圖像集的特征數(shù)目分別為NQ和NT，經(jīng)過特征選擇之后的特征數(shù)目分別為FQ和FT.圖4和圖5分別給出了兩種情況下的實驗結(jié)果，可以看出在訓(xùn)練圖像庫相同的情況下選擇測試圖像90%的特征用于分類可以獲得較高的分類正確率，但其分類速度稍低于后者，這與理論分析相一致.當(dāng) FQ=90%NQ，F(xiàn)T=90%NT時，圖像分類正確率為62.98%，分類時間為36.04 s，分類正確率雖然稍低于NBKNN算法，但其分類速度更快并且明顯優(yōu)于 NBNN算法.當(dāng) FQ=90%NQ，F(xiàn)T=80%NT及 FQ=80%NQ，F(xiàn)T=90%NT時圖像分類正確率分別為62.02%和61.77%，分類時間分別為32.53 s和34.94 s，雖然分類性能稍低于原始NBNN算法，但是分類速度明顯優(yōu)于原始算法.因此選擇合適的方式同時對測試圖像和訓(xùn)練圖像集進(jìn)行操作可以平衡分類正確率和分類時間之間的矛盾，將最近鄰分類器用于實際大規(guī)模圖像分類任務(wù)中.

圖4 Caltech-101中FQ=90%NQ與FQ=80%NQ時減少訓(xùn)練圖像集特征數(shù)目對分類正確率的影響Fig.4 Influence of reducing feature numbers of training sets while FQ=90%NQand FQ=80%NQfor classification accuracy in Caltech-101

圖5 Caltech-101中FQ=90%NQ與FQ=80%NQ時減少訓(xùn)練圖像集特征數(shù)目對分類時間的影響Fig.5 Influence of reducing feature numbers of training sets while FQ=90%NQand FQ=80%NQforclassification time in Caltech-101

4.3 Caltech-256圖像庫的實驗結(jié)果

為了進(jìn)一步驗證算法的有效性，本文在Caltech-256圖像庫上進(jìn)行分類實驗.在分類過程中分別從每類圖像中隨機選取15張圖像作為訓(xùn)練圖像和測試圖像，每組實驗分別執(zhí)行5次，實驗結(jié)果為數(shù)據(jù)集中所有類別圖像的平均分類正確率.與前述實驗設(shè)置相一致，當(dāng)選取最近鄰個數(shù)K為10時算法取得比較理想的分類正確率，后續(xù)實驗中K的值均取10.表2給出了本文算法與其他一些分類算法在Caltech-256圖像庫上的結(jié)果.

表2 不同算法在Caltech-256中分類正確率比較Table2 Classification accuracy comparison on Caltech-256 of different algorithms

從實驗結(jié)果可以看出本文算法取得的分類正確率比原始NBNN算法提高了近3%，與Local NBNN算法取得的分類正確率相當(dāng).從表2還可以看出，非參數(shù)化分類算法在Caltech-256圖像庫上所取得的識別正確率普遍優(yōu)于基于學(xué)習(xí)過程分類算法，主要原因是Caltech-256圖像庫包括了更多種類的圖像，圖像數(shù)據(jù)更加豐富，并且圖像類內(nèi)差距更加明顯，變化更具多樣性，在基于學(xué)習(xí)過程的分類算法中，訓(xùn)練器學(xué)習(xí)過程中容易產(chǎn)生過擬合等問題，并且上述算法中字典學(xué)習(xí)與特征編碼等過程帶來了一定的量化誤差，從而影響了最終的分類正確率.

對規(guī)模更大的Caltech-256圖像庫進(jìn)行分類所需時間更長，并且在近鄰搜索中占用了大量的內(nèi)存空間，因此這種局限性限制了基于NBNN思想的分類方法在實際大規(guī)模甚至中等規(guī)模圖像庫中的應(yīng)用.采用本文提出的快速NBKNN算法分別計算測試圖像和訓(xùn)練圖像集中各特征的Fi值并從大到小排序，分別保留測試圖像和訓(xùn)練圖像集前90%，80%，…，10%的特征用于分類決策.實驗結(jié)果如圖6和圖7所示，其中圖6給出了不同情況下圖像的平均分類正確率，圖7給了相應(yīng)情況下圖像的平均分類時間.從實驗結(jié)果可以看出減少測試圖像中的特征對分類正確率影響較大，減少訓(xùn)練圖像集中的特征對分類時間影響較大，這與前面實驗結(jié)果分析相一致.

圖6 Caltech-256中特征選擇對分類正確率的影響Fig.6 Influence of feature selection for classification accuracy in Caltech-256

圖7 Caltech-256中特征選擇對分類時間的影響Fig.7 Influence of feature selection for classification time in Caltech-256

為了進(jìn)一步提高算法的運行速度和減少算法的內(nèi)存開銷，嘗試同時在測試圖像和訓(xùn)練圖像集中進(jìn)行特征選擇.為了保證算法的分類正確率，分別選擇在測試圖像90%和80%特征的情況下，逐漸減少訓(xùn)練圖像集中的特征數(shù)目并比較圖像的分類正確率和分類時間，實驗結(jié)果如圖8和圖9所示.當(dāng) FQ=90%NQ，F(xiàn)T=90%NT時，圖像分類正確率為32.21%，分類時間為92.21 s，分類正確率與分類速度明顯優(yōu)于 NBNN算法.當(dāng) FQ=90%NQ，F(xiàn)T=80%NT及 FQ=80%NQ，F(xiàn)T=90%NT時圖像分類正確率分別為 31.28%和30.59%，分類時間分別為 83.71 s 和 88.20 s，分類性能與NBNN算法相接近，但是分類速度明顯優(yōu)于原始算法.

圖8 Caltech-256中FQ=90%NQ與FQ=80%NQ時減少訓(xùn)練圖像集特征數(shù)目對分類正確率的影響Fig.8 Influence of reducing feature numbers of training sets while FQ=90%NQand FQ=80%NQfor classification accuracy in Caltech-256

圖9 Caltech-256中FQ=90%NQ與FQ=80%NQ時減少訓(xùn)練圖像集特征數(shù)目對分類時間的影響Fig.9 Influence of reducing feature numbers of training sets while FQ=90%NQand FQ=80%NQfor classification time in Caltech-256

5 結(jié)論

本文在分析樸素貝葉斯分類算法的基礎(chǔ)上，結(jié)合K近鄰原理提出一種新的圖像分類算法，經(jīng)實驗驗證表明:

1)采用K近鄰(K=10)用于分類決策并去除背景信息對分類正確率的影響，提高了原始NBNN算法的分類正確率;

2)針對NBKNN分類算法，比較分別在測試圖像和訓(xùn)練圖像集上采用特征選擇的方式減少用于分類決策的特征數(shù)目對分類性能的影響，減少測試圖像的特征數(shù)目對分類正確率影響較大，而減少訓(xùn)練圖像集的特征數(shù)目對分類時間影響較大.

3)在NBKNN分類算法中選擇測試圖像90%的特征與訓(xùn)練圖像集80%的特征用于分類決策，取得了與原始NBNN分類算法相近的分類正確率，但比原始NBNN算法快了近5倍，平衡了分類正確率與分類時間之間的矛盾，為最近鄰分類器應(yīng)用于實際提供了可能.

基于最近鄰的圖像分類算法與基于BoVW模型的圖像分類算法各具優(yōu)缺點，如何結(jié)合二者之間的優(yōu)點在大數(shù)據(jù)背景下學(xué)習(xí)更有效、更合理的分類模型是本文后續(xù)工作的重點.

References)

［1］ Hong R，Wang M，Gao Y，et al.Image annotation by multiple-instance learning with discriminative feature mapping and selection［J］.IEEE Trans System，Man and Cybernetics Part:B，2014，44(5):669-680.

［2］ Hong R，Tang J，Tan H，et al.Beyond search:event driven summarization for web videos［J］.ACM Trans on Multimedia Computing，Communications，and Applications，2011，7(4):35-53.

［3］ Sivic J，Zisserman A.Video google:a text retrieval approach to object matching in videos［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2003:1470-1477.

［4］ Yang J，Jiang Y G，Hauptmann A G，et al.Evaluating bag-of-visual-words representations in scene classification［C］//Proceedings of the International Workshop on Workshop on Multimedia Information Retrieval.New York:ACM，2007:197-206.

［5］ Lazebnik S，Schmid C，Ponce J.Beyond bags of features:spatial pyramid matching for recognizing natural scene categories［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2006，2:2169-2178.

［6］ Yang J，Yu K，Gong Y，et al.Linear spatial pyramid matching using sparse coding for image classification［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2009:1794-1801.

［7］ Liu L，Wang L，Liu X.In defense of soft-assignment coding［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2011:2486-2493.

［8］ Varma M，Ray D.Learning the discriminative power-invariance trade-off［C］//Proceedings of the IEEE 11th International Conference on Computer Vision.Piscataway，NJ:IEEE，2007:1-8.

［9］ Boiman O，Shechtman E，Irani M.In defense of nearest-neighbor based image classification［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2008:1-8.

［10］ Tuytelaars T，F(xiàn)ritz M，Saenko K，et al.The NBNN kernel［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2011:1824-1831.

［11］ Wang Z，F(xiàn)eng J，Yan S，et al.Linear distance coding for image classification［J］.IEEE Transactions on Image Processing，2013，22(2):537-548.

［12］ McCann S，Lowe D G.Local naive bayes nearest neighbor for image classification［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2012:3650-3656.

［13］ Yang X，Zhang T，Xu C.Locality discriminative coding for image classification［C］//Proceedings of the Fifth International Conference on Internet Multimedia Computing and Service.New York:ACM，2013:52-55.

［14］ Tommasi T，Caputo B.Frustratingly easy nbnn domain adaptation［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:897-904.

［15］ Wang Z，Hu Y，Chia L T.Improved learning of I2C distance and accelerating the neighborhood search for image classification［J］.Pattern Recognition，2011，44(10):2384-2394.

［16］ Wang J，Yang J，Yu K，et al.Locality-constrained linear coding for image classification［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2010:3360-3367.

［17］ Tuytelaars T，Schmid C.Vector quantizing feature space with a regular lattice［C］//Proceedings of the IEEE 11th International Conference on Computer Vision.Piscataway，NJ:IEEE，2007:1-8.

［18］ Zhang H，Berg A C，Maire M，et al.SVM-KNN:discriminative nearest neighbor classification for visual category recognition［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2006，2:2126-2136.

［19］ Zhang H，Berg A C，Maire M，et al.SVM-KNN:discriminative nearest neighbor classification for visual category recognition［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2006，2:2126-2136.

［20］ Rematas K，F(xiàn)ritz M，Tuytelaars T.The pooled NBNN kernel:beyond image-to-class and image-to-image［C］//Lecture Notes in Computer Science(Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).Heidelberg:Springer Verlag，2013:176-189.

［21］ Muja M，Lowe D G.Fast approximate nearest neighbors with automatic algorithm configuration［C］//International Conference on Computer Vision Theory and Applications.Piscataway，NJ:IEEE，2009:331-340.

［22］ Berg A C，Malik J.Shape matching and object recognition［M］.Berlin Heidelberg:Springer，2006.

［23］ Hong R，Pan J，Hao S，et al.Image quality assessment based on matching pursuit［J］.Information Sciences，2014，273:196-211.