OCR method and apparatus using image equivalents

• US 5,764,799 A
• Filed: 06/26/1995
• Issued: 06/09/1998
• Est. Priority Date: 06/26/1995
• Status: Expired due to Term

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: Rutgers University
• Inventors: Hull, Jonathan J., Hong, Tao
• Primary Examiner(s): Couso, Yon J.
• Assistant Examiner(s): NGUYEN, HA T
• Application Number:
  US08/494,337
• Time in Patent Office: 1,079 Days
• Field of Search: 382/187, 382/229, 382/217, 382/230, 382/221, 382/225, 382/218, 382/309, 382/310, 382/311, 382/177
• US Class Current: 382/225
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

An OCR 300 stores signals representative of reference characters and scans a document 302 to generate a bit mapped digitized image of the document. After the characters and the words are recognized and candidate characters are identified, the initial results are post-processed to compare clusters of identical images to the candidates. Where the candidates of all equivalent images in a cluster are the same, the candidates are output as representative of the image on the document. Where the candidates are different, a majority of identical candidates determines the recognized candidates. Other post-processing operations include verification and re-recognition.

Claims

1. A method for recognizing words in a text on a medium comprising the steps of:

scanning the medium to generate bit mapped images of characters forming the words on the medium,

comparing a bit mapped image of a first number of bit mapped characters in a first word to one or more bit mapped images of characters in other words in order to identify equivalent bit mapped images in said document;

comparing the equivalent bit mapped images of the document to reference characters in order to recognize each bit mapped character as one of said reference characters;

comparing the corresponding recognized reference characters of each equivalent image to each other and selecting the reference characters identified for the equivalent bit mapped characters when the same reference characters are identified for corresponding bit mapped characters in said equivalent images; and

further processing said bit mapped images when different reference characters are recognized for corresponding equivalent bit mapped characters.

2. The method of claim 1 wherein equivalent images are clustered.

3. The method of claim 2 wherein clustering comprises the steps of digitizing the images of the first word and the equivalent word images into a plurality of sets of pixels, each pixel having a binary values of one or zero;

generating a count of or signals by comparing the pixels of the first word image to each corresponding pixel in each equivalent image to count the number of pixels where at least one of the compared pixels has a binary value of one;

generating a count of and signals by comparing the pixels of the first word image to each corresponding pixel of equivalent images to count the number of pixels where both of the compared pixels have a binary value of one;

determining equivalence by the ratio of the count of and signals to the count of or signals.

4. The method of claim 1 wherein the bit mapped image of one word is compared to bit mapped images of other words to determine equivalence.

5. The method of claim 1 wherein the bit mapped image of a first word is compared to a bit mapped image of a portion of a second word to determine equivalence between the first word and the portion of the second word.

6. The method of claim 5 wherein the portion of the second word is a prefix in said second word.

7. The method of claim 5 wherein the portion of the second word is a suffix in said second word.

8. The method of claim 5 wherein the portion of the second word is disposed between the first and the last character in the second word.

9. The method of claim 1 further comprising the step of selecting the reference characters for the first word in accordance with the reference characters comprising a majority of the equivalent images having the same recognized reference characters.

10. The method of claim 9 further comprising the step of

decomposing the bit mapped image of the first word into its characters and matching images of a first character to a second character to determine a font for the matched images.

11. The method of claim 9 further comprising the step of

decomposing the bit mapped image of a first word into two or more sub-images;

comparing the sub-images of the first word to images of other characters of other words to identify equivalent images for the sub-images of the first word;

comparing the equivalent images to reference words, reference word portions and reference characters to verify that the image of the first word corresponds to the most likely correct reference word.

12. The method of claim 11 further comprising re-recognizing the images on the medium, including the steps of

decomposing each image in to sub-images corresponding to other images recognized in the medium;

generating a lattice of overlapping sub-images by voting, font learning and verifying;

determining a relative score for each path through said lattice;

selecting the path with the highest score and outputting a reference word corresponding to the path with the highest score.

13. A system for recognizing words in a text on a medium comprising:

an optical character recognition machine for scanning the medium and generating bit mapped images of characters forming the words on the medium;

an image comparator for comparing a first bit mapped image of a first number of characters in one word to one or more bit mapped images of characters in other words in order to identify equivalent bit mapped images of said first bit mapped image;

a reference character recognizer for comparing the equivalent bit mapped images to reference characters in order to recognize each bit mapped character as one of said reference characters;

means for comparing the corresponding recognized reference characters of each equivalent image to each other and selecting the reference characters identified for equivalent bit mapped characters when the same reference characters are identified for corresponding bit mapped characters in said equivalent bit mapped images; and

means for further processing said bit mapped images when different reference characters are recognized for corresponding bit mapped characters in said equivalent bit mapped images.

14. The system of claim 13 further comprising means for clustering equivalent images.

15. The system of claim 13 wherein the means for clustering comprises

means for digitizing the images of the first word and digitizing equivalent word images into sets of pixels, each pixel having a binary values of one or zero;

means for counting a first number or signals by comparing the pixels of the first word image to each corresponding pixel in each equivalent image and counting the number of pixels where at least on of the compared pixels has a binary value of one;

means for counting a second number of signals by comparing the pixels of the first word image to each corresponding pixel of equivalent images and counting the number of pixels where both of the compared pixels have a binary value of one;

means for determining equivalence in accordance with a ratio of the count of and signals to the count of or signals.

16. The system of claim 13 wherein the bit mapped image of one word is compared to bit mapped images of other words to determine equivalence.

17. The system of claim 13 wherein the bit mapped image of a first word is compared to a bit mapped image of a portion of a second word to determine equivalence between the first word and the portion of the second word.

18. The system of claims 17 wherein the portion of the second word is a prefix in said second word.

19. The system of claims 17 wherein the portion of the second word is a suffix in said second word.

20. The system of claim 17 wherein the portion of the second word is disposed between the first and the last character in the second word.

21. The system of claim 13 further comprising means for selecting the reference characters for the first word in accordance with the reference characters comprising a majority of the equivalent images having the same recognized reference characters.

22. The system of claim 21 further comprising means for decomposing the bit mapped image of the first word into its characters and matching images of a first character to a second character to determine a font for the matched images.

23. The system of claim 21 further comprising the step of

means for decomposing the bit mapped image of a first word into two or more sub-images;

means for comparing the sub-images of the first word to images of other characters of other words to identify equivalent images for the sub-images of the first word;

means for comparing the equivalent images to reference words, reference word portions and reference characters to verify that the image of the first word corresponds to the most likely correct reference word.

24. The system of claim 23 further comprising means for re-recognizing the images on the medium, including

means for decomposing each image in to sub-images corresponding to other images recognized in the medium;

means for generating a lattice of overlapping sub-images by voting, font learning and verifying;

means for determining the score of each path though said lattice;

means for selecting the path with the highest score and outputting a reference word corresponding to the path with the highest score.