Abstract

Online sketching is an incremental and dynamic process: sketches are drawn one stroke at a time and can be captured in devices such as Tablet PCs and pen based PDAs. This is unlike scanned documents or pictures which only capture the finished product. The dynamic properties of the sketching process contain valuable information that can aid recognition [1]. In particular, in a number of domains, the order in which users lay out strokes during sketching contains patterns and is predictable. We have presented ways of taking advantage of these regularities to formulate sketch recognition strategies [1]. Here, we describe a framework that can handle more complex user input. Specifically, we show how we can take advantage of the regularities in sketching even when users draw objects in an interspersed fashion (e.g., start drawing object A, draw B before fully completing A, come back and complete drawing A).

Sketching as a Stochastic Process

Previous work has shown that in certain domains stroke ordering follows predictable patterns and can be modeled as a Markovian stochastic process. Work in [1] shows how sketches of mechanical engineering drawings, course of action diagrams, emoticons and scenes with stick-figure can be modelled and recognized using Hidden Markov Models. In these domains, HMM-based modeling and recognition is possible because objects are usually drawn one after the other using consistent drawing orders. The HMM-based approach exploits these regularities to perform very efficient segmentation and recognition.

The HMM-based recognition algorithm scales linearly with the scene size, but requires each object to be completed before the next one is drawn. In certain domains, although there is a preferred stroke ordering, objects can be drawn in an interspersed fashion. For example, in the domain of circuit diagrams, people occasionally stop to draw wires connecting to the pins of a transistor before they complete the transistor. One way of thinking about such a drawing scenario is that, instead of a single Markov process, we have multiple processes that generate observations, and the task is to separate observations from these processes. We model such drawing behavior as a multimodal stochastic process that can switch between different individual Markov processes, each of which captures drawing orders for individual objects. Although the new approach can also be described as a HMM, it is more easily described and understood using its dual representation as a dynamic Bayesian net (DBN).

Approach

Our approach to modeling interspersed drawing behavior is general enough to allow an arbitrary number of objects in a domain to be drawn in an interspersed fashion, but in practice people usually intersperse at most two objects. For example, in the circuit diagrams, unlike other circuit components, transistors have three connection points (emmiter, collector, base) sometimes people draw the wires connecting to these points when the transistor is only partially drawn, causing interspersing of transistor and wire strokes. We have created a model specialized to handle interspersing of wires with other components in circuit diagram sketches. The figure below shows our model. A detailed description of the network can be found here.

Progress and Implementation Issues

We have collected examples of circuit diagrams from electrical engineers. We annotated the data and are currently working on an initial implementation of the above model. Currently, the model dynamics cause some numerical instability problems in the standard junction tree algorithm used for inference. We are working on ways of avoiding this problem by using numerically stable learning and inference algorithms.

References:

[1] Sezgin, T. M., & Davis, R. (2005). HMM­based efficient sketch recognition. In The Proceedings of the Conference, International Conference on Intelligent User Interfaces, San Diego CA January 2005