where ~ means satisfying a distribution and kd is a constant. This model indicates that the expectation of the disparity at (u, v) equals the expectation of the disparity at the center of the window (0, 0), but the variance of their disparity difference increases with the increment of the distance from (u, v) to (0, 0).

Suppose further that the first-order partial differential of the image intensity at (u, v) in fL(x, y) satisfies the following statistical model

$\frac{\partial }{{}_{du}}{f}_L\left(u,v\right)~N\left(0,k_{\text{f}}\right)\left(2.52\right)$

where kf is a constant that denotes the fluctuant of the image intensity along a local direction (see below). This model indicates that the expectation of the image intensity at (u, v) equals the expectation of the image intensity at (0, 0). The uncertainty of this assumption increases with the increment of the distance between (u, v) and (0, 0).

According to the above two statistical models and the assumption that the first-order partial differentials on the image intensity and disparity are statistically independent, it can be proven that the statistical distribution of the image intensity difference between the pair of stereo images is

$n_S\left(u,v\right)=f_{\text{R}}\left(u,v\right)-f_{\text{L}}\left[u+d_{\text{r}}\left(0,0\right),v\right]\left(2.53\right)$

It can be considered as a distribution of the Gaussian noise, Kanade (1991)

$n_S\left(u,v\right)~N\left(0,2{\sigma }_n^2+k_{\text{f}}{k}_d\sqrt{u^2+v^2}\right)\left(2.54\right)$

where

$k_{\text{f}}=E\left\{{\left[\frac{\partial }{\partial u}{f}_{\text{L}}\left[u+d_{\text{r}}\left(0,0\right),v\right]\right]}^2\right\}\left(2.55\right)$

From eq. (2.54), it can be seen that the fluctuation of the first-order partial differential of fL(x, y) and the disparity dr(u, v) in the matching windows form a combined noise ns(u, v) with the image noise nL(u, v). This combined noise satisfies a zero-mean Gaussian distribution. Its variance consists of two parts: One is a constant $2{\sigma }_n^2,$ coming from the image noise; the other is a variable proportional to $\sqrt{u^2+v^2},$ coming from the local uncertainty in the matching windows. Such an uncertainty can be described by an additional noise whose energy is proportional to the distance between the center pixel and the surrounding pixels. When the disparity in the window is a constant (kd = 0), this additional noise is zero. The stronger the fluctuation in the matching window, the more uncertainty of the contribution of the surrounding pixels.

Suppose that d0(x, y) is an initial estimation of the correct disparity dr(x, y). Expending fL(u + dr(0,0), v)at u + d0(x, y) gives

$f_L\left[u+d_{\text{r}}\left(0,0\right),v\right]=f_{\text{L}}\left[u+d_0\left(0,0\right),v\right]+\Delta d\frac{\partial }{\partial u}{f}_{\text{L}}\left[u+d_0\left(0,0\right),v\right]\left(2.56\right)$

Taking eq. (2.56) into eq. (2.53) yields

$n_{\text{S}}\left(u,v\right)=f_{\text{R}}\left(u,v\right)-f_{\text{L}}\left[u+d_0\left(0,0\right),v\right]-\Delta d\frac{\partial }{\partial u}{f}_{\text{L}}\left[u+d_0\left(0,0\right),v\right]\left(2.57\right)$

where Δd = dr(0, 0) – d0(0,0) is the amended value for the disparity, which needs to be estimated. It can be proven that the conditional probability density of Δd satisfies the Gaussian distribution, so it can be computed in the following steps.

(1)Obtain an initial disparity value first by using any pixel level stereo-matching algorithm.

(2)For each pixel, where the subpixel level disparity is to be estimated, select the window for the disparity estimation with the minimum uncertainty and compute the amended value for the disparity.

(3)Stop the computation of the amended value for the disparity when it converges or attains a pre-defined iteration number.

Such a procedure for computing the subpixel-level disparity can also be used for multiple imaging or orthogonal trinocular vision cases.

Example 2.7 Illustration of the subpixel-level disparity.

One illustration showing the results of subpixel-level disparity is given in Figure 2.20. Figure 2.20(a–c) represents the left, right, and top images of an orthogonal trinocular system for a square pyramid. To facilitate the matching, a layer of texture is covered on its surface. Figure 2.20(d) is the pixel-level disparity map obtained with the orthogonal trinocular matching, Figure 2.20(e) is the subpixel-level disparity map obtained with the binocular matching. Figure 2.20(f) is the subpixel-level disparity map obtained with the orthogonal trinocular matching. Figure 2.20(g–i) are the 3-D plots of Figure 2.20(d–f), respectively.

Both the subpixel-level disparity maps obtained with the binocular and orthogonal trinocular matching have higher precision than that of the pixel-level disparity map obtained with orthogonal trinocular matching. By comparing Figure 2.20(e, f), it can be seen that the binocular matching with the subpixel-level disparity produces some mismatching along the diagonal direction, while the trinocular matching with subpixel-level disparity has no such problem.

Example 2.8 Disparity computation and volume measurement.

Suppose that the side length of the square is 2.4 m and the height of the pyramid is 1.2 m. The results of the volume computation with the disparity maps obtained by using the above three matching methods are listed in Table 2.1, Jia (2000c). The influence of the precision for the disparity computation on the precision of measurement is evident.

Example 2.9 Real computational examples of subpixel-level disparity.

The original images used for the computation in Figure 2.21 are those shown in Figure 2.3(a, b) and Figure 2.16(a). Figure 2.21(a) is the pixel-level disparity map obtained with the orthogonal trinocular matching algorithm. Figure 2.21(b) is the subpixel-level disparity map obtained with the binocular matching algorithm. Figure 2.21(c) is the subpixel-level disparity map obtained with the orthogonal trinocular matching algorithm.

2.7Error Detection and Correction

There are a number of error sources in the computation of disparity maps, such as the existence of periodic patterns or smooth regions, various occlusions, different constraints and so on. In the following, a general and fast error detection and correction algorithm for the disparity map is introduced, Jia (2000b). It can directly process disparity maps, independent of any matching algorithm. Its computational complexity is just proportional to the number of mismatching pixels.

2.7.1Error Detection

According to the ordering constraint discussed in Section 2.3, the concept of the ordering match constraint can be introduced. Suppose that fL(x, y) and fR(x, y) are a pair of images, and OL and OR are their imaging centers, respectively. As shown in Figure 2.22, P and Q are two nonoverlapping points in the space, PL and QL are the respective projections of P and Q on fL(x, y), and PR and QR are the respective projections of P and Q on fR(x, y).

Denoting the X coordinate X(•), it can be seen from Figure 2.22 that in correct matching there are X(PL) ≤ X(QL) and X(PR) ≤ X(QR) when X(P) < X(Q), or X(QL) ≤ X(PL) and X(Qr) ≤ X(PR) when X(P) > X(Q). Denoting $\Rightarrow$ as implying, the following conditions are satisfied

$\begin{array}{l}X\left(P_L\right)\le X\left(Q_L\right)\Rightarrow X\left(P_R\right)<X\left(Q_R\right)\left(2.58\right)\\ X\left(P_L\right)\le X\left(Q_L\right)\Rightarrow X\left(P_R\right)>X\left(Q_R\right)\end{array}$

It is said that PR and QR satisfy the ordering match constraint, otherwise they are crossing.

Using the ordering match constraints, crossing match regions can be detected. Let PR = fR(i, j) and QR = fR(k, j) be two pixels in the jth line of fR(x, y), and their matching points in fL(x, y) can be denoted PL = fL(i + d(i, j), j) and QL = fL(k + d(k, j), j), respectively. Let C(PR, QR) be the cross label between PR and QR. If eq. (2.58) holds, C(PR, QR) = 0; otherwise, C(PR, QR) = 1. The cross number Nc corresponding to a pixel PR is defined as

$N_c\left(i,j\right)={\displaystyle \sum _{k=0}^{N-1}C\left(P_R,Q_R\right)}k\cancel{=}i\left(2.59\right)$

where N is the number of pixels in the jth line.

2.7.2Error Correction

Calling the regions with nonzero cross numbers as cross-regions, the mismatching error in the cross-regions can be corrected by the following algorithm. Suppose that {fR(i, j)|i ⊆ [p, q]} is the cross-region corresponding to PR, and the total cross number in the cross-region, Ntc, is

$N_{\text{tc}}\left(i,j\right)={\displaystyle \sum _{i=p}^q{N}_c\left(i,j\right)}\left(2.60\right)$

The procedure for correcting mismatching points in cross-regions has the following steps:

(1)Find the pixel fR(l, j) with the maximum cross number. Here,

$l=\underset{i\subseteq \left[p,q\right]}{\max }\left[N_c\left(i,j\right)\right]\left(2.61\right)$

(2)Determine the search range {fL(i, j)|i ⊆ [s, t]} for the matching point fR(k, j), where

$\{\begin{array}{l}s=p-1+d\left(p-1,j\right)\\ t=q+1+d\left(q+1,j\right)\left(2.62\right)\end{array}$

(3)Search a new matching point that can reduce the total cross number Ntc in the above range.

(4)Use the new matching point to correct d(k, j), eliminating the mismatching corresponding to the pixel with the currently maximum cross number.

The above procedure can be iterated. Once a mismatching pixel is corrected, the procedure can be applied to the rest of the mismatching pixels. After correcting d(k, j), the new Nc(i, j) in the cross-region can be calculated by using eq. (2.59), and a new Ntc can be obtained. The procedure will be repeated until Ntc = 0. Since the criterion used in this algorithm is to make Ntc = 0, this algorithm is called the zero-cross correction algorithm.

Example 2.10 Matching error detection and removing.

Suppose that the computed disparity values for region [153,163] in the jth line of the image are listed in Table 2.2. The distribution of the match points before correction is shown in Figure 2.23. According to the corresponding relation between fL(x, y) and fR(x, y), it is known that the points in [160, 162] are the mismatching points. Following eq. (2.23), Table 2.3 gives the computed cross numbers.

According to Table 2.3, [fR(154, j), fR(162, j)] is a cross-region. Following eq. (2.60), Ntc = 28 can be determined. Following eq. (2.61), the pixel with the maximum cross number is fR(160, j). Following eq. (2.62), the search range for the new matching point fR(160, j) is fL(i, j)|i ⊆ [181, 190]}. Searching new matching points that correspond to fR(160, j) and that can reduce Ntc gives fL(187, j) in this range. Adjust the disparityvalue d(160, j) corresponding to fR(160, j) to a newvalue d(160, j) = X[fL(187, j)]–X[fR(160, j)] = 27. The above procedure can be repeated until Ntc = 0 for the whole region. The distribution of the match points after the correction is shown in Figure 2.24, in which all mismatching in the region [160,162] has been removed.

Example 2.11 Real error detection and removing.

One real example of error detection and removing is shown in Figure 2.25. The stereomatching images used are Figure 2.3(a, b). Only part of the images are shown here as Figure 2.25(a). Figure 2.25(b) is the disparity map obtained with stereo matching. Figure 2.25(c) is the result after further correction. Comparing Figure 2.25(b) and (c), it is easy to see that many mismatching points (black and white points in gray background) in the original disparity map have been removed.

Such a procedure for correcting errors in the disparity map is also applicable for the cases of multiple imaging or orthogonal trinocular vision.

2.8Problems and Questions

2-1*In Figure 2.11 of Volume I, suppose that λ = 0.05 m and B = 0.4 m. Obtain the disparity values for two cases: the point W is at (1, 0, 2 m) and at (2, 0, 3 m). If the disparity is 0.02 m, what is the corresponding Z?

2-3Show that the correlation coefficient of eq. (2.4) has values in the interval (–1,1).

2-4Give some real examples for point features, line features and blob features. Discuss their functions in stereo matching.

2-5Compare the two feature point-matching methods in Section 2.3. What are their differences in computation time and robustness?

2-6Prove eq. (2.12) by coordinate transforms.

2-7When using the method of horizontal multiple stereo matching, what would be the advantage of making different baselines in an integer proportion?

2-8In Example 2.2, in addition to baselines B1 and B2, add a third baseline B3. Suppose that B3 = 2B1. Draw the curves $E[S_{t3}(x;t)]\text{and}E[S_{t(123)}^{(S)}(x;t)].$

2-9*In Figure Problem 2-9, Bh = Bv. If a more accurate measurement for the depth of the point P is required, which pair of images, the left image L and the right image R or the left image L and top image T, should be used?

Figure Problem 2-9

2-10Consider Figure 2.12. Compare the changes produced by moving the camera in the XY plane and along the Z-axis. In what circumstances would moving the camera in the XY plane be more suitable for obtaining an accurate distance measurement?

2-11Compare the accuracy of the disparity obtained by using the following two processes: Use subpixel edge detection to find the boundary of an object and then perform stereo matching, or directly using the subpixel disparity computation.

2-12Implement the algorithm for error detection and correction in Section 2.7, and verify the algorithm with the help of the data in Table 2.2.

2.9Further Reading

1.Modules of Stereo Vision

–The introduction of stereo vision can be found in many computer vision textbooks; for example, Haralick (1992,1993), Jähne (2000), Shapiro (2001) and Forsyth (2003).

–One example of using stereo vision for scene understanding can be found in Franke (2000).

–Using models to improve stereo matching can be found in Maitre (1992).

2.Region-Based Binocular Matching

–Many matching techniques based on regions have been proposed, and a comparison can be found in Scharstein (2002).

–One assumption in correlation-based matching is the parallel between the observed surface and two project planes. When this assumption is not valid, the strategy discussed in Devernay (1994) can be used.

3.Feature-Based Binocular Matching

–Besides the types of feature points mentioned in the text, other features, such as straight lines Medioni (1985), moment Lee (1990) and junction of boundary can be used.

–An O(1) disparity refinement method based on belief aggregation and belief propagation is proposed in Huang (2016).

4.Horizontal Multiple Stereo Matching

–Further discussion on multiple stereo matching can be found in Kim (2002).

5.Orthogonal Trinocular Matching

–Further discussion on orthogonal trinocular matching with experiments can be found in Forsyth (2003).

–Multiple stereo matching and orthogonal trinocular matching can also be combined, Jia (2000a).

–One multi-view stereo reconstruction work can be found in Zhu (2011a).

6.Computing Subpixel-Level Disparity

–The principle behind the algorithm in Section 2.6 can be found in Okutomi (1993).

–Different discussions on subpixels can be found in Zhang (2001b).

–Other influencing factors on depth estimation can be found in Zhao (1996).

7.Error Detection and Correction

–A comprehensive discussion on matching error detection, correction and evaluation can be found in Mohan (1989).

–The error in the disparity map causes the error in depth estimation. The influence of camera calibration on the depth estimation can be found in Zhao (1996).