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.

624 #11 LADDER: Hammond

Comments

Drew

Introduction

LADDER is a system for describing and recognizing hand drawn shapes using a human readable geometric description language. This is meant to allow system designers to create sets of shapes that can be recognized as part of a visual grammar, that is a certain domain. In addition to shape recognition, LADDER also allows designers to describe how recognized shapes should be displayed, what actions can be performed on them or what actions they perform on other shapes.

Shape structures can be made up of basic recognition shapes, such as lines, poly-lines, circles etc. as well as previously defined shapes. Constraints can then be placed on the relationships between these subshapes.

The system uses these descriptions in a bottom up approach, starting with identifying basic shapes from strokes, constructing many higher level shapes from each basic shape. Eventually each shape is part of one high level shape.

Discussion

LADDER is very useful for domains with simple geometric shapes that are easy to describe either individually or as part of a hierarchy. This becomes problematic with more complex individual shapes that are hard to describe. It might be interesting, as mentioned in LADDER's future work, if a designer could automatically generate a LADDER description of a complex shape, both to make it easier on the designer and to show which shapes might be problematic for LADDER to describe at all. In such cases it would seem useful if a designer could use some other manner of recognition to describe a particular shape, but could then use that shape in a later LADDER description. This way LADDER could incorporate more complex shapes while still keeping the geometric descriptions to create composite complex shapes.

The question we all want answering....

"Does the generative annealing activation information composition visualization in the hot space, driven by information semantics, a user-interest model, and a res- ponsive crawler, help people to be creative?"

From Provocative Stimuli, Kerne et all, CHI 2011

624 #10 Graphical Input Through Machine Recognition of Sketches: Herot

Comments

Chris

Introduction

In this paper Herot discusses the HUNCH system, a hierarchy of inference programs for sketch recognition. HUNCH works by taking input data and running several layers of inference programs on top of that data, from basic line and curve recognizers, to line latching, overtracing and finally high level inferences such as 3d object inference or floor plan recognition. HUNCH encountered many problems with specific modules, such as the curve recognizer CURVIT and the line recognizer with endpoint latching STRAIT, however due to is modular design some of these inferences could be thrown out and higher level inferences could still be made to a certain extent.

Discussion

The most important idea from this paper is the hierarchy of recognizers that provide a chain of recognition and alternate interpretations of the same starting data. If a system is going to be interactive, multiple interpretations must be calculated while the user is entering a sketch so that the user is given options for correcting the interpretation if necessary. This also allows the programmer to add new recognition contexts to the system simply by adding a module that understands that context. In many ways this is what we are doing with Paleo for our truss recognition project.

624 #9 PaleoSketch: Paulson

Comments

Chris

Introduction

PaleoSketch is a primitive shape recognizer and beautifier. It supports recognition of several basic geometric types: Lines, Polylines, Cirles, Ellipses, Arcs, Curves, Spirals and Helixes. The recognizer takes input strokes and gives several possible interpretations depending on how ambiguous the stroke is. Paleo uses a few new features for recognition, mostly to distinguish between Polylines and Curves. These features are normalized distance between direction extremes (NDDE) and direction change ratio (DCR), both of which are used to find spikes in the direction graph that would differentiate between a Polyline and Curve.

Discussion

Paleo is very accurate at classification (99.89%) although it does not always present the correct interpretation as the primary interpretation. Still an overall recognition rate of 98.56% is very impressive and shows that Paleo can form a very solid basis for higher level recognition systems. I find this system to be a lot more useful for actual sketch recognition than most of the previous papers we have read. I understand that most of those are gesture recognizers, and that is all very well, but Paleo is much more relevant for complete sketch recognition.

624 #8 $N Multistroke Recognizer - Anthony

Introduction

$N is a recognizer based on wobbrock's $1 recognizer, extending it and giving it several new abilities. The most important extension is that $N is now a multistroke recognizer. This is achieved by connecting the endpoints of the multiple strokes together to form a unistroke and then interpolating all the different possible ways the multiple strokes could be connected. This in essence treats the user's whole gesture, both when their pen is drawing on the screen and when it is in the air, as a unistroke. The second improvement is that $N introduces bounded rotation invariance so that it can distinguish between gestures that have been rotated if necessary. The third change is that $N can now recognize the difference between 1D and 2D gestures. Finally there are a few optimizations that are included, the first is using the start angle of the gesture to constrain the search space and the second is by using the number of strokes to to further restrict the search space.

Discussion

$N adds several useful changes to $1 that makes $1 more flexible without losing very much of the simplicity of $1. What i like the most is the way in which they decided to bring multistroke gestures down to a single stroke in order to use the existing methods of $1 to analyze them.

624 #7 Sketch Based Interfaces - Sezgin

Introduction

The Segzin Stahovich Davis system is meant to take sketch data and clean it up and recognize basic shapes within a drawing. There are several steps to this process. The first is vertex detection which requires filtering out noise to find vertexes on straight edge objects. The second is detecting curves and drawing/approximating them with bezier curves. Finally the figures are beautified and then basic object recognition.

Discussion

This paper gives a fair amount of description about the vertex and curve detection processes, however it does not give very many specifics on beautification or recognition or for that matter what sort of recognition applications this system would be used for. I can only assume it was an early paper that is further expounded upon later, or that most of the other concepts were explored sufficiently in the related work.