A fast algorithm for stereo matching

Stereo matching is a useful method to obtain the 3-dimensional (3-D) depth information from a pair of images. In this paper, we first transform the stereo matching problem into a banded cyclic string-to-string correction (BCSTSC) problem. Then a brute-force algorithm, which runs in O(nmd) time, is described, where n and m are the lengths of the two given feature strings and d is the disparity. Further, an improved O(nm log d)-time algorithm for solving the BCSTSC problem is presented. Our result generalizes Maes's result (1990) since the special version of the BCSTSC problem can be transformed into the cyclic string-to-string correction problem when setting d = m. (C) 1997 Elsevier Science B.V.