Optical character recognition system and method

• US 5,091,968 A
• Filed: 12/28/1990
• Issued: 02/25/1992
• Est. Priority Date: 12/28/1990
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: NCR Corporation
• Inventors: Higgins, Raymond L., Golem, Dennis W.
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/635,899
• Time in Patent Office: 424 Days
• Field of Search: 382/30, 382/8, 382/16, 382/47, 382/9, 382/50, 382/27, 382/52, 358/444, 358/452
• US Class Current: 382/220
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

A system and method are disclosed for optical scanning and recognition of alphanumeric characters of different sizes and fonts such as E13B, OCRA, OCRB, and Farington 7B type fonts recorded on documents such as bank drafts and checks. The system comprises an optical scanner, a microprocessor, a read-only-memory (ROM), a random-access-memory (RAM, with a stored program) for storing data and a plurality of predetermined character-identification patterns (templates). Each template includes three configurations: an actual pixel patterns (bit configuration) or a character, a configuration representing significant portions of the character which remain the same and do not change despite changes in size of the character, and a configuration representing portions of the character which are given added weight in distinguishing between similar characters. The scanner optically scans each document and produces a plurality of gray-scale pixel values which are stored in the RAM under control of the microprocessor. The microprocessor processes the stored pixel values, and effectively locates and segments each character on the document. The microprocessor then converts the segmented-character pixel value to binary data, and selects, from the plurality of templates, the template that matches the binary data, the matching template serving to identify (recognize) the segmented character.

Claims

1. Optical character recognition system comprising:

means for optically scanning a character recorded on a document, the character and document having different opacities, and producing a plurality of gray-scale values corresponding to said opacities, said gray-scale values representing light and dark pixels;

memory means disposed for storing the gray-scale values, said memory means including a stored program, and predetermined data including a plurality of predetermined binary patterns, one of said predetermined binary patterns representing the character, each predetermined binary pattern including first, second, and third bit configuration, said first bit configuration representing an actual bit pattern of the character, said second bit configuration representing predetermined significance of respective bits of the actual bit pattern, and said third bit configuration representing weighted values of respective bits of the actual bit pattern; and

processing means coupled to the scanning means and to the memory means, and operating under control of the stored program, for locating the character on the document by selecting from said gray-scale values a matrix of values representative of the character, for converting the matrix values to binary data, and for selecting from the plurality of predetermined binary patterns a pattern that matches the converted binary data, said matching pattern serving to identify the character.

2. The system as in claim 1 wherein said character has a right, left, top and bottom edge, and said scanning means includes a means for reading from the bottom edge to the top edge in a vertical direction.

3. The system as in claim 2 wherein said processing means includes a means for framing a region having a plurality of pixels proximate to a dark pixel.

4. The system as in claim 3 wherein said framing means includes a means for defining a window for bordering said region.

5. The system as in claim 4 wherein said framing means includes a means for positioning the window so that the sum of the gray-scale values within the window is a maximum, corresponding to the character being centrally located in the window, said maximum-sum values corresponding to a matrix of selected pixel values representative of the character.

6. The system as in claim 5 wherein said framing means also includes a means for confirming the presence of a character within the window, by determining the total number of pixels in the window that exceeds a predetermined confirmation threshold.

7. The system as in claim 6 wherein said processing means includes a means for calculating an average threshold value for said selected pixel values.

8. The system as in claim 7 wherein said calculating means includes a means for producing binary data representative of the magnitudes of said selected pixel values relative to said average threshold value.

9. The system as in claim 8 wherein said processing means includes a means for producing a mismatch count for each predetermined binary pattern said count being indicative of the extent of mismatch between the predetermined binary pattern and the converted binary data.

10. The system as in claim 9 wherein said means for producing a mismatch count includes a means for selecting from the mismatch counts the count that best satisfies at least one predetermined threshold criterion.

11. The system as in claim 10 wherein the means for producing a mismatch count includes a means for producing mismatch words and calculating a count based on the contents of selected ones of said words, said words being indicative of the extent of mismatch between the converted binary data and selected bit configurations of said predetermined binary pattern.

12. The system as in claim 11 wherein said means for producing a mismatch count includes a logic means for performing an exclusive-OR operation between the converted binary data and the first bit configuration to produce a first mismatch word.

13. The system as in claim 12 wherein said means for producing a mismatch count includes a logic means for performing an AND operation between the first mismatch work and the second bit configuration to produce a second mismatch word.

14. The system as in claim 13 wherein said means for producing a mismatch count includes a logic means for performing an AND operation between the second mismatch word and the third bit configuration to produce a third mismatch word.

15. The system as in claim 14 wherein each of said predetermined binary patterns represents a predetermined template, and said framed character may be compared against a predetermined template in each of nine positions, a center position and eight non-center positions, and said means for producing a mismatch count includes a means for positioning a template relative to the center portion of the framed character.

16. The system as in claim 15 wherein said means for positioning places the predetermined binary pattern relative to one of the non-center portions of the framed character.

17. The system as in claim 16 wherein said gray-scale values are in the range 0 to 255.

18. The system as in claim 17 wherein said character is a member of a selected character set.

19. The system as in claim 18 wherein said character and said window are each of a predetermined size for a selected font.

20. The system as in claim 19 wherein each bit-configuration of said predetermined binary pattern is a first predetermined number of pixels wide by a second predetermined number of pixels high.

26. The method of claim 2 where the step of framing the character includes the step of confirming the presence of a character within the window, by determining the total number of pixels in the window that exceeds a predetermined confirmation threshold.

27. The method of claim 26 where the step of converting includes the step of calculating an average threshold value from the values represented by the dark pixels of the framed character.

28. The method of claim 27 where the step of converting also includes the step of producing binary data representative of the magnitudes of said selected pixel values relative to said average threshold value.

29. The method of claim 28 where the step of selecting a predetermined binary pattern that matches the converted binary data includes the step of producing a mismatch count for each predetermined binary pattern, said count being indicative of the extent of mismatch between the predetermined binary pattern and the converted binary data.

30. The method of claim 29 wherein the step of selecting a predetermined binary pattern also includes the step of selecting from the mismatch counts the count that best satisfies at least one predetermined threshold criterion.

31. The method of claim 30 where the step of producing a mismatch count includes the steps of producing mismatch words and calculating a count based on the contents of selected ones of said words, said words being indicative of the extent of mismatch between the converted binary data and selected bit configurations of said predetermined binary pattern.

32. The method of claim 31 where the step of producing a mismatch count includes the step of performing an exclusive-OR logical operation between the converted binary data and the first bit configuration for producing a first mismatch word.

33. The method of claim 32 where the step of producing a mismatch count includes the step of performing an AND logical operation between the first mismatch words and the second bit configuration for producing a second mismatch word.

34. The method of claim 33 where the step of producing a mismatch count further includes the step of performing AND logical operation between the second mismatch word and the third bit configuration for producing a third mismatch word.

35. The method of claim 34 where the framed character may be divided virtually into nine portions, a center portion and eight non-center portions, and the step of producing a mismatch count includes the step of positioning a predetermined binary pattern relative to the center portion of the framed character.

36. The method of claim 35 where the step of positioning includes placing the predetermined binary pattern relative to one of the eight non-center portions of the framed character.

21. Method of optically identifying a character on a document, the character and document having different opacites, the method comprising the steps of:

optically scanning the document and producing a plurality of gray-scale values corresponding to said opacities, said gray-scale values representing light and dark pixels;

locating the character by selecting, from said gray-scale values, a matrix of values representative of the character;

converting the matrix values to binary data;

representing the character as one of a plurality of predetermined binary pattern including first, second, and third bit configurations, said first bit configuration representing an actual bit pattern of the character, said second bit configuration representing predetermined significance of respective bits of the actual bit pattern, and said third bit configuration representing weighted values of respective bits of the actual bit pattern; and

selecting from the plurality of predetermined binary patterns a pattern that matches.

22. The method of claim 21 where the step of optically scanning the document includes the step of reading each character on the document from bottom to top in a vertical direction.

23. The method of claim 22 where the step of locating the character includes the step of framing a region having a plurality of pixels proximate to a dark pixel.

24. The method of claim 23 where the step of framing includes the step of defining a window for bordering said region.

25. The method of claim 24 where the step of framing also includes the step of positioning the window so that the sum of the gray-scale values within the window is a maximum, corresponding to the character being centrally located in the window, said maximum-sum values corresponding to a matrix of selected pixel values representative of the character.

37. Method of identifying a character imaged on a document, the character and document having different opacities, the document being optically scanable, with images thereon representable as a plurality of stored gray-scale pixel values corresponding to said opacities, the method comprising the steps of:

locating the character by selecting from said gray-scale pixel values a matrix of values representing the character;

converting the matrix value to binary data;

representing the character as one of a plurality of predetermined binary patterns, each predetermine binary pattern including first, second, and third bit configuration, said first bit configuration representing an actual bit pattern of the character, said second bit configuration representing predetermined significance of respective bits of the actual bit pattern, and said third bit configuration representing weighted values of respective bits of the actual bit pattern; and

identifying the character by selecting, from the plurality of predetermined binary patterns, a pattern that matches the converted binary data.