Three main concerns

Three main concerns in sketch recognition and an approach to addressing them - James V. Mahoney and Markus P. J. Fromherz

Mahoney and Fromherz examine the segmentation of strokes into lines and curves useful for recognition. For the classification of strokes into the components of stick figures, segmentation ambiguity (lack of a 1-1 mapping of strokes and possible segments) often occurs due to small gaps between strokes, overlapping of strokes, crossing strokes, or interaction with background strokes. They seek to correct these problems by creating multiple interpretations either joining or dividing strokes so that the newly created strokes. These alternate interpretations can greatly improve the sub-graph matching recognition method used to classify components. Their method uses two stages to determine possible alternate graphs. The first is graph elaboration composed of 5 parts. Proximity linking joins small gaps. Link closure replaces connections or intersections with links. Virtual junction splitting divides a stroke near a non-connected endpoint and inserts links. Spurious segment jumping inserts links around small, possibly erroneous strokes. Lastly, continuity tracing adds a connected interpretation for segments that could connect smoothly.

The second stage attempts to classify strokes. First, strokes are preprocessed and divided at corners, then passed through the first stage, creating an input graph of connected segments and segment interpretations. Next, the input is compared models of sketches describing a connected graph of that class including optional segments. This is done using subgraph matching, that is the input graph is checked for a subgraph whose components match the components of the model graph, as well as matching characteristics of the model components (relative length, etc). Subgraph matching is solve by translating it to a constraint satisfaction problem. The CSP has several constraints not translated from the graph including 1-1 matching of data to model components, minimum total link length, optimal proportions, and maximal part count (as many non-optional parts assigned to data components).