Abstract
We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the node and edge similarities between them. A randomized construction algorithm is proposed to build feasible solutions to the problem. Two neighborhood structures and a local search procedure for solution improvement are also proposed. Computational results are presented and discussed, illustrating the effectiveness of the combined approach involving randomized construction and local search.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bengoetxea, E., Larranaga, P., Bloch, I., Perchant, A., Boeres, C.: Inexact graph matching by means of estimation distribution algorithms. Pattern Recognition 35, 2867–2880 (2002)
Bloch, I.: Fuzzy relative position between objects in image processing: a morphological approach. IEEE Transactions on Pattern Analysis Machine Intelligence 21, 657–664 (1999)
Bloch, I.: On fuzzy distances and their use in image processing under imprecision. Pattern Recognition 32, 1873–1895 (1999)
Bloch, I., Maître, H., Anvari, M.: Fuzzy adjacency between image objects. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 5, 615–653 (1997)
Chan, K.P., Cheung, Y.S.: Fuzzy-attribute graph with application to chinese character recognition. IEEE Transactions on Systems, Man and Cybernetics 22, 402–410 (1992)
Cross, A.D.J., Hancock, E.R.: Relational matching with stochastic optimization. In: International Conference on Computer Vision, pp. 365–370 (1995)
Cross, A.D.J., Wilson, R.C., Hancock, E.R.: Inexact graph matching using genetic search. Pattern Recognition 30, 953–970 (1997)
Duarte, A.R.: New heuristics and an exact integer programming formulation for an inexact graph matching problem (in Portuguese). M.Sc. Dissertation, Catholic University of Rio de Janeiro (2004)
El-Sonbaty, Y., Ismail, M.A.: A new algorithm for subgraph optimal isomorphism. Pattern Recognition 31, 205–218 (1998)
Finch, A.W., Wilson, R.C., Hancock, E.R.: Symbolic Graph matching with the EM algorithm. Pattern Recognition 31, 1777–1790 (1998)
Moissinac, H., Maître, H., Bloch, I.: Markov random fields and graphs for uncertainty management and symbolic data fusion in a urban scene interpretation. In: EUROPTO Conference on Image and Signal Processing for Remote Sensing, vol. 2579, pp. 298–309 (1995)
Perchant, A.: Morphisme de graphes d’attributs flous pour la reconnaissance structurelle de scènes. Doctorate thesis, École Nationale Supérieure des Télécommunications (2000)
Perchant, A., Bloch, I.: A new definition for fuzzy attributed graph homomorphism with application to structural shape recognition in brain imaging. In: Proceedings of the 16th IEEE Conference on Instrumentation and Measurement Technology, pp. 402–410 (1999)
Perchant, A., Boeres, C., Bloch, I., Roux, M., Ribeiro, C.C.: Model-based scene recognition using graph fuzzy homomorphism solved by genetic algorithm. In: 2nd IAPR-TC-15 Workshop on Graph-based Representations, pp. 61–70 (1999)
Ranganath, H.S., Chipman, L.J.: Fuzzy relaxaton approach for inexact scene matching. Image and Vision Computing 10, 631–640 (1992)
Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 219–249. Kluwer, Dordrecht (2002)
Rosenfeld, A., Hummel, R., Zucker, S.: Scene labeling by relaxation operations. IEEE Transactions on Systems, Man and Cybernetics 6, 420–433 (1976)
Schrage, L.: A more portable FORTRAN random number generator. ACM Transactions on Mathematical Software 5, 132–138 (1979)
Singh, M., Chaudhury, A.C.S.: Matching structural shape descriptions using genetic algorithms. Pattern Recognition 30, 1451–1462 (1997)
Wong, A.K.C., You, M., Chan, S.C.: An algorithm for graph optimal monomorphism. IEEE Transactions on Systems, Man and Cybernetics 20, 628–636 (1990)
Wong, E.K.: Model matching in robot vision by subgraph isomorphism. Pattern Recognition 25, 287–303 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boeres, M.C., Ribeiro, C.C., Bloch, I. (2004). A Randomized Heuristic for Scene Recognition by Graph Matching. In: Ribeiro, C.C., Martins, S.L. (eds) Experimental and Efficient Algorithms. WEA 2004. Lecture Notes in Computer Science, vol 3059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24838-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-24838-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22067-1
Online ISBN: 978-3-540-24838-5
eBook Packages: Springer Book Archive