An efficient and general-purpose technique for grouping hand-drawn pen strokes into objects

Engineers use sketches in the early phases of design because their expressiveness and ease of creation facilitate creativity and efficient communication. Our goal is to build software that leverages these strengths and enables natural sketch-based human-computer interaction. Specifically, our work is focused on creating algorithms that group hand-drawn strokes into individual objects so that they can be recognized. Grouping strokes is a difficult problem. Many previous approaches have required the user to manually group the strokes. Others have used a search process, resulting in a computational cost that rises exponentially with the number of strokes in the sketch. In this dissertation we present a novel method for grouping strokes into objects based on a two-step algorithm that has a polynomial computational cost. In the first step, strokes are classified according to the type of object to which they belong, thus helping to create artificial separation between objects. In the second step, a pairwise classifier groups strokes of the same class into individual objects. Both steps rely on general machine learning techniques which seamlessly integrate spatial and temporal information, and which can be extended to new domains with no hand-coding. Our single-stroke classifier is the first in literature to perform multi-way classification to facilitate efficient grouping, and it performs as well as or better than previous classifiers on text vs. non-text classification. Our grouping algorithm correctly groups between 84% and 91% of the ink in diagrams from four different domains, with between 61% and 82% of objects being perfectly clustered. Our method runs in O( n2) time, where n is the number of points in the sketch. Real-world performance is improved with a conservative filter to eliminate consideration of distant strokes, and computation occurs incrementally as the sketch is constructed. Even without the filter, the computation for a large sketch containing over 700 strokes took less than 12% of the time required to draw the sketch. Experimental evaluation of our technique has shown it to be accurate and effective in four domains.