Stereo without epipolar lines: A maximum-flow formulation

This paper describes a new algorithm for solving the stereo correspondence problem with a global 2-d optimization by transforming it into a maximum-flow problem in a graph. This transformation effectively removes explicit use of epipolar geometry, thus allowing direct use of multiple cameras with arbitrary geometries. The maximum-flow, solved both efficiently and globally, yields a minimum-cut that corresponds to a disparity surface for the whole image at once. This global and efficient approach to stereo analysis allows the reconstruction to proceed in an arbitrary volume of space and provides a more accurate and coherent depth map than the traditional stereo algorithms. In particular, smoothness is applied uniformly instead of only along epipolar lines, while the global optimality of the depth surface is guaranteed. Results show improved depth estimation as well as better handling of depth discontinuities. While the worst case running time is O(n(1.5) d(1.5) log(nd)), the observed average running time is O(n(1.2) d(1.3)) for an image size of n pixels and depth resolution d.