Document scanner

• US 9,852,348 B2
• Filed: 04/17/2015
• Issued: 12/26/2017
• Est. Priority Date: 04/17/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Chaudhury, Krishnendu, Chen, Lu, Petrou, David, Aguera-Arcas, Blaise
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US14/690,274
• Publication Number:
  US 20160307059A1
• Time in Patent Office: 984 Days
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations
• CPC Class Codes: G06V 10/247 by affine transforms, e.g. correction due to perspective effects; Quadrilaterals, e.g. trapezoids
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• 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

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, to generate a scannable document. In one aspect, a method includes receiving a scan request, wherein the scan request includes a plurality of text images; for each text image of the plurality of text images: rectifying the text image to generate a text image with parallel image lines, generating a plurality of word bounding boxes that enclose one or more connected components in the text image, wherein each word bounding box is associated with a respective word, and generating, for each respective word in the text image, a plurality of points that represent the respective word; combining the plurality of text images to form a single text document; and providing the combined image as a scannable document.

Claims

1. A computer implemented method, the method comprising:

receiving a scan request, wherein the scan request includes a plurality of text images, each text image representing a portion of a text document, wherein the plurality of text images includes a first text image and a second text image that at least partially overlap;

for each text image of the plurality of text images;

rectifying the text image to generate a text image with parallel image lines,

generating a plurality of word bounding boxes that enclose one or more connected components in the text image, wherein each word bounding box is associated with a respective word of the text image, and

generating, for each respective word bounding box in the text image, a vector that describes a shape of the respective word;

combining text images of the plurality of text images that at least partially overlap to form a single text document including combining the first text image of the plurality of text images and the second text image of the plurality of text images by matching one or more shape descriptors from a first set of vectors generated for each respective word in the first text image and one or more shape descriptors from a second set of vectors generated for each respective word in the second text image; and

providing the combined image as a scannable document.

2. The method of claim 1, wherein rectifying each text image of the plurality of text images comprises:

determining a plurality of connected components in the text image, each connected component being a filled portion of a symbol;

generating a plurality of image lines in the text image including vertical linelets and horizontal linelets based on the plurality of connected components;

calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines; and

applying a geometric formula to the first and second vanishing points to restore parallel lines in the text image.

3. The method of claim 2, wherein the plurality of image lines includes a plurality of vertical linelets and a plurality of horizontal linelets, each vertical linelet being a skeletal line through an upright portion of a connected component, each horizontal linelet being a regression line through a center of a set of adjacent connected components.

4. The method of claim 3, wherein calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines further comprises:

calculating the horizontal vanishing point using the horizontal linelets; and

calculating the vertical vanishing point using the vertical linelets.

5. The method of claim 1, wherein combining the first text image and the second text image includes blending the first text image with the second text image.

6. The method of claim 1, wherein a number of matching shape descriptors between the first set of vectors associated with the first text image and the second set of vectors associated with the second text image satisfies a threshold number of matching shape descriptors.

7. The method of claim 1, wherein combining the plurality of text images further comprises:

blending the plurality of text images that form the single text document;

de-skewing the single text document; and

performing optical character recognition on the single text document.

22. The method of claim 1, wherein generating a particular vector for a particular word includes generating a grid for the corresponding word bounding box, performing histogram oriented gradient over the cells of the grid to determine word shape descriptors, and generating the particular vector from the words shape descriptors.

8. A system, comprising:

one or more computers;

one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving a scan request, wherein the scan request includes a plurality of text images, each text image representing a portion of a text document, wherein the plurality of text images includes a first text image and a second text image that at least partially overlap;

for each text image of the plurality of text images;

rectifying the text image to generate a text image with parallel image lines,

generating a plurality of word bounding boxes that enclose one or more connected components in the text image, wherein each word bounding box is associated with a respective word of the text image, and

generating, for each respective word bounding box in the text image, a vector that describes a shape of the respective word;

combining text images of the plurality of text images that at least partially overlap to form a single text document including combining the first text image of the plurality of text images and the second text image of the plurality of text images by matching one or more shape descriptors from a first set of vectors generated for each respective word in the first text image and one or more shape descriptors from a second set of vectors generated for each respective word in the second text image; and

providing the combined image as a scannable document.

9. The system of claim 8, wherein rectifying each text image of the plurality of text images comprises:

determining a plurality of connected components in the text image, each connected component being a filled portion of a symbol;

generating a plurality of image lines in the text image including vertical linelets and horizontal linelets based on the plurality of connected components;

calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines; and

applying a geometric formula to the first and second vanishing points to restore parallel lines in the text image.

10. The system of claim 9, wherein the plurality of image lines includes a plurality of vertical linelets and a plurality of horizontal linelets, each vertical linelet being a skeletal line through an upright portion of a connected component, each horizontal linelet being a regression line through a center of a set of adjacent connected components.

11. The system of claim 10, wherein calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines further comprises:

calculating the horizontal vanishing point using the horizontal linelets; and

calculating the vertical vanishing point using the vertical linelets.

12. The system of claim 8, wherein combining the first text image and the second text image includes blending the first text image with the second text image.

13. The method of claim 8, wherein a number of matching shape descriptors between the first set of vectors associated with the first text image and the second set of vectors associated with the second text image satisfies a threshold number of matching shape descriptors.

14. The system of claim 8, wherein combining the plurality of text images further comprises:

blending the plurality of text images that form the single text document;

de-skewing the single text document; and

performing optical character recognition on the single text document.

15. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a scan request, wherein the scan request includes a plurality of text images, each text image representing a portion of a text document, wherein the plurality of text images includes a first text image and a second text image that at least partially overlap;

for each text image of the plurality of text images;

rectifying the text image to generate a text image with parallel image lines,

generating a plurality of word bounding boxes that enclose one or more connected components in the text image, wherein each word bounding box is associated with a respective word of the text image, and

generating, for each respective word bounding box in the text image, a vector that describes a shape of the respective word;

combining text images of the plurality of text images that at least partially overlap to form a single text document including combining the first text image of the plurality of text images and the second text image of the plurality of text images by matching one or more shape descriptors from a first set of vectors generated for each respective word in the first text image and one or more shape descriptors from a second set of vectors generated for each respective word in the second text image; and

providing the combined image as a scannable document.

16. The computer storage medium of claim 15, wherein rectifying each text image of the plurality of text images comprises:

determining a plurality of connected components in the text image, each connected component being a filled portion of a symbol;

generating a plurality of image lines in the text image including vertical linelets and horizontal linelets based on the plurality of connected components;

calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines; and

applying a geometric formula to the first and second vanishing points to restore parallel lines in the text image.

17. The computer storage medium of claim 16, wherein the plurality of image lines includes a plurality of vertical linelets and a plurality of horizontal linelets, each vertical linelet being a skeletal line through an upright portion of a connected component, each horizontal linelet being a regression line through a center of a set of adjacent connected components.

18. The computer storage medium of claim 17, wherein calculating a horizontal vanishing point and a vertical vanishing point based on the plurality of image lines further comprises:

calculating the horizontal vanishing point using the horizontal linelets; and

calculating the vertical vanishing point using the vertical linelets.

19. The computer storage medium of claim 15, wherein combining the first text image and the second text image includes blending the first text image with the second text image.

20. The method of claim 15, wherein a number of matching shape descriptors between the first set of vectors associated with the first text image and the second set of vectors associated with the second text image satisfies a threshold number of matching shape descriptors.

21. The computer storage medium of claim 15, wherein combining the plurality of text images further comprises:

blending the plurality of text images that form the single text document;

de-skewing the single text document; and

performing optical character recognition on the single text document.