SketchREAD: a multi-domain sketch recognition engine

ABSTRACT

We present SketchREAD, a multi-domain sketch recognition engine capable of recognizing freely hand-drawn diagrammatic sketches. Current computer sketch recognition systems are difficult to construct, and either are fragile or accomplish robustness by severely limiting the designer's drawing freedom. Our system can be applied to a variety of domains by providing structural descriptions of the shapes in that domain; no training data or programming is necessary. Robustness to the ambiguity and uncertainty inherent in complex, freely-drawn sketches is achieved through the use of context. The system uses context to guide the search for possible interpretations and uses a novel form of dynamically constructed Bayesian networks to evaluate these interpretations. This process allows the system to recover from low-level recognition errors (e.g., a line misclassified as an arc) that would otherwise result in domain level recognition errors. We evaluated Sketch-READ on real sketches in two domains--family trees and circuit diagrams--and found that in both domains the use of context to reclassify low-level shapes significantly reduced recognition error over a baseline system that did not reinterpret low-level classifications. We also discuss the system's potential role in sketch based user interfaces.

REFERENCES

• 1: Christine J. Alvarado , Randall Davis, Multi-domain sketch understanding, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 2: C. Alvarado. Sketch recognition and usability: Guidelines for design and development. In AAAI Fall Symposium on Pen-Based Interaction, 2004.
• 3: C.Alvarado and R. Davis. Resolving ambiguities to create a natural sketch based interface. In Proc. of IJCAI, 2001.
• 4: Eugene Charniak, Bayesian networks without tears: making Bayesian networks more accessible to the probabilistically unsophisticated, AI Magazine, v.12 n.4, p.50-63, Winter 1991
• 5: Kenneth D. Forbus , Jeffrey Usher , Vernell Chapman, Sketching for military courses of action diagrams, Proceedings of the 8th international conference on Intelligent user interfaces, January 12-15, 2003, Miami, Florida, USA [doi>10.1145/604045.604059]
• 6: Mark D. Gross , Ellen Yi-Luen Do, Ambiguous intentions: a paper-like interface for creative design, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.183-192, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237119]
• 7: T. Hammond and R. Davis. LADDER: A language to describe drawing, display, and editing in sketch recognition. In Proc. of IJCAI, 2003.
• 8: D. Koller and A. Pfeffer. Object-oriented bayesian networks. In Proc. of UAI, 1997.
• 9: James A. Landay , Brad A. Myers, Interactive sketching for the early stages of user interface design, Proceedings of the SIGCHI conference on Human factors in computing systems, p.43-50, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223910]
• 10: A. Chris Long, Jr. , James A. Landay , Lawrence A. Rowe , Joseph Michiels, Visual similarity of pen gestures, Proceedings of the SIGCHI conference on Human factors in computing systems, p.360-367, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332458]
• 11: J. V. Mahoney and M. P. J. Fromherz. Three main concerns in sketch recognition and an approach to addressing them. In AAAI Spring Symposium on Sketch Understanding, 2002.
• 12: Kim Marriott , Bernd Meyer , Kent B. Wittenburg, A survey of visual language specification and recognition, Visual language theory, Springer-Verlag New York, Inc., New York, NY, 1998
• 13: M. W. Newman, J. Lin, J. I. Hong, and J. A. Landay. DENIM: An informal web site design tool inspired by observations of practice. Human-Computer Interaction, 18(3):259--324, 2003.
• 14: Eric Saund , David Fleet , Daniel Larner , James Mahoney, Perceptually-supported image editing of text and graphics, Proceedings of the 16th annual ACM symposium on User interface software and technology, p.183-192, November 02-05, 2003, Vancouver, Canada [doi>10.1145/964696.964717]
• 15: 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]
• 16: M. Shilman, H. Pasula, S. Russell, and R. Newton. Statistical visual language models for ink parsing. In AAAI Spring Symposium on Sketch Understanding, 2002.
• 17: Thomas F. Stahovich , Randall Davis , Howard Shrobe, Generating multiple new designs from a sketch, Artificial Intelligence, v.104 n.1-2, p.211-264, Sept. 1998 [doi>10.1016/S0004-3702(98)00058-7 ]
• 18: Thomas M. Strat , Martin A. Fischler, Context-Based Vision: Recognizing Objects Using Information from Both 2D and 3D Imagery, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.10, p.1050-1065, October 1991 [doi>10.1109/34.99238 ]
• 19: A. Torralba and P. Sinha. Statistical context priming for object detection. In Proc. of ICCV, 2001.
• 20: L. Wu, S. L. Oviatt, and P. R. Cohen. Multimodal integration--a statistical view. IEEE Trans. on Multimedia, 1(4):334--341, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications

Additional 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:
Bayesian networks, input and interaction technology, intelligent UIs, pen-based UIs, sketch recognition