基于Fisher約束和字典對的圖像分類

郭繼昌 張 帆 王 楠

?

基于Fisher約束和字典對的圖像分類

郭繼昌*張 帆 王 楠

(天津大學電子信息工程學院 天津 300072)

基于稀疏表示的分類方法由于其所具有的簡單性和有效性獲得了研究者的廣泛關注，然而如何建立字典原子與類別信息間的聯系仍然是一個重要的問題，與此同時大部分稀疏表示分類方法都需要求解受范數約束的優化問題，使得分類任務的計算較復雜。為解決上述問題，該文提出一種新的基于Fisher約束的字典對學習方法。新方法聯合學習結構化綜合字典和結構化解析字典，然后通過樣本在解析字典上的映射直接求解稀疏系數矩陣；同時采用Fisher判別準則編碼系數使系數具有一定的判別性。最后將新方法應用到圖像分類中，實驗結果表明新方法在提高分類準確率的同時還大大降低了計算復雜度，相較于現有方法具有更好的性能。

圖像分類；稀疏表示；字典對；Fisher約束

1 引言

在對基于稀疏表示的分類方法進行研究的過程中，研究者們發現字典性能的好壞直接關系到最后的分類結果。字典最早用于解決信號重構的相關問題，它旨在獲得一個具有良好表示能力的字典而沒有考慮字典的判別性，因此并不利于分類問題[4]。近年來的研究表明判別性字典更加適合用于圖像分類任務，此類字典既要被用來對樣本進行稀疏編碼，又要被用于執行最后的分類判別。判別性字典大致可分為兩類：第1類是直接學習具有判別性的字典，文獻[5]對不同類別的子字典添加低秩約束來學習一個具有判別性的字典，文獻[6]考慮不同類別子字典間的非一致性信息提出了結構不相干字典學習方法，文獻[7]提出同時學習一個所有類別的公共字典和多個特定類別的子字典的字典學習方法；第2類是對稀疏系數添加約束項來提升系數的判別性，進而獲得具有判別性的字典[8,9]，文獻[8]在字典學習過程中對系數添加樣本的類別信息提出了標簽一致K奇異值分解(Label Consistent K-Singular Value Decomposition, LC-KSVD)方法，文獻[9]提出了對系數添加Fisher判別約束的字典學習方法。

上述字典學習方法均屬于綜合型字典學習。綜合型字典學習方法一直是研究者關注的熱點，因此基于綜合模型的字典學習理論相對比較成熟[10]，但是綜合型字典學習方法的計算量都較大，因此研究者們又提出了解析型字典學習方法[11,12]。解析模型中通過學習到的解析字典來獲得樣本的稀疏編碼，具有較高的編碼效率。與綜合模型相比，在維數相同時解析模型的子空間數較多，有更靈活和更豐富的表示能力。

本文將解析字典學習模型和綜合字典學習模型結合起來，提出一種新的字典學習方法，稱之為基于Fisher判別約束的字典對學習方法。新方法一方面聯合學習由結構化綜合字典和結構化解析字典構成的字典對，并對字典添加判別性約束使得學習到的字典對具有判別性；另一方面通過樣本在解析字典上的映射直接求解稀疏系數矩陣，避免了對標準稀疏編碼問題的求解，同時采用Fisher判別準則編碼系數使系數具有一定的判別性。最后將新模型應用到人臉圖像庫，目標圖像庫和場景圖像庫上進行評估。

2 字典學習模型及字典對模型

2.1 綜合型字典學習模型

2.2 解析型字典學習模型

解析型字典學習是綜合型字典學習的對偶形式，它的核心思想是通過學習到的解析字典直接獲得樣本在新映射空間的稀疏表示，解析型字典如圖1(b)所示。優化模型可以表示為式(2)，為解析型字典，是度量稀疏度的函數。

2.3 字典對模型

基于解析型字典學習的稀疏表示研究處于起步階段，還沒有較多地應用到稀疏表示分類問題中。比較有代表性的是文獻[13]中提出的字典對學習(Dictionary Pair Learning，DPL) 模型。DPL模型通過樣本在解析字典上的映射直接求解稀疏系數矩陣，避免了對受范數約束的標準稀疏編碼問題的求解，從而大大減少了分類任務的計算復雜度。設矩陣，本文中用表示將矩陣和按列進行合并，用表示將矩陣和按行進行合并。DPL模型中用表示類訓練樣本，其中每類訓練樣本的個數為。求解DPL模型得到綜合字典和解析字典。其中是第類樣本對應的子字典對。在DPL模型中第類的解析子字典對第類樣本的映射集合幾乎為空集，即，用字典對表示的最小化重構誤差為

3 基于Fisher約束的字典對學習模型

DPL模型利用解析字典大大減少了計算復雜度，但是其并沒有充分利用訓練樣本所具有的類別信息，同時在字典學習模型中也沒有考慮不同類別樣本對應的字典原子和系數矩陣間的相關性信息。為克服以上缺點，本文提出了一種新的字典學習模型，稱之為基于Fisher約束的字典對學習(Fisher constraint Dictionary Pair Learning, FDPL)模型。該模型同時學習結構化綜合字典和結構化解析字典，并且在字典學習過程中對解析字典添加判別性約束來衡量解析子字典間存在的相關性信息，同時對系數添加Fisher約束來衡量系數矩陣間的相關性信息。FDPL模型的優化問題可以表示為

3.1 誤差項的設計

FDPL模型中對訓練樣本和字典均采用結構化表示方式。結構化表示方式下解析字典和系數的優化問題以及綜合字典和系數的優化問題分別表示為

因此FDPL模型的重構誤差項和編碼誤差項為

(6)

3.2 字典判別性約束項的設計

3.3 系數判別性約束項的設計

文獻[9]中指出Fisher約束可以用來衡量樣本間的相似性信息，具體是通過最小化系數的類內離散度和最大化系數的類間離散度來實現的。設稀疏系數矩陣為，其中為第類樣本對應的系數矩陣，表示第類字典對第類樣本的編碼矩陣。的類內離散度、類間離散度為

(8)

3.4 模型求解

求解FDPL模型可以采用迭代優化的方法，將優化求解分為固定字典對更新系數和固定系數更新字典對兩個子問題。

(11)

(13)

(15)

表1 FDPL模型的字典學習過程

3.5 分類準則

本文采用兩種分類準則，第1種是將樣本的重構誤差作為分類準則，在這種分類準則下直接利用訓練階段求得的解析字典來獲得測試樣本的稀疏編碼；第2種是同時考慮樣本的重構誤差和編碼誤差進行分類，此時根據訓練階段獲得的綜合字典通過求解標準稀疏表示問題獲得測試樣本的稀疏編碼，再與解析字典獲得的稀疏編碼相比較作為編碼誤差。

(1)根據重構誤差進行分類：通過求解FDPL模型得到每個類別對應的字典對，解析型子字典只對與它同類別的樣本具有很好的表示能力，同時綜合型子字典可以根據編碼系數對第類的樣本進行重構，此時的重構誤差較小，但當時的值較大。因此在測試階段如果待測試樣本屬于第類則，顯然根據重構誤差可以用來確定測試樣本的類別：

(17)

(19)

4 實驗及分析

為了驗證FDPL算法的性能，本文不僅比較FDPL算法在兩種分類準則下的性能，而且將FDPL方法與已有的效果較好的字典學習方法進行比較，例如LC-KSVD[8], Fisher 判別約束字典學習(Fisher Discrimination Dictionary Learning, FDDL)[9]、支持向量引導的字典學習 (Support Vector Guided Dictionary Learning, SVGDL)[15]和DPL[13]。衡量分類模型性能好壞時既要考慮其分類準確率又要考慮其分類效率，因此實驗中采用兩種衡量指標：一是分類準確率，二是分類復雜度。

4.1 圖像庫

Extended YaleB圖像庫包含38人共2414張圖像，每人隨機選取32張圖像作為訓練集，其余作為測試集，圖像特征采用504維的隨機臉。AR圖像庫包含126人共4000多張圖像，選取50個男性和50個女性共計2600張圖像來進行實驗，每人隨機選取20張圖像作為訓練集其余作為測試集，圖像特征采用540維的隨機臉。Caltech-101圖像庫共有102類9144張圖像，每類圖像個數從31到800不等，每類隨機選取30張圖像作為訓練集其余作為測試集。Scene15圖像庫共有15類4485張圖像，每類圖像個數從200到400不等，每類隨機選取100張圖像作為訓練集其余作為測試集。在Caltech-101和Scene15圖像庫上首先按的圖像塊、6像素的步長提取圖像的原始稠密SIFT特征；然后對原始特征進行空間金字塔最大池化，得到SIFT池化特征；通過K-means方法對池化特征進行稀疏編碼，對每幅圖像的所有稀疏編碼運用空間金字塔最大化池方法；最后通過PCA降維得到3000維的含有空間信息的SIFT特征。

4.2 參數設置

表2 FDPL算法的主要參數

4.3 FDPL方法在不同分類準則下的分類性能對比

3.5節對兩種分類準則進行了具體描述，第1種分類準則直接利用解析字典求解稀疏系數，第2種分類準則在求編碼誤差時仍然需要求解標準稀疏編碼問題來獲得待測樣本在綜合字典下的稀疏系數。首先對比表3中的分類準確率可以看出，第2種分類準則下的分類準確率較高但提升不是很明顯；然后對比分類用時可以看出，第1種分類準則在分類用時方面具有明顯優勢。衡量分類模型性能好壞時既要考慮其分類準確率又要考慮其分類效率，綜合評定可知第1種分類準則的優勢更為明顯，也說明了采用樣本在解析字典上的投影直接獲得稀疏系數矩陣的方法具有高效性和可行性。

圖2 AR圖像庫上目標函數的收斂性曲線

4.4 字典原子個數不同時分類性能對比

已有研究表明，字典學習過程中每類選取的字典原子個數直接關系到分類性能的好壞，因此將其設置為實驗過程中的變量。LC-KSVD和SVGDL算法中限制總的字典原子個數不大于選取的訓練樣本個數，在AR圖像庫上每類選取的訓練樣本個數為20，因此在字典原子個數為30時沒有對應的數據。改變字典原子個數時的分類準確率如表4所示，黑體標注為相同字典原子個數下的最高分類準確率。表5是各種方法保持硬件條件一致的情況下的分類用時比較。

表3 FDPL方法在不同分類準則下的分類準確率(%)和分類用時(s)

表4 不同原子個數下的分類準確率(%)

表5 不同原子個數下的分類用時(s)

對比表中每列的數據，為了說明本文算法的有效性首先與LC-KSVD, SVGDL算法進行對比，通過LC-KSVD和SVGDL算法獲得的是所有類別公用的綜合字典，并且在字典學習過程中沒有考慮字典原子間的相關性信息，因此采用LC-KSVD和SVGDL算法獲得的字典的判別性能較差，進而造成分類準確率較低。為了進一步論證本文算法的有效性，將與FDDL和DPL算法進行對比，FDDL算法通過對系數添加Fisher約束來獲得具有判別性的字典，但該方法沒有考慮字典原子間的相關性信息，DPL算法聯合學習綜合字典和解析字典，但是該方法并沒有考慮系數間的相關性信息，因此采用FDDL, DPL算法進行圖像分類的效果也較差。通過對比發現FDPL算法具有較高的分類準確率。

4.3節中通過對比FDPL方法在兩種分類準則下的分類用時，可知第2種分類準則在時間消耗上并不具有優勢，因此在與其它方法進行對比時主要考慮第1種分類準則下的分類用時。與其它方法相比FDPL方法分類用時明顯較少并且受字典原子個數的影響較小。分析上述結果原因主要有以下兩點：在訓練階段進行迭代更新時FDPL方法需要求解的是標準最小二乘問題，該問題可以通過解析方法求其閉式解，從而避免了處理FDDL, LC-KSVD和SVGDL方法中受范數約束的稀疏編碼問題；在分類階段FDPL方法通過樣本在解析字典上的映射直接求解稀疏系數矩陣，也避免了對標準稀疏編碼問題的求解，因此用時較短。

然而通過運行時間分析復雜度并不可靠，接下來將從理論上對FDPL方法的計算復雜度進行分析。采用迭代更新的方法更新,,的時間復雜度分別為,,,是采用ADMM方法更新字典時的迭代次數，通常。在實際應用中每類訓練樣本個數和字典原子個數都遠遠小于特征維數，因此訓練階段的計算復雜度主要是由更新引起的。第1種分類準則下重構誤差項的計算復雜度為，分類階段總的復雜度為。相較于求解標準稀疏編碼問題，FDPL方法具有較小的計算復雜度且受字典原子個數和訓練樣本個數影響較小。

4.5 稀疏性分析

將實驗過程中得到的樣本的系數矩陣提取出來進行稀疏性分析，以Extended YaleB為例。圖3為在每類字典原子個數為10的情況下的稀疏性分析。

5 結束語

本文提出了基于Fisher約束和字典對學習的圖像分類方法，FDPL方法一方面既考慮字典判別性又考慮系數判別性，使得所得字典和系數均具有良好的判別能力；另一方面通過樣本在解析字典上的映射直接求解稀疏系數矩陣，避免了對標準稀疏編碼問題的求解，減少了計算復雜度。在多個圖像庫上對FDPL方法進行了實驗驗證并與現有效果較好的方法進行了比較，實驗結果表明FDPL方法克服了當下主流字典學習算法中計算復雜、訓練速度慢的缺點，在總體上縮短了圖像分類時間，并且具有更高的分類準確率。本文并未考慮圖像特征表示這一因素對分類性能的影響，采用了已有的提取圖像SIFT特征的方法，因此在未來的研究中將會尋求更好的圖像特征表示方法，然后與本文方法相結合。

圖3 稀疏性分析

[1] RUBINSTEIN R, BRUCKSTEIN A, ELAD M,. Dictionaries for sparse representation modeling[J]., 2010, 98(6): 1045-1057.doi: 10.1109/JPROC.2010.2040551.

[2] GAO Shenghua, TSANG I, and MA Yi. Learning category- specific dictionary and shared dictionary for fine-grained image categorization[J]., 2014, 23(2): 623-634.doi: 10.1109/TIP.2013. 2290593.

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

SONG Xiangfa and JIAO Licheng. A multi-instance multi-label image classification method based on sparse coding and ensemble learning[J].&, 2013, 35(3): 622-626. doi: 10.3724/ SP.J.1146.2012.01218.

[4] AHARON M, ELAD M, and BRUCKSTEIN A. K-SVD: an algorithm for designing of overcomplete dictionaries for sparse representation[J]., 2006, 54(11): 4311-4322.doi: 10.1109/TSP. 2006.881199.

[5] MA Long, WANG Chunheng, XIAO Baihua,. Sparse representation for face recognition based on discriminative low-rank dictionary learning[C]. IEEE Conference on Computer Vision and Pattern Recognition, Providence, USA, 2012: 2586-2593.

[6] RAMIREZ I, SPRECHMANN P, SAPIRO G,. Classification and clustering via dictionary learning with structured incoherence and shared features[C]. IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA, 2010: 3501-3508.

[7] NING Zhou and FAN Jianping. Jointly learning visually correlated dictionaries for large-scale visual recognition applications[J]., 2014, 36(4): 715-730.doi: 10.1109/ TPAMI.2013.189.

[8] JIANG Zhuolin, LIN Zhe, LARRY S,. Label consistent K-SVD: Learning a discriminative dictionary for recognition [J]., 2013, 35(11): 2651-2664.doi: 10.1109/TPAMI. 2013.88.

[9] YANG Meng, ZHANG Lei, FENG Xiangchu,. Sparse representation based fisher discrimination dictionary learning for image classication[J]., 2014, 109(3): 209-232. doi: 10.1007/s11263-014- 0722- 8.

[10] 練秋生, 石保順, 陳書貞. 字典學習模型、算法及其應用研究進展[J]. 自動化學報, 2015, 41(2): 240-260. doi: 10.16383/ j.aas.2015.c140252.

LIAN Qiusheng, SHI Baoshun, and CHEN Shuzhen. Research advances on dictionary learning models, algorithms and applications[J]., 2015, 41(2): 240-260. doi: 10.16383/j.aas.2015.c140252.

[11] RUBINSTEIN R, PELEG T, and ELAD M. Analysis K-SVD: A dictionary-learning algorithm for the analysis sparse model[J]., 2013, 61(3): 661-677. doi: 10.1109/TSP.2012.2226445.

[12] CHEN Yunjin, RANFTL R, and POCK T. Insights into analysis operator learning: From patch-based sparse models to higher order MRFs[J]., 2014, 23(3): 1060-1072.doi: 10.1109/TIP.2014. 2299065.

[13] GU Shuhang, ZHANG Lei, ZUO Wangmeng,.Projective dictionary pair learning for pattern classification[C]. Advances in Neural Information Processing System, Vancouver, BC, Canada, 2014, 1: 793-801.

[14] RAKOTOMAMONJY A.Applying alternating direction method of multipliers for constrained dictionary learning[J]., 2013, 61(3): 126-136. doi: 10.1016/j. neucom.2012.10.024.

[15] CAI Sijia, ZUO Wangmeng, ZHANG Lei,.Support vector guided dictionary learning[C]. European Conference on Computer Vision, Zurich, Switzerland, 2014, 8692: 624-639.

[16] GORSKI J, PFEUFFER F, and KLAMROTH K. Biconvex sets and optimization with biconvex functions: a survey and extensions[J]., 2007, 66(3): 373-407. doi:10.1007/s00186-007-0161-1.

Image Classification Based on Fisher Constraint and Dictionary Pair

GUO Jichang ZHANG Fan WANG Nan

(,,300072,)

Classification method based on sparse representation has won wide attention because of its simplicity and effectiveness, while how to adaptively build the relationship between dictionary atoms and class labels is still an important open question, at the same time most of the sparse representation classification methods need to solve a norm constraint optimization problem, which increases the computational complexity in the classification task. To address this issue, this paper proposes a novel Fisher constraint dictionary pair learning method to jointly learn a structured synthesis dictionary and a structured analysis dictionary, then directly obtains the sparse coefficient matrix by analysis dictionary. In this paper, the Fisher criterion is used to encode the coefficients. Finally the new method is applied to image classification task, the experimental results show that the new method not only improves the accuracy of classification but also greatly reduces the computational complexity. Compared with the existing methods, the new method has better performance.

Image classification; Sparse representation; Dictionary pair; Fisher constraint

TP391

A

1009-5896(2017)02-0270-08

10.11999/JEIT160296

2016-03-31；改回日期：2016-07-25；

2016-10-09

郭繼昌 jcguo@tju.edu.cn

國家973計劃項目(2014CB 340400)，天津市自然科學基金(15JCYBJC15500)

The National 973 Program of China (2014CB340400), The Natural Science Foundation of Tianjin (15JCYBJC15500)

郭繼昌： 男，1966年生，教授，研究方向為數字圖像處理、語音信號處理等.

張 帆： 女，1993年生，碩士生，研究方向為圖像分類.

王 楠： 男，1990年生，碩士生，研究方向為圖像分類.