A polynomial formula for the perspective four points problem

Cet article présente une solution polynomiale rapide et précise au problème de la perspective à quatre points, basée sur une nouvelle séparation des variables qui réduit le problème à une orientation absolue, offrant ainsi une accélération significative par rapport aux algorithmes existants.

L'essentiel

Imaginez que vous êtes un photographe ou un robot qui regarde le monde à travers un objectif. Vous voyez des points sur votre photo (l'image 2D), et vous savez où se trouvent ces points dans la vraie vie (les coordonnées 3D). Le grand défi, c'est de deviner : « Où est ma caméra ? » et « Comment est-elle orientée ? » par rapport à ces points. C'est ce qu'on appelle le problème « Perspective N-Points » (PnP).

Dans cet article, David Levahi et Brian Osserman proposent une nouvelle méthode pour résoudre ce casse-tête, spécifiquement quand on utilise 4 points. Leur solution est comme un tour de magie mathématique : elle est extrêmement rapide (des milliers de fois plus rapide que les méthodes actuelles) et tout aussi précise.

Voici comment ça marche, expliqué simplement avec des analogies :

1. Le Problème : Trouver l'aiguille dans la botte de foin

Imaginez que vous avez un tas de paires de points (un point sur la photo, son correspondant dans la réalité). La plupart de ces paires sont fausses (c'est du bruit, des erreurs). Pour trouver la bonne position de la caméra, vous devez utiliser un algorithme appelé RANSAC.

Le RANSAC fonctionne comme un détective qui teste des hypothèses :

1. Il prend 4 points au hasard (un « échantillon » ou « seed »).
2. Il essaie de calculer la position de la caméra avec ces 4 points.
3. Si ça marche bien, il vérifie si d'autres points correspondent.
4. Si ça ne marche pas, il rejette l'échantillon et en prend un autre.

Le problème actuel : Les méthodes actuelles (comme EPnP ou SQPnP) sont lentes pour faire l'étape 2. Elles passent beaucoup de temps à faire des calculs complexes pour chaque petit échantillon. C'est comme essayer de résoudre un Sudoku géant pour chaque hypothèse, alors que la plupart des hypothèses sont fausses.

2. La Solution : Le « Détecteur de Faux Amis » ultra-rapide

Les auteurs ont inventé une nouvelle façon de voir les choses. Au lieu de calculer directement la position de la caméra (ce qui est dur), ils font deux choses intelligentes :

A. Changer de langage (Les coordonnées)

Au lieu de parler de « coordonnées X, Y, Z » (qui changent si on tourne la caméra), ils parlent de distances et d'angles entre les points.

• Analogie : Imaginez que vous essayez de décrire la forme d'un mobile suspendu au plafond. Au lieu de dire « le point A est à 2 mètres à gauche et 3 mètres en haut », vous dites « la ficelle entre A et B mesure 1 mètre, et l'angle entre A et C est de 45 degrés ».
• Pourquoi c'est génial ? Ces distances et angles ne changent pas si vous tournez le mobile. C'est une description « invariante ». Cela simplifie énormément les équations mathématiques.

B. La Réduction Magique (Transformer le problème)

Leur astuce de génie consiste à transformer le problème difficile (trouver la caméra) en un problème facile (trouver l'orientation d'un objet).

1. Ils prennent les 4 points 3D et les 4 points 2D.
2. Ils calculent une configuration intermédiaire : « Si ces points 2D étaient dans l'espace, à quelle profondeur seraient-ils pour que les distances entre eux correspondent exactement aux distances réelles ? »
3. Ils utilisent une formule mathématique directe (comme une recette de cuisine) pour trouver ces profondeurs. Pas de boucles, pas d'essais-erreurs, juste une formule.
4. Une fois qu'ils ont ces profondeurs, ils ont un nouveau jeu de points 3D. Le problème devient alors : « Comment superposer ce nouveau jeu de points sur l'original ? ». C'est un problème très simple et rapide à résoudre (appelé « orientation absolue »).

3. Pourquoi c'est une révolution ?

• Vitesse Éclair : Leur méthode pour vérifier si un échantillon de 4 points est valide est 100 fois plus rapide que les méthodes actuelles.
  • Analogie : C'est la différence entre un détective qui lit tout un livre pour trouver un mot (méthode actuelle) et un détective qui utilise un scanner laser qui trouve le mot en une microseconde (leur méthode).
• Élimination Précoce : Comme leur calcul est si rapide, ils peuvent rejeter les mauvaises hypothèses (les points qui ne correspondent pas) presque instantanément, sans même avoir besoin de calculer la position finale de la caméra.
• Robustesse : Même si les points sont alignés bizarrement (ce qui trompe souvent les autres algorithmes), leur méthode tient bon.

4. Le Résultat Final

Grâce à cette formule, les robots et les logiciels de réalité augmentée peuvent :

1. Tester des milliers de combinaisons de points en une seconde.
2. Jeter immédiatement les mauvaises combinaisons.
3. Garder les meilleures pour calculer la position précise de la caméra.

En résumé :
Les auteurs ont trouvé une formule mathématique élégante qui permet de « tricher » intelligemment. Au lieu de chercher la réponse complète tout de suite, ils vérifient d'abord si le puzzle a même une chance de se résoudre, et ce, à une vitesse fulgurante. C'est comme avoir un filtre magique qui ne laisse passer que les pièces de puzzle qui s'emboîtent vraiment, rendant la reconstruction de la scène 3D beaucoup plus rapide et fiable.

Résumé technique

1. Le Problème : PnP (Perspective-n-Points)

Le problème PnP consiste à retrouver la pose (position et orientation, soit 6 degrés de liberté) d'une caméra calibrée à partir de $n$ points 3D dans le monde et de leurs correspondances 2D sur l'image (la "toile" ou canvas).

• Contexte : Ce problème est fondamental en vision par ordinateur, notamment pour la localisation et la reconstruction 3D.
• Défi spécifique ($n=4$) : Dans les algorithmes RANSAC (RANdom SAmple Consensus), on utilise souvent des sous-ensembles de 3 ou 4 points comme "graines" (seeds) pour estimer une pose initiale. Cependant, la plupart des appariements 2D-3D sont incorrects (bruit, faux positifs).
• Objectif : Trouver une solution pour le cas $n=4$ qui soit extrêmement rapide (pour permettre un rejet rapide des mauvaises graines) tout en maintenant une précision comparable aux méthodes de l'état de l'art (comme EPnP et SQPnP).

2. Méthodologie : Une Nouvelle Approche par Séparation de Variables

L'innovation centrale de l'article réside dans une séparation des variables et une réduction du problème de perspective à un problème d'orientation absolue (absolute orientation).

A. Reformulation par Invariants

Au lieu de travailler directement avec les coordonnées cartésiennes (ce qui nécessiterait 20 nombres pour 4 points 3D et 4 points 2D), les auteurs utilisent des coordonnées invariantes par rotation et translation :

• Côté 3D : Les carrés des distances entre les points ($a_i, c_i$).
• Côté 2D : Les produits scalaires des points après avoir aligné un point de référence sur l'axe optique ($b_i, d_i$).
  Cette réduction ramène les données d'entrée à 12 variables invariantes.

B. Réduction au Problème d'Orientation Absolue

L'algorithme procède en plusieurs étapes clés :

1. Rotation de la toile : On rotate l'image 2D pour que le quatrième point soit sur l'axe optique.
2. Calcul des profondeurs ($z$) : L'objectif est de trouver les profondeurs $z_i$ des points 2D projetés sur les rayons optiques, de sorte que les distances entre les points 3D reconstruits ($z_i \cdot p_i$) correspondent aux distances réelles des points 3D originaux.
3. Formules Polynomiales : En utilisant un système d'algèbre computationnelle (Singular), les auteurs ont dérivé des formules explicites. Le problème est réduit à la résolution de quatre polynômes quadratiques ($Q_i(x)$) dont les coefficients sont des fonctions polynomiales explicites des invariants ($a, b, c, d$).
4. Résolution :
   • On résout les quadratiques pour obtenir $z_i^2$.
   • On génère 16 combinaisons possibles de signes pour les racines carrées.
   • On sélectionne la combinaison qui minimise l'erreur sur les équations de distance.
5. Sortie Intermédiaire : On obtient une configuration 3D estimée (les profondeurs). Cela transforme le problème P4P en un problème d'orientation absolue (trouver la transformation rigide entre deux nuages de points 3D), qui peut être résolu rapidement (ex: algorithme de Horn).

C. Avantages Algorithmiques

• Absence de branches : L'algorithme consiste presque entièrement en l'évaluation de formules polynomiales, ce qui le rend idéal pour les implémentations SIMD (Single Instruction, Multiple Data) et vectorielles.
• Rejet précoce : Avant même de calculer la pose complète, l'algorithme fournit une mesure d'erreur. Si l'erreur est trop élevée (graine incohérente), on rejette immédiatement la combinaison sans passer par l'étape coûteuse de l'orientation absolue.

3. Contributions Clés

1. Vitesse Inégalée : L'algorithme est deux ordres de grandeur plus rapide que les solveurs standards (EPnP, SQPnP) pour la phase de réduction à l'orientation absolue.
2. Formule Explicite : Déduction d'une formule polynomiale fermée pour le cas $n=4$, obtenue via l'algèbre computationnelle mais exécutable sans solveur symbolique lourd.
3. Robustesse aux Configurations Dégénérées : Contrairement à d'autres méthodes, l'approche reste stable avec des points coplanaires ou alignés.
4. Efficacité pour le RANSAC : La capacité à rejeter les mauvaises graines très rapidement permet de traiter un nombre beaucoup plus grand de combinaisons, augmentant ainsi la probabilité de trouver une pose correcte dans des environnements bruyants.

4. Résultats Expérimentaux

Les auteurs ont comparé leur méthode avec les implémentations OpenCV d'EPnP et SQPnP sur des données synthétiques avec différents niveaux de bruit et configurations géométriques (générale, planaire, points alignés).

• Performance Temporelle (sur CPU Intel i7 13th Gen) :
  • EPnP ($n=4$) : ~25.8 µs
  • SQPnP ($n=4$) : ~36.3 µs
  • Algorithme proposé : 0.48 µs (soit **50 à 70 fois plus rapide**).
  • Avec compilation AVX2 : ~0.26 µs.
• Précision :
  • Avec un seuil d'erreur faible, la précision est comparable à SQPnP (le "gold standard" pour la précision).
  • Avec un seuil plus large, elle est comparable à EPnP.
  • L'algorithme souffre beaucoup moins des configurations dégénérées que ses concurrents.
• Rejet des Faux Positifs (Fast Rejection) :
  • Dans un scénario où les appariements sont incorrects (bruit élevé), l'algorithme rejette 99% des mauvaises configurations avec un seuil strict, contre une résolution complète (et donc lente) pour EPnP/SQPnP. Cela permet d'économiser un temps de calcul massif.

5. Signification et Impact

Ce travail représente une avancée significative pour les applications de vision par ordinateur en temps réel et pour les systèmes embarqués :

• Transformation du RANSAC : En rendant l'étape de génération de graines (seed generation) extrêmement rapide, il permet d'utiliser des stratégies RANSAC plus agressives (plus d'itérations, plus de combinaisons testées) sans pénalité de temps.
• Robustesse : La capacité à gérer le bruit et les configurations dégénérées (fréquentes dans le monde réel) en fait une solution supérieure pour la reconstruction 3D robuste.
• Implémentation Matérielle : La nature purement polynomiale et sans branches de l'algorithme le rend parfaitement adapté aux architectures modernes (GPU, CPU vectoriels), offrant des gains de performance supplémentaires par rapport aux méthodes itératives basées sur le gradient (comme Levenberg-Marquardt).

En résumé, Levahi et Osserman proposent une solution qui ne se contente pas d'accélérer le calcul de la pose, mais qui change la dynamique du processus de sélection des données, permettant une reconstruction 3D plus précise et plus rapide dans des conditions réalistes et bruyantes.