Unconstrained handwriting is especially difficult to recognize because of its variability and ambiguity. It is, however, not considered impossible if we can use various sources of knowledge. For example, a word is written letter by letter in a strict order.
Viewing a handwritten word as an alternating sequence of characters and ligatures, we develop a circularly interconnected network of hidden Markov models that models the variabilities of handwritten English words of any length. In this network the task of recognition is defined by the process of finding the most probable path for a given input. The search is based on the Viterbi algorithm, which is a dynamic programming technique, that maximizes the alignment of a given input to all possible circular paths. The recognizer organized in this way carries out recognition and segmentation simultaneously. During the path search, we also consult a lexicon so that we can direct the search to a correct path.
In the path search with the lexicon lookup, the interpretation of the initial part of a handwriting affects the interpretation of the following part. This implies that the search result depends on the search direction. It is very hard to decide the best search direction for a given input handwriting. This thesis analyzes the issue of directional sensitivity, and then proposes a dynamic backtracking technique called candidate refilling. Candidate refilling is a solution that remedies the problem of blocked path by backtracking dynamically to generate partial path candidates and replace the illegal candidates. Using this technique, the experimental recognizer is shown to achieve recognition rate over 99.42% of the correctness of the optimal recognizer efficiently. The advantage of candidate refilling method is more remarkable when the beginning parts of sample is written ambiguous.
The complexity of search space is another difficulty. Since every point in a handwriting is potential segmentation point, we have to consider a huge number of possible segmentations in the path search. So we introduce two methods of stroke type analysis and velocity profile analysis. They reduce the number of potential segmentation points, which then reduces task of the candidate maintenance. In the experiment, the reduction rate of 45.95% was obtained without degradation of recognition rate.
영어 단어의 제약 없는 온라인 필기는 내재된 변형과 해석의 모호성으로 인하여 인식이 매우 어렵다. 그러나 여러 가지 종류의 지식을 사용함으로써 문제의 난이도를 줄일 수 있다. 예를 들면 단어 내에서 문자가 좌측에서 우측으로 차례로 필기 된다는 사실을 이용하면 많은 잘못된 해석의 가능성을 줄일 수 있다.
본 논문에서는 필기 문자에 포함된 많은 변형을 해결하기 위하여 은닉 마르코프 모델을 사용하였다. 또한 필기 단어를 문자와 연결획이 교대로 나타나는 연속체로 보고 이를 인식하기 위해 순환 구조로 연결된 은닉 마르코프 모델의 네트웍을 사용하였다. 인식의 문제는 이 네트웍 상에서 주어진 필기 입력에 대해 확률이 가장 높은 경로를 찾는 것으로 정의된다. 경로 탐색은 동적 프로그래밍 기법인 Viterbi 알고리즘을 기반으로 한다. 이 알고리즘은 주어진 입력과 가능한 모든 경로 간의 최적 정합을 찾아낸다. 이 과정에서 인식기는 인식과 문자 분리를 동시에 수행한다. 또한 경로 탐색 과정에서 정확한 경로를 찾도록 유도하기 위해 단어 사전을 참조한다.
단어 사전을 참조하는 경로 탐색에서는 필기 입력의 앞부분에 대한 해석의 결과가 뒷부분에 대한 해석에 영향을 미친다. 이것은 탐색의 방향 즉 어디에서 탐색이 시작되어 어디로 진행되는가가 인식 결과를 좌우한다는 것을 의미한다. 그러나 주어진 입력에 대해 가장 좋은 탐색 방향을 결정하는 것은 매우 어렵다. 본 논문에서는 인식 결과가 탐색 방향에 민감하게 영향을 받는 현상을 분석하였으며, 이를 극복하기 위해 후보 보충 방법이라는 동적인 역추적 기법을 제안하였다. 후보 보충 방법은 경로가 단절되는 상황을 보상하기 위한 해결책으로 동적인 역추적 기법에 의해 새로운 후보를 만들어 불합리한 경로를 대체하는 방법이다. 실험에서는 이 방법을 사용하여 이상적인 탐색 방법이 갖을 수 있는 추정 한계 인식률에 99.42% 이상 근접하는 인식률을 효율적으로 얻을 수 있었다. 후보 보충 방법은 특히 앞부분이 모호하게 필기된 입력에 대해 두드러진 성능향상을 보였다.
필기 인식에서 탐색 공간의 복잡도는 해결해야 할 또 하나의 어려운 문제이다. 필기 데이타를 이루는 모든 점들이 잠재적으로 문자의 분리점이 될 수 있으므로 경로 탐색에서 엄청나게 많은 문자 분할 방법을 고려해야 한다. 이러한 복잡도를 덜기 위해 본 논문에서는 획의 유형 분석과 필기 속도의 변화 유형 분석 방법을 도입하였다. 이 방법들은 문자 분리점이 될 수 있는 점의 범위를 제한함으로써 결국 경로 탐색 과정의 부담을 줄여준다. 실험에서 문자 분리점의 후보로 전체에서 45.95%의 점들을 인식률의 저하 없이 줄일 수 있었다.
