A method for segmentation and recognition of image structures based on graph homomorphisms is presented in this paper. It is a model-based recognition method where the input image is over-segmented and the obtained regions are represented by an attributed relational graph (ARG). This graph is then matched against a model graph thus accomplishing the model-based recognition task. This type of problem calls for inexact graph matching through a homomorphism between the graphs since no bijective correspondence can be expected, because of the over-segmentation of the image with respect to the model. The search for the best homomorphism is carried out by optimizing an objective function based on similarities between object and relational attributes defined on the graphs. The following optimization procedures are compared and discussed: deterministic tree search, for which new algorithms are detailed, genetic algorithms and estimation of distribution algorithms. In order to assess the performance of these algorithms using real data, experimental results on supervised classification of facial features using face images from public databases are presented.
Description
Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms
%0 Journal Article
%1 CesarJr20052099
%A Jr., Roberto M. Cesar
%A Bengoetxea, Endika
%A Bloch, Isabelle
%A Larrañaga, Pedro
%D 2005
%J Pattern Recognition
%K 2013 algorithm based graph inexact matching model similarity
%N 11
%P 2099 - 2113
%R 10.1016/j.patcog.2005.05.007
%T Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms
%U http://www.sciencedirect.com/science/article/pii/S0031320305002177
%V 38
%X A method for segmentation and recognition of image structures based on graph homomorphisms is presented in this paper. It is a model-based recognition method where the input image is over-segmented and the obtained regions are represented by an attributed relational graph (ARG). This graph is then matched against a model graph thus accomplishing the model-based recognition task. This type of problem calls for inexact graph matching through a homomorphism between the graphs since no bijective correspondence can be expected, because of the over-segmentation of the image with respect to the model. The search for the best homomorphism is carried out by optimizing an objective function based on similarities between object and relational attributes defined on the graphs. The following optimization procedures are compared and discussed: deterministic tree search, for which new algorithms are detailed, genetic algorithms and estimation of distribution algorithms. In order to assess the performance of these algorithms using real data, experimental results on supervised classification of facial features using face images from public databases are presented.
@article{CesarJr20052099,
abstract = {A method for segmentation and recognition of image structures based on graph homomorphisms is presented in this paper. It is a model-based recognition method where the input image is over-segmented and the obtained regions are represented by an attributed relational graph (ARG). This graph is then matched against a model graph thus accomplishing the model-based recognition task. This type of problem calls for inexact graph matching through a homomorphism between the graphs since no bijective correspondence can be expected, because of the over-segmentation of the image with respect to the model. The search for the best homomorphism is carried out by optimizing an objective function based on similarities between object and relational attributes defined on the graphs. The following optimization procedures are compared and discussed: deterministic tree search, for which new algorithms are detailed, genetic algorithms and estimation of distribution algorithms. In order to assess the performance of these algorithms using real data, experimental results on supervised classification of facial features using face images from public databases are presented. },
added-at = {2014-01-15T16:59:59.000+0100},
author = {Jr., Roberto M. Cesar and Bengoetxea, Endika and Bloch, Isabelle and Larrañaga, Pedro},
biburl = {https://www.bibsonomy.org/bibtex/24c3de7cb5267f270d3f587440838500f/s_nkeha},
description = {Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms},
doi = {10.1016/j.patcog.2005.05.007},
interhash = {e5455316ff1a4a78daa2f1571e2dd183},
intrahash = {4c3de7cb5267f270d3f587440838500f},
issn = {0031-3203},
journal = {Pattern Recognition },
keywords = {2013 algorithm based graph inexact matching model similarity},
number = 11,
pages = {2099 - 2113},
timestamp = {2014-01-15T16:59:59.000+0100},
title = {Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms },
url = {http://www.sciencedirect.com/science/article/pii/S0031320305002177},
volume = 38,
year = 2005
}