Σκοπός της παρούσας εργασίας είναι η παρουσίαση των σταδίων της πιο γενικής από τις παθητικές μεθόδους τρισδιάστατης ανακατασκευής στατικών σκηνών, της δομής από κίνηση. Εκτός της χρήσης στερεοσκοπικών ζευγών εικόνων για την δημιουργία πυκνών χαρτών βάθους, παρουσιάζεται και η περίπτωση χρήσης παράλληλων εικόνων, που αποτελούν την καλύτερη λύση σε περιπτώσεις που η κύρια συνιστώσα της κίνησης της κάμερας είναι παράλληλη στον οπτικό της άξονα. Επίσης, παρουσιάζεται μια πρωτότυπη γεωμετρική μέθοδος διόρθωσης των εικόνων τόσο για την δημιουργία στερεοσκοπικών ζευγών, όσο και για την περίπτωση των παράλληλων εικόνων. Σε κάθε στάδιο της όλης διαδικασίας, περιγράφονται οι μέθοδοι εκείνες που θεωρούνται οι αντιπροσωπευτικότερες της κατηγορίας τους. / The purpose of this paper is to present the phases of the most general passive method of three dimensional reconstruction of static scenes,called structure from motion.Besides using stereo images as the final result of image rectification; we examine the case of using parallel images that represent the best solution in cases where the main component of the camera motion is parallel to the optical axis. Also we show an original geometric correction method of images both for generating stereo pairs and parallel images pairs. At each stage of the process we describe some of the known methods that can be considered representative of their class.

Une carte généralisée est un modèle topologique permettant de représenter implicitementun ensemble de cellules (sommets, arêtes, faces , volumes, . . .) ainsi que l’ensemblede leurs relations d’incidence et d’adjacence au moyen de brins et d’involutions. Les cartes généralisées sont notamment utilisées pour modéliser des images et objets3D. A ce jour il existe peu d’outils permettant l’analyse et la comparaison de cartes généralisées.Notre objectif est de définir un ensemble d’outils permettant la comparaisonde cartes généralisées.Nous définissons tout d’abord une mesure de similarité basée sur la taille de la partiecommune entre deux cartes généralisées, appelée plus grande sous-carte commune.Nous définissons deux types de sous-cartes, partielles et induites, la sous-carte induitedoit conserver toutes les involutions tandis que la sous-carte partielle autorise certaines involutions à ne pas être conservées. La sous-carte partielle autorise que les involutionsne soient pas toutes conservées en analogie au sous-graphe partiel pour lequelles arêtes peuvent ne pas être toutes présentes. Ensuite nous définissons un ensembled’opérations de modification de brins et de coutures pour les cartes généralisées ainsiqu’une distance d’édition. La distance d’édition est égale au coût minimal engendrépar toutes les successions d’opérations transformant une carte généralisée en une autrecarte généralisée. Cette distance permet la prise en compte d’étiquettes, grâce à l’opérationde substitution. Les étiquettes sont posées sur les brins et permettent d’ajouter del’information aux cartes généralisées. Nous montrons ensuite, que pour certains coûtsnotre distance d’édition peut être calculée directement à partir de la plus grande souscartecommune.Le calcul de la distance d’édition est un problème NP-difficile. Nous proposons unalgorithme glouton permettant de calculer en temps polynomial une approximation denotre distance d’édition de cartes. Nous proposons un ensemble d’heuristiques baséessur des descripteurs du voisinage des brins de la carte généralisée permettant de guiderl’algorithme glouton, et nous évaluons ces heuristiques sur des jeux de test générésaléatoirement, pour lesquels nous connaissons une borne de la distance.Nous proposons des pistes d’utilisation de nos mesures de similarités dans le domainede l’analyse d’image et de maillages. Nous comparons notre distance d’éditionde cartes généralisées avec la distance d’édition de graphes, souvent utilisée en reconnaissancede formes structurelles. Nous définissons également un ensemble d’heuristiquesprenant en compte les étiquettes de cartes généralisées modélisant des images etdes maillages. Nous mettons en évidence l’aspect qualitatif de notre appariement, permettantde mettre en correspondance des zones de l’image et des points du maillages. / A generalized map is a topological model that allows to represent implicitly differenttypes of cells (vertices, edges, volumes, . . . ) and their relationship by using a set of dartsand some involutions. Generalized maps are used to model 3D meshes and images.Anyway there exists only few tools to compare theses generalized maps. Our main goalis to define some tools tolerant to error to compare them.We define a similarity measure based on the size of the common part of two generalizedmaps, called maximum common submap. Then we define two types of submaps,partial and induced, the induced submap needs to preserve all the involutions whereasthe partial one can allow some involutions to be removed. Then we define a set of operationsto modify a generalized map into another and the associated edit distance. Theedit distance is equal to the minimal cost of all the sequences of operations that modifya generalized map into the other. This edit distance can use labels to consider additionalinformation, with the operation called ’substitution’. Labels are set on darts. Wenext showa relation between our edit distance and the distance based on the maximumcommon submap.Computing theses distance are aNP-hard problem.We propose a greedy algorithmcomputing an approximation of it. We also propose a set of heuristics based on thedescription of the neighborhoob of the darts to help the greedy algorithm.We try thesesheuristics on a set of generalized maps randomly generated where a lower bound of thedistance is known. We also propose some applications of our similarity measures inthe image analysis domain. We compare our edit distance on generalized maps withthe edit distance on graphs. We also define a set of labels specific on images and 3Dmeshes. And we show that the matching computed by our algorithm construct a linkbetween images’s areas.

La numérisation est un procédé qui consiste à enregistrer un objet dans un ordinateur pour pouvoir ensuite le manipuler à l'aide d'outils informatiques. Nous nous intéressons dans ce manuscrit à la numérisation d'objets tridimensionnels. Il s'agit tout d'abord d'enregistrer leur forme. De nombreuses méthodes ont été développées pour répondre à ce problème, et nous nous concentrerons sur les objets représentés par des maillages. Sur ces objets, il est alors utile de pouvoir représenter des attributs tels que la couleur, la température ou la charge électrique, selon l'application. Nous proposons deux approches complémentaires pour aborder ce problème. La première est fondée sur le placage de textures. Cette technique consiste à déplier (paramétrer) le maillage à plat sur une image dans laquelle l'attribut est stocké. Une valeur récupérée dans l'image est ainsi associée à chaque point de l'objet. Nous proposerons une méthode permettant de masquer l'artéfact des coutures qui est inhérent à cette technique. Déplier le maillage nécessite qu'il soit de bonne qualité, ce qui n'est pas toujours le cas. Nous décrivons donc également dans un second temps une approche de l'échantillonnage d'une surface via un diagramme de Voronoï restreint. Nous expliquons en particulier comment calculer efficacement un tel objet et comment l'optimiser par rapport à un critère de qualité. Ces résultats sont ensuite appliqués au problème de l'ajustement de surfaces / Digitalisation is an operation which consists in storing an object in a computer for further manipulation using data processing tools. In this document, we are interested in the digitalisation of three-dimensional objects. It is first a matter of recording the shape of the object. Many methods have been developed to address this problem, and we will focus on objects described as meshes. On such objects the storage of attributes like colour, temperature or electrical charge is often useful, depending on the application. We will describe two complementary approaches to deal with this issue. The first one relies on texture mapping. This technique consists in unfolding ? parametrising ? the mesh on a flat image in which the attribute is stored. A value recovered from the image can therefore be associated with each point of the object. We will describe a method which hides the seam artifact, commonly encountered using this technique. Unfolding the mesh demands that its quality be good, which is not always the case. We thus secondly describe a surface sampling method based on a restricted Voronoï diagram. We especially detail how to efficiently compute such an object and how to optimise it with respect to some quality measure. These results are then applied to the surface fitting problem

L’appariement d’images est un sujet central de recherche en vision par ordinateur. La recherche sur cette problématique s’est longuement concentrée sur ses aspects optiques, mais ses aspects géométriques ont reçu beaucoup moins d’attention. Cette thèse promeut l’utilisation de la géométrie pour compléter les informations optique dans les tâches de mise en correspondance d’images. Tout d’abord, nous nous penchons sur les méthodes globales pour lesquelles les occlusions et arêtes vives posent des défis. Dans ces scenarios, le résultat est fortement dépendant de la contribution du terme de régularisation. À l'aide d’une caractérisation géométrique de ce comportement, nous formulons une méthode d’appariement qui dirige les lignes de la grille loin des régions problématiques. Bien que les méthodes variationnelles fournissent des résultats qui se comportent bien en général, les méthodes locales basées sur la propagation de correspondances fournissent des résultats qui s’adaptent mieux à divers structures 3D mais au détriment de la cohérence globale de la surface reconstruite. Par conséquent, nous présentons une nouvelle méthode de propagation guidée par des reconstructions locales de surface / AbstractImage matching is a central research topic in computer vision which has been mainly focused on optical aspects. The aim of the work presented herein consists in the direct use of geometry to complement optical information in the tasks of 2D matching. First, we focus on global methods based on the calculus of variations. In such methods occlusions and sharp features raise difficult challenges. In these scenarios only the contribution of the regularizer accounts for results. Based on a geometric characterization of this behaviour, we formulate a variational matching method that steers grid lines away from problematic regions. While variational methods provide well behaved results, local methods based on match propagation provide results that adapt closely to varying 3D structures although choppy in nature. Therefore, we present a novel method to propagate matches using local information about surface regularity correcting 3D positions along with corresponding 2D matchings

Η εργασία αυτή επικεντρώνεται στις τεχνολογίες τρισδιάστατης απεικόνισης στο διαδίκτυο. Αρχικά δίνεται μια σύντομη επισκόπηση των κυριότερων αντιπροσώπων των τεχνολογιών αυτών παρουσιάζοντας τα διακριτά χαρακτηριστικά τους. Στη συνέχεια, έχοντας πλέον περιγράψει τις δυνατότητες της τεχνολογίας αυτής, παρουσιάζεται η υλοποίηση ενός συστήματος που συνδυάζει στοιχεία της τεχνολογίας X3D με αυτή της HTML. Η εφαρμογή έχει ως στόχο να αναδείξει τις δυνατότητες συνεργασίας των δύο αυτών τεχνολογιών τόσο μεταξύ τους όσο και σε επίπεδο αλληλεπίδρασης με το χρήστη. / This study is focused on web 3D technologies. Starting with a short review of current major web 3D technology representatives, highlighting their distinct characteristics. Following, having all major capabilities of web 3D technology described, a system that combines X3D and HTML technologies is presented. This application aims on advancing the X3D and HTML unification benefits on internal and user interaction.

Les créatures à n-pattes, comme les quadrupèdes, les arachnides ou les reptiles, sont une partie essentielle de n’importe quelle simulation et ils participent à rendre les mondes virtuels plus crédibles et réalistes. Ces créatures à n-pattes doivent être capables de se déplacer librement vers les points d’intérêt de façon réaliste, afin d’offrir une meilleure expérience immersive aux utilisateurs. Ces animations de locomotion sont complexes en raison d’une grande variété de morphologies et de modes de déplacement. Il convient d’ajouter à cette problématique la complexité des environnements où ils naviguent. Un autre défi lors de la modélisation de tels mouvements vient de la difficulté à obtenir des données sources. Dans cette thèse nous présentons un système capable de générer de manière procédurale des animations de locomotion pour des dizaines de créatures à n-pattes, en temps réel, sans aucune donnée de mouvement préexistante. Notre système est générique et contrôlable. Il est capable d’animer des morphologies différentes, tout en adaptant les animations générées à un environnement dynamique complexe, en temps réel, ce qui donne une grande liberté de déplacement aux créatures à n-pattes simulées. De plus, notre système permet à l’utilisateur de contrôler totalement l’animation produite et donc le style de locomotion / Multi-legged characters like quadrupeds, arachnids, reptiles, etc. are an essential part of any simulation and they greatly participate in making virtual worlds more life-like. These multi-legged characters should be capable of moving freely and in a believable way in order to convey a better immersive experience for the users. But these locomotion animations are quite rich due to the complexity of the navigated environments and the variety of the animated morphologies, gaits, body sizes and proportions, etc. Another challenge when modeling such animations arises from the lack of motion data inherent to either the difficulty to obtain them or the impossibility to capture them.This thesis addresses these challenges by presenting a system capable of procedurally generating locomotion animations fordozens of multi-legged characters in real-time and without anymotion data. Our system is quite generic thanks to the chosen Procedural-Based techniques and it is capable of animating different multi-legged morphologies. On top of that, the simulated characters have more freedom while moving, as we adapt the generated animations to the dynamic complex environments in real-time. Themain focus is plausible movements that are, at the same time,believable and fully controllable. This controllability is one of the forces of our system as it gives the user the possibility to control all aspects of the generated animation thus producing the needed style of locomotion