A new attributed relational graph matching algorithm using the nested structure of earth mover´s distance

In general, object features can be represented as the nodes in attributed relational graph (ARG) with the connecting edges implying their relations. Therefore, the ARG matching plays a significant role in object recognition. Actually, the ARG matching can be implemented as a 2-step procedure, composed of constructing a distance matrix and establishing the correspondence based on the distance matrix, which seems to be similar to the point matching procedure. In this paper, we present a new ARG matching algorithm using the nested structure of earth mover´s distance (EMD). More specifically, the nested structure of the EMD consists of inner EMD and outer EMD: The inner EMD reflects the difference of both nodes and edges between a pair of nodes in two ARG´s in a perceptual manner, and the outer EMD establishes the correspondence between nodes in the two ARG´s in a natural way. In order to demonstrate the robustness of the proposed algorithm against noise, we have conducted synthetic experiments for fully connected and undirected ARG´s.