A General Expression of the Fundamental Matrix for Both Perspective and Affine Cameras

1 Introduction

Since the work of Koenderink and van Doorn [Koen­ derink and van Doorn, 1991) on affine structure from motion and that of Forsyth et al. [Forsyth et al., 1991) on invariant description, the development of non­ metric vision has attracted quite a number of re­ searchers [Faugeras, 1992; Hartley et al., 1992) (to cite a few) . We can find a range of applications: object recog­ nition, 3D reconstruction of scenes, image matching, vi­ sual navigation, motion segmentation, image synthesis, etc.

This paper addresses the recovery of structure and motion from two uncalibrated images of a scene un­ der full perspective or under affine projection. There is already a large amount of work reported in the lit­ erature [Faugeras, 1992; 1995; Hartley et al. , 1992; Shashua, 1994; Zisserman, 1992), and it is known that Gang Xu Department of Computer Science Ritsumeikan University Kusatsu, Shiga 525, Japan xu@cs.ritsumei.ac.jp the structure of the scene can only be recovered up to a projective transformation for two perspective images and up to an affine transformation for two affine im­ ages. We cannot obtain any metric information from a projective or affine structure: measurements of lengths and angles do not make sense. However, projective or affine structure still contains rich information, such as coplanarity, collinearity and ratios. The latter is some­ times sufficient for artificial systems, such as robots, to perform tasks such as navigation and object recognition. We believe that these results are important to the whole community of computer vision. However, they are usu­ ally stated using tools from Projective Geometry, which is not accessible to most researchers. One objective of this paper is to present these results in a way such that everyone having knowledge of linear algebra can under­ stand without difficulty.

*On leave from INRIA Sophia-Antipolis, France

Other contributions of this paper are the following:

• A general expression of the fundamental matrix for any projection model is presented. Previously, the fundamental matrix is formulated separately for full perspective and affine projection. Our formula is valid for both.
• A new efficient technique for affine reconstruction from two affine images is developed. We decom­ pose the problem into two subproblems: recovery of affine epipolar geometry and 3D reconstruction with respect to an implicit affine basis.

This paper is organized as follows. Section 2 presents different camera projection models . Section 3 derives an expression of fundamental matrix which is valid for any projection model (ignoring the lens distortion). Sec­ tion 4 describes the projective reconstruction from two uncalibrated perspective images. In Section 5, we first specialize the general fundamental matrix to the case of affine cameras and then show that only affine structure can be recovered, and finally a new technique for affine reconstruction is proposed.

2 Perspective Projection and its Approximations

If the lens distortion can be i~nored, the projection from a space point M = [X, Y, Z] to its image point m =

[x, yjT can be represented linearly by

where x = UjS, andy= VjS if S -:j; 0, and Pis the 3 x 4 projection matrix which varies with projection model and with the coordinate system in which space points M are expressed. Given a vector x = [x,y, ···JT, we use x to denote its augmented vector by adding 1 as the last element , i.e., :X= [x, y, · · · , 1]T. Now we can rewrite the above formula concisely as

where s = S is an arbitrary nonzero scalar.

The projection matrix corresponding to the full per­ spective is of the form:

which is defined up to a scalar factor. This implies that there are only 11 degrees of freedom in a full perspective projection matrix. In terms of the intrinsic and extrinsic parameters of a camera, P can be decomposed as P = A[R t] , where A is a 3 x 3 matrix defined by the intrinsic parameters (see e.g., [Faugeras, 1993]), and (R, t) is the rotation and translation (extrinsic parameters) relating the world coordinate system to the camera coordinate system.

The affine camera, introduced by Mundy and Zisser­ man [Mundy and Zisserman, 1992] as a generalization of orthographic, weak perspective and paraperspective projections, has the following form:

The elements P31 , P32 and P33 are equal to 0. This is an approximation to the full perspective, and works quite well when object size and depth is small compared with the distance between the camera and object.

3 Fundamental Matrix for Any Projection Model

Consider now the case of two images whose projection matrices are P and P', respectively (the prime ' is used to indicate a quantity related to the second image). A point m in the first image is matched to a point m' in the second image. From the camera projection model (2) , we have

An image point m' defines actually an optical ray, on which every space point M' projects on the second image at iii'. This optical ray can be written in parametric form as

where P'+ is the pseudo-inverse of matrix P':

and p'.L is any 4-vector that is perpendicular to all the row vectors of P', i.e., P'p'.L = 0 . Thus, p'.L is a null vector of P'. As a matter of fact, p'.L indicates the position of the optical center (to which all optical rays converge). We show later how to determine p'.L. For a particular value s', equation (5) corresponds to a point on the optical ray defined by m'. Equation ( 5) is easily justified by projecting M' onto the second image, which indeed gives m'.

Similarly, an image point m in the first image defines also an optical ray. Requiring the two rays to intersect in space implies that a point M' corresponding to a par­ ticular s' in (5) must project onto the first image at m, that is

Performing a cross product with Pp'.L yields

Eliminating s and s' by multiplying iii T from the left (equivalent to a dot product), we have

where F is a 3 x 3 matrix, called fundamental matrix:

Equation (7) is the well-known epipolar equation [Hart­ ley et al., 1992; Faugeras et al., 1992; Luong and Faugeras, 1996], but the form of the fundamental matrix (8) is general and, to our knowledge, is not yet reported in the literature. It does not assume any particular pro­ jection model. Indeed, equation (8) only makes use of the pseudo-inverse of the projection matrix (which is valid for full perspective as well as for affine cameras). In [Lu­ ong and Faugeras, 1996], for example, the fundamental matrix is formulated only for full perspective, because it involves the inverse of the first 3 x 3 submatrix of P which is not invertible for affine camera. In [Zisserman, 1992], a separate fundamental matrix is given for affine cameras. Our formula (8) works for both. We will spe­ cialize it for affine cameras in Sect. 5.1.

The fundamental matrix F recapitulates all geometric information between two images. The nine elements ofF are not independent from each other. In fact, F has only 7 degrees of freedom. This can be seen as follows. First F is defined up to a scale factor because ifF is multiplied by any nonzero scalar, the new F still satisfy (7) . Second, the rank of F is at most 2, i.e., det(F) = 0. This is because the determinant of the antisymmetric matrix [Pp'.L] x is equal to zero. Another thing to mention is that the two images play a symmetric role. Indeed, (7) can also be rewritten as m'TFT iii = 0. It can be shown that FT = [P'p.L]xP'P+.

The vector p'.L still needs to be determined. We first note that such a vector must exist because the difference between the row dimension and the column dimension is one, and that the row vectors are generally independent from each other. Indeed, one way to obtain p'.l is

where w is an arbitrary 4-vector. To show that p'.l is perpendicular to each row of P', we multiply p'.l by P' from the left: P'p'.l = (P'-P'P'T(P'P'T)- 1 P')w = 0, which is indeed a zero vector. The action of I - P'+p' is to transform an arbitrary vector to a vector that is perpendicular to every row vector of P'. If P' is of rank 3 (which is usually the case), then p'.l is unique up to a scale factor. See [Xu and Zhang, 1996J for more details.

4 Projective Reconstruction

We show in this section how to estimate the position of a point in space, given its projections in two images whose epipolar geometry is known. The problem is known as 3D reconstruction in general, and triangulation in partic­ ular. We assume that the fundamental matrix between the two images is known (e.g., computed with the meth­ ods described in [Zhang et al. , 1995]), and we say that they are weakly calibrated.

4.1 Fundamental Matrix for Full Perspective

We now derive a usual form of fundamental matrix for full perspective from the general expression (8). Let A and A' be the 3 x 3 matrices containing the intrinsic parameters of the first and second image. Without loss of generality, we choose the second camera coordinate system as the world coordinate system. Then, the cam­ era projection matrices are P = A [R tJ and P' = A' [I OJ , where (R, t) is the rotation and translation re­ lating the two camera coordinate systems, and I is the 3 x 3 identity matrix and 0 is a zero 3-vector.

It is not difficult to see that

This yields:

Using the property (Ax) x (Ay) = det(A)A -T(x x y), Vx, y, and the general expression of the fundamen­ tal matrix (8), we have

where ~ means "equal" up to a scale factor. The above equation is the usual form of the fundamental matrix (see e.g., [Luong and Faugeras, 1996]).

4.2 Projective Reconstruction

In the calibrated case, a 3D structure can be recovered from two images only up to a rigid transformation and an unknown scale factor (this transformation is also known as a similarity), because we can choose an arbitrary co­ ordinate system as a world coordinate system (although one usually chooses it to coincide with one of the cam­ era coordinate systems). Similarly, in the uncalibrated case, a 3D structure can only be performed up to a pro­ jective transformation of the 3D space [Faugeras, 1992; Hartley et al., 1992; Maybank, 1992; Faugeras, 1995J. A 4 x 4 nonsingular matrix H defines a linear transforma­ tion from one projective point to another, and is called the projective transformation. The matrix H, of course, is also defined up to a nonzero scale factor, and we write py = Hx, if :X is mapped toy by H. Here pis a nonzero scale factor.

Now we are given two perspective images of a scene. The intrinsic parameters of the images are unknown. Assume that the true camera projection matrices are P and P'. From (8), we have the following relation F = [Pp'.l]xPP'+. Given 8 or more point matches in general position, the fundamental matrix F can be uniquely determined from two images. We are now in­ terested in recovering P and P' from F, and once they are recovered, triangulation can be conducted to recon­ struct the scene in 3D space.

Proposition 1 Given two perspective images of a scene whose epipolar geometry (i.e., the fundamental matrix) is known, the camera projection matrices can only be determined up to an unknown projective transformation.

The proof of this proposition is omitted due to space limitation. The consequence of this proposition is the following: if P and P' are two camera projection ma­ trices consistent with the fundamental matrix F , then P = PH and P' = P'H are also consistent with the same F, where H is any projective transformation of the 3D space. If the true structure is M, then the structure reconstructed from image points is H- 1 M, i.e., up to a projective transformation. This is because PH- 1 M= PM gives the exact projection for the first image; the same is true for the second image. Although the above result has been known for several years, we believe that it is easier to understand our discussion than what has been presented in the literature.

In order to reconstruct points in 3D space, we need to compute the camera projection matrices from the funda­ mental matrix F with respect to a projective basis, which can be arbitrary because of Proposition 1. One way is to use a canonical representation [Luong and Vieville, 1994; Beardsley et al., 1994J:

where e is the epipole in the first image (FT e = 0) and M = - 11 ~ 11 2 [eJxF.

5 Affine Reconstruction

This section deals with two images taken by an affine camera at two different instants or by two different affine cameras.

5.1 Affine Fundamental Matrix

In the case of a general affine camera, the projection matrix (4) can be rewritten as

We now derive the specific fundamental matrix for affine cameras from the general form (8).

For any affine camera, we can construct p 1 .l as

Here, we have defined p; = p~ x p~. From p~T p; = 0 and p~T p; = 0, we can verify that p 1 .l is indeed perpen­ dicular to P 1 · Multiplying P with p 1 .l yields

Let us assume P 1 + = [QT q4 ]r, where Q = [q1 Q2 q3) is a 3 x 3 matrix and q4 is a 3-vector. Since

q 4 can be uniquely determined: q4 = [0, 0, 1/ P~4jT . The constraint for matrix Q is then

It is evident that Q cannot be uniquely determined. For us, any Q that satisfies the above equation suffices.

Now substituting these matrices for (8), we have

where aij are related to the coefficients of the camera projection matrices. The fact that the affine fundamen­ tal matrix has the form of (12) is mentioned in [Zisser­ man, 1992]. Defined up to a scale factor, FA has only 4 degrees of freedom. The corresponding points in the two images must satisfy the following relation, called the affine epipolar equation:

Expanding the epipolar equation, the left-hand side is a first-order polynomial of the image coordinates, and we have

It means that the epipolar lines are parallel everywhere in the image, and the orientations of the parallel epipolar lines are completely determined by the affine fundamen­ tal matrix.

5.2 Affine Reconstruction

Given a sufficient number of point matches (at least 4) between two images, the affine fundamental matrix FA can be estimated (see [Shapiro et al., 1994]). We are now interested in recovering P A and P~ from FA , and once they are recovered, the structure can be redressed in 3D space.

Since P A and P~ are defined up to a scale factor, with­ out loss of generality, we assume ?34 = P~4 = 1. Then the relation between a 3D point and its 2D image is given by m =PAM and m 1 = P~M. Note that there is no more scale factor in the above equations. From the affine epipolar equation (13) , it is easy to obtain

and

Equation (15) becomes

Since this equation should be true for all points, the four coefficients must be all zero, which leads to

We thus have 4 simple constraints on the coefficients of the projection matrices, which is consistent with the number of the degrees of freedom in an affine fundamen­ tal matrix. Writing them in matrix form gives:

We now show the following proposition.

Proposition 2 Given two images of a scene taken by an affine camera, the 3D structure of the scene can be reconstructed up to an unknown affine transformation as soon as the epipolar geometry (i.e., the affine fundamen­ tal matrix} between the two images is known.

Let the 3D structure corresponding to the true cam­ era projection matrices P A ~nd P~ be M. We need to show that the new structure M = H:4 1 M is still consistent with the same sets of image points (i.e., with the affine fundamental matrix) , where

is an affine transformation of the 3D space, A is a 3 x 3 matrix, and t is a 3-vector. It follows that M = AM+ t . Proof : The camera projection matrices corresponding to the new structure M are:

We only need to show that the new affine projection matrices PA and P~ satisfy the same relation as (16), where Pij and Pfj should be replaced by Pij and Pfj. Indeed, multiplying both sides of (16) by HA from the right , i.e.,

This completes the proof.

·

Because of the above result , there is no unique deter­ mination of PA and P~ from FA based on (16). One simply way is the following:

Once P A and P~ are determined from FA, the 3D structure can be uniquely recovered. Let m = [u, vjT and m' = [u', v'f be the observed image points which have been matched between the two images. Let M = [X, Y, Zf be the corresponding space point to be esti­ mated, which projects on to the two cameras PA and P~ as

Because the observations are made in image plane and the noise level can be reasonably assumed to be the same for each extracted image point , a physically mean­ ingful criterion is to minimize, over the structure pa­ rameter M, the point-to-point distances between the ob­ served locations (m and m') and the image projections of the estimated scene structure (m and m'): F(M) = llm-mll 2 +lim' -m'll 2 . The solution is obtained by set­ ting the derivative of F(M) with respect toM to zero, i.e., 8F(M)/8M = 0. This yields a vector equation BM = b, where B is a 3 x 3 matrix and b is a 3D vector. The 3D reconstructed point is then given by M = B- 1 b.

5.3 Experimental Results

We have tested the proposed technique with computer simulated data under affine projection, and very good results have been obtained. In this subsection, we show the result with data obtained under full perspective pro­ jection but treated as if it were obtained under affine projection.

The parameters of the camera set-up are taken from a real stereovision system. The two cameras are sepa­ rated by an almost pure translation (the rotation angle is only 6 degrees). The baseline is about 350 mm (millime­ ters). An object of size 400 x 250 x 300 mm 3 is placed in front of the cameras at a distance of about 2500 mm. Two images of this object under full perspective projec­ tion are generated as shown in Fig. 1. Line segments are drawn only for visual effect, and only the endpoints (12 points) are used in our experiment. The image resolu­ tion is 512 x 512 pixels 2 , and the projection of the object occupies a surface of about 130 x 120 pixels2.

The method described in [Shapiro et al., 1994] is used to compute the affine epipolar geometry, and the root of the mean point-to-point distance is 0.065 pixels . This implies that even the images are perspective, their re­ lation can be quite reasonably described by the affine epipolar geometry. The affine reconstruction result ob­ tained with the technique described in this paper is shown in Fig. 2.

In order to have a quantitative measure of the recon­ struction quality, we estimate, in a least-squares sense, the affine transformation which brings the set of affinely reconstructed points to the original set of 3D points. The root of the mean of the squared distances between the corresponding points is 10.4 mm, thus the error is less than 5%. The superposition of the two sets of data is shown in Fig. 3. It is interesting to observe that the re­ construction of the near part is larger than the real size while that of the distant part is smaller. This is because the assumption of an affine camera ignores the perspec­ tive distortion in the image.

6 Conclusion

We have addressed in this paper the problem of deter­ mining the structure and motion from two uncalibrated images of a scene under full perspective or under affine projection. Epipolar geometry, projective reconstruction and affine reconstruction have been elaborated in a way such that everyone having knowledge of linear algebra can understand without difficulty. A general expression of the fundamental matrix has been derived which is valid for any projection model without lens distortion (including full perspective and affine camera). A new and efficient technique for affine reconstruction from two affine images has been developed, which consists in first estimating the affine epipolar geometry and then per­ forming a triangulation with respect to an implicit affine basis for each point match.