Thesis (MSc (Mathematics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: In this thesis we consider the essential topics relating to stereo-vision and the correspondence
problem in general. The aim is to reconstruct a dense 3D scene from
images captured by two spatially related cameras. Our main focus, however, is on
speed and real-time implementation on a standard desktop PC. We wish to use
the CPU to solve the correspondence problem and to reserve the GPU for model
rendering. We discuss three fundamental types of algorithms and evaluate their
suitability to this end. We eventually choose to implement a hierarchical version of
the dynamic programming algorithm, because of the good balance between accuracy
and speed. As we build our system from the ground up we gradually introduce
necessary concepts and established geometric principles, common to most stereovision
systems, and discuss them as they become relevant. It becomes clear that the
greatest weakness of the hierarchical dynamic programming algorithm is scanline
inconsistency. We nd that the one-dimensional LULU- lter is computationally inexpensive
and e ective at removing outliers when applied across the scanlines. We
take advantage of the hierarchical structure of our algorithm and sub-pixel re nement
to produce results at video rates (roughly 20 frames per second). A 3D model
is also constructed at video rates in an on-line system with only a small delay between
obtaining the input images and rendering the model. Not only is the quality
of our results highly competitive with those of other state of the art algorithms, but
the achievable speed is also considerably faster. / AFRIKAANSE OPSOMMING: In hierdie tesis beskou ons die noodsaaklike onderwerpe wat in die algemeen verband
hou met stereovisie en die ooreenstemmingsprobleem. Die mikpunt is om 'n digte
3D toneel te rekonstrueer vanaf beelde wat deur twee ruimtelik-verwante kameras
vasgelê is. Ons hoofdoel is egter spoed, en intydse implementering op 'n standaard
rekenaar. Ons wil die SVE (CPU) gebruik om die ooreenstemmingsprobleem op
te los, en reserveer die GVE (GPU) vir model-beraping. Ons bespreek drie fundamentele
tipes algoritmes en evalueer hul geskiktheid vir hierdie doel. Ons kies
uiteindelik om 'n hiërargiese weergawe van die dinamiese programmeringsalgoritme
te implementeer, as gevolg van die goeie balans tussen akkuraatheid en spoed. Soos
wat ons ons stelsel van die grond af opbou, stel ons geleidelik nodige konsepte voor
en vestig meetkundige beginsels, algemeen tot meeste stereovisie stelsels, en bespreek
dit soos dit toepaslik word. Dit word duidelik dat skandeerlyn-strydigheid die
grootste swakheid van die hiërargiese dinamiese programmeringsalgoritme is. Ons
vind dat die een-dimensionele LULU- lter goedkoop is in terme van berekeninge,
en e ektief aangewend kan word om uitskieters te verwyder as dit dwarsoor skandeerlyne
toegepas word. Ons buit die hiërargiese struktuur van ons algoritme uit en
kombineer dit met sub-piksel verfyning om resultate te produseer teen video tempo
(ongeveer 20 raampies per sekonde). 'n 3D model word ook gekonstrueer teen video
tempo in 'n stelsel wat aanlyn loop, met slegs 'n klein vertraging tussen die verkryging
van die intree-beelde en die beraping van die model. Die kwaliteit van ons
resultate is nie net hoogs mededingend met dié van die heel beste algoritmes nie,
maar die verkrygbare spoed is ook beduidend vinniger.
Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/4294 |
Date | 03 1900 |
Creators | Singels, Francois |
Contributors | Brink, Willie, Herbst, Ben, University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. |
Publisher | Stellenbosch : University of Stellenbosch |
Source Sets | South African National ETD Portal |
Language | English |
Detected Language | Unknown |
Type | Thesis |
Format | 33 p. : ill. |
Rights | University of Stellenbosch |
Page generated in 0.0015 seconds