---
title: "Stereo by Two-Level Dynamic Programming"
authors:
  - "Yuichi Ohta"
  - "Takeo Kanade"
doi: ""
url: "https://ijcai.org/proceedings/1985/230"
pdf: "https://ijcai.org/proceedings/1985/0230.pdf"
venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence"
year: 1985
pages: "1120-1125"
track: "Robotics"
keywords:
---

# Stereo by Two-Level Dynamic Programming

Yuichi Ohta, Takeo Kanade

*Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 1120-1125.

## 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.