Home

Sketch-Based Recognition System for General Articulated Skeletal Figures

Sketch-Based Recognition System for General Articulated Skeletal Figures

Shane Zamora

Overview

We present a new sketch-based recognition framework for detecting general articulated figures in sketched scenes. Our recognizer is largely based on related work in the field by Mahoney and Fromherz [1] that has been shown to be effective for detecting a single form of sketched skeletal figure in a scanned document. Our system generalizes their approach for detecting a human stick figure to the more general skeletal figure, defined as any general connected and articulated figure consisting of lines and ellipses. While our initial inspiration was to create a recognition system to detect more drawing styles of stick figures from the one style of stick figure supported in [1], our skeletal figure definition is general enough to be able to detect symbols from a variety of domains, including those with symbols that are not articulated, such as cars, elephants, cats, geometric shapes, arrows, letters and characters, and more.

Details

Our recognition algorithm is based on solving the graph isomorphism problem. A graph called the data graph is generated from the set of input strokes through a process called graph elaboration, which translates the spatial and visual structure of the sketched scene into edge connectivity relations and alternate structure interpretations. The templates that define symbols for the system to recognize describe the model graph, a tree of lines and ellipses with edges that define connectivity relations between primitives and groupings of such edges that define joints in the articulated figure. Our framework defines the symbols that should be recognized using two structures: figure targets and templates.


Figure targets outline the class of figure that should be recognized by the system (e.g. Human, Cat, Elephant, Car, etc.). Figure targets define a set of key points on the class of figure called anchor points. These anchor points outline information about the class of figure that will be universal amongst all of the styles of drawing that figure; for example, a human stick figure may have anchor points such as "Top of Head", "Base of Neck", "Right Knee" and "Left Elbow". Finally, these anchor points are connected in a spanning tree that is meaningful to the skeletal structure of the figure; on a human figure, the hip anchor point would connect to the knee, which would connect to the ankle, etc.

Where figure targets outline the class of figure that is to be recognized, templates outline a particular drawing style of that figure. For example, a human figure target may have one template that uses a single line as the torso, where another template may use an ellipse for the torso. Templates are assigned a single figure target to represent, and define a connected system of lines and ellipses. These lines and ellipses are then labeled with a set of anchor labels from the set of anchor points from the figure target. The model graph tree for a given figure the system will recognize is directly derived from the template.


Once the graph isomorphism (aka subgraph matching) algorithm finds an instance of a given template in the data graph, the drawn strokes that make up the recognized figure are annotated with the anchor points of the appropriate figure target. In this framework, an application using our recognition system will be able to ignore the particular drawing style used to recognize, for example, a human stick figure, and work only with the information from a human figure being drawn. Supporting alternate drawing styles for given classes of figures thus require no additional code on the part of the application developer. Our system also provides a GUI based template and figure target development environment that allows users to create figure targets and templates for new symbols within minutes.


(Left) The fully elaborated data graph of a sketched scene of various lines and ellipses. Green lines are line segments, and red ellipses are ellipses. Light blue lines are connectivity relations and configurations of dark blue and red lines represent alternate structures and mutual exclusion contraints placed within the data graph. (Right) The human stick figure our system recognized from the sketched scene.

References

[1] Mahoney, James. V., Fromherz, Markus. P. J.: Handling ambiguity in constraint-based recognition of stick figure sketches. In Document Recognition and Retrieval IX (2001), vol. 4670, pp. 89–100.