SketchREAD: A Multi-Domain Sketch Recognition Engine

Bibliographical Information:
Christine Alvarado and Randall Davis. 2004. SketchREAD: a multi-domain sketch recognition engine. In Proceedings of the 17th annual ACM symposium on User interface software and technology (UIST '04). ACM, New York, NY, USA, 23-32. DOI=10.1145/1029632.1029637 http://doi.acm.org.lib-ezproxy.tamu.edu:2048/10.1145/1029632.1029637

URL:
http://dl.acm.org.lib-ezproxy.tamu.edu:2048/citation.cfm?id=1029637

SketchREAD is a system developed by Christine Alvarado and Randall Davis, which uses many different principles in the field of sketch recognition to present an algorithm that is as least intrusive to the user sketching experience as possible. The main motivation behind this paper is the fact that most systems regarded as "accurate" are either overly restrictive in the sketches the consider (e.g., one can only draw the primitive shape using one stroke), require the user to input a significant amount of additional data (e.g., training data or labeling shapes), or severely sacrifice response time or accuracy. SketchREAD was designed as a way for the recognizer to work "in the background", and to continuously update its own recognition with 1) no prior training data and 2) no feedback provided to the user, as the latter is considered to be distracting to the sketching experience.

This algorithm makes extensive use of Bayesian Networks, which are networks of predictions based on uncertainty that use background data to calculate said uncertainty. They consist of two parts, a "directed acyclic graph that encodes" which world factors influence each other, and a set of probabilities that specify how these factors affect each other. This is used especially in one of the two test cases for the SketchREAD system: the formulation of a family tree. Because the relationship between family trees and, therefore, the identification of object attributes, depends on how the objects are translated, the system continues to update its interpretation as more sketch components are added. Bottom-up and top-down approaches are applied to help the run time of the recognition algorithm. This is distinctly similar to how the ShortStraw algorithm is implemented. Additionally, pruning is performed on probability calculations, which we have also seen in HMMs.

Overall, I think this paper is an amalgam of a large number of different techniques employed in several other recognition algorithms. The system is shown to significantly improve the user experience in both the family writing domain and the circuit design domain as well. Finally, it employs heavy use of the hierarchical system of sketch recognition, which has also been seen in other systems such as the one currently in place for SRL's Mechanix. I think this system can easily be applied to several other kinds of domains, and the fact that it draws from many other sketch recognition algorithms to create its own implementation is an indication of a solid application of the best aspects of these algorithms.