Recovery of Drawing Order from Multi-stroke Handwritten Images Based on Graph Models and Ambiguous Zone Analysis = 그래프 모델과 Ambiguous Zone Analysis에 기반한 Multi-stroke 필기체 궤적복원

다국어 초록 (Multilingual Abstract)

Recovery of drawing order of strokes in a handwritten image can be seen as searching the smoothest path for each stroke on an undirected graph that is constructed from the skeleton of the handwritten image. However, this requires the correction of separating strokes, and detecting starting points at first. Moreover, ambiguousness at junction points (ambiguous zones) increases the complexity of finding these paths. In order to resolve these issues, an effective four-stage approach that can simultaneously detect the points to separate strokes and find the smoothest path for each stroke is proposed. In the first stage, a skeleton graph is built from the thinned image of handwriting. Adjustments that include merging nodes of spurious edges and separating touching characters and crossing strokes in some cases are performed. The smoothness of two adjacent edges that is used to search the smoothest path is estimated by a function of the angle between those edges at their junction point. The skeleton graph may be divided into many subgraphs as the result of this stage, and then each of those is iteratively input into next stages. In the second stage, the smoothest path is searched on the line graph of each subgraph. Some potential starting edges are proposed. For each of those, a smoothest path is obtained and the best one is chosen. Touches and crossings at ambiguous zones are detected and the smoothness values are adjusted to improve accuracy of the recovery. Then, the smoothest path is separated to many strokes in the third stage by using the curvature of edges, the un-smoothness between edges and the appearance of double-traced edges. Finally, in the fourth stage, pixel sequences of strokes are extracted and ordered by using rules of handwriting. In order to validate the effectiveness of the proposed method, experiments are performed on two datasets. The first dataset includes 2180 images of single-stroke handwriting. The second includes 1640 images of multi-stroke handwriting. Root Means Square Error (RMSE) and Dynamic Time Warping (DTW) are applied to measure the error between the recovered drawing order and ground truth. Results of the proposed method show impressive accuracy and are compared to two recent methods.

국문 초록 (Abstract)

필기체 궤적복원은 필기체의 골격(skeleton)으로 부터 구성된 무방향 그래프의 각 획의 smoothest path를 찾는 것으로 볼 수 있다. 그러나 필기체 궤적복원은 처음에 분리된 획들의 교정과 시작점을 검출하는 것을 요구한다. 더욱이 교차점(junction point)에서의 애매함은 smoothest path를 찾는 것을 어렵게 한다. 본 논문에서는 이러한 문제를 해결하기 위해, 획들을 분리하기 위한 점을 검출하고 각 획의 smoothest path를 찾는 효과적인 네 단계 방법을 제안한다. 첫 번째 단계로, 세선화된(thinned) 필기체 이미지로 골격 그래프를 만든다. 그리고 spurious edges의 노드 통합, 접촉된 문자의 분리(separating touching characters), 교차된 획의 분리를 수행한다. 두 개의 인접 엣지들의 smoothness는 인접 엣지들 사이의 각도에 대한 함수로 추정한다. 골격 그래프는 많은 서브 그래프들로 나눠지고, 그것들은 다음단계에 반복적으로 사용된다. 두 번째 단계로, smoothest path를 각 서브그래프의 line graph에서 찾는다. 먼저, 필기체 규칙에 의해 시작하는 엣지 후보군을 찾는다. 엣지 후보군 각각에 대해 smoothest path를 구하고 최선의 것을 선택한다. 그리고 애매한 영역(ambiguous zones)에서 접촉?교차하는 부분을 검출하고, 복원의 정확률을 높히기 위해 smoothness values를 보정한다. 세 번째 단계에서 smoothest path는 엣지들의 곡률, 엣지와 double-traced 엣지들 사이의 un-smoothness를 사용하여 많은 획들로 나눈다. 마지막으로, 네 번째 단계에서 필기 규칙을 사용함에 따라 획들의 픽셀 순서가 추출되고 정렬된다. 제안된 방법의 효과를 입증하기 위해 두 가지 데이터셋에 대해 실험이 수행 되었다. 첫번째 데이터셋은 2180개의 single-stroke 필기체를 포함한다. 두 번째는 1640개의 multi-stroke 필기체를 포함한다. 복원된 궤적과 ground truth 사이의 에러를 측정하기 위해 제곱근 편차(RMSE)와 DTW(Dynamic Time Warping)를 사용하였다. 본 논문에서 제안된 방법은 최근의 다른 두 방법들과 비교해서 인상적인 정확률을 보여주고 있다.

목차 (Table of Contents)

• 1. INTRODUCTION 1
• 1.1 Overview 1
• 1.2 Related works and proposed method 1
• 2. BACKGROUND 4
• 2.1 Skeleton and Graph 4
• 2.1.1 Skeleton 4
• 2.1.2 Skeleton Graph 5
• 2.2 Terminal Node and Terminal Edge 5
• 2.3 Real-segments and Spurious-segments 6
• 2.4 Bridges 6
• 2.5 Line Graph 7
• 2.6 Complete Graph 8
• 2.7 Hamiltonian Path, Hamiltonian Cycle and pre-Hamiltonian Path 8
• 2.8 Dynamic Time Warping for Time Series Matching 9
• 2.9 Greedy Algorithm 11
• 2.10 Dijkstras Algorithm 12
• 3. PROPOSED METHOD 14
• 3.1 Building Skeleton Graph 15
• 3.1.1 Skeletonization 15
• 3.1.2 Extracting nodes and edges 15
• 3.1.3 Detecting Spurious Segments, k-Bridges and Merging Nodes 15
• 3.1.4 Smoothness Estimation 18
• 3.1.5 Separating Touching Characters and Crossing Strokes 19
• 3.2 Searching Smoothest Path 20
• 3.2.1 Detecting touches and crossings 20
• 3.2.2 Choosing Potential Starting Edges 23
• 3.2.3 Searching Minimum pre-Hamiltonian Path 24
• 3.3 Separating Smoothest Path 26
• 3.3.1 Remove Redundant Edges 26
• 3.3.2 Detecting Straight and Curved Edges 28
• 3.3.3 Separating Strokes 28
• 3.4 Extracting Pixel Sequences and Ordering 30
• 4. EXPERIMENTAL RESULTS 32
• 5. CONCLUSION 35
• REFERENCES 36
• ACKNOWLEDGEMENTS 40
• (초록) 41