In this thesis, a hierarchical random graph (HRG), which is a stochastic graph for handwritten character modeling, is proposed. In addition, based on the HRG, a handwritten Hangul recognition system also has been developed. In the HRG, the bottom layer is constructed with chain graphs to describe various strokes, while the next upper layers are constructed with random graphs [1] to model spatial and structural relationships between strokes and between sub-characters. Since the proposed HRG is a stochastic model, the recognition can be formulated into the problem that chooses a model producing maximum probability given an input data. In this context, matching score is obtained not by any heuristic similarity function, but by the observation probability calculated by multiplying observation probabilities of features of an input character.
To estimate the model parameters of the HRG, we apply embedded training, which estimates all the models in the HRG at the same time so as to avoid manual segmentation of an input character. As the criteria of parameter estimation in embedded training, we adopt maximum likelihood estimation (MLE) and maximum mutual information estimation (MMIE), which are representative methods to estimate the model parameters in statistical approaches, especially having been used for the parameter estimation of hidden Markov models (HMM). The criteria are examined in the information theoretic view, and a new criterion based on minimum entropy estimation (MEE) is proposed. Since it is not necessary to assume that the parameter space of models is correct, MEE will perform not less than any other estimation methods under the condition that the training data size is large enough. Some experiments with handwritten Hangul characters show the performance of the three estimation methods. Besides, many issues for automatic parameter estimation of the HRG are discussed and implemented, including exclusive training, parameter smoothing, and initial parameter estimates.
As an application of the HRG, the KAIST-HR, a handwritten Hangul recognition system, has been developed. The recognition process of the KAIST-HR begins with converting an input character image into an attributed graph through the preprocessing and the graph representation. Matching between an attributed graph and the hierarchical graph model is performed bottom-up. To avoid the errors of incorrect stroke grouping, which would be generated by making a hierarchy of an attributed graph before recognition, a hierarchical representation of an attributed graph is not given until the recognition ends. This so-called internal segmentation approach can reduce the errors caused by pre-construction of the hierarchy of input graphs. Many attempts to improve the KAIST-HR are also introduced such as 2D-lattice representation, which enables to combine graphemes of Hangul into syllables efficiently, and grapheme-pair models, which are devised to improve the modeling power. Series of experiments conducted with unconstrained handwritten Hangul characters have shown that the usefulness and effectiveness of the proposed HRG.
본 논문에서는 필기 문자를 모델링하기 위한 계층적 랜덤 그래프 표현 방법과 학습 방법을 제안하였다. 또한, 제안된 모델을 이용하여 필기 한글 인식 시스템을 개발하였다. 제안된 계층적 랜덤그래프에서 최하위 계층은 다양한 획을 표현하기 위해 체인그래프로 구성되고, 그 위 계층들은 획이나 부분 문자들간의 구조적, 공간적 위치관계를 모델링하기 위해서 랜덤 그래프로 구성된다. 제안된 모델은 통계적 모델이기 때문에 이를 이용하면 문자인식은 주어진 입력영상에 대해 최고의 확률을 갖는 모델을 선택하는 문제로 정의된다. 이때 모델과 입력의 매칭값은 유사도 측정함수 대신 입력문자영상에 대한 관측 확률로부터 얻어진다.
제안된 모델의 파라미터를 추정하기 위해서 embedded 학습방법을 적용하였다. 이 방법은 계층모델에 포함된 모든 모델 파라미터를 동시에 학습하기 때문에 입력 문자를 수작업으로 분할할 필요가 없다는 장점이 있다. Embedded학습시 파라미터 추정 방법으로서 최대우도 추정법(Maximum Likelihood Estimation)과 최대상호정보 추정법(Maximum Mutual Information Estimation)이 사용되었다. 이것은 통계적 접근방법에서 모델의 파라미터를 추정하는 대표적 방법으로 특히 hidden Markov models (HMM)의 파라미터 추정에 주로 응용되어왔다. 이러한 추정방법을 정보이론의 관점에서 살펴본 후, 최소엔트로피 추정법(Minimum Entropy Estimation)에 기반한 새로운 추정척도를 제안하였다. MEE는 MLE나 MMIE와 달리 모델에 관한 아무런 가정을 하지 않기 때문에 학습데이터의 양이 충분하다는 조건 하에서 다른 어느 추정방법 못지않은 성능을 보인다. 이외에 exclusive 학습, 파라미터 평활화(parameter smoothing), 초기파라미터 추정 등, 계층랜덤그래프의 파라미터 자동학습을 위해 필요한 많은 문제들이 연구되었다.
제안된 모델의 효용성을 입증하기 위해 계층랜덤그래프를 이용하여 필기 한글 인식 시스템 KAIST-HR을 개발하였다. KAIST-HR에서는 입력문자영상을 인식하기 위해서 먼저 속성그래프로 표현한 후 계층그래프 모델과 매칭한다. 속성그래프와 계층그래프 모델과의 매칭은 상향식 매칭으로 진행된다. 매칭할 때 속성그래프의 계층구조를 미리 결정함으로써 발생할 수 있는 오류를 방지하기 위해서 속성그래프의 계층구조는 매칭이 다 끝난 후에 매칭 결과에 따라 결정하도록 하였다. 이외에도 2D-lattice 표현 방법이나 자소쌍 모델 등이 KAIST-HR의 성능을 높이기 위해서 도입되었다.
KAIST-HR의 성능 평가를 위해서 필기 한글 데이터를 이용한 일련의 실험을 수행한 결과 제안된 모델이 유용하고 효과적임을 보였다. 또한, 기타 다양한 실험을 통하여 제안된 모델이 필기 문자의 특성을 효과적으로 표현할 수 있기 때문에 필기 한글 뿐 아니라 필기 숫자 인식이나 혼용 문자 인식, 단어 인식 등에 확장 가능성이 있음을 보였다.
