Polynomial Segmentation: An Analytic Solution to Eigenvector Segmentation

Rene Vidal and Aaron Ames
(Professor S. Shankar Sastry)
(ONR) N00014-00-1-0621

We propose a simple analytic solution to the eigenvector segmentation problem. In the absence of noise, we derive a rank constraint, from which one can determine the number of groups n present in the scene. Once n has been determined, the segmentation of the image measurements can be obtained from the roots of a polynomial of degree n in one variable. Since the coefficients of the polynomial are computed by solving a linear system, we show that there is a unique global solution to the eigenvector segmentation problem, which can be obtained in closed form when n < 5.

This purely algebraic solution is shown to be robust in the presence of noise and can be used to initialize an optimal algorithm. We derive such an optimal objective function for the case of zero-mean Gaussian noise on the entries of the eigenvector. We then study the case of multiple eigenvectors and show that it can be reduced to a collection of polynomial segmentation problems.

We present experimental results on intensity-based and motion-based image segmentation. Our experiments show that our algorithm performs similarly or better than Kmeans and EM, and is at least eight times faster. This is because it only needs to solve one linear system in n variables plus one polynomial of degree n in one variable.

Figure 1: A comparison of Kmeans, EM, and Polysegment on intensity-based segmentation of the penguin image

Figure 2: Motion based segmentation of a sequence with two moving robots

R. Vidal, Y. Ma, and S. Sastry, Generalized Principal Component Analysis, UC Berkeley Electronics Research Laboratory, Memorandum No. UCB/ERL M02/15, May 2002.

More information (http://www.eecs.berkeley.edu/~rvidal/) or

Send mail to the author : (rvidal@eecs.berkeley.edu)

Edit this abstract