Systems and methods for automatically identifying document information

• US 10,127,444 B1
• Filed: 03/09/2017
• Issued: 11/13/2018
• Est. Priority Date: 03/09/2017
• Status: Active Grant

• Current Assignee: Coupa Software Incorporated
• Original Assignee: Coupa Software Incorporated
• Inventors: Burch, Mark Oliver, Borhanazad, Hanieh
• Primary Examiner(s): Nguyen, Maikhanh
• Application Number:
  US15/454,987
• Time in Patent Office: 614 Days
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

Described herein is a computer implemented method for processing an electronic document. The method comprises accessing a comparison set of reference document codifications, each reference document codification in the comparison set comprising a plurality of canonical feature codifications. Each canonical feature codification in each reference document codification in the comparison set is processed by determining whether the electronic document has one or more text rectangles in a potential position of the canonical feature and, in response determining that the electronic document has one or more text rectangles in a potential position of the canonical feature, recording a preliminary association between the or each text rectangle and the canonical feature. For each text rectangle preliminarily associated with one or more canonical features, a final canonical feature assignment is determined for the text rectangle based on the one or more preliminarily associated canonical features.

Claims

1. A computer implemented method for processing an electronic document, the method comprising:

receiving the electronic document;

generating an initial codification of the electronic document, the initial codification of the electronic document comprising a plurality of canonical feature codifications, each canonical feature codification comprising a plurality of attribute values describing attributes of the canonical feature as it appears in the electronic document;

accessing a reference set of reference document codifications;

for each reference document codification in the reference set, determining a similarity between the reference document codification and the initial codification of the electronic document;

generating a comparison set of reference document codifications by including at most a threshold number of reference document codifications that are determined to be the most similar to the initial codification of the electronic document,

each reference document codification in the comparison set comprising a plurality of canonical feature codifications, each canonical feature codification comprising a plurality of attribute values describing a position of the canonical feature in the reference document;

processing each canonical feature codification in each reference document codification in the comparison set by;

determining whether the electronic document has one or more text rectangles in a potential position of the canonical feature, the potential position of the canonical feature defined with reference to the attribute values of the canonical feature in the canonical feature codification; and

in response determining that the electronic document has one or more text rectangles in a potential position of the canonical feature, recording a preliminary association between the text rectangle and the canonical feature; and

for each text rectangle preliminarily associated with one or more canonical features, determining a final canonical feature assignment for the text rectangle, the final canonical feature assignment being determined based on the one or more canonical features preliminarily associated with the text rectangle.

2. The computer implemented method according to claim 1, wherein:

determining a similarity between a given reference document codification and the initial codification of the electronic document comprises processing the given reference document codification and the initial codification of the electronic document to calculate a similarity measure in respect of the given reference document; and

generating the comparison set comprises including at most the threshold number of reference document codifications with the highest similarity measure.

3. The computer implemented method according to claim 2, wherein the similarity measure is calculated based on comparing corresponding pairs of attribute values in the given reference document codification and the initial codification of the electronic document.

4. The computer implemented method according to claim 1, further comprising:

processing the electronic document to identify text rectangles therein; and

generating a text rectangle dataset for the electronic document, the text rectangle dataset storing text rectangle details in respect of each identified text rectangle, the text rectangle details for a given text rectangle comprising positional details defining a position of the text rectangle in the electronic document;

and wherein;

determining whether the electronic document has one or more text rectangles in a potential position of the canonical feature comprises searching the text rectangle data set.

5. The computer implemented method according to according to claim 1, wherein the plurality of attribute values describing a given canonical feature comprise one or more attribute values selected from a group comprising:

a font style attribute value, a font size attribute value, a font weight attribute value, and a data type attribute value.

6. The computer implemented method according to claim 1, wherein reference document codifications are generated in accordance with a document codification template, the document codification template defining an order of document features and attributes of those features.

7. The computer implemented method according to claim 6, wherein the document features defined by the codification template comprise the plurality of canonical features and a document-level feature.

8. The computer implemented method according to claim 7, wherein attributes of the document-level feature comprise one or more attribute values selected from a group comprising:

a document density, a partial document density, a document height, a document width, and a document zero point.

9. The computer implemented method according to claim 1, further comprising extracting data in respect of at least one canonical feature from the electronic document by:

identifying a text rectangle with a final canonical feature assignment; and

extracting the text from the identified text rectangle as the canonical feature assigned to that text rectangle.

10. A system for processing an electronic document, the system comprising:

one or more processors;

one or more non-transitory computer-readable storage media storing sequences of instructions which, when executed by the one or more processors, cause the one or more processors to;

receive the electronic document;

generating an initial codification of the electronic document, the initial codification of the electronic document comprising a plurality of canonical feature codifications, each canonical feature codification comprising a plurality of attribute values describing attributes of the canonical feature as it appears in the electronic document;

accessing a reference set of reference document codifications;

for each reference document codification in the reference set, determining a similarity between the reference document codification and the initial codification of the electronic document;

generating a comparison set of reference document codifications by including at most a threshold number of reference document codifications that are determined to be the most similar to the initial codification of the electronic document,

each reference document codification in the comparison set comprising a plurality of canonical feature codifications, each canonical feature codification comprising a plurality of attribute values describing a position of the canonical feature in the reference document;

process each canonical feature codification in each reference document codification in the comparison set by;

determining whether the electronic document has one or more text rectangles in a potential position of the canonical feature, the potential position of the canonical feature defined with reference to the attribute values of the canonical feature in the canonical feature codification; and

in response determining that the electronic document has one or more text rectangles in a potential position of the canonical feature, recording a preliminary association between the text rectangle and the canonical feature; and

for each text rectangle preliminarily associated with one or more canonical features, determine a final canonical feature assignment for the text rectangle, the final canonical feature assignment being determined based on the one or more canonical features preliminarily associated with the text rectangle.

11. The system according to claim 10, wherein:

determining a similarity between a given reference document codification and the initial codification of the electronic document comprises processing the given reference document codification and the initial codification of the electronic document to calculate a similarity measure in respect of the given reference document; and

generating the comparison set comprises including at most the threshold number of reference document codifications with the highest similarity measure.

12. The system according to claim 11, wherein the similarity measure is calculated based on comparing corresponding pairs of attribute values in the given reference document codification and the initial codification of the electronic document.

13. The system according to claim 10, wherein when executed, the sequences of instructions further cause the one or more processors to:

process the electronic document to identify text rectangles therein; and

generate a text rectangle dataset for the electronic document, the text rectangle dataset storing text rectangle details in respect of each identified text rectangle, the text rectangle details for a given text rectangle comprising positional details defining a position of the text rectangle in the electronic document; and

wherein;

determining whether the electronic document has one or more text rectangles in a potential position of the canonical feature comprises searching the text rectangle data set.

14. The system according to according to claim 10, wherein the plurality of attribute values describing a given canonical feature comprise one or more attribute values selected from a group comprising:

a font style attribute value, a font size attribute value, a font weight attribute value, and a data type attribute value.

15. The system according to claim 10, wherein reference document codifications are generated in accordance with a document codification template, the document codification template defining an order of document features and attributes of those features.

16. The system according to claim 15, wherein the document features defined by the codification template comprise the plurality of canonical features and a document-level feature.

17. The system according to claim 16, wherein attributes of the document-level feature comprise one or more attribute values selected from a group comprising:

a document density, a partial document density, a document height, a document width, and a document zero point.

18. The system according to claim 10, wherein when executed, the sequences of instructions further cause the one or more processors to extract data in respect of at least one canonical feature from the electronic document by:

identifying a text rectangle with a final canonical feature assignment; and

extracting the text from the identified text rectangle as the canonical feature assigned to that text rectangle.