Shape clustering and cluster-level manual identification in post optical character recognition processing

• US 7,697,758 B2
• Filed: 09/11/2006
• Issued: 04/13/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): Dang; Duy M
• Application Number:
  US11/519,368
• Publication Number:
  US 20080063278A1
• Time in Patent Office: 1,310 Days
• Field of Search: 382/160, 382/173, 382/177, 382/181, 382/187, 382/224, 382/225, 382/309, 382/321
• US Class Current: 382/177
• 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 computer-implemented method for processing output from an optical character recognition (OCR) process, comprising:

classifying separated images in an output of the OCR process generated from processing an original image of a document into a plurality of clusters of separated images, each cluster comprising separated images of similar image sizes and shapes that are assigned the same one or more particular characters by the OCR process;

using a cluster image to represent separated images in a respective cluster;

selecting a cluster which has a low level of confidence to obtain a manual assignment of one or more characters with the cluster image of the selected cluster; and

using the one or more characters obtained by the manual assignment to verify or replace respective one or more particular characters previously assigned by the OCR process in the output of the OCR process,

wherein the method is performed by one or more computer processors.

2. The method of claim 1, 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 in the received OCR output and (2) clusters in which each clip image is associated with two or more adjacent bounding boxes in the received OCR output.

3. The method of claim 1, further comprising:

averaging separated images in each cluster to generate an averaged image as the cluster image.

4. The method of claim 1, further comprising:

using shape differences between a cluster image of each cluster and cluster images of all other clusters to measure a level of confidence for the one or more particular characters assigned to each cluster by the OCR process.

5. The method of claim 1, further comprising:

when the manual assignment identifies the cluster image of the selected cluster as a nonsensical image for the OCR process, indicating a nonsensical status of the selected cluster in the OCR output.

6. The method of claim 1, further comprising:

directing the cluster image of the selected cluster to an on-line server which is operable to direct the cluster image to one or more users and to solicit one or more manually generated characters for the cluster image from the one or more users; and

using one or more manually generated characters returned from the on-line server as the newly assigned one or more particular characters for the selected cluster.

7. The method of claim 6, wherein:

the on-line server is operable to provide an on-line game which supplies the cluster image of the selected cluster to the one or more users for user response as part of the on-line game.

8. The method of claim 6, wherein:

the on-line server is operable to provide an on-line service and to supply the cluster image of the selected cluster as part of a challenge-response test to determine whether or not a user of the one-line service is a human.

9. The method of claim 1, wherein:

the selected cluster has a shape distance to other clusters greater than a threshold shape distance.

10. The method of claim 1, wherein:

the selected cluster has a number of images less than a threshold number.

11. A system for optical character recognition (OCR), comprising:

an OCR engine operable to process an original image of a document to produce separated images extracted from the original image and assign one or more characters to each separated image; and

a post-OCR engine operable to classify separated images in the OCR output into a plurality of clusters of separated images, each cluster comprising separated images of similar image sizes and shapes that are assigned the same one or more particular characters by the OCR engine,

wherein the post-OCR engine is operable to generate a cluster image to represent separated images in a respective cluster, select a cluster which has a low level of confidence to obtain a manual assignment of one or more characters with the cluster image of the selected cluster, and use the one or more characters obtained by the manual assignment to verify or replace respective one or more particular characters previously assigned by the OCR engine; and

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

12. The system of claim 11, further comprising:

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

an on-line server in communication with the communication network,

wherein the post-OCR engine is operable to direct the cluster image of the selected cluster to the on-line server which is operable to direct the cluster image to one or more users and to solicit one or more manually generated characters for the cluster image from the one or more users; and

wherein the post-OCR engine is operable to use one or more manually generated characters returned from the on-line server as the newly assigned one or more particular characters for the selected cluster.

13. The system of claim 12, wherein:

the communication network is operable to direct the original image of the document from a client computer to the OCR engine and to direct an output from the post-OCR engine to the client computer.

14. The system of claim 12, wherein:

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

15. The system of claim 12, wherein:

the on-line server is operable to provide an on-line game which supplies the cluster image of the selected cluster to the one or more users for user response as part of the on-line game.

16. The system of claim 12, wherein:

the on-line server is operable to provide an on-line service and to supply the cluster image of the selected cluster as part of a challenge-response test to determine whether or not a user of the one-line service is a human.

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

classifying separated images in an output of an optical character recognition (OCR) process generated from processing an original image of a document into a plurality of clusters of separated images, each cluster comprising separated images of similar image sizes and shapes that are assigned the same one or more particular characters by the OCR process;

using a cluster image to represent separated images in a respective cluster;

selecting a cluster which has a low level of confidence to obtain a manual assignment of one or more characters with the cluster image of the selected cluster; and

using the one or more characters obtained by the manual assignment to verify or replace respective one or more particular characters previously assigned by the OCR process in the output of the OCR process.

18. The computer program product of claim 17, wherein:

the operations further comprise;

directing the cluster image of the selected cluster to an on-line server which is operable to direct the cluster image to one or more users and to solicit one or more manually generated characters for the cluster image from the one or more users; and

using one or more manually generated characters returned from the on-line server as the newly assigned one or more particular characters for the selected cluster.

19. A computer-implemented method, comprising:

classifying clip images defined in a received OCR output of a document processed by an optical character recognition (OCR) process into a plurality of clusters of clip images, each cluster comprising clip images of similar image sizes and shapes that are assigned the same one or more particular characters by the OCR process;

generating a cluster image to represent clip images in each cluster;

selecting a cluster image of a particular cluster as part of an on-line challenge-response test to solicit a user identification of the cluster image of the particular cluster; and

using the user identification received from the on-line challenge-response test to verify or correct one or more particular characters assigned to the particular cluster by the OCR process,

wherein the method is performed by one or more computer processors.

20. The method of claim 19, 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 in the received OCR output and (2) clusters in which each clip image is associated with two or more adjacent bounding boxes in the received OCR output.

21. The method of claim 19, further comprising:

obtaining a user identification of the cluster image of the particular cluster from each of a plurality of different users based on the on-line challenge-response test;

validating a particular user identification of the cluster image of the particular cluster by using obtained user identifications from other users of the plurality of different users; and

using the validated user identification to verify or correct one or more particular characters assigned to the particular cluster by the OCR process.

22. The method of claim 19, wherein

the on-line challenge-response test is for determining whether or not a user of the one-line service is a human.

23. A computer-implemented method, comprising:

classifying clip images defined in a received OCR output of a document processed by an optical character recognition (OCR) process into a plurality of clusters of clip images, each cluster comprising clip images of similar image sizes and shapes that are assigned the same one or more particular characters by the OCR process;

using a cluster image to represent clip images in each cluster;

using an on-line game to supply a cluster image of a particular cluster to one or more users of the on-line game for a user response as part of the on-line game; and

using the user response received from the on-line game to verify or correct one or more particular characters assigned to the particular cluster by the OCR process,

wherein the method is performed by one or more computer processors.

24. The method of claim 23, 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 in the received OCR output and (2) clusters in which each clip image is associated with two or more adjacent bounding boxes in the received OCR output.