賈 旭,孫福明,李豪杰,曹玉東
(1.遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院,遼寧 錦州 121001; 2.大連理工大學(xué) 軟件學(xué)院,遼寧 大連 116024)(*通信作者電子郵箱gbjdjiaxu@163.com)
特征提取是模式識(shí)別的關(guān)鍵問(wèn)題之一,其提取特征的有效性將對(duì)識(shí)別效果產(chǎn)生重要影響。一般來(lái)說(shuō),直接對(duì)圖像進(jìn)行特征提取后將得到較高維度的特征向量,而通常這些高維特征向量存在較大的冗余,并且很難知道該特征是否有利于識(shí)別與分類,從而影響識(shí)別的效率與普適性,因此,關(guān)于如何獲得一種低維有效并具有普適性的圖像特征的研究具有重要意義。
目前,特征降維可分為無(wú)監(jiān)督降維方法和有監(jiān)督降維方法。其中,無(wú)監(jiān)督降維方法包括主成分分析法(Principal Component Analysis, PCA)、局部保持投影法(Locality Preserving Projection, LPP)、稀疏表示法(Sparse Representation, SP)等[1];而有監(jiān)督降維方法包括離散判別分析(Linear Discriminant Analysis, LDA)、最大邊緣準(zhǔn)則法(Maximum Margin Criterion, MMC)等[2]。在圖像特征提取過(guò)程中,基于以上方法可以獲得新的特征基與分解系數(shù),而分解系數(shù)將作為新的圖像特征。從數(shù)學(xué)的角度來(lái)說(shuō),新的特征基與分解系數(shù)可以是負(fù)值,也可以是正值或0,但對(duì)于一些特定的應(yīng)用背景,負(fù)值將很難被賦予實(shí)際的意義,如圖像像素值都是非負(fù)的,因此分解得到的基圖像中的負(fù)值難以被解釋和表達(dá)。1999年,Lee等[3]提出了一種非負(fù)矩陣分解(Nonnegative Matrix Factorization, NMF)的數(shù)據(jù)降維方法,從而使降維后數(shù)據(jù)的意義得到了更好的詮釋。而后,一些學(xué)者將其進(jìn)行了改進(jìn),并應(yīng)用在了圖像識(shí)別或分類上,其中包括:從特征的稀疏性考慮,提出了稀疏約束的NMF[4-5];從特征基的相關(guān)性考慮,提出了正交約束的NMF[6-7];從不同類別特征的區(qū)分性考慮,提出了離散判別約束的NMF[8-9];從特征的非線性特性考慮,提出了流形約束的NMF[10];從特征匹配策略考慮,提出了匹配測(cè)量約束的NMF[11-12];從特征向量結(jié)構(gòu)考慮,提出了圖正則化約束的NMF[13]等。以上方法分別從不同的角度考慮,采用了不同的約束條件進(jìn)行非負(fù)矩陣分解,從而獲得滿足各自需求的新的特征基與特征向量。
特征提取與分類器設(shè)計(jì)是模式識(shí)別的兩個(gè)關(guān)鍵問(wèn)題,提取出有效的圖像特征將會(huì)大幅度降低分類器的分類壓力?,F(xiàn)有的算法雖然可以取得一定的分類效果,但并未針對(duì)特征提取方法的普適性進(jìn)行分析,為此,本文提出了一種具有普適性的基于改進(jìn)NMF的圖像特征提取方法。該方法同時(shí)考慮了圖像特征的低維性、稀疏性、類間區(qū)分性,在原始NMF模型基礎(chǔ)上,加入了稀疏正則項(xiàng)與聚類屬性正則項(xiàng),形成了改進(jìn)的NMF模型,并通過(guò)梯度下降法對(duì)其進(jìn)行求解,從而獲得新的圖像特征。實(shí)驗(yàn)表明,在幾種常用分類器下,提出的算法獲得的圖像特征更有利于圖像的正確識(shí)別或分類。
Y≈UV
s.t.uij,vjk≥0
(1)
然而,若想獲得有效的圖像特征,僅僅滿足基向量與系數(shù)向量非負(fù)性是不夠的,應(yīng)對(duì)NMF模型增加約束條件,使獲得的新的特征向量,即系數(shù)向量更有利于圖像的分類或識(shí)別。以下將從兩方面對(duì)模型約束條件進(jìn)行分析:
1)稀疏性。信號(hào)稀疏表示的目的就是在超完備字典中用盡可能少的原子來(lái)表示信號(hào),獲得信號(hào)更為簡(jiǎn)潔的表示方式[14]。而在基于NMF的圖像特征提取過(guò)程中,則希望在NMF分解得到的基圖像中用盡可能少的組合來(lái)表示原始圖像,從而更容易地獲取圖像中所蘊(yùn)含的信息,因此,NMF模型需增加稀疏性約束,如式(2)所示:
(2)
其中α為平衡因子。
根據(jù)壓縮感知理論,求解V的0范數(shù)是一個(gè)NP難問(wèn)題,為求解方便,可以將求解V的0范數(shù)轉(zhuǎn)化為求解2范數(shù),如式(3)所示:
(3)
2)聚類屬性。對(duì)圖像進(jìn)行特征提取時(shí),好的圖像特征應(yīng)滿足以下屬性,即不同類的圖像特征應(yīng)具有較大的可區(qū)分性,這樣的特征將更利于正確識(shí)別或分類。這里,選用歐氏距離作為特征間相似性的測(cè)度函數(shù),那么特征類間區(qū)分性可分別用式(4)來(lái)表示:
(4)
因此,需對(duì)NMF模型作進(jìn)一步的改進(jìn),即添加聚類屬性約束項(xiàng),如式(5)所示:
(5)
其中:β為平衡因子。
為方便模型求解,需將式(4)轉(zhuǎn)化為矩陣表達(dá)形式。
(6)
(7)
這里
再將類間平均特征向量差異轉(zhuǎn)化為矩陣形式。
令
可得式(8):
(8)
(9)
另外,稀疏約束項(xiàng)可由式(10)表示:
‖V‖2=tr(VTV)
(10)
至此,改進(jìn)的NMF模型可轉(zhuǎn)化為式(11):
(11)
建立模型后,將采用梯度下降法對(duì)該模型進(jìn)行優(yōu)化求解,最終求得全局或局部極小值。
經(jīng)過(guò)化簡(jiǎn),目標(biāo)函數(shù)式(11)可以轉(zhuǎn)化為式(12):
(12)
根據(jù)tr(PQ)=tr(QP),式(12)可轉(zhuǎn)化為式(13):
(13)
而后,求解式(13)對(duì)U與V的偏導(dǎo)數(shù),如式(14)、式(15):
(14)
βVAZBT+βVBAZT-βVBBT
(15)
給定U與V的初始值后,將按照以下迭代規(guī)則式(16)與式(17)迭代,直至滿足停止條件。
(16)
vij,(t+1)←vij,(t)·
(17)
梯度下降具體計(jì)算過(guò)程如下。
輸入量:初始特征矩陣Y,平衡因子α與β。
步驟1 給定初始化矩陣U(0)與V(0),矩陣所有元素均在0與1之間,設(shè)置最大迭代次數(shù)nmax,迭代誤差閾值e,計(jì)數(shù)器初始化t=0。
步驟2 計(jì)數(shù)器自增t=t+1。
步驟3 求解式(12)的值J(U(t),V(t))。
如果J(U(t),V(t))
步驟4 對(duì)U與V中所有元素按以下規(guī)則進(jìn)行迭代;
vij,(t+1)←vij,(t)·
迭代后進(jìn)入步驟2。
步驟5 迭代結(jié)束,得到最優(yōu)解U(t)與V(t)。
為證明式(16)與式(17)收斂性,需要引入一個(gè)輔助函數(shù)。
定義1 如式(18)與式(19)成立,定義G(h,h′)是F(h)輔助函數(shù):
G(h,h′)≥F(h)
(18)
G(h,h)=F(h)
(19)
引理1 如果G是一個(gè)輔助函數(shù),則函數(shù)F在式(20)迭代更新規(guī)則是非增的:
(20)
證明F(ht+1)≤G(ht+1,ht)≤G(ht,ht)=F(ht)。
(21)
因此,通過(guò)定義輔助函數(shù),可證明式(16)與式(17)收斂性。
對(duì)于目標(biāo)函數(shù)式(11),假設(shè)U為獨(dú)立的變量,可得:
(22)
(23)
這里,F(xiàn)(u)=J(u),0
引理2 假設(shè)U為獨(dú)立變量,可定義式(24)為輔助函數(shù):
(24)
證明 由G(u,u)=F(u),只需證明G(u,uij)≥F(uij)。
將目標(biāo)函數(shù)(11)進(jìn)行泰勒級(jí)數(shù)展開(kāi),得到式(25):
(25)
uij(VVT)jj≥uij(VVT)jj
(26)
因此,引理2證畢。
對(duì)于目標(biāo)函數(shù)式(11),假設(shè)V為獨(dú)立的變量,可得:
βVAZBT+βVBAZT-βVBBT)ij
(27)
(28)
這里,F(xiàn)(u)=J(u),0
引理3 假設(shè)V為獨(dú)立變量時(shí),可定義式(29)為輔助函數(shù):
G(v,vij)=F(vij)+F′(vij)(v-vij)+
(29)
證明 由G(v,v)=F(v),只需證明G(v,vij)≥F(vij)。
將目標(biāo)函數(shù)(11)進(jìn)行泰勒級(jí)數(shù)展開(kāi),得到式(30):
(30)
(UTU)iivij≥(UTU)iivij
(31)
(αV)ij=αvij
(32)
BAZT)jj>vij(AZBT+BAZT-AZAZT-BBT)jj
(33)
因此,引理3證畢。
本實(shí)驗(yàn)選擇3個(gè)數(shù)據(jù)庫(kù),即人臉數(shù)據(jù)集[15]、指靜脈數(shù)據(jù)庫(kù)[16]、手背靜脈數(shù)據(jù)庫(kù)[17],其中部分樣本圖像如圖1所示。
圖1 部分實(shí)驗(yàn)樣本示意圖
人臉數(shù)據(jù)庫(kù)中包含有40個(gè)對(duì)象,每個(gè)對(duì)象有10幅圖像,共計(jì)400幅圖像;指靜脈數(shù)據(jù)庫(kù)包含64個(gè)對(duì)象,每個(gè)對(duì)象有10幅圖像,共計(jì)640幅圖像;手背靜脈數(shù)據(jù)庫(kù)包含38個(gè)對(duì)象,每個(gè)對(duì)象包含5至10幅圖像不等,共計(jì)245幅圖像。
此外,實(shí)驗(yàn)軟件環(huán)境為Windows 7操作系統(tǒng),Matlab 2014b編程工具;硬件為PC,其中,處理器為Intel Core i5- 4460 3.2 GHz,8 GB內(nèi)存。
改進(jìn)的NMF模型中共包含3個(gè)可調(diào)參數(shù),分別為降維后特征維數(shù)r、平衡因子α與β。這里,將分別在不同參數(shù)組合的條件下進(jìn)行實(shí)驗(yàn),從而選擇最優(yōu)的模型參數(shù)。本實(shí)驗(yàn)首先將圖像進(jìn)行分塊處理,即每個(gè)圖像塊的大小為32×32像素,而相鄰子圖像塊重疊16像素,并將其作為窗口逐行逐列進(jìn)行滑動(dòng),如圖2所示。
圖2 樣本圖像分塊示意圖
提取每一子圖像8個(gè)方向的直方圖(Histogram of Oriented Gradient, HOG)特征[18],而后逐行逐列融合所有子圖像的特征,從而形成圖像的初始特征。
當(dāng)調(diào)整模型的參數(shù)時(shí),最優(yōu)的模型參數(shù)將可以獲得最優(yōu)的識(shí)別結(jié)果。這里,令平衡因子α與β分別依次取值1,0.1,0.01;特征維數(shù)的取值分別為原特征維數(shù)的30%至70%;識(shí)別時(shí)采用最近鄰分類器;樣本進(jìn)行5次交叉檢驗(yàn),使得每一個(gè)的圖像都有機(jī)會(huì)成為訓(xùn)練樣本和測(cè)試樣本;并利用錯(cuò)誤接受率(False Accept Rate, FAR)與錯(cuò)誤拒絕率(False Reject Rate, FRR)作為衡量識(shí)別效果的標(biāo)準(zhǔn)。
對(duì)于人臉圖像數(shù)據(jù)庫(kù),當(dāng)采用不同模型參數(shù)時(shí),實(shí)驗(yàn)所得到的FAR值與FRR值分布如圖3所示。
圖3中的FAR與FRR值是針對(duì)不同數(shù)據(jù)集實(shí)驗(yàn)后加權(quán)求和得到的,如式(34)與式(35)所示:
(34)
(35)
由圖3可知,對(duì)于選擇的3種數(shù)據(jù)集,當(dāng)平衡因子α=0.1,β=0.1時(shí),F(xiàn)AR值為0.021,F(xiàn)RR值為0.025,進(jìn)而在該參數(shù)下可獲得最低的FAR+FRR值,即可獲得最優(yōu)的識(shí)別效果,因此,將改進(jìn)的NMF模型中參數(shù)設(shè)定為α=0.1,β=0.1。
同樣針對(duì)應(yīng)用的3種樣本數(shù)據(jù)庫(kù),對(duì)圖像按4.2節(jié)中方法進(jìn)行初始特征提取,識(shí)別時(shí)采用最近鄰分類器,通過(guò)FAR-GAR曲線來(lái)對(duì)改進(jìn)的NMF特征降維方法與其他降維方法的性能進(jìn)行比較,其中GAR(Genuine Accept Rate)為真實(shí)接受率。
首先,不考慮降維后圖像特征的實(shí)際意義,僅僅從數(shù)學(xué)分析的角度出發(fā),將提出的算法與幾類經(jīng)典的數(shù)據(jù)降維方法進(jìn)行比較,即PCA、LDA、LPP降維方法,比較結(jié)果如圖4所示。
由圖4可以看出,當(dāng)FAR為0.05時(shí),提出的改進(jìn)NMF模型在識(shí)別過(guò)程中達(dá)到0.96的真實(shí)接受率(GAR),高于其他算法GAR值0.21以上;此外,提出的改進(jìn)NMF模型的FAR-GAR識(shí)別性能曲線整體上在其他降維方法的FAR-GAR曲線之上,可說(shuō)明提出的改進(jìn)的NMF模型相對(duì)于PCA、LDA、LPP可獲得更好的識(shí)別效果。
然后,考慮降維后圖像特征的實(shí)際意義,即降維后特征具有非負(fù)性特點(diǎn),將提出的算法與幾類常用的NMF降維方法進(jìn)行比較,這些NMF模型分別從不同的角度出發(fā),對(duì)降維后特征分別賦予不同的約束條件,即SNMF(Sparse Nonnegative Matrix Factorization)模型、DNMF(Discriminate Nonnegative Matrix Factorization)模型、匹配測(cè)量約束的NMF模型[11]、半監(jiān)督稀疏約束的NMF模型[18],比較結(jié)果如圖5所示。
同樣,由圖5可以看出,當(dāng)FAR為0.05時(shí),提出的改進(jìn)NMF模型的GAR值高于其他算法0.14以上;此外,從不同方法的FAR-GAR曲線的位置來(lái)看,提出的改進(jìn)NMF模型的FAR-GAR曲線明顯高于SNMF模型、DNMF模型、半監(jiān)督SNMF模型,略高于匹配測(cè)量約束的NMF模型,亦可說(shuō)明改進(jìn)的NMF模型在識(shí)別效果上的優(yōu)勢(shì)。
圖3 不同參數(shù)下識(shí)別效果比較
圖4 本文模型與經(jīng)典降維算法識(shí)別性能比較
圖5 多種改進(jìn)NMF算法識(shí)別性能比較
本文通過(guò)對(duì)NMF模型進(jìn)行分析與改進(jìn),提出了一種更具普適性的特征降維與優(yōu)化方法,其創(chuàng)新點(diǎn)在于考慮新特征稀疏特性的同時(shí),將特征的聚類屬性也作為NMF的另一約束項(xiàng),通過(guò)實(shí)驗(yàn)驗(yàn)證,提出的算法降維得到的特征更有利于圖像的分類或識(shí)別。在取得一定效果的同時(shí),仍存在一些問(wèn)題有待解決,如選擇的樣本庫(kù)種類及樣本數(shù)還需增加,從而進(jìn)一步提高方法的普適性。
References)
[1] SHAN H, ZHANG J, KRUGER U. Learning linear representation of sparse partitioning trees based on unsupervised kernel dimension reduction [J]. IEEE Transaction on Cybernetics, 2016, 46(12): 3427-3438.
[2] VLASSIS N, MOTOMURA Y, KROSE B. Supervised dimension reduction of intrinsically low-dimensional data [J]. Neural Computation, 2014, 14(1): 191-215.
[3] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization [J]. Nature, 1999, 401(6755): 788-791.
[4] HAN H, LIU S J, GAN L. Non-negativity and dependence constrained sparse coding for image classification [J]. Journal of Visual Communication and Image Representation, 2015, 26: 247-254.
[5] WEN J H, TIAN Z, LIU X Z, et al. Neighborhood preserving orthogonal PNMF feature extraction for hyperspectral image classification [J]. IEEE Journal of Selected Topic in Applied Earth Observations and Remote Sensing, 2013, 6(2): 759-768.
[6] POMPILI F, GILLIS N, ABSIL P A, et al. Two algorithms for orthogonal nonnegative matrix factorization with application to clustering [J]. Neurocomputing, 2014, 141(2): 15-25.
[7] KOTSIA I, ZAFEIRIOU S, PITAS I. A novel discriminant non-negative matrix factorization algorithm with applications to facial image characterization problems [J]. IEEE Transactions on Information Forensics and Security, 2007, 2(3): 588-595.
[8] ZDUNEK R, PHAN A H, CICHOCKI A. Image classification with nonnegative matrix factorization based on spectral projected gradient [J]. Artificial Neural Networks, 2015, 4: 31-50.
[9] JI Z, PANG Y, LI X. Relevance preserving projection and ranking based on one-class classification for Web image [J]. IEEE Transactions on Image Processing, 2015, 24(11): 4137-4147.
[10] 汪金濤,曹玉東,孫福明.稀疏約束圖正則非負(fù)矩陣分解的增量學(xué)習(xí)算法[J].計(jì)算機(jī)應(yīng)用,2017,37(4):1071-1074.(WANG J T, CAO Y D, SUN F M. Incremental learning algorithm based on graph regularized non-negative matrix factorization with sparseness constraints [J]. Journal of Computer Applications, 2017, 37(4): 1071-1074.)
[11] JIA X, SUN F M, LI H J, et al. Image multi-label annotation based on supervised nonnegative matrix factorization with new matching measurement [J]. Neurocomputing, 2017, 219(C): 518-525.
[12] LIU H, WU Z, CAI D, et al. Constrained nonnegative matrix factorization for image representation [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2012, 34(7): 1299-1311.
[13] CAI D, HE X, HAN J, et al. Graph regularized nonnegative matrix factorization for data representation [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(8): 1548-1560.
[14] LIU Q. Kernel local sparse representation based classifier [J]. Neural Processing Letters, 2016, 60(1): 1684-1695.
[15] YIN Y L, LIU L L, SUN X W. SDUMLA-HMT: a multimodal biometric database [C]// Proceedings of the 6th Chinese Conference on Biometric Recognition. Beijing: [s.n.], 2011: 260-268.
[16] CHUA T S, TANG J, HONG R, et al. NUSWIDE: a real-world Web image database from National University of Singapore [C]// Proceedings of the 2009 ACM International Conference on Image and Video Retrieval. New York: ACM, 2009: 48.
[17] 苑瑋琦,王爇,孫書(shū)會(huì).基于2DFLD的手背靜脈識(shí)別算法[J].計(jì)算機(jī)應(yīng)用,2010,30(3):646-649.(YUAN W Q, WANG R, SUN S H. Palm-dorsa vein recognition based on two-dimensional Fisher linear discriminant [J]. Journal of Computer Applications, 2010, 30(3): 646-649.)
[18] 胡學(xué)考,孫福明,李豪杰.基于稀疏約束的半監(jiān)督非負(fù)矩陣分解算法[J].計(jì)算機(jī)科學(xué),2015,42(7):280-284.(HU X K, SUN F M, LI H J. Constrained nonnegative matrix factorization with sparseness for image representation [J]. Computer Science, 2015, 42(7): 280-284.)
This work is partially supported by the National Natural Science Foundation of China (61502216, 61572244).
JIAXu, born in 1983, Ph. D., associate professor. His research interests include pattern recognition, machine learning.
SUNFuming, born in 1972, Ph. D., professor. His research interests include multimedia processing, machine learning.
LIHaojie, born in 1973, Ph. D., professor. His research interests include multimedia processing, computer vision.
CAOYudong, born in 1971, Ph. D., associate professor. His research interests include pattern recognition, image processing.