Segmentation using Eigenvectors: A Unifying View

Yair WeissICCV 1999 · OpenReview

Abstract

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.

Introduction

In computer vision, segmentation is the critical task of grouping pixels or data points into coherent objects. Traditionally, this was approached as a statistical mixture model problem, often solved via the Expectation-Maximization (EM) algorithm. However, EM is prone to local optima and requires robust initialization. Eigenvector-based methods, or spectral clustering, emerged as a stable, "one-shot" alternative. Despite their popularity, the field initially lacked a unified theoretical framework, with various researchers employing different matrices, eigenvectors, and post-processing steps. This paper addresses this gap by providing a unifying view of these algorithms and identifying the core factors behind their success.

Methods and the Unifying Approach

The study compares four primary algorithms: Perona and Freeman (PF), Shi and Malik (SM/Normalized Cuts), Scott and Longuet-Higgins (SLH), and Costeira and Kanade (CK). While these methods appear distinct, they can be unified by analyzing their behavior on block-diagonal affinity matrices.

Block-diagonal affinity matrix for three clusters

In an ideal scenario where clusters are perfectly separated, the affinity matrix $W$ exhibits a clear block-diagonal structure, as shown in the figure above. The author proves that for such cases, these algorithms are essentially performing the same operation. A critical insight is the role of normalization. Using a raw affinity matrix $W$ can be problematic if clusters have varying densities, as the primary eigenvector may only capture the densest group. Normalizing the matrix (e.g., $N = D^{-1/2}WD^{-1/2}$) ensures that all clusters are represented equally in the spectral decomposition.

Analysis and Key Results

The theoretical analysis is supported by experiments on synthetic point clusters and real-world images. The results demonstrate that the eigenvectors of a properly normalized matrix act as indicator vectors for the clusters.

Eigenvector values showing three distinct clusters

As illustrated above, the values of the second generalized eigenvector for a 30-point dataset clearly delineate three distinct groups. Beyond individual eigenvectors, the paper highlights the utility of the "Q-matrix" ($VV^T$), constructed from the top $k$ eigenvectors. This matrix provides a robust measure of cluster membership, where $Q_{ij}$ ideally approaches 1 if points $i$ and $j$ belong to the same cluster.

On real-world benchmarks, such as the "Baseball Player" image, the normalized approach successfully separated the subject from the background, whereas unnormalized methods produced indistinct results. The proposed hybrid algorithm (SM+SLH) combines Shi and Malik's normalization with the SLH Q-matrix construction, offering superior robustness in the presence of noise and varying textures.

Conclusion and Future Work

This unified treatment clarifies the relationship between various spectral clustering methods and emphasizes the necessity of matrix normalization. While these methods are powerful, they remain sensitive to the scaling parameter $\sigma$ used to define affinity. Additionally, the computational cost of eigendecomposition for large-scale images remains a practical hurdle. Future work involves developing automated methods for parameter selection and exploring more complex affinity measures that incorporate semantic information beyond low-level pixel features.

Summary updated

Abstract

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.
BibTeX
@inproceedings{weiss1999segmentation,
  author = {Yair Weiss},
  title = {{Segmentation using Eigenvectors: A Unifying View}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {1999},
  url = {https://openreview.net/forum?id=S1-KLWzuZH},
}
Figure