A TOPOLOGICAL STEREO MATCHER

Presented here is a new stereo algorithm that produces dense, high-quality, subpixel disparity maps. It offers two improvements over previous algorithms. First, it does not blur disparity values across sharp changes in depth. Second, it can reconstruct the correct correspondence between two images even when there is substantial vertical displacement between them: this algorithm has been tested with rotations up to 10 degrees and vertical translations up to 16 pixels. Although such image pairs require extra processing time, this ability is vital when exact calibration cannot be maintained. The new algorithm depends on two new ideas. First, it exploits the fact that the correct vertical disparity field is due to camera misalignment and, thus, has only a few (significant) degrees of freedom. The algorithm passes camera alignment parameters, not raw disparity fields, between scales. Disparities at individual locations can diverge only slightly from this global model, greatly reducing the algorithm's search space. Second, the new algorithm uses a pre-match filter that prevents two patches of image from matching if they do not have the same (local) topological structure. This constraint subsumes previous "figural continuity" proposals and can be checked by simple, local operations. The filter seems to improve the algorithm's ability to select the correct match from many alternatives and it suppresses intermediate values near sharp changes in disparity. This technique can be extended to other matching tasks, such as motion tracking, analyzing texture periodicity, and evaluating the performance of edge finders.