Efficient Matching of Dynamically Changing Graphs
Horst Bunke, T. Glauser, Thanh Ha Tran · Series in machine perception and artificial intelligence · 1992
Subgraph isomorphism detection is a fundamental technique in computer vision. In this paper we propose a new subgraph matching procedure that is particularly useful if the number of prototype graphs is large, and if the graph representation of the image to be interpreted is dynamically changing. Our procedure is derived from the RETE-matching algorithm that has been developed for forward chaining rule-based systems [1]. We introduce our new method and discuss its computational complexity. It will be shown that the computational complexity of the proposed approach is not better than that of a naive, straigth-forward solution to the problem. In the best case, however, a significant speedup can be achieved. Finally, we show experimental results which confirm our theoretical complexity analysis. 1 Introduction Graph matching is a fundamental technique in computer vision and image understanding. In many vision systems a graph extracted from an image is matched to stored model gra...