A Representation for Image Curves

David H. MarimontAAAI 1984

This seminal 1984 work from the Stanford Artificial Intelligence Laboratory addresses a fundamental challenge in computer vision: representing image curves (edges) in a way that allows a computer to recognize specific objects despite changes in viewpoint, noise, or occlusion. The paper introduces a robust, hierarchical description of shapes based on "critical points" that remain stable across different resolutions.

The Challenge of Curve Representation

In model-based vision, matching edges found in an image to a database of known shapes is complicated by three primary factors:

  1. Viewpoint Sensitivity: Geometric distortions occur as the camera moves relative to the object.
  2. Noise and Resolution: Digital images are inherently grainy, and the level of detail varies with distance.
  3. Occlusion: Objects often partially hide one another, requiring a representation that can handle fragmented curves.

David Marimont argues for a representation that is "partially invariant" to these factors. A representation that changes drastically with minor camera movements makes computational matching impossible.

Methodology

The proposed system utilizes a three-stage pipeline to transform raw image data into a structured representation:

1. Multi-Scale Smoothing

Raw sampled curves from an edge detector are smoothed using Gaussian filters at various scales. This process filters out high-frequency noise and allows the system to capture the global structure of the shape.

2. Critical Point Extraction

On these smoothed curves, the algorithm identifies "knots"—specific locations where the curvature $\kappa$ is either zero (inflection points) or at a local extremum (sharp bends or peaks). These points serve as the fundamental primitives for the representation.

Figure 1: Identification of critical points (maxima, minima, and zeros of curvature) on various sample curves.

3. Monotone Curvature Splines and Dynamic Programming

To ensure mathematical consistency, Marimont introduces splines composed of circular arcs where curvature changes monotonically between knots. Finally, a dynamic programming (DP) approach selects the optimal subset of knots across different scales, finding the shortest list of points that approximates the original curve within a defined error tolerance.

Key Insights

  • Projective Invariance: A core mathematical insight is that zeros of curvature are invariant under orthographic projection. While curvature extrema are not perfectly invariant, they move predictably, making them reliable features for matching.
  • Local Support: Because the representation consists of discrete knots, it possesses "local support." If an object is partially occluded, the knots for the visible portion remain unchanged, facilitating identification.
  • The Scale-Space Conjecture: Building on the work of Andrew Witkin, Marimont notes that while smoothing can cause critical points to merge or disappear, it rarely creates new ones. This top-down simplification is central to multi-scale analysis.
Figure 5: The evolution of critical points across eight different scales of smoothing, demonstrating the stability and hierarchical nature of the representation.

Results and Stability

The paper demonstrates that critical points remain remarkably stable even under significant rotation or tilt. The dynamic programming approach efficiently finds the best approximation for any given number of knots, with a computational complexity of $O(n^2)$, where $n$ is the number of candidate knots. As the number of allowed knots decreases, the algorithm naturally preserves the most structurally significant features of the shape.

Limitations and Future Work

While the representation is robust, the paper identifies several areas for further research, including the automation of "natural" scale selection and the integration of knots from disparate scales. The actual "matching engine" for comparing these knot lists to 3D model databases was left for subsequent publications.

Summary updated

BibTeX
@inproceedings{marimont1984representation,
  author = {David H. Marimont},
  title = {{A Representation for Image Curves}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure