Reading 22: HMM-based efficient sketch recognition

Citation

Sezgin, Tevfik Metin, and Randall Davis. "HMM-based efficient sketch recognition." Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 2005.

PDF

Summary

This paper presents a novel way of doing sketch recognition by considering it as an interactive process where strokes are entered one after another. The system captures that stroke ordering to draw a complex shape tell a lot about what shape is being drawn. Earlier sketch recognition systems only used geometric or gesture based methods to conclude what shape is being drawn. The authors conducted a user study and found out that most people follow very strict stroke ordering when drawing a complex system.

Sketch recognition involves grouping strokes that constitute the same object (segmentation) and determining the object class for each group (recognition). The framework the authors introduce in this paper provides a mechanism for capturing an individual's preferred stroke ordering during sketching, and uses it for efficient segmentation and recognition of hand-sketched objects in polynomial time.

Discussion

The system uses Hidden Markov Models to model individual shapes. When a stroke is input the system checks among the trained HMM models to give probabilities of the predicted shapes. The shape with the maximum probability is chosen. The system is incremental, as the user adds more strokes to the sketch, the new sketch is again run through the trained HMM models to get the new classification probabilities for the complex shape.

The system also differs from numerous sketch recognition systems by its ability to do recognition with only polynomial time and space complexity, and by its utilization of drawing order for capturing and modeling user sketching styles.