Weakly-Calibrated Stereo Perception for Rover Navigation ^{∗}

Luc Robert

INRIA

2004 Route des Lucioles, BP93 06902 Sophia Antipolis Cedex

France.

Michel Buffa and Martial Hebert

The Robotics Institute Carnegie Mellon University

5000 Forbes Avenue Pittsburgh PA 15213

Abstract

In this paper we present a vision system for autonomous navigation based on stereo perception without 3-D reconstruction. This approach uses weakly calibrated stereo images, i.e., images for which only the epipolar geometry is known. The vision system first rectifies the images, matches selected points between the two images, and then computes the relative elevation of the point relative to a reference plane as well as the images of their projections on this plane. We have integrated this vision module into a complete navigation system. In this system, the relative elevation is used as a shape indicator in order to compute appropriate steering directions everytime a new stereo pair is processed. We have conducted initial experiments in unstructured, outdoor environments with an wheeled rover.

1 Introduction

Conventional stereo systems for navigation use three basic steps. First, matches between pixels in the left and right images are computed. Second, the matches are converted to points in 3-D space. Finally, the 3-D points are arranged into a map which is used for evaluating possible vehicle paths and for selecting the safest path.

This conventional approach has been demonstrated successfully in a limited number of systems [Matthies, 1992; Ross, 1993]. However, this approach suffers from several limitations that compromise its use in full-fledged navigation systems. In particular, one major limitation is the need for precise camera calibration.

We set out to develop an alternative more general and robust approach by eliminating the conversion to Cartesian coordinates and the construction of a dense elevation map. More precisely, our approach is to initially compute some of the parameters of the stereo system by matching natural features in the environment: First, the epipolar geometry of the cameras is used for computing rectification transformations. Applied at run-time on the pairs of images, these transformations generate new pairs of images in which the epipolar lines are horizontal. This allows fast stereo matching between the images. Then, based on some simple additional geometric information, we compute the relative elevations of the observed matched points. Once these image measurements have been performed, an optimal vehicle path is selected based on a comparison of the image projections of the candidate paths with the distribution of elevation values.

This article is organized as follows: In Section 2, we give the notations and describe the basic geometric properties that are used in the paper. In Section 3, we describe our method for rectifying the images. In Section 4, we show how we perform fast and reliable stereo matching in rectified images. In Section 5, we describe our approach to computing relative elevations from stereo matches and briefly mention how elevations are used for trajectory evaluation.

2 Background

In this section we briefly describe the geometry of the stereo system and the notations that we use throughout the paper.

2.1 The camera model

We assume that the cameras follow the standard pinhole projective model. The 2-D location of a pixel [u, v]^{t} is denoted by the three-vector of its homogeneous coordinates m = λ[u, v, 1]^{t} (λ ≠ 0). Similarly, a space point [x, y, z]^{t} is represented by a four-component vector up to a scale factor: M = μ[x_{w}, y_{w}, z_{w}, 1]^{t} (μ ≠ 0). The projection representations are described in detail in [Mundy and Zisserman, 1992] and [Faugeras, 1993].

The projection m of a point M in one camera is obtained by applying a linear projective transformation: m = P M (By applying the usual “=” sign to homogeneous vectors, we mean that the vectors are equal up to a scale factor).

This projection model includes other simpler camera models (e.g., affine, orthographic). Unlike these models, however, it deals with perspective distortions, and behaves uniformly across ranges.

∗This research is supported in part by NASA under Grant NAGW-1175 and by ARPA under contracts DACA76-89-C-0014 and DAAE07-90-C-R059. Luc Robert and Michel Buffa were supported by INRIA post-doctoral fellowships.

In the rest of the paper, we assume weak calibration of the cameras, that is, only the epipolar geometry of the system is known. In this case, the geometry of the system is represented by the fundamental matrix F [Faugeras et al., 1992] such that any two pixels m_{l}, m_{r} are images of a single point if and only if

m_{r}^{T} F m_{l} = 0

This matrix can be derived by matching features between the two images without the use of an external calibration target [Faugeras, 1992; Faugeras, 1993] Recent work presented in [Zhang et al., 1994] allows performing this computation in a very robust manner.

Finally, we denote the epipoles by e_{l} and e_{r}.

2.2 Image properties of planes Let us consider a flat ground plane observed by two cameras. Let M be a generic point on the plane and m_{l} and m_{r} be its projections in the left and right images represented by 2-D projective coordinates, i.e., three-vectors up to a scale factor. It can be easily shown that for any point M, the projections are related by a linear projective transformation, or homography, H: m_{r} = Hm_{l}. In this relation, the symbol = means that the two sides are equal in the projective sense, i.e., that their coordinates are proportional. Intuitively, as shown in Figure 4(a), H maps a pixel from the left image to its location in the right image assuming that the corresponding 3-D scene point lies on the plane.

This transformation H can be represented by a 3×3 matrix that we also denote by H. This matrix is defined up to a scale factor, so it has 9 − 1 = 8 degrees of freedom. Thus, a set of four point correspondences in general position (i.e., no three of which are aligned) is sufficient for computing H. Three point correspondences are sufficient for determining H if the F matrix is known [Shashua, 1993; Robert and Faugeras, 1993].

3 Rectification

Many conventional systems are limited in that, in order to facilitate the initial search for matches between left and right images, their cameras either need to be aligned manually so that the epipolar lines are the scanlines of the images, or they need to be precisely calibrated with respect to a common external calibration target in order to compute rectification transformations which bring the images into a standard configuration, irrespective of the physical configuration of the cameras [Ayache and Hansen, 1988]. Recently, it has been shown that rectification can be performed with weakly-calibrated cameras [Hartley and Gupta, 1993; Zeller and Faugeras, 1994]. In this section we describe a technique which explicitly searches over the whole parameter space for the rectification parameters that minimize distortion in both rectified images.

3.1 Rectification transformations The purpose of rectifying images is to generate new images in which epipolar lines are parallel to a given direction (in general horizontal or vertical). The rectification consists of finding two homographies H_{l}, H_{r} which map the two images onto the same virtual image plane. A frame is chosen in this plane so that the epipole of the first image is mapped onto point [1, 0, 0]^{T}, i.e., the epipole of the rectified epipolar lines. From Figure 1, we can see that the homography H induced by the rectification plane from the left image to the right image is such that

H_{r}H = H_{l}

We note that the projections of points lying on the rectification plane in rectified images have zero disparity.

H_{l}  H  H_{r}

Figure 1: Points in left (resp. right) image are mapped onto the rectification plane by homography H_{l} (resp. H_{r}). H induced by the plane is such that H_{r}H = H_{l}.

Let us now assume that the rectification plane is given, i.e., H is known. If H_{l} is given, then H_{r} can be computed. As a consequence, the number of degrees of freedom on the pairs of rectification projections is equal to the total number of degrees of freedom for H and H_{l}. There are 3 degrees of freedom for H because it is defined by a plane in space which is completely characterized by three parameters. There are 6 degrees of freedom for H_{l} because the image of the epipole is constrained to be [1, 0, 0]^{T}. Among these 9 parameters, 4 are related to the origin of the coordinate system in the rectification plane and to the size of the pixels: Once images have been rectified, one can arbitrarily apply a magnification or a translation to both images while keeping the epipolar properties. Let us now show how these parameters are introduced and computed.

For simplicity, we express points of the left images with respect to a normalized coordinate system, in which the image occupies the unit square. Using homogeneous coordinates, we denote by [e_{x}, e_{y}, e_{z}] the coordinates of the left epipole. We now describe a parametrization of H_{l}^{s}, i.e., the inverse of the rectification matrix in the left image, that explicitly introduces the two free rectification parameters. Some additional constraints on H_{l}^{s} allow the elimination of the additional parameters (shift and scaling in the rectified image plane):

1. H_{l}^{s} maps point [1, 0, 0]^{T} onto the epipole. This is the condition for the epipolar lines to be horizontal in the rectified images.

2. We impose that the origin of the rectified image be mapped onto the origin of the left image (This fixes two translation parameters in the rectified image plane). In other words, H_{l}^{s}[0, 0, 1]^{T} = λ[0, 0, 1]^{T}.

3. Since H_{l}^{s} maps horizontal lines onto epipolar lines, we impose that the top-right corner of the image be mapped onto point t_{r} = [e_{x}, −e_{y}, e_{x}] of the left image, intersection of the epipolar line of the left corner with the right edge of the image^{1} (Figure 2). This sets the horizontal scale factor on the rectified image coordinates.

4. We impose that the lower left corner of the rectified image be mapped onto the epipolar line of the lower left corner of the left image. This sets the vertical scale factor of the rectified image coordinates.

From the first three constraints, we infer that the matrix H_{l}^{s} is of the form:

H_{l}^{s} = [ \begin{matrix}e_{x} & ? & 0 \\ e_{y} & ? & 0 \\ e_{z} & ? & e_{x} − e_{z} \end{matrix} ]

From the fourth constraint, we have that H_{l}^{s}[0, 1, 1]^{T} = e_{l} × [0, 1, 1]^{T} up to a scale factor. In other words, H_{l}^{s}[0, 1, 1]^{T} is a linear combination of e_{l} and [0, 1, 1]^{T}, so there exist α, β such that

H_{l}^{s} = [ \begin{matrix}e_{x} & αe_{x} & 0 \\ e_{y} & αe_{x} + β & 0 \\ e_{z} & αe_{z} + β + e_{z} − e_{x} & e_{x} − e_{z} \end{matrix} ]

Assuming that the rectification plane is known (homography H), any choice of α, β defines rectification matrices for the two images.

rectified image  e_{l}  left image

Figure 2: H_{l}^{s} maps corners of the rectified image onto particular points of the left image, and maps point at infinity [1, 0, 0]^{T} onto the epipole e_{l}.

We now show how we choose α, β so as to introduce as little image distortion as possible. Since there is no absolute measure of global distortion for images, the criterion that we use is based on the following observation: vertical edges of the rectified image are orthogonal to epipolar lines. If the rectification transformation induced no deformation, then the images of these edges would in particular remain orthogonal to the direction epi_{l} of the epipolar line passing through the image of a reference point P. Let t, b respectively be the top, bottom points on a vertical line l of the rectified image. For a given value of α, β, we define the residual

R_{l}(l) = (epi_{l}.\underline{H_{l}^{s}(t)H_{l}^{s}(b)})^{2}

which measures the shift between H_{l}^{s}(t) and H_{l}^{s}(b) along the epipolar direction. An analogous residual R_{r} can be defined in the right image, with the rectification transformation H_{r}^{s} = HH_{l}^{s}. To determine rectification transformations, we compute α, β which minimize the sum of R_{l} and R_{r} computed for both the left and the right columns of the images. We end up with a simple linear least-squares problem, which can be solved very efficiently.

The reference point P which defines the epipolar line directions epi_{l}, epi_{r} is chosen arbitrarily, so as to project approximately in the center of the “interesting zones” of both images. This point plays another role: we force the point to belong to the rectification plane. Any potential rectification plane can then be characterized by two other points Q, R (we mentioned above that with weakly-calibrated cameras, a plane can be characterized by three pairs of image points). In order to span the set of planes passing through P, we arbitrarily choose two points q_{l}, r_{l} in the left image, and we sample their epipolar lines in the right image, thus defining a set of potential locations for the corresponding points q_{r}, r_{r}. For each potential pair (q_{r}, r_{r}), we compute the homography of the corresponding rectification plane, and apply the method described above to compute the rectification matrices. The plane which induces the smallest distorsion is retained as the rectification plane.

3.2 Rectifying sequences of images Once the rectification matrices are computed, rectifying an image is a fast process that uses standard image synthesis techniques to apply a projective transformation of the plane to the image. Furthermore, we are dealing with a specific case in which the rectification transformations are computed only once, and have to be applied to a whole sequence of images. Thus, we store the mapping between pixel positions in the original image and the corresponding positions in the rectified image in a look-up table, so that no geometric computation has to be done to generate rectified images. With this method, rectifying a full 480x640 image takes 0.2s on a Sparc-10 workstation.

Figure 3 shows an example of a stereo pair and the corresponding rectified pair.

Figure 3 shows a laboratory image and its rectified version.

4 Computing stereo matches

Stereo matching is performed by means of a standard window-based cross-correlation method. We chose to use normalized correlation as the evaluation criterion for the Figure 3: Original pair (top); Rectified pair (bottom).

1Since cameras are in a horizontal configuration, this intersection point exists. However, the same method can be easily adapted to other cases.

matching because of its high robustness to photometric differences between images.

Once both images are rectified, the best match to a pixel in the left image is found by evaluating a normalized correlation criterion at the pixels in the right image along the corresponding scanline. The search is limited to a pre-set disparity interval [d_{min}, d_{max}].

For more efficiency, the search is first performed at half-resolution in the interval [d_{min}/2, d_{max}/2], using half-resolution image data. The search is then performed at full resolution around the maximum of correlation found at half-resolution. In the current configuration, the horizontal and vertical sizes W of the correlation windows are both 14 pixels when using 480x640 images at full resolution.

The stereo algorithm is implemented as a random access function which takes as input a pixel position (x_{r}, y_{r}) and a disparity interval [d_{min}, d_{max}], and outputs the corresponding disparity. We chose this implementation over the conventional raster scan implementation because we need to compute only a small number of matches compared to the total number of pixels in the image. Furthermore, the anticipated range of disparity [d_{min}, d_{max}] can be adjusted dynamically at each pixel.

It is well known that any stereo matching algorithm is prone to false matches due to lack of texture, repetitive texture, and occlusions. In our case, false matches are of great consequence because they directly impact the behavior of the entire driving system. To reduce instances of false matches, we implemented three levels of mismatch detection. First, pixels at which the variation of intensity in the neighborhood, σ, is insufficient are not matched. This test eliminates points on uniform surfaces such as roads. Second, matches with an insufficient correlation value ρ are not matched. This test eliminates points in occluded parts, for example. A third test finds the local extrema of the correlation curve ρ(d) at each pixel and discards the pixel if there exists a local maximum d_{i} such that ρ_{max} − ρ(d_{i}) < δρ, where ρ_{max} is the global maximum value of correlation.

The current values used in the three tests are: σ_{min} = 2, ρ_{min} = 0.5, and δρ = 0.05.

5 Computing Relative Elevation from Stereo Matches

As previously mentioned, a limitation of the conventional approach to stereo driving is that, in order to convert matches to 3-D points, it relies on precise metric calibration with respect to an external calibration target. From a practical standpoint, this is a serious limitation in scenarios in which the sensing hardware cannot be physically accessed. In particular, this limitation implies that the vision system must remain perfectly calibrated over the course of an entire mission. Nevertheless, navigation should not require the precise knowledge of the 3-D position of points in the scene: What is important is how much a point deviates from the reference ground plane rather than its exact position.

Based on these observations, we developed an approach in which a relative measure of height with respect to a ground plane is computed from the matches without requiring the knowledge of the full set of camera parameters. This height is relative in the sense that it is, up to some approximation that will be detailed further, a multiple of the true height by a unknown scale factor.

The geometry described below has been used in earlier work in which a point is classified as belonging to one of two halfspaces based on its projections in two uncalibrated images [Robert and Faugeras, 1993].

5.1 Characterizing of the ground plane In Section 2.2, we showed that the ground plane induces a homographic correspondence H between the images. H can be easily estimated from real images in the following way. First, n features m_{l}^{i} representing points of the ground plane are selected in the left image and the corresponding pixels m_{r}^{i} in the right image are computed using the algorithm of Section 4, using a constant disparity search interval. Then, the parameters of H are computed by solving for the least-squares criterion: ∑_{i} ∥Hm_{l}^{i} ×m_{r}^{i}∥^{2}. The features used in the computation of H may be anywhere in the image. Moreover, computing H does not require any information on the actual 3-D positions of the scene points used as features.

5.2 Intersecting a line with the ground plane We now show that we need only H to compute a relative elevation map. Consider a world point M and its projections m_{l} and m_{r}. Let us assume that we also have defined once and for all a ”reference” point M^{∗} described by its projections m_{l}^{∗} and m_{r}^{∗}. M^{∗} may be anywhere in space so long as it is not on the reference plane. Of course, the point M^{∗} is not known; only its projections in the images are known. Let us consider now the image points p_{r} = Hm_{l} and p_{r}^{∗} = Hm_{l}^{∗} (Figure 4(a)). Point p_{r} (resp. p_{r}^{∗}) is the point at which M (resp. M^{∗}) would be projected in the right image if it were on the ground plane. Finally, consider the point q_{r}, intersection in the right image of the two segments m_{r}m_{r}^{∗} and p_{r}p_{r}^{∗}. Since m_{r}m_{r}^{∗} is the projection of the segment MM^{∗} and p_{r}p_{r}^{∗} is the projection of a line segment contained in the plane, the intersection point q must be the projection of the intersection of MM^{∗} with the reference plane, as shown in Figure 4(b).

5.3 Computing heights The previous reasoning shows that we now have a way to compute the intersection of the line joining a point and a reference point with a reference plane without computing the 3-D position of the point. Now, let us see how this can be used for computing point elevations.

The distance of a point M to the reference plane is related to the location of M along the direction orthogonal to the plane. Let us consider the line (D) orthogonal to the ground plane and passing through the reference point M^{∗}. Denoting by Q^{∗} the intersection between (D) and the ground plane, the height of M is, in fact, equal to the signed distance Q^{∗}M_{D}, where M_{D} is obtained by projecting M on (D) along the direction of the ground plane.

From simple affine geometric properties, the ratios of signed distances Q^{∗}M_{D}/M^{∗}Q^{∗} and QM/M^{∗}Q are equal. Thus, if we consider an arbitrary point M^{r} which we declare to be at height one from the reference plane, the height of M in relative to this unit can be expressed as h = Q^{∗}M_{D}/Q^{∗}M_{D}^{r} = (QM/M^{∗}Q)/(Q^{r}M^{r}/M^{∗}Q^{r}) as shown in Figure 4(c).

In practice, we cannot directly compute distances between 3D points. However, using the result of the previous paragraph, we can compute their projections on the right image plane. Ratios of distances are affine invariants, so if we assume that the right camera performs affine projection, we can write

h = (q_{r}m_{r}/m_{r}^{∗}q_{r})/(q_{r}m_{r}^{r}/m_{r}^{∗}q_{r}^{r})

Under affine viewing, this definition of height is exact in the sense that h is proportional to the distance between M and the reference plane. Otherwise, this formula is only an approximation. At any rate, it is accurate enough for the purpose of navigation, because the heights are computed at relatively long range from the camera and over a relatively shallow depth of field.

The relative height is also used for limiting the search in the stereo matching. More precisely, we define an interval [h_{min}, h_{max}] of heights which we anticipate in a typical terrain. This interval is converted at each pixel to a disparity range [d_{min}, d_{max}]. This is an effective way of limiting the search to physically meaningful disparities at each pixel.

5.4 Projecting points on the reference plane The algorithms described above give us the tools for computing the intersection of a line with a reference plane and the corresponding relative height. To use these tools in navigation applications, however, we need to compute the projection of the image points onto the reference plane in the direction of the normal to the plane. This is because we need to know the location in the image of projection of the obstacles on the ground the plane in the direction of the vertical.

There are two ways to modify the algorithm of Section 5.2 in order to compute projections. First, we can

M Q Q^{r} M^{r}  Q^{∗} M_{D} M^{∗}  c)  m_{r}^{∗} q_{r} m_{r} mr_{r} qr_{r}

Figure 4: Computation of relative height: (a) Relation between the projections of a point in the reference ground plane in the images; (b) Computing the intersection of a line segment with the ground plane; (c) Computing the height relative to unit point M^{r}.

define the reference point M^{∗} as the point at infinity of a line defining the projection direction. In that case, m_{l}^{∗} and m_{r}^{∗} are the vanishing points of this direction in the left and right image, respectively. The projection of an image point proceeds exactly as in Section 5.2 by using the vanishing points instead of an arbitrary reference point. Second, we can modify the algorithm to compute the intersection with the plane of the line originating at M and parallel to a fixed direction v in the image.

The first approach requires the computation of the vanishing points by selecting four points a pair of images. This needs to be done only once for a given configuration. This first approach is general in that it does not depend on the cameras being in any particular configuration with respect to the ground plane. The second approach requires the selection of a direction in the image defined by two points. This needs also to be done once for a given configuration. This second approach requires less information but it is less general because it assumes implicitly that the vanishing point is at infinity. In many camera configurations for mobile robots, however, this condition is satisfied to a degree that makes the locations of the projections indistiguishable from the projections obtained by using the real vanishing points.

In all the results shown in the remainder of this paper, we use the projections of the points on the ground plane parallel to the vertical direction. For example, Figure 5 and Figure 6 show typical results of computing ground projections in stereo pairs.

Figure 5 shows the points selected on the ground on a pair of training images for the initial computation of the plane homography H. In this case, the points are selected manually at random locations in the left image and the corresponding points are found in the right image using the matching algorithm of Section 4. In addition to the point on the plane, the figure also shows the two points selected for defining the unit height in the tree line on the right side of the image.

Figure 6 shows the projections on the ground plane of a few points selected at random in two stereo pairs. The points, selected in the left image of each pair, are shown as unfilled squares. The corresponding points computed by stereo matching are shown in the right image and their projections on the ground plane are shown as black squares.

We chose the two stereo pairs in order to illustrate the performance of the algorithm in different cases. In the stereo pair shown at the top of Figure 6, a number of points are selected on the road in front of the vehicle to show that the projection algorithm does correctly recover the fact that these points belong to the reference ground plane. At the same time, the points on the obstacles around the road are also correctly projected.

The example displayed at the bottom of Figure 6 shows that the projections are correct both at short range, on the small obstacle in the middle of the image, and at long range, on the tree line in the background.

Figure 5: Set of of points used for computing the ground plane homography and the reference elevation

5.5 Evaluating paths In this section, we briefly describe how the algorithms for computing relative heights and projections can be used for autonomous driving. We give only an overview of the approach since a detailed description of the driving system is outside the scope of this paper. A detailed description of the stereo driving system can be found in [Krotkov et al., 1994]. The autonomous navigation architecture is described in [Langer et al., 1994] and [Hebert et al., 1994].

In autonomous driving, the problem is use the data in the stereo images to compute the best steering command for the vehicle, and to update the steering command every time a new image is taken. Our basic approach is Figure 6: Projections of a few points selected in two stereo pairs

to evaluate a set of possible steering directions based on the relative heights and the projections of a set points in a regular grid in the image. Specifically, a given steering radius corresponds to an arc which can be projected into a curve in the image. This curve traces the trajectory that the vehicle would follow in the image if it used this steering radius. Given the grid and the set of steering radii, we compute a vote for every arc and every point of the grid which reflects how drivable the arc is, given the height and projection values at the grid point.

The vote for a given steering radius is set to -1, i.e., inhibits the arc, if the ground projection of the grid point is close to the projection of the arc in the image and if the grid point has a high elevation value; the vote is set to +1 if the grid point has no effect on the arc, i.e., its projection is far from the projection of the arc in the image or the relative elevation of the grid point is small. For a given steering radius, the votes from all the grid points are aggregated into a single vote by taking the minimum of the votes computed from the individual grid points. The output is, therefore, a distribution of votes between -1 and +1, -1 being inhibitory, for the set of possible steering arcs. This distribution is then sent to an external module which can combine the distribution of votes from stereo with distributions from other modules in order to generate the steering command corresponding to the highest combined vote.

This approach assumes that a transformation is available for projecting the steering arcs onto the image plane. Such a transformation can be computed from features in sequences of images using an approach similar to the estimation algorithm of Section 5.1.

Figures 7 and 8 illustrate our approach. Figure 7 shows the three distributions of votes computed using three points selected in an image. The points are shown in the image as hollow rectangles, and their projections are shown as black rectangles. The projections of the arcs in the image is also shown.

The three vote distributions are shown at the bottom of the figure. In each graph, The horizontal axis is the arc number from 0 to 51, arc 0 being the leftmost turn. Although a total of 51 arcs is used in this case, only the 15 arcs at the center can be evaluated because the arcs on the left and right parts of the graph fall outside of the field of view and their votes are always set to -1. The upper left, upper right, and bottom graphs correspond to the points on the left side, center, and right side of the image.

The vote distributions are interpreted as follows: The distribution for the leftmost point is almost uniformly +1 because the point is very close to the ground plane; the distribution for the center point exhibits a sharp drop at the center because the point is on a tall obstacle at the center-right of the image, causing the corresponding arcs to be inhibited; the vote distribution for the rightmost point also exhibits lower vote values for the arcs going toward the point because it is also on the obstacle, although the arcs are not inhibited as much as for the center point because the relative elevation of the rightmost point is lower.

Figure 8(top) shows a grid of points superimposed on the image and their ground projections. The grid points are shown as small dots; the projected points are shown as black squares. Figure 8(bottom) shows the vote distribution computed by combining the vote distributions computed from all the grid points. The vote distribution exhibits the desired shape. An extended set of arcs on the right has a low set of votes, i.e., it is inhibited, while the remaining arcs on the left have votes close to +1, i.e. they are drivable. Figure 9 shows the arc evaluation in another example scene.

We have successfully used this algorithm for arc evaluation in initial experiments on our HMMWV [Hebert et al., 1994], a converted truck for autonomous navigation. In this case, a 400 points grid was used. The combination of stereo computation and arc evaluation was done at an average of 0.5s on a Sparc-10 workstations. New steering directions were issued to the vehicle at that rate. This update rate is comparable to what can be achieved using a laser range finder [Langer et al., 1994].

An important aspect of the system is that we are able to navigate even though a relatively small number of points is processed in the stereo images. This is in contrast with the more conventional approach in which a dense elevation map is necessary, thus dramatically increasing the computation time. Using such a small number of points is justified because it has been shown that the set of points needed for driving is a small fraction of the entire data set independent of the sensor used [Kelly, 1994], and because we have designed our stereo matcher to compute matches at specific points.

In addition to the relative elevation, a measure of slope relative to the ground plane can also be computed with minimal knowledge of camera geometry. We do not describe the slope evaluation algorithm here because it is not integrated in the current system although the slope information is necessary for autonomous navigation because slope information is not sufficient to characterize all possible hazards. We refer the reader to [Robert and Hebert, 1994] and [Devernay, 1993] for a detailed presentation of the slope computation.

Figure 7: Evaluating steering at individual points; (top) Three points selected in a stereo pair and their projections; (bottom) Distributions of votes corresponding to the three points.

6 Conclusion

In this paper, we have presented a new approach to rover perception based on stereo without 3-D reconstruction. This approach uses weakly calibrated stereo images, and evaluates the traversability of terrain using relative elevation as a shape indicator. The vision task includes a rectification process, a fast and robust stereo matcher, and an algorithm for computing relative elevation and ground projections of image points.

We have validated this approach by combining it with a ateering evaluation algorithm and by integrating it with an existing navigation system. We have conducted experiments in natural terrain using our testbed vehicle. These preliminary experiments have shown that reasonable level of performance in autonomous driving can be achieved by using a small number of data points without strong calibration of the camera system.

Figure 8: Evaluating steering directions in an image; (top) Regular grid of points (dots) and corresponding projections (squares); (bottom) Distribution of votes for this image.

Figure 9: Example of arc evaluation in the case of a small obstacle.

Our current work concentrates on eliminating the limitations of the existing system in order to make it a practical alternative to conventional driving systems. These improvements include: extending the restricted field of view for typical video cameras; automatically adjusting system parameters; e.g., the location and density of the grid; including the slope computation; and using a feature detector in order to automate the initial training phase.

References

[Ayache and Hansen, 1988] N. Ayache and C. Hansen. Rectification of Images for Binocular and Trinocular Stereovision. In Proc. 9th International Conference on Pattern Recognition, Rome, Italy, October 1988.

[Devernay, 1993] F. Devernay. Calcul de Proprietes Differentielles de Formes Tridimensionnelles a Partir d’Images Stereoscopiques. Technical Report Rapport de stage, University of Nice, 1993.

[Faugeras et al., 1992] O.D. Faugeras, Q.T. Luong, and S.J. Maybank. Camera Self-Calibration: Theory and Experiments. In Giulio Sandini, editor, Proc. 2nd European Conference on Computer Vision, pages 321–334, Santa Margherita Ligure, Italy, May 1992. Springer Verlag.

[Faugeras, 1992] O. Faugeras. What Can be Seen in Three Dimensions with an Uncalibrated Stereo Rig. In Proc. European Conference on Computer Vision, Santa Margherita, 1992.

[Faugeras, 1993] O. Faugeras. Three-Dimensional Computer Vision: a Geometric Viewpoint. MIT Press, 1993.

[Hartley and Gupta, 1993] R. Hartley and R. Gupta. Computing Matched-Epipolar Projections. In Proc. Computer Vision and Pattern Recognition 93, pages 549–555, New York, New York, June 1993. IEEE.

[Hebert et al., 1994] M. Hebert, D. Pomerleau, A. Stentz, and C. Thorpe. A Behavior-Based Approach to Autonomous Navigation Systems: The CMU UGV Project. In To Appear in IEEE Expert, 1994, 1994.

[Kelly, 1994] A. Kelly. A Partial Analysis of the High Speed Autonomous Navigation Problem. Technical Report CMU-RI-TR-94-16, The Robotics Institute, Carnegie Mellon, 1994.

[Krotkov et al., 1994] E. Krotkov, M. Hebert, M. Buffa, F. Cozman, and L. Robert. Stereo Driving and Position Estimation for Autonomous Planetary Rovers. In 2nd Workshop on Robotics in Space, International Advanced Robotics Program, 1994.

[Langer et al., 1994] D. Langer, J. Rosenblatt, and M. Hebert. A Reactive System for Autonomous Navigation in Unstructured Environments. In Proc. International Conference on Robotics and Automation, San Diego, 1994.

[Matthies, 1992] L. Matthies. Stereo Vision for Planetary Rovers: Stochastic Modeling to Near-Real Time Implementation. International Journal of Computer Vision, 1(8), 1992.

[Mundy and Zisserman, 1992] J. L. Mundy and A. Zisserman, editors. Geometric invariance in computer vision. MIT Press, 1992.

[Robert and Faugeras, 1993] L. Robert and O. Faugeras. Relative Positioning and 3D Convex Hull Computation from a Weakly Calibrated Stereo Pair. In Proc. International Conference on Computer Vision, Berlin, 1993.

[Robert and Hebert, 1994] L. Robert and M. Hebert. Deriving Orientation Cues from Stereo Images. In Proc. European Conference on Computer Vision, Stokholm, 1994.

[Ross, 1993] B. Ross. A Practical Stereo Vision System. In Proc. Computer Vision and Pattern Recognition, New York, 1993.

[Shashua, 1993] A. Shashua. Projective Depth: a Geometric Invariant for 3D Reconstruction from Two Perspective/Orthographic Views and For Visual Recognition. In Proc. 4th International Conference on Computer Vision, pages 583–590, Berlin, Germany, May 1993. IEEE.

[Zeller and Faugeras, 1994] C. Zeller and O. Faugeras. Applications of Non-Metric Vision to Some Visual Guided Tasks. In Proc. International Conference on Pattern Recognition, Jerusalem, October 1994.

[Zhang et al., 1994] Z. Zhang, R. Deriche, O. Faugeras, and Q.T. Luong. A Robust Technique for Matching Two Uncalibrated Images Through the Recovery of the Unknown Epipolar Geometry. Technical Report 2273, INRIA, 1994.