Affine Structure from Line Correspondences With Uncalibrated Affine Cameras.
AbstractThis paper presents a linear algorithm for recovering 3D affine shape and motion from line correspondences with uncalibrated affine cameras. The algorithm requires a minimum of seven line correspondences over three views. The key idea is the introduction of a one-dimensional projective camera. This converts 3D affine reconstruction of "line directions" into 2D projective reconstruction of "points." In addition, a line-based factorization method is also proposed to handle redundant views. Experimental results both on simulated and real image sequences validate the robustness and the accuracy of the algorithm.
Introduction
Using line segments instead of points as features has attracted
the attention of many researchers [1], [2], [3], [4],
[5], [6], [7], [8], [9] for various tasks such as pose estima-
tion, stereo and structure from motion. In this paper, we
are interested in structure from motion using line correspondences
across mutiple images. Line-based algorithms
are generally more difficult than point-based ones for the
following two reasons. The parameter space of lines is non
linear, though lines themselves are linear subspaces, and a
line-to-line correspondence contains less information than
a point-to-point one as it provides only one component of
the image plane displacement instead of two for a point
correspondence. A minimum of three views is essential for
line correspondences, whereas two views suffice for point
ones. In the case of calibrated perspective cameras, the
main results on structure from line correspondences were
established in [4], [10], [5]: With at least six line correspondences
over three views, nonlinear algorithms are possible.
With at least thirteen lines over three views, a linear algorithm
is possible. The basic idea of the thirteen-line linear
algorithm is similar to the "eight-point" one [11] in that
it is based on the introduction of a redundant set of intermediate
parameters. This significant over-parametrization
of the problem leads to the instability of the algorithm reported
in [4]. The thirteen-line algorithm was extended to
uncalibrated camera case in [12], [9]. The situation here
might be expected to be better, as more free parameters
are introduced. However, the 27 tensor components that
are introduced as intermediate parameters are still subject
to 8 complicated algebraic constraints. The algorithm
Long QUAN is with CNRS-GRAVIR-INRIA, ZIRST 655, avenue de
l'Europe, 38330 Montbonnot, France. E-mail: Long.Quan@imag.fr
Takeo KANADE is with The Robotics Institute, Carnegie Mellon
University, Pittsburgh, PA 15213, U.S.A. E-mail: tk@cs.cmu.edu
can hardly be stable. A subsequent nonlinear optimization
step is almost unavoidable to refine the solution [5], [4],
In parallel, there has been a lot of work [13], [14], [15], [16],
[17], [18], [19], [20], [21], [22], [14], [16], [23], [17], [24], [25]
on structure from motion with simplified camera models
varing from orthographic projections via weak and paraperspective
to affine cameras, almost exclusively for point
features. These simplified camera models provide a good
approximation to perpsective projection when the width
and depth of the object are small compared to the viewing
distance. More importantly, they expose the ambiguities
that arise when perspective effects diminish. In such cases,
it is not only easier to use these simplified models but also
advisable to do so, as by explicitly eliminating the ambiguities
from the algorithm, one avoids computing parameters
that are inherently ill-conditioned. Another important advantage
of working with uncalibrated affine cameras is that
the reconstruction is affine, rather than projective as with
uncalibrated projective cameras.
Motivated on the one hand by the lack of satisfactory line-based
algorithms for projective cameras and on the other
by the fact that the affine camera is a good model for many
practical cases, we investigate the properties of projection
of lines by affine cameras and propose a linear algorithm for
affine structure from line correspondences. The key idea is
the introduction of a one-dimensional projective camera.
This converts the 3D affine reconstruction of "line direc-
tions" into 2D projective reconstruction of "points". The
linear algorithm requires a minimum of seven lines over
three images. We also prove that seven lines over three images
is the strict minimum data needed for affine structure
from uncalibrated affine cameras and that there are always
two possible solutions. This result extends the previous results
of Koenderink and Van Doorn [14] for affine structure
with a minimum of two views and five points. To deal with
redundant views, we also present a line-based factorisation
algorithm which extends the previous point-based factorisation
methods [18], [21], [22]. A preliminary version of
this work was presented in [26].
The paper is organized as follows. In Section II, the affine
camera model is briefly reviewed. Then, we investigate
the properties of projection of lines with the affine camera
and introduce the one-dimensional projective camera
in Section III. Section IV is focused on the study of the un-calibrated
one-dimensional camera, and in this section we
present also a linear algorithm for 2D projective reconstruction
which is equivalent to the 3D affine reconstruction of
IEEE-PAMI, VOL. *, NO. *, 199*
line directions. Later, the linear estimation of the translational
component of the uncalibrated affine camera is given
in Section V and the affine shape recovery is described in
Section VI. To handle redundant views, a line-based factorisation
method is proposed in Section IX. The passage
to metric structure from the affine structure using known
camera parameters will be described in Section XI. Finally
in Section XIII, discussions and some concluding remarks
are given.
Throughout the paper, tensors and matrices are denoted
in upper case boldface, vectors in lower case boldface and
scalars in either plain letters or lower case Greek.
II. Review of the affine camera model
For a projective (pin-hole) camera, the projection of a point
of P 3 to a point
be described by a 3 \Theta 4 homogeneous projection matrix
For a restricted class of camera models, by setting the third
row of the perspective camera P 3\Theta4 to (0; 0; 0; ), we obtain
the affine camera initially introduced by Mundy and
Zisserman [27],
The affine camera A 3\Theta4 encompasses the uncalibrated
versions of the orthographic, weak perspective and paraperspective
projection models. These reduced camera
models provide a good approximation to the perspective
projection model when the depth of the object is small
compared to the viewing distance. For more detailed relations
and applications, one can refer to [20], [22], [28], [29],
[13].
For points in the affine spaces IR 3 and IR 2 , they are naturally
embedded into by the mappings w a 7!
We have thus
. If we
further use relative coordinates of the points with respect
to a given reference point (for instance, the centroid of the
set of points), the vector t 0 is cancelled and we obtain the
following linear mapping between space points and image
points:
\Deltaw
This is the basic equation of the affine camera for points.
III. The affine camera for lines
Now consider a line in IR 3 through a point x 0 , with direction
The affine camera A 3\Theta4 projects this to an image line
A 3\Theta4
passing through the image point
with direction
This equation describes a linear mapping between direction
vectors of 3D lines and those of 2D lines, and reflects
a key property of the affine camera: lines parallel in 3D
remain parallel in the image. It can be derived even more
directly using projective geometry by considering that the
line direction d x is the point at infinity
the projective line in P 3 and the line direction dw is the
point at infinity
of the projective line in
Equation (4) immediately follows as the affine camera
preserves the points at infinity by its very definition.
Comparing Equation (4) with Equation (1)-a projection
from P 3 to P 2 , we see that Equation (4) is nothing but a
projective projection from P 2 to P 1 if we consider the 3D
and 2D "line directions" as 2D and 1D projective "points".
This key observation allows us to establish the following.
The affine reconstruction of line directions with a two-dimensional
affine camera is equivalent to the projective
reconstruction of points with a one-dimensional projective
camera.
One of the major remaining efforts will be concerned with
projective reconstruction from the points in P 1 . There
have been many recent works [30], [31], [32], [33], [34], [35],
[36], [37], [38], [39], [40], [41], [10], [42], [43] on projective
reconstruction and the geometry of multi-views of two dimensional
uncalibrated projective cameras. Particularly,
the tensorial formalism developed by Triggs [36] is very interesting
and powerful. We now extend this study to the
case of the one-dimensional camera. It turns out that there
are some nice properties which were absent in the 2D case.
IV. Uncalibrated one-dimensional camera
A. Trilinear tensor of the three views
First, rewrite Equation (4) in the following form:
in which we use
of dw and d x to stress that we are dealing with "points"
QUAN: AFFINE STRUCTURE FROM LINE CORRESPONDENCES 3
in the projective spaces P 2 and P 1 rather than "line direc-
tions" in the vector spaces IR 3 and IR 2 .
We now examine the matching constraints between multiple
views of the same point. Since two viewing lines in the
projective plane always intersect in a point, no constraint is
possible for less than three views. There is one constraint
only for the case of 3 views. Let the three views of the
same point x be given as follows:
These can be rewritten in matrix form as@ M u
x
which is the basic reconstruction equation for a one-dimensional
camera. The vector
be zero, so fi fi fi fi fi fi
The expansion of this determinant produces a trilinear constraint
of three viewsX
or in short
homogeneous tensor
whose components T ijk are 3 \Theta 3 minors of the following
6 \Theta 3 joint projection matrix:@ M
The components of the tensor can be made explicit as
2: (11)
where the bracket [ij 0 k 00 ] denotes the 3 \Theta 3 minor of i-
row vector of the above joint projection
matrix and bar " " in  i,  j and
k denotes the dualization
It can easily be seen that any constraint obtained by
adding further views reduces to a trilinearity. This proves
the uniqueness of the trilinear constraint. Moreover, the
homogeneous tensor T 2\Theta2\Theta2 has
d.o.f., so it is a minimal parametrization of three views
since three views have exactly
3 \Theta (2 \Theta 3 \Gamma
d.o.f. up to a projective transformation in P 2 .
Each point correspondence over three views gives one linear
constraint on the tensor components T ijk . We can establish
the following.
The tensor components T ijk can be estimated linearly with
at least 7 points in P 1 .
At this point, we have obtained a remarkable result that for
a one-dimensional projective camera, the trilinear tensor
encapsulates exactly the information needed for projective
reconstruction in P 2 . Namely, it is the unique matching
constraint, it minimally parametrizes the three views and
it can be estimated linearly. Contrast this to the 2D projective
camera case in which the multilinear constraints are
algebraically redundant and the linear estimation is only an
approximation based on over-parametrization.
B. Retrieving normal forms for projection matrices
The geometry of the three views is most conveniently, and
completely represented by the projection matrices associated
with each view. In the previous section, the trilinear
tensor was expressed in terms of the projection matrices.
Now we seek a map from the trilinear tensor representation
back to the projection matrix representation of the three
views.
Without loss of generality, we can always take the following
normal forms for the three projection matrices
Actually, the set of projection matrices fM;M
parametrized this way has more than the
minimum of 7. Further constraints can be imposed. We
can observe that any projective transformation in P 2 of the
I 2\Theta2 0
for an arbitrary 2-vector v leaves M invariant and transforms
~
A c
As c cannot be a zero vector, it can be normalized such
that c T c = 1. If we further choose an arbitrary vector v
to be \GammaA T c, then ~
A. It can now be easily
verified that ~
This amounts to saying that ~
A in
4 IEEE-PAMI, VOL. *, NO. *, 199*
~
M 0 can be taken to be a rank 1 matrix up to a projective
transformation, i.e.
~
a 1 aea 1
a
for a non-zero scalar ae. The 2-vector c is then (\Gammaa 2 ; a 1 ) T .
Hence M 0 can be represented as
a
by two parameters, the ratio a 1 : a 2 and ae. Therefore, a
minimal 7 parameter representation for the set of projection
matrices has been obtained.
With the projection matrices given by (13), the trilinear
tensor (T ijk ) defined by (11) becomes
represents the dulization (12).
If we consider the tensor (T ijk ) as an 8-vector
the eight homogeneous equations of (15) can be rearranged
into 7 non-homogeneous ones by taking the ratios t l : t 8 for
7. By separating the entries of M 0 from those of
G 7\Theta6@ d
e
where the matrix G 7\Theta6 is given
Since the parameter vector (d; cannot be zero,
the 7 \Theta 6 matrix in Equation (16) has at most rank 5. Thus
all of its 6 \Theta 6 minors must vanish. There are
such minors which are algebraically independent,
and each of them gives a quadratic polynomial in a 1 , a 2
and ae as follows:
ae
By eliminating ae, we obtain a homogeneous quadratic equation
in a 1 and a
where
This quadratic equation may be easily solved for a 1 =a 2 .
Then ae is given by the following linear equation for each of
two solutions of a 1 =a 2
Thus, we obtain two possible solutions for the projection
Finally, the 6-vector (d; for the projection matrix M 00
is linearly solved from Equation (16) (for instance, using
SVD) in terms of M 0 .
C. 2D projective reconstruction-3D affine line direction
reconstruction
With the complete determination of the projection matrices
of the three views, the projective reconstruction
of "points" in P 2 , which is equivalent to the affine
reconstruction of "line directions" in IR 3 , can be performed.
From the projection equation each point of a
view homogeneous linear equation
in the unknown point x in P 2
2 are the first and second row vector of
the matrix M. With one point correspondence in three
views we have the following homogeneous
linear equation system,@
A
where   designates a constant entry. This equation system
can be easily solved for x, either considered as a point in
or as an affine line direction in IR 3 .
V. Uncalibrated translations
To recover the full affine structure of the lines, we still
need to find the vectors t 3\Theta1 of the affine cameras defined
in (2). These represent the image translations and magnification
components of the camera. Recall that line correspondences
from two views-now a 2D view instead of 1D
view-do not impose any constraints on camera motion:
The minimum number of views required is three. If the
interpretation plane of an image line for a given view is defined
as the plane going through the line and the projection
center, the well-known geometric interpretation of the constraint
available for each line correspondence across three
views (cf. [3], [5]) is that the interpretation planes from
different views must intersect in a common line in space.
QUAN: AFFINE STRUCTURE FROM LINE CORRESPONDENCES 5
If the equation of a line in the image is given by
l T
then substituting produces the equation
of the interpretation plane of l in space:
l T A 3\Theta4
The plane is therefore given by the 4-vector p
which can also be expressed as
the normal vector of the plane.
An image line of direction nw can be written as
its interpretation plane being
The 2 \Theta 3 submatrices M 2\Theta3 representing uncalibrated
camera orientations have already been obtained from the
two-dimensional projective reconstruction. Now we proceed
to recover the uncalibrated translations.
For each interpretation plane (n x ; p) T of each image line,
its direction component is completely determined by the
previously computed fM;M as
Only its fourth component remains undetermined.
This depends linearly on t. Notice that as the direction
vector can still be arbitrarily and individually rescaled, the
interpretation plane should be properly written as
Hence the ratio = is significant, and this justifies the
homogenization of the vector t.
So far we have made explicit the equation of the interpretation
planes of lines in terms of the image line and the
projection matrix, the geometric constraint of line correspondences
on the camera motion gives a 3 \Theta 4 matrix
whose rows are the three interpretation planes@
which has rank at most two. Hence all of its 3 \Theta 3 minors
vanish. Only two of the total of four minors are
algebraically independent, as they are connected by the
quadratic identities [44].
The vanishing of any two such minors provides the two
constraints on camera motion for a given line correspondence
of three views. The minor formed by the first three
columns contains only known quantities. It provides the
constraint on the directions. It is easy to show that it is
equivalent to the tensor by using suitable one-dimensional
projective transformations.
By taking any two of the first three columns, say the first
two, and the last column, we obtain the following vanishing
determinant: fi fi fi fi fi fi
l T t
l 0T t 0
l 00T t 00
where the " " designates a constant entry.
Expanding this minor by cofactors in the last column gives
a homogeneous linear equation in t, t 0 and
\Theta \Theta \Theta
where the "\Theta" designates a constant 3-vector in a row.
Collecting all these vanishing minors together, we obtainB @
\Theta \Theta \Theta
\Theta \Theta \ThetaC A
n\Theta9@
for n line correspondences in three views.
At this stage, since the origin of the coordinate frame in
space is not yet fixed, we may take up to
a scaling factor, say t so the final homogeneous linear
equations to solve for
\Theta \Theta
\Theta \ThetaC A
n\Theta7@ t 0
This system of homogeneous linear equations can be nicely
solved by Svd factorisation. The least squares solution for
subject to jj(t is the right singular
vector corresponding to the smallest singular value.
VI. Affine shape
The projection matrices of the three views are now completely
determined up to a common scaling factor. From
now on, it is a relatively easy task to compute the affine
shape. Two methods to obtain the shape will be described,
one based on the projective representation of lines and another
on the minimal representation of lines, inspired by
[5].
A. Method 1: projective representation
A projective line in space can be defined either by a pencil
of planes (a pencil of planes is defined by two projective
planes) or by any two of its points.
The matrix
WP =@
6 IEEE-PAMI, VOL. *, NO. *, 199*
should have rank 2, so its kernel must also have dimension
2. The range of WP defines the pencil of planes and the
null space defines the projective line in space.
Once again, using Svd to factorize WP gives us everything
we want. Let
be the Svd of WP with ordered singular values. Two
points of the line might be taken to be v 3 and v 4 , so the
line is given by
One advantage of this method is that, using subset selection
[45], near singular views can be detected and discarded.
B. Method 2: Minimal representation
As a space line has 4 d.o.f., it can be minimally represented
by four parameters. One such possibility is suggested by [5]
which uses a 4-vector l such that the line
is defined as the intersection of two planes (1; 0; \Gammaa; \Gammax
and (0; 1; \Gammab; \Gammay 0 ) T with equations:
Geometrically this minimal representation gives a 3D line
with direction (a; b; 1) T and passing through the point
This representation excludes, therefore, the
lines of direction (a; b; parallel to the xy plane. Two
other representations are needed, each excluding either the
directions (0; b; c) T or (a; 0; c) T . These 3 representations
together completely describe any line in space.
In our case, we have no problem in automatically selecting
one of the three representations, as the directions of lines
have been obtained in the first step of factorisation, allowing
us to switch to one of the three representations. There
remain only two unknown parameters x 0 and y 0 for each
line.
To get a solution for x 0 and y 0 , as the two planes
defining the line belong
to the pencil of planes defined by WP , we can still
stack these two planes on the top of WP to get the matrix
Since this matrix still has rank 2, all its 3 \Theta 3 minors vanish.
Each minor involving x 0 and y 0 gives a linear equation in x 0
and y 0 . With n views, a linear equation system is obtained
An\Theta2
This can be nicely solved using least squares for each line.
VII. Affine-structure-from-lines theorem
Summarizing the results obtained above, we have established
the following.
For the recovery of affine shape and affine motion from
line correspondences with an uncalibrated affine camera,
the minimum number of views needed is three and the minimum
number of lines required is seven for a linear solu-
tion. There are always two solutions for the recovered affine
structure.
This result can be compared with that of Koenderink and
Doorn [14] for affine structure with a minimum of two
views and five points.
We should also note the difference with the well-known results
established for both calibrated and uncalibrated projective
cameras [3], [4], [5], [39]: A minimum of 13 lines in
three views is required to have a linear solution. It is important
to note that with the affine camera and the method
presented in this paper, the number of line correspondences
for achieving a linear solution is reduced from 13 to 7, which
is of great practical importance.
VIII. Outline of the 7-line \Theta 3-view algorithm
The linear algorithm to recover 3D affine shape/motion
from at least 7 line correspondences over three views with
uncalibrated affine cameras may be outlined as follows:
1. If an image line segment is represented by its end-points
the direction vector of the line
this as the homogeneous coordinates of a point in P 1 .
2. Compute the tensor components (T ijk ) defined by
Equation linearly with at least 7 lines in 3 views.
3. Retrieve the projection matrices fM;M of the
one-dimensional camera from the estimated tensor using
Equations (17), (18) and (16). There are always
two solutions.
4. Perform 2D projective reconstruction using equation
which recovers the directions of the affine lines
in space and the uncalibrated rotations of the camera
motion.
5. Solve the uncalibrated translation vector (t; t
using Equation (20) by linear least squares.
6. Compute the final affine lines in space using Equation
(21) or (22).
IX. Line-based factorisation method from an
image stream
The linear affine reconstruction algorithm described above
deals with redundant lines, but is limited to three views.
In this section we discuss redundant views, extending the
algorithm from the minimum of three to any number N ? 3
of views.
In the past few years, a family of algorithms for structure
from motion using highly redundant image sequences
called factorisation methods have been extensively studied
QUAN: AFFINE STRUCTURE FROM LINE CORRESPONDENCES 7
[18], [19], [20], [21], [22] for point correspondences for affine
cameras. Algorithms of this family directly decompose the
feature points of the image stream into object shape and
camera motion. More recently, a factorisation based algorithm
has been proposed by Triggs and Sturm [36], [37] for
3D projective reconstruction. We will accomodate our line-based
algorithm to this projective factorisation schema to
handle redundant views.
A. 2D projective reconstruction by rescaling
According to [36], [37], 3D projective reconstruction is
equivalent to the rescaling of the 2D image points. We
have already proven that recovering the directions of affine
lines in space is equivalent to 2D projective reconstruction
from one-dimensional projective images. Therefore, a re-construction
of the line directions in 3D can be obtained
by rescaling the direction vectors, viewed as points of P 1 .
For each 1D image point in three views (cf. Equation (6)),
the scale factors ,  0 and  00 -taken individually-are ar-
bitrary. However, taken as a whole (;
the projective structure of the points x in P 2 .
One way to recover the scale factors (;  is to use
the basic reconstruction equation (7) directly or alternatively
to observe the following matrix identity:@ M u
The rank of the left matrix is therefore at most 3. All 4 \Theta 4
minors vanish, and three them
are algebraically independent, for instance,
M u
Each of them can be expanded by cofactors in the last column
to obtain a linear homogeneous equation in ;
Therefore can be solved linearly using@
A@
where   designate a known constant entry in the matrix.
For each triplet of views, the image points can be consistently
rescaled according to Equation (23). For the case
of n ? 3 views, we can take appropriate triplets among
n views such that each view is contained in at least two
triplets. Then, the rescaling equations of all triplets of
views for any given point can be chained together over n
views to give a consistent (;
B. Direction factorisation-step 1
Suppose we are given m line correspondences in n views.
The view number is indexed by a superscript and the line
number by a subscript. We can now create the 2n \Theta m
measurement matrix WD of all lines in all views by stacking
all the direction vectors d (j)
properly rescaled by  (j)
of m lines in n views as follows:
wm
(n)
Since the following matrix equation holds for the measurement
the rank of WD is at most of three. The factorisation
method can then be applied to WD .
Let
be the Svd factorisation (cf. [45], [46]) of WD . The 3 \Theta 3
diagonal matrix \Sigma D3 is obtained by keeping the first three
singular values (assuming that singular values are ordered)
of \Sigma and UD3 (VD3 ) are the first 3 columns (rows) of U
(V).
Then, the product UD3 \Sigma D3V T
D3 gives the best rank 3 approximation
to WD .
One possible solution for "
D may be taken to be
For any nonsingular 3 \Theta 3 matrix A 3\Theta3 -either considered
as a projective transformation in P 2 or as an affine transformation
in
MA 3\Theta3 and "
D are also
valid solutions, as we have
This means that the recovered direction matrix "
D and the
rotation matrix "
are only defined up to an affine transformation

C. Translation factorisation-Step 2
We can stack all of the interpretation planes from different
views of a given line to form the following n \Theta 4 measurement
matrix of planes:
l T t
l 0T t 0
8 IEEE-PAMI, VOL. *, NO. *, 199*
This matrix WP geometrically represents a pencil of
planes, so it still has rank at most 2. For any three rows
of WP , taking any minor involving the t (i) , we
obtain fi fi fi fi fi fi fi
l (i) T
l (j) T t (j)
l
0:
Expanding this minor by cofactors in the last column gives
a homogeneous linear equation in t (i) , t (j) and t
\Theta \Theta \Theta
\Delta@
where each "\Theta" designates a constant 3-vector in a row.
Collecting all these minors together, we
\Theta \Theta \Theta 0 0
We may take up to a scaling factor, say
so the final homogeneous linear equations to solve for
are
\Theta \Theta 0 0
Once again, this system of equations can be nicely solved
by Svd factorisation of W T . The least squares solution
for subject to jj(t
the singular vector corresponding to the smallest singular
value of W T .
Note that the efficiency of the computation can be further
improved if the block diagonal structure of W T is
exploited.
D. Shape factorisation-Step 3
The shape reconstruction method developed for three views
extends directly to more than 3 views. Given n views, for
each line across n views, we just augment the matrix W p
from a 3 \Theta 4 to n \Theta 4 matrix, then apply exactly the same
method.
X. Outline of the line-based factorisation
algorithm
The line-based factorisation algorithm can be outlined as
follows:
1. For triplets of views, compute the tensor (T ijk ) associated
with each triplet, then rescale the directions of
lines of the triplet using Equation (23).
2. Chain together all the rescaling
factors (;  for each line across the
sequence.
3. Factorise the rescaled measurement matrix of direction

to get the uncalibrated rotations and the directions of
the affine lines
4. Factorise the measurement matrix using the constraints
on the motion
to get the uncalibrated translation vector
5. Factorise the measurement matrix of the interpretation
planes for each line correspondence over all views
to get two points of the line
XI. Euclidean structure from the calibrated
affine camera
So far we have worked with an uncalibrated affine camera,
the recovered shape and motion are defined up to an affine
transformation in space. If the cameras are calibrated, then
the affine structure can be converted into a Euclidean one
up to an unknown global scale factor.
Following the decomposition of the submatrix M 2\Theta3 of
the affine camera A 3\Theta4 as introduced in [22],
the metric information from the calibrated affine camera
is completely contained in the affine intrinsic parameters
KK T . Each view with the associated uncalibrated rotation
is subject to
for the unknown affine transformation X which upgrades
the affine structure to a Euclidiean one. A linear solution
may be expected as soon as we have three views if we
QUAN: AFFINE STRUCTURE FROM LINE CORRESPONDENCES 9
solve for the entries of XX T . However it may happen that
the linear estimate of XX T is not positive-definite due to
noise. An alternative non-linear solution using Cholesky
parametrization that ensures the positive-definiteness can
be found in [22].
Once we obtain the appropriate "
carry the rotations of the camera and the directions of lines.
The remaining steps are the same as the uncalibrated affine
camera case.
If we take the weak perspective as a particular affine camera
model, with only the aspect ratio of the camera, Euclidean
structure is obtained this way.
XII. Experimental results
A. Simulation setup
We first use simulated images to validate the theoretical development
of the algorithm. To preserve realism, the simulation
is set up as follows. First, a real camera is calibrated
by placing a known object of about 50 cm 3 in front of the
camera. The camera is moved around the object through
different positions. A calibration procedure gives the projection
matrices at different positions, and these projection
matrices are rounded to affine projection matrices. Three
different positions which cover roughly 45 o of the field of
view are selected. A set of 3D line segments within a cube
of generated synthetically and projected onto the
different image planes by the affine projection matrices. All
simulated images are of size 512 \Theta 512. Both 3D and 2D
line segments are represented by their endpoints.
The noise-free line segments are then perturbed as follows.
To take advantage of the relatively higher accuracy of line
position obtained by the line fitting process in practice,
each 2D line segment is first re-sampled into a list of evenly
spaced points of the line segment. The position of each
point is perturbed by varying levels of noise of uniform
distribution. The final perturbed line is obtained by a least
squares fit to the perturbed point data.
Reconstruction is performed with 21 line segments and two
different re-sample rates. The average residual error is defined
to be the average distance of the midpoint of the
image line segment to the reprojected line in the image
plane from the 3D reconstructed line. In Table I, the average
residual errors of reconstruction are given with various
noise levels. The number of points used to fit the line
is the length of the line segment in pixels, this re-sample
rate corresponds roughly to the digitization process. Table
II shows the results with the number of points used
to fit the line equal to only one fourth the length of the
line segment. We can notice that the degradation with the
increasing noise level is very graceful and the reconstruction
results remain acceptable with up to \Sigma5:5 pixel noise.
These good results show that the reconstruction algorithm
is numerically stable. While comparing Table I and II, it
shows that higher re-sample rate gives better results, this
confirms the importance of the line fitting procedure-the
key advantage of line features over point features.
Another influential factor for the stability of the algorithm
is the number of lines used. Table III confirms that the
more lines used, the better the results obtained. In this
test, the pixel error is set to \Sigma1:5.
Lines # 8 13 17 21
Average residual error 1.9 1.6 0.59 0.26


III
Average residual errors of reconstruction with \Sigma 1.5 pixel
noise and various number of lines.
B. The experiment with real images
A Fujinon/Photometrics CCD camera is used to aquire a
sequence of images of a box of size 12 \Theta 12 \Theta 12:65cm. The
image resolution is 576 \Theta 384. Three of the frames in the
sequence used by the experiments are shown in Figure 1.
A Canny-like edge detector is first applied to each image.
The contour points are then linked and fitted to line segments
by least squares. The line correspondences across
three views are selected by hand. There are a total of 46
lines selected, as shown in Figure 2.
Fig. 2. Line segments selected across the image sequence.
The reconstruction algorithm generates infinite 3D lines,
each defined by two arbitrary points on it. 3D line segments
are obtained as follows. We reproject 3D lines into
one image plane. In the image plane selected, the corresponding
original image line segments are orthogonally projected
onto the reprojected lines to obtain the reprojected
line segments. Finally by back-projecting the reprojected
line segments to space, we obtain the 3D line segments,
each defined by its two endpoints.
Excellent reconstruction results are obtained. An average
residual error of one tenth of a pixel is achieved. Figure 3
shows two views of the reconstructed 3D line segments.
We notice that the affine structure of the box is almost
perfectly recovered.

Table

IV shows the influence of the number of line segments
Average residual error 0.045 0.061 0.10 0.15 0.20 0.25


I
Average residual errors with various noise levels for the reconstruction with 21 lines over three views. The number of
points to fit the line is the length of the line segment in pixels.
Average residual error 0.077 0.26 0.31 0.44 0.65 1.1


II
Average residual errors of reconstruction with various noise levels. The number of points to fit the line segment is one
fourth the length of the line segment.
Fig. 1. Three original images of the box used for the experiments.
used by the algorithm. The reconstruction results degrade
gracefully with decreasing number of lines.
Average residual error 1.3 0.88 0.28 0.12


IV
Table of residual errors of reconstruction with different
number of line segments.

Table

V shows the influence of the distribution of line segments
in space. For instance, one degenerate case for structure
from motion is that when all line segments in space lie
on the same plane. Actually, in our images, line segments
lie on three different planes-pentagon face, star shape face
and rectangle face-of the box. We also performed experiments
with line segments lying on only two planes. Table V
shows the results with various different two-plane configu-
rations. Compared with the three-plane configuration, the
reconstruction algorithm does almost equally well.
To illustrate the effect of using affine camera model as an
approximation to the perspective camera, we used a bigger
cube of size 30 \Theta 30 \Theta 30cm, which is two and a half times
the size of the first smaller cube. The affine approximation
to the perspective camera is becoming less accurate
than it was with the smaller cube. A sequence of images
of this cube is aquired in almost the same conditions as for
the smaller cube. The perspective effect of the big cube
is slightly more pronounced as shown in Figure 4. The
configuration of line segments is preserved. A total of 39
line segments of three views is used to perform the recon-
struction. Figure 5 illustrates two reprojected views of the
reconstructed 3D line segments. Compared with Figure 3,
the reconstruction is slightly degraded: in the top view of

Figure

5, we notice that one segment falls a little apart
from the pentagon face of the cube. Globally, the degradation
is quite graceful as the average residual error is only
0.3 pixels, compared with 0.12 pixels for the smaller cube.
The affine structures obtained can be converted to Euclidean
ones (up to a global scaling factor) as soon as we
know the aspect ratio [22], which is actually 1 for the camera
used. Figure 6 shows the rectified affine shape illustrated
in Figure 3. The two sides of the box are accurately
orthogonal to each other.
XIII. Discussion
A linear line-based structure from motion algorithm for
uncalibrated affine cameras has been presented. The algorithm
requires a minimum of seven line correspondences
over three views. It has also been proven that seven lines
over three views are the strict minimum data needed to recover
affine structure with uncalibrated affine cameras. In
other words, in contrast to projective cameras, the linear
algorithm is not based on the over-parametrization. This
gives the algorithm intrinsic stability. The previous results
of Koenderink and Van Doorn [14] on affine structure from
motion using point correspondences are therefore extended
to line correspondences. To handle the case of redundant
views, a factorisation method was also developed. The experimental
results based on real and simulated image sequences
demonstrate the accuracy and the stability of the
algorithms.
As the algorithms presented in this paper are developed
within the same framework as suggested in [22] for points,
it is straightforward to integrate both points and lines into
the same framework.
QUAN: AFFINE STRUCTURE FROM LINE CORRESPONDENCES 11
Line configuration star+rect.+pent. star+rect. pent.+rect. star+pent.
Average residual error 0.12 0.078 0.14 0.28


Table of residual errors of reconstruction with different data.
Fig. 3. Reconstructed 3D line segments: a general view and a top
view.
Fig. 4. One original image of the big cube image sequence.
Fig. 5. Two views of the reconstructed line segments for the big box:
a general view and a top view.
Fig. 6. A side view of the Euclidean shape obtained by using the
known aspect ratio of the camera.

Acknowledgement

This work was supported by CNRS and the French Min-
ist'ere de l'Education which is gratefully acknowledged. I
would like to thank D. Morris, N. Chiba and B. Triggs for
their help during the development of this work.



--R

"Deter- mination of the attitude of 3D objects from sigle perspective view"
Stereovision and Sensor Fusion
"Estimation of rigid body motion using straight line correspondences"
"A linear algorithm for motion estimation using straight line correspondences"
"Motion and structure from point and line matches"
3D Dynamique Scene Analysis
"Motion and structure from line correspondences: Closed-form solution, uniqueness, and op- timization"
"Optimal estimation of object pose from a single perspective view"
"Motion of points and lines in the uncalibrated case"
"A unified theory of structure from motion"
"A computer program for reconstructing a scene from two projections"
"Projective reconstruction from line correspon- dences"
The Interpretation of Visual Motion
"Affine structure from mo- tion"
"Affine shape representation from motion through reference points"
"Finding point correspondences and determining motion of a rigid object from two weak perspective views"
"Recursive affine structure and motion from image sequences"
"Shape and motion from image streams under orthography: A factorization method"
"Linear and incremental acquisition of invariant shape models from image sequences"
"3D motion recovery via affine epipolar geometry"
"A paraperspective factorization method for shape and motion recovery"
"Self-calibration of an affine camera from multiple views"
"Object pose: the link between weak perspective, para perspective, and full perspec- tive"
PhD thesis
"Recognition by linear combinations of models"
"A factorization method for affine structure from line correspondences"
Geometric Invariance in Computer Vision
"Obtaining surface orientation from texels under perspective projection"
"Perspective approximations"
"What can be seen in three dimensions with an un-calibrated stereo rig?"
"Stereo from uncalibrated cameras"
Matrice fondamentale et autocalibration en vision par ordinateur
"Canonic representations for the geometries of multiple projective views"
"Relative 3D reconstruction using multiple uncalibrated images"
"Invariants of six points and projective reconstruction from three uncalibrated images"
"Matching constraints and the joint image"
"A factorization based algorithm for multi-image projective structure and motion"
"On the geometry and algebra of the point and line correspondences between n images"
"Lines and points in three views - an integrated approach"
"Algebraic functions for recognition"
"Structure from motion using line correspondences"
"Dual computation of projective shape and camera positions from multiple images"
"Ac- tive visual navigation using non-metric structure"
Algorithms in Invariant Theory
Matrix Computation
Numerical Recipes in C
--TR

--CTR
Nassir Navab , Yakup Genc , Mirko Appel, Lines in One Orthographic and Two Perspective Views, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.7, p.912-917, July
Jong-Seung Park, Interactive 3D reconstruction from multiple images: a primitive-based approach, Pattern Recognition Letters, v.26 n.16, p.2558-2571, December 2005
Fredrik Kahl , Anders Heyden, Affine Structure and Motion from Points, Lines and Conics, International Journal of Computer Vision, v.33 n.3, p.163-180, Sept. 1999
Long Quan, Two-Way Ambiguity in 2D Projective Reconstruction from Three Uncalibrated 1D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.212-216, February 2001
Yichen Wei , Eyal Ofek , Long Quan , Heung-Yeung Shum, Modeling hair from multiple views, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Adrien Bartoli , Peter Sturm, Structure-from-motion using lines: representation, triangulation, and bundle adjustment, Computer Vision and Image Understanding, v.100 n.3, p.416-441, December 2005
Magnus Oskarsson , Kalle strm , Niels Chr. Overgaard, The Minimal Structure and Motion Problems with Missing Data for 1D Retina Vision, Journal of Mathematical Imaging and Vision, v.26 n.3, p.327-343, December  2006
Kalle strm , Magnus Oskarsson, Solutions and Ambiguities of the Structure and Motion Problem for 1DRetinal Vision, Journal of Mathematical Imaging and Vision, v.12 n.2, p.121-135, April 2000
Olivier Faugeras , Long Quan , Peter Strum, Self-Calibration of a 1D Projective Camera and Its Application to the Self-Calibration of a 2D Projective Camera, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1179-1185, October 2000
Kalle strm , Fredrik Kahl, Ambiguous Configurations for the 1D Structure and Motion Problem, Journal of Mathematical Imaging and Vision, v.18 n.2, p.191-203, March
Loong-Fah Cheong , Chin-Hwee Peh, Depth distortion under calibration uncertainty, Computer Vision and Image Understanding, v.93 n.3, p.221-244, March 2004
Ben Tordoff , David Murray, Reactive Control of Zoom while Fixating Using Perspective and Affine Cameras, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.1, p.98-112, January 2004
Hayman , Torfi Thrhallsson , David Murray, Tracking While Zooming Using Affine Transfer and Multifocal Tensors, International Journal of Computer Vision, v.51 n.1, p.37-62, January
structure from motion;one-dimensional camera;uncalibrated image;factorization method;affine structure;affine camera;line correspondence