Abstract

Semi-global matching (SGM) is among the top-ranked stereovision algorithms. SGM is an efficient strategy for approximately minimizing a global energy that comprises a pixel-wise matching cost and pair-wise smoothness terms. In SGM the two-dimensional smoothness constraint is approximated as the average of one-dimensional line optimization problems. The accuracy and speed of SGM are the main reasons for its widespread adoption, even when applied to generic problems beyond stereovision. This approximate minimization, however, also produces characteristic low amplitude streaks in the final disparity image, and is clearly suboptimal with respect to more comprehensive minimization strategies. Based on a recently proposed interpretation of SGM as a min-sum Belief Propagation algorithm, we propose a new algorithm that allows to reduce by a factor five the energy gap of SGM with respect to reference algorithms for MRFs with truncated smoothness terms. The proposed method comes with no compromises with respect to the baseline SGM, no parameters and virtually no computational overhead. At the same time it attains higher quality results by removing the characteristic streaking artifacts of SGM.

• [pdf]
• [Extended Abstract]
• [Supplementary Material]
• [code on GitHub]
• [optimization code (C++/Matlab)]

Note: The code and the online demo also admit the truncated-linear smoothness potentials as in [Felzenszwalb and Huttenlocher'06].

Online demo

An online demo for MGM is available here.