Simple but Effective Tree Structures for Dynamic Programming-based Stereo Matching

By Michael Bleyer and Margrit Gelautz

Abstract

This work describes a fast method for computing dense stereo correspondences that is capable of generating results close to the state-of-the-art. We propose running a separate disparity computation process in each image pixel. The idea is to root a tree graph on the pixel whose disparity needs to be reconstructed. The tree thereby forms an individual approximation of the standard four-connected grid for this specific pixel. An exact optimum of a predefined energy function on the applied tree structure is determined via dynamic programming (DP), and the root pixel is assigned to the disparity of optimal costs. We present two simple tree structures that allow for the efficient calculation of all trees' optima with only four scanline-based DP passes. These simple trees are designed to capture all pixels of the reference frame and incorporate horizontal and vertical smoothness edges in order to weaken the scanline streaking problem inherent in DP-based approaches. We evaluate our results using the Middlebury test set. Our algorithm currently ranks at the eighth position of approximately 30 algorithms in the Middlebury database. More importantly, it is the currently best-performing method that does not use image segmentation and is significantly faster than most competing algorithms. Our method needs less than a second to determine the disparity map for typical stereo pairs.

Reference

M. Bleyer, M. Gelautz: "Simple but Effective Tree Structures for Dynamic Programming-based Stereo Matching"; Talk: International Conference on Computer Vision Theory and Applications (VISAPP 2008), Funchal, Madeira - Portugal; 01-22-2008 - 01-25-2008; in: "International Conference on Computer Vision Theory and Applications (VISAPP)", (2008), 415 - 422.

Additional Information

Presentation slides are available for download here.

Downloads

simple tree

1.91 MB

PDF document

Download

BibTeX

@inproceedings{TUW-169059,     author = {Bleyer, Michael and Gelautz, Margrit},     title = {Simple but Effective Tree Structures for Dynamic Programming-based Stereo Matching},     booktitle = {International Conference on Computer Vision Theory and Applications (VISAPP)},     year = {2008},     pages = {415--422},     url = {http://publik.tuwien.ac.at/files/PubDat_169059.pdf},     keywords = {Stereo matching, tree-based dynamic programming, fast stereo method.},     note = {Vortrag: International Conference on Computer Vision Theory and Applications (VISAPP 2008), Funchal, Madeira - Portugal; 2008-01-22 -- 2008-01-25} } Click into the text area and press Ctrl+A/Ctrl+C or ⌘+A/⌘+C to copy the BibTeX into your clipboard… or download the BibTeX.