Shape Clustering in Post Optical Character Recognition Processing

• US 20100232719A1
• Filed: 05/20/2010
• Published: 09/16/2010
• Est. Priority Date: 09/08/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Smith, Raymond W., Vincent, Luc
• Granted Patent: US 8,111,927 B2
• Time in Patent Office: Days
• 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

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

Claims

1. A method for post optical character recognition (OCR) processing, 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 including clip images that are identical or similar in size and are assigned the same one or more characters codes by the OCR process;

processing clip images in each of the plurality of clusters to generate a cluster image for each cluster;

for a first cluster assigned one or more first OCR character codes, identifying (1) a second cluster assigned one or more second OCR character codes different from the one or more first OCR character codes, where the cluster image of the second cluster is closer in shape to a cluster image of the first cluster than to cluster images of other clusters assigned one or more OCR characters different from the one or more first OCR character codes, and (2) a third cluster assigned the same one or more first OCR character codes as the first cluster, where the cluster image of the third cluster is closer in shape to the cluster image of the first cluster than to the cluster images of other clusters assigned the one or more first OCR character codes; and

using at least shape differences between the cluster images of the first cluster and the second cluster and between the cluster images of the first cluster and the third cluster to determine a level of confidence in the one or more first OCR character codes assigned to the first cluster.

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, wherein:

clip images in each cluster are recognized by the OCR engine to be a particular shape and of a particular clip image size.

4. The method of claim 1, wherein:

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

5. The method of claim 1, wherein:

the cluster image for each cluster is derived from an average of images in the respective cluster.

6. The method of claim 1, wherein:

the cluster image for each cluster is selected from one of the clip images in the respective cluster.

7. The method of claim 1, further comprising:

replacing the one or more first OCR character codes assigned to the first cluster with the one or more different, second OCR character codes assigned to the second cluster as a newly assigned one or more OCR character codes for the first cluster when a shape metric distance from the first cluster to the second cluster is shorter than a shape metric distance from the first cluster to the third cluster and the second cluster has a greater number of clip images than the first cluster.

8. The method of claim 7, wherein:

maintaining the one or more first OCR character codes assigned to the first cluster when the shape metric distance from the first cluster to the second cluster is longer than the shape metric distance from the first cluster to the third cluster.

9. The method of claim 7, further comprising:

selecting a cluster, that has a shape metric distance from any of all other clusters greater than a threshold shape metric distance, to be further processed to verify one or more OCR character codes currently assigned to the selected cluster.

10. The method of claim 9, further comprising:

soliciting manual identification of the cluster image of the selected cluster; and

using the manual identification to verify, or generate new one or more OCR character codes to replace, the one or more OCR character codes assigned to the selected cluster.

11. The method of claim 8, further comprising:

selecting a cluster, that has a number of clip images less than a threshold number, to be further processed to verify one or more OCR character codes currently assigned to the selected cluster.

12. The method of claim 11, further comprising:

soliciting manual identification of the cluster image of the selected cluster from a person; and

using the manual identification by the person to verify, or generate one or more new OCR character codes to replace, the one or more OCR character codes assigned to the selected cluster.

13. The method of claim 1, further comprising:

using gray scale information or color information in the original image of the document for each clip image to obtain each cluster image.

14. The method of claim 1, further comprising:

obtaining a centroid of each clip image;

aligning different clip images within a cluster with respect to the obtained centroids of the different clip images; and

obtaining an averaged image of the aligned clip images for the cluster to generate a cluster image for the cluster.

15. The method of claim 14, wherein:

the OCR output includes a bounding box to identify each clip image produced by the OCR engine, and

the centroid of each clip image is obtained by a centroid of an image area defined by a respective bounding box.

16. The method of claim 14, further comprising:

using gray scale information or color information for each clip image in the original image of the document to obtain the centroid of each clip image.

17. The method of claim 14, further comprising:

using image information for each clip image in the OCR output of the document to obtain the centroid of each clip image.

18. The method of claim 17, wherein:

the image information for each clip image in the OCR output of the document is binary image information.

19. The method of claim 1, further comprising:

selecting a cluster image of a cluster to solicit manual identification from a person; and

using the manual identification by the person to verify or correct one or more OCR character codes assigned to the selected cluster.

20. The method of claim 19, 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 20, further comprising:

using an on-line game provided by the on-line server to supply the cluster image of the selected cluster to the one or more users for a user response as part of the on-line game.

22. The method of claim 20, further comprising:

using an on-line service provided by the on-line server to supply the cluster image of the selected cluster as part of a challenge-response test.

23. The method of claim 22, wherein:

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

24. The method of claim 1, further comprising:

selecting a cluster image of a cluster having a high confidence score as a cluster image template;

aligning the cluster image template with a plurality of different portions within an image of a word in the received OCR output along a predetermined direction, one portion at a time;

obtaining shape metric distances between the cluster image template and the plurality of different portions of the word image, respectively;

using the obtained shape metric distances to determine whether a portion of the word image matches the cluster image template;

separating a matching portion of the word image that matches the cluster image template from on or more other portions of the word image; and

assigning one or more OCR character codes assigned to the cluster to the separated matching portion of the word image.

25. The method of claim 1, further comprising:

selecting a first cluster image of a first cluster as a cluster image template;

aligning the cluster image template with a plurality of different portions within a second cluster image of a second selected cluster along a predetermined direction, one portion at a time;

using shape metric distances between the cluster image template and the plurality of different portions of the second cluster image, respectively;

to search for a mach; and

using a matched portion to segment the second cluster image into two or more cluster images.

26. A computer program product, encoded on a computer-readable medium, operable to cause data processing apparatus to perform operations 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 including clip images that are identical or similar in size and are assigned the same one or more characters codes by the OCR process;

processing clip images in each of the plurality of clusters to generate a cluster image for each cluster;

for a first cluster assigned one or more first OCR character codes, identifying (1) a second cluster assigned one or more second OCR character codes different from the one or more first OCR character codes, where the cluster image of the second cluster is closer in shape to a cluster image of the first cluster than to cluster images of other clusters assigned one or more OCR characters different from the one or more first OCR character codes, and (2) a third cluster assigned the same one or more first OCR character codes as the first cluster, where the cluster image of the third cluster is closer in shape to the cluster image of the first cluster than to the cluster images of other clusters assigned the one or more first OCR character codes; and

using at least shape differences between the cluster images of the first cluster and the second cluster and between the cluster images of the first cluster and the third cluster to determine a level of confidence in the one or more first OCR character codes assigned to the first cluster.

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

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

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

wherein the post-OCR engine is operable to process clip images in each of the plurality of clusters to generate a cluster image for each cluster,

wherein the post-OCR engine is operable to identify, for a first cluster assigned one or more first OCR character codes, (1) a second cluster assigned one or more second OCR character codes different from the one or more first OCR character codes, where the cluster image of the second cluster is closer in shape to a cluster image of the first cluster than to cluster images of other clusters assigned one or more OCR characters different from the one or more first OCR character codes, and (2) a third cluster assigned the same one or more first OCR character codes as the first cluster, where the cluster image of the third cluster is closer in shape to the cluster image of the first cluster than to the cluster images of other clusters assigned the one or more first OCR character codes; and

wherein the post-OCR engine is operable to use at least shape differences between the cluster images of the first cluster and the second cluster and between the cluster images of the first cluster and the third cluster to determine a level of confidence in the one or more first OCR character codes assigned to the first cluster.

28. The system of claim 27, 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.

29. The system of claim 28, wherein:

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

30. The system of claim 27, 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 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 and the post-OCR 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 produced by the OCR engine and the post-OCR engine.

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

a cluster generation engine operable to receive an OCR output including separated images produced by an OCR engine in processing an original image of a document and one or more characters assigned to each separated image by the OCR engine, the 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 engine; and

a cluster processing engine operable to obtain shape metric distances between a cluster image of a cluster and cluster images of other clusters and to detect whether an error exists in assignment of one or more OCR character codes assigned to each cluster by the OCR engine based on the obtained shape metric distances, the cluster processing engine further operable to correct one or more erroneously assigned OCR character codes for a cluster.

32. The system of claim 31, 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.

33. The system of claim 31, wherein:

the cluster processing engine is further operable to replace one or more first OCR character codes assigned to a 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 has a higher level of confidence than the first cluster.

34. The system of claim 33, wherein:

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

35. The system of claim 33, wherein:

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

36. The system of claim 33, wherein:

the cluster processing engine is further operable to apply gray scale or color information in the original image in the document in obtaining each cluster image.

37. The system of claim 36, wherein:

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

38. The system of claim 36, wherein:

the cluster image is one of clip images in each cluster.

39. The system of claim 31, 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.

40. The system of claim 31, 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 characters for each cluster processed by the cluster processing engine to each clip image belonging to the cluster.

41. The system of claim 40, wherein:

the output processing engine is operable to;

select a cluster image of a cluster having a high confidence score as a cluster image template;

align the cluster image template with a plurality of different portions within an image of a word in the received OCR output along a predetermined direction, one portion at a time;

obtain shape metric distances between the cluster image template and the plurality of different portions of the word image, respectively;

use the obtained shape metric distances to determine whether a portion of the word image matches the cluster image template;

separate a matching portion of the word image that matches the cluster image template from on or more other portions of the word image; and

assign one or more OCR character codes assigned to the cluster to the separated matching portion of the word image in the modified OCR output.

42. The system of claim 31, wherein:

the cluster processing engine is further operable to;

select a cluster with a high confidence score to use a corresponding averaged image of the selected cluster as a cluster image template;

align the cluster image template with a plurality of different portions of an averaged image of a second selected cluster of a low confidence score at a plurality of different positions along a predetermined direction;

obtain shape metric distances between the cluster image template and each of the plurality of different portions of the averaged image of the second selected cluster;

use the obtained shape metric distances for the cluster image template to determine whether a portion of the averaged image of the second selected cluster matches the cluster image template;

separate a matched portion from the averaged image of the second selected cluster as a new cluster; and

assign to the new cluster one or more OCR character codes that have been assigned to the selected cluster.

43. The system of claim 31, further comprising:

one or more server computers that comprise the OCR engine, the cluster generation engine and the cluster processing 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 and to direct the modified OCR output for the original image of the document from the one or more server computers to the client computer.

44. The system of claim 43, wherein:

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

45. The system of claim 31, further comprising:

one or more OCR computer servers that comprise the OCR engine, the cluster generation engine and the cluster processing engine;

a communication network with which the one or more OCR 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 and to direct the modified OCR output for the original image of the document from the one or more OCR computer servers to the client computer; and

a computer server in communication with the communication network and operable to direct a selected cluster image to one or more users for manual identification of the selected cluster image,

wherein the cluster processing engine is operable to;

direct a cluster image of the selected cluster to the computer server; and

use manual identification of the cluster image returned from the computer server to verify or correct one or more OCR character codes assigned by the OCR engine to the selected cluster.

46. The system of claim 31, further comprising:

one or more server computers that comprise the OCR engine, the cluster generation engine and the cluster processing engine;

a communication network with which the one or more computer servers 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 produced by the OCR engine and the post-OCR engine.

47. A method for optical character recognition (OCR), comprising:

receiving an OCR output including separated images produced by an OCR engine in processing an original image of a document and one or more characters assigned to each separated image by the OCR engine,

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 engine;

obtaining shape metric distances between a cluster image of a cluster and cluster images of other clusters and to detect whether an error exists in assignment of one or more OCR character codes assigned to each cluster by the OCR engine based on the obtained shape metric distances; and

correcting one or more erroneously assigned OCR character codes for a cluster.

48. The method of claim 47, 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.

49. The method of claim 47, further comprising:

replacing one or more first OCR character codes assigned to a 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 has a higher level of confidence than the first cluster.

50. The method of claim 49, wherein:

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

51. The method of claim 49, wherein:

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

52. The method of claim 49, further comprising:

applying gray scale or color information in the original image in the document in obtaining each cluster image.

53. The method of claim 52, wherein:

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

54. The method of claim 52, wherein:

the cluster image is one of clip images in each cluster.

55. The method of claim 49, 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.

56. The method of claim 47, further comprising:

selecting a cluster image of a cluster having a high confidence score as a cluster image template;

aligning the cluster image template with a plurality of different portions within an image of a word in the OCR output along a predetermined direction, one portion at a time;

obtaining shape metric distances between the cluster image template and the plurality of different portions of the word image, respectively;

using the obtained shape metric distances to determine whether a portion of the word image matches the cluster image template;

separating a matching portion of the word image that matches the cluster image template from on or more other portions of the word image; and

assigning one or more OCR character codes assigned to the cluster to the separated matching portion of the word image in the modified OCR output.

57. The method of claim 47, further comprising:

selecting a cluster with a high confidence score to use a corresponding averaged image of the selected cluster as a cluster image template;

aligning the cluster image template with a plurality of different portions of an averaged image of a second selected cluster of a low confidence score at a plurality of different positions along a predetermined direction;

obtaining shape metric distances between the cluster image template and each of the plurality of different portions of the averaged image of the second selected cluster;

using the obtained shape metric distances for the cluster image template to determine whether a portion of the averaged image of the second selected cluster matches the cluster image template;

separating a matched portion from the averaged image of the second selected cluster as a new cluster; and

assigning to the new cluster one or more OCR character codes that have been assigned to the selected cluster.

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

receiving an OCR output including separated images produced by an optical character recognition (OCR) process in processing an original image of a document and one or more characters assigned to each separated image by the OCR process,

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;

obtaining shape metric distances between a cluster image of a cluster and cluster images of other clusters 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 obtained shape metric distances; and

correcting one or more erroneously assigned OCR character codes for a cluster.