Visuele odometrie aan de hand van optical flow Thijs De Vits
Promotor: prof. dr. ir. Peter Veelaert Begeleiders: David Van Hamme, Gianni Allebosch Masterproef ingediend tot het behalen van de academische graad van Master of Science in de industriële wetenschappen: elektronica-ICT
Vakgroep Industriële Technologie en Constructie Voorzitter: prof. Marc Vanhaelst Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2014-2015
Dankwoord De realisatie van dit eindwerk zou onmogelijk geweest zijn zonder de hulp, steun en tijd van heel wat mensen. Via deze weg wil ik aan hen graag een woord van dank richten. Eerst en vooral wil ik mijn thesisbegeleider David Van Hamme bedanken voor de zeer goede begeleiding doorheen het jaar, de ontzettend behulpzame feedback en bovenal zijn geduld met mij. Zonder hem was dit eindwerk wellicht nooit tot een goed einde gebracht. Vervolgens wil ik ook mijn promotor, prof. dr. ir. Peter Veelaert, bedanken voor het mogelijk maken van dit eindwerk. Ook zijn interessante lessen die ik heb genoten tijdens mijn opleiding zullen niet worden vergeten. Ook mijn andere begeleider, Gianni Allebosch zou ik willen bedanken voor de feedback en het nalezen van mijn werk. Verder verdienen ook enkele vrienden een woordje van dank. Met name Michiel Creve voor het gebruik van zijn eindwerk, Thomas Peiffer voor zijn goede raad en Tim Scheys voor zijn oprechte steun. Daarnaast wil ik ook nog een speciaal woordje van dank richten aan mijn ouders. Dit hoofdzakelijk voor de morele steun gedurende dit hele proces maar ook omdat zij mij tenslotte de kans hebben gegeven om verder te studeren. Het beste heb ik tot het laatste bewaard: leren kan niet zonder afwisseling, ontspanning en afleiding. En wat dat betreft wil ik mijn vriendin, Lieselotte Thyssen, bedanken. Zonder haar steun was dit me misschien nooit gelukt.
i
Abstract Tot op heden kan de exacte positiebepaling via satellietsignalen bij navigatiesystemen een probleem vormen. Dit komt hoofdzakelijk door het wegvallen of verstoord raken van deze signalen door tunnels, wolkenkrabbers of andere hoge obstakels. In dit werk wordt hiervoor een oplossing aangeboden die aan de hand van visuele odometrie de relatieve beweging van een wagen kan achterhalen wanneer de gangbare navigatiesystemen het laten afweten. Een enkelvoudige camera wordt vooraan of achteraan de wagen bevestigd en is gericht naar de weg. De bijdrage in dit werk is dat via optical flow, een methode binnen de beeldverwerking, de beweging van de omgeving rondom de wagen in kaart wordt gebracht en dat mits toepassing van de juiste regularisatietechnieken uiteindelijk een schatting kan worden gemaakt van de relatieve voortbeweging van de wagen. Uit de resultaten blijkt het concept van de oplossing in zijn opzet geslaagd. Maar inzake precisie en toepasbaarheid op verschillende ondergronden is de methodiek nog voor verbetering vatbaar. Trefwoorden: Visuele odometrie, optical flow, navigatie, positiebepaling, beeldverwerking
ii
Abstract To this day, a precise position estimation through satellite navigation still remains problematic and inaccurate at times. This is mainly due to the loss of or the disturbance of satellite signals by tunnels, skyscrapers or other high obstacles. In order to solve this problem, a solution is being proposed in this thesis which offers the possibility to obtain the relative motion of the vehicle using images taken from a single camera and visual odometry. This camera is mounted on the front or on the back of the vehicle directed towards the road. Based on a method within the domain of computer vision called optical flow, the motion of the surroundings with respect to the vehicle are examined. Applying the right regularization techniques, the relative motion can be estimated. The results prove the validity of the concept, although questions remain concerning precision and applicability on certain terrain types. Keywords: Visual odometry, optical flow, navigation, position estimation, computer vision
iii
Inhoudsopgave 1 Inleiding 1.1 Probleemstelling . . . . . . . . . . . . . . . . . . 1.2 Ontleding van het probleem . . . . . . . . . . . . 1.2.1 Algemeen . . . . . . . . . . . . . . . . . . 1.2.2 Camera . . . . . . . . . . . . . . . . . . . 1.2.3 Omzetten van 2D- naar 3D-co¨ordinaten . 1.2.4 Vertaling naar beweging van het voertuig 1.3 Plan van aanpak . . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
1 1 3 3 3 4 4 5
2 Literatuurstudie 7 2.1 Visuele Odometrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Optical Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Feature extractie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Voorbewerking van de beelden 17 3.1 Cameramodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Region of interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Bepaling van de flowvectoren 22 4.1 Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Flowvectoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5 Translatie en rotatie
26
6 Regularisatie 6.1 Wegingsfactor toepassen . . . . . . 6.2 Optimalisatie via minimalisatie . . 6.3 Clustering . . . . . . . . . . . . . . 6.3.1 Clusteren van rotatiecentra 6.3.2 Clusteren van rotatiehoeken
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
30 30 31 36 36 39
7 Resultaten 7.1 Technische details . . . . . . . . . . . . . 7.1.1 Camerabeelden . . . . . . . . . . . 7.1.2 Parameters . . . . . . . . . . . . . 7.2 Least absolute deviations versus clustering 7.3 Sparse versus Dense . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
40 41 41 42 44 48
. . . . .
iv
. . . . .
. . . . .
7.4 7.5
Getransformeerde beelden versus getransformeerde flowvectoren . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Andere camerabeelden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8 Toekomstig werk 8.1 Parameteroptimalisatie . . . . . . . . . . . . . . . 8.2 Verdere optimalisatie van de gebruikte methodes 8.3 Automatische foutcorrectie . . . . . . . . . . . . 8.4 Kwantitatieve analyse . . . . . . . . . . . . . . . 8.5 Combinatie met andere systemen . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
63 63 63 64 64 65
9 Conclusie 66 9.1 Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 9.2 Performantie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
v
Lijst van figuren 1.1 1.2
Urban canyon met multipath interference . . . . . . . . . . . . . . . . . . . Overzicht van de verschillende stappen tijdens het proces. Links de methodiek waarbij optical flow toegepast wordt op de getransformeerde beelden, rechts de toepassing op de originele beelden waarbij de bekomen flowvectoren getransformeerd worden . . . . . . . . . . . . . . . . . . . . . . . . . .
2
6
2.1
Aan de linkerkant wordt weergegeven hoe twee objecten verschoven worden gedurende twee opeenvolgende beelden. Rechts wordt deze verschuiving weergegeven aan de hand van vectoren. . . . . . . . . . . . . . . . . . . . . 10
3.1 3.2
Voorbeeld van de perspectiefprojectie . . . . . . . . . . . . . . . . . . . . . 18 Voorbeeld van een beeld afkomstig van de camera op de wagen (links) en zijn teruggeprojecteerde virtuele grondvlak (rechts) . . . . . . . . . . . . . . 20 De gebruikte maskers waarbij de witte pixels de region of interest voorstellen (links) en een voorbeeldframe met de region of interest roodgekleurd (rechts). 21
3.3 4.1 4.2 5.1 5.2 5.3 5.4 6.1 6.2
6.3 6.4
Het verdelen van het getransformeerde beeld in zes delen om het aantal features in de overeenkomstige delen met elkaar te kunnen vergelijken. . . . 23 Twee voorbeeldframes waarbij de verkregen flowvectoren worden weergegeven, (a) dense optical flow en (b) sparse optical flow . . . . . . . . . . . . . 25 Voorstelling van het principe van Ackermann . . . . . . . . . . . . . . . . De bepaling van het Instantaneous Center of Rotation (ICR) van de wagen aan de hand van de flowvectoren u, v en w . . . . . . . . . . . . . . . . . . Bepaling van de rotatiehoek . . . . . . . . . . . . . . . . . . . . . . . . . . Bepaling van de grootte van de translatie gekenmerkt door de vector z . . Een voorbeeldframe van een getransformeerd camerabeeld aan de linkerzijde en een visualisatie van het bijhorende gewichtsmasker aan de rechterzijde Drie visuele weergaven van de kost bij het bepalen van het momentane rotatiecentrum, telkens bij een andere situatie. In volgorde van voorkomen: (a) een bocht naar rechts, (b) een bocht naar links en (c) rechtdoor rijden. Een voorbeeld van de bepaling van een nieuwe waarde voor x op basis van de gulden snede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Clustering van de rotatiecentra bij het nemen van een bocht naar rechts. (a): clustering zonder samenvoeging van clusters, (b): clustering met samenvoeging van clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
. 26 . 27 . 28 . 29 . 30
. 33 . 35
. 38
6.5
Clusteren van de verschillende rotatiehoeken aangegeven door de verschillende flowvectoren. In dit geval wordt een bocht naar rechts genomen. . . . 39
7.1
Luchtfoto van de parking van Hogeschool Gent Campus Schoonmeersen met weergave van het achtvormige testtraject . . . . . . . . . . . . . . . . . . . Weergave van de cumulatieve rotatiehoek bij de twee gebruikte regularisatiemethoden wat betreft de rotatiecentra. . . . . . . . . . . . . . . . . . Weergave van de momentane rotatiehoek bij de twee gebruikte regularisatiemethoden wat betreft de rotatiecentra. . . . . . . . . . . . . . . . . . De bekomen trajecten bij beide regularisatiemethodes . . . . . . . . . . . Het bekomen traject bij beide optical flow methodes . . . . . . . . . . . . Weergave van de cumulatieve rotatiehoek bij de twee gebruikte optical flow methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weergave van de momentane rotatiehoek bij de twee gebruikte optical flow methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Het bekomen traject bij beide oplossingsmethodieken . . . . . . . . . . . . Weergave van de cumulatieve rotatiehoek bij de twee gebruikte oplossingsmethodieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weergave van de momentane rotatiehoek bij de twee gebruikte oplossingsmethodieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Duidelijkere weergave van het bekomen traject bij de tweede oplossingsmethodiek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Een voorbeelframe (a) van de beelden bij het nieuwe testtraject en het bijhorende getransformeerde beeld (b) . . . . . . . . . . . . . . . . . . . . Het gebruikte masker (a) dat toegepast wordt op de originele camerabeelden (b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weergave van het tweede traject . . . . . . . . . . . . . . . . . . . . . . . Het bekomen traject bij het toepassen van de voorgestelde oplossingsmethodiek op de andere camerabeelden . . . . . . . . . . . . . . . . . . . . . Vergelijking van beide trajecten bij de andere camerabeelden. (a) het origineel, (b) het bekomen resultaat . . . . . . . . . . . . . . . . . . . . . . . . Twee voorbeeldframes waarbij het zoeken naar de corresponderende beeldpunten foutloopt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Twee voorbeeldframes waarbij het koppelen van beeldpunten foutloopt desondanks de hoge mate van contrast in het beeld . . . . . . . . . . . . . . . Kostencurve van ´e´en van de voorbeeldsituaties waarbij de bepaling van de correcte flowvectoren misloopt . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11 7.12 7.13 7.14 7.15 7.16 7.17 7.18 7.19
vii
. 41 . 45 . 46 . 47 . 49 . 50 . 51 . 53 . 54 . 55 . 56 . 57 . 57 . 58 . 59 . 59 . 60 . 61 . 62
Lijst van tabellen 6.1
Vergelijking van tien algoritmes bij de bepaling van het minimum bij de kostencurves van de rotatiecentra op basis van de uitvoeringstijd. . . . . . . 34
7.1
Vergelijking van de twee gebruikte regularisatiemethodes wat betreft de rotatiecentra en dit op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt. . . . . . . . . . . . . . . . . . . . . . . . . . 45 Vergelijking van de twee gebruikte optical flow methodes en dit op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt 49 Vergelijking van de twee gebruikte oplossingsmethodieken op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt . . 53
7.2 7.3
viii
Hoofdstuk 1
Inleiding 1.1
Probleemstelling
Global Positioning System, beter bekend als GPS, is vandaag de dag meer en meer een ingeburgerd gegeven aan het worden. Mensen die met behulp van omslachtige en (voor sommigen onder ons) ingewikkelde kaarten de weg naar hun bestemming proberen uit te vissen, zijn stilaan uit het straatbeeld aan het verdwijnen. Met slechts enkele aanrakingen op het touchscreen van het GPS-toestel weet men in geen tijd de kortste weg naar zijn bestemming. Maar elk voordeel heeft ook zo zijn nadeel. De mens wordt op deze manier immers meer en meer afhankelijk van technologie om op zijn bestemming te geraken. En wanneer deze technologie het laat afweten, kan men zich dus al snel verdwaald voelen. Het wegvallen of verstoord geraken van GPS-signalen is hier een voorbeeld van. Het is namelijk zo dat in dichtbevolkte, stedelijke omgevingen GPS-signalen verstoord kunnen worden of zelfs helemaal niet tot bij de ontvanger geraken. Dit komt hoofdzakelijk door de zeer hoge wolkenkrabbers die urban canyons vormen. Het zijn deze hoge obstakels die signalen, afkomstig van satellieten, kunnen blokkeren. Een ander fenomeen dat hier ook kan optreden is multipath interference. Hierbij worden de signalen (afkomstig van de satellieten) gereflecteerd via deze hoge obstakels en veroorzaken interferentie met de niet-gereflecteerde signalen bij de ontvanger (Figuur 1.1).
1
Figuur 1.1: Urban canyon met multipath interference
Aangezien signalen van vier verschillende satellieten nodig zijn om een precieze locatie te kunnen bepalen, is de aanwezigheid van de hiervoor genoemde problemen allesbehalve gewenst. Wanneer er na 30 seconden of meer geen precieze positiebepaling kan plaatsvinden door bijvoorbeeld te weinig satellieten in de line-of-sight, zal een GPS-gebaseerd systeem in de meeste gevallen een verkeerde schatting maken wat betreft de huidige positie van de bestuurder. Wat GPS betreft zal deze situtatie er blijkbaar niet op verbeteren, aangezien de vervanging van verouderde satellieten door nieuwe veel langer duurt dan voorzien en vooral een veel hogere kost met zich meedraagt dan op voorhand was voorspeld [41]. Het gelijkaardige Russische systeem GLONASS kampt zelfs met slechtere prestaties dan GPS. Dit ligt enerzijds aan het gebrek aan onderhoud dat er gedurende de jaren negentig was doordat er niet genoeg financi¨ele middelen aanwezig waren. Maar anderzijds ook door het lagere aantal satellieten in de constellatie en de minder geavanceerde technologie die de satellieten bezitten [12]. Het Europese project, Galileo genaamd, zou daarentegen de meeste tekortkomingen van de huidige systemen moeten verhelpen. Daarbovenop zal Galileo kunnen samenwerken met GPS en GLONASS om zodoende de precisie nog meer op te drijven. In [19] wordt aangetoond dat deze combinatie van navigatiesystemen verbeteringen brengt op vlak van onder andere beschikbaarheid van satellieten, maar in stedelijke omgevingen laat dit blijkbaar nog steeds wat te wensen over. En misschien ook nog een niet onbelangrijk detail: het wordt geschat dat alle satellieten die behoren tot het Galileo-project pas tegen 2019 in de ruimte zullen hangen. Al dit voorgaande in acht genomen, is er duidelijk een werkend alternatief nodig. Een mogelijk alternatief zou visuele odometrie kunnen zijn. Hierbij wordt met behulp van camera’s de beweging van het voertuig achterhaald, om zo tot een positiebepaling te komen tijdens de afwezigheid van de GPS-signalen. Voor meer uitleg over visuele odometrie wordt er doorverwezen naar Hoofdstuk 2. Auto’s worden tegenwoordig meer en meer uitgerust met camera’s om allerhande taken uit te voeren. Enkele van deze taken zijn rijstrookdetectie en detectie van verkeersborden. Men kan dus makkelijk inzien dat visuele odometrie een re¨ele oplossing zou kunnen bieden wat betreft het GPS-probleem. Maar visuele odometrie is niet alleen nuttig als aanvulling voor GPS, het kan ook toegepast
2
worden in situaties waar GPS onmogelijk is, namelijk bij indoor navigatie of zelfs op andere planeten. De NASA rovers Spirit en Opportunity maakten bijvoorbeeld al succesvol gebruik van visuele odometrie tijdens hun wetenschappelijke onderzoeken op de planeet Mars [24]. In deze thesis wordt er gebruikgemaakt van een reeds bestaande oplossing als referentie [41]. Hierbij wordt een camera gemonteerd op het voertuig waarna men aan de hand van de camerabeelden en via bepaalde beeldverwerkingstechnieken de relatieve beweging van het voertuig kan achterhalen. In dit werk wordt deze relatieve beweging met behulp van een andere beeldverwerkingstechniek geanalyseerd, namelijk optical flow (zie Hoofdstuk 2).
1.2
Ontleding van het probleem
Eerst zal er kort worden geschetst wat de eisen zijn aan welke het systeem moet trachten te voldoen. Daarna worden enkele problemen en moeilijkheden besproken.
1.2.1
Algemeen
Het systeem dient in de eerste plaats een aanvulling te zijn op bestaande navigatiesystemen zoals GPS, meer bepaald wanneer de precisie het laat afweten of er te weinig satellietsignalen beschikbaar zijn. Maar dit sluit uiteraard niet uit dat het systeem ook los van GPS kan werken. De functie bestaat er namelijk in de relatieve beweging van het voertuig ten opzichte van zijn omgeving te achterhalen en dit voor het gehele traject dat het voertuig aflegt. Men kan het in principe ook omgekeerd bekijken, dat het systeem wordt bijgestaan door GPS om eventueel een geaccumuleerde fout bij het bepalen van de huidige positie te corrigeren. Wat hierbij ook zou kunnen helpen is de reeds afgelegde route steeds te mappen op een offline stratenplan, zo kunnen afwijkingen van de route meteen opgevangen worden. In deze thesis wordt echter enkel ingegaan op het verwerken van de camerabeelden om hieruit de relatieve beweging van het voertuig te achterhalen.
1.2.2
Camera
Een opmerking kan gemaakt worden inzake de camerabeelden. Men kan hiervoor camera’s in stereo [30, 20], een omnidirectionele camera [33, 38] of slechts ´e´en camera met een standaard lens [7] gebruiken. In vergelijking met de andere twee mogelijkheden, scoort de enkelvoudige camera het best qua praktische overwegingen. Enkelvoudige camera’s zijn namelijk makkelijker om mee te werken, kosten het minste en kunnen onopvallend verwerkt worden in het koetswerk van de wagen waardoor het uitzicht van de wagen onverstoord blijft. Bij camera’s in stereo wordt de kalibratie een stuk moeilijker aangezien er rekening moet gehouden worden met input van twee camera’s met elk een ander standpunt en daarbovenop zal deze implementatie ook een stuk duurder zijn. Ook omnidirectionele camera’s (heeft een gezichtsveld van 360◦ ) hebben enkele nadelen. Naast de hogere kostprijs is het
3
namelijk vrijwel onmogelijk om deze onopvallend te monteren op voertuigen. Omnidirectionele camera’s zijn vanwege hun werking en concept genoodzaakt bovenop het voertuig gemonteerd te worden. De meeste modellen zijn ook niet echt compact waardoor het uitzicht van de wagen hieronder kan lijden. Tot slot van rekening levert de enkelvoudige camera prestaties die als voldoende bruikbaar kunnen beschouwd worden[41]. Al kan men opmerken dat deze niet opwegen tegenover de prestaties van stereo- of omnidirectionele camera’s. Het is echter wanneer men zich in het echte verkeer begeeft of men hogere snelheden aanneemt, dat zekere problemen de kop kunnen opsteken. De beweging van andere voertuigen kan namelijk voor verstoring zorgen. Ook snel accelereren of hard remmen kan leiden tot inconsistentie van het beeld. En wat de hogere snelheid betreft, wordt de relatieve beweging gemeten tussen twee frames groter (pixels schuiven meer op).
1.2.3
Omzetten van 2D- naar 3D-co¨ ordinaten
In wezen zijn de beelden afkomstig van de camera die op het voertuig geplaatst is, tweedimensionaal. Punten in het beeld bezitten dan ook slechts twee co¨ordinaten. Maar om de relatieve beweging van het voertuig te analyseren louter gebaseerd op deze beelden, is het nodig om de 3D wereldco¨ ordinaten te weten van deze punten. Het omzetten van deze 2D-co¨ ordinaten afkomstig van gekozen punten uit de camerabeelden is echter zeer complex. Het is om die reden dat we in deze thesis een compromis stellen en aannemen dat alle gekozen punten uit de camerabeelden zich in het grondvlak bevinden. Op deze manier wordt het omzetten van de 2D-co¨ordinaten een pak eenvoudiger aangezien we de ontbrekende dimensie invullen met een constante hoogte. Door dit aan te nemen, moet er ook rekening gehouden worden met het feit dat slechts een bepaald gebied uit de camerabeelden mag gebruikt worden. Met andere woorden, gebieden die niet in het grondvlak liggen (bijvoorbeeld struiken of bomen in de achtergrond) moeten worden uitgesloten. Dit komt allemaal uitgebreider aan bod in Hoofdstuk 3.
1.2.4
Vertaling naar beweging van het voertuig
Om de relatieve beweging van een bewegend object uit camerabeelden te halen bestaan verscheidene mogelijkheden binnen het domein van de computervisie (zie Hoofdstuk 2). Hierbij komt de eerste stap meestal neer op het kiezen van bepaalde punten in een beeld, om vervolgens te zoeken naar de overeenkomstige punten in de daaropvolgende beelden. Op deze manier is het mogelijk om te achterhalen hoe objecten of gebieden in het beeld bewegen en dus ook hoe de camera zelf is bewogen ten opzichte van deze objecten of gebieden. In deze thesis werd gekozen om hiervoor gebruik te maken van Optical Flow (zie Hoofdstuk 2). Hoe deze informatie in dit werk vertaald wordt naar de beweging van het voertuig wordt duidelijk gemaakt in Hoofdstuk 4 en 5.
4
1.3
Plan van aanpak
Om de relatieve beweging van een voertuig te achterhalen aan de hand van camerabeelden zal er gebruikgemaakt worden van perspectieftransformatie. Hierbij zullen de originele camerabeelden geprojecteerd worden op een virtueel grondvlak. In Hoofdstuk 5 zal duidelijk gemaakt worden waarom dit laatste een belangrijke stap is bij het achterhalen van de voortbeweging van een voertuig. Er zal ook een masker worden aangebracht op de beelden om ervoor te zorgen dat enkel een bepaald gebied van het beeld zal worden gebruikt bij het zoeken naar goede features1 . Dit aanbrengen van een masker wordt het bepalen van de region of interest genoemd (zie Hoofdstuk 3). Zoals al eerder vermeld zal er gebruik worden gemaakt van Optical Flow om de camerabeelden te analyseren. Er bestaan hiervoor menige technieken en in Hoofdstuk 2 worden de bekendste wat meer in detail uitgelegd. In dit werk werd gekozen om twee van deze technieken te gebruiken. Hierna zullen flowvectoren worden opgesteld (zie Hoofdstuk 4), elk met hun unieke eigenschappen die samen de rotatie en translatie van het voertuig bepalen (zie Hoofdstuk 5). Bij deze laatste stap zal er ook gebruik worden gemaakt van enkele regularisatietechnieken (zie Hoofdstuk 6). In het eerste deel zijn het de getransformeerde beelden die gebruikt worden voor de analyse. Hierbij wordt met andere woorden Optical Flow toegepast op de teruggeprojecteerde beelden om daarna via de verkregen flowvectoren de relatieve beweging te achterhalen. In het tweede deel wordt Optical Flow meteen op de originele camerabeelden toegepast en zijn het de bekomen flowvectoren die getransformeerd worden. De resultaten van de uitgevoerde experimenten worden voorgesteld in hoofdstuk 7. Hierbij wordt onder andere de performantie en de precisie van de gebruikte methodes besproken. Figuur 1.2 geeft de verschillende stappen weer die genomen worden tijdens het proces van deze voorgestelde oplossing.
1 Features zijn interessante punten in een beeld, zoals bijvoorbeeld hoekpunten, waarmee een omgeving of object beschreven kan worden
5
Camerabeelden
Camerabeelden
Perspectieftransformatie
Region of interest via masker
Region of interest via masker
Optical Flow
Optical Flow
Flowvectoren
Flowvectoren
Perspectieftransformatie
Regularisatie
Regularisatie
Translatie en rotatie bepalen
Translatie en rotatie bepalen
Relatieve beweging
Relatieve beweging
Figuur 1.2: Overzicht van de verschillende stappen tijdens het proces. Links de methodiek waarbij optical flow toegepast wordt op de getransformeerde beelden, rechts de toepassing op de originele beelden waarbij de bekomen flowvectoren getransformeerd worden
6
Hoofdstuk 2
Literatuurstudie 2.1
Visuele Odometrie
Algemeen Het woord odometrie komt van de Griekse woorden odos en metron. Odos verwijst naar een reis of traject en metron betekent meten. Bij odometrie worden sensoren gebruikt om het verschil in locatie en ori¨entatie te bepalen van een voertuig naargelang het voertuig zich voortbeweegt. Onder deze sensoren vallen onder andere GPS, Inertial Measurement Unit (IMU) [9], lasers en sonar [39] en het visuele aspect via camera’s (zie verder). Onder dit visuele aspect verstaat men dus ’Visuele Odometrie’. De naam is in feite tot stand gekomen op basis van de gelijkenis met Wheel Odometry. Wheel odometry tracht namelijk ook de relatieve beweging van een voertuig te bepalen, maar dit op basis van het integreren van het aantal omwentelingen van de wielen van het voertuig in functie van de tijd [14]. Alhoewel de term ’Visuele Odometrie’ reeds in 1996 was gebruikt door Mandyam Srinivasan die als Australische bioloog het ori¨entatievermogen van bijen beschreef, werd het pas echt bekend in 2004 na de vermelding in het artikel van Nist´er D. et al. [27]. Bij visuele odometrie wordt de relatieve beweging van een voertuig gemeten aan de hand van beelden van een of meerdere camera’s die op het voertuig gemonteerd zijn. Deze techniek wordt dan ook in het bijzonder toegepast in de robotica- en automobielsector. Sterk gerelateerd hieraan is Simultaneous Localization And Mapping (SLAM), meer bepaald Visual SLAM, waarbij het de bedoeling is de locatie en omgeving van de desbetreffende autonome robot in kaart te brengen aan de hand van camera-beelden. Het gaat hier dan over het mappen van de omgeving, het wegwerken van onzekerheden en eventuele iteratieve stappen waarbij gebruikgemaakt wordt van bundle adjustment 1 [16]. Er wordt vooral gefocust op het globale aspect van het traject, niet zozeer op het real-time karakter. Dat terwijl visuele odometrie zich in principe enkel bezighoudt met het schatten van de huidige beweging van het voertuig, met name het locale aspect van het traject. Hier is de 1 Bundle adjustment kan worden omschreven als het probleem van het verfijnen van een visuele reconstructie om uiteindelijk een zo realistisch mogelijke 3D structuur te bekomen alsook het benaderen van de camera-karakteristieken (standpunt en/of kalibratie-gegevens) [40].
7
real-time performantie net wel een belangrijke factor [32]. Een voordeel van visuele odometrie ten opzichte van wheel odometry is dat visuele odometrie geen negatieve gevolgen overhoudt bij wielslip ten gevolge van bijvoorbeeld een glad wegdek. Visuele odometrie kan bijgevolg een nuttige uitbreiding zijn voor wheel odometry. Evenals voor navigatiesystemen zoals bijvoorbeeld GPS wanneer satellietsignalen niet toegankelijk blijken te zijn (zie 1.1 Probleemstelling). Al sinds de jaren tachtig is men bezig met het bekomen van de relatieve beweging van een voertuig op basis van enkel camerabeelden [6, 11]. En hoewel men al meer dan 30 jaar met dit concept bezig is, dateert het slechts van een kleine 10 jaar geleden dat het gebruik van camerabeelden hierbij centraal staat [10]. Er werd toen meer aandacht gegeven aan sensor-gebaseerde systemen zoals lasers en sonar [39]. Dit had namelijk verschillende redenen [33]: • vele algoritmes werkten enkel offline en maar met een beperkte frame-rate, • er waren processoren nodig met een grote rekenkracht, • de meeste algoritmes waren zeer complex of enkel ontworpen voor specifieke camera’s, • het merendeel van de methodes ging uit van statische sc`enes en ging de mist in bij dynamische sc`enes waarbij bijvoorbeeld andere voertuigen voorbij komen, • bij het bepalen van de relatieve beweging zijn meestal vele kenmerkende punten nodig in het beeld en wanneer er maar weinig textuur in het beeld zit, bijvoorbeeld bij een uniform wegdek, zijn er ook maar weinig kenmerkende punten waardoor de meeste algoritmes falen. Door de jaren heen kampte visuele odometrie dan ook met heel wat problemen die dienden verholpen te worden om vooruitgang te kunnen boeken. Zo was er onder andere de gevoeligheid aan de slechte kwaliteit van het automatisch tracken van punten in opeenvolgende beelden [2], enkel de mogelijkheid om met omnidirectionele camera’s te werken [34] of gewoon de onbekwaamheid om de gelijktijdige rotatie en translatie van het voertuig te kunnen duiden [18]. Desalniettemin is het zo dat er in de tussentijd een stevige wiskundige basis is uitgedacht om de problemen, die gepaard gaan met visuele odometrie te verhelpen [1, 21, 27]. En het is bijvoorbeeld in het werk van Nist´er D. [25] dat het five-point relative pose probleem2 wordt opgelost. Uit de literatuur blijkt ook dat Nist´er et al. de eersten waren om een real-time monocular3 SLAM-systeem te ontwikkelen zonder gebruik te maken van eerder opgenomen beelden van de omgeving [28].
Bestaande toepassingen De reeds ontwikkelde oplossingen die zich baseren op visuele odometrie kunnen in feite in drie categori¨en worden verdeeld. 2
Het probleem bestaat uit het vinden van de mogelijke oplossingen voor het relatieve camerastandpunt bepaald aan de hand van twee gekalibreerde beelden waarbij 5 overeenkomstige punten tussen de beelden gegeven zijn. 3 Het niet laten overlappen van de camerabeelden, vergelijkbaar met het zicht van bijvoorbeeld vissen.
8
Ten eerste is er de aanpak met omnidirectionele camera’s waar Tardif et al., 2008 [38] en Scaramuzza et al., 2009 [33] toe behoren. In [38], stellen Tardif et al. een oplossing voor waarbij op incrementele wijze aan 3D-mapping wordt gedaan op basis van Structure From Motion (SFM)4 . Hierbij wordt niet gebruikgemaakt van bundle adjustment, maar wordt de rotatiebepaling helemaal gescheiden van de translatiebepaling. De rotatie wordt namelijk bepaald via punten op oneindig (liggen met andere woorden zeer ver weg) en de translatie op basis van de gereconstrueerde 3D-map. Slechte overeenkomsten worden verwijderd via het preemptive RANSAC 5 -principe [26]. Wat hier op te merken valt is het gebruik van meerdere enkelvoudige camera’s om het omnidirectionele effect na te bootsen. Zeer goede resultaten werden behaald op een afstand van maar liefst 2,5km. In [33] wordt aangetoond dat de beweging van voertuigen beschreven kan worden aan de hand van slechts ´e´en parameter. Het idee hierachter is dat er telkens een centrum van rotatie (Instantaneous Center of Rotation ICR) bestaat en dat het voertuig steeds een circulaire beweging maakt rondom dit punt. Dit zorgt er ook voor dat het verwijderen van uitschieters (bepalen van de inliers) significant kan worden versneld. Ten tweede zijn er de oplossingen die werken met stereo camera’s zoals bij Obdrz´alek et al., 2010 [30] of Kitt et al., 2010 [20]. In [30] wordt het probleem van de zes vrijheidsgraden dat gepaard gaat met het bepalen van de relatieve beweging op basis van 3D-beelden aangepakt via een strategie op basis van stemmingen. Rotatie wordt namelijk bepaald via een soort stemming waarbij de rotatie die gepaard gaat met een bepaalde vector gewicht krijgt naargelang de afstand van het bijhorende punt tot de camera. Na de rotatie volgt de translatie die op een soortgelijke manier wordt bepaald. Bij [20] opteert men ervoor om een Iterated Sigma Point Kalman Filter (ISPKF) te gebruiken in combinatie met een op RANSAC gebaseerde verwijdering van uitschieters. De ISPKF kan men voorstellen als een op visuele odometrie gebaseerde Kalman Filter6 . En ten derde zijn er de systemen die slechts gebruikmaken van ´e´en camera met een standaard lens, hieronder vallen Campbell et al., 2005 [7] en Van Hamme et al., 2012 [41]. In [7] werden de problemen van het inschatten van de diepte van de omgeving en de dualiteit tussen translatie en rotatie aangepakt door een camera bovenop de gebruikte robot te bevestigen waarbij de camera lichtjes naar beneden werd gericht waardoor meer van het grondvlak zichtbaar was dan de lucht. Het beeld werd vervolgens verdeeld in drie delen; grondvlak, horizon en lucht. Het grondvlak werd gebruikt om de translatie na te gaan, het luchtgedeelte om de rotatie te bepalen. Hiervoor werd optical flow (zie verder) gebruikt. Experimenten werden wel enkel op kleine schaal uitgevoerd. Bij [41] wordt er gebruikgemaakt van projectie van de 3D beelden op een virtueel grondvlak. In dit virtuele grondvlak worden kenmerkende punten gekozen via Harris Corner detectie waarna deze teruggeprojecteerd worden op het grondvlak in de 3D-beelden rekeninghoudend met de onzekerheden die hiermee gepaard gaan. Aan de hand van een Hough-gebaseerd systeem 4
Hierbij wordt een 3D reconstructie gemaakt van de omgeving op basis van 2D camerabeelden van verschillende standpunten. 5 RANdom SAmple Consensus is een iteratieve methode om parameters van een bepaald wiskundig model te schatten aan de hand van een dataset die uitschieters bevat. Het is de bedoeling om op basis van willekeurige samples uit deze dataset de inliers van de outliers te onderscheiden. 6 Via een Kalman filter wordt een bepaald proces wiskundig gemodelleerd. Aan de hand van een transitiemodel en ruizige observaties wordt op elk gewenst ogenblik de staat van het proces geschat.
9
wordt de beweging in deze onzekerheidsmodellen van het grondvlak bepaald. Een voordeel van het werken met deze terugprojectie is dat er nog steeds zinvolle schattingen kunnen gemaakt worden wat de relatieve beweging betreft zelfs al zijn er maar enkele features voorhanden. Dit komt door de vermindering van de vrijheidsgraden door de projectie op het virtuele grondvlak. Een bescheiden aantal experimenten toont een nauwkeurigheid aan van 8% afwijking op het afgelegde traject. Het principe van de projectie van de camerabeelden naar een virtueel grondvlak zal ook in dit werk gebruikt worden.
2.2
Optical Flow
Algemeen Doorheen de jaren zijn er verscheidene definities voor optical flow gepubliceerd geweest. De meest gangbare is deze van Horn(1986) en leunt het sterkst aan bij de hedendaagse toepassingen: ”De ogenschijnlijke beweging van heldere patronen die waargenomen worden door een camera die relatief ten opzichte van de waar te nemen objecten beweegt, wordt optical flow genoemd”. Er wordt met andere woorden gezocht naar de verschuiving van overeenkomstige patronen (dit op basis van de lichtsterkte) bij opeenvolgende beelden. Mensen en dieren maken hier zelfs onbewust de hele tijd gebruik van om allerlei beweging rondom zichzelf in te schatten. Het algoritme dat deze definitie toepast, zorgt ervoor dat de te onderzoeken beelden onderverdeeld worden in zeer kleine hokjes. Men kan deze hokjes beschouwen als potenti¨ele features van het beeld. De grootte van deze hokjes is instelbaar afhankelijk van het gebruikte algoritme, maar omvat steeds meerdere pixels. Voor elk hokje wordt de verschuiving tussen twee opeenvolgende frames berekend. Een opmerking die hier kan gemaakt worden is dat het algoritme uitgaat van verschuivingen die lokaal constant zijn. Dit wil zeggen dat men aanneemt dat naburige pixels dezelfde verschuiving ondergaan. Daarnaast houdt men ook vast aan het feit dat de lichtintensiteit van de pixels hetzelfde blijft tussen twee opeenvolgende beelden [2]. In Figuur 2.1 wordt een simplistisch voorbeeld gegeven waarbij de verschuiving van objecten wordt nagegaan aan de hand van optical flow.
Figuur 2.1: Aan de linkerkant wordt weergegeven hoe twee objecten verschoven worden gedurende twee opeenvolgende beelden. Rechts wordt deze verschuiving weergegeven aan de hand van vectoren.
10
Men kan de bestaande algoritmes die optical flow toepassen onderverdelen in twee categori¨en, namelijk dense optical flow en sparse optical flow. Bij dense optical flow wordt de eerder genoemde te berekenen verschuiving bepaald voor elk hokje in de afbeelding. Bij sparse optical flow daarentegen worden er slechts een beperkt aantal features gebruikt. Een voorbeeld van zo’n dense optical flow algoritme is de methode van Horn en Schunck [17] (zie verder). Het voordeel hierbij is dat men zich niet moet bezighouden met het bepalen welke features uit het beeld zullen worden gebruikt, maar het heeft ook het nadeel minder goed bestand te zijn tegen ruis. Wat sparse optical flow betreft is de methode van Lucas-Kanade [23] veruit de populairste methode. Hierbij gaat men uit van een zekere lokale gelijkheid wat de textuur betreft. Dit maakt de methode robuuster tegen ruis. Het nadeel bij deze methodiek is dat er een kleiner bewegingsveld wordt bekomen daar slechts een beperkt aantal features worden gebruikt. Desondanks het kleinere bewegingsveld wordt sparse optical flow verkozen boven dense optical flow vanwege het beter bestand zijn tegen ruis [7, 33].
Wiskundige voostelling Het standaard uitgangspunt bij optical flow is het feit dat de lichtintensiteit van een object gedurende een zeer kort interval δt constant blijft. Om dit wiskundig uit te drukken, wordt de lichtsterkte van een bepaald punt (x, y) op tijdstip t voorgesteld door I(x, y, t). Men kan vervolgens aannemen dat bij tijdstip t+δt dezelfde lichtsterkte bij een naburig punt in het beeld kan gevonden worden. Hierbij wordt er uitgegaan van het feit dat er zich slechts kleine verschuivingen hebben voorgedaan tussen t en δt. Dit kan geschreven worden als: I(x, y, t) = I(x + δx, y + δy, t + δt)
(2.1)
Dit is tevens ook de eerste restrictie die wordt opgelegd. De rechterkant van de vergelijking kan worden ontbonden via Taylorreeksontwikkeling tot het volgende: I(x + δx, y + δy, t + δt) = I(x, y, t) +
∂I ∂I ∂I δx + δy + δt + h.o.t. ∂x ∂y ∂t
(2.2)
Waar h.o.t. staat voor ’hogere orde termen’. Indien we vergelijking 2.1 invullen met de bovenstaande reeksontwikkeling en de hogere orde termen verwaarlozen (uitgaande van een kleine verschuiving) bekomen we volgende vergelijking: ∂I dx ∂I dy ∂I + + =0 ∂x dt ∂y dt ∂t dy Indien men stelt dat u = dx dt , v = dt , Ix = uiteindelijk uit op onderstaande vergelijking.
∂I ∂x ,
Iy =
Ix u + Iy v + I t = 0
(2.3) ∂I ∂y
en It =
∂I ∂t
dan komt men (2.4)
Hierbij duidt (Ix , Iy ) op de gradi¨ent van de lichtintensiteit, It op de tijdsgradi¨ent en (u, v) op de zogenoemde flow vector v en het is net deze flow vector die wordt gezocht. De bovenstaande uitdrukking heeft de vorm van een rechte lijn wat ervoor zorgt dat de te bekomen flow vectoren op deze lijn dienen te liggen. Dit is tevens de eerste restrictie die wordt opgelegd. De lijn blijkt orthogonaal te liggen ten opzichte van de richting van
11
de gradi¨ent van de lichtintensiteit wat een belangrijke relatie aan het licht brengt. De optical flow kan namelijk enkel in de richting van de gradi¨ent berekend worden. Wanneer bijvoorbeeld een set features in de richting van deze gradi¨ent beweegt, is het mogelijk om de optical flow hiervan te bepalen, maar wanneer deze set features in een richting orthogonaal ten opzichte van de gradi¨ent zou bewegen wordt het al veel lastiger of zelfs onmogelijk om de optical flow hiervan te achterhalen. Dit probleem staat bekent als het aperture-probleem. Dit probleem zou echter wel vermeden kunnen worden als men er voor zorgt dat er steeds een gradi¨ent aanwezig is in twee richtingen, zoals bij hoeken, maar dit leidt onherroepelijk tot een nog schaarser flowveld.
Verschillende technieken Door de jaren heen zijn er ontzettend veel manieren uitgewerkt om optical flow te berekenen. In het overzicht van Beauchemin [2] worden maar liefst zes verschillende klassen besproken, zelfs zonder het te hebben over de methodes die zich baseren op feature detectie. Hieronder zal er telkens een korte uitleg volgen over enkele van de meest gebruikte technieken. Hiertoe behoren de methode van Horn en Schunck [17], deze van Lucas en Kanade [23] en het algoritme van Gunnar Farneb¨ack [13]. Als laatste techniek wordt ook nog deze van Michael Tao et al. [37] besproken, wat een van de recentste methodes is op vlak van berekenen van optical flow. Voor een uitgebreider overzicht wordt er verwezen naar het werk van Peter O’Donovan [31]. Het is de methode van Lucas en Kanade [23] en het algoritme van Gunnar Farneb¨ack [13] die gebruikt werden in dit werk. Horn en Schunck Als eerste wordt de methode van Horn en Schunck [17] kort toegelicht. Deze methode wordt als een van de klassiekers beschouwd op vlak van optical flow. Enerzijds wordt er uitgegaan van de hierboven vernoemde restrictie op basis van het constant blijven van de lichtintensiteit, maar anderzijds legt men ook een zekere beperking op wat de gelijkmatigheid van de verschuiving betreft. De gedachte hierbij is dat het flowveld steeds gelijkmatig varieert en slechts weinig discontinu¨ıteiten vertoont. Deze nieuwe restrictie kan omgezet worden naar volgende vergelijking: 2
E =
�
∂u ∂x
�2
+
�
∂u ∂y
�2
+
�
∂v ∂x
�2
+
�
∂v ∂y
�2
(2.5)
Hierbij is het de bedoeling om het kwadraat van de grootte van de variatie van de flow ∂u ∂v ∂v vector v = (u, v) te minimaliseren. ∂u ∂x , ∂y en ∂x , ∂y stellen telkens de variatie voor in de twee dimensies voor respectievelijk de u- en v component. E symboliseert hier de lichtintensiteit bij punt (x, y) op tijdstip t. De fout hierbij wordt beschouwd als de fout van de flowvector ten opzichte van zijn buren. Indien de vector significant verschillend is zal de gradi¨ent van de flow vectoren hetzij in de x-richting, hetzij in de y-richting relatief groot zijn. Het is uiteindelijk de som van de fout op de voorgaande vergelijking en de fout bij vergelijking 2.4 die dient geminimaliseerd te worden.
12
We kunnen de totale fout als volgt beschrijven: �� � � �2 � �2 � �2 � � � 2 ∂u ∂u ∂u ∂u E2 = dxdy (Ix u + Iy v + It ) + α2 + + + ∂x ∂x ∂x ∂x
(2.6)
De eerste term stelt de restrictie op basis van lichtsterkte voor (vergelijking 2.4), de tweede de restrictie op basis van gelijkmatige variatie (vergelijking 2.5) welke vermenigvuldigd wordt met een constante wegingsfactor α2 . Wat er dus eigenlijk gebeurt, is dat de totale fout bij de flow vector van elke pixel gesommeerd wordt. Deze fout kan er enerzijds op wijzen dat de flow vector verschilt van de gradi¨enten, maar anderzijds ook dat er een gebrek aan gelijkmatigheid in verschuiving is bij een bepaald aantal pixels. Voor een verdere en gedetailleerde uitwerking van deze vergelijking wordt er verwezen naar [17]. Voor de rest kan men ook nog zeggen dat deze methode gebruikmaakt van alle pixels in het beeld, wat ervoor zorgt dat deze tot de categorie van dense optical flow behoort. Een opmerking die hier nog dient gemaakt te worden is dat uit de literatuur blijkt dat deze methode als lichtelijk verouderd wordt bestempeld. Het is zelfs zo dat men eerder methodes zoals deze van Lucas en Kanade [23] of Farneb¨ack [13] aanraadt om te gebruiken. Lucas en Kanade Ten tweede volgt het algoritme van Lucas en Kanade [23] wat wellicht als een van de populairdere algoritmes kan omschreven worden. Deze methode steunt ook op het constant blijven van de lichtintensiteit (vergelijking 2.4), maar gaat er ook van uit dat naburige pixels dezelfde verschuiving ondergaan. Er wordt maar een bepaald aantal features gebruikt wat maakt dat deze methode sparse maakt. Het is aan de hand van de kleinste kwadratenmethode en een wegingsfactor dat men de optical flow van het punt (x, y) uiteindelijk kan bepalen: E=
�
W 2 (p)(Ix (p)u + Iy (p)v + It (p))
(2.7)
p∈Ω
Waar opnieuw E de lichtintensiteit bij punt (x, y) op tijdstip t symboliseert, Ix (p), Iy (p) en It (p) de gradi¨enten zijn van de naburige pixel p, (u, v) stelt de optical flow vector v voor van het punt (x, y) en W (p) is de wegingsfactor die geassocieerd wordt met de naburige pixel p. Ω met grootte n bepaalt het aantal naburige pixels dat in rekening wordt gebracht. Deze wegingsfactor wordt gebruikt om naburige pixels die op een grotere afstand liggen van het gegeven punt (x, y) een kleinere impact te laten geven. Op deze manier wordt de invloed van naburige pixels die verder liggen en wellicht al wat meer verschillen wat de gradi¨enten betreft verlaagd. Het uiteindelijke systeem heeft echter meer vergelijkingen dan onbekenden. Als compromis wordt de kleinste kwadratenmethode methode (least-squares in het Engels) gebruikt om volgende vergelijking op te lossen: AT W 2 Av = AT W 2 b of
T
v = (A A)
13
−1
T
A b
(2.8) (2.9)
Hierbij stelt A een vector voor van de spatiale gradi¨enten van alle naburige pixels, W stelt de gewichten voor elke naburige pixel voor en b is een vector die alle tijdsgradi¨enten omvat. Het oplossen van 2.9 kan men ook als volgt noteren: �
� � � n Ix (pi )2 Vx = �n i=1 Vy i=1 Iy (pi )Ix (pi )
�−1 � � � �n n − I (p )I (p ) I (p )I (p ) x i t i i=1 x i y i � �i=1 n n 2 I (p ) I − y i i=1 i=1 y (pi )It (pi )
(2.10)
Een verdere en gedetailleerde uitwerking kan gevonden worden in [23]. Deze methode heeft verscheidene voordelen, maar de bijzonderste is toch dat het bepalen van de flow vector lokaal gebeurt, terwijl Horn en Schunck eerder een globale aanpak hanteren, wat maakt dat er aanneembare resultaten kunnen bekomen worden zonder daarvoor het hele beeld nodig te hebben. Ook het gemak in implementatie en de snelheid van het algoritme behoren tot de voordelen. Een nadeel van deze methode is dat het minder goed bestand is tegen grote verschuivingen in het beeld, aangezien telkens maar gekeken wordt naar een bepaald aantal naburige pixels. Om dit probleem te verhelpen kan er gebruikgemaakt worden van beeldpyramides 7 . En naargelang er omhoog wordt gegaan in de pyramide, worden kleinere verschuivingen verwijderd en worden grote verschuivingen omgevormd tot kleine verschuivingen. Deze uitbreiding wordt voorgesteld in [5] en het is deze methode die tevens wordt gebruikt in dit werk. Gunnar Farneb¨ ack Ten derde is er de methode van Gunnar Farneb¨ack [13] dat zich baseert op het concept van ontbinden in veeltermen. Het idee hierachter is dat men de naburige pixels van een bepaald punt (x, y) kan benaderen via een veelterm, meer bepaald een kwadratische veelterm. Praktisch kan dit als volgt beschreven worden: f (x) ∼ xT Ax + bT x + c
(2.11)
Waarbij A een symmetrische matrix is, b een vector en c een constante. Deze co¨effici¨enten worden bepaald aan de hand van een gewogen kleinste kwadratenmethode. Deze wegingsfactor is gelijkaardig aan deze uit de voorgaande methode. Voor een gedetailleerde uitwerking van deze veelterm wordt er verwezen naar [13]. Maar indien er uitgegaan wordt van een ideale translatie d over het hele beeld en een traag vari¨erend flowveld, dan wordt er uiteindelijk volgende uitdrukking bekomen die dient geminimaliseerd te worden: � W (Δx) � A(x + Δx)d(x) − Δb(x + Δx) �2 (2.12) Δx∈Ω
Ω stelt ook hier de naburige pixels voor,W (Δx) de wegingsfactor per naburige pixel en d(x) de verschuiving van de pixel in kwestie. Opnieuw verwijs ik naar [13] voor de gedetailleerde uitwerking van de verschillende parameters. Het komt er alleszins op neer dat op een iteratieve wijze wordt gezocht naar de kleinste fout bekomen door de voorgaande 7 Bij beeldpyramides maakt men een reeks afbeeldingen uitgaande van het originele beeld waarbij de resolutie telkens verlaagt in opklimmende volgorde. Dit wordt gedaan door telkens bepaalde kolommen en rijen uit het onderliggende beeld te verwijderen en nieuwe pixels te vormen aan de hand van 5 pixels uit het onderliggende beeld. Wanneer men dan deze afbeeldingen op elkaar zou leggen (grootste beeld onderaan, kleinste bovenaan) bekomt men als het ware een pyramide.
14
uitdrukking. Aangezien ook deze methode gebruikmaakt van alle pixels in het beeld valt deze onder de noemer dense. Een nadeel van deze methode is dat er uitgegaan wordt van een traag vari¨erend flowveld waardoor discontinu¨ıteiten worden uitgesmeerd en dus incorrect in rekening worden gebracht. Ook hier kunnen grote verschuivingen een probleem veroorzaken, maar om dit tegen te gaan werd voorgesteld om met meerdere schalen te werken wat betreft het rekeninghouden met de naburige pixels. Dus eerst een grove schaal gebruiken om een idee te krijgen van de verschuiving om daarna iteratief te verfijnen zodat steeds een accurater resultaat bekomen wordt. SimpleFlow Ten slotte wordt het SimpleFlow algoritme van Michael Tao et al. [37] kort besproken. Hier wordt ook gesteund op de klassieke restrictie wat betreft de constante lichtintensiteit en wordt als het kwadratisch verschil tussen intensiteiten weergegeven: e(x, y, u, v) =� It (x, y) − It+1 (x + u, y + v) �2
(2.13)
De notatie is hierbij wel lichtelijk verschillend met deze uit de voorgaande vergelijkingen. It (x, y) betekent hier de intensiteit van punt (x, y) van het beeld op tijdstip t en analoog stelt It+1 (x + u, y + v) de intensiteit van punt (x + u, y + v) van het beeld op tijdstip t + 1 voor. Daarnaast gaat men ook uit van een lokale gelijkmatigheid wat de verschuiving betreft. Nog een vereiste is dat elke flow vector van elk punt in het beeld een goeie duiding is van de verschuiving, alsook representatief is voor naburige punten die behoren tot een bepaald gebied Ω. Door het meegeven van bepaalde informatie aan Ω om de beste flow vector (u, v) voor het punt (x, y) te bepalen, kan een verzameling flow vectors N beschouwd worden waaruit kan gekozen worden om zo te kunnen voldoen aan de restrictie van constante intensiteit. Dit wordt gedaan aan de hand van het minimaliseren van de fout die men bekomt bij vergelijking 2.13. Men gebruikt hierbij ook gewichten om aan te geven wat de onderlinge verhouding is tussen pixels zowel ruimtelijk als inhoudelijk (hun intensiteit). De vector (u0 , v0 ) is de vector met de laagste kost voor het punt (x0 , y0 ) en kan als volgt uitgedrukt worden: � ωd ωc e(x, y, u, v) (2.14) (u0 , v0 ) = arg min (u,v)∈N (x,y)∈Ω
met
ωd = exp(− � (x0 , y0 ) − (x, y) �2 /2σd2 ) ωc = exp(− � I�t (x0 , y0 ) − I�t (x, y) �2 /2σ 2 ) c
(2.15) (2.16)
ωd en ωc zijn gewichten eigen aan de pixels. σd2 slaat op de variantie van het spatiale domein en bepaalt het aantal punten die mee in rekening worden genomen. σc2 duidt op de varantie van het bereik, met andere woorden hoe verschillend twee intensiteiten mogen zijn. Aangezien hier enkel met lokale verbanden wordt gewerkt is ook deze methode minder goed bestand tegen grote verschuivingen, maar door ook gebruik te maken van beeldpyramides kan dit probleem verholpen worden. Wat nog dient op te merken is dat deze methode niet iteratief is, maar ook dat slechts een beperkt aantal features binnen gebieden met een uniforme verschuiving wordt gebruikt bij de berekeningen wat de snelheid aanzienlijk opdrijft. Desondanks niet alle punten in het beeld gebruikt worden in de berekeningen,
15
zal er toch voor elk punt een flow vector bepaald worden en dit via interpolatie. Op deze manier hoort deze methode toch bij de dense optical flow algoritmes. Al kan deze methode ook wel als een hybride tussen dense en sparse beschouwd worden. Wat wel een nadeel kan zijn van de interpolatie is dat kleine objecten, die zich bevinden in een gebied waarbinnen zich slechts weinig significante verschuivingen voordoen, kunnen over het hoofd gezien kunnen worden en dit net door de interpolatie.
2.3
Feature extractie
Bij de methode van Lucas en Kanade [23] wordt maar een beperkt aantal features gebruikt om de optical flow te achterhalen. Om te bepalen welke features hiervoor worden gebruikt en welke niet kan men beroep doen op verschillende technieken: Harris corners [15], ”good features to track” [35], SIFT [22], SURF [3], Canny randdetectie [8] of gewoon willekeurige selectie van pixels. Hieronder volgt een korte toelichting bij deze technieken. Harris Corners worden bepaald door punten waar twee randen samenkomen en baseert zich hiervoor op het berekenen van een covariantiematrix. De methode van Shi en Tomasi, good features to track (GFTT) genaamd, is gebaseerd op de Harris Corners in dat opzicht dat er gezocht wordt naar punten waar er voldoende variatie is in twee orthogonale richtingen. Scale Invariant Feature Transform (SIFT) gebruikt een gaussiaans filter waar het het beeld eerst mee laat convolueren met verschillende schalen. Daarna wordt via Difference of Gaussian (DoG) gezocht naar de key-points (de gezochte features) die in feite de lokale minima en maxima zijn van het DoG-beeld. Bij Speeded-Up Robust Features (SURF) wordt gebruikgemaakt van de Hessian-Laplace operator. Deze operator zoekt naar punten in het beeld die sterke gradi¨enten vertonen in twee orthogonale richtingen. Het algoritme voor Canny randdetectie zoekt in de eerste stap naar alle randpixels in het beeld. Als tweede stap wordt het beeld onderverdeeld in kleine blokken waarbij wordt gezocht naar de randpixel die het dichtst bij het midden van dit blok zit. Wanneer zo’n pixel wordt gevonden, wordt deze als feature bestempeld van dat blok. Uit het onderzoek van Navid Nourani-Vatani et al. [29] blijken de Canny randdetectie, de Harris Corners en GFTT het beste te scoren. In dit werk is er dan ook gekozen om te werken met de GFTT-methode van Shi en Tomasi [35].
16
Hoofdstuk 3
Voorbewerking van de beelden De 3D-informatie van de punten afkomstig van de camerabeelden (tweedimensionaal) worden gesimuleerd door te stellen dat alle punten in het grondvlak liggen. Dit maakt het probleem wiskundig gezien makkelijker om op te lossen, maar dit zorgt er daarentegen ook voor dat een zekere robuustheid moet worden ingebouwd daar deze stelling in principe niet geldig is voor alle punten uit het beeld en dus fouten zou kunnen opleveren. Er werd al eerder aangehaald dat er twee delen te onderscheiden zijn in dit werk. Namelijk een eerste deel waarbij optical flow wordt toegepast op de getransformeerde beelden en een tweede deel waarbij optical flow wordt toegepast op de originele beelden en de hierbij verkregen flowvectoren daarna worden gerectificeerd. De uitleg over perspectieftransformatie die hieronder zal volgen geldt dan ook zowel voor het rectificeren van beelden als voor het rectificeren van punten van de flowvectoren. De perspectieftransformatie komt aan bod bij het bespreken van het cameramodel. Daarna wordt het bepalen van de region of interest uitgelegd.
3.1
Cameramodel
De enkelvoudige camera die wordt gebruikt, wordt parallel aan de rijrichting op de motorkap gemonteerd. Verder gaan we uit van het principe van de gaatjescamera (in het Engels: pinhole camera) en wel het ideale geval waarbij er zich geen distortie voordoet. Een gaatjescamera is een camera zonder lens. Er wordt in de plaats gebruikgemaakt van een klein gaatje. Over het algemeen geldt dat hoe kleiner het gaatje is, hoe scherper het beeld is. Om het model van de camera op te stellen dient men een retinaal vlak � en het middelpunt van de perspectiefprojectie C te bepalen. De projectie van een punt uit de sc`ene kan dan gevonden worden als het snijpunt van het vlak � met de rechte die het punt uit de sc`ene en het middelpunt C verbindt. Een voorbeeld hiervan wordt weergegeven in Figuur 3.1 door punt M te projecteren op � waarbij punt m bekomen wordt.
17
Figuur 3.1: Voorbeeld van de perspectiefprojectie
Hierbij staat de ’optische as’ (optical axis in de figuur) loodrecht op het vlak � en gaat door het middelpunt C. Het snijpunt met � wordt het principieel punt c(x0 , y0 ) genoemd. In de meeste gevallen is dit het midden van het beeld waarop geprojecteerd wordt. Wat verder ook nog gedefinieerd dient te worden zijn de gebruikte assenstelsels. In dit werk wordt er net zoals in [41] gebruikgemaakt van drie verschillende co¨ordinaatsystemen, meer bepaald de 3D wereldco¨ ordinaten, de 3D cameraco¨ordinaten en de 2D co¨ordinaten van het uiteindelijk bekomen beeld. Bij de 3D wereldco¨ordinaten wordt een rechtshandig assenstelsel gebruikt waarbij de oorsprong op het wegdek ligt net onder het rotatiecentrum van de wagen. Hierbij dient opgemerkt te worden dat dit assenstelsel gelinkt is met de wagen en de beweging van de wagen zich voordoet als bewegende textuur over een vast vlak. De Z-as staat hierbij loodrecht op het grondvlak en de Y -as staat parallel met de richting van voortbeweging van de wagen. Het assenstelsel van de camera-co¨ordinaten wordt gelijkaardig ingesteld met dat verschil dat de oorsprong in het middelpunt van de projectie van de camera ligt. De Y-as ligt hierbij ook parallel met de kijkrichting en de Xen Z-as worden respectievelijk met de horizontale- en de verticale beeldsensor gealigneerd. Wat het 2D co¨ ordinatensysteem betreft, wordt er gekozen om de oorsprong in de linkerbovenhoek te leggen, de X-as naar rechts te doen wijzen en de Y -as naar beneden. Dit vanwege programmeringsoverwegingen en het feit dat dit overeenkomt met de manier waarop beeldinformatie wordt bijgehouden in het geheugen. Om de perspectiefprojectie van 3D wereldco¨ordinaten naar 2D beeldco¨ordinaten verder te kunnen beschrijven, worden de punten uit het 2D beeld voorgesteld als x = [x y 1 ]T en de punten uit de 3D wereld als X = [X Y Z 1]T . De perspectiefprojectie kan geschreven worden als volgt: x = C [R|t] X (3.1) Matrix C stelt hierbij het product van de inwendige bovendriehoeksmatrix van de camera (ook wel kalibratiematrix genoemd) en de lineaire projectiematrix voor. Deze bevat de horizontale en verticale schaalfactoren αx en αy en de co¨ordinaten van het principieel punt
18
c(x0 ,y0 ). De lineaire projectiematrix zorgt voor de omzetting van de wereldco¨ordinaten in co¨ordinaten van het camera-assenstelsel. De co¨effici¨enten hiervan geven de eerder genoemde veronderstellingen weer wat betreft de gekozen assenstelsels. De schaalfactoren αx en αy worden bepaalt door respectievelijk het quoti¨ent van de brandpuntsafstand f en de breedte van de pixels eigen aan de camera en het quoti¨ent van f en de hoogte van zo’n pixel. Men kan matrix C als volgt weergeven: 1 0 0 α x 0 x0 C = 0 αy y0 0 0 −1 (3.2) 0 0 1 0 1 0
[R | t] bevat de rotatiematrix R die het wereldse assenstelsel in overeenstemming brengt met het assenstelsel van de camera. Deze rotatiematrix wordt verder nog uitgebreid met vector t die slaat op de 3D translatie tussen de oorsprongen van beide assenstelsels. Maar aangezien er enkel interesse is in de punten in het grondvlak van wereldse assenstelsel, kan men voor alle punten Z gelijkstellen aan 0. Dit resulteert in een uiteindelijke 3x3 homografiematrix H: X x (3.3) x = w y = H Y 1 1
Men kan hierbij nog opmerken dat de homografie slechts tot op een schaalfactor w bepaald hoeft te zijn. Het is echter de bedoeling om de omgekeerde transformatie te bekomen, namelijk beeldpunten projecteren op het wereldse grondvlak. Dit kan simpelweg door het inverse van H te gebruiken zoals in onderstaande vergelijking: x X −1 (3.4) X = W Y = H y 1 1
Opnieuw stelt W hier de schaalfactor voor. De parameters bij de cameramatrix C kunnen gevonden worden via standaard kalibratiemethodes. Zo is het bijvoorbeeld mogelijk om aan de hand van een 3D-object waarvan we de geometrie kennen, te zoeken naar de best passende set parameters zodat de berekende projectie van de structuur overeenkomt met de waargenomen projectie op het beeld.In het werk van Bouguet [4] worden er echter nog meer kalibratiemethodes uit de doeken gedaan, maar hier zal in dit werk niet verder op in gegaan worden. Bij een camera met een vaste zoom zullen deze parameters constant blijven en moeten deze dan in principe ook maar 1 keer berekend worden. Vector t is constant aangezien de wereldco¨ordinaten vasthangen aan het voertuig, deze wordt manueel ingevuld. De rotatiematrix R wordt opgebouwd aan de hand van drie rotaties, telkens rondom een van de assen. Een van de meest gangbare beschrijvingen van deze rotaties is door yaw, pitch en roll wat respectievelijk de rotaties rond de Z-, X- en Y-as zijn. Deze rotaties kunnen relatief gemakkelijk gemeten worden in wereldco¨ordinaten. Hierbij dient wel nog opgemerkt te worden dat in principe enkel de yaw als constant kan aanschouwd worden tijdens het rechtlijnig voortbewegen van de wagen. Pitch en roll zijn daarentegen afhankelijk van de ophanging van de wagen en kunnen dus niet als constant worden beschouwd daar deze schommelen rond de kalibratiewaarden die bekomen zijn bij stilstand.
19
In Figuur 3.2 wordt het virtuele grondvlak getoond samen met het overeenkomstige camerabeeld.
Figuur 3.2: Voorbeeld van een beeld afkomstig van de camera op de wagen (links) en zijn teruggeprojecteerde virtuele grondvlak (rechts)
3.2
Region of interest
Punten die zich ver van de wagen bevinden (boven of dicht bij de horizon) en in de meeste gevallen ook niet tot het grondvlak behoren, zouden tot slechte resultaten kunnen leiden. Dit is hoofdzakelijk te wijten aan de uitsmering (door de perspectieftransformatie) van objecten die in de originele beelden een zekere hoogte bezitten. Daarom wordt er gekozen om slechts een bepaald stuk uit de beelden te gebruiken. Dit wordt de region of interest genoemd en wordt bekomen door een binair masker aan te brengen waarbij de witte pixels een 1 voorstellen en de zwarte pixels een 0. Het spreekt voor zich dat de witte pixels de region of interest vormen. Nog een moeilijkheid die hiermee kan verholpen worden, is de weerspiegeling van de omgeving door de motorkap. Hier kunnen ook foute resultaten door veroorzaakt worden dus ook de motorkap verhullen door het masker is hier de oplossing. In Figuur 3.3 worden de maskers voor zowel de reeds getransformeerde beelden als de originele beelden weergegeven. Bij 6.2b wordt het masker toegepast op de getransformeerde beelden terwijl bij 6.2c het masker wordt aangebracht op de originele beelden.
20
(a)
(b)
Figuur 3.3: De gebruikte maskers waarbij de witte pixels de region of interest voorstellen (links) en een voorbeeldframe met de region of interest roodgekleurd (rechts).
21
Hoofdstuk 4
Bepaling van de flowvectoren In dit hoofdstuk zal uitgelegd worden hoe de flowvectoren, de vectoren die de verschuiving tussen twee beelden voorstellen, worden bekomen.
4.1
Features
Een van de twee methodes van optical flow die in dit werk gebruikt worden, behoort tot de categorie dense en gebruikt alle pixels om tot optical flow te komen. Deze sectie is dus in principe enkel relevant voor de methode van Lucas en Kanade [23]. En zoals al eerder werd vermeld, wordt er met de methode van Shi en Tomasi [35] gewerkt bij het bepalen welke features al dan niet zullen gebruikt worden bij het samenstellen van de flowvectoren. Hieronder zal deze methode even kort toegelicht worden. Voor iedere te onderzoeken pixel zal nagegaan worden hoezeer deze pixel deel uitmaakt van een hoek in het beeld. Dit gebeurt op basis van het berekenen van de minimale eigenwaarde van de covariantiematrix van de gradi¨enten in kwestie. De covariantiematrix wordt hierbij bepaald als volgt: � � �2 � � dI dI �2 dI Ω dx Ω dx dy �2 � � �2 M = � � dI dI dI Ω
dx dy
Ω
(4.1)
dy
Waarbij Ω een gebied met vaste grootte rond de desbetreffende pixel voorstelt. De gradi¨enten worden hier aan de hand van een Sobelfilter berekend. De Sobelfilter maakt gebruik van Gaussiaanse uitsmering wat het beter bestand maakt tegen ruis. Het berekenen van de minimale eigenwaarde van de covariantiematrix wordt aanzien als een kwaliteitsmeting die aangeeft in hoevere deze pixel deel uitmaakt van een hoek in het beeld. Hoe hoger deze waarde, hoe meer deze pixel als hoek wordt aanzien. Na het bepalen van deze waarde voert het algoritme een non-maximum suppression uit. Enkel het lokale maximum uit een 3x3 omgeving wordt namelijk bijgehouden. Aan de functie wordt vervolgens een waarde meegegeven onder de vorm van een kwaliteitsniveau. Het is het product van dit kwaliteitsniveau met de grootste minimale eigenwaarde uit het beeld dat de drempelwaarde vormt waarbij waarden die hieronder liggen worden verwijderd. Bijvoorbeeld als de beste hoek overeenkomt met een minimale eigenwaarde van 1500 en het meegegeven kwaliteitsniveau bedraagt 0.01, dan worden hoeken met een waarde onder 15 verwijderd.
22
Uiteindelijk wordt er ook nog gekeken of er in de buurt (grootte van de omgeving wordt meegegeven aan de functie als minDistance) van de pixel in kwestie nog een betere hoek is. Is dit het geval dan wordt deze pixel bijgehouden in de plaats. Deze laatste stap staat in principe los van de voorgaande non-maximum suppression, maar kan als gelijkaardig beschouwd worden. Om ervoor te zorgen dat er een gelijk aantal features wordt bepaald zowel aan de linkerals rechterkant van het beeld, wordt het beeld opgesplitst in twee of zes delen. Meer features aan ´e´en kant zou immers kunnen zorgen voor een afwijking naar links of rechts (afhankelijk van de situatie) doordat steeds wordt gekeken hoe deze features liggen ten opzichte van het middelpunt van de achterste as van de wagen (zie Hoofdstuk 5). In het eerste geval wanneer optical flow wordt losgelaten op de getransformeerde beelden gebeurt de opsplitsing in zes delen. Namelijk drie delen aan de linkerzijde en drie delen aan de rechterzijde. In Figuur 4.1 worden deze zes delen weergegeven. Hierbij worden respectievelijk A en B, C en D en E en F met elkaar vergeleken. A en B stellen elk een vierde voor van het totale beeld, terwijl de andere delen elk een achtste van het totale beeld voorstellen. Dit werd zo gekozen omdat hoe dichter een feature bij de wagen ligt, hoe relevanter hij is vanwege de vervorming van het beeld naargelang de pixels verder van de wagen verwijderd zijn. Verder steunend op dat principe, wordt er ook een vast percentage van het meegegeven maximum aantal te vinden features opgelegd per deel van het beeld. Zo zullen C en D een hoger percentage toegewezen krijgen dan A en B of E en F. In het tweede geval wanneer optical flow wordt losgelaten op de originele camerabeelden wordt het beeld slechts opgesplitst in twee delen aangezien vervorming van het beeld naarmate de feature verder van de wagen zou liggen hier niet aan de orde is.
Figuur 4.1: Het verdelen van het getransformeerde beeld in zes delen om het aantal features in de overeenkomstige delen met elkaar te kunnen vergelijken.
23
4.2
Flowvectoren
Wat de flowvectoren betreft, wordt er geen onderscheid gemaakt tussen de twee gebruikte methodes. Er wordt dus op dezelfde manier omgegaan met de flowvectoren ongeacht of de methode dense of sparse is en ongeacht de hoeveelheid flowvectoren (veel bij dense, minder bij sparse). Er wordt nog even doorgegaan met de voorgaande methode (sparse) om het daarna ook te hebben over het dense optical flow algoritme.
Sparse Eens de features zijn bepaald, treedt de uitbreiding op het algoritme van Lucas en Kanade [5] in werking. Aan de hand van het vorige beeld, het huidige beeld en de posities van de features uit het vorige beeld, zullen de nieuwe posities van deze features in het huidige beeld achterhaald worden. Met andere woorden, er wordt gezocht naar waar de features uit het vorige beeld zich bevinden in het huidige beeld. Hierbij wordt een beroep gedaan op de naburige pixels. De verdere beschrijving van de werking van de methode kan teruggevonden worden in Hoofdstuk 2 . Wanneer er uiteindelijk voor iedere feature in het vorige beeld een feature werd gevonden in het huidige beeld, kunnen deze overeenkomstige koppels verbonden worden tot een flowvector.
Dense De beschrijving van de werking kan opnieuw teruggevonden worden in Hoofdstuk 2, maar het principe bij de dense optical flow methode is nagenoeg gelijkaardig aan dit van de sparse methode. Alleen gaat men hier niet zelf de features bepalen, maar aan de hand van het volledige beeld van het vorige en het huidige frame de momentane optical flow berekenen. Men bekomt hierbij een flowveld waarbij volgende vergelijking geldt: prev(y, x) ≈ next(y + f low(y, x)[1], x + f low(y, x)[0])
(4.2)
Het linkerdeel staat voor een bepaalde pixel in het vorige beeld en het rechterdeel voor de overeenkomstige pixel in het volgende beeld waarbij flow op het flowveld slaat, flow(y,x)[1] de verschuiving in de y-richting voorstelt en flow(y,x)[0] de verschuiving in de x-richting van het beeld voorstelt. Het flowveld wordt pixelgewijs opgesteld en bevat in principe de gezochte flowvectoren. Het flowveld kan dan ook makkelijk worden omgezet naar aparte flowvectoren door het flowveld in kwestie pixelgewijs te overlopen en telkens prev(y,x) te koppelen met next(y + flow(y,x)[1], x + flow(y,x)[0]) tot een flowvector. In Figuur 4.2 worden twee voorbeeldframes weergegeven waarop de verkregen flowvectoren te zien zijn. Op beide ogenblikken wordt er een bocht naar rechts genomen. Enerzijds voor het dense optical flow algoritme toegepast op de getransformeerde beelden (4.2a) en anderzijds voor het sparse optical flow algoritme toegepast op de originele beelden (4.2b).
24
(a)
(b)
Figuur 4.2: Twee voorbeeldframes waarbij de verkregen flowvectoren worden weergegeven, (a) dense optical flow en (b) sparse optical flow
25
Hoofdstuk 5
Translatie en rotatie Uit het vorige hoofdstuk is reeds duidelijk geworden hoe de flowvectoren worden opgesteld, maar nog niet hoe deze de rotatie en de translatie van de wagen kunnen duiden. In dit hoofdstuk zullen verschillende eigenschappen van de flowvectoren aan bod komen en zal duidelijk worden dat de uiteindelijke beweging van de wagen met behulp van deze eigenschappen achterhaald kan worden. Allereerst dient beschreven te worden hoe een wagen precies voortbeweegt. Het principe waar hier op gesteund wordt, heet het principe van Ackermann [36]. Dit legt op dat de assen van de wielen van een wagen uitgelijnd dienen te worden als stralen van cirkels met een gemeenschappelijk middelpunt en dit om het zijwaarts slippen van de wielen bij het nemen van een bocht te voorkomen. Aangezien de achterste as van de wagen vast is, dient dit gemeenschappelijk middelpunt daarom steeds in het verlengde van deze achterste as te liggen. Dit gemeenschappelijke middelpunt is beter bekend als momentane centrum van rotatie of Instantaneous Center of Rotation (ICR). In Figuur 5.1 wordt dit principe weergegeven. Zoals kan worden afgeleid uit de figuur is de bepaling van het ICR eenvoudiger wanneer men slechts tweedimensionaal werkt (vanuit vogelperspectief met andere woorden). Het is dan ook om deze reden dat we de perspectieftransformatie gebruiken.
Figuur 5.1: Voorstelling van het principe van Ackermann
26
Afgaand op het voorgaande is het dus cruciaal om eerst het momentane rotatiecentrum te vinden om dan de uiteindelijke translatie en rotatie te bekomen. Er wordt hiervoor gebruikgemaakt van de reeds verkregen flowvectoren die dienen als beschrijving van hoe de omgeving beweegt ten opzichte van de wagen. Het is namelijk zo dat de flowvectoren in feite koordes zijn van draaicirkels rondom het momentane centrum van rotatie. In Figuur 5.2 wordt de bepaling van dit momentane rotatiecentrum weergegeven.
Figuur 5.2: De bepaling van het Instantaneous Center of Rotation (ICR) van de wagen aan de hand van de flowvectoren u, v en w
Hierbij zijn u, v en w de flowvectoren die de verschuiving van de omgeving weergeven. De draaicirkels worden voorgesteld door b1 , b2 en b3 en de onderste volle blauwe lijn is het verlengde van de achterste as van de wagen. Aangezien de flowvectoren dus als koordes kunnen beschouwd worden, kan het middelpunt van de bijhorende cirkel gevonden worden door middelloodlijnen door deze koordes (blauwe streepjeslijn in Figuur 5.2) te tekenen en het snijpunt hiervan te bepalen. Het effectieve snijpunt bepalen, gebeurt aan de hand van line-line intersection. Hierbij wordt het snijpunt van twee rechten bepaald met behulp van vier punten (twee punten op elke rechte). Het gaat hier dus om de rechten enerzijds gevormd door de middelloodlijn van de flowvector en anderzijds door de achterste as van het voertuig. De bepaling van dit snijpunt komt tot stand via twee determinanten, ´e´en voor de x-co¨ordinaat en ´e´en voor de y-co¨ordinaat. Deze worden hieronder weergegeven in vergelijking 5.1 waar XP staat voor de x-co¨ ordinaat van het snijpunt, YP voor de y-co¨ordinaat en de co¨ordinaten xi en yi voor de co¨ordinaten van de vier punten van beide rechten (i gaande van 1 tot en met 4).
27
�� �� x �� 1 �� �� x 2 � � �� �� �� x 3 �� �� x 4 XP = ��� �x �� 1 �� �� x 2 � � �� �� � �x 3 �� � �x 4
� y1 �� � y2 � � y3 �� � y4 � � 1�� � 1� � 1�� � 1�
� �� � x 1� � � 1 �� � �� � x 2 1� � � � � �� � x 1� � � 3 �� � �� � x 4 1� � � �� � y 1� � � 1 �� � �� � y 2 1� � � � � �� � y 1� � � 3 �� � �� � y 4 1� �
�� ��x �� 1 �� ��x 2 � � �� �� ��x 3 �� ��x 4 YP = ��� �x �� 1 �� ��x 2 � � �� �� ��x 3 �� ��x 4
� y1 �� � y2 � � y3 �� � y4 � � 1�� � 1� � 1�� � 1�
� �� �y 1�� � 1 �� � �� �y2 1�� � � � �� �y 1�� � 3 �� � �� �y4 1�� � �� �y 1�� � 1 �� � �� �y2 1�� � � � �� �y 1�� � 3 �� � �� �y4 1��
(5.1)
Eens het momentane rotatiecentrum is bepaald, kan voor elke flowvector, die als koorde van een cirkel rond het ICR kan beschouwd worden, de middelpuntshoek berekend worden. In Figuur 5.3 worden deze middelpuntshoeken weergegeven door α, β en γ voor respectievelijk de vectoren u, w en v. Deze middelpuntshoek stelt de momentane rotatiehoek voor en zou voor elke vector gelijk moeten zijn. In de figuur is dit het geval maar in de praktijk is een kleine afwijking van elkaar niet uit te sluiten. De hoeken bedragen hierbij 5◦ , maar dat is louter ter illustratie.
Figuur 5.3: Bepaling van de rotatiehoek
28
Aangezien deze rotatiehoek (in theorie) voor elke vector hetzelfde is, kan er op deze manier ook een flowvector getekend laten worden vertrekkend van het middelpunt van de achterste as van de wagen (Mcar ). Op de figuur wordt deze vector voorgesteld door de blauwe vector z met bijhorende rotatiehoek δ. Deze flowvector kan bekomen worden door een koorde (ten opzichte van het ICR) te tekenen vanuit Mcar , waarbij de middelpuntshoek die deze koorde vormt even groot is als de eerder bekomen rotatiehoek. Deze vector z stelt de translatie voor van de achterste as van de wagen. De grootte van deze vector kan makkelijk bepaald worden via driehoeksmeetkunde aangezien de rotatiehoek en de afstand tussen het ICR en Mcar gekend zijn. In Figuur 5.4 wordt deze translatie van iets naderbij bekeken waardoor het makkelijker aan te tonen valt hoe aan de grootte van de vector z gekomen wordt. Punten A en Mcar vormen de vector z, de lengte van vector z (ltot ) wordt bepaald door de som van lengten l1 en l2 of gewoon twee maal lengte l2 . δ stelt de momentane rotatiehoek voor die alle flowvectoren (in theorie) gemeenschappelijk hebben en α is de helft hiervan omdat de middelloodlijn door punt B hiervoor zorgt. De afstand tussen Mcar en ICR wordt voorgesteld door d.
Figuur 5.4: Bepaling van de grootte van de translatie gekenmerkt door de vector z
Hierbij gelden dan volgende vergelijkingen: |l2 | |d| = 2.l2 en δ = 2α � � δ ltot = 2.|d|.sin 2 sin(α) ≈
met
ltot
dus :
29
(5.2) (5.3) (5.4)
Hoofdstuk 6
Regularisatie Tot nu toe werd er nog geen aandacht besteed aan mogelijke afwijkingen van bepaalde waarden en werd er steeds uitgegaan van perfecte meetwaarden. De realiteit is echter anders en zorgt ervoor dat steeds rekening moet worden gehouden met het mogelijk optreden van uitschieters1 en ruis bij de meetwaarden. In dit hoofdstuk zullen drie technieken aan bod komen die de invloed van deze factoren trachten te minimaliseren. Dit kan men omschrijven als regularisatie.
6.1
Wegingsfactor toepassen
Een eerste techniek die wordt gehanteerd is het toepassen van een wegingsfactor op de flowvectoren aan de hand van een gewichtsmasker. Dit gewichtsmasker wordt opgesteld door het combineren van een horizontale- en een verticale gaussiaan, waarbij de standaarddeviaties van elkaar verschillen. Wat de afmetingen van het masker betreft wordt er steeds uitgegaan van het getransformeerde beeld. In Figuur 6.1 wordt het getransformeerde beeld en zijn bijhorende gewichtsmasker weergegeven.
Figuur 6.1: Een voorbeeldframe van een getransformeerd camerabeeld aan de linkerzijde en een visualisatie van het bijhorende gewichtsmasker aan de rechterzijde 1
Uitschieters of in het Engels outliers kunnen worden omschreven als waarnemingen die niet bij de overige data lijken te passen.
30
Hier is duidelijk dat de verwachte waarde eerder centraal en net boven de wagen ligt. Er wordt immers aangenomen dat flowvectoren die meer centraal in het beeld liggen relevanter zijn bij het bijdragen tot het uiteindelijke resultaat dan flowvectoren die eerder aan de rand van het beeld gelegen zijn. Het is namelijk zo dat de kans op het overtreden van de gemaakte veronderstellingen (alles ligt in het grondvlak) groter is naarmate de afstand tot de wagen vergroot en dit dus voor storing in de metingen kan zorgen. Hier zal bijgevolg een lagere factor aan worden meegegeven. Het is door het toewijzen van een gewicht aan elke flowvector dat in verdere berekeningen bepaalde flowvectoren meer invloed kunnen uitoefenen dan andere om uiteindelijk via deze manier een betrouwbaarder resultaat te bekomen.
6.2
Optimalisatie via minimalisatie
Ook bij het bepalen van het momentane rotatiecentrum blijken de meetwaarden niet geheel consistent te zijn en dit opnieuw door ruis en uitschieters. Om dit tegen te gaan werd er in dit werk gebruikgemaakt van twee verschillende methodes die apart van elkaar werden ge¨ımplementeerd. Wat hier wel dient opgemerkt te worden is dat de aparte implementatie hier enkel om de regularisatie bij het bepalen van het rotatiecentrum gaat, voor de rest hebben beide implementaties alles gemeen. De eerste methode zal in deze sectie uitgelegd worden, de tweede methode wordt in de volgende sectie toegelicht. In het volgende hoofdstuk komen de resultaten van deze twee methodes aan bod en zullen deze met elkaar vergeleken worden. Bij de eerste methode wordt naar de minimale kost bij het bepalen van het momentane rotatiecentrum gezocht. Het principe hierachter berust in het feit dat wanneer men het momentane rotatiecentrum als middelpunt van een cirkel gaat beschouwen, de flowvectoren hierbij op koordes lijken. Met andere woorden, de afstand van het beginpunt van deze vector tot het rotatiecentrum is in principe gelijk aan de afstand van het eindpunt van deze vector tot hetzelfde rotatiecentrum. Uiteindelijk kan men het ook als volgt stellen: het verschil in hierboven vermelde afstanden is minimaal wanneer men het effectieve momentane rotatiecentrum bereikt. De enige variabele hierbij is de x-co¨ordinaat van het rotatiecentrum aangezien de y-co¨ ordinaat reeds vastligt. Deze is namelijk gelijk aan de y-co¨ordinaat van de achterste as van het voertuig door het principe van Ackermann (zie vorige hoofdstuk). Het geheel kan beschouwd worden als een least absolute deviations fit 2 van het beste rotatiecentrum voor alle flowvectoren waarbij gebruik wordt gemaakt van een numerieke optimalisatie om het minimum te zoeken van de bekomen ´e´endimensionale curve. Concreet wordt de kost bepaald door bij elk gegeven rotatiecentrum de abolute waarden van de verschillen tussen enerzijds de afstand van het eerste punt van elke flowvector tot het gegeven rotatiecentrum en anderzijds de afstand van het tweede punt van elke flowvector tot het gegeven rotatiecentrum te sommeren. Dit kan voorgesteld worden in 2
De least absolute deviations methode is een statistische optimalisatietechniek waarbij de som van de absolute fouten (sum of absolute errors of kortweg SAE) wordt geminimaliseerd om tot het best passende resultaat bij de bijhorende dataset te komen.
31
onderstaande formule waar c de te minimaliseren kost vertegenwoordigt, (XR ,YR ) het ogenblikkelijke rotatiecentrum voorstelt, n voor het totaal aantal flowvectoren staat en (Xi1 ,Yi1 ) en (Xi2 ,Yi2 ) respectievelijk het eerste- en het tweede punt van de desbetreffende flowvector symboliseren. c=
n �� � � � � � � (Yi1 − YR )2 + (Xi1 − XR )2 − (Yi2 − YR )2 + (Xi2 − XR )2 �
(6.1)
i=0
Een visuele weergave van enkele ´e´endimensionale kostencurves is te zien in Figuur 6.2. Hierbij werd voor elk mogelijk rotatiecentrum (x-co¨ordinaat is hier de variabele) de kost bepaald met behulp van vergelijking 6.1. De figuur geeft respectievelijk drie situaties weer: een bocht naar rechts, een bocht naar links en rechtdoor rijden.
32
��� ���
����
��� ���
��� ��� ��� ��� ��
�� �� �� �� �� � �� �� �� �� �� �������������������������������������������
�� ���
(a)
���
����
���
���
���
��� ��
�� �� �� �� �� � �� �� �� �� �� �������������������������������������������
�� ���
(b) ���
���
����
���
���
���
� ���
���
��� ��� �� � �� ��� ��� �������������������������������������������
���
(c) Figuur 6.2: Drie visuele weergaven van de kost bij het bepalen van het momentane rotatiecentrum, telkens bij een andere situatie. In volgorde van voorkomen: (a) een bocht naar rechts, (b) een bocht naar links en (c) rechtdoor rijden.
33
Om nu het momentane rotatiecentrum met de minste kost te selecteren dient men dus het minimum van deze kostencurves te bepalen. Het berekenen van de volledige curve om hiervan nadien het minimum te bepalen vergt echter zeer veel rekentijd en dit wordt alleen erger wanneer het aantal flowvectoren toeneemt. Het is daarom dat eerder werd gekozen voor een optimalisatie algortime dat stelselmatig naar het minimum zoekt in plaats van de hele curve af te lopen en telkens de kleinste waarde en index bij te houden. In dit werk werd gekozen om een combinatie van het algoritme van Brent en parabolische interpolatie te gebruiken zoals beschreven in [42]. Er wordt hier gesuggereerd dat deze oplossing het effici¨entst is voor dit probleem. Uit experimenten blijkt dit inderdaad de meest performante oplossing voor dit probleem. Deze worden weergegeven in Tabel 6.1. Hier wordt het voorgestelde minimalisatie algoritme vergeleken met enkele andere bestaande methodes. Er werd per algoritme in tien verschillende situaties, waarbij dezelfde situatie tien keer werd herhaald, telkens naar het minimum gezocht. Hierbij werd iedere keer de uitvoeringstijd bijgehouden en werd achteraf het gemiddelde genomen. Dit gemiddelde (van de honderd uitvoeringstijden) per algoritme wordt dus hieronder weergegeven. Tabel 6.1: Vergelijking van tien algoritmes bij de bepaling van het minimum bij de kostencurves van de rotatiecentra op basis van de uitvoeringstijd.
Algoritme Brent Sequential Least Squares Programming (SLSQP) Powell’s method Nelder-Mead (Simplex) Nonlinear Conjugate Gradient (CG) Limited-memory BFGS Constrained Optimization By Linear Approximation (COBYLA) Broyden-FletcherGoldfarbShanno (BFGS) Truncated Newton Conjugate-Gradient (TNC) Simulated annealing
Uitvoeringstijd (ms) 15.38 15.42 16.41 16.60 16.83 17.27 18.62 18.94 20.55 73.83
Het principe van het gebruikte algoritme uit [42] bestaat dus uit twee delen, namelijk parabolische interpolatie en de methode van Brent. Bij parabolische interpolatie gaat men aan de hand van drie gekozen punten op de curve een parabool opstellen en hiervan het minimum berekenen. Uit deze vier punten bepaalt men de drie laagste om de voorgaande stap mee te herhalen. Dit wordt telkens herhaald tot het uiteindelijke minimum is bereikt. Dit principe is echter enkel van toepassing wanneer de te onderzoeken curve slechts ´e´en uitgesproken minimum heeft en dus een eenvoudige parabolische vorm heeft of unimodaal wordt genoemd. Maar aangezien dit slechts bij een zeer klein aantal situaties het geval is, wordt er eerst beroep gedaan op de andere methode, meer bepaald de methode van Brent. Bij de methode van Brent is het zo dat er gebruik wordt gemaakt van zes punten: twee om de momentane grenzen af te bakenen (a en b), drie om de punten van de voorgaande stappen bij te houden (u, v en w ) en ´e´en dat de laagste waarde tot nu toe bevat (x ). Hierbij stelt u het meest recent ge¨evalueerde punt voor, w het punt met de tweede laagste
34
waarde en v stelt de voorgaande waarde van w voor. Parabolische interpolatie zal plaatsvinden bij de punten x, v en w maar moet aan twee criteria voldoen vooraleer het resultaat hiervan geaccepteerd wordt. Ten eerste moet het resultaat binnen het interval [a,b] liggen. Ten tweede mag het resultaat slechts de helft van de verschuiving bij de vorige stap verschuiven ten opzichte van het momentane punt met de laagste functiewaarde (x ). Dit laatste criterium zorgt ervoor dat er zeker convergentie optreedt. Indien er niet wordt voldaan aan deze criteria zal via het triplet u, v en w gezocht worden naar de volgende (nieuwe) waarde voor x. Er zal dan nagegaan worden welk van de drie punten de laagste functiewaarde bezit om vervolgens te bepalen tussen welke twee punten van de drie een nieuw punt zal worden gezocht. Stel dat u de laagste functiewaarde bezit en het interval [u,w ] groter is dan het interval [v,u] zoals weergegeven in Figuur 6.3. Dan zal het nieuwe punt worden gezocht in het interval [u,w ] en dit op de plaats waar a + c = b. Op de figuur is dit aangegeven met een stippellijn. Deze laatste voorwaarde is gebaseerd op de gulden snede en zorgt voor de nodige convergentie.
Figuur 6.3: Een voorbeeld van de bepaling van een nieuwe waarde voor x op basis van de gulden snede
35
6.3
Clustering
Nog een methode die wordt gehanteerd bij het voorkomen van invloed door ruis en uitschieters is clustering. Bij clustering is het de bedoeling om een zekere dataset in groepen te verdelen op zo’n manier dat objecten uit dezelde groep (ook wel cluster genoemd) meer bij elkaar horen dan bij objecten uit andere groepen en dit aan de hand van specifieke eigenschappen van deze objecten. Er bestaan verscheidene algoritmes om dit probleem aan te pakken, maar in dit werk werd gekozen voor k-means clustering. Hierbij wordt de dataset verdeeld in k clusters (k zijnde een zelf opgegeven natuurlijk getal) op basis van de afstand tot ´e´en van de centra van de clusters.
6.3.1
Clusteren van rotatiecentra
Het clusteren wordt naast de methode van Brent uit de voorgaande sectie ook toegepast op de rotatiecentra en het zijn deze methodes die in het volgende hoofdstuk met elkaar zullen vergeleken worden. Maar onafhankelijk van de regularisatie bij de bepaling van het rotatiecentrum wordt ook clustering toegepast bij de bepaling van de momentane rotatiehoek. Ten eerste zal de implementatie van clustering bij de bepaling van het rotatiecentrum verduidelijkt worden. Eenmaal alle rotatiecentra zijn berekend, kan clustering worden toegepast. De flowvectoren kunnen drie verschillende situaties weergeven: een bocht naar links maken (rotatiecentra links van de wagen), een bocht naar rechts maken (rotatiecentra rechts van de wagen) en rechtdoor rijden (rotatiecentra liggen theoretisch gezien oneindig ver van de wagen3 ). Uit metingen is gebleken dat ook rotatiecentra op of vlak naast het middelpunt van de wagen worden bepaald. Dit zou echter wijzen op het feit dat de wagen plots bijvoorbeeld een kwartslag kan draaien uit stilstand. Een dermate kleine draaicirkel is niet mogelijk bij reguliere wagens dus ook hiermee zal rekening moeten gehouden worden. Er wordt uiteindelijk voor drie clusters gekozen aangezien de flowvectoren in het slechtste geval drie verschillende mogelijkheden op hetzelde moment kunnen weergeven. De mogelijke situaties en hun mogelijkheden: • Bocht naar links – rotatiecentra links van het middelpunt van de wagen – rotatiecentra extreem links van het middelpunt van de wagen (minderheid) – rotatiecentra rechts of in de buurt van het middelpunt van de wagen (minderheid) • Bocht naar rechts – rotatiecentra rechts van het middelpunt van de wagen – rotatiecentra extreem rechts van het middelpunt van de wagen (minderheid) – rotatiecentra links of in de buurt van het middelpunt van de wagen (minderheid) 3
De flowvectoren staan in dit geval loodrecht op de achterste as van de wagen. De middelloodlijnen en de achterste as snijden elkaar dan theoretisch gezien op oneindig.
36
• Rechtdoor rijden – rotatiecentra extreem links van het middelpunt van de wagen – rotatiecentra extreem rechts van het middelpunt van de wagen – rotatiecentra in de buurt van het middelpunt van de wagen (minderheid) Na deze clustering wordt gecontroleerd of er eventueel clusters kunnen worden samengevoegd. Dit gebeurt op basis van het centrum van de ene cluster en de standaarddeviatie en het centrum van de andere cluster. Meer bepaald als het gemiddelde van cluster1 op een afstand dat kleiner of gelijk aan twee maal de standaarddeviatie van cluster2 van het gemiddelde van cluster2 ligt, dan kunnen deze twee clusters samengevoegd worden. De mogelijkheid om alledrie de clusters samen te voegen wordt hierbij ook onderzocht. Uiteindelijk wordt naar de meest significante cluster (degene met de meeste waarden) gekeken om het centrum hiervan als momentane rotatiecentrum door te geven. In Figuur 6.4 wordt de clustering van de rotatiecentra voorgesteld tijdens het nemen van een bocht naar rechts. Hierbij geeft de X-as de afstand van het rotatiecentrum tot het middelpunt van de wagen weer en worden de centers van elke cluster voorgesteld door een geel balkje. Zoals men kan zien kunnen de rode- en groene cluster in Figuur 6.4a bij elkaar gevoegd worden, Figuur 6.4b toont hiervan het resultaat. Het is hier ook duidelijk op te merken dat de uiteindelijke groene cluster in Figuur 6.4b de bovenhand neemt en zijn center zal doorgeven als momentane rotatiecentrum.
37
�� ��
����������
� � � � �
��
��
�� �� � �� ���������������������������
��
��
��
��
(a) ��
����������
��
��
��
�
�
��
��
�� �� � �� ���������������������������
(b) Figuur 6.4: Clustering van de rotatiecentra bij het nemen van een bocht naar rechts. (a): clustering zonder samenvoeging van clusters, (b): clustering met samenvoeging van clusters
38
6.3.2
Clusteren van rotatiehoeken
Wat de clustering bij de rotatiehoeken betreft wordt ongeveer hetzelfde principe gehanteerd als bij de rotatiecentra. De rotatiecentra per flowvector worden hier echter eerst berekend met behulp van de cosinusregel (zie Hoofdstuk 5) en het aantal clusters is bij deze implementatie gezet op twee aangezien zich steeds maar twee mogelijkheden kunnen voordoen bij de rotatiehoeken: ofwel dicht bij 0 graden wanneer de wagen rechtdoor rijdt, ofwel verder weg van 0 graden wanneer de wagen een bocht maakt. Wel dient hier opgemerkt te worden dat bij dense optical flow een groter gewicht wordt meegegeven aan de cluster waarbij het centrum verder weg ligt van 0 graden en dus wijst op een bocht. Dit omdat bij dense optical flow ontzettend veel flowvectoren steeds 0 graden aangeven (hoofdzakelijk flowvectoren aan de randen) en deze op die manier foutieve resultaten zouden kunnen veroorzaken. Dit wordt dus louter toegepast om de invloed van deze eerder foutieve flowvectoren in te perken. In Figuur 6.5 wordt de clustering van de rotatiehoeken bij een bocht naar rechts weergegeven. De twee gevormde clusters zijn van elkaar te onderscheiden door de verschillende kleur die toegewezen zijn aan elke cluster, namelijk groen voor de rotatiehoeken links of in de buurt van 0 graden en rood voor de hoeken verder weg van 0 graden aan de rechterkant. De centers van elke cluster worden aangegeven met een gele kleur. In dit geval is het wel duidelijk dat de cluster met rode kleur de bovenhand neemt en zijn center zal doorgeven als momentane rotatiehoek.
��
����������
��
��
�
� ���
���
���
��� ��� ��� �������������������������
���
���
���
Figuur 6.5: Clusteren van de verschillende rotatiehoeken aangegeven door de verschillende flowvectoren. In dit geval wordt een bocht naar rechts genomen.
39
Hoofdstuk 7
Resultaten In dit hoofdstuk zullen de resultaten van de verschillende gebruikte methodes aan bod komen alsook de onderlinge vergelijking ervan. Allereerst zullen de gebruikte camerabeelden besproken worden waarna een volledige uiteenzetting volgt van de waarden bij de verschillende in te stellen parameters bij elke gebruikte methode. Daarna zullen de gebruikte regularisatiemethoden en hun nut aan bod komen en zullen de resultaten van de twee gebruikte methoden bij het regulariseren van de rotatiecentra met elkaar vergeleken worden. Vervolgens zullen de twee verschillende optical flow algoritmes tegenover elkaar worden geplaatst, zowel bij het toepassen ervan op de getransformeerde beelden als bij de toepassing op de originele camerabeelden. Performantie en nauwkeurigheid zullen hierbij de maatstaf zijn. Hierna zal er ook onderling een vergelijking worden gemaakt tussen het toepassen van optical flow op de getransformeerde beelden en de toepassing op de originele camerabeelden, zowel bij dense- als bij sparse optical flow. Ook hier zullen performantie en nauwkeurigheid naar voor worden geschoven. Als laatste wordt de voorgestelde oplossing in dit werk toegepast op camerabeelden van een ander traject. Dit werd uitgevoerd om de toepasbaarheid van de gekozen oplossingsmethodiek aan te kaarten.
40
7.1 7.1.1
Technische details Camerabeelden
Als testtraject is gekozen voor een achtvormig parcours op de parking van Hogeschool Gent Campus Schoonmeersen. Hierin zitten dus vier bochten van elk 180◦ , meer bepaald twee naar rechts en vervolgens twee naar links. Het precieze traject wordt weergegeven in Figuur 7.1. De blauwe lijn stelt het traject voor en het startpunt (en stoppunt) wordt aangegeven door een groene stip.
Figuur 7.1: Luchtfoto van de parking van Hogeschool Gent Campus Schoonmeersen met weergave van het achtvormige testtraject
De camera werd op de motorkap geplaatst en bracht beelden op zoals bijvoorbeeld reeds werd getoond in Figuur 4.2b. Zo goed als alle tests zijn op deze beelden uitgevoerd en alle resultaten die hieronder te vinden zijn, buiten deze in de laatste sectie van dit hoofstuk, komen ook voort uit deze beelden. De originele beelden zijn 960x540 pixels en de getransformeerde zijn 400x400 pixels. Om de perspectieftransformatie te kunnen uitvoeren zijn echter nog enkele parameters nodig eigen aan de camera en de plaatsing ervan op de wagen: • zijdelingse afwijking van de camera ten opzichte van de lengteas van de wagen: 0.2 m • afwijking in de lengterichting van de camera ten opzichte van de voorste wielas van de wagen: 1.3 m • camerahoogte ten opzichte van de grond: 1.2 m
41
• camera’s wentellingsgraad (roll ): -0.035000 radialen • camera’s hellingsgraad (pitch): -0.25 radialen • camera’s richtingsgraad (yaw ): 0.007545 radialen • brandpuntsafstand van de camera: 730.00 pixels • aantal pixels per meter1 : 20 pixels • framerate: 25 frames per seconde
7.1.2
Parameters
Hieronder volgt een oplijsting van de gebruikte parameterinstellingen bij de verschillende gebruikte methodes. Alle gekozen waarden zijn bekomen door experimentele ondervinding inzake performantie en nauwkeurigheid, tenzij anders vermeld. Bij de meeste gevallen zijn er nog meer parameters instelbaar dan hieronder wordt weergegeven, maar indien deze niet vermeld worden betekent dit dat de standaardwaarde werd ingevuld. Gewichtsmasker Zoals reeds aan bod kwam in Hoofdstuk 6 wordt een gewichtsmasker aangebracht op de getransformeerde beelden om aan de hand hiervan een gewicht mee te kunnen geven aan de bekomen flowvectoren. Een voorbeeld hiervan werd reeds weergegeven in Figuur 6.1. Maar om dit gewichtsmasker te bekomen werd gebruikgemaakt van twee gaussiaanse curves, namelijk ´e´en voor in de horizontale- en ´e´en voor in de verticale richting. De standaarddeviaties bij beide curves zijn echter verschillend, namelijk 0.05625 voor de verticale gaussiaan en 0.15 voor de horizontale gaussiaan. Sparse methode Bij de sparse methode worden features bepaald aan de hand van de good features to track methode en een zeker symmetrie-criterium. Bij dit laatste worden de beelden onderverdeeld in verticaal symmetrische delen waarbij wordt gezorgd dat een gelijk aantal features wordt bepaald in zowel het linker als het rechter deel van het beeld. De parameters die hiervoor dienen ingesteld te worden, worden hieronder weergegeven. Meer uitleg over deze twee principes kan respectievelijk teruggevonden worden in Hoofdstuk 2 en Hoofdstuk 4. • maximum aantal te bepalen features: 200 • kwaliteitsniveau2 : 0.01 • kleinst mogelijke afstand tussen twee features: 5 1
Deze waarde wordt gebruikt om de uiteindelijk bepaalde co¨ ordinaten om te zetten naar meter Via deze parameter is het mogelijk een minimum aan kwaliteit op te leggen aan de features. Deze waarde wordt namelijk vermenigvuldigd met de hoogste kwaliteitswaarde om als minimum drempelwaarde te dienen voor de andere features. Bijvoorbeeld als de hoogste kwaliteitswaarde 1500 bedraagt en het kwaliteitsniveau 0.01, dan moeten de rest van de features een minimumwaarde van 15 bezitten om geaccepteerd te worden. 2
42
• percentages van het maximum aantal te bepalen features per stuk van het beeld bij het symmetrie-criterium in het geval van verdeling in zes delen: – A of B: 10% – C of D: 30% – E of F: 10% Een opmerking kan hier gemaakt worden omtrent het maximum aantal te bepalen features. De waarde 200 is uiteindelijk gekozen als compromis tussen nauwkeurigheid en snelheid. Wat ook kon vastgesteld worden is dat wanneer men deze waarde zeer hoog ging nemen, de hoeknauwkeurigheid zelfs naar beneden ging. Meer features zorgt in principe voor meer uitmiddeling, maar aangezien reeds naar de beste hoeken wordt gezocht met de methode van good features to track, betekenen meer features eerder meer kans op outliers. Wat de sparse optical flow methode van Lucas en Kanade betreft werden volgende parameterwaarden gebruikt: • venstergrootte3 : 31x31 pixels • maximum aantal niveaus in de beeldpyramide4 : 4 • drempelwaarde voor de minimale eigenwaarden: 0.001 Dense methode Bij de dense optical flow methode van Gunnar Farneb¨ack worden volgende parameterwaarden gehanteerd: • schaalfactor bij het bepalen van de volgende laag in de beeldpyramide: 0.5 • maximum aantal niveaus in de beeldpyramide: 1 (geen pyramide dus) • venstergrootte: 15x15 pixels • maximum aantal iteraties per niveau in de pyramide: 5 • grootte van de naburigheid van de desbetreffende pixel waarbij men het principe van ontbinden in veeltermen toepast: 5 • standaarddeviatie van de gebruikte gaussiaanse curve5 : 1.1 3
Dit is de grootte van het gebied waarbinnen wordt gezocht naar de overeenkomstige feature. Zie Hoofdstuk 2 5 De gaussiaanse curve wordt hierbij gebruikt om afgeleiden af te vlakken die op hun beurt gebruikt worden bij het ontbinden in veeltermen. 4
43
Optimalisatie via least absolute deviations De methode van Brent die hierbij gebruikt wordt, bezit ook enkele parameters die kunnen ingevuld worden: • initi¨ele grenswaarden ten opzichte van het middelpunt van de wagen: -10000 pixels en 10000 pixels • epsilon6 : 0.000001
7.2
Least absolute deviations versus clustering
Om de regularisatiemethodes bij het bepalen van de rotatiecentra met elkaar te vergelijken zullen snelheid, momentane rotatiehoek, cumulatieve rotatiehoek en het uiteindelijk bepaalde traject in rekening worden gebracht. Deze vergelijking zal gemaakt worden bij het gebruik van de sparse optical flow methode op de originele beelden. In Figuur 7.2 wordt voor beide methodes de cumulatieve rotatiehoek voorgesteld bij het afleggen van het achtvormige parcours. Men kan in beide gevallen de vier bochten duidelijk herkennen, namelijk aan de steile delen in elke grafiek. Algemeen kan men stellen dat het verloop van de grafiek bij de least absolute deviations methode het stabielst is. Ook kan men opmerken dat de nauwkeurigheid wat de rotatiehoeken betreft hier zeer hoog ligt. Enkel na de derde bocht valt er een kleine afwijking van 2 a ` 3 graden te bespeuren. Dit in tegenstelling tot de grafiek van de clustermethode, hier laat de nauwkeurigheid te wensen over. Nog voor de eerste bocht is er al sprake van een afwijking en deze zet zich voort doorheen het hele traject. Het grillige verloop van de resultaten van de clustermethode in Figuur 7.2a is te danken aan de ruis die nog steeds aanwezig is bij de momentane rotatiehoek. In Figuur 7.3 wordt dit opnieuw door twee grafieken weergegeven. Hieruit valt duidelijk af te leiden dat er nog steeds zeer veel ruis aanwezig is bij de clustermethode (Figuur 7.3a) en dit hoofdzakelijk wanneer de wagen rechtdoor rijdt. De clustermethode is kennelijk enkel geschikt voor situaties met bochten aangezien hier dan weer weinig ruis te bespeuren is. De least absolute deviations methode is echter wel geschikt voor beide situaties en dat valt duidelijk waar te nemen in Figuur 7.3b. Hier is nagenoeg geen ruis meer aanwezig. Gaat men kijken naar de uitvoeringstijd van beide methodes, dan scoren beide methodes nagenoeg gelijk. Al kan men uit Tabel 7.1 toch afleiden dat de least absolute deviations methode over het algemeen net iets sneller is. In de tabel wordt namelijk weergegeven hoeveel frames gemiddeld kunnen worden verwerkt per seconde. Dit werd gemeten over het hele proces en dus niet enkel over de desbetreffende methodes. Het gaat hier om de performantie in combinatie met alle voorgaande methodes. Er werd om de vijftig frames bijgehouden hoeveel frames dat per seconde werden verwerkt. Deze stap werd tien keer herhaald en van alle resultaten werd uiteindelijk een gemiddelde genomen. Het is dit finale gemiddelde dat wordt weergegeven in de tabel. 6
Wanneer het verschil in functiewaarden tussen twee iteraties kleiner is dan deze zeer kleine waarde, dan wordt het algoritme be¨ındigt
44
Tabel 7.1: Vergelijking van de twee gebruikte regularisatiemethodes wat betreft de rotatiecentra en dit op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt.
���������������������������
Methode Least absolute deviations Clustering
Aantal frames per seconde 14.94 13.33
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
���������������������������
(a) Clustering
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Least absolute deviations methode Figuur 7.2: Weergave van de cumulatieve rotatiehoek bij de twee gebruikte regularisatiemethoden wat betreft de rotatiecentra.
45
�������������������������
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
�������������������������
(a) Clustering
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Least absolute deviations methode Figuur 7.3: Weergave van de momentane rotatiehoek bij de twee gebruikte regularisatiemethoden wat betreft de rotatiecentra.
46
Tenslotte kan men ook het uiteindelijk bekomen traject bij elke methode met elkaar vergelijken. De bekomen trajecten van beide methodes worden weergegeven in Figuur 7.4. Het startpunt van het traject wordt aangegeven met een groene stip. Over het algemeen lijkt het bekomen traject bij de clustermethode wel te kloppen mits rekening te houden met een serieuze afwijking van de cumulatieve rotatiehoek. Bij de least absolute deviations methode is er weinig op te merken wat hoekafwijkingen betreft. De enige opmerking die men zou kunnen maken als men echt gaat vergelijken met het originele traject uit Figuur 7.1 is dat de derde en vierde bocht wijder zouden moeten zijn. Maar gezien dit de enigste opmerking is, is het toch de least absolute deviations methode die hier de bovenhand neemt.
(a) Clustering
(b) Least absolute deviations methode
Figuur 7.4: De bekomen trajecten bij beide regularisatiemethodes
Al deze resultaten in acht genomen, kan men stellen dat de least absolute deviations methode beter geschikt is voor deze toepassing. Zoals werd aangetoond vertoont deze methode zowel op vlak van nauwkeurigheid als van snelheid betere resultaten.
47
7.3
Sparse versus Dense
Ook bij de vergelijking van de sparse optical flow methode met de dense optical flow methode zal gekeken worden naar snelheid, momentane rotatiehoek, cumulatieve rotatiehoek en het uiteindelijk bepaalde traject. Bij deze vergelijking worden beide methodes toegepast op de getransformeerde beelden en zal telkens voor de least absolute deviations methode gekozen worden bij de regularisatie van de rotatiecentra. In Figuur 7.6 wordt voor beide methodes de cumulatieve rotatiehoek gedurende het hele traject voorgesteld. Men kan ook hier in beide gevallen de vier bochten duidelijk herkennen. Beide methodes scoren behoorlijk wat betreft de nauwkeurigheid bij het bereiken van de correcte hoek na elke bocht. Wat opvalt is dat de sparse methode stabieler is in de rechte stukken, de dense methode heeft hier de neiging om af te wijken. Over het algemeen geeft de sparse methode steeds de correcte hoek aan tot op 6 graden nauwkeurig. Dit kan men zien na de eerste bocht en helemaal op het einde na de vierde bocht. De dense methode scoort minder goed qua nauwkeurigheid aangezien net voor de eerste bocht reeds een kleine afwijking te bespeuren is en de afwijking over de rest van het traject op kan lopen tot 13 graden. Dit kan men duidelijk zien na de derde en vierde bocht. Inzake de cumulatieve rotatiehoek is het toch de sparse methode die het nauwkeurigst blijkt te zijn. Vergelijkt men de momentane rotatiehoeken bij beide optical flow methoden met elkaar (Figuur 7.7), dan kan men stellen dat de sparse methode globaal gezien meer ruis vertoont dan de dense methode. Dit in tegenstelling tot de verwachting aangezien bij de cumulatieve rotatiehoek het net de sparse methode was die het nauwkeurigst bleek te zijn. Een mogelijke verklaring hiervoor kan zijn dat de momentane rotatiehoeken bij het rechtdoor rijden in Figuur 7.7a elkaar over tijd uitmiddelen en uiteindelijk evenwel tot een nauwkeurige cumulatieve hoek leiden. Bij de dense methode kan men zien dat bij de rechte stukken (momentane rotatiehoek zou moeten nul zijn) er steeds een kleine positieve rotatiehoek aanwezig is. Het is deze kleine rotatiehoek die zorgt voor de kleine stijgende afwijking die op te merken viel in Figuur 7.6b. Bij de bochten is het de sparse methode die de hoogste hoeken bereikt. Daar waar de dense methode slechts nipt 1.3 graden bereikt, geraakt de sparse methode zelfs boven 1.4 graden. Hoge momentane rotatiehoeken spreken hierbij echter in het nadeel van de sparse methode aangezien dit kan leiden tot te hoge cumulatieve rotatiehoeken. Een voobeeld hiervan is te zien in Figuur 7.6a, namelijk na de eerste bocht waar de cumulatieve hoek boven 180 graden zit. Bij het gebruikte testtraject wordt dit effect teniet gedaan doordat er even grote negatieve hoeken aan bod komen en valt het uiteindelijk niet zo erg op. In andere situaties zou dit echter meer problemen kunnen geven. Het algemene verloop is stabieler bij de dense methode aangezien er hierbij telkens rekening wordt gehouden met elk punt in het beeld waardoor de overgang van de ene momentane rotatiehoek naar de andere ook veel vloeiender zal zijn. In Tabel 7.2 werd op dezelfde manier als in de vorige sectie gezocht naar het gemiddeld aantal frames dat per seconde verwerkt kon worden. Op vlak van uitvoeringstijd valt het niet te ontkennen dat de sparse methode de snelste methode is. Het feit dat de sparse methode slechts rekening moet houden met 200 features en de dense methode met meer
48
dan 20000 zal hier zeker een grote rol in spelen. Er werd geprobeerd om frames over te slaan om het aantal frames per seconde op te drijven, maar dit ging ten koste van de nauwkeurigheid wat nog minder wenselijk is. Tabel 7.2: Vergelijking van de twee gebruikte optical flow methodes en dit op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt
Methode Sparse optical flow Dense optical flow
Aantal frames per seconde 33.19 2.68
Als men gaat kijken naar het uiteindelijk bekomen traject bij de twee optical flow methodes, valt het op dat de kleine afwijkingen uit de vorige grafieken niettemin grote gevolgen hebben. De vier bochten zijn wel nog steeds duidelijk herkenbaar, maar de momentane translatie die berekend wordt op basis van de momentane- en cumulatieve rotatiehoek laat te wensen over. Dit is voornamelijk zichtbaar bij de vierde bocht bij de sparse methode en bij de derde en vierde bocht bij de dense methode. Gaat men vergelijken met het originele traject uit Figuur 7.1 dan zou men kunnen zeggen dat het traject van de sparse methode er het meest op lijkt afgezien van de afwijkende cumulatieve rotatiehoek en de afwijkende translatie tijdens de laatste bocht.
(a) Sparse optical flow
(b) Dense optical flow
Figuur 7.5: Het bekomen traject bij beide optical flow methodes
Uit voorgaande resultaten kan besloten worden dat de sparse methode zegeviert in dit vergelijk. Qua precisie bij de rotatiehoeken zijn beide methodes nagenoeg van hetzelfde niveau. Het is echter bij de snelheidsmeting en bij het bekomen traject dat de sparse methode de leiding neemt.
49
���������������������������
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
���������������������������
(a) Sparse optical flow
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Dense optical flow Figuur 7.6: Weergave van de cumulatieve rotatiehoek bij de twee gebruikte optical flow methodes
50
�������������������������
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
�������������������������
(a) Sparse optical flow
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Dense optical flow Figuur 7.7: Weergave van de momentane rotatiehoek bij de twee gebruikte optical flow methodes
51
7.4
Getransformeerde beelden versus getransformeerde flowvectoren
In deze sectie zullen de twee voorgestelde oplossingsmethodieken met elkaar vergeleken worden. Bij de eerste oplossingsmethodiek worden de camerabeelden eerst getransformeerd. Daarna wordt optical flow toegepast op deze getransformeerde beelden. Bij de tweede oplossingsmethodiek wordt optical flow toegepast op de originele camerabeelden waarbij het vervolgens de bekomen flowvectoren zijn die worden getransformeerd. In deze sectie zullen de namen ’getransformeerde camerabeelden’ en ’getransformeerde flowvectoren’ gebruikt worden om respectievelijk de eerste en de tweede oplossingsmethodiek voor te stellen. Net als bij de vorige vergelijkingen zal ook in deze sectie gekeken worden naar de cumulatieveen momentane rotatiehoek, de snelheid en het uiteindelijk bekomen traject. Verder zal er gebruikgemaakt worden van de sparse optical flow methode om beide oplossingsmethodieken als dusdanig met elkaar te vergelijken. De cumulatieve rotatiehoek voor beide oplossingsmethodieken wordt in Figuur 7.9 weergegeven. De eerste grafiek is reeds in de vorige sectie besproken(Figuur 7.6a). Daar werd uitgegaan van de eerste oplossingsmethodiek en werd sparse met dense vergeleken. Zoals dus reeds werd gezegd verloopt de grafiek over het algemeen zeer stabiel, maar is er toch een zekere afwijking aanwezig. Maar ook de tweede grafiek is reeds aan bod gekomen, namelijk bij de vergelijking van de regularisatiemethodes want hier werd gebruikgemaakt van de tweede oplossingsmethodiek en sparse optical flow. Desalniettemin kan uit de grafiek in Figuur 7.9b) worden afgeleid dat de eerder vermelde afwijking nagenoeg niet aanwezig is. Enkel na de derde bocht kan men een afwijking van 3 graden meten. Niettegenstaande deze kleine afwijking, is het duidelijk dat de tweede oplossingsmethodiek een nauwkeuriger resultaat geeft wat betreft de cumulatieve rotatiehoek. Figuur 7.10 geeft de momentane rotatiehoek weer van beide oplossingsmethodieken. Er kan opnieuw hetzelfde bemerkt worden wat betreft de grafieken, namelijk dat deze reeds werden geanalyseerd in voorgaande secties. Figuur 7.10a is in feite dezelfde als Figuur 7.7a en Figuur 7.10b is een kopie van Figuur 7.3b. De voornaamste kenmerken van de eerste grafiek bleken de ruis bij de rechte stukken en de (te) hoge momentane rotatiehoeken. Bij de tweede grafiek is de ruis bijna helemaal verdwenen en zijn er quasi geen te hoge momentane rotatiehoeken op te merken. Meteen een verklaring voor de nauwkeurigheid die in de voorgaande vergelijking werd aangehaald. Ook bij deze vergelijking werd getest op snelheid en wordt dit weergegeven aan de hand van het aantal frames per seconde dat kon verwerkt worden. De gegevens zijn te vinden in Tabel 7.3. Het valt op dat de eerste oplossingsmethodiek meer dan tweemaal sneller is dan de tweede oplossingsmethodiek, maar dit gaat duidelijk ten koste van nauwkeurigheid op vlak van rotatiehoeken. De reden hiervoor is dat er bij de eerste oplossingsmethodiek slechts in een omgeving van 400x400 pixels (grootte van het getransformeerde beeld) moet worden gezocht naar features, terwijl bij de tweede oplossingsmethodiek dit een omgeving van 960x540 pixels (grootte van het originele beeld) is. Een grotere omgeving betekent immers meer mogelijkheden op goeie features en daardoor duurt het zoeken ernaar langer wat het hele proces vertraagt.
52
Tabel 7.3: Vergelijking van de twee gebruikte oplossingsmethodieken op basis van het aantal frames per seconde die gemiddeld gezien kunnen worden verwerkt
Methode Getransformeerde beelden Getransformeerde flowvectoren
Aantal frames per seconde 33.19 14.94
De trajecten van beide oplossingsmethodieken worden voorgesteld in Figuur 7.8. Ook deze werden in de voorgaande secties reeds apart besproken. Waar de eerste oplossingsmethodiek kampte met momentane translatie fouten is dit niet het geval bij de tweede oplossingsmethodiek. Kennelijk verhelpt het transformeren van de flowvectoren in plaats van de camerabeelden dit probleem. De enigste opmerking die hier nogmaals kan worden gemaakt is dat de twee laatste bochten iets wijder zouden moeten zijn als men gaat vergelijken met het originele traject. Maar dat gezegd zijnde, kan men stellen dat het traject van de tweede oplossingsmethodiek het meest voldoet aan de verwachtingen.
(a) Getransformeerde camerabeelden
(b) Getransformeerde flowvectoren
Figuur 7.8: Het bekomen traject bij beide oplossingsmethodieken
Inzake rotatiehoeken behalen beide oplossingsmethodieken zeer goeie resultaten. Al is het de tweede oplossingsmethodiek die er bovenuit steekt. Als besluit van deze vergelijking kan men stellen dat desondanks de tweemaal lagere snelheid, het transformeren van de flowvectoren een betere oplossing is dan het transformeren van het beeld. De verklaring hiervoor kan enerzijds gevonden worden in het feit dat bij de originele beelden de pixelverschuivingen kleiner zijn en preciezer kunnen bepaald worden. Anderzijds komt dit ook omdat er minder distorsie is bij features die op enige afstand van de wagen liggen.
53
���������������������������
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
���������������������������
(a) Getransformeerde camerabeelden
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� �� �� �� �� � �� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Getransformeerde flowvectoren Figuur 7.9: Weergave van de cumulatieve rotatiehoek bij de twee gebruikte oplossingsmethodieken
54
�������������������������
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
�������������������������
(a) Getransformeerde camerabeelden
��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� ��� � � �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� �� ��� �����������������
(b) Getransformeerde flowvectoren Figuur 7.10: Weergave van de momentane rotatiehoek bij de twee gebruikte oplossingsmethodieken
55
�����������������
Aangezien de sparse optical flow methode in combinatie met de least absolute deviations methode toegepast op de originele beelden de beste methodiek blijkt te zijn, wordt hieronder de positiebepaling even naderbij bekeken. In Figuur 7.11 wordt een duidelijkere weergave gegeven van het traject uit Figuur 7.8b. Ook hier wordt het startpunt aangegeven door een groene stip.
�� �� �� �� �� �� �� �� �� �� � � � � � � � � � �� �� �� �� �� �� ��
��
�
��
��
�� �� �� �� �����������������
��
��
��
���
Figuur 7.11: Duidelijkere weergave van het bekomen traject bij de tweede oplossingsmethodiek
Wetende dat de parking bijna 100 meter lang is en de afstand tussen twee rijbanen ongeveer 16 meter is, kan men stellen dat de dimensies van de positiebepaling blijken te kloppen. Al is uit de figuur wel duidelijk af te leiden dat de algemene positiebepaling van deze methode niet erg nauwkeurig is. Dit is vooral te merken na het nemen van de tweede bocht, hier is al een afwijking van 4 meter merkbaar. Net voor het nemen van de derde bocht bedraagt deze afwijking zelfs bijna 8 meter. En door de afwijkende hoek na de derde bocht, lijkt het alsof uiteindelijk het startpunt opnieuw is bereikt, maar dit is natuurlijk slechts toeval. Een reden voor deze systematische afwijking zou ook het gevolg kunnen zijn van een gebrekkige kalibratie, met name de instellingen voor roll, pitch en yaw.
56
7.5
Andere camerabeelden
Om dit hoofdstuk af te sluiten werd de performantste methodiek, namelijk de tweede oplossingsmethodiek (transformeren van de flowvectoren in plaats van de camerabeelden) gebruikmakend van sparse optical flow en de least absolute deviations methode, ook toegepast op een ander traject. De camera werd hierbij achteraan de auto geplaatst om de beelden te maken. In Figuur 7.12 wordt een voorbeeldframe van de originele beelden en het bijhorende gerectificeerde beeld weergegeven. Figuur 7.13 toont het gebruikte masker bij deze camerabeelden.
(a)
(b)
Figuur 7.12: Een voorbeelframe (a) van de beelden bij het nieuwe testtraject en het bijhorende getransformeerde beeld (b)
(a)
(b)
Figuur 7.13: Het gebruikte masker (a) dat toegepast wordt op de originele camerabeelden (b)
57
Wat de parameters bij de perspectieftransformatie betreft, werd gekozen voor volgende waarden: • zijdelingse afwijking van de camera ten opzichte van de lengteas van de wagen: 0 m • afwijking in de lengterichting van de camera ten opzichte van de voorste wielas van de wagen: 0.48 m • camerahoogte ten opzichte van de grond: 1.17 m • camera’s wentellingsgraad (roll ): -0.005 radialen • camera’s hellingsgraad (pitch): -0.507 radialen • camera’s richtingsgraad (yaw ): -0.016 radialen • brandpuntsafstand van de camera: 626.2 pixels • aantal pixels per meter: 20 pixels • framerate: 25 frames per seconde
De enigste parameterwaarde die voor de rest nog werd aangepast is deze van de venstergrootte bij het sparse optical flow algortime. Dit werd namelijk vergroot naar 71x71 pixels aangezien de snelheid van de wagen tijdens dit traject hoger ligt. Dit maakt dat de pixels meer verschuiven en de overeenkomstige pixels dus in een grotere omgeving dienen gezocht te worden. Alle andere parameterwaarden bleven behouden. Het traject stelt een autorit rondom de campus van Hogeschool Gent Campus Schoonmeersen voor. Een grafische weergave hiervan wordt getoond in Figuur 7.14. Vertrekkende vanop de parking (aangeduid met een groene stip) wordt er via gebouw B naar de Voskenslaan gereden om uiteindelijk via gebouw P terug uit te komen op de parking.
Figuur 7.14: Weergave van het tweede traject
58
Het uiteindelijke resultaat wordt weergegeven in Figuur 7.15, maar lijkt alles behalve te kloppen.
Figuur 7.15: Het bekomen traject bij het toepassen van de voorgestelde oplossingsmethodiek op de andere camerabeelden
Ter vergelijking werden nummers toegevoegd aan de meest significante delen van het originele traject en aan de overeenkomstige plaatsen bij het bekomen traject. Dit wordt weergegeven in Figuur 7.16.
(a)
(b)
Figuur 7.16: Vergelijking van beide trajecten bij de andere camerabeelden. (a) het origineel, (b) het bekomen resultaat
59
Tot en met de vierde bocht lijkt alles goed te gaan, maar vanaf dan duiken er zo te zien enorm veel foute meetresultaten op. De bocht bij plaats 5 in de figuur is nog net herkenbaar, maar deze bij plaats 6 zijn helemaal verkeerd ingeschat. Het traject vanaf plaats 6 tot en met plaats 9 lijkt goed gemeten, maar de verhoudingen kloppen niet. Het traject tussen 7 en 9 zou bijvoorbeeld veel langer moeten zijn (ongeveer tweemaal het traject tussen 6 en 7). De bocht bij plaats 10 is ook helemaal fout en de flauwe bocht bij 11 is nauwelijks herkenbaar. Het is pas wanneer men terug de parking bereikt (plaats 12 en verder) dat opnieuw acceptabele metingen teruggegeven worden. Het is dus duidelijk dat er heel wat significante stukken blijken te ontbreken of helemaal niet de juiste vorm bezitten. In Figuur 7.17 worden twee voorbeelden gegeven waarbij het optical flow algoritme het lastig heeft met het zoeken naar het juiste corresponderende beeldpunt in de volgende frame. Deze zijn respectievelijk afkomstig uit plaatsen 5 en 8 uit het traject.
Figuur 7.17: Twee voorbeeldframes waarbij het zoeken naar de corresponderende beeldpunten foutloopt
60
Maar ook bij situaties waar veel contrast aanwezig is bij de ondergrond loopt het ook mis. Figuur 7.18 toont twee voorbeelden waarbij over stenen klinkers wordt gereden en de beeldpunten foutief met elkaar worden gekoppeld. De flowvectoren geven in beide gevallen aan dat de wagen een bocht naar rechts aan het nemen is terwijl de wagen in feite rechtdoor rijdt. De beeldfragmenten zijn respectievelijk afkomstig uit plaatsen 6 en 8 uit het traject. Het algoritme maakt deze verkeerde inschatting vanwege het zo sterk op elkaar lijken van de straatstenen. Het is dan ook daardoor dat verkeerde beeldpunten met elkaar worden gekoppeld.
Figuur 7.18: Twee voorbeeldframes waarbij het koppelen van beeldpunten foutloopt desondanks de hoge mate van contrast in het beeld
In Figuur 7.19 wordt nog een andere situatie waarbij de methodiek in de mist gaat eens van naderbij bekeken en wordt de kostencurve van de least absolute deviations methode berekend. Het gaat hier om een situatie uit plaats 6 in het traject waarbij een bocht naar links wordt gemaakt. Hier kan men zien dat het momentane rotatiecentrum verkeerd wordt ingeschat aangezien het globale minimum hier op nog geen meter van het nulpunt (centrum van de achterste as van de wagen) ligt. Daarenboven is dat zelfs onmogelijk voor een wagen die voortbeweegt op een reguliere manier. De curve toont ook nog een tweede minimum, dit zou een meer acceptabel minimum kunnen zijn aangezien dit een rotatiecentrum op 5 meter van het middelpunt van de achterste as van de wagen aangeeft. Dit vertaalt zich naar een scherpe linkse bocht en dat was in deze situatie het geval.
61
��� ��� ���
����
��� ��� ��� ��� ��� ��� ��
�� �� �� �� �� � �� �� �� �� �� �������������������������������������������
�� ���
Figuur 7.19: Kostencurve van ´e´en van de voorbeeldsituaties waarbij de bepaling van de correcte flowvectoren misloopt
Het voorkomen van deze foutieve metingen heeft echter verschillende oorzaken. Allereerst zijn de beelden van dit nieuwe traject iets minder scherp dan de beelden van het vorige traject waardoor het correct koppelen van beeldpunten op zich al moeilijker wordt. Ten tweede is er de ondergrond die een cruciale rol speelt. De voorgestelde oplossingsmethodiek is namelijk hoofdzakelijk afhankelijk van de textuur van de ondergrond in de gebruikte camerabeelden. Bij het zoeken naar features en vooral bij het zoeken naar de bijhorende features in het volgende frame is een ruwe textuur met veel contrast zeer wenselijk. Zoals reeds duidelijk was bij de beelden van het eerste traject (achtvormig parcours op de parking) is de ondergrond op de parking hier zeer goed voor geschikt. Maar in de beelden van dit nieuwe traject komen ook andere delen voor, delen met zowel veel als weinig contrast (zie Figuren 7.17 en 7.18). Het zijn dan ook deze andere delen die het optical flow algoritme parten spelen. Bij de delen met weinig contrast in het beeld is het de vage grijze asfalt die voor problemen zorgt en bij de delen met veel contrast zoals bijvoorbeeld in Figuur 7.18 is het het patroon van de klinkers die voor verwarring zorgt. Ten derde kan er ook nog opgemerkt worden dat de camera lager op de wagen en dus dichter bij het wegdek werd geplaatst dan bij het vorige traject. Dit maakt dat de pixels ogenschijnlijk sneller verschuiven en moeten de corresponderende beeldpunten verder worden gezocht. Daarenboven ligt de snelheid van de wagen ook nog eens hoger wat dit effect alleen maar vergroot. Dit is dan ook de reden waarom voor een grotere venstergrootte werd gekozen bij het sparse optical flow algoritme. Als laatste vermelden we net zoals in de vorige sectie de mogelijkheid dat de gebrekkige kalibratie (instellingen roll, pitch en yaw) hierin ook een rol kunnen spelen. In deze sectie werd de toepasbaarheid van de voorgestelde oplossingsmethodiek op een ander traject met andere camerabeelden nagegaan. Uit de resultaten is gebleken dat de voorgestelde oplossingsmethodiek zoals hij nu is uitgewerkt echter ondermaats presteert. Vooral de afhankelijkheid van de juiste mate van contrast in de beelden en het niet bestand zijn tegen bepaalde patronen in de weg hebben hier de bovenhand genomen.
62
Hoofdstuk 8
Toekomstig werk In dit hoofdstuk zullen nog enkele voorstellen gedaan worden inzake de verdere uitwerking en verbetering van de voorgestelde oplossingsmethodiek in dit werk.
8.1
Parameteroptimalisatie
Er is nog te weinig ingegaan op het effect van de camerainstellingen op de behaalde resultaten. Zoals reeds vermeld werd, kan de systematische afwijking bij enkele resultaten immers het gevolg zijn van gebrekkige kalibratie, met name de instellingen voor roll, pitch en yaw. Maar ook de parameters bij de verschillende gebruikte methodes binnen de oplossingsmethodiek kunnen eventueel nog worden geoptimaliseerd aangezien deze op dit moment slechts suboptimaal werden bepaald aan de hand van de huidige camerainstellingen. Zoals in het voorgaande hoofdstuk werd vermeld was het nodig de venstergrootte aan te passen bij het gebruik van de camerabeelden waarbij de camera achteraan de wagen werd geplaatst. De snelheid van de wagen lag tijdens dit traject namelijk hoger waardoor de beeldpunten meer opschoven. Hierdoor moest de omgeving waarbinnen het corresponderende beeldpunt in de daaropvolgende frame diende gezocht te worden dus groter zijn. Een mogelijkheid hierbij is het automatisch laten vergroten en verkleinen van deze parameter. Wanneer er sneller gereden wordt en er dus gedetecteerd wordt dat de beeldpunten meer lijken op te schuiven moet de venstergrootte groter worden. Omgekeerd dient dit natuurlijk ook het geval te zijn.
8.2
Verdere optimalisatie van de gebruikte methodes
Bij de toepassing van de voorgestelde oplossingsmethodiek op de camerabeelden van het andere traject werd het duidelijk dat deze methodiek niet feilloos is in elke situatie. Verdere optimalisatie aan de hand van de beelden waarbij de methodes falen bij de correcte inschatting van de relatieve beweging is dus niet overbodig. Een voorbeeld van zo een incorrecte inschatting werd weergegeven in Figuur 7.19. Men zou het principe van lowpass filtering kunnen toepassen bij de gebruikte regularisatiemethodes. Bij de least-squares methode zouden er dan vereisten zoals bijvoorbeeld een
63
minimum aan gladheid kunnen worden opgelegd aan de kostencurve.
8.3
Automatische foutcorrectie
Op dit moment is het nog steeds mogelijk dat ´e´en enkele foutieve meting op frameniveau het globale resultaat sterk kan be¨ınvloeden. Als er door ruis of uitschieters toevallig een extreem grote momentane rotatiehoek zou worden gemeten (alles boven 2 graden per frame kan als hoog worden beschouwd), dan heeft dit gevolgen voor alle daaropvolgende metingen. Het is namelijk zo dat alle positiebepalingen die daarna volgen, gebruikmaken van de cumulatieve hoek die verstoord is door deze eenmalige foutieve meting. Het inbouwen van feedback zou kunnen aangeven dat bij het rechtdoorrijden niet meteen momentane rotatiehoeken van boven 1 graad moeten verwacht worden aangezien de voorgaande meting nul graden aangaf. Het principe hierbij is dat een wagen op een vloeiende manier bochten neemt en bijvoorbeeld niet plots 90 graden kan draaien rond zijn as. Dit betekent dus dat de rotatiehoeken slechts met kleine stappen mogen vari¨eren en niet sterk mogen afwijken van de vorige waarde.
8.4
Kwantitatieve analyse
Aangezien er slechts werd getest op twee verschillende trajecten kan men spreken van een beperkte dataset. Meer testen op meer trajecten zou zeker bijdragen tot verbeteringen van de oplossingsmethodiek en dient in de toekomst nog te worden uitgevoerd. Daarbij kan gefocust worden op specifieke situaties en hun specifieke eigenschappen wat de omgeving betreft. In de zomer zou het vele zonlicht een nadeel kunnen zijn als de zon rechtstreeks in de camera zou schijnen bijvoorbeeld. Sneeuw in de winter zou het wegdek helemaal kunnen bedekken waardoor er weinig of geen contrast meer op te merken valt en het bepalen van de correcte flowvectoren bemoeilijkt wordt. Maar ook het eventuele effect van regen en mist dient nagegaan te worden. In dit werk werd steeds aangenomen dat het volledige beeld beschikbaar is, maar de camera zou kunnen besmeurd geraken waardoor slechts een gedeelte van de weg zichtbaar wordt. Het testen of de methode dan nog naar behoren presteert kan ook zeker als een meerwaarde beschouwd worden. Bij de gebruikte camerabeelden is weinig hinder door ander verkeer op te merken. Hier en daar wel eens een fietser die door het beeld passeert of een wagen die in de omgekeerde richting rijdt op het andere rijvak, maar voor de rest niet noemenswaardig. Het testen of de methode hier tegen bestand is, is ook zeker een factor om mee rekening te houden.
64
8.5
Combinatie met andere systemen
In het begin van dit werk werd de problematiek bij navigatiesystemen aangehaald en werd deze methode als mogelijke oplossing voorgesteld. De huidige staat van deze methodiek biedt echter geen waterdichte oplossing en zeker niet wanneer deze methode los van andere systemen wordt gebruikt. Het zou daarom nuttig kunnen zijn om bijvoorbeeld GPS-data te gebruiken om foutcorrectie toe te passen waar nodig. Ook het gebruik van offline-mapping van het huidige bepaalde traject kan een nuttige aanvulling zijn. Situaties waarbij de wagen doelbewust van de weg afwijkt komen namelijk weinig voor. Daarenboven kan ook het gebruik van sensoren zoals een accelerometer of een gyroscoop enorm zinvol zijn. Zo goed als alle bovengenoemde systemen zijn terug te vinden in de meeste hedendaagse smartphones. Hierdoor kan men stellen dat implementatie van deze technologie¨en in wagens ter ondersteuning van de voorgestelde methodiek geen al te grote meerkost met zich mee zou mogen brengen. Deze optie kan dus als een realistische mogelijkheid tot uitbreiding van deze oplossing worden beschouwd.
65
Hoofdstuk 9
Conclusie 9.1
Algemeen
Het wegvallen of verstoord geraken van satellietsignalen vormt heden ten dage nog steeds een probleem bij de precieze positiebepaling door routenavigatiesystemen zoals bijvoorbeeld GPS. In dit werk werd een mogelijke oplossing hiervoor voorgesteld die het mogelijk maakt aan de hand van camerabeelden de relatieve beweging van een auto te achterhalen. De enkelvoudige camera wordt vooraan of achteraan de wagen bevestigd en is gericht naar de weg. Aan de hand van optical flow (een methode binnen de visuele odometrie) wordt vervolgens nagegaan hoe de omgeving beweegt ten opzichte van de wagen. Mits toepassing van de juiste regularisatietechnieken zal uiteindelijk met deze gefilterde informatie een schatting worden gemaakt van de relatieve voortbeweging van de wagen.
9.2
Performantie
Zoals uit de resultaten bij de drie vergelijkingen in Hoofdstuk 7 is gebleken, scoort de combinatie van het sparse optical flow algoritme, het transformeren van de flowvectoren en de least absolute deviations methode globaal gezien het best in vergelijking met de andere mogelijke oplossingsmethodieken. Over de uitvoeringstijd kan men zeggen dat de voorgestelde oplossing naar behoren werkt. Al tonen de resultaten uit Hoofdstuk 7 aan dat de oplossing in zijn huidige staat er niet in slaagt in real-time de relatieve beweging te achterhalen. De framerate van de camerabeelden ligt immers hoger dan het aantal frames dat per seconde kan worden verwerkt. Wat betreft de positiebepaling kan men opmerken dat alles afhangt van het optical flow algoritme. Enkel en alleen wanneer de correcte beeldpunten met elkaar gekoppeld worden, kan er nagenoeg een correcte inschatting van de relatieve beweging worden gemaakt. Als kanttekening hierbij kan worden vermeld dat de camerainstellingen een belangrijke rol spelen bij de nauwkeurigheid van de positiebepaling. Voortbouwend op het voorgaande kan men zeggen dat de hele methodiek zeer ondergrondsafhankelijk is. Alles hangt af van de juiste hoeveelheid contrast in het beeld en
66
dan voornamelijk op de weg. Is er weinig contrast dan koppelt het algoritme de verkeerde beeldpunten doordat er te veel beeldpunten zijn die op elkaar lijken. Maar is er net zeer veel contrast door een patroon in de straatstenen, dan kunnen alsnog verkeerde beeldpunten gekoppeld worden net omdat de randen en hoeken van de verschillende straatstenen zo goed op elkaar lijken. Algemeen kan men stellen dat deze voorgestelde oplossingsmethodiek conceptueel meer dan geslaagd is. Maar als naar de nauwkeurigheid inzake positiebepaling en de toepasbaarheid bij andere ondergronden wordt gekeken, kan men concluderen dat deze voorgestelde oplossing in zijn huidige staat zeker geen alleenstaande oplossing genoemd kan worden en daarenboven nog verbetering kan gebruiken.
67
Bibliografie [1] O. Amidi, T. Kanade, and R. Miller. Vision-based autonomous helicopter research at carnegie mellon robotics institute 1991-1997. American Helicopter Society, 1998. [2] J. Barron, D. Fleet, and S. Beauchemin. Performance of optical flow techniques. International journal of computer vision, 12(1):43–77, 1994. [3] H. Bay, T. Tuytelaars, and L. Van Gool. Surf: Speeded up robust features. In Computer Vision–ECCV 2006, pages 404–417. Springer, 2006. [4] J. Bouguet. Visual methods for three-dimensional modeling. PhD thesis, California Institute of Technology, 1999. [5] J. Bouguet. Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5, 2001. [6] T. Broida and R. Chellappa. Estimation of object motion parameters from noisy images. Pattern Analysis and Machine Intelligence, IEEE Transactions on, (1):90– 99, 1986. [7] J. Campbell, R. Sukthankar, I. Nourbakhsh, and A. Pahwa. A robust visual odometry and precipice detection system using consumer-grade monocular vision. In Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, pages 3421–3427. IEEE, 2005. [8] J. Canny. A computational approach to edge detection. Pattern Analysis and Machine Intelligence, IEEE Transactions on, (6):679–698, 1986. [9] F. Caron, E. Duflos, D. Pomorski, and P. Vanheeghe. Gps/imu data fusion using multisensor kalman filtering: introduction of contextual aspects. Information Fusion, 7(2):221–230, 2006. [10] A. Davison, I. Reid, N. Molton, and O. Stasse. Monoslam: Real-time single camera slam. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(6):1052– 1067, 2007. [11] L. Dreschler and H-H Nagel. Volumetric model and 3d trajectory of a moving car derived from monocular tv frame sequences of a street scene. Computer Graphics and Image Processing, 20(3):199–228, 1982. [12] B. Eissfeller, G. Ameres, V. Kropp, and D. Sanroma. Performance of gps, glonass and galileo. In Photogrammetric Week, volume 7, pages 185–199, 2007.
68
[13] G. Farneb¨ ack. Two-frame motion estimation based on polynomial expansion. In Image Analysis, pages 363–370. Springer, 2003. [14] F. Fraundorfer and D. Scaramuzza. Visual odometry part ii: Matching, robustness, optimization, and applications. Robotics and Automation Magazine, IEEE, 19(2):78– 90, June 2012. [15] C. Harris and M. Stephens. A combined corner and edge detector. In Alvey vision conference, volume 15, page 50. Manchester, UK, 1988. [16] R. Hartley and A. Zisserman. Multiple view geometry in computer vision. Cambridge university press, 2003. [17] B. Horn and B. Schunck. Determining optical flow. In 1981 Technical Symposium East, pages 319–331. International Society for Optics and Photonics, 1981. [18] B. Horn and E. Weldon Jr. Direct methods for recovering motion. International Journal of Computer Vision, 2(1):51–76, 1988. [19] S. Ji, W. Chen, X. Ding, Y. Chen, C. Zhao, and C. Hu. Potential benefits of gps/glonass/galileo integration in an urban canyon hong kong. Journal of Navigation, 63:681–693, October 2010. [20] B. Kitt, A. Geiger, and H. Lategahn. Visual odometry based on stereo image sequences with ransac-based outlier rejection scheme. Intelligent Vehicles Symposium (IV), 2010 IEEE, pages 486–492, June 2010. [21] A. Levin and R. Szeliski. Visual odometry and map correlation. In Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, volume 1, pages I–611. IEEE, 2004. [22] D. Lowe. Object recognition from local scale-invariant features. In Computer vision, 1999. The proceedings of the seventh IEEE international conference on, volume 2, pages 1150–1157. Ieee, 1999. [23] B. Lucas, T. Kanade, et al. An iterative image registration technique with an application to stereo vision. In IJCAI, volume 81, pages 674–679, 1981. [24] M. Maimone, Y. Cheng, and L. Matthies. Two years of visual odometry on the mars exploration rovers. Journal of Field Robotics, 24(3):169–186, 2007. [25] D. Nist´er. An efficient solution to the five-point relative pose problem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(6):756–770, 2004. [26] D. Nist´er. Preemptive ransac for live structure and motion estimation. Machine Vision and Applications, 16(5):321–329, 2005. [27] D. Nist´er, O. Naroditsky, and J. Bergen. Visual odometry. Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, 1:652–659, June-July 2004. [28] D. Nist´er, O. Naroditsky, and J. Bergen. Visual odometry for ground vehicle applications. Journal of Field Robotics, 23(1):3–20, 2006.
69
[29] N. Nourani-Vatani, P. Borges, and J. Roberts. A study of feature extraction algorithms for optical flow tracking. In Australasian Conference on Robotics and Automation, 2012. [30] S. Obdrz´ alek and J. Matas. A voting strategy for visual ego-motion from stereo. Intelligent Vehicles Symposium (IV), 2010 IEEE, pages 382–387, June 2010. [31] P. O’Donovan. Optical flow: Techniques and applications. Saskatchewan, TR, 502425, 2005.
The University of
[32] D. Scaramuzza and F. Fraundorfer. Visual odometry part i: The first 30 years and fundamentals. Robotics & Automation Magazine, IEEE, 18(4):80–92, 2011. [33] D. Scaramuzza, F. Fraundorfer, and R. Siegwart. Real-time monocular visual odometry for on-road vehicles with 1-point ransac. IEEE International Conference on Robotics and Automation, 2009. ICRA ’09, pages 4293–4299, May 2009. [34] O. Shakernia, R. Vidal, and S. Sastry. Infinitesimal motion estimation from multiple central panoramic views. In Motion and Video Computing, 2002. Proceedings. Workshop on, pages 229–234. IEEE, 2002. [35] J. Shi and C. Tomasi. Good features to track. In Computer Vision and Pattern Recognition, 1994. Proceedings CVPR’94., 1994 IEEE Computer Society Conference on, pages 593–600. IEEE, 1994. [36] P. Simionescu and D. Beale. Optimum synthesis of the four-bar function generator in its symmetric embodiment: the ackermann steering linkage. Mechanism and Machine Theory, 37(12):1487–1504, 2002. [37] M. Tao, J. Bai, P. Kohli, and S. Paris. Simpleflow: A non-iterative, sublinear optical flow algorithm. In Computer Graphics Forum, volume 31, pages 345–353. Wiley Online Library, 2012. [38] J.-P Tardif, Y. Pavlidis, and K. Daniilidis. Monocular visual odometry in urban environments using an omnidirectional camera. IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2008, pages 2531–2538, September 2008. [39] S. Thrun et al. Robotic mapping: A survey. Exploring artificial intelligence in the new millennium, pages 1–35, 2002. [40] B. Triggs, P. McLauchlan, R. Hartley, and A. Fitzgibbon. Bundle adjustmenta modern synthesis. In Vision algorithms: theory and practice, pages 298–372. Springer, 2000. [41] D. Van Hamme, P. Veelaert, and W. Philips. Communicationless navigation through robust visual odometry. International IEEE Conference on Intelligent Transportation Systems (ITSC), pages 1555–1560, September 2012. [42] H. William, S. Teukolsky, W. Vetterling, and B. Flannery. Numerical recipes in C, volume 2. Citeseer, 1996.
70
