User-Directed Sketch Interpretation

Matt Notowidigdo & Robert Miller

Motivation
Structured diagrams (e.g. flow charts, module dependency diagrams) are commonly created using an editor such as Visio or XFig. These applications are powerful and expressive, but they are cumbersome to use, and they make it difficult to communicate drawing styles and shape sizes. Realizing the shortcomings of the user interfaces of these applications, recent research has focused on sketch understanding systems that recognize hand-drawn structured diagrams. These systems use stroke information collected on a tablet computer to accurately recognize parts of the diagram as the user sketches them. While these systems are much more natural to use than the menu- and mousedriven editors, they have subtle deviations from an actual pen-and-paper interface. For example, adding an arrowhead to a line segment that was drawn much earlier will likely confuse the system since the recognition uses temporal information. The user must delete the line segment and re-draw it with the arrowhead.


Figure 1: Communicating drawing styles in Microsoft Visio.

Approach
UDSI (User-Directed Sketch Interpretation) is a new system for creating structured diagrams that is based on understanding hand-drawn sketches of structured diagrams. Unlike the existing systems that require devices that can capture stroke information while the user sketches the diagram, UDSI uses scanned images of sketches. The user presents a scanned pen sketch of the diagram to the UDSI system and guides the application's interpretation of the sketch. The final interpretation is a structured diagram that can be incorporated into technical documents or refined in an existing structured graphics editor. The user can therefore iteratively create the diagram using a pure pen-and-paper interface until she is satisfied with the style, layout, and position of the components of the diagram.

The power of this system is that the user can use the pen-and-paper interface where it is natural and convenient (e.g. sizing shapes, placing arrows, and routing line segments) and then can use a mouse and keyboard where it is more efficient (e.g. typing in text, selecting colors, formatting fonts).

The UDSI system combines standard algorithms from the machine vision literature for filtering, segmentation, and shape detection [2] with novel algorithms for extracting text regions and recognizing arrowheads. These algorithms produce (possibly conflicting) interpretations of the scanned sketch that are combined using an elimination algorithm to produce not only the best candidate interpretation, but also multiple alternative interpretations. These alternatives are presented to the user through a novel user interface that allows the user to effectively select alternative interpretations that the system has generated.

References

[1] Matt Notowidigdo and Robert C. Miller. "Off-line Sketch Interpretation." Proceedings of AAAI Fall Symposium on Making Pen-Based Interaction Intelligent and Natural, October 2004.

[2] Matthew Notowidigdo. User-Directed Sketch Interpretation. MEng thesis, Massachusetts Institute of Technology, June 2004.