In this thesis, an HMM-based stochastic framework is proposed for the problem of on-line cursive script modeling. Basically, we use HMMs for modeling letters, the most natural unit chosen from the consideration of modeling difficulty and trainability. Then ligatures, the primary source of shape variability, are considered to include pen-up moves as well as pen-down drags. Clustered into a number of sets based on their position and left, right context, they are modeled as separate entities which in turn enable us to model both discrete and cursive unconstrained script.
By concatenation of letter and ligature HMMs according to writing order and character (or word) composition rules, we are lead to a network model for on-line handwriting. When the design principle is extended to exploiting the sentential or multingual knowledge or more, a similar construction of HMM network is realized over a consistent framework.
Given the network, the stochastic inference over the model is formulated into that of finding the most likely path. A recognizer is realized if the search is made for the best path given an observation sequence. A script generator is realized if the search is made for the best observation sequence from a given path. Finally, when the search is performed over a static handwriting image for the best sequence of observations and states, we can recover the pen trajectory that can aid or even serve off-line static image recognition. The search algorithms we have presented for those applications are based on the same technique of dynamic programming, and they are efficient and practical for real time applications.
The capability of traditional HMM is often questioned because of its incorrect state duration modeling. As this can cause some problem when the the duration behavior is directly concerned, a new type of HMM called nonstationary hidden Markov model (NSHMM) is proposed in theoretical terms as a generalization - in descriptive power - of standard HMM; it is shown highly robust in discrimination and more correct in state duration behavior.
A series of experiments confirmed the viability of the overall modeling framework: high performance with up to 93.3 % correct recognition for natural Hangul samples, higher than comparative systems with no ligature or no network basis; highly natural script patterns generated by NSHMM; reasonable pen trajectories uncovered over several static test images.
본 논문에서는 온라인 필기를 모델링하는 문제에 은닉 마르코프 모형(HMM)을 기초로 한 통계적 방법을 제안하였다. 기본적으로 자소 또는 알파베트 단위의 필기 모형화에서 출발하여, 자소 또는 알파베트 모형의 순차적 연결로 글자 또는 단어 등 구조적 필기 패턴 모형화를 시도하였다. 즉, 필기의 최소 기본 단위를 자소 또는 알파베트로 보고 이들 각각에 대하여 HMM을 하나씩 설계하며, 자소와 자소 사이에 나타나는 특징적 패턴을 연결획으로 분리하여 별도의 연결획 HMM으로 모형화 하였다.
한글의 연결획은 앞 자소의 끝, 뒷 자소의 시작 부분의 연결 방향, 위치 등에 따라 적절한 갯수의 연결획 타입으로 분류하였다. 각 타입을 표현하는 연결획 HMM은 방향을 중요한 특징으로 간주하고, pen-down 연결과 pen-up 이동 연결을 동시에 모형화 한다. 이러한 연결획 모형화로써 또박또박 쓴 글씨, 획를 이어 흘려쓴 글씨 등을 구별없이 동시에 수용이 가능하다.
자소와 연결획의 HMM이 구성되면 제자 원리, 단어의 길이 등의 언어 조건에 따라 HMM의 접속 스트링으로 글자 모델을 구성한다. 이때, 스트링 상의 같은 위치 같은 자소는 공유를 함으로써 모델의 중복을 최소화한 축약된 네트워크 구조의 모델을 설계할 수 있다. 한글 필기 모델(BongNet)은 이와 같은 설계 원리에 따라 구성된 온라인 필기 모델이다. 이 네트워크 모델의 각 경로는 유일한 하나의 글자에 대응된다.
따라서 인식은 주어진 입력에 대해서 적절한(하나의 완전한 경로라는) 확률적 기준에 따라 최고 확률의 경로를 찾아 내는 문제로 정의된다. 이러한 경로 탐색 문제는 동적 프로그래밍(DP) 기법에 의한 효율적인 Viterbi 알고리즘 등으로 해결이 가능하다. 입력이 코드의 열로 주어졌을 때, 네트워크의 모든 가능한 경로에 대해서 최적의 input-path 배열(mappin)을 구함으로써 필기 인식과 동시에 자소의 경계도 알아 낼 수 있다.
한편, 앞에서 설계한 필기 모델을 응용하여 새로운 두가지의 문제, 즉 사람들의 평균적 필기 패턴 생성과 스캐너에서 받은 오프라인 영상에서 펜 궤적을 추정하는 문제 각각에 대하여 새로운 해결 방법을 제시하였다. 인식에 사용되었던 DP 알고리즘의 기본 원리를 그대로 응용하여 필기 생성의 경우에는 네트워크의 경로에서 관찰 가능한 최적의 코드열을, 궤적 추정 문제에서는 네트워크 경로와 최적 대응되는 흑백 화소의 일차원적 궤적을 그 출력으로 한다.
HMM은 모델링 능력은 우수하지만 기본적으로 시불변 파라미터로 된 모델이고, 또 일차 마르코프 가정으로 극히 단순화한 모델이기 때문에 실제 응용에 있어서 정확한 동작을 보이지 않는다. 특히 마르코프프 체인에서 어떤 상태에 '체류'(state duration)하는 시간의 분포가 지수 함수 형태로 나타나게 되어 실제 물리적 신호에 나타나는 분포 패턴과는 큰 차이가 난다. 이 점을 해결하고 인식 문제에 적용했을 때 모델간의 분별력이 뛰어난 새로운 형태의 모형(NonStationary HMM 또는 NSHMM)을 제안하였다. HMM 의 상태 전이 행렬을 상태 체류 시간의 함수로 정의하고, 이에 따라 NSHMM을 평가 및 파라미터 추정 식을 유도하였다.
요약하면, HMM을 이용한 필기 모델 설계 방법론을 기반으로 하여, 하나의 필기 모델 위에서 동일한 통계적 추론에 따라 필기 인식, 필기 생성, 그리고 오프라인 영상에서 펜 궤적 추정을 해낼 수 있는 통합된 틀이 가능함을 보였다.
