Determining camera pose from three landmarks and accelerometer: initial notes

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 m₁ and m₂, 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 m₃ does not lie on the same line as both m₁ and m₂, and hence neither the pair m₁ and m₃ nor th epair m₂ and m₃ 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 m₁ and m₂ satisfy (a), suppose that some pair of landmarks lies on the same horizontal plane. It can’t be m₁ and m₂ (as then they will be at the same point, and hence all three landmarks will be on one line). Without loss of generality, suppose m₁ and m₃ lie on the same horizontal plane H. The pair m₁ and m₃ cannot satisfy (a) (or else m₃ is at the same point as m₁). 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 m₁ and m₂. Let m′₃ be the projection of m₃ to this plane. From the camera’s optical parameters and the camera image, we can calculate the angles m₁Cm₂, m₁Cm′₃ and m₂Cm′₃. 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 m₁Cm₂, m₁Cm′₃ and m₂Cm′₃ must intersect in at least three points. This would require m₁, m₂, m′₃ and C to all lie on the same circle T.

Now, suppose m₃ lies off the plane H. Then given the camera image and the gravity vector, we can measure the angle between m₃, the camera and the plane H, and given the position of m₃ we can compute the distance from m′₃ to the camera. This constrains the camera to lie on the circle T as well as on a second circle T′ around m′₃. Since m′₃ lies on T, these two circles intersect in at most two points. Thus, we have at most two solutions.

On the other hand, when m₃ is in the same plane, so m₁, m₂, m₃ 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 m₁, m₂ and m₃ 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 m₁ and m₂ lie on the same plane and m₃ lies off the plane. Suppose the camera is horizontally oriented, and pointed at m₁. Wherever the camera is on the blue arc, it sees m₁ and m₂ the same way (because the angle indicated by the dotted lines does not change, as discussed above). The image of m₃ in the camera is always directly above or below the image of m₁, and as long as the distance from camera to m₁ is the same, the image of m₃ does not move. Thus, the image of m₃ 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.