Using graph distance in object recognition

ABSTRACT

In this paper the concept of the distance between graphs is applied to the problem of recognizing objects. An unknown object is represented by a graph H and from the data base of possible solutions {G1, …, Gn} (also graphs) we select the graph Gi for which the distance to H is the smallest. The graph Gi is the recognition of H. The distance between graphs is defined in terms of edge rotation and deletion. It is shown that this distance defines a metric on the space of all graphs. The bounds for distance between two graphs are given in terms of their sizes and the size of their greatest common subgraph. It is proved that finding a distance between two graphs is an NP-complete problem even for planar graphs. An algorithm based on exhaustive search utilizing the linear algorithm by Hopcroft and Wong for recognizing isomorphism of planar graphs with some stopping criteria to maintain polynomial complexity, is possible.

REFERENCES

• 1: S. Ansaldi, L. De Floriani and B. Falcidieno, Edge - Face Representation of Solid Objects, IEEE, 164--169 (1984).
• 2: H.G. Barrow and R.M. Burstall, Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques. Information Processing Letters 4, 83 - 84 (1976).
• 3: Paul J. Besl , Ramesh C. Jain, Three-dimensional object recognition, ACM Computing Surveys (CSUR), v.17 n.1, p.75-145, March 1985 [doi>10.1145/4078.4081]
• 4: Gary Chartrand , Linda Lesniak, Graphs & digraphs (2nd ed.), Wadsworth Publ. Co., Belmont, CA, 1986
• 5: G. Chartrand, F. Saba and H.B. Zou, Edge Rotation and Distance Between Graphs. Cas. Pest. Mat. 110, 87 - 91 (1985).
• 6: T. Fan, G. Medioni and R. Nevatia, 3-D Object Recognition using Surface Descriptions. Proceedings of DARPA image Understanding Workshop, Cambridge, 383-397 (1988)
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 9: G. Maderleckner and O. Jeppsson, Representation, Classification and Modelling of Graphs for Efficient Pattern Recognition in Line lmages. IEEE, 678- 680 (1988).
• 10: H. Yang and LTai, On Isomorphism of Attributed Relational Graphs for Pattern Analysis and a New Branch Algorithm. IEEE, 957 -959 (1988).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Verification