Een nieuwe door MIT ontwikkelde techniek stelt robots in staat om snel objecten te identificeren die verborgen zijn in een driedimensionale datawolk. doet denken aan hoe sommige mensen een "Magic Eye"-beeld met een dicht patroon kunnen begrijpen als ze het op de juiste manier observeren.

Robots "zien" hun omgeving meestal door middel van sensoren die een visuele scène verzamelen en vertalen in een matrix van stippen. Denk aan de wereld van, goed, "De Matrix, " behalve dat de enen en nullen die door het fictieve personage Neo worden gezien, worden vervangen door stippen - heel veel stippen - waarvan de patronen en dichtheden de objecten in een bepaalde scène omlijnen.

Conventionele technieken die objecten proberen te onderscheiden van zulke wolken stippen, of puntenwolken, kan dit met snelheid of nauwkeurigheid doen, maar niet allebei.

Met hun nieuwe techniek, de onderzoekers zeggen dat een robot een object nauwkeurig kan uitkiezen, zoals een klein dier, die anders verborgen is in een dichte wolk van stippen, binnen enkele seconden na ontvangst van de visuele gegevens. Het team zegt dat de techniek kan worden gebruikt om tal van situaties te verbeteren waarin machineperceptie zowel snel als nauwkeurig moet zijn. inclusief zelfrijdende auto's en robotassistenten in de fabriek en thuis.

"Het verrassende aan dit werk is, als ik je vraag om een ​​konijntje te vinden in deze wolk van duizenden punten, dat kan je op geen enkele manier doen, " zegt Luca Carlone, assistent-professor luchtvaart en ruimtevaart en lid van MIT's Laboratory for Information and Decision Systems (LIDS). "Maar ons algoritme is in staat om het object door al deze rommel heen te zien. Dus we bereiken een niveau van bovenmenselijke prestaties bij het lokaliseren van objecten."

Carlone en afgestudeerde student Heng Yang zullen later deze maand details van de techniek presenteren op de Robotics:Science and Systems-conferentie in Duitsland.

"Falen zonder het te weten"

Robots proberen momenteel objecten in een puntenwolk te identificeren door een sjabloonobject te vergelijken - een 3D-puntweergave van een object, zoals een konijn - met een puntenwolkrepresentatie van de echte wereld die dat object kan bevatten. De sjabloonafbeelding bevat "functies, " of verzamelingen stippen die karakteristieke krommingen of hoeken van dat object aangeven, zoals het oor of de staart van het konijn. Bestaande algoritmen halen eerst vergelijkbare kenmerken uit de echte puntenwolk, probeer vervolgens die kenmerken en de kenmerken van de sjabloon te matchen, en uiteindelijk de objecten roteren en uitlijnen met de sjabloon om te bepalen of de puntenwolk het object in kwestie bevat.

Maar de puntenwolkgegevens die naar de sensor van een robot stromen, bevatten steevast fouten, in de vorm van stippen die zich op de verkeerde plaats of op de verkeerde afstand bevinden, wat het proces van feature-extractie en matching aanzienlijk kan verwarren. Als gevolg hiervan, robots kunnen een groot aantal verkeerde associaties maken, of wat onderzoekers 'uitbijters' tussen puntenwolken noemen, en uiteindelijk objecten verkeerd identificeren of helemaal missen.

Carlone zegt dat state-of-the-art algoritmen in staat zijn om de slechte associaties van de goede te scheiden zodra de kenmerken zijn gematcht. maar ze doen dat in "exponentiële tijd, " wat betekent dat zelfs een cluster van computers die veel rekenkracht nodig hebben, het doorzoeken van dichte puntenwolkgegevens met bestaande algoritmen, niet in staat zou zijn het probleem binnen een redelijke termijn op te lossen. dergelijke technieken, hoewel nauwkeurig, zijn onpraktisch voor het analyseren van grotere, real-life datasets met dichte puntenwolken.

Andere algoritmen die snel kenmerken en associaties kunnen identificeren, doen dat haastig, het creëren van een groot aantal uitbijters of verkeerde detecties in het proces, zonder op de hoogte te zijn van deze fouten.

"Dat is verschrikkelijk als dit draait op een zelfrijdende auto, of enige veiligheidskritieke toepassing, "zegt Carlone. "Mislukken zonder te weten dat je faalt, is het ergste wat een algoritme kan doen."

Een ontspannen uitzicht

Yang en Carlone bedachten in plaats daarvan een techniek die uitschieters in "polynomiale tijd, " wat betekent dat het zo snel kan doen, zelfs voor steeds dichtere wolken van stippen. De techniek kan dus snel en nauwkeurig objecten identificeren die verborgen zijn in rommelige scènes.

De onderzoekers gebruikten eerst conventionele technieken om kenmerken van een sjabloonobject uit een puntenwolk te extraheren. Vervolgens ontwikkelden ze een proces in drie stappen om de grootte aan te passen, positie, en oriëntatie van het object in een puntenwolk met het sjabloonobject, terwijl tegelijkertijd goede en slechte kenmerkassociaties worden geïdentificeerd.

Het team ontwikkelde een "adaptief stemschema"-algoritme om uitbijters te snoeien en de grootte en positie van een object te matchen. voor maat, het algoritme maakt associaties tussen sjabloon- en puntenwolkkenmerken, vergelijkt vervolgens de relatieve afstand tussen objecten in een sjabloon en corresponderende objecten in de puntenwolk. Indien, zeggen, de afstand tussen twee objecten in de puntenwolk is vijf keer die van de corresponderende punten in de sjabloon, het algoritme kent een "stem" toe aan de hypothese dat het object vijf keer groter is dan het sjabloonobject.

Het algoritme doet dit voor elke kenmerkassociatie. Vervolgens, het algoritme selecteert die associaties die vallen onder de groottehypothese met de meeste stemmen, en identificeert deze als de juiste associaties, terwijl je de andere wegsnoeit. Op deze manier, de techniek onthult tegelijkertijd de juiste associaties en de relatieve grootte van het object dat door die associaties wordt vertegenwoordigd. Hetzelfde proces wordt gebruikt om de positie van het object te bepalen.

De onderzoekers ontwikkelden een apart algoritme voor rotatie, die de oriëntatie van het sjabloonobject in de driedimensionale ruimte vindt.

Om dit te doen is een ongelooflijk lastige rekentaak. Stel je voor dat je een mok vasthoudt en probeert hem zo te kantelen, om een ​​wazig beeld van iets aan te passen dat diezelfde mok zou kunnen zijn. Er zijn een aantal hoeken waarmee je die mok kunt kantelen, en elk van die hoeken heeft een zekere kans om overeen te komen met het wazige beeld.

Bestaande technieken pakken dit probleem aan door elke mogelijke kanteling of rotatie van het object als een "kost" te beschouwen - hoe lager de kosten, hoe waarschijnlijker het is dat die rotatie een nauwkeurige overeenkomst tussen kenmerken creëert. Elke rotatie en bijbehorende kosten worden weergegeven in een soort topografische kaart, samengesteld uit meerdere heuvels en valleien, met lagere hoogtes geassocieerd met lagere kosten.

Maar Carlone zegt dat dit gemakkelijk een algoritme kan verwarren, vooral als er meerdere valleien zijn en geen waarneembaar laagste punt dat de ware, exacte overeenkomst tussen een bepaalde rotatie van een object en het object in een puntenwolk. In plaats daarvan, het team ontwikkelde een "convex relaxatie"-algoritme dat de topografische kaart vereenvoudigt, met één enkele vallei die de optimale rotatie vertegenwoordigt. Op deze manier, het algoritme kan snel de rotatie identificeren die de oriëntatie van het object in de puntenwolk definieert.

Met hun aanpak het team was in staat om snel en nauwkeurig drie verschillende objecten te identificeren:een konijn, een draak, en een Boeddha - verborgen in puntenwolken van toenemende dichtheid. Ze waren ook in staat om objecten in levensechte scènes te identificeren, waaronder een woonkamer, waarin het algoritme al snel een cornflakesdoos en een baseballpet kon spotten.

Carlone zegt dat omdat de benadering in "polynomiale tijd kan werken, " het kan eenvoudig worden opgeschaald om nog dichtere puntenwolken te analyseren, die lijkt op de complexiteit van sensorgegevens voor auto's zonder bestuurder, bijvoorbeeld.

"Navigatie, gezamenlijke productie, huishoudelijke robots, zoek en Red, en zelfrijdende auto's is waar we een impact hopen te maken, ' zegt Carlijn.

Dit verhaal is opnieuw gepubliceerd met dank aan MIT News (web.mit.edu/newsoffice/), een populaire site met nieuws over MIT-onderzoek, innovatie en onderwijs.