A distance measure between attributed relational graphs for pattern recognition

TLDR

The paper proposes a method to compute a distance measure between two nonhierarchical attributed relational graphs. The method uses descriptive graph grammars to represent graphs and defines the distance as the minimal cost of node and branch modifications—including recognition costs and label substitutions—computed via cost functions. Unlike prior measures, this approach incorporates node recognition costs, and it successfully distinguishes lower‑case handwritten English characters.

Abstract

A method to determine a distance measure between two nonhierarchical attributed relational graphs is presented. In order to apply this distance measure, the graphs are characterised by descriptive graph grammars (DGG). The proposed distance measure is based on the computation of the minimum number of modifications required to transform an input graph into the reference one. Specifically, the distance measure is defined as the cost of recognition of nodes plus the number of transformations which include node insertion, node deletion, branch insertion, branch deletion, node label substitution and branch label substitution. The major difference between the proposed distance measure and the other ones is the consideration of the cost of recognition of nodes in the distance computation. In order to do this, the principal features of the nodes are described by one or several cost functions which are used to compute the similarity between the input nodes and the reference ones. Finally, an application of this distance measure to the recognition of lower case handwritten English characters is presented.