陳思寶，陳道然，羅　斌

(1.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽合肥 230601； 2.安徽省工業(yè)圖像處理與分析重點(diǎn)實(shí)驗(yàn)室，安徽合肥 230039)

?

基于L1-范數(shù)的最大間距準(zhǔn)則

陳思寶1,2，陳道然1,2，羅斌1,2

(1.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽合肥 230601； 2.安徽省工業(yè)圖像處理與分析重點(diǎn)實(shí)驗(yàn)室，安徽合肥 230039)

在進(jìn)行線性投影降維時(shí)，由于傳統(tǒng)的最大間距準(zhǔn)則(Maximum Margin Criterion，MMC)算法基于L2-范數(shù)，易于受到野值(outliers)及噪聲的影響.該文提出一種基于L1-范數(shù)的最大間距準(zhǔn)則(L1-norm-based MMC，MMC-L1)降維方法，它充分利用L1-范數(shù)對(duì)野值及噪聲的強(qiáng)魯棒性以及最大間距準(zhǔn)則，提出了一種快速迭代優(yōu)化算法，并給出了其單調(diào)收斂到局部最優(yōu)的證明.在多個(gè)圖像數(shù)據(jù)庫上的實(shí)驗(yàn)驗(yàn)證了該方法的魯棒性與高效性.

最大間距準(zhǔn)則(MMC)；L1-范數(shù)；線性投影；降維

1　引言

在統(tǒng)計(jì)模式識(shí)別和圖像處理領(lǐng)域中，高維數(shù)據(jù)是限制多種模式識(shí)別技術(shù)的主要因素.當(dāng)訓(xùn)練樣本的數(shù)目相對(duì)于特征數(shù)目較小時(shí)，大量的特征會(huì)降低分類器的性能，而且會(huì)出現(xiàn)由“維數(shù)災(zāi)難”[1]造成的“峰化現(xiàn)象”.此外，在高維空間中存在著測度的“集中現(xiàn)象”，即樣本數(shù)據(jù)點(diǎn)之間距離的度量可區(qū)分性隨著樣本數(shù)據(jù)維數(shù)的增加而減弱.為了克服這些問題并且使得后續(xù)的數(shù)據(jù)表示或分類更加穩(wěn)健，對(duì)高維數(shù)據(jù)進(jìn)行降維就成了一個(gè)非常重要的步驟.

眾所周知，經(jīng)典的線性投影降維方法通常將高維訓(xùn)練數(shù)據(jù)用向量形式進(jìn)行表示，再進(jìn)行線性投影降維和特征提取，其中最經(jīng)典的特征提取方法主要有主成分分析(Principal Component Analysis，PCA)、線性判別分析(Fisher Linear Discriminant Analysis，LDA)[1]和最大間距準(zhǔn)則(MMC)[2,3].PCA中的線性轉(zhuǎn)換矩陣W∈Rp×q由樣本協(xié)方差矩陣的最大特征向量(主成分)構(gòu)成，它盡可能的保持方差中的信息，并通過擴(kuò)展正交成分上的數(shù)據(jù)，獲得較小的重構(gòu)誤差.但是最大特征值對(duì)應(yīng)的特征向量所提供的去相關(guān)和統(tǒng)計(jì)顯著性的測量并不能保證分類器中類別的必要結(jié)構(gòu)信息.此外，與模型相關(guān)的分類信息可能會(huì)被忽略，因此PCA在很大意義上是次優(yōu)的.LDA[1]選擇使得Fisher準(zhǔn)則函數(shù)達(dá)到最大的向量作為最佳投影方向，從而使得訓(xùn)練樣本在該方向上投影后，得到最大的類間離散度和最小的類內(nèi)離散度.然而，在人臉圖像識(shí)別領(lǐng)域存在著大量的典型的小樣本問題，在該類問題中，類內(nèi)散布矩陣通常是奇異的.這主要是因?yàn)榇R(shí)別圖像向量的維數(shù)較高，而在實(shí)際問題中難以找到或根本不可能找到足夠多的訓(xùn)練樣本來保證類內(nèi)散布矩陣的可逆性.

為了避免模式識(shí)別中的小樣本問題，Li[2]、Song[3]等人提出了一種基于最大間距準(zhǔn)則(MMC)[2,3]的特征抽取方法，它是基于特征空間的類間散度與類內(nèi)散度的差的最大化，其目的是尋求一組最佳鑒別矢量為投影軸進(jìn)行投影變換，使得特征空間樣本的類間散度的最大，類內(nèi)散度最小.然而，MMC是基于L2-范數(shù)來計(jì)算相應(yīng)的目標(biāo)函數(shù).當(dāng)訓(xùn)練數(shù)據(jù)中存在野值或噪聲時(shí)，所取得的投影方向不穩(wěn)定，因?yàn)長2-范數(shù)中的平方操作放大了野值的影響，因此亟待需要解決MMC的魯棒性問題.

顯而易見，相對(duì)于L2-范數(shù)，L1-范數(shù)[4～7]中的絕對(duì)值操作減弱了對(duì)野值的影響，因此L1-范數(shù)對(duì)野值具有很強(qiáng)的魯棒性.最新文獻(xiàn)中也出現(xiàn)了基于L1-范數(shù)的線性投影降維方法，諸如：基于L1-范數(shù)的PCA(L1-norm-based Principal Component Analysis，PCA-L1)[4]及基于L1-范數(shù)的LDA(L1-norm-based Fisher Linear Discriminant Analysis，LDA-L1)[5,6].PCA-L1通過最大化特征空間中的基于L1-范數(shù)的方差以獲得局部最優(yōu)投影向量，但是PCA-L1沒有充分利用訓(xùn)練數(shù)據(jù)中的類別信息以獲得更有判別能力的投影方向.LDA-L1通過最大化基于L1-范數(shù)的類間離散度和基于L1-范數(shù)的類內(nèi)離散度的比率以獲得局部最優(yōu)投影向量.

受L1-范數(shù)在PCA與LDA上運(yùn)用取得的強(qiáng)魯棒性的啟發(fā)，為了克服MMC在數(shù)據(jù)含噪和有野值情況下的脆弱性，本文提出基于L1-范數(shù)的最大間距準(zhǔn)則，即MMC-L1.MMC-L1不僅充分利用L1-范數(shù)對(duì)野值及噪聲的強(qiáng)魯棒性，而且充分利用最大間距準(zhǔn)則以獲得更具有判別能力的投影方向.相比于以前的方法對(duì)野值及噪聲具有更強(qiáng)的魯棒性，并且在分類識(shí)別的性能上取得了顯著提高.

2　基于L1-范數(shù)的最大間距準(zhǔn)則

2.1問題公式化

J(W)=tr(WTSbW-αWTSwW)

(1)

通過簡單的轉(zhuǎn)換，式(1)可以寫成

(2)

從式(2)中可以看出，MMC的目標(biāo)函數(shù)依據(jù)L2-范數(shù)距離準(zhǔn)則.然而，平方操作會(huì)放大異常值的影響，因此，基于L1-范數(shù)的最大間距準(zhǔn)則的目標(biāo)函數(shù)如下：

(3)

(4)

其中，wTw=1.根據(jù)式(4)所求的一系列最優(yōu)解也許不同于根據(jù)式(3)所求的最優(yōu)解，但是它旨在尋求一個(gè)充分逼近.然而，絕對(duì)值操作并不是可微的，因此不易于直接獲得式(4)的全局最優(yōu)解.下面一節(jié)，描述了利用一個(gè)迭代算法找到式(4)局部最優(yōu)解的過程.

2.2尋找MMC-L1單個(gè)投影方向

我們采用一種梯度法來迭代計(jì)算MMC-L1最優(yōu)投影方向w.在迭代的第t(t=0,1,2,…)步時(shí)，由于目標(biāo)函數(shù)J(w(t))中存在絕對(duì)值符號(hào)，然而絕對(duì)值操作是非凸的，故為了消除絕對(duì)值符號(hào)，分別定義符號(hào)函數(shù):

(5)

再利用w(t+1)=w(t)+γg(w(t))來更新MMC-L1最優(yōu)投影方向w(t)，其中

(6)

0<γ<1為學(xué)習(xí)步長.循環(huán)交替計(jì)算式(5)的符號(hào)函數(shù)及式(6)的梯度公式來求解MMC-L1最優(yōu)投影方向w.在迭代過程中，若目標(biāo)函數(shù)J(w(t+1))停止增長，則終止循環(huán).否則，更新符號(hào)函數(shù)式(5)并繼續(xù)循環(huán)，直到找到滿足條件的投影向量w.由下一節(jié)的迭代收斂性可知，在每次循環(huán)計(jì)算式(5)與式(6)后，式(4)中的目標(biāo)函數(shù)J(w(t+1))都保持非降.

2.3MMC-L1多個(gè)投影方向擴(kuò)展

(7)

(8)

(9)

算法1MMC-L1算法

輸出：投影矩陣W=[w1,…,wq]∈Rp×q.

1.記l=0，Wl為空；

2.計(jì)算投影向量wl+1:

②初始化：設(shè)迭代次數(shù)t=0，并生成一個(gè)任意p維的非零向量β(0)；

③計(jì)算符號(hào)函數(shù)：

④更新為β(t+1)=β(t)+γg(t)，其中

4.合并Wl，wl+1:Wl+1=[Wl,wl+1]，其中

5.如果l+1

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

為了驗(yàn)證所提出的MMC-L1方法的魯棒性及最終識(shí)別性能，本文選擇在3個(gè)常用的人臉圖像數(shù)據(jù)庫(AR[9]、ORL[10]及Extended Yale B[11])上進(jìn)行先降維后分類識(shí)別的對(duì)比實(shí)驗(yàn).在實(shí)驗(yàn)中，我們選擇六種對(duì)比方法，分別是MMC-L1、MMC、LDA-L1、LDA、PCA-L1和PCA.為了保證實(shí)驗(yàn)結(jié)果的公平與合理性，同類實(shí)驗(yàn)中的參數(shù)設(shè)置均一致.為簡化實(shí)驗(yàn)，我們先采用最近鄰分類器進(jìn)行分類識(shí)別，再測試不同分類器對(duì)識(shí)別率的影響.

3.1AR人臉數(shù)據(jù)庫

AR[9]人臉數(shù)據(jù)庫由西班牙巴塞羅那計(jì)算機(jī)視覺中心建立，包括3120幅圖像，共120個(gè)人，每人26幅圖像，采集環(huán)境中的攝像機(jī)參數(shù)、光照環(huán)境、攝像機(jī)距離等都受到嚴(yán)格控制.所有人臉圖像都被縮放到50×40大小，量化到256級(jí)灰度.

3.1.1權(quán)重參數(shù)α對(duì)識(shí)別率的影響

本節(jié)展示了MMC-L1和MMC中的權(quán)重參數(shù)α對(duì)識(shí)別率的影響.其中每類的前一半作為訓(xùn)練集，余下的作為測試集.權(quán)重參數(shù)α的大小依次為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1、0.5、1、5、10，實(shí)驗(yàn)效果如圖1所示.

圖1表明，在提取投影向量的過程中，隨著權(quán)重參數(shù)α的逐漸增加，MMC的識(shí)別率逐漸增加，而MMC-L1的識(shí)別率先逐漸升高再逐漸降低.當(dāng)α<10時(shí)，MMC-L1的識(shí)別率高于MMC，因此選擇一個(gè)合適的權(quán)重參數(shù)α至關(guān)重要.

3.1.2測試訓(xùn)練集的大小對(duì)識(shí)別率的影響

為了驗(yàn)證不同的訓(xùn)練集大小對(duì)識(shí)別率的影響，本節(jié)選擇每類中前k(k=2,…,20)幅圖像作為訓(xùn)練集，余下的作為測試集.實(shí)驗(yàn)效果如圖2所示.

圖2表明，同等條件下，隨著訓(xùn)練樣本數(shù)目的增多，與其它方法相比，MMC-L1算法的識(shí)別率一直最高，這表明訓(xùn)練集的大小對(duì)最終識(shí)別率有很大的影響，但不影響MMC-L1算法的高效性.

3.1.3測試不同的投影軸數(shù)對(duì)識(shí)別率的影響

線性投影降維是處理高維數(shù)據(jù)的一個(gè)重要步驟.為驗(yàn)證不同的投影軸數(shù)對(duì)識(shí)別率的影響，本節(jié)依次選擇1,2,…,30個(gè)投影軸數(shù)進(jìn)行測試，其中每類的前一半作為訓(xùn)練集，余下的作為測試集.實(shí)驗(yàn)效果如圖3所示.

圖3表明，隨著投影軸數(shù)的逐漸增加，各種方法的識(shí)別率逐漸增高，并且當(dāng)投影軸數(shù)足夠大時(shí)，識(shí)別率都達(dá)到一個(gè)飽和值.然而，當(dāng)投影軸數(shù)相同時(shí)，MMC-L1方法的識(shí)別率比其它方法的識(shí)別率高.

3.2ORL人臉數(shù)據(jù)庫

ORL[10]數(shù)據(jù)庫是一個(gè)最為常用的人臉數(shù)據(jù)庫，它由40個(gè)人，每個(gè)人10幅92×112的灰度人臉正面圖像組成，每張人臉圖像都有姿態(tài)、表情和面部飾物的變化.所有的人臉圖像都被縮放到64×64大小，量化到256級(jí)灰度.

測試噪聲對(duì)識(shí)別率的影響:為了驗(yàn)證MMC-L1對(duì)噪聲的魯棒性，本節(jié)在加有高斯噪聲或椒鹽噪聲的人臉圖像上進(jìn)行對(duì)比分類識(shí)別實(shí)驗(yàn).圖4(a)和圖4(b)分別為加入高斯噪聲和椒鹽噪聲后的部分圖像示例，圖像加入高斯噪聲的方差或椒鹽噪聲的密度從小到大依次為0.0001、0.0005、0.001、0.005、0.01、0.05、0.1.實(shí)驗(yàn)效果如圖5所示.

圖5表明，當(dāng)噪聲的方差或密度較小時(shí)，MMC-L1和LDA-L1算法的識(shí)別率相差很小，但是隨著噪聲方差或密度的逐漸增加，MMC-L1的識(shí)別率高于LDA-L1的識(shí)別率，而且一直高于其它算法的識(shí)別率，這說明當(dāng)受到較強(qiáng)的外界條件干擾時(shí)，MMC-L1具有更好的魯棒性.

3.3Extended Yale B人臉數(shù)據(jù)庫

Extended Yale B[11]人臉數(shù)據(jù)庫包含38個(gè)人共2414幅圖片，其中人臉圖像的姿態(tài)和光照變化都是在嚴(yán)格控制的條件下采集的.本節(jié)依據(jù)文獻(xiàn)[11]的方法將Extended Yale B人臉數(shù)據(jù)庫分成5個(gè)子庫，分別為subfea1、subfea2、subfea3、subfea4和subfea5，其中subfea1中的圖像光照強(qiáng)度正常，而subfea2、subfea3、subfea4和subfea5的光照強(qiáng)度依次減弱，因此本部分為了去除光照強(qiáng)度對(duì)實(shí)驗(yàn)效果的影響，選擇Extended Yale B數(shù)據(jù)庫中光照條件較好的兩個(gè)子庫subfea1和subfea2分別作為訓(xùn)練集和測試集，所有人臉圖像都被縮放到32×32大小，量化到256級(jí)灰度.

3.3.1測試不同大小的隨機(jī)缺失遮擋塊對(duì)識(shí)別率的影響

為了驗(yàn)證所提出的MMC-L1的魯棒性，本節(jié)對(duì)訓(xùn)練集subfea1中的人臉圖像設(shè)置不同比例的缺失或遮擋，設(shè)置人臉圖像缺失或遮擋的百分比分別為5%、10%，15%，20%，25%，30%，35%，40%、45%、50%.圖6(a)為部分不同比例塊隨機(jī)缺失示例，圖6(b)為部分不同比例塊隨機(jī)遮擋示例.實(shí)驗(yàn)效果如圖7所示.

圖7表明，當(dāng)圖像的隨機(jī)缺失遮擋比例逐漸增大時(shí)，各種算法的識(shí)別率逐漸降低，而且MMC-L1的識(shí)一直高于其它算法的識(shí)別率，這說明MMC-L1具有較強(qiáng)的魯棒性.

3.3.2測試不同分類器對(duì)識(shí)別率的影響

為了測試不同分類器對(duì)所提方法最終識(shí)別率的影響，本節(jié)選擇3個(gè)常用的分類器(最近鄰分類器、SVM分類器和最近中心分類器)來測試各個(gè)算法的最終識(shí)別率.選擇子庫subfea1和subfea2分別作為訓(xùn)練集和測試集，并在測試某一個(gè)分類器的過程中設(shè)置不同的降維投影軸數(shù)，圖8顯示了各種方法隨著不同的投影維數(shù)在三種分類器下的識(shí)別率變化趨勢(shì).

從圖8(a)～(c)可知，對(duì)同一分類器，當(dāng)改變投影軸數(shù)時(shí)，識(shí)別率會(huì)隨著投影軸數(shù)的增加而提高，并且在三個(gè)不同分類器的實(shí)驗(yàn)中MMC-L1的識(shí)別率一致最高，其中采用SVM分類器時(shí)MMC-L1的識(shí)別率最高，因此可知在三種常見的分類器下，MMC-L1表現(xiàn)出一致的較高識(shí)別性能.

4　結(jié)束語

本文在PCA-L1、LDA-L1和MMC方法的基礎(chǔ)上，提出基于L1-范數(shù)的最大間距準(zhǔn)則(MMC-L1).該方法充分利用L1-范數(shù)對(duì)野值及噪聲的強(qiáng)魯棒性，充分利用最大間距準(zhǔn)則，提出了一個(gè)單調(diào)優(yōu)化迭代算法來求解其最優(yōu)投影矩陣，并給出了其單調(diào)收斂到局部最優(yōu)的證明.在多個(gè)圖像數(shù)據(jù)庫上的實(shí)驗(yàn)結(jié)果表明，所提出的MMC-L1對(duì)野值及噪聲具有強(qiáng)魯棒性，并且比其它方法具有更好的識(shí)別性能.注意到，本文所提出的方法僅僅是收斂到局部最優(yōu).在后續(xù)的工作中，我們將繼續(xù)深入研究如何找到全局最優(yōu).

[1]Duda R O,Hart P E,Stork D G.Pattern Classification[M].Second Edition.New York:John Wiley & Sons,2001.2-4.

[2]Haifeng Li,Tao Jiang,Keshu Zhang.Efficient and robust feature extraction by maximum margin criterion[J].IEEE Transactions on Neural Networks,2006,17(1):157-165.

[3]Fengxi Song,David Zhang,Qinglong Chen,et al.Face recognition based on a novel linear discriminant criterion[J].Pattern Anal Applic,2007,10(3):165-174.

[4]Kwak N.Principal component analysis based on L1-norm maximization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(9):1672-1680.

[5]Haixian Wang,Xuesong Lu,Zilan Hu,et al.Fisher discriminant analysis with L1-norm[J].IEEE Transactions on Cybernetics,2013,44(6):828-842.

[6]Fujin Zhong,Jiashu Zhang.Linear discriminant analysis based on L1-norm maximization[J].IEEE Transactions on Image Processing,2013,22(8):3018-3027.

[7]Haixian Wang,Qin Tang,Wenming Zheng.L1-norm-based common spatial patterns[J].IEEE Transactions on Biomedical Engineering,2012,59(3):653-662.

[8]Obozinski G,Bach F,Jenatton R.Structured sparse principal component analysis[J].HAL-INRIA,2009,43(6):1505-1527.

[9]Martinez A M,Benavente R.The AR Face Database[R].USA:Purdue University,1998.

[10]Samaria F,Harter A.Parameterisation of a stochastic model for human face identification[A].Proceedings of the Second IEEE Workshop on Applications of Computer Vision[C].Sarasota:IEEE,1994.138-142.

[11]Imran Naseem,Roberto Togneri,Mohammed Bennamoun.Linear regression for face recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(11):2106-2112.

陳思寶男，1979年8月出生于安徽天長.現(xiàn)為安徽大學(xué)副教授，碩士生導(dǎo)師，目前從事圖像處理與模式識(shí)別方面的研究.

E-mail:sbchen@ahu.edu.cn

陳道然女，1989年5月出生于河南信陽.現(xiàn)為安徽大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)碩士研究生，主要從事圖像處理與模式識(shí)別方面的研究.

E-mail：youzi-90@163.com

羅斌男，1963年5月出生于安徽合肥，現(xiàn)為安徽大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)系博士生導(dǎo)師，主要從事計(jì)算機(jī)視覺與模式識(shí)別方面的研究.

L1-Norm-Based Maximum Margin Criterion

CHEN Si-bao1,2,CHEN Dao-ran1,2,LUO Bin1,2

(1.SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei,Anhui230601,China;2.KeyLaboratoryforIndustrialImageProcessingandAnalysisofAnhuiProvince,Hefei,Anhui230039,China)

When performing dimensionality reduction with linear projections,maximum margin criterion (MMC) is often affected by outliers and noises due to L2-norm.In this paper,L1-norm-based maximum margin criterion (MMC-L1) is proposed for dimensionality reduction.It makes full use of Maximum Margin Criterion and strong robustness of L1-norm to outliers and noises.A rapid iterative optimization algorithm,with its proof of monotonic convergence to local optimum,is given.Experiments on several public image databases verify the robustness and efficiency of the proposed method.

maximum margin criterion (MMC);L1-norm;linear projection;dimensionality reduction

2014-12-01;修回日期:2015-05-05;責(zé)任編輯：梅志強(qiáng)

國家863計(jì)劃項(xiàng)目(No.2014AA015104);國家自然科學(xué)基金(No.61202228，No.61472002);安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目(No.KJ2012A004);安徽省電力公司科技項(xiàng)目(No.521200130MOU，No.5212M01353B4)

TP391.4

A

0372-2112 (2016)06-1383-06