En ny MIT-utvecklad teknik gör det möjligt för robotar att snabbt identifiera objekt dolda i ett tredimensionellt moln av data, påminner om hur vissa människor kan förstå en tätt mönstrad "Magic Eye"-bild om de observerar den på precis rätt sätt.

Robotar "ser" vanligtvis sin miljö genom sensorer som samlar in och översätter en visuell scen till en matris av prickar. Tänk på världen av, väl, "Matrisen, " förutom att 1:orna och 0:orna som ses av den fiktiva karaktären Neo ersätts av prickar - massor av prickar - vars mönster och tätheter beskriver objekten i en viss scen.

Konventionella tekniker som försöker plocka ut föremål från sådana moln av prickar, eller punktmoln, kan göra det med antingen hastighet eller precision, men inte båda.

Med sin nya teknik, forskarna säger att en robot exakt kan plocka ut ett föremål, som ett litet djur, som annars är skymd i ett tätt moln av prickar, inom några sekunder efter att ha mottagit den visuella informationen. Teamet säger att tekniken kan användas för att förbättra en mängd situationer där maskinuppfattningen måste vara både snabb och exakt, inklusive förarlösa bilar och robotassistenter i fabriken och hemmet.

"Det överraskande med det här arbetet är, om jag ber dig hitta en kanin i detta moln av tusentals poäng, det finns inget sätt att du kan göra det, säger Luca Carlone, biträdande professor i flyg- och astronautik och medlem av MIT:s Laboratory for Information and Decision Systems (LIDS). "Men vår algoritm kan se objektet genom allt det här röran. Så vi kommer till en nivå av övermänsklig prestanda när det gäller att lokalisera objekt."

Carlone och doktorand Heng Yang kommer att presentera detaljer om tekniken senare denna månad på Robotics:Science and Systems-konferensen i Tyskland.

"Att misslyckas utan att veta"

Robotar försöker för närvarande identifiera objekt i ett punktmoln genom att jämföra ett mallobjekt – en 3D-punktsrepresentation av ett objekt, som en kanin – med en punktmolnrepresentation av den verkliga världen som kan innehålla det objektet. Mallbilden innehåller "funktioner, " eller samlingar av punkter som indikerar karakteristiska krökningar eller vinklar för det objektet, som kaninens öra eller svans. Befintliga algoritmer extraherar först liknande funktioner från det verkliga punktmolnet, försök sedan matcha dessa funktioner och mallens funktioner, och slutligen rotera och anpassa funktionerna till mallen för att avgöra om punktmolnet innehåller objektet i fråga.

Men punktmolndata som strömmar in i en robots sensor innehåller alltid fel, i form av prickar som är i fel position eller felaktigt placerade, vilket avsevärt kan förvirra processen med att extrahera och matcha funktioner. Som en konsekvens, robotar kan göra ett stort antal felaktiga associationer, eller vad forskare kallar "outliers" mellan punktmoln, och i slutändan felidentifierar objekt eller missar dem helt.

Carlone säger att state-of-the-art algoritmer kan sålla de dåliga associationerna från de goda när funktionerna har matchats, men de gör det i "exponentiell tid, " vilket betyder att även ett kluster av bearbetningstunga datorer, sålla igenom täta punktmolndata med befintliga algoritmer, inte skulle kunna lösa problemet inom rimlig tid. Sådana tekniker, även om det är korrekt, är opraktiska för att analysera större, verkliga datauppsättningar som innehåller täta punktmoln.

Andra algoritmer som snabbt kan identifiera funktioner och associationer gör det hastigt, skapa ett stort antal extremvärden eller felaktiga upptäckter i processen, utan att vara medveten om dessa fel.

"Det är hemskt om det här körs på en självkörande bil, eller någon säkerhetskritisk tillämpning, " säger Carlone. "Att misslyckas utan att veta att du misslyckas är det värsta en algoritm kan göra."

En avslappnad utsikt

Yang och Carlone utarbetade istället en teknik som beskär bort extremvärden i "polynomtid, "vilket betyder att det kan göra så snabbt, även för allt tätare moln av prickar. Tekniken kan på så sätt snabbt och exakt identifiera objekt gömda i röriga scener.

Forskarna använde först konventionella tekniker för att extrahera egenskaper hos ett mallobjekt från ett punktmoln. De utvecklade sedan en process i tre steg för att matcha storleken, placera, och orientering av objektet i ett punktmoln med mallobjektet, samtidigt som man identifierar goda från dåliga funktionsassociationer.

Teamet utvecklade en "adaptivt röstningsschema"-algoritm för att beskära extremvärden och matcha ett objekts storlek och position. För storlek, Algoritmen gör associationer mellan mall- och punktmolnsfunktioner, jämför sedan det relativa avståndet mellan funktioner i en mall och motsvarande funktioner i punktmolnet. Om, säga, avståndet mellan två funktioner i punktmolnet är fem gånger det för motsvarande punkter i mallen, Algoritmen tilldelar en "röst" till hypotesen att objektet är fem gånger större än mallobjektet.

Algoritmen gör detta för varje funktionsassociation. Sedan, Algoritmen väljer de föreningar som faller under storlekshypotesen med flest röster, och identifierar dessa som de korrekta associationerna, medan du beskär de andra. På det här sättet, tekniken avslöjar samtidigt de korrekta associationerna och den relativa storleken på objektet som representeras av dessa associationer. Samma process används för att bestämma objektets position.

Forskarna utvecklade en separat algoritm för rotation, som hittar orienteringen av mallobjektet i tredimensionellt utrymme.

Att göra detta är en oerhört knepig beräkningsuppgift. Föreställ dig att du håller en mugg och försöker luta den bara så, för att matcha en suddig bild av något som kan vara samma mugg. Det finns hur många vinklar du kan luta den muggen, och var och en av dessa vinklar har en viss sannolikhet att matcha den suddiga bilden.

Befintliga tekniker hanterar detta problem genom att betrakta varje möjlig lutning eller rotation av objektet som en "kostnad" - ju lägre kostnad, desto mer sannolikt är att den rotationen skapar en exakt matchning mellan funktioner. Varje rotation och tillhörande kostnad representeras i en topografisk karta av olika slag, består av flera kullar och dalar, med lägre höjder i samband med lägre kostnad.

Men Carlone säger att detta lätt kan förvirra en algoritm, speciellt om det finns flera dalar och ingen urskiljbar lägsta punkt som representerar det sanna, exakt matchning mellan en viss rotation av ett objekt och objektet i ett punktmoln. Istället, teamet utvecklade en "konvex avslappningsalgoritm" som förenklar den topografiska kartan, med en enda dal som representerar den optimala rotationen. På det här sättet, Algoritmen kan snabbt identifiera den rotation som definierar objektets orientering i punktmolnet.

Med deras tillvägagångssätt, teamet kunde snabbt och exakt identifiera tre olika föremål – en kanin, en drake, och en Buddha – gömd i punktmoln med ökande täthet. De kunde också identifiera föremål i verkliga scener, inklusive ett vardagsrum, där algoritmen snabbt kunde upptäcka en flinglåda och en basebollhatt.

Carlone säger att eftersom tillvägagångssättet kan fungera i "polynomtid, "det kan lätt skalas upp för att analysera ännu tätare punktmoln, liknar komplexiteten hos sensordata för förarlösa bilar, till exempel.

"Navigering, kollaborativ tillverkning, inhemska robotar, Sök och rädda, och självkörande bilar är där vi hoppas kunna påverka, säger Carlone.

Den här historien återpubliceras med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT-forskning, innovation och undervisning.