Automatic document classification using lexical and physical features

• US 8,503,797 B2
• Filed: 09/05/2008
• Issued: 08/06/2013
• Est. Priority Date: 09/05/2007
• Status: Active Grant

• Current Assignee: NEAT Company Incorporated Doing Business As Neatreceipts Incorporated
• Original Assignee: The Neat Company, Inc.
• Inventors: Turkelson, Adam, Ma, Huanfeng
• Primary Examiner(s): Seth, Manav
• Application Number:
  US12/205,613
• Publication Number:
  US 20090067729A1
• Time in Patent Office: 1,796 Days
• Field of Search: None
• US Class Current: 382/224
• CPC Class Codes: G06F 16/353 into predefined classes
• 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

Abstract

An automatic document classification system is described that uses lexical and physical features to assign a class c_iεC{c₁, c₂, . . . , c_i} to a document d. The primary lexical features are the result of a feature selection method known as Orthogonal Centroid Feature Selection (OCFS). Additional information may be gathered on character type frequencies (digits, letters, and symbols) within d. Physical information is assembled through image analysis to yield physical attributes such as document dimensionality, text alignment, and color distribution. The resulting lexical and physical information is combined into an input vector X and is used to train a supervised neural network to perform the classification.

Claims

1. A method for classifying a scanned document, comprising:

extracting non-graphical physical attributes of the scanned document using a processor programmed to extract said physical attributes, said non-graphical physical attributes excluding graphical attributes relating to the way content is organized and displayed within the scanned document; and

classifying the scanned document based on the extracted physical attributes of the scanned document.

2. The method of claim 1, further comprising:

creating an input vector from the extracted physical attributes; and

providing the input vector to a processing system to train the processing system to classify the document from one or more features of the input vector.

3. The method of claim 2, wherein extracting the physical attributes of the scanned document comprises cropping and/or rotating the scanned document as needed to create a processed scanned document for feature extraction.

4. The method of claim 3, wherein extracting physical attributes of the scanned document comprises extracting the size of the processed scanned document.

5. The method of claim 3, wherein extracting physical attributes of the scanned document comprises detecting the margin smoothness of the processed scanned document.

6. The method of claim 5, wherein detecting the margin smoothness of the processed scanned document comprises calculating a jig jag degree (D_jig-jag) by computing an average position of a margin of the document, computing a standard deviation of the margin, converting the margin into a sequence of numbers with values of 0, −

1, and 1 as follows;

7. The method of claim 3, wherein the extracting of physical attributes of the scanned document comprises detecting the colorfulness of the scanned document.

8. The method of claim 3, wherein the extracting of physical attributes of the scanned document comprises detecting whether the image is an inverse image of the scanned document.

9. The method of claim 3, wherein the extracting of physical attributes of the scanned document comprises detecting whether the scanned document is in a portrait or a landscape orientation.

10. The method of claim 9, wherein detecting whether the scanned document is in a portrait or a landscape orientation comprises:

defining three thresholds;

minimum black length, maximum black length, and minimum white length;

dividing the scanned document into non-overlapping square windows each with size N×

N;

ignoring windows without text;

computing horizontal and vertical projection profiles for each window with text;

checking black and white stripes on each projection profile and deciding if each black and white stripe has a black-and-white text pattern whereby all black stripe lengths are greater than or equal to the minimum black length and less than or equal to the maximum black length, all white stripe lengths are greater than or equal to the minimum white stripe length, and the maximum of a white stripe length is less than or equal to twice the minimum of a white stripe length;

determining from the black and white stripe check whether a horizontal projection profile has a black and white text pattern and, if so, determining that the window is in portrait mode;

determining from the black and white stripe check whether a vertical projection profile has a black and white text pattern and, if so, determining that the window is in landscape mode;

computing the squared sums of the horizontal and vertical projection profiles S_h and S_v, respectively, as follows;

11. The method of claim 3, wherein the extracting of physical attributes of the scanned document comprises detecting the presence of a logo in the scanned document.

12. The method of claim 11, wherein detecting the presence of a logo in the scanned document comprises:

identifying logo component candidates;

for each logo component candidate, counting the number of components covered by the logo component candidate;

if the number of components covered by the logo component candidate is greater than 1, then determining that the logo component candidate is a logo;

if the number of components covered by the logo component candidate is not greater than 1, counting the number of holes (N_hole) inside the logo component candidate;

if N_hole is less than or equal to 3, then determining that the logo component candidate is not a logo;

if N_hole is greater than 3, then counting the total number of pixels covered by the holes (P_hole) and comparing a number of pixels covered by the component; and

determining that the component is or is not a logo component as follows;

13. The method of claim 3, wherein the extracting of physical attributes of the scanned document comprises computing a text/nontext ratio of the scanned document.

14. The method of claim 2, further comprising collecting the physical attributes for the input vector, selecting at least one physical attribute from the collected physical attributes that describes a target class of said scanned document, and identifying the selected at least one physical attribute and target class to said processing system.

15. The method of claim 14, wherein the target class of said scanned document comprises either a receipt or a business card.

16. The method of claim 2, further comprising extracting lexical features from the scanned document, combining the extracted lexical features and extracted physical attributes into a unified set of features, and providing the unified set of features to the processing system to classify the scanned document.

17. A non-transitory computer readable storage medium having instructions stored thereon that when executed by a processor causes said processor to implement a method for classifying a scanned document, said method comprising:

extracting non-graphical physical attributes of the scanned document, said non-graphical physical attributes excluding graphical attributes relating to the way content is organized and displayed within the scanned document; and

classifying the scanned document based on the extracted physical attributes of the scanned document.

18. The medium of claim 17, further comprising instructions for:

creating an input vector from the extracted physical attributes; and

providing the input vector to a processing system to train the processing system to classify the document from one or more features of the input vector.

19. The medium of claim 18, wherein the instructions for extracting the physical attributes of the scanned document comprises instructions for cropping and/or rotating the scanned document as needed to create a processed scanned document for feature extraction.

20. The medium of claim 19, wherein the instructions for extracting physical attributes of the scanned document comprises instructions for extracting the size of the processed scanned document.

21. The medium of claim 19, wherein the instructions for extracting physical attributes of the scanned document comprises instructions for detecting the margin smoothness of the processed scanned document.

22. The medium of claim 21, wherein the instructions for detecting the margin smoothness of the processed scanned document comprises instructions for calculating a jig-jag degree (D_jig-jag) by computing an average position of a margin of the document, computing a standard deviation of the margin, converting the margin into a sequence of numbers with values of 0, −

1, and 1 as follows;

23. The medium of claim 19, wherein the instructions for extracting of physical attributes of the scanned document comprises instructions for detecting the colorfulness of the scanned document.

24. The medium of claim 19, wherein the instructions for extracting of physical attributes of the scanned document comprises instructions for detecting whether the image is an inverse image of the scanned document.

25. The medium of claim 19, wherein the instructions for extracting of physical attributes of the scanned document comprises instructions for detecting whether the scanned document is in a portrait or a landscape orientation.

26. The medium of claim 25, wherein the instructions for detecting whether the scanned document is in a portrait or a landscape orientation comprises instructions for:

defining three thresholds;

minimum black length, maximum black length, and minimum white length;

dividing the scanned document into non-overlapping square windows each with size N×

N;

ignoring windows without text;

computing horizontal and vertical projection profiles for each window with text;

checking black and white stripes on each projection profile and deciding if each black and white stripe has a black-and-white text pattern whereby all black stripe lengths are greater than or equal to the minimum black length and less than or equal to the maximum black length, all white stripe lengths are greater than or equal to the minimum white stripe length, and the maximum of a white stripe length is less than or equal to twice the minimum of a white stripe length;

determining from the black and white stripe check whether a horizontal projection profile has a black and white text pattern and, if so, determining that the window is in portrait mode;

determining from the black and white stripe check whether a vertical projection profile has a black and white text pattern and, if so, determining that the window is in landscape mode;

computing the squared sums of the horizontal and vertical projection profiles S_h and S_v, respectively, as follows;

27. The medium of claim 19, wherein the instructions for extracting of physical attributes of the scanned document comprises instructions for detecting the presence of a logo in the scanned document.

28. The medium of claim 27, wherein the instructions for detecting the presence of a logo in the scanned document comprises instructions for:

identifying logo component candidates;

for each logo component candidate, counting the number of components covered by the logo component candidate;

if the number of components covered by the logo component candidate is greater than 1, then determining that the logo component candidate is a logo;

if the number of components covered by the logo component candidate is not greater than 1, counting the number of holes (N_hole) inside the logo component candidate;

if N_hole is less than or equal to 3, then determining that the logo component candidate is not a logo;

if N_hole is greater than 3, then counting the total number of pixels covered by the holes (P_hole) and comparing a number of pixels covered by the component; and

determining that the component is or is not a logo component as follows;

29. The medium of claim 19, wherein the instructions for extracting of physical attributes of the scanned document comprises instructions for computing a text/nontext ratio of the scanned document.

30. The medium of claim 18, further comprising instructions for collecting the physical attributes for the input vector, selecting at least one physical attribute from the collected physical attributes that describes a target class of said scanned document, and identifying the selected at least one physical attribute and target class to said processing system.

31. The medium of claim 30, wherein the target class of said scanned document comprises either a receipt or a business card.

32. The medium of claim 18, further comprising instructions for extracting lexical features from the scanned document, combining the extracted lexical features and extracted physical attributes into a unified set of features, and providing the unified set of features to the processing system to classify the scanned document.

33. A system for classifying a document, comprising:

a scanner that scans and digitizes images on the document;

a processing system adapted to extract non-graphical physical attributes of the scanned document, said non-graphical physical attributes excluding graphical attributes relating to the way content is organized and displayed within the scanned document, and to classify the scanned document based on the extracted physical attributes of the scanned document.

34. The system of claim 33, wherein the processing system is further adapted to create an input vector from the extracted physical attributes and to provide the input vector to a neural network to train the neural network to classify the document from one or more features of the input vector.

35. The system of claim 34, wherein the processing system extracts the physical attributes of the scanned document by cropping and/or rotating the scanned document as needed to create a processed scanned document for feature extraction.

36. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by extracting the size of the processed scanned document.

37. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by detecting the margin smoothness of the processed scanned document.

38. The system of claim 37, wherein the processing system detects the margin smoothness of the processed scanned document by calculating a jig-jag degree (D_jig-jag) by computing an average position of a margin of the document, computing a standard deviation of the margin, converting the margin into a sequence of numbers with values of 0, −

1, and 1 as follows;

39. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by detecting the colorfulness of the scanned document.

40. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by detecting whether the image is an inverse image of the scanned document.

41. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by detecting whether the scanned document is in a portrait or a landscape orientation.

42. The system of claim 41, wherein the processing system detects whether the scanned document is in a portrait or a landscape orientation by:

defining three thresholds;

minimum black length, maximum black length, and minimum white length;

dividing the scanned document into non-overlapping square windows each with size N×

N;

ignoring windows without text;

computing horizontal and vertical projection profiles for each window with text;

checking black and white stripes on each projection profile and deciding if each black and white stripe has a black-and-white text pattern whereby all black stripe lengths are greater than or equal to the minimum black length and less than or equal to the maximum black length, all white stripe lengths are greater than or equal to the minimum white stripe length, and the maximum of a white stripe length is less than or equal to twice the minimum of a white stripe length;

determining from the black and white stripe check whether a horizontal projection profile has a black and white text pattern and, if so, determining that the window is in portrait mode;

determining from the black and white stripe check whether a vertical projection profile has a black and white text pattern and, if so, determining that the window is in landscape mode;

computing the squared sums of the horizontal and vertical projection profiles S_h and S_v, respectively, as follows;

43. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by detecting the presence of a logo in the scanned document.

44. The system of claim 43, wherein the processing system detects the presence of a logo in the scanned document by:

identifying logo component candidates;

for each logo component candidate, counting the number of components covered by the logo component candidate;

if the number of components covered by the logo component candidate is greater than 1, then determining that the logo component candidate is a logo;

if the number of components covered by the logo component candidate is not greater than 1, counting the number of holes (N_hole) inside the logo component candidate;

if N_hole is less than or equal to 3, then determining that the logo component candidate is not a logo;

if N_hole is greater than 3, then counting the total number of pixels covered by the holes (P_hole) and comparing a number of pixels covered by the component; and

determining that the component is or is not a logo component as follows;

45. The system of claim 35, wherein the processing system extracts physical attributes of the scanned document by computing a text/nontext ratio of the scanned document.

46. The system of claim 34, wherein the processing system further collects the physical attributes for the input vector, selects at least one physical attribute from the collected physical attributes that describes a target class of said scanned document, and identifies the selected at least one physical attribute and target class to said neural network.

47. The system of claim 46, wherein the target class of said scanned document comprises either a receipt or a business card.

48. The system of claim 34, wherein the processing system further extracts lexical features from the scanned document, combines the extracted lexical features and extracted physical attributes into a unified set of features, and provides the unified set of features to the neural network to classify the scanned document.