Recognition and processing of hand-drawn diagrams using syntactic and semantic analysis

ABSTRACT

We present an approach to the processing of hand-drawn diagrams. Hand drawing is inherently imprecise; we rely on syntactical and semantical analysis to resolve the inevitable ambiguities arising from this impreciseness. Based on the specification of a diagram language (containing aspects like concrete and abstract syntax, grammar rules for a parser, and attributes for semantics), editors supporting free hand drawing are generated. Since the generation process relies on the specifications only, our approach is fully generic. In this paper the overall architecture and concepts of our approach are explained and discussed. The user-drawn strokes (forming the diagram) are transformed into a number of independent models. The drawn components are recognized in these models, directed by the specification. Then the set of all components is analyzed to find the interpretation that best fits the whole diagram. We build upon DiaGen, a generic diagram editor generator enabling syntax and semantic analysis for diagrams, and extend it to support hand drawing. Case studies (done with a fully working implementation in Java) confirm the strength and applicability of our approach.

REFERENCES

• 1: C. Alvarado and R. Davis. Resolving ambiguities to create a natural computer-based sketching environment. In Proc. IJCAI '01, pp. 1365--1374, 2001.
• 2: Ajay Apte , Van Vo , Takayuki Dan Kimura, Recognizing multistroke geometric shapes: an experimental evaluation, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.121-128, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168654]
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: F. Brieler and M. Minas. A new approach to flexible, trainingless sketching. In Proc. VMSIS '05, pp. 43--50, 2005.
• 5: F. Brieler and M. Minas. Ambiguity resolution for sketched diagrams by syntax analysis based on graph grammars. In Proc. GT-VMT '08, 2008.
• 6: Giovanni Casella , Gennaro Costagliola , Vincenzo Deufemia , Maurizio Martelli , Viviana Mascardi, An Agent-Based Framework for Context-Driven Interpretation of Symbols in Diagrammatic Sketches, Proceedings of the Visual Languages and Human-Centric Computing, p.73-80, September 04-08, 2006 [doi>10.1109/VLHCC.2006.8]
• 7: Ronald Chung , Petrut Mirica , Beryl Plimmer, InkKit: a generic design tool for the tablet PC, Proceedings of the 6th ACM SIGCHI New Zealand chapter's international conference on Computer-human interaction: making CHI natural, p.29-30, July 07-08, 2005, Auckland, New Zealand [doi>10.1145/1073943.1073950]
• 8: G. Costagliola, A. Delucia, S. Orefice, and G. Polese. A classification framework to support the design of visual languages. Journal of Vis. Lang. Comput., 13(6):573--600, 2002.
• 9: Gennaro Costagliola , Vincenzo Deufemia , Michele Risi, A Trainable System for Recognizing Diagrammatic Sketch Languages, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.281-283, September 20-24, 2005 [doi>10.1109/VLHCC.2005.12]
• 10: Gennaro Costagliola , Vincenzo v , Michele Risi, A Multi-layer Parsing Strategy for On-line Recognition of Hand-drawn Diagrams, Proceedings of the Visual Languages and Human-Centric Computing, p.103-110, September 04-08, 2006 [doi>10.1109/VLHCC.2006.4]
• 11: F. Drewes , H.-J. Kreowski , A. Habel, Hyperedge replacement graph grammars, Handbook of graph grammars and computing by graph transformation: volume I. foundations, World Scientific Publishing Co., Inc., River Edge, NJ, 1997
• 12: M. D. Gross and E. Y.-L. Do. Drawing on the back of an envelope: a framework for interacting with application programs by freehand drawing. Computers & Graphics, 24(6):835--849. Elsevier, 2000.
• 13: John Grundy , John Hosking, Supporting Generic Sketching-Based Input of Diagrams in a Domain-Specific Visual Language Meta-Tool, Proceedings of the 29th international conference on Software Engineering, p.282-291, May 20-26, 2007 [doi>10.1109/ICSE.2007.81]
• 14: T. Hammond and R. Davis. Tahuti: A geometrical sketch recognition system for uml class diagrams. Papers from the 2002 AAAI Spring Symposium on Sketch Understanding, pp. 59--68, 2002.
• 15: T. Hammond and R. Davis. Ladder, a sketching language for user interface developers. Computers & Graphics, 29(4):518--532. Elsevier, 2005.
• 16: Jason I. Hong , James A. Landay, SATIN: a toolkit for informal ink-based applications, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.63-72, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354412]
• 17: Levent Burak Kara , Thomas F. Stahovich, Hierarchical parsing and recognition of hand-sketched diagrams, Proceedings of the 17th annual ACM symposium on User interface software and technology, October 24-27, 2004, Santa Fe, NM, USA [doi>10.1145/1029632.1029636]
• 18: L. B. Kara and T. F. Stahovich. An image-based, trainable symbol recognizer for hand-drawn sketches. Computers & Graphics, 29(4):501--517. Elsevier, 2005.
• 19: James Lin , Mark W. Newman , Jason I. Hong , James A. Landay, DENIM: finding a tighter fit between tools and practice for Web site design, Proceedings of the SIGCHI conference on Human factors in computing systems, p.510-517, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332486]
• 20: Jennifer Mankoff , Scott E. Hudson , Gregory D. Abowd, Interaction techniques for ambiguity resolution in recognition-based interfaces, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.11-20, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354407]
• 21: Mark Minas, Concepts and realization of a diagram editor generator based on hypergraph transformation, Science of Computer Programming, v.44 n.2, p.157-180, August 2002 [doi>10.1016/S0167-6423(02)00037-0]
• 22: M. Minas. Generating meta-model-based freehand editors. In Proc. GraBaTs '06, 2006.
• 23: Ken Perlin, Quikwriting: continuous stylus-based text entry, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.215-216, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288613]
• 24: B. Plimmer and I. Freeman. A toolkit approach to sketched diagram recognition. In Proc. HCI '07. Springer, 2007.
• 25: Dean Rubine, Specifying gestures by example, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.329-337, July 1991
• 26: Tevfik Metin Sezgin , Thomas Stahovich , Randall Davis, Sketch based interfaces: early processing for sketch understanding, Proceedings of the 2001 workshop on Perceptive user interfaces, November 15-16, 2001, Orlando, Florida [doi>10.1145/971478.971487]
• 27: I. E. Sutherland. Sketchpad: A man-Machine graphical Communication System. PhD thesis, MIT, 1963.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

Keywords:
DiaGen, ambiguity resolution, hand drawing, model, recognition, sketching