Faculté informatique et communications IC, Département d'informatique, IC - Section d'informatique IC-SIN

Algorithms for VLSI stereo vision circuits applied to autonomous robots

Lopez de Meneses Novosilzov, Yuri ; Nicoud, Jean-Daniel (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 1999 ; no 2058.

Add to personal list
    Summary
    Since the inception of Robotics, visual information has been incorporated in order to allow the robots to perform tasks that require an interaction with their environment, particularly when it is a changing environment. Depth perception is a most useful information for a mobile robot to navigate in its environment and interact with its surroundings. Among the different methods capable of measuring the distance to the objects in the scene, stereo vision is the most advantageous for a small, mobile robot with limited energy and computational power. Stereoscopy implies a low power consumption because it uses passive sensors and it does not require the robot to move. Furthermore, it is more robust, because it does not require a complex optic system with moving elements. On the other hand, stereo vision is computationally intensive. Objects in the scene have to be detected and matched across images. Biological sensory systems are based on simple computational elements that process information in parallel and communicate among them. Analog VLSI chips are an ideal substrate to mimic the massive parallelism and collective computation present in biological nervous systems. For mobile robotics they have the added advantage of low power consumption and high computational power, thus freeing the CPU for other tasks. This dissertation discusses two stereoscopic methods that are based on simple, parallel cal- culations requiring communication only among neighboring processing units (local communication). Algorithms with these properties are easy to implement in analog VLSI and they are also very convenient for digital systems. The first algorithm is phase-based. Disparity, i.e., the spatial shift between left and right images, is recovered as a phase shift in the spatial-frequency domain. Gábor functions are used to recover the frequency spectrum of the image because of their optimum joint spatial and spatial-frequency properties. The Gábor-based algorithm is discussed and tested on a Khepera miniature mobile robot. Two further approximations are introduced to ease the analog VLSI and digital implementations. The second stereoscopic algorithm is difference-based. Disparity is recovered by a simple calculation using the image differences and their spatial derivatives. The algorithm is simulated on a digital system and an analog VLSI implementation is proposed and discussed. The thesis concludes with the description of some tools used in this research project. A stereo vision system has been developed for the Webots mobile robotics simulator, to simplify the testing of different stereo algorithms. Similarly, two stereo vision turrets have been built for the Khepera robot.
    Résumé
    Depuis les origines de la robotique, l'information visuelle a été incorporée pour permettre aux robots d'interagir avec leur environnement, en particulier lorsqu'il s'agit d'un environnement changeant. La perception de la profondeur, i.e., de la distance, est une information très utile pour un robot qui doit naviguer dans son environnement et interagir avec son milieu. Parmi les différentes méthodes pour mesurer la distance aux objets d'une scène, la vision stéréoscopique est la plus avantageuse pour un petit robot mobile avec une énergie et une puissance de calcul limitées. La stéréoscopie implique une moindre consommation de puissance, parce qu'elle utilise des capteurs passifs et qu'elle n'exige pas que le robot soit en mouvement. Qui plus est, elle est plus robuste, car elle ne nécessite pas d'une optique complexe avec des éléments mobiles. En revanche, la vision stéréoscopique est très gourmande en puissance de calcul puisqu'il faut détecter les objets dans la scène et les apparier avec ses correspondants sur l'autre image. Les systèmes sensoriels biologiques se basent sur des éléments de calcul simples, qui traîtent l'information en parallèle et communiquent entre eux. Les chips de VLSI analogique sont un substrat idéale pour recréer le parallélisme massif et le calcul collectif présent dans les systèmes nerveux biologiques. Pour la robotique mobile ils ont l'avantage ajouté d'une faible consommation de puissance et une grande puissance de calcul, libérant ainsi le processeur central pour d'autres tâches. Cette thèse présente deux méthodes de vision stéréoscopique qui se basent sur des calculs simples et parallèles qui nécessitent uniquement de la communication entre unités de calcul voisines. Des algorithmes avec des telles propriétés sont plus facilement mis en oeuvre en VLSI analogique et ils sont aussi très avantageux pour les systèmes digitaux. Le premier algorithme est basé sur la phase. La disparité, c'est à dire, le décalage spatial entre les images gauche et droite, est extraite comme un décalage de phase dans le domaine des fréquences spatiales. Des fonctions de Gábor sont employées pour obtenir le spectre de fréquences des images, en raison de leurs propriétés optimales à la fois dans le domaine spatial et des fréquences spatiales. L'algorithme de Gábor est présenté et vérifié sur un petit robot mobile Khepera. Deux approximations qui visent à faciliter la mise en oeuvre en systèmes analogiques et digitaux sont proposées. Le second algorithme stéréoscopique est basé sur des différences. La disparité est récupérée par un calcul simple qui utilise la différence des images et leur dérivée. L'algorithme est simulé sur un système digital et une mise en oeuvre en VLSI analogique est proposée et décrite. La thèse se termine avec la description de quelques outils employés dans ce projet de recherche. Un système de vision stéréo a été développé pour le simulateur de robots mobiles Webots. Il simplifie la vérification des algorithmes stéréoscopiques. Pareillement, deux tourelles de vision stéréoscopique on été développées pour le robot Khepera.