Stella X. Yu : Research

Multiclass Spectral Clustering
Stella X. YU and Jianbo SHI
International Conference on Computer Vision (ICCV'01), 2003.
We propose a principled account on multiclass spectral clustering. Given a discrete clustering formulation, we first solve a relaxed continuous optimization problem by eigendecomposition. We clarify the role of eigenvectors as a generator of all optimal solutions. We then solve an optimal discretization problem, which finds a nearly global-optimal discrete solution closest to the continuous optima. Our method is robust to random initialization and converges faster than other clustering methods. Flexible initialization also allows us to obtain nearly optimal solutions with special requirements. Extensive experiments on real image segmentation are reported.
clustering, spectral graph partitioning, kmeans, image segmentation