A polynomial formula for the perspective four points problem

David Lehavi, Brian Osserman · 2025

Read A polynomial formula for the perspective four points problem by David Lehavi, Brian Osserman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13058.txt.

Introduction

David Lehavi and Brian Osserman solve a camera geometry problem in a paper from two thousand twenty-five. The perspective n-points problem asks where a camera is, given points in space and their images. Their fast, accurate solution tackles the four-point case with a new split of the problem.

First, they place new points along the camera rays so that distances between them match the original points as closely as possible. That step turns the problem into an absolute orientation task, which has an explicit formula solution. Their coordinates use squared distances and dot products to stay orientation-free. Tests showed an order of magnitude speed gain over top methods, at similar accuracy under noise. The split also speeds seed rejection in RANSAC.

Catalog record

CREATORDavid Lehavi, Brian Osserman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13058

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A polynomial formula for the perspective four points problem David Lehavi, Brian Osserman Abstract . We present a fast and accurate solution to the perspective n n -points problem, by way of a new approach to the n = 4 n=4 case. Our solution hinges on a novel separation of variables: given four 3D points and four corresponding 2D points on the camera canvas, we start by finding another set of 3D points, sitting on the rays connecting the camera to the 2D canvas points, so that the six pair-wise distances between these 3D points are as close as possible to the six distances between the original 3D points. This step reduces the perspective problem to an absolute orientation problem, which has a solution via explicit formula. To solve the first problem we set coordinates which are as orientation-free as possible: on the 3D points side our coordinates are the squared distances between the points. On the 2D canvas-points side our coordinates are the dot products of the points after rotating one of them to sit on the optical axis. We then derive the solution with the help of a computer algebra system. Our solution is an order of magnitude faster than state of the art algorithms, while offering similar accuracy under realistic noise. Moreover, our reduction to the absolute orientation problem runs two orders of magnitude faster than other perspective problem solvers, allowing extremely efficient seed rejection when implementing RANSAC. 1991 Mathematics Subject Classification 65D19, 68T45, 13-04, 14P10 1. Introduction The perspective n point problem (PnP) goes back to the mid 19th-century, and seeks to recover the 6DoF pose of a calibrated camera given n points in the world, and their images on a camera canvas. The problem arises as a localization problem in most computer visions problems involving both images and 3D data. Typically in these problems one starts with a large number of pairings between 2D and 3D points, where unfortunately each pairing is correct with relatively low probability; one then uses many subsets of size 3 or 4 of these pairings as the “seeds” or “RANdom SAmple” part of a RANSAC on the entire set of pairings. In this paper we propose a novel solution to the n=4 problem, which is an order of magnitude faster than previously suggested solutions, while providing accuracy close to state of the art. Moreover, our algorithm provides an accuracy measure which enables us to efficiently reject low-accuracy seeds and then unite compatible seeds before even solving for the actual pose; this part runs fully two orders of magnitude faster than existing solutions. A portion of this efficiency is due to the fact that our algorithm consists almost entirely of evaluating algebraic formulas, so it is nearly devoid of branches, which makes it extremely amenable to SIMD implementation. Our key contribution is an extremely fast algorithm which, given four marked 3D points, and four 2D points on the camera plane with corresponding markings, reduces the perspective problem to an absolute orientation problem as follows: one may first rotate the 2D canvas so that the last point would be on the camera axis, then compute the six distances between the 3D points as well as the six dot products between the 2D points, reprojected to the rotated canvas. Next one feeds these values into explicit algebraic formulas , yielding four estimated depths associated to the 2D points in the rotated system. Finally, the depths are rescaled to obtain depths relative to the original, non-rotated camera plane. This is our intermediate output, which is in effect another configuration of 3D points, and thus reduces the original perspective problem to an absolute orientation problem. This reduction step runs two orders of magnitude faster than standard algorithms. Having achieved the intermediate output, we can reject seeds having high error, and then unite low-error seeds when they yield the same set of z -depths for a common triple of points. This is all done prior to solving the absolute orientation problem (using e.g. Horn’s algorithm – see [ Ho ] ), which yields additional efficiency compared to approaches that require solving for the pose on each seed separately. Finally, we use Fletcher’s variant of the Levenberg-Marquardt gradient descent algorithm [ F ] to fine-tune the solution and minimize the reprojection error. Another benefit of uniting seeds before solving for pose is that simply by prioritizing seeds which can be united with large numbers of other seeds, our approach will often implicitly discard seeds which have very low apparent error but are in fact based on mismatched points, since these typically can’t be united with as many other seeds. The crux of why our reduction is feasible lies in the fact that we are reducing the number of parameters involved in both the problem input, and the problem output. Instead of directly representing the coordinates of each of the four input 3D points and the four 2D canvas points, which would require (3+2)\cdot 4=20 numbers, our input consists of the 12 squared distances and dot products described above. Likewise, our intermediate output consists of four depths, instead of the 4+3 numbers typically needed to represent rotation via quaternionic representation and translation. This concise representation of data enables us to obtain the aforementioned explicit algebraic formula for the output in terms of the input. We obtained this formula with the assistance of the computer algebra system Singular , which is in itself remarkable, since algebra problems arising from real-world problems and involving so many variables are usually well beyond the reach of computer algebra packages. Even with our reduced variable count, Singular was unable to solve the problem in the most direct way, and we had to use some ad hoc experimentation with different approaches in order to obtain our ultimate formulas. We emphasize however that the computer algebra system was used only in deriving our algorithm; our algorithm itself requires nothing more sophisticated than evaluating multivariate polynomials and taking square roots. 2. Related work The n=3 and n=4 cases are conceptually different: the case n=3 (which goes back to [ G ] ) admits four pairs of solutions for nondegenerate configurations. Since [ G ] various ways have been suggested to solve this case, all essentially boiling down to how to find a bi-quartic polynomial representing the solutions. In the case n>3 the perspective n points problem is overdetermined, which means that putatative solution can come with some accuracy measures which may help fast rejection - which is useful for algorithms which come before a RANSAC algorithm. Indeed, the prevalent algorithms for n>3 all come – at least internally – with such a measure. Broadly speaking, one may classify perspective n>3 points solvers along two dimensions: (1) which quantity is one trying to minimize or maximize? E.g., reprojection error, reconstruction error, error in the space of the rotations, or likelihood of the position being correct; (2) which optimization strategy is employed? E.g., finding a kernel of some matrix, least squares, or direct solution via formula. The most influential work in the problem domain is “EPnP” [ LMFP ] , which minimizes distances in the space of quaternions after algebraically eliminating the translation; the optimization strategy is finding

Read the complete text