Anders Heyden

Fredrik Kahl

Long Quan

Minimal Projective Reconstruction including Missing Data

The minimal data necessary for projective reconstruction from point features is well-known when each object point is visible in all images. In this paper, we formulate and propose solutions to a new family of reconstruction problems for multiple images from minimal data, where there are missing points in some of the images. The ability to handle the minimal cases with missing data is of great theoretical and practical importance. It is unavoidable to use them to bootstrap robust estimation such as RANSAC and LMS algorithms and optimal estimation such as bundle adjustment.

First, we develop a framework to parameterize the multiple view geometry, needed to handle the missing data cases. Then we present a solution to the minimal case of 8 points in 3 images, where one point is missing in one of the three images. We prove that there are in general as many as 11 solutions for this minimal case. Furthermore, all minimal cases with missing data for 3 and 4 images are catalogued. Finally, we demonstrate the method on both simulated and real images and show that the algorithms presented in this paper can be used for practical problems.

Introduction

Obtaining a 3D reconstruction is one common goal in computer vision. Recently, reconstruction methods have been successfully extended to projective reconstruction within an uncalibrated framework [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Hartley | Stereo from uncalibrated cameras[END_REF]. Solving minimal cases to perform 3D reconstruction is of both theoretical and practical importance, whereby a minimal case is meant that omission of one point in one image gives an infinite number of solutions. It is common to use the solutions obtained from the minimal cases to either bootstrap a robust estimation algorithms such as RANSAC or LMS schema [START_REF] Fischler | Random sample consencus, a paradigm for model fitting with application to image analysis and automated cartography[END_REF][START_REF] Torr | Robust parameterization and computation of the trifocal tensor[END_REF][START_REF] Zhang | A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry[END_REF] or an optimal estimation algorithm such as bundle adjustment. The minimal data necessary for projective reconstruction is well-known. In the two-view case, the minimum number of the points is 7, cf. Sturm's method [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF] reintroduced into computer vision in [START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF][START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Maybank | A theory of self calibration of a moving camera[END_REF]. For three views, the minimum number of the points is 6, cf. [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF]. The solutions to these problems rely on solving a cubic equation, and thus there are in general up to 3 solutions. However, these minimal cases do not allow the possibility of missing data. In practice, the missing data cases are frequent; the more images we have, the higher possibility that missing data occur. One typical example is illustrated in Figure 1 in which no matter how we locate the cameras, one of the 8 corners will not be visible. Even more, the missing point changes with the viewing position. Three possible camera positions are indicated in the figure that may result in three different missing corners in the images. This motivates us to formulate a new family of minimal reconstruction problems containing missing data. We will first develop a framework for efficiently parameterizing the multiple view geometry. Then, we will concentrate on the typical minimal case of 8 points in 3 images, where one point is missing in each of the three images. We will show that, not surprisingly, the algorithms for missing data cases are generally more complicated than the non-missing counterparts. The typical minimal case described above has 11 solutions. Finally, a catalogue of the different minimal cases for 3 and 4 images will be provided. Although the algebraic solutions are complicated, we demonstrate that the solutions are stable enough for dealing with real image sequences.

Previous work on reconstruction with missing data has been primarily concentrated on solely handling the redundant data cases. For example, the 'hallucination' of Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], the closure constraints in the projective case of Triggs [START_REF] Triggs | Linear projective reconstruction from matching tensors[END_REF] and in the affine case of Kahl and Heyden [START_REF] Kahl | Affine structure and motion from points, lines and conics[END_REF]. The ability to deal with both a minimal case and missing data is, to our knowledge, new to the computer vision community.

The paper is organized as follows. In Section 2, we first formulate the minimal missing data problem for reconstruction. Then, we solve the minimal case of 8 points in 3 images with one missing point in each image in Section 3. Next, we summarize all known minimal missing data cases for 3 and 4 images in a catalogue in Section 4. After that, we evaluate the performance of the solutions on both simulated and real images in Section 5. Finally, some concluding remarks are given in Section 6.

Problem formulation

Throughout the paper, vectors are denoted in lower case boldface and matrices in upper case boldface. Scalars are any plain letters or lower case Greek.

We assume a perspective projection (uncalibrated pin-hole camera) as the camera model.

Thus the object space may be considered as embedded in P 3 and the image space embedded in P 2 . The camera performs a projection from P 3 to P 2 and can be represented by a 3 4 matrix P 3 4 of rank 3 whose kernel is the projection center. The relation between a object point x in P 3 and an image point u in P 2 can be written u = P 3 4 x :

(1)

It is well known that both the problem of reconstructing 6 points from 3 images (see [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF]) as well as 7 points from 2 images, see [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF][START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF], have in general 3 different solutions. However, these minimal cases do not allow the possibility of having missing data in any of the images. For practical applications, it is important to be able to deal with the minimal cases which may contain missing data in some of the images. For two images, there are no minimal cases with missing data since a point visible in only one image does not give any constraint on the viewing geometry. So the minimum number of images in which we are interested is three.

For each point in each image, two quantities are measured (x-and y-coordinates). Thus, given 6 points visible in 3 images, 6 3 2 = 36 constraints (or equations) are obtained.

The unknowns are the 3D point coordinates and the camera matrices modulo the projective coordinate frame, in total 3 6 + 3 11 ? 15 = 36 unknowns. This is a minimal case without missing data as #unknowns = #equations = 36: Starting with the above minimal case, i.e. 6 points in 3 images, and removing the sixth point from the third image gives, of course, less equations than unknowns. However, trying to add a seventh point visible in images 1 and 2 results in 5 3 2 + 2 2 2 = 38 (5 points in 3 images and 2 points in 2 images) equations and 7 3 + 3 11 ? 15 = 39 (7 points and 3 camera matrices up to the projective transformation) unknowns. This is still underdetermined as #unknowns > #equations.

By further adding a point in images 2 and 3, we obtain 5 3 2 + 3 2 2 = 42 (5 points in 3 images and 3 points in 2 images) equations and 8 3 + 3 11 ? 15 = 42 (8 points and 3 camera matrices) unknowns, i.e. a minimal case since #unknowns = #equations = 42. This incidence relation can be visualized by the following matrix, where 0 in row i and column j means that point j is missing in image i and means visible: (2)

The three images of a cube indicated in Figure 1 may result in the above incidence relation. We conclude the discussion with a formal problem statement. Problem 1. Reconstruct the object and the camera matrices (structure and motion) from 8 points 3 images where one point is missing in each image and determine the number of different solutions.

Problem solution

In this section we will first outline a parameterization framework for handling the geometry of multiple cameras. Then a solution to Problem 1 will be derived. As we are working within an uncalibrated projective setting, all quantities are determined only up to an unknown projective transformation, therefore we may without restriction1 introduce a projective coordinate system such that the first 5 points in space are assigned to the canonical projective coordinates

x 1 x 2 x 3 x 4 x 5 = 2 6 6 4 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 3 7 7 5
and the first 4 image points in each image are assigned to

u 1 u 2 u 3 u 4 = 2 4 1 0 0 1 0 1 0 1 0 0 1 1 3 5 :
Using this choice of coordinates it is not hard to see that we get the following special form of camera matrices

P = 2 4 0 0 0 0 0 0 3 5 :
This reduced camera matrix using canonical projective coordinates has been successfully applied by many researchers [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF][START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF][START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF][START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF].

By further using the fact that the fifth basis point in space (1; 1; 1; 1) projects onto the fifth point in each image as (u 5 ; v 5 ; w 5 ), we obtain Observe that both the left side and the right side are only determined up to an unknown scale factor. This means that we can fix the scale factors consistently by putting 5 = 1, which gives a natural scale to the camera matrix, inherited from the homogeneous coordinates (u 5 ; v 5 ; w 5 ).

We will assume that this fixation of scales already have been made in the sequel. This leads to the following reduced camera matrix:

P = 2 4 ? u 5 0 0 0 ? v 5 0 0 0 ? w 5 3 5 : (3)
It is important to observe that this reduced camera matrix only contains one unknown parameter . We are now ready to state our main theorem of the section.

Theorem 1. There are in general 11 algebraic solutions to Problem 1. The solutions may include complex and not physically feasible solutions.

Proof. Without restrictions we can make projective changes of coordinates in the object space as well as in the images. We then arrive at the reduced camera matrix parameterized by only one unknown as in [START_REF] Faugeras | Motion from point matches: Multiplicity of solutions[END_REF]. For a set of three images, we have three unknowns , 0 and 00 . Consider the sub-configuration of 6 points that are visible in both the first and second image. If the first 5 points are chosen as projective basis, then the image of the sixth point in the first image is given by x 6 y 6 z 6 t 6 3 7 7

5 :

Note that they are both homogeneously linear in x 6 , y 6 , z 6 , t 6 , 6 and 0 6 and can be rewritten together as = 0;

or more compactly denoted as M 6 6 (x 6 ; 6 ; 0 6 ) T = 0:

(5)

Since the vector (x 6 ; 6 ; 0 6 ) does not vanish, the 6 6 matrix M has to be singular, i.e. det M = 0. Expanding the vanishing determinant gives a polynomial equation p 12 ( ; 0 ) = 0, where p 12 = a 1 2 0 + a 2 0 2 + a 3 2 + a 4 0 + a 5 0 2 + a 6 + a 7 0

and the coefficients a i are polynomial expressions in u 5 ; u 0 5 ; u 6 and u 0 6 .

Exactly the same analysis can be done for the seventh point in images 1 and 3, which leads to M 0 6 6 (x 7 ; 7 ; 00 7 ) T = 0: [START_REF] Heyden | Geometry and Algebra of Multipe Projective Transformations[END_REF] and for the eighth point in images 2 and 3 M 00 6 6 (x 8 ; 0 8 ; 00 8 ) T = 0:

(7)
The vanishing of the determinants jM 0 j and jM 00 j gives the two polynomial equations p 13 ( ; 00 ) = 0 and p 23 ( 0 ; 00 ) = 0, where p 13 and p 23 are given as p 13 = b 1 2 00 + b 2 00 2 + b 3 2 + b 4 00 + b 5 00 2 + b 6 + b 7 00

and p 23 = c 1 0 2 00 + c 2 0 00 2 + c 3 0 2 + c 4 0 00 + c 5 00 2 + c 6 0 + c 7 00 :

The coefficients b i are polynomial expressions in u 5 ; u 00 5 ; u 7 and u 00 7 and the c i in u 0 5 ; u 00 5 ; u 0 8 and u 00

8 . Now, we have to solve the polynomial system of equations 8 < : p 12 ( ; 0 ) = 0; p 13 ( ; 00 ) = 0; p 23 ( 0 ; 00 ) = 0;

for the three unknown camera parameters , 0 and 00 . Since each equation is cubic in the unknowns, there may be as many as 3 3 3 = 27 different solutions in view of Bezout's theorem. However, as the polynomials are not dense, e.g. the monomials 3 , 0 3 and the constant are missing in p 12 , we could expect to have much less than 27 possible solutions.

Computing the resultant, which we denote by p 0 12 , of p 13 and p 23 with respect to 00 yields a polynomial equation in and 0 of degree 7 with coefficients that are polynomial expressions in the image coordinates. Next, taking the resultant of the polynomials p 0 12 and p 12 with respect to 0 , one obtains a polynomial equation in of degree 15.

At this stage, one might (mistakingly) conclude that there are 15 solutions. However, in the derivation we have introduced spurious solutions, which are independent of the image data.

These solutions are identified by carefully inspecting the matrix M 6 6 in (5). If = u 5 and 0 = u 0 5 , then the first column of the matrix M is a zero vector, resulting in the singularity of the matrix M. The same is true for M 0 and M 00 in ( 6) and ( 7), respectively. In summary, all three matrices M, M 0 and M 00 contain a zero column, hence singular if ( ; 0 ; 00 ) = (u 5 ; u 0 5 ; u 00 5 ); ( ; 0 ; 00 ) = (v 5 ; v 0 5 ; v 00 5 ); ( ; 0 ; 00 ) = (w 5 ; w 0 5 ; w 00 5 ); or ( ; 0 ; 00 ) = (0; 0; 0): These solutions imply, in turn, that the camera center one of the three cameras is located at (1; 0; 0; 0); (0; 1; 0; 0); (0; 0; 1; 0) or (0; 0; 0; 1):

For instance, = u 5 gives the first camera center at (1; 0; 0; 0) as the ker(P) = (1; 0; 0; 0). This means that the camera center coincides with the first object point in the projective basis. These 4 solutions are obviously not a general situation and can be easily singled out from the final 15th degree polynomial equation. This concludes the proof that we can have at most 11 = 15 ? 4 solutions. Remark. The special choice of coordinates made above can also be used to solve the minimal case of 6 points visible in all 3 images. Again we have the 3 unknowns , 0 and 00 , representing the unknown parameters in each reduced camera matrix (3) obtained after a projective change of coordinates. Analogously to (4), the images of the sixth point in all three images gives a matrix equation: ? u 5 0 0 ?u 6 0 0 0 ? v 5 0 ?v 6 0 0 0 0 ? w 5 ?w 6 0 0 0 ? u 0 5 0 0 0 0 ?u 0 6 0 0 0 ? v 0 5 0 0 0 ?v 0 6 0 0 0 0 ? w 0 5 0 0 ?w 0 6 0 0 ? u 00 5 0 0 0 00 0 ?u 00 6 0 0 ? v 00 5 0 0 00 0 ?v 00 6 0 0 0 ? w 00 5 0 00 0 ?w 00 = 0 ;

which is homogeneously linear in x 6 , y 6 , z 6 , t 6 , 6 , 0

6 and 00 6 and can be written as M 9 7 (x 6 ; 6 ; 0 6 ; 00 6 ) T = 0 : As M 9 7 must be rank deficient, all 7 7 minors vanish. Consider first the condition obtained from the images of the sixth point in the first and second image, which is the same as in the proof of Theorem 1 and result in a polynomial constraint of the form p 12 ( ; 0 ) = a 1 2 0 + a 2 0 2 + a 3 2 + a 4 0 + a 5 0 2 + a 6 + a 7 0 = 0 :

Similarly the condition obtained from the images of the sixth point in the first and third image, gives p 13 ( ; 00 ) = b 1 2 00 + b 2 00 2 + b 3 2 + b 4 00 + b 5 00 2 + b 6 + b 7 00 = 0 : However, in this case we can also consider the minor obtained from the rows (1; 2; 4; 5; 7; 8; 9) of M 9 7 (assuming w 00 6 6 = 0), giving p 123 ( ; 0 ; 00 ) = c 1 + c 2 0 + c 3 00 + c 4 0 + c 5 00 + c 6 0 00 = 0 :

We now have to solve the system of polynomial equations: 8 < : p 12 ( ; 0 ) = 0; p 13 ( ; 00 ) = 0; p 123 ( ; 0 ; 00 ) = 0:

Taking the resultant of p 13 and p 123 with respect to 00 and then the resultant of this polynomial and p 12 with respect to 0 gives a seventh degree polynomial equation in . Removing the same spurious solutions as above we finally obtain a third order polynomial equation, giving three solutions. Remark. The special choice of coordinates can also be used to solve the minimal case of 7 points visible in 2 images. The details are left to the reader.

A catalogue of minimal cases with missing data

Having solved one minimal case with missing data, we now systematically look for all other possible cases. First, however, we can already apply Carlsson duality [START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF] to the problem we have solved. Recall that Carlsson and Weinshall demonstrated the following remarkable result: Theorem 2 (see [START_REF] Carlsson | Dual computation of projective shape and camera positions from multiple images[END_REF]). The projective reconstruction with n points and m images is equivalent to that with m + 4 points and n ? 4 images. The n points and m images is said to be dual to m+4 points and n-4 images.

For instance, the case of 7 points in 2 images is equivalent to 6 points in 3 images. So knowing that 6 points in 3 images has in general 3 solutions, it follows directly by the Carlsson duality that 7 points in 2 images also has 3 solutions. Now dualizing Theorem 1 for the minimal case of 8 points in 3 images with 1 point missing, we obtain another minimal case with 7 points in 4 images where one point is missing in one of the 4 images.

Corollary 1. There are in general 11 different solutions to the projective reconstruction for 7 points in 4 images where one point is missing in 1 of the 4 images.

The procedure of dualizing can also be demonstrated for the incidence relationship in [START_REF] Faugeras | What can be seen in three dimensions with an uncalibrated stereo rig?[END_REF].

Start by removing the first 4 columns corresponding to 4 base points of the duality. Then transpose the remaining matrix, and add the 4 base columns again. After that we obtain the following dualized incidence relation corresponding to Corollary 1. (10)

Three images

We can now find all other minimal cases for three images.

Let n 2 and n 3 denote the number of points which appear simultaneously only in two and three images. Clearly, n 3 < 6, otherwise we have the case of (at least) 6 points in 3 images, respectively.

The number of unknowns for the three-view geometry is 3 11 for the three cameras and 3 (n 2 +n 3 )?15 for the n 2 +n 3 points modulo a projective transformation, while the number of equations is 4 n 2 + 6 n 3 . By equating the number of unknowns and the number of equations, we have necessary conditions for minimal cases, 4n 2 + 6n 3 = 33 + 3(n 2 + n 3 ) ? 15; i.e. n 2 + 3n 3 = 18: This is a Diophantine equation whose solution is ( n 2 = 3k n 3 = 6 ? k k = 1; :::; 6 : for 0 n 3 < 6, as n 3 6 leads to the trivial non-missing data case.

The solution k = 1 gives n 2 = 6 and n 3 = 5 which may result in the following two incidence relations (not symmetric over three images) in addition to the one that we have solved in Theorem 1:

In general, equating the number of equations and unknowns gives only necessary conditions. It is not sufficient to guarantee a finite number of solutions. For the incidence relation [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF], the first two images have 7 points in common, so it could be solved by Sturm's method resulting in up to 3 solutions. For each of these three solutions, we need to determine the geometry of the third camera. The constraint for the eighth point, visible in images 1 and 3, is given by p 13 in (8). This is a second degree equation in the remaining unknown 00 . Note that is already solved for using images 1 and 2. Hence there are up to two possibilities for the third camera. In total, there might be up to 6 possible solutions for this case.

For the case described by the incidence relation [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF], the geometry of the first two cameras is generally uniquely determined as they have 8 points in common, which is overconstrained, while there are infinitely many possibilities for the third camera, since it is underconstrained.

The other values for k > 1 can be handled in a similar manner, but the resulting polynomial equations are of very high degree and therefore hard to solve. One probably needs to rely on numerical computations.

Four images Let n p , p = 2; 3; 4 denote the number of points which appear simultaneously in p images. Equating the number of unknowns and the number of constraints gives the following Diophantine equation: 4n 2 + 6n 3 + 8n 4 = 44 + 3(n 2 + n 3 + n 4 ) ? 15

i.e. n 2 + 3n 3 + 5n 4 = 29:

There are quite many solutions to the above equation. The complete catalogue for four images consists of all solutions to the above equation. We discuss a few of the cases below for small k, for which the solutions are obtainable with symbolic calculations in, for example, Maple without requiring waste computer resources. n 4 = 5, n 3 = n 2 = 1. This is the dual of the incidence relations shown in [START_REF] Sturm | Das Problem der Projektivität und seine Anwendung auf die Flächen Zweiten Grades[END_REF] and ( 12), (13) So in the first case, there are 6 solutions and in the second case, the cameras and the first 6 points are in general uniquely determined, while the seventh point is undetermined since it is only visible in one image. n 4 = 5, n 3 = 0, n 2 = 4. If the 4 points visible in only 2 images are symmetrically distributed such that no subset of 7 points is common in 2 images, i.e. then one can show, in the same way as in the proof of Theorem 1, that there are up to 27 solutions! The dual case consists of 5 images and 8 points. n 4 = 4, n 3 = 3, n 2 = 0. This is the dual of Theorem 1 whose solution is given in Corollary 1 with incidence relation [START_REF] Quan | Invariants of six points and projective reconstruction from three uncalibrated images[END_REF].

The list of cases continues, but they occur less frequently in practice, and often the complexity of the involved polynomials is too high in order to solve with symbolic computations.

Experiments

The algorithm for 8 points in 3 images described in this paper has been implemented in Maple.

We first demonstrate the algorithm on the popular sequence of images of a wooden house (cf. Figure 2), which has been previously used for different projective reconstruction algorithms by many researchers. Three views covering about a 45 o rotation of the camera around the wooden house are taken. The point features are first detected as the maximum of curvatures of the B-Spline approximation of the edge chains, then automatically tracked for the three images. The location of point features is also optimized by a nonlinear subpixel corner detector. The minimal missing data is shown in Figure 3. The first 5 points are visible in all three images and the 6th point is considered missing in the third, the 7th missing in the second and the 8th missing in the first image. Note that the 7th point is indeed missing in the third image as the side face is becoming tangent to the camera view. As more points are available in this sequence, a traditional method based on bundle adjustment has first been applied using all available 54 points. This 3D reconstruction is used as ground truth.

We start by computing the real solutions of ; 0 and 00 for the projection matrices with the Maple implementation of the algorithm. For each real solution of projection matrices, we compute the projective structure of the set of 8 points. The projective reconstruction is then transformed into its Euclidean representation by applying a space collineation calculated with the 5 known reference points from the ground truth. Finally, the root mean square (RMS) error is computed for the reconstructed 6th, 7th and 8th point w.r.t. their known Euclidean coordinates.

In this real image case, very interestingly, up to the maximum of 11 real solutions are obtained! The lowest RMS solution is considered as the true solution. The other 46 matched points across the three images are also reconstructed in space for this solution. The final reconstruction of all points by the minimal missing data algorithm is superimposed with the reconstruction results obtained by a bundle adjustment. The result is illustrated in Figure 4. The reconstruction is remarkably good, only in the side view, we can see the error is more pronounced for the farther points such as those on the cup. The readers can also compare with that presented in [START_REF] Quan | Invariant of a pair of non-coplanar conics in space: Definition, geometric interpretation and computation[END_REF] using 6 points in 3 images. struction. We first proposed a general framework to parameterize the geometry of the multiple cameras. Then we solved the first problem of 8 points in 3 images with one point missing in one of the 3 images, proving that this problem can have as many as 11 algebraic solutions including complex and negative depth solutions. We also showed that the minimal cases with missing data for reconstruction is generally more complicated than those without missing data. Though we have to solve very high degree polynomial equations, the actual Maple implementation of the algorithms presented in this paper demonstrated remarquable reconstruction results. The accuracy and stability of algebraic solutions with missing data are comparable with those obtained without missing data. It suggests that these algorithms can be practically used for bootstrapping robust and optimal reconstruction. A complete catalogue of the minimal missing data cases for 3 and 4 images is also provided.

Figure 1 :

 1 Figure 1: A frequent practical example of missing data. A cube with 8 corners where (in general) only 7 corners will be visible in each image. Three possible camera positions resulting in three different missing points are indicated by arrows.

Figure 4 :

 4 Figure 4: A general, front and side view of two superimposed reconstructions: the points reconstructed from the minimal missing data are marked as diamonds, and the points from bundle adjustment solution are marked as crosses.

Figure 5 :

 5 Figure 5: RMS errors of 3D reconstruction vs. standard deviation of image noise, for the best and second best solutions of the 8-point algorithm, and the best solution for the 6-point algorithm.

Figure 6 :

 6 Figure 6: The number of real solutions and solutions with all points having positive depths vs. standard deviation of image noise, for the 8-point algorithm.

We are implicitly assuming that the first 5 object points are projectively independent as well as the first 4 points in each image.

Acknowledgments

This work has been done with support from the ESPRIT LTR project CUMULI.

We also check the stability of the algorithm by running on simulated data with the following set-up. We use three real camera matrices similar to the previous real image case, typically obtained from a bundle adjustment algorithm. A set of 8 known points are selected and projected by these projection matrices onto the synthesized images. Then, the projected positions of the points in the images are perturbed by varying levels of noise of a Gaussian distribution. The realism of the simulation is preserved in this way, and the image noise can be quantatively controlled as well in order to observe its influence. From the perturbed image points, the same computation procedure as for the previous real image case is performed. In addition, with the same data, the 8 points were reconstructed using the 6-point algorithm (where all points are visible), resulting in 3 solutions. For each of these solutions, the 7th and 8th point were reconstructed using the obtained camera matrices. The reconstruction errors are graphed in Figure 5, for both algorithms. In Figure 6, the number of real solutions and the number of solutions with all points having positive depths are illustrated.

We note that the solutions degrade very smoothly with increasing noise level. The behaviour of the 8 point algorithm is similar to the performance of the 6-point algorithm. Even if there are several real solutions, we see that there are at most one solution with all points in front of the camera. This suggests that the algorithm presented in this paper is of very practical importance even a very high degree polynomial equation has to be solved.

Conclusions

A new family of projective reconstruction problems using the minimal data from multiple uncalibrated images has been formulated and solved. Instead of the minimal data available in all images, we allow that the minimal data could be partly missing in some of the images. These minimal cases are undoubtedly of theoretical importance in order to understand the geometry of multiple views. But also they are of practical importance for both robust and optimal recon-