Efficient algorithms for matching attributed graphs and function-described graphs

Function-described graphs (FDG) have been introduced by the authors as a representation of an ensemble of attributed graphs (AG) for structural pattern recognition alternative to first-order random graphs. In previous works, algorithms for the synthesis of FDG and a branch-and-bound algorithm for er...

Full description

Saved in:
Bibliographic Details
Main Authors: Serratosa, F., Alquezar, R., Sanfeliu, A.
Format: Conference Proceeding
Language:English
Subjects:
Error analysis
Labeling
Neural networks
NP-complete problem
Pattern recognition
Polynomials
Space exploration
Testing
Time measurement
Tree graphs
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Function-described graphs (FDG) have been introduced by the authors as a representation of an ensemble of attributed graphs (AG) for structural pattern recognition alternative to first-order random graphs. In previous works, algorithms for the synthesis of FDG and a branch-and-bound algorithm for error-tolerant graph matching, which computes a distance measure between AG and FDG, have been reported. Since the worst-case complexity of that matching algorithm is exponential in the number of nodes, an approximate algorithm to compute a suboptimal measure is proposed in this paper. Results in 3D-object recognition show that, although the computational time is reduced, there is only a slight decrease of effectiveness while classifying an AG against a set of FDG.
ISSN:1051-4651
2831-7475
DOI:10.1109/ICPR.2000.906212