Stereo Matching by Hierarchical, Microcanonical Annealing

TL;DR

This paper introduces an improved stereo matching algorithm that significantly boosts performance by combining a novel "microcanonical annealing" technique with a hierarchical, coarse-to-fine resolution approach. This allows for more efficient and controllable computation of dense disparity maps, tackling much larger disparity ranges than previous methods.

What Problem Does This Paper Address?

Stereo matching, the process of determining the 3D structure of a scene from two or more images taken from different viewpoints, is a fundamental problem in computer vision. A key challenge is accurately estimating the "disparity" – the horizontal shift between corresponding points in the left and right images – for every pixel. Traditional methods often struggle with large disparity ranges and computational complexity. This paper aims to overcome these limitations by developing a more efficient and robust stochastic optimization approach.

Methods

The paper presents two main innovations:

  • Microcanonical Annealing: This is a variation of simulated annealing, a powerful optimization technique. Instead of the conventional "canonical" approach (where the system is in thermal contact with a heat bath), microcanonical annealing simulates a "thermally isolated" system where total energy is conserved. This is achieved using a "demon" that carries excess energy. The authors adopt the Creutz algorithm for this, which is noted for being faster, simpler, and more controllable than the Metropolis algorithm, and importantly, does not require transcendental functions or high-quality random numbers, making it suitable for parallel processing.
  • Hierarchical, Coarse-to-Fine Resolution: The algorithm now operates across multiple levels of image resolution, starting with a coarse representation and progressively refining it. This is achieved using a Laplacian pyramid, a technique that decomposes an image into a series of bandpass-filtered, smaller images. By starting with a small, low-resolution problem, an approximate ground state is found quickly. This solution is then used to initialize the annealing process at the next, finer resolution level. This hierarchical approach significantly reduces computational complexity, especially for large disparity ranges.

Datasets

The authors evaluate their algorithm on an aerial stereo pair of 512x512 pixels from the Martin Marietta test site near Denver. This dataset features a disparity range of up to 50 pixels. The paper notes that the largest problem solved by the previous version of their system was a 256x256 pair with 15 levels of disparity.

Key Insights and Ideas

  • Microcanonical Annealing for Efficiency: The shift from canonical to microcanonical annealing offers a significant speedup (potentially an order of magnitude) and simplifies implementation, especially for parallel hardware.
  • Hierarchical Approach for Scalability: The coarse-to-fine strategy is crucial for handling large disparity ranges. By solving smaller problems first and propagating solutions, the algorithm avoids the exponential explosion of the state space that plagues traditional methods.
  • Brownian State Transitions: A modified state-transition function that restricts disparity changes to +/- 1 pixel (Brownian motion) is key to the hierarchical approach. This, combined with the hierarchical structure, makes the algorithm more efficient and eliminates the need to pre-specify disparity bounds.
  • Overcoming Symmetry Issues: When expanding solutions from coarser to finer levels, a spurious symmetry can be introduced. The authors propose "adding heat" (increasing demon temperature) to break this symmetry and prevent the system from getting stuck in metastable states.

Key Results

The paper demonstrates a substantial improvement in performance. A 512x512 pair with a 50-pixel disparity range was computed in approximately 12 hours on a Symbolics 3600. This is remarkable considering that the previous version would have required vastly more computation for such a large disparity range (a factor of over 10^36000 greater state space). The hierarchical approach, combined with the microcanonical annealing, is credited with this dramatic increase in performance.

Limitations and Future Work

  • Quantitative Evaluation: While qualitative improvements are clear, the authors state they are "currently evaluating the quantitative increase in performance attributable to each new technique."
  • Parallel Implementation: While microcanonical annealing is well-suited for parallel processing, the single-demon algorithm used for the results is sequential. The paper mentions preliminary experiments with a multi-demon approach (one per site) showing good performance, suggesting this as a direction for further parallelization.
  • Generalizability: The authors believe both microcanonical annealing and the hierarchical control structure are general techniques applicable to other simulated-annealing problems in low-level vision.

Summary updated

BibTeX
@inproceedings{1987stereo,
  title = {{Stereo Matching by Hierarchical, Microcanonical Annealing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure