In some dense urban environments (e.g., a street with tall buildings around), vehicle localization result provided by Global Positioning System (GPS) receiver might not be accurate or even unavailable due to signal reflection (multi-path) or poor satellite visibility. In order to improve the accuracy and robustness of assisted navigation systems so as to guarantee driving security and service continuity on road, a vehicle localization approach is presented in this thesis by taking use of the redundancy and complementarities of multiple sensors. At first, GPS localization method is complemented by onboard dead-reckoning (DR) method (inertial measurement unit, odometer, gyroscope), stereovision based visual odometry method, horizontal laser range finder (LRF) based scan alignment method, and a 2D GIS road network map based map-matching method to provide a coarse vehicle pose estimation. A sensor selection step is applied to validate the coherence of the observations from multiple sensors, only information provided by the validated sensors are combined under a loosely coupled probabilistic framework with an information filter. Then, if GPS receivers encounter long term outages, the accumulated localization error of DR-only method is proposed to be bounded by adding a GIS building map layer. Two onboard LRF systems (a horizontal LRF and a vertical LRF) are mounted on the roof of the vehicle and used to detect building facades in urban environment. The detected building facades are projected onto the 2D ground plane and associated with the GIS building map layer to correct the vehicle pose error, especially for the lateral error. The extracted facade landmarks from the vertical LRF scan are stored in a new GIS map layer. The proposed approach is tested and evaluated with real data sequences. Experimental results with real data show that fusion of the stereoscopic system and LRF can continue to localize the vehicle during GPS outages in short period and to correct the GPS positioning error such as GPS jumps; the road map can help to obtain an approximate estimation of the vehicle position by projecting the vehicle position on the corresponding road segment; and the integration of the building information can help to refine the initial pose estimation when GPS signals are lost for long time.

La cystoscopie est actuellement l'examen clinique de référence permettant l'exploration visuelle des parois internes de la vessie. Le cystoscope (instrument utilisé pour cet examen) permet d'acquérir une séquence vidéo des parois épithéliales de la vessie. Cependant, chaque image de la séquence vidéo ne visualise qu'une surface réduite de quelques centimètres carrés de la paroi. Les travaux réalisés dans le cadre de cette thèse ont pour objectif de construire une carte 3D reproduisant d'une manière fidèle les formes et les textures des parois internes de la vessie. Une telle représentation de l'intérieur de la vessie permettrait d'améliorer l'interprétation des données acquises lors d'un examen cystoscopique. Pour atteindre cet objectif, un nouvel algorithme flexible est proposé pour le calibrage de systèmes cystoscopiques à vision active. Cet algorithme fournit les paramètres nécessaires à la reconstruction précise de points 3D sur la portion de surface imagée à chaque instant donné de la séquence vidéo cystoscopique. Ainsi, pour chaque acquisition de la séquence vidéo, un ensemble de quelques points 3D/2D et une image 2D est disponible. L'objectif du deuxième algorithme proposé dans cette thèse est de ramener l'ensemble des données obtenues pour une séquence dans un repère global pour générer un nuage de points 3D et une image panoramique 2D représentant respectivement la forme 3D et la texture de la totalité de la paroi imagée dans la séquence vidéo. Cette méthode de cartographie 3D permet l'estimation simultanée des transformations 3D rigides et 2D perspectives liant respectivement les positions du cystoscope et les images de paires d'acquisitions consécutives. Les résultats obtenus sur des fantômes réalistes de vessie montrent que ces algorithmes permettent de calculer des surfaces 3D reproduisant les formes à retrouver / Cystoscopy is currently the reference clinical examination for visual exploration of the inner walls of the bladder. A cystoscope (instrument used in this examination) allows for video acquisition of the bladder epithelium. Nonetheless, each frame of the video displays only a small area of few squared centimeters. This work aims to build 3D maps representing the 3D shape and the texture of the inner walls of the bladder. Such maps should improve and facilitate the interpretation of the cystoscopic data. To reach this purpose, a new flexible algorithm is proposed for the calibration of cystoscopic active vision systems. This algorithm provides the required parameters to achieve accurate reconstruction of 3D points on the surface part imaged at each given moment of the video cystoscopy. Thus, available data for each acquisition are a set of few 3D points (and their corresponding 2D projections) and a 2D image. The aim of the second algorithm described in this work is to place all the data obtained for a sequence in a global coordinate system to generate a 3D point cloud and a 2D panoramic image representing respectively the 3D shape and the texture of the bladder wall imaged in the video. This 3D cartography method allows for the simultaneous estimation of 3D rigid transformations and 2D perspective transformations. These transformations give respectively the link between cystoscope positions and between images of consecutive acquisitions. The results obtained on realistic bladder phantoms show that the proposed method generates 3D surfaces recovering the ground truth shapes

Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèle. / The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

This thesis focuses on the problem of 3D acquisition using coded structured light (CSL). In CSL, a projected pattern impinges artificial texture onto the object surface, increasing the number of correspondences in the retrieved image. Finally, 3D acquisition is pursued by triangulation. An active research is being done in CSL techniques for moving scenarios. In this thesis, a review of the main CSL approaches is presented. Afterwards, we perform a deep study of the two most used frequency-based techniques, and a new proposal for automatic selection of the window width using Windowed Fourier Transform (WFT). Using this analysis, we implemented a new technique for one-shot dense acquisition, able to work in moving scenarios. The technique is based on adaptive WFT and DeBruijn coding. The results show the proposed method obtains dense acquisition with accuracy levels comparable to DeBruijn algorithms. Finally, the thesis focuses on the problem of registration in SL. / Esta tesis estudia el problema de la reconstrucción 3D con Luz Estructurada (LE). En LE se proyecta un patrón en la superficie del objecto, a fin de incrementar la textura y el número de correspondencias con la imagen capturada, de la que se extrae la información 3D. Actualmente se trabaja en soluciones de LE para entornos moviles. La tesis presenta un compendio de las principales tecnicas en LE. Además, se estudian en detalles las dos propuestas de análisis frecuencial, proponiendo un algoritmo para el análisis del patrón capturado. Con ésto, se propone un método de un único patrón proyectado, obteniendo reconstrucción densa. La técnica se basa en WFT combinado con codificación DeBruijn. Los resultados muestran niveles de precisión comparables con otras técnicas DeBruijn, pero obteniendo reconstrucción densa. Finalmente, se estudia el problema de registro de reconstrucciones LE.

La reconstruction précise d’une scène 3D à partir de plusieurs caméras offre un contenu synthétique 3D à destination de nombreuses applications telles que le divertissement, la télévision et la production cinématographique. Cette thèse propose une nouvelle approche pour la reconstruction 3D multi-vues basée sur l’enveloppe visuelle et la stéréovision multi-oculaire. Cette approche nécessite en entrée l’enveloppe visuelle et plusieurs jeux d’images rectifiées issues de différentes unités multiscopiques constituées chacune de plusieurs caméras alignées et équidistantes. Nos contributions se situent à différents niveaux. Le premier est notre méthode de stéréovision multi-oculaire qui est fondée sur un nouvel échantillonnage de l’espace scénique et fournit une carte de matérialité exprimant la probabilité pour chaque point d’échantillonnage 3D d’appartenir à la surface visible par l’unité multiscopique. Le second est l’hybridation de cette méthode avec les informations issues de l’enveloppe visuelle et le troisième est la chaîne de reconstruction basée sur la fusion des différentes enveloppes creusées tout en gérant les informations contradictoires qui peuvent exister. Les résultats confirment : i) l’efficacité de l’utilisation de la carte de matérialité pour traiter les problèmes qui se produisent souvent dans la stéréovision, en particulier pour les régions partiellementoccultées ; ii) l’avantage de la fusion des méthodes de l’enveloppe visuelle et de la stéréovision multi-oculaire pour générer un modèle 3D précis de la scène. / Accurate reconstruction of a 3D scene from multiple cameras offers 3D synthetic content tobe used in many applications such as entertainment, TV, and cinema production. This thesisis placed in the context of the RECOVER3D collaborative project, which aims is to provideefficient and quality innovative solutions to 3D acquisition of actors. The RECOVER3Dacquisition system is composed of several tens of synchronized cameras scattered aroundthe observed scene within a chromakey studio in order to build the visual hull, with severalgroups laid as multiscopic units dedicated to multi-baseline stereovision. A multiscopic unitis defined as a set of aligned and evenly distributed cameras. This thesis proposes a novelframework for multi-view 3D reconstruction relying on both multi-baseline stereovision andvisual hull. This method’s inputs are a visual hull and several sets of multi-baseline views.For each such view set, a multi-baseline stereovision method yields a surface which is usedto carve the visual hull. Carved visual hulls from different view sets are then fused iterativelyto deliver the intended 3D model. Furthermore, we propose a framework for multi-baselinestereo-vision which provides upon the Disparity Space (DS), a materiality map expressingthe probability for 3D sample points to lie on a visible surface. The results confirm i) theefficient of using the materiality map to deal with commonly occurring problems in multibaselinestereovision in particular for semi or partially occluded regions, ii) the benefit ofmerging visual hull and multi-baseline stereovision methods to produce 3D objects modelswith high precision.

La mesure de la forme 3D du visage est une problématique qui attire de plus en plus de chercheurs et qui trouve son application dans des domaines divers tels que la biométrie, l’animation et la chirurgie faciale. Les solutions actuelles sont souvent basées sur des systèmes projecteur/caméra et utilisent de la lumière structurée pour compenser l’insuffisance de la texture faciale. L’information 3D est ensuite calculée en décodant la distorsion des patrons projetés sur le visage. Une des techniques les plus utilisées de la lumière structurée est la codification sinusoïdale par décalage de phase qui permet une numérisation 3D de résolution pixélique. Cette technique exige une étape de déroulement de phase, sensible à l’éclairage ambiant surtout quand le nombre de patrons projetés est limité. En plus, la projection de plusieurs patrons impacte le délai de numérisation et peut générer des artefacts surtout pour la capture d’un visage en mouvement. Une alternative aux approches projecteur-caméra consiste à estimer l’information 3D par appariement stéréo suivi par une triangulation optique. Cependant, le modèle calculé par cette technique est généralement non-dense et manque de précision. Des travaux récents proposent la super-résolution pour densifier et débruiter les images de profondeur. La super-résolution a été particulièrement proposée pour les caméras 3D TOF (Time-Of-Flight) qui fournissent des scans 3D très bruités. Ce travail de thèse propose une solution de numérisation 3D à faible coût avec un schéma de super-résolution spatio-temporelle. Elle utilise un système multi-caméra étalonné assisté par une source de projection non-étalonnée. Elle est particulièrement adaptée à la reconstruction 3D de visages, i.e. rapide et mobile. La solution proposée est une approche hybride qui associe la stéréovision et la codification sinusoïdale par décalage de phase, et qui non seulement profite de leurs avantages mais qui surmonte leurs faiblesses. Le schéma de la super-résolution proposé permet de corriger l’information 3D, de compléter la vue scannée du visage en traitant son aspect déformable. / 3D face measurement is increasingly demanded for many applications such as bio-metrics, animation and facial surgery. Current solutions often employ a structured light camera/projector device to overcome the relatively uniform appearance of skin. Depth in-formation is recovered by decoding patterns of the projected structured light. One of the most widely used structured-light coding is sinusoidal phase shifting which allows a 3Ddense resolution. Current solutions mostly utilize more than three phase-shifted sinusoidal patterns to recover the depth information, thus impacting the acquisition delay. They further require projector-camera calibration whose accuracy is crucial for phase to depth estimation step. Also, they need an unwrapping stage which is sensitive to ambient light, especially when the number of patterns decreases. An alternative to projector-camera systems consists of recovering depth information by stereovision using a multi-camera system. A stereo matching step finds correspondence between stereo images and the 3D information is obtained by optical triangulation. However, the model computed in this way generally is quite sparse. To up sample and denoise depth images, researchers looked into super-resolution techniques. Super-resolution was especially proposed for time-of-flight cameras which have very low data quality and a very high random noise. This thesis proposes a3D acquisition solution with a 3D space-time non-rigid super-resolution capability, using a calibrated multi-camera system coupled with a non calibrated projector device, which is particularly suited to 3D face scanning, i.e. rapid and easily movable. The proposed solution is a hybrid stereovision and phase-shifting approach, using two shifted patterns and a texture image, which not only takes advantage of the assets of stereovision and structured light but also overcomes their weaknesses. The super-resolution scheme involves a 3D non-rigid registration for 3D artifacts correction in the presence of small non-rigid deformations as facial expressions.

Ce manuscrit propose une approche méthodologique pour la constitution d’une chaîne complète de vidéosurveillance pour des environnements naturellement encombrés. Nous identifions et levons un certain nombre de verrous méthodologiques et technologiques inhérents : 1) à l’acquisition de séquences vidéo en milieu naturel, 2) au traitement d’images, 3) au suivi multi-cibles, 4) à la découverte et la modélisation de motifs comportementaux récurrents, et 5) à la fusion de données. Le contexte applicatif de nos travaux est la surveillance apicole, et en particulier, l’étude des trajectoires des abeilles en vol devant la ruche. De ce fait, cette thèse se présente également comme une étude de faisabilité et de prototypage dans le cadre des deux projets interdisciplinaires EPERAS et RISQAPI (projets menées en collaboration avec l’INRA Magneraud et le Muséum National d’Histoire Naturelle). Il s’agit pour nous informaticiens et pour les biologistes qui nous ont accompagnés, d’un domaine d’investigation totalement nouveau, pour lequel les connaissances métiers, généralement essentielles à ce genre d’applications, restent encore à définir. Contrairement aux approches existantes de suivi d’insectes, nous proposons de nous attaquer au problème dans l’espace à trois dimensions grâce à l’utilisation d’une caméra stéréovision haute fréquence. Dans ce contexte, nous détaillons notre nouvelle méthode de détection de cibles appelée segmentation HIDS. Concernant le calcul des trajectoires, nous explorons plusieurs approches de suivi de cibles, s’appuyant sur plus ou moins d’a priori, susceptibles de supporter les conditions extrêmes de l’application (e.g. cibles nombreuses, de petite taille, présentant un mouvement chaotique). Une fois les trajectoires collectées, nous les organisons selon une structure de données hiérarchique et mettons en œuvre une approche Bayésienne non-paramétrique pour la découverte de comportements émergents au sein de la colonie d’insectes. L’analyse exploratoire des trajectoires issues de la scène encombrée s’effectue par classification non supervisée, simultanément sur des niveaux sémantiques différents, et où le nombre de clusters pour chaque niveau n’est pas défini a priori mais est estimé à partir des données. Cette approche est dans un premier temps validée à l’aide d’une pseudo-vérité terrain générée par un Système Multi-Agents, puis dans un deuxième temps appliquée sur des données réelles. / This manuscript provides the basis for a complete chain of videosurveillence for naturally cluttered environments. In the latter, we identify and solve the wide spectrum of methodological and technological barriers inherent to : 1) the acquisition of video sequences in natural conditions, 2) the image processing problems, 3) the multi-target tracking ambiguities, 4) the discovery and the modeling of recurring behavioral patterns, and 5) the data fusion. The application context of our work is the monitoring of honeybees, and in particular the study of the trajectories bees in flight in front of their hive. In fact, this thesis is part a feasibility and prototyping study carried by the two interdisciplinary projects EPERAS and RISQAPI (projects undertaken in collaboration with INRA institute and the French National Museum of Natural History). It is for us, computer scientists, and for biologists who accompanied us, a completely new area of investigation for which the scientific knowledge, usually essential for such applications, are still in their infancy. Unlike existing approaches for monitoring insects, we propose to tackle the problem in the three-dimensional space through the use of a high frequency stereo camera. In this context, we detail our new target detection method which we called HIDS segmentation. Concerning the computation of trajectories, we explored several tracking approaches, relying on more or less a priori, which are able to deal with the extreme conditions of the application (e.g. many targets, small in size, following chaotic movements). Once the trajectories are collected, we organize them according to a given hierarchical data structure and apply a Bayesian nonparametric approach for discovering emergent behaviors within the colony of insects. The exploratory analysis of the trajectories generated by the crowded scene is performed following an unsupervised classification method simultaneously over different levels of semantic, and where the number of clusters for each level is not defined a priori, but rather estimated from the data only. This approach is has been validated thanks to a ground truth generated by a Multi-Agent System. Then we tested it in the context of real data.

This work presents a system for semi-autonomous optical localization of distant moving targets using multiple positionable cameras. The cameras were calibrated and stationed using custom designed calibration targets and methodology with the objective to alleviate the main sources of errors which were pinpointed in thorough precision analysis. The detection of the target is performed manually, while the visual tracking is automatic and it utilizes two state-of-the-art approaches. The estimation of the target location in 3-space is based on multi-view triangulation working with noisy measurements. A basic setup consisting of two camera units was tested against static targets and a moving terrestrial target, and the precision of the location estimation was compared to the theoretical model. The modularity and portability of the system allows fast deployment in a wide range of scenarios including perimeter monitoring or early threat detection in defense systems, as well as air traffic control in public space.

Les robots et véhicules autonomes représentent le futur des modes de déplacements et de production. Les enjeux de l’avenir reposent sur la robustesse de leurs perceptions et flexibilité face aux environnements changeant et situations inattendues. Les capteurs stéréoscopiques sont des capteurs passifs qui permettent d'obtenir à la fois image et information 3D de la scène à la manière de la vision humaine. Dans ces travaux nous avons développé un système de localisation, par odométrie visuelle permettant de déterminer la position dans l'espace du capteur de façon efficace et performante en tirant partie de la carte de profondeur dense mais également associé à un système de SLAM, rendant la localisation robuste aux perturbations et aux décalages potentiels. Nous avons également développé plusieurs solutions de cartographie et interprétation d’obstacles, à la fois pour le véhicule aérien et terrestre. Ces travaux sont en partie intégrés dans des produits commerciaux. / Autonomous vehicles and robots represent the future of transportation and production industries. The challenge ahead will come from the robustness of perception and flexibility from unexpected situations and changing environments. Stereoscopic cameras are passive sensors that provide color images and depth information of the scene by correlating 2 images like the human vision. In this work, we developed a localization system, by visual odometry that can determine efficiently the position in space of the sensor by exploiting the dense depth map. It is also combined with a SLAM system that enables robust localization against disturbances and potentials drifts. Additionally, we developed a few mapping and obstacles detections solutions, both for aerial and terrestrial vehicles. These algorithms are now partly integrated into commercial products.

Dans cette thèse, nous étudions les problèmes de reconstruction statique et dynamique à partir de vues multiples et texturation, en s'appuyant sur des applications réelles et pratiques. Nous proposons trois méthodes de reconstruction destinées à l'estimation d'une représentation d'une scène statique/dynamique à partir d'un ensemble d'images/vidéos. Nous considérons ensuite le problème de texturation multi-vues en se concentrant sur la qualité visuelle de rendu..