View of Robust Detection of Point Correspondences in Stereo Images

(1)

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] algorithms 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 estimation 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 described in [3] and [7]. As the locations of point correspondences are superimposed with noise, the computation of the covariance matrix of the fundamental matrix provides further 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 distribution. We simulate this effect by adding Gaussian noise to the eight correspondences selected by RANSAC during the fundamental matrix computation. We obtain a set of different versions of the same eight point correspondences, and compute the fundamental matrix from each version using the normalized 8-point algorithm.

A large number of different fundamental matrices is obtained, 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 byS_F.

2.2 Epipolar line and epipolar envelope

For a given pointxin the first image, the corresponding epipolar linelin homogeneous coordinates is given by

l=Fx, (1)

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.

(2)

whereFis 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

Sl=JFJ^T, (2)

whereJis the Jacobian of the mapping l x

= Fx

F . (3)

The Mahalanobis distancekof a possible epipolar linem from the estimated epipolar linelis then given by

(l-m)^TS_l⁺(l-m)=k².

Thus we have an approximation of how well a certain epipolar linemmatches with the knowledge acquired so far about the epipolar geometry and its uncertainty. For a given value ofk² , we can compute an envelope of epipolar lines containing all possible epipolar lines having a value less or equal tok². With the assumption that the elements oflhave normal distribution,k²has a cumulativec22

distribution and a probability that the true epipolar line is within this envelope can be associated to thek²-value, as can be seen in Fig. 1. The region can be described by a conicCdefined in homogeneous coordinates by

C=ll^T-k²S_l. (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 correspondences 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 problem of Wnding an epipolar band for a given likelihood (i.e. a givenk²respectively probabilitya). For a given pointx¢in the second view corresponding to a pointxin the first view, we want to find the conic with minimalk²comprising the point

¢

x. In other terms, we are retrieving the valuek²in equation (4) that provides a hyperbola passing throughx¢.

The considerations behind this idea are very simple if we know that the epipolar line of a pointxin the first image will lie with a certain probability within an epipolar band in the second image, the corresponding pointx¢, which is located somewhere on the epipolar line, will be within the epipolar band with the same probability.

General Problem Statement

The pointx¢belongs to the conicCif the following equation is verified

¢ ¢ =

x^TCx 0 , (5)

whereCis given by:

C=ll^T -k²S_l. (6) F₂^-^{1 2}( )k =ais the probability to findx¢withinC. We use again the notationmfor an epipolar line in the second image.

In factlis here the estimated epipolar line corresponding to the pointxin the first image.

It is not possible to retrieve directly the corresponding valuek²from a pointx¢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 computation is marked by a white point. The epipolar band shown here represents the envelope of epipolar lines with equal k²=599915. . The according probability that the true epipolar line lies within this band isa=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 foreground, as the epipolar band is much more extended.

INRIA Syntim owns the copyright of the image.

(3)

bility would consist in computing a multitude of different conics using a range of different values fork², and localizex¢ in between the conics. An approximation fork²would be obtained 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 pointx¢in the second image corresponds to a pointxin the first view is in relation with the probability of the epipolar geometry that would explain the correspondence pairx« ¢x and having at the same time the highest probability. In other terms, for a potential point correspondence x« ¢, we retrieve thex epipolar linempassing throughx¢having maximal probability, i.e. minimalk²regarding equation (14). This assumption differs from the assumption made in [1], and we obtain a different criterion, which is more suitable for our purpose.

If we denote withmthe unknown epipolar line and withl 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 S

0 (7)

Ifx¢ =( , , )x y z,m=( , , )a b c^T,l=( , , )l l l_{1 2 3}^T, and Sl+=

æ

è çç ç

ö

ø

÷÷

÷

s s s

11 12 13

21 22 23

31 32 33

(8)

we obtain functionf(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 s s s

s s s

s31 s32 s33 1 2 3

æ

è çç ç

ö

ø

÷÷

÷ -

- - æ

è çç ç

ö

ø

÷÷

÷

l a

l b

l c

and a constraintg(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

( , , ) ( , , ) ( , , )

l

0 (10)

After expandingf(a,b,c) and computing its derivatives we have:

¶

¶ s s s s s s

s s

f

a a l l l l l

b b

= - - - - -

+ +

2 ₁₁ 2_{1 11} _{2 21} _{3 31} _{2 12} _{3 13}

21 12+cs31+cs13,

¶

¶ s s s s s s

s s

f

b b l l l l l

a a

= - - - - -

+ +

2 ₂₂ 2_{2 22} _{1 12} _{1 21} _{3 23} _{3 32}

21 12+cs23+cs32,

¶

¶ s s s s s s

s s

f

c c l l l l l

a a

= - - - - -

+ +

2 ₃₃ 2_{3 33} _{1 13} _{1 31} _{2 23} _{2 32}

13 31+bs23+bs32.

Forg a b c( , , ) we have the following derivatives:

¶

¶¶

¶ g

a x

g

b y

g c z

=

= , , .

(11)

Thus we have l¶

¶

¶ l ¶

¶ l¶

¶

¶ l ¶

¶ l¶

¶

¶ g a

f

a x f

g a b

f

b y f

g b c

f

= Û =

=

- - 1 1

, ,

¶ l ¶

¶

c z f

Û = ^-1 c.

(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 linem, we obtain the set of equations:

x f

a y f

b

y f

b z f

ax by cz c

- -

=

+ + =

1 1

0

¶

¶ ¶

¶

¶ .¶

, (13)

Expanding equation (13) we have the set of equations

a b

c

x y x y

2 ₁₁ ₁₂ ₂₁ ₁₂ ₂₁ 2 ₂₂

13

s s s s s s

s s

æ -

èç ö

ø÷ + æ -

èç ö

ø÷ +

+ +

+ ₃₁ ₂₃ ₃₂

x - y h1

æè

ç ö

ø÷ =

+

s s ,

a b

c

x y x z

2 ₁₁ ₁₃ ₃₁ ₁₂ ₂₁ ₂₂ ₃₂

1

s s s s s s s

s

æ -

èç ö

ø÷ + æ -

èç ö

ø÷ +

+ + +

3 31 2 33

+ - 2

æè

ç ö

ø÷ =

s s

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

= + + + +

- + +

s s s s s

s s s21+l3 23s +l3 32s

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

s s s s s

s s s31+l2 23 +l2 32

z

s s .

This set of equations can be easily computed and the solution vector ( , , )a b c^T is the vector mpassing throughx¢and having minimalk²in terms of equation (7). Finally, we obtain coordinates of the linempassing throughx¢and the corresponding valuek²that would produce an epipolar band delimited by a hyperbola passing throughx¢. The valuek²will be of special interest in applications, as we will use it as a quality 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 bym,

(4)

that corresponds to the pointxin the first image which is marked by a white point. Further we computed the epipolar band (delimited by the hyperbola) for a valuek² =59915. , respectively a probabilitya=095. 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 minimalk²in terms of equation (7). The lines are dark and represent the lines previously denoted bym.

A further question to answer is the valuek²of the chosen linem. It can be easily computed using

(l-m)^TS_l⁺(l-m)=k².

In Fig. 3 we obtain a value ofk² =848178. for the central point associated to the vertical linem, and a value ofk² =607. for the point in the right side of the image. The fact that this value is almost equal to 5.991 and the corresponding linemis 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 minimalk². One of the reasons why we cannot use the criterion 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 estimated epipolar line (which is of course the most probable epipolar line) do not have the same probability.

In Fig. 4 we see that the linemis identical to the estimated epipolar linel. Thus we havek²=0for each point on the esti-

mated line. Another effect is shown in Fig. 5. We computed the linemfor a point on the hyperbola delimiting the epipolar band. We see that the dark line that we obtain is tangent to the hyperbola and the value fork²is equal to the value we used fork²to compute the hyperbola. In other terms, if we want to retrieve the valuek²for a hyperbola passing through

Fig. 3: Example of an image pair with points and their respective line with minimalk²: We see the estimated epipolar line in the second image,l, that corresponds to the pointxin the first image, which is marked by a white point. The epipolar band for a valuek²=59915. , respectively a probabilitya=0 95. is within the hyperbola. Points marked by a black circle in the second image are shown together with the lines of minimalk², denoted bym, and represented dark.

Fig. 4: Line with minimalk²computed for a point on the estimated epipolar line: We see the epipolar band for a value k²=59915. , marked by the hyperbola, corresponding to the pointxin the first image, which is marked by a white point. Obviously the epipolar line with smallest k² for points on the estimated epipolar line is the epipolar line itself. Here we see that these two lines are superposed. The corresponding value isk²=0.

Fig. 5: Line with minimalk²computed for a point on the hyperbola: We see the epipolar band for a value k²=59915. , marked by the hyperbola, corresponding to the pointxin the first image which is marked by a white point. The line mwith minimalk²for the black point on the hyperbola is tangent to the hyperbola. The corresponding value fork² is equal to the value we choose to compute the hyperbola, i.e.k²=5991. .

(5)

the pointx, it is sufficient to compute the line with minimalk² as thek²obtained for the line will be equal to the value obtained if we retrieved the hyperbola.

Results

We started from the situation that for a pointxin a first image a region in the second image, delimited by a hyperbola, was defined. We knew from the epipolar geometry and its uncertainty that its correspondencex¢would be located within this region with a given probabilitya, which was de- rived from the Mahalanobis distancek.

The result is that we can now compute for a pair of corresponding pointsx« ¢x the corresponding hyperbola, passing throughx¢, and the valuek²corresponding to the hyperbola. In the old application the probability to find the corresponding pointx¢within the hyperbola was increasing with higher values fork², (the region bounded by the hyperbola increases with higher values ofk²), in our application a low value fork²indicates that the probability thatx« ¢x are corresponding points is high and vice versa.

The way to find the value for k², which is actually the Mahalanobis distance k between the estimated epipolar line and the line passing throughx¢with minimalk, is of no rele- vance in applications. This means that in our applications, for a pointx¢, we will only be interested in the Mahalanobis distance of the corresponding linem, not in the line itself.

For the purpose of illustration we generated Fig. 6, where for each pixelx¢we computed the Mahalanobis distancek² according to the minimization problem from equation (7) and represented it using grayscales. In particular, points in white

k² 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 inc 9 [ ( p ) - b r c 9 [ 0 . 1 ( a ) 2 6 s 1 ( l i ) 2 7 e 0 . 1 ( a ) 2 6 s c [ ( t ) 2 6 7 . 8 ( h ) 2 b c 9 [ s 1 ( l i ) 2 7 c [ ( t ) 2 6 . 1 ( l i ) 2 7 m [ ( t ) 5 [ 0 . 1 ( a ) 2 6 c [ ( t ) 2 6 . 1 ( l i ) 2 7 9 . 6 ( o ) 2 6 . 1 ( i t ) - 1 . 6 ( o ) 2 6 3 2 2 ( f ) - c [ ( t ) 2 6 7 . 8 ( h ) 2 f . 1 ( n ) 2 2 5 . 1 6 6 n n a - e ( e q u a 6 ) - 4 3 m a t r - . 7 - 1 ( p ) 2 6 1 . 7 ( w i a 6 ) - 7 2 2 . 8 ( 2 6 ) - 4 3 5 i p o l a 7 ro b f o p o l a 7 r o i n t 6 5 - 2 5 3 . 7 ( i 6 8 - 2 2 7 . 9 ( t h 6 ) - 4 3 5 . 1 ( f o p o 9 ( r ) g ) - 1 ( r ) 3 5 ( o - . 1 . ( a n d ) ] T J 0 . 5 0 0 2 T D - . 0 1 4 4 T T 1 . 1 ( h e 6 - 2 9 7 . 1 ( u 3 - 3 . 4 ( s e 6 - 2 9 2 4 7 ( o f 9 9 [ 0 . ( o f ) - 4 3 8 . 1 ( t ) - h 8 . 7 ( r ) 3 4 s . 9 ( d 7 ( o f 9 9 4 T * [ ( d i s t a n c e 6 - 2 9 0 . 5 ( t f ) - 4 3 e 1 . 9 ( l i m . 4 ( s e 6 - 2 9 2 . 7 ( a ) [ ( o u t s 4 ( s e 6 - 2 1 4 . 8 ( w 6 - 3 . 7 ( i l 5 7 - 2 5 0 . 3 ) 3 4 a ) 0 ( n d ) ] T J T * - . 0 1 3 7 T 8 . 3 ( t 5 7 - 2 . 3 ( t 5 ) - 4 3 e 1 . 9 ( l i m i n a 3 ( t 5 ) - 4 3 2 . 8 ( o ) . 4 t 5 ) - 2 2 9 . 3 ( p ) . 7 ( o i n 4 5 5 - 2 0 4 . 1 - 3 9 5 r t 1 ( i g h 4 6 l ) 2 7 0 w 2 . 5 ( a 5 ) - 2 7 f 9 ( h e r ) 3 4 . 9 ( t 5 ) - 4 3 6 . 8 ( t h 5 5 - 2 0 c 1 ( e r i n i m a l ) ] T J T * - . 0 1 4 4 T c ) . 7 ( o c [ ( , ) - 2 2 7 . 9 ( 4 ) 1 . 7 ( s ) - 5 1 4 . 8 ( w 6 - s c a l e ) - 4 4 7 . 1 ( 6 - 2 . 3 ( o t ) - 2 5 o b s e r v s c a l e ) - 4 4 i . 6 ( s ) . 3 ( o t ) - 2 5 6 . 1 a ) 3 5 ) 7 5 ( i g . ) - 2 2 8 ( i g . e r ) 3 ( b ) e r s a . ) ] T J 1 . 4 9 1 9 3 - 1 . 6 7 9 1 [ ( S . 9 ( p i p o l a 4 9 - 1 9 0 . 5 ( t ) - 1 . 8 2 4 6 t ) - 1 . 4 ( ( ) . 3 p o l a 4 9 - 1 9 a - . 3 ( p p l i c a t i o n s e ) - 3 4 4 . 8 ( w 6 - s c a l 4 4 - 4 4 7 . 1 ( 6 - [ ( w o u e . ) - 7 4 7 . n s ( d i p o l a 4 9 - 1 9 u 3 . 1 ( s i n 4 6 t ) - 6 . 8 ( t ) - 1 . 8 ( h e ) ] T J - 1 . 4 9 1 9 2 0 4 9 7 T D - . 0 1 4 T 2 4 9 ( e p i p o l a 6 ) - 4 3 b c [ ( a n 6 7 9 0 . 5 ( t 6 5 - 2 5 [ ( a r ) 3 4 . 2 ( r r 9 ( t h 6 ) - 2 5 o [ ( o u t s 5 ( i g 6 ) - 2 9 T ) ( T ) - . 1 ( h i 6 ) - 2 9 m . 6 ( d ) - ) - 2 ( e a n 6 ) - 2 9 3 . 7 ( t h a e ) - 2 6 i n s t 4 a ) 0 a n 6 7 9 4 . 9 ( o f 8 ( o r ) ] T J T 7 . 3 ( c o . 1 ( s i n 1 1 - 2 7 0 . 6 ( t ) - 1 . 4 ( h 0 ) - 2 7 2 4 9 ( e p i p o l a 1 4 - 3 2 1 . 7 ( l i h 0 ) - 2 7 c [ ( a n a ) - 3 1 0 . 6 ( t ) - 1 . 4 ( h 0 ) - 6 T * [ ( d i s t a n c 0 ) - 6 T 2 4 7 ( o 1 2 - 3 1 7 . 8 n 1 1 - 3 4 3 . 7 4 p ) . 2 ( o i n s ) - 3 1 t o s i n 1 1 - 2 7 0 h e 0 ( n d ) ] T J T * - . 0 1 3 9 T 2 4 9 ( e p i p o l a ( m ) 5 0 1 . 7 ( i o n s , 2 - 3 1 4 . 8 ( w 1 - s c a l 0 i t ) - j 2 2 ( f 7 ) 2 . 5 ( a l 0 5 - 2 5 7 . 2 ( c ) 2 . 2 ( o m p u t e 2 ( ( ) . 3 ( t h 0 ) - 1 9 2 . 3 ) 2 7 1 9 ( e p i p o l a ( m ) 5 0 3 5 ( o b ) a . 1 ( u n d , 2 - 3 1 c [ ( a n 0 ) - 4 3 p o 9 ( r ) r r 9 ( m a l ) ] T J T * - 2 0 1 4 4 T c ) . 7 ( o o l a 7 ) - 2 5 l o c e n e r a t e 8 0 t ) - 1 . 8 - 2 9 7 t s ( d i o l a 7 ) - 2 5 3 . 5 ( t ) - 1 . 6 ( h 7 ) - 2 5 2 4 9 ( e p i p o l a 8 2 - 2 2 4 . n f i n e d 7 8 9 T ) 0 ) - . 1 ( h i 7 ) - 2 5 2 9 7 ( w ) - [ ( w o u e 8 0 t ) - 2 . 2 ( r ) 3 4 . 7 ( e ) 1 o l r 9 ( m a l ) ] T J T * - . 0 1 3 5 T 6 . 8 ( t h 0 8 ) 2 7 1 . - 2 4 7 . 9 ( r ) - 1 . - 2 2 4 9 ( o b l 4 1 1 - 3 4 4 . 9 l 4 1 1 - 3 4 7 . 9 ( r ) - e 5 ( o b ) r r . 1 ( s i 4 1 l ) 2 7 c ) . 7 ( o o l h 0 8 ) 2 7 f 9 ( h e r 4 3 4 . 9 ( t 1 1 - 3 4 6 . 8 ( t h 0 8 ) 2 7 3 5 ( o ( e ) . k g 7 . 9 ( r ) - 1 . - 2 2 - . 1 . ( t h 0 8 ) 6 ( A l . 1 ( a ) T j - 2 0 . 4 8 9 1 . 0 0 0 1 T D 0 T c ( - ) T j - 2 5 1 7 7 3 6 1 9 - 9 0 4 9 7 T D - . 0 1 4 T t h 4 . 9 ( o - 2 9 8 - 2 0 3 . a n o b i s 6 - 1 9 a - . 3 ( p p l i c a o b i s 9 ( i ) 1 . 2 ( b ) 1 e m n o b i s 6 - 1 9 1 . 2 ( b ) u i t a 4 9 ( , o b i s 6 - 9 ( t 4 . 3 ( w ) - o o - 2 9 8 - 4 4 3 . 7 4 p a r a m e t u t s 4 ( s s 6 - 1 9 h . 9 ( a ) a v e ( a n d ) ] T J 0 . 5 0 0 2 . 2 2 2 8 2 5 5 2 T c [ 9 ( r ) - 1 . - - 2 5 1 . 2 3 9 - 2 6 2 . 2 ( i ) 1 . 2 3 8 ) 5 0 7 . 7 3 ) - 4 3 6 [ 9 ( r ) - . ) c 9 [ F ) a s ) - 2 1 2 . 5 3 ) - 3 5 8 . 2 3 3 - 3 9 4 . 8 3 ) - 3 5 t 4 . 2 e ) - 4 3 e 7 . 8 3 6 ) 5 [ 0 . 1 d ) - 4 3 v . 1 d ) - 2 9 e c [ 9 ( r ) - 1 m [ 9 ( r 1 [ 0 . 1 d ) - 4 3 k 9 4 ( n ) 5 7 e 0 . 1 d ) - 4 3 n 0 . 1 d ) - 4 3 4 . 8 3 ) - 3 5 4 . 8 3 ) - 3 5 u . 2 e ) - 9 ( m [ 9 ( r 1 [ 1 . 1 3 7 f ) - c [ 9 ( r ) - 2 . 5 3 ) - 3 5 o . 1 d ) - 9 5 0 . 8 ( n 5 [ 0 . 1 d ) - 4 3 1 . 2 3 9 - 2 6 o . 1 d ) - 9 5 u . 2 e ) - 9 ( t c [ 9 ( r ) - 7 . 8 3 6 ) ) 3 4 . 6 ( e ) v . 1 d ) - 2 9 0 . 1 d ) - 4 3 8 . 2 3 3 - 3 9 2 . 5 3 ) - 3 5 - t i v e ) ] T J T * - . 0 1 4 1 T d i s t a n c e p r ) 3 4 f 4 ( s e ) - 2 5 3 . 6 ( t h e p r ) 3 p . 6 ( E ) . 2 ( o i n t ) - 2 2 0 . 1 ( c o r ) - 2 2 . 1 ( r ) 3 4 . 8 ( e s p o n d o c [ ( , 4 - 2 2 7 . 9 ( 1 ) - . 2 ( n d 7 - 2 0 3 . 6 ( t h e p r ) 3 v 2 2 ( f 7 ) . 8 ( v a l u . e r ) 3 3 . 6 ( f o r ) ] T J / F 1 1 1 o r ) 7 6 8 6 5 6 7 9 0 T D 0 T c ( k ) T j / F 2 1 T f 7 . 5 9 9 8 0 0 7 . 5 5 2 6 ) 5 t 1 1 4 6 ) - 2 4 2 . 3 2 6 6 T m ( 2 ) T j 9 . 4 9 9 9 0 0 9 . 4 5 3 3 - 0 3 5 5 4 6 l ) 4 4 6 . 0 7 0 5 T m - . 0 1 3 5 T f 9 ( h e r 4 3 4 . 9 9 ( e ) ] T 9 8 7 7 9 T J 0 . 5 0 0 2 . 2 8 - . 0 1 4 T w . 5 ( o ) 2 9 7 . 8 9 e r ) 3 5 . ( t ) - ( o ) . 3 3 F ) 1 0 e w . 5 ( o ) 2 9 e c . ( t ) - ( o o . 8 9 e r 5 ( m [ 9 ) - 3 4 3 . 2 s ) - 3 9 5 . ( a p ) 2 9 t . 2 ( i ) 4 . 6 9 t . 2 ( i ) 7 . 8 9 e r 1 ) 2 6 9 ( 9 m ) 5 0 7 . 2 s ) - 3 9 i 9 ( 9 m ) 3 0 7 . 2 s ) - 3 9 o . 8 9 e r 5 ( 1 . 1 9 9 1 9 0 . 1 9 5 3 ( o ) . 4 4 ) 2 7 3 5 ( 9 ) - 3 1 7 . 1 9 5 3 ( o 2 9 4 ( ) - 2 9 d 2 9 4 ( ) - 2 9 6 9 ( 9 m ) 5 0 6 9 ( 9 m ) 5 0 d 9 4 ( ) - 2 9 s t . 2 ( i ) o 3 5 ( 9 ) - 3 1 e s 9 ( 9 m ) 3 0 6 9 ( 9 m ) 5 0 t . 2 ( i ) . I [ 9 ) - 3 4 n t . 2 ( i ) 7 . 8 9 e r 1 ) 2 l i n e ) ] T J T * - . 0 1 4 T f o l c [ ( l ) - 3 1 3 . 2 ( b ) 1 ( s i ( t w ) 4 8 4 . 3 ( w ) - e s i ( t ) - 4 3 3 . 5 ( p r 9 3 5 . 1 ( e s i ( t ) - 2 0 6 . 0 5 0 . 8 ( t ) - 7 0 6 . 0 5 - . 2 ( l g o r . 8 ( t 7 f ) - r 9 . 5 ( p r 9 3 7 . 3 i 1 ( s i ( t w ) 4 8 3 . 6 ( t ( t ) - 4 3 d . 5 ( f ) - 1 a 4 . 3 ( w ) - - 8 ( o r ) ] T J T b ) . k s a g e . ) - 6 9 4 . 9 ( o f 8 s e d ) - 7 1 0 . 6 ( t ) - 1 . 4 ( e . ) - ) - 3 . [ ( l g o r i t h e . ) - 6 9 m . 6 ( d ) - ) n l i c a . 5 ( s e d ) - 3 1 7 b r 9 ( t e . ) - ) - 3 5 ( o 4 ( b ) 2 ( h ) - 2 5 u . 3 ( w ) - s p o n d i n g 7 ) 2 9 2 . - 2 9 7 r u t e d ) - 3 5 2 . 9 ( m a l ) ] T J T * - 8 2 5 5 2 5 7 . 6 ( c r i n a t i ( k ) T 3 / F 1 1 1 0 1 3 7 9 9 9 8 0 1 0 1 3 7 9 9 9 8 3 0 6 . 1 3 m ) - 1 4 2 4 6 0 0 6 T m 0 T . 1 A - . 2 ( l g o r . v a l ) T j / F 2 1 T f 9 . 4 9 9 9 0 0 9 . 4 9 9 9 3 2 0 . 3 7 8 ) 2 0 7 7 3 2 6 6 T m - . 0 1 4 T T 1 . 1 ( ( o ) - 1 3 v 2 2 ( f 6 - 3 . 5 ( a l u ( o ) - 3 5 7 . 2 ( h o s e a t i o n 3 - 4 3 5 . 4 ( f ( f o p o l 1 9 e r ) 3 t 1 . 1 ( ( o ) - 1 3 1 . 2 ( b ) ( d i d a a c c o r ) 3 4 . 9 ( n 3 - 4 3 d e v i p l i c a o i t y ) ] T J / F 4 1 9 4 1 6 . 4 2 3 1 0 T D 0 T D ( ) T j / F 2 1 7 0 3 7 5 2 7 4 0 T D - . 0 1 4 6 T 4 f 4 ( ( m ) - 8 7 c ) . 7 ( o o l 1 8 9 - 2 2 8 . 8 9 ( e ) ] T 0 . 1 6 8 T J 0 . 5 0 0 2 T 7 . 3 ( c o 8 ( t h 0 3 4 8 . 2 ( t ) - 1 ( h 0 3 4 c o v a r i d i s t a n h 0 3 4 m a t r - . 7 - 4 0 ) - 2 4 7 ( 4 0 6 - 2 2 5 . 1 ( t h 0 3 4 f . 6 ( p ) - . 1 a m 1 ( e ( e q u 4 - b r ) 3 m a t r - . 7 m a l ) ] T J T * - 1 . 0 1 4 T c [ ( 5 - 2 8 3 . - 2 9 8 - 5 3 3 . 6 ( v 7 0 6 r y p o n , o b i s 2 0 6 . ( b ) 1 5 ( s e 0 3 ( i ) 1 . u s . - 2 9 8 - 6 5 6 . 1 ( w 9 8 - 5 3 f 2 . 2 ( i s e 0 3 ( 9 5 7 . 2 ( 9 ( . 3 ( c o m p u t e 0 ) - 2 7 1 . 8 t ) - 1 . 5 ( h 9 8 - 5 3 3 . 8 ( v a f o r ) ] T J / F 1 1 1 o ( t ) 8 3 4 5 6 7 9 0 T D 0 T c ( k ) T j / F 2 1 T f 7 . 5 9 9 8 0 0 7 . 5 5 1 6 - 2 3 2 4 6 n g ) - 2 0 7 . 3 2 6 6 T m ( 2 ) T j 9 . 4 9 9 9 0 0 9 . 4 5 T 9 8 1 5 4 . 1 3 5 5 - 3 0 7 . 0 7 0 5 T m 5 0 1 4 6 T 4 f 4 ( 3 t ) - 4 3 e 2 . 2 ( r s t ) ] T J 8 4 7 8 4 9 1 9 2 0 4 9 7 T D - . 0 1 4 3 T u 6 ( b a s e 3 9 - 3 2 0 . 8 ( p o i n 4 0 4 7 . 1 ( 7 ( [ ( c o r ) - 2 2 . 3 ( r ) 3 4 . 2 ( i ) 1 8 ( e s p o n d i n e d 3 7 ( I f a s e 3 9 - 3 4 3 . 7 ( w ) - . 5 ( h 3 6 ) ) 3 7 . n s ( d i p o l a 4 1 - 2 5 3 . 6 ( t h 3 6 ) ) 3 d . 4 ( f ) - 1 s t r - b u l i c a o b i 3 9 - 3 2 o f 7 m a l ) ] T J T * 2 . 0 1 3 9 T c [ ( t h 0 5 - 1 3 v 2 2 1 v ) - 3 . 5 ( a f o r ) ] T J / F 1 1 1 ) - 2 n g 7 5 6 7 9 0 T D 0 T c ( k ) T j / F 2 1 T f 7 . 5 9 9 8 0 0 7 . 5 e d ) - 4 7 2 2 3 3 6 ) 3 0 7 4 5 7 2 7 T m ( 2 ) T j 9 . 4 9 9 9 0 0 9 . 4 9 d 7 - 7 2 . 4 3 3 p ) 2 0 . 2 5 m J T * - . 0 1 4 T f o r 3 ( a s ) - 2 9 6 9 ( e ) . 9 ( a c 0 8 - 4 4 3 . 7 4 p . 8 ( p o i 3 0 ) - 6 T 3 . 2 ( i 0 9 9 4 T 6 . 1 a ) 7 1 3 . 2 ( b ) 7 5 ( i 3 t ) - 7 0 7 , ( i 3 t ) - 7 0 c [ ( w o r ) 3 0 s e [ ( w o r ) 3 0 0 . 6 ( t ) - 1 a p o i 3 0 ) - 6 T m . 6 ( d ) - o s p o i 3 0 ) - 6 T 4 . 9 ( o f 8 s e ( T ) 5 0 0 . 6 ( t ) - 1 . 4 r s t ) ] w ) 4 0 5 . 4 9 1 9 2 0 4 9 7 T D - 5 0 1 4 2 T c [ ( c o r ) 5 ( ( n t e r ) 3 4 . 8 ( e s p o n d o q u 4 1 a ) 7 1 a ( n t e r ) 3 4 q u 4 1 a ) 6 1 8 . 1 ( v 1 ) 2 o m e t 4 7 9 ( a ) - . ( t ) - m a l l c [ ( 7 5 . ) - 2 9 1 ( w ) - h . 6 ( p ) 4 ( n t e r ) 3 4 a o q u 4 1 a ) 7 1 - . ( t ) - o m 4 q u 4 1 a ) 6 1 c . 6 ( s ) [ ( c o r ) 5 ( ( n t e r ) 3 4 . 6 ( s ) . 8 ( e . 1 ( a ) T j - 2 0 . 4 1 4 3 . 0 0 0 2 T D 0 T c ( - ) T j - 2 5 1 7 7 3 6 2 - 1 . 5 0 0 2 T D - . 0 1 3 8 T s p o n d o q u n g ) - 2 2 c [ ( h a v e ) - 1 u g ( a f o r ) ] T J / F 1 1 1 7 - 2 4 6 . 7 4 4 2 0 T D 0 T c ( k ) T j / F 2 1 T f 7 . 5 9 9 8 0 0 7 . 5 3 e ) - 2 2 5 . 6 ) , ) - 2 0 . 2 5 m J T m ( 2 ) T j 9 . 4 9 9 9 0 0 9 . 4 9 o ) - 0 5 7 4 5 e ( T ) 7 0 6 . 2 6 7 2 T * - . 0 1 4 1 T c [ ( v a . q u n g ) - 8 ( A o b i 3 ) - 2 9 c l . 9 ( p f ( p p l i c a o b i 2 ) - 6 T 4 . 1 ( o ) 0 ( 2 9 - 4 4 i . 6 ( 4 3 n ( o u t s 4 ( s 2 6 t ) - c [ ( a n 2 ) - 6 T 4 . 1 ( u 5 ( u s t ) 1 6 - 7 9 2 8 4 1 4 3 . 0 0 0 2 T D 0 T c ( - ) T j - 2 5 1 7 7 3 6 2 - 1 . 5 0 0 2 T D - . 0 1 4 3 T ( o u t s 4 ( s e ) - 4 4 7 . 1 ( 7 - 2 . 3 ( o t ) - 6 2 2 . 8 ( 2 e ) - 2 5 4 a o i . 4 ( n l 5 5 4 3 . 7 ( p e r f o r m e d e v e l . ) ] T 8 / F 2 1 T 9 7 . 5 9 9 8 0 9 7 . 5 9 9 9 4 2 . 4 8 5 1 9 6 1 6 0 0 6 T m 0 ' C z e c h T e c h n ( p p l U n i 0 . 2 ( i t y P u b l i s h p o n H o u 6 ( c ( - 0 . 5 8 4 - 1 . . 8 . 1 2 5 4 9 T 9 8 6 0 0 . 3 1 0 5 0 h t t p : / / c t n . c v u t . c z / a p / c ( - E T 6 T m / C S 0 . 5 8 4 - 1 . . 8 . 1 2 S C N - 0 J 0 j . 5 3 2 w ( f 6 1 3 M [ ] 0 d 1 i q 1 9 9 9 8 0 i 3 ) - f . 7 4 J - 1 8 c m 9 9 9 8 m w ) - 2 3 . 3 1 0 l S Q 2 g s ) T j 9 . 4 9 9 9 0 0 9 . 4 5 9 9 1 5 5 8 4 8 5 1 9 6 1 6 0 0 6 c s . 1 3 7 2 5 . 1 2 1 5 7 . 1 2 5 4 9 ( 2 7 D ( . ) T 6 4 - 1 7 8 2 2 1 . 6 7 9 1 [ ( A c t a ( a n d ) - 3 ( P o l y t e c h n ( p p ( t h 6 ) - 2 5 V o l . g 7 5 N o . g 5 / 2 - 1 7 v e l . ) E T 6 c s . 1 3 7 2 5 . 1 2 1 5 7 . 1 2 S C N - f 1 7 w q 1 9 9 9 8 0 9 9 9 4 2 7 8 8 . - . 0 c m 9 9 9 8 m 5 9 8 3 2 . 7 7 3 l S Q 2 q 9 9 9 4 2 6 1 5 - 2 n g m 9 9 9 4 2 7 6 9 - 3 7 9 T l ) 1 6 4 . s . 7 6 9 - 3 7 9 T l ) 1 6 4 . s . 6 1 5 - 2 n g l 9 9 9 4 2 6 1 5 - 2 n g l W n 2 q 2 5 . - 1 . 5 9 9 8 - 1 5 4 . 6 4 6 9 9 9 4 2 7 6 9 - 3 7 9 T c m / I m 8 D o Q 2 Q 2 q 1 e ) - 2 5 . 6 6 1 5 - 2 n g m 1 e ) - 2 5 . 6 7 6 9 - 3 7 9 T l ) 2 8 9 - 0 9 . 6 7 6 9 - 3 7 9 T l ) 2 8 9 - 0 9 . 6 6 1 5 - 2 n g l 1 e ) - 2 5 . 6 6 1 5 - 2 n g l W n 2 q 2 5 . - 1 . 5 9 9 8 - 1 5 4 . 6 4 6 1 e ) - 2 5 . 6 7 6 9 - 3 7 9 T c m / I m 1 0 D o Q 2 Q 2 g s 8 0 9 . 5 9 9 8 8 0 9 . 5 9 9 9 4 2 . 4 6 0 ) - 4 0 3 4 5 7 2 7 1 4 3 7 - . 0 1 4 T F ) 7 5 ( i g 8 ) - 4 3 6 : ( i g 8 6 ) 5 [ I . 4 4 ) 2 0 3 . 7 ( v ) - 3 6 ( a n g e 5 ( ( n 8 ( t ) - e p r 5 . 1 ( e s i a ) 3 5 ) o n d i n g 6 ) 5 0 0 . 6 4 t ) - 1 . 3 ( h e 5 ( 0 . 6 ( M [ ( M ) - 4 ( 3 ( h a l a n o b i s 6 - 3 1 2 . ( d ) - 1 s 0 . 6 4 t ) - ) - 4 ( 3 ( h s t a n c e ) ] T J / F 9 1 2 4 t ) 5 5 . 7 4 4 2 0 T D 0 T c ( k ) T 8 / F 7 1 T 7 9 . 4 9 9 9 T 7 9 . 4 ( , ) - 2 9 3 2 6 9 9 4 0 3 4 5 7 2 7 T m ( 2 8 0 9 . 5 9 9 8 8 0 9 . 5 e d ) - - 5 0 6 0 ) - 4 0 3 4 5 7 2 7 1 4 3 6 . 0 1 3 9 T r 9 . 5 b i s 9 - 2 . 3 r s t ) ] T J n d ) T J 0 . 5 0 0 2 . 0 0 8 5 0 1 4 4 T c [ ( i : ( i 5 t ) - 2 2 T h ) 3 W ) 7 6 . 3 5 5 - 2 2 . 6 ( p ) - g h ) 3 W ) 7 e s i ( g ) - 2 5 3 9 8 ( i m a 5 5 - 2 6 . 6 ( s ) h ) 3 W ) 7 o . 6 ( s ) w s m a 5 5 4 ( i ) 1 . 3 3 W ) 7 6 . 3 5 5 - 2 8 ( a t e ) p ) ) - 3 1 3 . 8 ( t ) - p ) ) - 3 1 o . 6 ( s ) p i p o l 5 a ) - 3 5 b . 7 ( v ) - 3 [ ( a 5 t ) - 6 2 3 2 2 ( f ) - . 6 ( f o r ) ] T J / F 9 1 . 0 7 7 T J 0 . 4 2 . 3 2 0 T D 0 T c ( k ) T 8 / F 7 1 T 7 8 1 2 4 9 9 9 T 7 8 1 2 4 7 5 1 9 2 . 4 5 e ) - 4 2 0 4 5 7 2 7 T m ( 2 8 0 9 . 5 9 9 8 8 0 9 . 5 8 9 - 5 8 1 6 5 7 8 6 2 2 1 5 7 2 7 1 4 - . 0 1 3 5 T 5 5 b i ( v 1 ) 9 9 1 9 ( e l ) ] T J / F 7 1 - . 8 1 8 . 6 8 2 3 0 T D 0 c ( k ) T 8 / F 7 1 ) - 2 5 7 4 3 5 7 0 T D ( . 1 ( 7 ) , ) 4 1 4 3 4 5 0 0 2 . 2 4 - . 0 1 3 4 T . I [ 3 ( f ) - n t . 2 3 ) - 3 4 1 . 5 3 ) - 2 6 2 . 2 ( 1 . 1 3 2 9 6 9 ( 3 7 ) 1 1 2 . ( n ) - 7 1 0 . 6 2 1 2 . 5 3 3 ( m [ 9 3 n 5 [ 0 . 1 d ) - 2 9 5 . h 3 6 ) 4 0 e w . 5 ( 5 - 2 8 3 c 9 ( 3 7 ) 1 6 o . 1 d ) - 4 ( m [ 9 3 n 5 [ p . 5 3 ) - 2 2 5 . 1 3 ( f ) - t . 2 3 ) - 3 4 6 9 ( 3 7 ) 1 1 d 2 . ( n ) - 7 1 o . 1 d ) - 4 ( r . 7 ( v ) - 6 9 ( 3 7 ) 1 1 0 . 1 d ) - 2 9 c 9 ( 3 7 ) 1 6 h . ( t ) - p . 5 3 x . 1 d 3 7 e l

(6)

Our proposition is to compute the median value ofk². 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 median value fork²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 eliminate 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 deviations 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 criterion. 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 fundamental matrices computed from the initial set of point correspondences 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 correspondences 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 5^th 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 7^thInternational 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

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 correspondence set using the new criterion. INRIA Syntim owns the copyright of the image pair.