周 航，董西偉,2，荊曉遠(yuǎn)

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210023;2.九江學(xué)院 信息科學(xué)與技術(shù)學(xué)院,江西 九江 332005)

1 概 述

近年來(lái)，隨著壓縮感知理論的發(fā)展，稀疏表示受到國(guó)內(nèi)外眾多學(xué)者的廣泛研究。稀疏表示最初應(yīng)用于信號(hào)處理領(lǐng)域，并成功地解決了很多該領(lǐng)域的問題，比如圖像去噪[1-2]、圖像壓縮[3-5]、圖像重構(gòu)[6-7]等。Yang等[8]使用稀疏表示來(lái)解決信號(hào)的分類問題，通過(guò)將Fisher判別準(zhǔn)則加入其目標(biāo)函數(shù)，得到了具有良好判別性能并且可以重構(gòu)信號(hào)的稀疏系數(shù)。在人臉識(shí)別[9-10]研究領(lǐng)域中，WRIGHT等[11]提出基于稀疏表示的分類(Sparse Representation based Classification，SRC)。SRC算法的基本原理是用訓(xùn)練樣本構(gòu)造過(guò)完備字典，然后用該字典中原子的線性組合來(lái)表示測(cè)試樣本，最后通過(guò)計(jì)算重構(gòu)誤差進(jìn)行分類識(shí)別。而為了解決SRC算法在處理非線性樣本時(shí)的不足，GAO等[12]提出基于核稀疏表示的分類(Kernel SRC，KSRC)。KSRC的基本原理是將非線性的樣本映射到高維的核空間中，在該空間中訓(xùn)練樣本可以更輕易地線性表示出測(cè)試樣本。

在SRC算法中，字典學(xué)習(xí)是其關(guān)鍵環(huán)節(jié)，經(jīng)過(guò)眾多學(xué)者的研究，現(xiàn)階段的字典構(gòu)造方式主要有兩種：通過(guò)先驗(yàn)知識(shí)構(gòu)造字典；通過(guò)訓(xùn)練樣本的自適應(yīng)學(xué)習(xí)構(gòu)造字典。ENGAN等[13]提出的最優(yōu)方向法(Method of Optimal Directions，MOD)，是比較經(jīng)典的字典學(xué)習(xí)算法之一。MOD是一種期望最大值的字典學(xué)習(xí)算法，該算法通過(guò)迭代在訓(xùn)練過(guò)程中不斷更新字典原子，使稀疏表示的殘差不斷減小來(lái)滿足收斂條件，最終得到具有良好判別性能的字典。

在SRC算法中，字典性能的優(yōu)異對(duì)于算法的識(shí)別率影響很大，因此在字典學(xué)習(xí)過(guò)程中，如何去除冗余的原子，得到性能更佳的字典是非常值得研究和探索的?；诖耍闹型ㄟ^(guò)在經(jīng)典的MOD算法中加入聚類算法來(lái)優(yōu)化字典的設(shè)計(jì)，提出一種增強(qiáng)型MOD算法(E-MOD)。傳統(tǒng)的MOD算法雖然可以通過(guò)迭代學(xué)習(xí)得到性能不錯(cuò)的字典，但是在原始樣本集規(guī)模很大時(shí)，其并不能很好地解決字典過(guò)于冗余的問題。E-MOD算法在字典學(xué)習(xí)階段加入競(jìng)爭(zhēng)聚集聚類算法(Competitive Agglomeration，CA)[14]，CA算法可以將原始數(shù)據(jù)集劃分為最少的簇?cái)?shù)，并且簇中數(shù)據(jù)更加集中，因此通過(guò)CA算法的優(yōu)化后，可以得到最優(yōu)的劃分簇?cái)?shù)。接著使用正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)[15]來(lái)逼近得到稀疏表示系數(shù)，最終得到的字典性能優(yōu)越。

2 相關(guān)算法描述

2.1 OMP算法

OMP算法是匹配追蹤(MP)算法的改進(jìn)，其選取最佳原子的方式類似于MP算法，都是用字典中與信號(hào)殘差最小的原子，不同的是其之后采用Gram-Schmidt進(jìn)行正交化處理。

R0=gγj+R1

(1)

其中，gγj為字典中與信號(hào)殘差最小的原子。

選定原子，采用Gram-Schmidt做正交化處理：

(2)

此時(shí)，殘差Rj投影到pj上，得到：

(3)

上述過(guò)程經(jīng)過(guò)t次迭代后，信號(hào)可以表示為：

(4)

2.2 CA算法

目前存在的聚類算法形式主要有兩種，一種是層次式聚類，一種是劃分式聚類。前者通過(guò)將數(shù)據(jù)按照一定的層次級(jí)別劃分為不同的簇，其可以細(xì)分為自頂向下分裂方式和自底向上的凝聚方式；后者通過(guò)預(yù)先指定聚類的數(shù)目或聚類的中心，然后在滿足迭代終止條件時(shí)結(jié)束聚類過(guò)程，得到最終的聚類結(jié)果。

CA算法從基本屬性上來(lái)看是屬于劃分式聚類的一種，而劃分式聚類是預(yù)先指定聚類中心，但CA算法聚類中心的確定方式類似于層次式聚類中的凝聚方式。由此可以得知，在充分利用兩種聚類方式的優(yōu)點(diǎn)后，CA算法的性能更加優(yōu)秀，因此聚類后的效果更佳。

(5)

其中，d2(xi,βj)表示樣本xi到中心βj的距離；uij表示樣本xi對(duì)聚類中心βj的隸屬度。

由上式可以看到，目標(biāo)函數(shù)的前半部分與模糊C均值聚類算法(FCM)的目標(biāo)函數(shù)相似，用來(lái)確定聚類簇中樣本的分布情況；后半部分是一個(gè)偏移項(xiàng)，用來(lái)尋找最佳的簇?cái)?shù)。偏移項(xiàng)中參數(shù)α計(jì)算如下：

(6)

η(k)=η0exp(-k/τ)

(7)

其中，k為算法迭代次數(shù)；η0和τ為固定取值。

基于此，相較于其他聚類算法，通過(guò)優(yōu)化CA算法的目標(biāo)函數(shù)能得到更佳的聚類效果，即經(jīng)過(guò)CA算法聚類后的簇集相對(duì)較少，并且其內(nèi)部的距離也相對(duì)較小。因此，CA算法可以達(dá)到去除簇集過(guò)于冗余的效果，最終得到更佳的簇集。

2.3 MOD算法

(8)

其中，D=[g1,g2,…,gN]T為字典矩陣，gj為字典原子；wi為xi對(duì)應(yīng)字典原子gj的稀疏系數(shù)；T0為稀疏表示系數(shù)中非零元素的個(gè)數(shù)。

MOD算法通過(guò)反復(fù)迭代來(lái)更新系數(shù)矩陣W和字典矩陣D。先使用OMP算法逼近結(jié)果，以此更新稀疏系數(shù)wi，再根據(jù)樣本X和稀疏系數(shù)矩陣W更新字典：

(9)

當(dāng)滿足迭代停止條件時(shí)，輸出最終的字典D。

3 增強(qiáng)型MOD算法

在MOD算法中加入CA算法來(lái)優(yōu)化字典的設(shè)計(jì)，利用CA算法的去除冗余能力得到性能更佳的字典。在MOD算法的稀疏編碼階段，用CA算法代替OMP算法來(lái)更新稀疏系數(shù)wj，將字典原子gj作為聚類中心，uij為樣本xi對(duì)字典原子gj的隸屬度，由此得到優(yōu)化字典設(shè)計(jì)階段的目標(biāo)函數(shù)為：

(10)

(11)

xi和gj間的歐氏距離為：

d2(xi,gj)=‖xi-gj‖2

(12)

MOD算法和CA算法之間由uij來(lái)聯(lián)系，uij和wj的關(guān)系定義如下：

(13)

(14)

固定D和X，得到：

(15)

為方便計(jì)算，假設(shè)τt值在連續(xù)迭代后沒有發(fā)生明顯的改變，將式(15)代入目標(biāo)函數(shù)的約束中求解λs：

(16)

整理后得到：

(17)

將式(17)代入式(15)：

(18)

(19)

其中，u(update)和u(prune)由式(18)來(lái)定義。當(dāng)u(update)占主導(dǎo)地位時(shí)，通過(guò)更新可以得到uij；當(dāng)u(prune)占主導(dǎo)地位時(shí)，uij根據(jù)使用的gj增加或減少。

E-MOD算法的具體流程如下：

(1)給定訓(xùn)練樣本集X∈Rn×N，字典矩陣D∈Rn×M，單位化X和D的每一列；

(2)稀疏編碼階段：通過(guò)式(19)計(jì)算隸屬度uij，再通過(guò)式(13)計(jì)算系數(shù)wj；

(3)字典學(xué)習(xí)階段：用上面計(jì)算得到的wj和式(8)來(lái)更新字典原子dj；

(4)滿足終止條件時(shí)停止迭代，得到系數(shù)矩陣W和字典D。

4 實(shí) 驗(yàn)

本節(jié)將在AR以及CAS-PEAL人臉庫(kù)上進(jìn)行實(shí)驗(yàn)，通過(guò)對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證文中算法的有效性，使用的對(duì)比方法包括SRC、KSRC以及MOD。

4.1 圖像數(shù)據(jù)庫(kù)

AR庫(kù)中包含126人共4 000多張人臉圖像，為節(jié)約計(jì)算成本以及存儲(chǔ)空間，選取庫(kù)中100個(gè)人，每個(gè)人的26張圖片全部選取，對(duì)選取的圖片按行展開排成一列再進(jìn)行降維操作，維數(shù)降到600。在E-MOD算法中，設(shè)置參數(shù)η0=5，τ=10。

CAS-PEAL人臉數(shù)據(jù)庫(kù)包含106個(gè)人共1 060張人臉圖像，同樣為節(jié)約計(jì)算成本，選取庫(kù)中80個(gè)人，并且對(duì)選取的圖片進(jìn)行降維操作，將圖片降維到480。在E-MOD算法中，設(shè)置參數(shù)η0=6，τ=10。

4.2 實(shí)驗(yàn)結(jié)果及分析

在AR數(shù)據(jù)庫(kù)中，隨機(jī)選取每個(gè)人的20張圖像作為訓(xùn)練樣本，其余作為測(cè)試樣本；在CAS-PEAL數(shù)據(jù)庫(kù)中，隨機(jī)選取每個(gè)人的6張圖像作為訓(xùn)練樣本，其余作為測(cè)試樣本。圖1和圖2分別為AR和CAS-PEAL數(shù)據(jù)庫(kù)上所有方法20次隨機(jī)實(shí)驗(yàn)的識(shí)別率對(duì)比圖；表1為所有方法的平均識(shí)別率和方差。

圖1 AR數(shù)據(jù)庫(kù)上的識(shí)別率對(duì)比

方法平均識(shí)別率/%AR庫(kù)CAS-PEAL庫(kù)SRC83.31±4.3485.11±3.21KSRC85.14±3.6787.35±2.47MOD87.96±3.2589.69±2.93E-MOD91.67±2.4392.78±1.79

從圖1、圖2以及表1可以看出，文中算法有更好的分類性能。在AR庫(kù)上，E-MOD算法比SRC、KSRC以及MOD三個(gè)對(duì)比方法的平均識(shí)別率至少提高了8.36%(91.67%-83.31%)；在CAS-PEAL庫(kù)上，E-MOD算法比三個(gè)對(duì)比方法的平均識(shí)別率至少提高了7.67%(92.78%-85.11%)。實(shí)驗(yàn)結(jié)果充分驗(yàn)證了文中算法能有效地提高識(shí)別率。

5 結(jié)束語(yǔ)

在模式識(shí)別領(lǐng)域，通過(guò)大量的研究已經(jīng)證實(shí)了在圖像分類問題上SRC算法的有效性。在SRC算法中，字典學(xué)習(xí)是其關(guān)鍵環(huán)節(jié)，文中在MOD算法的基礎(chǔ)上，引入一種優(yōu)化字典設(shè)計(jì)的技術(shù)，提出一種增強(qiáng)字典學(xué)習(xí)能力的MOD算法(E-MOD)。先在稀疏編碼階段，通過(guò)CA算法來(lái)更新目標(biāo)函數(shù)，以得到稀疏表示系數(shù)；然后在字典學(xué)習(xí)階段，根據(jù)稀疏系數(shù)更新字典，得到性能優(yōu)異的字典。通過(guò)在AR以及CAS-PEAL人臉數(shù)據(jù)庫(kù)上的對(duì)比實(shí)驗(yàn)對(duì)E-MOD算法進(jìn)行了充分的驗(yàn)證。

[1] 劉帥奇,胡紹海,肖 揚(yáng).基于稀疏表示的Shearlet域SAR圖像去噪[J].電子與信息學(xué)報(bào),2012,34(9):2110-2115.

[2] 王金金,宋余慶,桂長(zhǎng)青.基于小波變換和稀疏表示的圖像去噪[J].測(cè)控技術(shù),2015,34(8):23-26.

[3] 蔡 紅.基于稀疏表示的SAR圖像壓縮方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(24):177-181.

[4] 雷 萌,張 環(huán),王 弘.基于哈希表的稀疏圖像壓縮算法研究[J].軟件導(dǎo)刊,2013,12(9):50-52.

[5] 閆雪南,鄒建成.基于稀疏表示的人臉圖像壓縮方法[J].北方工業(yè)大學(xué)學(xué)報(bào),2014,26(3):6-10.

[6] 李 雪,蔣愛民,劉小峰,等.基于稀疏表示的圖像超分辨率重構(gòu)算法[J].微處理機(jī),2014,35(1):41-45.

[7] 路錦正,吳 斌,張啟衡.正則化恢復(fù)聯(lián)合稀疏表示的圖像超分辨率重構(gòu)[J].光電工程,2013,40(9):1-7.

[8] YANG J,WANG J,HUANG T.Learning the sparse representation for classification[C]//International conference on multimedia & expo.[s.l.]:IEEE,2011:1-6.

[9] 王東李.一種新的人臉識(shí)別算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(5):138-144.

[10] 趙振勇,王保華,王 力,等.人臉圖像的特征提取[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(5):221-224.

[11] WRIGHT J,YANG A Y,GANESH A,et al.Robust face recognition via spare representation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2009,31(2):210-227.

[12] GAO S,TSANG I W H,CHIA L T.Kernel sparse representation for image classification and face recognition[C]//European conference on computer vision.[s.l.]:[s.n.],2010:1-14.

[13] ENGAN K,AASE S O,HUSOY J H.Method of optimal directions for frame design[C]//International conference on acoustics,speech,and signal processing.[s.l.]:IEEE,1999:2443-2446.

[14] FRIGUI H,KRISHNAPURAM R.Clustering by competitive agglomeration[J].Pattern Recognition,1997,30(7):1109-1119.

[15] TROPP J A,GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.