Combining Stereo and Monocular Information to Compute Dense Depth Maps that Preserve Depth Discontinuities

1 Introduction

Over the years numerous algorithms for passive stereo have been proposed, they can roughlf be classified in two main categories [Barnard et al. 82J :

1. Feature Based. Those algorithms extract features of interest from the images, such as edge segments or contours, and match them in two or more views.

*This research was supported in part under the Centre National d'Etudes Spatiales VAP contract and in part under a Defense Advanced Research Projects Agency contract.

These methods are fast because only a small sub­ set of the image pixels are used, but may fail if the chosen primitives cannot be reliably found in the images; furthermore they usually only yield very sparse depth maps .

1. Area Based. In these approaches, the system at­ tempts to correlate the grey levels of image patches in the views being considered, assuming that they present some similarity. The resulting depth map can then be interpolated. The underlying assump­ tion appears to be a valid one for relatively tex­ tured areas; however if may prove wrong at occlu­ sion boundaries and within featureless regions.

Alternatively the map can be computed by directly fitting a smooth surface that accounts for the dispar­ ities between the two images. This is a more prin­ cipled approach since the problem can be phrased as an optimization one; however the smoothness as­ sumptions that are required may not always be sat­ isfied.

All these techniques have their strengths and weak­ nesses and it is difficult to assess their compared merits since few researchers work on similar data sets. How­ ever, one can get a feel for the relative performances of these systems from the study by Giielch [Guelch 88] . In this work, the author has assembled a standardized data set and sent it to 15 research institutes across the world. It appears that the correlation based system de­ veloped at SRI by Hannah [Hannah 88] has produced the best results both in terms of precision and . reliabil­ ity. Unfortunately this system only matches a very small proportion, typically less than 1%, of the image points.

In this paper we propose a correlation algorithm that reliably produces far denser maps with very few false matches and can therefore be effectively interpolated. In the next section we describe our hypothesis generation mechanism that attempts to match every point in the image and uses a consistency criterion to reject invalid matches . This criterion is designed so that when the correlation fails, instead of yielding an incorrect answer, the algorithm returns NO answer. As a result, the density of the computed disparity map is a very good measure of its reliability. The interpolation technique described in the section that follows combines the depth map produced by correlation and the grey level information present in the image itself to introduce depth discontinuities and fit a piecewise smooth surface. These algorithms have proven very effective on real data. Their parallel im­ plementation on a Connection Machinetm 1 relies only on local operations and on nearest neighbor communica­ tion; they could be ported to a dedicated architecture, thereby making fast and cheap systems possible.

2 Correlation

Most correlation based algorithms attempt to find inter­ est points on which to perform the correlation. While this approach is justified when only limited computing resources are available, with modern hardware architec­ tures and massively parallel computers it becomes possi­ ble to perform the correlation over the whole image and retain only results that appear to be "valid." The hard problem is then to provide an effective definition of what we call validity and we will propose one below.

In our approach, we compute correlation scores for ev­ ery point in the image by taking a fixed window in the first image and a shifting window in the second. The second window is moved in the second image by integer increments along the epipolar line and an array of corre­ lation scores is generated. In this work we use correlation of grey level values and take the correlation score to be s = max(O, 1- c) where

/ 1 and / 2 being the left and right image intensities, X the average value of X over the correlation window and dx, dy the displacement along the epipolar line. 2 The measured disparity can then be taken to be the one that provides the highest value of s. In fact, to compute the disparity with subpixel accuracy, we fit a second degree curve to the correlation scores in the neighborhood of the maximum and compute the optimal disparity by in­ terpolation.

2.1 Validity of the Disparity Measure

As shown by Nishihara [Nishihara et al. 83], the prob­ ability of a mismatch goes down as the size of the corre­ lation window and the amount of texture increase. How­ ever, using large windows leads to a loss of accuracy and the possible loss of important image features . For smaller windows, the simplest definition of validity would call for a threshold on the correlation score; unfortunately such a threshold would be rather arbitrary and, in practice, hard to choose. Another approach is to build a corre­ lation surface by computing disparity scores for a point in the neighborhood of a prospective match and check­ ing that the surface is peaked enough [Anandan 89]. It is more robust but also involves a set of relatively ar­ bitrary thresholds. Here we propose a definition of a valid disparity measure in which the two images play a symmetric role and that allows us to reliably use small windows. We perform the correlation twice by reversing the roles of the two images and consider as valid only those matches for which we measure the same depth at corresponding points when matching from /1 into /2 and h into It . As shown in Figure 1, this can be defined as follows.

1 TMC Inc.

2 We remove the mean to offset transformations of the im­ ages that may result from slightly different settings of the cameras.

Given a point P1 in It, let P2 be the point of / 2 located on the epipolar line corresponding to P1 such that the windows centered on P1 and P2 yield the optimal correlation measure. The match is valid if and only if P1 is also the point that maximizes the score when correlating the window centered on P2 with windows that shift along the epipolar line of 11 corresponding to P2 .

For example, the validity test is likely to fail in pres­ ence of an occlusion. Let us assume that a portion of a scene is visible in / 1 but not /2. The pixels in /1 cor­ responding to the occluded area in /2 will be matched, more or less at random, to points of / 2 that correspond to different points of 11 and are likely to be matched with them. The matches for the occluded points will there­ fore be declared invalid and rejected. We illustrate this behaviour using the portion of the tree scene of Figure 2 outlined in Figure 2(a). Different parts of the ground between the two trees and between the trees and the stump are occluded in Figures 2 (b) and (c). In Figures 3 (a) and (b), we show the computed disparities for this image window after correlation with the images shown in Fig­ ures 2(b) and 2(c) respectively. The points for which no valid match can be found appear in white and the areas where their density becomes very high correspond very closely to the occluded areas for both pairs of images. These results have been obtained using 3x3 correlation windows; these small windows are sufficient in this case because the scene is very textured and gives our validity test enough discriminating power to avoid errors.

We use the face shown in Figure 4 to demonstrate an­ other case in which the validity test rejects false matches. The epipolar lines are horizontal and in Figure 4(d) we show the resulting disparity image, using 7x7 windows, in which the invalid matches appear in black. In Figure 4(e) we show another disparity image computed after having shifted one of the images vertically by two pixels, thereby degrading the calibration and the correlation. Note that the disparity map becomes much sparser but that no gross errors are introduced. In practice, we take advantage of this behaviour for poorly calibrated images: we compute several disparity maps by shifting one of the images up or down and retaining the same epipolar lines, 3 thereby replacing the line by a band, and retain the highest scoring valid matches. 4

In the two examples described above, we have shown that when the correlation between the two images of a stereo pair is degraded our algorithm tends, instead of making mistakes, to yield sparse maps. Generally speaking, correlation based algorithms rely on the fact that the same texture can be found at corresponding points in the two images of a stereo pair and are known to fail when:

3 assumed not to be exa.ctly vertica.l

4 The precision of the computed distance is then obviously degra.ded, but rema.ins qua.lita.tively correct for la.rge enough baselines.

• The areas to be correlated have little texture.
• The disparities vary rapidly within the correlation window.
• There is an occlusion.

If we consider the local image texture as a signal to be found in both images, we can model these problems as noise that corrupts the signal. In a companion report [Fua 91], we use synthetic data to formalize this argu­ ment and show that as the noise to signal ratio increases, or equivalently, as the problems mentioned above be­ come more acute, the performance of our correlation al­ gorithm degrades gracefully in the following sense:

As the signal is being degraded, the density of matches decreases accordingly but the ratio of correct to false matches remains high until this proportion has dropped very low.

In other words, a relatively dense disparity map is a guar­ antee that the matches are correc.t, at least up to the pre­ cision allowed by the resolution being used. In the report [Fua 91], we also show the effectiveness of a very simple heuristic: if we reject not only invalid matches but also isolated valid matches we can increase even more the ratio correct/incorrect matches without losing a large number of the correct answers.

Other stereo systems include a validity criterion sim­ ilar to ours but use it as only one among many others. In our case, because we correlate over the whole image and not only at interest or contour points, we do not need the other criteria and can rely on density alone. However, our validity test depends on the fact that it is

(a)

(b)

improbable to make the same mistake twice when cor­ relating in both directions and can potentially be fooled by repetitive patterns, which is a problem we have not addressed yet.

2.2 Hierarchical Approach and Additional Images

To increase the density of our potentially sparse dispar­ ity map, we use windows of a fixed size to perform the matching at several levels of resolution, 5 which is al­ most equivalent to matching at one level of resolution with windows of different sizes as suggested by Kanade [Kanade et al. 90] but computationally more efficient. More precisely, as shown by Burt [Burt et al. 82], it amounts to performing the correlation using several fre­ quency bands of the image signal.

We then merge the disparity maps by selecting, for ev­ ery pixel, the highest level of resolution for which a valid disparity has been found. In Figure 4 (c) we show the merger of the disparity maps for two levels of resolution that is dense and exhibits more of the fine details of the face than the map of figure 4 (e) computed using only the coarsest level of resolution. The reliability of our validity test allows us to deal very simply with several resolutions without having to introduce, as in [Kanade et al. 90] for example, a correction factor accounting for the fact that correlation scores for large windows tend to be inferior to those for small windows.

The computation proceeds independently at all lev­ els of resolution and this is a departure from traditional hierarchical implementations that make use of the re­ sults generated at low resolution to guide the search at higher resolutions. While this is a good method to reduce computation time, it assumes that the results generated at low resolution are more reliable, if less precise, than those generated at high resolution; this is a questionable assumption especially in the presence of occlusions. For example in the case of the trees of Figure 2, it could lead to a computed distance for the area between the trunks that would be approximately the same as that of the trunks themselves, which would be wrong. Further­ more, it can be shown [Fua 91] that, in the absence of repetitive patterns, the output of our algorithm is not appreciably degraded by using the large disparity ranges that our approach requires.

5 Computed by subsampling gaussian smoothed images.

As suggested by several researchers, more than two im­ ages can and should be used whenever practical. When dealing with three images or more , we take the first one to be our reference frame, compute disparity maps for all pairs formed by this image and one of the others and merge these maps in the same way as those computed at different levels of resolution. In this way we can gen­ erate a dense disparity map, such as the one of Figure 3 (c): the three images of Figure 2 belong to a series of five taken by an horizontally moving camera. Taking the image of 2(a) as our reference frame, we merge the four resulting disparity maps, each of them relatively sparse, to produce a dense map with few errors .

In this section we have presented an hypothesis gener­ ation mechanism that produces depth maps that are cor­ rect where they are dense and unreliable only where they become very sparse. Typically these sparse measure­ ments occur in featureless areas that are usually smooth and at occlusion boundaries where one expects to find an image intensity edge. To fit a surface, one must therefore interpolate those measures in such a way as to propa­ gate the depth information in the featureless areas and preserve depth discontinuities. In the next section, we describe the model and algorithm we use to perform the interpolation.

3 Interpolation

We model the world as made of smooth surfaces sep­ arated by depth discontinuities. We also assume that these depth discontinuities produce gradients in grey level intensities due to changes in orientation and sur­ face material. We first describe a simple interpolation model that is well suited to images with sharp contrasts and then propose a refinement of that scheme for lower contrast scenes.

3.1 Simple Interpolation Model

Ideally, if we could measure with absolute reliability the depth, wO, at a number of locations in the image, we could compute a depth image w by minimizing the following criterion:

s = 1 if wO has been measured, 0 otherwise.

0 if horizontal discontinuity, Cx otherwise.

0 if vertical discontinuity, cy otherwise.

where Cx and cy are two real numbers that control the amount of smoothing.

As discussed in the previous section, when a valid dis­ parity can be found it is reliable and can be used, along with the camera models, to estimate wO; we then take s to be the normalized correlation score of Equation 1. As­ suming that changes in reflectance can be found at depth discontinuities, we replace the Ax and Ay of Equation 2, by terms that are inversely proportional to the image gradients in the x and y directions. In fact, we have ob­ served that the absolute magnitudes of the gradients are not as relevant to our analysis as their local relative mag­ nitudes: boundaries can be adequately characterized as the locus of the strongest local gradients, independent of the actual value of these gradients. We therefore write:

where FNorm is the piecewise linear function defined by:

and zo and z1 are twb constants. In all our examples, z0 is the median value of z in the image and z1 its max­ imum value. The result is quite insensitive to the value chosen for z0 as long as it does not become so large as to force the algorith~ to ignore all edges. What really matters is the monotonicity of FNorm that allows the depth information to propagate faster in the directions of least image gradient and gives to the algorithm a be­ haviour somewhat similar to that of adaptative diffusion schemes (e.g [Perona et al. 87]).

To compute W, the vector of all values of w, we dis­ cretize the quadratic criterion C of Equation 2; we then solve, using a conjugate gradient method [Szeliski 90; Terzopoulos 86], the linear equation

In Figure 3.1, we show the depth map computed by in­ terpolating the disparity map of Figure 4(c). Note that the main features of the face, nose, eyebrows and mouth have been correctly recovered.

This simple interpolation technique is appropriate for the face of Figure 4 that presents few low-contrast depth discontinuities but produces a somewhat blurry result for the tree scene of Figure 2, as can be seen in Figure 6(a). To improve upon this situation, we propose a slightly more elaborate interpolation scheme that takes depth discontinuities explicitly into account.

3.2 Introducing Depth Discontinuities

The A.: and Ay coefficients defined by Equation 3 in­ troduce "soft" discontinuities: when the contrast is low, some smoothing occurs across the discontinuity. The depth image, however, is less smoothed than in the com­ plete absence of an edge resulting in a strong w gradient . We take advantage of this property of our "adaptative" smoothing by defining the following iterative scheme:

1. Interpolate using the Ax and Ay defined above.
2. Iterate the following procedure:
3. (a) Recompute Ax and Ay as functions of both the intensity gradient and the depth gradient of the

interpolated image:

where a is a constant equal to 2 in our exam­ ples.

• (b) Interpolate again the raw disparity map using the new Ax and Ay coefficients.

The algorithm converges after a few iterations resulting in a much sharper depth map such as the one of Figure 6(b ). This algorithm can be regarded as a continuation method on the depth discontinuities. We start without knowing their location, use the grey level information to hypothesize them and then propagate the results.

4 Conclusion

In this work we have described a correlation based algo­ rithm that combines two simple and parallel techniques to yield reliable depth maps in the presence of depth discontinuities, occlusions and featureless areas:

• The correlation is performed twice over the two images by reversing their roles and only matches that are consistent in both directions are retained, thereby guaranteeing a very low error rate.
• The disparity map is then interpolated using a tech­ nique that takes advantage of the grey level infor­ mation present in the image to preserves depth dis­ continuities and propagate the information across featureless areas.

The depth maps that we compute are qualitatively cor­ rect and the density of acceptable matches provides us with an excellent estimate of their reliability. Because of the great regularity and simplicity of the techniques described here, 6 we hope to be able to build dedicated hardware that would implement them and could, for ex­ ample, be used by a mobile robot in an outdoor environ­ ment.