A random graph approach to pattern recognition
Manlai You · 1983
The use of attributed graph and random graph as a means of combining the syntactic and the statistical approaches toward pattern recognition is proposed. The attributed graph is an effective way of describing relational structures. Further, the random graph encompasses both the structural and the probabilistic aspects of the relational patterns. A hierarchical graph synthesis algorithm has been developed to synthesize a random graph for characterizing an ensemble (or class) of attributed graphs. This algorithm resembles the learning process in conventional pattern recognition approaches. Graph distance measures are defined and used as a criterion for combining graphs in the synthesis process. In order to obtain computational efficacy, a branch-and-bound searching algorithm adopting a heuristic function for cost estimation has been proposed for the identification of graph morphisms and distances. Finally, recognition of an unknown graph pattern can be accomplished by matching it with the random graphs of different classes and then assigning it to the nearest class or to the class with the highest likelihood.