Constrained matching

For dense correspondence matching a disparity estimator based on the dynamic programming scheme of Cox et al. [26], 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 ${\bf I^l_k}$ for maximum normalized cross correlation in ${\bf I^k_l}$ by shifting a small measurement window (kernel size 5x5 or 7x7) along the corresponding scan line. The selected search step size $\Delta D$ (usually 1 pixel) determines the search resolution and the minimum and maximum disparity values determine the search region. This is illustrated in Figure 7.3.

Figure 7.3: Cross-correlation for two corresponding epipolar lines (light means high cross-correlation). A dynamic programming approach is used to estimate the optimal path.

Matching ambiguities are resolved by exploiting the ordering constraint in the dynamic programming approach [86]. 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 [39]. The estimate is stored in a disparity map $D_{(k,l)}$ with one of the following values:

- a valid correspondence ${\tt m}^k_l = D_{(k,l)}[{\tt m}^l_k]$,

- 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[90]. To further reduce measurement outliers the uniqueness constraint is employed by estimating correspondences bidirectionally $D(k \rightarrow l), D(l \rightarrow k)$. Only the consistent correspondences with

$\vert D(k \rightarrow l) - D(l \rightarrow k) \vert < \Delta D$ are kept as valid correspondences.