Subspace Segmentation: MATLAB/C Source Codes

Source codes posted on this page will be frequently updated whenever new versions and variations are available. Please notify the webmaster if you find any problems with any of the code or would like to contribute a new version.

© Copyright Notice: It is important that you read and understand the copyright of the following software packages as specified in the individual items. The copyright varies with each package due to its contributor(s). The packages should NOT be used for any commercial purposes without direct consent of their author(s). By listing the packages in this website, we are not responsible for any potential property loss or damage caused directly or indirectly by the usage of the software.

Statistical Methods

Expectation-Maximization (EM) & K-Subspaces
  This package uses iterative EM and K-Subspaces methods to estimate multiple subspace structures with all dimensions given.
 

References:

[1] J. Ho, M. Yang, J. Lim, K. Lee, and D. Kriegman. Clustering appearances of objects under varying illumination conditions. In CVPR, 2003.

[2] Rene Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis: Estimation and Segmentation of Hybrid Models. (A new book in preparation, draft available upon request.)
  MATLAB source : http://perception.csl.uiuc.edu/software/GPCA/EM.tar.gz
  Contact: Allen Yang. Latest update: 6-6-06.
   
RANSAC on Subspaces
 

This package consists of two implementations about using ransom sampling techniques to estimate multiple subspaces:

  • RANSACarrangement: Sample subsets to estimate a union of subspaces together.
  • RANSACsubspaces: Estimate one subspace at a time with a subspace degeneracy testing to avoid overfitting problems associated to subspaces of different dimensions in the union.

Reference: Allen Y. Yang, Shankar R. Rao, and Yi Ma. Robust statistical estimation and segmentation of multiple subspaces. CVPR workshop on 25 years of RANSAC, 2006. [PDF]

  MATLAB source: http://perception.csl.uiuc.edu/software/GPCA/RANSAC-subspaces.tar.gz
  Contact: Allen Yang. Latest update: Apr. 19, 2006.
   

 

Generalized Principal Component Analysis (GPCA)

Polynomial Differentiation Algorithm (PDA)
  This package implements the original algebraic solution to the GPCA problem. The number of subspaces are given, and all subspaces are assumed to be hyperplanes.
  References: Rene Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis (GPCA): an analytic solution to segmentation of mixtures of subspaces. CVPR 2004.
 

MATLAB source : http://perception.csl.uiuc.edu/software/GPCA/pda.tar.gz

Copyright (c) Rene Vidal.
  Contact: Rene Vidal. Latest update: Nov. 20, 2005.
   
GPCA for Subspaces of Different Dimensions (GPCA-Voting)
  This package contains a variation of the original algebraic solution, which uses a voting scheme to improve the segmentation performance in the presence of noise. The number of subspaces and their dimensions are assumed to be given.
  References: Allen Y. Yang, Shankar Rao, Andrew Wagner, and Yi Ma. Hilbert Functions and Applications to the Estimation of Subspace Arrangements. ICCV 2005.
 

MATLAB source : http://perception.csl.uiuc.edu/software/GPCA/gpca-voting.tar.gz

Copyright (c) University of Illinois, 2005.
  Contact: Allen Yang. Latest update: Jan. 1, 2007.
   
 
Performance Comparison in Terms of Segmentation Error Percentage

Note: "Method A + Method B" means starting with the algebraic method A followed by the iterative method B as post-processing. The statistics was obtained by the standard test script included in each package. All cases are averaged with 200 tries. By no means are results given below meant to be conclusive! Please exercise discretion when choosing the method for your own data or application.
Methods
(2,2,1) in R3, 4% noise
(2,2,2) in R3, 4% noise
(4,2,2,1) in R5, 4% noise
(4,4,4,4) in R5, 4% noise
EM
29%
11%
53%
20%
K-Subspaces
27%
12%
57%
25%
PDA
10.3%
10.6%
39.8%
25.3%
GPCA-V
6.4%
9.2%
5.7%
17%
GPCA-V + K-Subspaces
5.4%
8.6%
5.7%
11%
   
Robust GPCA
  This package consists of implementations of three robust techinques to robustify GPCA-Voting in the presence of large amounts of outliers. For function details, please read the README file in the package.
 

References:

1. Allen Y. Yang, Shankar R. Rao, and Yi Ma. Robust statistical estimation and segmentation of multiple subspaces. CVPR workshop on 25 years of RANSAC, 2006. [PDF]

2. Yi Ma, Allen Y. Yang, Harm Derksen, and Robert Fossum. Estimation of subspace arrangements with applications in modeling and segmenting mixed data. Submitted to SIAM Review, 2006.

 

MATLAB code: http://perception.csl.uiuc.edu/software/GPCA/rgpca.tar.gz

Copyright(c) University of Illinois, 2006.

  Contact: Allen Yang. Latest update: Jan. 1, 2007.
 

This movie in QuickTime format demonstrates the robustness of Multivariate Trimming (MVT) in rejecting outliers with respect to multiple subspaces. The a priori outlier percentage is 24%, and the maximal magnitude of the outliers is set to be 3 times higher than that of the inliers. MVT gradually trims out samples from 0% to 54%.

Notice that, although the data are multi-modal in the data space, they are converted to uni-modal in the Veronese embedded space. Therefore, MVT is guaranteed to converge to the true covariance matrix in a probability sense. The breakdown point of MVT in this case is also the rejection rate.
 

 

Similar behaviors can also be observed in the Influence Function approach. The accuracy of the influence function is less than MVT.

However, some of our experiments show that MVT has the tendency to overfit a data set if the outlier percentages are over-estimated, while the influence function is more stable towards overfitting problem. Therefore, in some real applications, the influence function may outperform MVT.

 

C Implementations
GPCA for Hyperplanes (GPCA-H)
  This package was specifically programmed to estimate multiple hyperplanes (with codimension one). The number of subspaces is assumed given.
  References: Shankar Rao, Andrew Wagner, Allen Y. Yang, and Yi Ma. Improving Subspace Segmentation with the Rayleigh Quotient. UIUC Tech Report.
 

C source : http://perception.csl.uiuc.edu/software/GPCA/gpca_kgc_hyperplane_c.zip

Copyright(c) University of Illinois, 2005.

  Contact: John Wright. Latest update: Aug. 5, 2005.