Les travaux de ce doctorat concernent le développement d'une technique de caractérisation non destructive encore peu utilisée dans le domaine de la microélectronique : la tomographie par rayons X dans un microscope électronique à balayage. Cet instrument a été utilisé pour l'analyse haute résolution d'interconnexions métalliques, telles que les piliers de cuivre ainsi que les vias traversants, utilisées dans le cadre de l'intégration 3D pour connecter verticalement plusieurs puces entre elles. Les contributions les plus significatives de ces travaux sont : (1) l'amélioration des capacités d'analyse offertes par l'instrument. De nombreuses études – simulations et expériences – ont été menées afin de déterminer et améliorer les résolutions 2D et 3D de ce système d'imagerie. Il a été montré que la résolution 2D de ce système d'imagerie pouvait atteindre 60 nanomètres. La qualité des images acquises et reconstruites a également été améliorée à travers l'implémentation d'algorithmes de reconstruction itératifs et de nombreuses méthodes d'alignement des radiographies. (2) La réduction du temps d'analyse d'un facteur 3 à travers l'implémentation d'algorithmes de reconstruction contraints tels que la méthode de reconstruction basée sur la minimisation de la variation totale. (3) La mise en place d'algorithmes de correction efficaces pour l'élimination d'artéfacts de reconstruction liés à la polychromaticité du faisceau de rayons X utilisé. (4) La mise en application de l'ensemble de ces algorithmes sur des cas réels, rencontrés par des technologues. / In this thesis, an original non-destructive 3D characterization technique has been developed : the X-ray tomography hosted in a scanning electron microscope. This instrument is not widely used in the microelectronics field. This computed tomography (CT) system has been used for the high resolution analysis of metallic interconnections such as copper pillars and through silicon vias (TSVs). These components are widely used in the field of 3D integration to make vertical stacks of interconnected chips.The most significant contributions of this thesis are : (1) the enhancement of the analytical capabilities of the instrument. Many studies – simulations and experiments – have been performed in order to determine and improve the 2D and 3D resolutions of this imaging system. It has been shown that the 2D resolution of this instrument can reach 60 nanometers. The quality of the projections and reconstruction has also been improved through the implementation of iterative reconstruction algorithms and various projections alignment methods. (2) The reduction of the scanning time by a factor 3 through the implementation of constrained reconstruction techniques such as the reconstruction method based on the total variation minimization. (3) The application of effective correction algorithms for removing reconstruction artefacts due to the polychromaticity of the X-ray beam. (4) The application of all these reconstruction methods and algorithms on real cases encountered by materials engineers.

La thèse s'inscrit dans le domaine de la vision par ordinateur. Il s'agit, dans un environnement intérieur inconnu, partiellement connu ou connu de trouver la position et l'orientation d'une camera mobile en temps réel à partir d'une séquence vidéo prise par cette même camera. Le sujet implique également la reconstruction 3D de l'environnement. Les algorithmes de vision seront implémentés et testés sur des plateformes massivement parallèles. Processing the video sequence of a indoor camera in motion we have to find the position and angle of the camera in real time. We will use a single prime lens camera. It may involve an unknown, partially known or well known environment. A big part of the computation is the 3D reconstruction of the scene. The algorithms used to locate the camera will be implemented and tested on GPU. / In this thesis, we explore the problem of modeling an unknown environment using monocular vision for localization applications. We focus in modeling dynamic indoor environments. Many objects in indoor environments are likely to be moved. These movements significantly affect the structure and appearance of the environment and disrupt the existing methods of visual localization. We present in this work a new approach for modeling the environment and its evolution with time. We define explicitly the scene as a static structure and a set of dynamic objects. The object is defined as a rigid entity that a user can take, move and that is visually detectable. First, we show how to automatically discover new objects in a dynamic environment. Existing methods of visual localization simply ignore the inconsistencies due to changes in the scene. We aim to analyze these changes to extract additional information. Without any prior knowledge, an object is a set of points with coherent motion relative to the static structure of the scene. We combine two methods of visual localization to compare various explorations in the same environment taken at different time. The comparison enables to detect objects that have moved between the two shots. For each object, a geometric model and an appearance model are learned. Moreover, we extend the scene model while updating the metrical map and the topological map of the static structure of the environment. Object discovery using motion is based on a new algorithm of multiple structures detection in an image pair. Given a set of correspondences between two views, the method based on RANSAC extracts the different structures corresponding to different model parameterizations seen in the data. The method is applied to homography estimation to detect planar structures and to fundamental matrix estimation to detect structures that have been shifted one from another. Our approach for dynamic scene modeling is applied in a new formulation of place recognition to take into account the presence of dynamic objects in the environment. The model of the place consists in an appearance model of the static structure observed in that place. An object database is learned from previous observations in the environment with the method of object discovery using motion. The place recognition we propose detects the dynamic objects seen in the place and rejects the false detection due to these objects. The different methods described in this dissertation are tested on synthetic and real data. Qualitative and quantitative results are presented throughout the dissertation.

Les techniques de reconstruction 3d sont devenues incontournables pour des applicationstelles que la caractérisation et l'analyse de surfaces. Les travaux réalisés au coursde cette thèse ont pour objectif d'améliorer la qualité des reconstructions 3d par stéréophotométrie.Cette méthode repose sur deux principes, l'inversion d'un modèle d'interactionlumière/matière (BRDF) et la configuration d'un système d'éclairage et de prises de vues.Pour des surfaces diffuses, la stéréo-photométrie est réalisée à partir d'un minimum detrois images acquises d'un point de vue fixe pour des directions d'éclairages différentes.Son avantage est d'extraire simultanément les propriétés géométriques et colorimétriquesdes surfaces analysées même en cas de forte rugosité. Néanmoins, son application exige laformulation de plusieurs hypothèses qui sont difficilement respectables dans un contexteréel. Ceci génère des erreurs significatives dans les reconstructions. Pour les réduire, nousproposons différentes contributions qui s'articulent autour de la prise en compte globale de lachaine d'acquisition. Les apports de nos travaux se situent aux niveaux de la caractérisationet de la modélisation du système d'éclairage, du capteur d'acquisition et de l'améliorationde la qualité des images. Nous nous sommes aussi intéressés à l'optimisation des protocolesde prises de vues dans le cas de spécularité surfacique ou d'ombrage dus à la présence derugosité. Les résultats obtenus montrent que la prise en compte de ces caractéristiques dansl'inversion d'un modèle de BRDF permet une nette amélioration des reconstructions et offrela possibilité de réduire la taille des systèmes d'acquisition. / Tridimensional reconstruction method has become essential for applications suchas the characterization and analysis of surfaces. In this thesis, aims are to increase the qualityof 3d reconstructions by photometric stereo. This method is based on two principles, reversinglight-matter interaction model and configuration of a lighting system. With diffuse surfaces,the photometric stereo use three captured images from a fixed point of view for differentillumination directions. Its main advantage is to extract the color and geometric propertiesfor the textured rough surfaces. However, its application requires to make assumptions thatare not credible in real cases. This problem generates significant errors in the reconstructions.To reduce them, we offer various solutions around the overall consideration of the acquisitionchain. Our contribution focuses on the characterization and modeling of the lighting system,the acquisition sensor and improved image quality. We are also interested to optimize acquisitionprotocol in the case of specular surface or shading due to the surface geometry. Ourresults show that the inclusion of these features in the inversion of a BRDF model allowsan improvement of 3d reconstructions as well as the possibility of reducing the size of theacquisition systems.

La polarisation de la lumière, phénomène physique parfaitement maîtrisé, a été introduit depuis une dizaine d'années seulement dans le domaine de l'imagerie. En effet, tout comme l'œil humain, les capteurs ne sont pas, par construction, sensible à la polarisation de la lumière. Cette propriété particulièrement intéressante ne peut être obtenue qu'en ajoutant des composants optiques aux caméras classiques. L'objectif de ce travail de thèse est de développer un système à la fois stéréoscopique et sensible à l'état de polarisation. En effet, de nombreux insectes dans la nature, comme les abeilles par exemple, ont la capacité à s'orienter dans l'espace et à extraire des informations pertinentes issues de la polarisation. Le prototype ainsi développé doit permettre de reconstruire en trois dimensions des points d'intérêt tout en associant à ces points un ensemble de paramètres relatifs à l'état de polarisation. Le système proposé ici est constitué de deux caméras équipés chacune de deux composants à cristaux liquides permettant d'obtenir deux images avec des orientations de polarisation différentes. Pour chaque acquisition, quatre images sont obtenues : deux pour chacune des caméras. Le verrou majeur soulevé ici est la possibilité de remonter à des informations de polarisation à partir de deux caméras différentes. Après une première étape de calibration géométrique et photométrique, la mise en correspondance des points d'intérêt est rendue délicate en raison des composants optiques placés devant les objectifs. Une étude approfondie des différentes méthodes de mise en correspondance a permis de sélectionner la méthode la moins sensible aux effets de polarisation. Une fois les points mis en correspondance, les paramètres de polarisation de chacun des points sont calculés à partir des quatre valeurs issues des quatre images acquises. Les résultats obtenus sur des scènes réelles montrent la faisabilité et l'intérêt d'un tel système pour des applications robotiques. / The polarization of light was introduced last ten years ago in the field of imaging system is a physical phenomenon that can be controlled for the purposes of the vision system. As that found in the human eyes, in general the imaging sensors are not under construction which is sensitive to the polarization of light. These properties can be measured by adding optical components on a conventional camera. The purpose of this thesis is to develop an imaging system that is sensitive both to the stereoscopic and to the state of polarization. As well as the visual system on a various of insects in nature such as bees, that are have capability to move in space by extracted relevant information from the polarization. The developed prototype should be possible to reconstruct threedimensional of points of interest with the issues associated with a set of parameters of the state of polarization. The proposed system consists of two cameras, each camera equipped with liquid crystal components to obtain two images with different directions of polarization. For each acquisition, four images are acquired: two for each camera. Raised by the key of main capability to return polarization information from two different cameras. After an initial calibration step; geometric and photometric, the mapping of points of interest process is made difficult because of the optical components placed in front of different lenses. A detailed study of different methods of mapping was used to select sensitivity to the polarization effects. Once points are mapped, the polarization parameters of each point are calculated from the four values from four images acquired. The results on real scenes show the feasibility and desirability of this imaging system for robotic applications.

Ces travaux de thèse constituent la première étape d'une réflexion sur la conception d'un système participatif visant la reconstruction et la visualisation de l'espace urbain de la ville de Reims au cours du temps. Dans ces travaux, nous abordons les problèmes de reconnaissance, de reconstruction et géoréférencement spatio-temporel. Ce projet s'appuie sur l'exploitation des sources historiques iconographiques et contextuelles hétérogènes et éparses, dont une collection de cartes postales anciennes et le cadastre actuel géoréférencé.Dans l'objectif d'un travail participatif, il s'avère nécessaire de procurer une aide efficace à l'utilisateur lorsqu'il apporte de nouvelles connaissances dans le système. Une solution robuste doit être apportée en raison de multiples évolutions ou déformations du modèle urbain à travers le temps. Nous avons développé une solution répondant à ce besoin. Elle s'appuie sur des briques de traitement complémentaires, en interaction avec l'utilisateur et s'insère naturellement dans une approche incrémentale de reconstruction. Nous proposons une solution permettant d'extraire, de reconstruire en 3D et de visualiser des bâtiments multi-façades présents dans les cartes postales sans disposer des dimensions réelles des bâtiments. La construction du modèle repose sur l'identification de façades 2D. Elle est obtenue au travers de l'analyse du contenu de l'image. Cette phase d'identification permet de procéder à la reconstruction de modèles 3D, d'extraire des textures 2D associées à ces modèles ainsi que d'enrichir dynamiquement notre système. Les caractéristiques retrouvées dans les images infèrent une estimation sur leur datation, et l'alignement des modèles reconstruits avec le cadastre sur le géoréférencement des bâtiments. Le système ainsi construit constitue une amorce pour la conception d'un système d'information géographique participatif 3D+T permettant aux citoyens de Reims de s'approprier l'histoire de leur ville. / This thesis is the first step toward the design of a Volunteered system for the reconstruction and visualization of urban space in the city of Reims through time. In this work, we address the problems of spatio-temporal recognition, reconstruction and georeferencing. This project relies on the use of heterogeneous and sparse iconographic and contextual historical data, particularly a collection of old postcards and the current cadastral map.With the aim of a Volunteered work, it is necessary to provide useful help to the user when bringing new knowledge into the system. A robust solution is required due to multiple changes of the urban model through time. We have developed a solution to meet those needs. This process fits in an incremental approach of reconstruction and will be completed by a user. We propose to extract, reconstruct and visualize 3D multi-façade buildings from old postcards with no knowledge on their real dimensions. The construction of the models is based on 2D façades identification. It can be obtained through image analysis. This identification allows the reconstruction of 3D models, the extraction of their associated 2D façades textures and the enhancement of the system. The features found in the images infer an estimate of their dating, and the alignment of the models with the cadastral map allows there georeferencing. The system thus constructed is a primer for the design of a Volunteered 3D+T GIS for Reims citizens to capture the history of their city.

L'objectif de cette thèse concerne l'analyse automatique d'images de façades de bâtiments à partir de descriptions formelles à priori de formes géométriques. Ces informations suggérées par un utilisateur permettent de modéliser, de manière formelle, des contraintes spatiales plus ou moins dures quant à la segmentation sémantique produite par le système. Ceci permet de se défaire de deux principaux écueils inhérents aux méthodes d'analyse de façades existantes qui concernent d'une part la coûteuse fidélité de la segmentation résultante aux données visuelles de départ, d'autre part, la spécificité architecturale des règles imposées lors du processus de traitement. Nous proposons d'explorer au travers de cette thèse, différentes méthodes alternatives à celles proposées dans la littérature en exploitant un formalisme de représentation d'à priori de haut niveau d'abstraction, les propriétés engendrées par ces nouvelles méthodes ainsi que les outils de résolution mis en œuvres par celles-ci. Le système résultant est évalué tant quantitativement que qualitativement sur de multiples bases de données standards et par le biais d'études comparatives à des approches à l'état de l'art en la matière. Parmi nos contributions, nous pouvons citer la combinaison du formalisme des grammaires de graphes exprimant les variations architecturales de façades de bâtiments et les modèles graphiques probabilistes modélisant l'énergie attribuée à une configuration paramétrique donnée, dans un schéma d'optimisation par minimisation d'énergie; ainsi qu'une nouvelle approche par programmation linéaire d'analyse avec à priori de formes. Enfin, nous proposons un formalisme flexible de ces à priori devançant de par ses performances les méthodes à l'état de l'art tout en combinant les avantages de la généricité de contraintes simples manuellement imposées par un utilisateur, à celles de la précision de la segmentation finale qui se faisait jusqu'alors au prix d'un encodage préliminaire restrictif de règles grammaticales complexes propres à une famille architecturale donnée. Le système décrit permet également de traiter avec robustesse des scènes comprenant des objets occultants et pourrait encore être étendu notamment afin de traiter l'extension tri-dimensionnelle de la sémantisation d'environnements urbains sous forme de nuages de points 3D ou d'une analyse multi-image de bâtiments / The aim of this work is to propose a framework for facade segmentation with user-defined shape priors. In such a framework, the user specifies a shape prior using a rigorously defined shape prior formalism. The prior expresses a number of hard constraints and soft preference on spatial configuration of segments, constituting the final segmentation. Existing approaches to the problem are affected by a compromise between the type of constraints, the satisfaction of which can be guaranteed by the segmentation algorithm, and the capability to approximate optimal segmentations consistent with a prior. In this thesis we explore a number of approaches to facade parsing that combine prior formalism featuring high expressive power, guarantees of conformance of the resulting segmentations to the prior, and effective inference. We evaluate the proposed algorithms on a number of datasets. Since one of our focus points is the accuracy gain resulting from more effective inference algorithms, we perform a fair comparison to existing methods, using the same data term. Our contributions include a combination of graph grammars for expressing variation of facade structure with graphical models encoding the energy of models of given structures for different positions of facade elements. We also present the first linear formulation of facade parsing with shape priors. Finally, we propose a shape prior formalism that enables formulating the problem of optimal segmentation as the inference in a Markov random field over the standard four-connected grid of pixels. The last method advances the state of the art by combining the flexibility of a user-defined grammar with segmentation accuracy that was reserved for frameworks with pre-defined priors before. It also enables handling occlusions by simultaneously recovering the structure of the occluded facade and segmenting the occluding objects. We believe that it can be extended in many directions, including semantizing three-dimensional point clouds and parsing images of general urban scenes

La caractérisation tridimensionnelle de matériaux anciens plats est restée une activité non évidente à accomplir par des méthodes classiques de tomographie à rayons X en raison de leur morphologie anisotrope et de leur géométrie aplatie.Pour surmonter les limites de ces méthodologies, une modalité d'imagerie basée sur le rayonnement diffusé Compton est étudiée dans ce travail. La tomographie classique aux rayons X traite les données de diffusion Compton comme du bruit ajouté au processus de formation d'image, tandis que dans la tomographie du rayonnement diffusé, les conditions sont définies de sorte que la diffusion inélastique devienne le phénomène dominant dans la formation d'image. Dans ces conditions, les rotations relatives entre l'échantillon et la configuration d'imagerie ne sont plus nécessaires. Mathématiquement, ce problème est résolu par la transformée de Radon conique. Le problème direct où la sortie du système est l'image spectrale obtenue à partir d'un objet d'entrée est modélisé. Dans le problème inverse une estimation de la distribution tridimensionnelle de la densité électronique de l'objet d'entrée à partir de l'image spectrale est proposée. La faisabilité de cette méthodologie est supportée par des simulations numériques. / Three-dimensional characterization of flat ancient material objects has remained a challenging activity to accomplish by conventional X-ray tomography methods due to their anisotropic morphology and flattened geometry.To overcome the limitations of such methodologies, an imaging modality based on Compton scattering is studied in this work. Classical X-ray tomography treats Compton scattering data as noise in the image formation process, while in Compton scattering tomography the conditions are set such that Compton data become the principal image contrasting agent. Under these conditions, we are able to avoid relative rotations between the sample and the imaging setup. Mathematically this problem is addressed by means of the conical Radon transform. A model of the direct problem is presented where the output of the system is the spectral image obtained from an input object. The inverse problem is addressed to estimate the 3D distribution of the electronic density of the input object from the spectral image. The feasibility of this methodology is supported by numerical simulations.

Cette thèse aborde le problème de la reconstruction tridimensionnelle de zones urbaines à partir d'images satellitaires très haute résolution. Le contenu informatif de ce type de données est insuffisant pour permettre une utilisation efficace des nombreux algorithmes développés pour des données aériennes. Dans ce contexte, l'introduction de connaissances a priori fortes sur les zones urbaines est nécessaire. Les outils stochastiques sont particulièrement bien adaptés pour traiter cette problématique.<br /><br />Nous proposons une approche structurelle pour aborder ce sujet. Cela consiste à modéliser un bâtiment comme un assemblage de modules urbains élémentaires extraits d'une bibliothèque de modèles 3D paramétriques. Dans un premier temps, nous extrayons les supports 2D de ces modules à partir d'un Modèle Numérique d' Elévation (MNE). Le résultat est un agencement de quadrilatères dont les éléments voisins sont connectés entre eux. Ensuite, nous reconstruisons les bâtiments en recherchant la configuration optimale de modèles 3D se fixant sur les supports précédemment extraits. Cette configuration correspond à la réalisation qui maximise une densité mesurant la cohérence entre la réalisation et le MNE, mais également prenant en compte des connaissances a priori telles que des lois d'assemblage des modules. Nous discutons enfin de la pertinence de cette approche en analysant les résultats obtenus à partir de données satellitaires (simulations PLEIADES). Des expérimentations sont également réalisées à partir d'images aériennes mieux résolues.

The three-dimensional structure of the world makes 3D as the natural evolution of a huge panel of applications. Many different 3D reconstruction algorithms have been implemented to meet different application needs. We target immersive applications. The reconstructed models of users and objects are inserted in 3D virtual environments creating the mixed reality, which is rendered on spatially immersive displays. The user sees its model on the projection walls, allowing him to interact with elements of the virtual world. Immersion requires small latency, high reconstruction rates and non-invasive systems. Furthermore, we choose to reconstruct arbitrary shapes with a geometric method. The review of the state of the art shows that all the acquisition devices cannot be connected to a single computer performing real time reconstruction. The system needs a cluster of computers and a strategy to share information between them. We present a distributed and scalable architecture for real time reconstruction of arbitrary shapes exploiting inter-frame redundancy. The architecture is composed of acquisition nodes and master nodes. Each acquisition node reconstructs partial models from its attached cameras and sends non-redundant information to its master. Each master node merges several partial models. The output of several masters can be merged by another master. We exploit the properties of volumetric algorithms, i.e. an efficient exploitation of inter-frame redundancy and an efficient merging of partial models, to increase performances. We test our volumetric architecture with an innovative implementation of the visual hull. We use a label that codes simultaneously occupancy, subdivision of space and visibility allowing each camera to see only part of the volume of interest. We test our system on a particular implementation of the framework composed of eight cameras and twelve cores, two per acquisition node and four for the master. We achieve fifteen reconstructions per second and less than 100 ms latency from segmentation to the display of the reconstructed model. System performances have been measured on sequences of more than 20 000 frames with unconstrained user’s movements. The system computes a fair approximation of the user in all situations. / La structure tridimensionnelle du monde fait de la 3D l’évolution naturelle d’un grand nombre d’applications. De nombreux algorithmes de reconstruction différents ont été développés pour satisfaire les besoins de différents types d’applications. On cible les applications immersives: Les modèles reconstruits de l’utilisateur ainsi que des objets qu’il porte sont insérés dans des environnements virtuels créant ainsi la réalité mixte. Cette dernière est affichée ce qui permet à l’utilisateur d’interagir avec des éléments virtuels. Le caractère immersif de l’application requiert une reconstruction temps réel à faible latence. Qui plus est, on désire la reconstruction de modèles de formes arbitraires à l’aide de méthodes géométriques. L’état de l’art montre que les différentes caméras ne peuvent pas être connectées à un seul ordinateur responsable de la reconstruction 3D. L’application requiert un cluster d’ordinateurs et une méthode étudiée afin de répartir la charge de travail et d’optimiser les performances. J’ai développé au cours de ma thèse une architecture volumétrique distribuée pour reconstruire des objets de forme arbitraire en temps réel et avec faible latence. Le système exploite les propriétés des algorithmes volumétriques pour améliorer les performances. Il est composé de deux types de nœuds: acquisition et fusion. Les nœuds de type acquisition reconstruisent des modèles partiels et envoient des informations non redondantes aux nœuds de type fusion. Chaque nœud fusion est responsable de la création d’un modèle global à partir de plusieurs modèles partiels. Grâce aux algorithmes développés, chaque étape de fusion rassemble les informations de plusieurs modèles partiels tout en ayant un impact faible sur la latence totale du système. L’architecture a été testée avec une implémentation particulière du Visual Hull permettant une disposition plus libre des caméras. Ces dernières ne doivent plus observer l’entièreté du volume d’intérêt. Chaque partie de l’utilisateur est modélisée grâce aux caméras qui l’observent. Notre système dispose de quatre nœuds d’acquisitions dual core et d’un nœud de fusion dual CPU dual core. On reconstruit quinze modèles par seconde avec une latence inférieure à 100 ms mesurée depuis la segmentation jusqu’au rendu. Quelques soient les mouvements de l’utilisateur et les objets qu’il manipule, le système est capable de le modéliser.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.