Faugeras, Olivier
- Vieville, Thierry
- Theron, E.
- Vuillemin, J.
- Hotz, B.
- Zhang, Zhengyou
- Moll, L.
- Bertin, P.
- Mathieu, Herve
- Fua, P.
- Berry,
G.
- Proy, C.
Rapport de recherche de l'INRIA -
Sophia Antipolis ,
Equipe : ROBOTVIS
45 pages - Août 1993 - Document en anglais
Abstract : This paper describes some of the work on stereo that has been going on at INRIA in the last four years. The work has concentrated on obtaining dense, accurate and reliable range maps of the environment at rates compatible with the real-time constraints of such applications as the navigation of mobile vehicles in man-made or natural environments. The class of algorithm- s which has been selected among several is the class of algorithms which has been selected among several is the class of correlation-based stereo algorithms because they are the only ones that can produce sufficiently dense range maps with an algoritmic structure which lends itself nicely to fast implementations because of the simplicity of the underlying computatio- n. We describe the various improvements that we have brought to the original idea, including validation and characterization of the quality of the matches, a recursive implementation of the score computation which makes the method independent of the size of the correlation window and a calibration method which does not require the use of a calibration pattern. We then describe two implementations of this algorithm on two very different pieces of hardware. The first implementation is on a board with four digital signal processors designed jointly with Matra MSII. This implementation can produce 64x64 range maps at rate varying between 200 and 400 ms, depending upon the range of disparities. The second implementation is on a board developed by DEC-PRL and can perform the cross-correlation of two 256X256 images in 140 ms. The first implementation has been integrated in the navigation system of the INRIA cart and used to correct for inertial and odometric errors in navigation experiments both indoors and outdoors on road. This is the first application of our correlation-based algorithm which is described in the paper. The second application has been done jointly with people from the french national space agence (CNES) to study the possibility of using stereo on a future planetary rover for the constructi- on of digital elevation maps. We have shown that real time stereo is possible today at low-cost and can be applied in real applications. The algorithm that has been described is not the most sophisticated available but we have made it robust and reliable thanks to a number of improvements. Evan though each of these improvements is not earth-shattering from the pure research point of view, altogether they have allowed us to go beyond a very important threshold. This threshold measures the difference between a program that runs in the laboratory on a few images and one that works continuously for hours on a sequence of stereo pairs and produces results at such rates and of such quality that they can be used to guide a real vehicle or to produce discrete elevation maps. We believe that this threshold has only been reached in a very small number of cases.
Résumé : Cet article fait la synthese de travaux realises dans le domaine de la stereoscopie a l'INRIA ces quatre dernieres annees. Ces travaux se sont concentres sur l'obtention de cartes de profondeur denses, precises et fiables a des cadences compatibles avec les contraintes du temps reel liees a des applications comme la navigation d'un vehicule dans un environneme- nt artificiel ou naturel. La classe d'algorithmes qui a ete selectionnee parmi les differentes methodes possibles de stereoscopie est celle des algorithmes a base de correlations. Seules ces methodes peuvent produire des cartes de profondeurs suffisamment denses a partir d'une structure algorithmique qui se prete facilement a des implementations rapides de par sa simplicite intrinseque. Nous decrivons differentes ameliorations apportees au schema initial, en particulier la validation et la caracterisatio- n de la qualite des appariements, une implementation recursive des score de calcul qui rend la methode independante de la taille de la fenetre de correlation, et une methode de calibration qui ne necessite pas l'utilisati- on d'une grille de calibration. Nous decrivons ensuite deux implementations de cet algorithme sur deux systemes materiels tres differents. La premiere implementation a ete realisee sur une carte industrielle dotee de quatre processeurs de traitement du signal (DSP) realisee conjointement par l'INRIA et Matra-MSII. Cette implementation permet de calculer des cartes de profondeu- rs de taille 64x64 a des cadences variant entre 200 et 400 msec, selon l'intervalle de disparite requis. La seconde implementation a ete realisee sur une carte developpee par DEC-PRL et peut realiser le calcul d'une carte d'intercorrelation de deux fois 256x256 en 140msec. La premiere implementation a ete integree au systeme de navigation du robot mobile de l'INRIA et utilisee pour corriger les erreurs des capteurs inertiels et odometriques lors d'experimentations de navigation autonome en interieur et en exterieur, sur une route. Ce travail constitue la premiere application de l'algorithme decrit dans ce papier. La seconde application a ete realisee conjointement avec une equipe de l'agence nationale francaise spatiale (CNES) pour etudier les possibilites d'utilisation de la stereoscopie lors de futures explorations planetaires necessitant la construction de cartes numeriques de terrain. Nous avons ainsi demontre qu'il est possible aujourd'hui de realiser a faible cout un module de vision stereoscopique temps-reel et utilisable au sein d'applications effectives. Cet algorithme n'est pas le plus sophistique des methodes actuellement disponibles, mais il a ete rendu robuste et fiable grace a de nombreuses ameliorations. Bien que chacune de ces ameliorations ne soient pas vraiment fondamentales au niveau theorique, ajoutees les unes aux autres, elles permettent de depasser une frontiere redibitoire. Cette frontiere est celle qui separe les programmes qui tournent en laboratoire sur quelques images et ceux qui travaillent de maniere continue des heures durant sur des sequences de paires stereoscopiques et produisent des resultats a des cadences et a des niveaux de qualite tels que l'on peut les utiliser pour guider un robot mobile sur sa trajectoire ou produire un modele numerique de terrain. Nous croyons que cette frontiere n'est franchie encore qu'assez rarement.
