Design of a realtime high speed recognizer for unconstrained handprinted alphanumeric characters
Creators: name: Wong, Ing Hoo
Publisher: name: University of British Columbia
Year: 2010

description: This thesis presents the design of a recognizer for unconstrained handprinted alphanumeric characters. The design is based on a thinning process that is capable of producing thinned images with well defined features that are considered essential for character image description and recognition. By choosing the topological points of the thinned ('line') character image as these desired features, the thinning process achieves not only a high degree of data reduction but also transforms a binary image into a discrete form of line drawing that can be represented by graphs. As a result powerful graphical analysis techniques can be applied to analyze and classify the image. The image classification is performed in two stages. Firstly, a technique for identifying the topological points in the thinned image is developed. These topological points represent the global features of the image and because of their invariance to elastic deformations, they are used for image preclassification. Preclassification results in a substantial reduction in the entropy of the input image. The subsequent process can concentrate only on the differentiation of images that are topologically equivalent. In the preclassifier simple logic operations localized to the immediate neighbourhood of each pixel are used. These operations are also highly independent and easy to implement using VLSI. A graphical technique for image extraction and representation called the chain coded digraph representation is introduced. The technique uses global features such as nodes and the Freeman's chain codes for digital curves as branches. The chain coded digraph contains all the information that is present in the thinned image. This avoids using the image feature extraction approach for image description and data reduction (a difficult process to optimize) without sacrificing speed or complexity. After preclassification, a second stage of the recognition process analyses the chain coded digraph using the concept of attributed relational graph (ARG). ARG representation of the image can be obtained readily through simple transformations or rewriting rules from the chain coded digraph. The ARG representation of an image describes the shape primitives in the image and their relationships. Final classification of the input image can be made by comparing its ARG with the ARGs of known characters. The final classification involves only the comparison of ARGs of a predetermined topology. This information is crucial to the design of a matching algorithm called the reference guided inexact matching procedure, designed for high speed matching of character image ARGs. This graph matching procedure is shown to be much faster than other conventional graph matching procedures. The designed recognizer is implemented in Pascal on the PDP11/23 and VAX 11/750 computer. Test using Munson's data shows a high recognition rate of 91.46%. However, the recognizer is designed with the aim of an eventual implementation using VLSI and also as a basic recognizer for further research in reading machines. Therefore its full potential is yet to be realized. Nevertheless, the experiments with Munson's data illustrates the effectiveness of the design approach and the advantages it offers as a basic system for future research.