The correspondence problem in stereo vision involves obtaining a disparity map, which represents the differences between the positions of matching pixels in two stereo images. Markov random fields (MRFs) are widely used to model vision problems, and they are particularly used to model the disparity map. Although MRF labeling is an intractable problem, two fast algorithms, graph cuts (GC) and belief propagation (BP), have recently arisen to approximate the optimal solution.

The problem of MRF-based algorithms is that their results are heavily influenced by the setting of parameters, which is usually empirically done by the user. Also, the optimal parameters may vary from one image pair to another.

An ingenious solution to this problem, the expectation maximization (EM) algorithm, is proposed in this paper. Starting with an arbitrary parameter set, the EM algorithm iterates in cooperation with an MRF-based stereo matching algorithm, and converges obtaining a convenient (nearly optimal) set of parameters and a related disparity map.

The method was designed to be combined with any existing stereo algorithm that works with a model that involves the minimization of two energy functions, one that represents the difference between matching pixels, and the other, the regularization term, that represents the difference between neighbor disparities. However, it has to be noted that, considering there is no unique metric to model the energy functions, for every different stereo algorithm it is necessary to have a redefinition of the formulas used in EM (and this could be the complicated part).

The authors test the EM algorithm, combined with the GC and BP stereo algorithms. They demonstrate that the EM algorithm improves the performance of the original algorithms with fixed parameters, resulting in a higher rank in the well-known Middlebury ranking table.