De nombreux domaines applicatifs utilisent des techniques de traitement d'images basées sur l'analyse de la topologie des images discrètes, en particulier pour des opérations devant préserver cette topologie. Si beaucoup de travaux théoriques et méthodologiques ont été menés dans le cadre des images binaires, les questions relatives à la modélisation et à la gestion simultanées des propriétés topologiques de plusieurs éléments sémantiques dans une même image discrète reste à l'heure actuelle un problème peu exploré. Dans cette thèse, nous avons porté notre attention sur la définition de déformations homotopiques compatibles avec la présence de plusieurs éléments non hiérarchisés dont les relations spatiales peuvent être significatives. Après avoir décrit le cadre théorique retenu pour les images binaires, et après avoir montré sa compatibilité avec les approches les plus fréquentes en imagerie, nous proposons des modélisations des images n-aires appuyées sur ce cadre théorique et dont les objets d'intérêts forment un sous-treillis de l'ensemble des parties de la partition initiale en régions de sémantiques distinctes. Ainsi, nous sommes en mesure de décrire quelques transformations élémentaires des images n-aires respectueuses non seulement des topologies individuelles des différents objets mais aussi des topologies "collectives" qui traduisent les inter-relations des objets.

Cette thèse porte sur l'extraction de représentations géométriques à partir d'images tridimensionnelles. Ces représentations ont d'importantes applications dans les domaines médicaux (examen non invasif et simulation, détection de pathologies, chirurgie assistée par ordinateur, fabrication de prothèses, etc) et biologiques (analyse des structures microscopiques et de leur fonctionnement). Deux approches peuvent être suivies~ : - Les méthodes de reconstruction discrète fournissent rapidement une représentation géométrique de ces données, mais laissent de côté l'aspect segmentation de l'image en ses constituants. Parmi ces méthodes, les plus utilisées sont~ : le marching-cubes, qui construit une surface triangulée, et le suivi de surface, qui délimite une surface digitale. En introduisant des considérations de topologie digitale, nous montrons l'équivalence de ces deux représentations. De cette manière, leurs propriétés respectives peuvent être combinées efficacement. - Les méthodes basées sur les modèles déformables réunissent les opérations de segmentation et de reconstruction en un seul processus~ : le modèle recherche les constituants de l'image en se déformant sous l'action de contraintes externes, issues de l'image, et internes, dérivées de sa structure géométrique. Les modèles existants sont souvent limités à l'extraction de formes simples. Nous proposons un modèle déformable générique, basé sur une triangulation de surface, et capable d'adapter automatiquement la topologie de sa maille aux déformations imposées à sa géométrie. Cette capacité permet au modèle d'appréhender les formes arbitrairement complexes de l'image et de les extraire de l'esquisse aux détails par une approche multi-résolution. Enfin, nous présentons l'application de ce modèle à des données biomédicales de modalités variées. Les résultats sont comparés à ceux obtenus par reconstruction discrète, puis combinés afin de tirer parti des avantages spécifiques des deux approches.

Cette thèse a porté sur l'analyse des électrocardiogrammes en vu de développer de nouvelles méthodes efficaces de classification des arythmies (un outil de diagnostique) et de localisation automatique des battements anormaux en temps réel dans un signal ECG (un outil de surveillance). Les signaux ECG sont prétraités et les battements extraits sont compressés puis analysés à l'aide de la décomposition en ondellettes. La méthode de classification proposée exploite les spécificités du patient en faisant un regroupement contextuel des battements et en utilisant une base de données de battements cardiaques annotés. La méthode utilise également une fonction de similarité pour comparer deux battements donnés. La méthode de localisation exploite aussi la décomposition en ondelettes mais se base sur une partie des données disponibles (set of parsimony) pour détecter automatiquement et temps réel à l'aide d'une fonction masque les battements cardiaques anormaux contenus dans le signal ECG. Les deux méthodes ont été testées sur les signaux électrocardiogrammes du MIT-BIH arrhythmia database et des bons résultats ont été obtenus.

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Cette thèse étudie deux modèles de calcul: les marches quantiques (QW) et les automates cellulaires quantiques (QCA), en vue de les appliquer en simulation quantique. Ces modèles ont deux avantages stratégiques pour aborder ce problème: d'une part, ils constituent un cadre mathématique privilégié pour coder la description du système physique à simuler; d'autre part, ils correspondent à des architectures expérimentalement réalisables.Nous effectuons d'abord une analyse des QWs en tant que schéma numérique pour l'équation de Dirac, en établissant leur borne d'erreur globale et leur taux de convergence. Puis nous proposons une notion de transformée de Lorentz discrète pour les deux modèles, QW et QCA, qui admet une représentation diagrammatique s'exprimant par des règles locales et d'équivalence de circuits. Par ailleurs, nous avons caractérisé la limite continue d'une grande classe de QWs, et démontré qu'elle correspond à une classe d'équations aux dérivées partielles incluant l'équation de Dirac massive en espace-temps courbe de $(1+1)$-dimensions.Finalement, nous étudions le secteur à deux particules des automates cellulaires quantiques. Nous avons trouvé les conditions d'existence du spectre discret (interprétable comme une liaison moléculaire) pour des interactions à courte et longue portée, à travers des techniques perturbatives et d'analyse spectrale des opérateurs unitaires. / This thesis is devoted to the development of two well-known models of computation for their application in quantum computer simulations. These models are the quantum walk (QW) and quantum cellular automata (QCA) models, and they constitute doubly strategic topics in this respect. First, they are privileged mathematical settings in which to encode the description of the actual physical system to be simulated. Second, they offer an experimentally viable architecture for actual physical devices performing the simulation.For QWs, we prove precise error bounds and convergence rates of the discrete scheme towards the Dirac equation, thus validating the QW as a quantum simulation scheme. Furthermore, for both models we formulate a notion of discrete Lorentz covariance, which admits a diagrammatic representation in terms of local, circuit equivalence rules. We also study the continuum limit of a wide class of QWs, and show that it leads to a class of PDEs which includes the Hamiltonian form of the massive Dirac equation in (1+1)-dimensional curved spacetime.Finally, we study the two particle sector of a QCA. We find the conditions for the existence of discrete spectrum (interpretable as molecular binding) for short-range and for long-range interactions. This is achieved using perturbation techniques of trace class operators and spectral analysis of unitary operators.

Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles. / Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets.

Dans cette thèse, nous nous intéressons aux méthodes de la fusion d'images multi focales. Cette technique consiste à fusionner plusieurs images capturées avec différentes distances focales de la même scène. Cela permet d'obtenir une image de meilleure qualité à partir des deux images sources. Nous proposons une méthode de fusion d'images s'appuyant sur les techniques des pyramides Laplaciennes en utilisant comme règle de sélection les transformées d'ondelettes discretes(DWT: Discrete Wavelet Transform). Nous développons, par la suite, deux méthodes de fusion d'images multi focales basée sur la variabilité locale de chaque pixel. Elle tient en compte les informations dans la région environnante des pixels. La première consiste à utiliser la variabilité locale comme information dans la méthode de Dempster-Shafer. La seconde utilise une métrique basée sur la variabilité locale. En effet, la fusion proposée effectue une pondération de chaque pixel par une exponentielle de sa variabilité locale. Une étude comparative entre les méthodes proposées et celles existantes a été réalisée. Les résultats expérimentaux démontrent que nos méthodes proposées donnent des meilleurs fusions, tant dans la perception visuelle que dans l'analyse quantitative. / In this thesis, we are interested in the multi-focus image fusion method. This technique consists of fusing several captured images with different focal lengths of the same scene to obtain an image with better quality than the two source images. We propose an image fusion method based on Laplacian pyramid technique using Discrete Wavelet Transform (DWT) as a selection rule. We then develop two multi-focus image fusion methods based on the local variability of each pixel. It takes into account the information in the surrounding pixel area. The first method is to use local variability as an information in the Dempster-Shafer theory. The second method uses a metric based on local variability. Indeed, the proposed fusion method weighs each pixel by an exponential of its local variability. A comparative study between the proposed methods and the existing methods was carried out. The experimental results show that our proposed methods give better fusions, both in visual perception and in quantitative analysis.

La détection sensible et sélective des métaux lourds, en particulier les métaux detransition, est d’une grande importance pour la santé publique ainsi que pour la surveillancede l’environnement. Les méthodes actuelles de référence, de par leur non portabilité, limitentla possibilité de disposer de mesures à haute résolution spatiale et temporelle. Lesmicrocapteurs optiques offrent un moyen attrayant et pratique pour surmonter ces limitationsde coût global et de temps d’analyse, en permettant la mesure en temps réel sur site.Pour démontrer ce potentiel, ces travaux de thèse sont orientés sur la détermination duchrome hexavalent Cr(VI) en solution à l’aide d’une réaction colorimétrique avec le 1,5-diphénylcarbazide (DPC), permettant de créer un complexe présentant un maximumd’absorption dans le domaine du visible. Ces travaux s’inscrivent dans la volonté dedévelopper un véritable laboratoire sur puce, intégrant la fonction fluidique parélectromouillage sur diélectrique pour créer la réaction colorimétrique, ainsi que la fonctionde mesure par intégration d’un capteur optique dédié à la mesure d’absorption dans desmicrovolumes (< μL). Pour la mesure d'absorption sur de si faibles volumes, l'utilisation demicrorésonateurs vise à augmenter de façon importante le chemin optique effectif et ainsi lasensibilité du capteur.Nous décrivons nos travaux sur la conception, la fabrication de la plateformemicrofluidique digitale ainsi que du résonateur optique en anneaux à des dimensionssubmicroniques par photolithographie par projection. Les matériaux polymères sontprivilégiés pour une intégration totale bas coût à terme, ainsi qu’un substrat verre, dont lespropriétés sont particulièrement adaptées aux applications optiques dans le domaine duvisible. / The selective and sensitive detection of heavy metals, such as transition metals, is ofparamount importance for health and safety an environmental monitoring. Current referencemethods, due to their lack of portability, are limiting factors to obtain high-resolution spatialand temporal data. Optical sensors offer an attractive and convenient way to overcome theselimitations of cost and time per analysis by offering real time, on-site measurementcapabilities.In order to demonstrate this potential, this thesis is focused on the detection and quantificationof hexavalent chromium Cr(VI) in water samples by a colorimetric reaction based on areaction with the 1,5-diphenylcarbazide (DPC), that produces a complex possessing anabsorption maximum in the visible range. This works endorse the goal of creating a true labon-chip, integrating both the fluidic function based on ElectroWetting on Dielectric (EWOD)to create the colorimetric reaction, and the sensing function based on the integration of anoptical sensor able to measure absorption variations in micro-volumes (< μL). In order toobtain sufficient sensitivity on such small volumes, optical microring resonators are used inthis work, due to their ability to enhance the effective optical path length by constructiveinterferences.This thesis describes the conception and fabrication of the EWOD microfluidic platform, aswell as the conception, simulation and fabrication of submicronic microring resonators usingstepper lithography. Polymer materials and glass substrates are selected, due to their greatoptical properties in the visible range, their compatibility with the EWOD platform, and theirintegrability at a reasonable cost.

Afin d’améliorer la durée de vie des micro-relais MEMS ohmiques, plusieurs traitements de surface de films minces d’or sont réalisés pour augmenter leur dureté tout en conservant une résistance électrique de contact faible.Les revêtements ultrafins de ruthénium (20 à 100 nm) déposés sur l’or augmentent la dureté des surfaces de contact d’un facteur 15. L’implantation ionique de bore ou d’azote (3,5 ppm à 10 % atomique) à une profondeur de 100 nm dans le film mince d’or permet d’atteindre un gain en dureté de 75%. Le contrôle (AFM, EBSD et DRX) de la microstructure induite met en évidence le durcissement par solution solide par insertion. Mais au-delà de 1% atomique, les atomes d’azote quittent le réseau cristallin de l’or pour former des précipités de nitrure d’or.L’analyse AFM (rugosité et diamètre) des empreintes résiduelles (quelques μm²) réalisées par nano-indentation sphérique, imitant le cyclage et le fluage des surfaces de contact de ces MEMS, démontre l’apport de ces traitements de surface. De plus, leurs résistances électriques de contact, mesurées par nano-indentation instrumentée reproduisant un micro-contact identique à un dispositif réel, sont similaires à celle de l’or pur.La modélisation discrète mécanique du contact rugueux est ajustée à la mesure de la déformation mécanique de nano-rugosités en comparant les relevés topographiques réalisés par AFM avant et après nano-indentation sphérique. La comparaison entre la modélisation et la mesure de la résistance électrique de contact indique que pour les gammes de force utilisées dans les micro-relais MEMS (inférieure au mN), seule une fraction allant de 2% à 9% de la surface de contact réelle est conductrice. / Ohmic MEMS switches made by gold thin films are promising devices but their mechanical contacts are one of the critical concerns for enhancing reliability. For this reason, surface processes are investigated in this work to improve both mechanical and electrical contact resistance (ECR) of MEMS gold contacts. Ruthenium ultra-thin films (20 to 100 nm) deposited on a top of gold layer increase surface hardness by a factor of fifteen. In parallel, surface implantations of both boron (<10% atomic) or nitrogen (<0.1% atomic) into gold reveals a solid solution hardening by insertion, thus increasing the hardness of initial film by about 75% and 25%, respectively. Notably, above 0.1% atomic of nitrogen, atoms precipitate from the tetra or octahedral sites of gold inducing a decrease of hardness.Static and multi load/unload spherical nano-indentation are performed on treated gold thin films to simulate the mechanical actuation of ohmic MEMS switches. Analysis of residual imprints (about few µm²) from treated surface exhibits both minimal local deformation and adhesion forces that reduce stiction probability. In-situ measurement of ECR for treated gold by instrumented nano-indentation, reproducing the design of MEMS, is in the same range of pure gold-to-gold configuration.A new mechanical discrete model of rough contact is introduced, confronted and validated to the experimental mechanical surface deformation obtained by comparison of AFM images before and after spherical nano-indentation. An electrical discrete model is added and fitted to the ECR measurements. In ohmic MEMS switch load range (< 1 mN), the conductive area is found to be about 2% to 9% of the real contact area.