# Singular Points in the Optical Center Distribution of P3P Solutions

Authors: Lihua Hu; Bo Wang; Jifu Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Multisolution phenomenon is an important issue in P3P problem since, for many real applications, the question of how many solutions could possibly exist for a given P3P problem must at first be addressed before any real implementation. In this work we show that, given 3 control points, if the camera’s optical center is close to one of the 3 toroids generated by rotating the circumcircle of the control point triangle around each one of its 3 sides, there is always an additional solution with its corresponding optical center lying in a small neighborhood of one of the control points, in addition to the original solution. In other words, there always exist at least two solutions for the P3P problem in such cases. Since, for all such additional solutions, their corresponding optical centers must lie in a small neighborhood of control points, the 3 control points constitute the singular points of the P3P solutions. The above result could act as some theoretical guide for P3P practitioners besides its academic value.


---

## Body

## 1. Introduction

The Perspective-3-Point Problem, or P3P problem, is a single-view based pose estimation method. It was first introduced by Grunert [1] in 1841 and popularized in computer vision community a century later by mainly Fischler and Bolles’ work in 1981 [2]. Since it is the least number of points to have a finite number of solutions and no feature-matching across views is needed, it has been widely used in various fields [3–11], either for its minimal demand in restricted working environment, such as robotics and aeronautics, or for its computational efficiency acting as a minimum-set based solver repeatedly called in robust-statistics based iterative estimation framework, such as the well-known RANSAC-like framework, where the computational time increases exponentially with the cardinality of the minimum set; hence, the P3P problem is preferred due to its minimum requirement.The P3P problem is defined as follows: Given the perspective projections of three control points with known coordinates in the world system and a calibrated camera, find the position and orientation of the camera in the world system. It is shown that the P3P problem could have 1, 2, 3, or at most 4 solutions depending on the configuration between the camera optical center and its 3 control points [12]. If the optical center and 3 control points happen to be concyclic, the problem becomes degenerated, and an infinitely large number of solutions could be possible.Since, in many real applications, some basic questions must be answered before its real implementation (such as the following: Does it have a unique solution? If not, how many solutions could it have? Is the solution stable?), the multiple solution phenomenon in the P3P problem has been a focus of investigation since its very inception in the literature. Traditionally the multisolution phenomenon in P3P problem is analyzed by at first transforming its 3 quadratic constraints into a quartic equation and then roots of this quartic equation are located to derive possible solutions. For example, Haralick et al. summarized 6 different transformation methods [12]. Gao et al. [13] gave a complete solution classification. Gao and Tang [14] also gave an analysis on the solutions distribution from the probabilistic point of view. Recently, Rieck [15–17] gave a systematic analysis on the multisolution phenomenon, in particular, on the cases where the optical center of the P3P problem is close to the danger cylinder. From the geometric point of view, Zhang and Hu [18] showed that when the optical center lies on the danger cylinder, the corresponding P3P problem must have 3 distinct solutions, and one must be a double solution. Lowe [3] and Zhang and Hu [19] showed that when the optical center lies on the three vertical planes perpendicular to the control point plane and going through one of the 3 altitudes of the control point triangle, the P3P problem must have a pair of side-sharing solutions and a pair of point-sharing solutions. (As shown in [19], a pair of side-sharing solutions refers to two such solutions that if their optical centers are superposed, they must share two control points or share a common side of the control point triangle. Similarly, a pair of point-sharing solutions refers to two such solutions that if their optical centers are superposed, they must share a single common control point.) Sun and Wang [20] gave an interpretation of the solution changes at the intersecting lines of the above three vertical planes with the danger cylinder. Wu and Hu [21] gave a thorough investigation on the degenerate cases in their “The PnP Problem Revisited” work. Recently, Wang et al. [22] show that the side-sharing pair of solutions is usually accompanied by a point-sharing pair of solutions, or the two kinds of pairs are often companion pairs. They also show [23] that if the optical center is outside of all the 6 toroids, each positive root of Grunert’s quartic equation must correspond to a positive solution of the P3P problem. Their work shows that the root-solution-relationship is of one-to-one correspondence when the optical center is outside of all the 6 toroids but much more complicated when the optical center is inside of them.In this work, we investigate the multisolution phenomenon in P3P problem for those cases where the camera optical center is very close to one of the 3 toroids. More specifically, based on Grunert’s derivation [12], we show that when the optical center of a given P3P problem is close to any one of the 3 toroids generated by rotating the circumcircle of the control point triangle around each of its 3 sides, in addition to its original solution, there is always an additional solution whose optical center always lies in a small neighborhood of control points. In other words, such a P3P problem always has at least two solutions. In addition, since, for all such additional solutions, their optical centers must be in a close neighborhood of control points, the 3 control points are singular points of the solutions’ optical centers distribution.


## 2. P3P Problem, 3 Toroids, and Grunert’s Quartic Equation

### 2.1. P3P Problem

As shown in Figure1, A, B, and C are the three control points with known distance: a=BC, b=AC, and c=AB; O is the camera optical center. Since the camera (under the pinhole model) is calibrated, the three subtended angles α, β, and γ of the projection rays can be considered as known entities and then, by the Law of Cosines, the following 3 basic constraints on the three unknowns s1=OA, s2=OB, and s3=OC in (1) must hold: (1)s12+s22-2cos⁡γs1s2=c2,s12+s32-2cos⁡βs1s3=b2,s22+s32-2cos⁡αs2s3=a2.Hence, the P3P problem means to determine such positive triplets (s1,s2,s3) satisfying all the 3 basic constraints in (1). And the multisolution phenomenon refers to the existence of multiple such positive triplets (s1,s2,s3) all satisfying the 3 constraints in (1).Figure 1
P3P problem definition:A, B, and C are the 3 control points and O is the camera optical center.


### 2.2. The 3 Toroids

As shown in Figure1, by rotating the circumcircle of the triangle ABC around one of its three sides by 2π separately, 3 pairs of toroids (or 6 toroids) can be generated [24] as shown in Figure 2. For each toroid pair, one is generated by rotating the arc with the subtended angle ∠ABC (or ∠BAC, or ∠ACB) and the other with its supplement angle (π-∠ABC) (or (π-∠BAC), or (π-∠ACB)). In this work, the 3 toroids refer to the 3 ones generated only with the subtended angle ∠ABC, ∠BAC, and ∠ACB, denoted by Toroid_AC, Toroid_BC, and Toroid_AB, respectively. Hence, when the optical center lies on Toroid_AC (or Toroid_BC, or Toroid_AB), the subtended angle β (or α, or γ) of the two projection rays (OA,OC) (or (OB,OC), or (OA,OB)), by definition, always has β=∠ABC (or α=∠BAC, or γ=∠ACB).Figure 2
(a) A single toroid; (b) three toroids.
(a)
(b)


### 2.3. Grunert’s Derivation

As shown in [12], by setting u=s2/s1 and v=s3/s1, (1) can be transformed into a quartic equation in v as(2)A4v4+A3v3+A2v2+A1v+A0=0,where(3)A4=a2-b2-c2b22-4c2b2cos2⁡α,A3=4a2-c2b2b2+c2-a2b2cos⁡β-b2-c2-a2b2cos⁡αcos⁡γ+2c2b2cos2⁡αcos⁡β,A2=2a2-c2b22-1+2a2-c2b22·cos2⁡β+2b2-c2b2cos2⁡α-4a2+c2b2cos⁡α·cos⁡βcos⁡γ+2b2-a2b2cos2⁡γ,A1=4-a2-c2b2a2+b2-c2b2cos⁡β+2a2b2·cos2⁡γcos⁡β-b2-a2-c2b2cos⁡αcos⁡γ,A0=a2+b2-c2b22-4a2b2cos2⁡γ,(4)s12=b21+v2-2vcos⁡β.u can be determined from the following quadratic equation:(5)u2-2uvcos⁡α+b2-a2b2v2+2va2b2cos⁡β-a2b2=0.From (4), it can be seen that, given a positive root v in (2), we can always obtain a positive s1. From (5), if a positive u can be obtained, then the positive triplet (s1, s2=us1, s3=vs1) must be a positive solution of the P3P problem. Note that, given a positive root v in (2), there could be 0,1,2 positive roots of u in (5). In other words, each positive v could correspond to 0,1,2 positive solutions of the P3P problem. In [23], the authors showed that if the optical center is outside of all the 6 toroids, each positive root must correspond to a unique positive solution of the P3P problem. In the next section, we show that when the optical center is close to one of the 3 toroids in Section 2.2, the corresponding P3P problem must have at least two different positive solutions, the one whose optical center is at the original position and the other whose optical center is in a small neighborhood around one of the 3 control points. Here “two different solutions” refer to “the two solutions with the same 3 control points, but their optical centers lie at a different position.”


## 2.1. P3P Problem

As shown in Figure1, A, B, and C are the three control points with known distance: a=BC, b=AC, and c=AB; O is the camera optical center. Since the camera (under the pinhole model) is calibrated, the three subtended angles α, β, and γ of the projection rays can be considered as known entities and then, by the Law of Cosines, the following 3 basic constraints on the three unknowns s1=OA, s2=OB, and s3=OC in (1) must hold: (1)s12+s22-2cos⁡γs1s2=c2,s12+s32-2cos⁡βs1s3=b2,s22+s32-2cos⁡αs2s3=a2.Hence, the P3P problem means to determine such positive triplets (s1,s2,s3) satisfying all the 3 basic constraints in (1). And the multisolution phenomenon refers to the existence of multiple such positive triplets (s1,s2,s3) all satisfying the 3 constraints in (1).Figure 1
P3P problem definition:A, B, and C are the 3 control points and O is the camera optical center.


## 2.2. The 3 Toroids

As shown in Figure1, by rotating the circumcircle of the triangle ABC around one of its three sides by 2π separately, 3 pairs of toroids (or 6 toroids) can be generated [24] as shown in Figure 2. For each toroid pair, one is generated by rotating the arc with the subtended angle ∠ABC (or ∠BAC, or ∠ACB) and the other with its supplement angle (π-∠ABC) (or (π-∠BAC), or (π-∠ACB)). In this work, the 3 toroids refer to the 3 ones generated only with the subtended angle ∠ABC, ∠BAC, and ∠ACB, denoted by Toroid_AC, Toroid_BC, and Toroid_AB, respectively. Hence, when the optical center lies on Toroid_AC (or Toroid_BC, or Toroid_AB), the subtended angle β (or α, or γ) of the two projection rays (OA,OC) (or (OB,OC), or (OA,OB)), by definition, always has β=∠ABC (or α=∠BAC, or γ=∠ACB).Figure 2
(a) A single toroid; (b) three toroids.
(a)
(b)


## 2.3. Grunert’s Derivation

As shown in [12], by setting u=s2/s1 and v=s3/s1, (1) can be transformed into a quartic equation in v as(2)A4v4+A3v3+A2v2+A1v+A0=0,where(3)A4=a2-b2-c2b22-4c2b2cos2⁡α,A3=4a2-c2b2b2+c2-a2b2cos⁡β-b2-c2-a2b2cos⁡αcos⁡γ+2c2b2cos2⁡αcos⁡β,A2=2a2-c2b22-1+2a2-c2b22·cos2⁡β+2b2-c2b2cos2⁡α-4a2+c2b2cos⁡α·cos⁡βcos⁡γ+2b2-a2b2cos2⁡γ,A1=4-a2-c2b2a2+b2-c2b2cos⁡β+2a2b2·cos2⁡γcos⁡β-b2-a2-c2b2cos⁡αcos⁡γ,A0=a2+b2-c2b22-4a2b2cos2⁡γ,(4)s12=b21+v2-2vcos⁡β.u can be determined from the following quadratic equation:(5)u2-2uvcos⁡α+b2-a2b2v2+2va2b2cos⁡β-a2b2=0.From (4), it can be seen that, given a positive root v in (2), we can always obtain a positive s1. From (5), if a positive u can be obtained, then the positive triplet (s1, s2=us1, s3=vs1) must be a positive solution of the P3P problem. Note that, given a positive root v in (2), there could be 0,1,2 positive roots of u in (5). In other words, each positive v could correspond to 0,1,2 positive solutions of the P3P problem. In [23], the authors showed that if the optical center is outside of all the 6 toroids, each positive root must correspond to a unique positive solution of the P3P problem. In the next section, we show that when the optical center is close to one of the 3 toroids in Section 2.2, the corresponding P3P problem must have at least two different positive solutions, the one whose optical center is at the original position and the other whose optical center is in a small neighborhood around one of the 3 control points. Here “two different solutions” refer to “the two solutions with the same 3 control points, but their optical centers lie at a different position.”


## 3. Solution Singularity in P3P Problem

We have the following main result.Proposition 1.
As shown in Figures1 and 2, if the optical center O is close to Toroid_AB, then except for some special curves, there is always another optical center O′ in a small neighborhood of control point C such that {O′,(A,B,C)} is another positive solution of the P3P problem in addition to its original solution {O,(A,B,C)}.Proof.
If the optical centerO lies on the Toroid_AB, γ=∠ACB. Hence, A0=0, and v=0 is a root of the quartic equation in (2).
Suppose the optical centerO is not on the Toroid_AB, but very close to it; then the three subtended angles from O to the three control points A, B, and C are as follows: α, β, γ=∠ACB+Δγ, where Δγ is quite small since O is very close to Toroid_AB. In fact, Δγ could be infinitesimally approaching 0 if the optical center is infinitesimally close to Toroid_AB.
SinceΔγ is very small, all the 5 coefficients Ai,i=0,1,2,3,4, can be approximated by its linear term at α, β, γ=∠ACB. In other words, we can keepα, β unchanged, but onlyγ is subject to a small change by Δγat γ=∠ACB.
Whenγ=∠ACB, v=0 is a root of the quartic equation in (2). When γ=∠ACB+Δγ, there should be a root Δv of the linearized equation of (2) at α, β, γ=∠ACB. Since (2) is a quartic equation, we need only to consider the last two terms: that is,(6)A1+ΔA1Δv+A0+ΔA0=0.If A1≠0 when γ=∠ACB, and since A0=0 when γ=∠ACB, then if ΔA0≠0, we have(7)Δv=-ΔA0A1≠0.Let us consider the condition of A1=0 and that of ΔA0=0 when γ=∠ACB.
Whenγ=∠ACB, if A1=0, we have(8)-a2-c2b2a2+b2-c2b2cos⁡β+2a2b2cos2⁡∠ACB·cos⁡β-b2-a2-c2b2cos⁡αcos⁡∠ACB=0.Since cos⁡∠ACB=a2+b2-c2/2ab, substituting it into the above equation and by some manipulations, the above equation can be simplified as(9)cos⁡∠ACBcos⁡βcos⁡∠BAC+cos⁡αcos⁡∠ABC=0.cos⁡∠ACB=0 means ∠ACB=π/2, or the control point triangle is a right triangle. In this case, the Toroid_AB degenerates into a sphere.
If∠ACB≠π/2, A1=0 indicates that the 3 subtended angles (α, β, γ=∠ACB+Δγ) of the optical center O with the three control points A, B, and C must satisfy the following relation: (10)cos⁡∠BACcos⁡α=-cos⁡∠ABCcos⁡β.Since ΔA0 can be expressed as(11)ΔA0=4a2b2sin⁡2∠ACBΔγ,then if ∠ACB≠π/2, ΔA0≠0.
In conclusion, if∠ACB≠π/2, and if cos⁡∠BAC/cos⁡α≠-cos⁡∠ABC/cos⁡β, Δv=-ΔA0/A1 always exists, and we can always make Δv=-ΔA0/A1>0 by choosing either Δγ>0 or Δγ<0. Geometrically, Δγ>0 means the optical center O is inside of Toroid_AB, and Δγ<0 means the optical center O is outside of Toroid_AB.
SinceΔv→0 when Δγ→0, from (5), u≈a/b. From Δv>0, u≈a/b>0, a positive triplet (s1,s2,s3) can be obtained, which must be another solution of the P3P problem. Since Δv is small, s3=Δv×s1=Δvb2/1+Δv2-2Δvcos⁡β≈bΔv=-(4a2/bsin⁡2∠ACB/A1)Δγ. Hence, when Δγ→0, s3→0, it indicates that the corresponding optical center O′ of this additional solution must be close to the control point C. In other words, O′ is in a close neighborhood of control point C. Hence, the proposition is proved.Remark 2.
When the optical centerO is close to Toroid_AC (or Toroid_BC), by setting the variables v=s2/s3, u=s1/s3 (or v=s1/s2, u=s3/s2), we can similarly prove that there exists additionally a positive solution whose corresponding optical center O′ lies in a close neighborhood of control point B (or A).Remark 3.
WhenΔABC is a right angle, say ∠ACB=π/2, Toroid_AB becomes a sphere, and this is quite a special case. As shown by Zhang and Hu [18] and Sun and Wang [20], the pair of side-sharing solutions degenerates into a double solution in this case.Remark 4.
In fact, “the closeness of neighborhood” in the above discussions can be explicitly quantified ass3≈-4a2sin⁡(2∠ACB)/A1bΔγ, or a linear relationship between s3 (the neighborhood size) and Δγ (the closeness magnitude of the optical center O to the toroid).Remark 5.
From the above discussion, we can see that if the optical center is close to one of the 3 toroids (inside or outside of the toroid), except for some special curves, there is always a P3P positive solution whose optical center is in a close neighborhood of one of the three control points. This indicates that the 3 control points are singular points of the optical centers distribution of the P3P solutions.


## 4. Computer Simulation

Although the correctness of our proposition lies in its proof, we nevertheless also verify it by computer simulations. Our simulation procedure is as follows.Generate 3 noncollinear control pointsA, B, and C.Repeat (1)–(4).(1)
Choose at random an optical centerO close to one of the 3 toroids.(2)
From{O,(A,B,C)}, compute the three quadratic constraints in (1) and then transform them into a quartic equation in (2).(3)
Compute the roots of (2) to determine a small root Δv.(4)
Compute the P3P solution corresponding toΔv as shown in Section 3.We generate about 10,000 triplets of control points, and for each triplet, about 10,000 different optical centers are simulated. All the simulations confirm our general theoretical conclusion; that is, the optical centers of all the additional P3P solutions are in a close neighborhood of control points. Figure3 is an example of the resulting optical center distributions around the control point A (for the visualization clarity purpose, only 100 points are shown). In Figure 3(a), the blue points are the optical centers near the Toroid_BC, the green point is the control point B, the pink point is the control point C, and the red points are the optical centers of those additional corresponding P3P solutions, which are all near the control point A. Figure 3(b) is the enlarged part near the control point A, and it shows that these optical centers are in a small neighborhood of A. Each blue point in Figure 3(a) has a corresponding red point in Figure 3(b). In other words, a blue point and the 3 control points constitute a P3P problem whose optical center (the blue point) is close to Toroid_BC, and this P3P problem has another solution (the corresponding red point and the 3 control points) whose optical center (the red point) is close to the control point A.Figure 3
An example of the resulting optical center distributions around the control pointA.
(a)
(b)


## 5. Conclusion

In this work, we find that, given 3 control points, if the camera optical center is close to any one of the 3 toroids, except for some special curves, there is always an additional positive solution for this P3P problem whose corresponding optical center always lies in a close neighborhood of one of the 3 control points. Hence, the 3 control points are singular points of the optical centers distribution of the P3P solutions. In other words, some singularity exists around the 3 control points for the P3P problem solutions.Our result provides some new insights into the nature of multisolution phenomenon; in addition to its academic value, the result could also provide some theoretical guidance for P3P practitioners to properly arrange their control points to avoid unstable solutions for the P3P based applications.



---

*Source: 147397-2015-06-28.xml*