La théorie de l'homologie formalise la notion de trou dans un espace. Pour un sous-ensemble de l'espace Euclidien, on définit une séquence de groupes d'homologie, dont leurs rangs sont interprétés comme le nombre de trous de chaque dimension. Ces groupes sont calculables quand l'espace est décrit d'une façon combinatoire, comme c'est le cas pour les complexes simpliciaux ou cubiques. À partir d'un objet discret (un ensemble de pixels, voxels ou leur analogue en dimension supérieure) nous pouvons construire un complexe cubique et donc calculer ses groupes d'homologie.Cette thèse étudie trois approches relatives au calcul de l'homologie sur des objets discrets. En premier lieu, nous introduisons le champ de vecteurs discret homologique, une structure combinatoire généralisant les champs de vecteurs gradients discrets, qui permet de calculer les groupes d'homologie. Cette notion permet de voir la relation entre plusieurs méthodes existantes pour le calcul de l'homologie et révèle également des notions subtiles associés. Nous présentons ensuite un algorithme linéaire pour calculer les nombres de Betti dans un complexe cubique 3D, ce qui peut être utilisé pour les volumes binaires. Enfin, nous présentons deux mesures (l'épaisseur et l'ampleur) associés aux trous d'un objet discret, ce qui permet d'obtenir une signature topologique et géométrique plus intéressante que les simples nombres de Betti. Cette approche fournit aussi quelques heuristiques permettant de localiser les trous, d'obtenir des générateurs d'homologie ou de cohomologie minimaux, d'ouvrir et de fermer les trous. / Homology theory formalizes the concept of hole in a space. For a given subspace of the Euclidean space, we define a sequence of homology groups, whose ranks are considered as the number of holes of each dimension. Hence, b0, the rank of the 0-dimensional homology group, is the number of connected components, b1 is the number of tunnels or handles and b2 is the number of cavities. These groups are computable when the space is described in a combinatorial way, as simplicial or cubical complexes are. Given a discrete object (a set of pixels, voxels or their analog in higher dimension) we can build a cubical complex and thus compute its homology groups.This thesis studies three approaches regarding the homology computation of discrete objects. First, we introduce the homological discrete vector field, a combinatorial structure which generalizes the discrete gradient vector field and allows to compute the homology groups. This notion allows to see the relation between different existing methods for computing homology. Next, we present a linear algorithm for computing the Betti numbers of a 3D cubical complex, which can be used for binary volumes. Finally, we introduce two measures (the thickness and the breadth) associated to the holes in a discrete object, which provide a topological and geometric signature more interesting than only the Betti numbers. This approach provides also some heuristics for localizing holes, obtaining minimal homology or cohomology generators, opening and closing holes.

La gestion et le contrôle des variations géométriques des produits pendant les processus de développement représentent une préoccupation importante pour la réduction des coûts, l’amélioration de la qualité et la compétitivité des entreprises dans un contexte de mondialisation. Pendant la phase de conception, les exigences fonctionnelles et les tolérances géométriques sont issues de l'intention de conception. La modélisation des formes et le dimensionnement des produits sont aujourd'hui largement supportés par des outils de modélisation géométrique. Toutefois, les variations géométriques ne peuvent pas être évaluées en utilisant intuitivement les outils de modélisation existants. En outre, les étapes de fabrication et de mesure sont les deux principaux générateurs de variations géométriques desquels découlent les deux axiomes bien connus de l'imprécision de la fabrication et de l'incertitude de la mesure. Une vision globale des spécifications géométriques des produits (GPS) devrait considérer non seulement le processus complet de tolérancement, la modélisation des tolérances, et la représentation des tolérances mais aussi les représentations des formes géométriques et les techniques de traitement appropriées ainsi que les algorithmes associés. GeoSpelling, solution considérée comme fondement des normes ISO GPS, offre un langage non ambigu et un cadre complet pour la modélisation et la description des variations géométriques sur le cycle de vie des produits. GeoSpelling s’appuie sur un ensemble de concepts forts dont celui du "Skin Model". Cependant, l’«opérationnalisation» de GeoSpelling n'a pas été réalisée et peu de recherches ont porté sur la génération du Skin Model. Le Skin Model, vu comme un modèle de forme discrète est l'objectif principal de cette thèse. Dans ce travail, les fondamentaux de la géométrie discrète sont appliqués à GeoSpelling, les techniques de simulation de Monte Carlo et les méthodes statistiques d'analyse de formes sont développées pour simuler et analyser les "formes réalistes" prenant en compte, les contraintes géométriques dérivées de spécifications fonctionnelles et de considérations de fabrication. En plus de cartographier les concepts fondamentaux et les opérations de GeoSpelling avec la géométrie discrète, ce travail propose un modèle de forme discrète intégrant les erreurs aléatoires et systématiques approchées du second ordre. Le concept d'un Skin Model moyen et ses statistiques robustes sont également développés. Une étude de cas plus complète, basée sur un embouti de tôle en forme de croix pour lequel le processus de fabrication est simulé avec des variations stochastiques, permet d’illustrer les résultats des simulations du skin model. Les performances de la méthode sont ensuite évaluées. / The management and the control of product geometrical variations during the whole development process is an important issue for cost reduction, quality improvement and company competitiveness in the global manufacturing era. During the design phase, geometric functional requirements and tolerances are derived from the design intent. Geometric modeling tools, now largely support the modeling of product shapes and dimensions. However, permissible geometrical variations cannot be intuitively assessed using existing modeling tools. In addition, the manufacturing and measurement stages are two main geometrical variations generators according to the two well know axioms of manufacturing imprecision and measurement uncertainty. A comprehensive view of Geometrical Product Specifications should consider not only the complete tolerancing process, tolerance modeling and tolerance representation but also shape geometric representations, and suitable processing techniques and algorithms. GeoSpelling as the basis of the GPS standard enables a comprehensive modeling framework and an unambiguous language to describe geometrical variations covering the overall product life cycle thanks to a set of concepts and operations based on the fundamental concept of the “Skin Model”. However, the “operationalization” of GeoSpelling has not been successfully completed and few research studies have focused on the skin model simulation. The skin model as a discrete shape model is the main focus of this dissertation. We investigate here discrete geometry fundamentals of GeoSpelling, Monte Carlo Simulation Techniques and Statistical Shape Analysis methods to simulate and analyze “realistic shapes” when considering geometrical constraints requirements (derived from functional specifications and manufacturing considerations). In addition to mapping fundamental concepts and operations to discrete geometry one’s, the work presented here investigates a discrete shape model for both random and systematic errors when taking into account second order approximation of shapes. The concept of a mean skin model and its robust statistics are also developed. The results of the skin model simulations and visualizations are reported. By means of a case study based on a cross-shaped sheet metal part where the manufacturing process is simulated using Finite Element Analysis considering stochastic variations, the results of the skin model simulations are shown, and the performances of the method are described.

Dans ce travail de thèse , je présente comment extraire les géométries discrètes de l'espace-temps de la formulation covariante de la gravitaté quantique à boucles, qui est appelé le formalisme de la mousse de spin. LQG est une théorie quantique de la gravité qui non-perturbativement quantifie la relativité générale indépendante d'un fond fixe. Il prédit que la géométrie de l'espace est quantifiée, dans lequel l'aire et le volume ne peuvent prendre que la valeur discrète. L'espace de Hilbert cinématique est engendré par les fonctions du réseau de spin. L'excitation de la géométrie peut être parfaitement visualisée comme des polyèdres floue qui collées à travers leurs facettes. La mousse de spin définit la dynamique de la LQG par une amplitude de la mousse de spin sur un complexe cellulaire avec un état du réseau de spin comme la frontiére. Cette thèse présente deux résultats principaux. Premièrement, la limite semi-classique de l'amplitude de la mousse de spin sur un complexe simplicial arbitraire avec une frontière est complètement étudiée. La géométrie discrète classique de l'espace-temps est reconstruite et classée par les configurations critiques de l'amplitude de la mousse de spin. Deuxièmement, la fonction de trois-point de LQG est calculé. Il coïncide avec le résultat de la gravité discrète. Troisièmement, la description des géométries discrètes de hypersurfaces nulles est explorée dans le cadre de la LQG. En particulier, la géométrie nulle est décrit par une structure singulière euclidienne sur la surface de type espace à deux dimensions définie par un feuilletage de l'espace-temps par hypersurfaces nulles. / In this thesis, I will present how to extract discrete geometries of space-time fromthe covariant formulation of loop quantum gravity (LQG), which is called the spinfoam formalism. LQG is a quantum theory of gravity that non-perturbative quantizesgeneral relativity independent from a fix background. It predicts that the geometryof space is quantized, in which area and volume can only take discrete value. Thekinematical Hilbert space is spanned by Penrose's spin network functions. The excita-tion of geometry can be neatly visualized as fuzzy polyhedra that glued through theirfacets. The spin foam defines the dynamics of LQG by a spin foam amplitude on acellular complex, bounded by the spin network states. There are three main results inthis thesis. First, the semiclassical limit of the spin foam amplitude on an arbitrarysimplicial cellular complex with boundary is studied completely. The classical discretegeometry of space-time is reconstructed and classified by the critical configurations ofthe spin foam amplitude. Second, the three-point function from LQG is calculated.It coincides with the results from discrete gravity. Third, the description of discretegeometries of null hypersurfaces is explored in the context of LQG. In particular, thenull geometry is described by a Euclidean singular structure on the two-dimensionalspacelike surface defined by a foliation of space-time by null hypersurfaces. Its quan-tization is U(1) spin network states which are embedded nontrivially in the unitaryirreducible representations of the Lorentz group.

Les travaux effectués durant cette thèse portent sur l’appariement de formes planes basé sur une squelettisation hiérarchique. Dans un premier temps, nous avons abordé la création d’un squelette de forme grâce à un algorithme associant des outils de la géométrie discrète et des filtres. Cette association permet d’acquérir un squelette regroupant les propriétés désirées dans le cadre de l’appariement. Néanmoins, le squelette obtenu reste une représentation de la forme ne différenciant pas les branches représentant l’allure générale de celles représentant un détail de la forme. Or, lors de l’appariement, il semble plus intéressant d’associer des branches ayant le même ordre d’importance, mais aussi de donner plus de poids aux associations décrivant un aspect global des formes. Notre deuxième contribution porte sur la résolution de ce problème. Elle concerne donc la hiérarchisation des branches du squelette, précédemment créé, en leur attribuant une pondération reflétant leur importance dans la forme. À cet effet, nous lissons progressivement une forme et étudions la persistance des branches pour leur attribuer un poids. L’ultime étape consiste donc à apparier les formes grâce à leur squelette hiérarchique modélisé par un hypergraphe. En d’autres termes, nous associons les branches deux à deux pour déterminer une mesure de dissimilarité entre deux formes. Pour ce faire, nous prenons en compte la géométrie des formes, la position relative des différentes parties des formes ainsi que de leur importance. / The works performed during this thesis focuses on the matching of planar shapes based on a hierarchical skeletonisation. First, we approached the creation of a shape skeleton using an algorithm combining the tools of discrete geometry and filters. This combination allows to acquire a skeleton gathering the desired properties in the context of matching. Nevertheless, the resulting skeleton remains a representation of the shape, which does not differentiate branches representing the general shape of those coming from a detail of the shape. But when matching, it seems more interesting to pair branches of the same order of importance, but also to give more weight to associations describing an overall appearance of shapes. Our second contribution focuses on solving this problem. It concerns the prioritization of skeletal branches, previously created by assigning a weight reflecting their importance in shape. To this end, we gradually smooth a shape and study the persistence of branches to assign a weight. The final step is to match the shapes with their hierarchical skeleton modeled as a hypergraph. In other words, we associate the branches two by two to determine a dissimilarity measure between two shapes. To do this, we take into account the geometry of the shapes, the relative position of different parts of the shapes and their importance.

L'étude non destructive du bois à partir de scanners à rayons X nécessite d’imaginer de nouvelles solutions adaptées à l'analyse des images. Préoccupation à la fois de la recherche agronomique et du milieu industriel des scieries, la segmentation des nœuds de bois est un défi majeur en termes de robustesse aux spécificités de chaque espèce et aux conditions d'acquisition des images. Les travaux menés dans cette thèse permettent de proposer un processus de segmentation en deux phases. Il isole d'abord chaque nœud dans une zone réduite puis segmente le nœud unique de chaque zone. Les solutions proposées pour chaque phase permettent d'intégrer les connaissances sur l'organisation interne du tronc et les mécanismes inhérents à sa croissance, à travers des outils classiques du traitement et de l'analyse d'image. La première phase repose en grande partie sur un principe de détection du mouvement emprunté à l'analyse vidéo et revisité. Deux approches de segmentation sont ensuite proposées, considérant pour l'une les coupes tomographiques initiales, et pour l'autre de nouvelles coupes ré-échantillonnées pour chaque nœud, orthogonalement à sa trajectoire. L'intégralité du processus a été implémenté dans un logiciel dédié aussi bien à l'expérimentation et la validation de l'approche qu'aux échanges interdisciplinaires. Le support applicatif du bois souligne la capacité de spécialisation des algorithmes génériques du traitement et de l'analyse d'image, et la pertinence de l'intégration de connaissances a priori dans cette optique / The non-destructive study of wood from X-Ray CT scanners requires to imagine new solutions adapted to analysis of images. Relating both agronomic research and industrial sector of sawmills, segmentation of wood knots is a major challenge in terms of robustness to specificities of each species and to image acquisition conditions. The works carried out in this thesis allow to propose a segmentation process in two phases. It first isolates each knot in a reduced area then it segments the unique knot of each area. Proposed solutions for each phase allow to integrate knowledges about internal organization of trunk and mechanisms inherent to its growth, through classical tools of image analysis and processing. The first phase is essentially based on a movement detection principle borrowed from video analysis and revisited. Two segmentation approaches are then proposed, considering for one the initial CT slices and for the other news slices resampled for each knot orthogonally to its trajectory. The complete process has been implemented in a software dedicated both for experimentation and validation of approach, and to interdisciplinary dialogs. The applicative support of wood emphasizes the specialization abilities of generic image analysis and processing algorithms, and the relevance to integrate priori knowledges in this perspective

La présence de spécularité sur un objet est un problème récurrent qui limite l'application de nombreuses méthodes de segmentation. En effet, les spécularités sont des zones ayant une intensité très élevée et perturbent énormément la détection dès lors que l'on utilise la notion de gradient de l'image. Les travaux menés dans cette thèse permettent de proposer une nouvelle méthode de détection d'un objet tubulaire métallique dans une image. La méthode s'affranchit de la notion de gradient en utilisant la notion de profil d'intensité. Nous proposons dans ce manuscrit, un processus qui parcourt des zones rectangulaires prédéfinies de l'image, par balayage d'un segment discret à la recherche d'un profil d'intensité référence. Ces travaux s'inscrivent dans une collaboration avec Numalliance, une entreprise qui fabrique des machines-outils. Cette collaboration permet de mettre en pratique cette méthode dans le cadre d'un système de contrôle qualité automatique et temps-réel des pièces manufacturées par les machines-outils. Pour cela, la méthode présentée doit être rapide, robuste aux spécularités et à l'environnement industriel tout en étant suffisamment précise pour permettre de conclure sur la conformité ou non de la pièce / The presence of specularity on an object is a recurring problem that limits the application of many segmentation methods. Indeed, specularities are areas with a very high intensity and greatly disturb the detection when the notion of gradient of the image is used. The work carried out in this thesis makes it possible to propose a new detection method for a metallic tubular object in an image. The method avoids the notion of gradient by using the notion of intensity profile. We propose in this manuscript a process which traverses predefined rectangular areas of the image by scanning a discrete segment in search of a reference intensity profile. This work is part of a collaboration with Numalliance, a company that manufactures machine tools. This collaboration enables this method to be put into a real industrial application as part of an automatic and real-time quality control system for parts manufactured by machine tools. To this end, the method presented must be fast, robust to the specularities and to the industrial environment while being sufficiently precise to make it possible to conclude on the conformity or not of the part

La géostatistique fournit de nombreux outils pour caractériser et traiter des données réparties dans l'espace. La plupart de ces outils sont basés sur l'analyse et la modélisation d'une fonction appelée variogramme qui permet de construire différents opérateurs spatiaux : le krigeage et les simulations. Les modèles variographiques sont relativement intuitifs : certains paramètres variographiques peuvent être directement interprétés en termes de caractéristiques structurales. Ces approches sont cependant limitées car elles ne permettent pas de prendre correctement en compte la structuration locale des données. Plusieurs types de modèles géostatistiques non-stationnaires existent. Ils requièrent généralement un paramétrage compliqué, peu intuitif, et ils n'apportent pas de réponse satisfaisante quant à certains de types de non-stationnarité. C'est pour répondre au besoin d'une prise en compte efficace et opérationnelle de la non-stationnarité dans un jeu de données que, dans le cadre de cette thèse, nous prenons le parti de déterminer des paramètres variographiques locaux, appelés M-Paramètres par des méthodes de traitement d'images. Notre démarche se fonde principalement sur la détermination des paramètres morphologiques de dimensions et d'orientations de structures. Il résulte de la détermination de M-Paramètres une meilleure adéquation entre modèles variographiques et caractéristiques structurales des données. Les méthodes de détermination de M-Paramètres développées ont été appliquées sur des données bathymétriques, sur des jeux de données laissant apparaître des corps géologiques complexes ou encore sur des jeux de données environnementaux, liés au domaine de la pollution en zone urbaine par exemple. Ces exemples illustrent les améliorations de résultats de traitement géostatistique obtenus avec M-Paramètres. Enfin, partant du constat que certains phénomènes ne respectent pas une propagation euclidienne, nous avons étudié l'influence du choix de la distance sur les résultats de krigeage et de simulation. En utilisant des distances géodésiques, nous avons pu obtenir des résultats d'estimation impossible à reproduire avec des distances euclidiennes.

Cette thèse s'inscrit dans le cadre de la géométrie discrète 2D avec pour principales applications l'analyse et la caractérisation de formes. Nous nous intéressons ici aux différents codages de contour de formes binaires que nous présentons dans un premier temps. Nous présentons ensuite plus en détail le plus ancien d'entre eux : le codage de Freeman, et nous développons plus particulièrement des algorithmes sur ce qu'il est possible de faire à partir de ce code. Nous étudions donc l'estimation de paramètres géométriques et de paramètres de formes sur une forme binaire comme le périmètre, l'aire, les diamètres apparents, la dimension fractale, et les coefficients de symétrie d'une forme. Nous voyons ensuite les transformations qu'il est possible d'effectuer sur le code de Freeman sans revenir à la représentation classique de la scène. Enfin, nous abordons la notion de morphologie mathématique en proposant une méthode d'obtention du code du dilaté et de l'érodé d'une forme connue par son code de Freeman.

L'imagerie médicale est une ressource de données principale pour différents types d'applications. Bien que les images concrétisent beaucoup d'informations sur le cas étudié, toutes les connaissances a priori du médecin restent implicites. Elles jouent cependant un rôle très important dans l'interprétation et l'utilisation des images médicales. Dans cette thèse, des connaissances anatomiques a priori sont intégrées dans deux applications médicales. Nous proposons d'abord une chaîne de traitement automatique qui détecte, quantifie et localise des anévrismes dans un arbre vasculaire segmenté. Des lignes de centre des vaisseaux sont extraites et permettent la détection et la quantification automatique des anévrismes. Pour les localiser, une mise en correspondance est faite entre l'arbre vasculaire du patient et un arbre vasculaire sain. Les connaissances a priori sont fournies sous la forme d'un graphe. Dans le contexte de l'identification des sous-parties d'un organe représenté sous forme de maillage, nous proposons l'utilisation d'une ontologie anatomique, que nous enrichissons avec toutes les informations nécessaires pour accomplir la tâche de segmentation de maillages. Nous proposons ensuite un nouvel algorithme pour cette tâche, qui profite de toutes les connaissances a priori disponibles dans l'ontologie.

L'objectif de cette thèse est de fournir des outils logiciels aux anatomistes et neuro-anatomistes afin de permettre une analyse tridimensionnelle quantitative des réseaux micro-vasculaires cérébraux. Cette analyse demande des images de très haute résolution (permettant de tenir compte du plus petit capillaire), mais aussi des images couvrant une surface du cortex suffisamment large pour être statistiquement significative. Comme elle ne peut être acquise en une seule fois, nous proposons de paver la surface à imager de plusieurs petites images et de créer ainsi une grande "mosaïque d'images". Chaque image est acquise grâce à un microscope confocal dont la résolution impose une grille anisotrope. Nous avons alors développé des outils de reconstruction spécifiques pour ce genre de mosaïques afin de générer des images à la fois très étendues et très précises. Or ces images sont trop volumineuses pour être chargées et traitées en une seule fois dans la mémoire d'un ordinateur standard. Nous avons donc développé des outils spécifiques de traitement d'image (filtrage, seuillage, outils de morphologie mathématique, de topologie discrète...) décomposés en traitements en sous-images. L'étude quantitative du réseau micro-vasculaire cérébral nécessite l'extraction des lignes centrales et une estimation des diamètres des vaisseaux. La géométrie discrète offre un cadre de travail rapide et puissant pour ce type de calculs. En effet, nous devons calculer une carte de distance en tout point de l'image. Afin d'avoir la meilleure précision possible tout en gardant un temps de traitement raisonnable, nous avons choisi une carte de distance du chanfrein. Une de nos contributions a été de proposer un calcul automatique des coefficients de chanfrein permettant de s'adapter à tout type d'anisotropie de grille. L'utilisation de telles cartes de distances permet de guider des algorithmes de squelettisation. De tels outils nécessitent la conservation d'une propriété globale, la topologie. Comme nous nous plaçons dans un cadre où l'on a accès qu'à des sous images, nous avons proposé un nouvel algorithme de squelettisation qui minimise le nombre d'accès à des sous-images afin de garantir un temps de calcul acceptable, tout en localisant correctement le squelette. Ces algorithmes ont été intégrés dans le logiciel ergonomique Amira et sont utilisés par les chercheurs de l'unité U455 de l'INSERM.