Equation Chapter 1 Section 1一種基于局部約束編碼抽取特征的圖像分類算法

摘要：針對(duì)傳統(tǒng)的抽取詞袋特征進(jìn)行非線性圖像分類時(shí)需要大量計(jì)算的問題，本文提出了一種基于局部約束編碼抽取特征的圖像分類算法來獲得分辨不同類別特征圖像，并通過在caltech-101 和caltech-256數(shù)據(jù)集上驗(yàn)證，結(jié)果表明本文算法在采用線性分類方法時(shí)能取得準(zhǔn)確率較高的分類結(jié)果。

關(guān)鍵詞：局部約束；抽取特征；圖像分類；線性分類

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599（2012）24-0031-03

隨著多媒體技術(shù)和數(shù)字信息技術(shù)的推廣和普及，數(shù)字圖像和視頻海量增長(zhǎng)。許多資料和文件通過圖像的形式來保存，這些圖像中包含了大量重要的信息，如何從海量的信息中檢索出自己感興趣的資料，是基于內(nèi)容的圖像信息檢索面臨的重大問題。圖像分類算法就是在這個(gè)背景下提出來的。

雖然人類的視覺系統(tǒng)能夠快速高效的分辨出圖像的類別，但是讓計(jì)算機(jī)正確理解圖像的內(nèi)容卻是一項(xiàng)復(fù)雜且具有挑戰(zhàn)的任務(wù)，這主要源自于“語(yǔ)義鴻溝”，即人的高層語(yǔ)義概念和計(jì)算機(jī)的低層圖像描述的差距，因此基于計(jì)算機(jī)視覺場(chǎng)景語(yǔ)義的研究成為當(dāng)前研究的熱點(diǎn)，總的來說歸納起來主要有三類：低層語(yǔ)義特征、中層語(yǔ)義特征和基于人類視覺模型的高層語(yǔ)義特征。Chang等[1]提取圖像的顏色和紋理兩種特征作為圖像的描述子，這種低層語(yǔ)義特征對(duì)圖片的大小和旋轉(zhuǎn)變化不敏感，但是顏色特征直方圖屬于全局的特征，無法表達(dá)像素之間的空間位置關(guān)系。對(duì)需要把紋理和顏色特征結(jié)合時(shí)又很難把握紋理和顏色特征的權(quán)重問題。這些都不利于對(duì)圖像的區(qū)分。在中層語(yǔ)義特征研究領(lǐng)域Lazebink和Schmid[2]提出了“詞袋”模型，主要思想是為圖像定義一組“視覺詞典”，然后求取每幅圖像中“視覺單詞”的分布情況作為圖像的特征。這種方法的詞典容量大，計(jì)算復(fù)雜。稀疏的模型是對(duì)人類視覺系統(tǒng)的模擬，Yang等[3]提取對(duì)圖像分塊后的SIFT特征對(duì)其進(jìn)行稀疏編碼，結(jié)合空間金字塔線性匹配的策略實(shí)現(xiàn)對(duì)圖像分類特征的抽取，具備較好的分類性能，但這種算法需要在碼本中全局的尋找最能表達(dá)特征的原子，由于碼本的原子數(shù)較大，因此在計(jì)算原始特征編碼時(shí)計(jì)算量較大。本文針對(duì)這一問題，提出了一種基于局約束編碼的特征抽取的圖像分類算法，在對(duì)圖像初始特征編碼時(shí)候考慮本原子的統(tǒng)計(jì)相關(guān)性，克服稀疏求解中為了追求稀疏性而可能用截然不同原子來表達(dá)相似特征的問題，根據(jù)在Caltech-101和Caltech-256數(shù)據(jù)集上驗(yàn)證，該算法在使用線性分類核的SVM分類器上都取得較好的實(shí)驗(yàn)結(jié)果。

1 基于人類視覺系統(tǒng)高層語(yǔ)義模型

人類視皮層V1的簡(jiǎn)單細(xì)胞的稀疏編碼模型[4] ，這種編碼的模型既符合生物進(jìn)化中的能量最小經(jīng)濟(jì)策略，又滿足電生理實(shí)驗(yàn)的結(jié)論。因此人們將這一視覺特性用在提取圖像分類特征的算法中，假設(shè)X為D維的從圖像中抽取的特征， .給出一個(gè)M列的碼本， ，這樣不同的原始特征在碼本中映射成為M維的編碼作為最后的特征，其中碼本B是過冗余的，即M>>D。求解編碼的過程就是在某種約束下求解公式（1）。

（1）

由于B是過完備的，因此方程有無窮多個(gè)解。解決這個(gè)問題需要加入正則項(xiàng)，在約束條件下求得唯一解。

1.1 傳統(tǒng)的量化方法

傳統(tǒng)的空間金字塔模型中采用矢量量化（Vector Quantization VQ）的方法解方程（2）：

（2）

這里 是X的編碼集。約束條件 表示只有一個(gè)不為零的元素在編碼 中用它來量化 。非負(fù)的 約束表示對(duì)x編碼的權(quán)值為1。我們通常用最鄰近查找的方法來確定這個(gè)非零的元素。由于只有碼本中的一個(gè)原子來表示特征向量的編碼，這種方法的誤差往往較大，在給圖像分類的時(shí)候要采用非線性的分類器來彌補(bǔ)這個(gè)誤差，而采用非線性的分類器往往帶來較大的計(jì)算量。

1.2 稀疏編碼的方法

為了改善矢量量化編碼中量化缺失的現(xiàn)象，文獻(xiàn)[2]將約束項(xiàng) 松弛為稀疏正則項(xiàng)。在稀疏編碼中，這些稀疏的元素可以通過 范數(shù)來查找，對(duì)每個(gè) 求解編碼即求解方程（3）：

（3）

由于碼本B通常是過完備的，也就是說M>>D，這里 正則項(xiàng)就保證了這個(gè)欠定方程有唯一的解。稀疏項(xiàng)突出了局部特征的顯著部分并且和VQ編碼方式相比誤差較小。但是稀疏編碼的約束項(xiàng)僅僅考慮了是最優(yōu)解達(dá)到稀疏的問題，沒有考慮到碼本中原子的統(tǒng)計(jì)相關(guān)性，稀疏編碼的方法需要在整個(gè)碼本中尋找最后的稀疏解，可能導(dǎo)致相似的圖像特征確要用截然不同的原子來表示。這種編碼方法可能給圖像分類帶來較大的誤差。

1.3 本文采用的編碼方法

本文提出了一種局部約束的線性編碼方式（Locality-constrained Linear Coding，LLC）。在文章中[5]，作者提出局部性比稀疏性更佳，且局部性必將是稀疏的，但是稀疏的并不一定有局部性。LLC編碼用局部約束來代替方程（3）中的稀疏約束，采用方程（4）來求解：

（4）

這里 代表元素的相乘， 是一個(gè)基向量和輸入特征i相似度自由度的控制因子。 用公式（5）來表示：

（5）

這里 ，并且 表示 和 之間的歐式距離。 用來表示局部控制因子下降速度的權(quán)值。通常把 進(jìn)行歸一化。約束項(xiàng) 是為了滿足LLC編碼的移動(dòng)不變性的要求。如圖1所示，LLC編碼捕捉到了相似的初始特征所共享原子（碼本的每一列為一個(gè)原子）表示的聯(lián)系。

在LLC編碼中，稀疏不是 范數(shù)中的概念，他的稀疏是說只有幾個(gè)有效的值。在實(shí)際中，設(shè)置閾值來限制那些系數(shù)很小的值。這種編碼方法考慮到了各個(gè)原子之間的統(tǒng)計(jì)關(guān)系，因此采用這種正則約束來求解的編碼具有較高的區(qū)分度，為下一步的分類奠定了良好地基礎(chǔ)。

圖1.Vector Quantization，稀疏編碼，LLC編碼的對(duì)比圖，用來表示初始特征的原子用黑色來表示（圖a，b，c分別表示表達(dá)特征向量的原子在碼本中的分布情況）

2 碼本的選擇

2.1 傳統(tǒng)求取碼本的方法

傳統(tǒng)的算法一般采用對(duì)訓(xùn)練樣本提取的初始特征進(jìn)行K-means聚類的方法獲得碼本。K-means 算法的工作過程說明如下：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下對(duì)象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù). k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。但是K-means算法的缺點(diǎn)也很大，產(chǎn)生類的大小相差不會(huì)很大，對(duì)于臟數(shù)據(jù)很敏感。而且這種方法的類心依賴于特征的密度。在越稠密的區(qū)域類心就越多，該性質(zhì)被認(rèn)為不利于構(gòu)造好的碼本[6]，因?yàn)樽畛３霈F(xiàn)的視覺特征往往對(duì)應(yīng)于信息量少的特征，比如平坦區(qū)域或者背景紋理等。

2.1 本文選用的訓(xùn)練碼本的方法

在本文中我們采用在線學(xué)習(xí)的方法來得到碼本。從碼本訓(xùn)練的過程中樣本的處理方法看來，學(xué)習(xí)碼本的構(gòu)造方式有兩種，批處理方式和在線學(xué)習(xí)的方式。大部分碼本（如K-SVD碼本訓(xùn)練方法）算法是二階批處理的過程：在每次迭代時(shí)總是一次訪問整個(gè)訓(xùn)練集，以便最小化某種約束條件下的代價(jià)函數(shù)。它比較適合小數(shù)據(jù)量或者能夠一次提供的訓(xùn)練樣本的場(chǎng)合，實(shí)驗(yàn)表明，二階迭代的批處理過程也比一階梯度下降法要快的多。但是批處理學(xué)習(xí)過程不能處理大的訓(xùn)練樣本集，也不能動(dòng)態(tài)地處理隨時(shí)間變化的樣本。碼本的在線學(xué)習(xí)在開始時(shí)候并不要求收集所有樣本，可以只在較小或者不完全的樣本集上訓(xùn)練碼本，他能隨著時(shí)間的推移自適應(yīng)地訓(xùn)練當(dāng)前最新的樣本。碼本的在線學(xué)習(xí)方式可以處理大的樣本集，動(dòng)態(tài)地生成能夠適應(yīng)不同環(huán)境的碼本原子。碼本優(yōu)化可以用方程（6）來表示：

（6）

方程（6）可以通過固定編碼時(shí)迭代的通過梯度下降的方法來優(yōu)化碼本，然后固定碼本，用同樣的方法來求出新的編碼。我們首先用k均值聚類的碼本來初始化碼本B。然后循環(huán)的通過訓(xùn)練所有特征來逐步更新碼本B。再每次迭代中，我們會(huì)選擇單個(gè)的樣本xi（或者是一小部分樣本）里然后求解方程（4）來得到當(dāng)前碼本下的LLC編碼。

3 實(shí)驗(yàn)結(jié)果

算法流程框圖如圖2所示：

圖2 本文算法流程框圖

在圖像數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩部分，用訓(xùn)練集上的特征訓(xùn)練冗余碼本，采用局部約束編碼投影的方法對(duì)測(cè)試集進(jìn)行分類。

我們采用Caltech-101和Caltech-265兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)證明算法的有效性。實(shí)驗(yàn)1.數(shù)據(jù)庫(kù)Caltech-101包括9144幅圖像，共101個(gè)類，包括動(dòng)物、車輛、花等，這些圖片在形狀上的變化很有特點(diǎn)。每類圖像有31-800幅不等。實(shí)驗(yàn)中通過取每類圖像中5，10，…..，30幅圖像訓(xùn)練2048個(gè)基的碼本進(jìn)行分類。圖像的原始特征用128維SIFT描述子，并把最后得到的特征放在三層金字塔上，采用SVM支持向量基的方法進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明LLC編碼的方法能取得更好的分類效果。詳細(xì)的結(jié)果如下表所示。另外我們的方法平均處理每幅圖像的時(shí)間只有0.24秒。

表1 在Caltech-101數(shù)據(jù)庫(kù)上的分類結(jié)果

訓(xùn)練數(shù)量

訓(xùn)練方法51015202530

矢量量化56.665.869.172.072.176.6

稀疏編碼54.464.970.473.375.377.6

本文61.169.765.377.480.683.4

表2 在Caltech-256上的分類結(jié)果

訓(xùn)練數(shù)量

訓(xùn)練方法15304560

矢量量化38.344.146.252.5

稀疏編碼37.744.047.450.1

本文43.351.255.357.6

實(shí)驗(yàn)2.在Caltech-256上進(jìn)行實(shí)驗(yàn)Caltech-256包括256個(gè)類，每個(gè)類至少有80幅圖像，一共30607幅圖像。這個(gè)數(shù)據(jù)庫(kù)比Caltech-101數(shù)據(jù)庫(kù)中的圖像在目標(biāo)尺寸，位置和姿勢(shì)上有更多的變化。在本實(shí)驗(yàn)中將每幅圖像裁剪成300*300像素的大小，并提取其128維SIFT特征作為原始特征，在每類圖像中取15，30，45，60幅圖進(jìn)行碼本的訓(xùn)練，訓(xùn)練的碼本維數(shù)是4096維。將提取的特征編碼后放在三層空間金字塔中進(jìn)行分類。從結(jié)果看，本文提出的LLC編碼方法取得了最好的效果，并且每幅圖像處理的平均時(shí)間是0.3秒。詳細(xì)的分類結(jié)果如表2所示。

4 結(jié)論

本文提出一種局部約束的線性抽取特征的算法，該算法一方面減少了特征量化時(shí)的誤差，另一方面是特征在碼本投影時(shí)相同的特征可以用近似的碼本原子來線性表達(dá)即同類的圖片得到的編碼近似，從而提高了分類的準(zhǔn)確性，即使用SVM的線性核來分類也可取得較好的分類效果。分類的精確性和碼本的構(gòu)造也有很大的關(guān)系，因此如何訓(xùn)練具有更高精度的碼本成為以后研究的重點(diǎn)。

參考文獻(xiàn)：

[1]Chang E，Goh K，Sychay G，Wu G.CBSA：content-based soft annotation for multimodal image retrieval using Bayes point machines.IEEE Transactions on Circuits and Systems for Video Techology，2003，13（1）：26-38.

[2]S.Lazebink，C.Schmid，and J.Ponce.Beyond bags of features：Spatial pyramid matching for recongnizing natural scene categories.Proc.of CVPR’06，2006.

[3]Yang J C，Yu K，Gong Y H，Huang T.Linear spatial pymaid matching using spare coding for image classification.In：Proceeding of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Miami，USA：IEEE.2009.1974-1801.

[4]F.Jurie，B.Triggs. Creating efficient codebooks for visual recognition.In proceedings of IEEE International Conference on Computer vision， volume1， pages604 -610，2005.

[5]K.Yu，T.Zhang，and Y.Gong.Nonlinear learning using local coordinate coding.Proc.of NIPS’09，2009.

[6]J.C.vanGemert，J.M.Geusebroek， C.J.Veenman， and A.W.M.Smeulders. Kernel codebooks for scene categorization.In Proceedings of European Conference on Computer Vision，2008.