Granted Patent B2

US 8,515,208 · App. 13/080,163 · Granted Aug 20, 2013

Abstract

Claims (46)

1. A method for aligning a document to a template, comprising:

identifying connected components of the document;

determining document image-bounding rectangles corresponding to at least some of the connected components of the document;

iteratively transforming pre-determined template image-bounding rectangles to match the document image-bounding rectangles;

aggregating transformations of the template image-bounding rectangles to generate a transform matrix; and

transforming the document according to an inverse of the transform matrix.

2. A method as claimed in claim 1 , wherein transforming pre-determined template image-bounding rectangles includes:

calculating a center point and an associated weight metric of each of a plurality of the document image-bounding rectangles, and a mean weighted center point of the plurality of document image-bounding rectangles;

calculating an initial transform to be uniformly applied to each of the pre-determined template image-bounding rectangles, such that a pre-determined mean weighted center point of the template image-bounding rectangles will be aligned to the mean weighted center point of the document image-bounding rectangles; and

applying the initial transform to the template image-bounding rectangles.

3. A method as claimed in claim 1 , wherein transforming pre-determined template image-bounding rectangles includes:

generating a plurality of trial transforms;

applying each of the plurality of trial transforms to the template image-bounding rectangles to produce a corresponding plurality of trial templates each including a plurality of trial image-bounding rectangles;

calculating a fitness score for each of the plurality of trial templates; and

accepting one of the plurality of trial templates as a transformed template.

4. A method as claimed in claim 3 , wherein during a first stage of iteratively transforming pre-determined template image-bounding rectangles, each of a plurality of first stage trial transforms is an affine translation; and during a second stage of iteratively transforming pre-determined template image-bounding rectangles, each of a plurality of second stage trial transforms is an affine transform smaller than an average size of the plurality of first stage trial transforms.

5. A method as claimed in claim 3 , wherein each of the plurality of trial transforms includes a translation.

6. A method as claimed in claim 3 , wherein the plurality of trial transforms includes at least one of a translation, a rotation, a shear, a skew, or a scaling.

7. A method as claimed in claim 6 , wherein the plurality of trial transforms includes at least two of a translation, a rotation, a shear, a skew, or a scaling.

8. A method as claimed in claim 7 , wherein at least one of the plurality of trial transforms includes at least two of a translation, a rotation, a shear, a skew, or a scaling.

9. A method as claimed in claim 3 , wherein calculating a fitness score includes:

identifying at least one trial image-bounding rectangle that intersects a document image-bounding rectangle; and

calculating an overlap area of the intersecting image-bounding rectangles.

10. A method as claimed in claim 9 , wherein calculating a fitness score includes calculating an aggregate overlap area of the plurality of trial image-bounding rectangles with the plurality of document image-bounding rectangles.

11. A method as claimed in claim 3 , wherein calculating a fitness score includes generating a seed value for a next plurality of trial transforms, and generating a plurality of trial transforms includes modifying a plurality of pre-determined transforms based on a seed value.

12. A method as claimed in claim 11 , wherein generating a seed value includes selecting a document image-bounding rectangle maximally distant from a mean weighted center point of the document, and calculating a vector from the center point of the selected document image-bounding rectangle to the center point of a trial image-bounding rectangle that intersects the selected document image-bounding rectangle.

13. A method as claimed in claim 1 , wherein pre-determined image-bounding rectangles of the template are determined from an electronic template image file generated by optically scanning a paper template.

14. A method as claimed in claim 1 , wherein determining document image-bounding rectangles includes excluding connected components of the document by comparison to a threshold criterion.

15. A method as claimed in claim 1 , wherein identifying connected components of the documents includes optically scanning an object.

16. A method as claimed in claim 1 , wherein transforming the document includes modifying an electronic image of the document.

17. A method as claimed in claim 1 , further comprising testing the transform matrix against pre-determined heuristics.

18. A method as claimed in claim 17 , further comprising selecting a new template based on the results of testing the transform matrix.

19. An apparatus for aligning an electronic image of a document to an electronic image of a template, comprising:

a processor configured by instructions to:

obtain the electronic image of the document;

identify, within the electronic image of the document, connected components of the document;

determine document image-bounding rectangles corresponding to at least some of the connected components of the document;

iteratively transform pre-determined template image-bounding rectangles to match the document image-bounding rectangles;

aggregate transformations of the template image-bounding rectangles to generate a transform matrix; and

transform the electronic image of the document according to an inverse of the transform matrix; and

a data storage device connected in communication with the processor, the data storage device storing at least one of the instructions, the electronic image of the document, or the electronic image of the template.

20. An apparatus as claimed in claim 19 , wherein the instructions include instructions for generating an electronic image of a new template based on the electronic image of the document.

21. An apparatus as claimed in claim 19 , wherein instructions to transform pre-determined template image-bounding rectangles include instructions for:

calculating a center point and an associated weight metric of each of a plurality of the document image-bounding rectangles, and a mean weighted center point of the plurality of document image-bounding rectangles;

calculating an initial transform to be uniformly applied to each of the pre-determined template image-bounding rectangles, such that a pre-determined mean weighted center point of the template image-bounding rectangles will be aligned to the mean weighted center point of the document image-bounding rectangles; and

applying the initial transform to the template image-bounding rectangles.

Assignments (10)