Inexact Graph Matching Using Estimation of Distribution Algorithms could be a PhD thesis focusing on a totally new approach to solve inexact graph matching problems while using learning and simulation of probabilistic graphical models for example Bayesian and Gaussian systems.

The thesis remains transported out underneath the supervision of Isabelle Bloch and Pedro Larrañaga, inside the Ecole Nationale Supérieure plusieurs Télécommunications (Paris, France) along with the College within the Basque Country (San Sebastian, The country) correspondingly.

This PhD thesis acquired sponsorship inside the following institution and offical physiques: the college within the Basque Country (projects UPV140.226-EB131/99 and 9/UPV/EHU 00140.226-12084/2000), the Department from the practice Universities and Research within the Basque Government (project PI 1999-40), the Spanish Ministry for Science and Education (project HF1999-0107), french Ministry for Education, Research and Technology (project Picasso-00773TE), along with the Spanish Ministry for Science (project TIC2001-2973-C05-03).

This site contains an abstract. summaries in French and Spanish. a table of contents. along with the whole thesis in PDF format to obtain downloaded.

Please, if you’re uploading this thesis or parts of it message me endika@si.ehu.es >to make certain which i keep close track of individuals interested concerning this field. Thanks.

Abstract

Within the yesteryear few years graphs are really suggested in computer vision and pattern recognition for encoding structural information. Furthermore, the interest of graph representations additionally for their corresponding graph matching techniques is growing because of the versatility of representing understanding by means of graphs.

Understanding is encoded of these graphs with the data acquired from images, where vertices represent the segments or entities within the image and edges show the relationships together. Types of areas by which this type of representation can be utilized are cartography, character recognition, and recognition of brain structures among much more. Excellent in the input image is transported out by constructing another graph from each image to obtain recognized and matching both model graph along with the recently generated graph (i.e. the information graph).

Numerous graph matching techniques is pertinent to think about an isomorphism which will match precisely the model along with the graph produced with the look. However, due to the schematic part of the model along with the difficulty to segment precisely the consider significant entities, the isomorphism condition may be too strong in a number of real problems and cannot need between both graphs. In such instances, such problems demand inexact graph matching, along with the aim on these would be to uncover the very best homomorphism possible. Inexact graph matching problems across the domain computer vision and pattern recognition constitute the objective that’s tackled concerning this thesis.

The inexact graph matching problem remains proven to obtain NP-hard, and thus algorithms that offer an approximation to acceptable solutions are seemly.

To be able to face this complex problem, inexact graph matching are as being a combinatorial optimization issue with constraints. This thesis analyzes the problems and mechanisms that might be examined for this reason, regarding solution representations and fitness functions. Estimation of Distribution Algorithms are perfect for solving this type of problems.

Estimation of distribution algorithms could be a recent subject in transformative computation which are put on optimization problems. Several algorithms and approaches are really created by different authors within the literature, but to date you will find very number of papers showing their potential and evaluating individuals with other transformative computation methods and algorithms. This thesis introduces the theoretical foundations of EDAs, and it also proposes its use –inside the discrete and continuous domains– to be able to solve inexact graph matching problems. Adaptations of EDA methods to the current problems with constraints are described, additionally for their performance for inexact graph matching is instead of individuals of broadly known transformative computation methods for example genetic algorithms and transformative strategies.

Regrettably, what size the graphs combined with amount of attributes that real problems contain is generally excessive for optimization algorithms, requiring individuals to complete for almost any extended time before coming back any acceptable result. This can be truly the problem for example of image recognition problems, where what size graphs increases thinking about the range of image features, making the matching method to be complex. Therefore, this thesis also introduces guidelines and experimental latest results for parallelization of EDAs aiming at reducing their computation time.

Finally, two particular inexact graph matching problems put on recognition of brain structures have been verified as types of the options this new graph matching approach offers.

Publications in the PhD and BibTeX entry

Publications in the PhD

The publication in the PhD, combined with CV within the author, are available here .

BibTeX Entry

@PHDTHESIS author = E. Bengoetxea,
title = Inexact Graph Matching Using Estimation of Distribution Algorithms ,
school = Ecole Nationale Sup’erieure plusieurs T’el’ecommunications,
year = 2002,
address = Paris, France,
month = 12 ,
>

Table of Contents

Chapter 1: Introduction

Chapter 2: The graph matching problem
2.1 Fundamental notation and terminology. 3
2.2 Definition and classification of graph matching problems. 4
2.3 Complexity of graph matching. 7
2.4 Symptom in the skill within the literature. 8
2.5 Graph matching problem types selected using this thesis. 17

Chapter 3: Graph matching as being a combinatorial optimization issue with constraints
3.1 Introduction. 19
3.2 Graph matching problems with special constraints within the literature. 20
3.3 Representations of graph matching solutions by way of individuals. 20
3.4 Fitness functions put on 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 Consecutive programs and parallelization. 78
5.3 Parallel architectures and systems. 85
5.4 Parallelism techniques to the literature put on graph matching. 90
5.5 Parallelization of consecutive EDA programs. 91

Chapter 6: Experiments with synthetic examples
6.1 Introduction. 97
6.2 Study 1: measurement within the performance. 97
6.3 Study 2: evolution of probabilistic graphical structures. 110
6.4 Study 3: parallelization. 115
6.5 Conclusions within the studies on synthetic problems. 120

Chapter Seven Personal bankruptcy: 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 expression. 133
7.4 Conclusions within the experiments in solid problems. 145

Appendix A: Example on the way to use a permutation-based approach in EDAs
A.1 Demonstration of converting within the permutation for that solution it symbolizes. 153
A.2 The redundancy problem on permutation-based representations. 156

Appendix C: On processes and threads: synchronization and communication in parallel programs
C.1 Consecutive and parallel programs: primary variations. 161
C.2 Processes and threads. 162
C.3 Communication and synchronization between processes or threads. 163

Appendix D: Analysis and parallelization within the source code of EBNABIC
D.1 Short review of the building blocks code within the consecutive EDA program. 177
D.2 Parallelization using threads. 179
D.3 Parallelization using MPI. 187