For dense correspondence matching a disparity estimator based on the dynamic programming scheme of Cox et al. [16], is employed that incorporates the above mentioned constraints. It operates on rectified image pairs where the epipolar lines coincide with image scan lines. The matcher searches at each pixel in image for maximum normalized cross correlation in by shifting a small measurement window (kernel size 5x5 or 7x7) along the corresponding scan line. The selected search step size (usually 1 pixel) determines the search resolution and the minimum and maximum disparity values determine the search region. This is illustrated in Figure 7.16.
Matching ambiguities are resolved by exploiting the ordering constraint in the dynamic programming approach [69]. The algorithm was further adapted to employ extended neighborhood relationships and a pyramidal estimation scheme to reliably deal with very large disparity ranges of over 50% of the image size [26]. The estimate is stored in a disparity map with one of the following values:
- a valid correspondence ,
- an undetected search failure which leads to an outlier,
- a detected search failure with no correspondence.
A confidence value is kept together with the correspondence that tells if a correspondence is valid and how good it is. The confidence is derived from the local image variance and the maximum cross correlation[73]. To further reduce measurement outliers the uniqueness constraint is employed by estimating correspondences bidirectionally . Only the consistent correspondences with
are kept as valid correspondences.