Identifying document forms using digital fingerprints

• US 10,115,010 B1
• Filed: 08/01/2018
• Issued: 10/30/2018
• Est. Priority Date: 10/28/2016
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Becker, Richard J., Knoblauch, Greg, Malynin, Pavlo, Eappen, Anju
• Primary Examiner(s): Osinski, Michael
• Application Number:
  US16/051,825
• Time in Patent Office: 90 Days
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• 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
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32267 combined with processing of the image
• CPC Class Codes: H04N 1/32309 in colour image data
• CPC Class Codes: H04N 1/32336 Informed embedding, i.e. the original image being known for the encoding or decoding method

Abstract

Techniques are disclosed to identify a form document in an image using a digital fingerprint of the form document. To do so, the image is evaluated to detect features of the image and determine a polygon bounding each feature. For each polygon, pixels are plotted in a second image based on coordinates of a center of the polygon. The second image is the digital fingerprint of the form. To identify the form corresponding to the digital fingerprint, the digital fingerprint may be compared to digital fingerprints of known forms.

Claims

1. A computer-implemented method for generating a digital fingerprint corresponding to a form depicted in a digital image, the method comprising:

identifying one or more features of a form depicted in a first digital image;

determining, for each of the one or more features, coordinates of a respective polygon bounding the feature within the first digital image; and

for each polygon;

identifying coordinates of a center of the polygon within the first digital image, and

plotting a pixel in a second image based on the coordinates of the center of the polygon, wherein a position of the pixel in the second image matches a position of the center of the polygon in the first digital image and wherein the second image comprises a digital fingerprint of the form depicted in the first digital image.

2. The method of claim 1, further comprising:

comparing the second image to a plurality of images, each image representing a digital fingerprint of a corresponding form;

determining, based on the comparison, a distance measure between the second image and each of the plurality of images;

identifying a matching image, of the plurality of images, wherein the matching image has a minimum distance measure determined between the second image and each of the plurality of images and wherein the minimum distance measure satisfies a distance measure threshold; and

recognizing the form depicted in the first digital image as an instance of a form corresponding to the matching image.

3. The method of claim 1, further comprising:

reducing the second image to a predetermined size.

4. The method of claim 1, further comprising:

prior to identifying the coordinates of the center of at least a first polygon, discarding the first polygon after determining that either (i) the first polygon has a ratio of a height to a width that does not satisfy a minimum threshold or (ii) the first polygon has a dimension that does not meet a minimum size.

5. The method of claim 1, further comprising:

encoding a value in an alpha channel of one or more pixels in the second image, wherein the value represents a level of importance of a polygon corresponding to each of the one or more pixels to the digital fingerprint of the form.

6. The method of claim 1, wherein the pixel comprises:

a first color channel which stores a height of a corresponding polygon,

a second color channel which stores a width of the corresponding polygon, and

a third color channel which stores a ratio of the height of the corresponding polygon to the width of the corresponding polygon.

7. The method of claim 1, further comprising:

normalizing image characteristics of the first digital image.

8. A non-transitory computer-readable storage medium storing instructions, which, when executed on a processor, perform an operation to generate a digital fingerprint corresponding to a form depicted in a digital image, the operation comprising:

identifying one or more features of a form depicted in a first digital image;

determining, for each of the one or more features, coordinates of a respective polygon bounding the feature within the first digital image; and

for each polygon;

identifying coordinates of a center of the polygon within the first digital image, and

plotting a pixel in a second image based on the coordinates of the center of the polygon, wherein a position of the pixel in the second image matches a position of the center of the polygon in the first digital image and wherein the second image comprises a digital fingerprint of the form depicted in the first digital image.

9. The non-transitory computer-readable storage medium of claim 8, further comprising:

comparing the second image to a plurality of images, each image representing a digital fingerprint of a corresponding form;

determining, based on the comparison, a distance measure between the second image and each of the plurality of images;

identifying a matching image, of the plurality of images, wherein the matching image has a minimum distance measure determined between the second image and each of the plurality of images and wherein the minimum distance measure satisfies a distance measure threshold; and

recognizing the form depicted in the first digital image as an instance of a form corresponding to the matching image.

10. The non-transitory computer-readable storage medium of claim 8, further comprising:

reducing the second image to a predetermined size.

11. The non-transitory computer-readable storage medium of claim 8, further comprising:

prior to identifying the coordinates of the center of at least a first polygon, discarding the first polygon after determining that either (i) the first polygon has a ratio of a height to a width that does not satisfy a minimum threshold or (ii) the first polygon has a dimension that does not meet a minimum size.

12. The non-transitory computer-readable storage medium of claim 8, further comprising:

encoding a value in an alpha channel of one or more pixels in the second image, wherein the value represents a level of importance of a polygon corresponding to each of the one or more pixels to the digital fingerprint of the form.

13. The non-transitory computer-readable storage medium of claim 8, wherein the pixel comprises:

a first color channel which stores a height of a corresponding polygon,

a second color channel which stores a width of the corresponding polygon, and

a third color channel which stores a ratio of the height of the corresponding polygon to the width of the corresponding polygon.

14. The non-transitory computer-readable storage medium of claim 8, further comprising:

normalizing image characteristics of the first digital image.

15. A system, comprising:

a processor; and

a memory hosting an application, which, when executed on the processor, performs an operation to generate a digital fingerprint corresponding to a form depicted in a digital image, the operation comprising;

identifying one or more features of a form depicted in a first digital image;

determining, for each of the one or more features, coordinates of a respective polygon bounding the feature within the first digital image; and

for each polygon;

identifying coordinates of a center of the polygon within the first digital image, and

plotting a pixel in a second image based on the coordinates of the center of the polygon, wherein a position of the pixel in the second image matches a position of the center of the polygon in the first digital image and wherein the second image comprises a digital fingerprint of the form depicted in the first digital image.

16. The system of claim 15, further comprising:

comparing the second image to a plurality of images, each image representing a digital fingerprint of a corresponding form;

determining, based on the comparison, a distance measure between the second image and each of the plurality of images;

identifying a matching image, of the plurality of images, wherein the matching image has a minimum distance measure determined between the second image and each of the plurality of images and wherein the minimum distance measure satisfies a distance measure threshold; and

recognizing the form depicted in the first digital image as an instance of a form corresponding to the matching image.

17. The system of claim 15, further comprising:

prior to identifying the coordinates of the center of at least a first polygon, discarding the first polygon after determining that either (i) the first polygon has a ratio of a height to a width that does not satisfy a minimum threshold or (ii) the first polygon has a dimension that does not meet a minimum size.

18. The system of claim 15, further comprising:

encoding a value in an alpha channel of one or more pixels in the second image, wherein the value represents a level of importance of a polygon corresponding to each of the one or more pixels to the digital fingerprint of the form.

19. The system of claim 15, wherein the pixel comprises:

a first color channel which stores a height of a corresponding polygon,

a second color channel which stores a width of the corresponding polygon, and

a third color channel which stores a ratio of the height of the corresponding polygon to the width of the corresponding polygon.

20. The system of claim 15, further comprising:

normalizing image characteristics of the first digital image.