甘 玲,左永強(qiáng)
(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶 400065) (*通信作者電子郵箱zyq_cqupt@163.com)
基于快速低秩編碼與局部約束的圖像分類算法
甘 玲,左永強(qiáng)*
(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶 400065) (*通信作者電子郵箱zyq_cqupt@163.com)
針對(duì)快速低秩編碼算法存在特征重建誤差較大,以及特征間局部約束條件丟失的問題,提出一種強(qiáng)化局部約束的快速低秩編碼算法。首先,使用聚類算法對(duì)圖像中特征進(jìn)行聚類,得到局部相似特征集合及其對(duì)應(yīng)的聚類中心;其次,在視覺詞典中采取K最近鄰(KNN)策略查找聚類中心對(duì)應(yīng)的K個(gè)視覺單詞,并將其組成對(duì)應(yīng)的視覺詞典;最后,使用快速低秩編碼算法獲得局部相似特征集合對(duì)應(yīng)的特征編碼。改進(jìn)算法在Scene-15和Caltech-101圖像庫上的分類準(zhǔn)確率比快速低秩編碼算法提高4%到8%,編碼效率比稀疏編碼算法提高5~6倍。實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法使得局部相似特征具有相似編碼,從而更加準(zhǔn)確地表達(dá)圖像內(nèi)容,能有效提高分類準(zhǔn)確率及編碼效率。
圖像分類;局部約束;低秩編碼;特征編碼;相似特征
圖像分類在圖像檢索[1]、智能交通[2]等領(lǐng)域中有著普遍的應(yīng)用。目前,最為常見的是基于視覺詞袋(Bag of Visual Words, BoVW)模型[3]的圖像分類,該模型中特征編碼方案的有效性、準(zhǔn)確性和魯棒性在很大程度上決定了圖像分類的效果和性能,因此特征編碼方案的構(gòu)建成為本文的一個(gè)重要研究?jī)?nèi)容。
BoVW模型主要是將圖像中的視覺詞匯聚類得到視覺字典,然后采用矢量量化策略,統(tǒng)計(jì)每一幅圖像中視覺詞匯對(duì)應(yīng)的視覺字典基上出現(xiàn)的頻次,從而構(gòu)建視覺特征直方圖,用來表示對(duì)應(yīng)圖像的內(nèi)容。然而,在特征編碼的過程中,存在的圖像空間語義信息丟失的問題。為此Lazebnik等[4]提出了將特征空間信息加入到特征編碼中的空間金字塔匹配(Spatial Pyramid Matching, SPM)算法(BowSPM),該算法使得每一個(gè)待重構(gòu)特征的編碼有且僅有一個(gè)非零元素,因此存在編碼重構(gòu)誤差較大的問題。為了進(jìn)一步減少重構(gòu)誤差,獲得更為準(zhǔn)確的特征表達(dá),Yang等[5]提出了一種基于稀疏編碼(ScSPM)的分類算法,該算法分別對(duì)每個(gè)特征進(jìn)行單獨(dú)的稀疏重構(gòu),使用1范數(shù)約束編碼,并利用SPM算法與最大值聚合(max-pooling)獲取圖像的最終編碼。然而,由于稀疏編碼的不穩(wěn)定性,存在相似特征的編碼差別較大的問題,并且忽略了特征之間的群組信息,計(jì)算復(fù)雜度較高,編碼效率低。為此Peng等[6]提出了快速低秩編碼(LrrSPM)算法,LrrSPM將每個(gè)特征集投影到另一個(gè)特征空間,然后在新的特征空間中計(jì)算特征新的表示,從而降低計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果表明,LrrSPM比ScSPM編碼效率提升了25~29倍。但LrrSPM算法在編碼過程中對(duì)所有特征直接計(jì)算,忽略了特征之間的結(jié)構(gòu)相關(guān)性和局部約束性。
本文在快速低秩編碼的理論框架下加入特征之間的相關(guān)性和局部性信息,提出一種強(qiáng)化局部約束的快速低秩編碼算法,從而達(dá)到約束特征編碼、降低編碼量化誤差、增強(qiáng)編碼準(zhǔn)確性的目標(biāo)。與文獻(xiàn)[5-6]算法相比,本文算法在快速處理大規(guī)模圖像分類的情況下,仍保持較高的分類準(zhǔn)確率。
圖像中局部特征的近似編碼不僅能準(zhǔn)確地表達(dá)圖像內(nèi)容,而且能有效改善分類的準(zhǔn)確性。目前,大多數(shù)的編碼方案都是在BoVW模型的基礎(chǔ)上改進(jìn)擴(kuò)展,如:BowSPM[4]、ScSPM[5]、LrrSPM[6]、 局部約束線性編碼(LLC)[7]和拉普拉斯稀疏編碼(LScSPM)[8]等。本章主要對(duì)BowSPM、ScSPM和LrrSPM三種編碼方案進(jìn)行介紹。其中矩陣X=[x1,x2,…,xn]∈Rd×n表示從圖像I中提取到的n個(gè)d維局部特征矩陣(如尺度不變特征轉(zhuǎn)換(Scale Invariant Feature Transform, SIFT)特征[9]、方向梯度直方圖(Histogram of Oriented Gradient, HOG)特征[10]),X中的每一列xi代表圖像中的一個(gè)局部特征向量。由隨機(jī)選取的樣本特征聚類得到的k個(gè)聚類中心組成一個(gè)視覺字典矩陣D=[d1,d2,…,dk]∈Rd×k,向量di表示字典中的視覺詞匯。特征編碼矩陣C=[c1,c2,…,cn]∈Rk×n,ci是xi對(duì)應(yīng)的特征編碼系數(shù)。在特征聚合階段,使用SPM算法將每一個(gè)圖像分解成不同的尺度l=0,1,2,每一尺度的圖像塊個(gè)數(shù)是2l×2l,然后計(jì)算每一個(gè)塊內(nèi)的局部特征直方圖,最終將所有直方圖組合成一個(gè)向量來表示圖像I。
對(duì)于圖像中的一個(gè)局部特征xi使用矢量量化(Vector Quantization, VQ)方式編碼[4],其目標(biāo)函數(shù)如式(1)所示:
(1)
s.tCard(ci)=1
其中:‖·‖2代表2范數(shù);ci∈Rk是xi經(jīng)過編碼之后的向量成為字典D的系數(shù);約束條件Card(ci)=1使局部特征xi僅需要一個(gè)最近鄰的視覺詞匯編碼得到ci,因此向量ci僅含有一個(gè)非零項(xiàng),造成編碼過程中丟失過多圖像語義信息。
Yang等[5]提出ScSPM對(duì)xi進(jìn)行稀疏編碼,模型表達(dá)式如式(2)所示:
(2)
其中:‖·‖1是1范數(shù),表示向量元素的絕對(duì)值之和;λgt;0是懲罰因子,其大小直接影響ci的稀疏度。ScSPM的優(yōu)點(diǎn)是ci具有稀疏性,能夠以少量的非零項(xiàng)更好地表示xi,具有較小的重建誤差,加入特征之間的流形結(jié)構(gòu)信息,并結(jié)合線性支持向量機(jī)(Support Vector Machine, SVM)獲得了較高的分類準(zhǔn)確率。但ScSPM對(duì)特征的編碼是獨(dú)立進(jìn)行的,因此具有稀疏性的ci不能夠反映特征的結(jié)構(gòu)性。此外,稀疏編碼的計(jì)算復(fù)雜度較高,處理數(shù)量較多的圖像庫時(shí)存在耗時(shí)過多的問題。
Peng等[6]提出了LrrSPM算法,其目標(biāo)函數(shù)如式(3)所示:
(3)
s.tX=DC
其中:rank(C)表示矩陣C的秩。該模型通過解決秩最小化問題將特征之間的群組信息加入到編碼中,不僅增強(qiáng)了編碼的判別性、魯棒性以及模型的泛化能力,而且提高了編碼的效率,文獻(xiàn)[6]中的實(shí)驗(yàn)結(jié)果表明,LrrSPM的編碼效率比ScSPM高25~29倍。但是LrrSPM在編碼過程中忽略了特征之間的相關(guān)性和局部性信息,使得特征編碼不能準(zhǔn)確表達(dá)圖像內(nèi)容。
采用不同的編碼方案,對(duì)編碼施加不同的約束,目的是從有限的特征集中篩選出具有判別性的信息,使編碼向量能夠更加準(zhǔn)確地表達(dá)圖像內(nèi)容。因此,本文在快速低秩編碼[8]的基礎(chǔ)上,以圖像中局部信息的重要性大于稀疏性信息[7]的結(jié)論為依據(jù),提出了一種基于局部約束的快速低秩編碼的圖像分類算法。算法在原有表達(dá)圖像特征之間群組結(jié)構(gòu)性信息的基礎(chǔ)上,加入特征之間的相似性和局部性信息,使圖像中的局部相似特征具有相似的編碼。另外考慮到局部特征之間的結(jié)構(gòu)相關(guān)性,采用特征聚類的方法強(qiáng)化特征空間的一致性,進(jìn)一步減小特征重建誤差,并且在快速分類的基礎(chǔ)上提高了分類的準(zhǔn)確率。
為了使相似特征具有相似的編碼,獲取特征之間的相似性信息,本文算法對(duì)特征點(diǎn)矩陣X進(jìn)行聚類,得到k′個(gè)聚類中心,則將矩陣X劃分k′類,Xi表示聚類得到的第i類特征點(diǎn)矩陣,Xi∈Rd×l,i∈{1,2,…,k′},li是第i類特征矩陣的特征個(gè)數(shù)。此外,為了加入特征之間的局部性信息,并且進(jìn)一步約束相似特征具有相似編碼,本文算法根據(jù)得到的k′個(gè)聚類中心,以K最近鄰(KNearest Neighbor, KNN)策略為依據(jù),依次找到每一個(gè)特征聚類中心對(duì)應(yīng)的字典D中的k"個(gè)近鄰的視覺詞匯組成小字典Dk",改進(jìn)算法如圖1所示,其中特征矩陣X中的每一列代表一個(gè)特征向量,字典矩陣D中的每一列代表一個(gè)視覺詞匯,特征編碼Ci中的每一列代表對(duì)應(yīng)特征的編碼系數(shù)。
圖1 改進(jìn)算法示意圖
根據(jù)得到的Xi以及對(duì)應(yīng)的小字典Dk",采用快速低秩編碼算法求解編碼系數(shù)Ci,其中,則本文改進(jìn)算法模型可表示為式(4):
(4)
s.t.Xi=Dk"Ci
本文采用文獻(xiàn)[6]方法求解式(4),其最優(yōu)解可表示為式(5)。但是在實(shí)際求解過程中,使用的是D的偽逆,可表示為式(6):
(5)
其中D-1表示D的逆。
(6)
基于上述結(jié)果,可以得出式(7):
min{rank(Dk"),rank(Xi)}
(7)
(8)
其中:λgt;0是正則化參數(shù);I表示單位矩陣。最終得到的k′個(gè)Ci,并根據(jù)每一個(gè)特征聚類中心對(duì)應(yīng)的單個(gè)視覺詞匯在字典D中的位置,還原每一個(gè)Ci,形成矩陣C表示一幅圖像中對(duì)應(yīng)局部特征的編碼,則C是X在字典D上的具有稀疏性、局部性和相似性的低秩編碼。
本文算法具體流程如下:
1)輸入圖像I,字典D∈Rd×k,正則化參數(shù)λ。
2)提取圖像I中的SIFT特征點(diǎn),構(gòu)成特征矩陣X。
3)使用k均值(k-means)聚類算法對(duì)特征點(diǎn)矩陣X聚類,得到k′個(gè)聚類中心,以及每一個(gè)類包含的特征點(diǎn)Xi。
4)將得到的k′個(gè)特征中心分別查找字典D中對(duì)應(yīng)的k"個(gè)近鄰視覺詞匯,并且將k"個(gè)視覺詞匯組成小字典Dk"。
6)考慮到字典中存在的噪聲問題,使用式(9)并設(shè)定閾值ε剔除C中的一些無效數(shù)據(jù),cji=[c1i,c2i,…,cki]T通常ε=0.98。
(9)
8)輸出表示圖像I的最終向量zi。
為驗(yàn)證本文所提改進(jìn)算法的有效性,選擇兩個(gè)常用圖像庫進(jìn)行圖像分類實(shí)驗(yàn),分別是Scene-15圖像庫[4]和Caltech-101圖像庫[12]。本文所有實(shí)驗(yàn),特征提取階段均采用Dense SIFT提取每一幅圖像中所有大小為16×16圖像塊的局部特征,步長(zhǎng)為6。采用無監(jiān)督聚類算法隨機(jī)選取圖像庫中200 000個(gè)SIFT特征作為構(gòu)建過完備字典的訓(xùn)練樣本。編碼過程中的正則化參數(shù)λ主要是為了避免出現(xiàn)過擬合的問題,閾值ε主要是用于消除部分編碼誤差,根據(jù)文獻(xiàn)[6]中所述,本文的所有實(shí)驗(yàn)設(shè)置λ=0.7,ε=0.98。特征聚合階段,采用l=3層的空間金字塔匹配模型(SPM)并結(jié)合max-pooling算法形成一幅圖像的最終表示向量。在分類階段,采用一對(duì)多的線性SVM作為分類器。為了獲取穩(wěn)定的分類結(jié)果,本文對(duì)所有圖像庫均進(jìn)行5次重復(fù)訓(xùn)練及測(cè)試,使用平均分類準(zhǔn)確率和平均編碼時(shí)間作為本文算法的評(píng)價(jià)指標(biāo)。
由于本文采用無監(jiān)督聚類方法分別對(duì)每一幅圖像中的所有特征聚類得到k′,以及使用KNN策略選取字典D中的k"個(gè)最近鄰視覺詞匯,為了觀察兩者之間的關(guān)系,在圖像庫Scene-15上,隨機(jī)選取每類的100幅圖像訓(xùn)練,其余作為測(cè)試圖像,設(shè)置k′=[20,30,40,50,60],k"=[20,30,40,50,60],得到k′和k"的關(guān)系如圖2所示,根據(jù)多組實(shí)驗(yàn)對(duì)比得出在k′=40,k"=40時(shí)本文算法能達(dá)到較好效果。
圖2 k′和k"在不同取值下的分類準(zhǔn)確率
Scene-15圖像庫中有15個(gè)場(chǎng)景,共計(jì)4 485幅圖像,包含辦公室、臥室、廚房和客廳等室內(nèi)場(chǎng)景,以及工廠、街道、森林、海岸、高速公路、原野和山脈等室外場(chǎng)景,每類場(chǎng)景包含圖像約200~400幅。實(shí)驗(yàn)過程中,訓(xùn)練字典D∈R128×1 024,隨機(jī)選取每類場(chǎng)景的100幅圖像作為訓(xùn)練圖像,剩余圖像作為測(cè)試圖像,實(shí)驗(yàn)結(jié)果如表1所示。
表1 不同算法對(duì)Scene-15圖像庫的分類準(zhǔn)確率及編碼時(shí)間對(duì)比
實(shí)驗(yàn)結(jié)果表明,本文算法的分類準(zhǔn)確率比LrrSPM算法提升了4.53%左右,比ScSPM算法提升了1%左右。而編碼時(shí)間比LrrSPM算法僅僅增加了36 s左右,但比ScSPM算法編碼效率提高了6倍左右。由于在場(chǎng)景分類中,每一類場(chǎng)景包含的信息都十分復(fù)雜而且非常豐富,本文算法通過加入特征之間的局部約束性信息,能較準(zhǔn)確地對(duì)場(chǎng)景中的有效特征進(jìn)行篩選編碼,并且使得特征編碼能夠較準(zhǔn)確地表達(dá)圖像內(nèi)容。因此本文算法與LrrSPM算法相比,能夠在編碼算法時(shí)間大致相當(dāng)?shù)那闆r下,顯著提高分類準(zhǔn)確率。與ScSPM算法相比,由于本文算法采用快速低秩編碼算法,編碼過程中主要是利用了F范數(shù)近似核范數(shù)的求解,F范數(shù)可直接求導(dǎo)得近似解,所以本文算法能夠在顯著降低編碼時(shí)間的情況下,仍然保持較高的分類準(zhǔn)確率。
Caltech-101圖像庫包含101類,共9 144幅圖像,如植物、動(dòng)物、交通工具和家具等類別,每類圖像包含31~800幅圖像。該圖像庫具有較大的類間變化及類內(nèi)變化,并且圖像自身更具多樣性和復(fù)雜性,因此該圖像庫是圖像分類中難度較高的數(shù)據(jù)庫之一。實(shí)驗(yàn)過程中訓(xùn)練字典D∈R128×2 048,隨機(jī)選取每類圖像的30幅作為訓(xùn)練圖像,其余作為測(cè)試圖像,實(shí)驗(yàn)結(jié)果如表2所示。
實(shí)驗(yàn)結(jié)果表明,本文算法比LrrSPM算法快50 s左右,并且本文算法的分類準(zhǔn)確率比LrrSPM提高了8%左右。與ScSPM算法相比,雖然分類準(zhǔn)確率降低了2%左右,但是編碼效率是ScSPM算法的5~6倍。在物體分類中,由于圖像的背景較為簡(jiǎn)單,噪聲較少,又因ScSPM算法是對(duì)單個(gè)特征單獨(dú)編碼,對(duì)于此種情況,ScSPM能夠較好地表達(dá)圖像中的物體信息,所以本文改進(jìn)的算法與ScSPM相比分類準(zhǔn)確率減少了1%左右。但是,本文算法實(shí)現(xiàn)了對(duì)圖像中局部相似特征的約束,剔除局部區(qū)域內(nèi)不相關(guān)的特征,使得特征編碼也能夠較準(zhǔn)確地表達(dá)圖像內(nèi)容,因此本文算法與LrrSPM算法相比不僅分類準(zhǔn)確率方面有顯著提高,并且編碼時(shí)間也有所減少。
表2 不同算法對(duì)Caltech-101圖像庫分類準(zhǔn)確率及編碼時(shí)間
由表1~2可知,本文算法在物體分類上的準(zhǔn)確率較高,由于加入特征的局部約束的條件,使得在場(chǎng)景分類上的準(zhǔn)確率更高。此外,在樣本數(shù)量增大一倍的情況下,本文改進(jìn)的編碼算法仍然具有較高的編碼效率。同時(shí),在數(shù)據(jù)量較大的情況下,本文算法編碼時(shí)間比LrrSPM有所降低,反映本文算法能夠較好地適應(yīng)較大規(guī)模的圖像分類問題。
本文在LrrSPM算法的基礎(chǔ)上,對(duì)LrrSPM算法中的編碼方式進(jìn)行改進(jìn),加入特征之間的相關(guān)性和局部性信息,實(shí)現(xiàn)了圖像的快速編碼,并且提升了編碼的一致性和準(zhǔn)確性,從而提高了分類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明,本文算法在物體圖像庫和場(chǎng)景圖像庫上都有較好的分類效果,然而相對(duì)于場(chǎng)景分類準(zhǔn)確率,物體分類效果欠佳。因此,在下一步的工作中將進(jìn)一步約束編碼方式以及增強(qiáng)字典的判別性,使特征編碼能夠更加準(zhǔn)確地表達(dá)圖像內(nèi)容,增強(qiáng)對(duì)物體分類的魯棒性,在保持較高編碼效率的情況下,進(jìn)一步提高分類的準(zhǔn)確率。同時(shí),也可以嘗試將本文算法應(yīng)用到模式識(shí)別的其他領(lǐng)域中,如人臉識(shí)別、人體行為識(shí)別等。
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。
國(guó)家自然科學(xué)基金資助項(xiàng)目(61272195)。
甘玲(1966—),女,重慶人,教授,碩士,主要研究方向:數(shù)字圖像處理、計(jì)算機(jī)視覺; 左永強(qiáng)(1990—),男,河南周口人,碩士研究生,主要研究方向:數(shù)字圖像分類。
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.