Sneller naar een virtuele wereld

Om het beste algoritme te selecteren, moeten we de algoritmes eerst met elkaar vergelijken. Zo bestaan er veel algoritmes die helpen om een virtuele wereld sneller op te bouwen. Virtuele werelden zijn onmisbaar. Denk maar aan zelfrijdende auto’s, die niet mogen botsen, of medisch personeel dat wordt opgeleid zonder in levende proefpersonen te moeten snijden.

Virtuele ogen

Wanneer je met de auto rijdt, gebruik je je ogen om in te schatten wanneer je moet remmen, om zo een aanrijding te vermijden. De ogen van een zelfrijdende wagen zijn sensors of 3D-camera’s. Deze 3D-camera’s geven ons een idee over de afstand van elk object tot de camera. Dat is niet het geval wanneer je met je smartphone een foto neemt van je huisdier. Die foto bestaat uit pixels, kleine vierkantjes met een welbepaalde kleur. Een afbeelding is echter een 2D, vlakke voorstelling van de werkelijkheid. De informatie over de diepte, of hoe ver elk object staat van de camera, wordt niet bewaard. Het resultaat van een 3D-camera is een puntenwolk, waarbij ieder punt nu een kleur heeft en diepte.

Een puntenwolk bestaande uit een collectie van punten die de driedimensionale wereld – hier een vliegtuig – voorstellen.

Het registratieprobleem

Beeld je nu in dat we twee puntenwolken hebben, bijvoorbeeld twee kubussen. Beide stellen hetzelfde object voor, maar staan op een andere plaats in de ruimte. Als we nu beide wolken willen samenbrengen, waardoor ze overlappen, lijkt dat een simpele taak. Voor een computer is deze alignatie echter niet zo voor de hand liggend. Dit probleem, namelijk ervoor zorgen dat de twee puntenwolken overlappen, heet ook wel het registratieprobleem en is zeer populair binnen de computerwetenschappen.

De twee kubussen (blauw, rood) worden gealigneerd door een algoritme. De positie van de ene kubus ten opzichte van de andere wordt zo gevonden.

Een zee van algoritmes

Er bestaan talloze methodes om het registratieprobleem op te lossen, met variërende resultaten. Het ligt dan voor de hand om het “beste” algoritme te selecteren. “Beste” is echter geen duidelijke maatstaf. Daarom vergelijken we in dit onderzoek enkele van deze verschillende methodes met elkaar. Sommige methodes zijn bijvoorbeeld zeer snel en leiden tot een oplossing in minder dan een seconde. Andere doen er wat langer over, maar resulteren in een veel nauwkeuriger resultaat.

Om de algoritmes te vergelijken voeren we de alignatie uit voor enkele eenvoudige, symmetrische vormen. De twee puntwolken maken we uit een driedimensionaal model van het voorwerp (dit is de template) en een scan gemaakt met een 3D-camera. Het experiment wordt meerdere keren herhaald, waarbij bijvoorbeeld het aantal punten wordt veranderd. Ieder individueel resultaat toetsen we op verschillende vlakken, zoals hoe goed de puntenwolken overlappen, de benodigde rekentijd enzovoort.

Het driedimensionaal model (blauw, ook wel “template” genoemd) wordt gealigneerd met de driedimensionale scan (rood).

Uit onze vergelijking blijkt dat sommige algoritmes zeer nauwkeurig zijn, maar ook wat trager. Dat maakt hen niet ideaal voor toepassingen waarbij de registratie vaak opnieuw moet worden opgelost, bijvoorbeeld als de objecten bewegen. Andere methodes zijn gemaakt om zeer snel te zijn en worden daardoor minder nauwkeurig. In die gevallen gebruiken we een extra algoritme om de resultaten verder te verfijnen.

De resultaten vatten we ook samen in een zogenaamde flowchart. Dit is een schema met verschillende ja-nee vragen. Door de vragen één voor één te beantwoorden, kan een andere onderzoeker (of geïnteresseerde lezer) de “beste” methode selecteren voor de eigen toepassing, als een soort “eerste hulp bij algoritme keuzestress”.

Een virtuele wereld scheppen

We kunnen de oplossing van het registratieprobleem ook gebruiken om complete virtuele werelden te bouwen. De echte wereld tot een driedimensionale, virtuele kopie omtoveren is immers een intensief karwei. Klassiek gebeurt dit door object per object een driedimensionaal model te bouwen. Beeld je bijvoorbeeld een stoel in onder een tafel. Dan moet je voor zowel de stoel als de tafel een 3D-model opbouwen tot in de kleinste details.  Een 3D-camera laat toe om dat proces te versnellen. Je loopt simpelweg rond de tafel en de stoel, scant de omgeving met de camera en je verkrijgt onmiddellijk een complete, driedimensionale puntenwolk.

Is daarmee het probleem opgelost? Niet helemaal. De punten in de puntenwolk vormen samen een kopie van de omgeving, maar hoe weet je bij welk object een punt hoort? Bijvoorbeeld, punt A is een onderdeel van het object “stoel” en punt B van het object “tafel”. Er bestaan verschillende algoritmes die de punten kunnen groeperen, onder meer You Only Look Once (YOLO). Met behulp van dit algoritme kunnen de punten worden onderverdeeld in de verschillende objecten of voorwerpen.

De puntenwolk bestaat uit duizenden punten, die aangeduid moeten worden. Bijvoorbeeld, de roze punten maken deel uit van het object stoel en de gele van het object tafel.

Er blijft echter nog één probleem over: hoe kunnen we nu van deze objecten de positie in de ruimte bepalen? Een robot bijvoorbeeld, moet weten waar een voorwerp staat om het te kunnen grijpen. De oplossing hiervoor is het registratieprobleem. Als we weten waar twee puntenwolken zich ten opzichte van elkaar bevinden, kunnen we ook hun positie achterhalen. Hiermee weet onze slimme, zelfrijdende wagen niet alleen exact waar de voorliggende auto zich bevindt, maar kan hij ook een volledige virtuele kopie maken van de omgeving waarin hij rijdt. 

De virtuele toekomst

Interactieve virtuele werelden bestaan ondertussen al in verschillende vormen en formaten. Denk hierbij maar aan VR spelletjes, waar je plots stapt op een smal plankje, dat zich hoog in de lucht bevindt, of de namen van sterrenbeelden die voor je ogen verschijnen wanneer je naar de sterren staart. De mogelijkheden zijn dan ook eindeloos en de enige limiet is je eigen verbeelding, op het maken van die virtuele wereld na. Het is net hierin dat dit onderzoek ons verder helpt. Door onderzoekers naar de beste methodes te leiden, kunnen nieuwe ideeën sneller ontstaan. Die beste methode selecteer je dan op basis van een vergelijking, zoals de onze. Met precieze 3D-camera's en een nauwkeurig en snel registratieproces, komen we sneller tot een virtuele wereld.