Carnegie Mellon University
Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming

Y. Ohta and Takeo Kanade
IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-7, No. 2, pp. 139-154, March, 1985.

  • Adobe portable document format (pdf) (14MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

This paper presents a stereo matching algorithm using the dynamic programming technique. The stereo matching 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 scan-lines. We call this search intra-scanline search. This intra-scanline search can be treated as the problem of finding a matching path on a two-dimensional (2D) search plane whose axes are the right and left scan-lines. Vertically connected edges in the images provide consistency constraints across the 2D search planes. Inter-scanline search in a three-dimensional (3D) search space, which is a stack of the 2D search planes, is needed to utilize this constraint. Our stereo matching algorithm uses edgedelimited 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 edgedelimited intervals on each scanline pair. Dynamic programming is used for both searches which proceed simultaneously: the former supplies the consistency constraint to the latter while the latter supplies the matching scok to the former. An interval-based similarity metric is used to compute the score. The algorithm has been tested with different types of images including urban aerial images, synthesized images, and block scenes, and its computational requirement has been discussed.

Associated Center(s) / Consortia: Vision and Autonomous Systems Center
Number of pages: 16

Text Reference
Y. Ohta and Takeo Kanade, "Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming," IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-7, No. 2, pp. 139-154, March, 1985.

BibTeX Reference
   author = "Y. Ohta and Takeo Kanade",
   title = "Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming",
   journal = "IEEE Trans. Pattern Analysis and Machine Intelligence",
   pages = "139-154",
   month = "March",
   year = "1985",
   volume = "PAMI-7",
   number = "2",