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 single-pixel-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.
본 논문에서는 선도형(line-drawing) 패턴을 인식하기 위한 모델 기반 기법(model-based scheme)을 제안하였다. 선도형 패턴은 속성 그래프(AG: attributed graph)로 표현되는데 하나의 AG는 버텍스(vertex)와 세그먼트(segment)의 집합으로 구성되고, 각 버텍스와 세그먼트에는 다양한 속성이 부여될 수 있다. 이와같이 모델 및 관찰된 선도형 패턴을 AG로 표현하게 되면, 선도형 패턴 인식의 문제는 관찰된 AG($AG_O$)를 각각의 모델 AG($AG_M$)와 정합하여 최소의 거리(distance)를 갖는 $AG_M$을 선택하는 AG 정합(matching) 문제로 귀착된다.
AG를 정합하는 과정은 다음과 같다. 첫째, 관찰된 선도형 패턴 영상을 단일 두께의 선표현(single-pixel-width line representations)으로 변환하고 이로부터 $AG_O$를 구성한다. 둘째, 빠른 최소 제곱 오류 변환(minimum square error transform)을 이용하여 각 $AG_M$에 대해서 $AG_O$의 위치 형태(pose)를 이동(translation), 회전(rotation) 및 축소 및 확대(scale)의 매개변수로 추정한다. 이 단계에서, 제어(control) 버텍스의 개념을 도입하였으며, 초기 단계에서 기하학적 제약을 가함으로써 적은 수의 후보 $AG_M$들을 선택할 수 있다. 세째, 표준 위치로 변환된 관찰된 AG($AG_O^N$)와 각 $AG_M$의 버텍스 또는 세그먼트 사이의 대응을 결정한다. 마지막으로 이 대응을 이용하여 $AG_O^N$과 각 $AG_M$ 사이의 거리를 계산하고, $AG_O^N$은 최소의 거리를 갖는 $AG_M$으로 분류한다.
제안된 기법의 효용성을 증명하기 위하여 손으로 그린 공학 도면 기호의 인식과 인장 자동 검증에 대한 실험 결과가 제시되었다. 제안된 기법은 대부분의 경우에 잘 동작하였다. 실패할 경우는 계산량을 줄이기 위해서 관찰된 기호로부터 제어 버텍스가 안전하게 구해질 수 있다고 한 논문에서의 가정이 적합하지 않은 경우였다. 그러나 다양한 실험 및 분석을 통하여, 그러한 가정이 무난하며 제안된 기법이 실제 문제에 잘 적용될 수 있음을 알 수 있었다.
