A general framework for the recognition of online handwritten graphics
Tóm tắt
We revisit graph grammar and graph parsing as tools for recognizing graphics. A top-down approach for parsing families of handwritten graphics containing different kinds of symbols and of structural relations is proposed. It has been tested on two distinct domains, namely the recognition of handwritten mathematical expressions and of handwritten flowcharts. In the proposed approach, a graphic is considered as a labeled graph generated by a graph grammar. The recognition problem is translated into a graph parsing problem: Given a set of strokes (input data), a parse tree which represents the best interpretation is extracted. The graph parsing algorithm generates multiple interpretations (consistent with the grammar) that can be ranked according to a global cost function that takes into account the likelihood of symbols and structures. The parsing algorithm consists in recursively partitioning the stroke set according to rules defined in the graph grammar. To constrain the number of partitions to be evaluated, we propose the use of a hypothesis graph, built from data-driven machine learning techniques, to encode the most likely symbol and relation hypotheses. Within this approach, it is easy to relax the stroke ordering constraint allowing interspersed symbols, as opposed to some previous works. Experiments show that our method obtains accuracy comparable to methods specifically developed to recognize domain-dependent data.
Tài liệu tham khảo
Plamondon, R., Srihari, S.N.: On-line and off-line handwriting recognition: a comprehensive survey. IEEE Trans. Pattern Anal. Mach. Intell. 22, 63–84 (2000)
Marriott, K., Meyer, B., Wittenburg, K.B.: A Survey of Visual Language Specification and Recognition, pp. 5–85. Springer, New York (1998)
Lin, Z., He, J., Zhong, Z., Wang, R., Shum, H.Y.: Table detection in online ink notes. IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1341–1346 (2006)
Chen, Q., Shi, D., Feng, G., Zhao, X., Luo, B.: On-line handwritten flowchart recognition based on logical structure and graph grammar. In: 5th International Conference on Information Science and Technology (ICIST), pp. 424–429 (2015)
Álvaro, F., Sánchez, J.A., Benedí, J.M.: An integrated grammar-based approach for mathematical expression recognition. Pattern Recognit. 51, 135–147 (2016)
Awal, A.M., Mouchère, H., Viard-Gaudin, C.: Improving online handwritten mathematical expressions recognition with contextual modeling. In: Proceedings of the 12th International Conference on Frontiers in Handwriting Recognition, pp. 427–432 (2010)
Álvaro, F., Sanchez, J.A., Benedi, J.M.: Recognition of printed mathematical expressions using two-dimensional stochastic context-free grammars. In: International Conference on Document Analysis and Recognition (ICDAR), pp. 1225–1229 (2011)
MacLean, S., Labahn, G.: A new approach for recognizing handwritten mathematics using relational grammars and fuzzy sets. Int. J. Doc. Anal. Recognit. 16(2), 139–163 (2013)
Celik, M., Yanikoglu, B.: Probabilistic mathematical formula recognition using a 2D context-free graph grammar. In: International Conference on Document Analysis and Recognition (ICDAR), pp. 161–166 (2011)
Rekers, J., Schürr, A.: Defining and parsing visual languages with layered graph grammars. J. Vis. Lang. Comput. 8(1), 27–55 (1997)
Han, F., Zhu, S.C.: Bottom-up/top-down image parsing by attribute graph grammar. IEEE Int. Conf. Comput. Vis. (ICCV) 2, 1778–1785 (2005)
Blostein, D., Grbavec, A.: Recognition of mathematical notation. In: Wang, P., Bunke, H. (eds.) Handbook of Character Recognition and Document Image Analysis, pp. 557–582. World Scientific, Singapore (1997)
Chan, K.F., Yeung, D.Y.: Mathematical expression recognition: a survey. Int. J. Doc. Anal. Recognit. 3, 3–15 (2000)
Zanibbi, R., Blostein, D.: Recognition and retrieval of mathematical expressions. Int. J. Doc. Anal. Recognit. 15(4), 331–357 (2012)
Miyao, H., Maruyama, R.: On-line handwritten flowchart recognition, beautification and editing system. In: International Conference on Frontiers in Handwriting Recognition, pp. 83–88 (2012)
Carton, C., Lemaitre, A., Coüasnon, B.: Fusion of statistical and structural information for flowchart recognition. In: 12th International Conference on Document Analysis and Recognition, pp. 1210–1214 (2013)
Bresler, M., Phan, T.V., Prusa, D., Nakagawa, M., Hlavác, V.: Recognition system for on-line sketched diagrams. In: 14th International Conference on Frontiers in Handwriting Recognition, pp. 563–568 (2014)
Matsakis, N.E.: Recognition of handwritten mathematical expressions. Master’s thesis, Massachusetts Institute of Technology, Cambridge (1999)
Tapia, E., Rojas, R.: Recognition of on-line handwritten mathematical expressions using a minimum spanning tree construction and symbol dominance. In: Lladós, J., Kwon, Y.B. (eds.) Graphics Recognition. Recent Advances and Perspectives, vol 3088, Springer, Berlin, pp. 329–340 (2004)
Zanibbi, R., Blostein, D., Cordy, J.R.: Recognizing mathematical expressions using tree transformation. IEEE Trans. Pattern Anal. Mach. Intell. 24, 1455–1467 (2002)
Álvaro. F., Zanibbi, R.: A shape-based layout descriptor for classifying spatial relationships in handwritten math. In: Proceedings of the ACM Symposium on Document Engineering, pp. 123–126 (2013)
Awal, A.M., Mouchère, H., Viard-Gaudin, C.: Towards handwritten mathematical expression recognition. In: Proceedings of the 10th International Conference on Document Analysis and Recognition, pp. 1046–1050 (2009)
Awal, A.M., Mouchère, H., Viard-Gaudin, C.: A global learning approach for an online handwritten mathematical expression recognition system. Pattern Recognit. Lett. 35, 68–77 (2012)
Yamamoto, R., Sako, S., Nishimoto, T., Sagayama, S.: On-line recognition of handwritten mathematical expressions based on stroke-based stochastic context-free grammar. In: International Workshop on Frontiers in Handwriting Recognition (2006)
Simistira, F., Katsouros, V., Carayannis, G.: Recognition of online handwritten mathematical formulas using probabilistic SVMs and stochastic context free grammars. Pattern Recognit. Lett. 53, 85–92 (2015)
Bunke, H.: Attributed programmed graph grammars and their application to schematic diagram interpretation. IEEE Trans. Pattern Anal. Mach. Intell. PAMI 4(6), 574–582 (1982)
Fahmy, H., Blostein, D.: A survey of graph grammars: theory and applications. In: 11th IAPR International Conference on Pattern Recognition, pp. 294–298 (1992)
Baumann, S.: A simplified attributed graph grammar for high-level music recognition. In: ICDAR (1995)
Fahmy, H., Blostein, D.: A graph grammar programming style for recognition of music notation. Mach. Vis. Appl. 6(2), 83–99 (1993)
Lavirotte, S., Pottier, L.: Optical formula recognition. In: Proceedings of the Fourth International Conference on Document Analysis and Recognition, vol. 1, pp. 357–361 (1997)
Younger, D.H.: Recognition and parsing of context-free languages in time \(n^3\). Inf. Control 10(2), 189–208 (1967)
Yuan, Z., Pan, H., Zhang, L.: A novel pen-based flowchart recognition system for programming teaching. In: Wang, F.L., Miao, L., Zhao, J., He, J., Leung, E.W. (eds.) Advances in Blended Learning, pp. 55–64. Springer, Berlin (2009)
Deng, Y., Kanervisto, A., Ling, J., Rush, A.M.: Image-to-markup generation with coarse-to-fine attention. In: Proceedings of the 34th International Conference on Machine Learning, ICML, pp. 980–989 (2017)
Zhang, J., Du, J., Zhang, S., Liu, D., Hu, Y., Hu, J., Wei, S., Dai, L.: Watch, attend and parse: an end-to-end neural network based approach to handwritten mathematical expression recognition. Pattern Recognit. 71, 196–206 (2017)
Le, A.D., Nakagawa, M.: Training an end-to-end system for handwritten mathematical expression recognition by generated patterns. In: 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), vol. 01, pp. 1056–1061 (2017)
Zhang, T., Mouchère, H., Viard-Gaudin, C.: A tree-BLSTM-based recognition system for online handwritten mathematical expressions. Neural Comput. Appl. (2018). https://doi.org/10.1007/s00521-018-3817-2
Zhang, J., Du, J., Dai, L.: Multi-scale attention with dense encoder for handwritten mathematical expression recognition. In: 24th International Conference on Pattern Recognition, pp. 2245–2250 (2018)
Zhang, J., Du, J., Dai, L.: Track, attend, and parse (TAP): an end-to-end framework for online handwritten mathematical expression recognition. IEEE Trans. Multimed. 21(1), 221–233 (2019)
Keysers, D., Deselaers, T., Rowley, H.A., Wang, L., Carbune, V.: Multi-language online handwriting recognition. IEEE Trans. Pattern Anal. Mach. Intell. 39(6), 1180–1194 (2017)
Pflatz, J., Rosenfeld, A.: Web grammars. In: Proceedings of First International Joint Conference on Artificial Intelligence, pp. 193–220 (1969)
Grune, D., Jacobs, C.J.H.: Parsing Techniques: A Practical Guide, 2nd edn. Springer, Berlin (2008)
Boullier, P., Nasr, A., Sagot, B.: Constructing parse forests that include exactly the N-best PCFG trees. In: Proceedings of the 11th International Conference on Parsing Technologies, pp. 117–128 (2009)
Delaye, A., Anquetil, E.: Hbf49 feature set: a first unified baseline for online symbol recognition. Pattern Recogninit. 46(1), 117–130 (2013)
Mouchère, H., Viard-Gaudin, C., Zanibbi, R., Garain, U.: ICFHR2016 CROHME: Competition on recognition of online handwritten mathematical expressions. In: 15th International Conference on Frontiers in Handwriting Recognition (ICFHR), pp. 607–612 (2016)
Julca-Aguilar, F., Mouchère, H., Viard-Gaudin, C., Hirata, N.S.T.: Progress in pattern recognition, image analysis, computer vision, and applications. In: 20th Iberoamerican Congress, Springer International Publishing, Cham, chap Top-Down Online Handwritten Mathematical Expression Parsing with Graph Grammar, pp. 444–451 (2015)
Julca-Aguilar, F., Viard-Gaudin, C., Mouchère, H., Medjkoune, S., Hirata, N.: Mathematical symbol hypothesis recognition with rejection option. In: 14th International Conference on Frontiers in Handwriting Recognition (2014)
Julca-Aguilar, F., Hirata, N.S.T., Mouchère, H., Viard-Gaudin, C.: Subexpression and dominant symbol histograms for spatial relation classification in mathematical expressions. In: 23rd International Conference on Pattern Recognition (ICPR), pp. 3446–3451 (2016)
Le Cun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient based learning applied to document recognition. Proc. IEEE 86(11), 2278–2324 (1998)
Awal, A.M., Feng, G., Mouchère, H., Viard-Gaudin, C.: First experiments on a new online handwritten flowchart database. Document Recognition and Retrieval XVIII. San Fransisco, United States, pp. 7874–78740A (2011)
Bresler, M., Prùa, D., Hlavác, V.: Modeling flowchart structure recognition as a max-sum problem. In: 12th International Conference on Document Analysis and Recognition, pp. 1215–1219 (2013)
Lemaitre, A., Mouchère, H., Camillerapp, J., Coüasnon, B.: Interest of Syntactic Knowledge for On-Line Flowchart Recognition, pp. 89–98. Springer, Berlin (2013)
Wang, C., Mouchère, H., Viard-Gaudin, C., Jin, L.: Combined segmentation and recognition of online handwritten diagrams with high order Markov random field. In: 15th International Conference on Frontiers in Handwriting Recognition (ICFHR), pp. 252–257 (2016)