Structuring and manipulating hand-drawn concept maps

ABSTRACT

Concept maps are an important tool to knowledge organization, representation, and sharing. Most current concept map tools do not provide full support for hand-drawn concept map creation and manipulation, largely due to the lack of methods to recognize hand-drawn concept maps. This paper proposes a structure recognition method. Our algorithm can extract node blocks and link blocks of a hand-drawn concept map by combining dynamic programming and graph partitioning and then build a concept-map structure by relating extracted nodes and links. We also introduce structure-based intelligent manipulation technique of hand-drawn concept maps. Evaluation shows that our method has high structure recognition accuracy in real time, and the intelligent manipulation technique is efficient and effective.

REFERENCES

• 1: Christine J. Alvarado , Randall Davis, Multi-domain sketch understanding, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 2: Xiang Ao , Junfeng Li , Xugang Wang , Guozhong Dai, Structuralizing digital ink for efficient selection, Proceedings of the 11th international conference on Intelligent user interfaces, January 29-February 01, 2006, Sydney, Australia [doi>10.1145/1111449.1111484]
• 3: Kenneth D. Forbus , Jeffrey Usher, Sketching for knowledge capture: a progress report, Proceedings of the 7th international conference on Intelligent user interfaces, January 13-16, 2002, San Francisco, California, USA [doi>10.1145/502716.502730]
• 4: Gennari, L., Kara, L.B., and Stahovich, T.F. Combining Geometry and Domain Knowledge to Interpret Hand-Drawn Diagrams. Computers & Graphics 29,4(2005), 547--562.
• 5: Hammond, T. and Davis, R. Tahuti: A Geometrical Sketch Recognition System for UML Class Diagrams. In Proceedings of AAAI Spring Symposium on Sketch Understanding, 2002, 59--66.
• 6: 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]
• 7: Karypis, G. and Kumar, V. hMETIS: A Hypergraph Partitioning Package(Version 1.5.3) {EB/OL}.http://glaros.dtc.umn.edu/gkhome/views/metis/hmetis/download.html.
• 8: Li, Y., Guan, Z.W., Wang, H.A., Dai, G.Z. and Ren, X.S. Structuralizing Freeform Notes by Implicit Sketch Understanding, In Proceedings of AAAI Spring Symposium on Sketch Understanding, 2002, 91--98.
• 9: Novak, J. D. and Cañas, A. J. The Theory Underlying Concept Maps and How to Construct Them. Technical Report IHMC CmapTools 2006-01 Rev 01-2008. Florida Institute for Human and Machine Cognition, 2008.
• 10: Novak, J.D. Learning, Creating, and Using Knowledge: Concept Maps as Facilitative Tools in Schools and Corporations. Lawrence Erlbaum Associates, Mahwah, NJ, 1998.
• 11: Ouyang, T.Y. and Davis, R. Recognition of Hand-Drawn Chemical Diagrams. In Proc AAAI 2007, 846--851.
• 12: Shilman M, Pasula H, Russell S, Newton R. Statistical visual language models for ink parsing. In Proceedings of AAAI Spring Symposium on Sketch Understanding, 2002, 126--132.
• 13: Michael Shilman , Paul Viola , Kumar Chellapilla, Recognition and Grouping of Handwritten Text in Diagrams and Equations, Proceedings of the Ninth International Workshop on Frontiers in Handwriting Recognition, p.569-574, October 26-29, 2004 [doi>10.1109/IWFHR.2004.86]
• 14: Szummer, M. and Cowans. P. Incorporating Context and User Feedback in Pen-Based Interfaces. In Proceeding of AAAI Fall Workshop on Making Pen-Based Interaction Intelligent and Natural, 2004, 159--166.
• 15: Jacob O. Wobbrock , Andrew D. Wilson , Yang Li, Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes, Proceedings of the 20th annual ACM symposium on User interface software and technology, October 07-10, 2007, Newport, Rhode Island, USA [doi>10.1145/1294211.1294238]

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)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Design

Keywords:
dynamic programming, graph partition, hand-drawn concept map, structure recognition