Apparatus and method for character recognition

• US 4,308,523 A
• Filed: 02/04/1980
• Issued: 12/29/1981
• Est. Priority Date: 02/04/1980
• Status: Expired due to Term

• Current Assignee: CompuScan, Inc.
• Original Assignee: CompuScan, Inc.
• Inventors: Schapira, Alexander D.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/118,412
• Time in Patent Office: 694 Days
• Field of Search: 340/146.3 Q, 340/146.3 E, 340/146.3 Y, 340/146.3 S, 250/567, 250/568
• US Class Current: 382/216
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A practice for storage recognition of unknown document characters contained in a matrix representation of a document region wherein a plurality of arrays of matrix positions incrementally displaced in accordance with a predetermined displacement pattern are interrogated and the results of these interrogations processed in accordance with predetermined reference character recognition equations to derive catalogues of errors. The lowest errors in the derived catalogues are analyzed to determine the reference characters recognizable as unknown document characters.

Claims

1. Apparatus for recognition storage of unknown document characters contained within a matrix representation of a document region comprising:

recognition evaluation means including;

means for interrogating a plurality of arrays of positions of said matrix representation, said arrays being incrementally displaced in accordance with a predetermined displacement pattern;

means for forming for each interrogation of an array a catalogue of errors each indicative respectively of discrepancy between the interrogated representation in that array and one of a number of reference characters usable on said document, each reference character being represented by a corresponding predetermined character recognition equation;

and means for selecting the lowest errors from each catalogue and storing said selected lowest errors and indicia representative of the reference characters corresponding to said selected lowest errors;

control processor means for controlling said recognition evaluation means and for receiving said stored lowest errors and said indicia and determining a reference character recognizable as an unknown document character;

and means for halting the interrogation of a particular array by said recognition means when the errors in the catalogue of errors being formed for that array all exceed a predetermined value.

13. Apparatus in accordance with claim 1, 2 or 8 wherein:

said predetermined displacement pattern and said predetermined recognition equations result in said stored lowest errors and corresponding reference characters evidencing at least one reference character having a high frequency of occurrence and a small average error in comparison to the frequency of occurrence and average error evidenced for other reference characters.

14. Apparatus in accordance with claim 13 wherein:

said control processor means selects as recognizable a reference character evidenced by said stored lowest errors as having a small average error and a high frequency of occurrence.

15. Apparatus in accordance with claim 1, 2 or 8 wherein:

said predetermined pattern follows a spiral-like path.

16. Apparatus in accordance with claim 15 wherein:

said spiral-like path comprises incrementally spaced path positions, the increment between successive path positions being definable in terms of one or more matrix array positions.

17. Apparatus in accordance with claim 16 wherein:

said increment between successive path positions varies.

18. Apparatus in accordance with claim 17 wherein:

said increment is in a range from 1 to 2 matrix array positions.

19. Apparatus in accordance with claim 1, 2 or 8 further comprising:

means for scanning said document region to provide an analog signal indicative of the content of said document region;

means for processing said analog signal to develop a digital signal each of whose bits corresponds to an incremental area of said document region and is assigned a first or second state depending upon whether that incremental area substantially contains a document segment or substantially contains a background area;

and means for assembling said bits of said digital signal into said matrix representation of said document region.

20. Apparatus in accordance with claim 1, 2 or 8 wherein:

said means for interrogating includes means for defining said pluralities of arrays in terms of a window matrix displaceable in accordance with said predetermined displacement pattern.

21. Apparatus in accordance with claim 20 wherein said matrix representation includes matrix positions P(X_BO, Y_BO) through P(X_B(m+r),Y_B(n+s)) and wherein:

said window matrix is defined as containing matrix positions P(X_B(i+k),Y_B(j+l)) through P(X_B(i+k+m) Y_B(j+l+n)), where i and j are parameters of an initial interrogation position, k and l are parameters defining the positions of said displacement pattern and m and n are constants of sufficient value to cover the matrix representation of the largest character usable on said document.

2. Apparatus for recognition storage of unknown document characters contained within a matrix representation of a document region comprising:

recognition evaluation means including;

means for interrogating a plurality of arrays of positions of said matrix representation, said arrays being incrementally displaced in accordance with a predetermined displacement pattern;

means for forming for each interrogation of an array a catalogue of errors each indicative respectively of discrepancy between the interrogated representation in that array and one of a number of reference characters usable on said document, each reference character being represented by a corresponding predetermined character recognition equation;

and means for selecting the lowest errors from each catalogue and storing said selected lowest errors and indicia representative of the reference characters corresponding to said selected lowest errors;

and control processor means for controlling said recognition evaluation means and for receiving said stored lowest errors and said indicia and determining a reference character recognizable as an unknown document character;

wherein;

said control processor includes means for identifying the location in said matrix representation of said determined reference character.

3. Apparatus in accordance with claim 2 wherein:

said means for identifying comprises;

means for determining the arrays resulting in the stored errors whose corresponding reference characters correspond to the determined reference character;

and means for calculating from said determined arrays the position of the determined reference character.

4. Apparatus in accordance with claim 3 wherein:

said means for calculating comprises means for forming an average of the positions of said determined arrays.

5. Apparatus in accordance with claim 2 wherein:

said recognition means repeats said interrogating, forming of catalogues of errors and selecting and storing of lowest errors for further pluralities of arrays of matrix positions, each of said further pluralities being incrementally displaced in accordance with said predetermined position pattern;

said control processor means for each of said repetitions receives the lowest errors resulting therefrom and determines a reference character recognizable as an unknown document character;

and said means for identifying identifies the location of each of said determined reference characters.

6. Apparatus in accordance with claim 5 wherein:

said control processor includes means for locating the first array in each of said further pluralities in said matrix representation at a location which is a function of the identified locations of the determined reference characters resulting from the interrogation of the preceding arrays.

7. Apparatus in accordance with claim 6 wherein:

said locating means locates said first array in each of said further pluralities in said matrix at a location which is a further function of the nominal characteristics of the characters usable on said document.

8. Apparatus for recognition storage of unknown document characters contained within a matrix representation of a document region comprising:

recognition evaluation means including;

means for interrogating a plurality of arrays of positions of said matrix representation, said arrays being incrementally displaced in accordance with a predetermined displacement pattern;

means for forming for each interrogation of an array a catalogue of errors each indicative respectively of discrepancy between the interrogated representation in that array and one of a number of reference characters usable on said document, each reference character being represented by a corresponding predetermined character recognition equation;

and means for selecting the lowest errors from each catalogue and storing said selected lowest errors and indicia representative of the reference characters corresponding to said selected lowest errors;

and control processor means for controlling said recognition evaluation means and for receiving said stored lowest errors and said indicia and determining a reference character recognizable as an unknown document character;

wherein;

each recognition equation corresponding to a particular reference character is defined in terms of certain reference character positions encompassed by that reference character, each reference character position being assigned a first, second or third state representative of said reference character position containing a character segment, containing background area or being irrelevant to that reference character.

9. Apparatus in accordance with claim 8 wherein:

said matrix representation of said document region comprises matrix positions each of which is assigned a first or second state representative of said matrix position containing a character segment or background area.

10. Apparatus in accordance with claim 9 wherein:

said evaluation means includes;

for the interrogation of each array of matrix positions, means for determining the assigned state of each matrix position in that array;

and for the forming of a catalogue of errors for each array means responsive to said assigned state determining means for simultaneously generating for each array matrix position whose assigned state has been determined an error corresponding to each reference character having a recognition equation including a character position corresponding to that matrix position, provided the assigned state of that matrix position and the assigned state of the corresponding character position differ; and

means for summing the errors generated for each character to form a composite error for that reference character.

11. Apparatus in accordance with claim 8 wherein:

the positions used in each reference character recognition equation to define that reference character include those which contain a character segment or a background area for substantially all expected degrees of distortion and/or displacement of that reference character.

12. Apparatus in accordance with claim 8 wherein:

the positions used in each reference character recognition equation to define that reference character include those which are within the skeleton and anti-skeleton representations of that reference character.

22. Apparatus for recognition storage of unknown document characters contained within a matrix representation of a document region comprising:

recognition evaluation means including;

means for interrogating a plurality of arrays of positions of said matrix representation, said arrays being incrementally displaced in accordance with a predetermined displacement pattern;

means for forming for each interrogation of an array a catalogue of errors each indicative respectively of discrepancy between the interrogated representation in that array and one of a number of reference characters usable on said document, each reference character being represented by a corresponding predetermined character recognition equation;

and means for selecting the lowest errors from each catalogue and storing said selected lowest errors and indicia representative of the reference characters corresponding to said selected lowest errors;

and control processor means for controlling said recognition evaluation means and for receiving said stored lowest errors and said indicia and determining a reference character recognizable as an unknown document character;

wherein;

said means for interrogating includes means for defining said pluralities of arrays in terms of a window matrix displaceable in accordance with said predetermined displacement pattern;

said window matrix defines positions located at every other vertical and horizontal position of said matrix representation.