RULEGRAPHS FOR GRAPH MATCHING IN PATTERN-RECOGNITION

In Pattern Recognition, the Graph Matching problem involves the matching of a sample data graph with the subgraph of a larger model graph where vertices and edges correspond to pattern parts and their relations. In this paper, we present Rulegraphs, a new method that combines the Graph Matching approach with Rule-based approaches from Machine Learning. This new method reduces the cardinality of the (NP-Complete) Graph Matching problem by replacing model part, and their relational, attribute states by rules which depict attribute bounds and evidence for different classes. We show how rulegraphs, when combined with techniques for checking feature label-compatibilities, not only reduce the search space but also improve the uniqueness of the matching process.