MDL patch correspondences on unlabeled images with occlusions

Johan Karlsson, Kalle ÅströmWorkshops @ CVPR 2008 · DOI

Introduction

Building robust computer vision models typically requires extensive human intervention in the form of labeled landmarks or pre-segmented images. This paper presents a framework for the unsupervised discovery of "parts+geometry" models from messy, unlabeled image sets. By leveraging the Minimum Description Length (MDL) principle, the proposed system treats model-building as a data compression problem, enabling simultaneous image classification, part identification, and occlusion handling without human supervision.

Problem Statement

Traditional computer vision struggles with real-world, unlabeled data characterized by three primary challenges:

  1. Unlabeled Images: Datasets often contain multiple object categories mixed together.
  2. Occlusions: Significant portions of an object may be hidden.
  3. Clutter: Background noise can interfere with object identification.

The goal is to solve for image classification, inlier detection, correspondence, and model complexity (determining the optimal number of parts) in a unified framework.

Methodology

The MDL Objective

The core of the approach is the MDL principle: the best model is the one that provides the shortest description of the data. The total description cost includes the model (mean part coordinates and PCA variational modes), parameters (rotation, scale, translation), residuals (errors between model and image points), and outliers (a penalty for unexplained points).

Optimization and Search Strategy

To navigate the complex combinatorial search space, the authors employ several strategies:

  • Initial Guess: A "transport problem" algorithm provides a starting point based on strong corner features.
  • Six-Move Search: Iterative refinement through moves such as adding/deleting points, swapping inlier/outlier status, and changing correspondences.
  • Scale Space: Coarse-to-fine optimization helps avoid local minima.
  • Missing Data Handling: Specialized Procrustes analysis and PCA are used to manage occluded data points.

Experimental Results

The framework was evaluated on diverse datasets, including face videos, headshots of different individuals, and mixed sets (e.g., faces and starfish).

Model Discovery and Correspondence

In tests with headshot images, the system successfully discovered coherent geometric models. Figure 1 illustrates a 20-point model discovered across a set of unlabeled face images, demonstrating how the algorithm identifies consistent landmarks across different subjects.

Example of a discovered 20-point geometric model on a headshot image, demonstrating correspondence across the dataset.

Robustness to Occlusion and Clutter

The system demonstrated high robustness to noise and occlusions. In the face video test, 880 raw feature points were reduced to a stable geometric model. Even with 50% synthetic occlusion, the algorithm maintained correct correspondences for visible parts. Figure 4 shows patch-based feature detection on a face with glasses, highlighting the system's ability to handle real-world variations and background clutter.

Patch-based feature detection and correspondence on a face image, illustrating the system's ability to handle real-world clutter and variations like eyewear.

When tested on a mix of faces and starfish, the system achieved 100% classification accuracy, automatically building distinct models for each class without prior knowledge of the number of categories.

Conclusion

The MDL-based approach provides a powerful, unsupervised method for discovering object structure in cluttered and occluded environments. By using compression as a proxy for truth, the system naturally balances model complexity and accuracy. Future work may involve exploring more complex transformation groups and reducing the computational cost of the combinatorial search.

Summary updated

BibTeX
@inproceedings{karlsson2008mdl,
  author = {Johan Karlsson and Kalle Åström},
  title = {{MDL patch correspondences on unlabeled images with occlusions}},
  booktitle = {Workshops @ CVPR},
  year = {2008},
  doi = {10.1109/cvprw.2008.4563085},
}
Figure