Handwritten Hangul (Korean) character recognition is one of the most challenging problems in pattern recognition which endows computers with human cognitive capabilities. Since a Hangul character consists of several graphemes, the difficulty of Hangul character recognition can be compared to that of English word recognition, which is also known to be a difficult task. In Hangul, furthermore, the existence of many character classes of similar shape and touching between graphemes make the recognition more difficult. In particular, the touching between graphemes varies because Hangul graphemes are composed on a two-dimensional space, whereas Roman alphabets are composed in left-to-right order. These characteristics also make the recognition intractable. A great deal of computation is needed to discriminate the confusing character classes and to consider all possible grapheme combinations. In this thesis, two concepts, hierarchical relationship modeling and candidate pruning, are proposed to tackle those problems in handwritten Hangul character recognition.
In structural character recognition, a character is usually viewed as a set of strokes and the spatial relationships between them. Therefore, strokes and their relationships should be properly modeled for effective character representation. For this purpose, we propose a modeling scheme by which strokes as well as relationships are represented by utilizing the hierarchical characteristics of target characters. A character is stochastically defined by a multivariate random variable over the components and its probability distribution is learned from a training data set. To overcome difficulties of the learning due to the curse of dimensionality, the probability distribution is approximated by a set of lower-order probability distributions by applying the idea of relationship decomposition recursively to components and subcomponents. Based on the hierarchical relationship representation, Hangul character recognition is formulated as hierarchical character recognition in a completely probabilistic framework.
To alleviate the high computational complexity associated with hierarchical Hangul character recognition, we present a method to integrate top-down processes into the hierarchical recognition process. The hierarchical recognition process consists of primitive stroke extraction, grapheme candidate generation, and character candidate generation. Noting that the complexity of the process comes mainly from the bottom-up characteristic of the candidate generation, we devise some top-down information available in Hangul characters and utilize them to efficiently generate character candidates and prune invalid candidates during the candidate generation.
Based on the stochastic relationship modeling and candidate pruning, a handwritten Hangul character recognition system was developed. Recognition experiments conducted on a public database, KU-1, show the effectiveness and efficiency of the developed system. As a result, errors in the recognition rate were reduced by 30.9% in comparison to the most successful system ever reported and 40.6% of speed improvement was achieved by integrating the devised top-down processes into a pure bottom-up matching based system.
필기한글인식은 인간의 인지능력을 컴퓨터에 부여하는 패턴인식 분야에서도 도전할 만한 문제 중의 하나이다. 한글문자가 자모들의 조합으로 이루어진다는 점에서 필기한글인식의 복잡도는 어려운 문제로 알려져 있는 영어단어인식과 비교될 수 있다. 더욱이 한글인식의 경우에는 유사한 형태를 갖는 다수의 문자들의 존재와 자모들 사이의 다양한 형태의 접촉으로 인하여 그 복잡도가 더욱 증가하게 된다. 특히, 이차원 공간에서 자모들이 결합되므로, 알파벳들이 일차원 공간에서 조합되는 영어단어인식에 비하여 자모들 사이의 접촉 형태가 다양하게 나타난다. 이러한 한글문자의 성격은 인식과정의 시간 복잡도 또한 증가시킨다. 즉, 유사한 문자를 구분하고 모든 가능한 자모들의 조합을 고려하는 데에는 높은 시간 복잡도가 요구된다. 이 논문에서는 필기한글인식의 이러한 문제점들을 해결하기 위한 방법으로 계층적 관계 모델링과 효율적인 후보제거 기법을 제안한다.
구조적 문자인식에서 문자는 일반적으로 획들과 획들 사이의 위치관계로서 표현된다. 따라서 효과적인 문자표현을 위해서는 획들과 획들 사이의 관계가 적절히 모델링되어야 한다. 이러한 목적으로 본 논문에서는 문자의 계층적 특성을 이용하여 획과 획들 사이의 관계를 표현하는 모델링 방법을 제안한다. 제안한 방법에서 문자는 문자를 구성하는 컴포넌트들의 다변수 확률변수로 정의되며, 그 확률분포는 학습 데이터로부터 학습된다. 이러한 확률을 이용한 문자표현 방식에서 문자의 확률분포는 일반적으로 높은 차수를 갖게 되며, 따라서 이 방식은 curse of dimensionality로 인한 확률분포 학습의 문제를 내포하고 있다. 이 문제를 해결하기 위하여 본 논문에서는 관계분해 (relationship decomposition)의 아이디어를 문자의 구성요소들에 재귀적으로 적용함으로서 문자의 확률분포를 낮은 차수의 확률분포들로 근사화한다. 제안한 계층적 관계 표현 방법에 기반하여, 한글인식 문제는 확률적인 틀에서 계층적 문자인식으로 체계화될 수 있다.
계층적 문자인식의 높은 시간 복잡도 문제를 해결하기 위해서 본 논문에서는 계층적 문자인식 과정에 하향식 정보를 결합하는 방법을 제안한다. 계층적 문자인식 과정은 기본획 추출, 자모후보 생성과정, 그리고 문자후보 생성과정의 세 단계로 구성된다. 계층적 문자인식의 복잡도가 후보생성 과정의 상향식 특성에 기인한다는 사실로부터, 제안한 방법은 한글문자에 적용가능한 하향식 정보들을 이용하여 효율적으로 문자후보를 생성하고 후보생성 과정에서 부적절한 후보들을 제거한다.
제안한 계층적 관계 모델링과 후보제거 기법에 기반하여 필기한글 인식 시스템을 개발하였다. 필기한글 데이터베이스 KU-1에 수행된 인식실험의 결과는 개발된 시스템이 필기한글인식에 효과적이며 효율적임을 보였다. 그 결과로서 기존에 발표된 시스템에 비하여 30.9%의 인식률 향상을 가져 왔으며, 상향식 매칭에만 의존한 시스템에 비하여 40.6%의 속도 향상을 얻을 수 있었다.
