Character Recognition on a touch screen : Part 2 (Algorithm)

There are various existing methods for character recognition. I used a very intuitive algorithm- The chain code algorithm.

Chain Code
This is basically a notation for recording list of edge points along a contour. It specifies contour direction at each edge in the list. Directions are quantized into one of the 8 directions. Starting at 1st edge in the list and going clockwise around the contour, the direction to the next edge is specified using one of the 8 chain codes. The direction is the chain code for the 8-neighbour of the edge.

Chain Code notation

Chain Code notation

Defining each direction

Defining each direction

Chain Code of an example curve

Chain Code of an example curve

Chain Code Histogram
A chain code histogram counts the frequency of occurrence of each of the 8 directions. This means the information of the order of occurrence of the directions is lost. However, instead of storing the entire chain code, this enables storing only 8 data values.
The loss of accuracy is negligible. The storage space gained is immensely useful for embedded systems which have constrained resources.

Comparing the Chain Code
Once the chain code histogram data for the current coordinates are stored, it has to be compared with the pre-stored character’s histogram data. For that, we find the standard deviation.
The standard deviation is defined as –

std dev

std dev 2

Here n=8.
Thus, we find the similarity between the stroke and pre-stored character by seeing the deviation in the count in each of the 8 values (representing the 8 directions). The stroke is compared with every pre-stored character, and the one with lowest standard deviation wins.

Summary of the algorithm

Summary of the algorithm

Samples from MATLAB
Shown below are sample inputs, taken in MATLAB, from the touchscreen. (Each of the characters has been shown inverted, due to some hardware limitations.) It can be seen that the algorithm correctly recognizes the input by comparing input histogram with each character’s histogram.

Input stroke similar to ‘O’ letter. Notice the similarity of histogram between ‘O’ and input stroke.

Input stroke similar to ‘O’ letter. Notice the similarity of histogram between ‘O’ and input stroke.

Input stroke similar to ‘S’ letter. Notice the similarity of histogram between ‘O’ and input stroke.

Input stroke similar to ‘S’ letter. Notice the similarity of histogram between ‘O’ and input stroke.’

Features of algorithm used
The algorithm is scale and position invariant. Thus, it doesn’t matter where the stroke is made on the touchscreen, or how big the stroke is. What matters is the shape of the stroke.
The algorithm is not rotation invariant. Thus, the strokes will be recognized only in a particular orientation.
The algorithm is very efficient in terms of storage and computations performed. Only 8 data values are stored per character. Comparison is done by performing standard deviation calculations, which are very fast.

Advertisements