Shape clustering in post optical character recognition processing

• US 8,170,351 B2
• Filed: 07/21/2011
• Issued: 05/01/2012
• Est. Priority Date: 09/08/2006
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Vincent, Luc, Smith, Raymond W.
• Primary Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US13/188,112
• Publication Number:
  US 20110280483A1
• Time in Patent Office: 285 Days
• Field of Search: 382/225
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 10/762 using clustering, e.g. of similar faces in social networks
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/12 Detection or correction of errors, e.g. by rescanning the pattern

Abstract

Systems, methods, and computer program products on storage devices for shape clustering and applications in processing various documents, including an output of an optical character recognition (OCR) process. The output of an OCR process is classified into a plurality of clusters of clip images and a representative image for each cluster is generated to identify clusters whose clip images were incorrectly assigned character codes by the OCR process.

Claims

1. A system for processing an optical character recognition (OCR) output including separated images produced by an OCR process in processing an original image of a document and one or more characters assigned to each separated image by the OCR process, comprising:

one or more computers, the one or more computers implementing;

a cluster generation engine operable to classify the separated images in the OCR output into a plurality of clusters of separated images that are of a particular image size and are assigned the same one or more OCR character codes by the OCR process; and

a cluster processing engine operable to determine shape metric distances between a cluster image of a cluster and cluster images of other clusters, wherein each cluster image is representative of separated images in each cluster, and to detect whether an error exists in assignment of one or more OCR character codes assigned to each cluster by the OCR process based on the shape metric distances,

wherein the cluster processing engine is further operable to correct one or more erroneously assigned OCR character codes for a first cluster including replacing one or more first OCR character codes assigned to the first cluster with one or more second OCR character codes assigned to a second cluster as new one or more OCR character codes for the first cluster when the second cluster has a shortest shape metric distance from the first cluster among all other clusters and the second cluster has a higher level of confidence than the first cluster.

2. The system of claim 1, wherein:

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

the clusters include (1) clusters in which each separated image is associated with a single bounding box in the received OCR output and (2) clusters in which each separated image is associated with two or more adjacent bounding boxes in the received OCR output.

3. The system of claim 1, wherein:

the one or more second OCR character codes assigned to the second cluster are manually assigned by a person.

4. The system of claim 1, wherein:

the second cluster has a larger number of images than the first cluster.

5. The system of claim 1, wherein:

the cluster processing engine is further operable to generate each cluster image including applying gray scale or color information in the original image in the document, wherein the gray scale or color information comprises pixel values in which each pixel value can assume more than two values.

6. The system of claim 5, wherein:

the cluster image is an average image of clip images in each cluster.

7. The system of claim 5, wherein:

the cluster image is selected from one of one or more clip images in each cluster.

8. The system of claim 1, wherein

the cluster processing engine is further operable to:

direct a cluster image of a selected cluster to an on-line server which is operable to direct the cluster image to one or more users for manual identification of the cluster image; and

use manual identification of the cluster image returned from the on-line server to verify one or more OCR character codes assigned to the selected cluster or assign one or more new OCR character codes to the selected cluster.

9. The system of claim 1, further comprising:

an output processing engine operable to produce a modified OCR output from the received OCR output, wherein the output processing engine, in producing the modified OCR output, assigns one or more OCR character codes for each cluster processed by the cluster processing engine to each clip image belonging to the cluster.

10. The system of claim 1, further comprising:

a communication network with which the one or more computers are in communication, the communication network operable to direct the original image of the document from a client computer to one or more computers implementing the OCR process and to direct the modified OCR output for the original image of the document from the one or more computers to the client computer.

11. The system of claim 10, wherein:

the cluster generation engine and the cluster processing engine are placed on a computer that is separate from a computer that implements the OCR process.

12. The system of claim 1, further comprising:

one or more computers implementing an OCR engine, wherein the OCR engine implements the OCR process;

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

one or more OCR storage server computers that are in communication with the communication network and store modified OCR outputs for images of selected documents produced by the OCR engine, the cluster generation engine, and the cluster processing engine,

wherein the communication network provides communications between a client computer and the one or more OCR storage server computers to allow the client computer to retrieve from the one or more OCR storage server computers an existing modified OCR output.

13. A computer-implemented method for processing an optical character recognition (OCR) output including separated images produced by an OCR process in processing an original image of a document and one or more characters assigned to each separated image by the OCR process, comprising:

classifying, by operations of a computer system comprising one or more computers, the separated images in the OCR output into a plurality of clusters of separated images that are of a particular image size and are assigned the same one or more OCR character codes by the OCR process;

determining, by operations of the computer system, shape metric distances between a cluster image of a cluster and cluster images of other clusters, wherein each cluster image is representative of separated images in each cluster, and to detect whether an error exists in assignment of one or more OCR character codes assigned to each cluster by the OCR process based on the shape metric distances; and

correcting one or more erroneously assigned OCR character codes for a first cluster including replacing one or more first OCR character codes assigned to the first cluster with one or more second OCR character codes assigned to a second cluster as new one or more OCR character codes for the first cluster when the second cluster has a shortest shape metric distance from the first cluster among all other clusters and the second cluster has a higher level of confidence than the first cluster.

14. The method of claim 13, wherein:

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

the clusters include (1) clusters in which each separated image is associated with a single bounding box in the received OCR output and (2) clusters in which each separated image is associated with two or more adjacent bounding boxes in the OCR output.

15. The method of claim 13, wherein:

the one or more second OCR character codes assigned to the second cluster are manually assigned by a person.

16. The method of claim 13, wherein:

the second cluster has a larger number of images than the first cluster.

17. The method of claim 13, further comprising:

generating each cluster image including applying gray scale or color information in the original image in the document, wherein the gray scale or color information comprises pixel values in which each pixel value can assume more than two values.

18. The method of claim 17, wherein:

the cluster image is an average image of clip images in each cluster.

19. The method of claim 17, wherein:

the cluster image is selected from one of one or more clip images in each cluster.

20. The method of claim 13, further comprising:

directing a cluster image of a selected cluster to an on-line server which is operable to direct the cluster image to one or more users for manual identification of the cluster image; and

using manual identification of the cluster image returned from the on-line server to verify one or more OCR character codes assigned to the selected cluster or assign one or more new OCR character codes to the selected cluster.

21. The method of claim 13, further comprising assigning the one or more second OCR character codes for the first cluster to each clip image belonging to the first cluster.

22. A computer program product, encoded on a computer-readable storage device, operable to cause data processing apparatus to perform operations for processing an optical character recognition (OCR) output including separated images produced by an OCR process in processing an original image of a document and one or more characters assigned to each separated image by the OCR process, comprising:

classifying the separated images in the OCR output into a plurality of clusters of separated images that are of a particular image size and are assigned the same one or more OCR character codes by the OCR process;

determining shape metric distances between a cluster image of a cluster and cluster images of other clusters, wherein each cluster image is representative of separated images in each cluster, and to detect whether an error exists in assignment of one or more OCR character codes assigned to each cluster by the OCR process based on the shape metric distances; and

correcting one or more erroneously assigned OCR character codes for a first cluster including replacing one or more first OCR character codes assigned to the first cluster with one or more second OCR character codes assigned to a second cluster as new one or more OCR character codes for the first cluster when the second cluster has a shortest shape metric distance from the first cluster among all other clusters and the second cluster has a higher level of confidence than the first cluster.

23. The computer program product of claim 22, wherein:

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

the clusters include (1) clusters in which each separated image is associated with a single bounding box in the received OCR output and (2) clusters in which each separated image is associated with two or more adjacent bounding boxes in the OCR output.

24. The computer program product of claim 22, wherein:

the one or more second OCR character codes assigned to the second cluster are manually assigned by a person.

25. The computer program product of claim 22, wherein:

the second cluster has a larger number of images than the first cluster.

26. The computer program product of claim 22, wherein the operations further comprise:

generating each cluster image including applying gray scale or color information in the original image in the document, wherein the gray scale or color information comprises pixel values in which each pixel value can assume more than two values.

27. The computer program product of claim 26, wherein:

the cluster image is an average image of clip images in each cluster.

28. The computer program product of claim 26, wherein:

the cluster image is selected from one of one or more clip images in each cluster.

29. The computer program product of claim 22, wherein the operations further comprise:

directing a cluster image of a selected cluster to an on-line server which is operable to direct the cluster image to one or more users for manual identification of the cluster image; and

using manual identification of the cluster image returned from the on-line server to verify one or more OCR character codes assigned to the selected cluster or assign one or more new OCR character codes to the selected cluster.

30. The computer program product of claim 22, wherein the operations further comprise assigning the one or more second OCR character codes for the first cluster to each clip image belonging to the first cluster.