624 #12 Constellation Models: Sharon

Comments

Introduction

This paper introduces Constellation Models (pictoral structure models) from computer vision as a method of sketch recognition. Constellation Models are used to identify the subcomponents of complex shapes, such as faces. This is done by using features of individual shapes as well as shared features between shapes to apply labels to shapes. In the case of recognizing parts of a face this would mean identifying that an ear has a relatively ear-like shape and that it is located a certain distance to the side of the eye and nose.

In order to make this method more efficient, as it is at heart an O(n^2) algorithm, Sharon defines certain sub-shapes as mandatory or optional. The mandatory shapes are a smaller subset of the total shapes and are identified first. Once the mandatory shapes are labeled they serve as a solid anchor for labeling the the optional shapes. The algorithm is further optimized by using a multipass algorithm that starts with a very optimistic threshold for identifying shapes and progressively gets lower, identifying more shapes as it progresses and narrowing down the search space as it goes.

Discussion

I like the Constellation method mostly because of the simplicity of the feature vector. The features calculated for each stroke are very simple but when used in conjunction with the relative positioning and shape of other strokes work as a good means of labeling. It is amazing to see some of the example sketches which have wildly varying sub-shapes, but due to their relative positioning all are identified correctly.

I do, however, have some problems with the paper as a whole. There does not seem to be much evaluation of recognition rates or failure points. There is a lot of discussion of the speed of the method, which is important, but what good is speed if you are mislabeling a large portion of the elements?

Another question is how this functions and deals with multi stroke shapes. Most of the example sub-shapes are single stroke, though there are a few that must be multi-stroke. It is not clear if these are grouped and labeled as a single shape or they are treated as multiple shapes of the same label.