Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs
An inexact matching algorithm for Attributed Relational Graphs is presented: according to it, two graphs are considered similar if, by using a defined set of syntactic and semantic transformations, they can be made isomorphic to each other. The matching p
- PDF / 1,139,795 Bytes
- 10 Pages / 481.882 x 691.647 pts Page_size
- 34 Downloads / 264 Views
Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs L. P. CordelIa, P. Foggia, C. Sansone, and M. Vento, Naples
Abstract
An inexact matching algorithm for Attributed Relational Graphs is presented: according to it, two graphs are considered similar if, by using a defined set of syntactic and semantic transformations, they can be made isomorphic to each other. The matching process is carried out by using a State Space Representation: a state represents a partial solution of the matching between the graphs, and a transition between two states corresponds to the addition of a new pair of matched nodes. A set of feasibility rules are introduced for pruning states associated to partial matching solutions which do not satisfy the required graphs morphism. Results outlining the computational cost reduction achieved by the method are given with reference to a set of randomly generated graphs. AMS Subject Classification: 68TlO (68RIO). Key words: Attributed relational graphs, graph isomorphism, inexact matching.
1. Introduction Structural descriptions of visual patterns can be conveniently put in form of Attributed Relational Graphs (ARGs) [1]. An ARG provides both syntactic information, held by the layout of unlabeled nodes and branches respectively identifying the structural primitive components of the pattern and their relations, and semantic information consisting of the attributes associated to nodes and branches. In real applications, pattern variability is such that samples are seldom identical to prototypes. The variations may be reflected by both syntactic and semantic deformations of the representative graphs, so that pattern recognition can only be achieved by inexact graph matching methods able to manage both these possibilities. The quite few approaches to inexact graph matching proposed in the literature, try to extend the applicability of exact matching methods, by introducing criteria allowing matching in presence of syntactic and/or semantic deformations. In [2], a pattern deformational model is proposed. In its preliminary form only a class of semantic (structure-preserving) deformations is considered and the matching algorithm is based on a graph isomorphism for the syntactic part of the ARG. A generalization of the method, including the possibility of deleting nodes and branches, is proposed in [3]. The algorithm, though powerful enough for some practical applications, is not effective when large varia-
44
L. P. CordelIa et al.
tions among the members of a same class may exist. In these cases inexact matching approaches based on the definition of a distance measure between graphs, seem more appropriate. In [4] the distance measure is based on the evaluation of the minimum number of transformations to be applied to one of the compared graphs in order to obtain the other one. Specifically, the distance measure is defined as the recognition cost of ARG nodes plus the cost of a given set of transformations including attribute values modification so as node and branch inse
Data Loading...
