Adaptive Pattern Recognition

ADAPTIVE PATTERN RECOGNITION

P. Hauff and E. Neidhart AEG-Telefunken

Konstanz, German Federal Republic

A store of characteristic patterns of features is a fundamental requirement for pattern recognition. This store may be compiled either by intuition or by mathematical analysis of representative patterns. The precision of the mathematical method is considerably enhanced by statistical analysis of numerous representative patterns. This statistical method is employed in the BSM character recognition system. The_ system is not only a reader, but also forms part of a statistical pattern analysator in order to create optimal read only stores of representative pattern features.

The process forms an adaptive system suitable for reading characters of any given font, generated by machine or handprinting. For each font classification rules based on a sufficient set of test samples can be built.

It is a real adaptive system as far as a computer carries also on the classifying phase by computing the distance values according to the computed classification matrix.

In our hardware recognition device the immediate feed-back links between the adaptive and the processing phase of the adaptive system are lost. The classifying rules have to be concretized mechanically.

The fonts in question are the following:

OC R·A

0 C R · B

407

1428

The basic recognition system is shown in Fig. 1.

The data carrier has to be presented at a pick-up point under a continuous speed. The light flood of two strong lamps is projected on the data carrier. ( Ref.2)

T he character to be read is imaged into the receptor by a highly corrected optical system of classical design. The receptor is an array of silicon photodiodes developed specially for this purpose, using MSI techniques. A common silicon crystal piece carries the 50 photo diodes. The light sensitive area of each element has 200 x 320 um (8 x 13 mils) .

This systematic gives a reading possibility of 8 mm on the document.

The photo signals which are inherent to the 50 diodes are submitted to a t ranslation in black and white quanta values. The quantisation is checked through a controling device which regulates the contrast between the character and the paper.

In the discriminator the processed pattern is compared with the stored feature sets characteristic for the pattern classes.

The read only storages for processor and discriminator consist of resistor matrices. While the prototype still uses discrete resistors, future devices will contain thin film substrates.

The amplifiers linked at the output of each matrix resolve with a feed -back network the following function :

1. They amplify the signal of the one channel which has the highest input signal
2. They amplify the difference between the signal of each one of the other channels and the maximum

At a checking circuit it will be controlled if the maximal input signal (U ma) and the difference (U ) between the highest and the next lower one are overstepping the estabiPshed limits.

In this case the selected channel will be ready for an output, otherwise a "Reject" Signal will be given.

The values of U and U can be adjusted and regulate essentially the relation Reject-~~~stitutioR. They allow in this way an optimal compromise for different application.

The reading device gives a large versatility, because the scanning and storage of characters are not dependent to a font, and because of the easy interchangeability of the matrix block.

The great amount of matrices allows the reading of alpha-numeric fonts where the complete font can be divided in subfonts. The subfonts can be read with different security (U max and U 0 )

For adaption of the reading system to a certain group of pattern classes, a large number of labelled character samples is presented to the syste~ . The receptor converts these samples into quantized samples labelled for class identification stored on magnetic tape. For these purpose the device contains an auxiliary interface oriented toward magnetic tape data storage. This sample tape does not only contain the peculiarities of each class, but also the result of the interaction of these with those of the receptor.

FilJ.2 shows the principle of this data preparation.

The labelled samples stored on the tape are then fed into an auxiliary EDP system for the adaption process.

The processor generates a positioned and digitalized image of the character in a 20 by 13 bit matrix. (Ref. 1) At its disposal is an intermediate storage of 650 bits, which allows for a vertical positioning tolerance of 2.5 character heights.

The screening in horizontal direction occurs through a pulsed sampling of the digital signals. A central master pulser controls the sampling. In this way it is possible to choose different transportation speed and to change the horizontal screening dimension.

The highest transportation speed is 7.6 m/sec, that is equal to a reading possibility of 3000 characters per second . An input register collects the result of a sampling operation. This occurs in parallel way. This input register is composed of 50 flipflops. Between two sampling pulses the data are shifted out of the input register into the main register in serial way. The main register is a chain of 650 bits, which has to be imagined to be a two-dimensional array of 13 columns of 50 rows each . The register organisation requires a high· operating frequency.

The advantage on the other hand is this: we can observe the marching- on of all bits from one single position. For example: the data preprocessing can be built in a central point, because each bit has to go through this point.

We chose a soft sort of processing which takes into consideration only the closest neighbourhood of the bit in question. We think that any radical manupulation on the bit pattern of a character has to be avoided as long as we do not know which character we have to deal with .

In relation with the amount and comprehensiveness of sample material disposable for the regression analysis, the varations of characters caused by spots or voids or different line thickness will lose their negative influence on the classification results.

The quanta of the reading zone move through the main register and, of course, we now have to find the precise moment in which the character is framed in the register. During the shift period we have to weigh, count and compare the black bits stored in the main register. This is done in separate digital adders for the left and the right half of the register.

The foiling formula gives the weight function

n = 1, 2, ... 6 = horizontal distance from the central column.

The development of this function in the mentioned value section bears resemblance to a square function . Simulating researches proved this function to be optimal.

When the black quantum of the right side of the register has a higher value than the one of the left side the data input is interrupted until the classification process is finished.

The the bit pattern which is stored in the register will be displaced in the direction of the columns until the momentum of the black bits of the upper half surpasses the one of the lower half.

This is ascertained by an analog register device acting on a weight function

n = 1, 2, ... 10 =vertical distance from the central row.

This function, too, was found to be optimal .

During the positioning it is controlled if the spatial extension of the character in question is within pre-established limits.

After being positioned the character occupies a place of 20 x 13 bits and is ready to be classified.

The adaption process is defined by a suitable software package for the auxiliary EDP system. The flow diagram of the adaption process is shown in Fig.3.

The labelled samples of digitalized characters are first processed for correct format and position. Then a statistical analysis is performed, yielding a two dimensional matrix indicating the probability for each image element to be black. (Ref. l These probability matrices generated by statistical analysis of the data input form the fondation for a subsequent regression analysis.

The result of the regression analysis is a set of design data for the realization of the character recognition system.

This design data output has the form of punched tape. With the design data at hand, the recognition system can be realized in its optimal form. However, with the auxiliary EDP system at hand, there is no need for immediate phys­ ical realization of the Recognition System in ·order to gain experiences.

Equipped with appropriate software, the auxiliary EDP system lends itself to the simulation of the recognition process. The design data computed by means of the adaption process control the working parameters of the simulated recognition system. The labelled samples of quantized characters are used as test material for simulated recognition. Additional to the simulated recognition the program performs a statistical analysis of errors and rejects. The error statistics are made possible by the. labelling of samples.

From the result of the simulation process it may be judged, if the design data cause desirable reaching system performance.

The design data are then transformed into hardware, using special read only memories composed of resistors. The reading device presently has a reading speed of 3000 characters per second.

Experiments have been conducted with documents generated by various high speed printers under uncontrolled conditions. Under these circumstances a deviation of 12 - 16% from the mean vector of a class has been observed. A test with 25.000 documents yielded 53 rejects.

The bit pattern of a typical rejected character is shown in Fig.6. As the outlines show, it is a zero mutilated by asymmetrical print force distribution.