Recognizing and interpreting diagrams in design

ABSTRACT

Hand drawn diagrams are essential tools for thinking and communicating in the early phases of design, yet computer based drawing tools support diagramming and sketching only poorly. Key components of computational support for early design include recognition, interpretation, and management of diagrams. The paper describes the motivation for, implementation of, and initial experience with the “computer as cocktail napkin” project, a design environment based on diagrams. It explains low level recognition of glyphs, construction of higher-level recognizers, and routines for managing diagrams in the cocktail napkin prototype.

REFERENCES

• 1: 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]
• 2: Sara A. Bly , Steve R. Harrison , Susan Irwin, Media spaces: bringing people together in a video, audio, and computing environment, Communications of the ACM, v.36 n.1, p.28-46, Jan. 1993 [doi>10.1145/151233.151235]
• 3: Chandrasekaran, B.. Narayanan, N.H., Iwasaki, Y. Reasoning with Diagrammatic Representations. AI Magazine, 14.2, (1993) pp. 49-56.
• 4: Stephen M. Ervin, Designing with diagrams: a role for computing in design education and exploration, The electronic design studio, MIT Press, Cambridge, MA, 1990
• 5: Robert P. Futrelle , Ioannis A. Kakadiaris , Jeff Alexander , Catherine M. Carriero , Nikos Nikolakis , Joseph M. Futrelle, Understanding Diagrams in Technical Documents, Computer, v.25 n.7, p.75-78, July 1992 [doi>10.1109/2.144445]
• 6: John S. Gero, Artificial intelligence in engineering: design, Computational Mechanics, Inc., Billerica, MA, 1988
• 7: Goel, V. "Ill-structured rcprescntations" for ill-structured problems. In: Proc. Fourteenth Annual Conference of the Cognitive Science Society. (Bloomington, IN, 1992). Hillsdale. NJ: Erlbaum, pp. 844-849.
• 8: Goldschmidt, G. The dialectics of sketching. Creativity Research Journal. 4.2. (1991) pp. 122-143.
• 9: Golin, E., Reiss, S.P. The specification of visual language syntax. In: Proc. IEEE Workshop on Visual Languages. (1989). IEEE Press, pp. 105110.
• 10: Richard Helm , Kim Marruitt , Martin Odersky, Building visual language parsers, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.105-112, April 27-May 02, 1991, New Orleans, Louisiana, United States [doi>10.1145/108844.108860]
• 11: Pascal Van Hentenryck , Yves Deville , Choh-Man Teng, A generic arc-consistency algorithm and its specializations, Artificial Intelligence, v.57 n.2-3, p.291-321, Oct. 1992 [doi>10.1016/0004-3702(92)90020-X]
• 12: Hiroshi Ishii , Naomi Miyake, Toward an open shared workspace: computer and video fusion approach of TeamWorkStation, Communications of the ACM, v.34 n.12, p.37-50, Dec. 1991 [doi>10.1145/125319.125321]
• 13: David Kurlander , Eric A. Bier, Graphical search and replace, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.113-120, June 1988
• 14: David Kurlander , Steven Feiner, Interactive constraint-based search and replace, Proceedings of the SIGCHI conference on Human factors in computing systems, p.609-618, May 03-07, 1992, Monterey, California, United States [doi>10.1145/142750.143053]
• 15: Lakin. F., Wambaugh, J., Leifcr. L., Cannon. D., Steward, C. The electronic notebook: performing medium and processing medium. Visual Computer. 5,( 1989) pp. 214-226.
• 16: Larkin, J., Simon, H. Why a diagram is (somctimcs) worth 10,000 words. Cognitive Science, 11,(1987) pp. 65-99.
• 17: Negroponte, N. Recent advances in sketch recognition. In: Proc. AI7PS (American Federation of Information Processing) National Computer Conference. (Boston, MA, 1973). pp. 663-675.
• 18: Dean Rubine, Specifying gestures by example, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.329-337, July 1991
• 19: van Sommers, P. Drawing and Cognifion - Descriplive and experitnenrul studies of gruphic pro&don processes. Cambridge University Press, Camhridgc. England, 1984.
• 20: Wittenburg, K., Weitzman, L. Visual Grammars and Incremental Parsing. In: Proc. IEEE Workshop on Vi.sual Languages. (Skokie, IL, 1990), pp. 235-243.
• 21: Rui Zhao, Incremental recognition in gesture-based and syntax-directed diagram editors, Proceedings of the SIGCHI conference on Human factors in computing systems, p.95-100, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169103]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Paint systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Theory