Reweighted sparse subspace clustering

摘要

Motion segmentation and human face clustering are two fundamental problems in computer vision. The state-of-the-art algorithms employ the subspace clustering scheme when processing the two problems. Among these algorithms, sparse subspace clustering (SSC) achieves the state-of-the-art clustering performance via solving a ℓ_1 minimization problem and employing the spectral clustering technique for clustering data points into different subspaces. In this paper, we propose an iterative weighting (reweighted) ℓ_1 minimization framework which largely improves the performance of the traditional ℓ_1 minimization framework. The reweighted ℓ_1 minimization framework makes a better approximation to the ℓ_0 minimization than tradition ℓ_1 minimization framework. Following the reweighted ℓ_1 minimization framework, we propose a new subspace clustering algorithm, namely, reweighted sparse subspace clustering (RSSC). Through an extensive evaluation on three benchmark datasets, we demonstrate that the proposed RSSC algorithm significantly reduces the clustering errors over the SSC algorithm while the additional reweighted step has a moderate impact on the computational cost. The proposed RSSC also achieves lowest clustering errors among recently proposed algorithms. On the other hand, as majority of the algorithms were evaluated on the Hopkins155 dataset, which is insufficient of non-rigid motion sequences, the dataset can hardly reflect the ability of the existing algorithms on processing non-rigid motion segmentation. Therefore, we evaluate the performance of the proposed RSSC and state-of-the-art algorithms on the Freiburg-Berkeley Motion Segmentation Dataset, which mainly contains non-rigid motion sequences. The performance of these state-of-the-art algorithms, as well as RSSC, will drop dramatically on this dataset with mostly non-rigid motion sequences. Though the proposed RSSC achieves the better performance than other algorithms, the results suggest that novel algorithms that focus on segmentation of non-rigid motions are still in need.