Kolmogorov and Zabih’s Graph Cuts Stereo Matching Algorithm
Vladimir Kolmogorov, Pascal Monasse, Pauline Tan
Vladimir Kolmogorov, Pascal Monasse, and Pauline Tan, Kolmogorov and Zabih’s Graph Cuts Stereo Matching Algorithm, Image Processing On Line, 4 (2014), pp. 220–251. https://doi.org/10.5201/ipol.2014.97

Communicated by Loïc Simon
Demo edited by Pascal Monasse


Binocular stereovision estimates the three-dimensional shape of a scene from two photographs taken from different points of view. In rectified epipolar geometry, this is equivalent to a matching problem. This article describes a method proposed by Kolmogorov and Zabih in 2001, which puts forward an energy-based formulation. The aim is to minimize a four-term-energy. This energy is not convex and cannot be minimized except among a class of perturbations called expansion moves, in which case an exact minimization can be done with graph cuts techniques. One noteworthy feature of this method is that it handles occlusion: The algorithm detects points that cannot be matched with any point in the other image. In this method displacements are pixel accurate (no subpixel refinement).


Non-Reviewed Supplementary Materials

These files and information are provided by the authors and have not been reviewed.