基于構造空間金字塔度量矩陣的圖像分類算法

李青彥,彭進業,李 展

(1.西北工業大學 電子信息學院, 陜西 西安 710072;2.西北大學 信息科學與技術學院, 陜西 西安 710127)

詞袋(Bag of words，BOW)被廣泛地應用到圖像分類技術中,是圖像分類技術中最有效的算法之一。就如何提高詞袋算法性能，學者們提出了多種算法,如碼詞和描述子共現的通用模型方法[1-4]，以及用于取代無監督K-means聚類的碼書判別學習方法[5-8]等。尤其需要注意的是,Grauman[9]提出了金字塔匹配核函數，該方法對特征空間進行網格分割,分成不同層次,利用不同的權重組合計算SIFT特征相似性,進而對圖像進行分類。鑒于金字塔匹配核函數并沒有充分考慮圖像特征的空間位置,Lazebnik[10]進而提出了空間金字塔匹配算法(Spatial pyramid matching,SPM)。

在實際應用中,SPM仍然存在如下問題。一方面,SPM算法使用了SIFT(Scale-invariant feature transform,SIFT)[11]算法提取圖像特征。SIFT在尺度空間利用高斯差分檢測算子,對特征點的梯度位置和方向都作了相應的量化, 具有平移、 尺度和旋轉不變性, 是對圖像局部特征的一種描述方式。 但是, SIFT算法主要針對灰度圖像進行特征提取, 忽略了圖像的顏色信息和光照信息。 另一方面, SPM算法使用了非線性分類器進行圖像分類。 若樣本數量為n, 則訓練集和測試集的復雜度分別為O(n3)和O(n)。 顯然, 該方法在處理大規模圖像集時會消耗大量的計算機資源。 為了解決該問題, 一些研究者開始使用線性分類器取代非線性分類器來進行圖像分類處理， 如ScSPM(SPM on Sparse coding)方法[14]、LLC (Locality-constrained linear coding)方法[15]、基于流形的特征詞典生成算法[16]、多核學習的核矩陣方法[17]、規范割對聚類特征詞方法[18]、拉普拉斯非負稀疏編碼方法(LNNSC)[19]，Zou等[20]提出的將圖像局部特征和全局特征融合的分類算法(LGP,Local-global fusion)，Peng等[20]提出的通過對圖像局部特征點進行哈希編碼來提高編碼速度和精度算法等,這些方法均是對特征點進行聚類獲得特征詞典,然后應用不同方法進行特征編碼,在一定程度上提高了圖像分類精度。但是,這些方法都沒有考慮詞典單詞之間的相關性,圖像集內部各子類的分類效果差異較大。

針對以上兩個問題,本文提出了一種基于構造空間金字塔度量矩陣的圖像分類算法。其特點在于，在圖像視覺單詞相關性建立方面,充分考慮圖像視覺單詞的空間關系,建立了鄰接矩陣模型,從而保證線性分類器的使用;在圖像底層特征提取方面,通過對比實驗,發現使用融合了顏色特征的CSIFT(Colored SIFT)[12]比SIFT具有更好的分類效果。文獻[13]提出的CSIFT將顏色信息加入到了SIFT的特征集中,使得CSIFT特征同時具有顏色和尺度不變性。而且,同一圖像中獲得的CSIFT特征數量平均是SIFT特征數量的1.94倍。同時,文獻[21]建立了基于鄰接矩陣的全文索引模型,在大規模文本索引中表現優異,提高了查詢效率。

本文算法步驟流程為：首先，提取融合了圖像顏色特征的CSIFT特征,進而獲取圖像特征的聚類中心；然后，對這些中心進行有向圖建模,用鄰接矩陣對聚類中心進行連通度測量,建立基于鄰接矩陣度量的圖像詞典；最后，使用線性分類器進行圖像分類。由于本文提出的方法考慮到了圖像詞典的空間關系,同時兼顧了圖像的全局顏色特征和局部位置特征,提取的特征具有顏色、旋轉、位置不變性。通過在Caltech-101圖像庫實驗驗證可得，本文算法提高了分類精度,尤其對彩色自然場景的圖像具有更好的分類效果。

1 基于鄰接矩陣的圖像不變特征詞典算法

本文首先使用融合了顏色特征和空間尺度不變特性的CSIFT方法進行圖像底層特征提取,然后使用K-means聚類方法,獲取底層圖像特征聚類中心,接著建立由底層聚類特征中心構成的n階有向圖鄰接矩陣,通過將圖像特征向矩陣投影,建立圖像直方圖,獲得了圖像局部特征,最后選用線性核的支持向量機進行分類。算法主要步驟如圖1所示。

圖1 本文算法主要步驟Fig.1 The main step of the algorithm

1.1 獲取圖像底層特征

從圖像訓練集I中提取出由M個CSIFT特征組成的集合X,每一個圖像特征為D維向量,即

X=[x1,…,xM]T,X∈RM×D。

(1)

應用式(2)的K-means優化模型對特征進行特征向量量化，

(2)

其中,V=[v1,…,vK]T,代表K-means方法獲得的K個聚類中心,即視覺單詞詞典,每個聚類中心稱之為詞典的單詞?！ぁ硎鞠蛄康腖2范數,即兩個向量的歐氏距離。

用U=[u1,…,uM]T表示任一CSIFT圖像特征編碼結果,um為轉后的圖像特征,特征量化用式(3)進行計算，

(3)

其中,Card(um)=1要求um中只有一個元素是非零值;|um|=1表示um的1-范數必須是1,即um中所有元素的絕對值之和為1;um≥0要求um均為非負數。

進一步考慮到CSIFT特征的位置信息,用位置因子λ|dm·um|替換式(3)的約束條件Card(um)=1,式(3)就轉化成了式(4)，

(4)

(5)

特征點xi與詞典V的距離為

dist(xi,V)=[dist(xi,v1),…,dist(xi,vM)]T，

(6)

σ用來調節距離的取值范圍,在高斯函數中,其表示寬度參數。

1.2 鄰接矩陣建模

文獻[23]建立了基于鄰接矩陣的全文索引模型,在大規模文本索引中表現優異,提高了查詢效率。文獻[14-15]改進了圖像編碼方法,開始運用線性分類器進行分類,取得了很好的分類效果。雖然這些方法都是將圖像特征投影到多個聚類中心,但均沒有考慮特征聚類中心之間的關系。本文對特征聚類中心運用鄰接矩陣進行建模,獲得了視覺詞典的相似度矩陣,然后再進行空間金字塔匹配。與文獻[14-15]相比較,本文的方法考慮了圖像字典中基元素之間的關聯度。

1.2.1 鄰接矩陣 數據結構中,圖分為有向圖和無向圖兩種,本文主要討論有向圖的鄰接矩陣。

有向圖D=〈V,E〉,其中,V={v1,v2,…,vn}代表圖的頂點,E代表各頂點的關系。鄰接矩陣Al表示D中長度為l的通路數，

即

Al=Al-1·A。

1.2.2 構建圖像特征詞典的鄰接矩陣 構造有向圖D=〈V,T〉,其中,詞典V={v1,v2,…,vn},T為n個向量之間的相似度矩陣,則有

(7)

其中,tij為向量vi到vj的相似度。

向量之間的相似度可以通過求解它們之間的距離來獲得。同時,為了使得相似的特征在編碼過程中有更大的權重,并使得矩陣T為稀疏矩陣，只求解vi與其k個最小近鄰的距離,其余均為0,即

tij=

(8)

其中，σ為高斯函數中的寬度參數,用來調節vi與vj距離的取值范圍,σ越大,函數越平滑,特征之間的差異性也就會越小。

式(8)表明,當兩個特征完全相同時,他們之間的相似度為1,完全不同時相似度為0。

令T(1)=T,我們稱T(1)為V的一階相似度矩陣。鄰接矩陣T(t)=T(t-1)T(1),T(t)就是V的t階相似度矩陣。

然后,對xi進行初始化，

yij=

(9)

其中,與文獻[24]的要求一樣,λ是歸一化因子,用來保證yi內各元素之和為1。

轉化后的圖像特征結果ui表示為

(10)

這樣,圖像的CSIFT特征最終轉化成了ui。然后,將圖像特征進行高分辨率的空間金字塔組合,最后得到表示圖像整體特征的向量。

由于隨著t值的增大,T(t)將不再稀疏,所以U也不是稀疏矩陣,這將給計算機帶來很大的開銷,尤其是對于大規模圖像集,嚴重降低了計算機的運算性能。因此,在具體實驗中對ui設置一個閾值e。由于小于這個閾值的元素對結果將產生非常小的影響,所以本文將其全部置為0,以保證U是稀疏矩陣。

2 實 驗

2.1 實驗概述

本文實驗所用計算機的配置為:CPU Corei5-3470雙核,主頻3.2GHz,內存4GB,顯存2GB。實驗所用圖像集為Caltech-101。Caltech-101圖像集有101類共計9 144幅圖像,每類圖像有40～800幅圖像,每幅圖像的尺寸大約為300×200像素。從每類中隨機選取10，15，25，30個訓練樣本,其余作為測試樣本,同時為了保證實驗的穩定性,每次實驗重復進行10次,取平均值和方差作為實驗的結果。

首先,把圖像分成16×16像素大小的圖像塊,圖像塊之間間隙為6個像素,使用 CSIFT 特征提取算法,將每個圖像塊進行向量量化。然后,利用K-means聚類獲得初始詞典,隨后利用本文提出的鄰接矩陣模型對圖像特征進行轉化,獲取每個圖像特征描述子um。接著,計算不同尺度空間的圖像特征,實驗中將圖像空間金字塔層級定為3層,即l=[0,1,2],這樣每一個圖像特征被空間金字塔方法轉化成了一個M維的向量U。

接著構造一個pooling函數:z=F(U)。這個函數對U的每一列進行計算,其每一列反映出了所有特征點與詞典中單詞的關系，本實驗采用了最大值函數，

zj=max{|u1j|,|u2j|,…,|uMj|}。

其中，uij是U的第i行j列的值,zj則是z的第j個元素。

2.2 實驗結果

鄰接矩陣階次n的取值與最終精度影響如圖2所示。其中，最小近鄰K=5，高斯核函數寬度參數σ=1，稀疏化參數e=0.01。從圖2可以看出,當鄰接矩陣階次n≤3時,分辨精度隨著n的增長而提高,n>3后,分類精度并沒有明顯的提升。

圖2 不同的鄰接矩陣階次n的取值對最終分辨精度的影響Fig.2 The effect of the order n elements value in the adjacency matrix on the final classification accuracy

本文對每類圖像分別隨機選取20幅和30幅訓練圖像,與其他分類方法進行比較。實驗發現,將經過鄰接矩陣優化過的詞典矩陣分別用于哈希編碼[22]和LLC方法,使用了基于鄰接矩陣的圖像詞典算法的分類精度獲得一定程度的提高，當最小近鄰K=5,鄰接矩陣階次n=3,高斯核函數寬度參數=1,稀疏化參數e=0.01時，本文算法與其他算法相比，分類精度如表1所示。

表1 本文與其他算法的分類精度對比Tab.1 Comparison of classification accuracy

本文的方法對于自然界中正常存在的圖像具有更好的分類效果。圖3列出了本文實驗所用的6種圖像，分別為水蓮、停止標示、比薩、羚羊、寶塔、金字塔。表2展示了本文與LLC方法在部分圖像類上的分類效果。水蓮、停止標示、比薩和羚羊4類圖像均為自然界中存在的彩色圖像,其分類效果好于LLC方法,CSIFT算子優于SIFT算子。在寶塔圖像集上,使用SIFT算子的鄰接矩陣分類方法和LLC方法的分類效果相同,使用了CSIFT算子后,由于增加了顏色和光照信息,分類效果有了明顯提升。對于含有電腦模擬或后期進行過再處理的圖像集(如圖3(f)金字塔),因為其包含了非自然界中正常存在的圖像,本文的分類效果稍差。

圖3 實驗用到的部分圖像示例Fig.3 Some image examples used in the experiment

圖像名稱算 法分類精度/%LLC28．57水蓮SIFT+鄰接矩陣85．71CSIFT+鄰接矩陣85．71LLC94．12停止標示SIFT+鄰接矩陣100CSIFT+鄰接矩陣100LLC82．61比薩SIFT+鄰接矩陣86．96CSIFT+鄰接矩陣91．31LLC85．11羚羊SIFT+鄰接矩陣87．05CSIFT+鄰接矩陣88．99LLC94．12寶塔SIFT+鄰接矩陣94．12CSIFT+鄰接矩陣98．88LLC74．07金字塔SIFT+鄰接矩陣62．96CSIFT+鄰接矩陣62．96

2.3 實驗相關參數取值對結果的影響

在鄰接矩陣模型中,參數取值涉及到訓練樣本數目、最小近鄰取值K、鄰接矩陣階次n、高斯核函數寬度參數σ和稀疏化參數e。

第二，教育者在對大學生進行思想政治教育的過程中，要積極推動思想政治工作傳統優勢同信息技術高度融合，拓寬社會主義核心價值觀教育的深度和廣度，讓社會主義核心價值觀內化于心，外化于行。并將優秀健康的價值觀及思想觀念的良好引導作用滲透到學生的日常生活及學習中，引導學生樹立正確的世界觀、人生觀、價值觀，做到以文化人。

實驗中,首先固定訓練樣本數目不變,然后變換其他參數,其中,最小近鄰K={3，5，7},鄰接矩陣階次n={1，2，3，4},高斯核函數寬度參數σ的取值{2，1，0.1，0.01},稀疏化參數e取值為{0.1,0.01,0.001}。各參數對實驗結果的影響情況為:

1)寬度參數σ太大或太小,分類精度都會降低。這是因為太大的寬度參數σ使得高斯函數變得平滑,相應特征之間的相似度度量取值趨向于1,同時如果寬度參數σ太小,則使得每個特征點變得孤立,與其他特征點的相似度趨近于0,使得算法還原成了沒有進行鄰接矩陣建模的情況,從而使本文算法失去了意義。

2)最小近鄰K取值越大,特征點與其他特征點的關聯度保留的越多。對于顯著特征相關性較強的圖像有更加強的分類能力,但同時會降低特征背景差異較大的圖像的分類能力。

3)鄰接矩陣階次n的取值越大,圖像特征點的相關性越強,算法對顯著特征相關性較強的圖像有更加強的分類能力，同時,其受稀疏化參數e的約束較為明顯。若稀疏化參數e取值越小,則鄰接矩陣階次n的取值對分類結果的影響越顯著,與此同時,矩陣稀疏化程度降低,運算消耗增加。

表3 CSIFT與SIFT特征提取時間平均消耗

Tab.3 The average cputime of extract features using CSIFT and SIFT ms

3 結 語

本文考慮了詞典中顯著特征之間的關系,利用鄰接矩陣的思想建立了詞典相似度矩陣。實驗證明,本文提出的方法應用在對圖像局部特征的各類改進算法中,能夠起到優化圖像詞典的作用;同時,本方法對圖像語義關聯緊密的圖像具有更高的分類精度,當使用了融合顏色和光照信息的底層特征CSIFT算子后,在自然界彩色圖像分類方面表現更為突出。但同時也看到,隨著圖像類型的增加,維度災難始終存在。實驗中,各參數的取值根據實驗經驗來尋找最優,并不能確保選取的參數為最優參數。如何將更多的圖像特征融合,并應用到圖像分類中,提高圖像分類精度，將是下一步研究的重點。

[1] BOIMAN O, SHECHTMAN E, IRANI M. In defense of Nearest-Neighbor based image classification[C]∥ IEEE Conference on Computer Vision and Pattern Recognition.IEEE, 2008:1-8.

[2] BOSCH A, ZISSERMAN A, MUOZ X. Scene classification using a hybrid generative/discriminative approach[J].IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 30(4):712.

[3] LI F F,PERONA P. A Bayesian hierarchical model for learning natural scene categories[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society，2005：524-531.

[4] QUELHAS P, MONAY F, ODOBEZ J M, et al. Modeling scenes with local descriptors and latent aspects[C]∥Tenth IEEE International Conference on Computer Vision. IEEE, 2005:883-890.

[5] YANG L,JIN R,SUKTHANKAR R, et al. Unifying discriminative visual codebook generation with classifier training for object category recognition[C]∥IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2008: 1-8.

[6] ELAD M,AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J].IEEE Transactions on Image Processing,2006,15(12): 3736-3745.

[7] MOOSMAN F,TRIGGS B,JURIE F. Randomized clustering forests for building fast and discriminative visual vocabularies[J].Advances in Neural Information Processing Systems,2006.

[8] FREDERIC J,TRIGGS B. Creating efficient codebooks for visual recognition[C]∥Tenth IEEE International Conference on Computer Vision. IEEE, 2005: 604-610.

[9] GRAUMAN K,DARRELL T. The pyramid match kernel: discriminative classification with sets of image features[C]∥Tenth IEEE International Conference on Computer Vision. IEEE, 2005: 1458-1465.

[10] LAZEBNIK S,SCHMID C,PONCE J. Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society , 2006: 2169-2178.

[11] LOWE D G. Object recognition from local scale-invariant features[C]∥The Proceedings of the Seventh IEEE International Conference on Computer Vision. IEEE,1999: 1150-1157.

[12] ABDELHAKIM A E, FARAG A A. CSIFT: A SIFT descriptor with color invariant characteristics[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 2006: 1978-1983.

[13] GEUSEBROEK J M, BOOMGAARD R V D, SMEULDERS A W M, et al. Color invariance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence, 2001, 23(12):1338-1350.

[14] YANG J,YU K,GONG Y,HUANG T. Linear spatial pyramid matching using sparse coding for image classification[C]∥IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009: 1794-1801.

[15] WANG J,YANG J,YU K,et al. Locality-constrained Linear coding for image classification[C]∥IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2010: 3360-3367.

[16] 章毓晉, 劉寶弟,王宇雄, 圖像分類中多流形上的詞典學習[J].清華大學學報(自然科學版), 2012，52(04): 575-579.

[17] 亓曉振,王慶.一種基于稀疏編碼的多核學習圖像分類方法[J].電子學報, 2012,40(4): 773-779.

[18] 丁鍇，陳偉海，吳星明，等.基于規范割的空間金字塔圖像分類算法[J].北京航空航天大學學報, 2013,39(10): 1342-1347.

[19] LI Qianqian,CAO Guo. Image classification based on laplacian non-negative sparse coding[J].Computer Engineering, 2013,39(11):240-244.

[20] ZOU J,LI W,CHEN C,DU Q. Scene classification using local and global features with collaborative representation fusion[J].Information Sciences, 2016,348:209-226.

[21] LINDE Y,BUZO A,GRAY R. An Algorithm for Vector Quantizer Design[J].IEEE Transactions on Communications, 1980, 28(1):84-95.

[22] PENG T, LI F. Image classification algorithm based on hash codes and space pyramid[J].Journal of Image & Graphics, 2016：114-118.

[23] 周水庚, 胡運發,關佶紅.基于鄰接矩陣的全文索引模型[J].軟件學報, 2002,13(10): 1933-1942.

[24] LIU L,WANG L,LIU X.In defense of soft-assignment coding[C]∥IEEE International Conference on Computer Vision. IEEE, 2011:2486-2493.