Recognizing Interspersed Sketches

Citation

T. A. Hammond and R. Davis, “Recognizing Interspersed Sketches Quickly,” pp. 157–166, 2009.

Link: http://dl.acm.org/citation.cfm?id=1555917

How often do we complete one sketch and then move on to the other while drawing complex shapes with multiple inter-related sketches? Natural sketching always imply completing some logical part of a sketch and then move to some other sketch that is related to the current sketch. So, there is lot of interspersing involved in a natural sketch.

In Sketch Recognition, if we enforce the user to draw a sketch completely before moving onto the next one, it takes away from the user the feel of natural drawing. This completely goes against the design principles of Sketch Recognition. Users must be allowed to draw sketches with minimum constraints. However, recognizing such sketches in Sketch Recognition often means considering all the possible combination of sub-shapes which is pretty time consuming(exponential) and might take forever thereby giving user a pretty bad experience (this, then, violates the other design principle of Sketch Recognition - Responsiveness). This paper came up with the idea that still runs in exponential time but is very responsive.

This paper solves the problem described above by introducing lot of new tweaks, and techniques enabling it to identify sub-shapes faster (in linear time - some cases; although worst case scenarios are still exponential) and with much less average space.

One of the methods by which it reduces the number of possible sub-shapes combination is by carrying out effective early sub-tree pruning. It also introduced the concept of Indexing that really helped in the further speed-up. It is done in essentially 3 steps:

1. Domain Independent Primitive Finding
2. Domain Independent Constraint Indexing
3. Domain Dependent Shape Formation

Thoughts and Future Work:

Though Indexing seemed to be a really good idea, but I didn't quite get hold of all the concepts explained in this paper. I would like to read more about this and look for possible enhancements and improvements.