Reading 20: Recognizing sketched multistroke primitives

Citation

Hammond, Tracy, and Brandon Paulson. "Recognizing sketched multistroke primitives." ACM Transactions on Interactive Intelligent Systems (TiiS) 1.1 (2011): 4.

PDF

Summary

This paper presents a novel way to detect multiple stroke primitives. The system achieves this by joining the strokes which may seem logically connected but are actually two different strokes. Once the strokes are combined then it is checked if the new shape match any primitive shape. The system uses low level recognizers such as Paleosketch to detect single stroke primitives against a database of known sketches. The flowchart for the algorithm is as follows:

Discussion

The first step is the graph building step. In this step a graph is built with each node representing an endpoint of a stroke and an edge representing a connection between the other end of the stroke or any other endpoint which is nearby but from another stroke. A special criterion is used to measure nearness of two nodes in the graph:

1) Euclidean distance between the endpoints divided by the total stroke length must be within a threshold.

2) Euclidean distance between the endpoints divided by the max of length or width of the bounding box must be within a threshold.

After the graph is built a graph searching algorithm is applied to get a strongly connected component from the graph. Tarjan's algorithm is used to find the strongly connected component in linear time. Tarjan's algorithm uses Depth First Search.

The strongly connected component is assumed to be a single stroke and the third step viz. stroke merging is applied. All the stroke endpoint that have an edge in the strongly connected component are connected to each other using a straight line.

Once we get a new combined shape low level recognizers are used to detect primitives. Some additional steps to remove false positives are also applied.