A Minimal Solution to the Generalised 3-Point Pose Problem

A Minimal Solution to the Generalised 3-Point Pose Problem
David Nist´er
Sarnoff Corporation
CN5300, Princeton, NJ 08530, USA
dnister@sarnoff.com
Abstract
It is a well known classical result that given the image pro-
jections of three known world points it is possible to solve
for the pose of a calibrated perspective camera to up to four
pairs of solutions. We solve the generalised problem where
the camera is allowed to sample rays in some arbitrary but
known fashion and is not assumed to perform a central per-
spective projection. That is, given three back-projected rays
that emanate from a camera or multi-camera rig in an ar-
bitrary but known fashion, we seek the possible poses of
Figure 1:
Left: The well known classical problem is to solve
the camera such that the three rays meet three known world
for the pose of three concurrent rays, such that the rays meet three
points. We show that the generalised problem has up to
known world points. Right: We solve the generalised problem
of finding the rigid pose of three arbitrary rays emanating from a
eight solutions that can be found as the intersections be-
generalised camera geometry, such that the three rays meet three
tween a circle and a ruled quartic surface. A minimal and
known world points. This lets us deal with any of the recently
efficient constructive numerical algorithm is given to find
very popular camera geometries that do not adhere to a central per-
the solutions. The algorithm derives an octic polynomial
spective model, such as for example a camera facing an arbitrarily
whose roots correspond to the solutions. In the classical
shaped mirror.
case, when the three rays are concurrent, the ruled quartic
surface and the circle possess a reflection symmetry such
that their intersections come in symmetric pairs. This man-
ifests itself in that the odd order terms of the octic polyno-
mial vanish. As a result, the up to four pairs of solutions
can be found in closed form. The proposed algorithm can
be used to solve for the pose of any type of calibrated cam-
era or camera rig. The intended use for the algorithm is in
a hypothesise-and-test architecture.
1. Introduction
Solving for the pose of a camera given the images of known
points in the world is a fundamental task in computer vision
in general and structure from motion in particular. Solu-
tions exist for most traditional camera models, such as for
example orthographic, weak perspective [2], affine, projec-
Figure 2: It is possible to think of the problem as that of find-
tive [5, 11] and calibrated perspective [8, 10].
ing the intersections between a ruled quartic surface and a circle.
In the case of a calibrated perspective camera, the images
There can be up to eight such intersections. The figure shows four
of three known world points constrain the possible poses of
intersections at the top and four at the bottom of the surface.
the camera to up to four pairs of solutions. At most one
solution from each pair is valid according to the orienta-
Prepared through collaborative participation in the Robotics Consortium sponsored by the U. S. Army
tion constraints and the other solution is the reflection of
Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-
01-2-0012. The U. S. Government is authorized to reproduce and distribute reprints for Government purposes
the camera centre across the plane of the three points.
notwithstanding any copyright notation thereon.

---

To find the solutions is the well known classical 3-point
lem attains a symmetry that groups the eight solutions into
perspective pose problem. It was considered already by La-
the well known four pairs of symmetric solutions.
grange and the first closed form algebraic solution appears
The rest of the paper is organised as follows. Section
to be by Grunert [9]. Grunert’s solution and those of several
2 highlights a relevant classical theorem. In section 3 we
other authors are compared in [10]. For more on the history
present the main idea of our solution approach. The con-
of the pose problem, see [8].
cepts of the solution are outlined in Sections 4 and 5. The
Many more point correspondences than the minimal
algorithm steps are stated in Section 6 and then given in
three are needed to obtain robust, accurate and automatic
detail in Section 7. Section 8 draws the link to the classi-
solutions. The strength of the minimal solutions in structure
cal case. Section 9 discusses the orientation constraints, 10
from motion is due to their application in hypothesise-and-
gives an experimental verification and 11 concludes.
test architectures such as [6, 13]. Many minimal solutions
are carried out and the multiple hypotheses thus generated
2. A Relevant Theorem
are scored based on their support over the complete set of
We will find Proposition 21 of book III of Euclid’s Elements
observations.
[4] relevant to our discussion:
We will solve a generalisation of the classical 3-point
perspective pose problem. The generalisation is motivated
Theorem 1 In a circle, all inscribed angles subtending the
by the recent popularity of generalised camera geometries
same arc are equal.
that do not adhere to the central perspective model and do
not correspond to a single viewpoint. We consider a gener-
An illustration is given in Figure 3.
alised camera that samples the light field or plenoptic func-
tion [1] in some arbitrary but known fashion. An illustration
is given in Figure 1. In practice, the generalised camera
can for example be a camera together with a curved mirror
such as a catadioptric or dioptric system, a multi-camera
rig [3, 14] or a compound camera made of many individual
sensing elements rigidly attached to each other.
A framework for generalised cameras is given in [7]
along with a calibration method. Calibration in this case
means that given an image point we know the ray of points
in the coordinate system of the camera that projects to the
Figure 3: In a circle, all inscribed angles subtending the same arc
image point. If the generalised camera has imaged three
are equal. We will find this highly relevant, since it corresponds to
known world points, the calibration immediately gives us
one of the two degrees of freedom that will remain when we study
the three rays that project to the image points. The gener-
what happens when the constraints from only two of the rays are
alised 3-point pose problem is then to find the rigid trans-
enforced.
formation of the three rays, such that they all meet their
corresponding world points.
3. Solution Approach
It is noteworthy that in solving this problem, we can treat
all generalised cameras in a unified way, without assuming
To solve our problem, we will first study how the constraints
a specific type of camera model. Without calibration, this
given by two of the three rays constrain the poses of the
would be very hard to accomplish, since in the uncalibrated
rigid bundle of rays with respect to the world. We will then
case, one would typically have to settle on a specific camera
see what this means in terms of the constraint from the third
model in which to solve for the parameters. By supposing
ray.
that the calibration is known, we can essentially relegate all
The pose has six degrees of freedom, three for rota-
specifics about the camera model to the calibration proce-
tion and three for translation. The constraint that a back-
dure, which can be carried out in a controlled environment.
projected ray should pass through a known world point re-
We will show that the generalised 3-point pose problem
moves two degrees of freedom. Hence, two rays constrain
can have up to eight solutions that correspond to intersec-
the pose to two degrees of freedom. We will think of one
tions between a circle and a ruled quartic surface as illus-
of these degrees of freedom in terms of a transformation of
trated in Figure 2. The intersections of the ruled quartic
the third world point and the other in terms of possible po-
surface with the plane of the circle is a quartic curve. A
sitions of the third back-projected ray. We will show that
plane quartic curve in general has eight intersections with
the first degree of freedom lets the third world point trace
a circle if complex solutions are taken into account. In the
out a circle relative to the camera. We will then show that
classical case, when all three rays are concurrent, the prob-
the other degree of freedom lets the third back-projected ray

---

trace out a ruled quartic surface in the world. The possible
rays are not all parallel. The case of parallel rays is es-
solutions for the pose correspond to the up to eight intersec-
sentially orthographic projection and the solutions are well
tions between the circle and the ruled quartic surface.
known [2]. If the rays are not all parallel we can find two
rays with distinct directions and choose them as the first two
4. The Circle
rays. They then have a unique common perpendicular direc-
tion. Moreover, there is a unique line in the perpendicular
In this section, we describe the first of the two degrees of
direction that meets both rays. We will refer to this line as
freedom that remain when we only enforce the constraints
the perpendicular axis. The situation is illustrated in Fig-
given by the first two rays. Consider one of the many pos-
ure 5. If we consider an orthographic projection along the
sible poses of the rigid configuration of the three rays with
perpendicular axis, we get a situation corresponding to The-
respect to the three world points, such that the first two rays
orem 1. More exactly, there is a rigid motion that revolves
meet the first two world points. The two world points define
the perpendicular axis around on a cylinder while satisfy-
a unique axis in space that passes through them both, see
ing the contraints imposed by the first two rays. In addition
Figure 4. We now observe that we are free to rotate the con-
to the perpendicular axis, the cylinder contains the first two
figuration of world points around this axis while keeping the
world points. The revolving motion affects all planes per-
configuration of rays fixed, without violating the constraints
pendicular to the axis equally, hence the intuitive notion of
given by the first two rays. This is the effect of one of our
an orthographic projection along the perpendicular axis.
degrees of freedom. We are essentially only interested in
how the rotation affects the third world point. As we rotate
around the axis of the first two world points, the third world
point describes a circle around the axis in a plane perpen-
dicular to the axis. One can therefore think of the world
coordinate system as containing the first two points and a
circle. The situation is illustrated in Figure 4.
Figure 5: An illustration of the second degree of freedom. If we
consider an orthographic projection (shown on the right) along the
perpendicular axis of the first two rays, we see that the situation
corresponds to Theorem 1. There is a set of Euclidean transfor-
mations that revolve the perpendicular axis around on a cylinder
while satisfying the contraints imposed by the first two rays. We
will find that this revolving motion causes the third ray to trace out
a ruled quartic surface.
To determine how the revolving motion affects the third
image ray, we now proceed to represent it algebraically.
We will determine a family of transformations, where each
transformation maps the world points to one of the valid
Figure 4: An illustration of the first of the two degrees of free-
positions traced out by the revolving motion. Note that this
dom that remain when we only enforce the constraints from the
means that we will think of the problem ’in reverse’, i.e.
first two point correspondences. We are free to rotate the third
the transformations we will consider map the world points
world point around the axis defined by the first two world points,
since this does not affect the constraints imposed by the first two
into the coordinate system of the image rays. We will find
rays. As we do this, the third world point describes a circle around
that the world points that can map onto the third ray lie on
the axis.
a ruled quartic surface, i.e. as we perform the revolving
motion, the third ray traces out a ruled quartic surface.
5. The Ruled Quartic Surface
5.1
Coordinate System
In this section, we describe the second degree of freedom
We first transform the rays and points to starting positions
that remains when the constraints from the first two rays
that will simplify the algebra. The starting positions are
have been enforced. We assume that the back-projected
illustrated in Figure 6. Let the first ray coincide with the

---

y-axis and let the perpendicular axis be the z-axis. Then,
where k is some slope. The transformation must also map
the origin is where the first ray meets the perpendicular axis
the second point onto the second ray. Hence, the two lines
and the axes are determined up to arbitrary signs. We then
(1) and (2) meet at the projection (b, c) of the second point
transform the points so that the first and second points take
and this projection has x-coordinate b such that
particular positions. Let the first point coincide with the
origin. Then rotate around the origin such that the second
m = (s − k)b.
(3)
world point lies on the line of intersection between the xz-
plane and the z-plane of the second ray. There are typically
Let the projected distance between the first two world points
two such locations for the second world point. For unique-
be D. The situation is depicted in Figure 7. By inspecting
ness, choose the point such that x >= 0. 1 This determines
the coordinate system for the world points up to a rotation
around the axis defined by the first two points. This rotation
can be chosen arbitrarily and does not affect the coordinate
representation of the circle.
Figure 6: Two orthographic views of the situation once we have
transformed the bundle of rays and the world points to starting
Figure 7: The situation after we have applied a valid transfor-
positions that will simplify the subsequent algebra.
mation that brings the world points to one of the configurations
arising from the revolving motion. The first world point is main-
tained on the first ray and the second world point now lies on the
5.2
Algebraic Form of the Revolving Motion
second ray.
We will now think solely in terms of a transformation in
the figure, it can now be seen that a valid transformation
the xy-plane that applies to the points while keeping the
maps the xy-coordinates (x, y) of a world point into the
rays fixed. 2 The transformation we are after moves the
xy-coordinates (˜
x, ˜
y) according to the formula
world points from the configuration shown in Figure 6 to
the configuration shown in Figure 7. The first two points
˜x
1
b
−(c − m)
x
are transformed onto their corresponding rays. The family
˜ =
0 +
. (4)
y
m
D
c − m
b
y
of transformations that achieve this represents the revolving
motion.
Let the scalar u be defined by
Let the slope of the projection of the second ray be s.
The line equation of the projection is then
u ≡ D .
(5)
b
y = sx.
(1)
Moreover, observe that by Pythagoras’ Theorem we have
The transformation must maintain the first point on the y-
(k2 + 1)b2 = D2, which leads to
axis. Let it position the first point at y = m. Moreover, let it
position the projection line of the axis through the first two
u2 = 1 + k2.
(6)
points such that the line equation of the projection is
If we use Equations (2), (3) and (5), we can now rewrite the
y = kx + m,
(2)
transformation in Equation (4) as
1If the three image points and world points do not correspond to a true
configuration, it is possible that the distance between the first two world
˜x
1
x
points is smaller than the perpendicular distance between the first two rays.
˜ = (
0
+ 1 −k
).
(7)
y
u
(s − k)D
k
1
y
In this case, the above procedure is not possible and the pose problem has
in fact no solution.
2That is, we consider a 3D transformation that affects all planes parallel
Thus, the one-dimensional family of valid transformations
to the xy-plane equally.
is parameterised by u and k under the constraint from (6).

---

5.3
The Effect on the Third Ray
The question is now which family of world points is mapped
onto the third ray by the revolving motion. If we take
Equation (7) and interpret the transformation as a full 3D-
transformation that maps homogeneous coordinates X =
0.5
x y z 1
of a world point into the new homoge-
0
neous coordinates ˜
X, we get
−0.5
−1
⎡
⎤
−1.5
x − ky
3
−2
˜
⎢ k(x − D) + sD + y ⎥
−2.5
X = ⎢
⎥
⎣
2
uz
⎦ .
(8)
−3
1
−3.5
u
−2.5
−2
−1.5
0
−1
−0.5
0
0.5
The transformed point
˜
X lies on a plane L
=
1
−1
1.5
l
Figure 8: An example of the ruled quartic surface that is traced
1
l2 l3 l4
if and only if L ˜
X = 0, i.e.
out by the third ray due to the revolving motion associated with the
a
second degree of freedom. It is interesting to note that all sections
1 + ka2 + ua3 = 0,
(9)
parallel to the xy-plane are limac¸ons and that the vertices of the
where
limac¸ons form a twisted cubic, part of which is a curve of self-
a1 ≡ xl1 + yl2 + sDl2
(10)
intersection for the surface.
a2 ≡ xl2 − yl1 − Dl2
(11)
a3 ≡ zl3 + l4.
(12)
2. Line up the points in their canonical position.
The third image ray can be represented by two planes L and
3. Compute the coefficients of the two planes represent-
L and if we define a1, a2, a3 analogously using L we have
ing the third ray.
a
4. Compute the coefficients of an octic polynomial whose
1 + ka2 + ua3
= 0
(13)
roots correspond to the intersections between the circle
a1 + ka2 + ua3 = 0.
(14)
and the quartic surface.
We eliminate k and u, respectively, to obtain
5. Extract the roots of the octic polynomial.
u(a2a3 − a2a3) = (a2a1 − a2a1)
(15)
6. Backsubstitute with each root to get the solutions for
−k(a
the transformation between the coordinate system of
2a3 − a2a3)
= (a3a1 − a3a1).
(16)
the points and the coordinate system of the rays.
If we insert these two expressions into Equation (6), we get
(
7. Algorithm Details
a2a1 − a2a1)2 = (a2a3 − a2a3)2 +(a3a1 − a3a1)2, (17)
We now give the detailed algebraic steps of the algorithm.
which by the degree is readily seen to be the definition of
a quartic surface. Since it is a union of lines, it is a ruled
7.1. Lining Up the Rays
quartic surface. An example is shown in Figure 8.
We can now insert the equation for the plane of the circle
Let the rays be represented by the points p1, p2, p3 on the
to obtain a quartic curve in its plane. A circle has up to eight
rays and the unit direction vectors d1, d2, d3. We wish to
intersections with a quartic curve and these correspond to
make d1 parallel to the y-axis. The common perpendicular
the solutions to the problem.
direction of the first two rays is
d
6. Algorithm Outline
4 ≡ (d1 × d2)/|d1 × d2|,
(18)
which is the direction we wish to make parallel to the z-axis.
An algorithm for finding the solutions to the generalised
Define also
3-point pose problem can now be discerned. The detailed
d5 ≡ d1 × d4,
(19)
numerical steps of the algorithm will be given in Section
which is the direction that will then become parallel to the
7. Before we dive into the details, we summarise the main
computational steps of the algorithm here:
x-axis. The above will be accomplished if we rotate the rays
by the rotation
1. Line up the rays in their canonical position.
R1 ≡
d5 d1 d4
.
(20)

---

The slope s of the second ray as defined by (1) will be
7.4. Intersecting the Quartic and the Circle
s ≡ (d1 d2)/(d5 d2).
(21)
We will now eliminate x and y from the quartic expression
(17) in order to get an octic polynomial in z. 3 After lining
We also wish to place the point where the first ray meets the
up the points, the circle sits in the plane defined by
perpendicular axis at the origin. This point is given by
p4 ≡ p1 + αd1,
(22)
x y z
d6 = q3 d6,
(34)
where
which gives
α ≡ (d1 − sd5) (p2 − p1).
(23)
x = κ1,
(35)
The transformation that brings the rays to their starting po-
where
|
sition is hence
q2 − q1|q
κ
3 d6
1 ≡ − e z +
.
(36)
H1 ≡
R1 −R1p4
D
D
0
1
.
(24)
Moreover, the circle is the intersection between the plane
We will henceforth assume that this transformation has al-
and the sphere
ready been applied to the rays.
x2 + y2 + z2 = |q3|2.
(37)
7.2. Lining Up the Points
If we insert Equation (35) into this, we get
Let the world points be given as q1, q2, q3. To bring them to
y2 = κ
their starting position, we first observe that the second ray
2,
(38)
now lies entirely in the z-plane whose z-coordinate e is the
where
third coordinate of p
κ
2. Note also that
2 ≡ |q3|2 − z2 − κ21.
(39)
D ≡
|q
By inserting Equation (35) into (10) and (11), we get
2 − q1|2 − e2.
(25)
Moreover,
a1 = yκ3 + κ4
(40)
d6 ≡
D 0 e
/|q2 − q1|
(26)
a2 = yκ5 + κ6
(41)
is a unit vector in the direction from the origin towards the
a3 = κ7
(42)
point where we wish to position the second world point.
Before the transformation, this direction is
a1 = yκ8 + κ9
(43)
a
d
2
= yκ10 + κ11
(44)
7 ≡ (q2 − q1)/|q2 − q1|.
(27)
Define also
a3 = κ12,
(45)
d8 ≡
0 1 0
(28)
where
d9 ≡ (d7 × (q3 − q1))/|d7 × (q3 − q1)|,
(29)
which are just unit vectors perpendicular to d6 and d7, re-
κ3 ≡ l2
(46)
spectively. Then our desired rotation is
κ4 ≡ l1κ1 + sDl2
(47)
R2 ≡ d6 d8 (d6×d8)
d7 d9 (d7×d9)
(30)
κ5 ≡ −l1
(48)
and the transformation applied to the points is
κ6 ≡ l2κ1 − Dl2
(49)
κ7 ≡ zl3 + l4
(50)
H2 ≡
R2 −R2q1
0
1
.
(31)
κ8 ≡ l2
(51)
We will henceforth assume that this transformation has al-
κ9 ≡ l1κ1 + sDl2
(52)
ready been applied to the points.
κ10 ≡ −l1
(53)
κ11 ≡ l
7.3. Computing the Plane Coefficients
2κ1 − Dl2
(54)
κ12 ≡ zl3 + l4.
(55)
To compute the coefficients L, L for the two plane equa-
tions that represent the third ray, we find two distinct nor-
Using Equations (40)-(45) and (38) we then expand the ex-
mal vectors n, n that are perpendicular to d3. We pick n as
pressions from Equation (17) as
the vector of largest magnitude out of the two vector prod-
ucts d3 ×
1 0 0
and d3 ×
0 1 0
. We then
a2a1 − a2a1 = κ13y + κ14
(56)
choose n ≡ d3 × n and the plane vectors are
a2a3 − a2a3 = κ15y + κ16
(57)
L ≡
n
−n p
a
3
(32)
3a1 − a3a1
= κ17y + κ18,
(58)
3
L
≡
n
−n p
We will work with polynomials in z labeled κ
3
.
(33)
i. To implement the
derivation of the octic, compute all the polynomials κi in sequence.

---

where
Then our desired rotation is
κ13 ≡ κ5κ9 + κ6κ8 − κ3κ11 − κ4κ10
(59)
κ
R
14
≡ κ6κ9 − κ4κ11 + κ2(κ5κ8 − κ3κ10) (60)
4 ≡ d6 d10 (d6×d10)
d6 d8 (d6×d8)
(73)
κ15 ≡ κ7κ10 − κ5κ12
(61)
and the transformation applied to the points is
κ16 ≡ κ7κ11 − κ6κ12
(62)
κ17 ≡ κ7κ8 − κ3κ12
(63)
H4 ≡
R4 0
0
1 .
(74)
κ18 ≡ κ7κ9 − κ4κ12.
(64)
The full transformation from the coordinate system of the
Squaring the right hand sides of Equations (56)-(58), insert-
points to the coordinate system of the rays is finally
ing into Equation (17) and again using Equation (38) yields
κ
H = H−1
19 = κ20y,
(65)
1 H3H4H2.
(75)
where
κ19 ≡ κ2(κ213 − κ215 − κ217) + κ214 − κ216 − κ218 (66)
8. Relation to the Classical Case
κ20 ≡ 2(κ15κ16 + κ17κ18 − κ13κ14).
(67)
In the classical case, the circle has its centre in the xy-plane
By squaring Equation (65) and again using (38) we get
and the plane of the circle is perpendicular to the xy-plane.
κ21 = 0,
(68)
The quartic surface also has a symmetry property in the
where
classical case. An example is shown in Figure 9. The re-
κ21 ≡ κ2
volving motion rotates the direction of the third ray by only
19 − κ2κ220,
(69)
180 degrees while revolving the projection centre around
which is an octic polynomial in z whose roots correspond
the complete circle, i.e. it takes two full laps for the third ray
to the up to eight solutions.
to return to its initial position. After one lap, the third ray
can be thought of as reflected across the xy-plane. Hence,
7.5. Solving the Octic
in the classical case, both the circle and the quartic surface
A method for extracting the roots of a polynomial, which is
are unaffected by a reflection across the xy-plane. In other
easy to implement with most linear algebra packages, is to
words, for any intersection point (x, y, z) there is a corre-
eigen-decompose a companion matrix. After normalising
sponding intersection (x, y, −z). The corresponding inter-
the polynomial so that it can be written
section represents the reflection of the camera projection
centre across the plane defined by the three world points.
z8 + β7z7 + β6z6 + . . . + β0,
(70)
Due to the symmetry, all the odd order terms of the octic
polynomial in Equation (68) have to vanish. This means
the roots are found as the eigenvalues of the 8×8 companion
that the octic can be considered a quartic in z 2 and the roots
matrix
⎡
⎤
−
can hence be found in closed form. Moreover, it is seen
β7 −β6 · · · −β0
⎢
that our generalised solution can handle the classical case
⎢ 1
⎥
⎢
⎥
seamlessly, without identifying it explicitly.
⎣
.
⎥
. .
⎦ .
(71)
1
9. The Orientation Constraints
More efficient however, is to find the roots using Sturm se-
In practical situations, there are typically orientation con-
quences. For more details, the reader is referred to [12],
straints arising from the requirement that the world points
where this was done for a tenth degree polynomial.
should be in the forward direction from the camera. Let a
camera ray be represented by the point p, which is where
7.6. Backsubstitution
the ray enters the camera, and the forward direction d. The
For each solution for z we can compute x by Equation (35)
world point q is then on the correct part of the ray when
and y by Equation (65). Then u and k can be computed
using Equations (15) and (16), respectively. The transfor-
d (q − p) > 0.
(76)
mation defined in Equation (7) is then uniquely determined.
We label it H3. For each solution, we also need to find
Once the tentative solutions have been extracted, it is
the transformation H4 that rotates the third world point q3
straightforward to test which ones satisfy the orientation
around to the correct point on the circle. Define
constraints. In the classical case, this singles out at most
one solution from each pair 4, leaving up to four solutions.
d10 ≡ (d6 × x y z
)/|d6 × x y z |. (72)
4Using the projection centre as p for all rays.

---

5
x 10
General Case
4
x 10
Classical Case
7
10
9
6
8
Trials 5
Trials
6
5
7
6
4
5
3
4
2
3
2
Nr Occurrences in 10
Nr Occurrences in 10
1
1
0
0
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
Nr Solutions Before Orientation Constraints
Nr Solutions Before Orientation Constraints
5
4
x 10
General Case
x 10
Classical Case
4
6
3.5
5
3
Trials
Trials
6
5
4
2.5
2
3
1.5
2
1
Nr Occurrences in 10
Nr Occurrences in 10 1
0.5
Figure 9: In the classical case, both the circle and the quartic are
0
0
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
Nr Solutions After Orientation Constraints
Nr Solutions After Orientation Constraints
symmetric with respect to reflection in the xy-plane. The solutions
Figure 11: Distribution of number of valid solutions with ran-
therefore come pairwise as reflections of each other across the xy-
dom general and classical configurations, before and after the ori-
plane. As a result, all the odd order terms of the octic polynomial
entation constraints have been enforced. In the bottom row, a mis-
vanish and the solutions can be found in closed form. The self-
alignment of 10−6 or less was required between all rays and their
intersection curve degenerates to a circle and a line.
corresponding points, which is the reason for the cases without
10. Experimental Verification
solutions. In the general case, the number of trials with eight solu-
tions is tiny but non-zero even with the orientation constraints.
The main requirements on a minimal method such as this
one are numerical accuracy and speed. Note that all min-
they have to be concurrent in a projection centre. The gen-
imal solutions will behave similarly with respect to noise.
eral solution can handle the classical case seamlessly, with-
The numerical precision is investigated in Figure 10.
out explicitly identifying it and without any numerical prob-
The majority of the computation effort is spent on find-
lems. The intended use for the algorithm is in a hypothesise-
ing the roots of the octic polynomial. An efficient imple-
and-test architecture to solve robustly for camera pose.
mentation using Sturm sequences can find the roots in less
than 25µs on a machine with a 3GHz processor. The com-
References
putation time is partially dependent on the number of real
[1] E. Adelson and J. Bergen, The Plenoptic Function and the Elements of Early
Vision, In Computational Models of Visual Processing, ISBN 0-262-12155-7,
solutions. The distribution of the number of valid solutions
MIT Press, 1991.
with random configurations is investigated in Figure 11.
[2] T. Alter, 3-D Pose from 3 Points Using Weak Perspective, IEEE Transactions
on Pattern Analysis and Machine Intelligence, Vol. 16, No.8, pp. 802-808,
1994.
General Case
Classical Case
[3] P. Baker, R. Pless, C. Ferm¨uller and Y. Aloimonos, Eyes from Eyes, SMILE
3500
8000
2000, LNCS 2018, pp. 204-217, 2001.
3000
7000
[4] Euclid, The Elements.
6000
Trials
[5] O. Faugeras, Three-Dimensional Computer Vision: a Geometric Viewpoint,
2500
Trials
5
5
5000
MIT Press, ISBN 0-262-06158-9, 1993.
2000
[6] M. Fischler and R. Bolles, Random Sample Consensus: a Paradigm for Model
4000
1500
Fitting with Application to Image Analysis and Automated Cartography, Com-
3000
1000
mun. Assoc. Comp. Mach., 24:381-395, 1981.
2000
[7] M. Grossberg and S. Nayar, A General Imaging Model and a Method for Find-
Nr Occurences in 10
Nr Occurrences in 10
500
1000
ing its Parameters, IEEE International Conference on Computer Vision, Volume
0
0
−16
−14
−12
−10
−8
−6
−4
−2
0
−16
−14
−12
−10
−8
−6
−4
−2
0
2, pp. 108-115, 2001.
Base 10 Logarithm of Numerical Error
Base 10 Logarithm of Numerical Error
[8] A. Gruen and T. S. Huang, Calibration and Orientation of Cameras in Com-
Figure 10:
The distribution of numerical error (in terms of
puter Vision, Springer Verlag, ISBN 3-540-65283-3, 2001.
[9] J. Grunert, Das Pothenotische Problem in erweiterter Gestalt nebst ¨uber seine
Frobenius norm) in the computed H based on 105 trials with ran-
Anwendungen in der Geod¨asie, Grunerts Archiv f¨ur Mathematik und Physik 1,
dom general and classical configurations of unit scale. In the gen-
238-248, 1841.
eral case, the error is below 10−6 for 96.3% of the trials. In the
[10] R. Haralick, C. Lee, K. Ottenberg and M. N¨olle, Review and Analysis of So-
lutions of the Three Point Perspective Pose Estimation Problem, International
classical case, which was not explicitly detected, the error is below
Journal of Computer Vision, 13(3):331-356, 1994.
10−6 for 99.9% of the trials.
[11] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision,
Cambridge University Press, ISBN 0-521-62304-9, 2000.
[12] D. Nist´er. An Efficient Solution to the Five-Point Relative Pose Problem, IEEE
11. Conclusion
Conference on Computer Vision and Pattern Recognition, Volume 2, pp. 195-
202, 2003.
[13] D. Nist´er. Preemptive RANSAC for Live Structure and Motion Estimation,
We have presented a generalised solution to the 3 point pose
IEEE International Conference on Computer Vision, pp. 199-206, 2003.
[14] R. Pless, Using Many Cameras as One, IEEE Conference on Computer Vision
problem, which works for any type of camera geometry,
and Pattern Recognition, Volume 2, pp. 587-593.
such as for example a camera facing an arbitrarily shaped
mirror. The generalisation removes all restrictions on the
The views and conclusions contained in this document are those of the authors and should not be interpreted as
representing the official policies, either expressed or implied, of the Army Research Laboratory or the U. S. Govern-
three rays into the camera, whereas in the classical case,
ment.

---