Algoritmen finder hurtigt skjulte objekter i tætte punktskyer

En ny MIT-udviklet teknik gør det muligt for robotter hurtigt at identificere objekter skjult i en tredimensionel sky af data, minder om, hvordan nogle mennesker kan give mening med et tæt mønstret "Magic Eye"-billede, hvis de observerer det på den helt rigtige måde.

Robotter "ser" typisk deres omgivelser gennem sensorer, der indsamler og oversætter en visuel scene til en matrix af prikker. Tænk på verden af, godt, "Matrix, " bortset fra at 1'erne og 0'erne, som den fiktive karakter Neo ser, erstattes af prikker - masser af prikker - hvis mønstre og tætheder skitserer objekterne i en bestemt scene.

Konventionelle teknikker, der forsøger at udvælge genstande fra sådanne prikker, eller punktskyer, kan gøre det med enten hastighed eller nøjagtighed, men ikke begge dele.

Med deres nye teknik, forskerne siger, at en robot nøjagtigt kan udvælge et objekt, såsom et lille dyr, der ellers er skjult i en tæt sky af prikker, inden for få sekunder efter modtagelse af de visuelle data. Teamet siger, at teknikken kan bruges til at forbedre en lang række situationer, hvor maskinopfattelsen skal være både hurtig og præcis, herunder førerløse biler og robotassistenter på fabrikken og i hjemmet.

"Det overraskende ved dette arbejde er, hvis jeg beder dig om at finde en kanin i denne sky med tusinder af punkter, der er ingen måde du kan gøre det " siger Luca Carlone, assisterende professor i aeronautik og astronautik og medlem af MIT's Laboratory for Information and Decision Systems (LIDS). "Men vores algoritme er i stand til at se objektet gennem alt dette rod. Så vi er ved at nå et niveau af overmenneskelig ydeevne i at lokalisere objekter."

Carlone og kandidatstuderende Heng Yang vil præsentere detaljer om teknikken senere på måneden på Robotics:Science and Systems-konferencen i Tyskland.

"Svigt uden at vide det"

Robotter forsøger i øjeblikket at identificere objekter i en punktsky ved at sammenligne et skabelonobjekt-en 3-D prikrepræsentation af et objekt, såsom en kanin – med en punktsky-repræsentation af den virkelige verden, der kan indeholde det objekt. Skabelonbilledet indeholder "funktioner, " eller samlinger af prikker, der angiver karakteristiske krumninger eller vinkler for det pågældende objekt, såsom kaninens øre eller hale. Eksisterende algoritmer udvinder først lignende funktioner fra den virkelige punktsky, forsøg derefter at matche disse funktioner og skabelonens funktioner, og i sidste ende rotere og justere funktionerne til skabelonen for at afgøre, om punktskyen indeholder det pågældende objekt.

Men punktskydataene, der strømmer ind i en robots sensor, inkluderer uvægerligt fejl, i form af prikker, der er i den forkerte position eller forkert placeret, hvilket kan forvirre processen med ekstraktion og matchning af funktioner betydeligt. Som en konsekvens, robotter kan lave et stort antal forkerte associationer, eller hvad forskere kalder "outliers" mellem punktskyer, og i sidste ende fejlidentificere objekter eller gå glip af dem helt.

Carlone siger, at state-of-the-art algoritmer er i stand til at sortere de dårlige associationer fra de gode, når først funktioner er blevet matchet, men de gør det i "eksponentiel tid, "hvilket betyder, at selv en klynge af behandlingstunge computere, sigte gennem tætte punktskydata med eksisterende algoritmer, ville ikke være i stand til at løse problemet inden for en rimelig tid. Sådanne teknikker, mens præcis, er upraktiske til at analysere større, virkelige datasæt, der indeholder tætte skyer.

Andre algoritmer, der hurtigt kan identificere funktioner og associationer, gør det hurtigt, skabe et stort antal afvigere eller fejlopdagelser i processen, uden at være opmærksom på disse fejl.

"Det er forfærdeligt, hvis det her kører på en selvkørende bil, eller enhver sikkerhedskritisk applikation, " siger Carlone. "At fejle uden at vide, at du fejler, er det værste, en algoritme kan gøre."

En afslappet udsigt

Yang og Carlone udtænkte i stedet en teknik, der beskærer yderpunkter i "polynomisk tid, "hvilket betyder, at det kan gøre så hurtigt, selv for stadig tættere skyer af prikker. Teknikken kan således hurtigt og præcist identificere objekter gemt i rodede scener.

Forskerne brugte først konventionelle teknikker til at udtrække træk ved et skabelonobjekt fra en punktsky. De udviklede derefter en tretrinsproces, der matchede størrelsen, position, og orientering af objektet i en punktsky med skabelonobjektet, og samtidig identificere gode fra dårlige funktionsassociationer.

Holdet udviklede en "adaptivt stemmeskema"-algoritme til at beskære afvigere og matche et objekts størrelse og position. For størrelse, algoritmen forbinder skabelon- og punktskyfunktioner, sammenligner derefter den relative afstand mellem funktioner i en skabelon og tilsvarende funktioner i punktskyen. Hvis, sige, afstanden mellem to elementer i punktskyen er fem gange afstanden mellem de tilsvarende punkter i skabelonen, algoritmen tildeler en "stemme" til hypotesen om, at objektet er fem gange større end skabelonobjektet.

Algoritmen gør dette for hver funktionstilknytning. Derefter, Algoritmen udvælger de associationer, der falder ind under størrelseshypotesen med flest stemmer, og identificerer dem som de korrekte associationer, mens man beskærer de andre væk. På denne måde teknikken afslører samtidig de korrekte associationer og den relative størrelse af objektet repræsenteret af disse associationer. Den samme proces bruges til at bestemme objektets position.

Forskerne udviklede en separat algoritme til rotation, som finder orienteringen af ​​skabelonobjektet i tredimensionelt rum.

At gøre dette er en utrolig vanskelig beregningsopgave. Forestil dig, at du holder et krus og prøver at vippe det bare så, at matche et sløret billede af noget, der kan være det samme krus. Der er et vilkårligt antal vinkler, du kan vippe kruset, og hver af disse vinkler har en vis sandsynlighed for at matche det slørede billede.

Eksisterende teknikker håndterer dette problem ved at betragte hver mulig hældning eller rotation af objektet som en "omkostning" - jo lavere omkostningerne er, jo mere sandsynligt er det, at denne rotation skaber et nøjagtigt match mellem funktioner. Hver rotation og tilhørende omkostninger er repræsenteret i et topografisk kort af slagsen, består af flere bakker og dale, med lavere højder forbundet med lavere omkostninger.

Men Carlone siger, at dette nemt kan forvirre en algoritme, især hvis der er flere dale og intet synligt laveste punkt, der repræsenterer det sande, nøjagtig match mellem en bestemt rotation af et objekt og objektet i en punktsky. I stedet, holdet udviklede en "konveks afslapnings"-algoritme, der forenkler det topografiske kort, med én enkelt dal, der repræsenterer den optimale rotation. På denne måde algoritmen er i stand til hurtigt at identificere den rotation, der definerer orienteringen af ​​objektet i punktskyen.

Med deres tilgang, holdet var i stand til hurtigt og præcist at identificere tre forskellige objekter - en kanin, en drage, og en Buddha – skjult i punktskyer med stigende tæthed. De var også i stand til at identificere objekter i virkelige scener, herunder en stue, hvor algoritmen hurtigt kunne få øje på en kornkasse og en baseballhat.

Carlone siger, at fordi tilgangen er i stand til at arbejde i "polynomisk tid, "det kan let skaleres op for at analysere endnu tættere punktskyer, ligner kompleksiteten af ​​sensordata til førerløse biler, for eksempel.

"Navigation, kollaborativ produktion, indenlandske robotter, Søg og Red, og selvkørende biler er det sted, hvor vi håber at få indflydelse, " siger Carlone.

Denne historie er genudgivet med tilladelse fra MIT News (web.mit.edu/newsoffice/), et populært websted, der dækker nyheder om MIT-forskning, innovation og undervisning.