Claude Universite

Bernard -Lyon

M Le Professeur

Frédéric Fleury

Hamda Ben

Hadid M Le Professeur Didier

Revel M Le Professeur

Philippe Chevalier

M Fabrice

Vallée Mme

Dominique Marchand

Composantes Sante

G Rode

La Mme

C Professeure

Burillon

D Bourgeois

Vinciguerra

M X Perrot

Keywords: Graph matching, Graph edit distance, Graph decomposition, Graph based modelling, Pattern recognition, 3D object recognition, Deformable object recognition, Kites, Satellite image S2, 1 S2, 3 S2, 0 S2, 2 0, 92 0, 99 0, 55 0

7.10 T SM Best Accuracy, T P R and T NR results in TOSCA database for the degree of neighborhood N K=1...6 . . . . . . . . . . . . . . . . . . . 103 7.11 E_Measure results of our method T SM using N K=1...6 neighborhood and other methods of the state of the art in TOSCA database. . . . 109 7.12 The Accuracy, T P R and T NR results with the degree of neighborhood N K=2 and according to the classification threshold, in the SHREC11 watertight database. . . .

COMPOSANTES ET DEPARTEMENTS DE SCIENCES ET TECHNOLOGIE

To my sisters and brothers.

To my fiancee.

I would like to thank my parents, my sisters, my brothers, my fiancee and all my family for their continuous moral support, understanding, patience and encouragement with their best wishes. Their love accompanies me wherever I go. Without them, this thesis would not have been possible. I'm very grateful to my mother and father, for all their love, support, and patience over the years. I'm also very thankful to my future wife. Words cannot describe how lucky I am to have her in my life.

I would like also to thank my friends, from Bejaia (Algeria), Lyon, Paris and Marseille (France), Ottawa (Canada) and everywhere. I prefer to not mention names, since the list is very long. I thank them for their continuous moral support and encouragement. I would also like to thank my friends and colleagues form LIRIS Laboratory and Lyon 1 University with whom I spent wonderful moments during my thesis.

I am greatly indebted to all the teachers and professors, in Béjaia (Algeria), Marseille, Montpellier, Paris, Lyon (France) and Ottawa (Canada), from whom I have learned over the years. I wish, through this thesis, to pay tribute to my cousin Ghilas Madi, who left us very younger at the age of 21 years, at February 14th, 2016. He was a wonderful and very respectful guy and a brilliant student in Computer Science.

Finally, I would like to dedicate this thesis dissertation to my parents, my sisters, my brothers, my fiancee and all my family. viii Abstract: 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(n 2 ) 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.

Résumé: 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 à 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 où 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(n 2 ), 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.

General Introduction

Graph theory is an important mathematical field. Its origin dates back to 1735 when the Swiss mathematician Leonard Euler solved the problem of the Seven Bridges of Königsberg, called also, the Königsberg bridge problem [START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF]. The city of Königsberg in Prussia (now Kaliningrad) was built on both sides of the Pregel River, and included two islands connected to each other and the mainland by seven bridges (See Figure 1.1). The problem was to find a continuous tour through the city of Königsberg that would cross each bridge exactly once, come back at the same point from which it began. The Swiss mathematician, Leonard Euler, demonstrated that no such tour was possible. He gave an abstract model of the problem by representing land masses with points and bridges with links between pairs of points (See Figure 1.2). This abstract description of the problem was the introduction to the graph notion, and its solution is often referred as the first theorem in graph theory [START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF].

Graphs are useful and powerful mathematical tools allowing both the description of properties of an object and the relationships between a set of objects. The object properties are described by means of nodes and the relationships between objects are represented by means of edges. In this context, graphs constitute an universal modeling tool and receive considerable attention from the whole scientific community, allowing their use in various fields of computer science, in particular the field of Pattern Recognition.

Pattern recognition describes the act allowing to determine the category or the class to which a given pattern belongs. The term "pattern" means an observation in the real world. Pattern recognition is one of the important capabilities of humans, with which intuitively we can recognize the face of a friend, a category of an animal, a written sentence, a spoken word, a car in the street, an object in a specific place, an image, etc. The aim of pattern recognition as a field of computer science is to propose algorithms allowing the imitation as possible of the human capacity of perception and recognition [START_REF] Riesen | Structural Pattern Recognition with Graph Edit Distance[END_REF].

Chapter 1. General Introduction Graph matching and more generally graph comparison is the main operation in the process of pattern recognition using a graph-based approach. Graph matching is the process of finding a correspondence between vertices and edges of two graphs that satisfies a certain number of constraints ensuring that substructures in one graph are mapped to similar substructures in the other. Graph matching solutions are classified into two wide categories: exact approaches and inexact approaches.

In this thesis, Inexact graph matching and its applications for 2D and 3D Pattern Recognition are investigated. Thus, the thesis is divided into 8 chapters organized into two parts. Each part contains two chapters. First of all, in Chapter 2, we give some preliminaries and introduce some notations needed in the rest of the thesis.

Then, we give in Chapter 3, an overview of the related work concerning graph matching and its applications in Pattern Recognition. to attest the effectiveness of the approach. We also perform a set of experimentations on other data sets in order to show that the proposed approach is extensible and quite general.

Part II: Inexact graph matching for 3D objects recognition

Object recognition is one of the fundamental challenges in computer vision, which has been studied for more than four decades [START_REF] Ullman | High-Level Vision: Object Recognition and Visual Cognition[END_REF]. In the last years, there has an increasing interest on the 3D objects analysis. The high advances in different fields of technology and specially in the field of 3D, engender a high growing need of automated methods for 3D objects recognition. Using triangular tessellations, 3D objects may be compared with graph matching techniques. This part addresses the problem of comparing deformable or non-rigid 3D objects (such as human and animal bodies). The shapes considered are represented by graphs, i.e., triangular tessellations.

We propose a new distance for comparing deformable 3D objects. This distance is based on the decomposition of triangular tessellations into a set of substructures that we call triangle-stars. A triangle-star is a connected component formed by the union of a triangle and its neighborhood. The proposed decomposition offers a parameterizable triangle-stars depending on the degree of the considered neighborhood. The number of triangle-stars obtained is much smaller than the number of nodes and the number of classic stars [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] and, as a result, the computational complexity is reduced. Furthermore, triangle-stars are local structures that cover a larger neighborhood than classic stars decomposition [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. Consequently, the proposed dissimilarity measure assures an optimal approximation. This is justified by the fact that optimal methods are based on graph's global structures and, consequently, a larger local structure allows to be closer to the global one. The proposed approach uses a set of descriptors which are invariant or at least oblivious under most common deformations. This part contains two chapters, in the first one (Chapter 6), we present the proposed decomposition of triangular tessellations into triangle-stars. We describe the proposed distance (dissimilarity measure). We prove that the proposed distance is a pseudo-metric and we analyse its time complexity.

In the second chapter (Chapter 7), we describe the experimentations that we undertook to evaluate our approach. We present the different databases that we use in our experiments, some state of the art shape-matching algorithms to compare with, the evaluation criteria and the experimental results. The analysis of the time complexity and our experimental results on three standard databases (TOSCA, SHREC09 and SHREC11) confirm the high performance and accuracy of our algorithm. The set of experimentations and the obtained results on SHREC09 database show that the proposed approach is efficient also for the 3D objects sub-matching, which prove that our method is extensible and quite general.

Finally, Chapter 8 concludes the thesis with a summary of the contributions and some suggestions for further research. One of the promising ideas that we project to realize in further research is described in this last chapter. We propose a more general graph matching approach founded on a new formalization based on the stable marriage problem [START_REF] Gusfield | The stable marriage problem: structure and algorithms[END_REF]. The proposed approach is optimal in term of execution time, i.e. the time complexity is quadratic O(n 2 ). The proposed algorithm is flexible in term of applicability (2D and 3D).

The set of publications arising from this thesis are listed in Appendix A. In this chapter, we first introduce some useful definitions related to graphs, and present a short overview of the notations used in this thesis. Secondly, we present some common concepts and typical classes of graphs. Finally, we present some aspects of graph matching. Definitions and notations related to a particular chapter can be found in the corresponding chapter. We refer the reader to ( [START_REF] Bondy | Graph theory with applications[END_REF], [START_REF] Harary | Graph theory. Addison-Wesley Series in Mathematics[END_REF], [START_REF] West | An Introduction to Graph Theory[END_REF] and [START_REF] Diestel | Graph Theory[END_REF]) for more background information on graph theory.

Basic definitions

In this section, we introduce some useful definitions and notation relating to graphs.

Graph: A graph is mathematical construct that models a relationship between a set of items. The set of items represents a set of objects. A link between the two items represents a relationship between two objects. The items are called vertices or nodes and the links are called edges. Thus, a graph G(V, E) is a set of nodes connected by a set of edges. Formally, a graph G is a four tuple

G = (V, E, α, β),
where V is a finite not empty set of nodes or vertices. that connects them. An edge uv is said to be incident to the nodes u and v. Two edges are adjacent if they are incident to a same node (they share a node). A loop at a node, links the node to itself and makes it its own neighbor. A graph is simple if there is at most one edge between every two nodes.

E ⊆ V × V is the set of edges. α : V → L V is the node labelling function, β : E → L E is
In this thesis, unless it is specified, the graphs which are considered will be finite simple undirected graphs, having no loops.

Neighborhood and Degree:

The set of all neighbors of a node v in a graph G,

is denoted by N (v). The number of neighbors of v is called the degree of v and it is denoted by deg(v). A node v is an isolated node if deg(v) = 0, which means that v is without any neighbors. A node of degree one (deg(v) = 1) is called a leaf or a pendant node. The minimum degree of a graph G is δ(G) = min{deg(v) : v ∈ V (G)}
and the maximum degree of a graph G is denoted by

Δ(G) = max{deg(v) : v ∈ V (G)}.

Path and Cycle:

A path is in an undirected graph G defined as a sequence of

nodes (v 1 , v 2 , . . . , v k ) such that each pair v i , v i+1 is an edge in E(G

E(H) ⊆ E(G).

Which means also that the graph G is a supergraph of the graph H.

Some special graphs

Several graph classes have been defined and considered in the graph theory literature, in order to model specific problems or to take advantage of the theoretical properties of those classes. In this section, we present some typical and important classes that will be considered in this thesis.

Planar graph: A graph is planar if it can be drawn in the plane without any edges crossing, which means that edges intersect only at their common nodes.

A graph G = (V, E) is bipartite if its set of nodes V can be split into two disjoint subsets V 1 and V 2 such that every edge of E connects a node in V 1 to another node in V 2 .

Graph matching

Graph matching is the process of finding a correspondence between nodes and edges of two graphs. In this section we present some important definitions related to graph matching. We present also the Graph edit distance (GED) which is one of the most famous and powerful fault-tolerant graph matching method.

Chapter 2. Preliminary Notions

Graph homomorphism: A graph homomorphism f from a graph G to a graph H, written as G → H, is a mapping from V (G) to V (H) with edge preserving, which means that, if two nodes are adjacent in G, their images by f are adjacent in H. However, more than one node of G may be mapped to the same node in H.

Formally, uv ∈ E(G) ⇒ f (u)f (v) ∈ E(H).
Graph isomorphism: A graph isomorphism f between two graphs G and H, written as G H, is a bijection between their sets of nodes V (G) and V (H) with edge preserving. In other words, a graph isomorphism is a graph homomorphism with one-to-one correspondence between V (G) and V (H). Figure 2.9 illustrates an example of an isomorphism f between two graphs G and H.

1 2 3 4 A B D C G H f(1)=A f(3)=D f(2)=B f(4)=C
λ(G 1 , G 2 ) = min (e1,...,ek) ∈ γ(G1,G2) k i=1 c(e i )
where γ(G 1 , G 2 ) denotes the set of edit paths transforming G 1 into G 2 , and c denotes the cost function measuring the strength c(e i ) of edit operation e i .

Introduction

Graphs are a powerful representation tool and a famous mathematical formalism used in many applications of structural Pattern Recognition and classification [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF][START_REF] Vento | A long trip in the charming world of graphs for pattern recognition[END_REF].

Graphs constitute an universal and a flexible modeling tool allowing both the description of properties of an object and the relationships between a set of objects.

Since [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. Recently, the authors of [START_REF] Babai | Graph isomorphism in quasipolynomial time[END_REF] show that graph isomorphism can be solved in quasi-polynomial time

(exp((log n) O(1)
)). Some algorithms for graph isomorphism with polynomial time

Graph matching methods

complexity have been proposed for special kinds of graphs (such as: e.g. trees [START_REF] Aho | The design and analysis of computer algorithms. series in computer science and information processing[END_REF] and planar graphs [START_REF] Hopcroft | Linear time algorithm for isomorphism of planar graphs[END_REF]). However, until now, no polynomial algorithms are proposed for the general case. Exact graph matching has exponential time complexity in the worst case. Consequently, the exact methods are known to be only able to deal with graphs having a small number of nodes. The exact methods are mainly aimed to reduce the computational time of the matching process deriving from the exponential complexity of the exact matching problem. In the following we briefly review some typical methods for exact graph matching.

Tree search based techniques

Tree search based techniques constitute the main pillar of the most of existing algorithms for exact graph matching. These techniques use principally backtracking process in addition to some heuristics. The key idea in tree search based techniques is the following: a partial matching is constructed starting with an empty mapping set and iteratively enriched by adding a new couple of mapped nodes, with possibility of backtracking, usually using some heuristics to cut as soon as possible unfruitful search paths in order to avoid the complete exploration of the research space of all the possible matchings.

Various algorithms based on tree search techniques have been proposed in the literature. Ullmann's algorithm [START_REF] Ullmann | An Algorithm for Subgraph Isomorphism[END_REF], is the first important algorithm based on tree search techniques. The algorithm is one of the most popular graph matching algorithm and still largely used until now despite of its age. Ullmann's algorithm addresses mainly graph isomorphism, subgraph isomorphism and monomorphism problems. However

Ullmann explain a way to use the algorithm for maximum clique detection and consequently for the Maximum common subgraph (MCS) problem. Ullmann proposes a procedure called refinement procedure in order to cut the search space (unfruitful matches). The proposed procedure uses a matrix of possible future mapped couples of nodes to remove. In 1998, the authors of [START_REF] Cordella | Graph matching: a fast algorithm and its evaluation[END_REF] propose the VF algorithm which is an algorithm for both isomorphism and subgraph isomorphism. The authors propose a fast heuristic which analyses the nodes adjacent to the ones already added in the partial matching. In 2004, the same authors propose an enhanced version of the algorithm [START_REF] Cordella | A (sub) graph isomorphism algorithm for matching large graphs[END_REF], called VF2, in which they reduce the memory requirement from

O(n 2 ) to O(n),
where n is the number of nodes in the graphs. An improved version of VF2 for biological graphs is presented in [START_REF] Carletti | VF2 plus: An improved version of VF2 for biological graphs[END_REF].

Chapter 3. Related work: Graph matching and its applications

More recent tree search based algorithms have been proposed. In 2007, the authors of [START_REF] Konc | An improved branch and bound algorithm for the maximum clique problem[END_REF] propose an enhanced algorithm for finding the Maximum Clique and by the same way the Maximum Common Subgraph (MCS), called MaxCliqueDyn. In order to prune unfruitful matches, the proposed algorithm uses branch and bound combined with approximate graph coloring for finding tight bounds. In 2011, Ullmann in [START_REF] Ullmann | Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism[END_REF] presents an important enhancement of his own very well-known isomorphism algorithm from 1976 [START_REF] Ullmann | An Algorithm for Subgraph Isomorphism[END_REF]. The new algorithm is based on the Binary Constraint Satisfaction Problem. Other algorithms based on Constraint Satisfaction Problem (CSP) have been proposed (eg., [START_REF] Larrosa | Constraint satisfaction algorithms for graph pattern matching[END_REF] and the improved version in [START_REF] Zampelli | Solving subgraph isomorphism problems with constraint programming[END_REF]). A more improved algorithm has been proposed by Solnon [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF], in which the author use a better filtering based on the AllDifferent constraint. In 2016, the authors of [START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF] proposed a new exact maximum clique algorithm for large and massive sparse graphs. The authors used a branch-and-bound algorithm with a novel sparse encoding for the adjacency matrix.

Other techniques

Other algorithms addressing the problem of exact graph matching, not based on tree search techniques, have been proposed in the literature. One of the most efficient, fastest and interesting algorithm addressing the problem of graph isomorphism, not based on tree search techniques, is Nauty's algorithm which is proposed in 1981 by

McKay [START_REF] Mckay | Practical graph isomorphism[END_REF]. Using some results coming from group theory, Nauty's algorithm constructs an automorphism group of each graph. The algorithm associates a canonical form to each graph, consequently, two graphs are isomorphic if their canonical forms are equal. The equality between two canonical forms can be verified in O(n 2 ) time, however the canonical form can be constructed in exponential time in the worst case, while in the average case, Nauty's algorithm achieves a good performance.

Other kind of approaches are graph invariants, which have been efficiently used to solve the graph comparison problem in general and the graph isomorphism problem in particular. They are used for example in Nauty [START_REF] Mckay | Practical graph isomorphism[END_REF]. A vertex invariant, for example, is a number i(v) assigned to a vertex v such that if there is an isomorphism that maps v to v then i(v) = i(v ). Examples of invariants are the degree of a vertex, the number of cliques of size k that contain the vertex, the number of vertices at a given distance from the vertex, etc. Graph invariants are also the basis of graph probing [START_REF] Lopresti | Comparing Semi-Structured Documents via Graph Probing[END_REF], where a distance between two graphs is defined as the norm of their

Graph matching methods

probes. Each graph probe is a vector of graph invariants. A generalization of this concept is also used in [START_REF] Xiao | Structure-based graph distance measures of high degree of precision[END_REF] to compare biological data.

Other algorithms not based on tree search have been proposed. In [START_REF] Gori | Exact and approximate graph matching using random walks[END_REF], the authors propose an isomorphism algorithm that is based on Random Walks. The authors of [START_REF] Dickinson | Matching graphs with unique node labels[END_REF] discuss the matching problem (graph isomorphism, subgraph isomorphism and maximum common subgraph) for the special case of graphs having unique node labels. In 2012, the authors of [START_REF] Dahm | Topological features and iterative node elimination for speeding up subgraph isomorphism detection[END_REF] propose a technique for speeding up existing exact subgraph isomorphism algorithms on large graphs.

Inexact graph matching

Identical structure with edge preserving in both directions are the constraints required by the exact graph matching so that two graphs will be isomorphic. Moreover, exact graph matching algorithms require a high computational complexity. All these strict constraints make exact graph matching only usable in few applications. The handled graphs in various graph-based applications, are subject to deformations due to several causes, (eg, the non-rigidity of the patterns, the noise in the acquisition process and the errors introduced by the modeling processes, etc). Consequently, the obtained graphs in many cases are different from the graph reference models.

Hence, the matching process must be fault tolerant and this by allowing the structural difference between the compared graphs. The matching process must also able to find the solution in acceptable time, even without guarantee to find the optimal solution, but at least, find a good approximate solution. All these reasons and needs that we cited above have prompted the authors to propose an important number of inexact graph matching algorithms. The ignoring of the identical structure with edge preserving constraint imposed in the exact graph matching algorithms, is replaced by considering a system of penalizing which is used when the edge preserving is not respected in the inexact graph matching process. Indeed, a specific cost is associated to the edges not satisfying the edge preserving constraint. Thus, inexact graph matching algorithms aim to find a matching between the compared graphs that minimizes (or maximizes) the matching cost. In other words, inexact graph matching algorithms aim to compute a distance between the compared graphs. This distance measures how similar (or dissimilar) are the graphs.

Inexact graph matching algorithms are mainly classified into two classes: optimal and approximate algorithms.

Chapter 3. Related work: Graph matching and its applications

Optimal inexact matching algorithms always find a solution if it exists. The solution found is exact and represents a global minimum of the matching cost. Consequently, these algorithms are considered as a generalization of exact matching algorithms.

Optimal inexact matching algorithms not only require an exponential time complexity as exact graph matching algorithms but they are generally more expensive, which makes these algorithms not useable for many applications.

Suboptimal or approximate matching algorithms find a local minimum of the matching cost. The local minimum found is generally not far from the global one. However, there are no guarantees to reach the global minimum and to be able to find an exact solution if it exists [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. The main advantage of these algorithms is their time complexity, which is usually polynomial. Hence, approximate matching algorithms are widely used in many applications.

A large number of inexact graph matching approaches have been proposed in the literature. In the following, we review some important inexact graph matching approaches, classified following the kind of the matching algorithm used.

Approaches based on Graph Edit Distance formulation

Many inexact graph matching algorithms are formulated as an approximation approach to compute the Graph Edit Distance (GED). Graph edit distance (GED) is one of the most famous and powerful fault-tolerant graph matching measures to determine the distance between graphs [START_REF] Bunke | A graph distance metric based on the maximal common subgraph[END_REF][START_REF] Papadopoulos | Structure-based similarity search with graph histograms[END_REF][START_REF] Sorlin | A generic graph distance measure based on multivalent matchings[END_REF]. It is based on a kind of graph transformation called an edit operation. An edit operation is either an insertion, a suppression or a substitution of a node and/or an edge in the graph. A cost function associates a cost to each edit operation. The edit distance between two graphs is defined by the minimum costing sequence of edit operations that are necessary to transform one graph into an other [START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF]. This sequence is called an optimal edit path (See Chapter 2 for a formal definition). Tolerance to noise and distortion is one of the advantages of GED. Unfortunately, computing the exact value of the edit distance between two graphs is NP-Hard for general graphs and induces an exponential computational complexity [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. This motivated the apparition of several heuristics giving rise to many inexact graph matching algorithms that approach the exact value of GED in polynomial time, using different methods such as bipartite assignment, dynamic programming and probability, etc.

Bipartite graph matching has been demonstrated to be one of the most efficient

Graph matching methods

algorithms to solve fault-tolerant graph matching [START_REF] Serratosa | Computation of graph edit distance: Reasoning about optimality and speed-up[END_REF]. In [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] and [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], the authors proposed an approach based on bipartite assignment in which they partition the compared graphs into smaller substructures and approximate GED by computing edit distance between substructures. A cost matrix between these substructures is defined and a mapping between them is realized using an algorithm of linear assignment, mainly, the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] or the Jonker-Volgenant algorithm [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF]. These substructures are generally stars, i.e., nodes with their direct neighbors and edges. However, they are called local descriptions in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], stars in [START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], b-stars in [START_REF] Yahiaoui | Coloring based approach for matching unrooted and/or unordered trees[END_REF] and probe vectors in [START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF]. The edit distance between substructures is achieved in O((n + m) 3 ) time steps, where n and m are the number of nodes in the two compared graphs.

In addition to classic operators (insertion, suppression and substitution) used in GED, other ones are proposed. In [START_REF] Berretti | A graph edit distance based on node merging[END_REF], the authors proposed a novel solution of GED in which they introduce a new operator to support the node merging and splitting. They proposed also to apply edit operations in the both compared graphs until a common graph structure, instead of applying edit operations only to one graph in order to transform it to the other. They proposed to consider virtual nodes in the process of graph matching. Virtual nodes are the result of merging compatible nodes. Two nodes i, j are compatible nodes if they are adjacent and the distance D w (i, j) is less than a defined threshold.

Another approximation called BEAM is proposed in [START_REF] Neuhaus | Fast suboptimal algorithms for the computation of graph edit distance[END_REF], where the authors present a fast suboptimal graph edit distance search which is a variant of a standard A* algorithm reducing the search space. Rather than expanding all successor vertices in the search tree, only a fixed number of vertices to be processed are kept in the set of open vertices at all times. The search space is not completely explored, only the vertices belonging to the most promising partial matches are expanded.

Recent works are realized in order to speed up the runtime of the bipartite graph matching based approaches. In [START_REF] Serratosa | Fast computation of bipartite graph matching[END_REF], the author proposed a new algorithm to compute the Graph Edit Distance in a sub-optimal way. The author demonstrated that the proposed algorithm ensure the same distance proposed in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] with a reduced run time, which is O((max(n, m)) 3 ), where n and m are the number of nodes in the two compared graphs. However, the edit costs have to be defined in such way allowing that the GED to be defined as distance function, which means that the cost of insertion plus deletion of nodes (or arcs) have to be lower or equal than the cost of substitution of nodes (or arcs). The same author, in [START_REF] Serratosa | Speeding up fast bipartite graph matching through a new cost matrix[END_REF], proposed a new Chapter 3. Related work: Graph matching and its applications fast algorithm, with O((max(n, m)) 3 ) time complexity, to compute the Graph Edit Distance in a sub-optimal way. The author used the Jonker-Volgenant linear solver [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF] which is known to produce similar results than the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] but with an important run time reduction. However, the Jonker-Volgenant linear solver [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF] has some convergence problems on some specific cost matrices. Hence, the author define a new cost matrix such that the Jonker-Volgenant linear solver [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF] converges and the matching algorithm obtains the same distance value than the Bipartite algorithm [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF]. In [START_REF] Fischer | Approximation of graph edit distance based on hausdorff matching[END_REF], the authors proposed a new distance called

Hausdorff Edit Distance (HED). The proposed distance (HED) is an adaptation of the well-known Hausdorff distance between sets [START_REF] Huttenlocher | Comparing images using the hausdorff distance[END_REF] for the Graph Edit Distance (GED). The proposed algorithm has a quadratic computational cost O(n * m), where n and m are the number of nodes in the two compared graphs. However, it does not obtain a bijective correspondence between the nodes of both graphs.

A comparison between the three algorithms Bipartite (BP) [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], Fast Bipartite (FBP) [START_REF] Serratosa | Fast computation of bipartite graph matching[END_REF] and Square Fast Bipartite (SFBP) [START_REF] Serratosa | Speeding up fast bipartite graph matching through a new cost matrix[END_REF] was realized in [START_REF] Serratosa | Computation of graph edit distance: Reasoning about optimality and speed-up[END_REF]. The authors have shown that the performance and the optimality of FBP and SFBP were not affected by the violation of the theoretically restrictions imposed in FBP and SFBP. The authors have shown also that SFBP [START_REF] Serratosa | Speeding up fast bipartite graph matching through a new cost matrix[END_REF] with the Jonker-Volgenant solver [START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF] is the fastest algorithm. In [START_REF] Serratosa | Graph edit distance: Moving from global to local structure to solve the graph-matching problem[END_REF], the authors proposed eight different options of local structures considered to construct the cost matrix in the Bipartite Graph Matching. The authors have shown also that the type of local structure and the distance defined between these structures is relevant for the runtime and classification ratio.

Other recent works have been proposed in order to speed up the runtime and/or improve the accuracy of Graph Edit Distance based approach. Among them we cite:

[54], [START_REF] Riesen | Improving the distance accuracy of bipartite graph edit distance[END_REF] and [START_REF] Riesen | Approximation of graph edit distance by means of a utility matrix[END_REF]. We refer the reader to [START_REF] Gao | A survey of graph edit distance[END_REF] for a detailed GED survey.

Tree search based techniques

As in the exact graph matching, tree search based techniques with backtracking have been also utilized for inexact graph matching. The principe, in this case, is that both the cost of the current partial matching and the estimated cost of the rest of nodes using a heuristic, are used to guide the search process. The total cost is utilized either to cut unfruitful paths as in a branch and bound algorithm, or to specify the order of branches to be traversed in the search tree, as in the A * algorithm [START_REF] Hart | Correction to "a formal basis for the heuristic determination of minimum cost paths[END_REF].

The considered heuristics may not ensure to find the optimal solution, which means

Graph matching methods

that the matching is suboptimal. Various inexact graph matching algorithms based on tree search techniques have been proposed, for example: [START_REF] Tsai | Error-correcting isomorphisms of attributed relational graphs for pattern analysis[END_REF], [START_REF] Tsai | Subgraph error-correcting isomorphisms for syntactic pattern recognition[END_REF], [START_REF] Eshera | A similarity measure between attributed relational graphs for image analysis[END_REF] and [START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF].

Many of the proposed algorithms are based on the well know A * algorithm, such as: [START_REF] Dumay | Consistent inexact graph matching applied to labelling coronary segments in arteriograms[END_REF], [START_REF] Berretti | A look-ahead strategy for graph matching in retrieval by spatial arrangement[END_REF], [START_REF] Bunke | Graph matching: Theoretical foundations, algorithms, and applications[END_REF], [START_REF] Berretti | Efficient matching and indexing of graph models in content-based retrieval[END_REF] and [START_REF] Neuhaus | Fast suboptimal algorithms for the computation of graph edit distance[END_REF].

Continuous optimization

Although graph matching is naturally a discrete optimization problem, and usually the methods proposed to solve it, use directly graphs. A thoroughly different method, is to solve the graph matching problem by solving an equivalent continuous one. This method is performed mainly on three steps: firstly, the graph matching problem is reformulated as a continuous problem. Secondly, the continuous problem is solved using an optimization algorithm. Finally, the continuous solution found is recast to the initial discrete domain. The inconvenient of this method is there is no guarantees to reach even the local optimality. Indeed, even the optimization algorithms used for the continuous problem in the second step ensure to find a local optimum (suboptimal solution). The final solution, resulting by the last approximation of the discretization step, may not guarantee to reach local optimality. However, continuous optimization based approach is very useful in many applications due to its very reduced computational cost which is usually polynomial [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF].

Several inexact graph matching algorithms based on continuous optimization have been proposed, mainly organized into two families: probabilistic relaxation labeling and weighted graph matching problem (WGM). The first family (the probabilistic relaxation labeling) is an iterative process trying to find a correspondence between graphs by assigning a label to each node or substructure of one graph and this based on a set of constraints. Various algorithms have been proposed in this category, such as: [START_REF] Fischler | The representation and matching of pictorial structures[END_REF], [START_REF] Kittler | Combining evidence in probabilistic relaxation[END_REF], [START_REF] Christmas | Structural matching in computer vision using probabilistic relaxation[END_REF], [START_REF] Wilson | Structural matching by discrete relaxation[END_REF], [START_REF] Huet | Shape recognition from large image libraries by inexact graph matching[END_REF], [START_REF] Torsello | Computing approximate tree edit distance using relaxation labeling[END_REF] and [START_REF] Aflalo | On convex relaxation of graph isomorphism[END_REF]. The second family is based on a formulation of the problem as a Weighted Graph Matching Problem (WGM). This approach is based on the use of a mapping matrix M containing real valued elements [0, 1] in order to find a matching between two sets of nodes or substructures of the two compared graphs. A defined objective function which depends on the weights of the edges preserved by the match, must be optimised by the required matching. Due to the continuous values [0, 1] of the elements of the matrix M , the WGM problem is usually and naturally transformed into a continuous problem. Hence, the WGM problem becomes a quadratic optimization problem. One of the important Chapter 3. Related work: Graph matching and its applications disadvantages of the weighted graph matching WGM based approach is that only the weights of edges are accepted as attributes and the nodes cannot have. The authors of [START_REF] Almohamad | A linear programming approach for the weighted graph matching problem[END_REF] were among the first, who linearized and solved the quadratic problem using the simplex algorithm. In [START_REF] Rangarajan | A lagrangian relaxation network for graph matching[END_REF], the authors propose an approach based on Lagrangian relaxation network for Graph Matching. The authors of [START_REF] -L. Chen | Approximating the maximum common subgraph isomorphism problem Bibliography with a weighted graph[END_REF], proposed a method to approximate the maximum common subgraph isomorphism problem by producing a weighted graph. The obtained weights indicate the probability that the associated link will be in the maximum common subgraph of the two graphs considered. Other methods for inexact graph matching based on continuous optimization have been proposed. Among them we can cite, the fuzzy graph matching ( [START_REF] Medasani | A fuzzy approach to content-based image retrieval[END_REF], [START_REF] Medasani | Graph matching by relaxation of fuzzy assignments[END_REF] and [START_REF] Gross | A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness[END_REF]), Kernel Methods for graph matching such as Reproducing Kernel Hilbert Spaces based approaches ( [START_REF] Van Wyk | Non-bayesian graph matching without explicit compatibility calculations[END_REF] and [START_REF] Van Wyk | Successive projection graph matching[END_REF]).

Spectral methods

The basic idea considered in spectral methods is that the eigenvalues and the eigenvectors of the adjacency matrix of a graph are invariant to node permutations.

Which means that, even if the rows and the columns of the adjacency matrix are permuted, its eigenvalues and eigenvectors stay unchanged. Consequently, the adjacency matrices of isomorphic graphs have the same eigenvalues and eigenvectors.

However, the inverse is not true [START_REF] Caelli | An eigenspace projection clustering method for inexact graph matching[END_REF], which means that we cannot infer that two graphs are isomorphic, if their eigenvalues and/or eigenvectors are equal. Moreover, spectral methods are inexact in the sense that they do not ensure finding the optimal solution [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]. Furthermore, spectral methods cannot use the attributes of nodes or edges except some spectral methods which are able to exploit only real weights of edges. However, due to the polynomial time complexity of the spectral methods, they are widely used for solving the graph matching problem. Hence, various algorithms based on this approach have been proposed. We can cite, [START_REF] Umeyama | An eigendecomposition approach to weighted graph matching problems[END_REF], [START_REF] Shapiro | Feature-based correspondence: an eigenvector approach[END_REF], [START_REF] Carcassoni | Spectral correspondence for point pattern matching[END_REF], [START_REF] Wang | A kernel view of spectral point pattern matching[END_REF],

[87], [START_REF] Cour | Balanced graph matching[END_REF], [START_REF] Escolano | Information-geometric graph indexing from bags of partial node coverages[END_REF], [START_REF] Leng | Graph matching based on stochastic perturbation[END_REF], [START_REF] Aflalo | On convex relaxation of graph isomorphism[END_REF] and [START_REF] Lyzinski | Spectral clustering for divide-and-conquer graph matching[END_REF]. We refer the readers to [START_REF] Wilson | A study of graph spectra for comparing graphs and trees[END_REF], in which the authors present a survey of various graph based spectral approaches for comparing graphs and trees.

Other techniques

Other categories of inexact graph matching that are not mentioned previously, exist in the literature, where several algorithms have been proposed. We can cite: de-

Graph matching methods

composition methods ( [START_REF] Messmer | A new algorithm for error-tolerant subgraph isomorphism detection[END_REF], [START_REF] Fuchs | Building reconstruction on aerial images through multi-primitive graph matching[END_REF], [START_REF] Fuchs | Efficient subgraph isomorphism with 'a priori'knowledge[END_REF]), [START_REF] Yan | A matrix decomposition perspective to multiple graph matching[END_REF] and [START_REF] Zhou | Factorized graph matching[END_REF], neural networks ( [START_REF] Shouxuy | Neural network approach for solving the maximal common subgraph problem[END_REF], [START_REF] Suganthan | Recognition of handprinted chinese characters by constrained graph matching[END_REF], [START_REF] Suganthan | Attributed relational graph matching by neural-gas networks[END_REF] and [START_REF] Mauro | Similarity learning for graph-based image representations[END_REF]), genetic algorithms ( [START_REF] Liu | Solving weighted graph matching problem by modified microgenetic algorithm[END_REF], [START_REF] Wang | Genetic-based search for errorcorrecting graph isomorphism[END_REF], [START_REF] Perchant | Model-based scene recognition using graph fuzzy homomorphism solved by genetic algorithm[END_REF], [START_REF] Khoo | Multiple relational graphs mapping using genetic algorithms[END_REF] and [START_REF] Riesen | Improving approximate graph edit distance using genetic algorithms[END_REF]), methods based on local properties ( [START_REF] Depiero | Graph matching using a direct classification of node attendance[END_REF], [START_REF] Ozer | A graph based object description for information retrieval in digital image and video libraries[END_REF] and [START_REF] Hlaoui | A new algorithm for graph matching with application to content-based image retrieval[END_REF]) and methods based on tabu research ( [START_REF] Sorlin | Reactive tabu search for measuring graph similarity[END_REF], [START_REF] Adamczewski | Discrete tabu search for graph matching[END_REF]).

Other graph-based methods

In this section we briefly describe some graph-based methods in Pattern Recognition which are not exactly considered as forms of graph matching. However, these approaches can be affiliated to graph matching methods either because they present a manner of comparing two graphs, such as graph embedding and graph kernels, or because they use graphs to classify objects into classes, such as graph clustering and graph learning [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]. In the recent years, graph embedding and graph kernels have received a special attention and have gained popularity ( [START_REF] Gärtner | Kernels for structured data[END_REF] and [START_REF] Bunke | Graph matching-challenges and potential solutions[END_REF]). The authors of [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF] and [START_REF] Bunke | Towards the unification of structural and statistical pattern recognition[END_REF] propose a survey related to graph kernels and graph embedding, in which they present these approaches as a manner to unify the statistical and structural techniques in Pattern Recognition. The authors show how to combine the complementary properties of the statistical and the structural techniques.

We can also cite the Elastic Graph Matching problem (EGM ) which is an image matching problem suing a graph structure. The idea is to superimpose a grid on the model image and define a set of attributes by computing some image features at the intersections of the grid lines. An isomorphic grid is also superimposed on the request image, and is then deformed (using the graph structure) in order to have the best matching between the features computed at the request grid points and the ones computed at the model grid. Several works dealing with the EGM problem have been realized, among them we cite: [START_REF] Wiskott | Face recognition by elastic bunch graph matching[END_REF], [START_REF] Duc | Face authentication with gabor information on deformable graphs[END_REF], [START_REF] Li | Recognizing hand gestures using the weighted elastic graph matching (wegm) method[END_REF], [START_REF] Sato | Multi-scale elastic graph matching for face detection[END_REF], [START_REF] Proença | Periocular biometrics: constraining the elastic graph matching algorithm to biologically plausible distortions[END_REF] and [START_REF] Li | Hegm: A hierarchical elastic graph matching for hand gesture recognition[END_REF].

Graph embedding

Graph embedding approaches are based on a mapping onto a vector space. Graph embedding approaches cover mainly two slightly different categories [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]. The first one includes the methods that match the set of nodes (or substructures) of a graph onto a set of points in a vector space, where similar nodes (or substructures) will be mapped onto close points in the vector space. Several works have been realized

in the literature, we can cite: [START_REF] Caelli | Inexact graph matching using eigen-subspace projection clustering[END_REF], [START_REF] Robles-Kelly | A riemannian approach to graph embedding[END_REF] and [START_REF] Escolano | Information-geometric graph indexing from bags of partial node coverages[END_REF]. The second category includes approaches that match entire graphs onto points in a vector space, where similar Chapter 3. Related work: Graph matching and its applications graphs will be mapped onto close points in the vector space. In this second category of graph embedding, according to the taxonomy proposed in [START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF], we distinguish four approaches. The first approach is the isometric embedding, in which the proposed methods use a similarity measure between graphs and aim to find a mapping to vectors conserving this measure. Among the proposed works in literature, we can cite: [START_REF] Mauro | Similarity learning for graph-based image representations[END_REF], [START_REF] Robles-Kelly | A riemannian approach to graph embedding[END_REF] and [START_REF] Jouili | Graph embedding using constant shift embedding[END_REF]. The second approach is the spectral embedding, in which the proposed methods are based on the use of spectral properties of graphs such as the properties related to the eigenvalues and eigenvectors. Among the proposed works in literature, we can cite: [START_REF] Luo | Spectral embedding of graphs[END_REF], [START_REF] Wilson | Pattern vectors from algebraic graph theory[END_REF], [START_REF] Xiao | Graph characteristics from the heat kernel trace[END_REF] and [START_REF] Xiao | Learning invariant structure for object identification by using graph methods[END_REF]. The third approach is the subpattern embedding, in which the proposed methods aim to classify some specific kinds of subpatterns in the graphs to be embedded. Many works have been proposed in the literature, we can cite: [START_REF] Torsello | Graph embedding using tree edit-union[END_REF], [START_REF] Richiardi | Vector space embedding of undirected graphs with fixed-cardinality vertex sequences for classification[END_REF], [START_REF] Czech | Graph descriptors from b-matrix representation[END_REF], [START_REF] Gibert | Dimensionality reduction for graph of words embedding[END_REF], [START_REF] Gibert | Feature selection on node statistics based embedding of graphs[END_REF], [START_REF] Gibert | Graph embedding in vector spaces by node attribute statistics[END_REF] and [START_REF] Gibert | Embedding of graphs with discrete attributes via label frequencies[END_REF]. The fourth approach is the prototype-based embedding, in which the proposed methods aim to find a mapping of a graph onto a vector space, according to the distances of the graph from a set of supposed graph prototypes, using a defined distance function. Among the proposed works in the literature, we can cite: [START_REF] Torsello | Graph embedding using tree edit-union[END_REF], [START_REF] Riesen | Classifier ensembles for vector space embedding of graphs[END_REF], [START_REF] Lee | A labelled graph based multiple classifier system[END_REF] and [START_REF] Lee | Selecting structural base classifiers for graph-based multiple classifier systems[END_REF]. Several strategies for selecting the graph prototypes have been proposed such as: [START_REF] Riesen | Graph embedding in vector spaces by means of prototype selection[END_REF], [START_REF] Riesen | Classifier ensembles for vector space embedding of graphs[END_REF], [START_REF] Riesen | Non-linear transformations of vector space embedded graphs[END_REF], [START_REF] Riesen | Graph classification based on vector space embedding[END_REF], [START_REF] Riesen | Reducing the dimensionality of dissimilarity space embedding graph kernels[END_REF] and [START_REF] Borzeshi | Discriminative prototype selection methods for graph embedding[END_REF].

Graph kernels

A graph kernel is a symmetric and positive semi-definite function k that maps a couple of graphs from the space of all the graphs G onto a real number, k : G × G → R. Every graph kernel k can be considered as a vector dot product, because they have similar properties. Instead of mapping graphs from G to a feature space and computing their dot product there, the value of kernel function k can simply be evaluated in G [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. Kernel methods allow to extend basic linear algorithms to complex non-linear ones in a unified and elegant way [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF]. Furthermore, kernel methods can replace the dot product in several vector-based algorithms and make standard algorithms, originally developed for vectors, applicable to more complex data structures such as graphs. Consequently, the concept of kernel machines can be extended from vectorial domains to structural domains [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF]. In addition, using graph kernels methods allows to benefit from both the representational power of graphs and the huge number of vector-based algorithms. Hence, kernel methods are more appropriate for difficult Pattern Recognition tasks than traditional methods

Applications of graph matching in Pattern Recognition

under some conditions [START_REF] Vapnik | Statistical learning theory[END_REF]. Several works have been realized in the literature, among them we cite: diffusion kernels ( [START_REF] Kondor | Diffusion kernels on graphs and other discrete input spaces[END_REF], [START_REF] Lebanon | Information diffusion kernels[END_REF] and [START_REF] Lafferty | Diffusion kernels on statistical manifolds[END_REF]), convolution kernel ( [START_REF] Haussler | Convolution kernels on discrete structures[END_REF], [START_REF] Watkins | Dynamic alignment kernels[END_REF] and [START_REF] Watkins | Kernels from matching operations[END_REF]), walk kernel ( [START_REF] Kashima | Kernels for graph classification[END_REF], [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF], [START_REF] Ralaivola | Graph kernels for chemical informatics[END_REF], [START_REF] Borgwardt | Protein function prediction via graph kernels[END_REF], [START_REF] Borgwardt | Shortest-path kernels on graphs[END_REF] and [START_REF] Rossi | A continuous-time quantum walk kernel for unattributed graphs[END_REF]), based on GED ( [START_REF] Neuhaus | Novel kernels for error-tolerant graph classification[END_REF], [START_REF] Gaüzere | Two new graphs kernels in chemoinformatics[END_REF], [START_REF] Gaüzere | Graph kernels: crossing information from different patterns using graph edit distance[END_REF], [START_REF] Grenier | Treelet kernel incorporating chiral information[END_REF]) and other methods ( [START_REF] Kondor | The graphlet spectrum[END_REF], [START_REF] Strug | Using kernels on hierarchical graphs in automatic classification of designs[END_REF] and [START_REF] Bai | Graph kernels from the jensen-shannon divergence[END_REF]).

Graph clustering

Graph clustering approaches cover mainly two different categories. In the first one, a graph is used to represent each pattern and the clustering is realized on the set of graphs. Various works have been realized in this first category, among them we cite: [START_REF] Günter | Self-organizing map for clustering in the graph domain[END_REF], [START_REF] Serratosa | Synthesis of function-described graphs and clustering of attributed graphs[END_REF], [START_REF] Günter | Validation indices for graph clustering[END_REF] and [START_REF] Jain | Graph quantization[END_REF]. In the second category, a graph is used to represent a set of patterns. Each node represent a pattern and edges are used to represent the relationships between couples of patterns. Usually, edges are weighted based on a similarity measure. In this category, the clustering is realized by partitioning the graph's nodes under some conditions. Many works have been realized in this second category, among them we cite: [START_REF] Guigues | The hierarchy of the cocoons of a graph and its application to image segmentation[END_REF], [START_REF] Silva | A partitional clustering algorithm validated by a clustering tendency index based on graph theory[END_REF], [START_REF] Grady | Isoperimetric graph partitioning for image segmentation[END_REF], [START_REF] Franti | Fast agglomerative clustering using a k-nearest neighbor graph[END_REF], [START_REF] Dhillon | Weighted graph cuts without eigenvectors a multilevel approach[END_REF], [START_REF] Foggia | A graph-based algorithm for cluster detection[END_REF], [START_REF] Laskaris | Beyond fcm: Graph-theoretic postprocessing algorithms for learning and representing the data structure[END_REF], [START_REF] Zanghi | Fast online graph clustering via erdősrényi mixture[END_REF], [START_REF] Kim | Clustering with r-regular graphs[END_REF], [START_REF] Wang | Integrated kl (k-means-laplacian) clustering: A new clustering approach by combining attribute data and pairwise relations[END_REF], [START_REF] Zanghi | Clustering based on random graph model embedding vertex features[END_REF], [START_REF] Conte | A method based on the indirect approach for counting people in crowded scenes[END_REF], [START_REF] Mimaroglu | Combining multiple clusterings using similarity graph[END_REF], [START_REF] Couprie | Power watershed: A unifying graph-based optimization framework[END_REF], [START_REF] Nie | Unsupervised and semi-supervised learning via l 1-norm graph[END_REF], [START_REF] Tabatabaei | Ganc: Greedy agglomerative normalized cut for graph clustering[END_REF], [START_REF] Ducournau | A reductive approach to hypergraph clustering: An application to image segmentation[END_REF], [START_REF] Shang | Graph dual regularization non-negative matrix factorization for co-clustering[END_REF] and [START_REF] Lasalle | Multi-threaded modularity based graph clustering using the multilevel paradigm[END_REF].

Graph learning

The term Graph learning represent the learning approaches using graphs and refers mainly to two categories. In the first one, each pattern is represented by a graph.

The class descriptions are also based on graph representation. Various works have been realized in this first category, among them we cite: [START_REF] Neuhaus | Self-organizing maps for learning the edit costs in graph matching[END_REF], [START_REF] Neuhaus | Automatic learning of cost functions for graph edit distance[END_REF], [START_REF] Maulik | Hierarchical pattern discovery in graphs[END_REF], [START_REF] Ferrer | Median graph: A new exact algorithm using a distance based on the maximum common subgraph[END_REF], [START_REF] Ferrer | Generalized median graph computation by means of graph embedding in vector spaces[END_REF], [START_REF] Serratosa | Automatic learning of edit costs based on interactive and adaptive graph recognition[END_REF], [START_REF] Solé-Ribalta | Exploration of the labelling space given graph edit distance costs[END_REF], [START_REF] Ferrer | A generic framework for median graph computation based on a recursive embedding approach[END_REF], [START_REF] Raveaux | Learning graph prototypes for shape recognition[END_REF] and [START_REF] Leordeanu | Unsupervised learning for graph matching[END_REF]. In the second category, a graph is used to represent a set of objects. Each node represents an object and edges are used to represent the relationships between couples of objects. Usually, edges are weighted based on a similarity or distance measure. Many works have been realized in this second category, among them we cite: [START_REF] Culp | Graph-based semisupervised learning[END_REF], [START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF], [START_REF] Hu | Unsupervised active learning based on hierarchical graph-theoretic clustering[END_REF], [START_REF] Rohban | Supervised neighborhood graph construction for semi-supervised classification[END_REF], [START_REF] Wang | Manifold-ranking based retrieval using k-regular nearest neighbor graph[END_REF], [START_REF] Shiga | Efficient semi-supervised learning on locally informative multiple graphs[END_REF], [START_REF] Zhuang | Non-negative low rank and sparse graph for semi-supervised learning[END_REF] and [START_REF] Gao | Optimal graph learning with partial tags and multiple features for image and video annotation[END_REF].

Applications of graph matching in Pattern Recognition

Several applications in Pattern Recognition using graph-based approaches have been proposed in the literature. Graph matching algorithms were the main build of Chapter 3. Related work: Graph matching and its applications these approaches and were evaluated using various applications. Whatever are the considered graph-based applications, a step of graph representation and construction is needed. In this section we present some graph representations used in Pattern recognition. We present also some applications in Pattern recognition, mainly in the fields of 2D and 3D.

Graph representations

In the step of graph representation, nodes, edges and their attributes will be spec- and extracting important regions [START_REF] Neuhaus | A graph matching based approach to fingerprint classification using directional variance[END_REF]. Then, a skeletonized representation of the extracted regions is obtained by applying a process of binarization and thinning.

Applications of graph matching in Pattern Recognition

Ending points and bifurcation points of the resulted skeleton are represented by nodes. Additional nodes are inserted in regular intervals between ending points and bifurcation points. Undirected edges link nodes that are directly connected through a ridge in the skeleton. Nodes are labeled with a two-dimensional attribute giving their positions. Edges are attributed with an angle giving the orientation of the edge with respect to the horizontal direction. Other data sets of the IAM Graph Database Repository (COIL Graphs, Web-page Graphs, AIDS Graphs, Mutagenicity Graphs and Protein Graphs) are detailed in [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF].

In the field of 3D image or object analysis, several graph based methods have been proposed [START_REF] Tangelder | A survey of content based 3d shape retrieval methods[END_REF]. Among them, approaches based on skeletons ( [START_REF] Sundar | Skeleton based shape matching and retrieval[END_REF], [START_REF] Biasotti | An overview on properties and efficacy of topological skeletons in shape modeling[END_REF] and [START_REF] Czajkowska | Skeleton graph matching vs. maximum weight cliques aorta registration techniques[END_REF]), in which the shapes are transformed into skeletons using a process of thinning. Then, the resulted skeletons are compared using graph matching methods. Approaches based on Reeb graphs which are constructed from functions defined on manifold objects. Several works have been proposed such as: [START_REF] Hilaga | Topology matching for fully automatic similarity estimation of 3d shapes[END_REF], [START_REF] Biasotti | 3d shape matching through topological structures[END_REF] and [START_REF] Barra | 3d shape retrieval using kernels on extended reeb graphs[END_REF]. Other graph-based approaches have been proposed, such as methods using shape segmentation, in which the shapes are segmented into a set of components. Then, a graph of these components is constructed, where nodes represent the resulted segments which are linked by edges. Finally, the obtained graphs are compared using graph matching methods. Several works have been realized, among them, we cite: [START_REF] Kalogerakis | A probabilistic model for component-based shape synthesis[END_REF],

[215] and [START_REF] Kleiman | SHED: shape edit distance for fine-grained shape similarity[END_REF]

Pattern Recognition examples using graphs

Various graph-based applications have been proposed in the literature, in many applications fields, among them, we can cite: 2D image analysis ( [START_REF] Wong | An algorithm for graph optimal monomorphism[END_REF], [START_REF] Suganthan | Recognition of handprinted chinese characters by constrained graph matching[END_REF], [START_REF] Pelillo | Matching hierarchical structures using association graphs[END_REF],

[218], [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], [START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF], [START_REF] Yahiaoui | Coloring based approach for matching unrooted and/or unordered trees[END_REF], [START_REF] Serratosa | Fast computation of bipartite graph matching[END_REF], [START_REF] Fischer | Approximation of graph edit distance based on hausdorff matching[END_REF]) and 3D image analysis, in which we can distinguish mainly two categories, rigid objects and non-rigid or deformable objects. In the first category, rigid objects are considered such as: a car, a chair, a bowl, ..., etc. Deformable objects can be also considered in the first category. However, each position of a deformable object is considered as a different object associated to a different class, for example, we associate each position of the human body (sitting, standing, hands raised, etc.) to a deferent class. In the second category, deformable objects are considered such as humans and animals. Unlike the first category, we associated one class to each deformable object, whatever the different positions. Various works have been realized in the field of 3D object analysis, among them: [START_REF] Christmas | Structural matching in computer vision using probabilistic relaxation[END_REF], [START_REF] Fuchs | Efficient subgraph isomorphism with 'a priori'knowledge[END_REF], [START_REF] Myers | Bayesian graph edit distance[END_REF],

Chapter 3. Related work: Graph matching and its applications [START_REF] Shokoufandeh | A unified framework for indexing and matching hierarchical shape structures[END_REF], [START_REF] Shokoufandeh | A unified framework for indexing and matching hierarchical shape structures[END_REF], [START_REF] Luo | Structural graph matching using the em algorithm and singular value decomposition[END_REF], [START_REF] Dimaio | Belief propagation in large, highly connected graphs for 3d part-based object recognition[END_REF], [START_REF] Su | Shape memorization and recognition of 3d objects using a similarity-based aspect-graph approach[END_REF], [START_REF] Cyr | 3d object recognition using shape similiaritybased aspect graph[END_REF], [START_REF] Bauckhage | 3d assembly recognition by matching functional subparts[END_REF], [START_REF] Garro | Scale space graph representation and kernel matching for non rigid and textured 3d shape retrieval[END_REF]. Document analysis including handwritten recognition (string, letters and digits) in different languages (Roman, Arabic, Chinese, etc.), symbol and graphics recognition. Several works have been realised in the field of Document analysis, among them, we cite: ( [START_REF] Filatov | Graph-based handwritten digit string recognition[END_REF], [START_REF] Foggia | Definition and validation of a distance measure between structural primitives[END_REF], [START_REF] Liu | Two-layer assignment method for online chinese character recognition[END_REF], [START_REF] Foggia | Symbolic vs. connectionist learning: an experimental comparison in a structured domain[END_REF], [START_REF] Lladós | Symbol recognition by error-tolerant subgraph matching between region adjacency graphs[END_REF], [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF], [START_REF] Zanibbi | Recognition and retrieval of mathematical expressions[END_REF], [START_REF] Serratosa | Component retrieval based on a database of graphs for hand-written electronic-scheme digitalisation[END_REF], [START_REF] Riesen | Iterative bipartite graph edit distance approximation[END_REF], [START_REF] Fischer | Approximation of graph edit distance based on hausdorff matching[END_REF], [START_REF] Riba | Handwritten word spotting by inexact matching of grapheme graphs[END_REF]). Biometric identification, including face recognition, face mentions and expressions recognition, fingerprint recognition, etc. Various works have been realized in this field, among them, we cite: [START_REF] Lades | Distortion invariant object recognition in the dynamic link architecture[END_REF], [START_REF] Maio | A structural approach to fingerprint classification[END_REF], [START_REF] Elagin | Automatic pose estimation system for human faces based on bunch graph matching technology[END_REF], [START_REF] Duc | Face authentication with gabor information on deformable graphs[END_REF], [START_REF] Kotropoulos | Frontal face authentication using morphological elastic graph matching[END_REF], [START_REF] Hong | Learning patterns from images by combining soft decisions and hard decisions[END_REF], [START_REF] Lim | Facial landmarks localization based on fuzzy and gabor wavelet graph matching[END_REF], [START_REF] Abdullah | Face recognition with symmetric local graph structure (slgs)[END_REF], [START_REF] Jin | Non-invertible analysis on graph-based hamming embedding transform for protecting fingerprint minutiae[END_REF], [START_REF] Cui | Discriminant non-negative graph embedding for face recognition[END_REF], [START_REF] Pawar | K-means graph database clustering and matching for fingerprint recognition[END_REF]. Medical images analysis, among them: [START_REF] Gao | Finding frequent approximate subgraphs in medical image database[END_REF], [START_REF] Hernandez | A novel graph-based approach for determining molecular similarity[END_REF] and [START_REF] Gao | Graph modeling and mining methods for brain images[END_REF], etc. Other graph-based applications have been proposed in the literature in other fields, among them, we cite:

Image database, Web-pages data, Video analysis, etc.

Conclusions

In this chapter, we presented and discussed a state of the art related to graph matching algorithms. The state of the art presented in this chapter only provides the necessary elements for understanding this thesis and placing it within the appropriate context. We surveyed graph matching algorithms available in the literature and especially the recent ones and we described the different classes of graph matching algorithms. We also presented some applications of graph-based approaches in Pattern Recognition. Kites are huge archaeological structures of stone visible from satellite images. Because of their important number and their wide geographical distribution, automatic recognition of these structures on satellite images is an important step towards understanding these enigmatic remnants. Kites are naturally represented by graphs.

In this chapter, we present the process of Kite graph construction from real images, and the process of generating a synthetic data set of Kite graphs generated randomly.

The two data sets (real and synthetic) are used to validate our algorithms.

This chapter is organized as follows: in Section 4.1, we give a short overview describing the archaeological structure called Kites. In Section 4.2, we explain the process of constructing and generating the real and synthetic Kite graph data sets.

Section 4.3 concludes the chapter.

Kite

A Kite is an archaeological structure consisting of two long walls built of stones and arranged within a funnel shape opening onto an enclosure. The walls can reach a length of several kilometers and the enclosure can cover an area of several hectares.

This yields huge constructions that are visible on satellite images as depicted in often absent [START_REF] Échallier | Nature and function of 'desert kites': new datta and hypothesis[END_REF][START_REF] Helms | The desert 'kites' of the badiyat esh-sham and north arabia[END_REF]. Recently, public access to high resolution satellite images (Google Earth, Bing) has significantly expanded the number of discovered Kites and also enlarged their geographical spread from the south of the Arabian Peninsula to the Aralo-Caspian region [START_REF] Barge | Visible from space, understood during the fieldwork: the example of desert kites in Armenia[END_REF]. The massive use of Kites, judging by the density of these structures, probably had territorial implications and socioeconomic importance in a region that has seen the advent of agriculture and the birth of the urban phenomenon. Kites are thus an underestimated phenomenon. Establishing the duration of their utilization, outlining their use and functioning, and trying to identify the population responsible for these constructions are the challenges that would highlight the significance of this unknown phenomenon. However, these issues cannot be seriously addressed without an almost exhaustive inventory of these structures [START_REF] Crassard | Addressing the desert kites phenomenon and its global range through a multi-proxy approach[END_REF]. For this purpose, automatic recognition of Kites on satellite images offers archeologists valuable help in understanding this phenomenon. This will allow a systematic and homogeneous search in the entire distribution area of Kites and then in the peripheral regions.

Kite graph data-set construction

In this section, we present the process of Kite graph construction from real images, and the process of generating a synthetic data set of Kite graphs generated randomly.

The two data sets (real and synthetic) are used to evaluate the efficiency and the resilience of the proposed approach (described in Chapter 5).

Real data set construction

On satellite images, Kites appear as flat surfaces delimited by a set of lines as illustrated in (Figure 4.1(a)). To convert Kites' images into attributed graphs, the (segment or line) detection in images is an intensively studied topic in image analysis [START_REF] Illingworth | A survey of the hough transform[END_REF][START_REF] Desolneux | Meaningful alignments[END_REF]. Besides, several recent methods such as [START_REF] Lacoste | Point processes for unsupervised line network extraction in remote sensing[END_REF][START_REF] Rochery | Higher order active contours[END_REF][START_REF] Gioi | Lsd: A fast line segment detector with a false detection control[END_REF] give good results on satellite images. The main difficulty with such methods is to find the adequate settings to obtain an acceptable segment detection for a specific application. For Kites, we investigated several solutions with various settings and the LSD algorithm [START_REF] Gioi | Lsd: A fast line segment detector with a false detection control[END_REF] gave us the most satisfactory set of segments (see Figure 4.1(b)). The LSD algorithm is followed by four steps to obtain the final Kite graphs:

• Deleting isolated segments: We consider that a segment is isolated if its length is less than a threshold length min and if it has no neighbors according to a minimum neighborhood distance neighbor min .

• Merging neighboring segments: During this step, each pair of segments that are neighbors according to neighbor min , do not cross each other and have the same angle with the horizontal line with a tolerance angle delta, are merged in one segment.

length min , neighbor min and delta are set during experimentations. Deleting isolated segments and merging neighboring ones are illustrated in Figure 4.1(c).

• Thinning segments: In this step, a skeleton is generated by reducing the width of all the segments to 1 pixel (see Figure 4.1(d)) using the Skeletonize "ImageJ" method, which is the implementation of the approach described in [START_REF] Lee | Building skeleton models via 3-d medial surface/axis thinning algorithms[END_REF].

• Graph construction: Finally, we construct the graph from the skeleton by representing lines by edges and ending points of lines by vertices (Figure 4.1(e)). Each vertex is labeled with a two-dimensional attribute giving its position and an n-dimensional attribute containing the angles between every pair of consecutive incident edges. According to the state of preservation of the Kite, a graph obtained by this process can have a single connected component (i.e., the Kite is totally preserved) or it can be composed by two or more connected components (i.e., some parts of the Kite have been destroyed).

We executed our algorithm on 350 images (250 with Kites and 100 without Kites)

with different states of preservation. We classified the obtained graphs into four preservation levels:

1. State I: The Kite is entire and well preserved. The Kite graph obtained is perfect and the few disconnections found are corrected manually with the help of the archeologists.

State II:

The Kite is entire and well preserved. The Kite graph may be disconnected but the disconnections are neither frequent nor important.

State III:

The Kite graph is very disconnected. Some parts of the Kite are not present.

State IV:

The graph is not a Kite. These graphs are obtained by executing the algorithm on images that do not contain Kites. These images are extracted near (geographical positions) the images containing Kites, so these images have the same reliefs as the images containing the Kites, and the graphs obtained represent structures close to Kites.

Conclusion

In this chapter, we introduced a graph representation of Kites and we proposed an automatic process for extracting and transforming Kites from satellite images into a set of graphs. We also proposed a process of generating randomly a synthetic data In this chapter, we propose 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 leading to an efficient Kite identification process. We analyze the time complexity of the proposed algorithms and conduct extensive experiments on both real and synthetic Kite graph data sets to attest the effectiveness of the proposed approach. We also perform a set of experimentations on other data sets in order to show that the proposed approach is extensible and quite general.

Introduction

Kite recognition as a graph matching problem is interesting because it raises several challenges not addressed by existing methods. In fact, Kite graphs are not connected and may contain several parts. They have specific geometric forms that distinguish them from other constructions. Furthermore, each processed image can involve a large number of graphs, thus implying the use of rapid recognition algorithms. To We compare our work with existing methods using the two data sets (real and synthetic) Kite graphs and we also apply it to other data sets mainly characterized by the geometric form of the graphs. These experimentations show that the proposed framework is a practical and efficient Kite recognition tool that applies directly to images. The realized experiments show also that the proposed approach is quite general.

The rest of the chapter is organized as follows: Section 5.2 describes the proposed similarity measure and presents its complexity analysis. Section 5.3 reports our experimental results and finally, Section 5.4 concludes the chapter.

Algorithm overview

In this section, we describe the proposed Kite recognition solution, which is a hierarchical graph-based approach consisting of: approaches measuring the distance between two graphs and a reconstruction process. Firstly we present the proposed approaches measuring the distance between two graphs: a global similarity measure denoted Global, a geometric local similarity measure denoted GeoLocal and two varieties of hierarchical measures that we call Global GeoLocal and GeoLocal Global which are the result of combining Global and GeoLocal depending on the defined order.

The global similarity Global is a fast computable measure based on graph invariants.

This similarity aims to rapidly discard the graphs that cannot be Kites and avoid unnecessary and more costly comparisons. The geometric local similarity GeoLocal is a more accurate measure based on the geometric form and the structured features extracted from the graphs. This similarity is based on graph edit distance GED to deal with the state of preservation of the Kites. Secondly, we present the reconstruction process, which aims to verify if the different connected components of the graph identified as Kite components (enclosure and antenna) constitute a Kite.

Identification of the different connected components of the graph as Kite components is realized using one of the proposed approaches of graph similarity measure,

Algorithm overview

Symbol Description

G(V, E)

undirected labeled graph where V is its vertex set and E its edge set.

Both vertices and edges are labeled.

V (G) vertex set of graph G. E(G) edge set of graph G. deg(v) degree of vertex v.

Δ(G)

the greatest vertex degree in graph G.

(e) the label of edge e.

A(G)

the greatest angle in graph G.

L(G)

the greatest edge label in graph G. S size of the set S.

(∠v 1 v 2 v 3 ) G i the angle between the two edges (v1, v2) and (v2, v3) in the graph G i . GeoLocal Global . Finally, we present the computational complexity of the proposed algorithm.

Table 5.1 summarizes the notation that we use in the remainder of this chapter.

Global similarity

Global similarity computes graph invariants. We consider the number of vertices of the compared graphs, the labels of the edges, which correspond to the length of the Kite walls, and the angles between edges. So, the global similarity between two graphs G 1 and G 2 is given by:

Global(G 1 , G 2 ) = w 1 * d V ertices (G 1 , G 2 ) + w 2 * d Edges (G 1 , G 2 ) + w 3 * d Angles (G 1 , G 2 ) + w 4 * d Convex (G 1 , G 2 ) (5.1)
where w i is a weighting coefficient with i=4 i=1 w i = 1, d V ertices (G 1 , G 2 ) compares the order of the two graphs.

d V ertices (G 1 , G 2 ) = V (G 1 ) -V (G 2 ) Max V (G 1 ) , V (G 2 ) (5.2) Chapter 5. Geometric Graph Matching d Edges (G 1 , G 2 )
compares the global size of the two Kites by comparing the distances reported on the edges of the corresponding graphs.

d Edges (G 1 , G 2 ) = E(G1) (e i ) i=1 - E(G2) (e j ) j=1 Max E(G1) (e i ) i=1 , E(G2) (e j ) j=1 (5.3) d Convex (G 1 , G 2 ) and d Angles (G 1 , G 2 )
compare the global geometric forms of the two Kites based on the convexity of the angles and the total value of the angles, respectively:

d Convex (G 1 , G 2 ) = a ∈ Angles G1 , a < ConvexityT h Angles G1 - b ∈ Angles G2 , b < ConvexityT h Angles G2 (5.4)
where Angles Gi denotes the set of angles of graph G i and ConvexityT h is an angle threshold at most equal to 180 • . However, it will be defined according to the form of the Kites.

d Angles (G 1 , G 2 ) = | Angle i,G1 -Angle j,G2 | Max( Angle i,G1 , Angle j,G2 ) (5.5)
where Angle i,G denotes the i th angle of graph G.

The algorithm takes as inputs a set of prototype graphs, which are: G Antenna , G Enclosure , four different G Kite and a query graph. For each connected component of the query graph, the algorithm returns the most similar Kite component.

Geometric local similarity

The geometric local similarity measure GeoLocal is a distance based on the approximation of the graph edit distance that compares the graphs using local descriptions of substructures (see Figure 2.8). However, unlike the approaches proposed in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Raveaux | A graph matching method and a graph matching distance based on subgraph assignments[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF], in our approach we extended local descriptions by considering angles in addition to degrees of vertices and labels of the edges. This allows us to distinguish between two isomorphic graphs with different geometry (Figure 5.1(a)). In fact, almost all existing graph similarity measures compare the structures of graphs in terms of vertices, edges and their labels, but they do not consider the geometric form of these graphs. Some authors even use the angle as an attribute or a label

Algorithm overview

associated with an edge [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF]. This attribute represents the angle between the considered edge and a horizontal or a vertical line landmark (Figure 5.1(d, e)). The drawback of this representation is that the value of the angle may change if a rotation is applied. This is not a problem in some graph representations such as graphs representing letters, digits, etc. However, considering a model that resists rotation and other deformations is very important when the graphs represent objects with specific forms as is the case of Kite graphs. Thus, in our framework two graphs are isomorphic if they also have the same form according to the following definition.

Definition 1 (geometrical isomorphic) Let G 1 (V 1 , E 1 ) and G 2 (V 2 , E 2 )
1 v 2 v 3 ) G3 = (∠v 1 v 2 v 3 ) G4 = (∠v 1 v 2 v 3 ) G5 ).
However, if we consider angles between edges and the horizontal axis x, G 3 and G 5 in (Figure 5.1(d, e)) are isomorphic but not geometrical isomorphic : (α 1, G3 = β 1, G5

and α 2, G3 = β 2, G5 ).

In order to compute the geometric local similarity, each vertex v is represented by a signature i.e., a vector defining its local structure as follows:

s(v) = {deg(v), { Ang i , (e i, 1 ), (e i, 2 ) } (deg(v)-1) 1
}, where:

• deg(v) is the degree of the vertex v.

• (e i, 1 ) and (e i, 2 ) are the labels (weights) of the two edges constituting the angle Ang i . (e i, 1 ) and (e i, 2 ) are ranked in descending order.

• The triplets { Ang i , (e i, 1 ), (e i, 2 ) } are ranked according to the angle Ang i in descending order.

• All the vertices are represented by signatures i.e. vectors which have the same

size: size = 1 + ((Δ(G 1 , G 2 ) -1) * 3).
• Δ(G 1 , G 2 )
is the greatest vertex degree in the compared graphs G 1 and G 2 .

• If a vertex v has a degree less than Δ(G 1 , G 2 ) , the rest of the vector is completed with zeros.

The similarity measure d between two signatures s 1 and s 2 is computed as follows:

d(s 1 , s 2 ) = 1 - i=3 i=1 ω i * F i (5.6)
The functions F i are defined as follows:

F 1 = |deg(v 1 ) -deg(v 2 )| Max(Δ(G 1 ), Δ(G 2 )) (5.7) F 2 = Max(Δ(G1),Δ(G2)) k=1 | (e 1,k ) -(e 2,k )| Max(Δ(G 1 ), Δ(G 2 )) * Max(L(G 1 ), L(G 2 )) (5.8) 56

Algorithm overview

F 3 = Max(Δ(G1),Δ(G2))-1 k=1 |Ang 1,k -Ang 2,k | (Max(Δ(G 1 ), Δ(G 2 )) -1) * Max(A(G 1 ), A(G 2 ))
(5.9)

where ω i are weighting coefficients with i=3 i=1 ω i = 1, Ang i, k is the k th angle of vertex v i . F i=1...3 compares, respectively, the degree of the vertices, the labels of edges and the angles.

The Geometric Local Similarity GeoLocal aims to determine the best matching between the signatures (defining the local structure of each vertex) associated with the two compared graphs. Formally, let G 1 and G 2 be two graphs, S 1 and S 2 their corresponding sets of signatures, and M the set of all possible matching between S 1 and S 2 . The similarity GeoLocal(S 1 , S 2 ) is formulated as follows:

GeoLocal(S 1 , S 2 ) = 1 - Max m ∈ M si ∈ S1, m(si) ∈ S2 d(s i , m(s i )) Max( S 1 , S 2 ) (5.10)
Computation of GeoLocal(S 1 , S 2 ) is equivalent to solving the assignment problem which is a fundamental combinatorial optimization problem that aims to find the minimum/maximum weight matching in a weighted bipartite graph. To solve this assignment problem, we define a n × n matrix D, where n = max( S 1 , S 2 ).

Each element D i,j of the matrix represents the similarity measure d(s i , s j ) between a signature s i in S 1 and a signature s j in S 2 . In the case of S 1 = S 2 , the smallest set of signatures is completed by

(max(||S 1 ||, ||S 2 ||) -min(||S 1 ||, ||S 2 ||))
empty signatures ε. The similarity between an empty signature ε and a signature s is computed by the formula (Eq. 5.6) and corresponds to the cost of adding s to the small graph (or of deleting s from the large graph).

We apply the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] on the matrix D in order to find the best assignment in O(n 3 ) time.

The resulting distance (dissimilarity) is compared to a threshold th ∈ [0, 1] defined by an expert or by experimentation, in order to decide if the compared graphs are similar or not. Like the algorithm of Global, the algorithm of GeoLocal takes as inputs a set of prototype graphs, which are: G Antenna , G Enclosure , four different G Kite and a query graph. For each connected component of the query graph, the algorithm returns the most similar Kite component.

Hierarchical similarity measure

In this section, we present two hierarchical measures that we call Global GeoLocal and GeoLocal Global which are the result of combining the global similarity measure Global and the geometric local similarity measure GeoLocal depending on the defined order.

Global geometric-Local similarity The Global geometric-Local similarity

Global GeoLocal is a hierarchical similarity measure, which aims to measure the distance between two graphs using firstly the global similarity measure Global, then using the geometric local similarity measure GeoLocal if necessary. The main idea is to measure the distance between the two graphs using Global. If the distance obtained is less than a specific threshold, which means that the two graphs are similar accord-

Algorithm overview

ing to Global, then we check this result using GeoLocal. Otherwise, the two graphs are not similar, which means that we do not need to use GeoLocal. Global GeoLocal aims to enhance time processing of Kite graphs by first computing invariants on the graphs. Formally, let G 1 and G 2 be two graphs, S 1 and S 2 the set of signatures of G 1 and G 2 respectively, th ∈ [0, 1] a threshold and

d 1 = Global(G 1 , G 2 ). Global GeoLocal (G 1 , G 2 ) = ⎧ ⎨ ⎩ d 1 , if d 1 > th GeoLocal(S 1 , S 2 ), otherwise (5.11) Geometric-Local Global similarity Like Global GeoLocal , the Geometric-Local
Global similarity GeoLocal Global is a hierarchical similarity measure, which aims to measure the distance between two graphs using firstly GeoLocal, then using Global if necessary. The main idea is to measure the distance between the two graphs using

GeoLocal. If the distance obtained is less than a specific threshold, which means that the two graphs are similar according to GeoLocal, then we check this result using Global. Otherwise, the two graphs are not similar, which means we do not need to use Global. However, only the vertices assigned in the phase of GeoLocal will be considered in the second phase using Global. In the case where the two graphs have the same number of vertices, all the vertices will be considered in the GeoLocal

Global (G 1 , G 2 ) = ⎧ ⎨ ⎩ d 2 , if d 2 > th Global(G 1 , G 2 ), otherwise
(5.12) The principle is to associate a subset of Kite parts classified as antennas to a Kite part classified as an enclosure, taking into account the distance between them and their orientations. The aggregated similarity Sim aggre of the reconstructed Kite i, is given by:

Reconstruction process

Sim aggre (Kite i ) = ψ * Sim(E i ) + j=n j=1 μ * Sim(A i,j ) (5.13)
Where: ψ + μ = 1, Sim(E i ) is the similarity attributed to the enclosure of the reconstructed Kite i, n is the number of antennas and Sim(A i,j ) is the similarity attributed to an antenna j of the reconstructed Kite i.

Complexity study

For the Geometric local similarity measure GeoLocal, the most important part, in term of complexity, is the one solving the assignment problem. We used the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] to find the best assignment in O(n 3 ) time, where n is the maximum number of vertices in the two compared graphs. Consequently, the time complexity of GeoLocal is O(n 3 ). The Global similarity measure Global is based on a graph invariant, which is linear in terms of computational complexity. Thus, the time complexity of Global is O(n), where n is the maximum number of vertices in the two compared graphs.

Experimental results

For evaluation, we used all the available graphs in the real data set described in Section 4.2.1 and the synthetic data set described in Section 4.2.2. We also used a well-known graph data set of symbols from architectural and electronic drawings named GREC [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF], which is one of the data sets of the IAM graph database repository. The GREC data set is composed of 1100 undirected graphs distributed over 22 classes from the original GREC database [START_REF] Dosch | Report on the second symbol recognition contest[END_REF]. The GREC data set is split into a training and a validation set, each of size 286, and a test set of size 528.

Experimental results

We conducted four series of experiments to evaluate the robustness and accuracy of our similarity measures. The first three series of experiments are realized on the real and synthetic Kite graph database, while the fourth experimentation is realized on the GREC data set. We compared our approach with two approaches from the state-of-the-art based on local structure comparison:

• GED Bipartite : a GED based on a bipartite assignment of vertices and their local structures [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF].

• Beam GED : a simple and fast suboptimal GED based on beam search [START_REF] Neuhaus | Fast suboptimal algorithms for the computation of graph edit distance[END_REF].

The proposed distances GeoLocal and Global are parameterized distances having a set of parameters α k allowing different configurations. The default value is:

α k = 1 and ConvexityT h = 150 • .
In addition, we defined a threshold in order to improve classification accuracy. The parameters α k and the threshold may be specified by inspection or by using machine learning techniques. In this chapter, for simplicity, we attribute to all the parameters of our methods and the methods with which we compare (GED Bipartite and Beam GED ) their default values. However, for each approach we choose the threshold giving the best accuracy.

The default parameters of GED Bipartite and Beam GED are: the same cost for vertex/edge deletions/insertions which is 1, the weighting parameters per vertex/edge is the same 1, the same cost for vertices and edges (vertexCost = edgeCost) and for Beam GED , the size of the OPEN set is 10.

In the first experiment, we show the impact of using the reconstruction process in the obtained accuracy. We can see that the four methods are globally more accurate with considering the process of reconstruction. This shows the importance of using the reconstruction process.

In the second series of experiments, we evaluated the accuracy of the proposed approach by performing classification. These experiments are realized on both the real and the synthetic Kite data set. GeoLocal Global avoids unnecessary comparison in the second level, thus the general runtime on the data set is better. We note also that GeoLocal Global achieves better classification accuracy compared to Global GeoLocal at all the levels of the real and the synthetic Kite data sets. However, Global GeoLocal achieves a better general runtime on the data set, due to the fact that Global is faster than GeoLocal.

In the third series of experiments we evaluated the scalability of our approach over an increasing number of vertices in the query graphs. These experiments are realized on both the real Kite data set and the synthetic Kite data set. From the 4081 graphs of the real Kite data set and 1000 graphs of the synthetic Kite data set, we Finally, we evaluated the accuracy of the proposed approach by performing classification on the GREC data set. We compare the results obtained by our approach

GeoLocal with the results obtained by GED Bipartite and Beam GED in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF]. Table 5.4

depicts the results obtained by our approach GeoLocal using the adequate threshold (0.07) and GED Bipartite and Beam GED . We can see that our method GeoLocal is more accurate than the two methods with which we compare GED Bipartite and Beam GED on the GREC data set. This confirms that considering the geometric form (angles) has a high added value for object recognition with specific geometric structures. This also shows that our method is extensible on other types of data and proves that the proposed approach is quite general.

Methods

GeoLocal GED

Conclusions

In this chapter, we proposed a novel geometric hierarchical graph matching method based on graph edit distance and graph invariants. The proposed method takes into account the geometric form of the graphs in addition to their structures. Both the theoretical time complexity and the experimental results on real and synthetic Kite data sets confirm the high performance of our approach. Furthermore, the experimentation performed on the GREC data set [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF] proves that the proposed

Conclusions

approach is extensible and quite general.

Part II

Inexact graph matching for 3D object recognition

Introduction to Part II

In the field of 3D object recognition, it is often required to compare different 3D objects represented by graphs. Using triangular tessellations, 3D objects may be compared with graph matching techniques. This part addresses the problem of comparing deformable or non-rigid 3D objects (such as human and animal bodies).

The shapes considered are represented by graphs, i.e., triangular tessellations. We

propose a new distance for comparing deformable 3D objects. This distance is based on the decomposition of triangular tessellations into a set of substructures that we call triangle-stars. A triangle-star is a connected component formed by the union of a triangle and its neighborhood. The proposed decomposition offers a parameterizable triangle-stars depending on the degree of the neighborhood considered. The number of triangle-stars obtained is much smaller than the number of nodes and the number of classic stars [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] and, as a result, the computational complexity is reduced. The proposed graph edit distance is based on triangle-stars which is a local structure that covers a larger neighborhood than a classic star decomposition [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF].

Consequently, the proposed dissimilarity measure assures an optimal approximation. This is justified by the fact that optimal methods are based on graph's global structures and, consequently, a larger local structure allows to be closer to the global one.

The distance that we propose uses a set of parameters which are either invariant or at least oblivious under most common deformations. We prove that the proposed distance is a pseudo-metric. We analyse its time complexity and we present a set of experimental results which confirm the high performance of our approach.

This part contains two chapters, in the first one (Chapter 6), we present the proposed decomposition of triangular tessellations into triangle-stars. We describe the proposed distance (dissimilarity measure). We prove that the proposed distance is a pseudo-metric and we analyse its time complexity. In the second chapter (Chapter 7), we describe the experimentations that we undertook to evaluate our approach.

We present the different databases that we use in our experiments, some state of the art shape-matching algorithms to compare with, the evaluation criteria and the experimental results.

Chapter 6

Graph-based approach for non-rigid 3D Object Recognition The remainder of the chapter is organized as follows. Firstly, in Section 6.1, we give an overview of the proposed approach. In Section 6.2, we introduce a set of concepts defining the triangle-stars substructures. In Section 6.3, we describe Chapter 6. Graph-based approach for non-rigid 3D Object Recognition the triangle order considered for the proposed decomposition method of triangular tessellations into a set of triangle-stars described in Section 6.4. In Section 6.5, we describe the proposed distance, we analyse its complexity in Section 6.7. Finally, Section 6.8 concludes the chapter.

Algorithm overview

We propose a new decomposition of triangular tessellations into connected components that we call triangle-stars. This decomposition aims to reduce the number of components while covering a larger number of neighbors. The neighborhood area covered by a triangle-star is parameterizable and depends on the N k order neighborhood considered in the proposed decomposition. In addition, this decomposition allows obtaining a representation which is invariant or at least oblivious under most common deformations. Prior to the decomposition, a strict total order on the triangles must be established. This order aims to reduce the number of triangle-stars that is generated and guarantees the uniqueness of the resulting decomposition. Finally, we propose a distance (dissimilarity measure) between the triangle-stars of the two triangular tessellations and address their matching. We also prove that the proposed distance is a pseudo-metric. We present the computational complexity of the proposed algorithm.

Graph decomposition

We propose a decomposition of a triangular tessellation graph into a set of connected components that we call triangle-stars (T S). We define the concept of triangle-star as follows:

Definition 1 (Triangular tessellations): A triangular tessellation g T r is a graph defined by a set of nodes, edges and triangles. Formally, g T r is a graph defined by a six tuple g T r = (N, E, T, α, β, θ), where T is a set of triangles and θ : T → L T is a labelling function and, L T is the set of triangle labels. In the case of k = 1, the N k -neighborhood is equivalent to a simple neighborhood (Definition 2).

Definition 4 (triangle-star): A triangle-star ts is a labelled sub-graph, defined by a triangle and a set of its neighbors. Formally, a triangle-star ts is a three tuple ts = (t r , T , θ), where: t r is the root triangle, T is the set of adjacent triangles and Example 1. Let a graph-tessellation G tr containing 17 triangles t 0...16 . Table 6.1

θ : T → L T is
shows the graph-tessellation G tr and the N k -triangle-stars of the triangle t 0 depending on the N k=0...2 neighborhood considered. In the case of N k=0 , the graphtessellation is decomposed into 17 triangle-stars (17 N 0 -T S, exactly the same number of triangles). Each triangle-star is constituted only by one triangle without any triangle neighbors. Thus, the resulted triangle-star N 0 -T S of the triangle t 0 is constituted only by the triangle t 0 . In the case of N k=1 , only the direct triangle neighbors are considered which means that the graph-tessellation is decomposed to a set of triangle-stars constituted using a triangle with its neighbors (See Definition 2). Thus, the resulted triangle-star N 1 -T S of the triangle t 0 is constituted by the triangle t 0 and its N 1 -neighbors (direct neighbors), i.e, T (N 1 -T S) = {t 0...7 }. In the case of N k=2 , the N 2 -neighbors are considered which means that the graphtessellation is decomposed into a set of triangle-stars constituted using a triangle with its N 2 -neighbors (See Definition 3). Thus, the resulted triangle-star N 2 -T S Chapter 6. Graph-based approach for non-rigid 3D Object Recognition of the triangle t 0 , is constituted by the triangle t 0 and its N 2 -neighbors (second degree neighborhood). T (N 2 -T S) = {t 0...16 }. In this example, T (N 2 -T S) is the all graph-tessellation G tr .

Graph G tr

The N 0 -T S of the triangle t0

The N 1 -T S of the triangle t0

The N 2 -T S of the triangle t0 Table 6.1: Example, N k -triangle-stars.

Triangle-star features: Each triangle t j is defined with six-tuple t j = (n 1 , n 2 , n 3 , e 1 , e 2 , e 3 ). The nodes n i are labelled by their Cartesian coordinates. In our case, the nodes n i are labelled with three coordinates n i = (x, y, z) corresponding to the three dimensions. The edges e k = (n p , n w ) are labelled (weighted) with the Euclidian distance between their associated nodes (n p , n w ). The triangles are labelled by a three-tuple t j = (id, Area, P erimeter), where id is a number. Each triangle-star is characterised by a set of descriptors, allowing the evaluation of the dissimilarity between triangle-stars. We consider the following descriptors: Area of triangle-star, Perimeter of triangle-star, Area of the triangles forming the triangle-stars, their

Perimeters, the Weights associated with their edges, and the Degrees of their nodes.

Graph decomposition

Our choice of the set of geometrical descriptors like the weights of edges and the area and the perimeter of the triangles and the triangle-stars, is justified by the fact that those geometrical descriptors are oblivious under different deformations and if necessary invariants (as required in some fields) by normalizing the weights of the edges and consequently the area and the perimeter. The normalization is realized according to the maximum edge's weight W MAX .

Triangle-star Vector representation: A vector representation is associated to each triangle-star, the vector contains the global area AG of the triangle-star, the global perimeter P G of the triangle-star, the area A and the perimeter P of each triangles of the triangle-star, the weights of edges W of the triangle-star and the degrees of nodes deg of the triangle-star. The vector representation of triangle-star is given by (see Table 6.5 for symbols descriptions):

{AG(ts), PG(ts), {A(t i ), P(t i ), W(t i, j=1...3 ), deg(t i, j=1...3 )} i= T (ts) i=1
} where:

• The triangles of triangle-star ts are ranked according to their areas (descending order).

• The weights of edges are ranked by descending order.

• The degrees of nodes are ranked by descending order.

• All triangle-stars T S are represented by vectors which has the same size :

size = 2 + (Γ * 8).
• Γ is the maximum number of triangles in the two sets of triangle-stars in the two compared graphs.

• If a triangle-star ts has a number of triangle less than Γ , the rest of the vector is completed with zeros.

Definition 6 (Disjoint triangle-stars): Two triangle-stars ts i and ts j are disjoints, if they do not share a common triangle. let i = j, ts i and ts j are disjoints ⇒ T (ts i ) ∩ T (ts j ) = ∅.

Definition 7 (Geodesic Distance):

The geodesic distance is the length of the shortest path λ ∈ Λ (with Λ is the set of all paths) between two points p i and p j .

Chapter 6. Graph-based approach for non-rigid 3D Object Recognition

The considered path must entirely lie within the object [START_REF] Paquet | Physics-based measurements, reflective measurements and meta-measurements for nonrigid and deformable shapes with application to structural proteomics and macromolecular docking[END_REF]. The geodesic distance GD is defined as follow:

GD λ (p i , p j ) = arg min λ ∈ Λ λ ds 6.

Triangles ordering

The proposed method of decomposition, allows to have disjoint triangle-stars (Definition 6), which significantly reduces the number of components ( T S N < T , see Figure 6.1) while reducing the number of comparisons in between the triangle-stars associated with the two triangular tessellations. However, according to the order considered, the set of triangle-stars obtained may be different (see Example 2). Indeed, the same triangular tessellation may generate different sets of triangle-stars, both in terms of cardinality and in terms of triangle-stars obtained, if the ordering of the triangles is not the same.

In order to ensure the uniqueness of the decomposition and a further reduced number of triangle-stars, a descending strict total order must be established on the set of triangles prior to their decomposition into triangle-stars (see Example 3).

The Figure 6.2 presents the average number of T S (N 1 -T S) obtained in the TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF] (See Section 7.1.1 for TOSCA database description) depending on the triangles order considered. This plot shows that considering a N eighbours (T riangles) descending order give the minimum number of triangle-stars T S, which reduces the complexity of the proposed algorithm.

In order to establish a descending strict total order on the triangles set, each triangle is represented by a 10-tuple < neighbors ; x 1 , y 1 , z 1 ; x 2 , y 2 , z 2 ; x 3 , y 3 , z The first step is to select six nodes n 1...6 . The two nodes n 1 and n 2 are selected as the two nodes which have the largest geodesic distance GD(n 1 , n 2 ).

The two nodes n 1 and n 2 represent the first axis that we call X. The nodes n 3

and n 4 are selected as the two nodes which have the largest geodesic distance GD(n 3 , n 4 ) in the perpendicular plane to the axis X. The two nodes n 3 and n 4 represent the second axis that we call Y . The nodes n 5 and n 6 are selected as the two nodes which have the largest geodesic distance GD(n 5 , n 6 ) in the perpendicular plane to the axis Y . The two nodes n 5 and n 6 represent the third axis that we call Z. The second step is to represent each node n i using the geodesic distance regarding the six nodes references selected n 1...6 as a 6-tuple

R i = < GD(n i , n 1 ), GD(n i , n 2 ), GD(n i , n 3 ), GD(n i , n 4 ), GD(n i , n 5 ), GD(n i , n 6 ) >.
The third step is to represent each triangles by a 19-tuple < neighbors ; R 1 ; R 2

; R 3 > constituted by the number of neighbors neighbors and the three 6-tuples R i=1...3 of the three nodes composing each triangle.

We can obtain from the same object a different tessellation depending on the tessellation algorithm used and its parametrisation. A different tessellation, even for the same object, may generate a different triangle-star decomposition. However, we suppose that the tessellation of objects is realized using the same algorithm with the same parameters. This ensures that same object have one tessellation representation, thus we obtain a unique triangle-star decomposition. In the worst case (the same object have a different tessellation), the proposed distance based on an approximation of Graph Edit Distance which is fault-tolerant to noise and distortion, allows to consider the two tessellations as the same (the distance between them is negligible).

Chapter 6. Graph-based approach for non-rigid 3D Object Recognition

N (t 1 ) = 1, N (t 2 ) = 3, N (t 3 ) = 2, N (t 4 ) = 1 and N (t 5 ) = 1,
where N is the triangle direct neighborhood (see Figure 6.3). By applying a descending order based on the number of neighbors N (t i ) , we obtained 2 triangle-stars (see Table 6.2).

And by applying the ascending order based on the number of neighbors N (t i ) , we 6.3. Triangles ordering obtained 3 triangle-stars (see Table 6.3). Table 6.2: The set of triangle-stars using a Descending order.

ST 1 ST 2 ST 3
Table 6.3: The set of triangle-stars using a Ascending order.

Example 3. Let a triangle t 0 with n triangle neighbors t 1...n (see Figure 6.4).

If we consider a triangle order based on the number of neighbors with descending order, we obtained only one triangle-star, otherwise, if the process of decomposition starts with any neighbors t 1...n we obtained 3 triangle-stars. When applying a descending order, we remark that t 0 and t 1 have the same number of neighbor which is the highest one. In this case, we use the coordinates of nodes to decide with which triangle we start t 0 or t 1 . However, whatever starting with t 0 or t 1 , we obtain the same number of triangle-stars with the same cardinality as shown in (Figure 6.5).

Triangle-stars decomposition

Once the strict total order of the triangles is established, we evaluate the decomposition of the graph into triangle-stars. The process of decomposition is presented in the following algorithm (Algo. 6.1).

We explore the list of triangles according to the defined order and we construct a N k -triangle-star which is defined by the current triangle and its N k -neighbors (Definition 4), according to the degree of neighborhood N k considered. The process terminates when the list of triangles not yet explored is empty.

The proposed decomposition of triangular tessellations into triangle-stars offers a reduced number of triangle-stars ts as opposed to the number of nodes T S N .

The resulting triangle-stars are disjoints, ∀ ts i , ts j ∈ T S(G), i = j ⇒ T (ts i ) ∩ T (ts j ) = ∅. The triangle-star covers a larger local area than the classical star [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF].

The proposed decomposition is also a parameterizable method depending on the degree of the neighborhood. Considering a high degree of neighborhood allows to Apply a descending strict total order on the set of triangles of g T r ;

5:

N k -T S = ∅ ; 6:
while (T (g T r ) = ∅) do 7:

t i = T (g T r )[0] 8: T (N k -ts i ) = t i ∪ N k -neighbors(t i ) ; 9: N k -T S = N k -T S ∪ N k -ts i ; 10: T (g T r ) = T (g T r ) -T (N k -ts i ) ; 11:
end while 12:

return T S ;

13: End Example 5. Let us consider a triangular tessellation defined as follow:

g T r = { 16 nodes , 20 triangles t 1...20 } (Table 6.4). The decomposition into triangles-Stars (N 1 -T S) begins by constructing the first triangle-star T S 1 using the triangle t 13 with the set of its triangle neighbors (N 1 -neighbors). The triangle t 13 is the first triangle chosen, since it is the one having the maximum number of neighbors, which is 12. In the remaining set of triangles not used in the construction of T S 1 , the triangle t 1 that had 7 neighbors which is the maximum, is used to construct the second triangle-star T S 2 . T S 2 is constructed using t 1 and its 3 neighbours (not

7, because T (T S 1 ) ∩ T (T S 2 ) = ∅).
The third triangle-star T S 3 is formed of t 11 and its neighbors, t 11 had 5 neighbors which is the maximum in the remaining set of triangles. T S 3 is constructed using t 11 and its 2 neighbours (not 6 neighbours, because i=3 i=1 T (T S i ) = ∅). In the case of N 2 -neighborhood, we obtain one triangle-star N 2 -T S 1 constituted by the triangle t 13 and the set of its triangle N 2neighbors which represent all the triangles of g T r . Consequently, N 2 -T S 1 is exactly the triangular tessellation g T r .

Edit distance between triangle-stars

The proposed similarity measure is intended for the comparison of deformable objects. Consequently, the set of descriptors must be invariant or at least oblivious under most common deformations. Indeed the proposed similarity measure is based on the following set of parameters: Area of triangle-star, P erimeter of trianglestar, Area of triangles, P erimeter of triangles, W eights of edges and Degrees of nodes. Formally a triangle-star is represented as follows: {AG(ts), P G(ts), {A(t i ),

P (t i ), W (t i, j=1...3 ), deg(t i, j=1...3 )} i= T (ts) i=1
}. The similarity measure d between two triangle-stars ts i and ts j is computed as:

d(ts i , ts j ) = 1 - k=6 k=1 sim k (ts i , ts j ) k=6 k=1 α k (6.1)
The similarity measure d is a normalized value (0 ≤ d ≤ 1) based on the set of functions sim k .

The functions sim k are defined as follow: Deformable objects. The aim of the proposed similarity measure d (Eq. 6.1) is to measure the similarity between non-rigid (deformable) objects. However, it can be adapted for the comparison of rigid objects by adding Angles to the set of descriptors. We associate an angle to each pair of adjacent edges. Consequently, a set of modifications are realized as follow:

sim 1 (ts i , ts j ) = α 1 * |AG(ts i ) -AG(
• The vector representation of triangle-star is modified as follow (see Table 6.5 for }. Where the angles Ang are ranked by descending order. The size of the vector is increased size = 2 + (Γ * 11).

• A new similarity sim 7 (ts i , ts j ) comparing the Angles of the two triangle-stars ts i and ts j is defined as follow:

sim 7 (ts i , ts j ) = α 7 * l=Γ l=1 k=3 k=1 | Ang i,l,k -Ang j,l,k | 3 * Ang MAX * Γ (6.8)
With Ang MAX is the maximum angle (See Table 6.5 for the rest of symbols).

• The proposed similarity measure d (Eq. 6.1) is modified as follow:

d(ts i , ts j ) = 1 -k=7 k=1 sim k (ts i , ts j ) k=7 k=1 α k (6.9)

Edit distance between two triangular tessellations

The dissimilarity between two graphs represented by triangle-stars is addressed in the last part of the algorithm. We call this dissimilarity measure triangle-star Measure T SM which aims to determine the best matching between the trianglestars associated with two graphs. The dissimilarity between two sets of trianglestars is defined as follows:

Definition 7 (T SM) Let g T r1 and g T r2 be two triangular tessellations, T S 1 and T S 2 their corresponding sets of triangle-stars and M the set of all possible matching between T S 1 and T S 2 . The similarity T SM(T S 1 , T S 2 ) (normalised similarity) is formulated as follow (Eq. 6.10):

T SM(T S 1 , TS 2 ) = 1 - max m∈M tsi ∈ T S1, m(tsi) ∈ T S2 d(ts i , m(ts i )) max( T S 1 , T S 2 ) (6.10)
The computation of T SM(T S 1 , T S 2 ) is equivalent to solving the assignment problem which is one of the fundamental combinatorial optimization problems that aim to find the minimum/maximum weight matching in a weighted bipartite graph. To solve this assignment problem, we define a n×n matrix D, with n = max( T S 1 , T S 2 ).

Each element D i,j of the matrix represents the dissimilarity measure d(ts i , ts j ) between a triangle-star ts i in T S 1 and a triangle-star ts j in T S 2 . In the case of We apply the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] on the matrix D in order to find the best assignment in O(n 3 ) time.

T S 1 = T S 2 ,
The resulting distance (dissimilarity) is compared to a threshold th ∈ [0, 1] defined by an expert or by experimentation (depending on the database), in order to decide if the compared triangular tessellations are similar or not.

The general process of computing the distance between two graphs (triangle tessellations), is summarized in the following algorithm (Algo. 6.2). The distance between two graphs using TSM.

1: Inputs: Two graphs g 1 and g 2 .

2: Outputs: The distance between g 1 and g 2 .

3: Begin

4:

Decomposition of g 1 into a set of triangle-stars T S 1 , (Algo. 6.1).

5:

Decomposition of g 2 into a set of triangle-stars T S 2 , (Algo. 6.1).

6:

Construct a matrix of distance D.

7:

For each ts i ∈ T S 1 and ts j ∈ T S 2 do 8:

D i,j = d(ts i , ts j ) (Eq. 6.1);

9:

end For each 10:

Solving (Eq. 6.10), by applying the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] on the matrix D.

11:

return the distance T SM(T S 1 , TS 2 ) ;

12: End Chapter 6. Graph-based approach for non-rigid 3D Object Recognition 2. symmetry: T SM(T S 1 , T S 2 ) = T SM(T S 2 , T S 1 ). The proposed decomposition is unique and the T SM is only based on symmetrical operations (addition and subtraction in absolute value). Consequently T SM is symmetric.

3. triangle inequality: T SM(T S 1 , T S 2 ) ≤ T SM(T S 1 , T S 3 )+T SM(T S 3 , T S 2 ).

We have the triangle inequality verified in:

|x 1 -x 2 | ≤ |x 1 -x 3 |+|x 3 -x 2 |.
Thus the triangle inequality is verified in sim k therefore, we have: T SM(T S 1 , T S 2 ) ≤

T SM(T S 1 , T S 3 ) + T SM(T S 3 , T S 2 ). Consequently the triangle inequality is verified in T SM.

Complexity of the proposed algorithm

The most important part, in term of complexity, is the one solving the assignment problem. We used the Hungarian algorithm [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF] to find the best assignment in O(n 3 ) time, where n is the maximum number of components in the two graphs compared. Let n = max( N 1 , N 2 ) and n = max( T S 1 , T S 2 ), where N i is the set of nodes and T S i is the set of triangle-stars in g tr i . In the proposed decomposition, any triangle-star has at least one triangle. Consequently, in the worst case, we have n = n 3 = 0.33 * n, which means that the complexity is O(0.037 n 3 ). However the number of triangle-stars depends on the structure of the underlying graph and the degree of neighborhood N k considered in the process of decomposition. The number of triangle-stars is decreasing with the increasing of the degree of neighborhood N k as shown in Figure 6.6, in which we can see also that the number of triangle-stars is less than the number of nodes and triangles N i+1 -T S ≤ N i -T S ≤ Nodes ≤ T riangles , with i = 1...5.

In the following, we present the time complexity depending on the degree of neighborhood N k in the TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF] (See Section 7.1.1 for TOSCA database description), which is one of the databases that we use in our experiments.

In the case the degree of Neighborhood N 1 (N 1 -T S), we have on average n = ). Table 6.7 summarizes the obtained time complexity depending on the degree of neighborhood N k=1...6 , in the TOSCA database. Table 6.7 shows that the obtained complexity is improved with the increasing of the degree of neighborhood K k .

N K Complexity N 1 O(0.74 * [ n log(n) ] 3 ) N 2 O(0.0001 * [ n log(n) ] 3 ) N 3 O(5.6115 * 10 -6 * [ n log(n) ] 3 ) N 4 O(9.84 * 10 -7 * [ n log(n) ] 3 ) N 5 O(3.59 * 10 -7 * [ n log(n) ] 3 ) N 6 O(1.80 * 10 -7 * [ n log(n) ] 3 )
Table 6.7: The time complexity depending on the degree of neighborhood N k , in the TOSCA database.

Conclusion

In this chapter, we presented a new matching algorithm for addressing the problem of comparing deformable 3D objects represented by graphs (triangular tessellations).

The proposed approach is based on a new decomposition of triangular tessellations into triangle-stars depending on the degree of the considered neighborhood. The resulting triangle-stars are used to determine the distance between triangular tessel-Chapter 6. Graph-based approach for non-rigid 3D Object Recognition lation using the Hungarian algorithm. The proposed algorithm assures a minimum number of disjoints triangle-stars, offers a better dissimilarity by covering a larger area of neighbors in triangle-stars and uses a set of descriptors which are invariant or at least oblivious under most common deformations. The proposed approach is based on an approximation of Graph Edit Distance which is fault-tolerant to noise and distortion, making our approach very appropriate for comparing deformable objects. We proved that the proposed distance T SM is a pseudo-metric. The analysis of the time complexity confirm the high performance of our algorithm. In the next chapter (Chapter 7), we evaluate our approach by performing a set of experimentations and comparisons in different databases. In order to evaluate the proposed approach (Chapter 6), we undertook a set of experimentations and we compare our approach with some state of the art shapematching algorithms on three databases: TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], SHREC11

watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] and SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]. In this chapter, we present the three databases that we use in our experiments, some state of the art shape-matching algorithms to compare with, the evaluation criteria and the experimental results.

The remainder of the chapter is organized as follows. Firstly, in Section 7.1, we describe the three databases that we use in our experiments. In Section 7.2, we Chapter 7. Experimental results of the Graph-based approach for non-rigid 3D Object Recognition describe the state of the art shape-matching algorithms with which we compare our approach. In Section 7.3, we detail the performance measures that we consider to evaluate our approach. In Section 7.4, we give and discuss the obtained results and we compare them with some state of the art shape-matching algorithms. Finally, Section 7.5 concludes the chapter.

Databases description

In this section, we describe the three databases that we use in our experiments.

TOSCA database

The TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF] is an interesting database for non-rigid object similarity measures. it consists of 148 three-dimensional objects. Each object is represented by a triangular tessellation. The database is categorized into 12 classes.

Each class contains an object with different poses (deformations). The cardinality of the classes is not the same, between 1 and 24 poses for each class (see Table 7.1).

On average, each triangular tessellation has 3154 nodes, 6220 triangles. Table 7.2

shows some 3D objects of the TOSCA Database. The set of algorithms with which we compare are:

Class

• CAM: 3D-Matching method using curve analysis [START_REF] Tabia | A new 3d-matching method of nonrigid and partially similar models using curve analysis[END_REF].

• GeodesicD2: An extension of the Euclidean D2 [START_REF] Osada | Shape distributions[END_REF], computed as a global distribution of geodesic distances in 3D shapes.

• DSR: The Hybrid Feature Vector, which is a combination of two view-based descriptors: the depth buffer and the silhouette and extent radialized function Chapter 7. Experimental results of the Graph-based approach for non-rigid 3D Object Recognition descriptor [START_REF] Vranic | 3D Model Retrieval[END_REF].

• RSH: The Ray-Based Approach with Spherical Harmonic Representation in which the authors of [START_REF] Saupe | 3d model retrieval with spherical harmonics and moments[END_REF] align the models into the canonical position, extract the maximal extents and apply spherical harmonic.

• TD: The temperature distribution (TD) descriptor [START_REF] Fang | Temperature distribution descriptor for robust 3d shape retrieval[END_REF] is shape descriptor based on geometric features. TD descriptor is driven by heat kernel and it is represented as one dimensional histogram. The L2 norm is used as matching method to compute the distance between two TD descriptors.

• Shape-DNA: The Shape-DNA [START_REF] Reuter | Laplace-beltrami spectra as 'shapedna' of surfaces and solids[END_REF] is a numerical fingerprint or signature, of any 2d or 3d manifold by taking the eigenvalues of its Laplace-Beltrami operator.

• SRCP-TD: The SRCP-TD [START_REF] Abdelrahman | Heat kernels for non-rigid shape retrieval: Sparse representation and efficient classification[END_REF] method is based on sparse representation of scale-invariant heat kernel. Laplace-Beltrami eigenfunctions are used, a shape descriptor is formed based on the heat kernels and Sparse representation is used.

• Modal Repr: An isometric deformation model is used based on the geodesic distance matrix as an isometry-invariant shape representation. The method proposed does not need explicit point correspondences for the comparison of 3D shapes [START_REF] Smeets | Isometric deformation invariant 3d shape recognition[END_REF].

• CMVD-Binary: The method CMVD-Binary ( [START_REF] Daras | A compact multi-view descriptor for 3d object retrieval[END_REF], [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]) CMVD-Binary is based on the Compact Multi-View Descriptor using the silhouettes of 3D objects.

• CMVD-Depth: The method CMVD-Depth ([275], [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]) is based Compact Multi-View Descriptor Depth (CMVD-Depth) and processes the depth maps.

• Merged: The method Merged corresponds to the fusion of the CMVD-Binary and CMVD-Depth methods ( [START_REF] Daras | A compact multi-view descriptor for 3d object retrieval[END_REF], [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]).

• BF-SIFT: The method BF-SIFT is based on the ideas of Bag of Features (BF) and the Scale Invariant Feature Transform (SIFT) ( [START_REF] Dutagaci | Shrec'09 track: Querying with partial models[END_REF], [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]). The method compares shapes of 3D models visually by using a set of local features extracted from multiple view 2D depth images of the model.

Evaluation criteria

• BF-GridSIFT: The method BF-GridSIFT is based on the ideas of Bag of Features (BF) and the Scale Invariant Feature Transform (SIFT) ( [START_REF] Dutagaci | Shrec'09 track: Querying with partial models[END_REF], [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]).

Evaluation criteria

Several performance measures are used in the literature to evaluate retrieval methods and 3D similarity measures ( [START_REF] Fawcett | An introduction to ROC analysis[END_REF], [START_REF] Powers | Evaluation: from precision, recall and f-factor to roc, informedness, markedness and correlation[END_REF]). In this thesis, we evaluate our approach using the following performance measures:

• True positive (T P ): The set of objects correctly identified.

False positive (F P ): The set of objects incorrectly identified.

True Negative (T N): The set of objects correctly not identified or rejected.

False Negative (F N): The set of objects incorrectly not identified or rejected. (See Figure 7.3). We have computed the confusion matrix for all the 3D-objects belonging to the TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF]. Each element of the confusion matrix is associated with the dissimilarity between objects i and j. In addition to the visual results represented as confusion matrix (Figure 7.4), other visual results are shown in Figure 7.7. The first column contains six 3D-object query, while the rest of columns contain the four retrieved 3D-objects in the TOSCA database for each 3D-object query using the N K=1 neighborhood. Figure 7.7 shows excellent results in which we can see that the 3D-object queries and their corresponding four retrieved 3D-objects belong to the same class (for example, the first query is a centaur and the four retrieved 3D-objects are centaurs also). An interesting result for the last 3D-object query "david11" which has as retrieved 3D-objects, three objects from the same class: "david7", "david10", "david4" and an object from an other class: "michael9". However, the two classes "david" and "michael" are semantically equivalent (belong to the class "man"). are considered in the process of computing the recall and precision since, otherwise, they are automatically classified as dissimilar by our algorithm T SM. As showed in Figure 7.8, we have obtained excellent precision-recall curves which confirm the visual results shown in Figure 7.7. For instance, gorilla 0 , horse 0 , lioness 0 and seahorse 0 have a precision of 100% for a recall that goes from 86% to 100%.

We performed also a comparison in term of precision and recall in which we compare our method T SM using the N K=1 neighborhood with the four methods (CAM, GeodesicD2, DSR and RSH) in the TOSCA database. Figure 7.9 shows the comparison of the precision and pecall plot of our approach T SM using the N K=1 neighborhood with the four methods (CAM, GeodesicD2, DSR and RSH) in the TOSCA database. As the curve of our approach is higher than the four approaches to which it was compared, we conclude that our method performs better than the others.(in [START_REF] Tabia | A new 3d-matching method of nonrigid and partially similar models using curve analysis[END_REF], CAM was compared to GeodesicD2, DSR and RSH).

We performed also an other comparison in term of E_Measure in which we compare our method T SM using the N K=1...6 neighborhood with the three methods (TD, Shape-DNA and SRCP-TD) in the TOSCA database. neighborhood and the three methods (TD, Shape-DNA and SRCP-TD). Table 7.11

shows that our method T SM provide excellent results in terms of E_Measure, and using T SM with the N K=1 neighborhood, give us the highest results. Table 7.11 shows also that our method T SM provides an E_Measure highly better than the

Results on the SHREC11 watertight

We compute the distance between each pair of triangular tessellations in the SHREC11

watertight database [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] using the proposed similarity measure T SM. Two triangular tessellations are considered similar if their distance is less than a specific threshold.

Depending on the parameters α k , the threshlod and the degree of neighborhood N K , the results may be different. Tables (7.12 and 7.13) show respectively some typical results depending on the degree of neighborhood N K=2 and N K=6 with the following settings: ∀ k, α k = 1, threshlod ∈ [0.05, 0.198]. Using N K=1 neighborhood gives us naturally better results accuracy than the ones obtained using N K=2

and N K=6 neighborhood. However, we are limited by the time and as shown in Figure 7.6, the time needed to process all the database using T SM with N K=i is longer than T SM with N K=i+1 and especially when using N K=1 neighborhood.

Table 7.14 shows the Accuracy, T P R and T NR results obtained by T SM in the SHREC11 watertight database, using the thresholds giving us the highest Accuracy, T P R and T NR for the two degrees of neighborhood (N K=2 and N K=6 ) and ∀ k, α k = 1.

We obtained excellent results which are between 61% and 67% in the Accuracy,

Results on the SHREC09 database

We compute the distance between each query and target triangular tessellations in the SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF] using the proposed similarity measure T SM. Two triangular tessellations are considered similar if their distance is less than a specific threshold. Depending on the parameters α k , the threshlod and the degree of neighborhood N K , the results may be different. Tables (7.16 and 7.17) show respectively some typical results depending on the degree of neighborhood N K=2 and N K=6 with the following settings: ∀ k, α k = 1, threshlod ∈ [0.09, 0.0401]. We don't present the results with N K=1 neighborhood because we are limited by the time and as shown in Figure 7.6, the time needed to process all the database using T SM with N K=i is longer than T SM with N K=i+1 and especially when using N K=1 neighborhood.

Table 7.18 shows the Accuracy, T P R and T NR results obtained by T SM in the SHREC09 database, using the thresholds giving us the highest Accuracy, T P R and T NR for the two degrees of neighborhood (N K=2 and N K=6 ) and ∀ k, α k = 1.

We obtained excellent results which are between 55% and 61% in the Accuracy, T P R

Results discussion

The set of experimentations and the comparisons with some state of the art shapematching algorithms, on the three databases: TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], SHREC11

watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] and SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF], show the high performance of our approach.

Indeed, we obtained excellent results in term of Accuracy, T P R and T NR on the three databases (TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], SHREC11 watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] and SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]). The visual results represented as a confusion matrix (Figure 7.4) and as the retrieved results in the TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], confirm the high performance of our approach. Our approach also realize a high performance in term of the run time (average and total run time) depending on the considered neighborhood degree, which confirms the theoretical time complexity. The excellent precision-recall curves obtained and the comparison performed with the four methods (CAM, GeodesicD2, DSR and RSH) in the TOSCA database, show the high Chapter 7. Experimental results of the Graph-based approach for non-rigid 3D Object Recognition performance of our approach in term of precision and recall and that our method is better. We also performed a comparison in term of E_Measure in which we compare our method T SM using the different degree of neighborhood with a set of methods from the state of the art shape-matching algorithms, on the three databases:

TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], SHREC11 watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] and SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF].

The obtained results show that our method performs excellent results in term of E_Measure and show that our approach is highly better in term of E_Measure than methods with which we compare.

The results shown in this chapter are obtained using the default parameters and the adequate threshold. Even the obtained results are excellent, an improvement in term of performance can be realized by specifying the adequate parameters, threshold and degree of neighborhood depending on the database considered and this by using machine learning techniques. The set of descriptors can be also enriched, which can be allows an improvement of the obtained results.

Conclusion

We proposed a new graph matching distance for addressing the problem of comparing deformable 3D objects represented by graphs (triangular tessellations). The proposed approach is based on a new decomposition of triangular tessellations into triangle-Stars. In order to evaluate our approach, we undertook a set of experiments in different well know databases for entire and partial deformable shape comparison.

Chapter 8

Conclusions and future works In this chapter, we first concludes the thesis with a summary of our contributions, in Section 8.1. We then describe some suggestions for further research and future works, in Section 8.2.

Conclusions

In this thesis, graph based approaches for Pattern Recognition and the associated applications, namely 2D and 3D, are investigated. Graph based techniques for Pattern Recognition aim to solve mainly two major problems. The first one is to find an optimal way to represent the considered patterns by graphs. The second problem is to find the adequate method to compare the objects represented by graphs. In this context, finding solutions to the problem of graph modeling and graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. Graph matching and more generally graph comparison is the aim operation in the process of pattern recognition using graph-based approaches. Graph matching solutions are classified into two wide categories: exact approaches and inexact approaches. In this thesis, we focused on inexact graph matching approaches and them applications on 2D and 3D Pattern Recognition.

In the first part of this thesis, we addressed the issue of geometric graph matching and its applications on 2D Pattern Recognition. Kite recognition in satellite images is the main application considered in this part. The visibility of Kites in satellite Chapter 8. Conclusions and future works images (due to their huge size), their important number and their wide geographical distribution, make automatic recognition of Kites an important step towards understanding these enigmatic remnants. We presented a complete identification tool relying on a graph representation of the Kites. In this context, we realized mainly two major contributions. The first one is the introducing of a graph representation of Kites and the proposition of an automatic process for extracting and transforming Kites from real images into graphs. We also proposed a process of generating randomly a synthetic data set of Kite graphs. Using the two proposed processes, we constructed a benchmark of Kite graphs (real and synthetic) structured in different level of deformations. This benchmark is used to validate our algorithms.

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 leading to an efficient Kite identification process. We analyzed the time complexity of the proposed algorithms and conducted extensive experiments both on real and synthetic Kite graph data sets which attested the effectiveness of the proposed approach. We also performed a set of experimentations on other data sets which showed that the proposed approach is extensible and quite general. The satellite images (ground truth data) used to the construction of the Kite database are provided by a team of archeologists expert on Kites. The archeologists have also checked and validated the experiments steps that we realized and the obtained results.

In the second part of this thesis, we addressed the problem of comparing deformable or non-rigid 3D objects. The shapes considered are represented by graphs, The proposed approach dealing with the geometric graphs matching was evaluated on the proposed Kite benchmark (real and synthetic) and on the well known database GREC [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF]. We project to realize other experiments on other well known graph databases, namely on the rest of data sets of the well-known IAM Graph

Database Repository [START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF], in order to further evaluate the performances of the proposed approach and specialty for confirming that the proposed approach is quite general. We project also to improve the proposed approach to be a general solution for structural Pattern Recognition in satellite images.

The images used for the construction of the prosed Kite database are acquired manually, as a technical improvement, we project to automate the process of image acquisition.

In this thesis, two graph based approaches for 2D and 3D Pattern Recognition are proposed. Their time complexity is excellent, O(n 3 ). However, a more general graph matching approach in term of applicability (2D and 3D) with a reduced time complexity, can be proposed. We can meet this objective using a new formalization based on the stable marriage problem [START_REF] Gusfield | The stable marriage problem: structure and algorithms[END_REF]. This approach is based on graph decomposition into a set of substructures, and then followed by a matching of these substructures based on stable marriage algorithm. The choice of the graph decomposition method depends on the kind of the considered graphs: a triangle-Stars decomposition for the triangular tessellations (graphs of 3D shapes) and a star decomposition for other kinds of graphs (graphs of 2D shapes).

The stable marriage problem is the problem of finding a stable matching between two sets of elements with equal size, based on an ordering of preferences associated to each element regarding other elements. Stability means that every matched couple of elements prefers to stay together rather than be mapped to an other one [START_REF] Gusfield | The stable marriage problem: structure and algorithms[END_REF].

Originally, stable marriage problem is introduced by Gale and Shapley in 1962 in order to find a matching between men and women, based on preference lists in which each person (man and woman) presents his or her preferences regarding the other persons with opposite gender. The problem has then adapted in several research areas, such as mathematics, economics, game theory, computer science, etc. We refer readers to [START_REF] Iwama | A survey of the stable marriage problem and its variants[END_REF] for more details on stable marriage problem and its variants.

Further works

The basic idea of our new approach is firstly to decompose the two graphs G 1 and G 2 that we want to compare into two sets of substructures S 1 and S 2 . Depending on the kind of the graphs (2D or 3D), the resulted substructures are either stars or triangle-Stars. A triangle-Stars decomposition (introduced in Chapter 6) for the triangular tessellations (graphs of 3D shapes) and a star decomposition for other kinds of graphs (graphs of 2D shapes). The second step is to associate to each substructure s 1,i ∈ S 1 from one graph G 1 , a vector of preferences regarding to the other substructures s 2,j ∈ S 2 of the other graph G 2 . The vectors associated to s 1,i ∈ S 1 (respectively s 2,j ∈ S 2 ) contain the set of substructures S 2 (respectively S 1 ) odored following the preferences with a descending order. The preference P (s 1,i , s 2,j ) between s 1,i ∈ S 1 and s 2,j ∈ S 2 is measured either using the proposed distance defined by the formula (Eq. 5.6, Chapter 5) in the case of stars or using the proposed distance defined by the formula (Eq. 6. empty substructures (ε), with the corresponding preference P (s k,i , ε). In the final, we obtain a set of vectors constituting a square matrix of preferences D t,t in which each case D i,j contain a substructure (or ε) with the corresponding preferences P i,j .

The third step consists to use the algorithm of stable marriage in order to find the best match of the different substructures S

Faculté

  Techniques des Activités Physiques et Sportives Observatoire des Sciences de l'Univers de Lyon Polytech Lyon Ecole Supérieure de Chimie Physique Electronique Institut Universitaire de Technologie de Lyon 1 Ecole Supérieure du Professorat et de l'Education Institut de Science Financière et d'Assurances Directeur : M. F. DE MARCHI Directeur : M. le Professeur F. THEVENARD Directeur : Mme C. FELIX Directeur : M. Hassan HAMMOURI Directeur : M. le Professeur S. AKKOUCHE Directeur : M. le Professeur G. TOMANOV Directeur : M. le Professeur H. BEN HADID Directeur : M. le Professeur J-C PLENET Directeur : M. Y.VANPOULLE Directeur : M. B. GUIDERDONI Directeur : M. le Professeur E.PERRIN Directeur : M. G. PIGNAULT Directeur : M. le Professeur C. VITON Directeur : M. le Professeur A. MOUGNIOTTE Directeur : M. N. LEBOISNE To my mother and father.

  Mots clés: Appariement de graphes, Distance d'édition de graphes, Décomposition de graphes, Modélisation à base de graphes, Reconnaissance de formes, Reconnaissance d'objets 3D, Reconnaissance d'objets déformables, Kites, Images satellites. xi List of Figures

2. 11 13 3. 1 18 4. 1 39 4. 2 46 4. 7 48 5. 1 78 6. 2 79 6. 4 80 6. 5 81 6. 6 104 7. 5 105 7. 6 106 7. 7 108 7. 9 108 8. 1 120 xxof Algorithms 6 . 1 82 6. 2

 111311813924674817827948058161045105610671089108112061822 Example of applying the Graph Edit Distance (GED). . . . . . . . . Taxonomy of Graph-based approaches in Pattern Recognition based on the taxonomies introduced in [2, 3]. . . . . . . . . . . . . . . . . . Illustration of Kite detection . . . . . . . . . . . . . . . . . . . . . . . Real data-set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3 State-I: Example of extraction and transformation of images into graphs 43 4.4 State-II: Example of extraction and transformation of images into graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.5 State-III: Example of extraction and transformation of images into graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.6 State-IV: Example of extraction and transformation of images into graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kite graphs syntectic data-set generation process. . . . . . . . . . . . Example of isomorphic graphs . . . . . . . . . . . . . . . . . . . . . . 56 5.2 The graphs G1 and G2 in Example 2. . . . . . . . . . . . . . . . . . 58 5.3 Runtime Vs number of vertices. . . . . . . . . . . . . . . . . . . . . . 64 List of Figures 6.1 Comparison of the average number of nodes, triangles and trianglestars in the TOSCA database. . . . . . . . . . . . . . . . . . . . . . . Comparison of the average of T S , depending on triangles order considered, in TOSCA database. . . . . . . . . . . . . . . . . . . . . 78 6.3 A graph-tessellation G tr . . . . . . . . . . . . . . . . . . . . . . . . . The triangle t 0 with n triangles neighbors. . . . . . . . . . . . . . . . Example of graph decomposition with pose changing. . . . . . . . . . The number of Nodes, Triangles and triangle-stars in different N k neighborhood in the TOSCA Database. . . . . . . . . . . . . . . . . 92 7.1 Example of two objects in each class of SHREC11 watertight data-set [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.2 The 20 3D partial models of the query data-set in SHREC09 [5]. . . 97 7.3 Confusion matrix of metric performances. . . . . . . . . . . . . . . . 99 7.4 The N K=1 Confusion matrix associated with the TOSCA Database. The average run time (Seconds) for each degree of neighborhood N K=1...6 , on the TOSCA database. . . . . . . . . . . . . . . . . . . . The total run time (Seconds) of the TOSCA database, for degree of neighborhood N K=1...6 . . . . . . . . . . . . . . . . . . . . . . . . . . . The first four retrieved results in the TOSCA database, with N K=1 neighborhood. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.8 Precision-recall curves for six distinct 3D-objects of the TOSCA database with N K=1 neighborhood. . . . . . . . . . . . . . . . . . . . . . . . . Precision and Recall plots comparing our approach to the CAM, GeodesicD2, DSR and RSH approaches on the TOSCA database. . . Vectors of Preferences of s 1,i=0..3 ∈ S 1 regarding to s 2,j=0..3 ∈ S 2 and vectors of preferences of s 2,j=0..3 ∈ S 2 regarding to s 1,i=0..3 ∈ S 1 , in descending order. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List Graph decomposition into N k -triangle-stars. . . . . . . . . . . . . . . The distance between two graphs using TSM. . . . . . . . . . . . . . . 88 Chapter 1

Figure 1 . 1 :

 11 Figure 1.1: The Seven Bridges of Königsberg city [1].

Figure 1 . 2 :

 12 Figure 1.2: Graph representation of Königsberg bridge problem [1].

Part I :

 : Geometric graph matching: application to 2D pattern recognitionIn the field of Pattern Recognition, it is often required to compare objects, and the question how to represent those objects in a formal way is a fundamental issue. Graphs are popular and powerful mathematical modeling tools. Graph based techniques for pattern recognition aim to solve mainly two major problems. The first is to find an optimal way to represent the considered patterns by graphs. The second problem is to find the adequate method to compare the objects represented by graphs. In this context, finding solutions to the problem of graph modeling and graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. The related work about graph modeling, graph matching and its applications in Pattern Recognition are detailed in Chapter 3. In this part, we address the issue of geometric graphs matching and its applications on 2D Pattern Recognition. Kite recognition in satellite images is the main application considered in this part. Kites are huge archaeological structures of stone visible from satellite images. Because of their important number and their wide geographical distribution, automatic recognition of these structures on images is an important step towards understanding these enigmatic remnants. In this part, we present a complete identification tool relying on a graph representation of the Kites. As Kites are naturally represented by graphs, graph matching methods are thus the main building blocks in the Kite identification process. However, Kite graphs are disconnected geometric graphs for which traditional graph matching methods are useless. This part of this thesis is realized within the KITE project, consequently, Kite recognition in satellite images, is the main application of the geometric graph matching part. KITE project allowed us to collaborate with a team of archeologists expert on Kites. The archeologists provided us the satellite images (ground truth data) needed to the construction of the Kite database. They have also checked and validated the experiments steps that we realized and the obtained results. This part contains two chapters, in the first one (Chapter 4), we present the process of Kite graphs construction from real images, and the process of generating a synthetic data set of Kite graphs generated randomly. The two data sets (real and synthetic) are used to validate our algorithms. In the second one (Chapter 5), we propose 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 leading to an efficient Kite identification process. In Chapter 5, we analyze the time complexity of the proposed algorithms and conduct extensive experiments both on real and synthetic Kite graph data sets

  the edge labelling function while L V and L E are the sets of labels associated with the nodes and edges respectively. The cardinality of the node set V (G) is called the order of G, commonly denoted by |V (G)|. The cardinality of the edge set E(G) is the size of G, commonly denoted by |E(G)|. A graph can be directed or undirected. In a Chapter 2. Preliminary Notions directed graph, edges are ordered pairs (u, v) connecting the source node u to the target node v, commonly denoted by -→ uv and called arcs. In an undirected graph, edges are unordered pairs {u, v} and connect the two nodes in both directions. The notation uv is used to indicate the edge {u, v}. In an undirected graph G, two distinct nodes u and v are adjacent or neighbors if there exists an edge uv ∈ E(G)

Figure 2 . 2 :Figure 2 . 3 :

 2223 Figure 2.2: Example of a cycle

  Figure 2.4 illustrates an example of a planar graph.

Figure 2 . 4 :

 24 Figure 2.4: Example of a planar graph

  Figure 2.5 illustrates an example of a bipartite graph.

Figure 2 . 5 :Figure 2 . 6 :

 2526 Figure 2.5: Example of a bipartite graph

Figure 2 . 7 :

 27 Figure 2.7: Example of a star.

Figure 2 . 8 :

 28 Figure 2.8: Example of stars of a graph

Figure 2 . 9 :

 29 Figure 2.9: Example of a graph isomorphism.

Figure 3 . 1 :

 31 Figure 3.1: Taxonomy of Graph-based approaches in Pattern Recognition based on the taxonomies introduced in [2, 3].

  ified. Depending on the kind of the application, the nodes can represent points and/or regions of interest or any other components obtained by applying a specific process on the data such as segmentation. Edges represent connections between these nodes and define a specific relationship between nodes, such as proximity, adjacency, etc. Several graph databases are available in the literature, among them we can cite the well-known IAM Graph Database Repository[START_REF] Riesen | IAM graph database repository for graph based pattern recognition and machine learning[END_REF], which contains several graph data sets. The first data set is the Letter Graphs data set which contains graphs that represent letter drawings (15 capital letters of the Roman alphabet that consist of straight lines only). Lines are represented by undirected edges and ending points of lines by nodes. Each node is labeled with a two-dimensional attribute giving its position relative to a reference coordinate system. Edges are unlabeled.The second data set is Digit Graphs, which consists of graphs representing handwritten digits. Nodes are inserted in regular intervals between the beginning and ending points of a line. Successive nodes are connected by undirected edges. Each node is labeled with a two-dimensional attribute giving its position relative to a reference coordinate system. Edges are attributed with an angle representing the orientation of the edge relative to the horizontal direction. GREC Graphs is the third data set consisting of graphs representing symbols from architectural and electronic drawings. Ending points, corners, intersections and circles are represented by nodes and labeled with a two-dimensional attribute giving their position. The nodes are connected by undirected edges which are labeled as line or arc. An additional attribute denotes the angle with respect to the horizontal direction or the diameter in case of arcs. The fourth data set is Fingerprint Graphs which consists of graphs representing fingerprints, which are converted into graphs by filtering the images

  This part addresses the issue of geometric graph matching and its applications on 2D Pattern Recognition. Kite recognition in satellite images is the main application considered in this part. We present a complete framework for Kite recognition on satellite images where Kites are modeled by graphs. Kites are huge archaeological structures of stone visible from satellite images. Because of their important number and their wide geographical distribution, automatic recognition of these structures on images is an important step towards understanding these enigmatic remnants. In this part, we present a complete identification tool relying on a graph representation of the Kites. As Kites are naturally represented by graphs, graph matching methods are thus the main building blocks in the Kite identification process. However, Kite graphs are disconnected geometric graphs for which traditional graph matching methods are useless. This part contains two chapters, in the first one (Chapter 4), we present the process of Kite graph construction from real images, and the process of generating a synthetic data set of Kite graphs generated randomly. The two data sets (real and synthetic) are used to validate our algorithms. In the second one (Chapter 5), we propose 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 leading to an efficient Kite identification process. In Chapter 5, we analyze the time complexity of the proposed algorithms and conduct extensive experiments both on real and synthetic Kite graph data sets to attest the effectiveness of the approach. We also perform a set of experimentations on other data sets in order to show that the proposed approach is extensible and quite general.The satellite images (ground truth data) used in the construction of the Kite database are provided by a team of archeologists expert on Kites. The archeologists have also checked and validated the experiment steps that we realized and the obtained results.

Figure 4 .

 4 Figure 4.1(a). Kites were discovered in the Middle East in 1920. They were first

4. 2 .Figure 4 . 1 :

 241 Figure 4.1: Illustration of Kite detection

Figure 4 .

 4 Figure 4.2 depicts some examples in each case. Figures (4.3, 4.4, 4.5 and 4.6)

  Figure 4.2 depicts some examples in each case. Figures (4.3, 4.4, 4.5 and 4.6) illustrate the process of extraction and transformation into graphs applied on twelve satellite images, three images per state of preservation. The characteristics of the data set are summarized in Table 4.1.

Figure 4 . 4 : 44 4. 2 .Figure 4 . 5 : 4 . 2 .Figure 4 . 7 :

 44442454247 Figure 4.4: State-II: Example of extraction and transformation of images into graphs

Chapter 5 .

 5 Geometric Graph Matchingtackle these challenges, we propose a multi-level recognition framework that first applies rapidly computed graph invariants to discard non-Kite graphs in the early stages of the recognition framework. Then, we use a local similarity measure that takes into account the geometric form of Kite graphs by considering the angles of the form. Finally, a reconstruction process allows us to consider disconnection within Kite graphs.

  be two graphs. G 1 and G 2 are geometrical isomorphic if they are isomorphic and have the same geometric form.Example 1 Let G i (V, E) where i = 1...5, be five graphs, such that V = {v 1 , v 2 , v 3 } and E = {e 1 , e 2 , e 3 } (Figure5.1(a, b)). We can easily find a mapping between the set of vertices of G 1 and G 2 ensuring edge preservation, thus G 1 and G 2 are isomorphic. However, they are not geometrical isomorphic because they do not have the same geometric form ((∠v1 v 2 v 3 ) G1 = (∠v 1 v 2 v 3 ) G2 ), (seeFigure 5.1(a)). G 3 , G 4 and G 5 (see Figure 5.1(b)) are geometrical isomorphic: because they are isomorphic and have the same geometric form ((∠v

Figure 5 . 1 :

 51 Figure 5.1: Example of isomorphic graphs

Figure 5 . 2 :The max sum is 3 . 25 . 1 - 3 .25 4 = 0 . 1875 .

 5232513401875 Figure 5.2: The graphs G1 and G2 in Example 2.

  second phase, i.e., Global. GeoLocal Global aims to improve Global, based on the graph invariants, in the second level by only considering the assigned vertices in the first level using GeoLocal. Formally, let G 1 and G 2 be two graphs, G 2 is the graph prototype, S 1 and S 2 the sets of signatures of G 1 and G 2 respectively, th ∈ [0, 1] a threshold, d 2 = GeoLocal(S 1 , S 2 ) and G 1 is the subgraph induced by the vertices of G 1 assigned in the first phase using GeoLocal.

  Each connected component from the whole graph representing the query image is compared to the set of prototype graphs (G Antenna , G Enclosure and four different G Kite ), using the proposed similarity measure (GeoLocal, Global, Global GeoLocal or GeoLocal Global ). Consequently, each connected component (a query graph) is classified as Kite, a part of Kite or not a Kite nor a part of Kite. When a query graph passes the considered similarity measure (GeoLocal, Global, Global GeoLocal or GeoLocal Global ) with more than one connected component classified as a Kite part and at least one of them is classified as an enclosure, we need to know if these Kite parts are parts of the same Kite or belong to different Kites. This is the aim of the reconstruction step that uses the coordinates of the vertices to eventually reconstruct the entire Kite from different components: i.e, enclosure and antennas.

5. 3 .

 3 Experimental resultsconstructed a set of query groups with the same number of vertices. The number of vertices vary from 2 vertices to 949 vertices in the real data set and from 30 vertices to 85 vertices in the synthetic data set.

Figure 5 .

 5 Figure 5.3 shows the average runtime performance of Global, GeoLocal, GED Bipartie and Beam GED in both the real Kite data set (Figure 5.3 (a)) and the synthetic Kite data set (Figure 5.3 (b)). The X-axis shows the number of vertices contained in the query graph and the Y -axis the average runtime, in log scale, obtained over the query group of the corresponding graph size when compared to the set of Kite prototype graphs. This figure clearly shows the interest of using the global similarity measure Global, which is largely faster than the geometric local similarity measure GeoLocal. Figure 5.3 also shows that GeoLocal is faster compared to GED Bipartie and Beam GED . The approaches with which we compare (GED Bipartie and Beam GED ) are approximatively equivalent with a little difference making GED Bipartie slight faster than Beam GED . The runtime performance shown in the figure confirms the theoretical time complexity, which is linear for Global and polynomial for GeoLocal and GED Bipartie . However, GeoLocal has a better time complexity, which is O((max(n , m)) 3 ) compared to GED Bipartie with O((n + m) 3 ), where n and m are the number of vertices of the two compared graphs.

Figure 5 . 3 :

 53 Figure 5.3: Runtime Vs number of vertices.

  the triangle labelling function while L T is a set of labels associated with the triangles. Definition 5 (N k -triangle-star): A N k -triangle-star N k -ts is triangle-star defined by a triangle and a set of its N k -neighbors. In the case of k = 1, the N ktriangle-star is a simple triangle-star (Definition 4). See Example 1.

  3 >: the number of neighbors and the coordinates x, y, z, in the reference frame defined by the Eigen vectors of the tensor of inertia associated with the tessellation, of the three nodes associated with the triangle. The number of neighbors neighbors is used in order to further reduce the number of triangle-stars. If two triangles have the same number of neighbors, the node's coordinates are utilised in order to ensure the uniqueness of the decomposition. The nodes of the triangle in the 10-tuple are ordered according to their coordinates, starting by the first coordinate x. In case of equality, the next coordinates are compared until an inequality is obtained. The coordinates of the nodes are solely considered in order to ensure the uniqueness the decomposition. The order of triangles may be affected by the pose changing due to the node's coordinates changing, consequently the obtained triangle-stars may 6.3. Triangles ordering be different. However, the number of triangle-stars and their cardinality are the same, because the triangles ordering is based mainly on the number of neighbors. The node's coordinates are only used when two triangles have the same number of neighbors (See Example 4). A solution to avoid that the order of triangles be affected by the pose changing is to consider the coordinates x, y, z, in the reference frame defined by the Eigen vectors of the tensor of inertia associated with the tessellation. Another solution, not affected by the object rotation, ensuring a descending strict total order on the set of triangles, is based on the selection of six nodes as a landmark reference and the use of geodesic distance (See Definition 7).

Figure 6 . 1 :

 61 Figure 6.1: Comparison of the average number of nodes, triangles and triangle-stars in the TOSCA database.

Figure 6 . 2 :Example 2 .

 622 Figure 6.2: Comparison of the average of T S , depending on triangles order considered, in TOSCA database.

Figure 6 . 3 :

 63 Figure 6.3: A graph-tessellation G tr

Figure 6 . 4 :

 64 Figure 6.4: The triangle t 0 with n triangles neighbors.

6. 4 .Figure 6 . 5 :Algorithm 6 . 1 : 1 : 2 :

 4656112 Figure 6.5: Example of graph decomposition with pose changing.

  the smallest set of triangle-stars is completed by (max(||T S 1 ||, ||T S 2 ||)-Chapter 6. Graph-based approach for non-rigid 3D Object Recognition min(||T S 1 ||, ||T S 2 ||)) empty triangle-stars ε. The similarity between an empty triangle-star ε and a triangle-star ts is computed by the equation (Eq. 6.1) and correspond to the cost of adding ts to the small set of triangle-stars (or to delete ts from the large set of triangle-stars).

Example 7 .

 7 Let T S 1 and T S 2 two set of triangle-stars, T S 1 = T S 2 = 4. Let D the matrix of similarities between T S 1 and T S 2 . 0 ts 2,1 ts 2,2 ts 2,3 ts 1,0 0.11 0.90 0.25 0.21 ts 1,1 0.10 0.15 0.65 0.89 ts 1,2 0.67 0.03 0.51 0.17

  The max sum, similarity = 3.21. The normalised dissimilarity (edit distance) isT SM(T S 1 , TS 2 ) = 1 -

n 3 .

 3 8510 = 0.2596 * n which means that the complexity is: O(0.0174 n 3 ). Since N T S ∼ = 1.1029 * log( N ) , the complexity is of the order of O(0.74 * [ n log(n) ] 3 ). In the case the degree of Neighborhood N 2 (N 2 -T S), we have on average n = n 68.6054 = 0.0145 * n which means that the complexity is O(3.0968 * 10 -6 n 3 ). Since N T S ∼ = 19.6480 * log( N ) , the complexity is of the order of O(0.0001 * [ n log(n) ] 3 ). For the degree of Neighborhood N 3 (N 3 -T S), we have on average n = n 196.4914 = 6.8. Conclusion 0.0050 * n which means that the complexity is O(1.3181 * 10 -7 n 3 ). Since N T S ∼ = 56.2736 * log( N ) , the complexity is of the order of O(5.6115 * 10 -6 * [ n log(n) ] 3 ). In the case the degree of Neighborhood N 4 (N 4 -T S), we have on average n = n 350.9977 = 0.0028 * n which means that the complexity is O(2.3125 * 10 -8 n 3 ). Since N T S ∼ = 100.5231 * log( N ), the complexity is of the order of O(9.84 * 10 -7 * [ n log(n) ] 3 ). For the degree of Neighborhood N 5 (N 5 -T S), we have on average n = n 491.0660 = 0.0020 * n which means that the complexity is O(8.4446 * 10 -9 n 3 ). Since N T S ∼ = 140.6376 * log( N ) , the complexity is of the order of O(3.59 * 10 -7 * [ n log(n) ] 3 ). In the case the degree of Neighborhood N 6 (N 6 -T S): we have on average n = n 617.3547 = 0.0016 * n which means that the complexity is: O(4.25 * 10 -9 n 3 ). Since N T S ∼ = 176.8057 * log( N ), the complexity is of the order of O(1.80 * 10 -7 * [ n log(n) ] 3

Figure 6 . 6 :

 66 Figure 6.6: The number of Nodes, Triangles and triangle-stars in different N k neighborhood in the TOSCA Database.

Table 7 . 1 :

 71 Number of poses per class in the TOSCA Database.

Figure 7 . 2 :

 72 Figure 7.2: The 20 3D partial models of the query data-set in SHREC09 [5].

Figure 7 . 3 :•

 73 Figure 7.3: Confusion matrix of metric performances.

Average run time in differents degree ofFigure 7 . 5 :

 75 Figure 7.5: The average run time (Seconds) for each degree of neighborhood N K=1...6 , on the TOSCA database.

Figure 7 .Figure 7 . 7 ,Figure 7 . 6 :

 77776 Figure 7.8 shows six precision-recall curves of the six 3D-object queries presented in Figure 7.7, from the TOSCA database using the N K=1 neighborhood.Our method T SM uses a threshold (threshold = 0.06 for N K=1 neighborhood), which means that only the objects which present a dissimilarity ≤ threshold

Figure 7 . 8 :

 78 Figure 7.8: Precision-recall curves for six distinct 3D-objects of the TOSCA database with N K=1 neighborhood.

Figure 7 . 9 :

 79 Figure 7.9: Precision and Recall plots comparing our approach to the CAM, GeodesicD2, DSR and RSH approaches on the TOSCA database.

Contents 8 . 1

 81 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.2 Further works . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

  i.e., triangular tessellations. In the field of 3D object recognition, it is often required to compare different 3D objects represented by graphs. Using triangular tessellations, 3D objects may be compared with graph matching techniques. We proposed a new graph based distance for comparing deformable 3D objects. This distance is based on a new decomposition of triangular tessellations into a set of substructures that we called triangle-Stars. A triangle-Star is a connected component formed by the union of a triangle and its neighborhood. The proposed decomposition offered a parameterizable triangle-Stars depending on the degree of the neighborhood considered. The number of triangle-Stars obtained is much smaller than the number of nodes and the number of classic stars[START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF] and, as a result, the computational Chapter 8. Conclusions and future works

1 and S 2 89 s 1 ,

 2891 based on their preferences vectors, in quadratic time O(n 2 ). The last step is to compute the score of the matching and this by the sum of preference values of each couple of substructuresScore = i,j=t i,j=1 P (s 1,i , s 2,j). An illustration of the the proposed approach is giving in Example 1.Example 1. Let S 1 and S 2 two set of substructures (stars or triangle-Stars) of two graphs G 1 and G 2 . S 1 = S 2 = 4. Let D the matrix of similarities between S 1 and S 2 calculated using one of the two formulas: Eq. 5.6 in the case of stars or Eq. 6.1 in the case of triangle-Stars. 2 0.67 0.03 0.51 0.17

s 1 ,

 1 3 0.66 0.88 0.33 0.99

  1.1 The Seven Bridges of Königsberg city [1]. . . . . . . . . . . . . . . . 2 1.2 Graph representation of Königsberg bridge problem [1]. . . . . . . . . 2 2.1 Example of a graph path . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Example of a cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Example of a connected graph . . . . . . . . . . . . . . . . . . . . . .

9 2.4 Example of a planar graph . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Example of a bipartite graph . . . . . . . . . . . . . . . . . . . . . . 10 2.6 Example of a tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.7 Example of a star. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.8 Example of stars of a graph . . . . . . . . . . . . . . . . . . . . . . . 11 2.9 Example of a graph isomorphism. . . . . . . . . . . . . . . . . . . . . 12 2.10 Example of a subgraph isomorphism. . . . . . . . . . . . . . . . . . . 12

  Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 2
	Preliminary Notions
	Contents
	2.1

7 2.2 Some special graphs . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Graph matching . . . . . . . . . . . . . . . . . . . . . . . . . . 11

  → ε), and the insertion of the element v by (ε → v). A cost is associated to each edit operation. A sequence of edit operations e 1 , ..., e k transforming G 1 into G 2 is called an edit path between G 1 and G 2 . However, for every pair of graphs G 1 and G 2 , several edit paths transforming G 1 into G 2 exist with different total costs. The edit distance of two graphs is then defined as the minimum cost edit path between the two graphs G 1 and G 2 . Figure 2.11 gives an example of the process graph edit distance (GED) transforming the graph G 1 into the graph G 2 .Formally, Let G 1 = (V 1 , E 1 , α 1 , β 1 ) be the source and G 2 = (V 2 , E 2 , α 2 , β 2 ) be the target graph. The graph edit distance between G 1 and G 2 is defined as following:

	2.3. Graph matching
	Maximum common subgraph isomorphism: A graph isomorphism f between
	the largest subgraph G of the graph G and a subgraph H of the graph H (G	H )
	is called Maximum common subgraph isomorphism between G and H. In other
	words, the Maximum common subgraph is the largest isomorphic part of two graphs.
	In general, in the literature, this problem is related to the maximum clique problem.
	Graph Edit Distance (GED) The Graph Edit Distance [9] between two graphs
	G 1 and G 2 is the minimum number of edit operations (minimum cost) to transform
	a graph G 1 into a graph G 2 . A set of edit operations is given by insertions, deletions
	and substitutions (or relabeling) of graph elements (nodes and/or edges). We denote
	the substitution of two elements u and v by (u → v), the deletion of the element u
	by (u
		G		H
	1	2	4	A	B	f(1)=A
						f(2)=B
		3			C	f(3)=C
	Figure 2.10: Example of a subgraph isomorphism.
	Graph monomorphism: A graph monomorphism is a relaxed instance of sub-
	graph isomorphism, in which the mapped subgraph allows additional edges. In other
	words, additional edges are allowed between nodes in the larger graph.

Subgraph isomorphism: A graph isomorphism f between a graph G and a subgraph H of the graph H (G H ) is called subgraph isomorphism between G and H. Figure 2.10 illustrates an example of a subgraph isomorphism f between two graphs G and H.

  Kite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

	Chapter 4
	Kite graph database construction
	Contents
	4.1

4.2 Kite graph data-set construction . . . . . . . . . . . . . . . . 38 4.2.1 Real data set construction . . . . . . . . . . . . . . . . . 38 4.2.2 Synthetic data set generation . . . . . . . . . . . . . . . 47 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Table 4

 4 .1.

		All the Data set	State-I	State-II	State-III	State-IV
	#G	4081	62	129	1581	2309
	#Img	350	50	100	100	100
	avg (V )	26.14	110.84	113.74	30.09	15.59
	max (V )	949	316	320	779	949
	avg (E)	26.28	116.51	122.34	30.56	15.90
	max (E)	1081	327	331	864	1081
	avgAng	91.22	91.19	91.31	91.24	91.15
	maxAng	180	180	180	180	180

#G: number of graphs. #Img: number of images. avg(V ): average number of vertices. avg(E): average number of edges. max(V ): maximum number of vertices. max(E): maximum number of edges. avgAng : average value of the angles. maxAng maximum angle value.

Table 4 .

 4 1: Real Data set CharacteristicsKite graphs Prototype(Real) With the help of the archeologists, we selected from the graphs in State-I, the most preserved Kites as prototype Kite graphs. Also,

to be able to deal with disconnected Kite graphs without adding significant computing costs, we constructed a prototype graph for each Kite component, namely:

Table 4 . 2

 42

: Synthetic Graph Data set Characteristics Kite graphs Prototype(Synthetic) Using the described process, we generate a set of prototype graphs representing: an antenna, an enclosure and four entire Kites.

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

	Chapter 5
	Geometric Graph Matching
	Contents
	5.1

5.2 Algorithm overview . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.1 Global similarity . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2.2 Geometric local similarity . . . . . . . . . . . . . . . . . . 54 5.2.3 Hierarchical similarity measure . . . . . . . . . . . . . . 58 5.2.4 Reconstruction process . . . . . . . . . . . . . . . . . . . . 59 5.2.5 Complexity study . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . 60 5.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Table 5 .

 5

1: Notation namely: Global, GeoLocal or one of two hierarchical measures Global GeoLocal or

Table 5

 5

	Methods	Reconstruction	State-I	State-II	State-III	State-IV
	Global	Yes	93.87%	96%	83%	77%
		No	89.79%	95%	81%	80%
	GeoLocal	Yes	100%	98%	91%	78%
		No	93.87%	93%	87%	78%
	Global GeoLocal	Yes	91.83%	94%	78%	78%
		No	87.75%	92%	76%	82%
	GeoLocal Global	Yes	93.87%	95%	85%	78%
		No	89.79%	93%	83%	77%

.2 depicts the results obtained depending on the use or not of the process of reconstruction (T hreshold = 0.28 ). These experiments are conducted on the real Kite data set.

Table 5 .

 5

2: The impact of the reconstruction process on the classification Chapter 5. Geometric Graph Matching

Table 5 .

 5 3 depicts the results obtained by our approaches and the approaches with which we compare, using the adequate threshold.

	Methods	Threshold	State	State	State	State	Synthetic
			I	II	III	IV	data set
	Global	0.28	93.87%	96%	83%	77%	98%
	GeoLocal	0.28	100%	98%	91%	77%	100%
	Global GeoLocal	0.28	91.83%	94%	78%	78%	98%
	GeoLocal Global	0.28	93.87%	95%	85%	78%	98%
	GED Bipartite	0.40	36.53%	41%	75%	11%	41.3%
	Beam GED	0.10	20.20%	28%	75%	44.44%	75%

Table 5 .

 5

3: Classification on the Kite data set We can see that our approaches GeoLocal, Global, Global GeoLocal and GeoLocal Global are more accurate than GED Bipartite and Beam GED at all the levels of the real and the synthetic Kite data set. This confirms that considering the geometric form (angles) has a high added value for Kite recognition. We can also see that GeoLocal is more accurate than Global, Global GeoLocal and GeoLocal Global at all the levels of the real and the synthetic Kite data set. However, Global GeoLocal and GeoLocal Global are slightly better in the negative data set (State IV) of the real data set. Although, GeoLocal achieves better classification accuracy compared to Global GeoLocal and GeoLocal Global . However, use of the hierarchical measures Global GeoLocal and

Table 5 . 4

 54

	Bipartite Beam GED

: Classification on the GREC data set

  In6.2. Graph decompositionother words, the neighbors of a triangle t are triangles sharing at least a common node with the triangle t.Definition 3 (N k -neighborhood of a triangle): two triangles t 0 and t k are N kneighbors, if there is between t 0 and t k a chain of (k -1) distinct triangles, at most, which are pairwise consecutive neighbors. Formally, t 0 and t k are N k -neighbors ⇔ ∃ t i=1..k-1 where : ∀ i = 1...(k -1), t i and t i+1 are neighbors. In other words, the N k -neighbors of a triangle t are the k recursive triangle neighbors of t.

Definition 2 (neighborhood of a triangle): two triangles are neighbors, if they share, at least, a common node. Let t 1 and t 2 two triangles and N (t 1 ) and N (t 2 ) their respective nodes. Then, t 1 and t 2 are neighbors ⇔ N (t 1 ) ∩ N (t 2 ) > 0.

Table 6 .

 6 ts j )| AG MAX (6.2)sim 1 (ts i , ts j ) compares the Area AG of the two triangle-stars ts i and ts j . (ts i , ts j ) compares the Perimeter P G of the two triangle-stars ts i and ts j .sim 3 (ts i , ts j ) = α 3 * (ts i , ts j ) compares the Area of each triangle A of the two triangle-stars ts i and ts j .sim 4 (ts i , ts j ) = α 4 * (ts i , ts j ) compares the Perimeter of each triangle P of the two triangle-stars ts i and ts j .sim 5 (ts i , ts j ) = α 5 * sim 5 (ts i , ts j ) compares the weights of each edge W of the two triangle-stars ts i and ts j .6.5. Edit distance between triangle-stars and triangular tessellations sim 6 (ts i , ts j ) = α 6 * sim 6 (ts i , ts j ) compares the Degree of each Node Deg of the two triangle-stars ts i and ts j .The symbols associated with the similarity measure are described in Table6.5. The triangle t l in the triangle-star ts i :t l ∈ ts i W i,l,kThe weight (Euclidian distance) of the edge e k of the triangle t l ∈ ts i Deg i,l,k The degree of node n k of the triangle t l ∈ ts i Γ Max number of triangles in the set triangle-stars of the two graphs g 1 and g 2 . Area of the triangle-star i. AG(ts i ) = 5: Symbols associated with the similarity measure and theirs description.Scale invariance. The proposed similarity measure d (Eq. 6.1) is sensitive to the scale changing, this means that two triangle-stars ts i and ts j having the same structure with different scale, are not similar d(ts i , ts j ) < 1. In the case that we want to ignore the scale changing (as required in some fields), the weights W of the edges of the compared graphs are normalized relativizing to the maximum edge's weight W MAX . Formally ∀i, W i = Wi WMAX . Let consider two triangle tessellations gT r1 and gT r2 having the same structure and composed by one triangle. Consequently, the triangle-stars ts 1 and ts 2 obtained are constituted by one triangle T (ts 1 ) = T (ts 2 ) = 1 (See Table 6.6). Even ts 1 and ts 2 have the same structure, the weights of edges are different W (ts 1 ) = {10, 15, 20} and W (ts 2 ) = {30, 45, 60}. Consequently, Chapter 6. Graph-based approach for non-rigid 3D Object Recognition d(ts i , ts j ) < 1, which means that ts 1 and ts 2 don't represent the same trianglestar. In the case where the weights of edges are normalized: W MAX1 = 20 and W MAX2 = 60 thus W (ts 1 ) = {10/20, 15/20, 20/20} = {0.5, 0.75, 1} and W (ts 2 ) = {30/60, 45/60, 60/60} = {0.5, 0.75, 1}. The normalized weights of edges are the same W (ts 1 ) = W (ts 2 ) and ts 1 and ts 2 have the same structure (See Table 6.6), consequently d(ts i , ts j ) = 1, which means that ts 1 and ts 2 (with normalized weights) represent the same triangle-star.

	sim 2 (ts i , ts j ) = α 2 *	|P G(ts i ) -P G(ts j )| P G MAX	(6.3)
	sim 2 l=Γ l=1 | A(T (ts i ) l ) -A(T (ts j ) l ) | A MAX * Γ	(6.4)
	sim 3 l=Γ l=1 | P (t i,l ) -P (t j,l ) | P MAX * Γ	(6.5)
	sim 4 l=Γ l=1	k=3 k=1 | W i,l,k -W j,l,k | 3 * W MAX * Γ	(6.6)

Table 6 . 6 :

 66 Example of triangle-stars with and without normalized weights.

  6.5. Edit distance between triangle-stars and triangular tessellations symbols descriptions): {AG(ts), PG(ts), {A(t i ), P(t i ), W(t i, j=1...3 ), deg(t i, j=1...3 ), Ang(t i, j=1...3 )}

	i= T (ts)
	i=1

  Databases description . . . . . . . . . . . . . . . . . . . . . . . 94 7.1.1 TOSCA database . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.1.2 SHREC11 watertight . . . . . . . . . . . . . . . . . . . . . . . 95 7.1.3 SHREC09 database . . . . . . . . . . . . . . . . . . . . . . . 95 7.2 Some state of the art shape-matching algorithms . . . . . . 95 7.3 Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . . . . 99 7.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.4.1 Results on the TOSCA database . . . . . . . . . . . . . . . . 100 7.4.2 Results on the SHREC11 watertight . . . . . . . . . . . . . . 109 7.4.3 Results on the SHREC09 database . . . . . . . . . . . . . . . 111 7.4.4 Results discussion . . . . . . . . . . . . . . . . . . . . . . . . 113 7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

	Chapter 7
	Experimental results of the
	Graph-based approach for
	non-rigid 3D Object Recognition
	Contents
	7.1

Table 7 .

 7 4: The accuracy with the degree of neighborhood N K=1 and according to the classification threshold, in the TOSCA database.

	Threshold Accuracy T P R	T NR
	0.06	83.24 %	82.29 % 83.35 %
	0.07	78.3 %	91.1 %	76.79 %
	0.08	74.6 %	95.46 % 72.14 %
	0.05	88.03 %	64.92 % 90.75 %
	0.04	90.54 %	40.75 % 96.40 %
	0.036	91.02 %	30.27 % 98.18 %
	0	89.48 %	0.17 %	100 %
	Threshold Accuracy T P R	T NR
	0.13	60.56 %	61.34 % 60.47 %
	0.11	68.45 %	52.00 % 70.40 %
	0.06	86.04 %	20.42 % 93.76 %
	0.08	79.90 %	32.90 % 85.44 %
	0	89.48 %	0.17 %	100 %

Table 7 .

 7 5: The accuracy with the degree of neighborhood N K=2 and according to the classification threshold, in the TOSCA database.

Table 7 .

 7 10 shows the Accuracy, T P R and T NR results obtained by T SM in the TOSCA database, using the thresholds giving us the highest Accuracy, T P R and T NR for each degree of neighborhood N K=1...6 and ∀ k, α k = 1.We obtained excellent results which are between 60% and 83% in the Accuracy, T P R and T NR, depending on the degree of neighborhood N K . The direct neighborhood N K=1 with threshold = 0.06, give us the best accuracy (in average 83%), followed by the accuracy obtained with N K=4 (in average 68%) then N K=3 and N

	Chapter 7. Experimental results of the Graph-based approach for
			non-rigid 3D Object Recognition
	Threshold Accuracy T P R	T NR
	0.19	65.78 %	66.93 % 65.65 %
	0.15	73.87 %	53.66 % 76.25 %
	0.11	80.70 %	36.47 % 85.91 %
	0	89.48 %	0.17 %	100 %

K=5 (in average 66%) and finally the accuracy obtained with N K=6 and N K=2 (in average 62%).

Table 7 .

 7 6: The accuracy with the degree of neighborhood N K=3 and according to the classification threshold, in the TOSCA database.

	Threshold Accuracy T P R	T NR
	0.22	68.65 %	67.89 % 68.74 %
	0.18	73.18 %	54.01 % 75.43 %
	0.14	82.04 %	34.99 % 87.58 %
	0.2	70.30 %	63.44 % 71.11 %
	0	89.48 %	0.17 %	100 %

Table 7 .

 7 7: The accuracy with the degree of neighborhood N K=4 and according to the classification threshold, in the TOSCA database.

	Threshold Accuracy T P R	T NR
	0.264	65.01 %	64.31 % 65.09 %
	0.22	71.27 %	51.92 % 73.55 %
	0.16	80.34 %	32.29 % 86 %
	0	89.48 %	0.17 %	100 %

Table 7 .

 7 8: The accuracy with the degree of neighborhood N K=5 and according to the classification threshold, in the TOSCA database.

Table 7 .

 7 Dark colours are associated to dissimilarity close or equal to zero, Light colours are associated to dissimilarity close or equal to one. Objects are similar if their dissimilarity is close or equal to 7.4. Resultszero.Using TOSCA database, we generate a n × n matrix, with n = 148 (the number of 3D objects) for each degree of neighborhood N K=1...6 using the adequate thresholds (see Table7.10). 9: The accuracy with the degree of neighborhood N K=6 and according to the classification threshold, in the TOSCA database.

	Threshold Accuracy T P R	T NR
	0.273	62.11 %	61.52 % 62.18 %
	0.24	66.95 %	50.17 % 68.93 %
	0.1		80.84 %	22.69 % 87.69 %
	0		89.48 %	0.17 %	100 %
	N K Threshold Accuracy T P R	T NR
	1	0.06	83.24 %	82.29 % 83.35 %
	2	0.13	60.56 %	61.34 % 60.47 %
	3	0.19	65.78 %	66.93 % 65.65 %
	4	0.22	68.65 %	67.89 % 68.74 %
	5	0.264	65.01 %	64.31 % 65.09 %
	6	0.273	62.11 %	61.52 % 62.18 %

Table 7 .

 7 10: T SM Best Accuracy, T P R and T NR results in TOSCA database for the degree of neighborhood N K=1...6 . Figure7.4 shows the confusion matrix associated with its dissimilarity for the degrees of neighborhood N K=1 . The darkest regions correspond to the block-diagonals of the confusion matrix which are associated with the intra-class dissimilarity. In the Figure7.4, we observe that objects from the same classes are similar, for instance, K=1 (approximately 9 days) and T SM with N K=2...6 (5 minutes for N K=2 and between 1 to 3 minutes for N K=3...6 ).

	the following classes: gorilla, centaur, horse ... etc. and we observe also that objects
	from different classes are dissimilar, for example: (cat, gorilla), (cat, seahorse),
	(gorilla, lioness) ... etc. In a few cases, there is some interclass similarity: the dog
	and the wolf, David and Victoria and, David and Michael. This is not surprising
	considering that their shape is relatively similar. All these observations demonstrate
	the efficiency of the proposed algorithm.

Table 7

 7

		Chapter 7. Experimental results of the Graph-based approach for
													non-rigid 3D Object Recognition
						centaur0: Precision and recall								gorilla0: Precision and recall
		1												1
	Precision	0.5											Precision	0.5
		0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1	0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
								Recall												Recall
						horse0: Precision and recall								lioness0: Precision and recall
		1												1
	Precision	0.5											Precision	0.5
		0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1	0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
								Recall												Recall
						seahorse0: Precision and recall								david11: Precision and recall
		1												1
	Precision	0.5											Precision	0.5
		0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1	0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
								Recall												Recall

.11 shows the obtained results (in term of E_Measure) of our approach T SM using the N K=1...

[START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF]

Table 7 .

 7 11: E_Measure results of our method T SM using N K=1...6 neighborhood and other methods of the state of the art in TOSCA database.

	7.4. Results
	three methods with which we compare.
	Methods	E_Measure
	Our method T SM with N K=1 0.9965
	Our method T SM with N K=2 0.9965
	Our method T SM with N K=3 0.9965
	Our method T SM with N K=4 0.9965
	Our method T SM with N K=5 0.9965
	Our method T SM with N K=6 0.9965
	TD	0.33
	Shape-DNA	0.55
	SRCP-TD	0.56

Table 7 .

 7 14: T SM Best Accuracy, T P R and T NR results in SHREC11 watertight database for the degree of neighborhood N K=2 and N K=6 .

	7.4. Results
	N K Threshold Accuracy T P R	T NR
	2	0.1076	67.08 %	67.04 % 67.08 %
	6	0.198	61.46 %	62.14 % 61.44 %
	Methods		E_Measure
	Our method T SM with N K=2 0.9961
	Our method T SM with N K=6 0.9966
	Modal-repr		0.731
	TD			0.3369
	Shape-DNA		0.6797
	SRCP-TD		0.69

Table 7 .

 7 [START_REF] Diestel | Graph Theory[END_REF]: E_Measure results of our method T SM using N K=2 and N K=6 neighborhood and other methods of the state of the art in SHREC11 watertight database.

Table 7 .

 7 [START_REF] Yan | A short survey of recent advances in graph matching[END_REF]: T SM Best Accuracy, T P R and T NR results in SHREC09 database for the degree of neighborhood N K=2 and N K=6 .

	7.4. Results
	N K Threshold Accuracy T P R	T NR
	2	0.026	55.41 %	55 %	55.42 %
	6	0.0401	61.19 %	59.17 % 61.25 %
		Methods		E_Measure
		Our method T SM with N K=2 0.94
		Our method T SM with N K=6 0.93
		CMVD-Binary		0.2
		CMVD-Depth		0.174
		Merged		0.192
		BF-SIFT		0.116
		BF-GridSIFT		0.204

Table 7 .

 7 [START_REF] Babai | Graph isomorphism in quasipolynomial time[END_REF]: E_Measure results of our method T SM using N K=2 and N K=6 neighborhood and other methods of the state of the art in SHREC09 database.

  1, Chapter 6) in the case of triangle-Stars. All the vectors have the same size t, which is equal to the maximum size of the two sets of substructures t = max(||S 1 ||, ||S 2 ||). In the case of ||S 1 || = ||S 2 ||, the vectors with small size will completed by (max(||S 1 ||, ||S 2 ||) -min(||S 1 ||, ||S 2 ||))

Acknowledgments

It would not have been possible to achieve this thesis and write this manuscript without the help and support of the kind people around me, to only some of whom it is possible to give particular mention here.

First of all, I wish to express my deepest gratitude to my advisors, Prof. Hamamache Kheddouci and Dr. Hamida Seba, for their valuable guidance, caring, patience and consistent encouragement throughout this research work. I thank them for giving me an interesting research topic related to graph matching field. I thank them also for continuous support and encouragement on both my research and other matters of life during my PhD.

I'm very thankful to Prof. Eric Paquet for introducing me to the field of 3D Pattern Recognition. I thank him for receiving me as visiting researcher at Ottawa University and National Research Council Canada during six months. I thank him for the knowledge and skills he imparted through our collaboration. He was always willing to help and give his best suggestions. Working with him is so enjoyable. I also appreciate his help to improve the quality of my dissertation. I also thank him for being a member of my PhD jury and for the time he spent to examine my thesis.

I'm also very thankful to all the members of KITE project. I thank Mr. Olivier Barge and all the archeologists' team of the Archéorient laboratory, for their expertise, help and collaboration which were necessary to realize and achieve our work on Kite recognition in satellite images. I'm also thankful to Dr. Charles-Edmond Bichot for his collaboration. I'm also very thankful to all the members of my PhD jury. Prof. Daniela Grigori and Prof. Olivier Togni for the time they spent for reviewing my thesis manuscript, and for their valuable feedback, comments and suggestions. Prof. Amel Bouzeghoub for spending her valuable time as my thesis examiner. I'm also very thankful to Prof. Mohand-Said Hacid, the head of LIRIS laboratory, for his help, availability and valuable guidance. vii We compared the obtained results with some state of the art shape-matching algorithms. We used in our experiments different evaluation criteria. In this chapter, we described and discussed the experimentations that we performed to evaluate our approach. We presented the different databases that we used in our experiments, some state of the art shape-matching algorithms to compare with, the evaluation criteria and the experimental results. The analysis of the time complexity (Section 6.7) and our experimental results on three standard databases (TOSCA, SHREC09 and SHREC11) under different evaluation criteria confirm the high performance and accuracy of our algorithm.

Edit distance between triangle-stars and triangular tessellations

In this section, we show how to compute the graph edit distance between trianglestars and between two triangular tessellations.

The pseudo metric

In this section we prove that the proposed distance is a pseudo-metric.

Definition : Let X a set of objects and x, y, z ∈ X. Let f be a function defined as follow f : X × X -→ R.

Let the following set of properties:

1. non-negativity: f (x, y) ≥ 0 2. symmetry: f (x, y) = f (y, x)

3. triangle inequality: f (x, y) ≤ f (x, z) + f (z, y)

The function f is a metric if f satisfies the four mentioned properties and f is a pseudo-metric if f satisfies only the first three properties (1, 2 and 3).

Since f is a pseudo metric, a distance function may be defined between each pair of graphs. As a result, the similarity of the objects associated with these graphs may be efficiently determined. Concretely, f is pseudo metric means that f return a correct value (f (X, Y ) ≥ 0 and f (X, Y ) = f (Y, X)) and f makes searching more efficient in the database using the triangle inequality [START_REF] Vleugels | Efficient image retrieval through vantage objects[END_REF][START_REF] Barros | Using the triangle inequality to reduce the number of comparisons required for similarity-based retrieval[END_REF].

Lemma The proposed similarity measure T SM (Eq. 6.10) between two sets of triangles-stars T S 1 and T S 2 is a pseudo-metric.

Proof: From (Eq. 6.10) it may be concluded that if T SM is a pseudo-metric then d (Eq. 6.1) is a pseudo-metric which implies that sim k (Eq. 6.

2) is a pseudometric. Consequently, we shall prove that sim k (Eq. 6.

2) is a pseudo-metric.

Proving that sim k (Eq. 6.

2) is a pseudo-metric is equivalent to check the first three properties in sim k (Eq. 6.2). The functions sim k are defined as follows:

Thus T SM is non-negative.

Class Pose 1 Pose 2 Pose 3

Centaur Gorilla Table 7.2: Some objects from the TOSCA Database.

SHREC11 watertight

The SHREC11 watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] is a large and diverse non-rigid 3D shape database, recreated and modified from several publicly available databases such as the McGill database [START_REF] Siddiqi | Retrieving articulated 3-d models using medial surfaces[END_REF], TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF] and the Princeton Shape Benchmark [START_REF] Shilane | The princeton shape benchmark[END_REF]. The SHREC11 watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] contains 600 non-rigid objects represented by triangular tessellations. The data-set is equally classified into 30 classes, with 20 poses per class. Figure 7.1 shows two objects of each class in the SHREC11 watertight data-set [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF].

SHREC09 database

The SHREC09 database [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF] is Partial 3D Models with the objective to retrieve the models which have parts similar to the query. It consists on two data-sets:

• Target data-set: The target database contains 720 complete 3D models is equally classified into 40 classes, with 18 models per class. The classes are defined with respect to their semantic categories. Table 7.3 shows the different classes in the target database.

• Query data-set: The query data-set consists of 20 3D partial models which are obtained by cutting parts from complete models (see Figure 7.2).

Some state of the art shape-matching algorithms

In order to evaluate and show the efficient of our approach, we compare it with a state of the art set of shape-matching algorithms.

Chapter 7. Experimental results of the Graph-based approach for non-rigid 3D Object Recognition T N + F P .

• Run time: We measure the average run time of computing the distance between two graphs and the global time needed for all the database.

• E_Measure: is based on the combination of precision and recall and it is defined using F_Measure. F_Measure is defined as follow:

F _M easure = 2 * P recision * Recall P recision + Recall . And E_Measure is defined as follow:

. With E_M easure ∈ [0, 1] and the higher value indicate better results.

Results

In this section, we discuss and compare the obtained results on the three databases (TOSCA [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF], SHREC11 watertight [START_REF] Lian | SHREC '11 track: Shape retrieval on non-rigid 3d watertight meshes[END_REF] and SHREC09 [START_REF] Axenopoulos | Shrec 2009-shape retrieval contest of partial 3d models[END_REF]).

The proposed distance T SM is a parameterized distance having a set of parameters α k allowing different configurations, the default value is: α k = 1, ∀ k. In addition, we defined a threshold in order to improve the classification accuracy. Considering the set of parameters α k and the threshold in our approach offer a error-tolerant distance and make the proposed approach invariant to different deformations. The parameters α k and the threshold may be specified by inspection or by using machine learning techniques.

In our experiments we consider: a descending strict total order on the triangles set of each object. Different degree of neighborhood N K . The default value of parameters ∀ k, α k = 1. The best threshlod for each degree of neighborhood N K and for each database.

Results on the TOSCA database

We compute the distance between each pair of triangular tessellations in the TOSCA database [START_REF] Bronstein | Efficient computation of isometry-invariant distances between surfaces[END_REF][START_REF] Bronstein | Calculus of nonrigid surfaces for geometry and texture manipulation[END_REF] using the proposed similarity measure T SM. Two triangular tessellations are considered similar if their distance is less than a specific threshold.

Depending on the parameters α k , the threshlod and the degree of neighborhood N K , the results may be different. Tables (7.4, 7.5, 7.6, 7.7, 7.8 and 7.9) show Chapter 7. Experimental results of the Graph-based approach for non-rigid 3D Object Recognition Even the obtained results using the direct neighborhood N K=1 are highly better than the results obtained with other degree of neighborhood N K = 2...6. However, we obtain a high performance in term of the run time using a high degree of neighborhood. (see Table 6.7).

We have also measured the total run time on the TOSCA database for each degree of neighborhood N k=1...6 (see Figure 7.6). The total run time performance shown in Figure 7.6 confirm the performances shown in Figure 7.5 and the theoretical time complexity. Figure 7.6 show clearly that the time needed to process all the database using T SM with N K=i is longer than T SM with N K=i+1 , i.e., T SM with N K=i need more time to process all the database than T SM with N K=i+1 . We remark also a big difference between the time needed to process all the database using T SM T P R and T NR results, depending on the degree of neighborhood N K=2 and N K=6 .

Using the N K=2 neighborhood with threshold = 0.1076, give us the best accuracy (in average 67%) which is better than the accuracy obtained using the N K=6 neighborhood with threshold = 0.198 (in average 61%).

We performed also an other comparison in term of E_Measure in which we compare our method T SM using N K=2 and N K=6 neighborhood with different methods of the state of art in the SHREC11 watertight database. Table 7.15 shows the obtained results (in term of E_Measure) of our approach T SM using N K=2 and N K=6 neighborhood compared to the other methods. Table 7.15 shows that our method T SM provides an E_Measure highly better than the other methods with which we compare. 7.17: The Accuracy, T P R and T NR results with the degree of neighborhood N K=6 and according to the classification threshold, in the SHREC09 database.

and T NR, depending on the degree of neighborhood N K=2 and N K=6 . Using the N K=6 neighborhood with threshold = 0.0401, give us the best accuracy (in average 61%) which is better than the accuracy obtained using the N K=2 neighborhood with threshold = 0.026 (in average 55%).

We performed also an other comparison in term of E_Measure in which we compare our method T SM using the N K=2 and N K=6 neighborhood with the five methods (CMVD-Binary, CMVD-Depth, Merged, BF-SIFT and BF-GridSIFT) in the SHREC09 database. Table 7. [START_REF] Babai | Graph isomorphism in quasipolynomial time[END_REF] shows the obtained results (in term of E_Measure) of our approach T SM using the N K=2 and N K=6 neighborhood compared to the five methods (CMVD-Binary, CMVD-Depth, Merged, BF-SIFT and BF-GridSIFT).

Table 7.19 shows that our method T SM provides excellent results in terms of E_Measure. Table 7. [START_REF] Babai | Graph isomorphism in quasipolynomial time[END_REF] shows also that our method T SM provides an E_Measure highly better than the other methods with which we compare.

Further works

complexity is reduced. The proposed graph edit distance is based on triangle-Stars which is a local structure that covers a larger neighborhood than a classic star decomposition [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][START_REF] Zeng | Comparing stars: On approximating graph edit distance[END_REF]. Consequently, the proposed dissimilarity measure assures an optimal approximation. The resulting triangle-Stars are used to determine the distance between triangular tessellation using the Hungarian algorithm. The proposed approach assured a minimum number of disjoints triangle-Stars, offered a better dissimilarity by covering a larger area of neighbors in triangle-Stars and used a set of descriptors which are invariant or at least oblivious under most common deformations. The proposed approach is based on an approximation of Graph Edit Distance which is fault-tolerant to noise and distortion, making our approach very appropriate for comparing deformable objects. We proved that the proposed distance is a pseudo-metric and we analysed its time complexity. We realized a set of experiments including comparisons, on different well known databases for entire and partial deformable shape comparison, and under various evaluation criteria.

The analysis of the time complexity and our experimental results on three standard databases (TOSCA, SHREC09 and SHREC11) confirmed the high performance and accuracy of our algorithm. The set of experimentations and the obtained results on SHREC09 database showed that the proposed approach is efficient also for the 3D objects sub-matching, which proved that our method is extensible and quite general.

Further works

In this section, we describe some suggestions for further research and future works.

The approaches that we proposed are parameterizable. Indeed, many parameters