De nombreuses applications informatiques nécessitent de résoudre des problèmes de décision qui sont difficiles d’un point de vue mathématique. La programmation par contraintes permet de modéliser et résoudre certains de ces problèmes, parfois définis sur des graphes. Au delà des difficultés intrinsèques aux problèmes étudiés, la taille des instances à traiter contribue à la difficulté de la résolution. Cette thèse traite de l’utilisation des graphes en programmation par contraintes, dans le but d’en améliorer la capacité de passage à l’échelle. Une première partie porte sur l’utilisation de contraintes pour résoudre des problèmes de graphes impliquant la recherche d’arbres, de chemins et de cycles Hamiltoniens. Ce sont des problèmes importants que l’on retrouve dans de nombreuses applications industrielles. Nous étudions à la fois le filtrage et les stratégies d’exploration de l’espace de recherche. Nous chercherons ensuite à nous extraire progressivement des problèmes classiquement définis sur les graphes pour exploiter ce concept sur des problèmes définis sur les entiers, voire les réels. Une seconde partie porte ainsi sur l’utilisation des graphes pour le filtrage de contraintes globales très répandues. Nous proposerons entre autres d’utiliser des graphes comme support pour décomposer dynamiquement des algorithmes de filtrage, de manière générique. Le fil conducteur de ces travaux sera d’une part l’utilisation du concept de graphe à la base de chaque raisonnement et d’autre part, la volonté pratique d’augmenter la taille des problèmes pouvant être traités en programmation par contraintes. / Many IT applications require to solve decision problems which are hard from a mathematical point of view. Constraint-programming enables to model and solve some of these problems. Among them, some are defined over graphs. Beyond the difficulty stemming from each of these problems, the size of the instance to solve increases the difficulty of the task. This PhD thesis is about the use of graphs within constraint programming, in order to improve its scalability. First, we study the use of constraint-programming to solve some graph problems involving the computation of trees and Hamiltonian paths and cycles. These problems are important and can be found in many industrial applications. Both filtering and search are investigated. Next, we move on problems which are no longer defined in terms of graph properties. We then study the use of graphs to propagate global constraints. In particular, we suggest a generic schema, relying ona graph structure, to dynamically decompose filtering algorithms. The central theme in this work is the use of graph concepts at the origin of every reasoning and the practical will to increase the size of problems that can be addressed in constraint-programming.

La mémoire épisodique correspond à la reviviscence consciente d'expériences personnelles ancrées dans un contexte spécifique. Ce travail de thèse porte sur l'étude des processus cognitifs et des mécanismes neuronaux du rappel épisodique chez l'Homme. Les souvenirs rappelés par les odeurs sont plus détaillés et plus émotionnels que ceux évoqués par d'autres modalités sensorielles. Ces spécificités expliquent pourquoi nous nous intéressons à l'évocation des souvenirs par des odeurs. Tout d'abord, une tâche comportementale novatrice est développée pour permettre l'étude contrôlée de la mémoire d'épisodes complexes constitués d'odeurs non familières (Quoi), localisées à des emplacements distincts (Où), d'un environnement visuel donné (Quel contexte). A l'aide de cette tâche, nous montrons que, lorsque les dimensions d'un épisode sont étroitement liées, la perception de l'odeur permet le rappel de l'ensemble du souvenir. Le rappel épisodique est essentiellement fondé sur des processus de recollection, la familiarité n'étant pas suffisante pour récupérer l'ensemble du souvenir. De plus, les odeurs associées à une émotion, quelle que soit leur valence, facilitent le rappel épisodique correct. Fonctionnellement, la mémoire épisodique est sous-tendue par un large réseau neuronal, constitué de régions typiquement impliquées dans la mémoire de laboratoire et la mémoire autobiographique. Les souvenirs corrects sont associés à un réseau neuronal différent des souvenirs incorrects, de la perception de l'odeur à la ré-expérience du souvenir. Des analyses de modularité indiquent que les interactions fonctionnelles au sein du réseau de la mémoire épisodique dépendent également de l'exactitude du souvenir. L'ensemble de ces travaux suggère que le rappel épisodique est un processus dynamique complexe, initié dès la perception des odeurs, et interdépendant d'autres systèmes de mémoire tels que les mémoires perceptive et sémantique / Episodic memory is the memory that permits the conscious re-experience of specific personal events and associated with a specific context. This doctoral research aims at investigating the cognitive processes and the neural bases of episodic retrieval in humans. Odor-evoked memories are known to be more detailed and more emotional than memories triggered by other sensorial cues. These specificities explain why we studied odor-evoked memories. First, a novel behavioral task has been designed to study in a controlled way the memory of complex episodes comprising unfamiliar odors (What), localized spatially (Where), within a visual context (Which context). From this approach, we suggest that when the binding between the episodes’ dimensions is strong, the odor perception evokes the whole episodic memory. The episodic retrieval is mainly based on recollection processes, the feeling of knowing being insufficient to induce complete memory recovery. Moreover, emotion carried by odors, whatever its valence, promote accurate episodic retrieval. Functionally, episodic memory is underpinned by a distributed network, constituted of regions typically found in laboratory and autobiographical memory approaches. Accurate memories are associated with a specific neural network, from odor perception to memory re-experience. Modularity analyses show that neural interactions within this network also depend on memory accuracy. Altogether, results of this research suggest that episodic retrieval is a dynamic and complex process, triggered by odors perception, closely linked to other memory systems such as perceptual and semantic memories

Le sujet abordé dans cette thèse concerne la contrôlabilité d’une classe de systèmes spatio-temporels, entièrement discrets de type automates cellulaires (AC). Le but de cette étude est de mettre en lumière de nouvelles pistes pour prouver la contrôlabilité des systèmes complexes. Plus spécifiquement, cette thèse se focalise sur la contrôlabilité régionale qui consiste à se restreindre à une région du domaine où le système devra atteindre un objectif donné à travers des actions ciblées. Le cas d’AC Booléens a été particulièrement examiné tout au long de cette thèse. La première partie est consacrée à l’étude du problème de la contrôlabilité régionale des AC déterministes lorsque les actions sont exercées sur la frontière de la régioncontrôlée. Une première démarche que nous avons utilisée s’appuie sur les chaines de Markov et la contrôlabilité est caractérisée en établissant une matrice similaire à leur matrice de transition en utilisant les définitions d’une chaîne ergodique et régulière. Cette étude a été étendue au cas des AC probabilistes qui sont largement utilisés pour modéliser de nombreux phénomènes réels. Le même problème a été appréhendé en utilisant des outils de la théorie des graphes. Nous proposons des conditions nécessaires et suffisantes pour la contrôlabilité régionale des AC déterministes en utilisant les notions de circuit hamiltonien et de composante fortement connexe. Le contrôle qui assure la contrôlabilité régionale est défini à travers un algorithme préimages. La deuxième partie est dédiée au problème de la contrôlabilité régionale frontière des AC Booléens qui consiste à agir sur la frontière du domaine pour atteindre un objectif sur une région cible. Nous considérons d’abord des AC linéaires pour lesquels nousdonnons un résultat de caractérisation grâce à la condition de Kalman. Nous proposons un algorithme pour déterminer le contrôle qui permet de forcer l’apparition d’une configuration désirée dans la région d’étude. Le cas des AC non linéaires a été également considéré en utilisant un algorithme de recherche des préimages. / The issue addressed in this thesis concerns the controllability of a class of discrete spatio-temporal systems named cellular automata (CA). The purpose of this study is to highlight new ways to prove the controllability of complex systems. Morespecifically, this thesis focuses on regional controllability which consists in restricting the study to a subregion of the domain where the system will have to achieve a given objective through targeted actions. The case of Boolean CA have been particularly examined throughout this thesis. The first part is devoted to the study of the problem of the regional controllability of deterministic CAs when the actions are exerted on the boundaries of the controlled region. A first approach that we used relies on Markov chains and controllability is characterized by establishing a matrix similar to their transition matrix using the definitions of a regular and ergodic chain. This study has been extended to the case of probabilistic CAs that are widely used tomodel many real phenomena. The same problem has been apprehended using tools of graph theory. We proposenecessary and sufficient conditions for the regional controllability of deterministic CAs using the notions of Hamiltonian circuit and strongly connected component. The control that ensures regional controllability is defined through a preimage algorithm.The second part is devoted to the problem of the boundary regional controllability of Boolean CAs, which consists of acting on the boundary of the domain in order to reach a desired goal in a target region. We first consider linear CAs for which we givea characterization result using the Kalman condition. We propose an algorithm to determine the control that allows to force the appearance of a desired configuration in the study area. The case of nonlinear CAs was also considered using a preimagesearch algorithm.

La théorie des jeux à champ moyen fut introduite en 2006 par Jean-Michel Lasry et Pierre-Louis Lions. Elle permet l'étude de la théorie des jeux dans certaines configurations où le nombre de joueurs est trop grand pour espérer une résolution pratique. Nous étudions la théorie des jeux à champ moyen sur les graphes en nous appuyant sur les travaux d'Olivier Guéant que nous étendrons à des formes plus générales d'Hilbertien. Nous étudierons aussi les liens qui existent entres les K-moyennes et les jeux à champ moyen ce qui permettra en principe de proposer de nouveaux algorithmes pour les K-moyennes grâce aux techniques de résolution numérique propres aux jeux à champ moyen. Enfin nous étudierons un jeu à champ moyen à savoir le problème "d'heure de début d'une réunion" en l'étendant à des situations où les agents peuvent choisir entre deux réunions. Nous étudierons de manière analytique et numérique l'existence et la multiplicité des solutions de ce problème. / The mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem.

L'un des problèmes les plus complexes dans l'analyse des images histologiques est l'évaluation de l¿organisation spatiale des structures histologiques dans le tissu. En fait, les sections histologiques peuvent contenir un très grand nombre de cellules de différents types et irrégulièrement réparties dans le tissu, ce qui rend leur contenu spatial indescriptible d'une manière simple. Les méthodes fondées sur la théorie des graphes ont été largement explorées dans cette direction, car elles sont des outils de représentation efficaces ayant la capacité expressive de décrire les caractéristiques spatiales et les relations de voisinage qui sont interprétées visuellement par le pathologiste. On peut distinguer trois familles principales de méthodes des graphes utilisées à cette fin: analyse de structure syntaxique, analyse de réseau et analyse spectrale. Cependant, un autre ensemble distinctif de méthodes basées sur la morphologie mathématique sur les graphes peut être développé et adapté pour ce problème. L'objectif principal de cette thèse est le développement d'un outil capable de fournir une évaluation quantitative des arrangements spatiaux des structures histologiques en utilisant la morphologie mathématique basée sur les graphes. / One of the most challenging problems in histological image analysis is the evaluation of the spatial organizations of histological structures in the tissue. In fact, histological sections may contain a very large number of cells of different types and irregularly distributed, which makes their spatial content indescribable in a simple manner. Graph-based methods have been widely explored in this direction, as they are effective representation tools having the expressive ability to describe spatial characteristics and neighborhood relationships that are visually interpreted by the pathologist. We can distinguish three main families of graph-based methods used for this purpose: syntactic structure analysis, network analysis and spectral analysis. However, another distinctive set of methods based on mathematical morphology on graphs can be additionally developed for this issue. The main goal of this dissertation is the development of a framework able to provide quantitative evaluation of the spatial arrangements of histological structures using graph-based mathematical morphology.

D’un côté, la transition écologique et les enjeux de développement durable sont de nos jours une réalité que l’on ne peut ignorer compte tenu des impacts négatifs des activités humaines sur leurs environnements. De l’autre côté, une numérisation toujours plus importante de ces environnements entraîne la génération de volumes massifs de traces numériques, qui sont autant d’indices sur le monde dans lequel vivent les acteurs de ces activités. Une difficulté non négligeable existe pour comprendre les tenants et aboutissants faisant que d’une activité à une autre, l’impact sur l’environnement mesuré dans ces travaux de recherche à travers le concept d’Emprise Énergétique (EmE) n’est pas le même. Notre approche considère l’identification sur la base de ces traces numériques, d’activité d’entités humaines et non humaines. L’instanciation de ces dernières au sein de pratiques mobilise des ressources (physiques et virtuelles) en plus ou moins grand nombre. Leurs modélisations permettraient de mieux appréhender les enjeux liés à la transition écologique. Identifier sur la base d’indicateurs quantifiables les pratiques ayant un impact réduit sur l’environnement serait une piste permettant de contribuer à cette transition. Ces pratiques, au sens de coordination de multiples entités hétérogènes dans le temps et l’espace, peuvent être formalisées sous forme de structures d’activités multidimensionnelles à l’aide de la théorie de l’Agencement et d’un ensemble d’outils mathématiques (Complexes Simpliciaux, Hypernetworks). Ces travaux de recherche tentent de modéliser le phénomène d’activité humaine et non humaine en s’appuyant sur la caractérisation du contexte de celles-ci à partir de données massives. Ces agencements sont calculés et représentés dans une application (IMhoTEP) ayant pour but de construire ces structures complexes non pas sur des catégorisations faites a priori des entités, mais en se focalisant sur les relations que celles-ci entretiennent dans plusieurs dimensions. L’objectif final est de proposer un outil d’accompagnement à la transition écologique à destination des acteurs participant à des activités induisant la consommation, voire la production de ressources. Ces travaux de recherche en informatique s’appuient sur la numérisation continue des espaces et particulièrement les espaces urbains (Smart City, Internet of Everything). / On one hand, the ecological transition and sustainable development issues are today a reality that cannot be ignored given the negative impacts of human activities on their environments. On the other side, an increasingly important digitization of these environments results in the generation of massive volumes of digital traces, which are all signs of actors’ activities. A significant challenge is to understand the ins and outs of environmental impact due activities and considering Emprise of Energy (EmE) as a key indicator and how this indicator can strongly change from an activity to another. Our approach considers the identification of Practice on the basis of these digital traces generated by human and non-human entities during specific activities. Practice (instantiation of activity) uses more or less resources (physical and virtual) during their existence. Be able to identify which one is more resources dependent would help to better understand how to promote ecological transition. Promoting or at least identifying on the basis of quantifiable indicators (i.e Energy Emprise), practices that have a low impact on the environment, could be an innovative approach. These practices, in the sense of coordination of multiple heterogeneous entities in time and space, can be formalized in the form of multidimensional structures activities - Hypergraph of Activities – using the theory of Assemblage (Agencement in french) and using a set of mathematical tool (Simplicial Complexes, Hypernetworks). This research attempts to model the phenomenon of human and not human activity based on the characterization of the context (massive contextual data). These Assemblages are calculated and represented in an research application (IMhoTEP) which aims to build these complex structures not based on a priori entities’ classification, but by focusing on the relationships that they maintain in several dimensions. The main goal is to offer a decision tool which support actors’ ecological transition by understand activities inducing consumption or production of resources. These academic research in the field of computer science is based continuous digitization of physical and virtual spaces, particularly highly connected urban areas (Smart City, Internet of Everything).

La gestion de projets complexes nécessite d’orchestrer la coopération de centaines de personnes provenant de diverses entreprises, professions et compétences, de travailler sur des milliers d'activités, livrables, objectifs, actions, décisions et risques. En outre, ces nombreux éléments du projet sont de plus en plus interconnectés, et aucune décision ou action n’est indépendante. Cette complexité croissante est l'un des plus grands défis de la gestion de projet et l'une des causes de l'échec du projet en termes de dépassements de coûts et des retards. Par exemple, dans l'industrie automobile, l'augmentation de l'orientation du marché et de la complexité croissante des véhicules a changé la structure de gestion des projets de développement de nouveaux véhicules à partir d'une structure hiérarchique à une structure en réseau, y compris le constructeur, mais aussi de nombreux fournisseurs. Les dépendances entre les éléments du projet augmentent les risques, car les problèmes dans un élément peuvent se propager à d'autres éléments qui en dépendent directement ou indirectement. La complexité génère un certain nombre de phénomènes, positifs ou négatifs, isolés ou en chaînes, locaux ou globaux, qui vont plus ou moins interférer avec la convergence du projet vers ses objectifs.L'objectif de la thèse est donc de réduire les risques associés à la complexité des projets véhicules en augmentant la compréhension de cette complexité et de la coordination des acteurs du projet. Pour ce faire, une première question de recherche est de prioriser les actions pour atténuer les risques liés à la complexité. Puis, une seconde question de recherche est de proposer un moyen d'organiser et de coordonner les acteurs afin de faire face efficacement avec les phénomènes liés à la complexité identifiés précédemment.La première question sera abordée par la modélisation de complexité du projet en analysant les phénomènes liés à la complexité dans le projet, à deux niveaux. Tout d'abord, une modélisation descriptive de haut niveau basée facteur est proposé. Elle permet de mesurer et de prioriser les zones de projet où la complexité peut avoir le plus d'impact. Deuxièmement, une modélisation de bas niveau basée sur les graphes est proposée. Elle permet de modéliser plus finement les éléments du projet et leurs interdépendances. Des contributions ont été faites sur le processus complet de modélisation, y compris l'automatisation de certaines étapes de collecte de données, afin d'augmenter les performances et la diminution de l'effort et le risque d'erreur. Ces deux modèles peuvent être utilisés en conséquence; une première mesure de haut niveau peut permettre de se concentrer sur certains aspects du projet, où la modélisation de bas niveau sera appliquée, avec un gain global d'efficacité et d'impact. Basé sur ces modèles, certaines contributions sont faites pour anticiper le comportement potentiel du projet. Des analyses topologiques et de propagation sont proposées pour détecter et hiérarchiser les éléments essentiels et les interdépendances critiques, tout en élargissant le sens du mot polysémique "critique".La deuxième question de recherche sera traitée en introduisant une méthodologie de « Clustering » pour proposer des groupes d'acteurs dans les projets de développement de nouveaux produits, en particulier pour les acteurs impliqués dans de nombreuses interdépendances liées aux livrables à différentes phases du cycle de vie du projet. Cela permet d'accroître la coordination entre les acteurs interdépendants qui ne sont pas toujours formellement reliés par la structure hiérarchique de l'organisation du projet. Cela permet à l'organisation du projet d’être effectivement plus proche de la structure en « réseau » qu’elle devrait avoir. L'application industrielle aux projets de développement de nouveaux véhicules a montré des résultats prometteurs pour les contributions aux deux questions de recherche. / The management of complex projects requires orchestrating the cooperation of hundreds of individuals from various companies, professions and backgrounds, working on thousands of activities, deliverables, and risks. As well, these numerous project elements are more and more interconnected, and no decision or action is independent. This growing complexity is one of the greatest challenges of project management and one of the causes for project failure in terms of cost overruns and time delays. For instance, in the automotive industry, increasing market orientation and growing complexity of automotive product has changed the management structure of the vehicle development projects from a hierarchical to a networked structure, including the manufacturer but also numerous suppliers. Dependencies between project elements increase risks, since problems in one element may propagate to other directly or indirectly dependent elements. Complexity generates a number of phenomena, positive or negative, isolated or in chains, local or global, that will more or less interfere with the convergence of the project towards its goals. The thesis aim is thus to reduce the risks associated with the complexity of the vehicle development projects by increasing the understanding of this complexity and the coordination of project actors. To do so, a first research question is to prioritize actions to mitigate complexity-related risks. Then, a second research question is to propose a way to organize and coordinate actors in order to cope efficiently with the previously identified complexity-related phenomena.The first question will be addressed by modeling project complexity and by analyzing complexity-related phenomena within the project, at two levels. First, a high-level factor-based descriptive modeling is proposed. It permits to measure and prioritize project areas where complexity may have the most impact. Second, a low-level graph-based modeling is proposed, based on the finer modeling of project elements and interdependencies. Contributions have been made on the complete modeling process, including the automation of some data-gathering steps, in order to increase performance and decrease effort and error risk. These two models can be used consequently; a first high-level measure can permit to focus on some areas of the project, where the low-level modeling will be applied, with a gain of global efficiency and impact. Based on these models, some contributions are made to anticipate potential behavior of the project. Topological and propagation analyses are proposed to detect and prioritize critical elements and critical interdependencies, while enlarging the sense of the polysemous word “critical."The second research question will be addressed by introducing a clustering methodology to propose groups of actors in new product development projects, especially for the actors involved in many deliverable-related interdependencies in different phases of the project life cycle. This permits to increase coordination between interdependent actors who are not always formally connected via the hierarchical structure of the project organization. This allows the project organization to be actually closer to what a networked structure should be. The automotive-based industrial application has shown promising results for the contributions to both research questions. Finally, the proposed methodology is discussed in terms of genericity and seems to be applicable to a wide set of complex projects for decision support.

L'Internet connaît à nouveau une expansion drastique. En plus des terminaux classiques, il permet aujourd'hui d'interconnecter toute sorte d'objets connectés permettant la capture d'événements depuis l'environnement considéré, mais également le contrôle à distance de cet environnement. Plusieurs milliards de ces objets sont ainsi amenés à l'horizon 2020 à contribuer à l'avènement de l'Internet des Objets (IoT). Ce paradigme, qui étend le concept de Machine-to-Machine (M2M), ouvre la voie à de nouveaux usages tels que la domotique, la télésurveillance, ou encore les usines du futur. Plusieurs architectures ont été proposées pour structurer l'IoT. Leur fondement est basé sur une vision en quatre niveaux : le niveau Équipement, qui comporte les objets connectés, le niveau Réseau contenant les différentes technologies nécessaires aux échanges, le niveau Intergiciel (ou Middleware) qui offre aux applications une couche d'abstraction des niveaux sous-jacents, et enfin le niveau Application qui consiste en l'ensemble des applications concourant, via leurs interactions avec les objets connectés, à la réalisation d'une activité métier. Nos travaux se positionnent au niveau Middleware sur la base de l'architecture définie dans le cadre des standards SmartM2M puis oneM2M. Plusieurs problématiques sont amenées à être (re)-posées dans ce contexte. Nous nous intéressons essentiellement à celle de la qualité de service (QoS - Quality of Service) exprimée par certaines applications métiers. Les solutions proposées en réponse à cette problématique concernent principalement le niveau Réseau. Au niveau Middleware, les standards se focalisent essentiellement sur la proposition d'architectures et de services fonctionnels. Les besoins non fonctionnels, typiquement orientés QoS, ne sont que peu ou pas considérés. Parallèlement, les solutions propriétaires ne considèrent pas l'évolution dynamique du contexte et des besoins. Face à ces limites, nous proposons une approche de gestion dynamique, i.e. durant l'exécution du système, et autonome induisant un minimum d'intervention humaine. La gestion proposée, guidée par des modèles, porte sur des actions de reconfiguration comportementales et structurelles touchant au trafic applicatif et/ou sur les ressources de niveau Middleware / The Internet is experiencing a drastic expansion again. In addition to conventional terminals, it now allows to interconnect all kinds of connected objects allowing the capture of events from the considered environment, but also the remote control of this environment. Billions of these objects are thus led in 2020 to contribute to the advent of the Internet of Things (IoT). This paradigm, which extends the Machine-to-Machine (M2M) concept, paves the way for new uses such as home automation, remote monitoring, or even the factories of the future. Several architectures have been proposed to structure the IoT. Their foundation is based on a vision in four levels: (1) Equipment level, which includes the IoT equipment, (2) Network level containing the various technologies for data exchanges, (3) Middleware level, which offers applications an abstraction layer for underlying levels, and finally, (4) Application level, which consists of the set of applications contributing, via their interactions with the connected objects, to the realization of a business activity. Our work is positioned at Middleware level and is based on the architecture defined in the SmartM2M and then oneM2M standards. Several challenges have to be (re)considered in this context. We are mainly interested in the Quality of Service (QoS) issue expressed by some business applications. Proposals addressing this issue essentially target the Network level. For the Middleware level, standards focus mainly on the proposal of architectures and functional services. The non-functional requirements, typically QoS, are little or not considered. Meanwhile, proprietary solutions do not consider the dynamic evolution of the context and requirements. In response to these limitations, we propose a dynamic management approach, i.e. during the execution of the system, and autonomous, i.e. without human intervention. The proposed management, guided by models, focuses on behavioural and structural reconfiguration actions related to application traffic and/or Middleware resources.

Le contexte de cette thèse est le recalage d'images endomicroscopiques. Le microendoscope multiphotonique fournit différentes trajectoires de balayage que nous considérons dans ce travail. Nous proposons d'abord une méthode de recalage non rigide dont l'estimation du mouvement est transformée en un problème d'appariement d'attributs dans le cadre des Log-Demons et d'ondelettes sur graphes. Nous étudions les ondelettes de graphe spectral (SGW) pour capturer les formes des images, en effet, la représentation des données sur les graphes est plus adaptée aux données avec des structures complexes. Nos expériences sur des images endomicroscopiques montrent que cette méthode est supérieure aux techniques de recalage d'images non rigides existantes. Nous proposons ensuite une nouvelle stratégie de recalage d'images pour les images endomicroscopiques acquises sur des grilles irrégulières. La transformée en ondelettes sur graphe est flexible et peut être appliquée à différents types de données, quelles que soient la densité de points et la complexité de la structure de données. Nous montrons également comment le cadre des Log-Demons peut être adapté à l'optimisation de la fonction objective définie pour les images acquises avec un échantillonnage irrégulier. / The context of this thesis is the image registration for endomicroscopic images. Multiphoton microendoscope provides different scanning trajectories which are considered in this work. First we propose a nonrigid registration method whose motion estimation is cast into a feature matching problem under the Log-Demons framework using Graph Wavelets. We investigate the Spectral Graph Wavelets (SGWs) to capture the shape feature of the images. The data representation on graphs is more adapted to data with complex structures. Our experiments on endomicroscopic images show that this method outperforms the existing nonrigid image registration techniques. We then propose a novel image registration strategy for endomicroscopic images acquired on irregular grids. The Graph Wavelet transform is flexible to apply on different types of data regardless of the data point densities and how complex the data structure is. We also show how the Log-Demons framework can be adapted to the optimization of the objective function defined for images with an irregular sampling.

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à “activer” au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de “protéger” un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe. / In this thesis, we investigate the computational complexity of optimization problems involving a “diffusion process” in a graph. More specifically, we are first interested to the target set selection problem. This problem consists of finding the smallest set of initially “activated” vertices of a graph such that all the other vertices become activated after a finite number of propagation steps. If we modify this process by allowing the possibility of ``protecting'' a vertex at each step, we end up with the firefighter problem that asks for minimizing the total number of activated vertices by protecting some particular vertices. In fact, we introduce and study a generalized version of this problem where more than one vertex can be protected at each step. We propose several complexity results for these problems from an approximation point of view and a parameterized complexity perspective according to standard parameterizations as well as parameters related to the graph structure.