skip to main content
10.5555/1555880.1555917guideproceedingsArticle/Chapter ViewAbstractPublication PagesgiConference Proceedingsconference-collections
research-article
Free access

Recognizing interspersed sketches quickly

Published: 25 May 2009 Publication History

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]
{AD04} Alvarado C., Davis R.: Sketchread: A multi-domain sketch recognition engine. In Proceedings of UIST '04 (2004), pp. 23--32.
[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]
{BP97} Bimbo A. D., Pala P.: Visual image retrieval by elastic matching of user sketches. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(2) (1997), 121--132.
[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]
{Ham07} Hammond T.: Ladder: A perceptually-based language to simplify sketch recognition user interface development. PhD Thesis, Massachusetts Institute of Technology, 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]
{LTC00} Lank E., Thorley J. S., Chen S. J.-S.: An interactive system for recognizing hand drawn UML diagrams. In Proceedings for CASCON 2000 (2000), p. 7.
[15]
{LVB*93} Lades M., Vorbruggen J., Buhmann J., Lange J., Von Der Malsburg C., Wurtz R., Konen W.: Distortion invariant object recognition in the dynamic linkarchitecture. IEEE Transactions on Computers 42(3) (March 1993), 300--311.
[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]
{Rub91} Rubine D.: Specifying gestures by example. In Computer Graphics (1991), vol. 25(4), pp. 329--337.
[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]
{Sez06} Sezgin T. M.: Sketch Interpretation Using Multiscale Stochastic Models of Temporal Patterns. PhD thesis, Massachusetts Institute of Technology, May 2006.
[21]
{SM92} Stein F., Medioni G.: Structural indexing: Efficient 3-d object recognition. IEEE Transaction on Pattern Analysis And Machine Intelligence (1992), 125--125.
[22]
{SSD01} Sezgin T. M., Stahovich T., Davis R.: Sketch based interfaces: Early processing for sketch understanding. In The Proceedings of 2001 Perceptive User Interfaces Workshop (PUI '01) (Orlando, FL, November 2001).
[23]
{WWL07} Wobbrock J., Wilson A., Li Y.: Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes. In Proceedings of UIST (2007).

Cited By

View all
  • (2018)$QProceedings of the 20th International Conference on Human-Computer Interaction with Mobile Devices and Services10.1145/3229434.3229465(1-12)Online publication date: 3-Sep-2018
  • (2018)The role of grouping in sketched diagram recognitionProceedings of the Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering10.1145/3229147.3229160(1-12)Online publication date: 17-Aug-2018
  • (2011)Recognizing sketched multistroke primitivesACM Transactions on Interactive Intelligent Systems10.1145/2030365.20303691:1(1-34)Online publication date: 31-Oct-2011
  • Show More Cited By

Index Terms

  1. Recognizing interspersed sketches quickly

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    GI '09: Proceedings of Graphics Interface 2009
    May 2009
    257 pages
    ISBN:9781568814704

    Sponsors

    • The Canadian Human-Computer Communications Society / Société Canadienne du Dialogue Humaine Machine (CHCCS/SCDHM)

    Publisher

    Canadian Information Processing Society

    Canada

    Publication History

    Published: 25 May 2009

    Qualifiers

    • Research-article

    Acceptance Rates

    GI '09 Paper Acceptance Rate 28 of 77 submissions, 36%;
    Overall Acceptance Rate 206 of 508 submissions, 41%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)13
    • Downloads (Last 6 weeks)7
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2018)$QProceedings of the 20th International Conference on Human-Computer Interaction with Mobile Devices and Services10.1145/3229434.3229465(1-12)Online publication date: 3-Sep-2018
    • (2018)The role of grouping in sketched diagram recognitionProceedings of the Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering10.1145/3229147.3229160(1-12)Online publication date: 17-Aug-2018
    • (2011)Recognizing sketched multistroke primitivesACM Transactions on Interactive Intelligent Systems10.1145/2030365.20303691:1(1-34)Online publication date: 31-Oct-2011
    • (2010)Feature extraction and classifier combination for image-based sketch recognitionProceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium10.5555/1923363.1923375(63-70)Online publication date: 7-Jun-2010

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media