Form identification and processing system using hierarchical form profiles

• US 5,721,940 A
• Filed: 04/04/1997
• Issued: 02/24/1998
• Est. Priority Date: 11/24/1993
• Status: Expired due to Term

• Current Assignee: Canon Information Systems Incorporated (Canon Inc.)
• Original Assignee: Canon Information Systems Incorporated (Canon Inc.)
• Inventors: Wang, Shin-Ywan, Luther, Willis J.
• Primary Examiner(s): Fetting, Anton W.
• Application Number:
  US08/832,849
• Time in Patent Office: 326 Days
• Field of Search: 395/761, 395/766-771, 395/779-785, 382/175, 382/219, 382/283, 358/403, 358/453
• US Class Current: 715/200
• CPC Class Codes: G06F 40/174 Form filling; Merging
• 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: 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/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method and an apparatus for identifying completed forms includes scanning a plurality of different blank forms, and creating hierarchical profiles of each scanned blank form. Each hierarchical form profile is stored in a dictionary. Once the form dictionary is created, a completed form is scanned. A hierarchical profile of the completed form is created, and the hierarchical profile of the completed form is compared with stored hierarchical form profiles. In accordance with the result of comparison, one of the stored hierarchical form profiles is identified as corresponding to the completed form hierarchical profile. Based on the identity of the corresponding hierarchical form profile, the completed form can be routed for further processing. A further aspect of the invention makes it possible to extract data from predesignated fields which may be unique to that particular form within a completed form based on the form'"'"'s identity. Furthermore, by using the form dictionary, it is possible to identify a completed form, extract data from the completed form, store the data with the form'"'"'s identity, and display the completed form by drawing the identified form using the vectorized data from the form dictionary and superimposing the extracted data from the completed form into respective data fields.

Claims

1. A method for creating a form dictionary, the method comprising the steps of:

scanning a first blank form;

creating a hierarchical profile of the first blank form;

scanning a plurality of exemplary completed forms of the first blank form;

creating a hierarchical profile for each exemplary completed form;

comparing each completed form hierarchical profile with each other completed form hierarchical profile to determine invariant elements between each completed form hierarchical profile;

extracting the invariant elements;

correlating the blank form hierarchical profile with the extracted invariant elements;

creating a first enhanced blank form hierarchical profile based on the correlating step; and

storing the first enhanced blank form hierarchical profile in the form dictionary.

2. A method according to claim 1, further comprising the steps of:

scanning a second blank form;

creating a hierarchical profile of the second blank form;

scanning a plurality of exemplary completed forms of the second blank form;

creating a hierarchical profile of each exemplary completed form of the second blank form;

comparing the extracting invariant elements between the hierarchical profiles of each exemplary completed form of the second blank form;

correlating the second blank form hierarchical profile with the extracted invariant elements between the hierarchical profiles of each exemplary completed form of the second blank form to create a second enhanced blank form hierarchical profile; and

storing the second enhanced blank form hierarchical profile in the form dictionary.

3. A method according to claim 2, further comprising the step of disambiguating, wherein the step of disambiguating comprises the steps of:

comparing the first enhanced blank form hierarchical profile and the second enhanced blank form hierarchical profile to determine invariant elements between the first enhanced blank form hierarchical profile and the second enhanced blank form hierarchical profile;

discarding the invariant elements from the first enhanced blank form hierarchical profile and the second blank form hierarchical profile to produce disambiguated hierarchical profiles of the first and second blank forms; and

storing disambiguated hierarchical profiles of the first and second blank forms in the form dictionary.

4. A method for identifying a completed form using a form dictionary of hierarchical form profiles, each of said hierarchical form profiles consisting of vectorized data which defines features of a corresponding blank form, the method comprising the steps of:

creating hierarchical profiles of different blank forms;

comparing the hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements of each hierarchical profile in a form dictionary;

scanning a completed form;

creating a hierarchical profile of vectorized data corresponding to the completed form;

comparing the hierarchical profile of vectorized data corresponding to the completed form with the hierarchical form profiles in the form dictionary; and

identifying, in accordance with the comparing step, one of the hierarchical form profiles in the form dictionary as corresponding to the hierarchical profile of the completed form.

5. A method according to claim 4, further comprising the step of extracting portions of the hierarchical profile of vectorized data corresponding to the completed form which differ from the identified hierarchical form profile in the form dictionary.

6. A method according to claim 5, further comprising the step of routing the extracted portions for processing in accordance with the identity of the corresponding hierarchical form profile.

7. A method according to claim 4, further comprising the step of storing predetermined data from the extracted portions in accordance with the identity of the corresponding hierarchical form profile.

8. A method according to claim 4, further comprising the step of displaying selected data from the extracted portions in accordance with the identity of the corresponding hierarchical form profile.

9. A method according to claim 4, further comprising the step of optical character recognition of selected data from the extracted portions in accordance with the identity of the corresponding hierarchical form profile.

10. A method for displaying completed portions of a form, the method comprising the steps of:

creating hierarchical profiles of different blank forms;

comparing the hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements of each hierarchical profile in a form dictionary;

scanning a completed form;

creating a hierarchical profile of vectorized data which defines features of the completed form;

comparing the hierarchical profile of vectorized data defining features of the completed form with a hierarchical profile of a blank form in the form dictionary;

extracting portions of the hierarchical profile defining features of the completed form which differ from corresponding portions of the hierarchical profile of the blank form; and

displaying portions of the completed form which are dissimilar to corresponding portions of the blank form using the extracted portions of the hierarchical profile defining features of the completed form.

11. A method according to claim 10, wherein the step of extracting includes the step of extracting respective field header information for the extracted portions of the hierarchical profile of the completed form and displaying extracted portions with the respective header information.

12. A method according to claim 10, further comprising

scanning a plurality of exemplary completed forms corresponding to a blank form;

creating a hierarchical profile of vectorized data corresponding to each exemplary completed form;

comparing each exemplary completed form hierarchical profile to each other exemplary completed form hierarchical profile to determine invariant elements between each of the exemplary completed form hierarchical profiles of vectorized data;

extracting the invariant elements from the completed form hierarchical profiles;

correlating a hierarchical profile of vectorized data of the blank form and the extracted invariant elements from the completed form hierarchical profiles of vectorized data to create an enhanced blank form hierarchical profile of vectorized data; and

storing the enhanced blank form hierarchical profile of vectorized data in the form dictionary.

13. A method for routing completed forms, the method comprising the steps of:

scanning a plurality of different blank forms;

creating a hierarchical profile of vectorized data which defines features of a blank form for each scanned blank form;

comparing the hierarchical profiles to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements of each hierarchical profile in a form dictionary;

scanning a completed form;

creating a hierarchical profile of vectorized data corresponding to the completed form;

comparing the hierarchical profile of the completed form with the hierarchical profiles for the blank forms in the form dictionary;

identifying one of the hierarchical profiles for the blank forms in the form dictionary as corresponding to the hierarchical profile of the completed form in accordance with the result of a comparison; and

routing the completed form for processing in accordance with the identity of the corresponding stored hierarchical profile.

14. A method according to claim 13, further comprising the steps of:

storing hierarchical profiles of vectorized data for a plurality of blank forms;

scanning a plurality of corresponding exemplary completed forms for each blank form;

creating a hierarchical profile of vectorized data for each exemplary completed form;

comparing each exemplary completed form hierarchical profile with each other corresponding exemplary completed form hierarchical profile to determine invariant elements between the exemplary completed form hierarchical profiles;

extracting the invariant elements from the corresponding exemplary completed form hierarchical profiles; and

correlating each blank form hierarchical profile with extracted invariant elements of corresponding exemplary completed form hierarchical profiles to create enhanced blank form hierarchical profiles which are stored in the form dictionary.

15. A method for storing and retrieving completed portions of a form, the method comprising the steps of:

scanning a plurality of different blank forms;

creating a hierarchical profile of vectorized data which defines features of a blank form for each scanned blank form;

comparing the hierarchical profiles to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements for each hierarchical profile in a form dictionary;

scanning a completed form;

creating a hierarchical profile of vectorized data for the completed form;

comparing the hierarchical profile of the completed form with the hierarchical profiles for the blank forms in the form dictionary;

identifying one of the hierarchical profiles of the blank forms as corresponding to the hierarchical profile of the completed form in accordance with a result of the comparison;

extracting completed portions of the completed form and respective header information which differ from the blank form corresponding to the identified stored hierarchical profile; and

displaying the extracted completed portions and respective header information.

16. A method according to claim 15, further comprising the steps of:

storing hierarchical profiles of vectorized data for a plurality of blank forms;

scanning a plurality of corresponding exemplary completed forms for each blank form;

creating a hierarchical profile of vectorized data for each exemplary completed form;

comparing each exemplary completed from hierarchical profile with each other corresponding exemplary completed from hierarchical profile to determine invariant elements between the exemplary completed form hierarchical profiles;

extracting the invariant elements from the corresponding exemplary completed form hierarchical profiles; and

correlating the blank form hierarchical profiles with extracted invariant elements of corresponding exemplary completed form hierarchical profiles to create enhanced blank form hierarchical profiles of vectorized data which are stored in the form dictionary.

17. An apparatus for identifying a completed form using a form dictionary of hierarchical form profiles, each of said hierarchical profiles consisting of vectorized data which defines features of a corresponding blank form, the apparatus comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements of each hierarchical profile in a form dictionary;

scanning means for scanning a completed form;

profile creating means for creating a hierarchical profile of vectorized data corresponding to the completed form;

comparison means for comparing the hierarchical profile of vectorized data corresponding to the completed form with the hierarchical form profiles in the form dictionary;

identifying means for identifying, in accordance with the result of the comparing means, one of the hierarchical form profiles in the form dictionary as corresponding to the hierarchical profile of the completed form; and

extracting means for extracting portions of the hierarchical profile of the completed form which differ from the identified hierarchical form profile in the form dictionary.

18. An apparatus according to claim 17, further comprising routing means for routing the extracted portions for processing in accordance with the identity of the identified hierarchical form profile of vectorized data.

19. An apparatus according to claim 17, further comprising storing means for storing predetermined data from the extracted portions in accordance with the identity of the identified hierarchical form profile of vectorized data.

20. An apparatus according to claim 17, further comprising displaying means for displaying selected data from the extracted portions in accordance with the identity of the identified hierarchical form profile of vectorized data.

21. An apparatus according to claim 17, further comprising character recognition means for recognizing selected data from the extracted portions in accordance with the identity of the identified hierarchical form profile of vectorized data.

22. An apparatus for displaying completed portions of a form, the apparatus comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding the invariant elements;

storing remaining elements of each hierarchical profile in a form dictionary;

scanning means for scanning a completed form;

profile creating means for creating a hierarchical profile of vectorized data which defines features of the completed form;

comparison means for comparing the hierarchical profile of vectorized data defining features of the completed form with a hierarchical profile of vectorized data corresponding to a blank form stored in the form directory;

extracting means for extracting portions of the hierarchical profile defining features of the completed form which differ from the hierarchical profile corresponding to the blank form; and

displaying means for displaying portions of the completed form which are dissimilar to corresponding portions of the blank form using the extracted portions of the hierarchical profile defining features of the completed form.

23. An apparatus according to claim 22, further comprising identifying means for identifying the scanned completed form by comparing the completed form to blank forms stored in the form dictionary.

24. An apparatus according to claim 22, wherein the extracting means includes means for extracting respective field header information with the extracted portions of the hierarchical profile corresponding to the completed form and the displaying means displays the extracted portions with the respective header information.

25. An apparatus according to claim 22, further comprising the steps of:

scanning means for scanning a plurality of exemplary completed forms corresponding to a blank form;

form profile creating means for creating a hierarchical profile of vectorized data corresponding to a blank form and for creating a hierarchical profile of vectorized data corresponding to each exemplary completed form;

comparing means for comparing each exemplary completed from hierarchical profile to each other exemplary completed from hierarchical profile to determine invariant elements between each exemplary completed form hierarchical profile of vectorized data;

extracting the invariant elements from the completed from hierarchical profiles; and

correlating means for correlating the hierarchical profile of the blank form and the extracted invariant elements from the exemplary completed form hierarchical profiles to create an enhanced blank form hierarchical profile of vectorized data which is stored in the form dictionary.

26. An apparatus for identifying completed forms, the apparatus comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding means for discarding the invariant elements;

storing means for storing remaining elements of each hierarchical profile in a form dictionary;

memory means for storing the form dictionary;

scanning means for scanning a completed form;

creating means for creating a hierarchical profile of vectorized data for the completed form;

comparison means for comparing the hierarchical profile of vectorized data for the completed form with the stored hierarchical profiles of vectorized data in the form dictionary;

identifying means for identifying one of the stored hierarchical profiles of vectorized data as corresponding to the completed form hierarchical profile of vectorized data in accordance with the result of the comparison by the comparing means; and

routing means for routing the completed form for processing in accordance with corresponding stored hierarchical profile of vectorized data.

27. A completed form identifier, comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding means for discarding the invariant elements;

storing means for storing remaining elements of each hierarchical profile in a form dictionary;

a scanner for scanning a completed form;

a hierarchical profile creator for creating a hierarchical profile of vectorized data which defines features of the scanned completed form;

a comparator for comparing the hierarchical profile of the scanned completed form with hierarchical profiles of vectorized data corresponding to various blank forms stored in the form dictionary;

a form identifier for identifying the completed form based on a comparison result of the comparator; and

a form router for routing the completed form for further processing based on an identification result of the form identifier.

28. An apparatus for displaying extracted data from a completed form, comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding means for discarding the invariant elements;

storing means for storing remaining elements of each hierarchical profile in a form dictionary;

a scanner for scanning a completed form;

a hierarchical profile creator for creating a hierarchical profile of vectorized data which defines features of the scanned completed form;

a comparator for comparing the hierarchical profile of vectorized data corresponding to the completed form to hierarchical profiles of vectorized data corresponding to various blank forms stored in the form dictionary;

a form identifier for identifying the completed form and for extracting data from the completed form based on an identification result of the identifier; and

a display screen for displaying the extracted data.

29. An apparatus for displaying a completed form, comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding means for discarding the invariant elements;

storing means for storing remaining elements of each hierarchical profile in a form dictionary;

a scanner for scanning a completed form;

a hierarchical profile creator for creating a hierarchical profile of vectorized data which defines features of the scanned completed form;

a comparator for comparing the hierarchical profile of the scanned completed form to hierarchical profiles of blank forms in the form dictionary and for locating a blank form hierarchical profile which matches the completed form hierarchical profile;

a data extractor for extracting data identifiers and data which is dissimilar to the matching blank form hierarchical profile from the hierarchical profile of the completed form;

a memory for storing the extracted data, data identifiers, and an indicia of the matching blank form; and

a screen display for displaying the extracted data superimposed on the matching blank form, wherein the matching blank form is drawn in accordance with the hierarchical profile of the blank form, and wherein the extracted data is superimposed into appropriate locations of the matching blank form in accordance with the extracted data identifiers.

30. A form identifier for identifying a completed form using a form dictionary of hierarchical form profiles, each of said hierarchical form profiles consisting of vectorized data which defines features of a corresponding blank form, the form identifier comprising:

comparing means for comparing hierarchical profiles of different blank forms to each other to determine invariant elements therebetween;

discarding means for discarding the invariant elements;

storing means for storing remaining elements of each hierarchical profile in a form dictionary;

a processing unit including a computer for executing stored program steps;

a memory for storing the form dictionary of hierarchical form profiles and process steps for execution by the processing unit; and

a scanner for scanning completed forms,

wherein the process steps stored in the memory include steps to create a hierarchical profile of vectorized data corresponding to a scanned completed form, to compare the hierarchical profile of the completed form to the hierarchical form profiles in the memory, to match the hierarchical form profile of the completed form to one of the hierarchical form profiles in the memory, and to form-process the completed form based on an identity of the matched hierarchical form profile in the memory.

31. A form identifier according to claim 30, wherein the process step of form-processing includes routing the completed form to an appropriate key-input operator.

32. A form identifier according to claim 30, wherein the process step of form-processing includes extracting invariant elements from the completed form hierarchical profile based on a comparison to the matched hierarchical form profile and displaying the extracted invariant elements to a key-input operator.