A Computational Framework for the Visual Correspondence Problem

A COMPUTATIONAL FRAMEWORK FOR THE VISUAL CORRESPONDENCE PROBLEM

Michael Kass

MIT Artificial Intelligence Laboratory 545 Technology Square Cambridge, M A 02139

but tl1is may not be necessary if the local information is extracted properly.

Previous work on the correspondence problem has centered on two types of similarity measures. The most straightforward algorithms have used similarity measures such as correl<ition or mean square intensity differences [3] [10] while more recent a!goritl1ms have relied on measures which declare two points to be similar if they fall on edges of approximately the same orientation [ 1] [2) [4) [9]. Neither approach has yet achieved the kind of noise immunity needed for a truly practical solution to the correspondence problem.

This paper will explore the possibility of increasing noise im· munity by combining independent measures of similarity. No single similarity measure will be trusted much in isolation, but unanimity among the measures will be taken as a strong indication of correspon· dcncc. Using this approach, algoritluns can be constructed which will tolerate signal·to·noisc ratios as low as two to one, while localizing matches to within a pixel.

Let I 1 (x, y) and I2(x, y) be tl1e light intensity functions for two images whose correspondence is to be computed and let D(x, y) be tl1e true offset or disparity between the images measured relative to the coordinate system of I 1 (x, y) and defined on some set of points D ~ !R 2 for which corresponding physical points arc visible in both images. Then for all p ED. I 1(p) and /2(p + D(p)) arc projections of the same physical point. The problem is to recover D from I1 and I2 .

Consider a collection /;(p, I), 1 < i < n of different image func· tionals (filters). Each functional implicitly defines a similarity measure for correspondence since we expect that f,(p, I 1) ""' J,(p + D(p), I2 ) provided the j, arc chosen carefully. If we combine the functionals into a vector at each point: F(p,I) = (f,(p,I),h(r,I), .. . ,fn(p,I)) then we can expect the vector F(p1, II) - F(p2 ,12 ) to be very small in each component if p, and p2 correspond. On the other hand, if p1 and r 2 do not correspond, it is likely that F(p1 , I 1) - F(p2 , I2) has at least one large component.

The above intuition can be translated into an algorithm as follows. Define matchp;(p 1 , p2 ) be a predicate which is true if and only if

where cr(x) denotes the square root of tl1c expected value of x 2 and let matchp(p1, p2 ) be a predicate which is true if and only if for all i E {1, 2, ... , n },matchp,(p,, P2l- Then matchp is true of a pair of points P1 and P2 if each component of F(r1,Ii}- F(p2,!2 ) is smaller than its globally determined threshold. It will be argued that matchp does a good job of solving the correspondence problem if the / ; and the k ; arc chosen appropriately-it is almost always true of corresponding points and almost never true of non-corresponding points.

In order to evaluate matchp, suppose the /; are orthogonal linear shift invariant functionals and consider the following stationary image model. Let J1 be stationary Gaussian white noise and let / 2 be derived from I1 by shifting it according to D(p) and adding Gaussian white correspondence noise, N(p). The efiicacy with which D(x,y)

Abstract

;I <'0111putotional(rame11Vrk for solving the visuol correspondence problem is JW'.\e/1/ed a11d l'valua/cd by usi11g a stochaslic image model. The frame1vork dij.f'rrs principal~)' .fTom previous work in !hat it em· phasizcs I he cumhi11a1ion of a large cullcclion of independe11t measure· llll'nts. l'anial derivwivcs of imagfs smootlli'd 1rilh a fl'lv different-sized Gaussian filt ers are suggested as sui/able measuremc11ts. A specific conJputalioll is shr>wn lo reliably es/ablish whflher or not two points currespuml, pro1·idcd thai the signal lo correspo11dencc noise ratio in the images tu be mmchcd exceeds two. The computation has been applied to anijicial and //a/Ural images with encouraging results.

The problem of matching up two similar views of the same scene is one of Ul·: critical problems wh ich any powerful visinn system must solve. Known as the correspondence problem, it occurs most notably in stereopsis where the two views come from separate vantage points, and in motion analysis where the two views come from the same vantage point but arc separated in time. In stereopsis, a solution to the correspondence problem yields relative depth information fairly . directly. In motion analysis tl1e correspondence is more difficult to interpret, but it includes information about tl1c velocities and 3-dimcn.,;,inal structure of tl1c objects being viewed. The human visuai system is known to solve both correspondence problems with impressive range, resolution. and noise immunity though the manner in which it docs so is ill understood. Computer solutions to the correspondence problem have fallen far short of similar perfonnance, parttcularly on natural 1magcs. I\ new approach to !l1c problem will be presented here which, it is hoped, will provide insight into the structure of the correspondence problem, as well as a robust technique for solving it.

The correspondence problem can be stated quite simply as follows. Given two similar images of the same scene, a point in the first image is said to correspond with a point in the second image if b_oth arc projections along lines of sight of the same physical point. l he correspondence problem consists of trying to match up as many pairs of corresponding points as possible given tl1c intensity profiles of the two similar images.

!1.11 algorithmic solutions to the problem arc based on the idea that the light intensity profiles surrounding corresponding points are quite similar. · For each point in the first image, only points in the second image with quite similar local intensity profiles need be considered as potential matches. If the similarity measure is chosen appropriately, then a large fraction of tl1c points in the first image will have only one potential match in the second. If it can be confidently determined that tl1e similarity between these points and their potential matches is not due to chance, then tl1c unique potential matches can be tntstcd as correct matches. Global consistency constraints can be used in some cases to choose among several potential matches,

This report describeS research done at the Artiticial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's Artificial Intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Resear· ch contract NOOOI4·75·C·0643, the Office of Naval Research under contract number N00\4-80-C-()505, and the System Development Foundation.

can be determined from the j, under these conditions depends upon how well the j , arc preserved between views. Let

be the signal-to-correspondence-noise ratio of the ith functional. If S N R, is greater than two for a dozen functionals, then matchp witl very reliably determine whether or not two points correspond.

Three performance criteria wi ll be considered for matchp. The first is the rate of false negatives-the probability that matchp will be false of two corresponding points. The second criterion is the rate of false po~itivcs-the probabili ty that matchp will be true of two non­ corresponding points. The third criterion is one of resolution and concerns the extent to which corresponding points can be spatially localized.

The false negative rate is [6) [7)

The false positive rate is (6) [7)

Suppose SN R; = 2 for all i and n = 12. Then the choice of k; represents a tradeoff' between a very tow false positive rate and a very low false negative rate. False positives often result in the generation of wrong disparity values so they tend to be quite serious. False negatives, on the other hand, usually result simply in not being able to determine the disparity at a particular point. "Ibus a reasonable choice of k ; is one which produces a negligable false positive rate while still keeping the false negative rate to a low level. One such choice is k ; = 1.2. The resul ting false positive rate is .2 per cent and the resulting false negative rate is 18 per cent. Both rates arc a good deal lower than what is needed to reliably determine image correspondence. If the signal-to-correspondence-noise ratio is improved to three, the false positive rate can be improved an order of magnitude without worsening the false negative rate.

The third criterion of performance for matchp is that of resolu­ tion. If matchp(p1 , p2) is true, then matchp{p1, p2 + r) is quite likely to be true if r is small enough. The value r s of r at which the probability of matchp(p1, p2 + r) drops to fifty percent is determined primarily by the functional with the most sharply peaked autocorrela­ tion function. If A ; is the autocorrelation (normalized to be one at zero) of the ith functional. the resolution can be approximated by [6) [7]:

In deriving the properties of matchp which allow it to be used to solve the correspondence problem, the existence of a set of independent. linear shift invariant functionats whose values arc loosely preserved between views was assumed. One such set w1l1 be presented here. If p 1 is a point in D and p2 is its corresponding point then the functions J1(p1 +r) and IAPt +D(pt) -f-r ) can be expected to be quite similar for small values of r. One complet.: charactenzauon of the local behavior of a function of two dimensions is its two dimensional Taylor series, so it is natural to exami ne derivatives of It(Pt + _r) and h(C(p1) + r). !l.s one might expect, first and second partial derivatives appear cmpiricalty to be fairly well preserved between views. Differentiation tends to accentuate noise, so it is usually a good idea to do some low pass filtering before taking any sort of derivative. Marr and Hildreth [5] [R] argue that the best low pass filter to usc for appl ications such as this is a filte r with a Gaussian point-spread function because it minimizes the product of localization in space and frequency. Hence a reasonable set of functionals to look at is the set of derivatives of Gaussian smoothed images.

Not all derivatives of Gaussian smoothed images arc indepen­ dent. In fact, the nth and n + 2nd derivatives of Gaussian smoothed white noise arc very strongly correlated. These correlations can be calculated fairly directly. For notational convenience, let

Then the correlation between f n,,m,,u, and ! n,,m,,u, is [6) (7)

For any particular amount of Gaussian smoothing, the largest sets of independent deriva tives are of cardinality fou r. One such is the following:

If the ratio between the standard deviations of the two Gaussians is s = a1 f a2 then the effect of the size of the Gaussians on their correlation can be expressed by the relation:

Let J' = l" U l.,., U lo.·' . ll1e maximum correlation between two functionals in J' is (2sf(s 2 + 1))' which occurs betwcc,n first order tenns. If s = 2, the correlation is .41 but if s = 2.5, it drops to .23 and if s = 3, it falls to .13. The impact of these sman, non-zero correlations on the performance of matchp can safely be ignored.

!l.s an initial test, matchp was applied to a pair of gray level images generated by computer with all the important characteristics of the image model used here. J' was used as the set of functionals. The image pair has a signal-to-correspondence-noise ratio of two and a disparity field which is zero everywhere except in a central square covering one ninth of the image area where it is (6, D) in pixels. For each point (x, y) in the left image, matchp(x + n, y), n E { - 8, - 7, - 6·, . .. , 6, 7, 8} was calculated. If there was only one n such that matchp( x + n, y) was true, n was recorded as the disparity value. If there was more than one n such that matchp(x + n, y) was true, the disparity was recorded as ambiguous. If there was no n such that matchp(x + n, y) was true, the disparity was recorded as unknown.

Figure one shows the results of applying matchp to the above pair of images. The dark points indicate areas where the algorithm was unable to find matches. Slightly over 93 percent of the pixels in each image were uniquely matched. The mean square error in the disparity values generated was a small fraction of a pixel despite the large amount of correspondence noise.

It is worth noting that matchp failed to match most of the points along the border of the shifted central square. Some of the points were occluded in the second image, so it was correct not to match them, but most of the points went unmatched because the steep disparity gradient on the border substantially decreased the signal-to­ noise ratio. Correlation and edge-based algorithms tend to generate significant numbers of incorrect disparity values at occluded regions and at places where the disparity gradient is large, but the algorithm based on matchp avoids doing so because of matchp's unusu;11ly low false positive rate.

M a.tchp has been applied to a small number of natural images as well. Figure 3 shows the results of interpolating a surface through disparity values generated by matchp for the stereo pair in figure 2. Intensity is proportional to depth. The photos arc of the campus of the University of British ·columbia and ~ere obtained from the B.C. Ministry of Forests.

The combination of independent results has long been a favorite methocl uf statisticiaw;. M atchp represents an attempt to bring the power of this method to bear on the visual correspondence problem. !Jc:;ptte using the simplest method of combination imaginable, matchp attains a rather high level of performance and so argues strongly for the applicability of this statistical tool to the correspondence problem.

Acknowledgements

Tomaso Poggio and Keilli Nishihara provitled important guidance. R.J. Woodh<U11 and Eric Grimson made the stereo photographs available.