Granted Patent B2

US 8,285,074 · App. 12/873,657 · Granted Oct 9, 2012

Assignees: Palo Alto Research Center Incorporated; Xerox Corporation

Abstract

Claims (68)

1. A method of generating image anchor templates from low variance regions of document images of a first class, wherein the document images of the first class is a collection of document images of a same type, said method comprising:

selecting a document image from the document images of the first class; aligning the other document images of the first class to the selected document image, the aligning comprising:

selecting a plurality of sub-regions from each of the other document images;

determining a best match in the selected document for each of the selected sub-regions of the each of the other document images;

determining a transformation for the each of the other document images using a least squares analysis to minimize the difference between the best matches of the selected sub-regions of the each of the other document images and the selected sub-regions of the each of the other document images; and

transforming the each of the other document images according to the determined transformation of the each of the other document images;

determining the low variance regions by comparing the aligned document images and the selected document image, wherein the low variance regions are those regions that vary little between the selected document image and other document images; and

generating image anchor templates from the determined low variance regions, wherein the method is performed using at least one digital processor.

2. The method of claim 1 , wherein the selected document image is higher quality than the other document images.

3. The method of claim 1 , the determining the best match of the each of the selected sub-regions of the each of the other document images comprising:

searching for the best match of the each of the selected sub-regions of the each of the other document images by correlating pixels in the each of the selected sub-regions of the each of the other document images with pixels in a corresponding portion in the selected document image.

4. The method of claim 1 , wherein the determining the best match of the each of the selected sub-regions of the each of the other document images is performed using a hierarchical search procedure.

5. A method of generating image anchor templates from low variance regions of document images of a first class, wherein the document images of the first class is a collection of document images of a same type, said method comprising:

electing a document image from the document images of the first class;

aligning the other document images of the first class to the selected document image, the aligning comprising:

defining each of the other document images as an ensemble of blocks, wherein each of the blocks of the ensemble of blocks of the each of the other document images includes neighbors;

determining a best match in the selected document image for the each of the blocks of the ensemble of blocks of the each of the other document images, wherein the best match of the each of the blocks of the ensemble of blocks of the each of the other document images includes a match score;

determining a translation vector for the each of the blocks of the ensemble of blocks of the each of the other document images; and

shifting the each of the blocks of the ensemble of blocks of the each of the other document images by the translation vector of the each of the blocks of the ensemble of blocks of the each of the other document images to define aligned documents;

determining the low variance regions by comparing the aligned document images and the selected document image, wherein the low variance regions are those regions that vary little between the selected document image and other document images; and

generating image anchor templates from the determined low variance regions, wherein the method is performed using at least one digital processor.

6. The method of claim 5 , the aligning further comprising:

dilating foreground pixels for the each of the blocks of the ensemble of blocks of the each of the other document images.

7. The method of claim 5 , the aligning further comprising:

determining whether the match score of the best match of the each of the blocks of the ensemble of blocks of the each of the other document images exceeds a confidence threshold, wherein the translation vector of the each of the blocks of the ensemble of blocks of the each of the other document images is extrapolated from the translation vectors of neighboring blocks if the match score fails to exceed the confidence threshold.

8. The method of claim 5 , the determining the best match of the each of the blocks of the ensemble of blocks of the each of the other document images comprising:

searching for the best match of the each of the blocks of the ensemble of blocks of the each of the other document images by correlating pixels in the each of the blocks of the ensemble of blocks of the each of the other document images with pixels in a corresponding portion in the selected document image.

9. The method of claim 1 , wherein the determined low variance regions are at least a predefined distance from high variance regions.

10. A method of generating image anchor templates from low variance regions of document images of a first class, said method comprising:

selecting a document image from the document images of the first class, wherein the document images of the first class is a collection of document images of a same type;

aligning the other document images of the first class to the selected document image;

determining the low variance regions by comparing the aligned document images and the selected document image; and

generating image anchor templates from the determined low variance regions, wherein the generated image anchor templates (i) facilitate discrimination between the document mages of the first class and document images of other classes, or (ii) facilitate data extraction from a data field of the document images of the first class, the generating image anchor templates comprising:

generating one or more candidate image anchor templates using one or more seed image anchor templates and/or at least one of the low variance regions;

determining a quality score for each of the one or more candidate image anchor templates and (i) the document images of the first class, or (ii) known locations of the data field within the document image;

ranking the one or more candidate image anchor templates according to quality score; and

selecting one or more of the most highly ranked image anchor templates;

wherein the method is performed using at least one digital processor.

11. A method of generating image anchor templates from a clean document image generated from document images of a first class, wherein the document images of the first class is a collection of document images of a same type, wherein the document images of the first class is a collection of document images of a same type, said method comprising:

selecting a document image from the document images of the first class;

aligning the other document images of the first class to the selected document image;

generating the clean document image by combining the aligned document images and the selected document image;

identifying large salient structures in the clean document image; and

generating image anchor templates from the clean document image, wherein the image anchor templates are generated from the identified salient structures and wherein the method is performed using at least one digital processor.

12. The method of claim 11 , the generating the clean document age comprising:

summing the aligned document images and the selected document image pixel-wise to define a collection of summations, where each of the summations of the collection of summations corresponds to a pixel location;

filtering the collection of summations, wherein summations of the collection exceeding a threshold are assigned a black pixel, wherein summations of the collection less than the threshold are assigned a white pixel; and

generating the clean document image from the pixels and the pixel locations assigned to the each of the summations of the collection of summations.

13. The method of claim 12 , wherein the summing gives additional weight to at least one of the selected document image and the aligned document images.

14. A system carried on a computer readable medium, of generating image anchor templates from low variance regions of document images of a first class, wherein the document images of the first class is a collection of document images of a same type, said system comprising:

a selection module that selects a document image from the document images of the first class;

an alignment module that aligns the other document images of the class to the selected document image, the alignment module comprising:

a sub-region selection module that selects a plurality of sub-regions from each of the other document images;

a match module that determines a best match in the selected document for each of the selected sub-regions of the each of the other document images;

an analysis module that determines a transformation for the each of the other document images using a least squares analysis to minimize the difference between the best matches of the selected sub-regions of the each of the other document images and the selected sub-regions of the each of the other document images; and

a transformation module that transform the each of the other document images according to the determined transformation of the each of the other document images;

a variance module that determines the low variance regions by comparing the aligned document images and the selected document image, wherein the low variance regions are those regions that vary little between the selected document image and other document images; and

an image anchor template module that generates image anchor templates from the determined low variance regions.

15. The system of claim 14 , wherein the determining the best match of the each of the selected sub-regions of the each of the other document images is performed using a hierarchical search procedure.

16. A system carried on a computer readable medium, of generating image anchor templates from low variance regions of document images of a first class, wherein the document images of the first class is a collection of document images of a same type, wherein the document images of the first class is a collection of document images of a same type, said system comprising:

a selection module that selects a document image from the document images of the first class;

an alignment module that aligns the other document images of the first class to the selected document image, the alignment module comprising:

a partition module that defines each of the other document images as an ensemble of blocks, wherein each of the blocks of the ensemble of blocks of the each of the other document images includes neighbors;

a search module that determines a best match in the selected document image for the each of the blocks of the ensemble of blocks of the each of the other document images, wherein the best match of the each of the blocks of the ensemble of blocks of the each of the other document images includes a match score;

a displacement computing module that determines a translation vector for the each of the blocks of the ensemble of blocks of the each of the other document images; and

a translation module that shifts the each of the blocks of the ensemble of blocks of the each of the other document images by the translation vector to define aligned documents;

a variance module that determines the low variance regions by comparing the aligned document images and the selected document image, wherein the low variance regions are those regions that vary little between the selected document image and other document images; and

an image anchor template module that generates image anchor templates from the determined low variance regions.

Assignments (8)

Continuity (1)