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

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

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

0 引 言

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

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

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

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

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

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

1 Fisher向量編碼方法

Fisher向量編碼方法的設(shè)計原理源自Fisher核理論，該理論能夠?qū)⑸墒侥Ｐ团c判別式模型緊密地結(jié)合起來．簡單地說，F(xiàn)isher核能夠利用一個生成模型的參數(shù)信息來定義一個核函數(shù)，進(jìn)而可以構(gòu)造一個分類器[25]．

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

(1)

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

(2)

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

(3)

(4)

其中

(5)

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

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

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

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

2.1 KDN-FV編碼方法的視覺字典構(gòu)造

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

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

假設(shè)d=(d1d2…dn)是由高斯混合模型方法構(gòu)成的含有n個單詞的視覺字典，集合p={p1，p2，…，pn}中包含了每一個單詞對應(yīng)的最大主成分向量．在KDN-FV編碼方法中，將局部描述符到高斯子模型均值向量之間的歐氏距離稱為描述符到子模型的距離．同時，任意兩個子模型di與dj的主方向向量夾角∠pipj被用來度量兩個子模型的拓?fù)浣Y(jié)構(gòu)差異性，∠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(xiàn)(·)表示任意兩個高斯子模型間主方向向量夾角的度量函數(shù)，定義為

(7)

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

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

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

(8)

(9)

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

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

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

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

f2…fl)

視覺字典d=(d1d2…dn)

候選子模型組參數(shù)m，有效子模型組參數(shù)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依據(jù)式(7)計算描述符fi所對應(yīng)的矩陣ai，

foro=1，2，…，m

forq=1，2，…，m

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

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

aioq←F(di，dj)

%依據(jù)式(7)進(jìn)行計算

end

end

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

yi←KDN(ai，m，k)

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

indexi←find(yi) %查找yi中非零元素對應(yīng)的下標(biāo)

vmi←ci[indexi]

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

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

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

end

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

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

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

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

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

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

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

(4)利用訓(xùn)練數(shù)據(jù)集中圖像的表達(dá)向量訓(xùn)練SVM分類器．

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

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

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

3.1 實驗參數(shù)設(shè)置

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

3.2 KDN-FV編碼方法關(guān)鍵參數(shù)的設(shè)置

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

3.3 基于DenseSIFT特征的KDN-FV圖像表達(dá)

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

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

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

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

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

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

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

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

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

3.5 結(jié)果分析

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

3.6 時耗性能分析

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

4 結(jié) 語

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