Les travaux de cette thèse se situent dans la cadre des approches structurelles pour la recon- naissance de formes. Plus précisément, nous avons porté notre choix sur les graphes. Le choix de la représentation structurelle est justifié par la grande capacité représentative des graphes par rapport à la représentation statistique (i.e. vecteurs). La première étape qui intervient dans l'étude de l'application des graphes dans le domaine des images est de définir une stratégie d'extraction de graphes représentatives d'images. Ensuite, il faut définir des fonctions néces- saires à la manipulation des bases de graphes. L'une des fonctions cruciales pour manipuler les graphes est la fonction de calcul des distances entre les graphes. En effet, le calcul de distances entre les graphes est un problème ouvert dans la littérature. De plus, il est considéré comme NP-complet. La plupart des solutions proposées dans la littérature présentent différentes limites d'utilisation telle que la taille des graphes, la prise en compte d'attributs, le temps de calcul. Outre la distance, le domaine des graphes souffre d'un manque d'algorithmes de classification (non-)supervisée appropriés. Dans ce sens, cette thèse présente un ensemble de contributions dont l'objectif est l'indexation de graphes. En premier lieu, nous montrons expérimentalement que choix de la représentation sous forme de graphes a un impact sur les performances. Ensuite, nous proposons une nouvelle approximation de la distance d'édition de graphes basée sur la no- tion de signature de noeuds. Nous introduisons aussi un algorithme de plongement de graphes. Cet algorithme consiste à représenter chaque graphe par un vecteur dans un espace euclidien. Ceci nous permet d'appliquer les algorithmes de classification des vecteurs sur les graphes par le biais du plongement. Dans le domaine de la classification non-supervisée (clustering), nous proposons un nouvel algorithme basé sur la notion du graphe médian et la notion du mean-shift. Enfin, nous proposons, une nouvelle méthode d'indexation de graphes basée sur la structure d'hypergraphe. Cette méthode permet aussi bien l'indexation que la navigation dans une base d'images représentées sous forme de graphes.

Cette thèse s’intéresse à une problématique ayant de nombreuses applications pratiques, à savoir la comparaison automatique d’objets et l’évaluation de la similarité. Lorsque les objets sont modélisés par des graphes, ce problème de comparaison automatique d’objets se ramène à un problème d’appariement de graphes, c’est-à-dire, chercher une mise en correspondance entre les sommets des graphes permettant de retrouver le plus grand nombre de caractéristiques communes. Différentes classes existent allant de la plus restrictive à la plus générale. Dans la plus restrictive isomorphisme de (sous-) graphes, il s’agit de chercher un appariement exact entre les sommets des graphes de manière à prouver que les deux graphes possèdent une structure identique ou que l’un d’eux est inclus dans l’autre, un sommet étant apparié avec au plus un sommet. Dans la plus générale (appariement multivoque), l’objectif n’est plus de trouver un appariement exact mais le meilleur appariement, c’est-à-dire, celui qui préserve un maximum de sommets et d’arcs, un sommet pouvant être apparié à un ensemble de sommets. Nous nous intéressons au problème de la recherche du meilleur appariement multivoque, ce problème étant plus général que les problèmes d’appariement restrictifs. Sa résolution est clairement un défi tant par la difficulté du problème que par l’importance de ses applications. Pour relever ce défi, nous proposons d’étudier les capacités de l’optimisation par colonies de fourmis (ACO). Notre étude est menée dans deux contextes : un contexte statique, où le problème est figé, et un contexte dynamique, où les graphes à comparer, les contraintes à respecter ainsi que les critères définissant la qualité des appariements changent régulièrement de sorte que la solution doit être dynamiquement adaptée. Un premier objectif, de cette thèse, est de proposer l’algorithme ACO générique pour la résolution des problèmes d’appariement de graphes. Plusieurs points clés sont étudiés dans cet algorithme, à savoir : l’influence des paramètres sur la qualité des solutions construites, l’influence de la stratégie phéromonale et du facteur heuristique, et l’hybridation avec une technique de recherche locale. Un deuxième objectif est de proposer un algorithme ACO générique pour résoudre des problèmes d’optimisation dynamiques. L’algorithme proposé est appliqué et expérimenté à quelques problèmes dynamiques, à savoir : l’appariement de graphes, le problème du sac à dos multidimensionnel, et le voyageur de commerce / The thesis addresses the problematic of comparing objects and similarity measuring. If objects are described by graphs, so that measuring objects similarity turns into determining graph similarity, i.e., matching graph vertices to identify their common features and their differences. Different classes of graph matching have been proposed going on the most restrictive ones to the most general. In restrictive graph matching (graph or sub-graph isomorphism), the objective is to show graph equivalence or inclusion, a vertex in a graph may be matched with one vertex at most on the other graph. In general graph matching (multivalent matching), the goal is not yet to find an “exact” matching (a matching which preserves all vertices and edges), but to look for a “best” matching (a matching which preserves a maximum number of vertices and edges), a vertex in one graph may be matched with a set of vertices in the other graph. In our work, we consider the problem of searching the best multivalent matching which is a NP-hard optimization problem. More precisely, we propose to investigate the ability if the ant colony optimization meta-heuristic (ACO). Two cases are considered in our study: the static case where the problem remains invariant through time and the dynamic case where graphs to compare constrained to satisfy and the criterions defining matching quality may change over the time, so that solutions must be dynamically adapted to the changes. A first goal of this thesis is to propose a generic ACO algorithm for solving graph matching problems. Different key points, like the pheromonal strategy to be used, the heuristic factor and the use of a local search procedure, are studied. A second goal of this work is to propose a generic ACO algorithm for solving dynamic optimization problems. The proposed algorithm will be applied and experimentally studied on three different dynamic problems: graph matching problem, multi-dimensional knapsack problem and the travelling salesman problem

L'objectif de cette thèse est d'instrumentaliser des moyens, centrés utilisateur, de représentation, d'acquisition, d'enrichissement et d'exploitation des métadonnées décrivant des documents multimédias socio-personnels. Afin d'atteindre cet objectif, nous avons proposé un modèle d'annotation, appelé SeMAT avec une nouvelle vision du contexte de prise de vue. Nous avons proposé d'utiliser des ressources sémantiques externes telles que GeoNames , et Wikipédia pour enrichir automatiquement les annotations partant des éléments de contexte capturés. Afin d'accentuer l'aspect sémantique des annotations, nous avons modélisé la notion de profil social avec des outils du web sémantique en focalisant plus particulièrement sur la notion de liens sociaux et un mécanisme de raisonnement permettant d'inférer de nouveaux liens sociaux non explicités. Le modèle proposé, appelé SocialSphere, construit un moyen de personnalisation des annotations suivant la personne qui consulte les documents (le consultateur). Des exemples d'annotations personnalisées peuvent être des objets utilisateurs (e.g. maison, travail) ou des dimensions sociales (e.g. ma mère, le cousin de mon mari). Dans ce cadre, nous avons proposé un algorithme, appelé SQO, permettant de suggérer au consultateur des dimensions sociales selon son profil pour décrire les acteurs d'un document multimédia. Dans la perspective de suggérer à l'utilisateur des évènements décrivant les documents multimédias, nous avons réutilisé son expérience et l'expérience de son réseau de connaissances en produisant des règles d'association. Dans une dernière partie, nous avons abordé le problème de correspondance (ou appariement) entre requête et graphe social. Nous avons proposé de ramener le problème de recherche de correspondance à un problème d'isomorphisme de sous-graphe partiel. Nous avons proposé un algorithme, appelé h-Pruning, permettant de faire une correspondance rapprochée entre les nœuds des deux graphes : motif (représentant la requête) et social. Pour la mise en œuvre, nous avons réalisé un prototype à deux composantes : web et mobile. La composante mobile a pour objectif de capturer les éléments de contexte lors de la création des documents multimédias socio-personnels. Quant à la composante web, elle est dédiée à l'assistance de l'utilisateur lors de son annotation ou consultation des documents multimédias socio-personnels. L'évaluation a été effectuée en se servant d'une collection de test construite à partir du service de médias sociaux Flickr. Les tests ont prouvé : (i) l'efficacité de notre approche de recherche dans le graphe social en termes de temps d'exécution ; (ii) l'efficacité de notre approche de suggestion des événements (en effet, nous avons prouvé notre hypothèse en démontrant l'existence d'une cooccurrence entre le contexte spatio-temporel et les événements) ; (iii) l'efficacité de notre approche de suggestion des dimensions sociales en termes de temps d'exécution.

Dans cette thèse, nous présentons tout d'abord une contribution visant à pallier ce problème de robustesse pour la reconnaissance d'instances, puis une extension directe de cette contribution à la reconnaissance et la localisation de classes d'objets. Dans un premier temps, nous avons développé une méthode inspiré de l'appariement de graphe (i.e. graph matching) afin de traiter le problème de la reconnaissance rapide d'instances d'objets spécifiques dans des conditions bruitées. Cette méthode permet de rajouter facilement un nombre quelconque d’autres types de caractéristiques locales (e.g. contours, textures…) moins affectées par le bruit tout en contournant le problème de la normalisation et sans pénaliser la vitesse de détection. Nos expériences sur plusieurs bases de test ont montré la pertinence de notre approche. Notre approche est globalement légèrement moins robuste à l'occultation que les approches existantes, mais elle produit des performances supérieures aux approches standard en conditions bruitées. Dans un second temps, nous avons développé une approche pour la détection de classes d'objets dans le même esprit que celui du sac de mots visuels. Pour cela, nous utilisons nos cascades de micro-classifieurs pour reconnaître des mots visuels plus distinctifs que les mots basés simplement sur des points d'intérêts. L'apprentissage se divise en deux parties: dans un premier temps, nous générons des cascades de micro-classifieurs servant à reconnaître des parties locales des images modèles ; puis dans un second temps, nous utilisons un classifieur afin de modéliser la frontière de décision entre les images de classe et celles de non-classe. Nous montrons que l'association de mots classiques (à partir de points d'intérêts) et de nos mots plus distincts produit une amélioration significative des performances pour un temps de calcul assez faible. / In this thesis, we first present a contribution to overcome this problem of robustness for the recognition of object instances, then we straightly extend this contribution to the detection and localization of classes of objects. In a first step, we have developed a method inspired by graph matching to address the problem of fast recognition of instances of specific objects in noisy conditions. This method allows to easily combine any types of local features (eg contours, textures ...) less affected by noise than keypoints, while bypassing the normalization problem and without penalizing too much the detection speed. Unlike other methods based on a global rigid transformation, our approach is robust to complex deformations such as those due to perspective or those non-rigid inherent to the model itself (e.g. a face, a flexible magazine). Our experiments on several datasets have showed the relevance of our approach. It is overall slightly less robust to occlusion than existing approaches, but it produces better performances in noisy conditions. In a second step, we have developed an approach for detecting classes of objects in the same spirit as the bag-of-visual-words model. For this we use our cascaded micro-classifiers to recognize visual words more distinctive than the classical words simply based on visual dictionaries. Training is divided into two parts: First, we generate cascades of micro-classifiers for recognizing local parts of the model pictures and then in a second step, we use a classifier to model the decision boundary between images of class and those of non-class. We show that the association of classical visual words (from keypoints patches) and our disctinctive words results in a significant improvement. The computation time is generally quite low, given the structure of the cascades that minimizes the detection time and the form of the classifier is extremely fast to evaluate.

Les Systèmes d'Information Géographiques (SIG) réclament des besoins particuliers de gestion de leur contenu, parce qu'ils manipulent des données dont les structures sont complexes et hétérogènes. Ces données sont souvent difficiles à décrire par des requêtes classiques ou des prédicats basés sur des attributs. Le croquis à main levée (sketch) est une veille forme de présentation qui a été employée pour visualiser, échanger et enregistrer l'information graphique. Il semble être ainsi facilement adaptable pour présenter et interroger d'une manière flexible les données des SIG

Les travaux présentés dans ce manuscrit s’inscrivent dans le contexte de l’inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle. Il s’agit de décider si l’assemblage mécanique a été correctement réalisé (assemblage conforme). Les travaux ont été menés dans le cadre de deux projets industriels. Le projet CAAMVis d’une part, dans lequel le capteur d’inspection est constitué d’une double tête stéréoscopique portée par un robot, le projet Lynx© d’autre part, dans lequel le capteur d’inspection est une caméra Pan/Tilt/Zoom (vision monoculaire). Ces deux projets ont pour point commun la volonté d’exploiter au mieux le modèle CAO de l’assemblage (qui fournit l’état de référence souhaité) dans la tâche d’inspection qui est basée sur l’analyse de l’image ou des images 2D fournies par le capteur. La méthode développée consiste à comparer une image 2D acquise par le capteur (désignée par « image réelle ») avec une image 2D synthétique, générée à partir du modèle CAO. Les images réelles et synthétiques sont segmentées puis décomposées en un ensemble de primitives 2D. Ces primitives sont ensuite appariées, en exploitant des concepts de la théorie de graphes, notamment l’utilisation d’un graphe biparti pour s’assurer du respect de la contrainte d’unicité dans le processus d’appariement. Le résultat de l’appariement permet de statuer sur la conformité ou la non-conformité de l’assemblage. L’approche proposée a été validée à la fois sur des données de simulation et sur des données réelles acquises dans le cadre des projets sus-cités. / The work presented in this manuscript deals with automated inspection of aeronautical mechanical parts using computer vision. The goal is to decide whether a mechanical assembly has been assembled correctly i.e. if it is compliant with the specifications. This work was conducted within two industrial projects. On one hand the CAAMVis project, in which the inspection sensor consists of a dual stereoscopic head (stereovision) carried by a robot, on the other hand the Lynx© project, in which the inspection sensor is a single Pan/Tilt/Zoom camera (monocular vision). These two projects share the common objective of exploiting as much as possible the CAD model of the assembly (which provides the desired reference state) in the inspection task which is based on the analysis of the 2D images provided by the sensor. The proposed method consists in comparing a 2D image acquired by the sensor (referred to as "real image") with a synthetic 2D image generated from the CAD model. The real and synthetic images are segmented and then decomposed into a set of 2D primitives. These primitives are then matched by exploiting concepts from the graph theory, namely the use of a bipartite graph to guarantee the respect of the uniqueness constraint required in such a matching process. The matching result allows to decide whether the assembly has been assembled correctly or not. The proposed approach was validated on both simulation data and real data acquired within the above-mentioned projects.

L'alignement automatique consiste à trouver une correspondance entre des unités de textes parallèles. Nous nous intéressons plus particulièrement à la réalisation d'un système qui procède à l'alignement au niveau des propositions, unités profitables dans beaucoup d'applications.<br />La présente thèse est constituée de deux types de travaux : les travaux introducteurs et ceux constituant le noyau central. Ce dernier s'articule autour de la notion de proposition syntaxique.<br />Les travaux introducteurs comprennent l'étude des généralités sur l'alignement ainsi que des travaux consacrés à l'alignement des phrases. Ces travaux ont conduit à la réalisation d'un système d'alignement des phrases adapté au traitement des textes français et japonais.<br />Le noyau de la thèse est composé de deux types de travaux, études linguistiques et réalisations informatiques. Les études linguistiques se divisent elles-mêmes en deux sujets : la proposition en français et la proposition en japonais. Le but de nos études sur la proposition française est de définir une grammaire pour la détection des propositions. Pour cet effet, nous avons cherché à définir une typologie des propositions, basée sur des critères uniquement formels. Dans les études sur le japonais, nous définissons d'abord la phrase japonaise sur la base de l'opposition thème-rhème. Nous tentons ensuite d'élucider la notion de proposition.<br />Les réalisations informatiques comportent trois tâches composant ensemble au final l'opération d'alignement des propositions, incarnées par trois systèmes informatiques distincts : deux détecteurs de propositions (un pour le français et un pour le japonais), ainsi qu'un système d'alignement des propositions.

L'alignement automatique consiste à trouver une correspondance entre des unités de textes parallèles. Nous nous intéressons plus particulièrement à la réalisation d'un système qui procède à l'alignement au niveau des propositions, unités profitables dans beaucoup d'applications.<br />La présente thèse est constituée de deux types de travaux : les travaux introducteurs et ceux constituant le noyau central. Ce dernier s'articule autour de la notion de proposition syntaxique.<br />Les travaux introducteurs comprennent l'étude des généralités sur l'alignement ainsi que des travaux consacrés à l'alignement des phrases. Ces travaux ont conduit à la réalisation d'un système d'alignement des phrases adapté au traitement des textes français et japonais.<br />Le noyau de la thèse est composé de deux types de travaux, études linguistiques et réalisations informatiques. Les études linguistiques se divisent elles-mêmes en deux sujets : la proposition en français et la proposition en japonais. Le but de nos études sur la proposition française est de définir une grammaire pour la détection des propositions. Pour cet effet, nous avons cherché à définir une typologie des propositions, basée sur des critères uniquement formels. Dans les études sur le japonais, nous définissons d'abord la phrase japonaise sur la base de l'opposition thème-rhème. Nous tentons ensuite d'élucider la notion de proposition.<br />Les réalisations informatiques comportent trois tâches composant ensemble au final l'opération d'alignement des propositions, incarnées par trois systèmes informatiques distincts : deux détecteurs de propositions (un pour le français et un pour le japonais), ainsi qu'un système d'alignement des propositions.

L’objectif de cette thèse est d’instrumentaliser des moyens, centrés utilisateur, de représentation, d’acquisition, d’enrichissement et d’exploitation des métadonnées décrivant des documents multimédias socio-personnels. Afin d’atteindre cet objectif, nous avons proposé un modèle d’annotation, appelé SeMAT avec une nouvelle vision du contexte de prise de vue. Nous avons proposé d’utiliser des ressources sémantiques externes telles que GeoNames , et Wikipédia pour enrichir automatiquement les annotations partant des éléments de contexte capturés. Afin d’accentuer l’aspect sémantique des annotations, nous avons modélisé la notion de profil social avec des outils du web sémantique en focalisant plus particulièrement sur la notion de liens sociaux et un mécanisme de raisonnement permettant d’inférer de nouveaux liens sociaux non explicités. Le modèle proposé, appelé SocialSphere, construit un moyen de personnalisation des annotations suivant la personne qui consulte les documents (le consultateur). Des exemples d’annotations personnalisées peuvent être des objets utilisateurs (e.g. maison, travail) ou des dimensions sociales (e.g. ma mère, le cousin de mon mari). Dans ce cadre, nous avons proposé un algorithme, appelé SQO, permettant de suggérer au consultateur des dimensions sociales selon son profil pour décrire les acteurs d’un document multimédia. Dans la perspective de suggérer à l’utilisateur des évènements décrivant les documents multimédias, nous avons réutilisé son expérience et l’expérience de son réseau de connaissances en produisant des règles d’association. Dans une dernière partie, nous avons abordé le problème de correspondance (ou appariement) entre requête et graphe social. Nous avons proposé de ramener le problème de recherche de correspondance à un problème d’isomorphisme de sous-graphe partiel. Nous avons proposé un algorithme, appelé h-Pruning, permettant de faire une correspondance rapprochée entre les nœuds des deux graphes : motif (représentant la requête) et social. Pour la mise en œuvre, nous avons réalisé un prototype à deux composantes : web et mobile. La composante mobile a pour objectif de capturer les éléments de contexte lors de la création des documents multimédias socio-personnels. Quant à la composante web, elle est dédiée à l’assistance de l’utilisateur lors de son annotation ou consultation des documents multimédias socio-personnels. L’évaluation a été effectuée en se servant d’une collection de test construite à partir du service de médias sociaux Flickr. Les tests ont prouvé : (i) l’efficacité de notre approche de recherche dans le graphe social en termes de temps d’exécution ; (ii) l’efficacité de notre approche de suggestion des événements (en effet, nous avons prouvé notre hypothèse en démontrant l’existence d’une cooccurrence entre le contexte spatio-temporel et les événements) ; (iii) l’efficacité de notre approche de suggestion des dimensions sociales en termes de temps d’exécution. / The overall objective of this thesis is to exploit a user centric means of representation, acquisition, enrichment and exploitation of multimedia document metadata. To achieve this goal, we proposed an annotation model, called SeMAT with a new vision of the snapshot context. We proposed the usage of external semantic resources (e.g. GeoNames ,, Wikipedia , etc.) to enrich the annotations automatically from the snapshot contextual elements. To accentuate the annotations semantic aspect, we modeled the concept of ‘social profile’ with Semantic web tools by focusing, in particular, on social relationships and a reasoning mechanism to infer a non-explicit social relationship. The proposed model, called SocialSphere is aimed to exploit a way to personalize the annotations to the viewer. Examples can be user’s objects (e.g. home, work) or user’s social dimensions (e.g. my mother, my husband's cousin). In this context, we proposed an algorithm, called SQO to suggest social dimensions describing actors in multimedia documents according to the viewer’s social profile. For suggesting event annotations, we have reused user experience and the experience of the users in his social network by producing association rules. In the last part, we addressed the problem of pattern matching between query and social graph. We proposed to steer the problem of pattern matching to a sub-graph isomorphism problem. We proposed an algorithm, called h-Pruning, for partial sub-graph isomorphism to ensure a close matching between nodes of the two graphs: motive (representing the request) and the social one. For implementation, we realized a prototype having two components: mobile and web. The mobile component aims to capture the snapshot contextual elements. As for the web component, it is dedicated to the assistance of the user during his socio-personnel multimedia document annotation or socio-personnel multimedia document consultation. The evaluation have proven: (i) the effectiveness of our exploitation of social graph approach in terms of execution time, (ii) the effectiveness of our event suggestion approach (we proved our hypothesis by demonstrating the existence of co-occurrence between the spatio-temporal context and events), (iii) the effectiveness of our social dimension suggestion approach in terms of execution time.

Les Graphes sont des structures mathématiques puissantes constituant un outil de modélisation universel utilisé dans différents domaines de l'informatique, notamment dans le domaine de la reconnaissance de formes. L'appariement de graphes est l'opération principale dans le processus de la reconnaissance de formes à base de graphes. Dans ce contexte, trouver des solutions d'appariement de graphes, garantissant l'optimalité en termes de précision et de temps de calcul est un problème de recherche difficile et d'actualité. Dans cette thèse, nous nous intéressons à la résolution de ce problème dans deux domaines : la reconnaissance de formes 2D et 3D. Premièrement, nous considérons le problème d'appariement de graphes géométriques et ses applications sur la reconnaissance de formes 2D. Dance cette première partie, la reconnaissance des Kites (structures archéologiques) est l'application principale considérée. Nous proposons un "framework" complet basé sur les graphes pour la reconnaissance des Kites dans des images satellites. Dans ce contexte, nous proposons deux contributions. La première est la proposition d'un processus automatique d'extraction et de transformation de Kites a partir d'images réelles en graphes et un processus de génération aléatoire de graphes de Kites synthétiques. En utilisant ces deux processus, nous avons généré un benchmark de graphes de Kites (réels et synthétiques) structuré en 3 niveaux de bruit. La deuxième contribution de cette première partie, est la proposition d'un nouvel algorithme d'appariement pour les graphes géométriques et par conséquent pour les Kites. L'approche proposée combine les invariants de graphes au calcul de l'édition de distance géométrique. Deuxièmement, nous considérons le problème de reconnaissance des formes 3D ou nous nous intéressons à la reconnaissance d'objets déformables représentés par des graphes c.à.d. des tessellations de triangles. Nous proposons une décomposition des tessellations de triangles en un ensemble de sous structures que nous appelons triangle-étoiles. En se basant sur cette décomposition, nous proposons un nouvel algorithme d'appariement de graphes pour mesurer la distance entre les tessellations de triangles. L'algorithme proposé assure un nombre minimum de structures disjointes, offre une meilleure mesure de similarité en couvrant un voisinage plus large et utilise un ensemble de descripteurs qui sont invariants ou au moins tolérants aux déformations les plus courantes. Finalement, nous proposons une approche plus générale de l'appariement de graphes. Cette approche est fondée sur une nouvelle formalisation basée sur le problème de mariage stable. L'approche proposée est optimale en terme de temps d'exécution, c.à.d. la complexité est quadratique O(n2), et flexible en terme d'applicabilité (2D et 3D). Cette approche se base sur une décomposition en sous structures suivie par un appariement de ces structures en utilisant l'algorithme de mariage stable. L'analyse de la complexité des algorithmes proposés et l'ensemble des expérimentations menées sur les bases de graphes des Kites (réelle et synthétique) et d'autres bases de données standards (2D et 3D) attestent l'efficacité, la haute performance et la précision des approches proposées et montrent qu'elles sont extensibles et générales / Graphs are powerful mathematical modeling tools used in various fields of computer science, in particular, in Pattern Recognition. Graph matching is the main operation in Pattern Recognition using graph-based approach. Finding solutions to the problem of graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. In this thesis, we investigate the resolution of this problem in two fields: 2D and 3D Pattern Recognition. Firstly, we address the problem of geometric graphs matching and its applications on 2D Pattern Recognition. Kite (archaeological structures) recognition in satellite images is the main application considered in this first part. We present a complete graph based framework for Kite recognition on satellite images. We propose mainly two contributions. The first one is an automatic process transforming Kites from real images into graphs and a process of generating randomly synthetic Kite graphs. This allowing to construct a benchmark of Kite graphs (real and synthetic) structured in different level of deformations. The second contribution in this part, is the proposition of a new graph similarity measure adapted to geometric graphs and consequently for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation. Secondly, we address the problem of deformable 3D objects recognition, represented by graphs, i.e., triangular tessellations. We propose a new decomposition of triangular tessellations into a set of substructures that we call triangle-stars. Based on this new decomposition, we propose a new algorithm of graph matching to measure the distance between triangular tessellations. The proposed algorithm offers a better measure by assuring a minimum number of triangle-stars covering a larger neighbourhood, and uses a set of descriptors which are invariant or at least oblivious under most common deformations. Finally, we propose a more general graph matching approach founded on a new formalization based on the stable marriage problem. The proposed approach is optimal in term of execution time, i.e. the time complexity is quadratic O(n2) and flexible in term of applicability (2D and 3D). The analyze of the time complexity of the proposed algorithms and the extensive experiments conducted on Kite graph data sets (real and synthetic) and standard data sets (2D and 3D) attest the effectiveness, the high performance and accuracy of the proposed approaches and show that the proposed approaches are extensible and quite general