The role of grouping in sketched diagram recognition

ABSTRACT

An early step in bottom-up diagram recognition systems is grouping ink strokes into shapes. This paper gives an overview of the key literature on automatic grouping techniques in sketch recognition. In addition, we identify the major challenges in grouping ink into identifiable shapes, discuss the common solutions to these challenges based on current research, and highlight areas for future work.

References

1. Harold Mouchre Christian Viard-Gaudin Ahmad-Montaser Awal, Guihuan Feng. 2011. First experiments on a new online handwritten flowchart database. (2011).
2. Christine Alvarado. 2007. Sketch recognition for digital circuit design in the classroom. In 2007 Invited Workshop on Pen-Centric Computing Research. Citeseer.
3. Christine Alvarado and Randall Davis. 2004. SketchREAD: a multi-domain sketch recognition engine. In Proceedings of the 17th annual ACM symposium on User interface software and technology. ACM, 23--32.
4. Christine Alvarado and Randall Davis. 2006. Dynamically constructed bayes nets for multi-domain sketch understanding. In ACM SIGGRAPH 2006 Courses. ACM, 32.
5. Relja Arandjelović and Tevfik Metin Sezgin. 2011. Sketch recognition by fusion of temporal and image-based features. Pattern Recognition 44, 6 (2011), 1225--1234.
6. Martin Bresler. 2016. Online recognition of sketched arrow-connected diagrams. International Journal on Document Analysis and Recognition (IJDAR) 19, 3 (2016), 253fi?!267.
7. Martin Bresler, Daniel Prùša, and Václav Hlavác. 2013a. Modeling Flowchart Structure Recognition As a Max-Sum Problem. In Proceedings of the 2013 12th International Conference on Document Analysis and Recognition (ICDAR '13). IEEE Computer Society, Washington, DC, USA, 1215--1219.
8. Martin Bresler, Daniel Průša, and Václav Hlaváč. 2013b. Simultaneous Segmentation and Recognition of Graphical Symbols using a Composite Descriptor. In CVWW 2013: Proceedings of the 18th Computer Vision Winter Workshop, Walter G. Kropatsch, Geetha Ramachandran, and Fuensanta Torres (Eds.). Vienna University of Technology, Karlsplatz 13, Vienna, Austria, 16--23.
9. Martin Bresler, Daniel Prusa, and Václav Hlavać. 2015a. Detection of arrows in on-line sketched diagrams using relative stroke positioning. In IEEE Winter Conference on Applications of Computer Vision. IEEE, 610--617.
10. Martin Bresler, Daniel Pruša, and Václav Hlavác. 2015b. Using agglomerative clustering of strokes to perform symbols over-segmentation within a diagram recognition system (CVWW). 67--74.
11. Martin Bresler, Truyen Van Phan, Daniel Prusa, Masaki Nakagawa, and Vclav Hlavc. 2014. Recognition system for on-line sketched diagrams. In Frontiers in Handwriting Recognition (ICFHR), 2014 14th International Conference on. IEEE, 563--568.
12. Beibei Chao, Xiaoyan Zhao, Dapeng Shi, Guihuan Feng, and Bin Luo. 2017. Eyes Understand the Sketch!: Gaze-Aided Stroke Grouping of Hand-Drawn Flowcharts. In Proceedings of the 22Nd International Conference on Intelligent User Interfaces (IUI '17). ACM, New York, NY, USA, 79--83.
13. Gennaro Costagliola, Vincenzo Deufemia, and Michele Risi. 2005. Sketch grammars: A formalism for describing and recognizing diagrammatic sketch languages. In Eighth International Conference on Document Analysis and Recognition (ICDAR'05). IEEE, 1226--1230.
14. Gennaro Costagliola, Mattia De Rosa, and Vittorio Fuccella. 2014. Local context-based recognition of sketched diagrams. Journal of Visual Languages & Computing 25, 6 (2014), 955 -- 962. DOI:http://dx.doi.org/ Distributed Multimedia Systems DMS2014 Part I.
15. Gennaro Costagliola, Mattia De Rosa, and Vittorio Fuccella. 2015. Extending local context-based specifications of visual languages. Journal of Visual Languages & Computing 31 (2015), 184 -- 195. DOI:http://dx.doi.org/ Special Issue on DMS2015.
16. Adrien Delaye. 2014. Structured prediction models for online sketch recognition. Interpretation 1, 3 (2014), 4--16.
17. Adrien Delaye and Kibok Lee. 2015. A flexible framework for online document segmentation by pairwise stroke distance learning. Pattern Recognition 48, 4 (2015), 1193--1206.
18. Vincenzo Deufemia, Michele Risi, and Genoveffa Tortora. 2014. Sketched Symbol Recognition Using Latent-Dynamic Conditional Random Fields and Distance-based Clustering. Pattern Recogn. 47, 3 (March 2014), 1159--1171.
19. Guihuan Feng, Christian Viard-Gaudin, and Zhengxing Sun. 2009. On-line Hand-drawn Electric Circuit Diagram Recognition Using 2D Dynamic Programming. Pattern Recogn. 42, 12 (Dec. 2009), 3215--3223.
20. Leslie Gennari, Levent Burak Kara, Thomas F Stahovich, and Kenji Shimada. 2005. Combining geometry and domain knowledge to interpret hand-drawn diagrams. Computers & Graphics 29, 4 (2005), 547--562.
21. Tracy Hammond and Brandon Paulson. 2011. Recognizing sketched multistroke primitives. ACM Transactions on Interactive Intelligent Systems (TiiS) 1, 1 (2011), 1--34.
22. Tracy A Hammond and Randall Davis. 2009. Recognizing interspersed sketches quickly. In Proceedings of Graphics Interface. Canadian Information Processing Society, 157--166.
23. James Herold and Thomas F Stahovich. 2012. The 1 Recognizer: a fast, accurate, and easy-to-implement handwritten gesture recognition technique. In Proceedings - Sketch-Based Interfaces and Modeling, SBIM. Eurographics Association, 39--46.
24. Heloise Hse and A. Richard Newton. 2004. Sketched Symbol Recognition Using Zernike Moments. In Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 1 - Volume 01 (ICPR '04). IEEE Computer Society, Washington, DC, USA, 367--370.
25. Heloise Hwawen Hse and A Richard Newton. 2005. Recognition and beautification of multi-stroke symbols in digital ink. Computers & Graphics 29, 4 (2005), 533--546.
26. Gabe Johnson, Mark D. Gross, Jason Hong, and Ellen Yi-Luen Do. 2009. Computational Support for Sketching in Design: A Review. Found. Trends Hum.-Comput. Interact. 2, 1 (Jan. 2009), 1--93.
27. David Johnston and Christine Alvarado. 2013. Sketch Recognition of Digital Logical Circuits. (2013).
28. F. Julca-Aguilar, H. Mouchère, C. Viard-Gaudin, and N. S. T. Hirata. 2017. A General Framework for the Recognition of Online Handwritten Graphics. ArXiv e-prints (Sept. 2017).
29. Levent Burak Kara and Thomas F Stahovich. 2007. Hierarchical parsing and recognition of hand-sketched diagrams. In ACM SIGGRAPH - International Conference on Computer Graphics and Interactive Techniques. ACM, 17.
30. Maria Karam and m. c. schraefel. 2006. Investigating User Tolerance for Errors in Vision-enabled Gesture-based Interactions. In Proceedings of the Working Conference on Advanced Visual Interfaces (AVI '06). ACM, New York, NY, USA, 225--232.
31. Mary LaLomia. 1994. User Acceptance of Handwritten Recognition Accuracy. In Conference Companion on Human Factors in Computing Systems (CHI '94). ACM, New York, NY, USA, 107--108.
32. C Lee, Josiah Jordan, Thomas F Stahovich, and James Herold. 2012. Newtons Pen II: an intelligent, sketch-based tutoring system and its sketch processing techniques. In Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling. Eurographics Association, 57--65.
33. Han-Lung Lin. 2014. Estimating Student Competence in Engineering Statics From a Lexical Analysis of Handwritten Equations. Thesis.
34. Stephen Marsland. 2003. Novelty detection in learning systems. Neural computing surveys 3, 2 (2003), 157--195.
35. Tom Ouyang and Randall Davis. 2009. Learning from neighboring strokes: Combining appearance and context for multi-domain sketch recognition. In Advances in Neural Information Processing Systems 22. 1401--1409.
36. Tom Y Ouyang and Randall Davis. 2007. Recognition of Hand Drawn Chemical Diagrams. In Proceedings of the 22Nd National Conference on Artificial Intelligence - Volume 1 (AAAI'07). AAAI Press, 846--851.
37. Tom Y Ouyang and Randall Davis. 2011. ChemInk: a natural real-time recognition system for chemical drawings. In In International Conference on Intelligent User Interfaces (IUI fi11. ACM, 267--276.
38. Brandon Paulson and Tracy Hammond. 2008. PaleoSketch: Accurate Primitive Sketch Recognition and Beautification. In Proceedings of the 13th International Conference on Intelligent User Interfaces (IUI '08). ACM, 1--10.
39. Eric Jeffrey Peterson, Thomas F Stahovich, Eric Doi, and Christine Alvarado. 2010. Grouping Strokes into Shapes in Hand-Drawn Diagrams. In Proceedings of the National Conference on Artificial Intelligence. 974--979.
40. Marco A.F. Pimentel, David A. Clifton, Lei Clifton, and Lionel Tarassenko. 2014. A review of novelty detection. Signal Processing 99 (2014), 215 -- 249.
41. Beryl Plimmer, Rachel Blagojevic, Samuel Hsiao-Heng Chang, Paul Schmieder, and Jacky Shunjie Zhen. 2012. Rata: codeless generation of gesture recognizers. In Proceedings of the 26th Annual BCS Interaction Specialist Group Conference on People and Computers. British Computer Society, 137--146.
42. J Reaver, Thomas F Stahovich, and James Herold. 2011. How to make a quick $: Using hierarchical clustering to improve the efficiency of the dollar recognizer. In Proceedings - SBIM: ACM SIGGRAPH / Eurographics Symposium on Sketch-Based Interfaces and Modeling. ACM, 103--108.
43. Dean Rubine. 1991. Specifying Gestures by Example. (1991), 329--337.
44. Eric Saund and Edward Lank. 2003. Stylus input and editing without prior selection of mode. In UIST: Proceedings of the Annual ACM Symposium on User Interface Softaware and Technology. ACM, 213--216.
45. Tevfik Metin Sezgin and Randall Davis. 2005. HMM-based efficient sketch recognition. In Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 281--283.
46. Tevfik Metin Sezgin and Randall Davis. 2007a. Sketch interpretation using multiscale models of temporal patterns. IEEE Computer Graphics and Applications 27, 1 (2007), 28--37.
47. Tevfik Metin Sezgin and Randall Davis. 2007b. Temporal Sketch Recognition in Interspersed Drawings. In Proceedings of the 4th Eurographics Workshop on Sketch-based Interfaces and Modeling (SBIM '07). ACM, New York, NY, USA, 15--22.
48. Tevfik Metin Sezgin and Randall Davis. 2008. Sketch recognition in interspersed drawings using time-based graphical models. Computers & Graphics 32, 5 (2008), 500--510.
49. Michael Shilman and Paul Viola. 2004. Spatial recognition and grouping of text and graphics. In Proceedings of the First Eurographics conference on Sketch-Based Interfaces and Modeling. Eurographics Association, 91--95.
50. Michael Shilman, Paul Viola, and Kumar Chellapilla. 2004. Recognition and grouping of handwritten text in diagrams and equations. In Frontiers in Handwriting Recognition, 2004. IWFHR-9 2004. Ninth International Workshop on. IEEE, 569--574.
51. Thomas F Stahovich, Eric J Peterson, and Hanlung Lin. 2014. An efficient, classification-based approach for grouping pen strokes into objects. Computers & Graphics 42 (2014), 14--30.
52. Philip C. Stevens, Rachel Blagojevic, and Beryl Plimmer. 2013. Supervised Machine Learning for Grouping Sketch Diagram Strokes. In Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling (SBIM '13). ACM, New York, NY, USA, 43--50.
53. Pang-Ning Tan, Michael Steinbach, and Vipin Kumar. 2005. Introduction to Data Mining, (First Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
54. Caglar Tirkaz, Berrin Yanikoglu, and T. Metin Sezgin. 2012. Sketched symbol recognition with auto-completion. Pattern Recognition 45, 11 (2012), 3926 -- 3937.
55. Chengcheng Wang, Harold Mouchère, Aurélie Lemaitre, and Christian Viard-Gaudin. 2017. Online flowchart understanding by combining max-margin Markov random field with grammatical analysis. International Journal on Document Analysis and Recognition (IJDAR) 20, 2 (01 Jun 2017), 123--136.
56. C. Wang, H. Mouchre, C. Viard-Gaudin, and L. Jin. 2016. Combined Segmentation and Recognition of Online Handwritten Diagrams with High Order Markov Random Field. In 2016 15th International Conference on Frontiers in Handwriting Recognition (ICFHR). 252--257.
57. Jacob O Wobbrock, Andrew D Wilson, and Yang Li. 2007. Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes. In UIST: Proceedings of the Annual ACM Symposium on User Interface Softaware and Technology. ACM, 159--168.
58. Kemal Tugrul Yesilbek and T. Metin Sezgin. 2017. Sketch recognition with few examples. Computers & Graphics 69 (2017), 80 -- 91. DOI:http://dx.doi.org/

Index Terms

• Human-centered computing

  • Human computer interaction (HCI)