Appearance-based keypoint clustering

Francisco J. Estrada, Pascal Fua, Vincent Lepetit, Sabine SüsstrunkCVPR 2009 · OpenReview

Abstract

We present an algorithm for clustering sets of detected interest points into groups that correspond to visually distinct structure. Through the use of a suitable colour and texture representation, our clustering method is able to identify keypoints that belong to separate objects or background regions. These clusters are then used to constrain the matching of keypoints over pairs of images, resulting in greatly improved matching under difficult conditions. We present a thorough evaluation of each component of the algorithm, and show its usefulness on difficult matching problems.

Introduction

In computer vision, "keypoints" (distinctive local features) are the fundamental units used to match objects across different image frames. However, standard matching algorithms often fail when the background is cluttered or the object of interest is non-rigid and changes shape. In a typical natural scene, such as a cheetah moving through tall grass, a standard matcher might find thousands of mathematically plausible but physically impossible matches due to the overwhelming amount of background noise.

Researchers from the University of Toronto and EPFL propose a method for perceptual grouping. By identifying which keypoints belong to the same "stuff" (the object) and which belong to the background, the system can ignore the noise. While full-image segmentation is a classic solution, it is computationally expensive and often fails on complex textures. This paper proposes a more efficient middle ground: clustering only the detected keypoints.

Methodology

The proposed pipeline consists of three main stages:

  1. Local Representation: For every detected keypoint, the algorithm extracts an 11x11 patch. It describes this patch using two cues: Color (standard RGB histograms) and Texture (a covariance matrix of first and second-order image derivatives).
  2. Spectral Embedding: This is the core innovation. The authors build a graph where each keypoint is a node and edges represent visual similarity. They use a random walk process to map high-dimensional appearance data into a low-dimensional (5D) space. In this new space, points belonging to the same object naturally drift together into tight, distinct "clouds."
  3. Mean-Shift Clustering: Finally, the algorithm uses the Mean-Shift algorithm to find the centers of these clouds, effectively labeling each keypoint as belonging to a specific visual group.
Keypoint clustering results where green points represent the foreground object (cheetah) and red points represent the background.

The authors found that keypoint clustering is inherently harder than pixel clustering because keypoints are often located on object boundaries, meaning a single patch often contains two different types of textures. Consequently, they found that physical proximity in the image is a vital constraint for successful grouping.

Experimental Evaluation

The algorithm was evaluated using the Berkeley Segmentation Database (BSD), with 50 images for parameter tuning and 250 images for testing. Additionally, the authors tested the practical application on difficult video sequences, including a cheetah moving through a natural environment, which presents significant non-rigid deformation and clutter.

Results and Discussion

The proposed method demonstrated superior performance across several metrics:

  • Accuracy: On the BSD benchmark, the method achieved a mean correct-classification rate of 66.13%, significantly outperforming the standard Normalized Cuts (Ncuts) approach, which scored 52.79%.
  • Robust Tracking: By using these clusters to constrain SIFT matching, the system could track a cheetah through perspective changes and deformations that caused standard SIFT matching to fail completely.
  • Efficiency: Because the algorithm only clusters a few thousand keypoints rather than millions of pixels, it is much more computationally efficient than full-scene segmentation.
A comparison of the pipeline: (Top) Input images and the resulting keypoint clusters. (Bottom) Standard SIFT matching (left) versus the proposed constrained matching (right).

Conclusion

This appearance-based clustering method provides a robust way to organize keypoints before attempting to match them across frames. While the current implementation uses a fixed cluster count, future work could automate this process. The authors suggest this framework could be integrated into higher-level tasks like 3D reconstruction or "bag of features" object recognition to provide a cleaner, more organized set of inputs.

Summary updated

Abstract

We present an algorithm for clustering sets of detected interest points into groups that correspond to visually distinct structure. Through the use of a suitable colour and texture representation, our clustering method is able to identify keypoints that belong to separate objects or background regions. These clusters are then used to constrain the matching of keypoints over pairs of images, resulting in greatly improved matching under difficult conditions. We present a thorough evaluation of each component of the algorithm, and show its usefulness on difficult matching problems.
BibTeX
@inproceedings{estrada2009appearance,
  author = {Francisco J. Estrada and Pascal Fua and Vincent Lepetit and Sabine Süsstrunk},
  title = {{Appearance-based keypoint clustering}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2009},
  url = {https://openreview.net/forum?id=B14psJMdZS},
}
Figure