"Constellation Models for Sketch Recognition"

by D. Sharon and M. van de Panne

Summary

The authors introduces a vision-based sketch recognition approach. It utilizes the pictorial structure , or constellation, to recognize strokes in sketches of particular classes. The system makes two assumptions: (1) similar parts are drawn with similar strokes, (2) mandatory parts must have exactly one instance in the sketch, optional parts may have multiple instances in the sketch.

The constellation model consists features of individual object parts as well as features of pairs of parts. Individual features capture shape and global positions, whereas pairwise features (only computed when at least one part is mandatory) summarize relative positions. The sketch recognition process has two phases: (1) search the space of possible mandatory label assignments, (2) search for optional labels for remaining unlabelled strokes. Probability distribution is used.

The labels are searched by using a brand-and-bound tree for maximum likelihood (ML) searth. Mandatory parts are labelled first. A node in depth i of the tree is extended by evaluating all possible assignments of mandatory label i+1 to unlabelled strokes. To speed up the search, multipass thresholding and hard constraints are introduced. If a node's likelihood, as computed by its current partial set of label assignments, is lower than a threshold, that search branch is terminated. And hard constraints (e.g. nose should be above mouth) are relationships that must be met for some pairs, since all training examples have meet these relationships bewteen their corresponding parts.


Discussion

This approach recognizes objects based on relative locations of the strokes of sketches. However, the feature vector just uses bounding box of the strokes, which means that on the one hand, as long as the strokes can be fit into corresponding bounding box and maintain the specified relationship, the sketch will be recognized as an object no matter how each stroke is drawn; and on the other hand, even if the sketch looks the same, if each part is not drawn in the specified way (i.e. a nose drawn in one stroke and a nose drawn in 2 strokes are not the same), the whole sketch may not be able to successfully recognized.