METHOD AND CIRCUIT ARRANGEMENT FOR AUTOMATIC RECOGNITION OF CHARACTERS WITH THE HELP OF A TRANSLATION INVARIANT CLASSIFICATION MATRIX

• US 3,815,090 A
• Filed: 09/26/1972
• Issued: 06/04/1974
• Est. Priority Date: 09/27/1971
• Status: Expired due to Term

• Current Assignee: Siemens Nixdorf Informationssysteme AG (Siemens AG)
• Original Assignee: Meinolf Muenchhausen
• Inventors: Muenchhausen, Meinolf
• Primary Examiner(s): Henon, Paul J.
• Assistant Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/292,288
• Time in Patent Office: 616 Days
• Field of Search: 340/146R,146.3H,146.3 179/15BC
• US Class Current: 382/206
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/186 by deriving mathematical or geometrical properties from the whole image
• CPC Class Codes: G06V 30/192 using simultaneous comparisons or correlations of the image signals with a plurality of references

Abstract

A method and apparatus for automatic character recognition of characters which may be varied, even within a class of significance, according to shape, size and position in a raster of a column-wise scanning field. The sensed data is transformed according to given rules in several steps to provide a translation invariant classification matrix from which a class of significance of the character is derived for which the highest probability is given through the use of values of individual elements. The scanning signals obtained during the scanning of the scanning field, and corresponding to the black value of the scanning elements and arranged in the scanning field in columns are one-dimensionally transformed with a set of orthogonal Walsh functions which has been extended over phase shifted sequences in such a way that the transformation result of a number of scanning signals forms a value of a one-dimensionally transformed image matrix. The transformed image matrix is again transformed in the same manner with a transposed set of applied Walsh functions and therefore results in a two-dimensionally transformed image matrix. From the two-dimensionally transformed image matrix a classification matrix, denoted as a sequence spectrum, is embodied in such a way that partial ranges merely due to phase shifted sequences of Walsh functions of equal order, and limited by lines and columns of equal order, are combined in the twodimensionally transformed image matrix by means of maximum value formation. Absolute values are found from the latter, as well as all remaining values of the two-dimensionally transformed image matrix, and are transferred as spectrum values into the sequence sprectrum. Combinations of the spectrum values are evaluated by discriminators and result in the probabilities for all possible classes of significance. The class of significance is therefore added to the sensed signals for which the most probability is provided.

Claims

1. A method for the automatic recognition of characters within a class of characters in which the individual characters are substantially identical yet differ from each other with respect to shape, size and position within a raster of a column-by-column scanning area, whereby the scanning signal produced by a scanning process are interpreted as a function of two variables which is transformed by a set of Walsh functions in several steps to result in a translation invariant classification matrix from which an identity of the character to be recognized is derived, comprising the steps of:

scanning the scanning area to obtain scanning signal corresponding to the brightness of the character elements in the scanning area;

one-dimensionally transforming the scanning signals column-bycolumn, according to the columns of the scanning area, with a set of orthogonal Walsh functions which have been extended over phase-shifted sequences in such a way that the result of the transformation of a column of scanning signals with one of the Walsh functions forms one of the elements of a onedimensionally transformed image matrix;

transforming the elements of the one-dimensionally transformed matrix in the same manner with the transposed set of said Walsh functions to provide a two-dimensionally transformed image matrix;

reducing the two-dimensionally transformed image matrix by determining the element of maximum value by means of maximum detectors within corresponding partial ranges of the twodimensionally transformed image matrix limited by lines and columns, which are referred to one of the phase-shifted sequences of equal order;

forming spectrum values of a sequence spectrum by determining absolute values of the elements of the reduced twodimensionally transformed image matrix;

comparing combinations of spectrum values with stored reference combinations of spectrum values to obtain probabilities of the identity of the character to be recognized; and

classifying said character in determining the maximum of these probabilities by means of a maximum detector.

2. Apparatus for the automatic recognition of characters which are generally the same and which may be individually varied within a class of signficance with respect to shape, size and position in a raster of columns and lines of a column-by-column scanning area, comprising:

means for scanning the scanning area column-by-column to produce signals corresponding to the brightness value of the character elements scanned;

first means including generator means for generating a set of orthogonal Walsh functions extended over phase-shift sequences and including means for providing a set of transposed Walsh functions, and responsive to said signals and said set of Walsh functions to produce a one-dimensionally transformed image matrix;

second means responsive to said image matrix and to said set of transposed Walsh functions to produce a two-dimensionally transformed image matrix;

third means for combining into a sequence spectrum partial ranges of the phase-shifted sequences of equal order, limited by lines and columns of equal order, into said two-dimensionally transformed image matrix, including means for effecting maximum value formation;

fourth means for determining absolute values from said maximum values and from the other values of the two-dimensionally transformed image matrix;

fifth means for transferring the absolute values into said sequence spectrum; and

sixth means for comparing combinations of spectrum values with all possible classes of character significance to determine the class of significance of a scanned character.

3. Apparatus according to claim 2, wherein said scanning means includes scanning elements for each column;

and said first means comprises a first plurality of mutually parallel adding units connected to the scanning elements of a column, each of said adding units comprising an operational amplifier having positive and negative inputs and an output, an input network connecting said positive input to a first portion of said scanning elements and said negative input to a second portion of said scanning elements for receiving therefrom digital signals upon scanning to cause said operational amplifier to provide a Walsh function at said output.

4. Apparatus according to claim 3, comprising a second plurality of said adding units, adding units of said first plurality which simulate the same Walsh functions connected to certain adding units of said second plurality to produce Walsh functions;

a resistor coupling field connected to the outputs of said second plurality of adding units to form the values of said two-dimensionally transformed image matrix; and

a plurality of diodes connected to said resistor coupling field in diode columns to provide maximum values of the partial ranges of said sequence spectrum.

5. Apparatus according to claim 2, wherein said scanning means includes a plurality of scanning elements for each column of the scanning area;

and said apparatus comprises an analog memory having analog storing elements associated with each of said scanning elements and arranged in columns and lines;

a clock producing clock pulses;

means connected to said clock for connecting scanning elements of a column with the associated storage elements on a column-by-column basis in sequence in response to clock pulses;

a plurality of sequence generators for providing Walsh functions connected to said clock and associated with respective lines of storage elements and sequentially operated by clock pulses; and

a plurality of switching means connected between respective sequence generators and the associated lines of storage elements and operable by said sequence generators so that all storage elements of a line add and subtract the analog value stored therein and received from said scanning elements to produce a combined brightness signal value for each column.

6. Apparatus according to claim 5, wherein said sequence generators each include a feedback shift register.

7. Apparatus according to claim 5, wherein said analog storage elements each comprise an RC circuit for storing analog values received from the respective scanning elements.