Ecole Nationale Supérieure des Télécommunications Département Traitement du Signal et des Images Ecole doctorale Edite 


abstract Publications and BibTeX entry table of contents Download...
whole thesis in PDF (3.5Mb) Preliminaries:
acknowledgements, table of contents...

Inexact Graph Matching Using Estimation of Distribution Algorithms is a PhD thesis concentrating on a new method to solve inexact graph matching problems based on the learning and simulation of probabilistic graphical models such as Bayesian and Gaussian networks.The thesis has been undertaken under the supervision of Isabelle Bloch and Pedro Larrañaga, from the Ecole Nationale Supérieure des Télécommunications (Paris, France) and the University of the Basque Country (San Sebastian, Spain) respectively. This PhD thesis obtained sponsorship from the following institution and offical bodies: the University of the Basque Country (projects UPV140.226EB131/99 and 9/UPV/EHU 00140.22612084/2000), the Department of Education Universities and Research of the Basque Government (project PI 199940), the Spanish Ministry for Science and Education (project HF19990107), the French Ministry for Education, Research and Technology (project Picasso00773TE), and the Spanish Ministry for Science and Technology (project TIC20012973C0503). This page contains an abstract, summaries in French and Spanish, a table of contents, and the whole thesis in PDF format to be downloaded. Please, if you are uploading this thesis or parts of it email me <endika@si.ehu.es>
so that I keep a record of those interested on this field.
Thanks. 
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 NPhard, 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 PhDThe publication of this PhD, as well as the CV of the author, can be found here. BibTeX Entry@PHDTHESIS{bengoetxeaPHD02, 
Preliminaries:
acknowledgements, table of contents, list of figures, list of tables
Summary
in French
Summary in Spanish
Chapter
1: Introduction
Chapter 2: The graph matching problem
2.1 Basic notation and terminology . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .3
2.2 Definition and classification of graph matching problems . . . . . . . .
. . . . . . 4
2.3 Complexity of graph matching . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .7
2.4 State of the art in the literature . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 8
2.5 Graph matching problem types selected for this thesis . . . . . . . . .
. . . . . 17
Chapter 3: Graph matching as a combinatorial
optimization problem with constraints
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .19
3.2 Graph matching problems with special constraints in the literature . . .
. . .20
3.3 Representations of graph matching solutions by means of individuals . .
. .20
3.4 Fitness functions applied to graph matching . . . . . . . . . . . . . .
. . . . . . . .28
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 41
Chapter 4: Estimation of distribution algorithms
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .43
4.2 Probabilistic graphical models . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . ...46
4.3 Estimation of distribution algorithms in discrete domains . . . . . . .
. . .. . . 50
4.4 Estimation of distribution algorithms in continuous domains . . . . . .
. . . . .58
4.5 Estimation of distribution algorithms for inexact graph matching . . . .
. . . .68
Chapter 5: Parallel estimation of distribution
algorithms
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .77
5.2 Sequential programs and parallelization . . . . . . . . . . . . . . . .
. . . . . . . . .78
5.3 Parallel architectures and systems . . . . . . . . . . . . . . . . . . .
. . . . . . . . ..85
5.4 Parallelism techniques in the literature applied to graph matching. . .
. . . .90
5.5 Parallelization of sequential EDA programs. . . . . . . . . . . . . . .
. . . . . . . .91
Chapter 6: Experiments with synthetic examples
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .97
6.2 Study 1: measurement of the performance . . . . . . . . . . . . . . . .
. . . . . . .97
6.3 Study 2: evolution of probabilistic graphical structures . . . . . . . .
. . . . . .110
6.4 Study 3: parallelization . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .115
6.5 Conclusions of the studies on synthetic problems . . . . . . . . . . . .
. . . . .120
Chapter 7: Experiments with real examples
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .125
7.2 Real example 1: recognition of brain images. . . . . . . . . . . . . . .
. . . . . .125
7.3 Real example 2: recognition of human facial features . . . . . . . . . .
. . . . 133
7.4 Conclusions of the experiments in real problems . . . . . . . . . . . .
. . . . . 145
Chapter
8: Conclusions and further work
8.1 Conclusions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .149
8.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 150
Appendix
A: Example on how to use a permutationbased approach in EDAs
A.1 Example
of translating from a permutation to the solution it symbolizes . 153
A.2 The redundancy problem on permutationbased representations . . . . . .
.156
Appendix
B: Example of correcting individuals
B.1 Simulation
with LTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .158
B.2 Simulation with ATM . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .159
Appendix
C: On processes and threads: synchronization and communication in parallel programs
C.1 Sequential and parallel programs: main differences . . . . . . . . . . .
. . . . . 161
C.2 Processes and threads . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .162
C.3 Communication and synchronization between processes or threads . . . ..163
Appendix
D: Analysis and parallelization of the source code of EBNABIC
D.1 Short review of the source code of the sequential EDA program . . . . .
. . 177
D.2 Parallelization using threads . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 179
D.3 Parallelization using MPI . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .187