We describe a theoretical formulation for stereo in terms of the Markov Random Field and Bayesian approach to vision. This formulation enables us to integrate the depth information from different types of matching primitives, or from different vision modules. We treat the correspondence problem and surface interpolation as different aspects of the same problem and solve them simultaneously, unlike most previous theories. We use techniques from statistical physics to compute properties of our theory and show how it relates to previous work. These techniques also suggest novel algorithms for stereo which are argued to be preferable to standard algorithms on theoretical and experimental grounds. It can be shown (Yuille, Geiger and Bülthoff 1989) that the theory is consistent with some psychophysical experiments which investigate the relative importance of different matching primitives.