In this thesis, a data-driven design method of HMM topology for on-line handwriting recognition is proposed. As one of the major research directions for on-line handwriting recognition, HMM is widely used because of the time sequential nature of on-line scripts as well as its capability of modeling shape variability in probabilistic terms. However, there is no simple and well-established method of designing the HMM topology. The choice of HMM topology should be determined based on available traning data and target patterns to be represented. Two design paramenters, i.e., the number of states in an HMM and the number of models for a class, are focused upon.
The design principle of the proposed method is that HMM topology should be constructed from data, reflecting the structure of target patterns. Here, it is assumed that handwriting is composed of straight-line segments. Accordingly, a sample of handwriting can be structurally decomposed and simplified as a sequence of the straight-line segments. Then, according to the design principle, a single state of the left-to-right HMM is assigned to each straight-line segment successively. Thus, the number of the states is determined by the number of the straight-line segments. For training, the initial observation probability distribution for each state can be first estimated from the distribution of straight-line segments, and then the Viterbi path training method is applied.
To handle variations present in a class, the sequences of straight-line segments, which are simplified representations of samples, are clustered to construct multiple models. The resulting multiple models for a single class are combined to form a single HMM architecture, called a multiple parallel-path HMM. When models for a single class contain parts that are similar not only in their shape but also in their structure, corresponding states are tied. The number of parameters in the HMM is hence reduced to a manageable size.
The proposed topology design method was evaluated using on-line Hangul (the Korean script)recognition, since Hangul graphemes are typically structured with straight-line segments. Experiments showed that the proposed method reduced about 17% of character recognition error compared to the previous methods. The proposed method can be applied to other scripts that are mostly composed of straight-line segments, such as Chinese characters.
본 논문에서는 온라인 (on-line) 필기 인식을 위한 데이터 기반의 HMM (은닉 마르코프 모델, hidden Markov model) 설계 방법을 제안한다. 시간에 따라 순차적인 온라인 필기의 특성과 HMM이 갖고 있는 변이 흡수 능력 등에 기인하여, HMM은 온라인 필기 인식의 주요 연구 방향 중의 하나로서 널리 이용되고 있다. 그러나, HMM을 필기 인식에 사용하기 위한 모델 구조의 설계에 관하여는 아직까지 정립된 방법론이 없고, 주로 직관적인 (intuitive) 지식이나 경험적인 (empirical) 지식에 의존하여 수작업으로 설계되어 왔다. 본 논문은 HMM 의 상태 (state)의 개수와 하나의 패턴 클래스 (class)를 위한 모델의 개수 등의 두 가지 설계 항목에 관한 연구이다.
제안하는 HMM 구조 설계의 원리는 모델을 데이터로부터 설계하며, 대상 패턴의 구조를 반영한다는 것이다. 필기 입력은 직선 성분의 조합으로 볼 수 있다. 그러므로, 직선 성분을 필기의 구조적인 단위로 삼아, 필기 입력을 구조적으로 분할하고 단순화하여 직선 성분 열로 표현할 수 있다. HMM 은 각 구조적 단위, 즉 직선 성분에 상태 하나씩을 순차적으로 할당하는 방식으로 구성한다. 결과적으로 HMM의 상태의 개수는 대상 패턴을 구성하는 직선 성분의 개수로부터 결정된다. 각 상태에 대한 해당 직선 성분의 분포로부터 각 상태의 초기 관측 (observation)확률 분포를 구할 수 있으며, 이를 이용하는 Viterbi 경로 훈련방법은 일반적인 HMM 의 훈련방법에 비하여 효과적인 결과를 얻을 수 있다.
각 패턴 클래스에 존재하는 다양한 필기 변형의 처리를 위하여, 훈련 데이터의 각 글씨를 직선 성분 열로 단순화한 후, 이들을 군집화 (clustering) 하여 다중 모델(multiple models)을 구성한다. 하나의 클래스에 대하여 생성된 다중 모델들은 제안하는 '다중 병렬경로 HMM (multiple parallel-path HMM)' 구조를 이용하여 하나의 HMM모델로 결합된다. 이때 하나의 클래스에 대한 다중 모델 중에 단지 글씨의 부분적 모양 뿐만이 아니라 구조적으로 동일한 부분이 있는 경우에는, 해당 상태의 파라미터 (parameter) 를 공유 (tying) 한다. 그 결과, HMM 의 파라미터의 개수를 줄이고 모델의 일반화를 유도한다.
제안하는 HMM 구조 설계 방법은 온라인 한글 인식에 적용되었다. 이는 한글의 자모가 전형적으로 직선 성분의 조합으로 구성되어 있기 때문이다. 한글 글자에 대한 인식 실험의 결과, 제안하는 구조 설계 방법은 기존의 설계 방법들과 비교하여 약 17%의 오류를 줄일 수 있었다. 제안하는 방법은 한자와 같이 주로 직선 성분으로 구성된 글자에 쉽게 적용될 수 있을 것이다.
