Font type identification

• US 6,496,600 B1
• Filed: 06/17/1996
• Issued: 12/17/2002
• Est. Priority Date: 06/17/1996
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Huang, Hung Khei
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US08/664,575
• Time in Patent Office: 2,374 Days
• Field of Search: 382/187, 382/191, 382/218, 382/301, 382/178, 382/228, 382/212, 382/203, 382/176
• US Class Current: 382/187
• CPC Class Codes: G06V 30/245 Font recognition

Abstract

An optical character recognition system identifies a font type for an image of a block of text. Key characters matching characters in a pre-defined character set are located in the text block. The image of the text block is partitioned into plural image segments where, for example, each image segment is an image of one line of text. Each image segment is evaluated to determine whether the characters in the image segment have fixed pitch or variable pitch. For each key character in the image segments designated as variable pitch, a determination is made whether a gap exists between a left edge of the key character image and the left border of the key character. A font type is identified for the characters in the image data based on the fixed pitch determinations and the gap determinations.

Claims

1. A method for determining from a pixel image of a character whether the character has a serif font or a sans serif font, comprising the steps of:

obtaining a position of pixels for a left border for the image of the character;

measuring plural lengths of blank pixels between the position of the left border and a position of a left edge of the character image, wherein each of the lengths corresponds to a number of blank pixels;

determining, based on a threshold and the measured lengths, whether a gap exists between the left edge of the character image and the left border of the character image; and

designating the character as serif if said determining step determines, based on the threshold and the measured lengths, that a gap exists and sans serif if said determining step determines, based on the threshold and the measured lengths, that no gap exists.

2. A method according to claim 1, further comprising the step of obtaining a rectangle circumscribed around the character image, wherein the left border for the character image is the left side of the rectangle.

3. A method according to claim 1, wherein the left border for the character image is a line segment passing through a leftmost pixel of the character image.

4. A method according to claim 1, wherein the step of measuring plural lengths of blank pixels further comprises measuring the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the character image.

5. A method according to claim 4, wherein the determination as to whether a gap exists is made by comparing the average of the measured lengths to the threshold.

69. A method according to claim 1, wherein the threshold is dependent on a width of a portion of the character image.

70. A method according to claim 69, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

71. A method according to claim 69, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

6. A method for determining a font type for plural characters from pixel image data that includes pixel images of the characters, comprising:

an accessing step of accessing a predefined character set consisting essentially of characters each having a substantially straight left edge;

a designating step of designating at least one character in the image data which matches a character in the pre-defined character set as a key character;

an obtaining step of obtaining a position of pixels for a left border for an image of each key character;

a measuring step of measuring, for each key character, plural lengths of blank pixels between the position of the left border and a position of a left edge for the image of each key character, wherein each of the lengths corresponds to a number of blank pixels;

a determining step of determining, based on a threshold and the measured lengths for each key character, whether a gap exists between the left edge of the image of the key character and the left border for the image of the key character;

an identifying step of identifying the font type for the characters in the image data based at least in part on whether the determining step determines that a gap exists for key characters.

7. A method according to claim 6, wherein the pre-defined character set includes characters having plural font styles, and wherein for each key character both the identity and the font style of the key character match the identity and font style of a character in the pre-defined character set.

8. A method according to claim 6, further comprising:

a first counting step of counting the key characters for which it is determined that a gap exists; and

a second counting step of counting the key characters for which it is determined that no gap exists,

wherein the identifying step identifies the font type for the characters in the image data based on a count value obtained in the first counting step and a count value obtained in the second counting step.

9. A method according to claim 6, further comprising a second obtaining step of obtaining for each key character image a rectangle circumscribed around the key character image, wherein the left border for each key character image is the left side of the rectangle circumscribed around the key character image.

10. A method according to claim 6, wherein the left border for the image of each key character is a line segment passing through a leftmost pixel of the key character image.

11. A method according to claim 6, wherein the measuring step measures, for each key character, the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the image for the key character.

12. A method according to claim 11, wherein the determination for each key character in the determining step is made by comparing the average of the measured lengths for the key character to the threshold.

13. A method according to claim 12, wherein the threshold for a key character is determined in accordance with the width of the darkened portion of the key character image.

14. A method according to claim 6, wherein the pre-defined character set contains only characters in which, after removal of any italic font style character slant, the substantially straight left edge is vertical.

15. A method according to claim 6, further comprising the-step of determining whether characters in the image data have fixed pitch, wherein the identifying step identifies the font type for the characters in the image data based on whether characters in the image data have fixed pitch.

16. A method according to claim 6, further comprising the step of printing the characters in the image data in the font type identified in said identifying step.

63. A method according to claim 6, wherein the obtaining, measuring and determining steps are performed only for key characters.

72. A method according to claim 6, wherein the threshold is dependent on a width of a portion of the character image.

73. A method according to claim 72, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

74. A method according to claim 72, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

17. A method for determining a font type for plural characters from pixel image data that include pixel images of the characters, comprising:

a designating step of designating plural characters in the image data as key characters, wherein each key character has a substantially straight left edge;

a partitioning step of partitioning the image data into image segments;

a fixed pitch determining step of determining for each image segment whether the characters in the image segment have fixed pitch, and in accordance with that determination, designating the image segment as fixed pitch or variable pitch;

a border-obtaining step of obtaining a position of pixels for a left border for an image of each key character in the image segments designated as variable pitch;

a measuring step of measuring, for each key character in image segments designated as variable pitch, plural lengths of blank pixels between the position of the left border and a position of a left edge for the image of each key character, wherein each of the lengths corresponds to a number of blank pixels;

a gap determining step of determining, based on a threshold and the measured lengths for each key character in image segments designated as variable pitch, whether a gap exists between the left edge of the image of the key character and the left border for the image of the key character; and

an identifying step of identifying the font type for the characters in the image data based on determinations made in the fixed pitch determining step and the gap determining step.

18. A method according to claim 17, wherein each image segment consists of a single line of text.

19. A method according to claim 17, further comprising:

a first counting step of counting the key characters for which it is determined that a gap exists;

a second counting step of counting the key characters for which it is determined that no gap exists; and

a third counting step of counting the key characters in the image segments designated as fixed pitch,

wherein the identifying step identifies the font type for the characters in the image data in accordance with a maximum count value obtained in said first, second and third counting steps.

20. A method according to claim 17, further comprising the step of printing the characters in the image data in the font type identified in said identifying step.

64. A method according to claim 17, wherein the obtaining, measuring and gap determining steps are performed only for key characters.

75. A method according to claim 17, wherein the threshold is dependent on a width of a portion of the character image.

76. A method according to claim 75, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

77. A method according to claim 75, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

21. An apparatus for determining from a pixel image of a character whether the character has a serif font or a sans serif font, said apparatus comprising:

a memory for storing the pixel image of the character and program instruction sequences; and

a processor for executing said program instruction sequences stored in said memory,

wherein said program instruction sequences include (a) a border obtaining step to obtain a position of pixels for a left border for the image of the character, (b) a measuring step to measure plural lengths of blank pixels between the position of the left border and a position of a left edge of the character image, wherein each of the lengths corresponds to a number of blank pixels, (c) a determining step to determine, based on a threshold and the measured lengths, whether a gap exists between the left edge of the character image and the left border of the character image, and (d) a designating step to designate the character as serif if said determining step determines, based on the threshold and the measured lengths, that a gap exists and sans serif if no gap exists.

22. An apparatus according to claim 21, wherein said program instruction sequences further include an obtaining step to obtain a rectangle circumscribed around the character image, wherein the left border for the character image is the left side of the rectangle.

23. An apparatus according to claim 21, wherein the left border for the character image is a line segment passing through a leftmost pixel of the character image.

24. An apparatus according to claim 21, wherein the measuring step measures the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the character image.

25. An apparatus according to claim 24, wherein the measuring step includes a comparing step to compare the average of the measured lengths to the threshold.

78. An apparatus according to claim 21, wherein the threshold is dependent on a width of a portion of the character image.

79. An apparatus according to claim 78, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

80. An apparatus according to claim 78, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

26. An apparatus for determining a font type for plural characters from pixel image data that include pixel images of the characters, said apparatus comprising:

a memory for storing the pixel image data and program instruction sequences; and

a processor for executing said program instruction sequences stored in said memory,

wherein said program instruction sequences include (a) an accessing step to access a predefined character set consisting essentially of characters each having a substantially straight left edge, (b) a designating step to designate at least one character in the image data which matches a character in the predefined character set as a key character, (c) a border obtaining step to obtain a position of pixels for a left border for an image of each key character, (d) a measuring step to measure, for each key character, plural lengths of blank pixels between the position of the left border and a position of a left edge for the image of each key character, wherein each of the lengths corresponds to a number of blank pixels, (e) a determining step to determine, based on a threshold and the measured lengths for each key character, whether a gap exists between the left edge of the image of the key character and the left border for the image of the key character, and (f) an identifying step to identify the font type for the characters in the image data based at least in part on whether the determining step determines that a gap exists for key characters.

27. An apparatus according to claim 26, wherein the pre-defined character set includes characters having plural font styles, and wherein for each key character both the identity and the font style of the key character match the identity and font style of a character in the pre-defined character set.

28. An apparatus according to claim 26, wherein said program instruction sequences further include (a) a first counting step to count the key characters for which it is determined that a gap exists and (b) a second counting step to count the key characters for which it is determined that no gap exists, wherein the identification of font type in the identifying step is based on a count value obtained in the first counting step and a count value obtained in the second counting step.

29. An apparatus according to claim 26, wherein said program instruction sequences further include a second obtaining step to obtain for each key character image a rectangle circumscribed around the key character image, wherein the left border for each key character image is the left side of the rectangle circumscribed around the key character image.

30. An apparatus according to claim 26, wherein the left border for the image of each key character is a line segment passing through a leftmost pixel of the key character image.

31. An apparatus according to claim 26, wherein the measuring step measures, for each key character, the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the image for the key character.

32. An apparatus according to claim 31, wherein the determination for each key character in the determining step is made by comparing the average of the measured lengths for the key character to the threshold.

33. An apparatus according to claim 32, wherein the measuring step includes a threshold determining step to determine the threshold for the key character in accordance with the width of the darkened portion of the key character image.

34. An apparatus according to claim 26, wherein the pre-defined character set contains only characters in which, after removal of any italic font style character slant, the substantially straight left edge is vertical.

35. An apparatus according to claim 26, wherein said program instruction sequences further include a fixed pitch determining step to determine whether characters in the image data have fixed pitch, wherein identification of font type in the identifying step is based on whether characters in the image data have fixed pitch.

36. An apparatus according to claim 26, further comprising a printer, wherein said program instruction sequences further include a printing step to cause the printer to print the characters in the image data in the font type identified in said identifying step.

37. An apparatus according to claim 26, further comprising a scanner, wherein said program instruction sequences further include a scanning step to cause the scanner to scan in the image data.

65. An apparatus according to claim 26, wherein the border obtaining, measuring and determining steps are performed only for key characters.

81. An apparatus according to claim 26, wherein the threshold is dependent on a width of a portion of the character image.

82. An apparatus according to claim 81, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

83. An apparatus according to claim 81, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

38. An apparatus for determining a font type for plural characters from pixel image data that include pixel images of the characters, said apparatus comprising:

a memory for storing the image data and program instruction sequences; and

a processor for executing said program instruction sequences stored in said memory,

wherein said program instruction sequences include (a) a designating step to designate plural characters in the image data as key characters, wherein each key character has a substantially straight left edge, (b) a partitioning step to partition the image data into image segments, (c) a fixed pitch determining step to determine for each image segment whether the characters in the image segment have fixed pitch, and in accordance with that determination, to designate the image segment as fixed pitch or variable pitch, (d) a border obtaining step to obtain a position of pixels for a left border for an image of each key character in the image segments designated as variable pitch, (e) a measuring step to measure, for each key character in image segments designated as variable pitch, plural lengths of blank pixels between the position of the left border and a position of a left edge for the image of each key character, wherein each of the lengths corresponds to a number of blank pixels, (f) a gap determining step to determine, based on a threshold and the measured lengths for each key character in the image segments designated as variable pitch, whether a gap exists between the left edge of the image of the key character and the left border for the image of the key character, and (g) an identifying step to identify the font type for the characters in the image data based on determinations made in the fixed pitch determining step and the gap determining step.

39. An apparatus according to claim 38, wherein each image segment consists of a single line of text.

40. An apparatus according to claim 38, wherein said program instruction sequences further include (a) a first counting step to count the key characters for which it is determined in the measuring step that a gap exists, (b) a second counting step to count the key characters for which it is determined in the measuring step that no gap exists, and (c) a third counting step to count the key characters in the image segments designated as fixed pitch, wherein the identification of font type in the identifying step is based on a maximum count value obtained in said first, second and third counting steps.

41. An apparatus according to claim 38, further comprising a printer, wherein said program instruction sequences further include a printing step to cause the printer to print the characters in the image data in the font type identified in said identifying step.

42. An apparatus according to claim 38, further comprising a scanner, wherein said program instruction sequences further include a scanning step to cause the scanner to scan in the image data.

66. An apparatus according to claim 38, wherein the border obtaining, measuring and gap determining steps are performed only for key characters.

84. An apparatus according to claim 38, wherein the threshold is dependent on a width of a portion of the character image.

85. An apparatus according to claim 84, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

86. An apparatus according to claim 84, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

43. Computer executable process steps to determine from a pixel image of a character whether the character has a serif font or a sans serif font, the process steps comprising:

a border obtaining step to obtain a position of pixels for a left border for the image of the character;

a measuring step to measure plural lengths of blank pixels between the position of the left border and a position of a left edge of the character image, wherein each of the lengths corresponds to a number of blank pixels;

a determining step to determine, based on a threshold and the measured lengths, whether a gap exists between the left edge of the character image and the left border of the character image; and

a designating step to designate the character as serif if said determining step determines, based on the threshold and measured lengths, that a gap exists and sans serif if said determining step determines, based on the threshold and measured lengths, that no gap exists.

44. Computer executable process steps according to claim 43, further comprising an obtaining step to obtain a rectangle circumscribed around the character image, wherein the left border for the character image is the left side of the rectangle.

45. Computer executable process steps according to claim 43, wherein the left border for the character image is a line segment passing through a leftmost pixel of the character image.

46. Computer executable process steps according to claim 43, wherein the measuring step measures the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the character image.

47. Computer executable process steps according to claim 46, wherein the measuring step includes a comparing step to compare the average of the measured lengths to the threshold.

87. Computer-executable process steps according to claim 43, wherein the threshold is dependent on a width of a portion of the character image.

88. Computer-executable process steps according to claim 87, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

89. Computer-executable process steps according to claim 87, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

48. Computer executable process steps to determine a font type for plural characters from pixel image data that include pixel images of the characters, said process steps comprising:

an accessing step of accessing a predefined character set consisting essentially of characters each having a substantially straight left edge;

a designating step to designate at least one character in the image data which matches a character in the predefined character set as a key character;

a border obtaining step to obtain a position of pixels for a left border for an image of each key character;

a measuring step to measure, for each key character, plural lengths of blank pixels between the position of the left border and a position of a left edge for the image of each key character image, wherein each of the lengths corresponds to a number of blank pixels;

a determining step to determine, based on a threshold and the measured lengths for each key character, whether a gap exists between the left edge of the image of the key character image and the left border for the image of the key character; and

an identifying step to identify the font type for the characters in the image data based at least in part on whether the determining step determines that a gap exists for key characters.

49. Computer executable process steps according to claim 48, wherein the pre-defined character set includes characters having plural font styles, and wherein for each key character both the identity and the font style of the key character match the identity and font style of a character in the pre-defined character set.

50. Computer executable process steps according to claim 48, further comprising:

a first counting step to count the key characters for which it is determined in the measuring step that a gap exists; and

a second counting step to count the key characters for which it is determined in the measuring step that no gap exists,

wherein the identification of font type in the identifying step is based on a count value obtained in the first counting step and a count value obtained in the second counting step.

51. Computer executable process steps according to claim 48, further comprising a second obtaining step to obtain for each key character image a rectangle circumscribed around the key character image, wherein the left border for each key character image is the left side of the rectangle circumscribed around the key character image.

52. Computer executable process steps according to claim 48, wherein the left border for the image of each key character is a line segment passing through a leftmost pixel of the key character image.

53. Computer executable process steps according to claim 48, wherein the measuring step measures, for each key character, the plural lengths of blank pixels at horizontal gaps between positions of the left border and positions of the left edge of the character image, the measurements of the plural lengths made at intermediate vertical positions between a top left and a bottom left pixel of the image for the key character.

54. Computer executable process steps according to claim 53, wherein the determination for each key character in the determining step is made by comparing the average of the measured lengths for the key character to the threshold.

55. Computer executable process steps according to claim 54, wherein the measuring step includes a threshold determining step to determine the threshold for the key character in accordance with the width of the darkened portion of the key character image.

56. Computer executable process steps according to claim 48, wherein the pre-defined character set contains only characters in which, after removal of any italic font style character slant, the substantially straight left edge is vertical.

57. Computer executable process steps according to claim 48, further comprising a fixed pitch determining step to determine whether characters in the image data have fixed pitch, wherein identification of font type in the identifying step is based on whether characters in the image data have fixed pitch.

58. Computer executable process steps according to claim 48, further comprising a printing step to print the characters in the image data in the font type identified in said identifying step.

67. Computer executable process steps according to claim 48, wherein the border obtaining, measuring and determining steps are performed only for key characters.

90. Computer-executable process steps according to claim 48, wherein the threshold is dependent on a width of a portion of the character image.

91. Computer-executable process steps according to claim 90, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

92. Computer-executable process steps according to claim 90, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.

59. Computer executable process steps to determine a font type for plural characters from pixel image data that include pixel images of the characters, comprising:

a designating step to designate plural characters in the image data as key characters, wherein each key character has a substantially straight left edge;

a partitioning step to partition the image data into image segments;

a fixed pitch determining step to determine for each image segment whether the characters in the image segment have fixed pitch, and in accordance with that determination, to designate the image segment as fixed pitch or variable pitch;

a border obtaining step to obtain a position of pixels for a left border for an image of each key character in the image segments designated as variable pitch;

a measuring step to measure, for each key character in image segments designated as variable pitch, plural lengths of blank pixels between the position of the left border and a position of a left edge the image of for each key character, wherein each of the lengths corresponds to a number of blank pixels;

a gap determining step to determine, based on a threshold and the measured lengths for each key character in image segments designated as variable pitch, whether a gap exists between the left edge of the image of the key character image and the left border for the image of the key character; and

an identifying step to identify the font type for the characters in the image data based on determinations made in the fixed pitch determining step and the gap determining step.

60. Computer executable process steps according to claim 59, wherein each image segment consists of a single line of text.

61. Computer executable process steps according to claim 59, further comprising:

a first counting step to count the key characters for which it is determined in the measuring step that a gap exists;

a second counting step to count the key characters for which it is determined in the measuring step that no gap exists; and

a third counting step to count the key characters in the image segments designated as fixed pitch,

wherein the identification of font type in the identifying step is based on a maximum count value obtained in said first, second and third counting steps.

62. Computer executable process steps according to claim 59, further comprising a printing step to print the characters in the image data in the font type identified in said identifying step.

68. Computer executable process steps according to claim 59, wherein the border obtaining, measuring and gap determining steps are performed only for key characters.

93. Computer-executable process steps according to claim 59, wherein the threshold is dependent on a width of a portion of the character image.

94. Computer-executable process steps according to claim 93, wherein a rectangle circumscribes the character image, the width of a portion of the character image corresponds to the width of the rectangle.

95. Computer-executable process steps according to claim 93, wherein the width of a portion of the character image corresponds to a width of a darkened portion of the character image.