Symbol classification depending on cluster shapes in difference image

• US 7,454,067 B1
• Filed: 09/12/2003
• Issued: 11/18/2008
• Est. Priority Date: 09/12/2003
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Pati, Amar K.
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US10/661,078
• Time in Patent Office: 1,894 Days
• Field of Search: 382182-187, 382217-225
• US Class Current: 382/225
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

Methods and apparatus, including computer program products, for classifying elements of a digital image. An element of the digital image and a prototype representing a class of elements are received and a difference image is generated. The difference image represents differences between the received element and the prototype and includes ON pixels that represent local differences between the received element and the prototype. The difference image includes one or more clusters of neighboring ON pixels. Relative arrangements of ON pixels are determined in the difference image. One or more scores are assigned to the difference image using the relative arrangements of ON pixels in the difference image. Based on the assigned scores, it is determined whether the received element belongs to the class represented by the prototype.

Claims

1. A method for classifying elements of a digital image, the method comprising:

receiving an element of the digital image and a prototype representing a class of elements;

generating a difference image representing differences between the received element and the prototype and including a plurality of ON pixels, each ON pixel representing a local difference between the received element and the prototype, wherein the difference image includes one or more clusters of ON pixels, each cluster including one or more neighboring ON pixels;

determining relative arrangements of ON pixels in the difference image;

assigning one or more scores to the difference image using the determined relative arrangements of ON pixels in the difference image;

based on the scores assigned to the difference image, determining whether the received element of the image belongs to the class represented by the prototype; and

generating a representation of the digital image, the representation including a symbol map associating one or more elements of the digital image with the prototype of the class.

2. The method of claim 1, further comprising:

identifying one or more of the clusters of ON pixels in the difference image.

3. The method of claim 2, wherein:

determining relative arrangements of ON pixels in the difference image includes, for each identified cluster, determining a relative arrangement of ON pixels in the cluster, the determined relative arrangement specifying a shape for the cluster.

4. The method of claim 3, wherein:

assigning one or more scores to the difference image includes assigning a score to each cluster based on the shape of the cluster.

5. The method of claim 1, wherein:

assigning one or more scores to the difference image includes assigning a score to each ON pixel in the difference image.

6. The method of claim 5, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel based on a number of other ON pixels in a predetermined neighborhood of the ON pixel.

7. The method of claim 6, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel according to a monotonically increasing function of the number of other ON pixels in the predetermined neighborhood of the ON pixel.

8. The method of claim 7, wherein:

the monotonically increasing function includes an exponential function of the number of ON pixels in the predetermined neighborhood.

9. The method of claim 8, wherein:

the exponential function is two to the power of the number of ON pixels in the predetermined neighborhood.

10. The method of claim 1, wherein:

generating a difference image includes generating a difference image that includes one or more OFF pixels, each OFF pixel representing lack of local difference between the received element and the prototype.

11. The method of claim 1, wherein:

receiving an element of the digital image includes receiving a bitmap image element including neighboring pixels of the same bit value.

12. The method of claim 11, wherein:

receiving a prototype includes receiving a bitmap of the prototype.

13. The method of claim 12, wherein:

generating a difference image includes performing a Boolean exclusive-or operation of each pixel of the bitmap image element with the bitmap of the prototype.

14. The method of claim 1, wherein:

if it is determined that the received element belongs to the class of the prototype, generating a representation of the digital image includes using the symbol map to represent the received element with the prototype of the class.

15. The method of claim 1, wherein:

receiving a prototype representing a class of elements includes receiving a glyph representing a character; and

determining whether the received element belongs to the class represented by the prototype includes determining whether the received element represents the character.

16. The method of claim 15, further comprising:

if it is determined that the received element represents the character, generating a text representation using a character code of the character.

17. The method of claim 16, wherein:

generating a text representation includes using a font that maps the character code to the glyph representing the character.

18. A computer readable medium storing a software product for classifying elements of a digital image, the software product comprising instructions operable to cause one or more data processing apparatus to perform operations comprising:

receiving an element of the digital image and a prototype representing a class of elements;

generating a difference image representing differences between the received element and the prototype and including a plurality of ON pixels, each ON pixel representing a local difference between the received element and the prototype, wherein the difference image includes one or more clusters of ON pixels, each cluster including one or more neighboring ON pixels;

determining relative arrangements of ON pixels in the difference image;

assigning one or more scores to the difference image using the determined relative arrangements of ON pixels in the difference image;

based on the scores assigned to the difference image, determining whether the received element of the image belongs to the class represented by the prototype; and

generating a representation of the digital image, the representation including a symbol map associating one or more elements of the digital image with the prototype of the class.

19. The computer readable medium of claim 18, further comprising instructions operable to cause one or more data processing apparatus to perform operations comprising:

identifying one or more of the clusters of ON pixels in the difference image.

20. The computer readable medium of claim 19, wherein:

determining relative arrangements of ON pixels in the difference image includes, for each identified cluster, determining a relative arrangement of ON pixels in the cluster, the determined relative arrangement specifying a shape for the cluster.

21. The computer readable medium of claim 20, wherein:

assigning one or more scores to the difference image includes assigning a score to each cluster based on the shape of the cluster.

22. The computer readable medium of claim 18, wherein:

assigning one or more scores to the difference image includes assigning a score to each ON pixel in the difference image.

23. The computer readable medium of claim 22, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel based on a number of other ON pixels in a predetermined neighborhood of the ON pixel.

24. The computer readable medium of claim 23, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel according to a monotonically increasing function of the number of other ON pixels in the predetermined neighborhood of the ON pixel.

25. The computer readable medium of claim 24, wherein:

the monotonically increasing function includes an exponential function of the number of ON pixels in the predetermined neighborhood.

26. The computer readable medium of claim 25, wherein:

the exponential function is two to the power of the number of ON pixels in the predetermined neighborhood.

27. The computer readable medium of claim 18, wherein:

generating a difference image includes generating a difference image that includes one or more OFF pixels, each OFF pixel representing lack of local difference between the received element and the prototype.

28. The computer readable medium of claim 18, wherein:

receiving an element of the digital image includes receiving a bitmap image element including neighboring pixels of the same bit value.

29. The computer readable medium of claim 28, wherein:

receiving a prototype includes receiving a bitmap of the prototype.

30. The computer readable medium of claim 29, wherein:

generating a difference image includes performing a Boolean exclusive-or operation of each pixel of the bitmap image element with the bitmap of the prototype.

31. The computer readable medium of claim 18, wherein:

if it is determined that the received element belongs to the class of the prototype, generating a representation of the digital image includes using the symbol map to represent the received element with the prototype of the class.

32. The computer readable medium of claim 18, wherein:

receiving a prototype representing a class of elements includes receiving a glyph representing a character; and

determining whether the received element belongs to the class represented by the prototype includes determining whether the received element represents the character.

33. The computer readable medium of claim 32, further comprising instructions operable to cause one or more data processing apparatus to perform operations comprising:

if it is determined that the received element represents the character, generating a text representation using a character code of the character.

34. The computer readable medium of claim 33, wherein:

generating a text representation includes using a font that maps the character code to the glyph representing the character.

35. A system comprising:

one or more processors;

and one or more computer readable mediums storing a software product for classifying elements of a digital image, the software product comprising instructions operable to cause the one or more processors to perform operations comprising;

receiving an element of the digital image and a prototype representing a class of elements;

generating a difference image representing differences between the received element and the prototype and including a plurality of ON pixels, each ON pixel representing a local difference between the received element and the prototype, wherein the difference image includes one or more clusters of ON pixels, each cluster including one or more neighboring ON pixels;

determining relative arrangements of ON pixels in the difference image;

assigning one or more scores to the difference image using the determined relative arrangements of ON pixels in the difference image;

based on the scores assigned to the difference image, determining whether the received element of the image belongs to the class represented by the prototype; and

generating a representation of the digital image, the representation including a symbol map associating one or more elements of the digital image with the prototype of the class.

36. The system of claim 35, the operations further comprising:

identifying one or more of the clusters of ON pixels in the difference image.

37. The system of claim 36, wherein:

determining relative arrangements of ON pixels in the difference image includes, for each identified cluster, determining a relative arrangement of ON pixels in the cluster, the determined relative arrangement specifying a shape for the cluster.

38. The system of claim 37, wherein:

assigning one or more scores to the difference image includes assigning a score to each cluster based on the shape of the cluster.

39. The system of claim 35, wherein:

assigning one or more scores to the difference image includes assigning a score to each ON pixel in the difference image.

40. The system of claim 39, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel based on a number of other ON pixels in a predetermined neighborhood of the ON pixel.

41. The system of claim 40, wherein:

assigning a score to each ON pixel includes assigning a score to each ON pixel according to a monotonically increasing function of the number of other ON pixels in the predetermined neighborhood of the ON pixel.

42. The system of claim 41, wherein:

the monotonically increasing function includes an exponential function of the number of ON pixels in the predetermined neighborhood.

43. The system of claim 42, wherein:

the exponential function is two to the power of the number of ON pixels in the predetermined neighborhood.

44. The system of claim 35, wherein:

generating a difference image includes generating a difference image that includes one or more OFF pixels, each OFF pixel representing lack of local difference between the received element and the prototype.

45. The system of claim 35, wherein:

receiving an element of the digital image includes receiving a bitmap image element including neighboring pixels of the same bit value.

46. The system of claim 45, wherein:

receiving a prototype includes receiving a bitmap of the prototype.

47. The system of claim 46, wherein:

generating a difference image includes performing a Boolean exclusive-or operation of each pixel of the bitmap image element with the bitmap of the prototype.

48. The system of claim 35, wherein:

if it is determined that the received element belongs to the class of the prototype, generating a representation of the digital image includes using the symbol map to represent the received element with the prototype of the class.

49. The system of claim 35, wherein:

receiving a prototype representing a class of elements includes receiving a glyph representing a character; and

determining whether the received element belongs to the class represented by the prototype includes determining whether the received element represents the character.

50. The system of claim 49, the operations further comprising:

if it is determined that the received element represents the character, generating a text representation using a character code of the character.

51. The system of claim 50, wherein:

generating a text representation includes using a font that maps the character code to the glyph representing the character.