| Přispěvatelé: |
Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), inconnu temporaire UPEMLV, Inconnu, Université Paris-Est, LIGM UMR CNRS 8049, France, Laurent Najman, Jean Cousty, Benjamin Perret |
| Popis: |
The wide literature on graph theory invites numerous problems to be modeled in theframework of graphs. In particular, clustering and segmentation algorithms designed inthis framework can be applied to solve problems in various domains, including imageprocessing, which is the main field of application investigated in this thesis. In thiswork, we focus on a semi-supervised segmentation tool widely studied in mathematicalmorphology and used in image analysis applications, namely the watershed transform.We explore the notion of a hierarchical watershed, which is a multiscale extension of thenotion of watershed allowing to describe an image or, more generally, a dataset withpartitions at several detail levels. The main contributions of this study are the following:- Recognition of hierarchical watersheds: we propose a characterization of hierarchicalwatersheds which leads to an efficient algorithm to determine if a hierarchy is ahierarchical watershed of a given edge-weighted graph.- Watersheding operator: we introduce the watersheding operator, which, given anedge-weighted graph, maps any hierarchy of partitions into a hierarchical watershedof this edge-weighted graph. We show that this operator is idempotent and its fixedpoints are the hierarchical watersheds. We also propose an efficient algorithm tocompute the result of this operator.- Probability of hierarchical watersheds: we propose and study a notion of probabilityof hierarchical watersheds, and we design an algorithm to compute the probabilityof a hierarchical watershed. Furthermore, we present algorithms to compute thehierarchical watersheds of maximal and minimal probabilities of a given weightedgraph.- Combination of hierarchies: we investigate a family of operators to combine hierarchiesof partitions and study the properties of these operators when applied tohierarchical watersheds. In particular, we prove that, under certain conditions, thefamily of hierarchical watersheds is closed for the combination operator.- Evaluation of hierarchies: we propose an evaluation framework of hierarchies, whichis further used to assess hierarchical watersheds and combinations of hierarchies.In conclusion, this thesis reviews existing and introduces new properties and algorithmsrelated to hierarchical watersheds, showing the theoretical richness of this frameworkand providing insightful view for its applications in image analysis and computervision and, more generally, for data processing and machine learning.; La littérature abondante sur la théorie des graphes invite de nombreux problèmes à êtremodélisés dans ce cadre. En particulier, les algorithmes de regroupement et de segmentationconçus dans ce cadre peuvent être utilisés pour résoudre des problèmes dans denombreux domaines tels que l’analyse d’image qui est le principal domaine d’applicationde cette thèse. Dans ce travail, nous nous concentrons sur un outil de segmentation semisupervisélargement étudié dans la morphologie mathematique et appliqué à l’analysed’image, notamment les Ligne de Partage des Eaux (LPE). Nous étudions la notion dehiérarchie de LPE, qui est une extension multi-échelle de la notion de LPE permettantde décrire une image ou, plus généralement, un ensemble de donnés par des partitionsà plusieurs niveaux de détail. Les contributions principales de cette étude sont les suivantes:- Reconnaissance de hiérarchies de LPE : nous proposons une caractérisation deshiérarchies de LPE qui mène à un algorithme efficace pour déterminer si une hiérarchieest une hiérarchie de LPE d’un graphe donné.- Opérateur watersheding : nous présentons l’opérateur watersheding, qui, étantdonné un graphe pondéré, associe n’importe quelle hiérarchie à une hiérarchie deLPE de ce graphe. Nous montrons que cet opérateur est idempotent et que sespoints fixes sont les hiérarchies de LPE. Nous proposons également un algorithmeefficace pour calculer le résultat de cet opérateur.- Probabilité de hiérarchies de LPE : nous proposons et étudions une notion deprobabilité d’une hiérarchie de LPE, et nous concevons un algorithme pour calculerla probabilité d’une hiérarchie de LPE. De plus, nous présentons des algorithmespour calculer des hiérarchies de LPE de probabilité minimale et maximale pour ungraphe pondéré donné.- Combinaison de hiérarchies : nous étudions une famille d’opérateurs pour combinerdes hiérarchies de partitions et nous étudions les propriétés de ces opérateurslorsqu’ils sont appliqués à les hiérarchies de LPE. En particulier, nous prouvonsque, dans certaines conditions, la famille des hiérarchies de LPE est fermée pourl’opérateur de combinaison.- Évaluation de hiérarchies : nous proposons un cadre d’évaluation de hiérarchies,qui est également utilisé pour évaluer les hiérarchies de LPE et les combinaisonsdes hiérarchies.En conclusion, cette thèse révise des propriétés existantes et des nouvelles propriétésliées aux hiérarchies de LPE, montrant la richesse théorique de ce cadre et fournissantune vue d’ensemble des ses applications dans l’analyse d’image et dans la vision parordinateur et, plus généralement, dans le traitement de donnés et dans l’apprentissageautomatique. |
