Kolmogorov and Zabih's Graph Cuts Stereo Matching Algorithm

Vladimir Kolmogorov (1) , Pascal Monasse (2, 3, 4) , Pauline Tan (5)

1 UCL-CS - Computer science department [University College London]
2 imagine [Marne-la-Vallée]
3 ENPC - École des Ponts ParisTech
4 LIGM - Laboratoire d'Informatique Gaspard-Monge
5 CMLA - Centre de Mathématiques et de Leurs Applications

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).

Domaines: Informatique [cs]; Vision par ordinateur et reconnaissance de formes [cs.CV]

Vladimir Kolmogorov, Pascal Monasse, Pauline Tan. Kolmogorov and Zabih's Graph Cuts Stereo Matching Algorithm. Image Processing On Line, 2014, 4, pp.220-251. ⟨10.5201/ipol.2014.97⟩. ⟨hal-01074878⟩