SYSTEM AND METHOD FOR LOCALIZING DATA FIELDS ON STRUCTURED AND SEMI-STRUCTURED FORMS

• US 20140003721A1
• Filed: 06/29/2012
• Published: 01/02/2014
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Saund, Eric
• Granted Patent: US 8,781,229 B2
• Time in Patent Office: Days
• US Class Current: 382/182
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

A method and system to localize data fields of a form. An image of a form is received, where the form includes data fields. Word boxes of the image are identified. The word boxes are grouped into candidate zones, where each of the candidate zones includes one or more of the word boxes. Hypotheses are formed from the data fields and the candidate zones, where each hypothesis assigns one of the candidate zones to one of the data fields or a null data field. A constrained optimization search of the hypotheses is performed for an optimal set of hypotheses. The optimal set of hypotheses assigns word box groups to corresponding data fields.

Claims

1. A method for localizing data fields of a form, said method comprising:

receiving by at least one processor an image of a form, the form including data fields;

identifying by the at least one processor word boxes of the image;

grouping by the at least one processor the word boxes into candidate zones, each candidate zone including one or more of the word boxes;

forming by the at least one processor hypotheses from the data fields and the candidate zones, each hypothesis assigning one of the candidate zones to one of the data fields or a null data field; and

,

performing by the at least one processor a constrained optimization search of the hypotheses for an optimal set of hypotheses, the optimal set of hypotheses optimally assigning word boxes to corresponding data fields.

2. The method according to claim 1, wherein the form is a color-dropout form and the image is without background information of the form.

3. The method according to claim 1, wherein the identifying includes:

whole page optical character recognizing the image to identify characters of the image; and

,

grouping the identified characters to form the word boxes.

4. The method according to claim 1, wherein the candidate zones include a candidate zone for each contiguous sequence of one or more word boxes on a common text line.

5. The method according to claim 1, wherein at least one of the word boxes lies outside nominal bounds of the associated data field.

6. The method according to claim 1, wherein the hypotheses include a hypothesis for each combination of data field and candidate zone.

7. The method according to claim 1, further including:

determining, for each of the hypotheses, an assignment quality.

8. The method according to claim 7, wherein the assignment quality for each of the hypotheses assigning a candidate zone to one of the data fields is based on text-based and layout-based comparison of the candidate zone and the data field.

9. The method according to claim 7, wherein the assignment quality for each of the hypotheses assigning a candidate zone to one of the data fields is based on a template model, the template model identifying, for each data field of the form, type of text pattern the data field is expected to contain and placement, including location and size, of the data field on the form.

10. The method according to claim 7, wherein the constrained optimization search is constrained by a hard constraint and a soft constraint, the soft constraint giving preference to sets of hypotheses with high assignment quality, and the hard constraint precluding a set of hypotheses from including overlapping word-box support of candidate zones.

11. The method according to claim 1, where constrained optimization search gives preference to sets of hypotheses which minimize unassigned word boxes.

12. The method according to claim 1, wherein the constrained optimization search is performed by a Best-First-Leaf-Search (BFLS) optimization algorithm.

13. A method for extracting data from a form, said method comprising:

the method according to claim 1; and

,

extracting data from the word boxes and assigning the extracted data to corresponding data fields based on the optimal set of hypotheses.

14. A system for localizing data fields of a form, said system comprising:

at least one processor programmed to;

receive an image of a form, the form including data fields;

identify word boxes of the image;

group the word boxes into candidate zones, each candidate zone including one or more of the word boxes;

form hypotheses from the data fields and the candidate zones, each hypothesis assigning one of the candidate zones to one of the data fields or a null data field; and

,

perform a constrained optimization search of the hypotheses for an optimal set of hypotheses, the optimal set of hypotheses optimally assigning word boxes to corresponding data fields.

15. The system according to claim 14, wherein the form is a color-dropout form and the image is without background information of the form.

16. The system according to claim 14, further including:

determining, for each of the hypotheses, an assignment quality.

17. The system according to claim 16, wherein the constrained optimization search is constrained by a hard constraint and a soft constraint, the soft constraint giving preference to sets of hypotheses with high assignment quality, and the hard constraint precluding a set of hypotheses from including zones that include the same word-box.

18. The system according to claim 14, wherein the constrained optimization search is performed by a Best-First-Leaf-Search (BFLS) optimization algorithm.

19. A system for extracting data from a form, said system comprising:

the system according to claim 14; and

,

at least one processor programmed to;

extract data from the word boxes; and

,

assign the extracted data to corresponding data fields based on the optimal set of hypotheses.

20. A data extraction system including:

at least one processor programmed to;

receive an image of a form and a template model of the form, the form including data fields;

identify word boxes of the image;

group the word boxes into candidate zones, each candidate zone including one or more of the word boxes;

form hypotheses from the data fields and the candidate zones, each hypothesis assigning one of the candidate zones to one of the data fields or a null data field;

determine, for each of the hypotheses, an assignment quality, wherein the assignment quality for each of the hypotheses assigning a candidate zone to one of the data fields is based on a template model of the form;

perform a constrained optimization search of the hypotheses for an optimal set of hypotheses based on assignment quality, the optimal set of hypotheses optimally assigning word boxes to corresponding data fields and the hypotheses of the optimal set of hypotheses being non-overlapping in word-box support; and

,

extract data from the word boxes and assign the extracted data to corresponding data fields based on the optimal set of hypotheses.