My Projects

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.

2 Comments

  1. Could you elaborate a little more on the “Comparing the Chain Code” section, please? I’m having a little trouble seeing how you get the most similar character using the input stroke’s standard deviation.

    1. Hi Mark. I’m storing the frequency of occurrence of each of the 8 directions. For example, if I draw a “1” from top to bottom, it will have a high frequency of the 3rd bin, since we’re going downwards in direction, and whenever the touchscreen is periodically sampled, it notices the direction and increments the count.

      Now that we have the data, we compare it with prior data of every character, and look at what’s the closest in similarity. We do this by calculating the standard deviation, which gives a measure of how much deviation, or dissimilarity is there between 2 terms. We calculate it for each of the 8 frequency bins for the 8 directions, comparing each with the corresponding bin of the pre-stored character.

      For example, someone who draws a “1” may have data like this-> 0, 0, 0, 30, 23, 0, 0, 0. Since bin 3 and 4 would be filled.
      We compare it with pre-existing data on what a “1” would look like, for example-> 0, 0, 0, 36, 20, 0, 0, 0.
      We compare 0 with 0, 30 with 36, 23 with 20 and so on. Since these are quite similar, we’ll have a low standard deviation.

Leave a Reply

Your email address will not be published. Required fields are marked *