Automatic document separation

• US 8,693,043 B2
• Filed: 12/19/2003
• Issued: 04/08/2014
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Tungsten Automation Corp.
• Original Assignee: Kofax Incorporated
• Inventors: Schmidtler, Mauritius A. R., Texeira, Scott S., Harris, Christopher K., Samat, Sameer, Borrey, Roland, Macciola, Anthony
• Primary Examiner(s): Demeter, Hilina K
• Application Number:
  US10/742,131
• Publication Number:
  US 20050134935A1
• Time in Patent Office: 3,763 Days
• Field of Search: 358/1.18, 358/448, 358/462, 358/1.9, 358/2.1
• US Class Current: 358/1.18
• CPC Class Codes: G06F 40/10 Text processing natural language analysis G06F40/20; semantic analysis G06F40/30; processing or translation of natural language G06F40/40
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition
• CPC Class Codes: H04N 1/32112 in a separate computer file, document page or paper sheet, e.g. a fax cover sheet H04N1/32122 takes precedence
• CPC Class Codes: H04N 2201/3225 of data relating to an image, a page or a document
• CPC Class Codes: H04N 2201/3243 of type information, e.g. handwritten or text document

Abstract

A method and system for delineating document boundaries and identifying document types by analyzing digital images of one or more documents, automatically categorizing one or more pages or subdocuments within the one or more documents and automatically generating delineation identifiers, such as computer-generated images of separation pages inserted between digital images belonging to different categories, a description of the categorization sequence of the digital images, or a computer-generated electronic label affixed or associated with said digital images.

Claims

1. In a computer-based system, a method of delineating document boundaries and identifying document types, comprising:

automatically categorizing a plurality of document images into a plurality of predetermined categories in accordance with classification rules for said categories; and

automatically generating at least one identifier for identifying which of said plurality of document images belongs to which of said at least two categories.

2. The method of claim 1 wherein said at least one identifier comprises a computer-generated separation page which is inserted between document images to delineate images belonging to different ones of said plurality of categories.

3. The method of claim 1 wherein said at least one identifier comprises a computer-readable description that identifies a categorization sequence for said plurality of digital images in accordance with their categorization.

4. The method of claim 3 wherein said computer-readable description comprises an XML message.

5. The method of claim 1 wherein said at least one identifier comprises at least one computer-generated label that is electronically associated with at least one of said plurality of document images.

6. The method of claim 1 wherein said plurality of categories comprises at least two different form types used in a financial transaction.

7. The method of claim 6 wherein said plurality of categories further comprise first, middle and end page categories for each of said at least two different form types.

8. The method of claim 1 wherein said step of automatically categorizing comprises:

producing an output score for each document image; and

using a graph search algorithm to determine an optimum categorization sequence from a plurality of possible categorization sequences for said plurality of document images based on said output scores.

9. The method of claim 8 wherein said output scores represents a probability that each document image belongs to at least one respective category from said plurality of categories.

10. The method of claim 8 wherein said step of using a graph search algorithm comprises:

using a graph structure to calculate a total output score, based on said output scores for each of said plurality of document images, for each said possible categorization sequence; and

determining which categorization sequence yields the highest total output score.

11. The method of claim 8 wherein said output scores represent a conditional probability that each document image belongs to at least one respective category from said plurality of categories, wherein said conditional probability for each document image depends on at least one category chosen for at least one preceding or subsequent document image.

12. The method of claim 8 wherein said step of automatically categorizing further comprises applying a manually generated classification rule that eliminates at least one possible categorization sequence.

13. The method of claim 12 wherein said at least one possible categorization sequence comprises a starting page of a first document type followed by a starting page of a second document type before an ending page of the first document type is identified.

14. The method of claim 12 wherein said at least one possible categorization sequence comprises two consecutive pages of a first document type known to have a predefined number of pages.

15. The method of claim 1 wherein said at least one document comprises a plurality of bank loan documents.

16. The method of claim 1 wherein said at least one document comprises a plurality of insurance forms.

17. The method of claim 1 wherein said at least one document comprises a plurality of tax forms.

18. The method of claim 1 wherein said at least one document comprises a plurality of employment forms.

19. The method of claim 1 wherein said at least one document comprises a plurality of healthcare forms.

20. The method of claim 1 wherein said at least one document comprises a plurality of invoice forms.

21. In a computer-based system, a method of delineating document boundaries and identifying document types, comprising:

automatically categorizing a plurality of document images into a plurality of predetermined categories in accordance with classification rules for said categories, comprising;

producing an output score for each document image; and

using a graph search algorithm to determine an optimum categorization sequence from a plurality of possible categorization sequences for said plurality of document images based on said output scores, comprising;

using a graph structure to calculate a total output score, based on said output scores for each of said plurality of document images, for each said possible categorization sequence; and

determining which categorization sequence yields the highest total output score; and

automatically generating at least one identifier for identifying which of said plurality of document images belongs to which of said at least two categories, wherein said graph structure is implemented using a finite state transducer wherein said plurality of document images comprise inputs and said plurality of categorization sequences comprise outputs.

22. The method of claim 21 wherein said graph structure is implemented using a weighted finite state transducer having said plurality of document images as inputs and said plurality of categorization sequences as outputs, wherein each categorization sequence has associated therewith a weighted value based on said output scores.

23. A non-transitory computer-readable medium for storing computer executable instructions that when executed by a computer perform a method of delineating document boundaries and identifying document types, said method comprising:

automatically categorizing a plurality of document images into a plurality of predetermined categories in accordance witch classification rules for said categories; and

automatically generating at least one identifier for identifying which of said plurality of document images belongs to which of said at least two categories.

24. The computer-readable medium of claim 23 wherein said at least one identifier comprises a computer-generated separation page which is inserted between document images to delineate images belonging to different ones of said plurality of categories.

25. The computer-readable medium of claim 23 wherein said at least one identifier comprises a computer-readable description that identifies a categorization sequence for said plurality of digital images in accordance with their categorization.

26. The computer-readable medium of claim 25 wherein said computer-readable description comprises an XML message.

27. The computer-readable medium of claim 23 wherein said at least one identifier comprises at least one computer-generated label that is electronically associated with at least one of said plurality of document images.

28. The computer-readable medium of claim 23 wherein said plurality of categories comprises at least two different form types used in a financial transaction.

29. The computer-readable medium of claim 28 wherein said plurality of categories further comprise first, middle and end page categories for each of said at least two different form types.

30. The computer-readable medium of claim 23 wherein said step of automatically categorizing comprises:

producing an output score for each document image; and

using a graph search algorithm to determine an optimum categorization sequence from a plurality of possible categorization sequences for said plurality of document images based on said output scores.

31. The computer readable medium of claim 30 wherein said output scores represent a probability that each document image belongs to at least one respective category from said plurality of categories.

32. The computer-readable medium of claim 30 wherein said step of using a graph search algorithm comprises using a graph structure to calculate a total output score, based on said output scores for each of said plurality of document images, for each said possible categorization sequence;

and determining which categorization sequence yields the highest total output score.

33. The computer-readable medium of claim 30 wherein said output scores represent a conditional probability that each document image belongs to at least one respective category from said plurality of categories, wherein said conditional probability for each document image depends on at least one category chosen for at least one preceding or subsequent document image.

34. The computer-readable medium of claim 30 wherein said step of automatically categorizing further comprises applying a manually generated classification rule that eliminates at least one possible categorization sequence.

35. The computer-readable medium of claim 34 wherein said at least one possible categorization sequence comprises a starting page of a first document type followed by a starting page of a second document type before an ending page of the first document type is identified.

36. The computer-readable medium of claim 34 wherein said at least one possible categorization sequence comprises two consecutive pages of a first document type known to have a predefined number of pages.

37. A non-transitory computer-readable medium for storing computer executable instructions that when executed by a computer perform a method of delineating document boundaries and identifying document types, said method comprising:

automatically categorizing a plurality of document images into a plurality of predetermined categories in accordance with classification rules for said categories, comprising;

producing an output score for each document image; and

using a graph search algorithm to determine an optimum categorization sequence from a plurality of possible categorization sequences for said plurality of document images based on said output scores, comprising;

using a graph structure to calculate a total output score, based on said output scores for each of said plurality of document images, for each said possible categorization sequence; and

determining which categorization sequence yields the highest total output score; and

automatically generating at least one identifier for identifying which of said plurality of document images belongs to which of said at least two categories, wherein said graph structure is implemented using a finite state transducer wherein said plurality of document images comprise inputs and said plurality of categorization sequences comprise outputs.

38. The computer-readable medium of claim 37 wherein said graph structure is implemented using a weighted finite state transducer having said plurality of document images as inputs and said plurality of categorization sequences as outputs, wherein each categorization sequence has associated therewith a weighted value based on said output scores.