Stereo Matching by Hierarchical, Microcanonical Annealing

Stephen T. Barnard

Introduction

Stereo matching—the process of identifying corresponding points in two images to calculate depth—remains a fundamental yet "ill-posed" problem in computer vision. Early stochastic approaches utilized simulated annealing, specifically the Metropolis algorithm, to find the "ground state" of an energy function. This function balances image similarity with surface smoothness. However, standard simulated annealing is computationally expensive, requiring transcendental functions and high-quality random numbers that are difficult to implement efficiently on parallel architectures.

This paper introduces a significantly faster and more scalable approach by replacing traditional simulated annealing with microcanonical annealing (the Creutz algorithm) and a hierarchical, coarse-to-fine control structure. This combination enables the processing of high-resolution imagery with large disparity ranges while drastically reducing computational complexity.

The Microcanonical Approach

Unlike the standard "heat bath" approach where a system is immersed in a constant temperature, the microcanonical approach simulates a thermally isolated system. It introduces an extra degree of freedom known as a "demon."

The energy function used to optimize disparity maps.

In this system, when a proposed change reduces the system's energy, the surplus energy is transferred to the demon. Conversely, when a change increases energy, the demon "pays" for it from its own energy reservoir. If the demon has insufficient energy, the move is rejected. This mechanism allows the algorithm to be implemented using simple integer arithmetic, avoiding the costly floating-point math required by the Metropolis algorithm. In this context, "temperature" becomes a statistical feature of the system rather than a manually controlled parameter.

Hierarchical Control and Laplacian Pyramids

To manage the exponential growth of the search space in high-resolution images, the algorithm employs a hierarchical strategy using Laplacian pyramids. The process begins at a coarse resolution (e.g., 16x16 pixels) to find an approximate solution, which then serves as the initialization for the next, finer level.

To further optimize the search, the system utilizes Brownian state-transitions. Instead of selecting a random disparity from the entire possible range, the system restricts moves to $\pm 1$ pixel from the current state. This guided "Brownian motion" through state space is highly efficient when initialized by the results of a lower-resolution level.

One critical insight involves "breaking symmetry" during transitions between scales. When upscaling a disparity map, the system can become trapped in a "metastable state" because only even-numbered disparities are initially occupied. The author addresses this by "adding heat" (increasing the demon's energy) during the transition to break this artificial symmetry and allow the system to settle into a more accurate state.

Results and Discussion

The algorithm was evaluated using a 512 x 512 aerial stereogram of the Martin Marietta ALV (Autonomous Land Vehicle) test site, featuring a disparity range of 50 pixels. Despite a state space $10^{36000}$ times larger than problems addressed by previous versions of the algorithm, the hierarchical approach achieved a massive speedup. The 512x512 pair was solved in approximately 12 hours on a Symbolics 3600—comparable to the time previously required for a much smaller 256x256 problem.

Disparity map result showing the 'hogback' ridge.

Qualitatively, the resulting disparity map successfully captures complex terrain features, including a prominent diagonal "hogback" ridge and surrounding valleys. While the current implementation uses a single demon (creating a sequential bottleneck), the underlying logic is well-suited for fine-grained parallel hardware like the Connection Machine. Future work will focus on multi-demon parallel implementations and more rigorous quantitative error analysis against ground-truth data.

Summary updated

BibTeX
@inproceedings{barnard1987stereo,
  author = {Stephen T. Barnard},
  title = {{Stereo Matching by Hierarchical, Microcanonical Annealing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure