Constellation

Constellation Models for Sketch Recognition - D. Sharon and M. van de Panne

Sharon and van de Panne use a constellation model to recognize groups of shapes. Individual objects are represented by a feature vector consisting of the x and y coordinates of the center of the bounding box and the length and angle of the diagonal of the bounding box. Pairs of parts are represented by a feature vector consisting of the relative change in x and y coordinates, the minimum distance between an end point of the first object to any point in the second, and the minimum distance between an end point of the second object to any point in the first. However, since this model does not scale well, parts are subdivided into two groups, mandatory and optional. Individual features are computed on all parts, while pair features are computed only if one of the pair is a mandatory part. Recognition is performed in two stages. First mandatory parts are found, then unlabeled strokes are fit to optional parts. Models are learned using probabilistic methods. From labeled examples, the mean and covariance are determined for the feature vectors of each modeled class. Strokes are labeled as various mandatory and optional parts by determining the maximum likelihood labeling. Using branch-and-bound, the algorithm assigns mandatory labels in sequence to the stroke that is most likely of that label. After training on 50-60 examples for each class, recognition is tested on several examples. Recognition generally runs in a relatively short time period.

Discussion - Recognition accuracy is surprisingly missing, while the results focus on the time taken during successful recognitions. It is also unclear whether all five models are considered for assignment of labels to a new sketch or if only the model corresponding to the class of sketch is used. If the second is the case, users must identify what kind of sketch has been drawn before the system can label the parts, and user labeling of the components doesn't seem to be too strenuous of an additional task.