Wolin, Aaron David (2010-05). Segmenting Hand-Drawn Strokes. Master's Thesis. Thesis uri icon


  • Pen-based interfaces utilize sketch recognition so users can create and interact with complex, graphical systems via drawn input. In order for people to freely draw

    within these systems, users' drawing styles should not be constrained. The low-level techniques involved with sketch recognition must then be perfected, because poor

    low-level accuracy can impair a user's interaction experience.

    Corner finding, also known as stroke segmentation, is one of the first steps to

    free-form sketch recognition. Corner finding breaks a drawn stroke into a set of primitive symbols such as lines, arcs, and circles, so that the original stoke data

    can be transformed into a more machine-friendly format. By working with sketched primitives, drawn objects can then be described in a visual language, noting what

    primitive shapes have been drawn and the shapes? geometric relationships to each


    We present three new corner finding techniques that improve segmentation accuracy. Our first technique, MergeCF, is a multi-primitive segmenter that splits drawn

    strokes into primitive lines and arcs. MergeCF eliminates extraneous primitives by merging them with their neighboring segments. Our second technique, ShortStraw,

    works with polyline-only data. Polyline segments are important since many domains use simple polyline symbols formed with squares, triangles, and arrows. Our ShortStraw

    algorithm is simple to implement, yet more powerful than previous polyline work in the corner finding literature. Lastly, we demonstrate how a combination technique can be

    used to pull the best corner finding results from multiple segmentation algorithms. This combination segmenter utilizes the best corners found from other segmentation techniques, eliminating many false negatives (missed primitive segmentations) from the final, low-level results.

    We will present the implementation and results from our new segmentation techniques, showing how they perform better than related work in the corner finding field. We will also discuss limitations of each technique, how we have sought to overcome those limitations, and where we believe the sketch recognition subfield of corner finding is headed.

publication date

  • May 2010