Comparative performance analysis of stroke correspondence search methods for stroke-order free online multi-stroke character recognition

Abstract

For stroke-order free online multi-stroke character recognition, stroke-to-stroke correspondence search between an input pattern and a reference pattern plays an important role to deal with the stroke-order variation. Although various methods of stroke correspondence have been proposed, no comparative study for clarifying the relative superiority of those methods has been done before. In this paper, we firstly review the approaches for solving the stroke-order variation problem. Then, five representative methods of stroke correspondence proposed by different groups, including cube search (CS), bipartite weighted matching (BWM), individual correspondence decision (ICD), stable marriage (SM), and deviation-expansion model (DE), are experimentally compared, mainly in regard of recognition accuracy and efficiency. The experimental results on an online Kanji character dataset, showed that 99.17%, 99.17%, 96.37%, 98.54%, and 96.59% were attained by CS, BWM, ICD, SM, and DE, respectively as their recognition rates. Extensive discussions are made on their relative superiorities and practicalities.

Keywords

cube search / bipartite weighted matching / individual correspondence decision / stable marriage / deviationexpansion model

References

[1] Sakoe H, Shin J. A stroke order search algorithm for online character recognition. Research Reports on Information Science and Electrical Engineering of Kyushu University, 1997, 2(1): 99-104 (in Japanese)

[2] Hsieh A J, Fan K C, Fan T I. Bipartite weighted matching for on-line handwritten Chinese character recognition. Pattern Recognition, 1995, 28(2): 143-151

[3] Odaka K, Wakahara T, Masuda I. Stroke order free on-line handwritten character recognition algorithm. IEICE Transactions on Information and Systems, 1982, J65-D(6): 679-686 (in Japanese)

[4] Wakahara T, Murase H, Odaka K. On-line handwriting recognition. In: Proceedings of the IEEE. 1992, 80(7): 1181-1194

[5] Yokota T, Kuzunuki S, Gunji, K, Katsura K, Hamada N, Fukunaga Y. An on-line cuneiform modeled handwritten Japanese character recognition method free from both the number and order of character strokes. Transactions of Information Processing Society of Japan, 2003, 44(3): 980-990 (in Japanese)

[6] Lin C K, Fan K C, Lee F T P. On-line recognition by deviation expansion model and dynamic programming matching. Pattern Recognition, 1993, 26(2): 259-268

[7] Liu C L, Jaeger S, Nakagawa M. Online recognition of Chinese characters: the state-of-the-art. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 198-213

[8] Lee J J, Kim J, Kim J H. Data-driven design of HMM topology for online handwriting recognition. International Journal of Pattern Recognition and Artificial Intelligence, 2001, 15(1): 107-121

[9] Nakai M, Shimodaira H, Sagayama S. Generation of hierarchical dictionary for stroke-order free kanji handwriting recognition based on substroke HMM. In: Proceedings of 7th International Conference on Document Analysis and Recognition. 2003, 514-518

[10] Nakai M, Akira N. Shimodaira H, Sagayama S, Substroke approach to HMM-based on-line kanji handwriting recognition. In: Proceedings of 6th International Conference on Document Analysis and Recognition. 2001, 491-495

[11] Tanaka H, Nakajima K, Ishigaki K, Akiyama K, Nakagawa M. Hybrid pen-input character recognition system based on integration of onlineoffline recognition. In: Proceedings of 5th International Conference on Document Analysis and Recognition. 1999, 209-212

[12] Oda H, Zhu B, Tokuno J, Onuma M, Kitadai A, Nakagawa M. A compact on-line and offline combined recognizer. In: Proceedings of 10th International Workshop on Frontiers in Handwriting Recognition. 2006, 133-138

[13] Katayama Y, Uchida S, Sakoe H. A new HMM for on-line character recognition using pen-direction and pen-coordinate features. In: Proceedings of 19th International Conference on Pattern Recognition. 2008.

[14] Liu J, Cham W K, Chang M M Y. Stroke order and stroke number free on-line Chinese character recognition using attributed relational graph matching. In: Proceedings of 13th International Conference on Pattern Recognition. 1996, 3: 259-263

[15] Zheng J, Ding X, Wu Y. Recognizing on-line handwritten Chinese character via FARG matching. In: Proceedings of 4th International Conference on Document Analysis and Recognition. 1997, 621-624

[16] Zheng J, Ding X, Wu Y, Lu Z. Spatio-temporal unified model for on-line handwritten Chinese character recognition. In: Proceedings of 5th International Conference on Document Analysis and Recognition. 1999, 649-652

[17] Chen J W, Lee S Y. On-line handwriting recognition of Chinese characters via rule-based approach. In: Proceedings of 13th International Conference on Pattern Recognition. 1996, 3: 220-224

[18] Chou K S, Fan K C, Fan T I. Radical-based neighboring segment matching method for on-line Chinese character recognition. In: Proceedings of 13th International Conference on Pattern Recognition. 1996, 3: 84-88

[19] Joe M J, Lee H J, A combined method on the handwritten character recognition. In: Proceedings of 3rd International Conference on Document Analysis and Recognition. 1995, 112-115

[20] Sakoe H, Chiba S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 1978, ASSP-26(1): 43-49

[21] Cai W, Uchida S, Sakoe H. An efficient radical-based algorithm for stroke-order-free online Kanji character recognition. In: Proceedings of 18th International Conference on Pattern Recognition. 2006, 2: 986-989

[22] Kuhn H W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 1955, 2: 83-97

[23] Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1): 32-38

[24] Papadimitriou C H, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey, 1982

[25] Sedgewick R. Algorithms. Addison-Wesley, second edition, 1988, 499-504

[26] Nakagawa M, Matsumoto K. Collection of on-line handwritten Japanese character pattern databases and their analysis. International Journal on Document Analysis and Recognition, 2004, 7(1): 69-81

[27] Liu C L, Yin F, Wang D H, Wang Q F. CASIA online and offline Chinese handwriting databases. In: Proceedings of 11th International Conference on Document Analysis and Recognition. 2011, 37-41

[28] Roy K, Sharma N, Pal T, Pal U, Online Bangla handwriting recognition system. In: Proceedings of International Conference on Advances in Pattern Recognition. 2007, 117-122

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg