胡湘萍，代江華

(1.河南經(jīng)貿(mào)職業(yè)學院計算機工程學院，河南 鄭州 450018；2.長江大學計算機科學學院，湖北 荊州 434023)

圖像分類是計算機視覺與模式識別領域的重要研究課題之一，其研究目標是為了給一幅圖像賦予某一類標簽。隨著電子產(chǎn)品的日新月異及普及，獲取圖像已經(jīng)變得越來越容易，大量的圖像需要有效地分類與管理，因而，圖像分類被應用到不同的領域，如視頻監(jiān)控、網(wǎng)絡圖像分析、生物信息學等。雖然經(jīng)歷了十幾年的發(fā)展，圖像分類仍然面臨著以下幾個方面的困難[1]:(1)由于光照變化、拍攝角度不同、遮擋等因素，同一類別的物體往往在圖像上的表現(xiàn)形式大不相同；(2)即使是同一類別的物體，其外觀、形態(tài)等表現(xiàn)形式也存在很大的差異；(3)在很多情況下，需要考慮圖像中不同物體之間的上下文關(guān)系或者物體與背景之間的依存關(guān)系，緩解單個物體時對賦予類別的不確定程度。

基于詞袋(Bag-of-Words，BoW)模型(又被稱為特征袋(Bag-of-Features，BoF)模型)的圖像表示方法是圖像分類研究中應用最廣泛同時也是最有效的體系框架之一[2]。文獻[3]將詞袋模型劃分為五個步驟:(1)劃分圖像塊。該過程以整個圖像作為輸入，其輸出為圖像塊，即將整幅圖像劃分為大小相等的小圖像塊，以用于后續(xù)處理。在對圖像劃分的過程中可以采用密集采樣方式或者稀疏采樣方式，兩種不同的采樣方式對分類準確度和計算代價都有一定的影響。一般而言，密集的采樣方式有助于提高圖像分類準確度，但需要更多的計算資源。(2)特征表示。對上一步得到的圖像塊給出恰當?shù)谋硎?，常用的特征表示?圖像的顏色直方圖[4]、紋理特征[5]、SIFT 特征[6]等。(3)生成字典。圖像分類的詞袋模型來源于文本分類[7]，其本質(zhì)是統(tǒng)計相關(guān)特征出現(xiàn)的頻次。字典的生成通常通過聚類算法實現(xiàn)，最常用的是K均值聚類。字典中的每個元素被稱為視覺詞(visual words)。(4)特征編碼。用于分類的圖像大小、特征數(shù)量并不完全相同，因此，需要將圖像特征結(jié)合字典進行編碼，將圖像表示為字典中相應視覺詞的出現(xiàn)頻次。特征編碼方式有很多，常用的有:硬編碼[2]、軟編碼[8]、稀疏編碼[9]等。(5)特征聯(lián)合(features pooling)。軟編碼和稀疏編碼得到的是編碼矩陣，需要將編碼矩陣表示為單個直方圖來對整個圖像進行描述。在此步驟之后，所有圖像擁有相同維度的直方圖表示，方便圖像之間的相似性比較和判定。常用的特征聯(lián)合方法有:平均聯(lián)合(average pooling)和最大聯(lián)合(max pooling)。

將圖像劃分為多個圖像塊有兩個方面的優(yōu)勢:(1)在一定程度上緩解物體遮擋和復雜背景對圖像分類任務造成的困難；(2)在一定程度上彌補對圖像采用直方圖表示而丟棄了圖像的空間信息的不足。

不可否認，基于詞袋模型的圖像分類框架取得了很大的成功，但是，仍然存在一些仍需解決的難題:(1)字典的構(gòu)造對分類性能有一定的影響，字典的最佳表示方式仍然沒有公論；(2)圖像特征的選擇、圖像劃分時的采樣策略、特征編碼方式等因素都會對分類性能產(chǎn)生一定的影響。一般來說，在詞袋模型中字典越大，表示圖像的直方圖維度就越高，直方圖的判別性就越強，因而分類準確度也越高。然而，字典越大，需要更多的計算資源和存儲資源，這對于大數(shù)據(jù)場景下變得很不適用。因此，對于詞袋模型來講，需要在分類準確度和計算資源之間取一個恰當?shù)恼壑小?/p>

本文的研究目標是通過對多個小字典下獲取的特征編碼，以一種在線加權(quán)融合的方式進行融合，使得融合后的結(jié)果與大字典下獲取的特征編碼一樣具有較強的判別性，即具有較高的分類準確度。與傳統(tǒng)的詞袋模型方法不同的是，本文通過在線學習的方式加權(quán)融合由多個小字典獲取的特征編碼，用于圖像分類任務。與傳統(tǒng)的詞袋模型方法及近年主要研究成果相比，在采用相同的字典學習方法和特征編碼方式的情況下，本文方法能夠獲得與采用大字典的詞袋模型方法類似的分類準確度，同時，所需的計算資源和存儲代價更小。

1 本文方法

本文方法大體上可以分為三個層次。第一層是字典生成過程，與傳統(tǒng)的詞袋模型不同的是，本文方法在這個過程中生成多個小字典而不是一個大的字典。第二層是特征編碼層，在這一層本文采用硬編碼(hard coding)，將每幅圖像表示為多個低維直方圖，并對不同字典下得到的直方圖采用直方圖交核(histogram intersection kernel)構(gòu)建相應的核矩陣。第三層采用在線學習方法對不同字典下的直方圖交核進行加權(quán)融合，獲得加權(quán)之后的核矩陣。最后，用簡單的分類器，如支持向量機(SVM)等，對圖像進行分類。本文的總體框架如圖1 所示。

圖1 本文方法總體框架圖

1.1 字典生成

對每一幅圖像，我們以密集采樣方式提取圖像的尺度不變特征變換(Scale Invariant Feature Transform，SIFT)特征。以行列每隔3 個像素進行采樣，將圖像劃分為像素且有部分重疊的圖像塊。對每個圖像塊，采用與文獻[6]相同的方式構(gòu)建圖像像素梯度直方圖的SIFT 描述符，特征表示為F＝(f1，…，f16)，其中16 為圖像被劃分的圖像塊的個數(shù)，F(xiàn)為128 維的SIFT 特征。SIFT 特征提取的是圖像的局部特征，為了能夠處理物體尺度的變化，在本文中在尺度空間理論(scale-space theory)[10]指導下，使用多個不同協(xié)方差的高斯函數(shù)對圖像塊進行平滑。

提取圖像特征之后，本文使用K均值聚類算法生成字典。選取K均值聚類算法源于其存在如下優(yōu)點[11]:(1)時間復雜度和空間復雜度相對于數(shù)據(jù)樣本個數(shù)而言是線性的；(2)算法確保收斂，且收斂速度為二次的；(3)其聚類結(jié)果不依賴于數(shù)據(jù)樣本的排列順序。其中，時間復雜度和空間復雜度是圖像分類研究領域中需要重點考慮的因素之一，尤其是在大數(shù)據(jù)或者實時應用需求環(huán)境下。

在這一層中，對于不同大小的字典，可以運行K均值算法多次，每次設定不同的聚類個數(shù)K；倘若需要的字典大小相同，可以通過輸出K均值聚類過程不同階段的結(jié)果作為相應的字典。本文實驗中，僅給出了第一種方式獲取圖像集的字典。

1.2 特征編碼

特征編碼在圖像分類任務中起著關(guān)鍵性的作用，文獻[12]的研究表明，在稀疏編碼框架下對圖像進行分類，編碼策略比字典學習更為重要。本文考慮的雖然是在詞袋模型下進行圖像分類，特征編碼仍然是關(guān)鍵因素。

硬編碼[2]策略是對圖像的每個特征賦予字典中其對應的最近距離的視覺詞，然后統(tǒng)計字典中每個視覺詞被賦予的特征個數(shù)。編碼結(jié)果則為歸一化的上述統(tǒng)計直方圖。

由于詞袋模型丟棄了圖像的空間信息，空間金字塔匹配模型[13](Spatial Pyramid Matching，SPM)在一定程度上彌補了空間信息的丟失，因此，本文在特征編碼階段應用空間金字塔匹配模型。SPM 以一種簡單的方式將圖像由粗到細劃分為不同金字塔層的多個子區(qū)域，不同層次不同區(qū)域的圖像特征單獨編碼，從而形成維度更高的直方圖圖像表示。本文將圖像劃分為3 個層次，每個層次的子區(qū)域為2?×2?，?＝0，1，2。金字塔的第一層為最粗劃分，是整個圖像，最細層將圖像劃分為22×22＝16 個子區(qū)域。經(jīng)過3 個層次的金字塔劃分之后，最終得到的圖像直方圖維度是字典大小的21 倍。

式中:i，j分別為Ii和Ij的索引，mt為第t個字典的視覺詞個數(shù)。因此，在特征編碼層中，我們既可以直接輸出圖像的特征編碼直方圖，又可以輸出對應的直方圖交核集合K＝，其中d是第一層生成的字典個數(shù)。本文采用直方圖交核集合作為這一層的輸出結(jié)果。

1.3 加權(quán)組合

上述討論得知，在第二層已經(jīng)獲取了直方圖交核集K＝由于不同字典對圖像分類任務的貢獻大小不相同，因此，需要給相應的直方圖交核賦予不同的權(quán)值，即

本文加權(quán)融合的目的是使得相同類別標簽的圖像相似性程度要高于不同類別標簽的圖像。理想情況下，希望權(quán)值向量η能夠滿足如下要求

即，

式中:Γ＝{(i，p，n)｜yi＝y(tǒng)p，yi≠yn}是圖像索引三元組，yi是圖像Ii的類別標簽。

在實際應用場景下，公式(3)所示的理想條件不可能完全滿足，于是，允許小部分圖像違背該條件。類比于SVM 軟分類情形，本文引入松弛變量ξipn≥0，公式(3)的軟條件可表述為

公式(4)中的ξipn可以看作是對不滿足限制條件(3)的懲罰項或損失項。在公式(4)的表述下，我們希望總損失值應該 最小，即∑i，p，n ξipn應 該最小。因此，類比于SVM，我們將上述限制條件和目標函數(shù)表示為二次限制優(yōu)化問題:

目標函數(shù)中項‖η‖2是正則化項，其目的在于避免過擬合現(xiàn)象的發(fā)生，常數(shù)C是為了權(quán)衡經(jīng)驗損失∑i，p，n ξipn和正則化項‖η‖2。

二次優(yōu)化問題(5)可以由數(shù)學優(yōu)化軟件直接求解，如Libsvm[15]，Mosek[16]等。然而，直接求解優(yōu)化問題(5)其計算復雜度通常是O(n3)，其中n是數(shù)據(jù)樣本的個數(shù)。因此，直接使用優(yōu)化軟件求解二次優(yōu)化問題(5)對于圖像分類任務并不適用。本文采用通過對數(shù)據(jù)采樣在線學習加權(quán)權(quán)值η，下一節(jié)將進行詳細介紹。

2 在線權(quán)值學習

本文采用OPA(Online Passive-Aggressive)算法[17]來求解上述二次優(yōu)化問題(5)。OPA 算法是基于數(shù)據(jù)采樣的在線學習算法，該算法的目標函數(shù)需要取一個折中，這個折中是在當前訓練數(shù)據(jù)下?lián)p失函數(shù)最小和當前迭代參數(shù)與上一次迭代參數(shù)距離最小之間實現(xiàn)。

我們定義三元組(i，p，n)的損失函數(shù)如下:

由1.3 節(jié)討論知，我們的目標是使得總損失函數(shù)在所有采樣的三元組(i，p，n)下最小，即∑i，p，nL(η)要最小。

類似于文獻[18]，我們將上述二次優(yōu)化問題(5)轉(zhuǎn)化為OPA 在線學習問題，

于是，在每一次迭代i，權(quán)值參數(shù)ηi的取值需要在是否與上一次迭代權(quán)值ηi－1距離很近和在當前采樣三元組下使得損失函數(shù)L(η)之間進行折中。

公式(7)同樣是一個限制條件下的二次優(yōu)化問題，為了求解該問題，我們定義其拉格朗日(Lagrange)函數(shù)如下:

其中，拉格朗日乘數(shù)子τ≥0，λ≥0。上式對參數(shù)η求偏導數(shù)，并令偏導數(shù)等于零，可得

式中:κ(i，p)＝[K1(i，p)，…，Kd(i，p)]為直方圖交核對應元素組成的向量，t＝1，…，d是字典索引。由此，新一次迭代時，加權(quán)參數(shù)η的更新表達式為

同樣，t＝1，…，d是字典索引。至此，我們?nèi)孕枰_定參數(shù)的取值。

進一步，令拉格朗日函數(shù)對參數(shù)ξipn求偏導數(shù)，有

已知參數(shù)λ≥0，因此，τ≤C。

更進一步，將公式(8)和公式(9)代入到拉格朗日函數(shù)中，對參數(shù)τ求偏導數(shù)，并令其為零，有

于是，我們可得參數(shù)τ的取值

式中:L為公式(6)中的損失函數(shù)。

由公式(9)，我們可以確定參數(shù)τ的取值為

綜上所述，算法1 總結(jié)了本文采用OPA 算法進行在線權(quán)值學習的過程。該算法給出了權(quán)值更新的閉式解，在計算效率上有很大的優(yōu)勢。

算法1 基于OPA 算法的在線權(quán)值學習

3 實驗結(jié)果及分析

為了驗證本文算法的有效性，我們在兩個圖像集上進行試驗驗證，這兩個數(shù)據(jù)集是:Caltech－101數(shù)據(jù)集[19]和Scene－15 數(shù)據(jù)集[13]。對于特征提取，我們使用開源軟件包VLFeat[20]按照1.1 節(jié)所述方式提取密集的SIFT 特征；在訓練分類器階段，我們使用LIBSVM[15]軟件包，使用預定義的核矩陣選項和默認的多分類選項。對于1.1 節(jié)生成的多個字典，實驗中使用K均值算法生成3 個字典，設定字典大小分別為50，100，150。對算法1 中的三元組采樣，設置采樣總數(shù)為105，即在訓練數(shù)據(jù)中隨機(可重復)采樣105個三元組對權(quán)值η進行更新。在詞袋模型[2]中，我們設定其字典分別為400，1 000和4 000 分別進行對比實驗。另外，本文方法還與SPM[13]方法、軟編碼[8]方法以及基于稀疏編碼的LLC[21]方法進行了實驗對比，這三個方法的實驗結(jié)果是對其論文的直接引用。為了實驗的公平性，所有實驗均運行10 次，取其均值和方差作為最終對比結(jié)果。下面對兩組數(shù)據(jù)集的實驗結(jié)果分別進行敘述。

3.1 Caltech－101 數(shù)據(jù)集

Caltech－101 數(shù)據(jù)集包含了101 個圖像類別(不包括背景類)，每個類別包括的圖像數(shù)目從31 個到800 個不等，整個數(shù)據(jù)集包含8 677 幅圖像，平均分辨率為300 pix×300 pix。在本文實驗中，我們在每個圖像類別中隨機選取15 幅圖像和30 幅圖像作為訓練集，進行兩組實驗。

圖像分類準確度結(jié)果如表1 所示，表中的詞袋模型為我們采用3 層金字塔匹配模型實現(xiàn)的經(jīng)典詞袋模型[2]，該實驗使用本文方法一樣的特征和編碼方式。詞袋模型后面括號里的數(shù)字表示對應的字典大小，如詞袋模型(400)表示采用字典大小為400的詞袋模型實現(xiàn)。實驗結(jié)果部分后面括號里表示的是相應算法在10 次運行過程中分類結(jié)果的方差。

表1 的實驗結(jié)果表明，在Caltech－101 數(shù)據(jù)集上，對于詞袋模型而言，字典大小的不同對圖像分類結(jié)果的影響比較大，雖然直觀上來說，字典越大，其字典包含的圖像內(nèi)容越精細，分類準確度也通常會越好。然而，從表1 看到，字典大小為400 時，在每類30 個訓練圖像下，其分類準確度為72.02%，略高于字典大小為4 000 時的71.24%。這個現(xiàn)象很可能是因為K均值聚類算法在獲取字典時的隨機性造成的。本文提出的圖像分類方法取得了最佳的分類準確度。與稀疏編碼[21]方法相比，本文算法同樣取得較高的分類準確度。

表1 Caltech－101 數(shù)據(jù)集圖像分類準確度對比

圖2 給出了本文算法在Caltech－101 數(shù)據(jù)集采用隨機選取30 幅圖像作為訓練集時的混淆矩陣圖像表示，圖3 給出了通過在線權(quán)值學習之后得到的直方圖交核圖像表示。

圖2 本文算法在Caltech－101 上的混淆矩陣

圖3 在線權(quán)值學習后的直方圖交核圖像

從圖2 可以看到，本文提出的圖像分類方法得到的結(jié)果主要集中在混淆矩陣的對角線上，非對角線上的值相對于對角線來說是很小的一部分。圖3給出了所有的8 677 幅圖像構(gòu)建的加權(quán)直方圖交核圖像顯示，該圖顯示出了明顯的塊效應，因此，在一定程度上表明基于OPA 的加權(quán)組合能夠使得相同標簽的圖像具有更高的相似性。

3.2 Scene－15 數(shù)據(jù)集

Scene－15 數(shù)據(jù)集包含15 個自然場景圖像，這些場景分別是CALsuburb，kitchen，living room，bedroom，store，industrial，MITcoast，MITforest，MIThighway，MITinsidecity，MITmountain，MITopencountry，MITstreet，MITtallbuilding 和PARoffice。每個場景包括200 到400 幅圖像，圖像的平均分辨率為300 pix×250 pix，整個數(shù)據(jù)集擁有圖像4 485 幅。在該數(shù)據(jù)集上，我們在每個場景類別中隨機選取100 幅圖像作為訓練集，剩余的圖像作為測試集。

表2 給出了該數(shù)據(jù)集下的圖像分類結(jié)果，由此表同樣可以看到本文算法在圖像分類準確度上的優(yōu)勢。圖4 給出了本文方法在該數(shù)據(jù)集上的混淆矩陣，對角線上的數(shù)值表示對應類別上的分類結(jié)果。

表2 Scene－15 數(shù)據(jù)集圖像分類準確度對比

圖4 本文算法在Scene－15 上的混淆矩陣

表2 的分類準確度對比中，本文方法為82.10%略低于詞袋模型在字典為4 000 時的82.55%，均高于其他對比方法。從圖4 可以看到，對于CALsuburb 類別的平均分類準確度可以達到99.81%，最低的分類結(jié)果為類別industrial，其分類結(jié)果也達到了71.23%。

3.3 復雜度分析

詞袋模型的計算復雜度是由圖像特征提取、字典生成、特征編碼和訓練等部分組成。本文方法與傳統(tǒng)的詞袋模型相比，在字典生成過程需要更多的K均值聚類次數(shù)，而K均值聚類算法的計算復雜度為O(kNd)，其中k是聚類的類別個數(shù)，n為數(shù)據(jù)樣本個數(shù)，d為數(shù)據(jù)樣本的維度。因此，在字典生成過程中，字典越大，需要的計算資源就越多。在本文的實驗中，詞袋模型若采用字典大小4 000，則在字典生成過程相比于本文方法大約需要10 倍的計算時間。

在特征編碼階段，由于均采用硬編碼策略，在查找最近鄰過程，其計算復雜度為O(kNd)，其中，k是字典大小，N是圖像特征個數(shù)，d為圖像特征維度，本文采用SIFT 特征，故d＝128。同樣，相比而言，字典越大，其需要的計算資源也越多。

表3 給出的是在Caltech－101 數(shù)據(jù)集上的計算時間比較，這些結(jié)果是運行在PC 機環(huán)境使用單線程獲取的。PC 機的配置如下:Intel Core i5 四核CPU，主頻為3.4 GHz，內(nèi)存為8GB，Windows 7 64 位操作系統(tǒng)，MATLAB2012b 開發(fā)環(huán)境。

表3 Caltech－101 計算時間比對 單位:s

從運行時間來看，在字典生成階段，本文由于需要3 次運行K均值算法，因而在計算時間上略高于字典大小為400 的詞袋模型方法。另外，在特征編碼方面也略高于字典大小為400 的詞袋模型方法，這可能是本文方法在查找最近鄰視覺詞時，同樣需要運行3 次查找算法的緣故。從該表看到:改進的OPA 算法的運行時間僅為13.58 s，相比于特征編碼，其運行時間不足1%。

同理，存儲代價同樣與字典大小呈線性關(guān)系，字典越大，其所需的存儲代價也越高。因此，在詞袋模型中，組合多個小字典既可以減少計算復雜度又可以減少存儲代價。

4 結(jié)束語

一般而言，基于詞袋模型的圖像分類算法，其用于特征編碼的字典越大，圖像分類準確度就越高，但同時也需要更高的計算資源和存儲代價。本文的研究目標是通過在線組合多個在小規(guī)模的字典下的特征編碼，以期其達到與大規(guī)模字典特征編碼相同的圖像分類準確度。

本文方法基于詞袋模型，在字典生成階段生成多個小字典而不是通常的大字典，并采用相應的特征編碼方式。在組合多個字典特征編碼時，以加權(quán)的方式對相應的特征編碼進行融合。在特征融合階段，本文改進了OPA(Online Passive-Aggressive)算法，得到了權(quán)值更新的閉式求解方式。實驗結(jié)果表明，本文方法在分類準確度上與當前主流方法不相上下，但在計算時間和存儲代價上更具優(yōu)勢，因此，驗證了本文方法的有效性。