Grouping Strokes into Shapes in Hand-Drawn Diagrams

Eric Jeffrey Peterson, Thomas F. Stahovich, Eric Doi, Christine AlvaradoAAAI 2010 · DOI

Abstract

Sketch understanding—the automated conversion of hand-drawn strokes into structured digital representations—is often hindered by the lack of explicit metadata in natural drawing. This paper presents a robust two-stage approach that classifies individual strokes into functional categories before using a pairwise classifier to group them into distinct objects. This method avoids the "chicken-and-egg" problem of simultaneous grouping and recognition, achieving high accuracy in unconstrained sketching environments like digital circuits and family trees.

Introduction

When users draw on digital tablets, they typically do not provide explicit signals to indicate the start or end of a shape. This lack of structure creates a significant challenge for computer vision: a system cannot easily recognize a shape without knowing which strokes belong together, yet it cannot group strokes accurately without knowing the intended shape. Traditional systems often bypass this by requiring "single-stroke" symbols or artificial pauses. This research addresses the challenge of unconstrained sketching, where strokes may overlap spatially or be interleaved temporally, making traditional clustering algorithms fail.

Methodology

The proposed system utilizes a two-step pipeline that treats stroke grouping as a classification task rather than an exhaustive search problem.

  1. Single-Stroke Classification: Individual strokes are analyzed using 27 features covering size, location, shape (e.g., curvature, self-intersection), kinematics (pen speed), and context (how it intersects other strokes). An AdaBoost classifier with decision trees labels each stroke (e.g., text, gate, or wire in a circuit domain).
  2. Stroke Grouping: The system then attempts to group strokes of the same class. A second AdaBoost classifier evaluates pairs of strokes to determine if they belong to the same object. The system uses a "chaining" logic: if stroke A is joined to B, and B is joined to C, all three form one cluster. To handle complex drawings, they classify pairs into three categories: "don't join," "near join" (physically close), and "far join" (strokes that belong to the same object but are separated by intermediate strokes).
Example of a hand-drawn digital circuit (a) and its decomposition into classified and grouped components (b).

Experimental Setup

The researchers evaluated their system on two distinct domains to prove its flexibility:

  • Digital Circuits: 192 sketches collected from 24 students. These diagrams are complex, containing an average of 51 strokes across wires, text, and logic gates.
  • Family Trees: 27 sketches from the EtchaSketches corpus. These were noted as being "messier" and more stroke-heavy (average of 61 strokes), consisting of "people" (boxes/ellipses), "links" (lines/arrows), and text.

Results and Discussion

The system demonstrated state-of-the-art performance for the time, particularly in its ability to distinguish text from non-text elements. In digital circuits, it achieved 97.2% accuracy in text vs. non-text classification, significantly outperforming commercial tools like Microsoft’s InkAnalyzer (63.4%) at the time.

Comparison of text vs. non-text classification accuracy between the proposed method and existing tools.

Key insights include the effectiveness of classification as a pre-filter. By removing "wire" strokes from the search space, the "gate" strokes become spatially and temporally isolated, making clustering much less computationally expensive than a global search. Furthermore, the researchers identified that intersection nuance—distinguishing between where strokes intersect (endpoint-to-endpoint vs. midpoint-to-endpoint)—is critical for accurate classification.

In terms of grouping success, the algorithm correctly clustered 91.4% of the ink in circuit diagrams. Perhaps more impressively, 79.5% of all shapes in those diagrams were "perfectly clustered," meaning every single stroke was correctly assigned with no extras.

Conclusion

The two-stage classification and grouping approach provides a flexible, data-driven framework for sketch understanding. While performance was slightly lower on the messier Family Tree dataset (86% ink grouped correctly), the results in the circuit domain validate the robustness of the method for structured diagrams. Future work will focus on refining the "far join" logic to better handle very complex, interleaved shapes and optimizing the pairwise classification for real-time performance on extremely large sketches.

Summary updated

BibTeX
@inproceedings{peterson2010grouping,
  author = {Eric Jeffrey Peterson and Thomas F. Stahovich and Eric Doi and Christine Alvarado},
  title = {{Grouping Strokes into Shapes in Hand-Drawn Diagrams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7650},
}

Loading related content...

Figure