局部約束相關自適應子空間分割

汪靜，魏萊

（上海海事大學信息工程學院，上海201306）

局部約束相關自適應子空間分割

汪靜，魏萊

（上海海事大學信息工程學院，上海201306）

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

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

0 引言

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

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

1 相關子空間分割模型概述

（1）SSC（Sparse Subspace Clustering）模型

SSC利用稀疏表示[10-11]算法來計算數(shù)據(jù)點之間的重構系數(shù)，通過重構系數(shù)表示數(shù)據(jù)點之間的相關性。

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

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

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

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

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

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

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

2 局部約束相關自適應子空間分割

2.1 目標函數(shù)

所謂的局部約束，在這里指的是在進行某一數(shù)據(jù)重構時，希望盡可能的選擇其局部數(shù)據(jù)點[16]來進行重構，因此局部約束相關自適應子空間分割的目標函數(shù)可以定義成：

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

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

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

2.2 算法流程

求解局部約束相關自適應子空間分割的算法可以描述如下：

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

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

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

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

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

3 實驗分析

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

3.1 實驗數(shù)據(jù)集和實驗設置

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

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

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

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

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

3.2 實驗結果

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

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

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

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

4 結語

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

[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-），女，安徽安慶人，碩士研究生，研究方向為信息處理與模式識別；

2017-04-21

2017-07-12

Subspace Segmentation;Locality-Constrained;Reconstructed Coefficients