L'analyse d'images est devenue ces dernières années une discipline de plus en plus riche de l'informatique. La topologie discrète propose un panel d'outils incontournables dans le traitement d'images, notamment grâce à l'outil du squelette, qui permet de simplifier des objets tout en conservant certaines informations intactes. Cette thèse étudie comment certains outils de la topologie discrète, notamment les squelettes, peuvent être utilisés pour le traitement d'images de matériaux.Le squelette d'un objet peut être vu comme une simplification d'un objet, possédant certaines caractéristiques identiques à celles de l'objet original. Il est alors possible d'étudier un squelette et de généraliser certains résultats à l'objet entier. Dans une première partie, nous proposons une nouvelle méthode pour conserver, dans un squelette, certaines caractéristiques géométriques de l'objet original (méthode nécessitant un paramètre de filtrage de la part de l'utilisateur) et obtenir ainsi un squelette possédant la même apparence que l'objet original. La seconde partie propose de ne plus travailler avec des objets constitués de voxels, mais avec des objets constitués de complexes cubiques. Dans ce nouveau cadre, nous proposons de nouveaux algorithmes de squelettisation, dont certains permettent de conserver certaines caractéristiques géométriques de l'objet de départ dans le squelette, de façon automatique (aucun paramètre de filtrage ne doit être donné par l'utilisateur). Nous montrerons ensuite comment un squelette, dans le cadre des complexes cubiques, peut être décomposé en différentes parties. Enfin, nous montrerons nos résultats sur différentes applications, allant de l'étude des matériaux à l'imagerie médicale

.

Dans son environnement quotidien, l'homme est volontairement ou involontairement exposé à des champs électromagnétiques radiofréquences. La prédiction de l'élévation de température induite par ce rayonnement, à l'aide d'un calcul sur un modèle anatomique maillé, dépend beaucoup de la qualité de ce modèle. Les méthodes actuelles de génération de maillages volumiques utilisent des représentations surfaciques intermédiaires des données anatomiques. Nous montrons qu'il n'est pas nécessaire d'avoir une représentation surfacique pour générer un maillage volumique. Nous proposons une construction de maillages tétraédriques basée sur les diagrammes de Voronoi Centroïdaux et leur dual, la triangulation de Delaunay. Cette approche, contrairement aux approches de la littérature, traite directement un volume de voxels segmentés, obtenu par IRM ou par tomographie X, sans passer par une représentation surfacique. An d'obtenir des maillages, non plus uniformes mais adaptés à la complexité anatomique, nous avons proposé une nouvelle méthode de capture de cette complexité à l'aide d'une approximation de l'axe médian. Une comparaison, avec trois autres méthodes de génération de maillages de la littérature, montre que notre approche construit des tétraèdres de meilleure qualité géométrique pour différents critères. De cette qualité découle une meilleure précision sur la température induite par le rayonnement électromagnétique, calculée par une méthode d'éléments finis, ainsi qu'un temps de calcul réduit. Ces résultats montrent le potentiel de notre approche discrète de type "Voronoï-Delaunay" pour la génération de maillages tétraédriques.

L'analyse d'images est devenue ces dernières années une discipline de plus en plus riche de l'informatique. La topologie discrète propose un panel d'outils incontournables dans le traitement d'images, notamment grâce à l'outil du squelette, qui permet de simplifier des objets tout en conservant certaines informations intactes. Cette thèse étudie comment certains outils de la topologie discrète, notamment les squelettes, peuvent être utilisés pour le traitement d'images de matériaux.Le squelette d'un objet peut être vu comme une simplification d'un objet, possédant certaines caractéristiques identiques à celles de l'objet original. Il est alors possible d'étudier un squelette et de généraliser certains résultats à l'objet entier. Dans une première partie, nous proposons une nouvelle méthode pour conserver, dans un squelette, certaines caractéristiques géométriques de l'objet original (méthode nécessitant un paramètre de filtrage de la part de l'utilisateur) et obtenir ainsi un squelette possédant la même apparence que l'objet original. La seconde partie propose de ne plus travailler avec des objets constitués de voxels, mais avec des objets constitués de complexes cubiques. Dans ce nouveau cadre, nous proposons de nouveaux algorithmes de squelettisation, dont certains permettent de conserver certaines caractéristiques géométriques de l'objet de départ dans le squelette, de façon automatique (aucun paramètre de filtrage ne doit être donné par l'utilisateur). Nous montrerons ensuite comment un squelette, dans le cadre des complexes cubiques, peut être décomposé en différentes parties. Enfin, nous montrerons nos résultats sur différentes applications, allant de l'étude des matériaux à l'imagerie médicale / These last years, the domain of image analysis has drastically evolved. Digital topology offer a set of tools adapted to image analysis, especially the skeletonization process (also called homotopic thinning) which can simplify input data while keeping specific information untouched. In this thesis, we focus on how digital topology, especially skeletons, can help material image analysis.The goal of a skeletonization process is to remove unnecessary information from an input, and provide a simplified object, called the skeleton, having the same characteristics than the original data. It is then possible to perform some computations on the skeleton and generalise their results to the original data. In the first part of this thesis, we propose some new tools for preserving, during skeletonization, important geometrical features of the original data, and obtain a skeleton with the same visual appearance than the input.In the second part, we present the cubical complex framework, where objects are no more made only of voxels. We propose in this framework new skeletonization algorithms, some of them preserving automatically the visual aspect of the input during the thinning process (no filtering parameter from the user is required). We then show how a skeleton, in the cubical complexes framework, can be decomposed into basic parts, and we show some applications of these algorithms to material image analysis and medical image analysis

.

Cette thèse s'inscrit dans la problématique de la reconstruction de surfaces à partir de nuages de points. Les récentes avancées faites dans le domaine de l'acquisition de formes 3D à l'aide de scanners donnent lieu à de nouveaux besoins en termes d'algorithmes de reconstruction. Il faut être capable de traiter de grands nuages de points bruités tout en donnant une représentation compacte de la surface reconstruite.<br>La surface est reconstruite comme le niveau zéro d'une fonction. Représenter une surface implicitement en utilisant des fonctions de base radiales (Radial Basis Functions) est devenu une approche standard ces dix dernières années. Une problématique intéressante est la réduction du nombre de fonctions de base pour obtenir une représentation la plus compacte possible et réduire les temps d'évaluation.<br>Réduire le nombre de fonctions de base revient à réduire le nombre de points (centres) sur lesquels elles sont centrées. L'objectif que l'on s'est fixé consiste à sélectionner un "petit" ensemble de centres, les plus pertinents possible. Pour réduire le nombre de centres tout en gardant un maximum d'information, nous nous sommes affranchis de la correspondance entre centres des fonctions et points de donnée, qui est imposée dans la quasi-totalité des approches RBF. Au contraire, nous avons décidé de placer les centres sur l'axe médian de l'ensemble des points de donnée et de montrer que ce choix était approprié.<br>Pour cela, nous avons utilisé les outils donnés par la géométrie algorithmique et approximé l'axe médian par un sous-ensemble des sommets du diagramme de Voronoi des points de donnée. Nous avons aussi proposé deux approches différentes qui échantillonnent de manière appropriée l'axe médian pour adapter le niveau de détail de la surface reconstruite au budget de centres alloué par l'utilisateur.

Étude des moyens de description et de manipulation des objets contenus dans des images binaires discrètes. Le calcul d'une ligne médiane, puis d'un graphe de la ligne médiane, aboutit a la représentation hiérarchisée de l'axe médian qui induit une analyse structurée de l'objet original. Différents procédés de manipulation de formes sont proposes et testés.

Cette thèse s'inscrit dans la problématique générale de l'inférence géométrique. Étant donné un objet qu'on ne connaît qu'à travers un échantillon fini, à partir de quelle qualité d'échantillonage peut-on estimer de manière fiable certaines de ses propriétés géométriques ou topologique? L'estimation de la topologie est maintenant un domaine assez mûr. La plupart des méthodes existantes sont fondées sur la notion de fonction distance. Nous utilisons cette approche pour estimer certaines notions de courbure dues à Federer, définies pour une classe assez générale d'objets non lisses. Nous introduisons une version approchée de ces courbures dont nous étudions la stabilité ainsi que calcul pratique dans le cas discret. Une version anisotrope de ces mesures de courbure permet en pratique d'estimer le lieu et la direction des arêtes vives d'une surface lisse par morceaux échantillonnée par un nuage de point. En chemin nous sommes amenés à étudier certaines propriétés de régularité de la fonction distance, comme le volume de l'axe médian. Un défaut des méthodes qui utilisent la fonction distance est leur extrême sensibilité aux points aberrants. Pour résoudre ce problème, nous sortons du cadre purement géométrique en remplaçant les compacts par des mesures de probabilité. Nous introduisons une notion de fonction distance à une mesure, robuste aux perturbations Wasserstein (et donc aux points aberrants) et qui partage certaines propriétés de régularité et de stabilité avec la fonction distance usuelle. Grâce à ces propriétés, il est possible d'étendre de nombreux théorèmes d'inférence géométrique à ce cadre.

Cette thèse s´inscrit dans la problématique de la reconstruction de surfaces à partir de nuages de points. Les récentes avancées faites dans le domaine de l´acquisition de formes 3D à l´aide de scanners donnent lieu à de nouveaux besoins en termes d´algorithmes de reconstruction. Il faut être capable de traiter de grands nuages de points bruités tout en donnant une représentation compacte de la surface reconstruite. La surface est reconstruite comme le niveau zéro d´une fonction. Représenter une surface implicitement en utilisant des fonctions de base radiales (Radial Basis Functions) est devenu une approche standard ces dix dernières années. Une problématique intéressante est la réduction du nombre de fonctions de base pour obtenir une représentation la plus compacte possible et réduire les temps d´évaluation. Réduire le nombre de fonctions de base revient à réduire le nombre de points (centres) sur lesquels elles sont centrées. L´objectif que l´on s´est fixé consiste à sélectionner un "petit" ensemble de centres, les plus pertinents possible. Pour réduire le nombre de centres tout en gardant un maximum d´information, nous nous sommes affranchis de la correspondance entre centres des fonctions et points de donnée, qui est imposée dans la quasi-totalité des approches RBF. Au contraire, nous avons décidé de placer les centres sur l´axe médian de l´ensemble des points de donnée et de montrer que ce choix était approprié. Pour cela, nous avons utilisé les outils donnés par la géométrie algorithmique et approximé l´axe médian par un sous-ensemble des sommets du diagramme de Voronoi des points de donnée. Nous avons aussi proposé deux approches diférentes qui échantillonnent de manière appropriée l´axe médian pour adapter le niveau de détail de la surface reconstruite au budget de centres alloué par l´utilisateur.

La tomodensitométrie est une technique très utile qui permet de mener avec succès des analyses non-invasives dans plusieurs types d'applications, par exemple médicales ou industrielles. L'analyse manuelle des structures d'intérêt présentes dans une image peut prendre beaucoup de temps, être laborieuse et parfois même impossible à faire en raison de sa complexité. C'est pour cela que dans cette thèse, nous proposons et développons des algorithmes nécessaires à cette analyse, basés sur la géométrie discrète et la topologie. Ces algorithmes peuvent servir dans de nombreuses applications, et en particulier au niveau de l'analyse quantitative automatique de l'arbre bronchique humain, sur la base d'images de tomodensitométrie. La première partie introduit les notions fondamentales de la topologie et de la géométrie discrètes utiles dans cette thèse. Ensuite, nous présentons le principe de méthodes utilisées dans de nombreuses applications : les algorithmes de squelettisation, de calcul de l'axe médian, les algorithmes de fermeture de tunnels et les estimateurs de tangentes. La deuxième partie présente les nouvelles méthodes que nous proposons et qui permettent de résoudre des problèmes particuliers. Nous avons introduit deux méthodes nouvelles de filtrage d'axe médian. La première, que nous appelons "hierarchical scale medial axis", est inspirée du "scale axis transform", sans les inconvénients qui sont propres à la méthode originale. La deuxième est une méthode nommée "discrete adaptive medial axis", où le paramètre de filtrage est adapté dynamiquement aux dimensions locales de l'objet. Dans cette partie, nous introduisons également des estimateurs de tangente nouveaux et efficaces, agissant sur des courbes discrètes tridimensionnelles, et que nous appelons "3Dlambda maximal segment tangent direction". Enfin, nous avons montré que la géométrie discrète et les algorithmes topologiques pouvaient être utiles dans le problème de l'analyse quantitative de l'arbre bronchique humain à partir d'images tomodensitométriques. Dans une chaîne de traitements de structure classique par rapport à l'état de l'art, nous avons appliqué des méthodes de topologie et de géométrie discrète afin de résoudre des problèmes particuliers dans chaque étape du processus de l'analyse quantitative. Nous proposons une méthode robuste pour segmenter l'arbre bronchique à partir d'un ensemble de données tomographiques (CT). La méthode est basée sur un algorithme de fermeture de tunnels qui est utilisé comme outil pour réparer des images CT abîmées par les erreurs d'acquisition. Nous avons aussi proposé un algorithme qui sert à créer un modèle artificiel d'arbre bronchique. Ce modèle est utilisé pour la validation des algorithmes présentés dans cette thèse. Ensuite nous comparons la qualité des différents algorithmes en utilisant un ensemble de test constitué de fantômes (informatiques) et d'un ensemble de données CT réelles. Nous montrons que les méthodes récemment présentées dans le cadre des complexes cubiques, combinées avec les méthodes présentées dans cette thèse, permettent de surmonter des problèmes indiqués par la littérature et peuvent être un bon fondement pour l'implémentation future des systèmes de quantification automatique des particularités de l'arbre bronchique / Computed tomography is a very useful technic which allow non-invasive diagnosis in many applications for example is used with success in industry and medicine. However, manual analysis of the interesting structures can be tedious and extremely time consuming, or even impossible due its complexity. Therefore in this thesis we study and develop discrete geometry and topology algorithms suitable for use in many practical applications, especially, in the problem of automatic quantitative analysis of the human airway trees based on computed tomography images. In the first part, we define basic notions used in discrete topology and geometry then we showed that several class of discrete methods like skeletonisation algorithms, medial axes, tunnels closing algorithms and tangent estimators, are widely used in several different practical application. The second part consist of a proposition and theory of a new methods for solving particular problems. We introduced two new medial axis filtering method. The hierarchical scale medial axis which is based on previously proposed scale axis transform, however, is free of drawbacks introduced in the previously proposed method and the discrete adaptive medial axis where the filtering parameter is dynamically adapted to the local size of the object. In this part we also introduced an efficient and parameter less new tangent estimators along three-dimensional discrete curves, called 3D maximal segment tangent direction. Finally, we showed that discrete geometry and topology algorithms can be useful in the problem of quantitative analysis of the human airway trees based on computed tomography images. According to proposed in the literature design of such system we applied discrete topology and geometry algorithms to solve particular problems at each step of the quantitative analysis process. First, we propose a robust method for segmenting airway tree from CT datasets. The method is based on the tunnel closing algorithm and is used as a tool to repair, damaged by acquisition errors, CT images. We also proposed an algorithm for creation of an artificial model of the bronchial tree and we used such model to validate algorithms presented in this work. Then, we compare the quality of different algorithms using set of experiments conducted on computer phantoms and real CT dataset. We show that recently proposed methods which works in cubical complex framework, together with methods introduced in this work can overcome problems reported in the literature and can be a good basis for the further implementation of the system for automatic quantification of bronchial tree properties