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

Character Recognition on a touch screen : Part1 (Hardware)

As part of my final year project, I got down to the basics. Using a 4 wire resistive touch screen, PSoC-1 (which is a microcontroller + some other cool blocks) , and MATLAB, I got the strokes on the touchscreen to be recognizable by MATLAB in a simple, efficient and fast manner.

I had originally planned on doing the entire thing on PSoC-1, which has a pretty watered down MCU core (M8C). However, lack of time got me to develop the algorithm on MATLAB instead.

Okay so here’s what I used-

1) Nintendo DC Touch Screen
2) Nintendo DC Touch Screen 4-wire Connector
3) PSoC-1 EVAL kit
4) USB-UART cable
5) MATLAB 2011b software

The Big Picture

Process Flow Diagram

Process Flow Diagram

Step 3 is the most important part, of course, and there are various ways of implementing it. I used a modified chain code algorithm, which I’ll describe in Part 2 of this series.

How the touch screen works

The x and y coordinates of a touch on a 4-wire touch screen can be read in two steps. First, Y+ is driven high, Y– is driven to ground, and the voltage at X+ is measured. The ratio of this measured voltage to the drive voltage applied is equal to the ratio of the y coordinate to the height of the touch screen. 5V is applied for the high input. The y coordinate can be calculated as shown in the figure below. The x coordinate can be similarly obtained by driving X+ high, driving X– to ground, and measuring the voltage at Y+. The ratio of this measured voltage to the drive voltage applied is equal to the ratio of the x coordinate to the width of the touch screen. This measurement scheme is shown in the figure below.

Measurement scheme for resistive touch screen

Measurement scheme for resistive touch screen

The PSoC-1 bit

PSoC (Programmable System-on-Chip) is a family of integrated circuits made by Cypress Semiconductor. These chips include a CPU and mixed-signal arrays of configurable integrated analog and digital peripherals.
PSoC 1 has been used for this project. It has an M8C core, with various configurable analog and digital blocks. Each digital block is considered an 8-bit resource that designers can configure using pre-built digital functions or user modules.
The software used to program and design applications for PSoC is PSoC Designer.
In this project, the user modules used are –
1)ADCINC (Analog to Digital Converter) –
The ADCINC is one of the ADC user modules offered with PSoC Designer for the PSoC 1 family of parts. It uses an analog switched capacitor block and one digital block. The ADCINC is an averaging ADC that samples the analog input many times (driven by DataClock) to produce one n-bit digital output sample.
2)PGA (Programmable Gain Amplifier)-
The input signal is buffered with the PGA and connected to the ADC. It uses one
3)PWM8 (Pulse Width Modulation 8-bit) –
2 PWM’s have been used to drive 2 LED’s, one for each axis. It has a programmable period and pulse width.
4)LCD
The character LCD is used to display the values of X and Y axis of touchscreen.

Digital blocks used in PSoC-1
Digital blocks used in PSoC-1

The screenshot shows 3 digital blocks being used.
DBB00 – ADCINC
DBB01 – PWM8_1
DCB02 – PWM8_2
An explanation of its usage has been provided in the next section.

Analog blocks used in PSoC-1
Analog blocks used in PSoC-1

Touch Screen Interfacing

Reading the Touch Screen Input
The input from the four-wire touchscreen comes from 4 wires, typically labelled X1, X2, Y1, Y2. They are all connected to Pins 0,1,3 and 7 of Port 0 on PSoC, and are dynamically configured as analog input when reading is required.
PSoC reads these values, and outputs it to LCD configured on Port 2. It also sends output to 2 LED’s, one for each axis, in pins 0 and 1 of Port 1.

Understanding the Code
The code was written in PSoC Designer. Here is an explanation
Firstly, all modules have been initialised. This is necessary before readings are taken from the touchscreen.
An infinite for loop has been used, since values are constantly being read from the touchscreen using the ADC. Each time the loop runs, it alternates between 2 sets of code. One is to read from the X axis, and the other from the Y axis. Since only 1 ADC has been used, its input is constantly being changed using a MUX.

When reading from the X-axis, Pin 0 and Pin 3 (of Port 0) are set in Strong Drive. Pin 1 and Pin 7 are set in High Z Analog Drive Mode. The input is taken from Pin 1.
When reading from the Y axis, Pin 1 and Pin 7 are set in Strong Drive. Pin 0 and Pin 3 are set in High Z Analog Drive Mode. The input is taken from Pin 3.
To constantly change these drive modes, we use the PRTxDMx registers, as explained in AN2074 (see reference 3).
Before further processing, the values for each axis are averaged out to eliminate any error due to noise.
Once the value has been read from the ADC, it is written as the pulse width in the PWM module. Since an 8-bit value is read, the pulse can vary from 0 to 255. The total period is 255. Thus the LED will glow at a maximum, when the ADC value reads 255, and minimum when it reads a 0.
The value is also written to the LCD.

____

This concludes Part 1 of the series. Part 2 will cover the algorithm which was implemented in MATLAB. Input from the touchscreen was decoded by PSoC, and then processed in MATLAB.