Le contexte est la géométrie discrète dans Zn. Il s'agit de décrire les courbes et surfaces discrètes composées de voxels: les définitions usuelles de droites et plans discrets épais se comportent mal quand on passe à des ensembles courbes. Comment garantir un bon comportement topologique, les connexités requises, dans une situation qui généralise les droites et plans discrets?Le calcul de données sur ces courbes, normales, tangentes, courbure, ou des fonctions plus générales, fait appel à des moyennes utilisant des masques. Une question est la pertinence théorique et pratique de ces masques. Une voie explorée, est le calcul de masques fondés sur la marche aléatoire. Une marche aléatoire partant d'un centre donné sur une courbe ou une surface discrète, permet d'affecter à chaque autre voxel un poids, le temps moyen de visite. Ce noyau permet de calculer des moyennes et par là, des dérivées. L'étude du comportement de ce processus de diffusion, a permis de retrouver des outils classiques de géométrie sur des surfaces maillées, et de fournir des estimateurs de tangente et de courbure performants. La diversité du champs d'applications de ce processus de diffusion a été mise en avant, retrouvant ainsi des méthodes classiques mais avec une base théorique identique.} motsclefs{Processus Markovien, Géométrie discrète, Estimateur tangentes, normales, courbure, Noyau de diffusion, Analyse d'images / The context of discrete geometry is in Zn. We propose to discribe discrete curves and surfaces composed of voxels: how to compute classical notions of analysis as tangent and normals ? Computation of data on discrete curves use average mask. A large amount of works proposed to study the pertinence of those masks. We propose to compute an average mask based on random walk. A random walk starting from a point of a curve or a surface, allow to give a weight, the time passed on each point. This kernel allow us to compute average and derivative. The studied of this digital process allow us to recover classical notions of geometry on meshes surfaces, and give accuracy estimator of tangent and curvature. We propose a large field of applications of this approach recovering classical tools using in transversal communauty of discrete geometry, with a same theorical base.

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. / Medical imaging is a principal data source for different applications. Even though medical images represent a lot of knowledge concerning the studied case, all the a priori knowledge known by the specialist remains implicit. Nevertheless this a priori knowledge has a major role in the interpretation and the use of the images. In this thesis, anatomical a priori knowledge is integrated in two medical applications. First, an automatic processing pipeline is proposed in order to detect, quantify and localize aneurysms on a segmented cerebrovascular tree. Centerlines of blood vessels are extracted and then used to automatically detect aneurysms and quantify them. To localize aneurysm, a matching is made between the cerebrovascular tree of the patient and a healthy one. The a priori knowledge, in this case, is represented by a graph. In the context of identifying sub-parts of an organ represented by a mesh, we propose the use of an anatomical ontology. This ontology is first enhanced by all information necessary to achieve the task of mesh segmenting. A new algorithm using this ontology to accomplish the segmentation task is then proposed.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. / In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented.

Les travaux présentés dans ce mémoire d'habilitation correspondent à des recherches effectuées depuis mon arrivée à Bordeaux en septembre 1999. J'ai choisi d'y présenter celles qui ont trait aux approches non-euclidiennes pour l'analyse d'image, la clé de voûte en étant la segmentation par modèle déformable. D'autres travaux plus amonts comme la topologie des espaces subdivisés et les invariants topologiques ou plus avals comme la reconstruction de colonne vertébrale en imagerie radiographique ne seront qu'évoqués. Ce choix, s'il peut sembler restrictif par rapport à une synthèse exhaustive de mes travaux, présente néanmoins une plus grande cohérence, à la fois dans les résultats et dans la démarche suivie. Ce mémoire montre notamment que l'utilisation d'autres géométries que la géométrie euclidienne classique, les géométries riemannienne et discrète, présente un intérêt certain en analyse d'images. Les modèles déformables constituent une technique classique de segmentation et de reconstruction en analyse d'image. Dans ce cadre, le problème de la segmentation est exprimé sous forme variationnelle, où la solution est idéalement le minimum d'une fonctionnelle. Pendant ma thèse, je m'étais déjà intéressé aux modèles hautement déformables, qui ont la double caractéristique de se baser uniquement sur l'information image pour repérer ses composantes et de pouvoir extraire des formes de complexité arbitraire. Pour assurer l'initialisation du modèle déformable, j'avais aussi mis en évidence les liens entre surfaces discrètes et triangulations d'isosurfaces. Ces premiers travaux expliquent le cheminement que j'ai suivi depuis dans mes recherches. En voulant attaquer deux problématiques fondamentales des modèles déformables (la minimisation du nombre de paramètres et de la complexité, la recherche d'une solution plus proche de l'optimale), j'ai été amené à changer l'espace de travail classique : l'espace euclidien. Le Chapitre 1 résume les approches classiques des modèles déformables, leurs différentes formulations, ainsi que les problématiques spécifiques auxquelles je me suis intéressé. Il montre enfin en quoi la formulation des modèles déformables dans des espaces non-euclidiens ouvre des pistes intéressantes pour les résoudre. La première voie explorée et résumée dans le Chapitre 2 est d'introduire une métrique riemannienne, variable dans l'espace et dépendante de l'information image locale. L'utilisation d'une autre métrique permet de déformer virtuellement l'espace afin de concentrer l'effort de calcul sur les zones d'intérêt de l'image. Une métrique judicieusement choisie permet d'adapter le nombre de paramètres du modèle déformable à la géométrie de la forme recherchée. Le modèle pourra ainsi se déplacer très vite sur les zones homogènes, extraire les parties droites, planes ou peu courbées avec très peu de paramètres, et conserver une grande précision sur les contours significatifs très courbés. Une telle approche conserve voire améliore la qualité et la robustesse de la segmentation, et minimise à la fois la complexité en temps et le nombre d'itérations avant convergence. La deuxième voie explorée parallèlement est le remplacement de l'espace euclidien continu par la grille cellulaire discrète. L'espace des formes possibles est alors fini tout en restant adapté à l'échantillonnage de l'image. D'autres techniques d'optimisation sont dès lors envisageables, la solution est bien définie et les problèmes numériques liés à la convergence d'un processus ne sont plus présents. Le Chapitre 3 décrit le principe suivi pour discrétiser le modèle déformable sur la grille cellulaire Z^n. Il présente les premiers résultats obtenus avec un algorithme de segmentation a posteriori. Il met aussi en évidence les problématiques soulevées par le passage au discret, problématiques qui se sont révélées être des voies de recherche par elles-mêmes. D'une part, il faut mettre au point des structures de données et des outils pour représenter les surfaces discrètes, pour mesurer leurs paramètres géométriques, et pour les faire évoluer. Le Chapitre 4 synthétise les travaux menés en ce sens. Cela nous conduit à proposer un nouveau formalisme algébrique pour représenter ces surfaces en dimension quelconque. Une étude précise des estimateurs géométriques discrets de tangente, de normale, de longueur et de courbure est ensuite conduite. Nous avons notamment évalué quantitativement leurs performances à basse échelle et proposé de nouveaux estimateurs pour les améliorer. Leurs propriétés asymptotiques lorsque la discrétisation est de plus en plus fine sont enfin discutées. D'autre part, le modèle déformable discret doit approcher au mieux le comportement du modèle déformable euclidien à résolution donnée mais aussi simuler de plus en plus exactement ce comportement lorsque la résolution augmente asymptotiquement. Les estimateurs géométriques discrets se doivent dès lors d'être convergents. En analysant finement la décomposition des courbes discrètes en segments discrets maximaux, nous avons obtenu des théorèmes de convergence ou de non-convergence de certains estimateurs. Le Chapitre 5 résume cette étude de la géométrie des courbes discrètes 2D et des propriétés géométriques asymptotiques du bord d'une discrétisation. Le mémoire se conclut par une synthèse des principaux résultats obtenus et montre les perspectives de recherche ouvertes par ces travaux.

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

Ce travail a pour but de proposer une méthode de modélisation et de segmentation du cortex en IRM qui soit adaptée aux utilisations en électroencéphalographie (EEG) et en magnétoencéphalographie (MEG). La complexité du cortex a nécéssité le développement de modèles mathématiques spécifiques. Les contributions de la thèse se situent donc à deux niveaux : au niveau théorique avec le développement d'un modèle discret à la fois volumique et surfacique reposant sur les complexes cellulaires, l'étude de ses propriétés, et le développement d'une méthodologie de segmentation prenant en compte ses caractéristiques ; et au niveau applicatif avec l'utilisation de ce modèle sur des IRM tridimensionnelles pour des applications en EEG et en MEG. L'étude des aspects algorithmiques, imposé par le volume de données, a également constitué une partie importante du travail.

La télédétection satellitaire est en mesure de fournir des informations globales sur les calottes polaires et d'en effectuer un suivi régulier dans le temps. Pour être facilement interprétées, afin d'en déduire les caractéristiques du manteau neigeux observé depuis l'espace (taille, forme de grains, rugosité de surface ... ), les données satellitaires doivent être validées et inversées à l'aide de paramétrisations simples. Il est alors indispensable de définir des paramètres robustes et simples de la taille et de la forme des grains de neige à partir de leur observation. Un moyen d'observation et de mesure est le traitement d'images gui a permis d' établir ces relations et qui a permis un traitement automatique d'un grand nombre de données indépendamment de l'observateur. Un autre problème glaciologique, est l'interprétation des données issues de l'analyse des gaz piégés dans les bulles d'air. Cette étude implique, en particulier, la datation de la glace dans le névé lors de la fermeture des pores, indispensable pour déterminer dans la glace profonde l'âge du gaz par rapport à la glace qui l'emprisonne. En effet la datation des gaz contenus dans les bulles des carottes de glace s'effectue à partir de l'âge de la glace, et par conséquent, elle néces ite la connaissance de la différence d'âge entre les gaz et la glace lors de la fermeture des pores. Ces datations nécessitent l'utilisation des modèles de densification, de fermeture des pores, et de diffusion des gaz dans le névé. Les carottages réalisés dans les régions centrales de l'Antarctique et du Groenland permettent d'obtenir des données expérimentales essentielles pour caractériser le névé polaire. Le traitement automatique des images issues de ces données a fourni les paramètres de structure introduits dans ces modèles. Un autre aspect étudié au Laboratoire de Glaciologie est l'augmentation de la taille moyenne des cristaux de glace avec la profondeur ou l'âge de la glace. Les analyses des lames minces de glace permettant de déterminer ces lois de grossissement des grains ont été réalisées jusgu'à présent manuellement. Le traitement automatique d' images 2D a permis d' analyser les lois de grossissement des grains sur d' autres sites et a permis d' étudier les microstructures en terme d' évolution des distributions de taille et en terme d'évolution de la topologie des grains.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d'apporter des réponses. On s'intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l'image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l'unicité de cette reconstruction ; 3) l'estimation d'informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d'aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d'ensembles ayant des propriétés de convexité qu'on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d'ensembles, nous montrons qu'elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d'ensemblesconvexes par quadrants qui, si l'unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l'unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d'estimer, à partir d'une seule projection, la surface d'un ensemble 2D. Concernant l'estimation du périmètre d'un ensemble 2D, en considérant les projections par une deuxième source d'un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l'objet projeté.

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d'apporter des réponses. On s'intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l'image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l'unicité de cette reconstruction ; 3) l'estimation d'informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d'aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d'ensembles ayant des propriétés de convexité qu'on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d'ensembles, nous montrons qu'elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d'ensemblesconvexes par quadrants qui, si l'unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l'unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d'estimer, à partir d'une seule projection, la surface d'un ensemble 2D. Concernant l'estimation du périmètre d'un ensemble 2D, en considérant les projections par une deuxième source d'un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l'objet projeté.

Ces travaux s'inscrivent dans la thématique de l'inférence géométrique dont le but est de répondre au problème suivant : étant donné un objet géométrique dont on ne connaît qu'une approximation, peut-on estimer de manière robuste ses propriétés? On se place dans cette thèse dans le cas où l'approximation est un nuage de points ou un ensemble digital dans un espace euclidien de dimension finie. On montre tout d'abord un résultat de stabilité d'un estimateur de normale basé sur l'analyse en composante principale, ainsi qu'un résultat de convergence multigrille d'un estimateur du Voronoi Covariance Measure qui utilise des matrices de covariance de cellules de Voronoi. Ces deux résultats, comme la plupart des résultats en inférence géométrique, utilisent la stabilité de la fonction distance à un compact. Cependant, la présence d'un seul point aberrant suffit pour que les hypothèses des résultats de stabilité ne soient pas satisfaites. La distance à une mesure est une fonction distance généralisée introduite récemment qui est robuste aux points aberrants. Dans ce travail, on généralise le Voronoi Covariance Measure à des fonctions distances généralisées et on montre que cet estimateur appliqué à la distance à une mesure est robuste aux points aberrants. On en déduit en particulier un estimateur de normale très robuste. On présente également des résultats expérimentaux qui montrent une forte robustesse des estimations de normales, courbures, directions de courbure et arêtes vives. Ces résultats sont comparés favorablement à l'état de l'art. / The purpose of geometric inference is to answer the following problem : Given a geometric object that is only known through an approximation, can we get a robust estimation of its properties? We consider in this thesis the case where the approximation is a point cloud or a digital set in a finite dimensional Euclidean space. We first show a stability result for a normal estimator based on the principal component analysis, as well as a result of multigrid convergence of an estimator of the Voronoi covariance measure, which uses covariance matrices of Voronoi cells. As most of geometric inference results, these two last results use the robustness of the distance function to a compact set. However, the presence of a single outlier is sufficient to make the assumptions of these results not satisfied. The distance to a measure is a generalized distance function introduced recently, that is robust to outliers. In this work, we generalize the Voronoi Covariance Measure to generalized distance functions and we show that this estimator applied to the distance to a measure is robust to outliers. We deduce a very robust normal estimator. We present experiments showing the robustness of our approach for normals, curvatures, curvature directions and sharp features estimation. These results are favorably compared to the state of the art.