Stereo by Two-Level Dynamic Programming

Abstract

This paper presents a stereo algorithm using dynamic programming technique. The stereo matehing problem, that is, obtaining a correspondence between right and left images, can be cast as a search problem. When a pair of stereo images is rectified, pairs of corresponding points can be searched for within the same scanlines. We call this search intra-scanline search. This intra-scanline search can be treated as the problern of finding a matehing path on a two dimensional (20) search plane whose axes are the right and left scanlines. Vertically connected edges in the images provide consistency constraints across the 20 search planes. lnter-sco.nline search in a three-dimensional (30) search space, which is a stack of the 20 search planes, is needed to utilize this constraint. Our stereo matehing algorithm uses edge-delimited intervals as elements to be matched, and employs the above mentioned two searches: one is inter-scanline search for possible correspondences of connected edges in right and left images and the other is intra-scanline search for correspondences of edge-delimited intervals on each scanline pair. Dynamic programming is used for both searches which proceed simultaneously in two Ieveis: the former supplies the consistency constraints to the latter while the latter supplies the matehing score to the former. An interval-based similarity metric is used to compute t he score.