Contour Organisation with the EM Algorithm

José A. F. Leite, Edwin R. HancockNeurIPS 1996

This paper, published in the late 1990s, presents a robust statistical approach to one of the fundamental challenges in computer vision: contour organization. It demonstrates how the Expectation-Maximization (EM) algorithm can be used to bridge the gap between local edge detection and global structural understanding.

The Challenge of Contour Organization

In early computer vision, the first step is usually "feature enhancement"—applying filters to find edges or lines. However, the output is often a mess of noisy, disconnected, and ambiguous local measurements. The real challenge is grouping these local fragments into meaningful global structures, like a continuous road or a boundary.

Existing solutions at the time fell into two camps:

  1. Biologically inspired models: These used "spline coverings" and "snake dynamics" to find smooth curves but often relied on ad hoc local compatibility rules.
  2. Statistical models: These used "probabilistic relaxation" (Bayesian frameworks), which were mathematically sound but computationally limited to very small neighborhoods (e.g., 3x3 pixels), making them "blind" to larger global structures.

The authors aim to bridge this divide by using a global spline representation within a formal statistical framework.

The EM Algorithm for Spline Fitting

The core of the paper is the application of the Expectation-Maximization (EM) algorithm to spline fitting. The image is modeled using a set of local cubic splines, where each pixel is characterized by a measurement vector from a battery of line-detection filters.

The authors treat the image data as a "mixture model" where each pixel's measurement could have been generated by one of several putative splines in its neighborhood.

  • The Expectation (E) Step: The algorithm calculates the a posteriori probability (a weight) that a specific pixel belongs to a specific spline based on how well the pixel's data matches the current spline parameters. This step is mathematically analogous to "probabilistic relaxation," providing a solid theoretical justification for why EM works well for grouping tasks.
  • The Maximization (M) Step: The spline parameters are updated to maximize the likelihood of the data. Because they use a Gaussian model for residuals, this step simplifies into a weighted least-squares problem, which can be solved using standard linear equations. By weighting the fit by the probabilities from the E-step, the algorithm naturally ignores "outliers" (noise) that don't fit the emerging contour.

This process repeats iteratively. As the splines become more accurate, the pixel assignments become less ambiguous, leading to a clean final contour map.

Results on Aerial Imagery

The authors evaluate their technique on aerial infra-red images, specifically focusing on the localization of road structures. These images are notoriously difficult due to noise, varying road widths, and complex junctions.

Original image, probability map, and final line map

The final contour maps show excellent connectivity compared to raw filter outputs. The "probability maps" demonstrate that while the initial neighborhood is highly ambiguous (with many competing splines), the final state is sharp and certain.

Junction Reconstruction and Convergence

One of the most impressive capabilities of the model is its handling of junctions. Even if a spline starts poorly oriented, the iterative process allows it to align itself with the underlying road segments.

Iterative refinement of splines at a junction

In the early iterations, many splines "compete" to explain the local data. As the algorithm converges, the splines "cooperate" to form a continuous, unambiguous structure. Qualitative results show the "evolution" of the splines, where a spline that starts displaced or poorly oriented "snaps" into the correct position and orientation over several iterations.

Limitations and Future Work

While powerful, the approach has a few notable limitations:

  • Initialization Dependence: Like all EM-based methods, the algorithm requires a decent starting point. It relies on an initial multi-scale line feature probability to kick off the process.
  • Computational Complexity: While more global than 3x3 relaxation, the spline-fitting process is still computationally intensive compared to simple edge detectors.
  • Parameter Tuning: The model uses a control variable to regulate the effect of fit residuals, which may require manual tuning for different types of imagery.

Despite these constraints, the authors suggest that this 2D spline-fitting framework is readily extendible to 3D surface patch reconstruction, hinting at broader applications in topographic mapping or medical imaging.

Summary updated

BibTeX
@inproceedings{leite1996contour,
  author = {José A. F. Leite and Edwin R. Hancock},
  title = {{Contour Organisation with the EM Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
}
Figure