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.

No description available.