Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Online recognition of sketched arrow-connected diagrams

  • Original Paper
  • Published:
International Journal on Document Analysis and Recognition (IJDAR) Aims and scope Submit manuscript

Abstract

We introduce a new, online, stroke-based recognition system for hand-drawn diagrams which belong to a group of documents with an explicit structure obvious to humans but only loosely defined from the machine point of view. We propose a model for recognition by selection of symbol candidates, based on evaluation of relations between candidates using a set of predicates. It is suitable for simpler structures where the relations are explicitly given by symbols, arrows in the case of diagrams. Knowledge of a specific diagram domain is used—the two domains are flowcharts and finite automata. Although the individual pipeline steps are tailored for these, the system can readily be adapted for other domains. Our entire diagram recognition pipeline is outlined. Its core parts are text/non-text separation, symbol segmentation, their classification and structural analysis. Individual parts have been published by the authors previously and so are described briefly and referenced. Thorough evaluation on benchmark databases shows the accuracy of the system reaches the state of the art and is ready for practical use. The paper brings several contributions: (a) the entire system and its state-of-the-art performance; (b) the methodology exploring document structure when it is loosely defined; (c) the thorough experimental evaluation; (d) the new annotated database for online sketched flowcharts and finite automata diagrams.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. http://graphviz.org/.

  2. https://dev.myscript.com/technology/math/.

  3. http://cmp.felk.cvut.cz/~breslmar/diagram_database.

  4. http://www.iam.unibe.ch/fki/databases/iam-online-document-database.

  5. http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro.

  6. http://www.ibm.com/software/integration/optimization/cplex-optimizer/.

References

  1. Alvarado, C., Davis, R.: SketchREAD: a multi-domain sketch recognition engine. In: UIST ’04: 17th Annual ACM Symposium on User Interface Software and Technology. UIST ’04, pp. 23–32. ACM, New York (2004)

  2. Álvaro, F., Sánchez, J.A., Benedí, J.M.: Recognition of on-line handwritten mathematical expressions using 2d stochastic context-free grammars and hidden Markov models. Pattern Recogn. Lett. 35, 58–67 (2014)

    Article  Google Scholar 

  3. Arvo, J., Novins, K.: Appearance-preserving manipulation of hand-drawn graphs. In: 3rd International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, GRAPHITE ’05, pp. 61–68. ACM (2005)

  4. Awal, A.M., Feng, G., Mouchere, H., Viard-Gaudin, C.: First experiments on a new online handwritten flowchart database. In: DRR’11, pp. 1–10 (2011)

  5. Blagojevic, R., Plimmer, B., Grundy, J., Wang, Y.: Using data mining for digital ink recognition: dividing text and shapes in sketched diagrams. Comput. Graph. 35(5), 976–991 (2011)

    Article  Google Scholar 

  6. Bresler, M., Průša, D., Hlaváč, V.: Detection of arrows in on-line sketched diagrams using relative stroke positioning. In: WACV ’15: IEEE Winter Conference on Applications of Computer Vision, pp. 610–617. IEEE Computer Society (2015)

  7. Bresler, M., Průša, D., Hlaváč, V.: modeling flowchart structure recognition as a max-sum problem. In: O’Conner, L. (ed.) ICDAR ’13: 12th International Conference on Document Analysis and Recognition, pp. 1247–1251. IEEE Computer Society (2013)

  8. Bresler, M., Průša, D., Hlaváč, V.: Using agglomerative clustering of strokes to perform symbols over-segmentation within a diagram recognition system. In: Paul Wohlhart, V.L. (ed.) CVWW ’15: Proceedings of the 20th Computer Vision Winter Workshop, pp. 67–74. Graz University of Technology (2015)

  9. Bresler, M., Van Phan, T., Průša, D., Nakagawa, M., Hlaváč, V.: Recognition system for on-line sketched diagrams. In: Guerrero, J.E. (ed.) ICFHR ’14: 14th International Conference on Frontiers in Handwriting Recognition, pp. 563–568. IEEE Computer Society (2014)

  10. Carton, C., Lemaitre, A., Couasnon, B.: Fusion of statistical and structural information for flowchart recognition. In: ICDAR ’13: 12th International Conference on Document Analysis and Recognition, pp. 1210–1214 (2013)

  11. Delaye, A.: Structured prediction models for online sketch recognition (2014). Unpublished manuscript. https://sites.google.com/site/adriendelaye/home/news/unpublishedmanuscriptavailable

  12. Delaye, A., Anquetil, E.: HBF49 feature set: a first unified baseline for online symbol recognition. Pattern Recogn. 46(1), 117–130 (2013)

    Article  Google Scholar 

  13. Delaye, A., Lee, K.: A flexible framework for online document segmentation by pairwise stroke distance learning. Pattern Recogn. 48(4), 1197–1210 (2015)

    Article  Google Scholar 

  14. Delaye, A., Liu, C.L.: Contextual text/non-text stroke classification in online handwritten notes with conditional random fields. Pattern Recogn. 47(3), 959–968 (2014)

    Article  Google Scholar 

  15. Feng, G., Viard-Gaudin, C., Sun, Z.: On-line hand-drawn electric circuit diagram recognition using 2D dynamic programming. Pattern Recogn. 42(12), 3215–3223 (2009)

    Article  MATH  Google Scholar 

  16. Hammond, T., Davis, R.: LADDER, a sketching language for user interface developers. Comput. Graph. 29, 518–532 (2005)

    Article  Google Scholar 

  17. Hammond, T., Davis, R.: Tahuti: A geometrical sketch recognition system for UML class diagrams. In: ACM SIGGRAPH 2006 Courses, SIGGRAPH ’06. ACM, New York (2006)

  18. Hammond, T., Paulson, B.: Recognizing sketched multistroke primitives. ACM Trans. Interact. Intell. Syst. 1(1), 4:1–4:34 (2011)

    Article  Google Scholar 

  19. Indermühle, E., Frinken, V., Bunke, H.: Mode detection in online handwritten documents using BLSTM neural networks. In: ICFHR ’12: 13th International Conference on Frontiers in Handwriting Recognition, pp. 302–307 (2012)

  20. Kara, L.B., Stahovich, T.F.: Hierarchical parsing and recognition of hand-sketched diagrams. In: 17th Annual ACM Symposium on User Interface Software and Technology, UIST ’04, pp. 13–22. ACM (2004)

  21. Le, A.D., Van Phan, T., Nakagawa, M.: A system for recognizing online handwritten mathematical expressions and improvement of structure analysis. In: DAS ’14: 11th IAPR International Workshop on Document Analysis Systems, pp. 51–55 (2014)

  22. Lemaitre, A., Mouchére, H., Camillerapp, J., Coüasnon, B.: Interest of syntactic knowledge for on-line flowchart recognition. In: GREC ’11: 9th IAPR International Workshop on Graphics Recognition, pp. 85–88 (2011)

  23. Liu, C.L., Zhou, X.D.: Online Japanese character recognition using trajectory-based normalization and direction feature extraction. In: Lorette, G. (ed.) Tenth International Workshop on Frontiers in Handwriting Recognition. Université de Rennes 1, Suvisoft (2006)

    Google Scholar 

  24. Martín-Albo, D., Plamondon, R., Vidal, E.: Training of on-line handwriting text recognizers with synthetic text generated using the kinematic theory of rapid human movements. In: Guerrero, J.E. (ed.) ICFHR ’14: 14th International Conference on Frontiers in Handwriting Recognition, pp. 543–548. IEEE Computer Society (2014)

  25. Miyao, H., Maruyama, R.: On-line handwritten flowchart recognition, beautification and editing system. In: ICFHR ’12: 13th International Conference on Frontiers in Handwriting Recognition, pp. 83–88 (2012)

  26. Mouchère, H., Viard-Gaudin, C., Zanibbi, R., Garain, U.: ICFHR 2014 competition on recognition of on-line handwritten mathematical expressions (CROHME 2014). In: J.E. Guerrero (ed.) ICFHR ’14: 14th International Conference on Frontiers in Handwriting Recognition, pp. 791–796. IEEE Computer Society (2014)

  27. Otte, S., Krechel, D., Liwicki, M., Dengel, A.: Local feature based online mode detection with recurrent neural networks. In: ICFHR ’12: 13th International Conference on Frontiers in Handwriting Recognition, pp. 531–535 (2012)

  28. Ouyang, T.Y., Davis, R.: Chemink: A natural real-time recognition system for chemical drawings. In: 16th International Conference on Intelligent User Interfaces, IUI ’11, pp. 267–276. ACM (2011)

  29. Plimmer, B., Purchase, H.C., Yang, H.Y.: Sketchnode: intelligent sketching support and formal diagramming. In: 22nd Conference of the Computer-Human Interaction Special Interest Group of Australia on Computer-Human Interaction, OZCHI ’10, pp. 136–143. ACM (2010)

  30. Qi, Y., Szummer, M., Minka, T.P.: Diagram structure recognition by Bayesian conditional random fields. In: Conference on Computer Vision and Pattern Recognition, pp. 191–196. IEEE Computer Society (2005)

  31. Refaat, K., Helmy, W., Ali, A., AbdelGhany, M., Atiya, A.: A new approach for context-independent handwritten offline diagram recognition using support vector machines. In: IJCNN ’08: IEEE International Joint Conference on Neural Networks, pp. 177–182 (2008)

  32. Sezgin, T.M., Davis, R.: HMM-based efficient sketch recognition. In: IUI ’05: 10th International Conference on Intelligent User Interfaces. IUI ’05, pp. 281–283. ACM, New York (2005)

  33. Stoffel, A., Tapia, E., Rojas, R.: Recognition of on-line handwritten commutative diagrams. In: ICDAR ’09: 10th International Conference on Document Analysis and Recognition, pp. 1211–1215 (2009)

  34. Szwoch, W., Mucha, M.: Recognition of Hand Drawn Flowcharts, Advances in Intelligent Systems and Computing, vol. 184. Springer, Berlin (2013)

    Google Scholar 

  35. Van Phan, T., Nakagawa, M.: Text/non-text classification in online handwritten documents with recurrent neural networks. In: J.E. Guerrero (ed.) ICFHR ’14: 14th International Conference on Frontiers in Handwriting Recognition, pp. 23–28. IEEE Computer Society (2014)

  36. Werner, T.: A linear programming approach to max-sum problem: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1165–1179 (2007)

    Article  Google Scholar 

Download references

Acknowledgments

The first author was supported by the Grant Agency of the CTU under the project SGS16/085/OHK3/1T/13. The second and the third authors were supported by the Czech Science Foundation under grant no. 15-04960S. The authors thank Truyen van Phan for his help with the text/non-text separation, Daniel Martín-Albo for creating the synthesized samples for the SVM classifiers and Roger Boyle for proofreading of the paper.

Author information

Authors and Affiliations

  1. Center for Machine Perception, Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 2, 166 27, Prague 6, Czech Republic

    Martin Bresler & Daniel Průša

  2. Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Zikova 4, 166 36, Prague 6, Czech Republic

    Václav Hlaváč

Authors
  1. Martin Bresler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Průša
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Václav Hlaváč
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Bresler.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bresler, M., Průša, D. & Hlaváč, V. Online recognition of sketched arrow-connected diagrams. IJDAR 19, 253–267 (2016). https://doi.org/10.1007/s10032-016-0269-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10032-016-0269-z

Keywords

Search

Navigation