Cette thèse décrit l'exploitation d'approches géométriques pour résoudre le probleme de segmentation d'images, ainsi que le probleme de détection d'événements en imagerie multi-sources. La structure géométrique utilisée est le diagramme de Voronoi ponctuel. Nous abordons tout d'abord une première approche de segmentation d'images en polygones de Voronoi dont l'algorithme fonctionne en trois étapes: une phase d'initialisation, une phrase de partition et une phase de fusion. Ce processus de segmentation est utilise pour détecter les différences entre des images acquises dans différents domaines de radiometrie. Nous présentons une seconde technique de segmentation fondée sur le processus de coopération d'un détecteur de frontières et d'un détecteur de régions. Cette approche utilise le diagramme de voronoi généralisé pour générer une partition initiale dont les frontières des régions s'appuient sur les contours détectés initialement. Pour réaliser cette segmentation nous avons propose un algorithme de calcul d'une approximation du diagramme de Voronoi généralisé en utilisant le diagramme de Voronoi ponctuel

L'influence des hétérogénéités microstructurales sur le comportement d'un matériau est devenue une problématique industrielle de première importance, cet état de fait explique l'engouement actuel pour la prise en compte de ces hétérogénéités dans le cadre de la modélisation numérique. Ainsi, de nombreuses méthodes pour représenter de manière digitale un matériau virtuel statistiquement équivalent à la microstructure réelle et pour connecter cette représentation à des calculs éléments finis se sont développées ces dernières années. Les travaux réalisés durant cette thèse s'inscrivent en grande partie dans cette thématique. En effet, un générateur de microstructures virtuelles permettant de générer à la fois des microstructures polyédriques ou sphériques a été développé. Ce générateur est basé sur les diagrammes de Laguerre et une méthode frontale de remplissage, une approche level-set pour l'immersion de ces microstructures dans un maillage éléments finis et une technique d'adaptation anisotrope de maillage pour assurer une grande précision lors de cette immersion mais également lors de la réalisation de simulations éléments finis sur ces microstructures. La capacité de ces outils à respecter des données statistiques concernant les microstructures considérées est assurée par le couplage d'une méthode frontale à une méthode d'optimisation des défauts locaux selon la nature de la microstructure considérée. Une technique de coloration de graphe est également appliquée afin de limiter le nombre de fonctions level-set nécessaires à l'adaptation de maillage. En outre, le coût élevé d'une simulation micro-macro entièrement couplée peut-être significativement réduite en limitant les calculs à une analyse entièrement découplée. Dans ce contexte, la réponse d'un Volume Élémentaire Représentatif (VER) soumis à des conditions aux limites représentatives de ce que subit la matière en un point précis d'un calcul macroscopique reste l'approche la plus complète à l'heure actuelle. Dans le cadre de ce travail, nous nous sommes intéressés à deux types de VER pour deux applications différentes : la déformation de VERs de mousses polyédriques élastiques et le calcul du tenseur de perméabilité pour des VERs composés de fibres cylindriques hétérogènes mais monodirectionnelles. Plus précisément, pour la première de ces applications, des cas de compression biaxiale de mousses élastiques à cellules fermées en nids d'abeille ou irrégulières sont modélisés comme un problème d'interaction fluide structure (IFS) entre un fluide compressible (l'air à l'intérieur des cellules) et un solide élastique compressible (le squelette de la mousse). Une formulation monolithique est utilisée pour résoudre ce problème en regroupant les équations d'états régissant le solide et le fluide en un seul jeu d'équations résolu sur un maillage unique discrétisant les deux phases. Une telle stratégie donne lieu, pour la partie solide, à l'apparition d'un tenseur d'extra-contrainte dans les équations de Navier-Stokes. Ces équations sont ensuite résolues par une méthode éléments finis mixte avec une interpolation de type P1+/P1. Concernant la deuxième application, des écoulements dans des milieux fibreux sont simulés en considérant les fibres comme rigides. Ici encore, une formulation monolithique est adoptée. Ainsi, les équations de Stokes sont résolues sur l'ensemble du domaine de calcul en utilisant une méthode de pénalisation. Par homogénéisation, la loi de Darcy est utilisée pour obtenir le tenseur de perméabilité.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d'éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d’éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres / Depending on the specific method used to build a 3D structural model, and on the exact purpose of this model, its mesh must be adapted so that it enforces criteria on element types, maximum number of elements, and mesh quality. Meshing methods developed for applications others than geomodeling forbid any modification of the input model, that may be desirable in geomodeling to better control the number of elements in the final mesh and their quality. The objective of this thesis is to develop meshing methods that fulfill this requirement to better manage the geometrical complexity of B-Rep geological structural models. An analysis of the sources of geometrical complexity in those models is first proposed. The introduced measures are a first step toward the definition of tools allowing objective comparisons of structural models and permit to characterize the model zones that are more complicated to mesh. We then introduce two original meshing methods based on Voronoi diagrams: the first for surface remeshing, the second for hybrid gridding. The key ideas of these methods are identical: (1) the use of a centroidal Voronoi optimization to have a globally controlled number of elements of good quality, and (2) combinatorial considerations to locally build the final mesh while sometimes modifying the initial model. The surface remeshing method is automatic and permits to simplify a model at a given resolution. The gridding method generates a hybrid volumetric mesh. Prisms and pyramids fill the very thin layers of the model while the remaining regions are filled with tetrahedra

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux « problèmes de placement de formes », thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes. / Computational geometry is an active branch of computer science whose goal is the design of efficient algorithms solving geometric problems. Such algorithms are useful in domains like engineering, industry and multimedia. In order to be efficient, algorithms often use special data structures.In this thesis we focused on such a structure: the Voronoi diagram. We proposed a new generalized diagram. We have proceeded by extending the empty disk predicate (satisfied by every Voronoi region) to an arbitrary union of disks. We have analyzed the new plane regions based on the extended predicate, and we designed algorithms for computing them.Then, we have considered another topic, which is related to the first one: shape placement problems. Such problems have been studied repeatedly by researchers in computational geometry. We introduced new notations along with a global framework for such problems. We proposed, for the first time a generic method, which is able to solve various placement problems using a single algorithm.Thus, our work extend the scope of Voronoi based data structures. It also simplifies the practical usage of placement techniques by unifying the associated definitions and algorithms.

Étant donné un ensemble S de points du plan, une triangulation de S est une décomposition de l'enveloppe convexe de S en triangles dont les sommets sont les points de S. Une triangulation de S est dite de Delaunay si le cercle circonscrit à chaque triangle ne contient aucun point de S en son intérieur. Dans cette thèse, nous étudions une généralisation de ces notions à un ensemble S de segments disjoints du plan.<br />Nous commençons par définir une nouvelle famille de diagrammes, appelés triangulations de segments. Nous étudions leurs propriétés géométriques et topologiques et nous donnons un algorithme pour construire efficacement une telle triangulation.<br />Nous généralisons ensuite la notion de triangulation de Delaunay aux triangulations de segments et nous mettons en évidence la dualité avec le diagramme de Voronoï de segments.<br />Nous étendons également la légalité des arêtes au cas des triangulations de segments en définissant, d'une part, la légalité géométrique qui caractérise la triangulation de Delaunay de segments parmi l'ensemble de toutes les triangulations de segments possibles et, d'autre part, la légalité topologique qui caractérise les triangulations de segments qui ont la même topologie que celle de Delaunay.<br />Enfin, nous décrivons un algorithme de « flip » qui transforme toute triangulation de segments en une triangulation qui a la même topologie que celle de Delaunay. À l'aide de fonctions localement convexes, nous démontrons que la suite de triangulations construites par cet algorithme converge vers celle de Delaunay et nous prouvons qu'une triangulation de segments qui a la même topologie que celle de Delaunay est obtenue après un nombre fini d'étapes.

.

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.

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux " problèmes de placement de formes ", thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes.

L’autonomie d’un agent mobile se définit par sa capacité à naviguer dans un environnement sans intervention humaine. Cette tâche s’avère très demandée pour les robots d’assistance à la personne. C’est pour cela que notre contribution s’est portée en particulier sur l’instrumentation et l’augmentation de l’autonomie d’un fauteuil roulant pour les personnes à mobilité réduite. L’objectif de ce travail est de concevoir des lois de commande qui permettent à un robot de naviguer en temps réel et en toute autonomie dans un environnement inconnu. Un cadre de perception virtuelle unifié est introduit et permet de projeter l’espace navigable obtenu par des observations éventuellement multiples. Une approche de navigation autonome et sûre a été conçue pour se déplacer dans un environnement peu encombré dont la structure peut être assimilée à un couloir (lignes au sol, murs, délimitation herbes, routes...). La problématique a été résolue en utilisant le formalisme de l’asservissement visuel. Les caractéristiques visuelles utilisées dans la loi de commande ont été construites à partir de la représentation virtuelle (à savoir la position du point de fuite et l’orientation de la ligne médiane du couloir). Pour assurer une navigation sûre et lisse, même lorsque ces paramètres ne peuvent pas être extraits, nous avons conçu un observateur d’état pour estimer les caractéristiques visuelles dans le but de maintenir la commande fonctionnelle du robot. Cette approche permet de faire naviguer un robot mobile dans un couloir même en cas de défaillance sensorielle (données non fiables) et/ou de perte de mesure. La première contribution de cette thèse a été étendue en traitant tout type d’environnement encombré statique ou dynamique. Cela a été réalisé en utilisant le diagramme de Voronoï. Le diagramme de Voronoï généralisé, également appelé squelette, est une représentation puissante de l’environnement. Il définit un ensemble de chemins à la distance maximale des obstacles. Dans ce travail, une approche d’asservissement visuel basée sur le squelette extrait en temps réel était proposée pour une navigation autonome et sûre des robots mobiles. La commande est basée sur une approximation du DVG local en utilisant le Delta Medial axis, un algorithme de squelettisation rapide et robuste. Ce dernier produit un squelette filtré de l’espace libre entourant le robot en utilisant un paramètre qui prend en compte la taille du robot. Cette approche peut faire face aux bruits de mesure au niveau de la perception et au niveau de la commande à cause des glissement des roues. C’est pour cela que nous avons conçu une approche d’asservissement visuel sur une prédiction d’une linéarisation du DVG. Une analyse complète a été réalisée pour montrer la stabilité des lois de commandes proposées. Des simulations et des tests expérimentaux valident l’approche proposée. / The autonomy of a mobile agent is defined by its ability to navigate in an environment without human intervention. This task is very required for personal assistance robots. That’s why our contribution has been particularly focused on instrumentation and increasing the autonomy of a wheelchair for reduced mobility peaple. The objective of this work is to design control laws that allow a robot to navigate in real time and independently in an unknown environment. A unified virtual perception framework is introduced and allows to project the navigable space obtained by possibly multiple observations. First we designed an autonomous and safe navigation approach in environment whose structure can be assimilated to a corridor (lines on the ground, walls, delimitation of grasses, roads ...). We have solved this problem by using the formalism of visual servoing. The visual characteristics used in the control law were constructed from the virtual representation (ie the position of the vanishing point and the orientation of the center line of the corridor). To ensure safe and smooth navigation, even when these parameters can not be extracted, we have designed a finite-time state observer to estimate the visual characteristics in order to maintain the robot’s control efficient. This approach let a mobile robot navigate in a corridor even in in the case of sensory failure (unreliable data) and/or loss of measurement. We have extended the first contribution of this work with dealing with any type of static or dynamic environment. This was done using the Voronoi diagram. The Generalized Voronoi Diagram (GVD), also named skeleton, is a powerful environment representation, since, among other reasons, it defines a set of paths at maximal distance from the obstacles. In this work, a real time skeleton based visual servoing approach is proposed for a safe autonomous navigation of mobile robots. The control is based on an approximation of the local GVD using the Delta Medial Axis, a fast and robust skeletonization algorithm. The latter produces a filtered skeleton of the free space surrounding the robot using a pruning parameter that takes into account the robot size. This approach can cope with measurement noises at the perception and control with the wheel slip. This is why we have designed a visual servoing approach on a prediction of a GVD linearization. A complete analysis was performed to show the stability of the proposed control laws. Simulations and experimental tests validate the proposed approach.