Abstract
This paper presents the first optimal, maximum likelihood solution to the triangulation problem for radially distorted cameras. The proposed solution to the two-view triangulation problem minimizes the $L_2$-norm of the reprojection error in the distorted image space. We cast the problem as the search for corrected distorted image points, and we use a Lagrange multiplier formulation to impose the epipolar constraint for undistorted points. For the one-parameter division model, this formulation leads to a system of five quartic polynomial equations in five unknowns, which can be exactly solved using the Groebner basis method. While the proposed Groebner basis solution is provably optimal; it is too slow for practical applications. Therefore, we developed a fast iterative solver to this problem. Extensive empirical tests show that the iterative algorithm delivers the optimal solution virtually every time, thus making it an $L_2$-optimal algorithm de facto. It is iterative in nature, yet in practice, it converges in no more than five iterations. We thoroughly evaluate the proposed method on both synthetic and real-world data, and we show the benefits of performing the triangulation in the distorted space in the presence of radial distortion.
Introduction
Triangulation—the process of determining a 3D point's location from its 2D projections in two or more images—is a cornerstone of computer vision. Traditionally, researchers rely on the "pinhole camera model," which assumes light travels in perfectly straight lines. However, most modern consumer cameras, such as those in smartphones or action cameras, suffer from significant radial distortion, where straight lines appear curved.
The standard "naive" approach is to first undistort the images and then perform triangulation. While simple, this is mathematically sub-optimal. Noise in digital images occurs in the distorted space (the actual pixels captured by the sensor). By undistorting first, the noise distribution is warped, meaning a standard triangulation on the "clean" images no longer provides the most likely 3D position. This paper tackles the challenge of performing triangulation while accounting for distortion directly in the optimization loop to achieve a Maximum Likelihood Estimate (MLE).
Methodology
The authors formulate triangulation as a constrained optimization problem: find the 3D point that minimizes the distance to the measured (noisy) points in the original distorted images, subject to the epipolar constraint.
The Division Model
They utilize the "one-parameter division model" to represent radial distortion: $$x = \frac{x_d}{1 + \lambda r_d^2}$$ This model is popular because it is expressive yet mathematically well-behaved for polynomial solvers, allowing the geometric constraints to be expressed as a system of equations.
Solvers: GBD and ITD
By applying Lagrange multipliers, the problem is transformed into a system of five quartic (degree-4) polynomial equations. Two solvers are proposed:
- GBD (Gröbner Basis Solver): An exact algebraic solver that finds all possible solutions. While provably optimal, it involves heavy matrix calculations (408x428) and is too slow for real-time use.
- ITD (Iterative Radial Distortion Triangulation): A fast iterative algorithm inspired by Lindstrom’s method for pinhole cameras. It solves a simple univariate quartic at each step and typically converges in just 3 to 5 iterations.
The Distorted Space Advantage
The core insight of this work is that minimizing error in the distorted image space is the only way to achieve an MLE when assuming Gaussian noise on pixel measurements.
As illustrated in the figure above, the proposed method maintains the integrity of the error model in the original image space. The benefits are most pronounced for points near the edges of the image. In wide-angle lenses, distortion is strongest at the borders; the "naive" method's error increases significantly here, whereas the proposed method remains robust by correctly modeling the noise distribution.
Experimental Results
The method was evaluated using synthetic data (2,000 random 3D points) and real-world data captured with a GoPro Hero4.
- Accuracy: On synthetic data with 5% distortion error, the ITD method reduced 3D error by a factor of over 1.6x compared to state-of-the-art pinhole triangulation for points near the image borders.
- Speed: The Newton-based version of the ITD solver is incredibly efficient, taking only 141 nanoseconds per point. This allows for the triangulation of roughly 7.1 million points per second, making it suitable for real-time applications like SLAM or 3D reconstruction.
- Convergence: In practice, the iterative solver almost always reaches the global optimum, even in the presence of high noise (up to 20px), effectively serving as a de facto optimal algorithm.
Conclusion
This paper introduces the first optimal, maximum-likelihood solution for triangulation in cameras with radial distortion. By providing a fast iterative algorithm that outperforms standard "undistort-then-triangulate" pipelines, the authors enable more accurate 3D reconstruction for modern wide-angle imaging systems. Future work may extend these iterative techniques to multi-view scenarios and more complex distortion models.
Summary updated