基于稀疏子空間聚類的人臉識(shí)別方法*

張彩霞，胡紅萍，白艷萍

（中北大學(xué)理學(xué)院，太原030051）

基于稀疏子空間聚類的人臉識(shí)別方法*

張彩霞，胡紅萍，白艷萍

（中北大學(xué)理學(xué)院，太原030051）

在現(xiàn)有的稀疏子空間聚類算法理論基礎(chǔ)上給出兩種稀疏子空間聚類優(yōu)化算法:稀疏線性子空間聚類和稀疏仿射子空間聚類。這兩種優(yōu)化算法針對(duì)不同的數(shù)據(jù)集會(huì)有不同的聚類效果。通過稀疏表達(dá)得到不同的稀疏系數(shù)矩陣，把稀疏系數(shù)矩陣應(yīng)用到較為簡(jiǎn)單的改進(jìn)的正則化譜聚類算法中實(shí)現(xiàn)聚類。應(yīng)用Yale B數(shù)據(jù)對(duì)人臉圖像進(jìn)行識(shí)別分類得出:采用稀疏線性子空間聚類算法優(yōu)于稀疏仿射子空間聚類算法；在算法執(zhí)行時(shí)間上和算法聚類錯(cuò)誤率比傳統(tǒng)的稀疏子空間聚類較為快速高效。

子空間聚類，稀疏子空間聚類，譜聚類算法，人臉識(shí)別

0 引言

在很多實(shí)際應(yīng)用中，高維數(shù)據(jù)無處不在，如計(jì)算機(jī)視覺、圖像處理、運(yùn)動(dòng)分割、人臉識(shí)別等。實(shí)際上，高維數(shù)據(jù)可以被相應(yīng)的低維子空間分別表示。

近年來，子空間聚類在壓縮感知問題上的應(yīng)用已吸引了很多學(xué)者的注意，在信息科學(xué)上是一個(gè)很熱的研究領(lǐng)域。子空間聚類的目的在于把高維數(shù)據(jù)劃分在其潛在的子空間并應(yīng)用到盡可能多的領(lǐng)域中。子空間聚類算法有4種:迭代法［1-2］，代數(shù)法［3］，統(tǒng)計(jì)法［4］和基于譜聚類方法［5-7］，而前三種方法都需要知道子空間的個(gè)數(shù)和維數(shù)或?qū)?shù)據(jù)初始值，噪聲，奇點(diǎn)比較敏感，譜聚類算法利用數(shù)據(jù)點(diǎn)之間的信息建立相似性，能夠很好地避免上述缺點(diǎn)。

稀疏子空間聚類是基于譜聚類提出一種稀疏表達(dá)的聚類方法。Elhamifar等［8］利用稀疏恢復(fù)算法的先進(jìn)性提出一種稀疏子空間聚類算法（Sparse Sub space Clustering，SSC），通過稀疏表示（Sparse representation，SR）構(gòu)造相似度矩陣，并應(yīng)用到譜聚類算法中，從而聚類數(shù)據(jù)，高維數(shù)據(jù)空間可由線性或仿射子空間稀疏表示，得到兩個(gè)稀疏最優(yōu)化算法:稀疏線性子空間優(yōu)化算法，稀疏仿射子空間優(yōu)化算法。本文首先在此理論基礎(chǔ)上應(yīng)用Yale B數(shù)據(jù)對(duì)各種不同的人臉圖像識(shí)別、分類。

1 稀疏子空間聚類

稀疏子空間聚類是一種全新的數(shù)據(jù)聚類方法，是目前機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺、圖像處理、模式識(shí)別等領(lǐng)域的研究熱點(diǎn)。

稀疏子空間聚類［8］的基本思想是:設(shè)有N個(gè)D維數(shù)據(jù)，處于RD空間的n個(gè)線性或仿射子空間中，子空間的維數(shù)分別為，將數(shù)據(jù)表示為所有其他數(shù)據(jù)的線性組合，

其中，系數(shù)矩陣Z∈RN×N滿足:當(dāng)xi和xj屬于不同的子空間時(shí)，有Zij=0，屬于同一子空間時(shí)Zij≠0，式（2）用數(shù)據(jù)集本身表示數(shù)據(jù)，稱為數(shù)據(jù)的自表示。若已知數(shù)據(jù)的子空間結(jié)構(gòu)，并將數(shù)據(jù)按類別逐列排放，則在一定條件下可使系數(shù)矩陣Z具有塊對(duì)角結(jié)構(gòu)，即

圖1 稀疏子空間聚類的流程

通常，稀疏子空間聚類基于系數(shù)向量的一維稀疏性或系數(shù)矩陣的二維稀疏性來建立高維數(shù)據(jù)在低維子空間的表示，利用表示系數(shù)矩陣Z構(gòu)造數(shù)據(jù)的相似度矩陣，最后利用譜聚類算法得到最終的聚類結(jié)果。圖1描述了稀疏子空間聚類的流程。

2 稀疏最優(yōu)化算法

位于線性或仿射集合的高維數(shù)據(jù)可以稀疏地被同一個(gè)子空間的點(diǎn)線性或者仿射表示。本文通過文獻(xiàn)［8］中稀疏表示技巧獲得高維數(shù)據(jù)的稀疏表示。

2.1 高維數(shù)據(jù)空間由線性子空間稀疏表示

2.2 高維數(shù)據(jù)空間由仿射子空間稀疏表示

其中，C為稀疏系數(shù)矩陣，E為稀疏奇異值矩陣，Z為噪聲矩陣，系數(shù)

本文的算法不需要提前知道子空間個(gè)數(shù)和維數(shù)最優(yōu)化的求解通過ADMM（Alternating Direction Method of Multipliers）算法下完成［9］。

3 正則化譜聚類算法

譜聚類算法［10］是建立在圖譜理論基礎(chǔ)上的一種重要的數(shù)據(jù)聚類的方法，首先根據(jù)給定的數(shù)據(jù)集建立數(shù)據(jù)間的相似度矩陣，然后構(gòu)造加權(quán)圖，通過尋找圖的最優(yōu)劃分實(shí)現(xiàn)數(shù)據(jù)聚類的目的，相似度矩陣建立的方法有很多種，本文采用上節(jié)所述稀疏表示的方法，獲得相似度矩陣，然后，根據(jù)加權(quán)圖的最優(yōu)劃分準(zhǔn)則，產(chǎn)生不同的Laplacian矩陣:

譜聚類算法［11］尋求相似加權(quán)圖的最優(yōu)劃分，要求類間切割權(quán)值最小而類內(nèi)相似權(quán)值最大，然而非正則化譜聚類有時(shí)不能滿足類內(nèi)相似權(quán)值最大這個(gè)要求，而正則化譜聚類能夠很好地滿足這兩個(gè)條件。因此，正則化的算法優(yōu)于非正則化譜聚類算法。譜聚類算法涉及到特征向量的計(jì)算，兩種正則化Laplacian矩陣的特征可知，L2特征向量計(jì)算L1比特征向量更為簡(jiǎn)單，算法執(zhí)行時(shí)間較為快速。由L2包含聚類信息的特征向量組構(gòu)成的矩陣具有分段常值性，所反映的聚類信息比較明顯。而由L1包含聚類信息的特征向量組構(gòu)成的矩陣具有分段平行性，其所反映的聚類信息不如矩陣L2的明顯［12］。在稀疏子空間聚類算法中，Elhamifar等選擇了L1，而本文經(jīng)過實(shí)驗(yàn)研究比較選擇了L2。

4 最優(yōu)化SSC算法

本文算法在獲得稀疏系數(shù)矩陣之后，選擇文獻(xiàn)［10］的正則化譜聚類算法。

①把n維線性或仿射空間的數(shù)據(jù)點(diǎn){yi}iN作為輸入利用稀疏子空間式（5）或式（6），獲得稀疏系數(shù)矩陣C，算法實(shí)現(xiàn)在ADMM算法下完成；

③根據(jù)稀疏系數(shù)矩陣建立相似加權(quán)圖，每個(gè)數(shù)據(jù)點(diǎn)只與其稀疏表示中的數(shù)據(jù)點(diǎn)連接，不同子空間的數(shù)據(jù)點(diǎn)無連接，權(quán)值矩陣為；

④把相似加權(quán)圖應(yīng)用到譜聚類算法［10］中，求Laplacian矩陣L2，對(duì)其求特征值，子空間個(gè)數(shù)n為特征值零的次數(shù)，獲得前n小個(gè)特征值，把其對(duì)應(yīng)的特征向量形成N×n的矩陣U；

⑤把U的每一行作為n維空間的一個(gè)向量，對(duì)U進(jìn)行K-means聚類，N行所對(duì)應(yīng)的類就是其N個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的類。得出輸出數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的類Y1，Y2，…，Yn。

5 實(shí)驗(yàn)結(jié)果與分析

本文的數(shù)據(jù)來自Yale B數(shù)據(jù)集，為1 024維的高維數(shù)據(jù)，包含38個(gè)不同人的人臉圖像，每一個(gè)人在不同變換條件下的正面臉部圖像有64個(gè)，每一個(gè)圖像由1 024維向量表示，為了清楚地理解Yale B數(shù)據(jù)，把像素點(diǎn)表示為32×32的像素讀成圖片如圖2所示。此高維數(shù)據(jù)空間可能由多個(gè)線性子空間組成或者由多個(gè)仿射子空間組成，利用前面提到的兩類稀疏最優(yōu)化算法，結(jié)合改進(jìn)的譜聚類算法分別對(duì)不同人臉圖像進(jìn)行分類識(shí)別。

圖2 兩人的人臉圖像

為突出本文數(shù)據(jù)選擇優(yōu)化算法和對(duì)優(yōu)化算法作出的改進(jìn)，實(shí)驗(yàn)選取了8個(gè)不同人的人臉圖像，從算法聚類錯(cuò)誤率和執(zhí)行時(shí)間兩方面作出比較。error1和error2表示稀疏線性和仿射子空間聚類結(jié)合正則化譜聚類L1聚類錯(cuò)誤率。error3和error4表示稀疏線性和仿射子空間聚類結(jié)合正則化譜聚類L2聚類錯(cuò)誤率。t1和t2表示稀疏線性子空間聚類結(jié)合L1和L2的算法執(zhí)行時(shí)間。t3和t4表示稀疏仿射子空間聚類結(jié)合L1和L2的算法執(zhí)行時(shí)間。N表示人臉圖像個(gè)數(shù)，S表示分類個(gè)數(shù)。所有的算法均在MATLAB R2014a下運(yùn)行。

表1 算法聚類錯(cuò)誤率

表2 算法執(zhí)行時(shí)間（s）

從表1得出Yale B數(shù)據(jù)人臉識(shí)別應(yīng)用稀疏子空間聚類結(jié)合正則化譜聚類L2聚類錯(cuò)誤率低于L1:利用稀疏線性子空間優(yōu)化算法聚類錯(cuò)誤率低于稀疏仿射子空間優(yōu)化算法聚類錯(cuò)誤率。從算法執(zhí)行時(shí)間上，L2較L1快速。

6 結(jié)論

本文指出Yale B數(shù)據(jù)集在稀疏線性子空間聚類效果優(yōu)于稀疏仿射子空間聚類，而文獻(xiàn)［8］的實(shí)驗(yàn)結(jié)果中稀疏仿射子空間聚類效果優(yōu)于稀疏線性子空間。從而得出稀疏線性或仿射子空間聚類優(yōu)化算法并不是對(duì)任何數(shù)據(jù)集聚類有效，兩種優(yōu)化算法聚類數(shù)據(jù)有選擇性。應(yīng)用改進(jìn)的一種較為簡(jiǎn)單的正則化譜聚類算法L2比L1實(shí)時(shí)高效。

［1］TSENG P.Subspace clustering［J］.Signal Processing Magazine，2001，28（2）:52-68.

［2］HO J，YANG M H，LIM J，et al.Clustering appearances of objects under varying illumination conditions［C］//IEEE Conference on Computer Vision and Recognition，2003.

［3］COSTERIRA J，KANADE T.A multibody factorization method for independently moving objects［J］.International Journal of Computer Vision，1998，29（3）:159-179.

［4］TIPPING M，BISHOP C.Mixtures of probabilistic principal component analyzers［J］.Neural Computation，1999，11（2）: 443-482.

［5］WEISS Y.On spectral clustering:analysis and algorithm［J］. Neural Information Processing Systems，2001:849-856.

［6］YAN J，POLLEFEYS M.A general framework for motion segmentation:Independent.Articulated，rigid.non-rigid.Degenerate and non-degenerate［C］//in European Conf.on computer，2006:94-106.

［7］CHEN G，LERMAN G.Spectral curvature clustering（SSC）［J］.International Journal of Computer Vision，2009，81（3）: 317-330.

［8］ELHAMIFAR E，VIDAL R.Sparse subspace clustering:Algorithm，theory，and applications［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）: 2765-2781.

［9］BOYD S，PARIKH N，CHU E，et al.Distributed optimization and statistical learning via the alternating direction method multipliers［J］.Foundations and Trends in Machine Learning，2010，3（1）:1-122.

［10］LUXBURG U.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17（4）:395-416.

［11］歐陽佩佩，趙志剛，劉桂峰.一種改進(jìn)的稀疏子空間聚類算法［J］.青島大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，27（3）: 44-48.

［12］蘇木亞.譜聚類方法研究及其在金融時(shí)間序列數(shù)據(jù)挖掘中的應(yīng)用［D］.大連:大連理工大學(xué)，2011.

［13］封睿，李小霞.基于GLC KSVD的稀疏表示人臉識(shí)別算法［J］.四川兵工學(xué)報(bào)，2014，35（4）:88-92.

Face Recognition Method Based on Sparse Subspace Clustering

ZHANG Cai-xia，HU Hong-ping，BAI Yan-ping
（Faculty of Science，Department of Maths，North University of China，Taiyuan 030051，China）

We offer two kinds of sparse subspace clustering optimization algorithm，sparse linear space clustering and sparse affine subspace clustering，based on the existing theory of sparse subspace clustering algorithm.For different data gathering，these two kinds of optimization algorithm has different clustering results.In this paper，different sparse coefficient matrix by sparse expression is obtained.In order to achieve cluster，the sparse coefficient matrix is applied to relatively simple regularization of spectral clustering algorithm.Application of Yale B data，we recognize and classify face image:using sparse linear space clustering algorithm is better than the sparse affine subspace clustering algorithm；Comparing with the traditional sparse subspace clustering，it is more fast and efficient in the time of execution and error rate of algorithm.

subspace clustering，sparse subspace clustering，spectral clustering algorithms，face regulation

TP391

A

1002-0640（2017）04-0029-04

2016-02-16

2016-03-25

國(guó)家自然科學(xué)基金（61275120）；2014年校自然科學(xué)基金資助項(xiàng)目

張彩霞（1989-），女，山西朔州人，在讀碩士研究生。研究方向：現(xiàn)代最優(yōu)化算法。