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.

My first (and last?) computer science paper

Some years back I was searching for a better method to play lightgun games like Duck Hunt under emulation by using a Wii remote as a light gun.

The standard Wii remote way of pointing at a TV with a sensor bar underneath is not precise enough. The Wii remote has an infrared camera that tracks the LEDs in the sensor bar, and uses that to estimate where the remote is pointing. But since all the LEDs in the sensor bars lie in a single line, there is no way to determine from the camera image exactly how the Wii remote points. (It’s easy to visualize how rotating the Wii remote about the axis defined by the sensor bar won’t change the camera image in it.) The Wii just guesses, but that’s not good enough for lightgun games.

I already had a way that involved putting four infrared LEDs around my TV, but I was wondering if one could do this with a standard sensor bar by leveraging the additional information from the accelerometer in the Wii remote. A web search came up with a paper by d’Alfonso et al. on determining camera pose using two landmarks and accelerometer. The paper claimed a theorem that, except in certain singular cases, one could determine the pose up to a two-option ambiguity—i.e., there will be two camera orientation/position setups that would result in the same landmark images and accelerometer data.

After thinking about the paper, I realized that the claimed theorem was incorrect: there were singular cases the authors didn’t know about, but more interestingly I discovered cases where one could determine camera pose from two landmark images and accelerometer data without any ambiguity. Moreover, one of these cases was precisely the one relevant to me: the two landmarks are on the same horizontal line (the Wii sensor bar supplies precisely that) and the camera is above or below the plane of that line (easy to arrange). Sadly, experiments showed that Wii remote accelerometer precision was insufficient to determine camera pose in this way.

Anyway, I don’t like the idea of there being a published “theorem” that is incorrect. At some point I worked out all the details with trigonometry, and found a precise characterization of the exact conditions under which in theory (i.e., given a sufficiently precise accelerometer, unlike the one in the Wii remote) one could determine camera pose from two landmark images and gravity data with no ambiguity, with an ambiguity of two, or with an ambiguity of infinity (in some singular cases).

I just got a paper with all the details published.

Sadly, as noted, the Wii remote application didn’t pan out. However, I did write some proof of concept code for my Pixel 7 Pro, and found that it worked pretty decently with its accelerometer. Here’s a screenshot where the accelerometer data plus the screen positions of the (centers of) the bottom two Aruco markers, together with data about the camera and the dimensions of my display board, is used to calculate the screen positions of the upper two Aruco markers (the calculated positions are marked in red).

I kind of suspect that the accelerometer in the right-hand Nintendo Switch joycon might be sufficiently precise for use as a lightgun with two infrared LEDs for positioning, but I haven’t had time to implement this. (Part of the problem is that the infrared LEDs that I have at home are the wrong wavelength for the joycon.)

While this may be my last computer science paper, if some computer science grad student or the like is interested in working with me, we could do some empirical work on seeing how applicable the algorithm is.

Inferentialism and the completeness of geometry

The Quinean criterion for existential commitment is that we incur existential commitment precisely by affirming existentially quantified sentences. But what’s an existential quantifier?

The inferentialist answer is that an existential quantifier is anything that behaves logically like an existential quantifier by obeying the rules of inference associated with quantifiers in classical logic.

Here is a fun little problem with the pairing of the above views. Tarski proved that, with an appropriate axiomatization, Euclidean geometry is complete and consistent, i.e., for every geometric sentence ϕ, exactly one of ϕ and its negation is provable from the axioms. Now let us stipulate a philosophically curious language L^*. Syntactically, the symbols of L^* are the symbols of L but with asterisks added after every logical connective, and the sentences are of L^* are the sentences of L with an asterisk added after every connective and predicate. The semantics of L^* are as follows: the sentence ϕ of L^* means that the sentence of L formed by dropping the asterisks from ϕ is provable from the axioms of Euclidean geometry.

Inferentially, the asterisked connectives of L^* behave exactly like the corresponding non-asterisked connectives of L.

Consider the sentence ϕ of L^* that is written ∃^*x(x=^*x). This sentence, by stipulation, means that ∃x(x=x) is provable from the axioms of Euclidean geometry. According to the Quinean criterion plus inferentialism, it incurs existential commitment, because ∃^*x, since it behaves inferentially just like an existential quantifier, is an existential quantifier. Now, it is intuitively correct that ∃^*x(x=^*x) does incur existential commitment: it claims that there is a proof of ∃x(x=x), so it incurs existential commitment to the existence of a proof. So in this case, the inferentialist Quinean gets right that there is existential commitment. But rather clearly only coincidentally so! For now consider the sentence ψ that is written ∀^*x(x=^*x). Since ∀^*x behaves inferentially just like ∀x, by inferentialist Quineanism it incurs no existential commitment. But ψ means that there is a proof of ∀x(x=x), and hence incurs exactly the same kind of existential commitment as ϕ did, which said that there was a proof of ∃x(x=x).

What can the inferentialist Quinean respond? Perhaps this: The language L^* is syntactically and inferentially compositional, but not semantically so. The meaning of p∨^*q, namely that the unasterisked version of p∨^*q has a proof, is not composed from the meanings of p and of q, which respectively mean that p has a proof and that q has a proof. But that’s not quite right. For meaning-composition is just a function from meanings to meanings, and there is a function from the meanings of p and of q to the meaning of p∨^*q—it’s just a messy function, rather than the nice function we normally associate with disjunction.

Perhaps what the inferentialist Quinean should do is to insist on the intuitive non-inferentialist semantic compositional meanings for the truth-functional connectives, but not for the quantifiers. This feels ad hoc.

Even apart from Quineanism, I think the above constitutes an argument against inferentialism about logical connectives. For the asterisked connectives of L^* do not mean the same thing as their unasterisked variants in L.

A new kind of project

I did something new and fun this fall: I wrote a computer science paper. It's an analysis of the conditions under which a device equipped with a camera and an accelerometer can identify its position relative to two observed landmarks with known positions. Except for a measure zero set of singular cases with infinitely many solutions, there are always at most two solutions for device positions (this was previously known), and I found necessary and sufficient conditions for there to be a single solution. In particular, if the two landmarks are at the same altitude, there is always a single solution, unless the device is at the same altitude as the landmarks.

I implemented the algorithm on a phone (code here). In the screenshot, the markers 1 and 2 are landmarks, identified and outlined in green with OpenCV library code, and then the phone uses their positions and the accelerometer data to predict where the control markers 3 and 4 are on the screen, outlining them in red.

For someone like me who does some philosophy of science, it was an interesting experience to actually do a real experiment and collect data from it.

I am planning at some point to try to implement the algorithm using infrared LEDs under a TV and the accelerometer and infrared camera inside a right Nintendo Switch joycon. To that end, over the last couple of days I've reverse-engineered two of the joycon infrared camera blob identification modes.

Greek mathematics

I think it is sometimes said that it is anachronistic to attribute to the ancient Greeks the discovery that the square root of two is irrational, because what they discovered was a properly geometrical fact, that the side and diagonal of a square are incommensurable, rather than a fact about real numbers.

It is correct to say that the Greeks discovered an incommensurability fact. But it is, I think, worth noting that this incommensurability fact is not really geometric fact: it is a geometric-cum-arithmetical fact. Here is why. The claim that two line segments are commensurable says that there are positive integers m and n such that m copies of the first segment have the same length as n copies of the second. This claim is essentially arithmetical in that it quantifies over positive integers.

And because pure (Tarskian) geometry is decidable, while the theory of the positive integers is not decidable, the positive integers are not definable in terms of pure geometry, so we cannot eliminate the quantification over positive integers. In fact, it is known that the rational numbers are not definable in terms of pure geometry either, so neither the incommensurability formulation nor theory irrationality formulation is a purely geometric claim.

I think. All this decidability and definability stuff confuses me often.