Institute of Information Sciences and Electronics, University of Tsukuba, Ibaraki, 305, Japan.
IEEE Trans Pattern Anal Mach Intell. 1985 Feb;7(2):139-54. doi: 10.1109/tpami.1985.4767639.
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 scanlines. 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 scanlines. 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 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: the former supplies the consistency constraint to the latter while the latter supplies the matching score 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.
本文提出了一种基于动态规划技术的立体匹配算法。立体匹配问题，即将左右图像进行匹配，可以转化为搜索问题。当一对立体图像被校正后，可以在同一扫描线内搜索到对应的点对。我们称这种搜索为 内扫描线搜索。这种内扫描线搜索可以看作是在二维（2D）搜索平面上找到匹配路径的问题，其轴是左右扫描线。图像中的垂直连接边缘在 2D 搜索平面之间提供了一致性约束。需要在三维（3D）搜索空间中进行 跨扫描线搜索，即 2D 搜索平面的堆叠，以利用这种约束。我们的立体匹配算法使用边缘限定的区间作为匹配元素，并采用上述两种搜索方法：一种是在左右图像中连接边缘的 跨扫描线搜索，另一种是在每一对扫描线上的边缘限定区间的 内扫描线搜索。动态规划用于这两种同时进行的搜索：前者为后者提供一致性约束，后者为前者提供匹配得分。使用基于区间的相似性度量来计算得分。该算法已经在不同类型的图像上进行了测试，包括城市航空图像、合成图像和块状场景，并讨论了其计算需求。
