Thesis (MScEng)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Simultaneous localization and mapping (SLAM) is vital for autonomous robot navigation. The robot
must build a map of its environment while tracking its own motion through that map. Although
many solutions to this intricate problem have been proposed, one of the most prominent issues that
still needs to be resolved is to accurately measure and track landmarks over time. In this thesis we
investigate the use of stereo vision for this purpose.
In order to find landmarks in images we explore the use of two feature detectors: the scale-invariant
feature transform (SIFT) and speeded-up robust features (SURF). Both these algorithms find salient
points in images and calculate a descriptor for each point that is invariant to scale, rotation and
illumination. By using the descriptors we match these image features between stereo images and
use the geometry of the system to calculate a set of 3D landmark measurements. A Taylor approximation
of this transformation is used to derive a Gaussian noise model for the measurements.
The measured landmarks are matched to landmarks in a map to find correspondences. We find that
this process often incorrectly matches ambiguous landmarks. To find these mismatches we develop
a novel outlier detection scheme based on the random sample consensus (RANSAC) framework. We
use a similarity transformation for the RANSAC model and derive a probabilistic consensus measure
that takes the uncertainties of landmark locations into account. Through simulation and practical
tests we find that this method is a significant improvement on the standard approach of using the
fundamental matrix.
With accurately identified landmarks we are able to perform SLAM. We investigate the use of three
popular SLAM algorithms: EKF SLAM, FastSLAM and FastSLAM 2. EKF SLAM uses a Gaussian
distribution to describe the systems states and linearizes the motion and measurement equations
with Taylor approximations. The two FastSLAM algorithms are based on the Rao-Blackwellized
particle filter that uses particles to describe the robot states, and EKFs to estimate the landmark
states. FastSLAM 2 uses a refinement process to decrease the size of the proposal distribution and
in doing so decreases the number of particles needed for accurate SLAM.
We test the three SLAM algorithms extensively in a simulation environment and find that all three
are capable of very accurate results under the right circumstances. EKF SLAM displays extreme
sensitivity to landmark mismatches. FastSLAM, on the other hand, is considerably more robust
against landmark mismatches but is unable to describe the six-dimensional state vector required for
3D SLAM. FastSLAM 2 offers a good compromise between efficiency and accuracy, and performs
well overall.
In order to evaluate the complete system we test it with real world data. We find that our outlier
detection algorithm is very effective and greatly increases the accuracy of the SLAM systems. We
compare results obtained by all three SLAM systems, with both feature detection algorithms, against
DGPS ground truth data and achieve accuracies comparable to other state-of-the-art systems.
From our results we conclude that stereo vision is viable as a sensor for SLAM. / AFRIKAANSE OPSOMMING: Gelyktydige lokalisering en kartering (simultaneous localization and mapping, SLAM) is ’n noodsaaklike
proses in outomatiese robot-navigasie. Die robot moet ’n kaart bou van sy omgewing en
tegelykertyd sy eie beweging deur die kaart bepaal. Alhoewel daar baie oplossings vir hierdie ingewikkelde
probleem bestaan, moet een belangrike saak nog opgelos word, naamlik om landmerke
met verloop van tyd akkuraat op te spoor en te meet. In hierdie tesis ondersoek ons die moontlikheid
om stereo-visie vir hierdie doel te gebruik.
Ons ondersoek die gebruik van twee beeldkenmerk-onttrekkers: scale-invariant feature transform
(SIFT) en speeded-up robust features (SURF). Altwee algoritmes vind toepaslike punte in beelde en
bereken ’n beskrywer vir elke punt wat onveranderlik is ten opsigte van skaal, rotasie en beligting.
Deur die beskrywer te gebruik, kan ons ooreenstemmende beeldkenmerke soek en die geometrie
van die stelsel gebruik om ’n stel driedimensionele landmerkmetings te bereken. Ons gebruik ’n
Taylor- benadering van hierdie transformasie om ’n Gaussiese ruis-model vir die metings te herlei.
Die gemete landmerke se beskrywers word dan vergelyk met dié van landmerke in ’n kaart om
ooreenkomste te vind. Hierdie proses maak egter dikwels foute. Om die foutiewe ooreenkomste
op te spoor het ons ’n nuwe uitskieterherkenningsalgoritme ontwikkel wat gebaseer is op die
RANSAC-raamwerk. Ons gebruik ’n gelykvormigheidstransformasie vir die RANSAC-model en lei ’n
konsensusmate af wat die onsekerhede van die ligging van landmerke in ag neem. Met simulasie en
praktiese toetse stel ons vas dat die metode ’n beduidende verbetering op die standaardprosedure,
waar die fundamentele matriks gebruik word, is.
Met ons akkuraat geïdentifiseerde landmerke kan ons dan SLAM uitvoer. Ons ondersoek die gebruik
van drie SLAM-algoritmes: EKF SLAM, FastSLAM en FastSLAM 2. EKF SLAM gebruik ’n Gaussiese
verspreiding om die stelseltoestande te beskryf en Taylor-benaderings om die bewegings- en meetvergelykings
te lineariseer. Die twee FastSLAM-algoritmes is gebaseer op die Rao-Blackwell partikelfilter
wat partikels gebruik om robottoestande te beskryf en EKF’s om die landmerktoestande af te
skat. FastSLAM 2 gebruik ’n verfyningsproses om die grootte van die voorstelverspreiding te verminder
en dus die aantal partikels wat vir akkurate SLAM benodig word, te verminder.
Ons toets die drie SLAM-algoritmes deeglik in ’n simulasie-omgewing en vind dat al drie onder die
regte omstandighede akkurate resultate kan behaal. EKF SLAM is egter baie sensitief vir foutiewe
landmerkooreenkomste. FastSLAM is meer bestand daarteen, maar kan nie die sesdimensionele
verspreiding wat vir 3D SLAM vereis word, beskryf nie. FastSLAM 2 bied ’n goeie kompromie
tussen effektiwiteit en akkuraatheid, en presteer oor die algemeen goed.
Ons toets die hele stelsel met werklike data om dit te evalueer, en vind dat ons uitskieterherkenningsalgoritme
baie effektief is en die akkuraatheid van die SLAM-stelsels beduidend verbeter. Ons
vergelyk resultate van die drie SLAM-stelsels met onafhanklike DGPS-data, wat as korrek beskou
kan word, en behaal akkuraatheid wat vergelykbaar is met ander toonaangewende stelsels.
Ons resultate lei tot die gevolgtrekking dat stereo-visie ’n lewensvatbare sensor vir SLAM is.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/71593 |
| Date | 12 1900 |
| Creators | Brink, Wikus |
| Contributors | Van Daalen, C. E., Brink, W. H., Stellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | 83 p. : ill. |
| Rights | Stellenbosch University |
Page generated in 0.003 seconds