In the recent years graphs have been proposed in the field of computer vision and pattern recognition as a means for encoding structural information. Furthermore, the interest of graph representations and their corresponding graph matching techniques is increasing due to the versatility of representing knowledge in the form of graphs. Knowledge is encoded in these graphs by means of the information extracted from images, where vertices represent the segments or entities of the image and edges show the relationships between them. Examples of areas in which this type of representation is used are cartography, character recognition, and recognition of brain structures among many others. The recognition of an input image is performed by constructing another graph from each image to be recognized and matching both the model graph and the newly generated graph (i.e. the data graph).

Many different graph matching techniques can be applied to search for an isomorphism that will match exactly the model and the graph generated from the image. However, because of the schematic aspect of the model and the difficulty to segment accurately the image into meaningful entities, the isomorphism condition can be too strong in many real problems and cannot be expected between both graphs. In these cases, such problems call for inexact graph matching, and the aim on these is to search for the best homomorphism possible. Inexact graph matching problems on the domain of computer vision and pattern recognition constitute the target that is tackled on this thesis.

The inexact graph matching problem has been proved to be NP-hard, and therefore algorithms that provide an approximation to acceptable solutions are seemly. In order to face this complex problem, inexact graph matching can be regarded as a combinatorial optimization problem with constraints. This thesis analyzes the issues and mechanisms that have to be considered for this purpose, regarding solution representations and fitness functions. Estimation of Distribution Algorithms are well suited for solving this type of problems.

Estimation of distribution algorithms is a recent topic in evolutionary computation that are applied to optimization problems. Several algorithms and approaches have already been introduced by different authors in the literature, but up to now there are very few papers showing their potential and comparing them to other evolutionary computation methods and algorithms. This thesis introduces the theoretical foundations of EDAs, and it proposes its use --both in the discrete and continuous domains-- in order to solve inexact graph matching problems. Adaptations of EDA approaches to such type of problems with constraints are described, and their performance for inexact graph matching is compared with that of broadly known evolutionary computation techniques such as genetic algorithms and evolutionary strategies.

Unfortunately, the size of the graphs as well as the number of attributes that real problems contain is usually too high for optimization algorithms, requiring them to execute for a long time before returning any satisfactory result. This is the case for instance of image recognition problems, where the size of graphs increases with the number of image features, making the matching process to be more complex. Due to this fact, this thesis also introduces guidelines and experimental results for parallelization of EDAs aiming at reducing their computation time.

Finally, two particular inexact graph matching problems applied to recognition of brain structures are shown as examples of the possibilities that this new graph matching approach offers.

Publications of this PhD

The publication of this PhD, as well as the CV of the author, can be found here.

BibTeX Entry

@PHDTHESIS{bengoetxeaPHD02,
author = "E. Bengoetxea",
title = "Inexact Graph Matching Using Estimation of Distribution Algorithms ",
school = "Ecole Nationale Sup\'erieure des T\'el\'ecommunications",
year = 2002,
address = "Paris, France",
month = "Dec"
}