| Sketching is simple and natural for most people. Intelligent interpretation of digital ink in a sketch-based application can augment a static sketch with meaningful interpretation, thus enabling the use of electronic editing and processing. The goal of this research was to determine whether a practical, trainable, and adaptive multi-stroke symbol recognition system for sketch-based applications could be developed. This dissertation provides a thorough background study and a detailed analysis of existing approaches to symbol recognition. Two new recognition methods are presented in this work. The first method uses a combined structural and statistical approach that extracts both global and local features from structural primitives of a shape to train a set of statistical classifiers. The challenge posed by a particular class of shapes led to the development of another recognition technique. This second technique uses Zernike moment descriptors for characterizing symbols and a Support Vector Machine classifier for learning and classification. A recognition accuracy rate of 97% has been achieved on a dataset consisting of 7,410 sketched symbols and using Zernike moment features up to the 8th order. Furthermore, in this dissertation, two optimal fragmentation algorithms that fragment common geometries into a basis set of line segments and elliptical arcs are presented. The first algorithm uses an explicit template in which the order and types of bases are specified. The other only requires the number of fragments of each basis type. For the set of symbols under test, both algorithms achieved 100% fragmentation accuracy rate for the symbols with line bases, >99% accuracy for the symbols with elliptical bases, and >90% accuracy for the symbols with mixed line and elliptical bases. Robust fragmentation is critical to the task of symbol beautification. The entire system including recognition, fragmentation, and beautification has been demonstrated in a real application, Microsoft PowerPoint 2003, to enable sketching symbols directly onto a presentation slide. |
