High resolution replication of document based on shape clustering

• US 7,646,921 B2
• Filed: 09/11/2006
• Issued: 01/12/2010
• Est. Priority Date: 09/11/2006
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Smith, Raymond W., Vincent, Luc
• Primary Examiner(s): Mariam; Daniel G
• Application Number:
  US11/519,320
• Publication Number:
  US 20080063277A1
• Time in Patent Office: 1,219 Days
• Field of Search: 382/173, 382175-182, 382/224, 382/225, 382/229, 382/298, 382/321
• US Class Current: 382/225
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1918 Fusion techniques, i.e. combining data from various sources, e.g. sensor fusion
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Techniques for shape clustering and applications in processing various documents, including an output of an optical character recognition (OCR) process.

Claims

1. A method, comprising:

processing an image of a document to produce a collection of non-overlapping sub-regions of the image, each sub-region being at a first resolution;

generating multiple clusters of visually similar clip sub-regions, each of the sub-regions in the collection being included in one of the clusters;

generating a representative cluster image for each of the multiple clusters from the sub-regions in the respective cluster at a second resolution higher than the first resolution; and

producing a replica image of the document by replacing sub-regions in the image with the representative cluster images for the clusters in which the respective sub-regions are included, wherein the method is performed by one or more computer processors.

2. The method of claim 1, wherein:

the document is a multiple page document; and

each sub-region is a portion of one page of the document.

3. The method of claim 2, wherein:

each original sub-region is defined by a rectangular bounding box.

4. The method of claim 1, wherein:

the document includes a plurality of different sub documents.

5. The method of claim 4, wherein:

the plurality of different sub documents are printed in a common style.

6. The method of claim 5, wherein:

the plurality of different sub documents are articles in a book or journal.

7. The method of claim 1, wherein:

the sub-regions of the image include gray scale or color data; and

using the gray scale or color data to generate the representative cluster images of the second resolution.

8. The method of claim 1, wherein:

the sub-regions of the image include gray scale or color data and the representative images generated from the clusters are binary images.

9. The method of claim 1, further comprising:

generating the multiple clusters of visually similar sub-regions by applying a hierarchically agglomerative clustering algorithm to the collection of sub-regions.

10. The method of claim 1, further comprising:

using an optical character recognition (OCR) engine to process the image at the first resolution to identify the sub-regions and to assign one or more characters to each sub-region; and

generating the multiple clusters of visually similar sub-regions by assigning the sub-regions to the multiple clusters of sub-regions so that each cluster includes only sub-regions that are assigned the same one or more particular characters by the OCR engine and that are of approximately the same size.

11. The method of claim 1, further comprising:

printing the replica image.

12. The method of claim 1, further comprising:

using gray scale or color information in the image of the document to generate an averaged image for each cluster at the second resolution.

13. The method of claim 1, wherein generating an averaged image further comprises:

obtaining gray scale or color information for each sub-region in a respective cluster;

using the gray scale or color information to obtain a centroid position of each sub-region;

overlapping centroid positions of the sub-regions within the cluster; and

using the overlapped sub-regions in the cluster to obtain the averaged image.

14. The method of claim 1, further comprising:

performing an interpolation in averaging the sub-regions in each cluster to obtain a corresponding averaged image.

15. The method of claim 14, wherein:

a bilinear interpolation algorithm is applied to the interpolation.

16. A computer program product, encoded on a computer-readable medium, operable to cause data processing apparatus to perform operations comprising:

processing an image of a document to produce a collection of non-overlapping sub-regions of the image, each sub-region being at a first resolution;

generating multiple clusters of visually similar clip sub-regions, each of the sub-regions in the collection being included in one of the clusters;

generating a representative cluster image for each of the multiple clusters from the sub-regions in the respective cluster at a second resolution higher than the first resolution; and

producing a replica image of the document by replacing sub-regions in the image with the representative cluster images for the clusters in which the respective sub-regions are included.

17. A method, comprising:

applying an optical character recognition (OCR) process to an original image of a document to produce clip images at different locations of the original image, each clip image being at a first resolution;

classifying the clip images into a plurality of clusters of clip images, each cluster including clip images that are assigned the same one or more characters codes by the OCR process and are identical or similar in size;

transforming each clip image in each cluster into a transformed clip image at a second resolution higher than the first resolution;

averaging transformed clip images in each cluster to generate a cluster image; and

using cluster images of the plurality of clusters to replace corresponding clip images initially produced by the OCR process to generate a replica of the original image of the document at the second resolution.

18. The method of claim 17, further comprising:

applying an interpolation algorithm to each clip image in each cluster to produce a respective transformed clip image.

19. The method of claim 18, wherein:

the interpolation algorithm is a bilinear interpolation algorithm.

20. The method of claim 17, further comprising:

using gray scale or color data in the original image of the document to form the clip images in each cluster.

21. The method of claim 17, further comprising:

printing the replica at the second resolution.

22. The method of claim 17, further comprising:

obtaining a centroid position of each transformed clip image in each cluster;

overlapping centroid positions of transformed clip images within the cluster; and

averaging the overlapped transformed clip images in the cluster to obtain the cluster image.

23. The method of claim 17, wherein:

each clip image is defined by a bounding box in the received OCR output, and

the clusters include (1) clusters in which each clip image is associated with a single bounding box produced by the OCR engine and (2) clusters in which each clip image is associated with two or more adjacent bounding boxes produced by the OCR engine.

24. A computer program product, encoded on a computer-readable medium, operable to cause data processing apparatus to perform operations comprising:

applying an optical character recognition (OCR) process to an original image of a document to produce clip images at different locations of the original image, each clip image being at a first resolution;

classifying the clip images into a plurality of clusters of clip images, each cluster including clip images that are assigned the same one or more characters codes by the OCR process and are identical or similar in size;

transforming each clip image in each cluster into a transformed clip image at a second resolution higher than the first resolution;

averaging transformed clip images in each cluster to generate a cluster image; and

using cluster images of the plurality of clusters to replace corresponding clip images initially produced by the OCR process to generate a replica of the original image of the document at the second resolution.

25. A system, comprising:

an optical character recognition (OCR) engine operable to process an original image of a document to produce an OCR output which includes clip images at different locations of the original image, each clip image being at a first resolution; and

a post-OCR engine in communication with the OCR engine to receive the OCR output,

wherein the post-OCR engine is operable to;

classify the clip images into a plurality of clusters of clip images, each cluster including clip images that are assigned the same one or more characters codes by the OCR engine and are identical or similar in size;

transform each clip image in each cluster into a transformed clip image at a second resolution higher than the first resolution;

average transformed clip images in each cluster to generate a cluster image; and

use cluster images of the plurality of clusters to replace corresponding clip images initially produced by the OCR engine to generate a replica of the original image of the document at the second resolution.

26. The system of claim 25, further comprising:

one or more server computers that comprise the OCR engine and the post-OCR engine; and

a communication network with which the one or more computer servers are in communication, the communication network operable to direct the original image of the document from a client computer to the OCR engine.

27. The system of claim 25, wherein:

the OCR engine and the post-OCR engine are on different server computers.

28. The system of claim 25, further comprising:

one or more server computers that comprise the OCR engine and the post-OCR engine;

a communication network with which the one or more computer servers are in communication; and

one or more storage server computers that are in communication with the communication network and store replicas of selected original images at the second resolution produced by the OCR engine and the post-OCR engine,

wherein the communication network provides communications between a client computer and the one or more storage server computers to allow the client computer to retrieve from the one or more storage server computers an existing replica at the second resolution for an original image produced by the OCR engine and the post-OCR engine.

29. The system of claim 25, further comprising:

a printer connected to the communication network to print the replica produced by the post-OCR engine.