基于k密集近鄰算法的局部Fisher向量編碼方法

冀 治 航， 胡 小 鵬， 楊 博， 田 云 云， 王 凡*

( 1.大連理工大學 計算機科學與技術學院， 遼寧 大連 116024；2.河南科技大學 信息工程學院， 河南 洛陽 471023 )

0 引 言

圖像分類一直是計算機視覺研究領域的熱點問題．近年來，許多學者致力于圖像表達方法的設計和研究，它是圖像分類系統中的一個重要環節．迄今為止，多種不同的圖像表達模型被相繼提出，而目前常用的則是視覺詞包模型[1-4]和卷積神經網絡[5-7]．近年來，卷積神經網絡因其在視覺應用方面的卓越表現而獲得了越來越多的關注．但是，該類方法性能的提升往往依賴大規模的數據和算力，且缺乏推理能力，在一定程度上限制了它的應用和部署[8-10]．

此外，視覺詞包模型也一直是圖像分類任務中常用的圖像表達方法之一[1-4]，該模型構建圖像表達的過程主要包含以下幾個步驟：(1)在訓練數據集上隨機提取一組圖像特征，并利用k-means或高斯混合模型(Gaussian mixture model，GMM)算法構建視覺字典；(2)對圖像中的局部特征進行編碼并匯集，從而形成圖像的表達向量．為了獲取具有區分能力的圖像表達向量，學者們相繼提出了稀疏編碼(sparse coding，SC)[11]、局部約束線性編碼(locality-constrained linear coding，LLC)[12]、局部聚合描述符向量(vector of locally aggregated descriptors，VLAD)[13]以及Fisher向量(Fisher vector，FV)編碼[14]等方法．其中，Fisher向量編碼以其優異的性能，得到了很多關注．

然而，在構建Fisher向量的過程中，Fisher向量編碼方法要計算每一個局部特征描述符相對于所有高斯子模型似然函數的梯度信息，而忽視了編碼的局部性原則[12，15]．該方法不僅削弱了圖像表達向量的辨別能力，也增加了計算量．此外，視覺字典中相似子模型的存在即近義詞現象，也會給編碼結果帶來影響[16]．

為了提高Fisher向量編碼結果的表達能力，Nakayama[15]提出了基于局部高斯度量(local Gaussian metrics，LGM)的Fisher向量編碼改進方法．該方法首先利用k-means對特征空間進行劃分，并利用單高斯對每一個聚類區域進行建模，從而構成視覺字典．在編碼過程中，LGM會將每一個特征投影到與它鄰接的k個高斯子模型上，并分別進行Fisher向量編碼，從而形成具有局部特點的Fisher向量圖像表達．此外，Garg等[17]將稀疏原則與Fisher向量編碼相結合，提出了稀疏判別Fisher向量(sparse discriminative Fisher vectors，SDFV)編碼．Lu等[18]同時引入稀疏以及局部性原則，并將它們與Fisher 向量編碼相結合，提出了稀疏Fisher向量(sparse Fisher vector，SFV)編碼．

近年來，許多學者將卷積神經網絡與Fisher向量編碼方法相結合，以此構建圖像表達．Cimpoi等[19]將CNN預訓練模型的最后一個卷積層輸出作為圖像特征，并利用Fisher向量編碼的方式來構建圖像表達．Sydorov等[20]借鑒CNN多層構架思想，將Fisher向量編碼與SVM分類器的訓練過程結合在一起，優化了GMM字典模型的生成過程，提升了分類效果．與原始Fisher向量編碼方法相比，上述兩個方法分別采用了不同的特征，優化了字典生成過程，但其并未考慮Fisher 向量編碼方法中存在的問題．為了區分圖像中不同特征之間的重要性，Pan等[21]通過學習方式對不同GMM視覺單詞賦予了不同的權重，以此提高了Fisher表達向量的辨別能力．此外，為了使得Fisher向量編碼方法能夠適應高維CNN特征，Liu等[22]將稀疏表達與Fisher向量編碼相結合，提出了稀疏Fisher向量編碼．文獻[21-22]所提方法是否對傳統手工特征也有效，作者并未探討．Tang等[23]將Fisher向量編碼過程進行分解，并融合到卷積神經網絡中的多個層中，從而將特征學習與Fisher向量編碼的相關參數統一在一起進行端到端的學習，以此獲取圖像表達．然而該方法需要依賴大規模的數據和算力．

上述這些方法從不同角度對Fisher向量編碼方法進行了改進，在一定程度上提升了Fisher 向量的表達能力，但并未考慮高斯子模型間拓撲結構的差異，近義詞現象并沒有得到解決．為此，本文提出一種改進的Fisher向量編碼方法，即基于k密集近鄰算法的局部Fisher向量(Fisher vector based onk-dense neighborhood algorithm，KDN-FV)編碼．在編碼階段，KDN-FV編碼方法會依據高斯子模型間拓撲結構的差異以及編碼局部性原則，利用k密集近鄰算法[24]為每一個特征描述符篩選編碼時所需的高斯子空間．KDN-FV編碼方法引入了局部性約束，并且考慮了子空間之間的拓撲結構差異．

1 Fisher向量編碼方法

Fisher向量編碼方法的設計原理源自Fisher核理論，該理論能夠將生成式模型與判別式模型緊密地結合起來．簡單地說，Fisher核能夠利用一個生成模型的參數信息來定義一個核函數，進而可以構造一個分類器[25]．

假設x={xi；i=1，…，t}是一組觀測樣本，pλ是由x中樣本所構造的生成模型對應的概率密度函數，λ=(λ1λ2…λn)∈Rn，是函數pλ的n維參數向量，則樣本x關于pλ似然函數的梯度可定義為

(1)

根據信息幾何理論，概率分布空間H={pλ}可以形成一個黎曼流形，它在參數λ處的局部度量函數可由Fisher信息矩陣Fλ∈Rn×n給出：

(2)

在Fisher信息矩陣給定的情況下，由樣本x和y之間的相似性可以導出Fisher核的定義：

(3)

(4)

其中

(5)

式(5)定義的梯度向量為樣本x的Fisher向量．

在文獻[14]中，Sánchez等將Fisher向量的思想引入到圖像編碼中．此時樣本集x={xi；i=1，…，t}將具體地表示從一幅圖像中提取到的局部描述符，例如SIFT、SURF等；而pλ表示含有k個子模型的混合高斯模型，其參數向量λ={wj，μj，Σj；j=1，…，k}，其中wj、μj和Σj分別表示第j個高斯子模型對應的混合權重、均值向量以及協方差矩陣．根據式(5)分別計算出對每一個參數wj、μj以及Σj的梯度，并將其串聯起來構成圖像的Fisher表達向量．

2 基于k密集近鄰算法的局部Fisher向量編碼方法

從上述Fisher向量編碼方法的介紹中可以看出，該方法在對局部特征描述符進行編碼時，會估計每一個局部特征相對于所有高斯子模型的似然函數，并計算相應梯度信息．該方法忽略了編碼的局部性原則，削弱了表達向量的區分能力[12，15]．為此，本文提出一種基于k密集近鄰算法的局部Fisher向量(KDN-FV)編碼方法．該方法能夠依據特征空間的分布，以及各個子模型間拓撲結構的異同性，僅選擇每一個局部特征的鄰近且拓撲結構差異較大的子模型進行編碼．

2.1 KDN-FV編碼方法的視覺字典構造

與原始Fisher向量編碼方法相同，KDN-FV編碼方法也采用高斯混合模型方法構建視覺字典．不同的是，改進方法會利用主成分分析法計算每一個高斯子模型中局部特征描述符的主方向向量，并以該向量衡量各個子模型間拓撲結構的差異．具體如圖1所示．

2.2 KDN-FV編碼方法的理論基礎和方法介紹

假設d=(d1d2…dn)是由高斯混合模型方法構成的含有n個單詞的視覺字典，集合p={p1，p2，…，pn}中包含了每一個單詞對應的最大主成分向量．在KDN-FV編碼方法中，將局部描述符到高斯子模型均值向量之間的歐氏距離稱為描述符到子模型的距離．同時，任意兩個子模型di與dj的主方向向量夾角∠pipj被用來度量兩個子模型的拓撲結構差異性，∠pipj越大，差異越大．

定義1對于每一個局部特征描述符，將與其最近鄰的m個高斯子模型稱為該描述符的候選子模型(candidate sub-model，CM)組．

定義2已知特征描述符f及其候選子模型組c=(df1df2…dfm)，若從中選取的一個含有k(k≤m)個子模型的子集(k-candidate sub-model，KCM)ck能夠使得

|ck|=k，ck?c

(6)

取得最大值，那么該子集ck被稱為有效子模型(valid sub-model，VM)組，記為vm．

這里diff(·)表示ck中兩兩子模型之間主方向夾角累加和，F(·)表示任意兩個高斯子模型間主方向向量夾角的度量函數，定義為

(7)

其中pi為di的主方向向量．

為了克服原始Fisher向量編碼方法的不足，在編碼階段，KDN-FV編碼方法僅利用每一個描述符鄰接的高斯子模型來進行編碼，同時需要這些子模型的拓撲結構存在著較大差異．也就是說，KDN-FV編碼方法在進行編碼時，首先要確定每一個局部描述符的有效子模型組．為此，本文提出了一種構建有效子模型組的方法．

已知一個特征描述符fi及其所對應的候選子模型組ci=(di1di2…dim)，進而可以得到一個m×m的矩陣a，其中aij=F(di，dj)，1≤i，j≤m．假設y是一個m維指示向量，可用來指出ci中的子模型是否屬于vmi，即：

(8)

(9)

式(9)是一個k密集近鄰求解問題，可由文獻[17]中給出的方法求得．

通過求解式(9)，可以獲得描述符fi的有效子模型組vmi．此后，對于圖像中的每一個描述符fi，KDN-FV編碼方法僅用其對應vmi中的高斯子模型進行Fisher向量編碼，并將所有描述符的編碼結果按照原始Fisher向量編碼的方式匯集在一起，由此構成圖像的KDN-FV表示向量．

2.3 KDN-FV編碼方法的主要步驟

輸入：圖像I的局部特征描述符集合f=(f1

f2…fl)

視覺字典d=(d1d2…dn)

候選子模型組參數m，有效子模型組參數k

輸出：圖像I的KDN-FV編碼向量kfv

子模塊1：計算集合D中每一個描述符的KDN-FV編碼

fori=1，2，…，l

步驟1.1利用KNN算法計算描述符fi的候選子模型組ci

indexi←KNN(fi，d，m)

ci←d[indexi]

步驟1.2依據式(7)計算描述符fi所對應的矩陣ai，

foro=1，2，…，m

forq=1，2，…，m

go，gq←ci(o)，ci(q)

%分別提取ci中的第o和第q個元素

aioq←F(di，dj)

%依據式(7)進行計算

end

end

步驟1.3通過求解式(9)，計算描述符fi的指示向量yi

yi←KDN(ai，m，k)

步驟1.4依據向量yi確定fi的有效子模型組vmi

indexi←find(yi) %查找yi中非零元素對應的下標

vmi←ci[indexi]

步驟1.5根據vmi中的每一個子模型，利用式(5)對描述符fi進行Fisher向量編碼，從而得到fi的KDN-FV編碼kfvi

αi←fit(fi，vmi) %計算描述符fi在有效子模型中各個子空間上分配的權重

kfvi←FV(fi，vmi，αi) %對描述符di進行Fisher向量編碼

end

子模塊2：將向量kfvi(i=1，2，…，l)進行累加并求平均，得到圖像I的KDN-FV編碼向量kfv

kfv←sum(kfv1，kfv2，…，kfvl)/l

2.4 基于KDN-FV編碼方法的圖像分類過程

基于KDN-FV編碼方法的圖像分類過程的關鍵步驟如下：

(1)在訓練數據集中隨機選取一組圖像，并從每一幅圖像中提取局部特征．

(2)使用GMM方法將所收集的局部特征進行聚類，構建GMM字典．

(3)依次提取數據集中每一幅圖像的局部特征，依據已得到的GMM字典，采用2.3節的KDN-FV編碼方法對每一幅圖像進行編碼，從而構建圖像表達．

(4)利用訓練數據集中圖像的表達向量訓練SVM分類器．

(5)對新輸入的圖像進行局部特征提取，然后利用KDN-FV編碼方法進行編碼并構建圖像的表達向量，最后將圖像的表達向量輸入到分類器中進行判別，從而完成圖像分類．

3 實驗結果及分析

為了展示KDN-FV編碼方法的有效性，分別在15-Scene[26]、Pascal VOC 2007[27]、Caltech 101[28]、Caltech 256[29]以及MIT Indoor 67[30]5個數據集上對其進行驗證．圖2展示了相關數據集的圖像示例．

3.1 實驗參數設置

在實驗過程中，DenseSIFT描述符以及CNN局部特征被分別用來構建圖像表達．所有方法和實驗都利用VLFeat[31]、MatConvNet[32]工具包來完成．在DenseSIFT特征提取過程中，每隔4個像素進行一次采樣．同時，采用空間金字塔匹配(spatial pyramid matching，SPM)[33]方法，將圖像劃分為多個規則的矩形區域，這里選擇1×1、2×2以及3×1的3層模式．在識別階段，所有實驗都采用SVM線性分類器進行分類識別．

3.2 KDN-FV編碼方法關鍵參數的設置

采用與文獻[12，21-22]相同的策略，即采用交叉驗證的方式來確定KDN-FV編碼方法中參數n、m、k的取值．圖3所示為在采用DenseSIFT局部特征的情況下，n、m、k采用不同組合時，KDN-FV編碼方法在Pascal VOC 2007數據集上的分類精度．由圖所示，當n=256，m=20，k=15時，改進方法能夠取得較好的結果．

3.3 基于DenseSIFT特征的KDN-FV圖像表達

本節構建基于DenseSIFT特征的KDN-FV圖像表達，與經典ScSPM[11]、LLC[13]和FV[14]方法進行比較．此外，為了進一步驗證所提方法的有效性，與其他學者提出的局部Fisher向量編碼方法進行對比，如LGM[15]、SDFV[17]和SFV[18]．表1列出了相應的比較結果．

表1 基于DenseSIFT特征的KDN-FV圖像表達分類性能

在Pascal VOC 2007數據集上，從每類圖像中隨機抽取200幅進行訓練，然后在測試集上進行測試．由表1可以看出，KDN-FV編碼方法取得了64.6%的分類精度(n=256，m=20，k=15)，比ScSPM和LLC分別高出12.7%、7.0%；比原始Fisher向量編碼方法(FV)高出2.8%．與具有相似思路的改進方法相比，如SDFV、SFV，KDN-FV編碼方法依然有明顯優勢．

在Caltech 101數據集上，從每種類別中隨機選取30幅圖像進行訓練，剩余圖像用于測試．同時，相關參數依次設置為n=256，m=20，k=15．與其他編碼方法相比，KDN-FV編碼方法取得了更高的分類結果，比原始Fisher向量編碼方法高出1.9%．

此外，KDN-FV編碼方法在Caltech 256和15-Scene數據集上也取得了較好的分類結果．它優于原始Fisher向量編碼方法，并在兩個數據集上分別高出3.1%和1.6%．同時，與SDFV和LGM方法相比，KDN-FV在15-Scene數據集上的分類結果也有一定的提升．

3.4 基于CNN局部特征的KDN-FV圖像表達

將AlexNet[5]預訓練模型最后一個全連接層的輸出作為特征，并與3種不同的表達策略進行比較：(1)全局CNN特征，即直接使用全連接層的輸出作為圖像表達．(2)CNN多尺度無序匯集[34]，即multi-scale orderless pooling CNN(MOP-CNN)．這種方法以多尺度采樣的方式在圖像中提取CNN局部特征，并將這些特征進行VLAD或Fisher向量編碼，形成圖像表達．(3)CNN 多尺度金字塔匯集[35]，即multi-scale pyramid pooling CNN(MPP-CNN)．該方法以多尺度采樣的方式在圖像中提取CNN局部特征，并引入金字塔策略，最終將這些特征進行Fisher向量編碼，形成圖像表達．在實驗過程中，使用與待比較方法相同的采樣策略和設置進行CNN局部特征采樣，并用KDN-FV編碼代替對應的編碼方法來構建圖像表達．其中對于MOP-CNN(KDN-FV)以及MPP-CNN(KDN-FV)方法，所采用的參數設置為n=512，m=40，k=25．表2列出了相應的比較結果．

表2 基于CNN特征的KDN-FV圖像表達分類性能

從表2可以看出，當用KDN-FV編碼方法替代被比較方法中的編碼方法后，新構建的圖像表達具有更強的區分能力，這也說明了KDN-FV編碼方法同樣適用于CNN局部特征．

3.5 結果分析

從上述實驗結果可以看出，KDN-FV編碼方法既適用于DenseSIFT手工特征，也適用于由CNN網絡提取出來的深度特征．文獻[15，17-18]指出局部性約束的引入可以提升Fisher向量的區分能力．而KDN-FV在引入局部性約束的同時，又利用子模型拓撲結構的差異對視覺單詞進行了篩選．它在Pascal VOC 2007和Caltech 256數據集上分別取得了64.6%和55.2%的分類精度，進一步提升了Fisher向量的表達能力．由此可以看出所提方案的有效性．

3.6 時耗性能分析

與原始Fisher向量編碼方法相比，改進的KDN-FV編碼方法增加了單詞篩選步驟．為了分析KDN-FV編碼方法的時間復雜性，采用與文獻[14，21]相同的策略，比較了KDN-FV編碼方法與原始Fisher向量編碼方法的單幅圖像平均編碼時耗．在實驗過程中，從Pascal VOC 2007數據集中選取了1 000幅圖像，并將所有圖像縮放為200×200，字典中單詞個數為128．硬件配置為Intel i5 6 600 KB 3.5 GHz CPU，16 GB內存．經測試，Fisher向量編碼方法單幅圖像編碼時間約為1 530 ms，而KDN-FV則為1 317 ms．實驗表明，KDN-FV編碼方法的時耗較少，這是因為即使KDN-FV中增加了單詞篩選環節，但在編碼階段，KDN-FV將每一個局部特征僅僅投影到所篩選出的視覺單詞即可，而原始Fisher向量編碼方法需要計算所有視覺單詞上的投影．由于單個單詞的投影過程計算量較大，而KDN-FV編碼方法僅需計算部分投影，這就減少了該方法的編碼時間．

4 結 語

針對原始Fisher向量編碼方法在編碼過程中存在的全局編碼以及未考慮視覺單詞之間拓撲結構差異的問題，本文提出了一種基于k密集近鄰算法的局部Fisher向量編碼方法．該方法依據圖像特征空間的流形結構，利用k密集近鄰算法為每一個特征描述符篩選編碼時所需的高斯子空間．KDN-FV編碼方法在編碼過程中引入了局部性約束，并且考慮了子空間之間的異同性，克服了原始Fisher向量編碼方法存在的問題．通過在多個數據集上進行測試，結果顯示改進后的方法增強了圖像表達向量的區分能力，提升了分類精度，提高了編碼效率．