Thesis (MEng)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: This thesis investigates the use of stereo vision sensors for dense autonomous mapping. It characterises and analyses the errors made during the stereo matching process so measurements can be correctly integrated into a 3D grid-based map. Maps are required for navigation and obstacle avoidance on autonomous vehicles in complex, unknown environments. The safety of the vehicle as well as the public depends on an accurate mapping of the environment of the vehicle, which can be problematic when inaccurate sensors such as stereo vision are used. Stereo vision sensors are relatively cheap and convenient, however, and a system that can create reliable maps using them would be beneficial. A literature review suggests that occupancy grid mapping poses an appropriate solution, offering dense maps that can be extended with additional measurements incrementally. It forms a grid representation of the environment by dividing it into cells, and assigns a probability to each cell of being occupied. These probabilities are updated with measurements using a sensor model that relates measurements to occupancy probabilities. Numerous forms of these sensor models exist, but none of them appear to be based on meaningful assumptions and sound statistical principles. Furthermore, they all seem to be limited by an assumption of unimodal, zero-mean Gaussian measurement noise. Therefore, we derive a principled inverse sensor model (PRISM) based on physically meaningful assumptions. This model is capable of approximating any realistic measurement error distribution using a Gaussian mixture model (GMM). Training a GMM requires a characterisation of the measurement errors, which are related to the environment as well as which stereo matching technique is used. Therefore, a method for fitting a GMM to the error distribution of a sensor using measurements and ground truth is presented. Since we may consider the derived principled inverse sensor model to be theoretically correct under its assumptions, we use it to evaluate the approximations made by other models from the literature that are designed for execution speed. We show that at close range these models generally offer good approximations that worsen with an increase in measurement distance. We test our model by creating maps using synthetic and real world data. Comparing its results to those of sensor models from the literature suggests that our model calculates occupancy probabilities reliably. Since our model captures the limited measurement range of stereo vision, we conclude that more accurate sensors are required for mapping at greater distances. / AFRIKAANSE OPSOMMING: Hierdie tesis ondersoek die gebruik van stereovisie sensors vir digte outonome kartering. Dit karakteriseer en ontleed die foute wat gemaak word tydens die stereopassingsproses sodat metings korrek geïntegreer kan word in 'n 3D rooster-gebaseerde kaart. Sulke kaarte is nodig vir die navigasie en hindernisvermyding van outonome voertuie in komplekse en onbekende omgewings. Die veiligheid van die voertuig sowel as die publiek hang af van 'n akkurate kartering van die voertuig se omgewing, wat problematies kan wees wanneer onakkurate sensors soos stereovisie gebruik word. Hierdie sensors is egter relatief goedkoop en gerieflik, en daarom behoort 'n stelsel wat hulle dit gebruik om op 'n betroubare manier kaarte te skep baie voordelig te wees. 'n Literatuuroorsig dui daarop dat die besettingsroosteralgoritme 'n geskikte oplossing bied, aangesien dit digte kaarte skep wat met bykomende metings uitgebrei kan word. Hierdie algoritme skep 'n roostervoorstelling van die omgewing en ken 'n waarskynlikheid dat dit beset is aan elke sel in die voorstelling toe. Hierdie waarskynlikhede word deur nuwe metings opgedateer deur gebruik te maak van 'n sensormodel wat beskryf hoe metings verband hou met besettingswaarskynlikhede. Menigde a eidings bestaan vir hierdie sensormodelle, maar dit blyk dat geen van die modelle gebaseer is op betekenisvolle aannames en statistiese beginsels nie. Verder lyk dit asof elkeen beperk word deur 'n aanname van enkelmodale, nul-gemiddelde Gaussiese metingsgeraas. Ons lei 'n beginselfundeerde omgekeerde sensormodel af wat gebaseer is op fisies betekenisvolle aannames. Hierdie model is in staat om enige realistiese foutverspreiding te weerspieël deur die gebruik van 'n Gaussiese mengselmodel (GMM). Dit vereis 'n karakterisering van 'n stereovisie sensor se metingsfoute, wat afhang van die omgewing sowel as watter stereopassingstegniek gebruik is. Daarom stel ons 'n metode voor wat die foutverspreiding van die sensor met behulp van 'n GMM modelleer deur gebruik te maak van metings en absolute verwysings. Die afgeleide ge inverteerde sensormodel is teoreties korrek en kan gevolglik gebruik word om modelle uit die literatuur wat vir uitvoerspoed ontwerp is te evalueer. Ons wys dat op kort afstande die modelle oor die algemeen goeie benaderings bied wat versleg soos die metingsafstand toeneem. Ons toets ons nuwe model deur kaarte te skep met gesimuleerde data, sintetiese data, en werklike data. Vergelykings tussen hierdie resultate en dié van sensormodelle uit die literatuur dui daarop dat ons model besettingswaarskynlikhede betroubaar bereken. Aangesien ons model die beperkte metingsafstand van stereovisie vasvang, lei ons af dat meer akkurate sensors benodig word vir kartering oor groter afstande.

Self-driving cars have recently become a challenging research topic, with the aim of making transportation safer and more efficient. Current advanced driving assistance systems (ADAS) allow cars to drive autonomously by following lane markings, identifying road signs and detecting pedestrians and other vehicles. In this thesis work we improve the robustness of autonomous cars by designing an on-road obstacle detection system. The proposed solution consists on the low-level fusion of radar and lidar through the occupancy grid framework. Two inference theories are implemented and evaluated: Bayesian probability theory and Dempster-Shafer theory of evidence. Obstacle detection is performed through image processing of the occupancy grid. Last, the Dempster-Shafer additional features are leveraged by proposing a sensor performance estimation module and performing advanced conflict management. The work has been carried out at Volvo Car Corporation, where real experiments on a test vehicle have been performed under different environmental conditions and types of objects. The system has been evaluated according to the quality of the resulting occupancy grids, detection rate as well as information content in terms of entropy. The results show a significant improvement of the detection rate over single-sensor approaches. Furthermore, the Dempster-Shafer implementation may slightly outperform the Bayesian one when there is conflicting information, although the high computational cost limits its practical application. Last, we demonstrate that the proposed solution is easily scalable to include additional sensors.

Robotic systems are known to be computationally intensive. To improve performance, developers tend to implement custom robotic algorithms in hardware. However, a full robotic system typically consists of many interconnected algorithmic components that can easily max-out FPGA resources, thus requiring the designer to adjust each algorithm design for each new robotic systems in order to meet specific systems requirements and limited resources. Furthermore, manual development of digital circuitry using a hardware description language (HDL) such as verilog or VHDL, is error-prone, time consuming, and often takes months or years to develop and verify. Recent developments in high-level synthesis (HLS), enable automatic generation of digital circuit designs from high-level languages such as C or C++. In this thesis, we propose to develop a database of HLS-generated pareto-optimal hardware designs for various robotic algorithms, such that a fully automated process can optimally compose a complete robotic system given a set of system requirements. In the first part of this thesis, we take a first step towards this goal by developing a system for automatic selection of an Occupancy Grid Mapping (OGM) implementation given specific system requirements and resource thresholds. We first generate hundreds of possible hardware designs via Vitis HLS as we vary parameters to explore the designs space. We then present results which evaluate and explore trade-offs of these designs with respect to accuracy, latency, resource utilization, and power. Using these results, we create a software tool which is able to automatically select an optimal OGM implementation. After implementing selected designs on a PYNQ-Z2 FPGA board, our results show that the runtime of the algorithm improves by 35x over a C++-based implementation. In the second part of this thesis, we extend these same techniques to the Particle Filter (PF) algorithm by implementing 7 different resampling methods and varying parameters on hardware, again via HLS. In this case, we are able to explore and analyze thousands of PF designs. Our evaluation results show that runtime of the algorithm using Local Selection Resampling method reaches the fastest performance on an FPGA and can be as much as 10x faster than in C++. Finally, we build another design selection tool that automatically generates an optimal PF implementation from this design space for a given query set of requirements.

Swarm robotics is the study of developing and controlling large groups of robots. Collectives of robots possess advantages over single robots such as being robust to mission failures due to single-robot errors. Experimental research in swarm robotics is currently limited by swarm robotic technology. Current swarm robotic systems are either small groups of sophisticated robots or large groups of simple robots due to manufacturing overhead, functionality-cost dependencies, and their need to avoid collisions, amongst others. It is therefore useful to develop a swarm robotic system that is easy to manufacture, that utilises its sensors beyond standard usage, and that allows for physical interactions. In this work, I introduce a new type of low-friction locomotion and show its first implementation in the HoverBot system. The HoverBot system consists of an air-levitation and magnet table, and a HoverBot agent. HoverBots are levitating circuit boards which are equipped with an array of planar coils and a Hall-effect sensor. HoverBot uses its coils to pull itself towards magnetic anchors that are embedded into a levitation table. These robots consist of a Printed Circuit Board (PCB), surface mount components, and a battery. HoverBots are easily manufacturable, robots can be ordered populated; the assembly consists of plugging in a battery to a robot. I demonstrate how HoverBot's low-cost hardware can be used beyond its standard functionality. HoverBot's magnetic field readouts from its Hall-effect sensor can be associated with successful movement, robot rotation and collision measurands. I build a time series classifier based on these magnetic field readouts, I modify and apply signal processing techniques to enable the online classification of the time-variant magnetic field measurements on HoverBot's low-cost microcontroller. This method allows HoverBot to detect rotations, successful movements, and collisions by utilising readouts from its single Hall-effect sensor. I discuss how this classification method could be applied to other sensors and demonstrate how HoverBots can utilise their classifier to create an occupancy grid map. HoverBots use their multi-functional sensing capabilities to determine whether they moved successfully or collided with a static object to map their environment. HoverBots execute an "explore-and-return-to-nest" strategy to deal with their sensor and locomotion noise. Each robot is assigned to a nest (landmark); robots leave their nests, move n steps, return and share their observations. Over time, a group of four HoverBots collectively builds a probabilistic belief over its environment. In summary, I build manufacturable swarm robots that detect collisions through a time series classifier and map their environment by colliding with their surroundings. My work on swarm robotic technology pushes swarm robotics research towards studies on collision-dependent behaviours, a research niche that has been barely studied. Collision events occur more often in dense areas and/or large groups, circumstances that swarm robots experience. Large groups of robots with collision-dependent behaviours could become a research tool to help invent and test novel distributed algorithms, to understand the dependencies between local to global (emergent) behaviours and more generally the science of complex systems. Such studies could become tremendously useful for the execution of large-scale swarm applications such as the search and rescue of survivors after a natural disaster.

Intelligent vehicles require perception systems with high performances. Usually, perception system consists of multiple sensors, such as cameras, 2D/3D lidars or radars. The works presented in this Ph.D thesis concern several topics on cameras and lidar based perception for understanding dynamic scenes in urban environments. The works are composed of four parts.In the first part, a stereo vision based visual odometry is proposed by comparing several different approaches of image feature detection and feature points association. After a comprehensive comparison, a suitable feature detector and a feature points association approach is selected to achieve better performance of stereo visual odometry. In the second part, independent moving objects are detected and segmented by the results of visual odometry and U-disparity image. Then, spatial features are extracted by a kernel-PCA method and classifiers are trained based on these spatial features to recognize different types of common moving objects e.g. pedestrians, vehicles and cyclists. In the third part, an extrinsic calibration method between a 2D lidar and a stereoscopic system is proposed. This method solves the problem of extrinsic calibration by placing a common calibration chessboard in front of the stereoscopic system and 2D lidar, and by considering the geometric relationship between the cameras of the stereoscopic system. This calibration method integrates also sensor noise models and Mahalanobis distance optimization for more robustness. At last, dynamic occupancy grid mapping is proposed by 3D reconstruction of the environment, obtained from stereovision and Lidar data separately and then conjointly. An improved occupancy grid map is obtained by estimating the pitch angle between ground plane and the stereoscopic system. The moving object detection and recognition results (from the first and second parts) are incorporated into the occupancy grid map to augment the semantic meanings. All the proposed and developed methods are tested and evaluated with simulation and real data acquired by the experimental platform "intelligent vehicle SetCar" of IRTES-SET laboratory.

Les systèmes de perception, qui sont à la base du concept du véhicule intelligent, doivent répondre à des critères de performance à plusieurs niveaux afin d’assurer des fonctions d’aide à la conduite et/ou de conduite autonome. Aujourd’hui, la majorité des systèmes de perception pour véhicules intelligents sont basés sur la combinaison de données issues de plusieurs capteurs (caméras, lidars, radars, etc.). Les travaux de cette thèse concernent le développement d’un système de perception à base d’un capteur de vision stéréoscopique et d’un capteur lidar pour l’analyse de scènes dynamiques en environnement urbain. Les travaux présentés sont divisés en quatre parties.La première partie présente une méthode d’odométrie visuelle basée sur la stéréovision, avec une comparaison de différents détecteurs de primitives et différentes méthodes d’association de ces primitives. Un couple de détecteur et de méthode d’association de primitives a été sélectionné sur la base d’évaluation de performances à base de plusieurs critères. Dans la deuxième partie, les objets en mouvement sont détectés et segmentés en utilisant les résultats d’odométrie visuelle et l’image U-disparité. Ensuite, des primitives spatiales sont extraites avec une méthode basée sur la technique KPCA et des classifieurs sont enfin entrainés pour reconnaitre les objets en mouvement (piétons, cyclistes, véhicules). La troisième partie est consacrée au calibrage extrinsèque d’un capteur stéréoscopique et d’un Lidar. La méthode de calibrage proposée, qui utilise une mire plane, est basée sur l’exploitation d’une relation géométrique entre les caméras du capteur stéréoscopique. Pour une meilleure robustesse, cette méthode intègre un modèle de bruit capteur et un processus d’optimisation basé sur la distance de Mahalanobis. La dernière partie de cette thèse présente une méthode de construction d’une grille d’occupation dynamique en utilisant la reconstruction 3D de l’environnement, obtenue des données de stéréovision et Lidar de manière séparée puis conjointement. Pour une meilleure précision, l’angle entre le plan de la chaussée et le capteur stéréoscopique est estimé. Les résultats de détection et de reconnaissance (issus des première et deuxième parties) sont incorporés dans la grille d’occupation pour lui associer des connaissances sémantiques. Toutes les méthodes présentées dans cette thèse sont testées et évaluées avec la simulation et avec de données réelles acquises avec la plateforme expérimentale véhicule intelligent SetCar” du laboratoire IRTES-SET. / Intelligent vehicles require perception systems with high performances. Usually, perception system consists of multiple sensors, such as cameras, 2D/3D lidars or radars. The works presented in this Ph.D thesis concern several topics on cameras and lidar based perception for understanding dynamic scenes in urban environments. The works are composed of four parts.In the first part, a stereo vision based visual odometry is proposed by comparing several different approaches of image feature detection and feature points association. After a comprehensive comparison, a suitable feature detector and a feature points association approach is selected to achieve better performance of stereo visual odometry. In the second part, independent moving objects are detected and segmented by the results of visual odometry and U-disparity image. Then, spatial features are extracted by a kernel-PCA method and classifiers are trained based on these spatial features to recognize different types of common moving objects e.g. pedestrians, vehicles and cyclists. In the third part, an extrinsic calibration method between a 2D lidar and a stereoscopic system is proposed. This method solves the problem of extrinsic calibration by placing a common calibration chessboard in front of the stereoscopic system and 2D lidar, and by considering the geometric relationship between the cameras of the stereoscopic system. This calibration method integrates also sensor noise models and Mahalanobis distance optimization for more robustness. At last, dynamic occupancy grid mapping is proposed by 3D reconstruction of the environment, obtained from stereovision and Lidar data separately and then conjointly. An improved occupancy grid map is obtained by estimating the pitch angle between ground plane and the stereoscopic system. The moving object detection and recognition results (from the first and second parts) are incorporated into the occupancy grid map to augment the semantic meanings. All the proposed and developed methods are tested and evaluated with simulation and real data acquired by the experimental platform “intelligent vehicle SetCar” of IRTES-SET laboratory.