Recognizing Interspersed Sketches Quickly

Bibliographical Information:
Tracy A. Hammond and Randall Davis. 2009. Recognizing interspersed sketches quickly. In Proceedings of Graphics Interface 2009 (GI '09). Canadian Information Processing Society, Toronto, Ont., Canada, Canada, 157-166.

URL:
http://dl.acm.org.lib-ezproxy.tamu.edu:2048/citation.cfm?id=1555917

One of the biggest challenges in sketch recognition is in the recognition of of "interspersed sketches", which consists whose shapes are drawn out of order from other shapes. In the drawing of two triangles, for instance, one may choose to draw the first two sides before drawing a third. This proves challenging for many recognition systems, with algorithms that end up running in exponential time. By coming up with a system of constraints in which to look, this recognition system greatly reduces the runtime for recognition that supports interspersed sketch drawing, even if it still runs in exponential time. This algorithm uses an indexing technique that uses geometric recognition for the purposes of ranking and pruning.

The geometric constraints can be classified in four different categories: Orientation-dependent constraints (such as "horizontal", "vertical", etc.), Orientation-independent constraints ("acute", "bisects", "same side"), Composite constraints ("smaller", "centered left"), and "other" ("equal", "greater than"). Signal noise, while significant, is handled by the recognition system itself. The template shapes are typically described without this signal noise, so when the user shape is recognized, there is no signal noise being accounted for either. Additional noise can occur if the user takes more than one stroke to draw a shape. This is alleviated by splicing together bigger shapes from smaller strokes if they correctly match a given shape. The system also uses a collection of constraints, each constraint with its own error tolerance that will cause the recognition to be discarded if it lies outside of this constraint. There are two types of "requirements" that must be satisfied. Not only must a shape be "geometrically satisfied", which is the constraints that are purely geometric based, but also "perceptually satisfied", which can be described as the set of constraints that any regular human would be able to perceive. For instance, a stroke that is "to the left" of another one may be geometrically satisfied if the shape is even one pixel to the left of the original, but a human would very rarely ever make the same call if two shapes are presented with this small a discrepancy. Making sure a human can perceive these constraints is key to making sure they are meaningful in sketch recognition. The constraints were both calculated and experimented with users.

The indexing algorithm to help rank these constraints and how they score is divided into three sections: domain-independent primitive finding, domain-independent constraint indexing, and domain-dependent shape formation. The first breaks down the shapes given to primitives such as arcs, ellipses, and circles, and corners, the last of which is found via speed and curvature data. The second uses indexing that occurs only once for every shape, such that the algorithm does not impose too many rules to the shapes it recognizes. Each shape is only indexed based on its own constraints and NOT to the constraints of the shapes around it. The final section attempts to group together indexed shapes into compound or more complex versions of the primitives. The system assigns recognized shapes into a limited number of "slots" which are then used for comparison and possible combination. The constraints applied to the compound shapes then dictate whether the shapes in the slots are removed, remain, or exchanged. This system also makes extensive use of pruning to prevent unnecessary branching, which cuts down the run time drastically.

I think that this constraint-based limitation is an interesting alternative implementation to the problem of interspersed-shape sketch recognition. This is especially useful in educational situations, where the user is expected to be a student who is not an expert in their field of study and thus are unlikely to have developed a standard, industry-followed order of sketch recognition, if there is even any one at all. In the field of education, sketch recognition needs to be highly flexible to allow different students to learn in their own way, so in this case the application of interspersed-shape sketching can prove very useful.