A polynomial formula for the perspective four points problem

Dit artikel presenteert een snelle en nauwkeurige oplossing voor het perspectief-vierpuntenprobleem door een nieuwe variabelescheiding te gebruiken die het probleem reduceert tot een absolute oriëntatieoplossing, wat resulteert in een algoritme dat aanzienlijk sneller is dan bestaande methoden.

De kern

Stel je voor dat je een camera hebt die een foto maakt van een object in de ruimte. Je wilt weten: waar staat de camera precies, en in welke richting kijkt hij? Dit is een heel oud probleem in de computerwetenschap, bekend als het "PnP-probleem" (Perspective n-Points).

Om dit op te lossen, kijken computers naar een paar punten op de foto (2D) en proberen ze te koppelen aan de echte punten in de wereld (3D). Vaak zijn er duizenden mogelijke koppelingen, maar de meeste zijn fout. De computer moet dus een slimme gok doen (een "zaadje" of seed) om de juiste positie te vinden.

De auteurs van dit paper, David Levahi en Brian Osserman, hebben een nieuwe, razendsnelle manier bedacht om dit te doen, specifiek voor het geval je vier punten gebruikt.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het oude probleem: Een ingewikkeld puzzel

Stel je voor dat je een 3D-puzzel hebt (een tetraëder, een piramide met vier punten) en je ziet alleen de schaduw ervan op een muur (de foto). Je wilt weten hoe groot de piramide is en hoe hij gedraaid is.

• Hoe het vroeger ging: De computer probeerde duizenden combinaties van rotaties en afstanden uit, alsof je blindelings probeert een sleutel in een slot te draaien. Dit kostte veel tijd en rekenkracht.
• Het probleem: Omdat er zoveel foutieve koppelingen zijn (bijvoorbeeld: punt A op de foto wordt per ongeluk gekoppeld aan punt B in de wereld), moet de computer heel veel "gokjes" doen en controleren of ze kloppen. Dit is traag.

2. De nieuwe aanpak: De "Meten-is-weten" methode

De auteurs zeggen: "Wacht even, laten we niet direct proberen de camera te draaien. Laten we eerst kijken naar de afstanden tussen de punten."

Ze gebruiken een slimme truc, vergelijkbaar met het volgende:

• De 3D-wereld: Je hebt vier punten in de lucht. Je weet de afstanden tussen hen (bijv. de afstand tussen punt 1 en 2, 1 en 3, etc.).
• De 2D-foto: Je ziet vier vlekken op de foto. Je weet niet hoe ver ze weg zijn, maar je kunt de hoeken tussen de lijnen naar de camera meten.

De auteurs zeggen: "Laten we een nieuwe, tijdelijke versie van die vier 3D-punten bedenken die precies op de lijnen van de camera staan, maar zo dat de afstanden tussen hen precies overeenkomen met de afstanden in de echte wereld."

3. De creatieve analogie: Het "Schaduw-herstel"

Stel je voor dat je een poppetje (het 3D-object) hebt en je ziet alleen zijn schaduw op de muur.

• De oude methode: Je probeert het poppetje blindelings te draaien en te verplaatsen tot de schaduw eruitziet als de echte schaduw.
• De nieuwe methode: Je zegt: "Ik ga een nieuwig poppetje bouwen dat op de lijnen van de schaduw staat, maar waarvan ik de poten zo lang maak dat de afstanden tussen de knieën en de ellebogen precies hetzelfde zijn als bij het echte poppetje."

Als je dat nieuwe poppetje hebt gebouwd, is het probleem opgelost! Je hebt nu twee identieke poppetjes:

1. Het echte poppetje (in de wereld).
2. Het nieuwe poppetje (op de lijnen van de camera).

Omdat ze identiek zijn, is het nu heel makkelijk om te berekenen hoe je het nieuwe poppetje moet draaien en verplaatsen om op het echte poppetje te lijken. Dit laatste stukje heet "absolute oriëntatie" en is een simpele wiskundige formule die computers razendsnel kunnen doen.

4. Waarom is dit zo snel? (De "Rekenmachine" vs. De "Gokker")

• De oude algoritmen (zoals EPnP of SQPnP) zijn als een gokker die duizenden keren probeert, meet, en dan weer probeert. Ze gebruiken complexe iteraties (herhalingen) om de fouten te minimaliseren.
• Deze nieuwe formule is als een rekenmachine die één keer een complexe vergelijking invult en direct het antwoord geeft. Er is geen gissen bij.
  • Ze gebruiken een computerprogramma (Singular) om de "recept" (de formule) te vinden.
  • Het resultaat is een simpele formule die alleen optellen, vermenigvuldigen en worteltrekken vereist.

5. De grote winst: "Snel afwijzen"

Dit is misschien wel het belangrijkste deel. In de echte wereld zijn veel koppelingen tussen foto-punten en 3D-punten fout.

• Met de oude methoden moet de computer vaak de hele berekening doen om te zien dat een koppeling fout is.
• Met deze nieuwe methode kan de computer direct zien of een koppeling onmogelijk is. Als de afstanden niet kloppen, wordt het "zaadje" (de gok) direct weggegooid, nog voordat de zware berekening begint.

De analogie:
Stel je bent een detective die duizenden verdachten moet controleren.

• Oude methode: Je nodigt iedereen uit voor een uitgebreid gesprek, laat ze een proef eten eten, en pas daarna zeg je: "Nee, jij bent het niet."
• Nieuwe methode: Je kijkt even naar hun paspoortfoto. Als de vorm van het gezicht niet past, zeg je direct: "Volgende!" Je bespaart 99% van de tijd.

Samenvatting in één zin

De auteurs hebben een nieuwe wiskundige formule bedacht die het probleem van het vinden van de camera-positie oplost door eerst een "perfecte kopie" van het object te bouwen op basis van afstanden, waardoor ze duizenden foutieve pogingen in een fractie van een seconde kunnen uitsluiten en de juiste positie razendsnel kunnen vinden.

Resultaat:

• Snelheid: 10 tot 100 keer sneller dan de huidige beste methoden.
• Nauwkeurigheid: Net zo goed als de beste methoden, zelfs bij ruis (fouten in de data).
• Toepassing: Ideaal voor robots, augmented reality (AR) en zelfrijdende auto's die snel moeten reageren.

Technische samenvatting

Titel: Een Polynoomformule voor het Perspectief Vier-Punten Probleem (P4P)

1. Het Probleem

Het Perspectief n-Punten Probleem (PnP) is een fundamenteel probleem in de computervisie waarbij de 6-vrijheidsgraad (6DoF) pose (positie en oriëntatie) van een gekalibreerde camera moet worden bepaald, gegeven $n$ 3D-punten in de wereld en hun corresponderende 2D-projecties op het beeldvlak.

• Context: Dit probleem is cruciaal voor localisatie in 3D-scènes. In praktijksituaties worden vaak duizenden 2D-3D-paarings gegenereerd, maar slechts een klein deel is correct.
• RANSAC: Om de juiste pose te vinden, wordt vaak de RANSAC-algoritme gebruikt, waarbij willekeurige subsets (zogenoemde "seeds") van 3 of 4 punten worden geselecteerd om een pose te schatten.
• De uitdaging: De $n=4$ case (P4P) is historisch gezien complex. Bestaande oplossingen zijn vaak traag of vereisen iteratieve optimalisatie, wat de snelheid van RANSAC beperkt, vooral bij grote datasets met veel foutieve matchings.

2. Methodologie

De auteurs presenteren een nieuwe, niet-iteratieve aanpak voor het P4P-probleem die volledig gebaseerd is op het evalueren van expliciete algebraïsche formules. De kern van hun methode is een nieuwe variabelescheiding die het perspectiefprobleem reduceert tot een absolute oriëntatieprobleem (het vinden van de transformatie tussen twee bekende 3D-configuraties).

De stappen van het algoritme:

1. Invarianten berekenen: In plaats van te werken met coördinaten (die afhankelijk zijn van rotatie en translatie), worden de invoerdata omgezet naar rotatie- en translatievrije grootheden:
   • Voor de 3D-punten: De kloven van de onderlinge afstanden (squared distances).
   • Voor de 2D-punten: Puntproducten (dot products) na het roteren van het beeldvlak zodat het vierde punt op de optische as ligt.
2. Reductie tot diepte-bepaling: Het doel is om de diepten ($z$-waarden) van de 2D-punten te vinden zodat de onderlinge afstanden van de gereconstrueerde 3D-punten overeenkomen met de werkelijke afstanden.
3. Polynoomoplossing:
   • De auteurs leiden een stelsel van vergelijkingen af dat leidt tot kwadratische polynomen $Q_i(x)$ voor de kwadraten van de diepten ($z_i^2$).
   • De coëfficiënten van deze polynomen zijn expliciete polynomen in de invoer-invarianten ($a, b, c, d$).
   • Er worden 16 mogelijke oplossingen gegenereerd (combinaties van wortels en tekens).
4. Selectie en Validatie:
   • De juiste oplossing wordt geselecteerd door de fout in de afstandvergelijkingen te minimaliseren.
   • Dit levert een geschatte 3D-configuratie op die voldoet aan de meetgegevens.
5. Absolute Oriëntatie: Omdat nu zowel de originele 3D-punten als de geschatte 3D-punten (op de stralen) bekend zijn, wordt het probleem gereduceerd tot het vinden van de rigide transformatie ertussen. Dit kan snel worden opgelost met standaardmethoden zoals Horn's algoritme.
6. Fijnafstelling: De oplossing wordt verder geoptimaliseerd met Fletcher's variant van het Levenberg-Marquardt-algoritme om de reprojectiefout te minimaliseren.

Technische details:

• De formules zijn afgeleid met behulp van het computeralgebra-systeem Singular, maar het uiteindelijke algoritme vereist alleen het evalueren van multivariate polynomen en het nemen van wortels (geen iteratieve lijnen of complexe matrixoperaties).
• De aanpak is uiterst geschikt voor SIMD-implementatie (Single Instruction, Multiple Data) omdat deze vrij is van vertakkingslogica (branches).

3. Belangrijkste Bijdragen

• Snelheid: Het algoritme is één orde van grootte sneller dan de huidige state-of-the-art algoritmen (zoals EPnP en SQPnP) voor het oplossen van de P4P-case.
• Efficiënte Seed-Verwerping: De reductie tot het absolute oriëntatieprobleem is twee orden van grootte sneller dan bestaande methoden. Dit stelt RANSAC in staat om zeer snel slechte "seeds" (onjuiste puntmatchings) te verwerpen voordat er überhaupt een pose wordt berekend.
• Accuraatheid: Biedt een nauwkeurigheid die vergelijkbaar is met de beste bestaande methoden (SQPnP) onder realistische ruiscondities.
• Robuustheid: Het algoritme presteert goed in gedegenereerde configuraties (zoals coplanaire punten of collineaire punten), waar andere methoden vaak falen of instabiel worden.
• Polynoomformule: Het leveren van een expliciete algebraïsche oplossing voor een probleem dat vaak als te complex voor directe symbolische oplossing werd beschouwd.

4. Resultaten en Experimenten

De auteurs hebben hun algoritme getest tegen EPnP en SQPnP (OpenCV-implementaties) op synthetische data met verschillende ruisniveaus en configuraties (algemeen, planair, en collineair).

• Berekeningstijd:
  • EPnP (n=4): ~25.77 µs
  • SQPnP (n=4): ~36.31 µs
  • Auteurs' algoritme: 0.48 µs (standaard) en **0.26 µs** met AVX2-vectorisatie.
  • Dit betekent een snelheidswinst van ongeveer 50 tot 100 keer ten opzichte van de concurrenten voor de initiële schatting.
• Nauwkeurigheid:
  • Bij een drempelwaarde van 0.05 is de rotatie- en translatiefout vergelijkbaar met SQPnP (de "gouden standaard" voor nauwkeurigheid).
  • Bij een hogere drempelwaarde (1.0) is de nauwkeurigheid vergelijkbaar met EPnP.
• Verwerping van Fouten (Early True Negative):
  • In scenario's met veel foutieve matchings (waarbij 3D-punten willekeurig worden vervangen), verwerpt het algoritme 99% van de verkeerde configuraties met een drempel van 0.05, terwijl EPnP en SQPnP deze vaak als oplossing accepteren met enorme fouten.
• Stabiliteit: Het algoritme vertoont een lagere variantie in de foutverdeling vergeleken met SQPnP, wat wijst op grotere stabiliteit.

5. Betekenis en Conclusie

Dit werk biedt een transformatieve oplossing voor het PnP-probleem in real-world toepassingen. Door de rekentijd voor het oplossen van de pose drastisch te verkorten en een zeer efficiënt mechanisme voor het verwerpen van slechte data te bieden, maakt het algoritme het mogelijk om veel grotere datasets te verwerken dan voorheen haalbaar was.

De belangrijkste impact ligt in situaties waar puntmatching onzeker is (bijvoorbeeld in ongestructureerde omgevingen of bij lage kwaliteit beelden). Het vermogen om duizenden kwadrupels van punten in real-time te screenen en alleen de meest veelbelovende kandidaten verder te verwerken, plaatst dit algoritme in een unieke klasse. Het combineert de snelheid van een directe formule met de nauwkeurigheid van geoptimaliseerde methoden, wat het ideaal maakt voor real-time computervisie-toepassingen zoals augmented reality, robotica en autonome voertuigen.