Suppose we have three landmarks at known locations in three
dimensional space, not all on one line, and a camera that is not located
at any landmark but sees all three landmarks, with known optical
parameters such as focal length. The problem of determining the camera
pose—the camera position and angles—from the positions of the landmarks
in the camera image is known as the P3P problem. It is known that in
general there will be at
most four solutions for camera pose. And indeed sometimes there will
be four solutions.
What if we have some additional information, namely we know how the
camera is oriented with respect to gravity (e.g., because the camera is
held horizontally or it’s equipped with an accelerometer)? Call the
problem of reconstructing the camera image from n landmarks and gravity data PnPA. I recently
showed that with just two landmarks, i.e., P2PA, there will be
either one, two or infinitely many solutions, and geometrically
characterized exactly which case occurs when.
Question: What can we say about the number of
solutions to P3PA?
In this post I will make some slight progress on this question.
First we characterize when there are more than two solutions. Note
that once we know the camera position, we can calculate the direction
it’s pointing from the camera image (Lemma 4 in my paper). So we only
need to look at the number of solutions for camera position.
Fact 1: There are at most two solutions for P3PA,
except in the case where the three landmarks and camera all lie on one
horizontal circle, in which case there are infinitely many
solutions.
Proof: For P2PA, we have more than two solutions in
precisely the following cases: (a) the two landmarks are on a single
vertical line; (b) the two landmarks are in the same horizontal plane
and so is the camera; and (c) the two landmarks and the camera are all
on one line. To have more that two solutions for P3PA, each pair of
landmarks must satisfy at least one of (a)–(c). Suppose this is so.
Suppose first that two landmarks, say m1 and m2, satisfy (a). Next
suppose that no two landmarks lie on the same horizontal plane, so (b)
is satisfied for no pair of landmarks. Then the third landmark m3 does not lie on the
same line as both m1 and m2, and hence neither the
pair m1 and m3 nor th epair m2 and m3 satisfies (a), and at
least one of these pairs fails to satisfy (c). Hence we have a pair that
fails to satisfy any of (a)–(c), and we have at most two solutions by my
P2PA result.
Now, continuing to suppose m1 and m2 satisfy (a), suppose
that some pair of landmarks lies on the same horizontal plane. It can’t
be m1 and m2 (as then they will be
at the same point, and hence all three landmarks will be on one line).
Without loss of generality, suppose m1 and m3 lie on the same
horizontal plane H. The pair
m1 and m3 cannot satisfy (a) (or
else m3 is at the
same point as m1).
If it satisfies either (b) or (c), the camera is on the plane P, and hence in any case we have
(b).
Furthermore, if no two landmarks satisfy (a), then since it can’t be
that every pair of landmarks satisfies (c) as that would put all the
landmarks on one line, at least one pair of landmarks must satisfy
(b).
We thus have reduced to the case where a pair of landmarks satisfies
(b): they are on the same horizontal plane H as the camera C. Let’s say that these landmarks
are m1 and m2. Let m′3 be the projection of
m3 to this plane.
From the camera’s optical parameters and the camera image, we can
calculate the angles m1Cm2,
m1Cm′3
and m2Cm′3.
It is known that the locus of points in a plane that subtend the same
angle to two fixed points is an arc through these points. Thus, if we
are to have more than two solutions, the arcs respectively through m1Cm2,
m1Cm′3
and m2Cm′3
must intersect in at least three points. This would require m1, m2, m′3 and C to all lie on the same circle
T.
Now, suppose m3
lies off the plane H. Then
given the camera image and the gravity vector, we can measure the angle
between m3, the
camera and the plane H, and
given the position of m3 we can compute the
distance from m′3
to the camera. This constrains the camera to lie on the circle T as well as on a second circle
T′ around m′3. Since m′3 lies on T, these two circles intersect in at
most two points. Thus, we have at most two solutions.
On the other hand, when m3 is in the same plane,
so m1, m2, m3 and the camera lie on
the same horizontal circle, we will have infinitely many solutions. For
if A and B are two fixed points on a circle,
and C is a third point on the
same side as A and B, the angle ACB will be
constant regardless of the choice of C. The landmarks m1, m2 and m3 split T into three arcs, and the camera
could be anywhere in the arc it’s in as far as the image goes.
Fact 2: There are cases where there are exactly two
solutions.
Proof by picture: Suppose m1 and m2 lie on the same plane
and m3 lies off the
plane. Suppose the camera is horizontally oriented, and pointed at m1. Wherever the camera
is on the blue arc, it sees m1 and m2 the same way (because
the angle indicated by the dotted lines does not change, as discussed
above). The image of m3 in the camera is
always directly above or below the image of m1, and as long as the
distance from camera to m1 is the same, the image
of m3 does not
move. Thus, the image of m3 does not change as the
camera moves on the red circle. Hence, at the two points where the red
and blue circles intersect, the camera sees the same thing, and hence we
have two solutions.