張旭，蔣建國(guó)，洪日昌*，杜躍

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

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

盡管非參數(shù)的分類器存在上述優(yōu)點(diǎn)，但其分類性能低于基于學(xué)習(xí)過(guò)程的分類算法［4-7］.文獻(xiàn)［8］比較了非參數(shù)最近鄰(NN)方法與BoVW模型的圖像分類性能，實(shí)驗(yàn)結(jié)果表明后者的分類正確率明顯優(yōu)于前者.而文獻(xiàn)［9］提出一種基于樸素貝葉斯最近鄰(NBNN)圖像分類算法，認(rèn)為基于非參數(shù)的最近鄰分類性能在實(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)點(diǎn)提出一種位置區(qū)分性編碼方法，通過(guò)特征-類別距離而非K-means聚類將局部特征轉(zhuǎn)化為特征向量，從而避免了量化帶來(lái)的信息損失.Tommasi等［14］基于 NBNN分類器提出一種領(lǐng)域適應(yīng)學(xué)習(xí)算法，實(shí)驗(yàn)結(jié)果進(jìn)一步證明了NBNN算法思想的有效性.Wang等［15］基于最近鄰分類提出一種加權(quán)I2C即圖像-類別距離學(xué)習(xí)方法，并采用空間劃分和Hubness Score的方法對(duì)圖像分類進(jìn)行加速，但這種方法模型復(fù)雜，特別是權(quán)重學(xué)習(xí)過(guò)程時(shí)間復(fù)雜度較高.

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

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

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

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

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

1.1 特征量化

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

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

1.2 圖像-類別距離度量化

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

2 樸素貝葉斯最近鄰分類

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

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

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

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

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

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

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

原始NBNN算法中取K為1，即對(duì)檢索圖像中的特征在類別C中尋找其最近鄰用于分類決策，實(shí)驗(yàn)取得不錯(cuò)的分類性能.

3 樸素貝葉斯K近鄰分類

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

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

對(duì)式(8)取對(duì)數(shù)運(yùn)算得

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

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

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

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

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

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

4.2 Caltech-101圖像庫(kù)的實(shí)驗(yàn)結(jié)果

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

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

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

表1給出了本文算法與其他一些分類算法的對(duì)比結(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算法選擇局部近鄰特征用于分類決策.雖然上述算法獲取的分類性能較高，但也存在運(yùn)行速度較慢、內(nèi)存開(kāi)銷大等問(wèn)題;表1中后4種算法是基于參數(shù)化分類算法的實(shí)驗(yàn)結(jié)果，算法包含了學(xué)習(xí)的過(guò)程.從實(shí)驗(yàn)結(jié)果可以看出，本文算法優(yōu)于 SPM［5］，LLC［16］，NBNN-Kernel［10］，但分類性能低于 SCSPM［6］及 LSC［7］，LSC 采用局部軟賦值編碼的思想，這種思想與本文算法相似，充分利用了各鄰域的信息，在一定程度上避免了量化過(guò)程中的信息損失，結(jié)合SVM分類器算法取得了較為理想的分類效果.雖然本文算法的分類性能低于ScSPM和LSC，但本算法不需要訓(xùn)練學(xué)習(xí)的過(guò)程，避免了學(xué)習(xí)過(guò)程中引起的諸多問(wèn)題.

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

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

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

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

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

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

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

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

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

圖4 Caltech-101中FQ=90%NQ與FQ=80%NQ時(shí)減少訓(xùn)練圖像集特征數(shù)目對(duì)分類正確率的影響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時(shí)減少訓(xùn)練圖像集特征數(shù)目對(duì)分類時(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圖像庫(kù)的實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

圖8 Caltech-256中FQ=90%NQ與FQ=80%NQ時(shí)減少訓(xùn)練圖像集特征數(shù)目對(duì)分類正確率的影響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時(shí)減少訓(xùn)練圖像集特征數(shù)目對(duì)分類時(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)實(shí)驗(yàn)驗(yàn)證表明:

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

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

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

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

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.