基于快速低秩編碼與局部約束的圖像分類算法

甘 玲,左永強

(重慶郵電大學 計算機科學與技術學院,重慶 400065) (*通信作者電子郵箱zyq_cqupt@163.com)

基于快速低秩編碼與局部約束的圖像分類算法

甘 玲,左永強*

(重慶郵電大學 計算機科學與技術學院,重慶 400065) (*通信作者電子郵箱zyq_cqupt@163.com)

針對快速低秩編碼算法存在特征重建誤差較大,以及特征間局部約束條件丟失的問題,提出一種強化局部約束的快速低秩編碼算法。首先,使用聚類算法對圖像中特征進行聚類,得到局部相似特征集合及其對應的聚類中心;其次,在視覺詞典中采取K最近鄰(KNN)策略查找聚類中心對應的K個視覺單詞,并將其組成對應的視覺詞典;最后,使用快速低秩編碼算法獲得局部相似特征集合對應的特征編碼。改進算法在Scene-15和Caltech-101圖像庫上的分類準確率比快速低秩編碼算法提高4%到8%,編碼效率比稀疏編碼算法提高5～6倍。實驗結果表明,改進算法使得局部相似特征具有相似編碼,從而更加準確地表達圖像內容,能有效提高分類準確率及編碼效率。

圖像分類;局部約束;低秩編碼;特征編碼;相似特征

圖像分類在圖像檢索[1]、智能交通[2]等領域中有著普遍的應用。目前,最為常見的是基于視覺詞袋(Bag of Visual Words, BoVW)模型[3]的圖像分類,該模型中特征編碼方案的有效性、準確性和魯棒性在很大程度上決定了圖像分類的效果和性能,因此特征編碼方案的構建成為本文的一個重要研究內容。

BoVW模型主要是將圖像中的視覺詞匯聚類得到視覺字典,然后采用矢量量化策略,統計每一幅圖像中視覺詞匯對應的視覺字典基上出現的頻次,從而構建視覺特征直方圖,用來表示對應圖像的內容。然而,在特征編碼的過程中,存在的圖像空間語義信息丟失的問題。為此Lazebnik等[4]提出了將特征空間信息加入到特征編碼中的空間金字塔匹配(Spatial Pyramid Matching, SPM)算法(BowSPM),該算法使得每一個待重構特征的編碼有且僅有一個非零元素,因此存在編碼重構誤差較大的問題。為了進一步減少重構誤差,獲得更為準確的特征表達,Yang等[5]提出了一種基于稀疏編碼(ScSPM)的分類算法,該算法分別對每個特征進行單獨的稀疏重構,使用1范數約束編碼,并利用SPM算法與最大值聚合(max-pooling)獲取圖像的最終編碼。然而,由于稀疏編碼的不穩定性,存在相似特征的編碼差別較大的問題,并且忽略了特征之間的群組信息,計算復雜度較高,編碼效率低。為此Peng等[6]提出了快速低秩編碼(LrrSPM)算法,LrrSPM將每個特征集投影到另一個特征空間,然后在新的特征空間中計算特征新的表示,從而降低計算復雜度。實驗結果表明,LrrSPM比ScSPM編碼效率提升了25～29倍。但LrrSPM算法在編碼過程中對所有特征直接計算,忽略了特征之間的結構相關性和局部約束性。

本文在快速低秩編碼的理論框架下加入特征之間的相關性和局部性信息,提出一種強化局部約束的快速低秩編碼算法,從而達到約束特征編碼、降低編碼量化誤差、增強編碼準確性的目標。與文獻[5-6]算法相比,本文算法在快速處理大規模圖像分類的情況下,仍保持較高的分類準確率。

1 基于BoVW的圖像分類

圖像中局部特征的近似編碼不僅能準確地表達圖像內容,而且能有效改善分類的準確性。目前,大多數的編碼方案都是在BoVW模型的基礎上改進擴展,如:BowSPM[4]、ScSPM[5]、LrrSPM[6]、 局部約束線性編碼(LLC)[7]和拉普拉斯稀疏編碼(LScSPM)[8]等。本章主要對BowSPM、ScSPM和LrrSPM三種編碼方案進行介紹。其中矩陣X=[x1,x2,…,xn]∈Rd×n表示從圖像I中提取到的n個d維局部特征矩陣(如尺度不變特征轉換(Scale Invariant Feature Transform, SIFT)特征[9]、方向梯度直方圖(Histogram of Oriented Gradient, HOG)特征[10]),X中的每一列xi代表圖像中的一個局部特征向量。由隨機選取的樣本特征聚類得到的k個聚類中心組成一個視覺字典矩陣D=[d1,d2,…,dk]∈Rd×k,向量di表示字典中的視覺詞匯。特征編碼矩陣C=[c1,c2,…,cn]∈Rk×n,ci是xi對應的特征編碼系數。在特征聚合階段,使用SPM算法將每一個圖像分解成不同的尺度l=0,1,2,每一尺度的圖像塊個數是2l×2l,然后計算每一個塊內的局部特征直方圖,最終將所有直方圖組合成一個向量來表示圖像I。

1.1 空間金字塔編碼(BowSPM)

對于圖像中的一個局部特征xi使用矢量量化(Vector Quantization, VQ)方式編碼[4],其目標函數如式(1)所示:

(1)

s.tCard(ci)=1

其中:‖·‖2代表2范數;ci∈Rk是xi經過編碼之后的向量成為字典D的系數;約束條件Card(ci)=1使局部特征xi僅需要一個最近鄰的視覺詞匯編碼得到ci,因此向量ci僅含有一個非零項,造成編碼過程中丟失過多圖像語義信息。

1.2 線性稀疏編碼(ScSPM)

Yang等[5]提出ScSPM對xi進行稀疏編碼,模型表達式如式(2)所示:

(2)

其中:‖·‖1是1范數,表示向量元素的絕對值之和;λgt;0是懲罰因子,其大小直接影響ci的稀疏度。ScSPM的優點是ci具有稀疏性,能夠以少量的非零項更好地表示xi,具有較小的重建誤差,加入特征之間的流形結構信息,并結合線性支持向量機(Support Vector Machine, SVM)獲得了較高的分類準確率。但ScSPM對特征的編碼是獨立進行的,因此具有稀疏性的ci不能夠反映特征的結構性。此外,稀疏編碼的計算復雜度較高,處理數量較多的圖像庫時存在耗時過多的問題。

1.3 快速低秩編碼(LrrSPM)

Peng等[6]提出了LrrSPM算法,其目標函數如式(3)所示:

(3)

s.tX=DC

其中:rank(C)表示矩陣C的秩。該模型通過解決秩最小化問題將特征之間的群組信息加入到編碼中,不僅增強了編碼的判別性、魯棒性以及模型的泛化能力,而且提高了編碼的效率,文獻[6]中的實驗結果表明,LrrSPM的編碼效率比ScSPM高25～29倍。但是LrrSPM在編碼過程中忽略了特征之間的相關性和局部性信息,使得特征編碼不能準確表達圖像內容。

2 本文算法

采用不同的編碼方案,對編碼施加不同的約束,目的是從有限的特征集中篩選出具有判別性的信息,使編碼向量能夠更加準確地表達圖像內容。因此,本文在快速低秩編碼[8]的基礎上,以圖像中局部信息的重要性大于稀疏性信息[7]的結論為依據,提出了一種基于局部約束的快速低秩編碼的圖像分類算法。算法在原有表達圖像特征之間群組結構性信息的基礎上,加入特征之間的相似性和局部性信息,使圖像中的局部相似特征具有相似的編碼。另外考慮到局部特征之間的結構相關性,采用特征聚類的方法強化特征空間的一致性,進一步減小特征重建誤差,并且在快速分類的基礎上提高了分類的準確率。

2.1 算法原理

為了使相似特征具有相似的編碼,獲取特征之間的相似性信息,本文算法對特征點矩陣X進行聚類,得到k′個聚類中心,則將矩陣X劃分k′類,Xi表示聚類得到的第i類特征點矩陣,Xi∈Rd×l,i∈{1,2,…,k′},li是第i類特征矩陣的特征個數。此外,為了加入特征之間的局部性信息,并且進一步約束相似特征具有相似編碼,本文算法根據得到的k′個聚類中心,以K最近鄰(KNearest Neighbor, KNN)策略為依據,依次找到每一個特征聚類中心對應的字典D中的k"個近鄰的視覺詞匯組成小字典Dk",改進算法如圖1所示,其中特征矩陣X中的每一列代表一個特征向量,字典矩陣D中的每一列代表一個視覺詞匯,特征編碼Ci中的每一列代表對應特征的編碼系數。

圖1 改進算法示意圖

根據得到的Xi以及對應的小字典Dk",采用快速低秩編碼算法求解編碼系數Ci,其中,則本文改進算法模型可表示為式(4):

(4)

s.t.Xi=Dk"Ci

本文采用文獻[6]方法求解式(4),其最優解可表示為式(5)。但是在實際求解過程中,使用的是D的偽逆,可表示為式(6):

(5)

其中D-1表示D的逆。

(6)

基于上述結果,可以得出式(7):

min{rank(Dk"),rank(Xi)}

(7)

(8)

其中:λgt;0是正則化參數;I表示單位矩陣。最終得到的k′個Ci,并根據每一個特征聚類中心對應的單個視覺詞匯在字典D中的位置,還原每一個Ci,形成矩陣C表示一幅圖像中對應局部特征的編碼,則C是X在字典D上的具有稀疏性、局部性和相似性的低秩編碼。

2.2 改進算法的流程

本文算法具體流程如下:

1)輸入圖像I,字典D∈Rd×k,正則化參數λ。

2)提取圖像I中的SIFT特征點,構成特征矩陣X。

3)使用k均值(k-means)聚類算法對特征點矩陣X聚類,得到k′個聚類中心,以及每一個類包含的特征點Xi。

4)將得到的k′個特征中心分別查找字典D中對應的k"個近鄰視覺詞匯,并且將k"個視覺詞匯組成小字典Dk"。

6)考慮到字典中存在的噪聲問題,使用式(9)并設定閾值ε剔除C中的一些無效數據,cji=[c1i,c2i,…,cki]T通常ε=0.98。

(9)

8)輸出表示圖像I的最終向量zi。

3 實驗結果及分析

3.1 實驗環境及參數設置

為驗證本文所提改進算法的有效性,選擇兩個常用圖像庫進行圖像分類實驗,分別是Scene-15圖像庫[4]和Caltech-101圖像庫[12]。本文所有實驗,特征提取階段均采用Dense SIFT提取每一幅圖像中所有大小為16×16圖像塊的局部特征,步長為6。采用無監督聚類算法隨機選取圖像庫中200 000個SIFT特征作為構建過完備字典的訓練樣本。編碼過程中的正則化參數λ主要是為了避免出現過擬合的問題,閾值ε主要是用于消除部分編碼誤差,根據文獻[6]中所述,本文的所有實驗設置λ=0.7，ε=0.98。特征聚合階段,采用l=3層的空間金字塔匹配模型(SPM)并結合max-pooling算法形成一幅圖像的最終表示向量。在分類階段,采用一對多的線性SVM作為分類器。為了獲取穩定的分類結果,本文對所有圖像庫均進行5次重復訓練及測試,使用平均分類準確率和平均編碼時間作為本文算法的評價指標。

由于本文采用無監督聚類方法分別對每一幅圖像中的所有特征聚類得到k′,以及使用KNN策略選取字典D中的k"個最近鄰視覺詞匯,為了觀察兩者之間的關系,在圖像庫Scene-15上,隨機選取每類的100幅圖像訓練,其余作為測試圖像,設置k′=[20,30,40,50,60],k"=[20,30,40,50,60],得到k′和k"的關系如圖2所示,根據多組實驗對比得出在k′=40,k"=40時本文算法能達到較好效果。

圖2 k′和k"在不同取值下的分類準確率

3.2 Scene-15圖像庫

Scene-15圖像庫中有15個場景,共計4 485幅圖像,包含辦公室、臥室、廚房和客廳等室內場景,以及工廠、街道、森林、海岸、高速公路、原野和山脈等室外場景,每類場景包含圖像約200～400幅。實驗過程中,訓練字典D∈R128×1 024,隨機選取每類場景的100幅圖像作為訓練圖像,剩余圖像作為測試圖像,實驗結果如表1所示。

表1 不同算法對Scene-15圖像庫的分類準確率及編碼時間對比

實驗結果表明,本文算法的分類準確率比LrrSPM算法提升了4.53%左右,比ScSPM算法提升了1%左右。而編碼時間比LrrSPM算法僅僅增加了36 s左右,但比ScSPM算法編碼效率提高了6倍左右。由于在場景分類中,每一類場景包含的信息都十分復雜而且非常豐富,本文算法通過加入特征之間的局部約束性信息,能較準確地對場景中的有效特征進行篩選編碼,并且使得特征編碼能夠較準確地表達圖像內容。因此本文算法與LrrSPM算法相比,能夠在編碼算法時間大致相當的情況下,顯著提高分類準確率。與ScSPM算法相比,由于本文算法采用快速低秩編碼算法,編碼過程中主要是利用了F范數近似核范數的求解,F范數可直接求導得近似解,所以本文算法能夠在顯著降低編碼時間的情況下,仍然保持較高的分類準確率。

3.3 Caltech-101圖像庫

Caltech-101圖像庫包含101類,共9 144幅圖像,如植物、動物、交通工具和家具等類別,每類圖像包含31～800幅圖像。該圖像庫具有較大的類間變化及類內變化,并且圖像自身更具多樣性和復雜性,因此該圖像庫是圖像分類中難度較高的數據庫之一。實驗過程中訓練字典D∈R128×2 048,隨機選取每類圖像的30幅作為訓練圖像,其余作為測試圖像,實驗結果如表2所示。

實驗結果表明,本文算法比LrrSPM算法快50 s左右,并且本文算法的分類準確率比LrrSPM提高了8%左右。與ScSPM算法相比,雖然分類準確率降低了2%左右,但是編碼效率是ScSPM算法的5～6倍。在物體分類中,由于圖像的背景較為簡單,噪聲較少,又因ScSPM算法是對單個特征單獨編碼,對于此種情況,ScSPM能夠較好地表達圖像中的物體信息,所以本文改進的算法與ScSPM相比分類準確率減少了1%左右。但是,本文算法實現了對圖像中局部相似特征的約束,剔除局部區域內不相關的特征,使得特征編碼也能夠較準確地表達圖像內容,因此本文算法與LrrSPM算法相比不僅分類準確率方面有顯著提高,并且編碼時間也有所減少。

表2 不同算法對Caltech-101圖像庫分類準確率及編碼時間

由表1～2可知,本文算法在物體分類上的準確率較高,由于加入特征的局部約束的條件,使得在場景分類上的準確率更高。此外,在樣本數量增大一倍的情況下,本文改進的編碼算法仍然具有較高的編碼效率。同時,在數據量較大的情況下,本文算法編碼時間比LrrSPM有所降低,反映本文算法能夠較好地適應較大規模的圖像分類問題。

4 結語

本文在LrrSPM算法的基礎上,對LrrSPM算法中的編碼方式進行改進,加入特征之間的相關性和局部性信息,實現了圖像的快速編碼,并且提升了編碼的一致性和準確性,從而提高了分類準確率。實驗結果表明,本文算法在物體圖像庫和場景圖像庫上都有較好的分類效果,然而相對于場景分類準確率,物體分類效果欠佳。因此,在下一步的工作中將進一步約束編碼方式以及增強字典的判別性,使特征編碼能夠更加準確地表達圖像內容,增強對物體分類的魯棒性,在保持較高編碼效率的情況下,進一步提高分類的準確率。同時,也可以嘗試將本文算法應用到模式識別的其他領域中,如人臉識別、人體行為識別等。

References)

[1] HONG R, TANG J, TAN H K, et al. Beyond search: event-driven summarization for Web videos [J]. ACM Transactions on Multimedia Computing Communications and Applications, 2011, 7(4): 702-715.

[2] HUANG Y, WU Z, WANG L, et al. Feature coding in image classification: a comprehensive study [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(3): 493-506.

[3] CSURKA G, DANCE C R, FAN L, et al. Visual categorization with bags of keypoints [EB/OL]. [2017- 01- 10]. http://www.europe.naverlabs.com/content/download/23625/171397/version/1/file/2004_010.pdf.

[4] LAZEBNIK S, SCHMID C, PONCE J. Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[C]// Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2006: 2169-2178.

[5] YANG J, YU K, GONG Y, et al. Linear spatial pyramid matching using sparse coding for image classification[C]// CVPR 2009: Proceedings of the 2009 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2009: 1794-1801.

[6] PENG X, YAN R, ZHAO B, et al. Fast low rank representation based spatial pyramid matching for image classification [J]. Knowledge-Based Systems, 2015, 90(12): 14-22.

[7] WANG J, YANG J, YU K, et al. Locality-constrained linear coding for image classification[C]// CVPR 2010: Proceedings of the 2010 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3360-3367.

[8] GAO S, TSANG W H, CHIA L T, et al. Local features are not lonely — Laplacian sparse coding for image classification[C]// CVPR 2010: Proceedings of the 2010 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3555-3561.

[9] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[10] DALAL N, TRIGGS B. Histograms of oriented gradients for human detection [C]// CVPR 2005: Proceedings of the 2005 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2005: 886-893.

[11] ZHANG H, YI Z, PENG X. FlRR: fast low-rank representation using Frobenius-norm [J]. Electronics Letters, 2014, 50(13): 936-938.

[12] FEIFEI L, FERGUS R, PERONA P. One-shot learning of object categories [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 594-611.

Imageclassificationalgorithmbasedonfastlowrankcodingandlocalconstraint

GAN Ling, ZUO Yongqiang*

(CollegeofComputerScienceandTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Aiming at the problem of large feature reconstruction error and local constraint loss between features in fast low rank coding algorithm, an enhanced local constraint fast low rank coding algorithm was put forward. Firstly, the clustering algorithm was used to cluster the features in the image, and obtain the local similarity feature set and the corresponding clustering center. Secondly, theKvisual words were found by using theKNearest Neighbor (KNN) strategy in the visual dictionary, and then theKvisual words were combined into the corresponding visual dictionary. Finally, the corresponding feature code of the local similarity feature set was obtained by using the fast low rank coding algorithm. On Scene-15 and Caltech-101 image datasets, the classification accuracy of the modified algorithm was improved by 4% to 8% compared with the original fast low rank coding algorithm, and the coding efficiency was improved by 5 to 6 times compared with sparse coding. The experimental results demonstrate that the modified algorithm can make local similarity features have similar codes, so as to express the image content more accurately, and improve the classification accuracy and coding efficiency.

image classification; local constraint; low rank coding; feature coding; similar feature

2017- 04- 05;

2017- 06- 17。

國家自然科學基金資助項目(61272195)。

甘玲(1966—),女,重慶人,教授,碩士,主要研究方向:數字圖像處理、計算機視覺; 左永強(1990—),男,河南周口人,碩士研究生,主要研究方向:數字圖像分類。

1001- 9081(2017)10- 2912- 04

10.11772/j.issn.1001- 9081.2017.10.2912

TP391.41

A

This work is partially supported by the National Natural Science Foundation of China (61272195).

GANLing, born in 1966, M. S., professor. Her research interests include digital image processing, computer vision.

ZUOYongqiang, born in 1990, M. S. candidate. His research interests include digital image classification.