SIMPLE BUT EFFECTIVE TREE STRUCTURES FOR DYNAMIC PROGRAMMING-BASED STEREO MATCHING

Michael Bleyer, Margrit Gelautz

2008

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.

Paper Citation

in Harvard Style

Bleyer M. and Gelautz M. (2008). SIMPLE BUT EFFECTIVE TREE STRUCTURES FOR DYNAMIC PROGRAMMING-BASED STEREO MATCHING . In Proceedings of the Third International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2008) ISBN 978-989-8111-21-0, pages 415-422. DOI: 10.5220/0001072904150422

in Bibtex Style

@conference{visapp08,
author={Michael Bleyer and Margrit Gelautz},
title={SIMPLE BUT EFFECTIVE TREE STRUCTURES FOR DYNAMIC PROGRAMMING-BASED STEREO MATCHING},
booktitle={Proceedings of the Third International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2008)},
year={2008},
pages={415-422},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001072904150422},
isbn={978-989-8111-21-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Third International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, (VISIGRAPP 2008)
TI - SIMPLE BUT EFFECTIVE TREE STRUCTURES FOR DYNAMIC PROGRAMMING-BASED STEREO MATCHING
SN - 978-989-8111-21-0
AU - Bleyer M.
AU - Gelautz M.
PY - 2008
SP - 415
EP - 422
DO - 10.5220/0001072904150422