the fundamental matrix theory algorithms and stability analysis(2004)

the fundamental matrix theory algorithms and stability analysis(2004)

The Fundamental matrix: theory, algorithms, and stability analysisQ.-T. Luong and O.D. Faugeras I.N.R.I.A. 2004 route des Lucioles, B.P. 93 06902 Sophia-Antipolis, France luong,faugeras@sophia.inria.frAbstract

In this paper we analyze in some detail the geometry of a pair of cameras, i.e. a stereo rig. Contrarily to what has been done in the past and is still done currently, for example in stereo or motion analysis, we do not assume that the intrinsic parameters of the cameras are known (coordinates of the principal points, pixels aspect ratio and focal lengths). This is important for two reasons. First, it is more realistic in applications where these parameters may vary according to the task (active vision). Second, the general case considered here, captures all the relevant information that is necessary for establishing correspondences between two pairs of images. This information is fundamentally projective and is hidden in a confusing manner in the commonly used formalism of the Essential matrix introduced by Longuet-Higgins 40]. This paper clari es the projective nature of the correspondence problem in stereo and shows that the epipolar geometry can be summarized in one 3 3 matrix of rank 2 which we propose to call the Fundamental matrix. After this theoretical analysis, we embark on the task of estimating the Fundamental matrix from point correspondences, a task which is of practical importance. We analyze theoretically, and compare experimentally using synthetic and real data, several methods of estimation. The problem of the stability of the estimation is studied from two complementary viewpoints. First we show that there is an interesting relationship between the Fundamental matrix and threedimensional planes which induce homographies between the images and create unstabilities in the estimation procedures. Second, we point to a deep relation between the unstability of the estimation procedure and the presence in the scene of so-called critical surfaces which have been studied in the context of motion analysis. Finally we conclude by stressing the fact that we believe that the Fundamental matrix will play a crucial role in future applications of three-dimensional Computer Vision by greatly increasing its versatility, robustness and hence applicability to real di cult problems.

1 IntroductionInferring three-dimensional information from images taken from di erent viewpoints is a central problem in computer vision. However, as the measured data in images are just pixel coordinates, there are only two approaches that can be used in order to perform this task: The rst one is to establish a model which relates pixel coordinates to 3D coordinates, and to compute the parameters of such a model. This is done by camera calibration 73] 20], which~ typically computes the 3 4 projection matrices P, which relate the image pixel coordinates to a world reference frame. The 11 parameters of this projection matrix account for the internal geometry

of the camera, as well as its position and orientation in space with respect to apresent address: EECS, University of California, Berkeley CA 94720, e-mail: qtluong@robotics.eecs.berkeley.edu

the fundamental matrix theory algorithms and stability analysis(2004)

xed reference frame. The knowledge of the internal geometry of a camera allows us to obtain directions in 3D space from pixel measurements, and thus the usual Euclidean concepts can be used: the relative positioning of cameras is described by a rigid displacement, and the world is described by metric quantities. However, it is not always possible to assume that cameras can be calibrated o -line, particularly when using active vision systems. Another drawback is that by doing so, many parameters have to be estimated in the case of a stereo rig, namely 11+ 11 which in our opinion is much more than what is really needed in most applications. Even an approach where cameras are just calibrated individually for their 5 internal parameters, and the rigid displacement between them is estimated subsequently would require at least the estimation of 15 parameters. Thus a second approach is emerging 55], which consists in using projective information, whose non-metric nature allows to use cameras whose internal parameters are unknown, This approach requires only geometric information which relates the di erent viewpoints, thus a much more small number of parameters have to be estimated. They also lead to a deeper understanding of the fundamental elements in the geometry of two cameras, being very naturally related to the image formation process. The geometric relations between the two cameras are described in projective terms rather than in Euclidean ones. We will see in this paper that only 7 parameters are su cient to describe the projective relation of two cameras. This information is entirely contained in a matrix called the Fundamental matrix, thus it is very important to develop precise techniques to compute it, and to study their stability with respect to various 3D point con gurations and di erent camera displacements. In spite of the fact that there has been some confusion between the Fundamental matrix and Longuet-Higgins' Essential matrix, it is now known that the fundamental matrix can be computed from pixel coordinates of corresponding points in uncalibrated images, which is the basic data we start from, in this paper. Methods to obtain such correspondences at a subpixel precision are now available, but are detailed elsewhere 42, 10, 10], since the emphasis of the paper is on geometric and algebraic relations which can be used to compute the fundamental matrix and to analyze its stability. Line correspondences are not su cient with two views. Another approach is to use linear lters tuned to a range of orientations and scales. Jones and Malik 32] have shown that it is also possible in this framework to recover the location of epipolar lines. In section 2, we clarify the concept of Fundamental matrix, and show its relation with the epipolar transforma

tion and the Essential matrix, and propose some parameterizations for its computation. In section 3, we proceed to analyze several methods to compute the Fundamental matrix in the general case and show, using both large sets of simulations and real data, that our non-linear computation techniques provide signi cant improvement in the accuracy of the Fundamental matrix determination over linear techniques. In section 4 we examine the case of planes, and point out an important relation between the Fundamental matrix and homography matrices, which yield unstability, but allows some new speci c algorithms to be applied. The stability of the computation is investigated in a more general framework where the in uence of the camera motion is also considered in section 5. We end the paper by pointing to several applications of the Fundamental matrix in order to stress its importance in computer vision.

In this paper we use boldface letters for vectors and matrixes i.e. x. Transposition of vectors and matrices is indicated by T, i.e. xT . The line between two points M1 and M2 is represented by hM1; M2 i. The cross-product of two three-dimensional vector x and y is represented by x y. The antisymmetric matrix such that v] x= v x for all vectors x is noted v] . We di erenciate between the projective geometric objects themselves and their representations. For example, a point in the image plane will be denoted by m whereas one of its coordinate vectors

2.1 Notations

2 The Fundamental Matrix

the fundamental matrix theory algorithms and stability analysis(2004)

will be denoted by m.

2.2 The projective model

The camera model which we consider is the pinhole model. In this model, the camera performs a perspective projection of an object point M onto a pixel m in the retinal plane through the optical center C. The optical axis is the line going through C and perpendicular to the retinal plane. It pierces that plane at point c. If we consider an orthonormal system of coordinates in the retinal plane, which we call normalized coordinates, centered at c, say (c; u; v) we can de ne a three-dimensional orthonormal system of coordinates centered at the optical center C with two axes of coordinates parallel to the retinal ones and the third one parallel to the optical axis (C; x; y; z). In these two systems of coordinates, the relationship between the coordinates of m, image of M is particularly simple: y u= x v= z z It is nonlinear but if we write it using the homogeneous (projective) coordinates of m and M, it becomes linear: 2 U 3 2 1 0 0 0 32 X 3 6Z7 4 V 5= 4 0 1 0 0 56 Y 7 (1) 4 5 0 0 1 0 S T In this equation U; V and T are the projective coordinates of the pixel m and X; Y; Z; T are the projective coordinates of the point M. If M is not at in nity (i.e. T 6= 0), its Euclidean Z coordinates are x= X; y= Y; z= T . Therefore, x; y and z can also be considered as the T T projective coordinates of the pixel m. We write equation (1) in matrix form:

~ where P is the 3 4 matrix appearing in (1). Introducing projective coo

rdinates induces a big simpli cation in the formulation of properties of cameras. It is one of the reasons why projective geometry is emerging as an attractive framework for computer vision 55]. In this paper, we assume that the reader is familiar with some elementary projective geometry. Such material can be found in classical mathematic textbooks such as 65, 6, 21], but also in the computer vision literature where it is presented in chapters of recent books 14, 34, 55], and articles 51, 33]. The main property of this camera model is thus that the relationship between the world coordinates and the pixel coordinates is linear projective. This property is independent of the choice of the coordinate systems in the retinal plane or in the three-dimensional space. Changing~ projective coordinates in the 3-D space is equivalent to multiplying matrix P to the right by a 0, then m= PDM0. A special~ four by four matrix. Indeed, suppose that we have M= DM case is the case of a rigid displacement represented by a rotation matrix R and a translation vector t. We have then t D= R 1 0 Similarly, changing coordinates in the retinal plane is equivalent to multiplying matrix P to the~ left by a three by three matrix. Indeed, suppose that we have m= Am0, then m0= A?1 PM. A special case is the case where the change of coordinates represents the change from the pixel coordinates to the normalized pixel coordinates 16, 14], accounting for the internal geometry of~ the camera. A pinhole camera can therefore be speci ed by a 3 4 matrix P which is de ned up to a scale factor (it is a projective quantity) and is of rank 3 (an easy way is to see that this is the case for the matrix appearing in (1) and that this rank property is preserved by multiplication on the right with matrixes of rank 4 and multiplication on the left with matrixes of rank 3).3

~ m= PM

the fundamental matrix theory algorithms and stability analysis(2004)

Since this will be used in what follows, let us now see how the optical center C can be~~ recovered from the matrix P. Let us decompose P as follows

~ P= Pp where P is a 3 3 matrix of rank 3 and p is a 3 1 vector. Let us assume without loss of~ generality that C is not at in nity and let C= CT 1]T be a projective representation of this point. C is its 3 1 Euclidean vector of coordinates and the component equal to 1 accounts for~~ the fact that C is not at in nity. C satis es the equation PC= 0 from which we conclude C=?P?1pWe now consider the case of two cameras looking at the same scene. The epipolar geometry is the basic constraint which arises from the existence of two viewpoints. Let us consider two images taken by linear projection from two di erent locations, as shown in gure 1. Let C be the optical center of the rst camera, and let C 0 be the optical center of the 0second camera. The line hC; C 0i projects to a point e in the rst image R, and to a point e in the second image R0 0. The points e, e0 are the epipoles. The lines through e in the rst image and the lines through e in the sec

ond image are the epipolar lines. The epipolar constraint is well-known in stereovision: for each point m in the rst retina, its corresponding point m0 lies on its epipolar 0 line lm . Similarly, for a given point m0 in the second retina, its corresponding point m lies on 0 its epipolar line lm0 . lm and lm0 are called corresponding epipolar lines.

2.3 The epipolar geometry and the Fundamental matrix

ΠM e’ e m lm’ C C’ l’m m’

R

R’

Figure 1: The epipolar geometryThe relationship between the retinal coordinates of a point m and its corresponding epipolar 0 line lm is projective linear, because the relations between m and hC; mi, and hC; mi and its 0 projection lm are both projective linear. We call the 3 3 matrix F which describes this correspondence the Fundamental matrix. The importance of the Fundamental matrix has been neglected in the literature, as almost all the work on motion and stereo has been done under the assumption that intrinsic parameters are known. In that case, the Fundamental matrix reduces to an Essential matrix. But if one wants to proceed only from image measurements, the Fundamental matrix is the key concept, as it contains all the geometrical information relating two di erent images. One way to see it is to remember that the position along epipolar lines are related to the three-dimensional depth 61]. But if we do not have any knowledge about the scene geometry, we cannot infer such information.

the fundamental matrix theory algorithms and stability analysis(2004)

Let us now express the epipolar constraint using the Fundamental matrix, in the case of uncalibrated cameras. For a given point m in the rst image, the projective representation l0m of its the epipolar line in the second image is given by0 Since the point m0 corresponding to m belongs to the line lm by de nition, it follows that:

l0m= Fm

m0T Fm= 0

(2)

Note that by reversing the role of the two images, the Fundamental matrix is changed to its transpose. Indeed, transposing equation (2), we obtain

mT FT m0= 0this shows that the epipolar line lm0 of m0 is represented by FT m. Just as in the one-camera case where we related the optical center to the perspective pro~ jection P, in the two-cameras case, we can also relate the fundamental matrix F to the two~~ perspective projection matrices P and P. The epipole in the second image is the projection of the optical center of the rst camera into the second camera, thus:?1~ e0= P0?P1 p= p0? P0P?1p

(3)

The epipolar line of a point m of the rst retina is de ned by the image from the second camera of two particular points of the optical ray hC; M i: the optical center C (which is projected to the epipole e0 ) and the point of in nity of hC; M i. This point is projected to:?1~ P0 P 0 m= P0P?1m 0 The projective representation of the epipolar line lm is obtained by taking the cross-product of these two points, and it is seen again that this expression is linear in m:

l0m= p0? P0P?1p] P0P?1 m=|p0? P0P?1 p] P0P?1 m{z} F

(4)

2.4 Projective inter

pretation: Relation with the epipolar transformationLet us enrich the idea of epipolar geometry and consider the one parameter family of planes going through hC; C 0i as shown in gure 2. This family is a pencil of planes. Let be any plane containing hC; C 0i. Then projects to an epipolar line l in the 0rst image and to an epipolar line l0 in the second image. The correspondences^ l and^ l are homographies1 between the two pencils of epipolar lines and the pencil of planes containing hC; C 0i. It follows that the correspondence l^ l0 is a homography, called the epipolar transformation. We relate it to the Fundamental matrix as follows. We prove the following interesting property of the fundamental matrix. The fundamental matrix is such that Fe= FT e0= 0 0 Indeed, the epipolar line of the epipole e is Fe. Geometrically, this line le is the image of the optical ray hC; ei in the second image. By construction this line is reduced to a point, e0 . This implies that l0e= Fe= 0. Same for the second epipole.1

It can be seen that by construction they preserve the cross-ratio.

the fundamental matrix theory algorithms and stability analysis(2004)

Figure 2: The epipolar pencils.As a consequence of this, the rank of F is less than or equal to 2. In general, that rank is equal to 2. The case where it is equal to 1 is not possible since it can be seen that it implies that the line hC; C 0i belongs to the two retinal planes and hence to their intersection. If we note lT; i= 1; 2; 3 the row vectors of F and ci its column vectors, it means that we can write e (resp. i e0) as li lj (resp. ci cj ) if li and lj (resp. ci and cj ) are linearly independent. We now nd a parameterization of the pencils of epipolar lines such that the epipolar correspondence has a simple form. One solution, valid in the practical case where epipoles are at nite distance, and illustrated in gure 3, consists in intersecting each epipolar line in each retinal plane with the line at in nity l1 of that plane; these lines consist of retinal points for which the third projective component is zero. Their equation is x3= 0 and their projective representation is (0; 0; 1)T . The epipolar transformation can then be expressed as a collineation between these two lines. If the epipolar line l goes through the point q, then its intersection with the line at in nity is y1= (e q) (0; 0; 1)T, which can be written as (1;; 0)T, with: q?e= q2? e2 (5) 1 1 Note that is the direction of the epipolar line l. Since the epipole is at nite distance, thus not on l1, it is an appropriate parameterization. If q0 corresponds to q, then the epipolar line l0 of the second image going through q0 corresponds to l. It is parameterized by the point 0 y1= (1; 0; 0)T, with its projective parameter obtained by priming the quantities in (5). The 0 epipolar transformation maps y1 to y1, and thus is a homographic function of the projective parameters: a+b (6) 7! 0= c+ d Thus we can characterize the epipolar transformation by the four coordinates of the two epipoles e

and e0 and by the three coe cients of the homography. It follows that the epipolar transformation, like the Fundamental matrix depends on seven independent parameters. Replacing and 0 by their values (5) in (6) and identifying the result with equation (2), we obtain expressions for the coe cients of F in terms of the parameters describing the epipoles and the homography: 2 be e0 3 ae3e03?ae2 e03? be1e03 3 3 5 F= 4?de03e3?ce03 e3 ce03 e2+ de03 e1 (7) de02e3? be3 e01 ce02 e3? ae3 e01?ce02 e2? de02 e1+ ae2 e01+ be1 e01

the fundamental matrix theory algorithms and stability analysis(2004)

h

the fundamental matrix theory algorithms and stability analysis(2004)

only, the three parameters of the 3-D rotation, and the two parameters de ning the direction of translation. It can be seen that the equation (9) is a special case of (2). Since normalized coordinates (used in (9)) are obtained from pixel coordinates (used in (2)) by a multiplication by the inverse of the intrinsic parameters matrix A, we have the relation: F= A?1T EA?1 (10) Unlike the essential matrix, which is characterized by the two constraints found by Huang and Faugeras 30] which are the nullity of the determinant and the equality of the two non-zero singular values, the only property of the Fund

amental matrix is that it is of rank two. As it is also de ned only up to a scale factor, the number of independent coe cients of F is seven. We will see in section 4.4 that the Fundamental matrix can be written as a product of an invertible matrix and an antisymmetric matrix.

2.6 Summary

In this section, we have described the epipolar transformation, both from a geometrical point of view and from an algebraic point of view. In order to provide the latter one, we have de ned the Fundamental matrix. Its properties and relations to the well-known Essential matrix have been made clear. It must be noted that the Fundamental matrix provides a complete description of the projective structure of a set of two cameras. No other geometrical information can be obtained from uncalibrated cameras without making further assumptions about the structure of the scene.

3.1 The linear criterion

3 General estimation methods: an analysis and experimental resultscoe cients of matrix F. Thus we know that if we are given 8 matches we will be able, in general, to determine a unique solution for F, de ned up to a scale factor. This approach, known as the eight point algorithm, was introduced by Longuet-Higgins 40] and has been extensively studied in the literature 38] 75] 12] 79] 37], for the computation of the Essential matrix. It has proven to be very sensitive to noise. Our contribution is to study it in the more general framework of Fundamental matrix computation. Some recent work has indeed pointed out that it is also relevant for the purpose of working from uncalibrated cameras 57], 16] 23]. In this framework, we obtain new results about the accuracy of this criterion, which will enable us to present a more robust approach. In practice, we are given much more than 8 matches and we use a least-squares method to solve: X (11) min (q0iT Fqi)2 When a Fundamental matrix obtained numerically does not verify the rank constraint, there is no exact solution to Fe= 0. In that case, we cannot use formulas (7), thus the epipole e is determined by solving the following classical constrained minimization problem min kFek2 subject to kek2= 1 (12) e

The eight point algorithm Equation 2) is linear and homogeneous in the 9 unknown

F

i

which yields e as the unit norm eigenvector of matrix FT F corresponding to the smallest eigenvalue. The same processing applies in reverse to the computation of the epipole e0. The epipolar transformation can then be obtained by a linear least-squares procedure, using equations (5) and (6).

the fundamental matrix theory algorithms and stability analysis(2004)

The advantage of the linear criterion is that it leads to a non-iterative computation method, however, we have found that it is quite sensitive to noise, even with numerous data points. Let us point out to the two main drawbacks of the linear criterion. A more detailed analysis of the linear criterion is performed in 43, 42], where some analytical results and numerical examples are provided.

The linear criterion cannot express the rank constraint Le

t l0 be an epipolar line in the second image, computed from a fundamental matrix F that was obtained by the linear criterion, and from the point m= (u; v; 1)T of the rst image. We can express m using the epipole in the rst image, and the horizontal and vertical distances from this epipole, x and y. A projective representation for l0 is: 0 e?x 1 0x1 1 (13) l0= Fm= F@ e2? y A= Fe? F@ y A 1 0|{z}l1If det(F)= 0, the epipole e satis es exactly Fe= 0, thus the last expression simpli es to l1, which is an epipolar line. If the determinant is not exactly zero, we see that l0 is the sum of a constant vector r= Fe which should be zero but is not, and of the vector l1, whose norm is p bounded by x2+ y2 kFk. We can conclude that when (x; y) ! (0; 0) (m ! e), the epipolar line of m in the second image converges towards a xed line represented by r, which is inconsistent p with the notion of epipolar geometry. We can also see that the smaller x2+ y2 is (ie the closer m is to the epipole), the bigger will be the error on its associated epipolar line. In particular, it can be concluded that if the epipole is in the image, the epipolar geometry described by the fundamental matrix obtained from the linear criterion will be inaccurate. This problem can be observed in the images shown in the experimental part, in gure 11 for the intersection of epipolar lines, and in gure 12, for the inconsistency of epipolar geometry near the epipoles. rical interpretation of the criterion (11). The Euclidean distance of the point q of the second 0 0 0 image to the epipolar line l0= (l1; l2; l3)T= Fq of the corresponding point q of the rst image is: 0T 0 d(q0; l0)= p 0jq2 l j 0 2 (14) (l1 )+ (l2 ) p0 0 We note that this expression is always valid as the normalizing term k= (l1 )2+ (l2 )2 is null only in the degenerate cases where the epipolar line is at in nity. The criterion (11) can be written: X 22 0 0 ki d (qi; li) (15) This interpretation shows that a geometrically signi cant quantity in the linear criterion is the distance of a point to the epipolar line of its corresponding point. This quantity is weighted by the coe cients k, de ned above. To see why it can introduce a bias, let us consider the case where the displacement is a pure translation. The fundamental matrix is antisymmetric and has the form: 2 0 1?y 3 4?1 0 x 5 y?x 0 where (x; y; 1)T are the coordinates of the epipoles, which are the same in the two images. If (ui; vi; 1)T are the coordinates of the point qi in the rst image, then the normalizing factor is ki2= 2((y? vi )2+(x? ui)2 ), where is a constant. When minimizing the criterion (15), we will minimize both ki and d2 (q0i; l0i). But minimizing ki is the same than favoring the fundamentali

The linear criterion su ers from lack of normalization Let us now0give a geomet-

the fundamental matrix theory algorithms and stability analysis(2004)

matrices which yield epipoles near the image. This is in fact still valid in the general case 42], and we conclude that the linear criterion shifts ep

ipoles towards the image center.

The distance to epipolar lines We now introduce a rst non-linear approach, basedXi

3.2 Non-Linear criteria

on the geometric interpretation of criterion (11) given in 3.1. To obtain a consistent epipolar geometry, it is necessary and su cient that by exchanging the two images, the fundamental matrix is changed to its transpose. This yields the following symmetric criterion: (d2(q0i; Fqi )+ d2(qi; FT q0i )) and can be written, using (14) and the fact that q0iT Fqi= qT FT q0i: i X 0T 1 1 2 (Fqi )2+ (Fqi )2+ (FT q0i )2+ (FT q0i )2 (qi Fqi ) 2 1 1 2 i

(16)

This criterion, which will be referred to in the sequel by DIST is clearly normalized in the sense that it does not depend on the scale factor used to compute F.

The Gradient criterion and an interpretation as a distance Correspondences are obtained with some uncertainty. When minimizing the expression (11), we have a sum of terms Ei= q0iT Fqi which have di erent variances. It is natural to weight them so that the contribution of each of these terms to the total criterion will be inversely proportional to its variance. The variance of Ei is given as a function of the variance of the points qi et qi0 by:2 Ei=

h

@ EiT@ qi

@ EiT@ q0i

i

qi 0

0 q0i

"

@ Ei@ qi@ Ei@ q0i

#

(17)

where qi and q0i are the covariance matrices of the points q et q0, respectively. These points are uncorrelated as they are measured in di erent images. We make the classical assumption that their covariance is isotropic and uniform, that is: qi= q0i= 0 0 The equation (17) reduces to: where rEi denotes the gradient of Ei with respect to the four-dimensional vector (ui; vi; u0i; vi0 )T built from the a ne coordinates of the points qi and qi0 . Thus:2 2 2 Ei= krEik

rEi= ((FT q0i )1; (FT q0i )2; (Fqi)1; (Fqi )2 )T We obtain the following criterion, referred to in the sequel as GRAD, which is also normalized: X (q0iT Fqi )2 (18) 2 2 T 0 2 T 0 2 i (Fqi )1+ (Fqi )2+ (F qi )1+ (F qi )2We can note that there is a great similarity between this criterion and the distance criterion (16). 1 Each of its terms has the form k2+k0 2 E, whereas the rst one has terms ( k12+ k102 )E . We can also consider the problem of the computing the fundamental matrix from the de nition (2) in the general framework of surface tting, The surface S is modeled by the implicit equation g(x; f )= 0, where f is the sought parameter vector describing the surface which best

the fundamental matrix theory algorithms and stability analysis(2004)

ts the data points xi . The goal is to minimize a quantity i d(xi; S )2, where d is a distance. In our case, the data points are the vectors xi= (ui; vi; u0i; vi0 ), f is one of the 7 dimensional parameterizations introduced in the previous section,, and g is given by (2). We have developed a method to perform the exact computation of this distance 42, 43], based on some special properties of the surface S, but this approach is computationally very expensive. The linear criterion can be considered as a gene

ralization of the Bookstein distance 5] for conic tting. The straightforward idea is to approximate the true distance of the point x to the surface by the number g(x; f ), in order to get a closed-form solution. A more precise approximation has been introduced by Sampson 64]. It is based on the rst-order approximation: g(x) ' g(x0 )+ (x? x0 ) rg(x)= g(x0 )+ kx? x0 k krg(x)k cos(x? x0; rg(x)) If x0 is the point of S which is the nearest from x, we have the two properties g(x0 )= 0 and cos(x? x0; rg(x0))= 1. If we make the further rst-order approximation that the gradient has the same direction at x and at x0: cos(x? x0; rg(x0)) ' cos(x? x0; rg(x)), we get: g(x) d(x; S )= kx? x0k ' krg(x)k P Il is now obvious that the criterion (18) can be written: i d(xi; S )2 .

P

3.3 Parameterizations of the Fundamental Matrix

the fact that F is de ned only up to a scale factor is to x one of the coe cients to 1 (only the linear criterion allows us to use in a simple manner another normalization, namely kFk). It yields a parameterization of F by eight values, which are the ratio of the eight other coe cients to the normalizing one. In practice, the choice of the normalizing coe cient has signi cant numerical consequences. As we can see from the expressions of the criteria previously introduced (16) and (18), the non-linear criteria take the general form: Q1(F11; F12; F13; F21; F22; F23; F31; F32; F33) Q2 (F11; F12; F13; F21; F22; F23) where Q1 and Q2 are quadratic forms which have null values at the origin. A well-known consequence is that the function Q1=Q2 is not regular near the origin. As the derivatives are used in the course of the minimization procedure, this will induce unstability. As a consequence, we have to choose as normalizing coe cients one of the six rst one, as only these coe cients appear in the expression of Q2. Fixing the value of one of these coe cients to one prevents Q2 from getting near the origin. We have established using covariance analysis that the choices are not equivalent when the order of magnitude of the di erent coe cients of F is di erent. The best results are theoretically obtained when normalizing with the biggest coe cients. We found in our experiments this observation to be generally true. However, as some cases of divergence during the minimization process sometimes appear, the best is to try several normalizations We note that as the matrices which are used to initialize the non-linear search are not, in general, singular, we have to compute rst the closest singular matrix, and then the parameterization.

A matrix de ned up to a scale factor The most natural idea to take into account

A singular matrix As seen in part 3.1, the drawback of the previous method is that we do not take into account the fact that the rank of F is only two, and that F thus depends on only 7 parameters. We have rst tried to use minimizations under the constraint det(F)= 0, which is a cubic polynomial in the coe cients of F.

The numerical implementations were not e cient and accurate at all.11

the fundamental matrix theory algorithms and stability analysis(2004)

Thanks to a suggestion by Luc Robert, we can express the same constraint with an unconstrained minimization: the idea is to write matrix F as: 0 a 1 a2 a3 1 A F=@ a4 a5 a6 (19) a7 a1+ a8 a4 a7a2+ a8a5 a7 a3+ a8 a6 The fact that the third line is a linear (thus this parameterization will be designated in the sequel by the letter L) combination of the two rst lines ensures that F is singular. Choosing such a representation allows us to represent F by the right number of parameters, once the normalization is done. A non-linear procedure is required, but it is not a drawback, as the criteria presented in section 3.2 are already non-linear.

A Fundamental matrix with nite epipoles The previous representation takes into account only the fact that F is singular. We can use the fact it is a Fundamental matrix to parameterize it by the values that are of signi cance for us, those de ning the epipolar transformation (thus this parameterization will be designated in the sequel by the letter T). Using the formulas (7) yield:0 F=@b a?ay? bx?d?c cy+ dx dy0? bx0 cy0? ax0?cyy0? dy0 x+ ayx0+ bxx0

1 A

(20)

The parameters that we use are the a ne coordinates (x; y) and (x0; y0 ) of the two epipoles, and three of the four homography coe cients, which are the coe cients of the submatrix 2 2 obtained by suppressing the third line and the third column. We normalize by the biggest of them. The initial parameters are obtained by computing the epipoles and the epipolar transformation by the approximations introduced in 2.4

3.4 An experimental comparison

We have presented an approach to the computation of the fundamental matrix which involves several parameterizations and several criteria. The goal of this part is to provide a statistical comparison of the di erent combinations.

The method An important remark is that if we want to make a precise assessment of the performance of any method, we have to change not only the image noise, as it is often done, but also the displacements. Di erent displacements will give rise to con gurations with stability properties that are very di erent. We start from 3D points that are randomly scattered in a cube, and from a projection matrix P. All these values are chosen to be realistic. Each trial consists of: Take a random rigid displacement D, Compute the exact fundamental matrix F0 from D and P, Compute the projection matrix P0 from D and P, Project the 3D points in the two 512 512 retinas using P and P0, Add Gaussian noise to the image points, Solve for the fundamental matrix F, Compute the relative distance of the epipoles from F and those from F0. In many applications (see the last section of this paper), only the coordinates of the epipoles are needed. In some sense, they are the most important piece of information contained in the12

the fundamental matrix theory algorithms and stability analysis(2004)

Fundamental matrix, and thus it is natural to attempt to quantify errors on this matrix by errors on i

ts epipoles. We de ne the relative error, for each coordinate of the epipole: jx j minf min(j?jxj0x j); 1g x; 0 We took a relative error since a same (absolute) deviation of the epipole will yield a larger error on the epipolar geometry if the epipole lies closer to the image center. This allows us to ensure a consistent maximal error on the direction of epipolar lines, regardless of the distance of the epipole to the image center. It has to be noted that the choice of an error measure for the epipoles is not an obvious matter, since they are basically quantities of the projective plane, which has no metric. A further discussion of error measures can be found in 46]. All the graphs shown in this section are averaged over a few hundred trials. In a scheme where only such a small number of experiments are averaged, a single very large value could signi cantly a ect statistics, and this is why the relative error is thresholded by 1. As our experimentations have shown that the average errors on the four coordinates are always coherent, we will take the mean of these four values as an error measure. Some experimental evidence to show that it is indeed an adequate characterization is provided next.

Epipoles stability characterize Fundamental matrix stability The estimation of the fundamental matrix can be done as a two-stage process, the rst one being the estimation of the coordinates of the epipoles, and the second one the estimation of the coe cients of the homography. If one of the two stages is signi cantly more sensitive to noise than the other one, then we can conclude that its stability determines the stability of the overall estimation. The fundamental matrix has been computed from point correspondences using the quadratic criterion derived from the linear relation (2). The epipoles e and e0 are then computed from this matrix using (12). The coe cients of the epipolar homography have been computed from the point correspondences and the correct epipoles, using a linear least-squares formulation based on the relation derived by making substitutions of (5) in (6).0.70

e0.60

e’ b/a c/a d/a

0.50

relative error (%)

0.40

0.30

0.20

0.10

0.00 0.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4

1.6

1.8

2.0

2.2

2.4

2.6

Figure 4: Sensitivity to noise of the di erent components of the fundamental matrix.Since the four coe cients of the epipolar transformation are de ned only up to a scale factor, we have normalized them by dividing by a, which allows to consider a relative error for each of them. From the results of the simulation shown Fig. 4, it is clear that:

Image noise (pixels)

the fundamental matrix theory algorithms and stability analysis(2004)

The stability of the epipoles in each of the images is comparable, which was to be expected, since the criterion (2) is symmetrical. Note that the non-linear criteria proposed in 43] also share this property. Once the epipoles are determined correctly, the computation of the homography is quite stable, and thus that the more unstable part of the computation is t

he determination of the epipoles. We thus conclude from this simulation that an adequate measure for the stability of the fundamental matrix is the stability of one of its epipoles. Note that this is consistent with the ndings of 47], where it has been shown that the epipole plays a particular role in the projective description of the geometry of a system of two cameras.

Non-linear criteria There are two di erent parameterizations, that are presented Sec-

tion 3.3, and two di erent non-linear criteria, presented in Section 3.2. The abbreviations for the four resulting combinations that we studied are in table 1. We have tried several minimization procedures, including material from Numerical Recipes, and programs from the NAG library.

Table 1: Non-linear methods for the computation of the fundamental matrix

LIN linear normalization by kFk DIST-L distance to epipolar lines (16) singular matrix (19) DIST-T distance to epipolar lines epipolar transformation (20) GRAD-L weighting by the gradient (18) singular matrix GRAD-T weighting by the gradient epipolar transformationThe comparison we have done is threefold: 1. The stability of the minimum corresponding to the exact solution. When noise is present, the hypersurface which represents the value of the criterion as a function of the parameters gets distorted, thus the coordinates of the minimum change. A measure of this variation is given by the distance between the exact epipole and the one obtained when starting the minimization with the exact epipole ( gure 5). 2. The convergence properties. The question is whether it is possible to obtain a correct result starting from a plausible initialization, the matrix obtained from the linear criterion. We thus measure the distance between the exact epipole and the one obtained when starting the minimization with the linear solution ( gure 6), and the distance between the epipole obtained when starting the minimization with the exact epipole and the one obtained when starting the minimization with the linear solution ( gure 7) . 3. The stability of the criterion. When the hypersurface which represents the value of the criterion as a function of the parameters gets distorted, the values of the criterion at local minima corresponding to inexact solutions can become less than the value of the criterion at the correct minimum ( gure 8). The conclusions are: The non-linear criteria are always better than the linear criterion. When starting a nonlinear computation with the result of the linear computation, we always improve the precision of the result, even if the noise is not important. The di erence increases with the noise. The di erence due to the choice of the criterion (DIST or GRAD, de ned in section3.2) is much less signi cant than the one due to the choice of the parameterization (L or T, de ned in section 3.3).

abbrev.

criterion

parameterization

the fundamental matrix theory algorithms and stability analysis(2004)

Relative errorImage noise (pixels)

Relative errorImage noise (pixels)

the fundamental matrix theory algorithms and stability analysis(2004)

Relative errorImage noise (pixels)

Number of false minima

Image noise (pixels)

the fundamental matrix theory algorithms and stability analysis(2004)

The parameterization T yields more stable minima than the parameterization L, as seen in gure 5. However, the criterion obtained with parameterization T has worse convergence and stability properties than the parameterization L, as seen in gures 7 and 8 As a consequence, when starting from the results of the linear criterion, the results of the four non-linear combinations are roughly equivalent, the results obtained with the parameterization L and the criterion DIST being slightly better, as seen in gure 6. The computation is quite sensitive to pixel noise: a Gaussian noise of variance 1 pixel yields a relative error which is about 30%. be seen in gure 9 that the pencils of epipolar lines obtained with the linear criterion, and those obtained with the non-linear criterion are very di erent. The epipoles obtained with the nonlinear criterion are much further away. It seems at rst that if one considers a point that was used in the computation, its epipolar line lies very close to its corresponding point. However, the zoom of gure 10 shows that the t is signi cantly better with the non-linear criterion. Figure 11 shows a set of epipolar lines obtained from the linear criterion, we can see that they don't meet exactly at a point, whereas they do by construction for the non-linear criterion. A consequence is illustrated in gure 12, which shows some more epipolar lines, drawn from points that were not used in the computation of the fundamental matrix. It can be seen that for the points on the wall, which are quite far from the epipole, the corresponding epipolar lines seem approximately correct, while for the points chosen on the table, the corresponding epipolar lines are obviously very incorrect, in the sense they are very far from the corresponding points. This situation does not occur with the non-linear criterion, as it can be seen in the bottom of this gure.

Real data We now illustrate the remarks made in section 3.1 with a pair

of images. It can

3.5 Summary

In this section, we focused on the problem of determining in a robust way the Fundamental matrix from a given number of image point correspondences. The classical linear criterion has been shown to be unable to express the rank and normalization constraints. Analyzing these drawbacks enabled us to introduce non-linear computation techniques, based on criteria that have a nice interpretation in terms of distances, and appropriate parameterizations. We have shown, using both large sets of simulations and real data, that our non-linear computation techniques provide signi cant improvement in the accuracy of the Fundamental matrix determination, and we have evaluated stability and convergence properties of each method.

4 Planes and the fundamental matrix: unstability and new algorithmsDe nition Let Mi be space points which happen to lie in the same plane and mi be their images by a projective linear relation from P 3 to P 2 . Its restriction to is a projective linear relation between points of P 2, which is an homography h. This relation is invertible, in the generic case. If two images of the points Mi lying in a plane, mi and m0i are available, we can consider the relation h0 h?1 between these two images. It is thus an homography, which means there is a 3 3 invertible matrix H, such that the following projective relation holds for each i:m0i= Hmi17(21)

4.1 The correspondence between the two images of a plane

the fundamental matrix theory algorithms and stability analysis(2004)

Figure 9: Epipolar lines obtained from the linear criterion (top), and from the non-linear criterion (bottom).

the fundamental matrix theory algorithms and stability analysis(2004)

Figure 10: Zoom showing the t with the linear criterion (left) and the non-linear criterion (right).The fact that there is such an analytic relation between the coordinates of matched points entails that we are able to identify planes using only measurements in the image. Predict-andverify algorithms have been already developed by 17], and more recently by 70] and 62], using uncalibrated cameras. The idea is to chose four points, to compute the homography, whose knowledge allows the position of the corresponding point of any new point on the plane to be predicted. The predicted position and the actual position are compared using a simple distance threshold, to decide whether the new point is on the plane de ned by the four points. In this paper, we will not elaborate on this issue, but rather on the computational problems which can be solved once the identi cation of planes has been performed.

Computation We now study the problem of computing the parameters of the homography

from point matches. By writing that the two proportionality constraints obtained from (21) are satis ed, we have two equations which are linear in the coe cients of H, and can be solved as soon as four point correspondences are available. In practice about 10 to 20 points are needed to compute an accurate homography, and the (variable) number of points used in the experiment conducted in this section will never be

less than that. We have found that with the criteria (LIN) based on a least-squares formulation of (21), there is a normalization problem, as for the computation of the fundamental matrix. A favorable thing is that we do not have a rank constraint to consider. The two non-linear criteria that we have investigated are similar to the ones introduced in Section 3.2: DIST: symmeterized Euclidean distance between predicted and measured points, GRAD: the two linear equations weighted by associated uncertainties. Convergence properties have been tested by using two di erent initializations: the exact value (-EX) and the value obtained from the linear criterion (-LIN). In the statistical simulation shown gure 13, averaged over many widely di erent set of correspondences, the error measure is the average relative error on each coe cient. We can conclude from these results that: The non-linear criteria give better results than the linear criterion.

the fundamental matrix theory algorithms and stability analysis(2004)

Figure 11: Intersection of epipolar lines obtained from the linear criterion.The results obtained from the two non-linear criteria are very close. The computation is more stable from the computation of the fundamental matrix, there is almost no convergence problem, thus it is possible to compute homographies with a good accuracy from point matches

4.2 Relation between homographies and the fundamental matrix

Let F be the fundamental matrix relating two images, and H an homography matrix relating the coordinates of points of a plane which projects in the two images. We consider the point m of the rst image to be the projection of a virtual point M of plane . The homography enables us to compute the projection m0 of M on the second image. The points m and m0 are in correspondence, thus, using (2), we obtain:

m0T Fm= (Hm)T Fm= mT HT Fm= 0This relation is to be satis ed by any point m, thus we can conclude that the matrix HT F is antisymmetric, which yields the important relation:

HT F+ FT H= 0 We are now going to show that a matrix H satis es condition (22) if, and only if: F= e0] H20

(22) (23)

the fundamental matrix theory algorithms and stability analysis(2004)

Figure 12: Additional epipolar lines obtained with the linear criterion (top), and with the non-linear criterion (bottom)

本文来源：https://www.bwwdw.com/article/49b4.html