Long Quan

Yuichi Ohta

A New Linear Method for Euclidean Motion/Structure from Three Calibrated Affine Views

We introduce a unified framework for developing matching constraints of multiple affine views and rederive 2-view (affine epipolar geometry) and 3-view (affine image transfer) constraints within this framwork. We then describe a new linear method for Euclidean motion and structure from 3 calibrated affine images, based on insight into the particular structure of these multiple-view constraints.

. We demonstrate the method on real image sequences.

Introduction

Motion/structure from orthographic or weak perspective views is a very old and popular topic. It is well known that at least 4 non-planar points over 3 orthographic or weak perspective views are sufficient to uniquely determine motion/structure up to a reflection about the image plane [START_REF] Ullman | The Interpretation of Visual Motion[END_REF][START_REF] Huang | Motion and structure from orthographic projections[END_REF][START_REF] Koenderink | Affine structure from motion[END_REF]. Many algorithms have been published for this problem: the linear methods of Huang and Lee [START_REF] Huang | Motion and structure from orthographic projections[END_REF][START_REF] Lee | Finding point correspondences and determining motion of a rigid object from two weak perspective views[END_REF], nonlinear algebric methods of Koenderink and Van Doorn [START_REF] Koenderink | Affine structure from motion[END_REF][START_REF] Bennet | Structure from two orthographic views of rigid motion[END_REF] and non-linear numerical method of Shapiro et al. [START_REF] Shapiro | 3D motion recovery via affine epipolar geometry[END_REF]. A good review of the different methods can be found in [START_REF] Shapiro | 3D motion recovery via affine epipolar geometry[END_REF].

In this paper, we introduce a unified framework for developing matching constraints of multiple affine views. In particular, 2-view and 3-view constraints will be derived, and all existing methods could be recast into this framework. Our key observation is that classical linear methods for metric motion/structure from 3 orthographic or weak perspective views were heavily based on affine epipolar geometry and did not use the full set of 3 image constraints, thus leading to over-parameterisation and inconsitent motion recovery. Based on insight into the particular structure of these constraints, we will propose a linear algorithm that uses 9 linear parameters to encode the 8 Euclidean motion parameters of 3 weak perspective views.

This work was initially motivated by the application of novel image synthesis from example images, as Euclidean reconstruction from a minimal number of images is required here [START_REF] Mukaigawa | Synthesis of arbitrarily oriented face views from two images[END_REF][START_REF] Zhang | Euclidean structure from uncalibrated images using fuzzy domain knowledge: Application to facial images synthesis[END_REF][START_REF] Quan | Notes on a general framework for 3view based image synthesis with affine cameras[END_REF].

The paper is organised as follows. In Section 2, we review the affine camera model. Then, we introduce a unified framwork for studying the geometric constraints among multiple affine images in Section 3. The linear method for Euclidean motion/structure from 3 calibrated affine images is developed in Section 4. Experimental results are presented in Section 5 and a short conclusion is given in Section 6 Throughout the paper, matrices are denoted in upper case boldface, vectors in lower case boldface and scalars are either in lower case or lower case Greek.

Review of the affine camera model

For a restricted class of camera models, by setting the third row of the perspective camera P ¢¡ ¤£ to ¥ §¦ ©¦ ©¦ , we obtain the affine camera initially introduced by Mundy and Zisserman in [START_REF] Mundy | Geometric Invariance in Computer Vision[END_REF][START_REF] Aloimonos | Perspective approximations[END_REF]]

A ¡ £ ! ©" # $# %" # '& (" # " # £ " ©& )# %" ©& $& (" ©& " ©& £ ¦ ¦ ¦ " £ 0 1 32 M & ¡ 0 # ¡ t ¢¡ # 54 76
The affine camera A ¡ £ subsumes the orthographic, weak perspective and para-perspective. For more detailed relations and applications, one can refer to [START_REF] Shapiro | 3D motion recovery via affine epipolar geometry[END_REF][START_REF] Quan | Self-calibration of an affine camera from multiple views[END_REF].

Finite points in affine spaces

tS ¥ §T # VU T 'T & U T PI ¥ " # £ U )" '£ ¨" W& £ U )" £ XI
. If we further use relative coordinates of the points with respect to a given reference point (for instance, the centroid of a set of points), the vector tS is cancelled, and we obtain the following linear mapping between relative space points and relative image points:

u M & ¡ x 6 (1)
Equation ( 1) is the basic projection equation for points in an affine camera when relative coordinates are used. The reference point to determine the relative coordinates determines uniquely the translational component of the affine projection matrix. Throughout this paper, the reference point is always taken to be the centroid in each image.

Unifying 2-view and 3-view geometry of points

For projective cameras, the geometric constraints among multiple projective views have been thoroughly studied in [START_REF] Triggs | Matching constraints and the joint image[END_REF][START_REF] Shashua | Algebraic functions for recognition[END_REF][START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between images[END_REF]. There has been no similar effort for affine camera case, although the geometric constraints among affine views are well known.

For notational simplicity, rewrite Equation (1) as u M & ¡ x 6

We can now examine the matching constraints between multiple views of the same point. Let the three views of the same point x be given as follows:

¡ ¢ £ u Mx ü¤ M¤ x ü¤ ¤ M¤ ¤ x 6 (2)
These can be rewritten together in matrix form as

! M u M¤ u¤ M¤ ¤ u¤ ¤ 0 1 2 x 4 ¦ ¨( 3
)
where ¦¥ ¦ encodes the (unrecoverable) global scale factor of the reconstruction.

As the vector ¥ x $ XI can not be zero, the rank of the coefficient matrix is at most 3, so all of its § © § minors vanish. There are £ G Q § Q § Q § such minors, which can be divided into two types:

2-view constraints involving only two views with two rows from each view, 3-view constraints involving all three views with two rows from one view and one from each of the others.

There are three 2-view and three sets of four 3-view constraints. Among the 3 sets of 3-view constraints, only one of them is independent due to the symmetry.

Each expansion of these § ¨ § minors is linear in the image coordinates u, u¤ and u¤ ¤ with the coefficients T "! coming from the ¨ minors of the following # $¨ joint projection matrix: PI 6 There are in total % ¦ (' Q ) § Q ' such minors, as we will see later that 4 of the 20 minors are common to the 2-view and 3-view constraints. All these minors provide a linear coordinate system to span the joint projection matrix. The constraints for more than 3 views will be briefly discussed in Section 6.

¥ M I ¨M¤ I ¨M¤ ¤ I PI ¥ 'G &% G ¤ % ¤ G ¤ ¤ % ¤ ¤

Two-view constraints

There are three 2-view constraints corresponding to the 3 pairs of the 3 views, namely the vanishing of the determi- The affine epipolar geometry equation was introduced in [START_REF] Huang | Motion and structure from orthographic projections[END_REF] for orthography, and later in [START_REF] Lee | Finding point correspondences and determining motion of a rigid object from two weak perspective views[END_REF] for weak perspective and also in [START_REF] Shapiro | 3D motion recovery via affine epipolar geometry[END_REF]. Shapiro et al. nicely related the affine epipolar geometry with Koenderink and Van Doorn's rotation parameterisation [START_REF] Koenderink | Affine structure from motion[END_REF]. But Koenderink's method is equivalent to Lee and Huang's [START_REF] Lee | Finding point correspondences and determining motion of a rigid object from two weak perspective views[END_REF].

nants 0 G 1% G ¤ % ¤ 32 , 0 G 1% G ¤ ¤ % ¤ ¤ 42 and 0 G ¤ % ¤ G ¤ ¤ % ¤ ¤ 42 : T # 65 Q T # £ 67 Q T # S 5 ¤ Q T 98 7 ¤ ¦ T # "@ 5 ¤ Q T # 67 ¤ Q T # BA 5 ¤ ¤ Q T # "C 7 ¤ ¤ ¦ T # 8 5 Q T & S 7 Q T # '& 5 ¤ ¤ Q T # $# 7 ¤ ¤ ¦

Three-view constraints

There are four 3-view constraints from the vanishing of the determinants 0 G % G ¤ G ¤ ¤ H2 , 0 G % I% ¤ G ¤ ¤ 42 , 0 G 1% G ¤ % ¤ ¤ 42 and 0 G 1% P% ¤ % ¤ ¤ 42 . By careful inspection of the minors (for example, using the computer algebra tool Maple), we have:

T £ Q5 Q T C 7 Q T # $# 5 ¤ Q T 98 5 ¤ ¤ ¦ T & 5 Q T Q7 Q T # # 7 ¤ Q T # S 5 ¤ ¤ ¦ T R5 Q T A 7 Q T # '& 5 ¤ Q T 98 7 ¤ ¤ ¦ T # 5 Q T @ 7 Q T # X& 7 ¤ Q T # S 7 ¤ ¤ ¦ 6
Among 12 minors, 8 of them are new ( T # to T C

) and 4 of them are common with 2-view constraints (

T S8 to T # X& ).
These are the transfer equations over three views [START_REF] Ullman | Recognition by linear combinations of models[END_REF]. Any orthographic view of a point set can be expressed as a linear combination of two other views if this point set undergoes a linear transformation in space. This has been extensively used in object recognition.

Since each point correspondence gives 4 linearly independent 3-view constraints, 4 points give

¥ § UT G V § G 1%
linear equations for solving these minors.

The appearance of common minors between 2-view and 3view constraints is not accidental, as we have 3+4=7 constraints, each of them has 4 coefficients, that amounts to § ¨¡ % ' . As there are only 20 minors, so 8 of them should appear at least more than once.

Euclidean motion/structure from 3 calibrated affine views

So far, the linear estimates of the 2-view and 3-view constraints yield, directly but implicitly, the affine motion/structure. To get Euclidean or more exactly similarity motion/structure, we need at least 3 calibrated affine images. Here we use the unified formulation introduced in [START_REF] Quan | Self-calibration of an affine camera from multiple views[END_REF] for calibrated affine cameras, thus the method developed will be valid for all calibrated orthographic, weakperspective and para-perspective models.

Each projection matrix M & ¡ can be decomposed [START_REF] Quan | Self-calibration of an affine camera from multiple views[END_REF] into

M

¢ KR ¨where ¢ is a scaling factor of the whole image, K is the intrinsic parameter matrix (for instance,

K 2 £ ¦ ¦ G 4
¨where £

is the aspect ratio for the weakperspective case), and R & ¡ represents 2 rows of a 3D rotation matrix. As we are assuming calibrated cameras, the intrinsic parameter matrix K is known and its inverse can be directly applied to the image points so that its effect is removed completely. So the projection matrix M for normalised image coordinates becomes M ¤¢ R ¨i.e. a scaled % ¨ rotation matrix. There are in total ' % ¨ Q % Euclidean parameters for a set of 3 views: two relative 3D rotations R and G each having 3 d.o.f. and 2 relative scale factors ¢ and ¢ ¤ between (say) the first view and the remain- ing ones.

Any linear algorithm will consist of first estimating linearly the minors using multiple view constraints, then extract the 8 Euclidean parameters from these minors by identifying the projection matrices M and M¤ with the scaled rotation matrices ¢ R and ¢ ¤ G.

Combining 2-view and 3-view constraints

We should keep in mind that although all 7 constraints are linearly independent, only ¥ # T ¨¥ § ©T of them are algebraically independent due to Grassmanian relations. There are in total 20 homogeneous coefficients-minors of the joint projection matrix. How to choose the most appropriate constraints is of primary importance. The selected constraints should be algebraically independent and contain as few coefficients as possible.

Taking only the three 2-view constraints is a poor choice since the third one is partially dependent on the first two by the composition rule on the rigid motions and each one is completely separate from the others. Taking only the 3view constraints leads to a complicated algebraic manipula-tion for the extraction of Euclidean parameters. Hence we combine 2-view and 3-view constraints.

The key observation is that there are common coefficients between 2-view and 3-view constraints: two of the three 2-view constraints share 4 minors T S8 T # S 'T # $# and T # '& with the 3-view constraints. This allows us to use the following combination: two 2-view constraints plus one of the 3-view constraints.

¡ ¢ £ T £ 5 Q T C 7 Q T # # 5 ¤ Q T 98 5 ¤ ¤ ¦ ©T # 5 Q T # £ 7 Q T # S 5 ¤ Q T 98 7 ¤ ¦ ©T # "@ 5 Q T # 7 Q T # '& 5 ¤ ¤ Q T # # 7 ¤ ¤ ¦ 6
These 10 unknown minors can be solved as a single homogeneous vector under the constraint ¥ ¦¥ t # S ¥ §¥ G :

! 5 7 5 ¤ ¤ ¦ 5 ¤ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 7 ¤ 5 ¤ ¦ ¦ 5 7 ¦ ¦ ¦ ¦ ¦ ¦ 7 ¤ ¤ 5 ¤ ¤ ¦ ¦ 5 7 0 1 t ¦ 6
Any ratio Assume that the affine epipolar geometry of two views is estimated as

¥ © W ¥ 5 ¨7 ¨5 ¤ ¨7 ¤ PI ¦
. From 3 ratios ! , exactly 3 Euclidean parameters can be extracted. Using a scaled rotation matrix instead of M, the following relation holds: " # $ % $ &¢ (' & T ¢ )' V # ' & T ' # 6 Therefore, the relative scale factor between the two views is immediately given as ¢ C 10 32 54 60 7 0 2 58 0 6

According to Koenderink and Van Doorn, the entire rotation can be decomposed into a rotation in the image plane (assume this rotation angle to be 9 ) and a rotation through an angle @ about an axis (angled at A to the positive x axis) in a frontoparallel plane. The rotation matrix in terms of Koenderink and Van Doorn's 9 T BA ©T C@ representation [16] can be recomposed as R ¢¡ : " # $ % $ ¢ yx @ 1 x ¥ A T 9 ¢ yx @ x ¦ ¥ A T 9 T 1 x A x @ T x G A x @ hence, the rotation angle in the image plane is easily determined by A 8 7 ¨and the rotation axis modulo out of the image plane by ¥ A T 9 4

D E GF

C

Obtaining the full solution with the 3-view constraint Up to this point, the only unknown is the rotation angle out of the image plane @ , which is the only component that generates depth information. The one-parameter family of solutions for the rotation matrix between the two views is

R ¢¡ ¥ @ 2 D & ¡ & Q 1 x @ E & ¡ & x G @ F & ¡ # x G @ G # ¡ & ( x @ 4 ẅhere D & ¡ & ¨E& ¡ & ¨F& ¡ # and G # ¡ &
are the known quantities.

Similarly, with the second 2-view constraint, we get another one-parameter family of solutions for the rotation matrix G ¢¡ ¥ @ ¤ of the other 2 views in terms of the unknown rotation angle out of the image plane @ ¤ . Now, it is time to use the 3-view constraint to fully determine the motion/structure. It can be easily verified that

T £ T C T # # T 98 ¢ ¢ ¤ ¥ ' # # ¡ # T ¡ # # ' # ¢ ¢ ¤ ¥ ' # X& ¡ # T ¡ # X& ' # T ¢ ¤ ¡ # ¢ (' # 6
Substituting the ratio

T B8 U T # # into T £ U T # $# and T C U T # #
, we get exactly 2 linear equations in 1 x @ and 1 x @ ¤ ,

¢ ¤£ ¦¥ £ H ©H ( x @ Q ( x @ ¤ Q £ ¨ §£ H ©H ¤ ) 1 x @ Q ¤ ( ( x @ ¤ Q ¤ i.e. A & ¡ & 2 1 x @ 1 x @ ¤ 4 B & ¡ # ¢6

Remarks

This new formulation contains only E G V¦ T G independent parameters, compared with the 8 Euclidean motion parameters of the set of 3 views, it is a minimal linear parameterisation.

The advantage of solving t as a whole is that it pro- vides more information, for instance the knowledge of the ratio T "8 T # $# which could not be recovered from 2-view constraints is the key for a linear solution in ( x @ and 1 x @ ¤ . Huang and Lee had to re-compute this ratio at the very begining of the second step with the rotation composition constraint.

Solving directly and linearly for 1 x @ and 1 x @ ¤ is of great significance. On the one hand, the intrinsic twoway ambiguity is nicely expressed by the fact that 1 x ¥ T @ ( x @ 6 This parameterisation indeed makes a linear solution possible since the two equations are solved together. On the other hand, the only failure mode of the entire linear algorithm is the possibility that 1 x @ © G which may happen due to numerical error when ( x @ is close to 1. Since 1 x @ G @ ¦ ©ẗ his means that actually there is almost no rotation out of the image plane. As rotation out of the image plane is the only component which contains depth information, this means that the 2D images we used do not contain the desired 3D structure, or equivalently we can report that @ ¦ for the motion. Essentially, this algorithm does not have the failure mode that the factorisation method suffers in its linear version.

Comparison with related work

We first make a comparison with the existing linear algorithms of Huang and Lee and the factorisation method of Tomasi and Kanade.

Basically, there are two steps in Huang and Lee's method [START_REF] Huang | Motion and structure from orthographic projections[END_REF], the first step computes the coefficients of the three 2view constraints. Any 3-view constraint was totally absent during the batch solution step and was introduced in the second step by the composition rule of rotation matrices

R # 7 R & R # X&
. In our new linear algorithm, the 3-view constraint has been already integrated in the first numerical step. No any other constraint was used afterwards. Since Euclidean depth information is only contained in 3-view constraints, therefore, it is dangerous to not use any 3-view constraint during the numerical step. Although 3 2-view constraints have also E @ ¨ independent parameters if each one is estimated individually, but they are essentially a set of 12 homogeneous parameters which breaks up into 3 sets of 4 homogeneous parameters. If we examine carefully the second step of Huang and Lee's method, it has to recompute this set of 12 homogeneous parameters (via the ratios between these 3 sets of 4 homogeneous parameters) using the 3-view constraint. In conclusion, Huang and Lee's method does not use the appropriate constraints. It will inevitably lead to the inconsistencies of the rotation matrix.

Compared with the factorization method of Tomasi and Kanade [START_REF] Tomasi | Shape and motion from image streams under orthography: A factorization method[END_REF][START_REF] Poelman | A paraperspective factorization method for shape and motion recovery[END_REF][START_REF] Weinshall | Linear and incremental acquisition of invariant shape models from image sequences[END_REF]-most suitable for redundant views, the major problem is to impose the 'metric constraint'. The linearly estimated matrix which is the product of an affine transformation and its transpose may not be positive definite, the whole Euclidean reconstruction process fails. The exact Cholesky parameterisation of the matrix introduced in [START_REF] Quan | Self-calibration of an affine camera from multiple views[END_REF] needs to solve simultaneous quadratic equations.

Other important work include Koenderink and Van Doorn [START_REF] Koenderink | Affine structure from motion[END_REF]. The method consists of three steps. The first step shows that the scale change between 2 views, the rotation in the image plane around the viewing direction and the projection of the rotation axis out of the image plane can be ob-tained with 2 views of 4 points. The second step is to parameterise the remaining Euclidean structure with the angle of the rotation out of the image plane and the 2 depths of the reference triangle, then eliminate the unknown angle to get a quadratic equation on the 2 Euclidean depths. Finally, with the third view, a second quadratic equation is obtained. Intersecting these two quadratics gives 4 possible solutions for the two depths. These intersections represent either one or two pairs of solutions that are related through a reflection in the fronto-parallel plane.

We can see that the first step of Koenderink and Van Doorn's method is similar to that of Huang and Lee [START_REF] Huang | Motion and structure from orthographic projections[END_REF] and Lee and Huang [START_REF] Lee | Finding point correspondences and determining motion of a rigid object from two weak perspective views[END_REF], it uses 2-view constraint to get partial solutions although Koenderink and Van Doorn's is more geometrically oriented. One major difference is that Koenderink and Van Doorn do not use the third 2-view constraint as Huang and Lee did. Unfortunately, Koenderink's method needs to intersect two quadratics for each pair of points, and can not handle all available points. Shapiro et al. [START_REF] Shapiro | 3D motion recovery via affine epipolar geometry[END_REF] extended Koenderink and Van Doorn's first step by nicely relating the Koenderink and Van Doorn's rotation representation to the affine epipolar geometry. Unfortunately they failed to get a closed form solution and adopted a non linear numerical optimisation approach for the 3-view case.

Ullman and Basri [START_REF] Ullman | Recognition by linear combinations of models[END_REF] and Poggio [START_REF] Poggio | A network that learns to recognize three-dimensional objects[END_REF] considered the 3-view constraint for linear combination for recognition. Although they essentially show the equivalence with motion/structure, they do not concentrate on motion/structure recovery, in fact there is no closed form solution which allows Euclidean structure extracted directly from linear combination coefficients.

Experimental results

The linear method for motion/structure from 3 calibrated affine images developed in this paper has been implemented and applied to real image sequences.

We first acquired a sequence of images of a calibration pattern with a standard camera mounted on a robot. It is important to stress that the imaging conditions were not chosen to be close to affine. The triplet of images we used is shown in Figure 1. The 69 points have been automatially identified and tracked for the triplet. , 9 T ¦ 6 I , @ ¦ 6 P and ¢ ¤ G 6 G G , A ¤ T G 6 , 9 P¤ T ¦ 6 § ¡ , @ ¤ ¦ 6 § . The re- sulting shape reconstruction from these motion parameters is shown in Figure 2. To evaluate the reconstruction quality, we did the same 3D reconstruction using a full perspective camera model, for instance the method described in [START_REF] Christy | Euclidean shape and motion from multiple perspective views by affine iterations[END_REF] is used. The two reconstructions differ by a 3D similarity transformation which can be easily estimated. The normalised relative error of the Euclidean reconstruction with affine camera with respect to perspective camera one is 6 # percent. We also tried our method on the popular hotel sequence kindly provided by Poelman and Kanade at CMU. In this sequence, the camera motion included substantial translation away from the camera and across the field of view. 197 points throughout the sequence of 181 images are automatically identified and traced. For a more detailed description of this set-up, consult [START_REF] Poelman | A paraperspective factorization method for shape and motion recovery[END_REF]. The triplet of images we used are displayed in Figure 4. The resulting 3D reconstruction is shown in Figure 5.

Conclusion

We have introduced a unified approach to 2-view and 3view geometric constraints of affine images, and a new linear method for Euclidean motion/structure from 3 calibrated affine images. The method has been validated on real image sequences. The application of the method to novel view synthesis is underway.

What is also important for the framework of multiple affine views developed in this paper is that line segment features could also be incorporated. Line segments over 3 affine views are essentially characterised by a % ¨% ¨% trilinear tensor [START_REF] Quan | Affine structure from line correspondences with uncalibrated affine cameras[END_REF]. It is easy to prove [START_REF] Quan | Notes on a general framework for 3view based image synthesis with affine cameras[END_REF] that the 3-view constraints on the points share the 8 components of the tensor, this opens the way to combine points with line segments. The more detailed developement could be found in [START_REF] Quan | Notes on a general framework for 3view based image synthesis with affine cameras[END_REF]. We can also mention that the geometric constraints of 4 affine views involving only one image coordinate can also be derived using the same framework.

6

 6 These are the affine epipolar geometry. The set of § G % coefficients T "! for D FE ¨6 H6 H6 G% ¦ are 12 of the 20 minors of the joint projection matrix. Each point correspondence from two images gives one homogeneous linear equation, taking into account of the reference point for relative coordinates, 4 points are sufficient for uniquely determining the affine epipolar geometry.

Figure 1 .

 1 Figure 1. The triplet of images of the calibration pattern.

Figure 2 .

 2 Figure 2. Two views of the resulting 3D reconstruction.

Figure 3 .

 3 Figure 3. Two different views of the two superimposed 3D reconstructions, one uses weak-perspective camera model (marked by a square) and the other full perspective (marked by a circle).

Figure 4 .Figure 5 .

 45 Figure 4. The triplet of hotel image sequence.

  ¦H PI RQ SF UT WV UV UQ XF UY `V §Q SF UY aI Rb 6V )c RQ SF UT WV UQ SF §b 6V dF ¦H PI RQ SF UT WV UV UQ XF UY `V §e XF §Y fI gb ©V hI iQ XF pT WV §e XF §b ©V e ©F UY `V §e XF UT WV F §H qI RQ SF pT WV §V Ue ©F UY `V §Q SF UY aI Rb 6V )c RQ SF UT WV Ue ©F Ub 6V dF ¦H PI RQ SF UT WV UV §e XF §Y `V Ue ©F UY fI gb 6V (c RQ XF pT WV §Q SF Ub 6V rI "Q SF §Y `V Ue ©F pT WV

	I "e ©F pT WV §e XF §Y 5I gb 6V	e ©F pT WV §Q SF UY sI Rb 6V	Q XF pT WV ut v Rw
	Therefore,

Acknowledgment This work was in part supported by European CUMULI project and University of Tsukuba. We would also like to thank S. Christy for providing comparative reconstruction results.


Caroline Baillard
email: caroline@robots.ox.ac.uk

Cordelia Schmid
email: cordelia.schmid@inrialpes.fr

Andrew Zisserman

Andrew Fitzgibbon

Automatic line matching and 3D reconstruction of buildings from multiple views

Keywords: line matching, building reconstruction, urban areas, multiple views, planar homography

This paper describes two developments in the automatic reconstruction of buildings from aerial images. The first is an algorithm for automatically matching line segments over multiple images. The algorithm employs geometric constraints based on the multi-view geometry together with photometric constraints derived from the line neighbourhood, and achieves a performance of better than 95% correct matches over three views. The second development is a method for automatically computing a piecewise planar reconstruction based on the matched lines. The novelty here is that a planar facet hypothesis can be generated from a single 3D line, using an inter-image homography applied to the line neighbourhood. The algorithm has successfully generated near complete roof reconstructions from multiple images. This work has been carried out as part of the EC IMPACT project. A summary of the project is included.

INTRODUCTION

Reconstruction of buildings from aerial images has received continual attention in the photogrammetry and computer vision literature. One approach is to compute a dense digital elevation model from multiple images using correlation based stereo. However, the resulting dense depth map is generally insufficiently accurate or complete to enable the precise shape of buildings to be recovered [START_REF] Berthod | High-resolution stereo for the detection of buildings[END_REF][START_REF] Baillard | Segmentation of urban scenes from aerial stereo imagery[END_REF][START_REF] Girard | Building detection from high resolution colour images[END_REF]. Thus most approaches have focused on reconstruction of specific building models: rectilinear shapes [START_REF] Mcglone | Projective and object space geometry for monocular building extraction[END_REF][START_REF] Roux | Feature matching for building extraction from multiple views[END_REF][START_REF] Noronha | Detection and description of buildings from multiple images[END_REF][START_REF] Collins | The ascender system: Automated site modeling from multiple images[END_REF], flat roofs [START_REF] Berthod | High-resolution stereo for the detection of buildings[END_REF], or parametric models [START_REF] Haala | Data fusion for the detection and reconstruction of buildings[END_REF]Hahn, 1995, Weidner and[START_REF] Weidner | Towards automatic building extraction from high-resolution digital elevation models[END_REF]. Recently, more generic reconstruction approaches involving multiple high-resolution images have been proposed [START_REF] Bignone | Automatic extraction of generic house roofs from high resolution aerial imagery[END_REF][START_REF] Moons | Automatic modelling and 3d reconstruction of urban house roofs from high resolution aerial imagery[END_REF].

The difficulty of reconstruction in urban environments comes from the complexity of the scene: the buildings are dense and varied, and the resulting image boundaries often have poor contrast. Consequently, feature detectors fragment or miss boundary lines, and only an incomplete 3D wireframe can be obtained. This paper presents our approach to solving this problem, which makes two contributions: First, an algorithm for matching individual line segments over multiple views; Second, an algorithm for computing planar facets of the scene starting from the matched lines. The key idea, which is common to both algorithms, is that both geometric and photometric constraints should contribute from all images.

In the line matching algorithm the match is computed using multi-view geometry and photometric similarity measures on the line neighbourhood in each image. Special attention is paid to using multiple images to overcome the deficiencies of the line segment feature extraction. In particular fragmented lines are joined and missing edges recovered. The algorithm is described in section 3.

In the plane generating algorithm 3D planar facets of the scene are computed by using both lines and their image neighbourhoods over multiple views. These surface facets then enable both line grouping and, by plane intersection, the creation of lines which were missed during feature detection. The particular novelty of the method is in the use of inter-image homographies (plane projective transformations) to robustly estimate the planar facets. It requires minimal image information since a plane is generated from only a line correspondence and its image neighbourhood. In particular two lines are not required to instantiate a plane. These minimal requirements and avoidance of specific building models facilitate the automatic reconstruction of objects with quite subtle geometry located within a complex environment. The algorithm is described in section 4.

Our work is part of the European IMPACT project and we begin with an overview of this project.

THE IMPACT PROJECT

The IMage Processing for Automatic Cartographic Tools (IMPACT) project is a five site collaboration funded under the European Community Esprit Long Term Research Programme. The partners are the Universities of Bonn (Germany), Leuven (Belgium), Oxford (England), Ecole Nationale Sup érieure des T él écommunications (ENST, France), and Eurosense (Belgium).

The objective of the IMPACT project is the automatic generation of 3D scene descriptions of urban and suburban areas from aerial imagery. Although this is a much studied problem in computer vision and photogrammetry, there are several aspects that differentiate the project from related work: First, the input data consists of high resolution colour images (¢ ¤£ ¥ §¦ ¨¢ ¤£ ¥ © on the ground, RGB). Second, at least 3 images taken from different positions are available of the scene. The project goes further than the traditional 2-view stereo approach and exploits the redundancy in such image sets to the full. Third, the scenes are of higher complexity than those that have traditionally been studied. In European urban and suburban areas buildings are often packed together and of variable types and irregular shapes. Figure 1 shows an example of six typical overlapping views which are used as input data within the project.

The strategy explored within the project is to generate as quickly as possible 3-dimensional information and perform all grouping and modelling operations in the 3-dimensional world. There is an abundance of geometric primitives in the individual images, and great care has been taken that only reliable 3-dimensional information is generated. To achieve this, information is verified over multiple images with typically 4 to 6 images being used. Although there is a wide diversity in the shapes of the individual buildings, almost all of them can initially be described as polyhedral structures. Hence, coplanarity of points and lines is the dominant criterion present in the grouping and modelling algorithms.

The five partners have developed various parts of the integrated system. Often their areas overlap, but the following summarizes the main emphasis at each site.

Bonn focused on generating a symbolic 3D description of the scene from a number of symbolic 2D image descriptions. The 2D description consists of a Feature Adjacency Graph (FAG), for example a 2D corner and its associated line segments and regions. The idea is to transfer the neighbourhood relations that are available from the images into object space and to use them to produce consistent 3D object descriptions. This involves matching the 2D descriptions over multiple images. Details are given in [START_REF] Brunn | Hierarchical bayesian nets for building extraction using dense digital surface models[END_REF]Weidner, 1998, Fischer et al., 1998).

ENST developed methods for the identification of buildings in the images by refining and analysing dense disparity maps between image pairs. These methods are based on two major ingredients: an in-depth statistical study of the distribution of 3D points on homogeneous areas and a careful analysis of the geometrical properties of local planar surfaces. Photometric information and general knowledge about the scene geometry are also exploited to detect and to reconstruct the buildings. Details are given in (Fradkin et al., 1999a, Fradkin et al., 1999b).

Eurosense provided the source images used by all the partners. They are 11500 ¦ 11500 pixel aerial images, with a ground length of 8.5 cm per pixel. The calibration and the orientation of the camera were also supplied for each view. Six overlapping subparts are shown in figure 1.

Leuven focused on grouping 3D line segments into polygonal faces of the roof structure. This is achieved by first grouping the extracted 3D line segments into sets of coplanar line segments. For each such set initial polygon hypotheses are formed using an algorithm based on the convex hull of the line end points. These hypotheses are then verified both in 3D and by back-projection in the images. The emphasis during this modeling stage is on extracting the correct topology of the roof structure rather than on the metric accuracy of the reconstruction. This allows a more efficient roof modeling involving few criteria. Errors in the polygon's shape are corrected by exploiting symmetry relations and a general preference for rectangular structures in buildings. Metric accuracy is obtained in an additional step by back-projecting the recovered (wireframe) model of the roof structure into the images and minimizing the total reprojection error. Details are given in [START_REF] Moons | Automatic modelling and 3d reconstruction of urban house roofs from high resolution aerial imagery[END_REF].

Oxford developed two areas. The first is a method for matching individual line segments between images. The method is described in section 3 of this paper and [START_REF] Schmid | Automatic line matching across views[END_REF]. The second is a method for automatically reconstructing 3D piecewise planar models from multiple images of a scene. The method is described in section 4 and in [START_REF] Baillard | Automatic reconstruction of piecewise planar models from multiple views[END_REF].

These approaches can cooperate in many ways. For example, the 3D lines produced by the Oxford line matching algorithm are used as input data by all partners. The strategy of ENST, based on dense disparity maps, is complementary to the feature-based approaches of the other partners. And the methods developed by Leuven and Oxford for generating polygonal faces are also complementary as will be explained in section 5.

LINE MATCHING OVER MULTIPLE VIEWS

Line matching is a difficult problem for several reasons. The first is due to the deficiencies in extracting lines and their connectivity: although the orientation of a line segment can be recovered accurately, the end points are not reliable, and furthermore the topological connections between line segments are often lost during segmentation. The second reason is that there is no strong disambiguating geometric constraint available over 2 views: In the case of points (corners), correspondences must satisfy the epipolar constraint. For infinite lines there is no geometric constraint, whilst for lines of finite length there is only a weak overlap constraint arising from applying the epipolar constraint to end points.

Existing approaches to line matching in the literature are of two types: those that match individual line segments; and those that match groups of line segments. Individual line segments are generally matched on their geometric attributes -orientation, length, extent of overlap [START_REF] Medioni | Segment-based stereo matching[END_REF][START_REF] Ayache | Stereovision and Sensor Fusion[END_REF][START_REF] Zhang | Token tracking in a cluttered scene[END_REF]. Some such as [START_REF] Crowley | Measurement and integration of 3d structures by tracking edge lines[END_REF][START_REF] Deriche | Tracking line segments[END_REF][START_REF] Huttenlocher | Comparing images using the Hausdorff distance[END_REF]) use a nearest line strategy which is better suited to image tracking where the images and extracted segments are similar.

Matching groups of line segments has the advantage that more geometric information is available for disambiguation. A number of methods have been developed around the idea of graph-matching [START_REF] Ayache | Building a consistent 3D representation of a mobile robot environment by combining multiple stereo views[END_REF][START_REF] Horaud | Stereo correspondence through feature grouping and maximal cliques[END_REF][START_REF] Gros | Matching and clustering: Two steps towards object modelling in computer vision[END_REF][START_REF] Venkateswar | Hierarchical stereo and motion correspondence using feature groupings[END_REF]. The graph captures relationships such as left of, right of, cycles, collinear with etc, as well as topological connectedness. Although such methods can cope with more significant camera motion, they often have a high complexity and again they are sensitive to error in the segmentation process.

The matching algorithm presented here is based on the one described in [START_REF] Schmid | Automatic line matching across views[END_REF], originally developed for three images. It is extended here to use any number of input images. The idea is to use the photometric neighbourhood of the line for disambiguation. Epipolar geometry is used to provide a point to point correspondence on putatively matched line segments over two images. The similarity of the line's neighbourhoods is then assessed by cross-correlation at the corresponding points. If the viewpoints are very different (for example a large baseline relative to depth or a substantially different attitude between views) then a correction is required to the cross-correlation neighbourhood. The computation of this correction (which is based on a planar homography) is described in [START_REF] Schmid | Automatic line matching across views[END_REF].

Two-view matching

This section describes the geometric and photometric constraints used in matching line segments between two views.

Reducing the search space. When matching lines over two views there is a weak overlap constraint for line segments of finite length arising from epipolar geometry. The two end-points of a segment generate two epipolar lines in the other image. These two lines define a region, called the epipolar "beam", which necessarily intersects or contains the corresponding segment [START_REF] Zhang | Token tracking in a cluttered scene[END_REF]. Figure 2 illustrates this idea. Therefore a search region in the second image is determined for each segment in the first image. This reduces the complexity of the search for corresponding segments.

Pairwise matching score. For each pair of lines which satisfies the geometric constraint above, the photometric information available from the surfaces in the neighbourhood of the lines is used to compute a photometric matching score. The basic idea is to treat each segment as a list of points to which neighbourhood correlation is applied as a measure of similarity. Only the point to point correspondence is required, and this is provided by the epipolar geometry.

Corresponding image points, represented as homogeneous 3-vectors & and & ! , satisfy the epipolar constraint: & (' 0) 21 3& 54 £ ¤£ 1 is the fundamental matrix, which is a 6 ¦ 76 matrix of rank 2. The epipolar line corresponding to & is ' # 4 81 3& , and the epipolar line corresponding to & ! is # 4 91 ) & ! . Note, lines are also represented by homogeneous 3-vectors, and ! in all cases indicates the second image.

Suppose two image lines, and ' correspond (i.e. have the same pre-image in 3-space) then the epipolar geometry generates a point-wise correspondence between the lines. A point & on corresponds to the point & ! which is the intersection of @! and the epipolar line 3). This construction is valid provided is not an epipolar line.

' # of & : The point & ! 4 ' ¦ A ' # 4 ' ¦ CB 1 3& (D (see figure
The matching score for a pair of line segments and 0! is computed as the average of the individual correlation scores for the points (pixels) of the line. The only points included in this average are those that are common to both line segments, i.e. the correlation is not extended past the ends of the measured segments. The pair hypothesis is valid if the matching score is above a certain threshold.

Three-view matching

With three views there is a strong geometric constraint available for line matching. The trifocal tensor (Spetsakis and [START_REF] Spetsakis | Structure from motion using line correspondences[END_REF][START_REF] Shashua | Trilinearity in visual recognition by alignment[END_REF][START_REF] Hartley | A linear method for reconstruction from lines and points[END_REF] enables lines matched in two views to be transferred to a third, and this process can be used to verify two view matches. This constraint provides a method for verifying putative pairwise line matches.

The matching algorithm over 3 views proceeds as follows: first a set of triple hypotheses is determined from putative pairwise matches, then consistent matches are selected.

Search for triple hypotheses. For every putative pair with a high correlation score (determined according to section 3.1), the position of the line in the third image is predicted using the trifocal tensor.

There are then two verification tests for the pair hypotheses:

geometric verification: a line segment is detected at the predicted position in the third image ; photometric verification: there is a sufficiently strong pairwise correlation score between the second and the third image at the predicted line position.

There are two possibilities: If the geometric test is passed, the photometric test must also be passed, but the score threshold is more lenient than that used in the two view matching (about 50% of its value). Otherwise, if the geometric test is not passed, the pair hypothesis can still be verified by the photometric test, but the score threshold is more conservative than that used in the two view matching (about 50% more than its value). A match can therefore be verified whether or not there is a line segment at the predicted position.

A search is also computed proceeding from pairwise matches in views two and three and verifying in view one.

Only consecutive views are used here for the two-view matching (i.e. matching is not performed between views 1 and 3) because of their greater photometric similarity.

Final matching set. The triple hypothesis set produced at the previous stage needs not to be consistent because one line can be associated with several lines in another image arising from different triplets. A consistent match set is therefore determined by a "winner takes all" scheme : whenever a line belongs to several triples, only the triple with the best score is retained.

Implementation details. The 2D line segments are extracted by a local implementation of the Canny edge detector at sub-pixel accuracy. Edgels are then linked into chains, jumping up to a one pixel gap. Tangent discontinuities in the chain are located using a worm, and line segments are fitted between the discontinuities using orthogonal regression. A very tight threshold is used for the line fitting so that curves are not piecewise linear approximated. Only line segments above a minimum length (here 15 pixels) are considered for matching. For computational efficiency, in each image the lines are stored in a raster format, i.e. a pixel indexes a line if there is one at that location.

The similarity score for a pair of line segments is computed as the average of the individual edgel correlation values. However, to be robust to occlusion, an individual correlation value is only included if above a threshold. Here a correlation window of ¥ ¦ ¥ pixels is used and the thresh- old value is 0.6. If there are fewer than a minimum number of matched edgels for a putative segment match, then that match is eliminated. Here the minimum is 15 edgels.

If there are ¤ lines in each image then the computational complexity of the 3-view matching algorithm would be ¥ B ¦¤ ¨ § D if all lines are considered in each view. However, since triple hypotheses are formed from pairwise matches (and only verified in the third view) the complexity is ¥ B ¦¤ D .

The lines are reconstructed in 3D by minimizing reprojection error over the 3 views using the Levenberg-Marquardt algorithm (see figure 4).

Results for 3-view line matching. For clarity the matching algorithm is illustrated on the © ¤£ ¦£ ¦ © ¦£ ¤£ pixel image set of figure 5. Figure 5b shows the detected 2D lines and figure 5c shows the 2D lines which have been matched. Figure 6a shows the corresponding 3D lines. About 40% of the detected lines are matched, and of these matches over 98% are correct. This is a very good performance: about 35% of the lines detected in one image are not detected in the other image, so although only 40% of the detected lines are matched, 62% of the lines which could be matched are indeed matched by the algorithm.

The matching results over 3 views for the data set of figure 1 are shown in figures 7a and 8a. About 20% of the detected lines have been matched.

Improving the quality of the matched lines

The line matches are refined in two ways. The first one -merging -overcomes a limitation of the winner takes all strategy. The second one -growing -overcomes the deficiency in line segmentation. Merging. During the line extraction, lines are often erroneously broken into several segments. Under "winner takes all" only one of these segments may be matched over three views. Suppose, for example, that in view one both lines ¢¡ and ¢£ match line ¡ in view two and line 6 in view 3. Even if lines ¤¡ and ¢£ are collinear, only one of the two triplets B ¤¡ ¦¥ ¡ §¥ 6 D and B ¤£ ¨¥ ¡ §¥ 6 D will be selected. If no further action is taken the effect of line fragmentation in detection is that line ¤£ will be unmatched.

If

¤¡

and

¢£ are collinear and the two triplets B ¢¡ ©¥ ¡ ¥ 6 D and B ¤£ ¨¥ ¡ ¥ 6 D are among the triplets before applying the winner takes all strategy, then it is likely that ¤¡ and ¤£ arose from a single (but fragmented) line. The lines are merged if it is possible to fill in the gap between ¤¡ and ¤£ , that is if there is correlation support for the gap over 3 views. In this manner a line match is generated which is the union of the lines detected in each of the views. Furthermore 3D lines estimated from this correspondence are improved because longer line segments are available in each view.

Growing. Another deficiency of line detection, other than fragmentation, is that a fitted line may be shorter than the true line. However, the missing edgels are in general not the same in the different images. Thus if a short line is matched to a longer line (determined by epipolar lines), the end points may be extended provided the "grown" edgels satisfy the photometric correlation tests over the three views. This another significant benefit of using multiple views.

The significant benefits of this improvement are demonstrated when comparing figures 6a and 6b, which show the 3D lines computed before and after the line clean-up. About 15% additional line matches are generated by merging, and more than 70% of all matched lines are grown.

Extension to N-view matching

Using more views reduces matching errors, and increases the accuracy of the estimated 3D line. A natural method to extend the matching from 3 to views would be to project the 3-view estimated line into subsequent images and verify its correspondence with a detected line in the new view using a combination of the geometric and photometric constraints described in section 3.2. Here a different method of extension is implemented which is better tuned to the acquisition circumstances of the image set.

As described in the caption of figure 1, the images were acquired in two sets. There are smaller photometric differences between images of the triple 1-3, and between images of the triple 4-6 than there are between any individual images. For this reason, lines are first matched within the triples, and then the triples are merged together.

In the case of 6 input images defining 2 triples, the matching is first performed independently for each. The correspondence between the triples is then established by reprojection in the images: Suppose B 0 $ ¥ ¥ § D is a line triple defined over views 1-3 and . If a line triple has not matched any other triple then matches are sought from the set of unmatched lines in the images of the other triple. Whenever such a line is found, it is added to the matching set. A match has to be supported by a minimal number of views (here 4) to be valid. The method can easily be extended to "! © views by dividing the image set into triples. The triples may or may not overlap depending on the acquisition characteristics.

Results for N-view matching. Figures 6c, 7b and 8b

show the matching results over 6 views for both example scenes, where a match has been accepted if verified over 4 views at least. The reconstructed 3D lines are of higher quality than those computed with only 3 views, and there are no mismatches at all. The total length of the reconstructed lines is about 15% higher than with 3 views. The accuracy of the reconstruction increases with the number of views, as shown in figure 9.

PRODUCING PIECEWISE PLANAR MODELS

This section describes the method for generating a piecewise planar model. The method proceeds from the computed 3D lines and consequently must cope with the shortcomings of that process and the earlier line detection: missing lines, fragmented lines, and the occasional mis-match.

The problems caused by missing features in piecewise planar reconstruction are illustrated by the detail in figure 13a, taken from the data set of figure 5. The correct roof model in this case is a four plane "hip" roof [START_REF] Weidner | Towards automatic building extraction from high-resolution digital elevation models[END_REF]. However, the oblique roof ridges are almost invisible in any view, and certainly are not reliably detected by an edge or bar detector with only local neighbourhood support. Consequently, 'classical' plane reconstruction algorithms which proceed from a grouping of two or more coplanar 3D lines [START_REF] Bignone | Automatic extraction of generic house roofs from high resolution aerial imagery[END_REF][START_REF] Moons | Automatic modelling and 3d reconstruction of urban house roofs from high resolution aerial imagery[END_REF], will produce a flat roof, or at best a two plane "gable" roof if the central horizontal ridge edge is detected -however the two smaller faces will be missed. The method described here requires only a single 3D line in order to generate a plane hypothesis. As will be seen it does not have the above failings of the two line methods.

The method consists of three main stages, which will be illustrated on the building shown in figure 13a: 1. Computing reliable half-planes defined by one 3D line and similarity scores computed over all the views (sec-

L θ π (θ)
Figure 10: The one-parameter family of half-planes containing the 3D line . The family induces a one-parameter family of homographies between any pair of images. tion 4.1). This is the most important and novel stage of the algorithm.

2. Line grouping and completion based on the computed half-planes (section 4.2). This involves grouping neighbouring 3D lines belonging to the same half-plane, and also creating new lines by plane intersection.

Plane delineation and verification

where the lines of the previous stage are used to delineate the plane boundaries (section 4.3).

Computing half-planes

Principles and objectives. Given a 3D line, there is a oneparameter family of planes § B ¥¡ D containing the line (see fig- ure 10). As each plane defines a (planar) homography between two images, the family also defines a one-parameter family of homographies ¢ B ¥¡ D between any pair of images.

Each side of the line can be associated with a different halfplane. Our objective is therefore to determine for each line side whether there is an attached half-plane or not, and if there is we want to compute a best estimate of ¡ . We wish to employ only the minimal information of a single 3D line and its image neighbourhood. Essentially we are hypothesizing a planar facet attached to the line, and verifying or refuting this model hypothesis using image support over multiple views.

Method. The existence of an attached half-plane and a best estimate of its angle is determined by measuring image similarity over multiple views. The geometry is illustrated in figure 11. Given ¡ , the plane § B ¥¡ D defines a point to point map between the images. If the plane is correct then the intensities at corresponding pixels will be highly correlated. The homography matrix is obtained from the 6 ¦ % camera projection matrices for each view. For example, if the projection matrices for the first and ¦ th views are & 4 (' ) ©0 21 and & £ 4 3' 4 £ 65 £ 1 respectively, and 3D points 7 on the plane satisfy § ) 7 4 £ , where the plane is represented as a homogeneous 4-vector § in the world frame, then [START_REF] Luong | Canonical representations for the geometries of multiple projective views[END_REF] ¢ £ 4 84 £ @9 5 £ ¥A ) CB ED @F HG IF A

4 P Q B Q $ ¥ Q ¥ Q § D ) provided Q SR 4 £ . Note, A is independent of the view ¦ .
The similarity score function has been designed to be selective, and also robust to occluded portions and irrelevant points. It is defined as:

!¦ CB ¥¡ D 4 T view ¦ valid U WV YX acb B & D Cor B & ¥ d¢ £ B ¥¡ D & (D
and ranges between B 0£ ¥ ¢ D . Figure 12 shows two typical examples of score functions. In the following, the various terms and parameters are described and motivated.

First, it is necessary to determine a texture point set in order to produce a selective and discriminating similarity function The black curve corresponds to a short baseline between views (e.g. views 1 & 2), the grey curve to a wide one (e.g. 1 & 4). The curves apply to the same half-plane.

A short baseline leads to high maxima (low distorsion between the images), but often located with a poor accuracy (wide peak); in contrast, a wide baseline is more likely to produce accurate maxima, but with a lower score. However, the maxima generally differ by less than ¥ ¡ .

of ¡ . Consider the case that the intensity of the image is locally homogeneous, then correlation between images is similar for any ¡ and provides no discrimination. However, at locally textured regions this problem will not arise. Correlation is thus computed only in the neighbourhood of textured Points Of Interest (POI). These points are computed by applying an edge detector to the first image, with a very low threshold on gradient (an example is given in figure 13).

The edges are then linked and regularly sampled to determine the POI. The choice of the first view is arbitrary and can be automated by selecting the most textured image.

The correlation term ¢ ¤£ ¦¥

B & ¥ & £ D is the centred normalized cross-correlation between & in the first view and & £ in the ¦ th view, evaluated over the points of interest. Cross- correlation is used because empirically it is highly selective on ¡ over textured intensity regions. The correlation is squared in order to give more weight to high scores, and therefore to be even more selective.

The weighting factor b B & (D is inversely proportional to the distance of the point & from the line projected onto the first view. This weighting provides some robustness, since it gives more weight to points which are closer to the line, and consequently are less likely to belong to other planes. Finally, additional robustness is provided by only including valid views in the summation. Valid views are those which have at least a threshold number of high correlation scores at points of interest, thereby rejecting views where the plane might be occluded. Averaging the scores over views exploits the complementarity of the short and wide baseline separations (see figure 14) in the data set.

The optimal angle ¡ is computed by searching for the max- imum of the function ©¦ CB ¥¡ D over a range ¨ § © ¡ © § . The algorithm used is recursive sub-division with a termination criterion of ¡ © . The half-plane hypothesis is accepted or rejected as valid according to the characteristics of !¦ CB ¥¡ D as shown in figure 12. The line side is then classified as supporting or not supporting a half-plane. For example, an occluding edge would not have a half-plane attached on the occluded side.

Results of half-plane detection.

In the following the parameter values for line matching have been relaxed: a minimal number of only 10 matched edgels (rather than 15) is scribed in section 2. This is more accurate than, for instance, averaging angles.

required to verify a line match, in order to produce more half-plane hypotheses. This is possible because erroneous hypotheses can be culled all along the process.

Figure 15 shows all the half-planes which are hypothesised on the example building. All parts of the roof of the main building are detected, whereas no valid planes are detected for the walls within the considered angle interval (we are not aiming to reconstruct vertical walls). Occasionally erroneous half-planes arise at shadows, but these are removed in the subsequent stages.

Grouping and completion of 3D lines based on half-planes

The computed half-planes are now used to support line grouping and the creation of new lines.

Collinear grouping (figure 16). Two collinear lines which have attached coplanar half-planes are merged together. The result of the collinear grouping of half-planes of figure 15 is shown in figure 18a.

Coplanar line and half-plane grouping (figure 17). Any line which is neighbouring and coplanar with the current plane is associated with it (see the example of figure 18b).

Creating new lines by plane intersections (figure 19). New lines are created when two neighbouring planes intersect in a consistent way. This is very important as it provides a mechanism for generating additional lines which may have been missed during image feature detection (see the example of figure 20).

Plane delineation and verification

In order to produce a piecewise planar model of the scene a closed delineation is required for each plane. For this purpose, it is necessary to determine its border lines (boundaries). The initial support line of a plane is a natural border line. Additional border lines are created as shown in figure 21. A closed delineation can then be computed by using heuristic grouping rules [START_REF] Weidner | Towards automatic building extraction from high-resolution digital elevation models[END_REF][START_REF] Noronha | Detection and description of buildings from multiple images[END_REF][START_REF] Moons | Automatic modelling and 3d reconstruction of urban house roofs from high resolution aerial imagery[END_REF] to associate border lines. For instance the end points of the border lines are updated when lines intersect or have close end points (see figure 22). Then the convex hull of the border line end points is computed. If only one border line has been detected, then the plane is rejected, and this provides a very efficient culling mechanism for removing erroneous half-planes.

Each delineated 3D face so produced is then verified by assessing intensity similarity over the complete image set, at corresponding points within the projected delineation. This verification step removes fallacious planes, for example those which erroneously bridge two buildings. Figure 23 shows both the 2D delineation and a 3D view of the roof produced for the building of figure 13a.

Finally, occlusion prediction is used to signal and resolve conflicts between inconsistent plane hypotheses. A conflict occurs between two facet hypotheses when their projections onto an image substantially overlap, i.e. when one of them is occluded by the other. Where conflicts between plane hypotheses arise, there are two possibilities, depending on the coplanarity of the conflicting planes.

If the the conflicting planes are coplanar, then the planes are merged together. The position of the new single plane is computed using lines belonging to both merged planes, and its delineation is obtained by merging the previous delineations together.

On the contrary, if the the conflicting planes are not coplanar, then the conflict is resolved using a confidence score B ¢ D , which denotes the quality of the face ¢ : Whenever a plane is merged or removed, the neighbouring planes are updated. In grouping operations, thresholds on distances are avoided by using a topological neighbourhood between projected lines, defined by a Delaunay triangulation constrained to fit the line segments. This also enables quick access to neighbours.

¨B ¢ D 4 ¤£ B ¢ D ¦ ¦¥ ¨ § # © B ¢ D ¥

Results of model building

Figure 24 shows the 3D reconstruction of the full scene of figure 5a. Figure 25 shows the result on the much larger and more complicated images of figure 1. Note that intricate and unusual roofs (for example the factory in the upper part of the image) have been completely recovered. This also demonstrates how little photometric texture is required by the method, since roofs with virtually homogeneous intensity are retrieved. Only two roofs are missed in the entire scene.

Performance. The quality of the reconstruction is governed by the completeness and correctness of the input line set. The method is robust to a proportion of missing and erroneous lines because mechanisms are included to generate new lines, by plane intersection, and to cull erroneous lines with their associated half-planes, in the final verification stages. However, the performance is improved if too many, rather than too few, lines are supplied. This is because a line is the only mechanism for instantiating a plane hypothesis, and if lines are missing then entire planes may be missed.

Of the three stages of the method, the half-plane detection stage is the most robust and is also the most expensive. This stage requires very few parameters to be specified. When a face is well textured (as in the case of the example building roof of figure 13), the angle of the initial half-plane is estimated to an accuracy of better than ¡ . When there is little texture, the accuracy can decrease to ¥ , but a higher accuracy is determined during the coplanar grouping stage.

FUTURE WORK AND EXTENSIONS

The results demonstrate that it is possible to automatically construct models of urban scenes from multiple images using quite minimal information. The models are of very reasonable quality.

How might the quality be improved further? The most significant improvement would be to provide additional features for matching. For example, a bar detector would gain extra lines in the example building of figure 13. A second improvement would be the incorporation of other, albeit more restrictive, 3D grouping mechanisms. The approach of this paper is not an alternative to roof generation systems based on the grouping of at least two neighbouring coplanar lines [START_REF] Bignone | Automatic extraction of generic house roofs from high resolution aerial imagery[END_REF][START_REF] Moons | Automatic modelling and 3d reconstruction of urban house roofs from high resolution aerial imagery[END_REF], but is complementary to such systems. An efficient and robust approach would use both, grouping and removing from consideration coplanar lines and using the described single 3D line method for the remainder. This requires an architecture for a cooperating strategy to be developed.

It would also be preferable if the similarity score function had a firmer statistical foundation. Measurements on the function correctly facilitate plane rejection and angle computation, but the measures are empirically based. An alternative approach would be to develop a probabilistic framework and compute a posterior estimate for the plane angle and the likelihood that a plane is there.

Figure 1 :Figure 2 :

 12 Figure 1: Six overlapping aerial views. The images are about ¢¡ ¤£ ¤£ ¦ ¥ ¢¡ ¤£ ¦£ pixels, one pixel corresponding to a ground length of 8.5cm. The images are acquired at a height of 1300m in two triplets: the camera approximately translated by about 300m between successive views in images 1-3, and between images 4-6. The first set acquired on the outward flight, and the second set on the approximately parallel return flight.

Figure 3 :

 3 Figure 3: The point-wise correspondence between the lines and ' is determined using epipolar geometry : & ! 4 ' ¦ ' # where ' # is the epipolar line of & .

  Figure 4: A line ¡ is reconstructed in 3D by minimizing reprojection error over 3 views. In this case the error used is the distance between the end points of the measured lines, ¢ £ , and the image, ¢ , of the line ¡ in each view.

Figure 5 :

 5 Figure 5: Three view line matching. The input images are © ¤£ ¦£ ¦ © ¤£ ¦£ pixels. There are 248/236/212 detected line segments and 88 lines are matched, with only one erroneous match.

  Figure 7: (a) Three view line matching for the first three images of figure 1. There are 1344/1307/1245 detected line segments and 229 matched lines (shown here). (b) Six view line matching for the images of figure 1. There are 332 matched lines over 6 views, produced by merging together 229 and 353 triplets. The figure shows the matched lines reprojected onto the 3 first images. Note, line segments missed in the triplet matches of figure (a) are recovered by matches in the second triplet.

¡

  $ § the corresponding estimated 3D line segment. Similarly suppose B 0 ¨¥ ¥ D is a line triple defined over views 4-6 and ¡ the corresponding 3D line segment. A correspondence is established between the two triples if the projection of ¡ $ § onto the images 4-6 matches at least two of the lines ¥ , , and reciprocally if the projection of ¡ onto the triple 1-3 matches at least

Figure 9 :

 9 Figure 9: Mean height difference between endpoints of horizontal lines (from the images of figure 1) versus the number of views: the accuracy of the reconstruction increases with the number of views. two of the lines $ ¥ ¥ §

Figure 11 :

 11 Figure 11: Geometric correspondence between views. ¡ , the homography ¢ ¤£ B ¥¡ D determines the geometric map be- tween a point in the first image and its corresponding point in image ¦ .

Figure 12 :

 12 Figure 12: Example of similarity score functions ©¦ B ¥¡ D . The black curve corresponds to a valid plane, whereas the grey one is rejected. The following validity criteria are used: maximum value of the function ©¦ CB ¥¡ £ D £ £ , absolute value of the estimated second derivative around the maximum ©¦ 7! ! B ¥¡ £ D £ £ , and global amplitude ©¦ CB ¥¡ £ D ! ©¦ B ¥¡ £

Figure 14 :

 14 Figure 14: Effect of the baseline on 2-view similarity scores.The black curve corresponds to a short baseline between views (e.g. views 1 & 2), the grey curve to a wide one (e.g. 1 & 4). The curves apply to the same half-plane. A short baseline leads to high maxima (low distorsion between the images), but often located with a poor accuracy (wide peak); in contrast, a wide baseline is more likely to produce accurate maxima, but with a lower score. How-

Figure 16 :

 16 Figure 15: Detected half-planes over the interval ' ¥ 9 ¥ 1 .

Figure 17 :

 17 Figure 17: Coplanar line and half-plane grouping. In the top case, belongs to the half-plane § B ¥ ¡ D , and a new plane is computed by orthogonal regression to a regular point sampling of and . In the bottom case, has an attached but consistent half-plane, therefore the two plane hypotheses are merged into a new unique plane, also computed by orthogonal regression.

Figure 19 :

 19 Figure 19: Creation of new lines when two planes intersect.

Figure 20 :

 20 Figure 20: New lines (black) created by plane intersection. where £ B ¢ D is the area of the face, and ¥ § # © B ¢ D the ratio of the length of input 3D lines to hypothesised lines in the delineation. The plane hypothesis with the lowest confidence score is suppressed.

Figure 21 :

 21 Figure 21: Border line computation for plane delineation:(a) The line lies in the plane § B ¥ D but has an attached plane which is not consistent with it, therefore it is stored as a border line; (b) The line does not belongs to the plane § B ¥ D but it is stored as a border line.

Figure 22 :Figure 23 :

 2223 Figure 22: Updating end points of the border lines: any end point outside the region of interest is moved into it; two close endpoints are replaced by the intersection of the two lines

Acknowledgements. Financial support for this work was provided by the EC Esprit Project IMPACT and the UK EP-SRC IUE Implementation Project GR/L05969.


Roberto Cipolla

Duncan Robertson

Edmond Boyer

PhotoBuilder { 3D Models of Architectural Scenes from Uncalibrated Images

We address the problem of recovering 3D models from uncalibrated images of architectural scenes. We propose a simple, geometrically intuitive method which exploits the strong rigidity constraints of parallelism and orthogonality present in indoor and outdoor architectural scenes. We show how these simple constraints can be used to calibrate the cameras and to recover the projection matrices for each viewpoint.

The projection matrices are used to recover partial 3D models of the scene and these can be used to visualise new viewpoints. Our approach does not need any a priori information about the cameras being used.

A working system called PhotoBuilder had been designed and implemented to allow a user to interactively build a VRML model of a building from uncalibrated images from arbitrary viewpoints.

Introduction

Considerable e orts have been made to recover photorealistic models of the real world. The most common geometric approach is to attempt to recover 3D models from calibrated stereo images 15] or uncalibrated extended image sequences 21, 1, 16] by triangulation and exploiting epipolar 13] and trilinear constraints [START_REF] Gortler | The Lumigraph[END_REF][START_REF] Shum | Interactive construction of 3D models from Panoramic Mosaics[END_REF]. An alternative approach consists of visualisation from image-based representations of a 3D scene. This has been successfully used to to generate an intermediate viewpoint image given two nearby viewpoints and has the advantage that it does not need to make explicit a 3D model of the scene [START_REF] Tomasi | Shape and motion from image streams under orthography: a factorization method[END_REF][START_REF] Press | Numerical Recipes in C, The Art of Scienti c Computing[END_REF][START_REF] Faugeras | 3D reconstruction of urban scenes from sequences of images[END_REF][START_REF] Kanatani | Statistical Optimization for Geometric Computation: Theory and Practice[END_REF][START_REF] Debevec | Modeling and Rendering Architecture from Photographs: A Hybrid Geometry-and Image-Based Approach[END_REF].

Facade 5] { one of the most successful systems for modelling and rendering architectural buildings from photographs { consists of a hybrid geometric and image-based approach. Unfortunately it involves considerable time and e ort from the user in decomposing the scene into prismatic blocks, followed by the estimation of the pose of these primitives. However the high quality of the results obtained with the Facade system has encouraged others to design interactive systems.

In this paper we propose a much simpler approach to construct a 3D model and generate new viewpoint images by exploiting strong constraints present in the scenes to be modelled. In the context of architectural environments, the constraints which can be used are parallelism and orthogonality. These constraints lead to very simple and geometrically intuitive methods to calibrate the intrinsic and extrinsic parameters of the cameras and to recover Euclidean models of the scene from only two images from arbitrary positions. Our approach is similar to another interactive system 19] but exploits vanishing points 2] directly to recover the projection matrices.

Outline of the algorithm

A 3D model can be recovered from two or more uncalibrated images in the following four stages (see gure 1).

1. The user selects a set of image edges which are either parallel or perpendicular in the world. These primitives are precisely localised in the image using the image gradient information. 2. The next step concerns the camera calibration: the intrinsic parameters of the camera are determined for each image. This is done by determining the vanishing points associated with parallel lines in the world. Three mutually orthogonal directions are exploited to give three intrinsic parameters and the orientation of each viewpoint. 3. A projection matrix for each viewpoint is computed from the image edges and vanishing points. These matrices are further re ned by exploiting epipolar constraints and additional matches to give the motion (a rotation and a translation) between the viewpoints. 4. The last step consists in using these projection matrices to nd more correspondences between the images and then to compute 3D textured triangles that represent a model of the scene.

A working application called PhotoBuilder has been designed and implemented to allow the user to interactively build a 3D VRML model from a pair of uncalibrated images from arbitrary viewpoints in less than 15 minutes.

X i Y i Z i 1 3 7 7 5 (1)
The projection matrix has 11 degrees of freedom and can be decomposed into the orientation and position of the camera relative to a the world co-ordinate system (a 3 3 rotation matrix R and a 3 1 translation vector T):

P = K R T (2)
and a 3 3 camera calibration matrix, K, corresponding to the following image plane transformation:

K = 2 4 u s u 0 0 v v 0 0 0 1 3 5 ;
(

where u , v are scale factors; s is a skew parameter; and u 0 , v 0 are the pixel coordinates of the principal point (the intersection of the optical axis with the image plane).

Approach

In our approach the vanishing points corresponding to three mutually orthogonal directions can be used to determine for each viewpoint:

1. the camera calibration matrix, K under the assumption of zero skew and known aspect ratio.

2. the rotation matrix R. 3. the direction of translation, T.

We show that the 8 degrees of freedom of the projection matrix for this special case can be determined from three vanishing points corresponding to the projections of 3 points at in nity and a reference point. The projection matrix can thus be recovered from the projection of at least one arbitrary cuboid. Applying the algorithm to two views allows the Euclidean reconstruction of all visible points up to an arbitrary scale.

Using vanishing points

From (1) and considering the points at in nity corresponding to the three orthogonal directions we can derive simple constraints on the elements of the projection matrix:

2 4 1 u 1 2 u 2 3 u 3 1 v 1 2 v 2 3 v 3 1 2 3 3 5 = P 2 6 6 4 1 0 0 0 1 0 0 0 1 0 0 0 3 7 7 5 (4)
where i are initially unknown scaling factors. This equation can be rearranged and expressed in terms of the camera calibration matrix K and camera orientation (rotation matrix), R:

2 4 u 1 u 2 u 3 v 1 v 2 v 3 1 1 1 3 5 2 4 1 0 0 0 2 0 0 0 3 3 5 = KR (5)

Camera calibration and recovery of orientation

By exploiting the properties of the rotation matrix, R, we can rerrange [START_REF] Collins | Vanishing point calculation as a statistical inference on the unit sphere[END_REF] to recover constraints on the intrinsic parameters of the camera and the unknown scaling parameters, i . In particular:

2 4 u 1 u 2 u 3 v 1 v 2 v 3 1 1 1 3 5 2 4 2 1 0 0 0 2 2 0 0 0 2 3 3 5 2 4 u 1 u 2 u 3 v 1 v 2 v 3 1 1 1 3 5 T = KK T (6)
Under the assumption of known aspect ratio and zero skew, (6) can be rewritten as 6 linear equations (from six elements of the symmetric matrix) and can be solved to recover 3 intrinsic parameters and the unknown scale factors, 2 i .

Geometric interpretation

Note that these equations can also be rearranged to derive the curious geometric interpretation (see gure 2) that the orthocentre of the image triangle formed by the three vanishing points is the principal point. This was rst shown by Caprile and Torre 2]. In addition to this property, we can show that the scale factors i have the geometric interpretation shown in gure 2.

Recovery of projection matrix

The solution of ( 6) and substitution into (5) leads to the recovery of the 3 3 sub-matrix of the projection matrix, KR, which can then be easily decomposed into the rotation matrix R.

The fourth column of the projection matrix depends on the position of the world co-ordinate system relative to the camera co-ordinate system. An arbitrary reference point can be chosen as the origin. Its image co-ordinates x the translation, T, up to an arbitrary scale factor, 4 : = KT [START_REF] Faugeras | Representing Three-Dimensional Data as a Collection of Images and Fundamental Matrices for Image Synthesis[END_REF] In a single viewpoint and with no metric information this scale is indeterminate and can be arbitrarily set, e.g. 4 = 1. For additional views the image correspondences of a fth point is required to x this scale factor in the additional views. This is equivalent to xing the epipoles from the translational component of image motion under known rotation { two point correspondences are required to recover the direction of translation.

Finding Vanishing Points

The key step in the algorithm to recover the projection matrices requires nding the vanishing points of parallel lines with known orientations. Image segments can be interactively de ned by a user and care must be taken to nd the corresponding vanishing points.

A vanishing point corresponds to the projection of the intersection of parallel lines at in nity. A number of approaches have been proposed to localise precisely this intersection, from the simple calculation of a weighted mean of pairwise intersections 2] to more elaborate approaches involving noise assumption and non-linear criteria 4, 10]. However, all these approaches are based on criteria which take into account image distances. Though trying to minimise the distance from the vanishing point to the image lines is geometrically correct, it appears to be numerically unstable in the presence of noise. In contrast, our approach is based on a linear criterion which optimises a three dimensional direction, the dual of a vanishing point in 3D space. Let l 1 ; ::; l n be a set of image lines corresponding to parallel space lines and let be the vanishing point de ned by these lines. Then if we suppose that l i and are expressed in homogeneous form in the image coordinate system (u; v; w), we have the following relation: l 1 ; ::; l n ] T = 0: [START_REF] Faugeras | 3D reconstruction of urban scenes from sequences of images[END_REF] and the null vector of the 3 n matrix l 1 ; ::; l n ] gives a solution ^ for the vanishing point position. However, the minimised criterion does not necessarily have a physical meaning. By choosing an appropriate normalisation for (l 1 ; ::; l n ), the solution ^ can minimise the sum of the Euclidean distances from ^ to l 1 ; ::; l n ]. As said before, this solution will not be completely satisfactory in the presence of noise due to poor conditioning of the matrix l 1 ; ::; l n ]. Now suppose that the intrinsic parameters of the camera are known. Then image lines and points can be expressed using normalised image coordinates, that is to say in the coordinate system (x; y) associated with the camera retinal plane (see gure 3). Let . This direction should belong to all the planes P i .

l l i j O L i V u v ν j V V P i P j L x y z
(L 1 ; ::; L n ) and V be the homogeneous representations of (l 1 ; ::; l n ), in the retinal plane. Since V belongs to all the image lines, we still have the relation: L 1 ; ::; L n ] T V = 0: (9) However, this relation has also an interpretation in the three dimensional coordinate system (x; y; z) associated with the camera (see gure 3). Indeed, L i is a vector orthogonal to the plane P i spanned by the camera projection centre O and the image line l i , and V is a three dimensional vector. This gives a physical meaning to the null vector V of L 1 ; ::; L n ] T which is the space direction closest to all planes (P 1 ; ::; P n ).

Finally, we compute the space direction V as the null vector of the matrix L 1 ; ::; L n ] T , where jL i j = 1. This is done using a singular value decomposition of L 1 ; ::; L n ] T 17]. Experiments show that estimating a space direction is more robust to noise perturbations than estimating an image point. We use this method in the calibration routine described in the next section.

In the case where the camera's intrinsic parameters are not known, an intermediate solution consists of using [START_REF] Faugeras | 3D reconstruction of urban scenes from sequences of images[END_REF] with prenormalized image point coordinates 9] in order to improve the condition number of the matrix l 1 ; ::; l n ].

Projection Matrices

Having found the vanishing points we can now recover the intrinsic parameters (and i scale factors) by solving equation ( 6) using singular value decomposition. In practice the principal point is very sensitive to error and is assumed known (i.e. at the centre of the image). The other parameters are extremely reliable and the vanishing points and directions are then used to obtain the orientation and position of the cameras. Note that the vanishing points are used directly to estimate the rotation (since these are independent of camera translation). The translation is then computed from pairs of corresponding points using the epipolar constraint.

These motions combined with the intrinsic parameters allow us to compute projection matrices for the di erent views involved. From these projection matrices, we can determine the epipolar geometry to help nd more point correspondences and then the 3D point positions. These points are then used in association with an image point triangulation to obtain 3D structure. This structure is rendered afterwards using a standard texture mapping procedure and the nal model is stored in standard VRML format.

Experiments on synthetic and real data have been conducted. Figure 4{6 show some preliminary results for real images of the Downing College library in the University of Cambridge. These images were obtained by an Olympus digital camera. The calibration for these images was performed using 3 pairs of parallel edges shown in Figure 4 to determine the vanishing points and hence calibrate the two cameras. The geometry was then computed using the vanishing points the 3D co-ordinates were then recovered. Figure 5 shows an example of the VRML mdoel with texture. This model consists of of forty textured triangles and was produced in less than 15 minutes.

Conclusions

The techniques presented have been successfully used to interactively build models of architectural scenes from pairs of uncalibrated photographs. The simple but powerful constraints of parallelism and orthogonality in architectural scenes can be used to recover very precise projection matrices with only a few point and line correspondences.

We plan to use these initial estimates of the projection matrices (and hence the epipolar geometry) to automatically match additional features and then to optimise the parameters of the camera motion and 3D structure by standard ray-bundle adjustment. The PhotoBuilder system has been use to build 3D models of numerous buildings and is presently being used to buid a VRML model of the University of Cambridge. Preliminary results are extremely impressive.

  1

3 .

 3 Finding vanishing points and camera calibration 1. Original uncalibrated photographs 4. Computation of projection matrices and camera motion 2. Primitive definition and localisation R + T 5. Triangulation, 3D reconstruction and texture mapping

Figure 1 :

 1 Figure 1: Outline of the algorithm. The user interactively labels a few parallel and perpendicular edges in the images. These are then localised precisely and used to compute the projection matrices for the viewpoints. Triangulation and texture mapping is used to produce a 3D VRML model.

Figure 2 :

 2 Figure 2: Geometric interpretation. The orthocentre, D, of the triangle formed by the three vanishing points (A, B and C) can be shown 2] to be the principal point, (u 0 ; v 0 ). The scale-factor, 2 1 , associated with the vanishing point A = (u 1 ; v 1 ), can similarly be shown to be the area of the triangle BCD normalised by the total area of the triangle ABC. A similar result applies to the other two factors and vanishing points, B and C. The scale factor u can also be inferred from the triangle.

Figure 3 :

 3 Figure 3: Vanishing point determination. The idea is to nd the viewing direction V of the vanishing point

Figure 4 :

 4 Figure 4: Original pair of photographs taken with di erent camera zoom setting. Six edges in each image are used to obtain the camera intrinsic parameters and the orientation and position of the viewpoints.

Figure 5 :

 5 Figure 5: 3D wireframe model with texture from original images. Correspondences are given manually and processed to re ne the motion between the viewpoints. Triangles that are visible in both views can be renconstructed.

Figure 6 :

 6 Figure 6: The 3D model can be output in VRML format and viewed from new viewpoints.