A novel isomorphism based on nearest neighbours for efficient graph matching algorithm

Abstract

For many applications in the fields of robotics, satellite imagery and medical imaging demanding real-time solutions, recognizing the crucial parts or structures in the given images continues to attract more attention. Tims, the paramount factor in these computer vision related fields is matching the objects in the images. Often graphs are used to represent the objects. It is well-known that graph matching is NT-complete problem in general. To accomplish the need of real-time solutions, various lower order complexity algorithms are developed with specific conditions. Here, a novel Node Neighbour Isomorphism (NNI) is introduced which efficiently matches two graphs in O(n/sup 4/) where n is the number of vertices in both the graphs which can be weighted and attributed. Using tliis NNI, the vertices of the graphs are grouped mutually exclusively. Instead of matching all the vertices, only the relevant NNI vertices alone are matched paving way for ample efficiency by reducing the number of matching operations. The algorithm is implemented on Sun Ultra 10 and results of crucial examples and random graphs are also tabled. The run-time performance and novality of the algorithm exemplifies the efficiency of the algorithm which also exhibits parallelism. The algorithm is compared with standard methods and requires the minimal time for matching the graphs.