Line-drawing pattern recognition with attributed graph matching

Abstract

In this thesis, a model-based scheme for recognition of line-drawing patterns is proposed. This scheme represents a line-drawing pattern by an attributed graph (AG) which consists of a set of vertices and segments connecting them. Both to the vertices and segments, various attributes may be attached. When observations as well as models are represented in AG, line-drawing pattern recognition can be formulated as the problem of matching an observed AG($AG_0$) against model AG``s($AG_M$``s) to produce one with the minimum distance. The process of AG matching proceeds with construction of an $AG_0$ from singlepixel-width line-representations of an observed line-drawing. The pose of $AG_0$ is then estimated in terms of translation, rotation and scale with respect to each of $AG_M$``s, based on the fast minimum square error transform we devised. By introducing the concept of control vertex and applying geometrical constraints in an early stage, a small number of candidate $AG_M$``s are selected. In the next step, the correspondence between components of observed AG after normalization ($AG_0^N$) and those of each $AG_M$ is found for the given pose. Finally, distances between $AG_0^N$ and $AG_M$``s are measured, based upon the correspondences, and $AG_0^N$ is classified as the $AG_M$ with the minimum distance. Although the proposed scheme has been found to perform well in most of the test cases, it fails in a few situations where the assumption of control vertices being found reliably is violated. However the experimental results for two classes of line-drawing patterns (circuit symbols in schematic diagrams and seal imprints) reveal that the assumption is quite acceptable, and the proposed scheme is attractive for practical applications.