ALIGNING A DATA TABLE WITH A REFERENCE TABLE

• US 20170147552A1
• Filed: 11/17/2016
• Published: 05/25/2017
• Est. Priority Date: 11/19/2015
• Status: Active Grant

• Current Assignee: DST Technologies, Inc. (SS&C Technologies Holdings Incorporated)
• Original Assignee: Captricity, Inc.
• Inventors: Carroll, Robert
• Granted Patent: US 10,417,489 B2
• Time in Patent Office: Days
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• 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: H04N 1/3873 defined only by a limited number of coordinate points or parameters, e.g. corners, centre; for trimming

Abstract

Methods, apparatuses, and embodiments related to aligning an image of a table of a form with an image of a table of a template of the form. Automatically extracting data entered in fields of a table of a form by a user can be aided by matching the form with a template of the form. The form template can have a digitized representation that identifies locations of fields of the form, and that identifies labels of the fields. Matching the form with the form template can enable locations and labels of fields of the form to be identified based on the digitized representation. However, matching the form with the form template may require matching the table of the form with the table of the form template, and matching two tables can be challenging. For example, the tables can be rotated, warped, scaled, etc. relative to each other.

Claims

1. A method for aligning grid lines of an image of a table of a filled-out paper form with grid lines of an image of a table of a template of the filled-out paper form, the method comprising:

generating, by a computer system, a thin feature image of a filled-out paper form by;

applying a median filter to an image of a filled-out paper form to generate a filtered image, wherein the applying of the median filter includes;

for each pixel of the image of the filled-out paper form;

selecting a plurality of pixels that have a pre-defined location relative to said each pixel,

identifying a median pixel of a set of pixels comprised of the plurality of pixels and said each pixel, and

generating the filtered image by replacing said each pixel with the median pixel, and

subtracting the filtered image of the filled-out paper form from the image of the filled-out paper form to generate the thin feature image,

wherein the thin feature image includes grid lines of a table of the filled-out paper form;

straightening, by the computer system, the grid lines of the table by;

aligning the grid lines of the table with an X axis or a Y axis, the X axis being a horizontal axis and the Y axis being a vertical axis, by;

for each sub-block of a plurality of sub-blocks of the thin feature image;

calculating a plurality of Hough transforms for said each sub-block, each of the plurality of Hough transforms being calculated based on a different rotation of said each sub-block relative to the X axis or the Y axis,

determining a dominant rotation relative to the X axis or the Y axis for said each sub-block based on the plurality of Hough transforms,

calculating a transformation for said each sub-block based on the dominant rotation, wherein the transformation aligns lines in said each sub-block with the X axis or the Y axis, and

applying the transformation to generate a rotation aligned version of said each sub-block, and

generating the rotation aligned version of the thin feature image based on the rotation aligned versions of the plurality of sub-blocks; and

scaling and shifting, by the computer system, the rotation aligned version of the thin feature image by;

determining a scale translation and a shift translation that maximizes a correlation between the grid lines of the table of the rotation aligned version of the thin feature image, and template grid lines of an image of a template table of a form template, and

applying the scale translation and the shift translation to the rotation aligned version of the thin feature image to generate a location aligned version of the thin feature image,

wherein an alignment of the grid lines of the table of the location aligned version of the thin feature image with the template grid lines of the image of the template table facilitates a determination that the table and the template table are aligned.

2. The method of claim 1, further comprising:

performing a one dimensional refinement of the alignment by;

for each pixel of the location aligned version of the thin feature image;

displacing said each pixel by a first displacement in either a first direction that is parallel with the X axis or a second direction that is parallel with the Y axis, the displacing of the pixel being to a displaced location,

selecting a pixel of the form template that is at a same position as the displaced location,

selecting a first value associated with said each pixel,

selecting a second value associated with the pixel of the form template,

calculating a third value by performing a mathematical operation that includes the first value and the second value, and

refining the alignment based on the third value.

3. The method of claim 1, further comprising:

performing a two dimensional refinement of the alignment by;

for each pixel of the location aligned version of the thin feature image;

displacing said each pixel by a first displacement in a first direction that is parallel with the X axis, and a second displacement in a second direction that is parallel with the Y axis, the displacing of the pixel being to a displaced location

selecting a pixel of the form template that is at a same position as the displaced location,

selecting a first value associated with said each pixel,

selecting a second value associated with the pixel of the form template,

calculating a third value by performing a mathematical operation that includes the first value and the second value, and

refining the alignment based on the third value.

4. The method of claim 1,

wherein the calculating the plurality of Hough transforms for said each sub-block includes calculating a squared Hough transform bin for each of the plurality of Hough transforms, and

wherein the dominant rotation is determined based on a summing of the squared Hough transform bin for said each of the plurality of Hough transforms.

5. The method of claim 1, wherein the straightening the grid lines of the table further includes calculating and applying a second transformation that linearizes the grid lines of the table.

6. A method comprising:

filtering, by a computer system, an image of a form to create a thin feature image of the form, wherein the thin feature image includes first grid lines of a table of the form;

transforming, by the computer system, the thin feature image of the form to create a rotation aligned version of the thin feature image that includes second grid lines, wherein the second grid lines have improved alignment, relative to the first grid lines, to an X axis or a Y axis, wherein the second grid lines have improved linearity relative to the first grid lines, and wherein the X axis is orthogonal to the Y axis; and

applying, by the computer system, a scale translation or a shift translation to the rotation aligned version of the thin feature image to generate a location aligned version of the thin feature image that includes third grid lines, wherein alignment of the third grid lines with template grid lines of a template table of an image of a form template is improved relative to alignment of the second grid lines with the template grid lines.

7. The method of claim 6, wherein the applying of the scale transaction or the shift translation includes applying one of the scale translation or the shift translation to the rotation aligned version of the thing feature image to create intermediate data, and applying an other one of the scale translation or the shift translation to the intermediate data to create the location aligned version of the thin feature image.

8. The method of claim 6, wherein the transforming of the thin image includes performing a first transformation to achieve the improved alignment, and includes performing a second transformation to achieve the improved linearity.

9. The method of claim 8, wherein the first transformation is a Hough transform.

10. The method of claim 9, wherein a plurality of Hough transforms are calculated based on the thin feature image, and wherein the first transformation is based on a dominant rotation that is determined based on the plurality of Hough transforms.

11. The method of claim 8, wherein the second transformation is calculated based on a warping model.

13. The method of claim 6, further comprising:

performing a one or two dimensional refinement of the alignment of the third grid lines with the template grid lines.

14. The method of claim 13, wherein the one or the two dimensional refinement includes displacing a pixel of the location aligned version of the thin feature image by a first predetermined displacement in a first direction that is parallel with the X axis or by a second predetermined displacement in a second direction that is parallel with the Y axis.

15. The method of claim 14, wherein the two dimensional refinement includes displacing the pixel of the location aligned version of the thin feature image by the first predetermined displacement in the first direction, and by the second predetermined displacement in the second direction.

16. The method of claim 6, wherein the filtering the image includes applying a median filter to the image.

17. The method of claim 16, wherein the applying of the median filter includes:

selecting a pixel of the image of the form,

selecting a plurality of pixels that have a pre-defined location relative to the pixel,

identifying a median pixel of a set of pixels comprised of the plurality of pixels and the pixel,

generating intermediate data by replacing the pixel with the median pixel, and

subtracting the intermediate data from the image of the form to generate the thin feature image.

18. The method of claim 17, wherein the pre-defined location is being within a rectangular boundary that is centered on the pixel, and that extends out from the pixel by a pre-determined number of pixels in each direction.

19. The method of claim 18, wherein the pre-determined number of pixels is different for said each direction.

12. The method of claim 12, wherein the warping model is a polynomial warping model.

20. A computer system comprising:

a processor;

a networking interface coupled to the processor; and

a memory coupled to the processor and storing instructions which, when executed by the processor, cause the computer system to perform operations including;

receiving an image of a form and an image of a form template;

generating a thin feature image of the form based on the image of the form, wherein the thin feature image includes first grid lines of a table of the form, wherein, when the image of the form includes a step-edge, the thin feature image does not include the step-edge, and wherein the step-edge is an edge between two constant regions of the image of the form; and

transforming the thin feature image of the form to create a rotation aligned version of the thin feature image that includes second grid lines, wherein the second grid lines have improved alignment, relative to the first grid lines, to an X axis or a Y axis, wherein the second grid lines have improved linearity relative to the first grid lines, and wherein the X axis is orthogonal to the Y axis

21. The computer system of claim 20,

wherein the image of the form includes an image of a piece of paper on which the form is printed and includes an image of an area beyond an edge of the piece of paper,

wherein the two constant regions are a first region and a second region,

wherein the first region is located entirely on the image of the piece of paper,

wherein one edge of the first region is located substantially at the edge of the piece of paper,

wherein the second region is located entirely on the image of the area beyond the edge of the piece of paper,

wherein one edge of the second region is located substantially at the edge of the piece of paper,

wherein the one edge of the first region and the one edge of the second region abut, and

wherein the step-edge is located where the one edge of the first region and the one edge of the second region abut.

22. The computer system of claim 20, wherein the operations further include:

applying a shift translation to the rotation aligned version of the thin feature image to generate a location aligned version of the thin feature image,

wherein a determination of the shift translation includes using a fast Fourier transform to determine a shift amount that optimizes a correlation between the location aligned version of the thin feature image and an image of a form template.