La segmentation est une tâche cruciale en analyse d’images. L’évolution des capteurs d’acquisition induit de nouvelles images de résolution élevée, contenant des objets hétérogènes. Il est aussi devenu courant d’obtenir des images d’une même scène à partir de plusieurs sources. Ceci rend difficile l’utilisation des méthodes de segmentation classiques. Les approches de segmentation hiérarchiques fournissent des solutions potentielles à ce problème. Ainsi, l’Arbre Binaire de Partitions (BPT) est une structure de données représentant le contenu d’une image à différentes échelles. Sa construction est généralement mono-critère (i.e. une image, une métrique) et fusionne progressivement des régions connexes similaires. Cependant, la métrique doit être définie a priori par l’utilisateur, et la gestion de plusieurs images se fait en regroupant de multiples informations issues de plusieurs bandes spectrales dans une seule métrique. Notre première contribution est une approche pour la construction multicritère d’un BPT. Elle établit un consensus entre plusieurs métriques, permettant d’obtenir un espace de segmentation hiérarchique unifiée. Par ailleurs, peu de travaux se sont intéressés à l’évaluation de ces structures hiérarchiques. Notre seconde contribution est une approche évaluant la qualité des BPTs en se basant sur l’analyse intrinsèque et extrinsèque, suivant des exemples issus de vérités-terrains. Nous discutons de l’utilité de cette approche pour l’évaluation d’un BPT donné mais aussi de la détermination de la combinaison de paramètres adéquats pour une application précise. Des expérimentations sur des images satellitaires mettent en évidence la pertinence de ces approches en segmentation d’images. / Segmentation is a crucial task in image analysis. Novel acquisition devices bring new images with higher resolutions, containing more heterogeneous objects. It becomes also easier to get many images of an area from different sources. This phenomenon is encountered in many domains (e.g. remote sensing, medical imaging) making difficult the use of classical image segmentation methods. Hierarchical segmentation approaches provide solutions to such issues. Particularly, the Binary Partition Tree (BPT) is a hierarchical data-structure modeling an image content at different scales. It is built in a mono-feature way (i.e. one image, one metric) by merging progressively similar connected regions. However, the metric has to be carefully thought by the user and the handling of several images is generally dealt with by gathering multiple information provided by various spectral bands into a single metric. Our first contribution is a generalized framework for the BPT construction in a multi-feature way. It relies on a strategy setting up a consensus between many metrics, allowing us to obtain a unified hierarchical segmentation space. Surprisingly, few works were devoted to the evaluation of hierarchical structures. Our second contribution is a framework for evaluating the quality of BPTs relying both on intrinsic and extrinsic quality analysis based on ground-truth examples. We also discuss about the use of this evaluation framework both for evaluating the quality of a given BPT and for determining which BPT should be built for a given application. Experiments using satellite images emphasize the relevance of the proposed frameworks in the context of image segmentation.

On étudie la conjecture des graphes jumeaux dénombrables, cas spécifique d’une conjecture de Thomassé, qui dit que le nombre de jumeaux d’un graphe dénombrable ( ses sous-graphes propres desquels il est aussi un sous-graphe propre) est soit nul, soit infini. On commence par étudier les graphes auto-abrités, que nous définissons, et en utilisant notre classification de ces graphes nous prouvons la conjecture dans certains cas, en précisant la cardinalité exacte du nombre de jumeaux. Nous donnons également des contre-exemples à l’article de l’arXiv «Self-contained graphs». / We make progress on the Graph Alternative Conjecture, a special case of a conjecture of Thomassé which says that the number of twins of a countable graph (i.e. its proper subgraphs of which that graph is also a proper subgraph) is either null or infinite. We begin by studying self-embedded graphs, which we define, and using our classification of these graphs, we prove the conjecture in some cases while specifying the exact number of twins. We also give counter-examples to a paper on arXiv called "Self-contained graphs".

Les jeux de données décrivant des objets par des propriétés Booléennes sont des relations binaires, c'est à dire des matrices 0/1. Dans une telle relation, un ensemble fermé est un sous-ensemble maximal d'objets partageant le même sous-ensemble maximal de propriétés. L'extraction de ces motifs, satisfaisant des contraintes de pertinences définies par l'utilisateur, a été étudiée en profondeur. Néanmoins, beaucoup de jeux de données sont des relations n-aires, c'est à dire des tenseurs 0/1. Réduire leur analyse à deux dimensions revient à en ignorer d'autres qui sont potentiellement intéressantes. Par ailleurs, la présence de bruit dans les jeux de données réelles conduit à la fragmentation des motifs à découvrir. On généralise facilement la définition d'un ensemble fermé aux relations de plus grande arité et à la tolérance au bruit. Au contraire, généraliser leur extraction est très difficile. Notre extracteur parcourt l'espace des motifs candidats d'une façon originale qui ne favorise aucune dimension. Cette recherche peut être guidée par une très grande classe de contraintes de pertinence que les motifs doivent satisfaire. En particulier, cette thèse étudie des contraintes spécifiques à la fouille de graphes dynamiques. Notre extracteur est plusieurs ordres de grandeurs plus efficace que les algorithmes existants, pourtant plus restreints dans leurs applications. Malgré ces résultats, une approche exhaustive ne peut souvent pas, en un temps raisonnable, lister des motifs tolérants beaucoup de bruit. Dans ce cas, compléter l'extraction avec une agglomération hiérarchique des motifs permet d'arriver à ses fins.

Une valeur propre est dite stable si sa multiplicité se maintient par petites perturbations. Cette hypothèse de stabilité dépend en particulier de la perturbation considérée. Nous verrons cela dans l'exemple de la sphère de dimension trois. Après avoir introduit la définition des opérateurs de Schrödinger avec champ magnétique sur une variété Riemannienne puis sur un graphe, nous montrerons que toute valeur propre de la sphère est stable pour les perturbations par champ électromagnétique et que la première valeur propre de la sphère avec champ magnétique constant est stable pour les potentiels. Nous prouverons que la multiplicité maximale de l'état fondamental d'un opérateur de Schrödinger avec champ magnétique sur S² est indépendant de la topologie du fibré. Nous montrerons par la suite que la multiplicité maximale de la première valeur propre d'un opérateur de Schrödinger avec champ magnétique sur un graphe est indépendant de sa planarité.

.

Cette thèse est d'abord motivée par le souci d'élucider certains liens existant entre la théorie des ensembles flous et celle des probabilités, en les replaçant toutes deux dans un contexte plus général de mesures dites « d'incertitude ». Sur cette base, on développe des outils mathématiques susceptibles d'exprimer rigoureusement, de façon quantitative, les concepts duaux de possibilité et de nécessité. On montre notamment qu'on peut par là généraliser les opérations logiques ainsi que d'autres notions, telles que la cardinalité, à des ensembles dont les frontières sont mal définies, représentés par le biais d'une fonction d'appartenance, qu'on peut voir comme une distribution de possibilité. On développe, dans le cadre de la théorie des possibilités, un calcul analogue à celui des fonctions de variables aléatoires, appelé calcule des intervalles flous, qui généralise le calcule d'erreurs. Des éléments d'analyse de fonctions floues, étendant l'analyse des correspondances, sont fournis, notamment l'intégration de Riemann.<br /><br />Ces outils mathématiques sont appliqués à la formulation et à la résolution de problèmes d'analyse de la décision et de recherche opérationnelle. On étudie plus particulièrement l'agrégation de critère, l'évaluation des décisions et le choix en environnement incertain et imprécisément décrit, les algorithmes de plus courts chemins dans les graphes imprécisément valués, la programmation linéaire avec contraintes floues. On tente dans chaque cas de discuter les mérites et les limites de la théorie des possibilités par rapport à celle des probabilités, tant sur le plan de leur pouvoir descriptif que sur celui des calculs qu'elles entraînent, et des résultats qu'elles permettent d'obtenir.

Cette thèse traite du problème de la redistribution dynamique parallèle efficace de la charge pour les problèmes numériques de très grande taille. Nous présentons tout d'abord un état de l'art des algorithmes permettant de résoudre les problèmes du partitionnement, du repartitionnement, du placement statique et du re-placement. Notre première contribution vise à étudier, dans un cadre séquentiel, les caractéristiques algorithmiques souhaitables pour les méthodes parallèles de repartitionnement. Nous y présentons notre contribution à la conception d'un schéma multi-niveaux k-aire pour le calcul sequentiel de repartitionnements. La partie la plus exigeante de cette adaptation concerne la phase d'expansion. L'une de nos contributions majeures a été de nous inspirer des méthodes d'influence afin d'adapter un algorithme de raffinement par diffusion au problème du repartitionnement.Notre deuxième contribution porte sur la mise en oeuvre de ces méthodes sur machines parallèles. L'adaptation du schéma multi-niveaux parallèle a nécessité une évolution des algorithmes et des structures de données mises en oeuvre pour le partitionnement. Ce travail est accompagné d'une analyse expérimentale, qui est rendue possible grâce à la mise en oeuvre des algorithmes considérés au sein de la bibliothèque Scotch. / This thesis concerns efficient parallel dynamic load balancing for large scale numerical problems. First, we present a state of the art of the algorithms used to solve the partitioning, repartitioning, mapping and remapping problems. Our first contribution, in the context of sequential processing, is to define the desirable features that parallel repartitioning tools need to possess. We present our contribution to the conception of a k-way multilevel framework for sequential repartitioning. The most challenging part of this work regards the uncoarsening phase. One of our main contributions is the adaptation of influence methods to a global diffusion-based heuristic for the repartitioning problem. Our second contribution is the parallelization of these methods. The adaptation of the aforementioned algorithms required some modification of the algorithms and data structure used by existing parallel partitioning routines. This work is backed by a thorough experimental analysis, which is made possible thanks to the implementation of our algorithms into the Scotch library.

Répondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s’intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d’un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L’un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L’une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l’étude porte sur un algorithme auto-stabilisant de calcul d’arbre de plus court chemin, ainsi que sur l’impact de la suppression de noeuds ou d’arêtes sur les tables de routage stockées aux routeurs. / In order to respond to routing queries, the entities of the network, nammedrouters, require to have a knowledge concerning the topology of the network, thisknowledge is called routing table. The network is modeled by a graph in whichnodes represent routers and edges represent communication links between nodes.This thesis focuses on routing tables computation in a distributed model. In thismodel, computations are done by a set of process placed on nodes. Every processhas for objective to compute the routing table of the node on which he is placed.To perform this computation, processes have to communicate with each other. Inlarge scale network, in the case of a distributed computation, maintaining routingtables up to date can be costly in terms of communication. This thesis focuses mainlyon the problem of communication cost reduction. One of the solution we proposeis to reduce routing tables size which allow to reduce communication cost. In thecentralised model this strategy is well known under the name of compact routing.This thesis presents in particular a distributed compact routing algorithm that allowsto reduce significantly the communication costs in networks like Internet, i.e. theautonomous systems network and others networks that present scale-free properties.This thesis also contains an experimental study of several distributed compact routingalgorithms. Finally, some problems linked to network dynamicity are addressed.More precisely, the problem of network deconnexion during a shortest path treecomputation with auto-stabilisation guaranties, together with a study of the impactof several edges or nodes deletion on the state of the routing tables.

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Cette thèse étudie les méthodes de regroupement basées sur le principe des plus proches voisins partagés (SNN). Comme la plupart des autres approches de clustering à base de graphe, les méthodes SNN sont effectivement bien adaptées à surmonter la complexité des données, l'hétérogénéité et la haute dimensionnalité. La première contribution de la thèse est de revisiter une méthode existante basée sur les voisins partagés en deux points. Nous présentons d'abord un formalisme basé sur la la théorie de décision à contrario. Cela nous permet de tirer des scores de connectivité plus fiable des groupes et une interprétation plus intuitive des voisinage selectionnés optimalement. Nous proposons également un nouveau algorithme de factorisation pour accélérer le calcul intensif nécessaire des matrices des voisins partagés. La deuxième contribution de cette thèse est une généralisation de la classification SNNau cas multi-source. La principale originalité de notre approche est que nous introduisons une étape de sélection des sources d'information optimales dans le calcul de scores de groupes candidats. Chaque groupe est alors associé à son propre sous-ensemble optimal des modalités. Comme le montre le expériences, cette étape de sélection de source rend notre approche largement robuste à la présence de sources locales aberrantes. Cette nouvelle méthode est appliquée à un large éventail de problèmes, y compris la structuration multimodale des collections d'images et dans le regroupement dans des sous-espaces basés sur les projections aléatoires.La troisième contribution de la thèse est une tentative pour étendre les méthodes SNNdans le contexte des graphes biparites. Nous introduisons de nouvelles mesures de pertinence SNNrevisitées pour ce contexte asymétrique et nous montrons qu'elles peuvent être utiliséespour sélectionner localement des voisinages optimales. En conséquence, nous proposons un nouveau algorithme de clustering bipartite SNN qui est appliqué à la découverte d'objets visuels.Les expériences montrent que cette nouvelle méthode est meilleure par rapport aux méthodes de l'état de l'art. Basé sur les objets découverts, nous introduisons également un paradigme de recherche visuelle, c.-à-d les objet basés sur la suggestion de requêtes visuel les. / This thesis investigates new clustering paradigms and algorithms based on the principle of the shared nearest-neighbors (SNN. As most other graph-based clustering approaches, SNN methods are actually well suited to overcome data complexity, heterogeneity and high-dimensionality.The first contribution of the thesis is to revisit existing shared neighbors methods in two points. We first introduce a new SNN formalism based on the theory of a contrario decision. This allows us to derive more reliable connectivity scores of candidate clusters and a more intuitive interpretation of locally optimum neighborhoods. We also propose a new factorization algorithm for speeding-up the intensive computation of the required sharedneighbors matrices.The second contribution of the thesis is a generalization of the SNN clustering approach to the multi-source case. Whereas SNN methods appear to be ideally suited to sets of heterogeneous information sources, this multi-source problem was surprisingly not addressed in the literature beforehand. The main originality of our approach is that we introduce an information source selection step in the computation of candidate cluster scores. As shown in the experiments, this source selection step makes our approach widely robust to the presence of locally outlier sources. This new method is applied to a wide range of problems including multimodal structuring of image collections and subspace-based clustering based on random projections. The third contribution of the thesis is an attempt to extend SNN methods to the context of bipartite k-nn graphs. We introduce new SNN relevance measures revisited for this asymmetric context and show that they can be used to select locally optimal bi-partite clusters. Accordingly, we propose a new bipartite SNN clustering algorithm that is applied to visual object’s discovery based on a randomly precomputed matching graph. Experiments show that this new method outperformed state-of-the-art object mining results on OxfordBuilding dataset. Based on the discovered objects, we also introduce a new visual search paradigm, i.e. object-based visual query suggestion.