Abstract
For decades, it has been widely accepted that the gold standard for two-view triangulation is to minimize the cost based on reprojection errors. In this work, we challenge this idea. We propose a novel alternative to the classic midpoint method that leads to significantly lower 2D errors and parallax errors. It provides a numerically stable closed-form solution based solely on a pair of backprojected rays. Since our solution is rotationally invariant, it can also be applied for fisheye and omnidirectional cameras. We show that for small parallax angles, our method outperforms the state-of-the-art in terms of combined 2D, 3D and parallax accuracy, while achieving comparable speed.
Introduction
Locating the 3D point given its projections in multiple views is called triangulation. This classic yet fundamental problem in computer vision has immediate relevance to many applications, including visual odometry [8] , simultaneous localization and mapping (SLAM) [23] and structure-from-motion (SfM) [28] . As such, achieving fast and accurate triangulation has been a goal of many research endeavors in the past decades.
Introduction
For two views of known calibration and pose, the problem could be solved ideally if one finds the intersection of two backprojected rays corresponding to the same point. However, the two rays are most likely skew due to noisy measurements and inaccurate camera model. Since it is not obvious how to estimate the 3D position of the point from two skew rays, different methods have been proposed. Mainly, they can be classified into three types: (1) midpoint methods [3, 4, 30] that find the (weighted) midpoint of the common perpendicular between the two rays, (2) linear least squares methods [15] , and (3) optimal methods that "minimally" correct the two rays to make them intersect [15, 16, 19] . Note that all these three types of methods produce solutions that minimize some cost function; the (weighted) midpoint minimizes the (weighted) sum of squared distances to each ray, linear least squares methods minimize the algebraic errors, and optimal methods minimize a cost function based on either image reprojection errors [15, 16, 20] or angular reprojection errors [19, 26] . The most common cost functions are the L 1 norm (sum of magnitude), L 2 norm (sum of squares) and L ∞ norm (maximum) of the reprojection errors.
Introduction
In this work, we suggest a different approach. Instead of minimizing geometric or algebraic errors, we find a midpoint between a certain pair of points on each ray. Like the classic midpoint method, our method takes the two rays as input. Therefore, it is invariant to changes of camera rotation and applicable for perspective, fisheye and omnidirectional cameras. Unlike the classic method, however, the two points on each ray are not necessarily on the common perpendicular. We will see that our midpoint method bears a striking similarity to the classic c 2019. The copyright of this document resides with its authors. It may be distributed unchanged freely in print or electronic forms. method in the formulation, and yet it offers a significant performance gain in 2D and parallax accuracy. Compared to the optimal methods, our method yields much lower 3D errors at low parallax and similar 2D errors to those of L 2 and L ∞ optimal methods. This motivates the question: In two-view triangulation, why optimize if there is a better way?
Introduction
The main contributions of this paper are the following:
Introduction
• We propose a novel method belonging to a group called the generalized weighted midpoint (GWM) method. We show that our method outperforms existing ones (including the classic midpoint method and the state-of-the-art optimal methods) in terms of combined 2D, 3D and parallax accuracy. • Additionally, we propose a test of the adequacy (similar to the cheirality check) that identifies unreliable results and a weighting scheme that enhances 2D accuracy. • We perform an extensive evaluation and analysis of various methods, revealing an intricate link between 3D accuracy and parallax estimation. This will provide an intuitive explanation of why our midpoint method performs better than the others.
Related Work
One of the earliest works that addressed the two-view triangulation problem is [21] where the depth of a 3D point is estimated using simple algebra. For robustness, later works mostly adopted geometric approaches, such as the midpoint method [3, 4] and the minimization of the epipolar distance [9, 10] or reprojection error [14] . Among those, the last approach has become the de facto standard in computer vision [13] .
Related Work
Optimal methods refer to those triangulation methods that minimize the cost based on reprojection errors. Assuming that the image measurements are independently perturbed by the noise in the same distribution of certain types, the optimal methods find the maximum likelihood (ML) solution. For Gaussian and Laplacian distribution, the ML solution is to minimize the L 2 norm or L 1 norm of the reprojection errors, respectively [18] . This can be found in closed form by solving a polynomial of degree six or eight [15] . Alternatively, the L 2 solution can be obtained using iterative correction methods [16, 20] . While these iterative methods do not guarantee global optimality, they were shown to be faster and more stable. For a uniform distribution, minimizing the L ∞ norm leads to the ML estimate for the lower bound of the noise [11] , and the solution is obtained by solving a quartic polynomial [24] . Unlike the L 1 and L 2 cost, the L ∞ cost has a simple shape with a single minimum, but it is relatively more sensitive to noise and outliers [12] .
Related Work
These optimal methods assume that the image measurement errors follow certain distributions. However, this assumption is neither justified nor likely [11] . An equally (if not more) justified alternative is to assume that the noise model applies to the bearing measurements instead of the image. For fisheye or omnidirectional cameras, the angular reprojection errors are more suitable than the image reprojection errors [22, 26] . Also, formulating the triangulation problem in terms of angular errors leads to much simpler ML solutions [19, 26] .
Related Work
Although the existing optimal methods can provide relatively good 3D results in many cases [15, 19] , none of them are theoretically optimal in terms of 3D errors. In fact, the discrepancy between 2D optimality and 3D accuracy has already been reported by Hartley and Sturm [15] . They found that in Euclidean reconstruction, the midpoint and the linear least squares method achieve higher 3D accuracy than the L 1 or L 2 optimal methods, despite consistently (and sometimes significantly) larger 2D errors. In this work, we provide additional insights on this matter. Furthermore, we show that a simple modification to the midpoint method can substantially reduce the 2D errors while maintaining 3D accuracy. After the triangulation, one can estimate the parallax (β ) from the corrected rays.
Preliminaries
Throughout the paper, we use bold letters for vectors and matrices, and light letters for scalars. The Euclidean norm of a vector v is denoted by v , and the unit vector by v = v/ v . The angle between two lines L 0 and L 1 is denoted by ∠ (L 0 , L 1 ) ∈ [0, π/2]. Consider a 3D point observed by two cameras C 0 and C 1 . We define x 0 = [x 0 , y 0 , z 0 ] and x 1 = [x 1 , y 1 , z 1 ] as the unknown 3D coordinates of the point in the camera reference frame C 0 and C 1 , respectively. Let R and t be the known rotation and translation between the two cameras, such that x 1 = Rx 0 + t. Assuming that the camera calibration matrix K is known, the normalized image coordinates f 0 = [x 0 /z 0 , y 0 /z 0 , 1] and f 1 = [x 1 /z 1 , y 1 /z 1 , 1] can be obtained by f 0 = K −1 u 0 and f 1 = K −1 u 1 , where u 0 = (u 0 , v 0 , 1) and u 1 = (u 1 , v 1 , 1) are the homogeneous pixel coordinates of the point observation in each frame.
Preliminaries
In the ideal situation ( Fig. 1a ), the two backprojected rays intersect, satisfying the epipolar constraint [21] , i.e., f 1 · (t × Rf 0 ) = 0. Then, the intersection is given by x 1 = λ 0 R f 0 + t or x 1 = λ 1 f 1 for some scalar depth λ 0 and λ 1 . However, this rarely happens due to inaccuracies in the image measurements and the camera model. Inferring a 3D point from two skew rays requires a nontrivial method.
Preliminaries
Once the estimate of the 3D point (x 1 ) is obtained using some triangulation method, its accuracy can be evaluated in several ways. One way is to compute the 3D error, i.e., e 3D = x 1 − x true . Another way is to compute the 2D error (aka the reprojection error), i.e.,
Preliminaries
These two errors are illustrated in Fig. 1b . Note that the 2D error represents the deviation from the measurement, whereas the 3D error represents the deviation from the ground truth. Also, unlike the 3D error, the 2D error of a 3D point can be evaluated in different norms, e.g.,
Preliminaries
). Besides 2D and 3D accuracy, we can also evaluate the accuracy of the resulting parallax angle (see Fig. 1c ). The parallax error is defined as follows:
Preliminaries
We define the "raw parallax" as the angle between the original backprojected rays:
Preliminaries
This gives a rough estimate of the parallax angle independently of the translation and the triangulation method. A GWM method consists of three steps: (1) Given two backprojected rays corresponding to the same point, estimate the depth along each ray (λ 0 , λ 1 ) using some method.
Preliminaries
(2) Compute the 3D point on each ray at depth λ 0 and λ 1 , i.e., t + λ 0 R f 0 and
Preliminaries
Obtain the final estimate of the 3D point by computing their weighted average. The classic midpoint method [3, 4, 15] is one such type of method where the two points on each ray are the closest pair of points with the equal weight. Fig. 2 shows another possible example of the generalized weighted midpoint.
Alternative Midpoint Method
We propose an alternative midpoint method that belongs to the generalized weighted midpoint method. First, consider the case where the two backprojected rays happen to intersect (see Fig.  1a ). In this case, the most sensible solution is the point of intersection, and the corresponding depths along the rays can be obtained using the sine rule:
Alternative Midpoint Method
We use this formula to estimate the depths even when the two rays are skew. Computing the 3D points on each ray at depth λ 0 and λ 1 , respectively, we get
Alternative Midpoint Method
Taking the midpoint between these two points leads to
Alternative Midpoint Method
Note that letting p = R f 0 × f 1 , q = R f 0 × t and r = f 1 × t allows us to write (4) as
Alternative Midpoint Method
Interestingly, these are in a similar form to the depths given by the classic midpoint method 1 : Figure 3 : (a) A scenario where the classic midpoint method gives negative depths. The cheirality check will identify and remove this point. (b) In the same situation, our midpoint method will give positive depths. The triangulation result satisfies the cheirality constraint, but it is most likely inaccurate. (c) For unweighted midpoint methods, the frame with a smaller depth tends to get a larger reprojection error. In this example, λ 1 < λ 0 and
Alternative Midpoint Method
The difference is in the numerator; (7) has the magnitude of r and q, whereas (8) has their projection onto p. As a result, we always get λ 0 ≥ λ mid0 and λ 1 ≥ λ mid1 . In most cases, this means that our midpoint will be located farther than the classic midpoint. Fig. 2 depicts one such example. When we estimate that a point is located farther away from the cameras, it usually results in a lower estimate of the parallax angle, as will be shown in Section 5.
Cheirality and Test of Adequacy
We say that the cheirality constraint [13] is violated when a triangulated point has negative depth(s). This can happen for many reasons, such as spurious data association or the noise in the image point near the epipole. Normally, it does not pose a serious problem because we can easily check the cheirality for each point and discard the bad ones. For the classic midpoint method, this can be done by checking the signs of the depths given by (8) . For our midpoint method, however, this is not possible because the depths given by (7) are always positive. Fig  3a and 3b illustrate the difference between the two methods. In our method, the depths alone cannot tell us whether or not the triangulation result is reliable. Therefore, we use a different method to test the adequacy; we discard the point correspondence if changing the sign of at least one depth to negative leads to a smaller distance between the two points on each ray, i.e.,
Cheirality and Test of Adequacy
For the classic midpoint method, letting λ 0 = |λ mid0 | and λ 1 = |λ mid1 | gives effectively the same result as the cheirality check. For example, (9) holds in Fig 3a because the two points are closest when λ 0 = −|λ mid0 | and λ 1 = −|λ mid1 |.
Inverse Depth Weighted Midpoint
The unweighted midpoint given by (6) often entails disproportionate reprojection errors in the two images. Fig. 3c shows an example. Notice that the ray with a smaller depth tends to yield a larger reprojection error. To compensate this imbalance, we propose to use the inverse depth [6] as a weight: Mid2 performs much better than those two, and wMid2 performs consistently better than Mid2. Expectedly, optimal methods perform best in their respective error criterion. However, the differences among them are smaller in L 1 norm than in the other two norms. Parallax results (bottom row): LinLS and Mid perform worst, and the rest almost equally. Looking at the under-and overestimation of the parallax separately, we notice that the low accuracy of LinLS and Mid is caused by their bias to overestimate the parallax on average.
Evaluation Results
We evaluate the following methods: Lee and Civera's L 1 , L 2 and L ∞ optimal angular methods ('L 1 ang', 'L 2 ang', 'L ∞ ang') [19] , Hartley and Sturm's L 1 and L 2 optimal methods ('L 1 img', 'L 2 img') and linear methods ('DLT', 'LinLS') [13, 15] , Lindstrom's L 2 method with five iterations ('L 2 img (5 it.)') [20] , Níster's L ∞ method ('L ∞ img') [24] , the classic midpoint method ('Mid') [3, 4, 15] , and our method without and with the weighting ('Mid2', 'wMid2'). The evaluation was performed on synthetic datasets generated as follows: A set of 8 × 8 point clouds of 5,000 points each are generated with a Gaussian radial distribution N (0, (d/4) 2 ) where d is the distance from the world origin. Each point cloud is centered at [0, 0, d] for d = 2 n with n = −1, 0, ..., +6, and their image projections are perturbed by Gaussian noise N (0, σ 2 ) for σ = 1, 2..., 8. The size and the focal length of the images are 1, 024 2 pixels and 512 pixel, respectively. We have four configurations for the camera poses: (1) 'orbital' -two cameras at [±0.5, 0, 0] pointing at the point cloud center, (2) 'lateral' -two cameras at [±0.5, 0, 0] pointing at [0, 0, ∞] , (3) 'forward' -two cameras at [0, 0, ±0.5] pointing at the point cloud center, and (4) 'diagonal' -two cameras at ±[ √ 3/6, √ 3/6, √ 3/6] pointing at [0, 0, ∞] . The poses are slightly perturbed with uniform noise U(0, 0.01). In total, the datasets provide over a million unique triangulation problems. 2D results for small parallax (mid 1 st -3 rd column): LinLS and Mid perform significantly worse than the rest in all norms. Aside from those two, L 1 methods perform much worse than the rest in L 2 and L ∞ norm, yet best in L 1 norm. The remaining methods perform similarly. 2D results for large parallax (bottom 1 st -3 rd column): In all norms, LinLS, Mid, Mid2 and DLT perform consistently worse than wMid2, L 2 and L ∞ methods. The latter perform similarly and much better than L 1 methods in L 2 and L ∞ norm, yet worse in L 1 norm. Parallax results (last column): For low-parallax points, LinLS and Mid perform worst (see Fig. 6 for more details). For high-parallax points, all methods perform equally well.
Evaluation Results
We aggregate the results in Fig. 4 and 5 . Our observations agree with [15] in that:
Evaluation Results
1. Generally, greater noise and lower parallax lead to larger 3D errors. All methods yield almost equally low 3D errors for high-parallax points (> 4 deg). 2. 2D and 3D errors are not well correlated. For example, LinLS and Mid perform best in 3D, but worst in 2D. Additionally, we report the following findings:
Evaluation Results
1. It is difficult to tell which method is the best in terms of 2D accuracy. For example, L 1 methods yield the lowest 2D errors in L 1 norm, but relatively larger errors in L 2 and L ∞ norm. It is not obvious which norm is more important. That said, some methods can still perform consistently better than others; wMid2, L 2 and L ∞ methods consistently outperform LinLS, Mid, Mid2 and DLT in all 2D error criteria. 2. As shown in Fig. 6 , LinLS and Mid are clearly more biased to overestimate the small parallax angles (< 4 deg). This explains their relatively low 3D errors at low parallax. Fig. 7 illustrates a simplified example of this effect. 3. Our methods (Mid2 and wMid2) achieve the best overall accuracy in 3D + parallax. Top: In this 2D example, the distance is proportional to cot (β /2). Bottom: Relative impact is defined as | f (β )/g(β )| where f (β ) and g(β ) are the distance errors when the parallax is under-and overestimated by 0.5 deg, respectively. Underestimating the parallax angle yields a larger distance error than overestimating it by the same degree, and especially more so for smaller parallax.
Evaluation Results
The last finding can be solely attributed to the low-parallax points, for which our methods show similar 3D accuracy to that of Mid, but much better parallax accuracy. The latter can be explained by the fact that Mid2 always yields larger depths than Mid (as discussed in Section 4.2), which in effect lowers the estimated parallax angle on average (as shown in Fig. 6 ). Since Mid tends to overestimate small parallax angles, this works to our advantage at low parallax.
Evaluation Results
The first plot in Fig. 6 shows that Mid, LinLS and our two methods underestimate small parallax angles slightly less than the rest. It is no coincidence that precisely these four methods achieve the best 3D accuracy; Fig. 7 suggests that underestimating a small parallax angle has a severe impact on 3D accuracy. At low parallax, it seems that our methods hit the sweet spot by (1) underestimating less than the optimal methods and DLT (thus achieving lower 3D errors) and (2) overestimating less than Mid and LinLS (thus achieving lower parallax errors). We suspect that some of the large 2D errors of Mid and LinLS at low parallax are related to their large parallax overestimation (see the second row of Fig. 5 ). Large reprojection errors mean that the rays were corrected by a large amount, and pivoting two almost parallel rays (i.e., rays that correspond to a low-parallax point) will most likely increase the angle between them. This link between the 2D and the parallax error could partially explain why our methods yield smaller 2D errors than Mid and LinLS for low-parallax points.
Evaluation Results
We also found that the 2D errors of wMid2 resemble those of L ∞ methods (see the bottom row of Fig. 5 ). Note that the L ∞ optimal solutions yield the equal reprojection errors in the two views [19, 24] . This suggests that our inverse depth weighting (Section 4.4) not only reduces the overall 2D errors, but also balances the reprojection errors in the two images. Fig. 8 compares the speed of each method. We included the test of the adequacy (Section 4.3) in both our methods. All methods were implemented in C++ using the Eigen library [1] , compiled using GCC [2] with -O3 level optimization, and run on a laptop CPU (Intel i7-4810MQ, 2.8 GHz). Although wMid2 is almost two times slower than Mid2 and three times than Mid, it is still at least ten times faster than the state-of-the-art method [20] . Notice that even though (7) and (8) are similar, Mid is still almost twice faster than Mid2. This happens for two reasons: First, we avoid computing the square root in (8) by multiplying the numerator and denominator by p and get λ mid0 = p r p p and λ mid1 = p q p p . Second, the test of adequacy described in Section 4.3 takes longer than the standard cheirality check. Nevertheless, given that the computational cost of triangulation is relatively small compared to other operations (e.g., point matching, pose estimation and structure refinement) [15] , our methods provide an excellent trade-off between speed and accuracy.
Discussions

On Optimality
A reasonable doubt is that the proposed (weighted) midpoint method may be in fact optimal in some error criterion. If we consider algebraic errors, it is obvious that our midpoint minimizes
On Optimality
is the vector-valued function given by the right-hand side of (6) or (10) . However, there are infinitely many other error functions for which the global minimum is g(R, t, f 0 , f 1 ), and it is hard to tell which one is geometrically meaningful (at least, we could not find it or disprove its existence).
On Optimality
Another reasonable doubt is that, among the GWM methods, there could be a better one than ours, since we have not proved the optimality of the proposed weighted midpoint. A more fundamental question is then: What accuracy measure should we choose to define the optimality, knowing that there is a discrepancy between different types of errors, e.g., image/angular reprojection errors in different norms, 3D and parallax errors? At least for our method, it seems that the weighting affects mostly the 2D errors, so there might be a certain weighting scheme that guarantees 2D optimality without compromising 3D and parallax accuracy. A more elaborate error analysis and the comparison of different weightings within the GWM framework remain for future work. For more discussion of the optimality in geometric vision, we refer to [11] and Appendix 3 of [13].
On Practical Implications
In many SfM pipelines, two-view triangulation is used to initialize the 3D map points prior to the bundle adjustment [25, 28, 29] . Since the points with small parallax angles are associated with large 3D uncertainty, they are usually discarded. This strategy is viable if there are enough correspondences with large parallax angles. However, it is not ideal, as (1) low-parallax points can be useful for camera orientation estimation [5, 27] and (2) if the goal itself is to reconstruct the scene with large depths compared to the baseline. For problems such as reconstruction from small-baseline (or accidental) motions [7, 31] , small parallax angles are quite common, so our method could be relevant. Extending our method to multiple views for reconstructing low-parallax scenes would be an interesting future direction.
Conclusions
Triangulation from two views with known calibration and pose is an age-old problem in computer vision. Existing methods formulate the problem as the minimization of some cost function, most commonly reprojection errors. In this paper, we asked ourselves if this is really the best approach. To this end, we proposed a novel variant of the classic midpoint method that does not minimize geometric or algebraic errors.
Conclusions
We found that all the existing methods we evaluated perform poorly at low parallax, producing large errors in either 2D, 3D or parallax. On the other hand, our midpoint method achieves very good overall accuracy. We also showed that incorporating the inverse depth weighting can further reduce the 2D errors. Although our method is not theoretically optimal, it provides, with speed and simplicity, a superior balance of 2D, 3D and parallax accuracy in practice.
Conclusions
In doing so, we will use the following properties of the dot product and the cross product operations:
Conclusions
Next, we introduce the following lemma: 
Conclusions
and
Conclusions
Proof. In geometry, it is a well-known fact that the closest pair of points on two skew lines lie on the common perpendicular to both lines. In other words, the vector r 0 − r 1 is perpendicular to both L 0 and L 1 . Therefore, for some scalar τ,
Conclusions
Since point r 0 and r 1 are respectively located along L 0 and L 1 , we can write r 0 = c 0 + λ 0 m 0 and r 1 = c 1 + λ 1 m 1 .
Conclusions
for some scalar λ 0 and λ 1 . Then, (16) becomes
Conclusions
where n = m 0 × m 1 . This makes a system of three equations (in each coordinate x, y and z) with three unknowns λ 0 , λ 1 , and τ. Removing τ from the equations leads to t x + λ 0 m 0x − λ 1 m 1x n x = t y + λ 0 m 0y − λ 1 m 1y n y (19) and t y + λ 0 m 0y − λ 1 m 1y n y = t z + λ 0 m 0z − λ 1 m 1z n z .
Conclusions
Note that t = [t x ,t y ,t z ] , n = [n x , n y , n z ] , m 0 = [m 0x , m 0y , m 0z ] and m 1 = [m 1x , m 1y , m 1z ] . From (19) and (20), we get λ 0 = λ 1 (m 1x n y − m 1y n x ) + t y n x − t x n y m 0x n y − m 0y n x
Conclusions
and λ 0 = λ 1 (m 1y n z − m 1z n y ) + t z n y − t y n z m 0y n z − m 0z n y .
Conclusions
Equating the right-hand sides of (21) and (22) leads to
Conclusions
where A = (t z n y − t y n z )(m 0x n y − m 0y n x ) B = (t y n x − t x n y )(m 0y n z − m 0z n y ) C = (m 1x n y − m 1y n x )(m 0y n z − m 0z n y ) = ( m 1 × n) z ( m 0 × n) x , D = (m 1y n z − m 1z n y )(m 0x n y − m 0y n x ) = ( m 1 × n) x ( m 0 × n) z .
We can rearrange A − B into
A − B = n y t ·   m 0y n z − m 0z n y m 0z n x − m 0x n z m 0x n y − m 0y n x   .
We can rearrange A − B into
The latter term in the dot product of (24) is equal to m 0 × n. Thus,
We can rearrange A − B into
A − B = n y t · ( m 0 × ( m 0 × m 1 )) (11) = n y t · ( m 0 ( m 0 · m 1 ) − m 1 ) = n y (( m 0 · m 1 ) ( m 0 · t) − m 1 · t) (12) = −n y ( m 0 × m 1 ) · ( m 0 × t) .
We can rearrange A − B into
We can rearrange C − D into
We can rearrange A − B into
= ((n · ( m 1 × m 0 )) n) y = − m 0 × m 1 2 n y = − m 0 × m 1 2 n y .
We can rearrange A − B into
Substituting (25) and (26) into (23) gives
We can rearrange A − B into
Finally, substituting (27) into (17) leads to (15) . Equation (14) is derived analogously.
We can rearrange A − B into
By substituting Rf 0 and f 1 into m 0 and m 1 , we can use lemma 1 to obtain λ mid0 and λ mid1 in (8) .
We can rearrange A − B into
Letting p = R f 0 × f 1 , q = R f 0 × t and r = f 1 × t leads to (8) .

{'paper_id': '198968322', 'title': 'Triangulation: Why Optimize?', 's2_url': 'https://api.semanticscholar.org/CorpusID:198968322', 'source': 'S2ORC'}