Significant Feature Detection and Matching in Image Pairs

I. Introduction

Computer algorithms for stereo vision and motion detection require the matching of features in one image to those in another. This is the correspondence problem. If the relative positions of features change from one image to another either because of motion in the scene or motion of the camera, then these changes can be used to estimate the relative velocities of moving objects in the scene or to partially

reconstruct the three-dimensional surfaces.

We seek a robust method for detecting these changes. To make this reliable, we need to first determine the location of features that are distmctive in the images; easily distinguished between views; and stable with respect to scale of viewing, orientation, and such projective effects as occlusion and P.erspective distortion . These features should be 'interesting" in the sense of (Moravec 1980), and be significantly different from their neighbors. They should be projections into the two-dimensional image of distinctive features in the three dimensional world, such as corners, contours, or surface markings.

Our main job then is to find significant features in complex images such as those in Figs. 1. In dealing

*Present address: Boeing Military Airplane Company, MS 48-88, POB 3707, Seattle, WA 98124, USA.

with the problem of complex images, we will proceed in a manner similar to many of the edge-based approaches (Fischler and Bolles 1986), (Freeman and Davis 1977), (Kruse and Rao 1978) in that we start our analysis with data structured into connected lists of edge-elements or contours. Part of our job will be to partition image contours at places where the edge connectivity may be deviating from the corresponding 3-space surface connectivity. These significant features then define our contour segmentation. In general the original contours will not limit themselves to following the outline of physical objects - rather, they follow level-set contours defined by some function on the underlying intensity surface.

We find our significant features by locating significant relative extrema of curvature along contours. Interesting features have high spatial gradients in all directions. A contour has a high spatial gradient in the orthogonal direction, and thus we have limited our problem to a search for high gradients in one direction - along the contour. These are extrema of curvature.

After finding a set of features in two images (and segmenting positions along the contours), we wish to put as many of these features as possible into correspondence . Corner matchers have been presented by (Shah and Jain 1984) and (Barnard and Thompson 1980). Here we wish to match significant features between images by local properties that are defined in terms of the original contour formation. These properties are curvature and the intensities on either side of the contour. We only use area based cross correlation (Hannah 1974) to verify a candidate match, not to originally locate a match.

II. Edge and Significant Feature Detection

In a common approach to edge detection (Marr and Hildreth 1980), edge-elements are positioned at the zeros in the result of convolving an intensity image with the laplacian of a Gaussian (loG). The loG is proportional to the difference of two Gaussians (DoG) with standard deviations s' and s as long as (s' - s) is "small."

Second derivative operators produce zeros ·at extrema of intensity changes. Zero crossings (edge­ elements) can be interpolated in the loG to subpixel precision. Contours are created by linking the zero crossings into edge lists. In our case the direction of a contour (the ordering of edge-elements in the edge list) is not arbitrary, but is set such that the positive region in the DoG is on the left-hand side of the contour (Marimont 1982). In addition to the (x,y) coordinates of the zero crossings, our edge lists contain resamplings of the original intensity values orthogonal to the edge on either side . This information will be used later when we match edge­ elements across images.

We define a significant feature as an edge-element at which the curvature goes through a significant local extremum. Significance is measured statistically. We first smooth each contour before computing the curvature k(s), where s is the arc length measured along a contour. This will give us both a more global and a more reliable measure of the curvature by increasing the signal-to-noise ratio from our original construction of the contour (Asada and Brady 1986), (Medioni and Yasumoto 1986). This smoothing is done by applying a Gaussian to the edge-elements along the contour.

Next we calculate the curvature at each point (xi.Yi) along the contour by noting that we can represent the curvature at each point on the contour by a circle of radius 11k(s) whose center lies along the normal vector at a distance 11k(s) from the curve. We then assign the sign (±)to the curvature according to which "side" of the contour our curvature circle lies (Fernet frame).

We select our significant features as significant local extrema of curvature. A significant feature is relative extremum of curvature more than "no" from the mean, where n is some positive number to be specified later. Contours measure an underlying connectivity in the image, and we select features relative to that connectivity.

Once we have determined, for example, that we have m interesting features, we can segment our contour into m smaller segments (ignoring for now the distinction between open and closed contours).

Our procedure is iterative. We can run our segmenter over the output of a previous segmentation. We can also change the threshold n for each iteration. This solves the problem of an initial contour with a varied structure. The result of our algorithm is a list of contour segments and significant features.

Stability can be established by slightly perturbing the parameters used in calculating our significant features and seeing if any of these features disappear, or if many new features suddenly appear. One stability test is that in the familiar scale space (Witkin 1983), (Asada and Brady 1986). Scale can be defined over a range of o's, and we obtain a set of contours smoothed by Gaussians with standard deviations from that range. We determine which significant features persistover a large range of o's, or scales. Another test of stability requires us to first plot the number of features as a function of the curvature threshold n. This plot will be a non-increasing function of n. If this function is constant over a range of values for n, then the significant features are stable over this region.

Our significant feature detector is both robust and dynamic. Each contour is treated separately and independently, and the criteria for significant features are selected dynamically for each. The algorithm is robust because it can handle both simple and complex contours by taking a long contour, breaking it into smaller sections, and then, by iteration, examining each smaller section individually and mdependently.

Ill. Significant Feature Matcher

We now wish to take the set of significant features found in the image pairs A and B, and see if we can find matches between the two sets. The three variables we intend to use first in matching the significant features in images A and B are the curvature, and the left and right intensities on either side of the contour.

Let us now consider a significant feature i in image A with a curvature C[Ai]. left intensity L[A,). and right intensity R[Aj] . Consider also a sign1ficant feature j in image B with curvature C[Bj]. and left and right intensities L[Bj] and R[Bj]. We now define three new curvature and intensity variables as follows :

The closer each variable is to zero, the closer the match between parameters from images A and B.

Our statistical model of the data has shown that these variables Cij. Rij. and Lij are consistent with being linearly dependent on the probability of a match between features i and j . A low value for the parameter Cij is, however, a better indicator of a correct match than is a similar score for Rij or Lij· We notice no significant statistical differences between Rij and Lu: The results are stored in an initial matched pornt 11st.

Since we know the approximate orientation of the two stereo images, we can now use cross correlation to check these initial matches (Hannah 1974) by calculating the correlation coefficient rij (Hays 1973) between two small areas surrounding our significant features. Cross-correlation is used only to confirm matches, not "find" matches.

If significant features i and j represent the same physical feature as seen in image A and image B, then the variables, then their x- and y- disparities should both form distributions with well defined means and standard deviations. We now el iminate all matched feature pairs whose x- or y- disparities lie outside of the 95% confidence level. We repeat this process until there are no matched feature pairs outside this range.

The results can be seen in Fig. (1 ). Figs. ( 1 a) and (1 b) are a stereo pair of a highway overpass. Figs. (1c) and (1d) are the edge segments and matched features. The matching routine found 27 features that matched, and there were no mistakes.

We can increase the number of matches by using a large scale space matching first, and using the results of this matching as seeds for our feature matcher. We start by taking the contours and smoothing them with a Gaussian with a larger o. We then run our matcher over these features and at the end, calculate the mean and standard deviations of the x- and y- disparities. We then use these disparities as seeds in our original feature matcher.

This increases our accuracy because it eliminates a large number of incorrect first guesses based on local curvature and intensity matching . We now find correct matches using only curvature and local intensity functions. We need not use cross-correlation to verify these matches. We have also increased the number of correct matches, since false matches that are not in the restricted search space will no longer be considered. This restricted search space for matching is equivalent to the initial assumptions in the matching done in (Barnard and Thompson 1980) and (Shah and Jain 1984).

IV. Conclusions and Summary

We have presented a dynamic significant feature detector and contour segmenter which works on complex images. The significant features found are based on local criteria, and are found independently. We then used significant features as input data for our general feature and segment matcher.

The feature matcher presumes that these significant features in the images can be matched on the basis of their local properties. If there are repeated structures in the images, this is not always the case. The solution is to use an edge detector that looks at larger structures in the image.

Another assumption we use is that the pan and tilt for the relative camera orientations are small . If they are large, then the difference in perspectives between stereo images is large, and matching becomes more difficult. We can distinguish this case from the previous cases by noting the x- and y-disparity standard deviations after our first scale space matching. If the standard deviations are large compared to the image dimensions, then the second stage of matching, restricting our matches to small average x- andy-disparities no longer makes sense.

Acknowledgements

We wish to thank Dr. H. Harlyn Baker for his many helpful comments and suggestions, and for his critical reading of this manuscript.