Paper Review #12: HMM-Based Efficient Sketch Recognition

1. Paper Bibliography

• Title: HMM-Based Efficient Sketch Recognition

• Authors: Sezgin, Tevfik Metin, and Randall Davis.

• Publication: Proceedings of the 10th international conference on Intelligent user interfaces. ACM, 2005.

2. Summary

• How viewing sketching as an interactive process
• User study: People have preferred ways of drawing in certain domain.
• Contribution
• Polynomial time algorithm for sketch recognition and segmentation
• Efficient sketch recognition, segmentation and classification

3. Terminology

• Segmentation: Grouping strokes which constitutes the same object
• Classification: Determining which object each group of strokes represent
• Labeling: Assigning labels to components of a recognized object

4. Details

• Capture an individual's preferred stroke ordering 
• Vertical, Horizontal, Positive slope and Negative slope
• sketching = incremental & interactive process
• Viterbi: Compute the best sequence of HMM state transition for generating O
• Baum-Welch algorithm: Estimate HMM parameter (probabilities of transition, observation and start)
• Encoding
• convert strokes into geometric primitives
• Modeling with fixed input length HMMs
• Modeling using HMMs with variable length training data

5. Evaluation

• Evaluation of the HMM-based recognition with real data
• Fixed length & Variable length (slightly better)
• Running time comparison to a baseline method
• Baseline: feature-based recognizer