基于圖正則化與非負組稀疏的自動圖像標注

錢智明 鐘 平王潤生

(國防科技大學電子科學與工程學院 長沙 410073)

基于圖正則化與非負組稀疏的自動圖像標注

錢智明 鐘 平*王潤生

(國防科技大學電子科學與工程學院 長沙 410073)

設計一個穩健的自動圖像標注系統的重要環節是提取能夠有效描述圖像語義的視覺特征。由于顏色、紋理和形狀等異構視覺特征在表示特定圖像語義時所起作用的重要程度不同且同一類特征之間具有一定的相關性，該文提出了一種圖正則化約束下的非負組稀疏(Graph Regularized Non-negative Group Sparsity, GRNGS)模型來實現圖像標注，并通過一種非負矩陣分解方法來計算其模型參數。該模型結合了圖正則化與l2,1-范數約束，使得標注過程中所選的組群特征能體現一定的視覺相似性和語義相關性。在Corel5K和ESP Game等圖像數據集上的實驗結果表明：相較于一些最新的圖像標注模型，GRNGS模型的魯棒性更強，標注結果更精確。

圖像標注；圖正則化；組稀疏；非負矩陣分解

1 引言

隨著圖像獲取與存儲技術的不斷進步，圖像數據呈現井噴式增長。如何檢索這些圖像是當前計算機視覺領域的一大難題。一般而言，用戶傾向于用文本查找相關圖像，這使得自動圖像標注技術受到了研究者們的廣泛關注。然而，由于“語義鴻溝”的存在，自動圖 像標注是一件極具挑戰性的任務。這里的“語義鴻溝”主要體現在很難建立低層視覺特征與高層圖像語義之間的相互映射關系。由于高層語義所對應視覺內容往往非常復雜，這里主要從多類特征選擇和人的認知需求兩個方面來分析視覺特征對語義理解的影響。

由于圖像內容千變萬化，僅僅使用一類視覺特征往往不足以滿足不同圖像語義的需求，所以圖像通常由多類異構視覺特征所共同表示。然而，這種高維的混合圖像特征在表示圖像特定語義時往往是冗余的。因此，選擇一個合理而又緊湊的圖像表示方法將能夠大大地提高圖像標注的效率。在處理高維特征方面，稀疏表示被證明是極其有效的[1]。對于圖像標注而言，稀疏表示的意義主要體現在：盡管豐富的圖像內容需要由高維特征來表示，但屬于某一特定語義類別的圖像往往可以由若干低維空間的視覺特征來很好地描述。近年來，有很多圖像標注方法[2,3]都通過對特征系數施以l1-范數約束來兼顧模型誤差與特征系數的稀疏性，以獲取更加穩健和準確的標注結果。但是，這些方法僅考慮了各獨立特征對圖像標注的不同作用，而忽略了特征之間的相關性對標注結果的影響。一般情況下，同類特征之間往往相關性較大，而異類特征對某一圖像語義則往往表現出不同的描述能力。例如，紋理特征能夠很好地用于指紋識別，而形狀特征則對車輛檢測有著較好的效果。這也就是說，選擇合適的組群特征能夠更加有效地描述圖像語義。為此，組稀疏方法[4?8]結合了傳統稀疏表示的l1-范數約束與嶺回歸中的l2-范數約束，使得在針對某一圖像語義的特征組選擇上盡可能保持稀疏，而在用同類特征表示圖像時則使損失誤差盡可能小。例如，Wu等人[5]構建了一個結構化的稀疏選擇模型來應對圖像標注過程中的特征組選擇問題。Yang等人[6]則在此基礎上提出了一種拉普拉斯聯合組稀疏模型(Laplacian Joint Group Lasso, LJGL)，用于從訓練數據中重構圖像區域，并根據區域特性來賦予標注信息。考慮到圖像數據中的多層特征結構，Gao等人[7]提出了一種多層組稀疏編碼的方法來實現圖像分類與標注。最近，Jayaraman等人[8]將結構化組稀疏用于多任務學習，以此選擇判別性較強的特征類，從而保持具有一致性的特征間的相關性并降低非相關特征對結果的影響。Bahrampour等人[9]則將樹結構組稀疏方法用于多模分類，如多視角人臉識別，多傳感器目標分類等。此外，組稀疏方法在視頻[10]、文檔[11]以及網頁數據分析[12]上也有著極具前景的應用。這些方法表明組稀疏模型能夠提取最具相關性的低層特征組來對高層語義進行建模，大大提高了模型的學習效率與應用性能。

在人的認知需求方面，一些心理學和生理學上的證據表明：基于部件(part-based)的表示方法在一定程度上能夠很好地描述人類大腦的認知模式[13,14]。這里的部件可以指圖像的局部結構或目標的組成部分，也可以指視覺特征的部分屬性。這一結論為進一步描述圖像語義提供了有力理論支撐。非負矩陣分解(Non-negative Matrix Factorization, NMF)[13]就是一種典型的用于學習目標部件的方法。由于NMF在求解過程中只包含加性的而不含減性的矩陣運算，這與目標部件表示的過程相吻合，所以其結果能夠在一定程度上較好地表示目標部件。然而，NMF在處理數據時假設數據的分布是全局線性的，而沒有考慮數據的內蘊幾何結構，這就使得NMF在處理具有非線性流形結構的數據時其效果往往不盡人意。于是，一些研究工作開始關注流形子空間里的數據處理問題。其中，圖正則化[6,14]是研究數據流形結構的最重要的方法之一。這類方法一般假設：如果數據點在原空間是鄰近點，那么對應到新的基下也是鄰近點。根據這一假設，圖正則化與傳統的線性降維方法相比，能夠更好地保持數據的內在幾何結構。

本文提出了一種圖正則化約束下的非負組稀疏(Graph Regularized Non-negative Group Sparsity, GRNGS)模型來實現圖像標注。相較于以往的組稀疏模型，GRNGS模型考慮到了圖像視覺特征空間的流形結構和非負特征對圖像理解所起到的作用，并根據這些特性選擇符合人眼視覺且最具鑒別力的圖像特征，以實現更高效的圖像標注。同時，利用特征的非負性，該模型參數可通過非負矩陣分解來有效地求解。

2 本文方法

如圖1所示，整個標注框架由模型構建與模型測試兩部分組成。在模型構建過程中，我們根據多種異構視覺特征和圖像語義信息來訓練模型參數；在模型測試過程中，我們首先提取測試圖像的多種異構視覺特征，然后根據模型參數計算各語義標簽的后驗概率，并對所求概率進行排序以確定標注結果。

2.1 組稀疏模型

給定一圖像訓練集{(xi,yi)∈?p×{0,1}C, i=1,2,…,n}，其中xi=[xi1xi2…xip]T∈?p表示第i幅圖像的特征向量，yi=[yi1yi2…yiC]T∈{0,1}C表示第i幅圖像所對應的標注信息(即如果該圖像的標注信息中有標簽k，則yik=1；否則，yik=0)。圖像特征一般由多種異構視覺特征所組成，這里我們假設p維圖像特征中含有G組不同類別的特征。用mg表示第g組特征的維數，則有。于是，第i幅圖像的特征向量可重新表示為xi=。令X=[x1x2…xn]T為n×p的訓練特征矩陣，Y=[y1y2…yn]T為n×C的標注矩陣，則結合組稀疏方法的圖像標注問題可表示為

圖1 基于GRNGS模型的圖像標注框架

其中，λ＞0為組稀疏因子，B=[β1β2…βC], βk=[βk1βk2…βkp]T∈?p為標記標簽k時的系數矢量，βk,g為第g組特征所對應的系數矢量。該方法可通過調節λ選擇對標注問題有意義的特征組，即βk,g≠0，并根據這些特征組來建立圖像視覺特征與圖像語義間的映射關系。由于每一語義標簽所對應的特征系數各不相同，我們將上述矩陣求解問題進一步細分為標簽k所對應的矢量求解問題。

2.2 GRNGS模型

為了有效地利用圖像特征的組效應、流形結構的緊湊性和非負性，本文提出了一種GRNGS模型來實現圖像標注。流形是線性子空間的一種非線性推廣，我們也可以將流形看作是一個局部可坐標化的拓撲空間。要保持上一節所描述的圖像標注問題中流形結構的緊湊性，可根據圖正則化方法中較典型的拉普拉斯特征映射(Laplacian Eigenmap, LE)[14]來尋找一個最佳映射，使得下面的損失函數最小：

其中，σ為一帶寬參數，NK(·)表示K近鄰搜索函數。于是，引入模型參數的非負約束以及式(3)中的流形約束，我們可將式(2)中的標注問題改為

其中，λ1＞0為組稀疏參數，用以選擇合適的特征組；λ2＞0為圖正則化參數，用以控制模型結構的復雜度。

令

則式(5)可重寫為

對于一幅測試圖像xnew，根據式(6)中所求的βk獲得標簽k對該圖像的后驗概率：

對所有標簽的后驗概率進行降序排序，則可取后驗概率最大的若干標簽對該圖像進行標注。

2.3 模型優化

為了求解式(6)中的優化問題，本文提出一種非負矩陣分解算法。首先，我們定義拉格朗日函數：

其中，Φ=[φ1φ2…φp]T為拉普拉斯乘子。對式(8)求導，可得φiβki=0)，并使?L/?βk=0，可得

為了確保算法的收斂性，利用K.K.T.條件[14](即

其中，“?”表示Hadamard積[15]。于是，我們可得模型優化算法的非負迭代過程如下：

這里，矢量商a/b是指矢量a和b中各元素值的商。該優化算法的具體過程如下：

第1步 計算Π,Θ,Λg，令迭代次數t=0，初始化；

2.4 模型分析

由于Π,Θ在給定數據的情況下是固定的，其計算復雜度為O(n2p2)。在每次迭代過程中，分母項的計算復雜度為O(np+p2) ，分子項的計算復雜度為O(np2)，因而其每次迭代過程的計算復雜度為O(np2)，與圖像個數是線性相關的，這對于大規模數據庫的標注工作是極其有利的。另外，非負迭代過程的迭代次數與所求系數矢量的維數一般是成比例的，故總的計算復雜度為O(n2p2+np3C)。

3 實驗

本文實驗安排如下：首先，給出實驗數據和評價準則等信息；然后，對實驗參數進行了評估；最后，給出了GRNGS模型與其他模型在圖像標注上的性能對比結果。

3.1 實驗設置

本文采用的數據集包括：Corel5K數據集[16]和ESP Game數據集[17]，其詳細信息如表1所示。

表 1 實驗數據集詳細信息

在特征提取方面，按照特征屬性不同將特征分為不同組群。本文實驗所采用的特征維數共320維，具體描述如下：128維的CPAM(Colored Pattern Appearance Model)特征[18]，96維的RGB和HSV顏色直方圖特征(每個顏色通道提取16維特征)，32維的梯度和方向直方圖特征，64維的形狀特征[19]。對于每一特征，我們將其值轉換到區間[0,1]上來，并對轉換后的特征值進行歸一化處理，即?xi，有。

為了對標注結果進行合理評價，本文采用兩種評價策略：第一，固定每幅圖像的語義標簽數為5，計算查準率(Prec@5)和查全率(Rec@5)[18]；第二，針對不同的查全率，計算所有平均查準率的平均值(Mean Average Precision, MAP)：

此外，所有實驗均在Matlab 2010平臺上運行，實驗所用計算機的主頻為2.30 GHz, RAM內存為8 G。

3.2 模型參數對圖像標注的影響

GRNGS模型主要需考察3個參數：式(4)中的最近鄰參數K，式(6)中的組稀疏參數λ1和圖正則化參數λ2。由于最近鄰參數K與另外兩個參數的相關性較弱，我們將分開對其進行評估，并使用MAP來衡量各參數取值的實驗結果。首先，我們令K=100，并考察參數λ1和λ2。在本實驗中，我們對這兩參數分別取值{0.0001,0.001,0.01,0.1,1,10}。

圖2給出了GRNGS模型在不同參數設置下的標注結果。我們發現當λ1=λ2時，標注結果相對較好。在接下來的實驗中，我們選取標注結果最好的模型參數作為實驗參數，即在處理Corel5K和ESP Game數據集時分別選取參數λ1=λ2=0.1和λ1= λ2=0.01。

接下來，我們考察最近鄰參數K對實驗結果的影響。由圖3可知，在K值較小時，標注結果隨著K值的增加而逐步改善；而當K達到一定值時，標注結果的MAP值則相對穩定或略微呈下降趨勢。據此，我們在接下來的所有實驗中均令K=200。

圖2 GRNGS模型在不同組稀疏參數和圖正則化參數下的標注結果比較

圖3 GRNGS模型在不同最近鄰參數下的標注結果比較

3.3 算法收斂性分析

為了驗證本文所提的非負矩陣分解算法的收斂性，我們對兩個數據庫的建模過程進行了跟蹤，并通過計算式(6)中的目標函數值來確定其收斂狀態。如圖4所示，GRNGS模型的優化算法在兩個數據集上都是收斂的。具體來講，該算法在Corel5K數據集上僅需不到50次迭代就可達到收斂條件；而在ESP Game數據集上達到收斂的迭代次數則需600次左右。另外，僅考慮算法的收斂過程，本文針對GRNGS模型所提的優化算法在Corel5K和ESP Game數據集上的用時分別為5 min 29 s和12 min 45 s。這些實驗結果均反映了本文所提的模型優化算法具有較好的收斂性能，且計算復雜度較低，有利于算法的進一步推廣和應用。

3.4 模型參數結構比較

為了更好地分析GRNGS模型的模型參數，我們將該參數與NMF和圖正則化的非負矩陣分解(Graph-regularized Nonnegative Matrix Factorization, GNMF )[14]所得的模型參數進行稀疏性和結構比較。圖5顯示了這3種方法在Corel5K數據集和ESP Game數據集上所學習得到的模型參數。這3種模型在Corel5K和ESP Game數據集上的參數矩陣分別為320×374和320×268。從這些結果可以看出，GNMF的稀疏性一般比GRNGS和NMF差，而GRNGS在較大的ESP GAME數據集上的稀疏性明顯強于NMF和GNMF。同時，GRNGS所學習得到的矢量具有明顯的組效應和較好的一致性，從而體現了組群特征的相關性且能夠去除不相關特征的干擾，以更好地滿足圖像部分屬性特征表示的需求。

3.5 圖像標注結果比較與分析

為了更好地分析GRNGS模型在圖像標注方面的性能，本文所比較的方法包括一些基準圖像標注方法和與本文方法最為接近的若干方法。基準圖像標注方法包括：SVM模型和TagProp模型[20]。與本文方法最接近的圖像標注方法包括：NMF模型[13]、GNMF模型[14]、基于結構化組稀疏的多標注學習模型(Multi-label Boosting with structural Grouping Sparsity, MtBGS)[6]、結合組稀疏與圖正則化的LJGL模型[7]。前兩種模型是非負分解方法，后3種模型是結合組稀疏的圖像標注模型。與MtBGS模型相比，LJGL模型和GRNGS模型在其基礎上增加了圖正則化項。而與LJGL模型相比，GRNGS模型則又進一步結合了模型的非負參數約束，使得模型學習過程更加符合人腦的認知模式。表2和表3給出了各方法的標注結果。

圖4 非負迭代算法的收斂過程

圖5 模型參數及其稀疏性分析

表 2 Corel5K數據集上的標注結果比較

表 3 ESP Game數據集上的標注結果比較

從實驗結果中可以看出，在Corel5K和ESP Game數據集上，將結合組稀疏的標注模型(如MtBGS, LJGL和GRNGS)相較于其他標注模型(如SVM, TagProp, NMF和GNMF)在實驗結果上有了一定的提高，這充分說明了組稀疏對圖像高層語義理解有著重要的意義。通過比較MtBGS, LJGL和GRNGS在兩個數據集上的標注結果，我們可以發現LJGL模型的標注結果相較于MtBGS的標注結果提高較少，這說明單一的流形約束并不能夠顯著地提高模型對圖像語義的理解；而本文方法在組稀疏和圖正則化的基礎上又進一步考慮了模型參數的非負性約束條件，使得標注結果相較于其他模型有了較為顯著的提高。

4 結束語

本文研究了組稀疏、圖正則化以及非負參數約束對圖像標注的影響，提出了GRNGS模型來構建多種異構視覺特征與圖像語義標簽之間的映射關系。實驗結果表明，本文方法具有較好的穩定性和良好的標注性能。在今后的工作中，我們將側重研究不同視覺特征在核映射空間上的自適應距離測度，并從層次化語義角度進一步改善“語義鴻溝”問題的解決方案。

[1] Wright J, Ma Y, Mairal J, et al.. Sparse representation for computer vision and pattern recognition[J]. Proceedings of the IEEE, 2010, 98(6): 1031-1044.

[2] Shen L, Yeo C, and Hua B. Intrinsic image decomposition using a sparse representation of reflectance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(12): 2904-2915.

[3] 宋相法, 焦李成. 基于稀疏編碼和集成學習的多示例多標記圖像分類方法[J]. 電子與信息學報, 2013, 35(3): 622-628.

Song Xiang-fa and Jiao Li-cheng. A multi-instance multi-label image classification method based on sparse coding and ensemble learning[J]. Journal of Electronics & Information Technology, 2013, 35(3): 622-628.

[4] Wu F, Han Y, Liu X, et al.. The heterogeneous feature selection with structural sparsity for multimedia annotation and hashing: a survey[J]. International Journal of Multimedia Information Retrieval, 2012, 1(1): 3-15.

[5] Wu F, Han Y, Tian Q, et al.. Multi-label boosting for image annotation by structural grouping sparsity[C]. ACM International Conference on Multimedia, Firenze, Italy, 2010: 15-24.

[6] Yang Y, Huang Z, Yang Y, et al.. Local image tagging via graph regularized joint group sparsity[J]. Pattern Recognition, 2013, 46(5): 1358-1368.

[7] Gao S, Chia L T, Tsang I W H, et al.. Concurrent single-label image classification and annotation via efficient multi-layer group sparse coding[J]. IEEE Transactions on Multimedia, 2014, 16(3): 762-771.

[8] Jayaraman D, Sha F, and Grauman K. Decorrelating semantic visual attributes by resisting the urge to share[C]. IEEE Conference on Computer Vision and Pattern Recognition, Columbus, USA, 2014: 1629-1636.

[9] Bahrampour S, Ray A, Nasrabadi N M, et al.. Quality-based multimodal classification using tree-structured sparsity[C]. IEEE Conference on Computer Vision and Pattern Recognition, Columbus, USA, 2014: 4114-4121.

[10] Cho J, Lee M, Chang H J, et al.. Robust action recognition using local motion and group sparsity[J]. Pattern Recognition, 2014, 47(5): 1813-1825.

[11] Yogatama D and Smith N A. Making the most of bag of words: sentence regularization with alternating direction method of multipliers[C]. International Conference on Machine Learning, Beijing, 2014, Vol. 32: 656-664.

[12] Yan L, Yan L, Xue G R, et al.. Coupled group lasso for web-scale CTR prediction in display advertising[C]. International Conference on Machine Learning, Beijing, 2014: 802-810.

[13] Lee D D and Seung H S. Learning the parts of objects by nonnegative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.

[14] Cai D, He X, Han J, et al.. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560.

[15] Zhou B, Zhang F, and Peng L. Compact representation for dynamic texture video coding using tensor method[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(2): 280-288.

[16] Müller H, Marchand-Maillet S, and Pun T. The truth about corel-evaluation in image retrieval[C]. ACM International Conference on Image and Video Retrieval, London, UK, 2002, Vol. 2383: 38-49.

[17] Von Ahn L and Dabbish L. Labeling images with a computer game[C]. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, New York, USA, 2004: 319-326.

[18] Zhou N, Cheung W K, Qiu G, et al.. A hybrid probabilistic model for unified collaborative and content-based image tagging[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(7): 1281-1294.

[19] Oliva A and Torralba A. Modeling the shape of the scene: a holistic representation of the spatial envelope[J]. International Journal of Computer Vision, 2001, 42(3): 145-175.

[20] Guillaumin M, Mensink T, Verbeek J, et al.. TagProp: discriminative metric learning in nearest neighbor models for image auto-annotation[C]. International Conference on Computer Vision, Kyoto, Japan, Sept. 2009: 309-316.

錢智明： 男，1986年生，博士，研究方向為圖像理解與目標識別.

鐘 平： 男，1979年生，副教授，研究方向為圖像理解與目標識別.

王潤生： 男，1941年生，教授，研究方向為圖像理解與目標識別.

Automatic Image Annotation via Graph Regularization and Non-negative Group Sparsity

Qian Zhi-ming Zhong Ping Wang Run-sheng
(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)

Extracting an effective visual feature to uncover semantic information is an important work for designing a robust automatic image annotation system. Since different kinds of heterogeneous features (such as color, texture and shape) show different intrinsic discriminative power and the same kind of features are usually correlated for image understanding, a Graph Regularized Non-negative Group Sparsity (GRNGS) model for image annotation is proposed, which can be effectively solved by a new method of non-negative matrix factorization. This model combines graph regularization with l2,1-norm regularization, and is able to select proper group features, which can describe both visual similarities and semantic correlations when performing the task of image annotation. Experimental results reported over the Corel5K and ESP Game databases show the robust capability and good performance of the proposed method.

Image annotation; Graph regularization; Group sparsity; Non-negative matrix factorization

TP391

： A

：1009-5896(2015)04-0784-07

10.11999/JEIT141282

2014-10-09收到，2014-12-30改回

國家自然科學基金(61271439)資助課題

*通信作者：鐘平 zhongping@nudt.edu.cn