Cette thèse porte sur l’appariement des formes, et la recherche par forme clef. Elle décrit quatrecontributions à ce domaine. La première contribution est une amélioration de la méthode des nuéesdynamiques pour partitionner au mieux les voxels à l’intérieur d’une forme donnée ; les partitionsobtenues permettent d’apparier les objets par un couplage optimal dans un graphe biparti. Laseconde contribution est la fusion de deux descripteurs, l’un local, l’autre global, par la règle duproduit. La troisième contribution considère le graphe complet, dont les sommets sont les formes dela base ou la requête, et les arêtes sont étiquetées par plusieurs distances, une par descripteur ;ensuite cette méthode calcule par programmation linéaire la combinaison convexe des distancesqui maximise soit la somme des longueurs des plus courts chemins entre la requête et les objetsde la base de données, soit la longueur du plus court chemin entre la requête et l’objet comparé àla requête. La quatrième contribution consiste à perturber la requête avec un algorithme génétiquepour la rapprocher des formes de la base de données, pour un ou des descripteur(s) donné(s) ; cetteméthode est massivement parallèle, et une architecture multi-agent est proposée. Ces méthodes sontcomparées aux méthodes classiques, et ont de meilleures performances, en terme de précision. / This thesis concerns shape matching and shape retrieval. It describes four contributions to thisdomain. The first is an improvement of the k-means method, in order to find the best partition ofvoxels inside a given shape ; these best partitions permit to match shapes using an optimal matchingin a bipartite graph. The second contribution is the fusion of two descriptors, one local, the otherglobal, with the product rule. The third contribution considers the complete graph, the vertices ofwhich are the shapes in the database and the query. Edges are labelled with several distances,one per descriptor. Then the method computes, with linear programming, the convex combinationof distances which maximizes either the sum of the lengths of all shortest paths from the query toall shapes of the database, or the length of the shortest path in the graph from query to the currentshape compared to query. The fourth contribution consists in perturbing the shape query, to make itcloser to shapes in the database, for any given descriptors. This method is massively parallel and amulti-agent architecture is proposed. These methods are compared to classical methods in the field,they achieve better retrieval performances.

Els inhibidors d'entrada del VIH han sorgit recentment com una nova generació de fàrmacs antiretrovirals, els quals bloquegen la unió del virus als co-receptors de membrana CXCR4 i CCR5. S'han desenvolupat diverses molècules petites antagonistes d'aquests co-receptors, algunes de les quals estan actualment en fase d'assaig clínic. No obstant això, donat que no existeixen estructures cristal·logràfiques per aquests co-receptors proteics, és necessari analitzar els modes d'unió d'inhibidors coneguts a la cavitat d'unió extracel·lular dels co-receptors mitjançant experiments de mutagènesi dirigida i estudis computacionals. En general, l'objectiu d'aquestes aproximacions computacionals és cribar un gran nombre de compostos candidats a fàrmacs ràpidament. El cribatge virtual s'ha convertit recentment en un complement útil dels mètodes de cribatge experimentals high-throughput screening per a grans llibreries de compostos. Per tant, en aquesta tesi s'ha portat a terme un protocol de cribatge virtual, mitjançant aproximacions basades en el receptor i en lligands actius coneguts, amb la finalitat de trobar antagonistes de CXCR4 i CCR5 que puguin servir com a potencials inhibidors d'entrada del VIH.Per al cribatge virtual basat en el receptor, s'han millorat els models dels co-receptors CXCR4 i CCR5 construïts a la secció de disseny molecular de l'IQS, i s'han portat a terme assajos preliminars de mode d'unió utilitzant aquests models i lligands coneguts d'elevada afinitat. Així mateix, s'ha analitzat el comportament en el cribatge virtual i en el post-processat de resultats de docking de diferents fingerprints d'interacció en comparació amb els resultats obtinguts per un nou fingerprint d'interacció (APIF) desenvolupat a la secció de disseny molecular de l'IQS.Per al cribatge virtual basat en lligands, s'han comparat models farmacofòrics i diverses aproximacions basades en la forma i propietats moleculars utilitzant lligands d'elevada afinitat com a molècules de referència. A més, s'ha desenvolupat una nova aproximació basada en la forma molecular, la qual s'ha utilitzat per a estudiar en profunditat la hipòtesi de la multi-regió d'unió de la cavitat d'unió extracel·lular del co-receptor CCR5.Tots els mètodes, ja siguin basats en el receptor o en lligands coneguts, s'han aplicat en primer lloc de manera retrospectiva utilitzant una extensa base de dades d'inhibidors de CXCR4/CCR5 i suposats inactius, similars en propietats als actius, recopilada en aquesta tesi. Per a cada receptor, la quimioteca ha estat cribada utilitzat inhibidors coneguts, S'han analitzat els factors d'enriquiment i la diversitat a les llistes finals de hits. A més, s'han portat a terme anàlisis ROC per a ambdós inhibidors de CXCR4 i CCR5 amb la finalitat de comparar l'habilitat del nou algoritme basat en la igualtat de formes de lligands amb la resta d'aproximacions de cribatge utilitzades.Una vegada validades les diferents aproximacions de cribatge i seleccionats els millors paràmetres per a cadascuna d'elles, s'han aplicat les eines de cribatge virtual de manera prospectiva sobre una quimioteca combinatòria dissenyada a la secció de disseny molecular de l'IQS, així com tècniques de disseny de novo de lligands per tal d'identificar nous bloquejadors de l'entrada del VIH a les cèl·lules. / Los inhibidores de entrada del VIH han surgido recientemente como una nueva generación de fármacos antiretrovirales, los cuales bloquean la unión del virus con los co-receptores de membrana CXCR4 y CCR5. Se han desarrollado diversas moléculas pequeñas antagonistas de estos co-receptores, algunas de las cuales están actualmente en fase de ensayo clínico. Sin embargo, dado que no existen estructuras cristalográficas para estos co-receptores proteicos, es necesario analizar los modos de unión de inhibidores conocidos a la cavidad de unión extracelular de los co-receptores mediante experimentos de mutagénesis dirigida y estudios computacionales. En general, el objetivo de estas aproximaciones computacionales es cribar un gran número de compuestos candidatos a fármacos rápidamente. El cribado virtual se ha convertido recientemente en un complemento útil de los métodos de cribado experimentales high-throughput screening para grandes librerías de compuestos. Por lo tanto, en esta tesis se ha llevado a cabo un protocolo de cribado virtual, mediante aproximaciones basadas en el receptor y en ligandos activos conocidos, con el fin de encontrar antagonistas de CXCR4 y CCR5 que puedan servir como potenciales inhibidores de entrada del VIH.Para el cribado virtual basado en el receptor, se han mejorado los modelos de los co-receptores CXCR4 y CCR5 construidos en la sección de diseño molecular del IQS, y se han llevado a cabo ensayos preliminares de modo de unión utilizando estos modelos y ligandos conocidos de elevada afinidad. Asimismo, se ha analizado el comportamiento en el cribado virtual y en el post-procesado de resultados de docking de diferentes fingerprints de interacción en comparación con los resultados obtenidos por un nuevo fingerprint de interacción (APIF) desarrollado en la sección de diseño molecular del IQS.Para el cribado virtual basado en ligandos, se han comparado modelos farmacofóricos y diversas aproximaciones basadas en la forma y propiedades moleculares utilizando ligandos de elevada afinidad como moléculas de referencia. Además, se ha desarrollado una nueva aproximación basada en la forma molecular, la cual se ha utilizado para estudiar en profundidad la hipótesis de la multi-región de unión de la cavidad de unión extracelular del co-receptor CCR5.Todos los métodos, ya sean basados en el receptor o en ligandos conocidos, se han aplicado en primer lugar de manera retrospectiva utilizando una extensa base de datos de inhibidores de CXCR4/CCR5 y supuestos inactivos, similares en propiedades a los activos, recopilada en esta tesis. Para cada receptor, la quimioteca ha sido cribada utilizando inhibidores conocidos, Se han analizado los factores de enriquecimiento y la diversidad en las listas finales de hits. Además, se han llevado a cabo análisis ROC para ambos inhibidores de CXCR4 y CCR5 con el fin de comparar la habilidad del nuevo algoritmo basado en la igualdad de formas de ligandos con el resto de aproximaciones de cribado utilizadas.Una vez validadas las diferentes aproximaciones de cribado y seleccionados los mejores parámetros para cada una de ellas, se han aplicado las herramientas de cribado virtual de manera prospectiva sobre una quimioteca combinatoria diseñada en la sección de diseño molecular del IQS, así como técnicas de diseño de novo de ligandos para identificar nuevos bloqueadores de la entrada del VIH a las células. / HIV entry inhibitors have emerged as a new generation of antiretroviral drugs that block viral fusion with the CXCR4 and CCR5 membrane co-receptors. Several small molecule antagonists for these co-receptors have been developed, some of which are currently in clinical trials. However, because no crystal structures for the co-receptor proteins are available, the binding modes of the known inhibitors within the co-receptor extracellular pockets need to be analyzed by means of site-directed mutagenesis and computational experiments. Generally, the objective of these computational approaches is to screen large numbers of candidate drug compounds rapidly. Virtual screening has recently become a useful complement to laboratory-based high-throughput screening methods for large libraries of compounds. Hence, in this thesis, a virtual screening protocol, using several receptor-based and ligand-based approaches, has been performed to find CXCR4 and CCR5 antagonists that could potentially serve as HIV entry inhibitors.For receptor-based virtual screening, homology models of CXCR4 and CCR5 co-receptors built in our research group have been improved, and preliminary binding mode analyses using these models and high affinity known ligands have been carried out. Also, the performance in virtual screening and docking post-processing of different interaction fingerprints, compared to the results obtained with a new interaction fingerprint (APIF) developed in our research group, has been analysed.For ligand-based virtual screening, pharmacophore modelling and several shape-based and property-based molecular comparison approaches have been compared, using high-affinity ligands as query molecules. Also, a novel consensus shape-based virtual screening approach has been developed and used to investigate and add further evidence for multiple binding sites within the CCR5 extracellular pocket hypothesis.All the receptor-based and ligand-based methods have been firstly applied in a retrospective virtual screening, using a large database of known CXCR4/CCR5 inhibitors and similar presumed inactive molecules assembled in this thesis. For each receptor, the library has been queried using known binders, and the enrichment factors and diversity of the resulting virtual hit lists have been analyzed. Moreover, receiver-operator-characteristic analyses for both CXCR4 and CCR5 inhibitors have been carried out in order to compare the performance of the new consensus shape matching algorithm with the other screening approaches used. Once the different virtual screening approaches have been validated and the best parameters for each one have been selected, prospective virtual screening of a combinatorial library designed by our research group and de novo design methods have been applied to identify new HIV entry blockers.

Les travaux effectués durant cette thèse portent sur l’appariement de formes planes basé sur une squelettisation hiérarchique. Dans un premier temps, nous avons abordé la création d’un squelette de forme grâce à un algorithme associant des outils de la géométrie discrète et des filtres. Cette association permet d’acquérir un squelette regroupant les propriétés désirées dans le cadre de l’appariement. Néanmoins, le squelette obtenu reste une représentation de la forme ne différenciant pas les branches représentant l’allure générale de celles représentant un détail de la forme. Or, lors de l’appariement, il semble plus intéressant d’associer des branches ayant le même ordre d’importance, mais aussi de donner plus de poids aux associations décrivant un aspect global des formes. Notre deuxième contribution porte sur la résolution de ce problème. Elle concerne donc la hiérarchisation des branches du squelette, précédemment créé, en leur attribuant une pondération reflétant leur importance dans la forme. À cet effet, nous lissons progressivement une forme et étudions la persistance des branches pour leur attribuer un poids. L’ultime étape consiste donc à apparier les formes grâce à leur squelette hiérarchique modélisé par un hypergraphe. En d’autres termes, nous associons les branches deux à deux pour déterminer une mesure de dissimilarité entre deux formes. Pour ce faire, nous prenons en compte la géométrie des formes, la position relative des différentes parties des formes ainsi que de leur importance. / The works performed during this thesis focuses on the matching of planar shapes based on a hierarchical skeletonisation. First, we approached the creation of a shape skeleton using an algorithm combining the tools of discrete geometry and filters. This combination allows to acquire a skeleton gathering the desired properties in the context of matching. Nevertheless, the resulting skeleton remains a representation of the shape, which does not differentiate branches representing the general shape of those coming from a detail of the shape. But when matching, it seems more interesting to pair branches of the same order of importance, but also to give more weight to associations describing an overall appearance of shapes. Our second contribution focuses on solving this problem. It concerns the prioritization of skeletal branches, previously created by assigning a weight reflecting their importance in shape. To this end, we gradually smooth a shape and study the persistence of branches to assign a weight. The final step is to match the shapes with their hierarchical skeleton modeled as a hypergraph. In other words, we associate the branches two by two to determine a dissimilarity measure between two shapes. To do this, we take into account the geometry of the shapes, the relative position of different parts of the shapes and their importance.

Cette thèse porte sur la reconnaissance et l’appariement de formes 3D pour des systèmes intelligents de vision par ordinateur. Elle décrit deux contributions principales à ce domaine. La première contribution est une implémentation d'un nouveau descripteur de formes construit à la base de la géométrie spectrale de l'opérateur de Laplace-Beltrami ; nous proposons une signature de point globale avancée (AGPS). Ce descripteur exploite la structure intrinsèque de l'objet et organise ses informations de manière efficace. De plus, AGPS est extrêmement compact puisque seulement quelques paires propres étaient nécessaires pour obtenir une description de forme précise. La seconde contribution est une amélioration de la signature du noyau d'onde ; nous proposons une signature du noyau d'onde optimisée (OWKS). La perfectionnement est avec un algorithme heuristique d'optimisation par essaim de particules modifié pour mieux rapprocher une requête aux autres formes appartenant à la même classe dans la base de données. L'approche proposée améliore de manière significative la capacité discriminante de la signature. Pour évaluer la performance de l'approche proposée pour la récupération de forme 3D non rigide, nous comparons le descripteur global d'une requête aux descripteurs globaux du reste des formes de l'ensemble de données en utilisant une mesure de dissimilarité et trouvons la forme la plus proche. Les résultats expérimentaux sur différentes bases de données de formes 3D standards démontrent l'efficacité des approches d'appariement et de récupération proposées par rapport aux autres méthodes de l'état de l'art. / This thesis concerns recognition and matching of 3D shapes for intelligent computer vision systems. It describes two main contributions to this domain. The first contribution is an implementation of a new shape descriptor built on the basis of the spectral geometry of the Laplace-Beltrami operator; we propose an Advanced Global Point Signature (AGPS). This descriptor exploits the intrinsic structure of the object and organizes its information in an efficient way. In addition, AGPS is extremely compact since only a few eigenpairs were necessary to obtain an accurate shape description. The second contribution is an improvement of the wave kernel signature; we propose an optimized wave kernel signature (OWKS). The refinement is with a modified particle swarm optimization heuristic algorithm to better match a query to other shapes belonging to the same class in the database. The proposed approach significantly improves the discriminant capacity of the signature. To assess the performance of the proposed approach for nonrigid 3D shape retrieval, we compare the global descriptor of a query to the global descriptors of the rest of shapes in the dataset using a dissimilarity measure and find the closest shape. Experimental results on different standard 3D shape benchmarks demonstrate the effectiveness of the proposed matching and retrieval approaches in comparison with other state-of-the-art methods.

Cette thèse est consacrée à la conception, au développement et à l'analyse de méthodes de déformation de maillage pour la modélisation, le traitement et la comparaison de forme -telles que l'appariement et la reconstruction de surface- ainsi qu’à la conception d'une méthode numérique robuste pour la reconstruction faciale. La reconstruction faciale tridimensionnelle consiste à estimer un visage numérique à partir de la seule donnée de son crâne sec. Il s'agit d'un défi en médecine légale et en anthropologie. La contribution majeure de cette thèse est la conception d'une nouvelle méthode pour l'appariement de forme, en s'appuyant sur des techniques d'optimisation de forme. Sous la seule hypothèse que les deux formes ont la même topologie, la transformation cherchée s'obtient comme une suite de déplacements élastiques, solutions d'un problème de minimisation d’énergie basée sur une fonction distance signée.Nous proposons également une méthode de drapage permettant la génération d'un modèle de surface fermée à partir d'un maillage source. La méthode repose sur une technique d’évolution de maillage utilisant les équations de l'élasticité linéaire. Un maillage modèle est itérativement déformé pour générer une séquence de formes qui s’approche de plus en plus de la triangulation source. Dans la deuxième partie de ce manuscrit, nous nous intéressons au développement d’une méthode automatique de reconstruction faciale numérique. En s’appuyant sur des techniques de déformation continue telles que le ‘morphing' et le ’warping’, l'approche proposée est intégrée par des connaissances anthropologiques et mécaniques. / This thesis is devoted to the conception, the development and the analysis of mesh deformation strategies for shape modeling, processing and comparison -as shape matching and surface reconstruction- and, in a rather independent concern, for devising a robust computational method for facial reconstruction. Facial reconstruction is about the estimation of a facial shape from the sole datum of the underlying skull and is a challenging problem in anthropology and forensic science. The main contribution of the thesis is the design of a novel method for shape matching, borrowing techniques from the shape optimization context. Under the sole assumption that the two shapes share the same topology, the desired mapping is achieved as a sequence of elastic displacements by minimizing an energy functional based on a signed distance function. Several numerical examples are presented to show the efficiency of the method.Also, a novel method for generating a closed surface mesh model of an initially non-closed source mesh model is developed. The method relies on an original PDE-based mesh evolution technique. A template shape is iteratively deformed, producing a sequence of shapes that get 'closer and closer' to the source triangulation.The second part of the manuscript deals with the development of a landmark-free, fully automated method for digital facial reconstruction. Based on techniques of continuous deformation as 'morphing' and 'warping', the proposed approach is integrated with anthropological assumptions and mechanical models.

A significant amount of research in the field of stereo vision has been published in the past decade. Considerable progress has been made in improving accuracy of results as well as achieving real-time performance in obtaining those results. Although much of the literature does not address it, many applications are sensitive to the tradeoff between accuracy and speed that exists among stereo vision algorithms. Overall, this work aims to organize existing efforts and encourage new ones in the development of stereo vision algorithms for resource limited systems. It does this through a review of the status quo as well as providing both software and hardware designs of new stereo vision algorithms that offer an efficient tradeoff between speed and accuracy. A comprehensive review and analysis of stereo vision algorithms is provided with specific emphasis on real-time performance and suitability for resource limited systems. An attempt has been made to compile and present accuracy and runtime performance data for all stereo vision algorithms developed in the past decade. The tradeoff in accuracy that is typically made to achieve real-time performance is examined with an example of an existing highly accurate stereo vision that is modified to see how much speedup can be achieved. Two new stereo vision algorithms, GA Spline and Profile Shape Matching, are presented with a hardware design of the latter also being provided, making Profile Shape Matching available to both embedded processor-based and programmable hardware-based resource limited systems.

Image segmentation is one of the most difficult tasks in image processing. Segmentation algorithms are generally based on searching a region where pixels share similar gray level intensity and satisfy a set of defined criteria. However, the segmented region cannot be used directly for partial image retrieval. In this dissertation, a Contour Based Image Structure (CBIS) model is introduced. In this model, images are divided into several objects defined by their bounding contours. The bounding contour structure allows individual object extraction, and partial object matching and retrieval from a standard CBIS image structure. The CBIS model allows the representation of 3D objects by their bounding contours which is suitable for parallel implementation particularly when extracting contour features and matching them for 3D images require heavy computations. This computational burden becomes worse for images with high resolution and large contour density. In this essence we designed two parallel algorithms; Contour Parallelization Algorithm (CPA) and Partial Retrieval Parallelization Algorithm (PRPA). Both algorithms have considerably improved the performance of CBIS for both contour shape matching as well as partial image retrieval. To improve the effectiveness of CBIS in segmenting images with inhomogeneous backgrounds we used the phase congruency invariant features of Fourier transform components to highlight boundaries of objects prior to extracting their contours. The contour matching process has also been improved by constructing a fuzzy contour matching system that allows unbiased matching decisions. Further improvements have been achieved through the use of a contour tailored Fourier descriptor to make translation and rotation invariance. It is proved to be suitable for general contour shape matching where translation, rotation, and scaling invariance are required. For those images which are hard to be classified by object contours such as bacterial images, we define a multi-level cosine transform to extract their texture features for image classification. The low frequency Discrete Cosine Transform coefficients and Zenike moments derived from images are trained by Support Vector Machine (SVM) to generate multiple classifiers.

Cette thèse traite d'une méthodologie de Reverse Engineering (RE) d'assemblages mécaniques à partir de données hétérogènes dans un contexte routinier. Cette activité consiste à partir d'un produit ou d'un assemblage, à récupérer la donnée numérique en partant de la donnée physique dans le but de reconstruire sa ma­quette numérique. Plusieurs techniques de numérisation peuvent être employées et permettent de générer des données de différents types (ex : nuage de points, photographies). Ces dernières sont utilisées comme données d'entrée à notre pro­cessus de RE et peuvent aussi être associées à des données liées au produit, exis­tantes au préalable, telles que des mises en plan ou encore une version antérieure de la maquette numérique du produit. Le traitement de l'ensemble de ces don­nées, dites "hétérogènes", requiert une solution qui soit capable de gérer d'une part, l'hétérogénéité des données et des informations qu'elles contiennent et d'autre part, l'incomplétude de certaines données qui est liée au bruit ou à la technologie utilisée pour numériser l'assemblage (ex : scanner ou photographie). Enfin la pertinence des informations extraites lors de la phase de traitement doit permettre, dans cer­tains cas, de générer des modèles CAO paramétrés, propres à l'activité de RE de l'entreprise ou du domaine d'application. L'état de l'art sur la reconnaissance de formes dans des données hétérogènes ainsi que sur la gestion de connaissances dans le cadre d'activités routinières, pro­pose des approches qui traitent soit d'un seul type de données, soit du RE de pièce unique ou soit elles ne permettent pas d'obtenir un modèle CAO qui soit exploitable (paramétrage géométrique des entités) pour une activité de RE. Cette thèse propose une méthodologie nommée Heterogeneous Data Integration for Reverse Engineering (HDI-RE) et qui se décompose en trois étapes : la seg­mentation, la signature et la comparaison avec une base de connaissances. Le but de cette méthode est d'automatiser le processus de RE et notamment en ce qui concerne les étapes de reconnaissance de composants dans les données d'entrée et d'aide à la reconstruction de modèles CAO (paramétrés ou non) en récupérant des informations géométriques et topologiques dans des données d'entrée. Pour cela, ces dernières sont segmentées afin d'en extraire des informations qui sont en­ suite formalisées sous la forme de signatures. Les signatures générées sont ensuite comparées à une base de connaissances comportant un ensemble de signatures de différents types et appartenant à des produits ou objets déjà connus. Le calcul des similarités issu de la comparaison permet d'identifier les composants présents dans les données en entrée. L'apport scientifique de ces travaux repose principalement sur l'utilisation de sig­natures qui, en fonction du souhait de l'utilisateur, permettent de reconstruire une maquette numérique en sortie du processus de RE avec trois niveaux d'information : un niveau global, un niveau géométrique et topologique ou un niveau fonctionnel. Par rapport à chaque niveau et du type de données traité, un mécanisme de signa­ture dédié est proposé. / This thesis deals with a methodology of Reverse Engineering (RE) of mechanical assemblies from heterogeneous data in a routine context. This activity consists, from the existing data of a part or an assembly, in rebuilding their digital mock-up. The data used in entrance of our process of RE can be drawings, photos, points clouds or another existing version of the digital mock-up. The proposed approach, called Heterogeneous Data Integration for Reverse Engineering (HDI-RE), is divided into three steps : the segmentation, the signature and the comparison of the initial data with a knowledge database. The signatures of the studied object are compared with the signatures of the same type existing in the database in order to extract components ordered by similarity (distance with the object). The parameterized digital mock-up which is the most similar to the object is then extracted and its parameters identified from the initial data. Data set processing, called "heterogeneous" data, requires a solution which is able to manage on one hand, the heterogeneousness of the data and the information which they contain and on the other hand, the incompleteness of some data which are in link with the noise (into points cloud) or with the technology used to digitize the assembly (ex: scanner or photography).

Casamento de padrões de pontos é um problema fundamental em reconhecimento de padrões. O objetivo é encontrar uma correspondência entre dois conjuntos de pontos, associados a características relevantes de objetos ou entidades, mapeando os pontos de um conjunto no outro. Este problema está associado a muitas aplicações, como por exemplo, reconhecimento de objetos baseado em modelos, imagens estéreo, registro de imagens, biometria, entre outros. Para encontrar um mapeamento, os objetos são codificados por representações abstratas, codificando as características relevantes consideradas na comparação entre pares de objetos. Neste trabalho, objetos são representados por grafos, codificando tanto as características `locais\' quanto as relações espaciais entre estas características. A comparação entre objetos é guiada por uma formulação de atribuição quadrática, que é um problema NP-difícil. Para estimar uma solução, duas técnicas de casamento entre grafos são propostas: uma baseada em grafos auxiliares, chamados de grafos deformados; e outra baseada em representações `esparsas\', campos aleatórios de Markov e propagação de crenças. Devido as suas respectivas limitações, as abordagens são adequadas para situações específicas, conforme mostrado neste documento. Resultados envolvendo as duas abordagens são ilustrados em quatro importantes aplicações: casamento de imagens de gel eletroforese 2D, segmentação interativa de imagens naturais, casamento de formas, e colorização assistida por computador. / Point set matching is a fundamental problem in pattern recognition. The goal is to match two sets of points, associated to relevant features of objects or entities, by finding a mapping, or a correspondence, from one set to another set of points. This issue arises in many applications, e.g. model-based object recognition, stereo matching, image registration, biometrics, among others. In order to find a mapping, the objects can be encoded by abstract representations, carrying relevant features which are taken into account to compare pairs of objects. In this work, graphs are adopted to represent the objects, encoding their `local\' features and the spatial relations between these features. The comparison of two given objects is guided by a quadratic assignment formulation, which is NP-hard. In order to estimate the optimal solution, two approximations techniques, via graph matching, are proposed: one is based on auxiliary graphs, called deformed graphs; the other is based on `sparse\' representations, Markov random fields and belief propagation. Due to their respective limitations, each approach is more suitable to each specific situation, as shown in this document. The quality of the two approaches is illustrated on four important applications: 2D electrophoresis gel matching, interactive natural image segmentation, shape matching, and computer-assisted colorization.

Casamento de padrões de pontos é um problema fundamental em reconhecimento de padrões. O objetivo é encontrar uma correspondência entre dois conjuntos de pontos, associados a características relevantes de objetos ou entidades, mapeando os pontos de um conjunto no outro. Este problema está associado a muitas aplicações, como por exemplo, reconhecimento de objetos baseado em modelos, imagens estéreo, registro de imagens, biometria, entre outros. Para encontrar um mapeamento, os objetos são codificados por representações abstratas, codificando as características relevantes consideradas na comparação entre pares de objetos. Neste trabalho, objetos são representados por grafos, codificando tanto as características `locais\' quanto as relações espaciais entre estas características. A comparação entre objetos é guiada por uma formulação de atribuição quadrática, que é um problema NP-difícil. Para estimar uma solução, duas técnicas de casamento entre grafos são propostas: uma baseada em grafos auxiliares, chamados de grafos deformados; e outra baseada em representações `esparsas\', campos aleatórios de Markov e propagação de crenças. Devido as suas respectivas limitações, as abordagens são adequadas para situações específicas, conforme mostrado neste documento. Resultados envolvendo as duas abordagens são ilustrados em quatro importantes aplicações: casamento de imagens de gel eletroforese 2D, segmentação interativa de imagens naturais, casamento de formas, e colorização assistida por computador. / Point set matching is a fundamental problem in pattern recognition. The goal is to match two sets of points, associated to relevant features of objects or entities, by finding a mapping, or a correspondence, from one set to another set of points. This issue arises in many applications, e.g. model-based object recognition, stereo matching, image registration, biometrics, among others. In order to find a mapping, the objects can be encoded by abstract representations, carrying relevant features which are taken into account to compare pairs of objects. In this work, graphs are adopted to represent the objects, encoding their `local\' features and the spatial relations between these features. The comparison of two given objects is guided by a quadratic assignment formulation, which is NP-hard. In order to estimate the optimal solution, two approximations techniques, via graph matching, are proposed: one is based on auxiliary graphs, called deformed graphs; the other is based on `sparse\' representations, Markov random fields and belief propagation. Due to their respective limitations, each approach is more suitable to each specific situation, as shown in this document. The quality of the two approaches is illustrated on four important applications: 2D electrophoresis gel matching, interactive natural image segmentation, shape matching, and computer-assisted colorization.