Improved HMM Based On-line Recognition of Handwritten Characters : 필기체 온라인 인식을 위한 개선된 HMM 알고리즘

다국어 초록 (Multilingual Abstract)

In this study, an improved HMM based recognition model is proposed for on-line English and Korean handwritten characters. The pattern elements of the handwriting model are subcharacter strokes and ligatures. To deal with the problem of handwriting style variations, a modified Hierarchical Clustering approach is introduced to partition different writing styles into severalclasses. For each of the English letters and each primitive grapheme in Korean characters, one HMM that models temporal and spatial variability of handwriting is constructed based on each class. Then the HMMs of Korean graphemes are concatenated to form the Korean character models. The recognition of handwriting characters is implemented by a modified level building algorithm, which incorporates the Korean character combination rules within the efficient network search procedure. Due to the limitation of HMM based method, a post-processing procedure which takes the global and structural features into account is proposed. Experiments showed the proposed recognition system achieved high writer independent recognition rate on unconstrained samples of both English and Korean characters. The comparison with other schemes of HMM-based recognition is also performed to evaluate the system.

다국어 초록 (Multilingual Abstract)

In this study, an improved HMM based recognition model is proposed for on-line English and Korean handwritten characters. The pattern elements of the handwriting model are subcharacter strokes and ligatures. To deal with the problem of handwriting style variations, a modified Hierarchical Clustering approach is introduced to partition different writing styles into severalclasses. For each of the English letters and each primitive grapheme in Korean characters, one HMM that models temporal and spatial variability of handwriting is constructed based on each class. Then the HMMs of Korean graphemes are concatenated to form the Korean character models. The recognition of handwriting characters is implemented by a modified level building algorithm, which incorporates the Korean character combination rules within the efficient network search procedure. Due to the limitation of HMM based method, a post-processing procedure which takes the global and structural features into account is proposed. Experiments showed the proposed recognition system achieved high writer independent recognition rate on unconstrained samples of both English and Korean characters. The comparison with other schemes of HMM-based recognition is also performed to evaluate the system.본 논문은 필기체로 작성된 영문과 한글 글자를 실시간으로 인식할 수 있도록 개선된 HMM 알고리즘을 제안한다. 필기체의 패턴요소는 글자를 구성하는 스트로크와 연결선 이다. 사람마다 다른 필기체는 스타일을 여러 개의 클래스로 구분하여 취급하는 계층적 클러스터링 알고리즘을 사용한다. 영어의 알파벳 글자와 한글의 기본 획에 대하여 클래스가 구축되고, 클래스 각각에 대하여 순간적이고 공간적인 필기체의 변화를 모델링하는 HMM 알고리즘이 적용된다. 그러면 한글의 기본 획에 대응되는 HMM이 순차적으로 연결되어 한글 글자를 인식하게 된다. 필기체 한글의 자모를 모아 글자를 인식하는 과정에서 레벨 빌딩 알고리즘을 변형하여 적용한다. 즉, 한글 자모들이 결합되는 규칙을 모델링한 네트웍을 효과적으로 탐색하는 기능이다. HMM 알고리즘의 태생적 제약을 극복하기 위하여 전역적이고 구조적인 특성을 고려하는 후처리 과정이 추가되었다. 본 논문에 구현된 알고리즘을 자유로운 한글과 영문 필기체 샘플들에 적용하여 실험한 결과 필자에 무관하게 높은 인식율을 얻을 수 있었다. HMM 알고리즘을 기반으로 개발된 다른 방식과 비교함으로써 본 논문이 제시한 필기 인식 시스템의 성능을 평가하였다.

목차 (Table of Contents)

• Chapter One: Introduction = 1
• 1.1 Statement of Research Problem = 1
• 1.2 Research Aim and Objects = 2
• 1.3 Contributions of the study = 3
• 1.4 Outline of the study = 3
• Chapter Two: Background and Related work = 5
• 2.1 Active areas of handwriting recognition = 5
• 2.2 Off-line handwriting recognition = 8
• 2.2.1 Overview of the off-line handwriting recognition system = 8
• 2.2.2 Pre-processing and segmentat = 11
• 2.2.3 Feature extraction = 13
• 2.2.4 Off-line handwriting recognition methods = 15
• 2.3 On-line handwriting recognition = 18
• 2.3.1 Overview of the on-line handwriting recognition system = 18
• 2.3.2 Pre-processing and segmentation = 19
• 2.3.3 Feature extraction and representations = 24
• 2.3.4 On-line handwriting recognition methods = 25
• 2.4 On-line recognition of handwritten Korean characters = 33
• 2.4.1 Recognition units = 33
• 2.4.2 Recognition methods = 34
• 2.5 Hidden Markov Model (HMM) = 37
• 2.5.1 Definition of Hidden Markov Model = 37
• 2.5.2 Three fundamental problems of HMMs = 39
• 2.5.3 Types of HMMs = 40
• 2.5.4 Viterbi Algorithm = 41
• Chapter Three: Developed On-line Handwriting Recognition System = 47
• 3.1Overview of the on-line handwriting recognition system = 47
• 3.2 Preprocessing and feature extraction = 47
• 3.3 Model of handwriting = 48
• 3.3.1 Modeling unit = 49
• 3.3.2 Ligature model = 50
• 3.3.3 Korean character model = 51
• 3.4 Clustering for multiple models design = 55
• 3.4.1 Modified Hierarchical Cluster algorithm = 56
• 3.4.2 Multiple HMMs design = 59
• 3.5 Training of HMMs = 60
• 3.5.1 Baum-Welch re-estimation algorithm = 60
• 3.5.2 Tied states training = 62
• 3.6 Recognition methods = 63
• 3.6.1 Isolated English letter recognition = 63
• 3.6.2 Modified level building algorithm = 64
• 3.7 Post-processing methods = 67
• 3.7.1 Shape verifier = 68
• 3.7.2 Position verifier = 69
• Chapter Four: Experiment and Results = 71
• 4.1 Data Sets = 71
• 4.2 Experimental results = 72
• Chapter Five: Conclusion = 78
• References = 80
• Appendix = 91
• Appendix A: GUI = 91