AP07_4-5.vp 1 Introduction Modern point matching algorithms like SIFT (see [4, 5]), provide a large number of point matches, even in stereo image pairs with large changes in scale, translation and rota- tion between the images. The only inconvenience is that there are some wrong matches among the correspondences, espe- cially when parts of the first image are not visible in the second. Algorithms for computing the fundamental matrix can be classified into algorithms sensitive to wrong matches and algorithms detecting and ignoring so-called outliers like RANSAC or Least Median of Squares. In [3] and [7] algo- rithms of both categories are described and compared. Basically, algorithms of the first category should only be used after preliminary outlier removal. The motivation to use them is that some of them perform better than RANSAC or LMedS (see [3]). Based on [3], we used RANSAC combined with the normalized 8-point algorithm to compute a first estimation of the fundamental matrix in order to perform outlier removal. An observation is that using the criterion presented in [7], i.e. the distance of a point to its corresponding epipolar line, some true correspondences, which may be important for an estimation of the epipolar geometry, are also eliminated. As a consequence we have developed a new criterion to evaluate correspondences between two images, considering the esti- mation of the fundamental matrix and its uncertainty. The paper is structured as follows: In section two, the computation of the covariance matrix of the fundamental matrix using Monte Carlo Simulation is described. Further we describe the computation leading to the new criterion. In section three, we show how the criterion can be used in an ef- fective way for outlier removal, and we compare our results with those using a conventional criterion. In section four a brief conclusion is given. 2 Confidence measure for point correspondences To evaluate the quality of a single point correspondence from a set of point correspondences, we use the only available geometric constraint, the epipolar geometry and its algebraic representation, the fundamental matrix. The computation of the fundamental matrix using the Random Sample Consen- sus combined with the normalized 8-point algorithm is de- scribed in [3] and [7]. As the locations of point correspon- dences are superimposed with noise, the computation of the covariance matrix of the fundamental matrix provides fur- ther useful information. 2.1 Computing the covariance matrix of the fundamental matrix To compute the covariance matrix, we assume that the noise on the correspondence locations has normal distribu- tion. We simulate this effect by adding Gaussian noise to the eight correspondences selected by RANSAC during the fun- damental matrix computation. We obtain a set of different versions of the same eight point correspondences, and com- pute the fundamental matrix from each version using the normalized 8-point algorithm. A large number of different fundamental matrices is ob- tained, showing how the epipolar geometry varies under slight changes in the point correspondence locations. A good description of this effect is given by the covariance matrix of the fundamental matrix, denoted by �F . 2.2 Epipolar line and epipolar envelope For a given point x in the first image, the corresponding epipolar line l in homogeneous coordinates is given by l x� F , (1) © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 23 Acta Polytechnica Vol. 47 No. 4–5/2007 Robust Detection of Point Correspondences in Stereo Images A. Stojanovic, M. Unger A major challenge in 3D reconstruction is the computation of the fundamental matrix. Automatic computation from uncalibrated image pairs is performed from point correspondences. Due to imprecision and wrong correspondences, only an approximation of the true fundamental matrix can be computed. The quality of the fundamental matrix strongly depends on the location and number of point correspondences. Furthermore, the fundamental matrix is the only geometric constraint between two uncalibrated views, and hence it can be used for the detection of wrong point correspondences. This property is used by current algorithms like RANSAC, which computes the fundamental matrix from a restricted set of point correspondences. In most cases, not only wrong correspondences are disregarded, but also correct ones, which is due to the criterion used to eliminate outliers. In this context, a new criterion preserving a maximum of correct correspondences would be useful. In this paper we introduce a novel criterion for outlier elimination based on a probabilistic approach. The enhanced set of correspondences may be important for further computation towards a 3D reconstruction of the scene. Keywords: 3D reconstruction, robust matching, fundamental matrix, probabilistic epipolar geometry, outlier elimination. where F is the fundamental matrix. Due to the uncertainty of the fundamental matrix, the point correspondence is more likely to be located within an area around the epipolar line. From the covariance matrix of the fundamental matrix, we can compute the covariance matrix of the epipolar line with � l � JFJ T, (2) where J is the Jacobian of the mapping l x x � F F . (3) The Mahalanobis distance k of a possible epipolar line m from the estimated epipolar line l is then given by ( ) ( )l m l ml� � � �T � k2. Thus we have an approximation of how well a certain epipolar line m matches with the knowledge acquired so far about the epipolar geometry and its uncertainty. For a given value of k2 , we can compute an envelope of epipolar lines containing all possible epipolar lines having a value less or equal to k2. With the assumption that the elements of l have normal distribution, k2 has a cumulative �2 2 distribution and a probability that the true epipolar line is within this envelope can be associated to the k2-value, as can be seen in Fig. 1. The region can be described by a conic C defined in homogeneous coordinates by C � �ll l T k2� . (4) In [3] the epipolar envelope is used for guided matching, i.e. searching correspondences within the epipolar band after a first estimation of the fundamental matrix. We observed that if the fundamental matrix is computed from correspon- dences located only in the foreground, the uncertainty in the background becomes very high (see Fig. 2). This is the reason why correct matches lying in the corners of the image are of- ten eliminated using a conventional criterion. To prevent this, we have to develop a new criterion being less stringent for matches in regions of high uncertainty. 2.3 Minimal Mahalanobis distance for a point correspondence Basic idea The basic idea for the new criterion is to invert the prob- lem of Wnding an epipolar band for a given likelihood (i.e. a given k2 respectively probability �). For a given point �x in the second view corresponding to a point x in the first view, we want to find the conic with minimal k2 comprising the point �x . In other terms, we are retrieving the value k2 in equation (4) that provides a hyperbola passing through �x . The considerations behind this idea are very simple if we know that the epipolar line of a point x in the first image will lie with a certain probability within an epipolar band in the second image, the corresponding point �x , which is located somewhere on the epipolar line, will be within the epipolar band with the same probability. General Problem Statement The point �x belongs to the conic C if the following equa- tion is verified � � �x xTC 0 , (5) where C is given by: C � �ll l T k2� . (6) F k2 1 2� �( ) � is the probability to find �x within C. We use again the notation m for an epipolar line in the second image. In fact l is here the estimated epipolar line corresponding to the point x in the first image. It is not possible to retrieve directly the corresponding value k2 from a point �x using the equations above. One possi- 24 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 Fig. 1: Envelope of epipolar lines: We computed the epipolar line (dark) and the epipolar band (light) in the second image. The point in the first image that we used for the computa- tion is marked by a white point. The epipolar band shown here represents the envelope of epipolar lines with equal k2 5 99915� . . The according probability that the true epi- polar line lies within this band is � � 0 95. . We see that for this value the conic is a hyperbola with two branches. Fig. 2: High insecurity for points in the background: In this fig- ure the effect of choosing points only in the foreground is demonstrated. We see that the insecurity for points in the background is much higher than for points in the fore- ground, as the epipolar band is much more extended. INRIA Syntim owns the copyright of the image. bility would consist in computing a multitude of different conics using a range of different values for k2, and localize �x in between the conics. An approximation for k2 would be ob- tained by interpolation, but we found a closed-form solution to the problem, providing an exact result. Closed-form solution Let us assume that the confidence, that any point �x in the second image corresponds to a point x in the first view is in relation with the probability of the epipolar geometry that would explain the correspondence pair x x� � and having at the same time the highest probability. In other terms, for a potential point correspondence x x� �, we retrieve the epipolar line m passing through �x having maximal probabil- ity, i.e. minimal k2 regarding equation (14). This assumption differs from the assumption made in [1], and we obtain a dif- ferent criterion, which is more suitable for our purpose. If we denote with m the unknown epipolar line and with l the estimated line in the second image, the constrained minimization problem can be stated as follows: min( ) ( )l m l m x m l� � � � � � �T T � 0 (7) If � �x ( , , )x y z , m � ( , , )a b c T, l � ( , , )l l l1 2 3 T, and � l � � � � � � � � � � � � � � � � � � � 11 12 13 21 22 23 31 32 33 (8) we obtain function f (a, b, c) to be minimized with f a b c l a l b l c ( , , ) � � � � � � � � � � � � 1 2 3 11 12 13 21 22 23 T � � � � � � � � �31 32 33 1 2 3 � � � � � � � � � � � � � � � � � � � l a l b l c and a constraint g(a, b, c) � 0 with g a b c ax by cz( , , ) � � � . (9) For the minimization we use the Lagrange multiplier method to obtain an exact solution by solving the set of equations: � � � � � � f a b c g a b c g a b c ( , , ) ( , , ) ( , , ) � 0 (10) After expanding f (a, b, c) and computing its derivatives we have: � � � � � � � � � � f a a l l l l l b b � � � � � � � � 2 211 1 11 2 21 3 31 2 12 3 13 21 12 31 13� �c c� � , � � � � � � � � � � f b b l l l l l a a � � � � � � � � 2 222 2 22 1 12 1 21 3 23 3 32 21 12 23 32� �c c� � , � � � � � � � � � � f c c l l l l l a a � � � � � � � � 2 233 3 33 1 13 1 31 2 23 2 32 13 31 23 32� �b b� � . For g a b c( , , ) we have the following derivatives: � � � � � � g a x g b y g c z � � � , , . (11) Thus we have � � � � � � � � � � � � � � � � � � � � g a f a x f a g b f b y f b g c f � � � � � � � � � 1 1 , , � � � �c z f c � � �1 . (12) As we are solving a problem with three unknown variables, 3 equations are sufficient. Using the relations from equation (12) and the constraint that the point is on the line m, we ob- tain the set of equations: x f a y f b y f b z f c ax by cz � � � � � � � � � 1 1 1 1 0 � � � � � � � � . , (13) Expanding equation (13) we have the set of equations a b c x y x y 2 211 12 21 12 21 22 13 � � � � � � � � � � � � � � � � � � � � � � � 31 23 32 1x y h� � � � � � �� � , a b c x y x z 2 11 13 31 12 21 22 32 1 � � � � � � � � � � � � � � � � � � � � � � � 3 31 332 2 � � � � � � � � � x z h , ax by cz� � � 0 . where h l l l l l x l l l 1 1 11 2 21 3 31 2 12 3 13 2 22 1 12 1 2 2 � � � � � � � � � � � � � � � � � �21 3 23 3 32� �l l y , h l l l l l x l l l � � � � � � � � 2 2 1 11 2 21 3 31 2 12 3 13 3 33 1 13 1 � � � � � � � � 31 2 23 2 32� �l l z � � . This set of equations can be easily computed and the solu- tion vector ( , , )a b c T is the vector m passing through �x and having minimal k2 in terms of equation (7). Finally, we obtain coordinates of the line m passing through �x and the corre- sponding value k2 that would produce an epipolar band de- limited by a hyperbola passing through �x . The value k2 will be of special interest in applications, as we will use it as a qual- ity criterion for point correspondences in our applications. Example in an image pair To summarize the algorithm, we can explain the different steps using an example in an image pair (see Fig. 3).We start after the fundamental matrix and its covariance have been computed for the given image pair. We see the estimated epipolar line in the second image, which we denoted by m, © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 25 Acta Polytechnica Vol. 47 No. 4–5/2007 that corresponds to the point x in the first image which is marked by a white point. Further we computed the epipolar band (delimited by the hyperbola) for a value k2 5 9915� . , re- spectively a probability � � 0 95. that the true epipolar line will be located within this region. Further, for points marked by a black circle in the second image, we computed the line passing through the point and having a minimal k2 in terms of equation (7). The lines are dark and represent the lines previously denoted by m. A further question to answer is the value k2 of the chosen line m. It can be easily computed using ( ) ( )l m l ml� � � �T � k2. In Fig. 3 we obtain a value of k2 848178� . for the central point associated to the vertical line m, and a value of k2 6 07� . for the point in the right side of the image. The fact that this value is almost equal to 5.991 and the corresponding line m is tangent to the hyperbola is an interesting observation, and will be discussed later. Properties We want to briefly show some special cases of lines with minimal k2. One of the reasons why we cannot use the crite- rion from [1] is because it also contains depth information coming from the chosen point correspondences to compute the fundamental matrix and its covariance. In practice, this becomes visible in the property that points lying on the esti- mated epipolar line (which is of course the most probable epipolar line) do not have the same probability. In Fig. 4 we see that the line m is identical to the estimated epipolar line l. Thus we have k2 0� for each point on the esti- mated line. Another effect is shown in Fig. 5. We computed the line m for a point on the hyperbola delimiting the epi- polar band. We see that the dark line that we obtain is tangent to the hyperbola and the value for k2 is equal to the value we used for k2 to compute the hyperbola. In other terms, if we want to retrieve the value k2 for a hyperbola passing through 26 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 Fig. 3: Example of an image pair with points and their respective line with minimal k2 : We see the estimated epipolar line in the second image, l, that corresponds to the point x in the first image, which is marked by a white point. The epipolar band for a value k2 59915� . , respectively a prob- ability � � 0 95. is within the hyperbola. Points marked by a black circle in the second image are shown together with the lines of minimal k2, denoted by m, and represented dark. Fig. 4: Line with minimal k2 computed for a point on the esti- mated epipolar line: We see the epipolar band for a value k2 59915� . , marked by the hyperbola, corresponding to the point x in the first image, which is marked by a white point. Obviously the epipolar line with smallest k2 for points on the estimated epipolar line is the epipolar line itself. Here we see that these two lines are superposed. The corresponding value is k2 0� . Fig. 5: Line with minimal k2 computed for a point on the hyper- bola: We see the epipolar band for a value k2 59915� . , marked by the hyperbola, corresponding to the point x in the first image which is marked by a white point. The line m with minimal k2 for the black point on the hyperbola is tangent to the hyperbola. The corresponding value for k2 is equal to the value we choose to compute the hyperbola, i.e. k2 5991� . . the point x, it is sufficient to compute the line with minimal k2 as the k2 obtained for the line will be equal to the value ob- tained if we retrieved the hyperbola. Results We started from the situation that for a point x in a first image a region in the second image, delimited by a hyper- bola, was defined. We knew from the epipolar geometry and its uncertainty that its correspondence �x would be located within this region with a given probability �, which was de- rived from the Mahalanobis distance k. The result is that we can now compute for a pair of corresponding points x x� � the corresponding hyperbola, passing through �x , and the value k2 corresponding to the hy- perbola. In the old application the probability to find the corresponding point �x within the hyperbola was increasing with higher values for k2, (the region bounded by the hyper- bola increases with higher values of k2), in our application a low value for k2 indicates that the probability that x x� � are corresponding points is high and vice versa. The way to find the value for k2, which is actually the Mahalanobis distance k between the estimated epipolar line and the line passing through �x with minimal k, is of no rele- vance in applications. This means that in our applications, for a point �x , we will only be interested in the Mahalanobis dis- tance of the corresponding line m, not in the line itself. For the purpose of illustration we generated Fig. 6, where for each pixel �x we computed the Mahalanobis distance k2 according to the minimization problem from equation (7) and represented it using grayscales. In particular, points in white have values close to k2 0� , points in black, a value close to the maximum value on the image. We used the whole range of k2 values on the second image and divided the range into 256 levels of equal width, each one represented by its relative grayscale level. 3 Application to outlier removal The initial aim was to develop a new criterion for robust outlier elimination. Existing algorithms use criteria based on the distance of a point to its corresponding epipolar line. For distance based algorithms, in the background, the distance to the epipolar line will increase as the estimation of the funda- mental matrix will be far better for points in the foreground. The use of a threshold distance to eliminate outliers will lead to an elimination of points further away from the central points, as we can observe in Fig. 8 (b). Similar to other applications, we could consider using the epipolar band to remove outliers. This means that instead of computing the epipolar line and the distance of a point to the epipolar line, we just compute the epipolar band, and remove points located outside the epipolar band. This would resolve the problem of removing points from the background. Al- though this application seems suitable, two parameters have to be set. First we have to make an assumption about the vari- ance of the point correspondences, and the value for k2 from where we compute the epipolar band needs to be set. In the following we present an algorithm overcoming the draw- backs of the algorithms mentioned above by using our new criterion. 3.1 Algorithm The values chosen for the standard deviation � of points to compute the covariance matrix of the fundamental matrix are varying, and thus we first computed the value k2 of each used point correspondence. If we consider the distribution of the value k2 for each point in Fig. 7, we see that most of the correspondences are very small, whereas some correspon- dences have huge k2 values. A classification of inliers and out- liers can be easily performed. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 27 Acta Polytechnica Vol. 47 No. 4–5/2007 Fig. 6: Image representing the Mahalanobis distance k2 over an image: The right image shows the epipolar band for k2 5991� . . In the left image we computed for each pixel �x the Mahalanobis distance k2 and represented it using grayscales. In particular, points in white have values close to k2 0� , points in black, a value close to the maximum value on the image. We used the whole range of k2 values and divided the range into 256 levels of equal width, each one represented by its relative grayscale level. Fig. 7. Distribution of the values of k2: This figure shows a histo- gram over the values for k2 of the point correspondences from Fig. 8 (a) Our proposition is to compute the median value of k2 . As the RANSAC algorithm does not perform well in the case of more than 50 percent outliers, we only consider the case of having at least 50 percent inliers. As a consequence the me- dian value for k2 will be the value of an inlier. An observation was that the values for inlier were very similar, whereas the values for outliers were huge. In practice we therefore elimi- nate every point correspondence with a value of more than ten times the median value. Another proportion may be used but in our tests we obtained reasonably good results. 3.2 Results The results presented here were obtained using RANSAC for an estimation of the fundamental matrix. Further, the covariance matrix of the fundamental matrix was computed by adding noise to the eight point correspondences used to compute the fundamental matrix. In fact we obtained the same results for the outlier elimination using a standard deviation � in the range of 0.02 to 10 pixels. Therefore no knowledge about the quality of the image and the variance of the correspondences is needed for the outlier removal with the new criterion. The results are presented in Fig. 8. 4 Discussion We have seen that the new criterion can be used for outlier removal without side information about the image quality and brings the advantage of providing a larger set of point correspondences. An observation is that the points preserved by the new algorithm are more widely spread throughout the image than the points obtained with a conventional crite- rion. Hence the initial fundamental matrix estimation rather seems to suit point correspondences in the center of the image. Our current research is focused on comparing fundamen- tal matrices computed from the initial set of point correspon- dences to those obtained with the enhanced set, using image pairs with known epipolar geometry, i.e. a comparison to ground truth. Furthermore we try to identify different planes spanned in space by the point correspondences, in order to examine the influence of the depth distribution of the corre- spondences onto the accuracy of the computed fundamental matrix. Acknowledgments The research described in this paper was supervised by Prof. J.-R. Ohm, IENT RWTH Aachen University. The authors wish to thank the team at IENT, RWTH Aachen University for its assistance and help. References [1] Brandt, S.: On the Probabilistic Epipolar Geometry. Journal of Mathematical Imaging and Vision, in press, 2007. [2] Hartley, R.-I.: In Defense of the 8-point Algorithm. Pro- ceedings of the 5th International Conference on Computer Vision, June 1995, p. 1064–1070. [3] Hartley, R.-I., Zisserman, A.: Multiple View Geometry in Computer Vision. Second edition. Cambridge University Press, 2004. [4] Lowe, D.: Object Recognition from Scale Invariant Fea- tures. Proceedings of the 7th International Conference on Com- puter Vision. Corfu, Greece, Vol. 2 (1999), p. 1150–1157. [5] Lowe, D.: Distinctive Image Features from Scale-Invari- ant Keypoints. International Journal of Computer Vision, (2004), p. 91–110. [6] Zhang Z., Deriche, R., Faugeras, O., Luong, Q.-T.: A Ro- bust Technique for Matching two Uncalibrated Images through the Recovery of the Unknown Epipolar Geometry. Artificial Intelligence, November 1995. [7] Zhang, Z.: Determining the Epipolar Geometry and its Uncertainty: A Review. International Journal on Computer Vision, Vol. 27 (1998), No. 2, p. 161–195. Ing. Aleksandar Stojanovic e-mail: stojanovic@ient.rwth-aachen.de Ing. Michael Unger e-mail: unger@ient.rwth-aachen.de Institute of Communication Engineering RWTH Aachen University 52056 Aachen, Germany 28 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 Fig. 8: Results: (a) stereo image pair with SIFT correspondences, the 8 points selected by RANSAC are dark. (b) remaining point correspondences after outlier removal using the distance from the epipolar line. (c) enhanced point corre- spondence set using the new criterion. INRIA Syntim owns the copyright of the image pair.