汪靜，魏萊

（上海海事大學(xué)信息工程學(xué)院，上海201306）

局部約束相關(guān)自適應(yīng)子空間分割

汪靜，魏萊

（上海海事大學(xué)信息工程學(xué)院，上海201306）

如何利用數(shù)據(jù)本身相關(guān)性以及數(shù)據(jù)的內(nèi)部結(jié)構(gòu)來(lái)對(duì)數(shù)據(jù)集進(jìn)行有效的分割是子空間分割的一個(gè)重要問(wèn)題。根據(jù)數(shù)據(jù)集本身的內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)之間相關(guān)性，提出一種新的基于局部約束的相關(guān)性自適應(yīng)子空間分割方法（LCASS）。為實(shí)現(xiàn)良好的子空間分割效果，在基于跡Lasso方法的相關(guān)自適應(yīng)子空間分割方法（CASS）基礎(chǔ)上，通過(guò)增加局部約束來(lái)計(jì)算重構(gòu)系數(shù)，并由此構(gòu)建數(shù)據(jù)集鄰接矩陣。在人臉聚類的實(shí)驗(yàn)證明中，此方法構(gòu)造的鄰接矩陣能夠更好地表征數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)，因此能夠得到更好的聚類效果。

子空間分割；局部約束；重構(gòu)系數(shù)

0 引言

子空間分割[1-2]作為圖像處理與計(jì)算機(jī)視覺(jué)中的基本問(wèn)題之一，往往是圖像分析的一個(gè)關(guān)鍵步驟。子空間分割主要是根據(jù)數(shù)據(jù)的相關(guān)特性對(duì)數(shù)據(jù)進(jìn)行聚類，分割的理想狀態(tài)是每個(gè)集群都對(duì)應(yīng)一個(gè)子空間，集群之間的關(guān)聯(lián)是稀疏的，集群之內(nèi)的關(guān)聯(lián)則相對(duì)密切。近二十年以來(lái)，人們?cè)谧涌臻g分割方面取得了很多進(jìn)展，根據(jù)分割子空間構(gòu)造的模型的不同，將常用的子空間分割方法分為代數(shù)方法、迭代方法、統(tǒng)計(jì)學(xué)方法和譜聚類[3-4]方法。具有代表性的譜聚類方法包括稀疏子空間聚類（Sparse Subspace Clustering，SCC）[5]、低秩表示（Low Rank Representation，LRR）[6]，最小二乘回歸（Least Square Regression，LSR）以及在這些方法基礎(chǔ)上擴(kuò)展的一些方法。譜聚類方法的共性是在假設(shè)子空間是獨(dú)立的情況下，第一步先利用數(shù)據(jù)點(diǎn)之間的相似性構(gòu)造一個(gè)關(guān)聯(lián)矩陣，第二步利用關(guān)聯(lián)矩陣去構(gòu)建一個(gè)無(wú)向圖，然后利用譜聚類（Spectral Clustering）方法，如Ncuts[7]來(lái)進(jìn)行分割。這些算法在人臉聚類、運(yùn)動(dòng)分割以及圖像分割等應(yīng)用中展示出良好的效果。但是在某些情況下，如當(dāng)數(shù)據(jù)樣本數(shù)比較小，并且有噪聲和異常值時(shí)，這些算法也很難表現(xiàn)出很好的魯棒性。

為了獲得更好的聚類效果，Lin等人提出了一種能有效的平衡SCC和LRR的新的子空間分割方法，即基于跡Lasso方法的相關(guān)性自適應(yīng)子空間分割方法（Correlation Adaptive Subspace Segmentation by Trace Lasso，CASS）[8]。該方法通過(guò)對(duì)系數(shù)向量及數(shù)據(jù)集乘積的跡Lasso的最小化約束，不僅保證了重構(gòu)系數(shù)向量的稀疏性，同時(shí)也使得向量之間具有一定的組相關(guān)性。受此方法的啟發(fā)，本文提出了局部約束[9]相關(guān)性自適應(yīng)子空間分割算法（Locality-constrained Correlation Adaptive Subspace Segmentation，LCASS），算法通過(guò)增加對(duì)系數(shù)向量的局部約束來(lái)保證某一數(shù)據(jù)點(diǎn)的近鄰點(diǎn)能夠優(yōu)先被選中來(lái)重構(gòu)原數(shù)據(jù)點(diǎn)，從而更為精確的發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)。實(shí)驗(yàn)證明，通過(guò)算法得到地系數(shù)向量構(gòu)造而成的系數(shù)矩陣，能夠有效地揭示數(shù)據(jù)集的內(nèi)在結(jié)構(gòu)，在人臉聚類中具有更好的分割效果。

1 相關(guān)子空間分割模型概述

（1）SSC（Sparse Subspace Clustering）模型

SSC利用稀疏表示[10-11]算法來(lái)計(jì)算數(shù)據(jù)點(diǎn)之間的重構(gòu)系數(shù)，通過(guò)重構(gòu)系數(shù)表示數(shù)據(jù)點(diǎn)之間的相關(guān)性。

稀疏表示的目標(biāo)函數(shù)可以表示為下式：

與SSC考慮稀疏性不同的是，LRR[12-13]主要是考慮數(shù)據(jù)集的低秩表達(dá)，目標(biāo)函數(shù)可以表示成如下形式：

其中‖w‖*代表系數(shù)矩陣W的核[14]范數(shù)，E是誤差矩陣，‖E‖2,1（∑ij‖Ej‖2）表示誤差矩陣的l2,1范數(shù)，?>0是一個(gè)參數(shù)，用來(lái)調(diào)節(jié)兩者效果。通過(guò)求解問(wèn)題（2），LRR可以直接得到重構(gòu)之后的系數(shù)矩陣，相比于SSC，LRR在數(shù)據(jù)集具有較大噪聲時(shí)仍然能夠發(fā)現(xiàn)數(shù)據(jù)集的全局內(nèi)在結(jié)構(gòu)，因此在很多子空間分割任務(wù)中，表現(xiàn)出了更好的效果。

（3）CASS（Correlation Adaptive Subspace Segmenta?tion by Trace Lasso）模型

最近，Lin等人在LRR和SSC的基礎(chǔ)上，提出了一種基于跡Lasso[15]的相關(guān)自適應(yīng)子空間分割模型（CASS），它平衡了LRR和SCC算法各自的特點(diǎn)，計(jì)算得到的系數(shù)向量能夠更好的表征數(shù)據(jù)之間的相關(guān)性。CASS主要解決以下優(yōu)化問(wèn)題：

盡管，CASS表現(xiàn)出了良好的性能，但是其沒(méi)有考慮數(shù)據(jù)集的局部結(jié)構(gòu)，很多算法已經(jīng)證明，通過(guò)考慮數(shù)據(jù)集的局部結(jié)構(gòu)，增加局部結(jié)構(gòu)約束，能夠有效提高算法的性能。針對(duì)這個(gè)問(wèn)題，本文提出了局部約束相關(guān)性自適應(yīng)子空間分割方法（Locality-constrained Correla?tion Adaptive Subspace Segmentation，LCASS）。

單支煙重量主要取決于卷入煙條的煙絲量和緊頭位置偏差。所以重量控制系統(tǒng)應(yīng)該確保卷入煙條煙絲量的穩(wěn)定，可通過(guò)調(diào)節(jié)平準(zhǔn)盤高度實(shí)現(xiàn)；同時(shí)應(yīng)該有效控制緊頭位置偏差，可通過(guò)調(diào)節(jié)平準(zhǔn)盤相位實(shí)現(xiàn)。

2 局部約束相關(guān)自適應(yīng)子空間分割

2.1 目標(biāo)函數(shù)

所謂的局部約束，在這里指的是在進(jìn)行某一數(shù)據(jù)重構(gòu)時(shí)，希望盡可能的選擇其局部數(shù)據(jù)點(diǎn)[16]來(lái)進(jìn)行重構(gòu)，因此局部約束相關(guān)自適應(yīng)子空間分割的目標(biāo)函數(shù)可以定義成：

其中⊙表示Hadamard乘積，公式（4）可以轉(zhuǎn)換成如下等式：

d∈RN是用來(lái)描述不同數(shù)據(jù)點(diǎn)之間的相似度的一種局部約束符，定義如下：

其中dist(xi,X)=[dist(xi,x1),…,dist(xi,xN)]T，dist(xi,xj)是xi和xj之間歐式距離，σ是用來(lái)調(diào)節(jié)局部約束符的權(quán)值的遞減速度。

2.2 算法流程

求解局部約束相關(guān)自適應(yīng)子空間分割的算法可以描述如下：

算法1：采用迭代算法估計(jì)局部約束參數(shù)c*

輸入：數(shù)據(jù)矩陣X∈RD×N,參數(shù)σ，d0=0，c0=0，μ

步驟1：采用歐氏距離計(jì)算出數(shù)據(jù)點(diǎn)之間的相似度度量參數(shù)d

步驟4：通過(guò)解決線性模型(XTX+?D) c*=XTy得到局部約束參數(shù)ci

通過(guò)算法1，可以計(jì)算得到所有ci，將其組織構(gòu)造成系數(shù)矩陣C=[c1,c2,…,cn]。再令最后使用Normalized Cuts進(jìn)行得到最終的分割結(jié)果。

3 實(shí)驗(yàn)分析

在本節(jié)之中，我們主要是通過(guò)對(duì)不同的人臉數(shù)據(jù)庫(kù)中的人臉進(jìn)行分割實(shí)驗(yàn)，用以對(duì)比本文的算法與現(xiàn)存的算法之間的優(yōu)劣。

3.1 實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

我們主要使用三個(gè)人臉數(shù)據(jù)庫(kù)中的人臉圖像來(lái)進(jìn)行分割實(shí)驗(yàn)，包括ORL[17]、Extended Yale B[18]以及AR[19]人臉數(shù)據(jù)庫(kù)。

ORL人臉數(shù)據(jù)庫(kù)包含40個(gè)對(duì)象，每個(gè)對(duì)象有10幅圖像，共計(jì)400幅灰度圖像，包含不同的光照、表情。圖像的原始尺寸是92×112，我們分別選取其中l(wèi)（l=10,20,40）個(gè)人的圖像作為分割樣本，我們將其正規(guī)化到32×32。圖1是ORL數(shù)據(jù)庫(kù)的一些圖片樣本。

Extended Yale B人臉數(shù)據(jù)庫(kù)是由38個(gè)對(duì)象共2432幅圖像組成，其中每個(gè)對(duì)象64幅灰度圖像，同樣，這些照片也是在不同的光照、表情下拍攝的。我們分別選取其中的l（l=5,10,20）個(gè)人的圖像用于實(shí)驗(yàn)。我們也將這些圖像大小正規(guī)化到32×32，圖2是Extended Yale B人臉數(shù)據(jù)庫(kù)的一些圖片樣本。

AR人臉數(shù)據(jù)庫(kù)是由50位男性和50位女性在不同的光照和表情下拍攝的照片組成，每個(gè)人26幅圖像共計(jì)2600幅灰度圖像。我們分別選取其中l(wèi)（l=10,20,30）個(gè)人的圖像，同樣，我們也將其正規(guī)化到32×32，圖3是AR人臉數(shù)據(jù)庫(kù)的一些圖片樣本。

表1 各種算法進(jìn)行子空間分割的最優(yōu)分割準(zhǔn)確率（%）

3.2 實(shí)驗(yàn)結(jié)果

我們通過(guò)分別在三個(gè)人臉數(shù)據(jù)庫(kù)上選擇不同角度不同光照下的人臉上進(jìn)行幾個(gè)算法的分割對(duì)比實(shí)驗(yàn)，根據(jù)自身經(jīng)驗(yàn)選擇相對(duì)比較好的數(shù)值來(lái)設(shè)置相關(guān)的參數(shù)?和μ的值，得到相關(guān)的分割準(zhǔn)確率。表1是各個(gè)算法得到的最優(yōu)分割準(zhǔn)確率，通過(guò)表1很明顯的可以看到本文所提出的LCASS方法要明顯優(yōu)于其他的幾個(gè)算法。

圖1 ORL人臉數(shù)據(jù)庫(kù)的圖片樣本

圖2 Extended Yale B人臉數(shù)據(jù)庫(kù)的圖片樣本

圖3 AR人臉數(shù)據(jù)庫(kù)的圖片樣本

4 結(jié)語(yǔ)

本文提出了一種新的子空間分割方法局部約束相關(guān)自適應(yīng)子空間分割方法LCASS。通過(guò)局部約束優(yōu)先地選擇相關(guān)數(shù)據(jù)點(diǎn)的近鄰點(diǎn)，來(lái)重構(gòu)原有的數(shù)據(jù)點(diǎn)，更好地表征了數(shù)據(jù)點(diǎn)的內(nèi)在結(jié)構(gòu)。從而從很好地利用了數(shù)據(jù)本身的內(nèi)在結(jié)構(gòu)以及數(shù)據(jù)點(diǎn)對(duì)之間的相關(guān)性，因而大大的提高了子空間分割的準(zhǔn)確率。同時(shí)，在ORL、Extended Yale B、AR等三個(gè)人臉數(shù)據(jù)庫(kù)上進(jìn)行了分割實(shí)驗(yàn)，證明本文提出的算法的有效性。

[1]Parsons L,Haque E,Liu H.Subspace Clustering for High Dimensional Data:a Review[J].ACM SIGKDD Explorations Newsletter,2004, 6（1）:90-105.

[2]Vidal,René.Subspace Clustering[J].IEEE Signal Processing Magazine,2011,28（2）:52-68.

[3]Lauer F,Schnorr C.Spectral Clustering of Linear Subspaces for Motion Segmentation[J].Proceedings,2009,30（2）:678-685.

[4]Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2006,52（4）:1289-1306.

[5]E.Elhamifar and R.Vidal.Sparse Subspace Clustering[C].IEEE Computer Society.DC,Washington:IEEE,2009:2790-2797.

[6]G.Liu,Z.Lin,and Y.Yu.Robust Subspace Segmentation by Low-rank Representation[C].International Conference on Machine Learning,New York:ICML,2010:663–670.

[7]Shi J,Malik J.Normalized Cuts and Image Segmentation[C].IEEE Transactions on Pattern Analysis and Machine Intelligence.Washington:IEEE,1997:888-905.

[8]Lu C,Feng J,Lin Z,et al.Correlation Adaptive Subspace Segmentation by Trace Lasso[J].2013,49:1345-1352.

[9]Wang J,Yang J,Yu K,et al.Locality-Constrained Linear Coding for Image Classification[C].IEEE Computer Society Conference on Computer Vision&Pattern Recognition IEEE Computer Society Conference on Cvpr.Washington:IEEE,2010:3360-3367.

[10]Wright J,Yang A Y,Ganesh A,et al.Robust Face Recognition via Sparse Representation[J].IEEE Transactions on Pattern Analysis& Machine Intelligence,2009,31（2）:210-227.

[11]Elhamifar E,Vidal R.Clustering Disjoint Subspaces Via Sparse Representation[C].Acoustics Speech and Signal Processing（ICASSP）,2010 IEEE International Conference on IEEE.Washington:IEEE,2010:1926-1929.

[12]Vidal R,Favaro P.Low Rank Subspace Clustering（LRSC）[J].Pattern Recognition Letters,2014,43（1）:47-61.

[13]Liu G,Lin Z,Yan S,et al.Robust Recovery of Subspace structures by Low-Rank Representation[J].Pattern Analysis&Machine Intelligence IEEE Transactions on,2013,35（1）:171-84.

[14]Zhang K,Wang Q,Lan L,et al.Sparse Semi-Supervised Learning on Low-Rank Kernel[J].Neurocomputing,2014,129（4）:265-272.

[15]Grave E,Obozinski G,Bach F.Trace Lasso:a Trace Norm Regularization for Correlated Designs[J].Advances in Neural Information Processing Systems,2011:2187-2195.

[16]Gui J,Sun Z,Jia W,et al.Discriminant Sparse Neighborhood Preserving Embedding for Face Recognition[J].Pattern Recognition, 2012,45（8）:2884-2893.

[17]Cambridge University Engineering Department.ORL.http://www.uk.research.att.com/facedatabase[DB].html,1992,4.

[18]Georghiades A S.YALE.http://cvc.yale.edu/projects/yalefaces/yalefaces[DB].html,1997,10.

[19]AR Face Database（AR）.http://rvl1.ecn.purdue.edu/～aleix/aleix_face_[DB].html.

Locality-Constrained Correlation Adaptive Subspace Segmentation

WANG Jing，WEI Lai

（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

It is an important problem of subspace segmentation that how to segment the data sets effectively by using the correlation of the data points and the internal structure.Proposes the Locality-constrained Correlation Adaptive Subspace Segmentation which based on the Correlation Adaptive Subspace Segmentation by Trace Lasso,calculates the reconstructed coefficients by adding local constraints and constructs a adja?cency matrix of data sets.The contrastive experiments on several benchmark face database show the effectiveness of proposed method.

1007-1423（2017）21-0031-05

10.3969/j.issn.1007-1423.2017.21.005

汪靜（1993-），女，安徽安慶人，碩士研究生，研究方向?yàn)樾畔⑻幚砼c模式識(shí)別；

2017-04-21

2017-07-12

Subspace Segmentation;Locality-Constrained;Reconstructed Coefficients