Reading #12: Constellation models

None yet

Sharon describes a system of Constellation Models for Sketch Recognition. Constellation models describe sketches by the relationships between various objects. The objects themselves are recognized using very simple features: the bounding box position, diagonal length, and angle. Interactions between objects are also described with very simple features: the distance between the centers of the strokes, the shortest distance between any two endpoints and the shortest distance between any two points.

The feature vectors are used in a ML search through the space of possible labellings to find the assignment of labels to strokes that maximizes the probability of the labeling being correct given the training data. The search is broken into two steps: required components and then optional components, which drastically improves the search time. Separating the search into two steps drastically reduces the search space, by reducing the potential number of labels and also the number of candidate strokes.

I think this is a really neat approach. With respect to the current assignment, it would be pretty cool to break course of action diagrams into components like this. For example, to identify the echelon modifier and the strength modifier.

This approach is also somewhat similar to LADDER in that it is very important where objects are in relation to the other objects in the sketch. For example, a right eye will never be on the wrong side of the left eye. These constraints are not modeled explicitly, but are learned from the training data. The constellation model only understands positional relationships, as opposed to LADDER, which can model more complex relationships like parallel-ness.

Reading #11 LADDER

None yet

In this paper, Tracy unleashes LADDER unto the world. LADDER is a sketching language, designed to describe sketches as combinations of geometric primitives following geometric constraints. A primitive shape is one that cannot be broken down into simpler shapes, for example a line- or arc-segment. Geometric constraints define how shapes interact with the world and with each other. For example, a constraint might describe one line as horizontal or two lines as perpendicular.

LADDER builds complex shapes up from combinations of simpler shapes, simultaneously tackling the grouping and recognition problems. The downside to this approach is that putting a large number of primitives on the screen will cause an exponential runtime explosion, which has been known to injure innocent bystanders with recursively-enumerable shrapnel.

Tracy notes that LADDER works well for shapes that can be described in terms of geometric primitives, especially shapes that don't have too much detail. How, then, should we deal with detailed shapes? This is one area of consideration for the current assignment. Is there a general way of approaching detailed shapes, or does each shape require custom-tailored recognition techniques?

Reading #10: Herot

None yet

Christopher Herot implements the Sezgin/Stahovich corner finder more than 25 years before they do. Or did he? I see a citation by Negroponte and Taggart in '71 called HUNCH-an experiment in sketch recognition. Maybe it really was more like 30 years before and not necessarily Herot.

In my estimation, Herot's real contribution in this paper is the exploration of context and user-guided recognition. Herot discusses training the corner finder to be parameterized for a single user. For example, if the user draws a square and tells STRAIN that she has done so, then STRAIN can be adjusted until it finds exactly five corners (including both endpoints).

Herot talks about representing sketches in a context-free structure. This reminds me of LADDER, whose Lisp-like language can probably be parsed by a simple push-down automata. Okay, that's just a fancy way of saying that HUNCH and LADDER consider the context of a sketch in very similar ways.