Document recognition and automatic indexing for optical character recognition

• US 4,949,392 A
• Filed: 05/20/1988
• Issued: 08/14/1990
• Est. Priority Date: 05/20/1988
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Barski, Lori L., Gaborski, Roger S.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Marcus, Joseph
• Application Number:
  US07/196,513
• Time in Patent Office: 816 Days
• Field of Search: 382/61, 382/30, 382/18, 382/69, 382/1, 382/17, 382/33, 382/42, 358/467, 358/261.1, 356/71, 209/534
• US Class Current: 382/283
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

A library of templates defining the spacings between pre-printed lines and the corresponding line lengths for a plurality of different business forms is compared with the image data of an unknown document to determine the known business form (template) to which the document corresponds. Once the form of the document is determined, the optical character recognition system may intelligently associate the text characters in certain locations on the document with information fields defined by the pre-printed lines. The pre-printed lines in the image data are determined from the corresponding template and removed from the image data prior to optical character recognition processing.

Claims

1. A lick document character recognition system for use with an optical character recognition system, said document character recognition system comprising:

means for storing in memory plural reference templates specifying spacings between and the lengths of pre-printed lines in corresponding plural pre-printed forms;

means for receiving incoming video data comprising successive video lines thereof representing the image of a document of unknown form;

means for generating a sample template from said incoming video data, said sample template specifying spacing between and lengths of pre-printed lines in said image of said document;

means for determining which one of said plural

reference templates most closely resembles said sample template;

buffer means for storing the video data representing said one document until said determining means identifies said one reference template; and

output processor means, responsive whenever said determining means identifies said one template, comprising (a) means for fetching the video data from said buffer means, (b) means for masking therefrom data representing pre-printed lines therein corresponding to the pre-printed line spacings and lengths in said one reference template, and (c) means for transmitting the data thus masked to said optical character recognition system.

2. The system of claim 1 wherein said plural reference templates and said sample template each specify the video line number of horizontal reprinted lines.

3. The system of claim 2 wherein said means for generating a sample template comprise:

means for generating a curve representing the linear density of "on" pixels in said video data as a function of video line number;

means for locating peaks exceeding a predetermined threshold in said curve and means for noting the locations of said peaks; and

means for determining the longest runlength of "on" video pixels in each video line corresponding to each one of said peaks.

4. The system of claim 3 wherein said means for generating a sample template further translates the noted locations of said peaks into a series of numbers representing spacings between successive horizontal lines in said image.

5. The system of claim 3 wherein said means for locating peaks in said curve comprise means for producing the differential of said curve and means for noting the locations of discontinuities in said differential of said curve.

6. The system of claim 1 wherein said means for determining which one of said plural reference templates most closely resembles said sample template comprises at least one of the following:

means for finding which one of said plural reference templates exactly matches said sample template and means for noting the identity thereof; and

means for computing a cross-correlation between each of said plural reference templates and said sample template and means for noting which one of said plural reference templates has the highest cross-correlation with said sample template.

7. The system of claim 6 wherein said means for determining include both said means for finding an exact match and said means for computing a cross-correlation, and wherein said determining means further comprises:

default means responsive whenever said means for finding fails to find an exact match for activating said means for computing said cross-correlation.

8. The system of claim 1 further comprising means for transmitting the contents of the one template identified by said determining means to said optical character recognition system and for means for transmitting said video data representing said one document to said optical character recognition system, whereby said optical character recognition system may associate the contents of said one template with the video data representing said one document.

9. The system of claim 1 wherein each of said templates comprises a pair of tables stored in memory, one of said tables listing spacings between subsequent pre-printed lines and the other of said tables represents the corresponding pre-printed line lengths, the contents of each of said two tables being arranged in order of the location of corresponding pre-printed lines on said image.

10. The system of claim 1 wherein said plural reference templates stored in said means for storing are generated by transmitting the image data of the corresponding plural forms in succession to said means for receiving incoming video data, whereby said means for generating a sample template generates corresponding plural sample templates comprising said plural reference templates, which may then be stored in said means for storing.

11. The system of claim 3 wherein said means for locating peaks in said curve comprise means for producing the differential of said curve and means for noting the locations of discontinuities in said differential of said curve.

12. The system of claim 1 wherein said plural reference templates stored in said means for storing are generated by transmitting the image data of the corresponding plural forms in succession to said means for receiving incoming video data, whereby said means for generating a sample template generates corresponding plural sample templates comprising said plural reference templates, which may then be stored in said means for storing.

13. A document character recognition system for use with an optical character recognition system, said document character recognition system comprising:

means for storing in memory plural reference templates specifying spacings between pre-printed lines in corresponding plural pre-printed forms;

means for receiving incoming video data comprising successive video lines thereof representing the image of a document of unknown form;

means for generating a sample template from said incoming video data, said sample template specifying spacings between pre-printed lines in said image of said document;

means for determining which one of said plural reference templates most closely resembles said sample template, wherein each of said templates comprises a pair of tables stored in memory, one of said tables listing spacings between subsequent pre-printed lines and the other of said tables representing the corresponding pre-printed line lengths, the contents of each of said two tables being arranged in order of the location of corresponding pre-printed lines of said image;

buffer means for storing the video data representing said one document until said determining means identifies said one reference template; and

output processor means, responsive whenever said determining means identifies said one template, comprising (a) means for fetching the video data from said buffer means, (b) means for masking thereof data representing pre-printed lines therein corresponding to the pre-printed line spacings and lengths in said one reference template, and (c) means for transmitting the data thus masked to said optical character recognition system.

14. The system of claim 13 further comprising means for transmitting the contents of the one template identified by said determining means to said optical character recognition and for means transmitting said video data representing said one document to said optical character recognition system, whereby said optical character recognition system may associate the contents of said one template with the video data representing said one document.

15. A document character recognition system for use with an optical character recognition system, said document character recognition system comprising:

means for storing in memory plural reference templates specifying spacings between pre-printed lines in corresponding plural pre-printed forms;

means for receiving incoming video data comprising successive video lines thereof representing the image of a document of unknown form;

means for generating a sample template from said incoming video data, said sample template specifying spacings between pre-printed lines in said image of said document;

means for determining which one of said plural reference templates most closely resembles said sample template, wherein said plural reference templates and said sample template each specify the video line number of horizontal pre-printed lines;

wherein said means for generating a sample template comprise;

means for generating a curve representing the linear density of "on" pixels in said video data as a function of video line number,

means for locating peaks exceeding a predetermined threshold in said curve and means for noting the locations of said peaks;

buffer means for storing the video data representing said one document until said determining means identifies said one reference template; and

output processor means, responsive whenever said determining means identifies said one template, comprising (a) means for fetching the video data from said buffer means, (b) means for masking therefrom data representing pre-printed lines therein corresponding to the pre-printed line spacings and lengths in said one reference template, and (c) means for transmitting the data thus masked to said optical character recognition system.

16. The system of claim 15 wherein said means for generating a sample template further translates the noted locations of said peaks into a series of numbers representing spacings between successive horizontal lines in said image.

17. A document character recognition system for use with an optical character recognition system, said document character recognition system comprising:

means for storing in memory plural reference templates specifying spacings between pre-printed lines in corresponding plural pre-printed forms;

means for receiving incoming video data comprising successive video lines thereof representing the image of a document of unknown form;

means for generating a sample template from said incoming video data, said sample template specifying spacings between pre-printed lines in said image of said document; and

means for determining which one of said plural reference templates most closely resembles said sample template;

wherein said means for determining which one of said plural reference templates most closely resembles said sample template comprises;

means for finding which one of said plural reference templates exactly matches said sample template and means for noting the identity thereof; and

means for computing a cross-correlation between each of said plural reference templates and said sample template and means for noting which one of said plural reference templates has the highest cross-correlation with said sample template;

wherein said determining means further comprises;

default means responsive whenever said means for finding fails to find an exact for activating said means for computing said cross-correlation.

18. A document character recognition method for use with an optical character recognition system, said document character recognition method comprising:

storing in memory plural reference templates specifying spacings between and the lengths of pre-printed lines if corresponding plural pre-printed forms;

receiving incoming video data comprising successive video lines thereof representing the image of a document of unknown form;

generating a sample template from said incoming video data, said sample template specifying spacing between and lengths of pre-printed lines in said image of said document;

determining which one of said plural reference templates most closely resembles said sample template;

storing the video data representing said one document in a buffer until said determining means identifies said one reference template; and

whenever said determining step identifies said one template, fetching the video data from said buffer means, masking therefrom data representing pre-printed lines therein corresponding to the pre-printed line spacings and lengths in said one reference template, and transmitting the data thus masked to said optical character recognition system.

19. The method of claim 18 wherein said plural reference templates and said sample template each specify the video line number of horizontal pre-printed lines.

20. The method of claim 19 wherein said generating step comprises:

generating a curve representing the linear density of "on" pixels in said video data as a function of video line number;

locating peaks exceeding a predetermined threshold in said curve and noting the locations of said peaks; and

determining the longest run length of "on" video pixels in each video line corresponding to each one of said peaks.

21. The method of claim 20 wherein said generating a sample template step further comprises translating the noted locations of said peaks into a series of numbers representing spacings between successive horizontal lines in said image.

22. The method of claim 18 wherein said step of determining which one of said plural reference templates most closely resembles said sample template comprises at least one of the following steps:

finding which one of said plural reference templates exactly matches said sample template and noting the identity thereof; and

computing a cross-correlation between each of said plural reference templates and said sample template and noting which one of said plural reference templates has the highest cross-correlation with said sample template.

23. The method of claim 18 further comprising transmitting the contents of the one template identified by said determining means to said optical character recognition system and transmitting said video data representing said one document to said optical character recognition system, whereby said optical character recognition system may associate the contents of said one template with the video data representing said one document.

24. The method of claim 19 wherein each of said templates comprises a pair of tables stored in memory, one of said tables listing spacings between subsequent pre-printed lines and the other of said tables represents the corresponding pre-printed line lengths, the contents of each of said two tables being arranged in order of the location of corresponding pre-printed lines on said image.