Après un post-doctorat à l'Université de Toronto au DGP, j'ai été recruté en octobre 1997 au laboratoire GRAVIR (UMR 5527 CNRS-UJF-INPG-INRIA; dirigé par Claude Puech), dans l'équipe iMAGIS. Mes travaux s'inscrivent dans le domaine de la synthèse d'images, l'équipe s'intéressant plus particulièrement au traitement des scènes complexes. "Complexe" recouvre ici de multiples dimensions, comme la nature des phénomènes (optiques et mécaniques), des formes et des matériaux, et la quantité d'information impliquée. Ce mémoire présente les approches que j'ai faites miennes pour tenter de représenter la complexité de la nature dans l'espoir d'en produire des images et animations de synthèses, ainsi que les travaux particuliers que j'ai menés dans cet esprit après ma thèse de doctorat. Dans le premier chapitre, j'introduis le contexte de la production d'images, ainsi que les trois principaux axes d'attaque que j'adopte pour le traitement de la complexité, à savoir le multi-échelle, le procéduralisme, et la simulation phénomènologique. Dans le second chapitre, je décline mes thèmes de recherche, et retrace les travaux existants relatifs au sujet. Dans le troisième, je résume mes contributions dans ces divers thèmes, le texte de mes principaux articles étant reproduit en Annexes A a D.

Un graphe est un objet mathématique modélisant des relations sur un ensemble d' éléments. Il est utilisé dans de nombreux domaines a des fi ns de modélisation. La taille et la complexité des graphes manipulés de nos jours entraînent des besoins de visualisation a fin de mieux les analyser. Dans cette thèse, nous présentons différents travaux en visualisation interactive de graphes qui s'attachent a exploiter les architectures de calcul parallèle (CPU et GPU) disponibles sur les stations de travail contemporaines. Un premier ensemble de travaux s'intéresse a des problématiques de dessin de graphes. Dessiner un graphe consiste a le plonger visuellement dans un plan ou un espace. La première contribution dans cette thématique est un algorithme de regroupement d'arêtes en faisceaux appelé Winding Roads. Cet algorithme intuitif, facilement implémentable et parallélisable permet de reduire considérablement les problèmes d'occlusion dans un dessin de graphe dus aux nombreux croisements d'arêtes. La seconde contribution est une méthode permettant de dessiner un réseau métabolique complet. Ce type de reseau modélise l'ensemble des réactions biochimiques se produisant dans les cellules d'un organisme vivant. L'avantage de la méthode est de prendre en compte la décomposition du réseau en sous-ensembles fonctionnels ainsi que de respecter les conventions de dessin biologique. Un second ensemble de travaux porte sur des techniques d'infographie pour la visualisation interactive de graphes. La première contribution dans cette thématique est une technique de rendu de courbes paramétriques exploitant pleinement le processeur graphique. La seconde contribution est une méthode de rendu nommée Edge splatting permettant de visualiser la densité des faisceaux d'arêtes dans un dessin de graphe avec regroupement d'arêtes. La dernière contribution porte sur des techniques permettant de mettre en évidence des sous-graphes d'interêt dans le contexte global d'une visualisation de graphes.

Ce travail de thèse concerne l'analyse structurelle des maillages triangulaires surfaciques, ainsi que leur traitement en vue de l'amélioration de leur qualité (remaillage) ou de leur simplification. Dans la littérature, le repositionnement des sommets d'un maillage est soit traité de manière locale, soit de manière globale mais sans un contrôle local de l'erreur géométrique introduite, i.e. les solutions actuelles ne sont pas globales ou introduisent de l'erreur géométrique non-contrôlée. Les techniques d'approximation de maillage les plus prometteuses se basent sur une décomposition en primitives géométriques simples (plans, cylindres, sphères etc.), mais elles n'arrivent généralement pas à trouver la décomposition optimale, celle qui optimise à la fois l'erreur géométrique de l'approximation par les primitives choisies, et le nombre et le type de ces primitives simples. Pour traiter les défauts des approches de remaillage existantes, nous proposons une méthode basée sur un modèle global, à savoir une modélisation graphique probabiliste, intégrant des contraintes souples basées sur la géométrie (l'erreur de l'approximation), la qualité du maillage et le nombre de sommets du maillage. De même, pour améliorer la décomposition en primitives simples, une modélisation graphique probabiliste a été choisie. Les modèles graphiques de cette thèse sont des champs aléatoires de Markov, ces derniers permettant de trouver une configuration optimale à l'aide de la minimisation globale d'une fonction objectif. Nous avons proposé trois contributions dans cette thèse autour des maillages triangulaires 2-variétés : (i) une méthode d'extraction statistiquement robuste des arêtes caractéristiques applicable aux objets mécaniques, (ii) un algorithme de segmentation en régions approximables par des primitives géométriques simples qui est robuste à la présence de données aberrantes et au bruit dans la position des sommets, (iii) et finalement un algorithme d'optimisation de maillages qui cherche le meilleur compromis entre l'amélioration de la qualité des triangles, la qualité de la valence des sommets, le nombre de sommets et la fidélité géométrique à la surface initiale.

Nous présentons une approche de rendu à base d'images qui permet, à partir de photos, de naviguer librement et générer des points de vue quelconques dans des scènes urbaines. Les approches précédentes se basent sur un modèle géométrique complet et précis de la scène. La qualité des résultats produits par ces méthodes se dégrade lorsque la géométrie est approximative. Dans cette thèse, nous proposons une approximation basée sur l'image pour compenser le manque de précision de la géométrie. Dans une première approche, nous utilisons une déformation discontinue des photos guidée par des cartes de profondeur quasi-denses, ce qui produit de meilleurs résultats que le plaquage de texture utilisé par les méthodes précédentes, en particulier lorsque la géométrie est imprécise. Cette approche nécessite quelques indications utilisateur pour identifier les bordures d'occlusion dans les photos. Nous proposons ensuite une méthode entièrement automatique basée sur la même idée de déformation d'image. Cette méthode permet de traiter des scènes plus complexes avec un plus grand nombre de photos. Nous évitons l'intervention utilisateur en sur-segmentant les images d'entrées pour former des superpixels. Nous déformons chaque superpixel indépendamment en utilisant l'information de profondeur clairsemée. Nous proposons également un algorithme de synthèse de profondeur approximative pour traiter les zones de l'image où la géométrie n'est pas disponible. Nous comparons nos résultats à de nombreuses approches récentes et montrons que notre méthode permet une navigation virtuelle libre. Nous avons aussi étudié les défauts du rendu à base d'images d'un point de vue perceptif. Dans une première études controlées, nous avons évalué la perception des distorsions de perspective produites lorsqu'une seule image est projetée sur une géométrie planaire. Les données obtenues lors de cette étude nous ont permis de développer un modèle quantitatif permettant de prédire les distorsions perçues en fonction des paramètres de capture et de visualisation. Dans une autre étude nous comparons les défauts visuels produits par des transitions d'images douces ou abruptes. Nous avons déduit de cette étude des conseils pour choisir le meilleur compromis entre les deux types de transition. Ces deux études ont motivé des choix de conception de nos algorithmes de rendu à base d'images. Enfin, nous démontrons l'utilisation de notre approche pour la thérapie cognitive, ce qui représente la première application de réalité virtuelle à base d'images. Notre méthode permet de réduire considérablement le coût de modélisation 3D d'une scène de réalité virtuelle tout en produisant des visites virtuelles très réalistes.

La synthèse d'images, qui consiste à développer des algorithmes pour générer des images à l'aide d'un ordinateur, est devenue incontournable dans de nombreuses disciplines. <p><p>Les méthodes d'affichage interactives permettent à l'utilisateur d'explorer des environnements virtuels en réalisant l'affichage des images à une cadence suffisamment élevée pour donner une impression de continuité et d'immersion. Malgré les progrès réalisés par le matériel, de nouveaux besoins supplantent toujours les capacités de traitement, et des techniques d'accélération sont nécessaires pour parvenir à maintenir une cadence d'affichage suffisante. Ce travail s'inscrit précisemment dans ce cadre. Il est consacré à la problématique de l'élimination efficace des objets masqués, en vue d'accélérer l'affichage de scènes complexes. Nous nous sommes plus particulièrement intéressé aux méthodes de précalcul, qui effectuent les calculs coûteux de visibilité durant une phase de prétraitement et les réutilisent lors de la phase de navigation interactive. Les méthodes permettant un précalcul complet et exact sont encore hors de portée à l'heure actuelle, c'est pourquoi des techniques approchées leur sont préférée en pratique. Nous proposons trois méthodes de ce type.<p><p>La première, présentée dans le chapitre 4, est un algorithme permettant de déterminer de manière exacte si deux polygones convexes sont mutuellement visibles, lorsque des écrans sont placés entre eux. Nos contributions principales ont été de simplifier cette requête, tant du point de vue théorique que du point de vue de l'implémentation, ainsi que d'accélérer son temps moyen d'exécution à l'aide d'un ensemble de techniques d'optimisation. Il en résulte un algorithme considérablement plus simple à mettre en oeuvre que les algorithmes exacts existant dans la littérature. Nous montrons qu'il est également beaucoup plus efficace que ces derniers en termes de temps de calcul.<p><p><p>La seconde méthode, présentée dans le chapitre 5, est une approche originale pour encoder l'information de visibilité, qui consiste à stocker l'ombre que générerait chaque objet de la scène s'il était remplacé par une source lumineuse. Nous présentons une analyse des avantages et des inconvénients de cette nouvelle représentation. <p><p>Finalement, nous proposons dans le chapitre 6 une méthode de calcul de visibilité adaptée aux scènes d'intérieur. Dans ce type d'environnements, les graphes cellules-portails sont très répandus pour l'élimination des objets masqués, en raison de leur faible coût mémoire et de leur grande efficacité. Nous reformulons le problème de la génération de ces graphes en termes de segmentation d'images, et adaptons un algorithme classique, appelé «watershed», pour les obtenir de manière automatique. Nous montrons que la décomposition calculée de la sorte est proche de la décomposition classique, et qu'elle peut être utilisée pour l'élimination des objets masqués.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Ce travail de thèse concerne l'analyse structurelle des maillages triangulaires surfaciques, ainsi que leur traitement en vue de l'amélioration de leur qualité (remaillage) ou de leur simplification. Dans la littérature, le repositionnement des sommets d'un maillage est soit traité de manière locale, soit de manière globale mais sans un contrôle local de l'erreur géométrique introduite, i.e. les solutions actuelles ne sont pas globales ou introduisent de l'erreur géométrique non-contrôlée. Les techniques d'approximation de maillage les plus prometteuses se basent sur une décomposition en primitives géométriques simples (plans, cylindres, sphères etc.), mais elles n'arrivent généralement pas à trouver la décomposition optimale, celle qui optimise à la fois l'erreur géométrique de l'approximation par les primitives choisies, et le nombre et le type de ces primitives simples. Pour traiter les défauts des approches de remaillage existantes, nous proposons une méthode basée sur un modèle global, à savoir une modélisation graphique probabiliste, intégrant des contraintes souples basées sur la géométrie (l'erreur de l'approximation), la qualité du maillage et le nombre de sommets du maillage. De même, pour améliorer la décomposition en primitives simples, une modélisation graphique probabiliste a été choisie. Les modèles graphiques de cette thèse sont des champs aléatoires de Markov, ces derniers permettant de trouver une configuration optimale à l'aide de la minimisation globale d'une fonction objectif. Nous avons proposé trois contributions dans cette thèse autour des maillages triangulaires 2-variétés : (i) une méthode d'extraction statistiquement robuste des arêtes caractéristiques applicable aux objets mécaniques, (ii) un algorithme de segmentation en régions approximables par des primitives géométriques simples qui est robuste à la présence de données aberrantes et au bruit dans la position des sommets, (iii) et finalement un algorithme d'optimisation de maillages qui cherche le meilleur compromis entre l'amélioration de la qualité des triangles, la qualité de la valence des sommets, le nombre de sommets et la fidélité géométrique à la surface initiale. / The work in this thesis concerns structural analysis of 2-manifold triangular meshes, and their processing towards quality enhancement (remeshing) or simplification. In existing work, the repositioning of mesh vertices necessary for remeshing is either done locally or globally, but in the latter case without local control on the introduced geometrical error. Therefore, current results are either not globally optimal or introduce unwanted geometrical error. Other promising remeshing and approximation techniques are based on a decomposition into simple geometrical primitives (planes, cylinders, spheres etc.), but they generally fail to find the best decomposition, i.e. the one which jointly optimizes the residual geometrical error as well as the number and type of selected simple primitives. To tackle the weaknesses of existing remeshing approaches, we propose a method based on a global model, namely a probabilistic graphical model integrating soft constraints based on geometry (approximation error), mesh quality and the number of mesh vertices. In the same manner, for segmentation purposes and in order to improve algorithms delivering decompositions into simple primitives, a probabilistic graphical modeling has been chosen. The graphical models used in this work are Markov Random Fields, which allow to find an optimal configuration by a global minimization of an objective function. We have proposed three contributions in this thesis about 2-manifold triangular meshes : (i) a statistically robust method for feature edge extraction for mechanical objects, (ii) an algorithm for the segmentation into regions which are approximated by simple primitives, which is robust to outliers and to the presence of noise in the vertex positions, (iii) and lastly an algorithm for mesh optimization which jointly optimizes triangle quality, the quality of vertex valences, the number of vertices, as well as the geometrical fidelity to the initial surface.

Cette thèse traite des problématiques de structuration et de traitement de données discrètes organisées ou non. Elle se décompose en deux parties. La première partie concerne la structuration de données représentées par des ensembles de points du plan ou de l'espace Euclidien. Dans ce contexte, nous considérons les problèmes de la reconstruction polygonale de courbes planaires et de la détection de formes géométriques 3D connues. Ces deux problèmes sont traités par des techniques de géométrie algorithmique et combinatoire, basées sur le diagramme de Voronoï et la triangulation de Delaunay. Dans le cadre de la reconstruction de courbes planaires, nous proposons une famille hiérarchique de sous-graphes du graphe de Gabriel, que nous appelons les beta-CRUSTS Locaux. Nous étudions les propriétés de cette famille, qui nous permettent de concevoir un algorithme de reconstruction des courbes simples. Ensuite, nous proposons une méthode de détection de formes géométriques connues à partir d'un ensemble de points 3D (nous nous restreignons au cas des structures linéaires et planaires), plongés dans un milieu bruité ou non. Cette méthode est basée sur une extension des alpha-formes, générées à partir de boules ellipsoïdales. Dans une deuxième partie, nous traitons le problème de la régularisation de données par des méthodes variationnelles discrètes sur graphes pondérés, de topologie quelconque. Pour cela, nous proposons une large famille de fonctionnelles discrètes, basées sur les normes L2 et Lp du gradient. Ceci conduit à des processus de diffusion linéaire ou non-linéaire sur graphes. Ce formalisme étend un certain nombre de modèles variationnels, que nous appliquons à des problèmes de restauration, de lissage, et de simplification d'images et de maillages.

Un objectif de longue date dans le domaine de la vision par ordinateur est de déduire le contenu 3D d’une scène à partir d’une seule photo, une tâche connue sous le nom d’inverse graphics. L’apprentissage automatique a, dans les dernières années, permis à de nombreuses approches de faire de grands progrès vers la résolution de ce problème. Cependant, la plupart de ces approches requièrent des données de supervision 3D qui sont coûteuses et parfois impossible à obtenir, ce qui limite les capacités d’apprentissage de telles œuvres. Dans ce travail, nous explorons l’architecture des méthodes d’inverse graphics non-supervisées et proposons deux méthodes basées sur des représentations 3D et algorithmes de rendus différentiables distincts: les surfels ainsi qu’une nouvelle représentation basée sur Voronoï. Dans la première méthode basée sur les surfels, nous montrons que, bien qu’efficace pour maintenir la cohérence visuelle, la production de surfels à l’aide d’une carte de profondeur apprise entraîne des ambiguïtés car la relation entre la carte de profondeur et le rendu n’est pas bijective. Dans notre deuxième méthode, nous introduisons une nouvelle représentation 3D basée sur les diagrammes de Voronoï qui modélise des objets/scènes à la fois explicitement et implicitement, combinant ainsi les avantages des deux approches. Nous montrons comment cette représentation peut être utilisée à la fois dans un contexte supervisé et non-supervisé et discutons de ses avantages par rapport aux représentations 3D traditionnelles / A long standing goal of computer vision is to infer the underlying 3D content in a scene from a single photograph, a task known as inverse graphics. Machine learning has, in recent years, enabled many approaches to make great progress towards solving this problem. However, most approaches rely on 3D supervision data which is expensive and sometimes impossible to obtain and therefore limits the learning capabilities of such work. In this work, we explore the deep unsupervised inverse graphics training pipeline and propose two methods based on distinct 3D representations and associated differentiable rendering algorithms: namely surfels and a novel Voronoi-based representation. In the first method based on surfels, we show that, while effective at maintaining view-consistency, producing view-dependent surfels using a learned depth map results in ambiguities as the mapping between depth map and rendering is non-bijective. In our second method, we introduce a novel 3D representation based on Voronoi diagrams which models objects/scenes both explicitly and implicitly simultaneously, thereby combining the benefits of both. We show how this representation can be used in both a supervised and unsupervised context and discuss its advantages compared to traditional 3D representations.