In this thesis, we present an efficient algorithm for image matching based on linear features of images. Two points are emphasized in the system; one is the development of line merging rules for simplifying line models of images and the other is heuristic search for efficient matching. With these line merging rules, lines are merged under some conditions or short isolated lines are deleted.
Linear features in an image are represented by a relation graph. In the graph, nodes represent lines and arcs represent the relations between lines. Matching two images is accomplished by comparing corresponding relation graphs. Formulating the graph matching as a state-space problem, we applied the heuristic search technique. It is shown that line merging and efficient graph matching is critical in the practical use of the line-based image matching approach.