Shape clustering in post optical character recognition processing

• US 20080063276A1
• Filed: 09/08/2006
• Published: 03/13/2008
• Est. Priority Date: 09/08/2006
• Status: Active Grant

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

comparing the cluster images to detect clusters to which one or more OCR character codes were erroneously assigned by the OCR process;

assigning one or more new OCR character codes to a first cluster that is detected to have an erroneously assigned one or more OCR character codes in the OCR output; and

using the one or more new OCR character codes to replace the erroneously assigned OCR character code at each occurrence of one of the clip images of the first cluster in the OCR output to produce a modified OCR output.

2. 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.

3. 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.

4. The method of claim 1, further comprising:

classifying joint clip images in the received OCR output into a plurality of joint clusters of joint clip images that are identical or similar in shape and size, each joint clip image being a combination of two or more clip images associated with two or more adjacent bounding boxes in the received OCR output; and

applying each processing on the clusters to the joint clusters.

5. The method of claim 1, wherein:

the cluster image for each cluster is derived from an average of clip 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:

using shape differences in cluster images between each cluster and other clusters to detect whether an error exists in one or more OCR character codes assigned to a cluster in the OCR output.

8. The method of claim 7, further comprising:

obtaining a shape metric distance between cluster images as a measure of a shape difference between two clusters.

9. The method of claim 8, further comprising:

replacing one or more first OCR character codes assigned to a first cluster with one or more different, second OCR character codes assigned to a second cluster as newly assigned one or more OCR character codes for the first cluster used in the modified OCR output when the second cluster has a shortest shape metric distance from the first cluster among all other clusters and has a higher confidence score than the first cluster.

10. The method of claim 9, wherein:

the one or more second OCR character codes for the second cluster are generated based on manual identification of a corresponding clip image.

11. The method of claim 8, 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.

12. The method of claim 11, further comprising:

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

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

13. The method of claim 9, wherein:

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

14. The method of claim 1, wherein:

comparing the cluster images to detect clusters to which one or more OCR character codes were erroneously assigned comprises;

determining a shape metric distance between the cluster image of each cluster that is assigned the same one or more character codes and each of all other clusters as a distance between the respective clusters; and

detecting a first cluster to have an erroneously assigned one or more OCR character codes if a second cluster is closer to the first cluster than other clusters that are assigned the same one or more character codes as the first cluster and if the second cluster is assigned one or more character codes different from the one or more character codes assigned to the first cluster and if the second cluster has a higher level of confidence than the first cluster.

15. 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.

16. The method of claim 15, further comprising:

using gray scale information or color information in the original image of the document to obtain shape distances between different clusters; and

using the shape distances to compare the cluster images.

17. 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.

18. The method of claim 17, 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.

19. The method of claim 17, 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.

20. The method of claim 17, further comprising:

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

21. The method of claim 20, wherein:

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

22. The method of claim 1, 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 corresponding OCR character codes currently assigned to the selected cluster.

23. The method of claim 22, 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.

24. 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.

25. The method of claim 1, 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 new one or more OCR character codes to the selected cluster.

26. The method of claim 25, 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.

27. The method of claim 25, 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.

28. The method of claim 27, wherein:

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

29. The method of claim 1, further comprising:

selecting a cluster image of a cluster including 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 in the modified OCR output.

30. 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;

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

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

using a matching portion of the second cluster image that matches the cluster image template as a new third cluster image for a third cluster to be formed;

separating a corresponding portion in each clip image in the second cluster that corresponds to the cluster image template to form a new clip image;

using new clip images respectively separated from the clip images in the second cluster to form the third cluster;

assigning one or more OCR character codes assigned to the first cluster to the third cluster;

using remainders of clip images of the second cluster after separation of the new clip images for the third cluster to form at least one fourth cluster; and

using the third cluster and the at least one fourth cluster to replace the second cluster in producing the modified OCR output.

31. The method of claim 30, wherein:

the second cluster image is an image of a ligature representing at least two language tokens for one or more languages used in the document.

32. The method of claim 30, further comprising:

obtaining shape metric distances between a cluster image of the fourth cluster and cluster images of other clusters; and

assigning to the fourth cluster one or more OCR character codes assigned to a fifth cluster that has a shortest shape metric distance from the fourth cluster among all other clusters.

33. The method of claim 30, further comprising:

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

using the manual identification by the person to generate new one or more OCR character codes for the fourth cluster.

34. The method of claim 1, wherein:

an OCR character code is a computer code representing a character used in the document.

35. The method of claim 34, wherein:

the character includes one of a letter, a numeral, and a symbol or mark which includes one of a punctuation mark, a typographical mark and a diacritical mark.

36. The method of claim 1, further comprising:

using a number of images in each cluster and shape metric distances of each cluster relative to other clusters to classify the plurality of clusters into acceptable clusters and suspect clusters, wherein assigned one or more particular characters for each acceptable cluster are used in the modified output without further processing and assigned one or more particular characters for each suspect cluster are marked to be further processed;

replacing assigned one or more particular characters for a suspect cluster with assigned one or more particular characters for an acceptable cluster as newly corrected assigned one or more particular characters for the suspect cluster when the acceptable cluster has a shortest shape metric distance from the suspect cluster and has a larger number of images than the suspect cluster; and

using the newly corrected assigned one or more particular characters for the suspect cluster to represent each instance in the modified output for the document where an image within the suspect cluster appears.

37. The method of claim 1, further comprising:

using a number of images in each cluster and shape metric distances of each cluster relative to other clusters to classify the plurality of clusters into acceptable clusters and suspect clusters, wherein assigned one or more particular characters for each acceptable cluster are used in the modified output without further processing and assigned one or more particular characters for each suspect cluster are marked to be further processed;

selecting a cluster image of a suspect cluster to be manually identified by a person;

using one or more manually generated characters returned by the person for the selected suspect cluster to verify or replace previously assigned one or more particular characters for the selected suspect cluster; and

reclassifying the selected suspect cluster assigned the one or more manually generated characters as an acceptable cluster.

38. The method of claim 1, further comprising:

using a number of images in each cluster and shape metric distances of each cluster relative to other clusters to classify the plurality of clusters into acceptable clusters and suspect clusters, wherein assigned one or more particular characters for each acceptable cluster are used in the modified output without further processing and assigned one or more particular characters for each suspect cluster are marked to be further processed;

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

using one or more manually generated characters returned from the on-line server to verify or replace previously assigned one or more particular characters for the selected suspect cluster; and

reclassifying the selected suspect cluster assigned the one or more manually generated characters as an acceptable cluster.

39. The method of claim 38, wherein:

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

40. The method of claim 38, wherein:

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

41. The method of claim 1, further comprising:

using a number of images in each cluster and shape metric distances of each cluster relative to other clusters to classify the plurality of clusters into acceptable clusters and suspect clusters, wherein assigned one or more particular characters for each acceptable cluster are used in the modified output without further processing and assigned one or more particular characters for each suspect cluster are marked to be further processed;

selecting at least one acceptable cluster to use a corresponding cluster image of the selected acceptable cluster as a cluster image template;

aligning the cluster image template with a plurality of different portions of a cluster image of a selected suspect cluster 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 cluster image of the selected suspect cluster;

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

separating a matched portion from the cluster image of the selected suspect cluster as a new acceptable cluster which is assigned the one or more characters for the selected acceptable cluster.

50. The method of claim 39, wherein:

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

42. 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 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;

comparing the cluster images to detect clusters to which one or more OCR character codes were erroneously assigned by the OCR process;

assigning one or more new OCR character codes to a first cluster that is detected to have an erroneously assigned one or more OCR character codes in the OCR output; and

using the one or more new OCR character codes to replace the erroneously assigned OCR character code at each occurrence of one of the clip images of the first cluster in the OCR output to produce a modified OCR output.

43. 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 the OCR output 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;

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, compare the cluster images to detect clusters to which one or more OCR character codes were erroneously assigned by the OCR engine, assign one or more new OCR character codes to a first cluster that is detected to have an erroneously assigned one or more OCR character codes in the OCR output, and use the one or more new OCR character codes to replace the erroneously assigned OCR character code at each occurrence of one of the clip images of the first cluster in the OCR output to produce a modified OCR output.

44. The system of claim 43, 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 and to direct the modified OCR output from the post-OCR engine to the client computer.

45. The system of claim 44, wherein:

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

46. The system of claim 43, 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.

47. 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.

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

49. The method of claim 47, wherein:

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

51. The method of claim 47, wherein:

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

52. The method of claim 47, wherein:

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

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

54. The method of claim 53, 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.

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

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

57. The method of claim 53, 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.

58. The method of claim 57, 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.

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

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

61. The method of claim 60, 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.

62. The method of claim 60, 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.

63. The method of claim 60, further comprising:

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

64. The method of claim 63, wherein:

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

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

66. The method of claim 65, 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.

67. The method of claim 66, 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.

68. The method of claim 66, 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.

69. The method of claim 68, wherein:

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

70. 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 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.

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

72. 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.

73. 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.

74. The system of claim 73, 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.

75. The system of claim 74, wherein:

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

76. The system of claim 73, 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.

77. 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.

78. The system of claim 77, 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.

79. The system of claim 77, 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.

80. The system of claim 79, wherein:

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

81. The system of claim 79, wherein:

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

82. The system of claim 79, 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.

83. The system of claim 82, wherein:

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

84. The system of claim 82, wherein:

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

85. The system of claim 77, 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.

86. The system of claim 77, 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.

87. The system of claim 86, 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.

88. The system of claim 77, 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.

89. The system of claim 77, 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.

90. The system of claim 89, 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.

91. The system of claim 77, 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.

92. The system of claim 77, 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.

93. 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.

94. The method of claim 93, 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.

95. The method of claim 93, 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.

96. The method of claim 95, wherein:

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

97. The method of claim 95, wherein:

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

98. The method of claim 95, further comprising:

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

99. The method of claim 98, wherein:

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

100. The method of claim 98, wherein:

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

101. The method of claim 95, 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.

102. The method of claim 93, 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.

103. The method of claim 93, 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.

104. 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.

105. A method, comprising:

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

applying gray scale or color information from the original document image in averaging clip images in each cluster to generate an averaged image for each cluster.

106. The method of claim 105, further comprising:

using shape differences between an averaged image of each cluster and averaged images of other clusters to verify or detect whether an error exists in the one or more particular characters assigned to each cluster by the OCR process;

correcting each detected error in a particular cluster by newly assigning one or more particular characters to the particular cluster; and

using the newly assigned one or more particular characters for the particular cluster to replace respective one or more particular characters previously assigned by the OCR process in a modified OCR output.

107. The method of claim 105, further comprising:

retrieving the gray scale or color information from the original document image that is absent in the OCR output.

108. The method of claim 105, further comprising:

applying gray scale or color information from the original document image in computing a centroid of each clip image in each cluster;

aligning centroids of all clip images in each cluster to align the clip images; and

averaging the aligned clip images to generate the averaged image for each cluster.

109. The method of claim 105, 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.

110. 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 comprising clip images of identical or similar image sizes and shapes that are assigned the same one or more particular characters by the OCR engine, and

wherein the post-OCR engine is operable to apply gray scale or color information from the original document image in averaging clip images in each cluster to generate an averaged image for each cluster.

111. The system of claim 110, 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.

112. The system of claim 111, wherein:

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

113. 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, from an optical character recognition (OCR) process that processes an original document image, into a plurality of clusters of clip images, each cluster comprising clip images of identical or similar image sizes and shapes that are assigned the same one or more particular characters by the OCR process; and

applying gray scale or color information from the original document image in averaging clip images in each cluster to generate an averaged image for each cluster.