Les techniques de segmentation de graphe sont souvent utilisées en traitement d'images puisque ces dernières peuvent être vues comme des graphes valués. Dans cette thèse, nous montrons des liens existant entre plusieurs paradigmes de segmentation de graphes valués. Nous présentons tout d'abord différentes définitions de ligne de partage des eaux et sélectionnons celle dont le cadre permet la comparaison avec des forêts couvrantes particulières. Nous montrons qu'une telle ligne de partage des eaux relative à des marqueurs arbitraires est équivalente à une coupe induite par une forêt couvrante de chemins de moindre altitude. Ensuite, les coupes induites par des forêts couvrantes de poids minimum sont démontrées comme étant des cas particuliers ayant l'avantage d'éviter certaines segmentations non souhaitées. Enfin, nous montrons qu'une coupe minimale coïncide avec une coupe induite par une forêt couvrante de poids maximum pour certaines fonctions de poids particulières. Dans une seconde partie, nous présentons deux applications utilisant la segmentation de graphe : la renaissance d'images et le mélange de textures pour la reconstruction 3D

Ce travail a pour but de concevoir des outils d'analyse d'image 3D de matériaux poreux, obtenues par microtomographie à rayons X, afin de caractériser géométriquement la structure micronique des pores et de mettre en évidence le lien entre microgéométrie et propriétés de transport macroscopiques. Partant d'une image segmentée, une séquence complète de traitements (filtrage d'artefacts, squelettisation, LPE, etc.) est proposée pour positionner et délimiter les pores. Une comparaison aux techniques existantes est faite, et une méthodologie qualifiant la robustesse des procédures est présentée. Cette décomposition est utilisée, premièrement pour extraire des descripteurs géométriques de la microstructure porale qui sont examinés en rapport avec la perméabilité intrinsèque ; deuxièmement pour aider à la construction d'un réseau de pores permettant d'effectuer des simulations numériques.

La segmentation d'images par la morphologie mathématique est une méthodologie basée sur les concepts de ligne de partage des eaux et de modification de l'homotopie. Ces deux outils sont construits à partir de transformations morphologiques élémentaires présentées dans la première partie de ce mémoire. Ces transformations élémentaires sont les transformations morphologiques sur images à teintes de gris et en particulier les opérations d'amincissement et d'épaississement, ainsi que les transformées géodésiques. Ces outils de base permettent l'élaboration de transformations plus sophistiqués. Parmi elles, le gradient morphologique et sa régularisation, opérateursimportants dans la segmentation d'images de gris et la ligne de partage des eaux. Après avoir introduit cette notion et mis en lumière ces liens avec les opérateurs géodésiques et les épaississements homotopiques, divers algorithmes permettant de la réaliser sont présentés par le biais du squelette de fonction et surtout au moyen d'une représentation des images à teintes de gris sous forme d'un graphe de fléchage.<br />La deuxième partie est consacrée à l'usage de ces outils. On montre en particulier comment le concept de marquage des régions à segmenter permet d'obtenir, en combinant la modification d'homotopie et la ligne de partage des eaux, une segmentation de l'image de bonne qualité. L'usage de ces outils est illustré dans le cas de segmentations plus complexes. On introduit alors une hiérarchisation de l'image, toujours basée sur la ligne de partage des eaux, et on montre comment cette hiérarchie permet la segmentation de certaines scènes où le marquage est moins évident. Un autre exemple, montrant la difficulté du marquage mais aussi les avantages de ce concept est également présenté.

La notion de clivage formalise l'idée d'ensemble frontiére dans un graphe. Fusionner deux régions, comme le requièrent certaines méthodes de segmentation d'images, pose des diffIcultés. Nous introduisons quatre classes de graphes (de fusion) dans lesquels ces diffIcultés sont progressivement supprimées. Nous montrons que l'une de ces classes est celle pour laquelle tout clivage est mince. Nous introduisons une relation d'adjacence, appelée grille de fusion parfaite, dans laquelle deux régions voisines peuvent être fusionnées, en préservant toutes les autres régions.<br /><br />La ligne de partage des eaux topologique (LPE) étend la notion de clivage aux graphes dont les sommets sont valués et permet de segmenter une image. Nous étendons les propriétés des clivages dans les graphes de fusion aux cas des fonctions et proposons un algorithme de LPE<br />monotone et linéaire dans les grilles de fusion parfaites. Grâce à la notion de graphe d'arêtes, les propriétés des LPE dans les grilles de fusion parfaites s'étendent aux graphes à arêtes valuées.<br /><br />Nous étudions en profondeur les LPE dans les graphes à arêtes valuées. Les LPE peuvent y être définies en suivant l'idée intuitive de gouttes d'eau s'écoulant sur un relief topographique. Nous établissons aussi bien la consistance que l'optimalité de cette définition. De plus, nous proposons deux algorithmes linéaires qui, à notre connaissance, sont les plus efficaces pour le calcul des LPE.<br /><br />En nous reposant sur ces résultats théoriques, nous proposons une méthode et développons un logiciel pour la segmentation du ventricule gauche dans des images cardiaques 3D+t par résonance magnétique. La méthode est quantitativement et qualitativement validée par comparaison avec des segmentations manuelles tracées par deux experts cardiologues.

Ce travail a pour but de concevoir des outils d'analyse d'image 3D de matériaux poreux, obtenues par microtomographie à rayons X, afin de caractériser géométriquement la structure micronique des pores et de mettre en évidence le lien entre microgéométrie et propriétés de transport macroscopiques. Partant d'une image segmentée, une séquence complète de traitements (filtrage d'artefacts, squelettisation, LPE, etc.) est proposée pour positionner et délimiter les pores. Une comparaison aux techniques existantes est faite, et une méthodologie qualifiant la robustesse des procédures est présentée. Cette décomposition est utilisée, premièrement pour extraire des descripteurs géométriques de la microstructure porale qui sont examinés en rapport avec la perméabilité intrinsèque ; deuxièmement pour aider à la construction d’un réseau de pores permettant d’effectuer des simulations numériques. / The objective of this work is to develop 3D image analysis tools to study the micronic pore structure of porous materials, obtained by X-ray microtomography, and study the relation between microgeometry and macroscopic transport properties. From a binarised image of the pore space, a complete sequence of processing (artefact filtration, skeletonisation, watershed, etc. ) is proposed for positioning and delimiting the pores. A comparison with available methods is performed, and a methodology to qualify the robustness of these processes is presented. The decomposition is used, firstly for extracting geometric parameters of the porous microstructure and studying the relation with intrinsic permeability; secondly to produce a simplified pore network on which to perform numerical simulations.

Cette thèse s’inscrit dans le cadre de l’évolution des Systèmes d’Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s’expriment de manière globale et transversale. Dans un contexte ou l’information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d’outil d’aide a la décision n’a jamais été aussi fort. Cette étude s’attache tout particulièrement au cadre de la résolution de problématiques liées à l’eau et l’environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d’ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d’accumulation. A cette fin nous introduisons une technique de calcul parallèle d’une forêt d’arbres couvrants minimums représentant le parcours de l’eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L’étude se poursuit par la description d’un algorithme parallèle pour le calcul très couteux des flots d’accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d’étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite. / My thesis is part of the development of Geographic Information Systems (GIS) and their ability to respond to environmental challenges that are expressed in a global and transversal way. We consider a context in which geographical information is growing, in addition the amount of data available continues to grow. Therefore, the need a tool for decision support has never been stronger. This study aim to solve problems related to water and the environment when the data become too large for sequential computing. The main objective of the thesis proposes a platform for distributed computing on a cluster of computers that parallelizes the watershed computing of major rivers and the determination of the flow accumulation. The idea is based on the construction of a minimal spanning tree, via a hierarchy of graphs, modeling the water route on the DEM toward the ocean. The technique begins from computing catchment basins that are set of pixels for which a drop of water will end the same local minimum. After that, a hierarchy of basins is computed in order to give the catchment basins of the rivers in the DEM. The study continues with a description of a parallel algorithm for computing the global flow accumulation for automatic drainage network extraction in large digital elevation models. Finally, the thesis presents a version ≪out-of-core≫ of our parallel algorithms to extend the scope of our work in clusters of size small that cannot load into memory the entire treated DEM.

L’objectif de ces travaux est de fournir une méthode de segmentation sémantique qui soit générale et automatique, c’est-à-dire une méthode qui puisse s’adapter par elle-même à tout type de base d’images, afin d’être utilisée directement par les non experts en traitement d’image, comme les biologistes par exemple. Pour cela, nous proposons d’utiliser la classification de pixel, une approche classique d’apprentissage supervisé, où l’objectif est d’attribuer à chaque pixel l’étiquette de l’objet auquel il appartient. Les descripteurs des pixels à classer sont souvent calculés sur des supports fixes, par exemple une fenêtre centrée sur chaque pixel, ce qui conduit à des erreurs de classification, notamment au niveau des contours d’objets. Nous nous intéressons donc à un autre support, plus large que le pixel et s’adaptant au contenu de l’image: le superpixel. Les superpixels sont des régions homogènes et plutôt régulières, issues d’une segmentation de bas niveau. Nous proposons une nouvelle façon de les générer grâce à la ligne de partage des eaux, les waterpixels, méthode rapide, performante et facile à prendre en main par l’utilisateur. Ces superpixels sont ensuite utilisés dans la chaîne de classification, soit à la place des pixels à classer, soit comme support pertinent pour calculer les descripteurs, appelés SAF (Superpixel-Adaptive Features). Cette seconde approche constitue une méthode générale de segmentation dont la pertinence est vérifiée qualitativement et quantitativement sur trois bases d’images provenant du milieu biomédical. / In this work, we would like to provide a general method for automatic semantic segmentation, which could adapt itself to any image database in order to be directly used by non-experts in image analysis (such as biologists). To address this problem, we first propose to use pixel classification, a classic approach based on supervised learning, where the aim is to assign to each pixel the label of the object it belongs to. Features describing each pixel properties, and which are used to determine the class label, are often computed on a fixed-shape support (such as a centered window), which leads, in particular, to misclassifcations on object contours. Therefore, we consider another support which is wider than the pixel itself and adapts to the image content: the superpixel. Superpixels are homogeneous and rather regular regions resulting from a low-level segmentation. We propose a new superpixel generation method based on the watershed, the waterpixels, which are efficient, fast to compute and easy to handle by the user. They are then inserted in the classification pipeline, either in replacement of pixels to be classified, or as pertinent supports to compute the features, called Superpixel-Adaptive Features (SAF). This second approach constitutes a general segmentation method whose pertinence is qualitatively and quantitatively highlighted on three databases from the biological field.

Notre travail s'inscrit dans le cadre de la parallélisation d’algorithmes de calcul de la Ligne de Partage des Eaux (LPE) en particulier la LPE d’arêtes qui est une notion de la LPE introduite dans le cadre des Graphes à Arêtes Valuées. Nous avons élaboré un état d'art sur les algorithmes séquentiels de calcul de la LPE afin de motiver le choix de l'algorithme qui fait l'objet de notre étude qui est l'algorithme de calcul de noyau par M-bord. L'objectif majeur de cette thèse est de paralléliser cet algorithme afin de réduire son temps de calcul. En premier lieu, nous avons présenté les travaux qui se sont intéressés à la parallélisation des différentes variantes de la LPE et ce afin de dégager les problématiques que soulèvent cette tâche et les solutions adéquates à notre contexte. Dans un second lieu, nous avons montré que malgré la localité de l'opération de base de cet algorithme qui est l’abaissement de la valeur de certaines arêtes nommées arêtes M-bord, son exécution parallèle se trouve pénaliser par un problème de dépendance de données, en particulier au niveau des arêtes M-bord qui ont un sommet non minimum commun. Dans ce contexte, nous avons proposé trois stratégies de parallélisation de cet algorithme visant à résoudre ce problème de dépendance de données. La première stratégie consiste à diviser le graphe de départ en des bandes appelées partitions, et les traiter en parallèle sur P processeurs. La deuxième stratégie consiste à diviser les arêtes du graphe de départ en alternance en des sous-ensembles d’arêtes indépendantes. La troisième stratégie consiste à examiner les sommets au lieu des arêtes du graphe initial tout en préservant le paradigme d’amincissement sur lequel est basé l’algorithme séquentiel initial. Par conséquent, l’ensemble des sommets non-minima adjacents aux sommets minima sont traités en parallèle. En dernier lieu, nous avons étudié la parallélisation d'une technique de segmentation basée sur l'algorithme de calcul de noyau par M-bord. Cette technique comprend les étapes suivantes : la recherche des minima régionaux, la pondération des sommets et le calcul des sommets minima et enfin calcul du noyau par M-bord. A cet égard, nous avons commencé par faire une étude relative à la dépendance des données des différentes étapes qui la constituent et nous avons proposé des algorithmes parallèles pour chacune d'entre elles. Afin d'évaluer nos contributions, nous avons implémenté les différents algorithmes parallèles proposés dans le cadre de cette thèse sur une architecture multi-cœurs à mémoire partagée. Les résultats obtenus ont montré des gains en termes de temps d’exécution. Ce gain est traduit par des facteurs d’accélération qui augmentent avec le nombre de processeurs et ce quel que soit la taille des images à segmenter / Our work is a contribution of the parallelization of the Watershed Transform in particular the Watershed cuts which are a notion of watershed introduced in the framework of Edge Weighted Graphs. We have developed a state of art on the sequential watershed algorithms in order to motivate the choice of the algorithm that is the subject of our study, which is the M-border Kernel algorithm. The main objective of this thesis is to parallelize this algorithm in order to reduce its running time. First, we presented a review on the works that have treated the parallelization of the different types of Watershed in order to identify the issues raised by this task and the appropriate solutions to our context. In a second place, we have shown that despite the locality of the basic operation of this algorithm which is the lowering of some edges named the M-border edges; its parallel execution raises a data dependency problem, especially at the M-border edges which have a common non-minimum vertex. In this context, we have proposed three strategies of parallelization of this algorithm that solve this problematic: the first strategy consists of dividing the initial graph into bands called partitions processed in parallel by P processors. The second strategy is to divide the edges of the initial graph alternately into subsets of independent edges. The third strategy consists in examining the vertices instead of the edges of the initial graph while preserving the thinning paradigm on which the sequential algorithm is based. Therefore, the set of non-minima vertices adjacent to the minima ones are processed in parallel. Finally, we studied the parallelization of a segmentation technique based on the M-border kernel algorithm. This technique consists of three main steps which are: regional minima detection, vertices valuation and M-border kernel computation. For this purpose, we began by studying the data dependency of the different stages of this technique and we proposed parallel algorithms for each one of them. In order to evaluate our contributions, we implemented the parallel algorithms proposed in this thesis, on a shared memory multi-core architecture. The results obtained showed a notable gain in terms of execution time. This gain is translated by speedup factors that increase with the number of processors whatever is the resolution of the input images

Cette thèse s'inscrit dans le cadre de l'évolution des Systèmes d'Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s'expriment de manière globale et transversale. Dans un contexte ou l'information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d'outil d'aide a la décision n'a jamais été aussi fort. Cette étude s'attache tout particulièrement au cadre de la résolution de problématiques liées à l'eau et l'environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d'ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d'accumulation. A cette fin nous introduisons une technique de calcul parallèle d'une forêt d'arbres couvrants minimums représentant le parcours de l'eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L'étude se poursuit par la description d'un algorithme parallèle pour le calcul très couteux des flots d'accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d'étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite.

La fusion d’informations a été largement étudiée dans le domaine de l’intelligence artificielle. Une information est en général considérée comme imparfaite. Par conséquent, la combinaison de plusieurs sources d’informations (éventuellement hétérogènes) peut conduire à une information plus globale et complète. Dans le domaine de la fusion on distingue généralement les approches probabilistes et non probabilistes dont fait partie la théorie de l’évidence, développée dans les années 70. Cette méthode permet de représenter à la fois, l’incertitude et l’imprécision de l’information, par l’attribution de fonctions de masses qui s’appliquent non pas à une seule hypothèse (ce qui est le cas le plus courant pour les méthodes probabilistes) mais à un ensemble d’hypothèses. Les travaux présentés dans cette thèse concernent la fusion d’informations pour la segmentation d’images.Pour développer cette méthode nous sommes partis de l’algorithme de la « Ligne de Partage des Eaux » (LPE) qui est un des plus utilisés en détection de contours. Intuitivement le principe de la LPE est de considérer l’image comme un relief topographique où la hauteur d’un point correspond à son niveau de gris. On suppose alors que ce relief se remplit d’eau par des sources placées au niveau des minima locaux de l’image, formant ainsi des bassins versants. Les LPE sont alors les barrages construits pour empêcher les eaux provenant de différents bassins de se mélanger. Un problème de cette méthode de détection de contours est que la LPE directement appliquée sur l’image engendre une sur-segmentation, car chaque minimum local engendre une région. Meyer et Beucher ont proposé de résoudre cette question en spécifiant un ensemble de marqueurs qui seront les seules sources d’inondation du relief. L'extraction automatique des marqueurs à partir des images ne conduit pas toujours à un résultat satisfaisant, en particulier dans le cas d'images complexes. Plusieurs méthodes ont été proposées pour déterminer automatiquement ces marqueurs.Nous nous sommes en particulier intéressés à l’approche stochastique d’Angulo et Jeulin qui estiment une fonction de densité de probabilité (fdp) d'un contour (LPE) après M simulations de la segmentation LPE classique. N marqueurs sont choisis aléatoirement pour chaque réalisation. Par conséquent, une valeur de fdp élevée est attribuée aux points de contours correspondant aux fortes réalisations. Mais la décision d’appartenance d’un point à la « classe contour » reste dépendante d’une valeur de seuil. Un résultat unique ne peut donc être obtenu.Pour augmenter la robustesse de cette méthode et l’unicité de sa réponse, nous proposons de combiner des informations grâce à la théorie de l’évidence.La LPE se calcule généralement à partir de l’image gradient, dérivée du premier ordre, qui donne une information globale sur les contours dans l’image. Alors que la matrice Hessienne, matrice des dérivées d’ordre secondaire, donne une information plus locale sur les contours. Notre objectif est donc de combiner ces deux informations de nature complémentaire en utilisant la théorie de l’évidence. Les différentes versions de la fusion sont testées sur des images réelles de la base de données Berkeley. Les résultats sont comparés avec cinq segmentations manuelles fournies, en tant que vérités terrain, avec cette base de données. La qualité des segmentations obtenues par nos méthodes sont fondées sur différentes mesures: l’uniformité, la précision, l’exactitude, la spécificité, la sensibilité ainsi que la distance métrique de Hausdorff / Information fusion has been widely studied in the field of artificial intelligence. Information is generally considered imperfect. Therefore, the combination of several sources of information (possibly heterogeneous) can lead to a more comprehensive and complete information. In the field of fusion are generally distinguished probabilistic approaches and non-probabilistic ones which include the theory of evidence, developed in the 70s. This method represents both the uncertainty and imprecision of the information, by assigning masses not only to a hypothesis (which is the most common case for probabilistic methods) but to a set of hypothesis. The work presented in this thesis concerns the fusion of information for image segmentation.To develop this method we start with the algorithm of Watershed which is one of the most used methods for edge detection. Intuitively the principle of the Watershed is to consider the image as a landscape relief where heights of the different points are associated with grey levels. Assuming that the local minima are pierced with holes and the landscape is immersed in a lake, the water filled up from these minima generate the catchment basins, whereas watershed lines are the dams built to prevent mixing waters coming from different basins.The watershed is practically applied to the gradient magnitude, and a region is associated with each minimum. Therefore the fluctuations in the gradient image and the great number of local minima generate a large set of small regions yielding an over segmented result which can hardly be useful. Meyer and Beucher proposed seeded watershed or marked-controlled watershed to surmount this oversegmentation problem. The essential idea of the method is to specify a set of markers (or seeds) to be considered as the only minima to be flooded by water. The number of detected objects is therefore equal to the number of seeds and the result is then markers dependent. The automatic extraction of markers from the images does not lead to a satisfying result especially in the case of complex images. Several methods have been proposed for automatically determining these markers.We are particularly interested in the stochastic approach of Angulo and Jeulin who calculate a probability density function (pdf) of contours after M simulations of segmentation using conventional watershed with N markers randomly selected for each simulation. Therefore, a high pdf value is assigned to strong contour points that are more detected through the process. But the decision that a point belong to the "contour class" remains dependent on a threshold value. A single result cannot be obtained.To increase the robustness of this method and the uniqueness of its response, we propose to combine information with the theory of evidence.The watershed is generally calculated on the gradient image, first order derivative, which gives comprehensive information on the contours in the image.While the Hessian matrix, matrix of second order derivatives, gives more local information on the contours. Our goal is to combine these two complementary information using the theory of evidence. The method is tested on real images from the Berkeley database. The results are compared with five manual segmentation provided as ground truth, with this database. The quality of the segmentation obtained by our methods is tested with different measures: uniformity, precision, recall, specificity, sensitivity and the Hausdorff metric distance