next up previous contents
Next: Multi-view stereo Up: Stereo matching Previous: Exploiting scene constraints   Contents


Constrained matching

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 ${\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.16.

Figure 7.16: Cross-correlation for two corresponding epipolar lines (light means high cross-correlation). A dynamic programming approach is used to estimate the optimal path.
\begin{figure}\centerline{\psfig{figure=stereo/kastcorr2.ps,width=14cm,height=14cm}}\end{figure}

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 $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[73]. 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.


next up previous contents
Next: Multi-view stereo Up: Stereo matching Previous: Exploiting scene constraints   Contents
Marc Pollefeys 2002-11-22