具有普適性的改進非負矩陣分解圖像特征提取方法

賈 旭，孫福明，李豪杰，曹玉東

(1.遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001； 2.大連理工大學 軟件學院，遼寧 大連 116024)(*通信作者電子郵箱gbjdjiaxu@163.com)

0 引言

特征提取是模式識別的關鍵問題之一，其提取特征的有效性將對識別效果產生重要影響。一般來說，直接對圖像進行特征提取后將得到較高維度的特征向量，而通常這些高維特征向量存在較大的冗余，并且很難知道該特征是否有利于識別與分類，從而影響識別的效率與普適性，因此，關于如何獲得一種低維有效并具有普適性的圖像特征的研究具有重要意義。

目前，特征降維可分為無監督降維方法和有監督降維方法。其中，無監督降維方法包括主成分分析法(Principal Component Analysis, PCA)、局部保持投影法(Locality Preserving Projection, LPP)、稀疏表示法(Sparse Representation, SP)等[1]；而有監督降維方法包括離散判別分析(Linear Discriminant Analysis, LDA)、最大邊緣準則法(Maximum Margin Criterion, MMC)等[2]。在圖像特征提取過程中，基于以上方法可以獲得新的特征基與分解系數，而分解系數將作為新的圖像特征。從數學的角度來說，新的特征基與分解系數可以是負值，也可以是正值或0，但對于一些特定的應用背景，負值將很難被賦予實際的意義，如圖像像素值都是非負的，因此分解得到的基圖像中的負值難以被解釋和表達。1999年，Lee等[3]提出了一種非負矩陣分解(Nonnegative Matrix Factorization, NMF)的數據降維方法，從而使降維后數據的意義得到了更好的詮釋。而后，一些學者將其進行了改進，并應用在了圖像識別或分類上，其中包括：從特征的稀疏性考慮，提出了稀疏約束的NMF[4-5]；從特征基的相關性考慮，提出了正交約束的NMF[6-7]；從不同類別特征的區分性考慮，提出了離散判別約束的NMF[8-9]；從特征的非線性特性考慮，提出了流形約束的NMF[10]；從特征匹配策略考慮，提出了匹配測量約束的NMF[11-12]；從特征向量結構考慮，提出了圖正則化約束的NMF[13]等。以上方法分別從不同的角度考慮，采用了不同的約束條件進行非負矩陣分解，從而獲得滿足各自需求的新的特征基與特征向量。

特征提取與分類器設計是模式識別的兩個關鍵問題，提取出有效的圖像特征將會大幅度降低分類器的分類壓力。現有的算法雖然可以取得一定的分類效果，但并未針對特征提取方法的普適性進行分析，為此，本文提出了一種具有普適性的基于改進NMF的圖像特征提取方法。該方法同時考慮了圖像特征的低維性、稀疏性、類間區分性，在原始NMF模型基礎上，加入了稀疏正則項與聚類屬性正則項，形成了改進的NMF模型，并通過梯度下降法對其進行求解，從而獲得新的圖像特征。實驗表明，在幾種常用分類器下，提出的算法獲得的圖像特征更有利于圖像的正確識別或分類。

1 改進NMF模型的建立

Y≈UV

s.t.uij,vjk≥0

(1)

然而，若想獲得有效的圖像特征，僅僅滿足基向量與系數向量非負性是不夠的，應對NMF模型增加約束條件，使獲得的新的特征向量，即系數向量更有利于圖像的分類或識別。以下將從兩方面對模型約束條件進行分析：

1)稀疏性。信號稀疏表示的目的就是在超完備字典中用盡可能少的原子來表示信號，獲得信號更為簡潔的表示方式[14]。而在基于NMF的圖像特征提取過程中，則希望在NMF分解得到的基圖像中用盡可能少的組合來表示原始圖像，從而更容易地獲取圖像中所蘊含的信息，因此，NMF模型需增加稀疏性約束，如式(2)所示：

(2)

其中α為平衡因子。

根據壓縮感知理論，求解V的0范數是一個NP難問題，為求解方便，可以將求解V的0范數轉化為求解2范數，如式(3)所示：

(3)

2)聚類屬性。對圖像進行特征提取時，好的圖像特征應滿足以下屬性，即不同類的圖像特征應具有較大的可區分性，這樣的特征將更利于正確識別或分類。這里，選用歐氏距離作為特征間相似性的測度函數，那么特征類間區分性可分別用式(4)來表示：

(4)

因此，需對NMF模型作進一步的改進，即添加聚類屬性約束項，如式(5)所示：

(5)

其中：β為平衡因子。

為方便模型求解，需將式(4)轉化為矩陣表達形式。

(6)

(7)

這里

再將類間平均特征向量差異轉化為矩陣形式。

令

可得式(8)：

(8)

(9)

另外，稀疏約束項可由式(10)表示：

‖V‖2=tr(VTV)

(10)

至此，改進的NMF模型可轉化為式(11)：

(11)

2 基于梯度下降的模型求解

建立模型后，將采用梯度下降法對該模型進行優化求解，最終求得全局或局部極小值。

經過化簡，目標函數式(11)可以轉化為式(12)：

(12)

根據tr(PQ)=tr(QP)，式(12)可轉化為式(13)：

(13)

而后，求解式(13)對U與V的偏導數，如式(14)、式(15)：

(14)

βVAZBT+βVBAZT-βVBBT

(15)

給定U與V的初始值后，將按照以下迭代規則式(16)與式(17)迭代，直至滿足停止條件。

(16)

vij,(t+1)←vij,(t)·

(17)

梯度下降具體計算過程如下。

輸入量：初始特征矩陣Y，平衡因子α與β。

步驟1 給定初始化矩陣U(0)與V(0)，矩陣所有元素均在0與1之間，設置最大迭代次數nmax，迭代誤差閾值e，計數器初始化t=0。

步驟2 計數器自增t=t+1。

步驟3 求解式(12)的值J(U(t),V(t))。

如果J(U(t),V(t))nmax，則進入步驟5；否則進入步驟4。

步驟4 對U與V中所有元素按以下規則進行迭代；

vij,(t+1)←vij,(t)·

迭代后進入步驟2。

步驟5 迭代結束，得到最優解U(t)與V(t)。

3 收斂性證明

為證明式(16)與式(17)收斂性，需要引入一個輔助函數。

定義1 如式(18)與式(19)成立，定義G(h,h′)是F(h)輔助函數：

G(h,h′)≥F(h)

(18)

G(h,h)=F(h)

(19)

引理1 如果G是一個輔助函數，則函數F在式(20)迭代更新規則是非增的：

(20)

證明F(ht+1)≤G(ht+1,ht)≤G(ht,ht)=F(ht)。

(21)

因此，通過定義輔助函數，可證明式(16)與式(17)收斂性。

對于目標函數式(11)，假設U為獨立的變量，可得：

(22)

(23)

這里，F(u)=J(u)，0

引理2 假設U為獨立變量，可定義式(24)為輔助函數：

(24)

證明 由G(u,u)=F(u)，只需證明G(u,uij)≥F(uij)。

將目標函數(11)進行泰勒級數展開，得到式(25)：

(25)

uij(VVT)jj≥uij(VVT)jj

(26)

因此，引理2證畢。

對于目標函數式(11)，假設V為獨立的變量，可得：

βVAZBT+βVBAZT-βVBBT)ij

(27)

(28)

這里，F(u)=J(u)，0

引理3 假設V為獨立變量時，可定義式(29)為輔助函數：

G(v,vij)=F(vij)+F′(vij)(v-vij)+

(29)

證明 由G(v,v)=F(v)，只需證明G(v,vij)≥F(vij)。

將目標函數(11)進行泰勒級數展開，得到式(30)：

(30)

(UTU)iivij≥(UTU)iivij

(31)

(αV)ij=αvij

(32)

BAZT)jj>vij(AZBT+BAZT-AZAZT-BBT)jj

(33)

因此，引理3證畢。

4 實驗結果及分析

4.1 實驗樣本庫及實驗環境

本實驗選擇3個數據庫，即人臉數據集[15]、指靜脈數據庫[16]、手背靜脈數據庫[17]，其中部分樣本圖像如圖1所示。

圖1 部分實驗樣本示意圖

人臉數據庫中包含有40個對象，每個對象有10幅圖像，共計400幅圖像；指靜脈數據庫包含64個對象，每個對象有10幅圖像，共計640幅圖像；手背靜脈數據庫包含38個對象，每個對象包含5至10幅圖像不等，共計245幅圖像。

此外，實驗軟件環境為Windows 7操作系統，Matlab 2014b編程工具；硬件為PC，其中，處理器為Intel Core i5- 4460 3.2 GHz，8 GB內存。

4.2 參數設定

改進的NMF模型中共包含3個可調參數，分別為降維后特征維數r、平衡因子α與β。這里，將分別在不同參數組合的條件下進行實驗，從而選擇最優的模型參數。本實驗首先將圖像進行分塊處理，即每個圖像塊的大小為32×32像素，而相鄰子圖像塊重疊16像素，并將其作為窗口逐行逐列進行滑動，如圖2所示。

圖2 樣本圖像分塊示意圖

提取每一子圖像8個方向的直方圖(Histogram of Oriented Gradient, HOG)特征[18]，而后逐行逐列融合所有子圖像的特征，從而形成圖像的初始特征。

當調整模型的參數時，最優的模型參數將可以獲得最優的識別結果。這里，令平衡因子α與β分別依次取值1，0.1，0.01；特征維數的取值分別為原特征維數的30%至70%；識別時采用最近鄰分類器；樣本進行5次交叉檢驗，使得每一個的圖像都有機會成為訓練樣本和測試樣本；并利用錯誤接受率(False Accept Rate, FAR)與錯誤拒絕率(False Reject Rate, FRR)作為衡量識別效果的標準。

對于人臉圖像數據庫，當采用不同模型參數時，實驗所得到的FAR值與FRR值分布如圖3所示。

圖3中的FAR與FRR值是針對不同數據集實驗后加權求和得到的，如式(34)與式(35)所示：

(34)

(35)

由圖3可知，對于選擇的3種數據集，當平衡因子α=0.1，β=0.1時，FAR值為0.021，FRR值為0.025，進而在該參數下可獲得最低的FAR+FRR值，即可獲得最優的識別效果，因此，將改進的NMF模型中參數設定為α=0.1，β=0.1。

4.3 方法比較及分析

同樣針對應用的3種樣本數據庫，對圖像按4.2節中方法進行初始特征提取，識別時采用最近鄰分類器，通過FAR-GAR曲線來對改進的NMF特征降維方法與其他降維方法的性能進行比較，其中GAR(Genuine Accept Rate)為真實接受率。

首先，不考慮降維后圖像特征的實際意義，僅僅從數學分析的角度出發，將提出的算法與幾類經典的數據降維方法進行比較，即PCA、LDA、LPP降維方法，比較結果如圖4所示。

由圖4可以看出，當FAR為0.05時，提出的改進NMF模型在識別過程中達到0.96的真實接受率(GAR)，高于其他算法GAR值0.21以上；此外，提出的改進NMF模型的FAR-GAR識別性能曲線整體上在其他降維方法的FAR-GAR曲線之上，可說明提出的改進的NMF模型相對于PCA、LDA、LPP可獲得更好的識別效果。

然后，考慮降維后圖像特征的實際意義，即降維后特征具有非負性特點，將提出的算法與幾類常用的NMF降維方法進行比較，這些NMF模型分別從不同的角度出發，對降維后特征分別賦予不同的約束條件，即SNMF(Sparse Nonnegative Matrix Factorization)模型、DNMF(Discriminate Nonnegative Matrix Factorization)模型、匹配測量約束的NMF模型[11]、半監督稀疏約束的NMF模型[18]，比較結果如圖5所示。

同樣，由圖5可以看出，當FAR為0.05時，提出的改進NMF模型的GAR值高于其他算法0.14以上；此外，從不同方法的FAR-GAR曲線的位置來看，提出的改進NMF模型的FAR-GAR曲線明顯高于SNMF模型、DNMF模型、半監督SNMF模型，略高于匹配測量約束的NMF模型，亦可說明改進的NMF模型在識別效果上的優勢。

圖3 不同參數下識別效果比較

圖4 本文模型與經典降維算法識別性能比較

圖5 多種改進NMF算法識別性能比較

5 結語

本文通過對NMF模型進行分析與改進，提出了一種更具普適性的特征降維與優化方法，其創新點在于考慮新特征稀疏特性的同時，將特征的聚類屬性也作為NMF的另一約束項，通過實驗驗證，提出的算法降維得到的特征更有利于圖像的分類或識別。在取得一定效果的同時，仍存在一些問題有待解決，如選擇的樣本庫種類及樣本數還需增加，從而進一步提高方法的普適性。

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] 汪金濤,曹玉東,孫福明.稀疏約束圖正則非負矩陣分解的增量學習算法[J].計算機應用,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] 苑瑋琦,王爇,孫書會.基于2DFLD的手背靜脈識別算法[J].計算機應用,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] 胡學考,孫福明,李豪杰.基于稀疏約束的半監督非負矩陣分解算法[J].計算機科學,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.