Recognizing interspersed sketches quickly

ABSTRACT

Sketch recognition is the automated recognition of hand-drawn diagrams. When allowing users to sketch as they would naturally, users may draw shapes in an interspersed manner, starting a second shape before finishing the first. In order to provide freedom to draw interspersed shapes, an exponential combination of subshapes must be considered. Because of this, most sketch recognition systems either choose not to handle interspersing, or handle only a limited pre-defined amount of interspersing. Our goal is to eliminate such interspersing drawing constraints from the sketcher. This paper presents a high-level recognition algorithm that, while still exponential, allows for complete interspersing freedom, running in near real-time through early effective sub-tree pruning. At the core of the algorithm is an indexing technique that takes advantage of geometric sketch recognition techniques to index each shape for efficient access and fast pruning during recognition. We have stresstested our algorithm to show that the system recognizes shapes in less than a second even with over a hundred candidate subshapes on screen.

REFERENCES

• 1: Christine Alvarado , Randall Davis, SketchREAD: a multi-domain sketch recognition engine, 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.1029637]
• 2: {AKJ02} Antani S., Kasturi R., Jain R.: A survey on the use of pattern recognition methods for abstraction, indexing, and retrieval of images and video. Pattern Recognition 35 (2002), 945--965.
• 3: {Alv00} Alvarado C.: A Natural Sketching Environment: Bringing the Computer into Early Stages of Mechanical Design. Master's thesis, MIT, 2000.
• 4: Alberto Del Bimbo , Pietro Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.121-132, February 1997 [doi>10.1109/34.574790]
• 5: {CGFJ02} Caetano A., Goulart N., Fonseca M., Jorge J.: JavaSketchlt: Issues in sketching the look of user interfaces. Sketch Understanding, Papers from the 2002 AAAI Spring Symposium (2002).
• 6: {FH01} Friedman-Hill E.: Jess, the java expert system shell. http://herzberg.ca.sandia.gov/jess, 2001.
• 7: {Go172} Goldmeier E.: Similarity in visually perceived forms. In Psychological Issues (1972), vol. 8:1.
• 8: Tracy Anne Hammond , Randall Davis, Ladder: a perceptually-based language to simplify sketch recognition user interface development, Massachusetts Institute of Technology, Cambridge, MA, 2007
• 9: {HD02} Hammond T., Davis R.: Tahuti: A geometrical sketch recognition system for UML class diagrams. AAAI Spring Symposium on Sketch Understanding (March 25--27 2002), 59--68.
• 10: {HD05} Hammond T., Davis R.: LADDER, a sketching language for user interface developers. Elsevier, Computers and Graphics 28 (2005), 518--532.
• 11: {HGDS02} Hammond T., Gajos K., Davis R., Shrobe H.: An agent-based system for capturing and indexing software design meetings. In Proceedings of International Workshop on Agents In Design, WAID '02 (2002).
• 12: {KKOH92} Kato T., Kurita T., Otsu N., Hirata K.: A sketch retrieval method for full color image databases - query by visual example. 11th IAPA International Conference on Pattern Recognition (1992), 530--533.
• 13: {Lon01} Long A. C.: Quill: a Gesture Design Tool for Pen-based User Interfaces. EECS department, computer science division, U. C. Berkeley, Berkeley, California, December 2001.
• 14: Edward Lank , Jeb S. Thorley , Sean Jy-Shyang Chen, An interactive system for recognizing hand drawn UML diagrams, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.7, November 13-16, 2000, Mississauga, Ontario, Canada
• 15: M. Lades , J. C. Vorbruggen , J. Buhmann , J. Lange , C. von der Malsburg , R. P. Wurtz , W. Konen, Distortion Invariant Object Recognition in the Dynamic Link Architecture, IEEE Transactions on Computers, v.42 n.3, p.300-311, March 1993 [doi>10.1109/12.210173]
• 16: {MF02} Mahoney J. V., Fromherz M. P. J.: Three main concerns in sketch recognition and an approach to addressing them. In Sketch Understanding, Papers from the 2002 AAAI Spring Symposium (Stanford, California, March 25--27 2002), AAAI Press, pp. 105--112.
• 17: {QS06} Quest Software I.: JProbe. website, http://www.quest.com/jprobe, 2006.
• 18: Dean Rubine, Specifying gestures by example, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.329-337, July 1991
• 19: {SAB97} Stevens M. R., Anderson C. W., Beveridge J. R.: Efficient indexing for object recognition using large networks. In Proceedings of IEEE International Conference on Neural Networks (1997).
• 20: Tevfik Metin Sezgin , Randall Davis, Sketch interpretation using multiscale stochastic models of temporal patterns, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 21: Fridtjof Stein , Gérard Medioni, Structural Indexing: Efficient 3-D Object Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.125-145, February 1992 [doi>10.1109/34.121785]
• 22: 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]
• 23: 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)