郭繼昌 張 帆 王 楠

?

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

郭繼昌*張 帆 王 楠

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

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

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

1 引言

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

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

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

2 字典學(xué)習(xí)模型及字典對模型

2.1 綜合型字典學(xué)習(xí)模型

2.2 解析型字典學(xué)習(xí)模型

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

2.3 字典對模型

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

3 基于Fisher約束的字典對學(xué)習(xí)模型

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

3.1 誤差項的設(shè)計

FDPL模型中對訓(xùn)練樣本和字典均采用結(jié)構(gòu)化表示方式。結(jié)構(gòu)化表示方式下解析字典和系數(shù)的優(yōu)化問題以及綜合字典和系數(shù)的優(yōu)化問題分別表示為

因此FDPL模型的重構(gòu)誤差項和編碼誤差項為

(6)

3.2 字典判別性約束項的設(shè)計

3.3 系數(shù)判別性約束項的設(shè)計

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

(8)

3.4 模型求解

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

(11)

(13)

(15)

表1 FDPL模型的字典學(xué)習(xí)過程

3.5 分類準(zhǔn)則

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

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

(17)

(19)

4 實驗及分析

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

4.1 圖像庫

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

4.2 參數(shù)設(shè)置

表2 FDPL算法的主要參數(shù)

4.3 FDPL方法在不同分類準(zhǔn)則下的分類性能對比

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

圖2 AR圖像庫上目標(biāo)函數(shù)的收斂性曲線

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

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

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

表4 不同原子個數(shù)下的分類準(zhǔn)確率(%)

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

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

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

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

4.5 稀疏性分析

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

5 結(jié)束語

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

圖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] 宋相法, 焦李成. 基于稀疏編碼和集成學(xué)習(xí)的多示例多標(biāo)記圖像分類方法[J]. 電子與信息學(xué)報, 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] 練秋生, 石保順, 陳書貞. 字典學(xué)習(xí)模型、算法及其應(yīng)用研究進展[J]. 自動化學(xué)報, 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)，天津市自然科學(xué)基金(15JCYBJC15500)

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

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

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

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