Active area identification on a machine readable form using form landmarks

• US 5,748,809 A
• Filed: 06/23/1997
• Issued: 05/05/1998
• Est. Priority Date: 04/21/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hirsch, David Edward
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/880,202
• Time in Patent Office: 316 Days
• Field of Search: 382/317, 382/175, 382/180, 382/287, 382/292, 358/403, 358/453, 395/145-149, 395/766-769
• US Class Current: 382/317
• CPC Class Codes: G06K 17/0032 Apparatus for automatic testing and analysing marked record carriers, used for examinations of the multiple choice answer type teaching apparatus working with questions and answers G09B7/00
• 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

Abstract

A forms creation and processing system which identifies and locates the active areas of a form using forms landmarks. The present invention eliminates the need to place predefined registration marks onto a machine readable form. The active areas of a form are those which may contain a user created mark, such as a checkbox or a signature box. A form is preanalyzed at the same time that the active areas are being described. The aim of the preanalysis is to find a set of graphic shapes, i.e. landmarks, that can be found on the form independent of their location or orientation in the image. Examples of such landmarks include paragraphs of text, heavy black lines and gray scale areas. The analysis looks at the geometric distribution and regularities of the connected components to choose a set of landmarks. The landmarks and active areas on the form are stored in a forms control file. A forms interpreter uses the forms control file to locate and examine the active areas of an instance of a form to determine if a mark has been placed thereon.

Claims

1. A method for identifying areas on an instance of a machine readable form to be examined for the presence of user made marks, said machine readable form void of predefined registration marks, said method comprising the steps of:

a) creating said machine readable form by performing the sub-steps of;

composing said machine readable form having one or more active areas;

analyzing an image of said machine readable form to identify one or more original landmarks, said original landmarks including text blocks, graphic blocks, horizontal bars and vertical bars; and

storing location and identifying information for said one or more original landmarks and said active areas in a forms control file;

b) creating a bit-mapped representation of said instance of said machine readable form;

c) analyzing said bit-mapped representation of said instance of said machine readable form to identify one or more instance landmarks, said instance landmarks including text blocks, graphic blocks, horizontal bars and vertical bars;

identifying an active area in said instance of a machine readable form by performing the steps of;

d) retrieving said forms control file;

e) comparing said one or more original landmarks from said forms control file with said one or more instance landmarks to obtain pairings of original landmarks with instance landmarks based on location and shape;

f) generating an offset based on said landmark pairings;

g) applying said offset to location information in said forms control file of an active area being processed;

h) examining said area identified in step g) as said active area.

2. The method as recited in claim 1 wherein said step of analyzing an image of said machine readable form to identify one or more original landmarks further comprises the steps of:

b1) creating a bit-mapped representation of said machine readable form;

b2) using a first process to identify said original landmarks for said machine readable form from said bit-mapped representation; and

b3) storing first location information for said original landmarks in said forms control file.

3. The method as recited in claim 2 wherein said step of creating a bit-mapped representation of said instance of said machine readable form is further comprised of the step of de-skewing said created bit-mapped representation of said instance of said machine readable form.

4. The method as recited in claim 3 wherein said step of analyzing said bit-mapped representation of said instance of said machine readable form to identify one or more instance landmarks is performed using said first process.

5. The method as recited in claim 4 wherein said first process further comprises the steps of:

a) reducing said bit-mapped representation to a predetermined standard resolution;

b) creating rectangles around areas of said reduced bit-mapped representation containing adjacent pixels having the same binary value;

c) performing the sub-steps of combining overlapping and close rectangles until a predetermined condition is achieved and a set of remaining rectangles have been created; and

d) providing said set of remaining rectangles as landmarks.

6. The method as recited in claim 1 wherein said step of generating an offset based on said landmark pairings further comprises the steps of:

f1) identifying a first pair of landmarks and a second pair of landmarks that are closest to the active area being processed;

f2) determining if said first pair of landmarks and said second pair of landmarks are within a predetermined distance from said active area being processed;

f3) if said first pair of landmarks and said second pair of landmarks are within a predetermined distance from said active area being processed, determining said offset by averaging the distance between said first pair of landmarks and the distance between said second pair of landmarks;

f4) if said first pair of landmarks and said second pair of landmarks are not within said predetermined distance from said active area being processed, determining said offset by constructing an affine transformation function between said original landmarks of said first and second pairs of landmarks and said instance landmarks of said first and second pairs of landmarks and applying said affine transformation on said active area being processed.

7. The method as recited in claim 1 wherein prior to said step of analyzing said machine readable form to identify one or more original landmarks performing the steps of:

determining if said machine readable form can be de-skewed; and

rejecting said machine readable form if said machine readable form cannot be de-skewed.

8. A method for locating active areas which may contain user created marks on an instance of a machine readable form, said machine readable form void of predefined registration marks, said method comprising the steps of:

a) receiving a forms control file associated with said instance of said machine readable form, said forms control file comprising a set of original landmarks of said machine readable form, said original landmarks including text blocks, graphic blocks, horizontal bars or vertical bars, said forms control file further comprising original position information for each active area on said machine readable form and an iteration count;

b) scanning said instance of a machine readable form to create a bit-mapped representation thereof;

c) analyzing said bit-mapped representation of said instance of a machine readable form to identify a set of instance landmarks, said instance landmarks including text blocks, graphic blocks, horizontal bars or vertical bars;

d) matching landmarks in said set of original landmarks with landmarks in said set of instance landmarks to create matched pairs of landmarks, said matching step based on predetermined spatial position and predetermined shape thresholds;

e) generating an offset based on said matched pairs of landmarks and original position information for an active area being processed; and

f) applying said offset to said original position information for the active area being processed.

9. The method as recited in claim 8 wherein said step of analyzing said bit-mapped representation of said instance of a machine readable form to identify a set of instance landmarks further comprises the steps of:

c1) creating rectangles around areas of said reduced bit-mapped representation containing adjacent pixels having the same binary value; and

c2) performing the sub-steps of combining overlapping and close rectangles a number of times specified by said iteration count to create said instance landmarks.

10. The method as recited in claim 9 wherein said step of matching landmarks in said set of original landmarks with landmarks in said set of instance landmarks to create matched pairs of landmarks is further comprised of the step of:

d1) for each original landmark, determining if an instance landmark exists that is within a predetermined spatial position and a predetermined shape threshold;

d2) if no such instance landmark exists, skipping said original landmark; and

d3) if such instance landmark exists, pairing said original landmark with said instance landmark.

11. The method as recited in claim 10 wherein said step of generating an offset based on said matched pairs of landmarks and original position information for an active area being processed is further comprised of the steps of:

e1) identifying a first pair of landmarks and a second pair of landmarks that are closest to the active area being processed;

e2) determining if said first pair of landmarks and said second pair of landmarks are within a predetermined distance from said active area being processed;

e3) if said first pair of landmarks and said second pair of landmarks are within said predetermined distance from said active area being processed, determining an offset by averaging the distance between said first pair of landmarks and the distance between said second pair of landmarks; and

e4) if said first pair of landmarks and said second pair of landmarks are not within said predetermined distance from said active area being processed, determining said offset by constructing an affine transformation function between said original landmarks of said first and second pairs of landmarks and said instance landmarks of said first and second pair of landmarks and applying said affine transformation on said active area being processed.

12. A forms processing system for identifying active areas in machine readable forms, said machine readable forms void of predefined registration marks, said forms processing system comprising;

a scanning device for scanning an instance of a machine readable form to create a bit-mapped representation thereof;

receiving circuitry for receiving a forms control file associated with said instance of said machine readable form, said forms control file comprising a set of original landmarks of said machine readable form, said original landmarks including text blocks, graphic blocks, horizontal bars or vertical bars, said forms control file further comprising original position information for each active area on said machine readable form;

first processing circuitry suitably adapted to provide functionality for analyzing said bit-mapped representation of said instance of a machine readable form to identify a set of instance landmarks, said instance landmarks including text blocks, graphic blocks, horizontal bars or vertical bars;

second processing circuitry suitably adapted to provide functionality for matching landmarks in said set of original landmarks with landmarks in said set of instance landmarks to create matched pairs of landmarks, said matching based on predetermined spatial position and predetermined shape thresholds;

third processing circuitry suitably adapted to provide functionality for generating an offset based on said matched pairs of landmarks and original position information for an active area being processed; and

fourth processing circuitry suitably adapted to provide functionality for applying said offset to original position information for said active area being processed.

13. The forms processing system as recited in claim 12 wherein said third processing circuitry is further comprised of:

circuitry for identifying a first pair of landmarks and a second pair of landmarks that are closest to the active area being processed;

circuitry for determining if said first pair of landmarks and said second pair of landmarks are within a predetermined distance from said active area being processed;

circuitry for determining if said first pair of landmarks and said second pair of landmarks are within said predetermined distance from said active area being processed, determining an offset by averaging the distance between said first pair of landmarks and the distance between said second pair of landmarks; and

circuitry for determining if said first pair of landmarks and said second pair of landmarks are not within said predetermined distance from said active area being processed, determining said offset by constructing an affine transformation function between said original landmarks of said first and second pairs of landmarks and said instance landmarks of said first and second pair of landmarks and applying said affine transformation on said active area being processed.

14. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for identifying active areas on a machine readable form, wherein said machine readable form is void of registrations marks, said method steps comprising:

b) receiving a bit-mapped representation of an instance of a machine readable form;

b) receiving a forms control file associated with said instance of said machine readable form, said forms control file comprising a set of original landmarks of said machine readable form, said original landmarks including text blocks, graphic blocks, horizontal bars or vertical bars, said forms control file further comprising original position information for each active area on said machine readable form;

c) analyzing said bit-mapped representation of said instance of a machine readable form to identify a set of instance landmarks, said instance landmarks including text blocks, graphic blocks, horizontal bars or vertical bars;

d) matching landmarks in said set of original landmarks with landmarks in said set of instance landmarks to create matched pairs of landmarks, said matching step based on predetermined spatial position and predetermined shape thresholds;

e) generating an offset based on said matched pairs of landmarks and original position information for an active area being processed; and

f) applying said offset to said original position information for said active area being processed.