Knowledge-based document analysis system

• US 5,937,084 A
• Filed: 05/22/1996
• Issued: 08/10/1999
• Est. Priority Date: 05/22/1996
• Status: Expired due to Term

• Current Assignee: Cufer Asset Ltd LLC (Intellectual Ventures LLC)
• Original Assignee: NCR Corporation
• Inventors: Peng, Antai, Crabtree, Ralph N.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/652,283
• Time in Patent Office: 1,175 Days
• Field of Search: 382/190, 382/175, 382/176, 382/228, 382/286, 382/137, 382/138, 382/139, 382/140, 382/317, 382/224, 382/225, 382/226, 382/227, 364/225.3, 707/500
• US Class Current: 382/137
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G07D 7/2016 using feature extraction, e.g. segmentation, edge detection or Hough-transformation

Abstract

A knowledge-based document analysis system and method for identifying and decomposing constrained and unconstrained images of documents is disclosed. Low level features are extracted within bitonal and grayscale images. Low level features are passed to a document classification means which forms initial hypotheses about the document class. For constrained documents, the document analysis system sorts through various models to determine the exact type of document and then extracts the relevant fields for character recognition. For unconstrained documents, through the use of a blackboard architecture which includes a knowledge database and knowledge sources, the document analysis means creates information and hypotheses to identify and locate relevant fields within the document. These fields are then sent for optical character recognition.

Claims

1. A system for analyzing a target document including at least one informational element, the system comprising:

(a) means for receiving a digitized image of the target document;

(b) means for extracting low level features from the digitized image;

(c) means for classifying the document based upon the extracted low level features from the digitized image to identify a most probable document type from a plurality of possible document classes that the target document most closely matches, wherein the means for classifying performs the steps of;

(i) extracting a sample immediate feature set from at least one sample document for each document class, wherein each sample immediate feature set includes at least one feature of a sample document;

(ii) Generating a sample indirect feature set for each sample document;

(iii) generating a target document immediate feature set and a target document indirect feature set, the target document immediate feature set comprising information describing a location and a type indicator for basic image features of the target document, and the target document indirect feature set comprising information summarizing attributes of the immediate features in the target document immediate feature set;

(iv) comparing the target document indirect feature set with each of the sample indirect feature sets; and

(v) classifying the target document responsive to the comparison of step (iv) to determine the most probable document type for the target document; and

(d) means for analyzing the target document in order to extract informational data associated with the at least one informational element based upon the most probable document type identified by the classifying means.

2. The system of claim 1, wherein the extracting means performs the steps of:

(i) generating the coordinates of a region that encloses each of the at least one informational elements;

(ii) generating a type indicator corresponding to the type of informational element located within the region;

(iii) transmitting the coordinates and the type indicator to the classifying means.

3. The system of claim 2, wherein the region is a rectangle.

4. The system of claim 2, wherein the type indicator is generated to correspond to an informational type selected from the group of:

machine print, hand print, vertical lines, horizontal lines or noisy regions.

5. The system of claim 1, wherein the at least one sample document may be selected from the group of:

business check, deposit slip, giro or personal check.

6. The system of claim 1, wherein the sample immediate feature set may include a feature selected from the group of:

machine print, hand print, vertical lines or horizontal lines.

7. The system of claim 1, wherein the sample indirect feature set may include a feature selected from the group of:

image width, document boundary width, horizontal line total length, horizontal line total count, horizontal line average length, vertical line total length, vertical line total count, vertical line average length, machine print total area, machine print total count, machine print average area, hand print total area, hand print total count, hand print average area, machine print vs. hand print area ratio, machine print vs. hand print count ratio, machine print vs. hand print average area ratio, or total number of boxes.

8. The system of claim 1, wherein the analyzing means performs the steps of:

(i) responsive to the classifying means, determining whether the target document is constrained;

(ii) if the target document is constrained, selecting one of a plurality of document models that matches the target document; and

(iii) locating the at least one information element of the selected target document and determining its type and value.

9. The system of claim 1, wherein the analyzing means performs the steps of:

(i) responsive to the classifying means, determining whether the location and characteristics of zones of interest in the target document are unconstrained; and

(ii) if so, determining the location and characteristics of the zones of interest, comprising steps of;

(A) determining which of a plurality of knowledge sources may be executed;

(B) selecting a best knowledge source to execute based on the type of the target document and any accumulated information for the target document; and

(C) executing the best knowledge source in order to determine the type and value of the at least one information element;

(D) accumulating information for the target document; and

(E) deciding whether accumulated information for the target document is sufficient for substantially locating and characterizing at least one of the zones of interest of the target document, and if not, repeating steps (A)-(E) to assemble more information for the target document until at least one zone of interest are substantially located and characterized.

10. The system of claim 1, further comprising an optical character recognition device for converting the informational data into associated characters.

11. The system of claim 1, wherein the means for analyzing locates those zones of the target document that most likely contain the informational data based on the most probable document class determined for the target document.

12. A process for analyzing a target document including at least one informational element, comprising the steps of:

(a) receiving a digitized image of the target document;

(b) extracting low level features from the digitized image;

(c) classifying the target document based upon the extracted low level features to identify a most probable document type from a plurality of possible document classes that the target document most closely matches, wherein the step of classifying comprises steps;

(i) extracting a sample immediate feature set from at least one sample document for each document class, and wherein each sample immediate feature set includes at least one feature of a corresponding sample document;

(ii) generating a sample indirect feature set for each sample document;

(iii) generating a target document immediate feature set and a target document indirect feature set, the target document immediate feature set comprising information describing a location and type indicator for basic image features of the target document, and the target document indirect feature set comprising information summarizing attributes of the immediate features in the target document immediate feature set;

(iv) comparing the target document indirect feature set with each of the sample indirect feature sets; and

(v) classifying the target document responsive to the comparison of step (iv) to determine the most probable document type for the target document; and

(d) analyzing the target document in order to extract informational data associated with the at least one informational element based upon the most probable document type.

13. The process of claim 12, wherein step (b) comprises the steps of:

(i) generating the coordinates of a region that encloses each of the at least one informational elements; and

(ii) generating a type indicator corresponding to the type of informational element located within the region.

14. The process of claim 13, wherein the region is a rectangle.

15. The process of claim 13, wherein the type indicator is generated to correspond to an informational type selected from the group of:

machine print, hand print, vertical lines, horizontal lines or noisy regions.

16. The process of claim 12, wherein the at least one sample document may be selected from the group of:

business check, deposit slip, giro or personal check.

17. The process of claim 12, wherein the sample immediate feature set may include a feature selected from the group of:

machine print, hand print, vertical lines or horizontal lines.

18. The process of claim 12, wherein the sample indirect feature set may include a feature selected from the group of:

image width, document boundary width, horizontal line total length, horizontal line total count, horizontal line average length, vertical line total length, vertical line total count, vertical line average length, machine print total area, machine print total count, machine print average area, hand print total area, hand print total count, hand print average area, machine print vs. hand print area ratio, machine print vs. hand print count ratio, machine print vs. hand print average area ratio, or total number of boxes.

19. The process of claim 12, wherein step (d) comprises the steps of:

(i) responsive to the classifying step, determining whether the target document is constrained; and

(ii) if the target document is constrained, locating the at least one information element of the target document responsive to the classification step and determining its type and value.

20. The process of claim 12, wherein the analyzing means performs the steps of:

(i) responsive to the classifying means, determining whether the location and characteristics of zones of interest in the target document are unconstrained; and

(ii) if so, the location and characteristics of the zones of interest, comprising steps of;

(A) determining which of a plurality of knowledge sources may be executed;

(B) selecting a best knowledge source to execute based on the type of the target document and any accumulated information for the target document; and

(C) executing the best knowledge source in order to determine the type and value of the at least one information element;

(D) accumulating information for the target document; and

(E) deciding whether accumulated information for the target document is sufficient for substantially locating and characterizing at least one of the zones of interest of the target document, and if not, repeating steps (A)-(E) to assemble more information for the target document until all zones of interest are substantially located and characterized.

21. The process of claim 12, wherein the analyzing step comprises the step of locating those zones of the target document that most likely contain the informational data based on the most probable document class determined for the target document.