A polynomial formula for the perspective four points problem

This paper introduces a fast and accurate polynomial solution to the perspective four-points problem by separating variables to reduce it to an absolute orientation problem, achieving significantly faster computation than state-of-the-art algorithms while maintaining comparable accuracy.

The Gist

Imagine you are a detective trying to figure out exactly where a camera was standing in a room, just by looking at a photograph of four specific objects (like a lamp, a chair, a book, and a plant) and knowing where those objects actually are in the real world.

This is the Perspective Four Points Problem. It's a classic puzzle in computer vision. The challenge is that the camera distorts the image (things look smaller if they are far away), and you don't know the distance to the objects. You have to calculate the "depth" (how far away each object is) to reconstruct the camera's position.

For decades, solving this puzzle has been like trying to untangle a giant knot of spaghetti using a pair of tweezers. It's slow, and if you have thousands of potential clues (pairs of 2D image points and 3D real-world points), you get stuck trying to solve the knot for every single possibility.

Here is the breakthrough David Levahi and Brian Osserman present in this paper:

The Old Way: The Slow, Heavy Lifter

Imagine you have a pile of 10,000 potential clues. To find the right one, the old methods (like EPnP or SQPnP) would pick four clues, try to solve the complex math puzzle for them, check if it works, and if it fails, throw them away and pick four new clues. They do this over and over. It's like trying to find a specific key in a dark room by feeling every single key on a giant ring one by one. It takes a long time.

The New Way: The "Magic Filter"

The authors found a way to turn the complex 3D puzzle into a much simpler math problem using a clever trick.

1. The "Shape-Shifting" Trick
Instead of trying to calculate the exact 3D coordinates immediately, they ask a simpler question: "If I could magically move these four 3D objects so they fit perfectly onto the lines of sight from the camera, how far apart would they be from each other?"

They realized that the distances between the objects are the most important thing. If you know the distances between four points, you know their shape (like a tetrahedron).

• The Analogy: Imagine you have a flexible wireframe of a tetrahedron. You don't need to know exactly where it is in the room; you just need to know the length of the wires.

2. The "Dot Product" Shortcut
On the camera side (the 2D photo), they do a similar thing. They rotate the photo so one point is straight ahead, and then they measure how the other points "relate" to it using simple math (dot products).

3. The "Magic Formula"
This is the real magic. The authors used a super-computer algebra system (a robot mathematician) to derive a single, explicit formula.

• The Analogy: Think of the old methods as trying to solve a maze by walking through it. The new method is like having a map that says, "If you start at point A, just walk 5 steps right and 3 steps up, and you are at the exit."
• They turned the complex 3D problem into a set of simple quadratic equations (like $x^2 + bx + c = 0$). These are the kind of equations you solve in high school algebra.

Why This Changes Everything

1. Speed: The Ferrari vs. The Bicycle
The old methods take about 25 to 36 microseconds to check one set of four points. The new method takes about 0.4 microseconds.

• The Metaphor: If the old method is a bicycle, the new method is a Formula 1 car. It is 50 to 100 times faster.
• Because it's so fast, it's almost entirely made of straight-line math (no "if-then" branching), which means it runs incredibly efficiently on modern computer chips (SIMD).

2. The "Bad Clue" Rejection
In real life, computers often match the wrong points (e.g., matching a tree in the photo to a car in the real world). This is a "bad seed."

• The Old Way: You spend a lot of time trying to solve the puzzle with the bad seed, realize it's wrong, and then move on.
• The New Way: Because the math is so fast and precise, the algorithm can instantly spot that the "distances" don't match up. It rejects the bad seed almost immediately.
• The Result: You can check thousands of bad clues in the time it used to take to check one. This makes the whole system much more robust when dealing with messy, real-world data.

3. Accuracy
Despite being incredibly fast, it is just as accurate as the best existing methods (SQPnP) for general situations. It handles tricky scenarios (like when points are in a straight line or flat on a table) much better than the competition.

The Bottom Line

The authors didn't just make a slightly better calculator; they changed the language of the problem.

• Instead of wrestling with 3D coordinates and rotations, they translated the problem into distances and simple algebra.
• They used a computer to find the "cheat code" (the explicit formula) that solves the puzzle instantly.

In everyday terms:
Imagine you are trying to find a lost hiker in a forest.

• Old Method: You send a team to every possible 4-square-mile patch of the forest, walk the whole area, and check if the hiker is there.
• New Method: You have a drone that can instantly scan the shape of the terrain from a satellite photo. It instantly tells you, "That patch of forest doesn't match the shape of the hiker's path. Ignore it." It filters out 99% of the forest in a split second, leaving you with only the few patches that actually need a ground team to investigate.

This paper gives computer vision a "super-powered filter" that makes solving 3D positioning problems faster, cheaper, and more reliable than ever before.

Technical Summary

1. Problem Statement

The paper addresses the Perspective-n-Point (PnP) problem, a fundamental challenge in computer vision and photogrammetry. The goal is to recover the 6 Degrees of Freedom (6DoF) pose (rotation and translation) of a calibrated camera given $n$ 3D world points and their corresponding 2D projections on the camera image plane.

While the problem is well-studied, the authors focus specifically on the $n=4$ case. This case is critical because it serves as the "seed" for RANSAC (Random Sample Consensus) algorithms used to solve PnP for larger $n$. In RANSAC, millions of random subsets of 4 points are tested to find the best pose. Current state-of-the-art solvers for $n=4$ are computationally expensive, creating a bottleneck in real-time applications where rapid rejection of incorrect point matches (seeds) is necessary.

2. Methodology

The authors propose a novel approach that reduces the perspective problem to an Absolute Orientation problem through a specific variable separation strategy. Unlike traditional methods that solve for rotation and translation directly or minimize reprojection error iteratively, this method relies on explicit algebraic formulas.

Key Steps of the Algorithm:

1. Coordinate Transformation (Invariant Representation):
   Instead of using raw Cartesian coordinates, the algorithm converts the input data into orientation-free invariants:

   • 3D Side: Uses the squared distances between the four 3D points ($a_i, c_i$).
   • 2D Side: Uses dot products of the 2D image points after rotating the coordinate system so one point lies on the optical axis ($b_i, d_i$).
   • This reduces the input dimensionality from 20 numbers (4 points $\times$ 5 coordinates) to 12 scalar values.

2. Derivation of Quadratic Polynomials:
   Using a Computer Algebra System (Singular), the authors derived explicit polynomial formulas. They established that the squared depths ($z_i^2$) of the 3D points relative to the camera satisfy a set of quadratic polynomials ($Q_i(x)$).

   • The coefficients of these quadratics are explicit polynomials of the input invariants ($a, b, c, d$).
   • This allows the calculation of potential depth values without iterative optimization.

3. Depth Estimation and Selection:

   • The algorithm solves the four quadratic equations to find 16 possible combinations of depth values ($z_0, z_1, z_2, z_3$).
   • It selects the correct combination by minimizing the error in the distance constraints (ensuring the reconstructed 3D distances match the original 3D distances).
   • The selected depths are then rescaled to the original camera coordinate system.

4. Pose Recovery and Refinement:

   • The estimated depths convert the 2D image points into a "pseudo-3D" configuration.
   • The problem is now reduced to Absolute Orientation (finding the rigid transformation between two sets of 3D points), which can be solved instantly using explicit formulas (e.g., Horn's method).
   • Finally, a gradient descent step (Levenberg-Marquardt) is applied to minimize the final reprojection error.

3. Key Contributions

• Explicit Algebraic Solution: The paper provides a closed-form polynomial solution for the $n=4$ PnP problem, avoiding the need for iterative solvers or matrix kernel computations during the initial seed generation.
• Variable Separation: The novel separation of variables (using squared distances and dot products) allows the reduction of a complex geometric problem into a system of solvable quadratic equations.
• Efficient Seed Rejection: The method includes a built-in accuracy measure. It can reject low-quality seeds (mismatched points) before solving for the full pose, running two orders of magnitude faster than existing methods for this specific step.
• SIMD Optimization: Because the algorithm consists almost entirely of evaluating multivariate polynomials and square roots (with no conditional branches), it is highly amenable to SIMD (Single Instruction, Multiple Data) vectorization, enabling massive parallel processing.

4. Experimental Results

The authors evaluated their algorithm against EPnP and SQPnP (the current state-of-the-art) using synthetic data with varying noise levels and geometric configurations (general, planar, and collinear).

• Computational Efficiency:

  • EPnP: ~25.77 $\mu$s per configuration.
  • SQPnP: ~36.31 $\mu$s per configuration.
  • Proposed Algorithm: 0.477 $\mu$s (standard) and 0.258 $\mu$s (with AVX2 SIMD).
  • Result: The proposed method is roughly 50x to 100x faster than competitors for the initial depth estimation step.

• Accuracy:

  • Under realistic noise, the algorithm achieves accuracy comparable to SQPnP (the gold standard for accuracy) and EPnP.
  • It demonstrates superior stability in degenerate configurations (e.g., planar points or collinear points), where other methods often fail or produce high errors.

• Robustness to Mismatches:

  • In "fast rejection" tests (where one point in a 4-tuple is intentionally mismatched), the proposed algorithm rejected 99% of bad seeds with a tight error threshold, whereas EPnP and SQPnP attempted to solve them, resulting in high rotational/translation errors.

5. Significance

This work represents a significant breakthrough in the efficiency of 3D reconstruction pipelines:

1. RANSAC Acceleration: By speeding up the $n=4$ solver by two orders of magnitude, it allows RANSAC to test significantly more random subsets in the same amount of time, increasing the probability of finding the correct pose in datasets with high outlier ratios.
2. Real-Time Viability: The extreme speed and vectorizability make this algorithm ideal for real-time applications (e.g., AR/VR, robotics, autonomous driving) where latency is critical.
3. Theoretical Insight: The paper demonstrates that complex geometric problems involving many variables can be solved via explicit algebraic formulas if the right invariant coordinates are chosen, a finding that was previously thought to be computationally intractable for such high-dimensional systems.

In summary, Levahi and Osserman have replaced a computationally heavy optimization problem with a fast, deterministic algebraic formula, fundamentally changing how the perspective 4-point problem is approached in high-performance computer vision.