Kolmogorov and Zabih’s Graph Cuts Stereo Matching Algorithm
Vladimir Kolmogorov, Pascal Monasse, Pauline Tan
→ BibTeX
    title   = {{Kolmogorov and Zabih’s Graph Cuts Stereo Matching Algorithm}},
    author  = {Kolmogorov, Vladimir and Monasse, Pascal and Tan, Pauline},
    journal = {{Image Processing On Line}},
    volume  = {4},
    pages   = {220--251},
    year    = {2014},
    doi     = {10.5201/ipol.2014.97},
% if your bibliography style doesn't support doi fields:
    note    = {\url{https://doi.org/10.5201/ipol.2014.97}}
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.