Abstract
A stochastic optimization approach to stereo matching is presented. Unlike conventional correlation matching and feature matching, the method provides a dense array of disparities, eliminating the need for interpolation. First, the stereo-matching problem is defined in terms of finding a disparity map that satisfies two competing constraints: (1) matched points should have similar image intensity, and (2) the disparity map should vary as slowly as possible. These constraints are interpreted as specifying the potential energy of a system of oscillators. Ground states are approximated by a new variant of simulated annealing, which has two important features. First, the microcanonical ensemble is simulated using a new algorithm that is more efficient and more easily implemented than the familiar Metropolis algorithm (which simulates the canonical ensemble). Secondly, it uses a hierarchical, coarse-to-fine control structure employing Gaussian or Laplacian pyramids of the stereo images. In this way, quickly computed results at low resolutions are used to initialize the system at higher resolutions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
D. Terzopoulos, “Image analysis using multigrid relaxation methods,” IEEE TRANS. PAMI, 8:129–139, 1986.
G. Sperling, “Binocular vision: A physical and neural theory,” J. Am. Psychol. 83:461–534, 1970.
B. Julesz, Foundations of Cyclopean Perception, Univ. of Chicago Press: Chicago, IL, 1971.
D. Marr and T. Poggio, “Cooperative computation of stereo disparity,” Science 194:283–287, 1976.
T. Poggio, V. Torre, and C. Koch, “Computational vision and regularization theory,” Nature 317:314–319, 1985.
A. Witkin, D. Terzopoulos, and M. Kass, “Signal matching through scale space,” Intern. J. Computer Vision 1:133–144, 1987.
B.K.P. Horn, Robot Vision, M.I.T. Press: Cambridge, MA, 1986.
G.H. Walker and J. Ford, “Amplitude instability and ergodic behavior for conservative nonlinear oscillator systems,” Phys. Rev. 188: 416–432, 1969.
N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, “Equations of state calculations by fast computing machines,” J. Chem. Phys. 21: 1087–1092, 1953.
P.J.M. van Laarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Applications, D. Reidel Publishing: Dordrecht, Holland, 1987.
S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by simulated annealing,” Science 220:671–680, 1983.
V. Černy, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm,” J. Opt. Theory Appl. 45:41–51, 1985.
S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and Bayesian restoration of images,” IEEE Trans. PAMI 6:721–741, 1984.
S. Barnard, “A stochastic approach to stereo vision,” in Proc. Nat. Conf. Artif. Intell., Philadelphia, pp. 676–680, 1986.
J.L. Marroquin, “Probabilistic solution of inverse problems,” Tech. Rept. 860, M.I.T. Artificial Intelligence Lab., Cambridge, MA, 1985.
R. Divko and K. Schulten, “Stochastic spin models for pattern recognition,” Physik-Department, Technische Universität München, personal correspondence, 1987.
P. Burt, “The Laplacian pyramid as a compact image code,” IEEE Trans. Communications 31:532–540, 1983.
M. Creutz, “Microcanonical Monte Carlo simulation,” Physical Rev. Lett 50:1411–1414, 1983.
G. Bhanot, M. Creutz, and H. Neuberger, “Microcanonical simulation of Ising systems,” Nuclear Physics B235[FS11], pp. 417–434, 1984.
S. Barnard, “Stereo matching by hierarchical, microcanonical annealing,” Proc. 10th Intern. Joint Conf. Artif Intell., Milan, Italy, pp. 832–835, 1987.
Author information
Authors and Affiliations
Additional information
Support for this work was provided by the Defense Advanced Research Projects Agency under contracts DCA 76-85-C-0004 and MDA 903-83-C-0084.
Rights and permissions
About this article
Cite this article
Barnard, S.T. Stochastic stereo matching over scale. Int J Comput Vision 3, 17–32 (1989). https://doi.org/10.1007/BF00054836
Issue Date:
DOI: https://doi.org/10.1007/BF00054836