Sketch Recognition Lab

Sketch recognition is the automated recognition of hand-drawn di-agrams. When allowing users to sketch as they would naturally, users may draw shapes in an interspersed manner, starting a sec-ond shape before finishing the first. In order to provide freedom to draw interspersed shapes, an exponential combination of subshapes must be considered. Because of this, most sketch recognition sys-tems either choose not to handle interspersing, or handle only a limited pre-defined amount of interspersing. Our goal is to elimi-nate such interspersing drawing constraints from the sketcher. This paper presents a high-level recognition algorithm that, while still exponential, allows for complete interspersing freedom, running in near real-time through early effective sub-tree pruning. At the core of the algorithm is an indexing technique that takes advantage of geometric sketch recognition techniques to index each shape for ef-ficient access and fast pruning during recognition. We have stress-tested our algorithm to show that the system recognizes shapes in less than a second even with over a hundred candidate subshapes on screen. Index Terms: H5.2 [Information interfaces and presentation]: User Interfaces- Graphical user interfaces