Method and apparatus for segmenting a character and for extracting a character string based on a histogram

• US 5,581,633 A
• Filed: 10/26/1995
• Issued: 12/03/1996
• Est. Priority Date: 06/11/1993
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Naoi, Satoshi, Hotta, Yoshinobu
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/548,414
• Time in Patent Office: 404 Days
• Field of Search: 382/171, 382/174, 382/177, 382/178, 382/179, 382/292, 382/202, 382/206
• US Class Current: 382/171
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/158 using character size, text spacings or pitch estimation

Abstract

In a character segmenting apparatus the extracting section extracts the character segment pattern on the basis of the connection data imparted to the segment pattern. The character size calculating section calculates a histogram of a lengthwise or crosswise character size of a circumscribed rectangle circumscribed with the extracted character segment pattern and also calculates an average character size and its variance value on the basis of the histogram of the character size. The character pitch calculating section calculates a histogram of a pitch between the circumscribed rectangles and also calculates an average character pitch and its variance value on the basis of the histogram of the character pitch. The integrating section integrates the character while changing character integrating conditions in accordance with the average character size, the size variance value, the average character pitch and the pitch variance value. The segment integrating section integrates the character by distinguishing the small segment patterns in the character segment pattern on the basis of the average character size.

Claims

1. A character segmenting apparatus segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, each segment pattern comprising one of a pattern formed by one character and a small segment pattern formed by a part of one character, said character segmenting apparatus comprising:

extracting means for extracting the character segment pattern on the basis of the connection data;

character size calculating means for calculating a first histogram of one of a lengthwise character size and a crosswise character size of rectangles circumscribing the character segment pattern extracted by said extracting means and, concurrently, calculating an average character size and a first variance value of the average character size based on the first histogram;

character pitch calculating means for calculating a second histogram of a pitch between the rectangles in said character size calculating means and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

integrating means for integrating together the character segment patterns forming the one character while changing character integrating conditions in accordance with the average character size and the first variance value and the average character pitch and the second variance value; and

segment integrating means for integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size obtained by said character size calculating means.

2. The character segmenting apparatus according to claim 1, further comprising stroke extracting means for extracting a small separation stroke by which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern based on a result of obtaining one of an area ratio and a height ratio of the average character size to the character size of the rectangle by use of the average character size calculated by said character size calculating means.

3. The character segmenting apparatus according to claim 2, wherein said integrating means changes character integrating conditions in accordance with a value of an evaluation function comprising the average character size, the size variance value, the average character pitch and the pitch variance value when integrating the characters containing the small separation stroke.

4. The character segmenting apparatus according to claim 3, wherein said integrating means comprises certainty factor integrating means for calculating distances between the small separation stroke and patterns located on the right and left sides thereof and for performing an integration based on a distance ratio therebetween when a pitch width is less than or equal to a certain threshold value, and when a value of the evaluation function falls within a certain range.

5. A character segmenting apparatus segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, each segment pattern comprising one of a pattern formed by one character and a small segment pattern formed by a part of one character, said character segmenting apparatus comprising:

extracting means for extracting the character segment pattern on the basis of the connection data;

character size calculating means for calculating a first histogram of one of a lengthwise character size and a crosswise character size of rectangles circumscribing the character segment pattern extracted by said extracting means and, concurrently, calculating an average character size and a first variance value of the average character size based on the first histogram;

character pitch calculating means for calculating a second histogram of a pitch between the rectangles in said character size calculating means and, concurrently, calculating an average character pitch and a second variance value based on the second histogram, wherein said character size calculating means comprises;

size histogram means for calculating the first histograms of one of the lengthwise character size and the crosswise character size of the rectangle circumscribing the character segment pattern in the character string pattern,

first average size means for calculating a tentative average character size based on the first histograms in the character string calculated by said size histogram means,

size area determining means for determining a character size calculating area based on the tentative average character size calculated by said first average size means, and

second average size means for calculating an average character size in the character size area determined by said size area determining means;

integrating means for integrating together the character segment patterns forming the one character while changing character integrating conditions in accordance with the average character size and the first variance value and the average character pitch and the second variance value; and

segment integrating means for integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size obtained by said character size calculating means.

6. A character segmenting apparatus segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, each segment pattern comprising one of a pattern formed by one character and a small segment pattern formed by a part of one character, said character segmenting apparatus comprising:

extracting means for extracting the character segment pattern on the basis of the connection data;

character size calculating means for calculating a first histogram of one of a lengthwise character size and a crosswise character size of rectangles circumscribing the character segment pattern extracted by said extracting means and, concurrently, calculating an average character size and a first variance value of the average character size based on the first histogram;

character pitch calculating means for calculating a second histogram of a pitch between the rectangles in said character size calculating means and, concurrently, calculating an average character pitch and a second variance value based on the second histogram, wherein said character pitch calculating means comprises;

pitch histogram means for calculating, as a pitch, a distance between the rectangles with respect to the segment pattern other than the small separation stroke in calculating a pitch between the characters and, concurrently, calculating a histogram of the pitch,

first average pitch means for calculating a tentative average character pitch based on the histogram obtained by said pitch histogram means,

pitch area determining means for determining a character calculating area based on the tentative average character pitch obtained by said first average pitch means, and

second average pitch means for calculating an average character pitch in the character pitch area determined by said pitch area determining means;

integrating means for integrating together the character segment patterns forming the one character while changing character integrating conditions in accordance with the average character size and the first variance value and the average character pitch and the second variance value;

segment integrating means for integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size obtained by said character size calculating means; and

stroke extracting means for extracting a small separation stroke by which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern based on a result of obtaining one of an area ratio and a height ratio of the average character size to the character size of the rectangle by use of the average character size calculated by said character size calculating means.

7. A character segmenting apparatus segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, each segment pattern comprising one of a pattern formed by one character and a small segment pattern formed by a part of one character, said character segmenting apparatus comprising:

extracting means for extracting the character segment pattern on the basis of the connection data;

character size calculating means for calculating a first histogram of one of a lengthwise character size and a crosswise character size of rectangles circumscribing the character segment pattern extracted by said extracting means and, concurrently, calculating an average character size and a first variance value of the average character size based on the first histogram;

character pitch calculating means for calculating a second histogram of a pitch between the rectangles in said character size calculating means and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

integrating means for integrating together the character segment patterns forming the one character while changing character integrating conditions in accordance with the average character size and the first variance value and the average character pitch and the second variance value;

segment integrating means for integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size obtained by said character size calculating means; and

stroke extracting means for extracting a small separation stroke by which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern based on a result of obtaining one of an area ratio and a height ratio of the average character size to the character size of the rectangle by use of the average character size calculated by said character size calculating means, wherein said segment integrating means comprises;

line density means for calculating line densities with respect to the small separation stroke, the segment patterns located on the right and left sides thereof and also, in integrating them, a segment pattern;

inclination calculating means for calculating an inclination of the small separation stroke; and

distinguishing means for distinguishing which one of the segment patterns located on the right and left sides the small separation stroke should be integrated with based on the line densities obtained by said line density means and the inclination of the small separation stroke obtained by said inclination calculating means.

8. The character segmenting apparatus according to claim 7, wherein said line density means equally divides the rectangle of the segment pattern at equal intervals to 10 pieces in calculating the line density and takes a maximum value of the line densities counted from the 2nd line to the 8th line in the lines of the 10 pieces divided at the equal intervals.

9. The character segmenting apparatus according to claim 7, wherein said line density means calculates the line density of the segment pattern in a given one direction and next, when turned in other direction, calculates the line density, thus obtaining a total of the line densities in multi-directions.

10. The character segmenting apparatus according to claim 7, said inclination calculating means divides the segment pattern at equal intervals in a longer-size direction with respect to the lengthwise size and the crosswise size of the rectangle and calculates an inclination based on intersections between the segment pattern and respective line divided at the equal intervals.

11. The apparatus for segmenting a character according to claim 7, wherein said stroke extracting means extracts the small separation stroke and a pattern formed by a small written single character,

said line density calculating means calculates the small separation stroke and the pattern formed by the small written single character, determines as the small separation stroke, if calculated line densities are smaller than a predetermined value, and determines as the pattern formed by the small written single character, if calculated line densities are larger than predetermined value, said inclination calculating means calculates the inclination of the small separation stroke.

12. The apparatus for segmenting a character according to claim 11, wherein said distinguishing means integrates the small separation stroke into one of the segment patterns located on the right and left sides on the basis of an inclination of the small separation stroke calculated by said inclination calculating means and distances between the segment patterns located on the right and left sides of the small separation stroke.

13. A character string extracting apparatus extracting a character string based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, said apparatus comprising:

extracting means for extracting the character segment pattern based on the connection data;

weighting projection means for obtaining a projection histogram by performing a weighting projection on one of a lengthwise line segment and a crosswise line segment of a rectangle circumscribing the segment pattern extracted by said extracting means;

axis determining means for determining a character string axis based on the projection histogram obtained by said weighting projection means;

character string extracting means for extracting a character string based on the character string axis determined by said axis determining means;

rectangle integrating means for integrating, if the respective rectangles are overlapped with each other, overlapped rectangles;

calculating means for calculating an average character size with respect to a result of integration by said rectangle integrating means; and

eliminating means for eliminating, as a group of contact characters between upper-lower character strings, one of the rectangles that is not less than a predetermined-value-times as large as the average character size obtained by said calculating means and rectangles which spread over a plurality of character strings.

14. The character string extracting apparatus according to claim 13, further comprising:

calculating means for calculating an average character height with respect to the rectangle; and

eliminating means for eliminating, as a group of contact characters, the rectangles that are not less than a-predetermined-value-times as large as a size of the average character height obtained by said calculating means.

15. The character string extracting apparatus according to claim 13, further comprising:

eliminating means for eliminating, as a group of contact characters, the rectangles that a plurality of character string axes traverse,

wherein said weighting projection means sets, as peaks, the upper and lower ends of one of the lengthwise line segment and crosswise line segment of the rectangle of the segment pattern and obtains the projection histogram by effecting the weighting projection in accordance with a distance from the upper end and a distance from the lower end,

said axis determining means determining a central axis of the character string from a peak value of the upper end and a peak value of the lower end of the projection histogram obtained by said weighting projection means, and

said character string extracting means extracts the character string to which the pattern belongs on the basis of a distance between the central axis and the center of each rectangle of the rectangles exclusive of the group of contact characters extracted by said eliminating means.

16. The character string extracting apparatus according to claim 13, wherein said weighting projection means effects the weighting projection on the upper and lower ends of the circumscribed rectangle of the segment pattern,

said axis determining means determines a candidate position of the upper end and a candidate position of the lower end of the projection histogram obtained by said weighting projection means and also determines a central axis of the character string from the upper end candidate position and the lower end candidate position, and

said character string extracting means extracts the character string to which the pattern belongs on the basis of a distance between the central axis and the center of each circumscribed rectangle.

17. The character string extracting apparatus according to claim 13, wherein said weighting projection means obtains each projection of a first projection histogram by performing a first weighting projection such that a weighting value attenuates from one end of the rectangle toward the other end and a second projection histogram by performing a second weighting projection such that the weighting value attenuates from the other end toward one end and thus obtains each peak value of the first projection histogram and the second projection histogram and thus estimates a one-character central position and a one-character existing area from the respective peak values.

18. A character segmenting method of segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, and each segment pattern comprises one of a pattern formed by one character and a small segment pattern formed by a part of one character, said method comprising the steps of:

an extracting step of extracting the character segment pattern on the basis of the connection data;

a character size calculating step of calculating a first histogram of one of a lengthwise character size and a crosswise character size of a rectangle circumscribing the extracted character segment pattern and, concurrently, calculating an average character size and a first variance value based on the first histogram;

a character pitch calculating step of calculating second histogram of a pitch between the rectangles and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

an integrating step of integrating together the character segment patterns forming the character while changing character integrating conditions in accordance with the average character size, the first value, the average character pitch and the second variance value; and

a segment integrating step of integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size.

19. The character segmenting method according to claim 18, further comprising a stroke extracting step of extracting a small separation stroke which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern on the basis of a result of obtaining an area ratio or a height ratio of the average character size to the character size of the rectangle by use of the average character size.

20. The character segmenting method according to claim 19, wherein said integrating step comprises changing character integrating conditions in accordance with a value of an evaluation function comprising the average character size, the size variance value, the average character pitch and the pitch variance value when integrating the characters containing the small separation stroke.

21. The character segmenting method according to claim 20, wherein said integrating step includes a certainty factor integrating step of calculating distances between the extracted small separation stroke and patterns located on the right and left sides thereof and performing an integration on the basis of a distance ratio therebetween when a pitch width is less than or equal to a certain threshold value, and when the value of the evaluation function falls within a certain range.

22. A character segmenting method of segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, and each segment pattern comprises one of a pattern formed by one character and a small segment pattern formed by a part of one character, said method comprising the steps of:

an extracting step of extracting the character segment pattern on the basis of the connection data;

a character size calculating step of calculating a first histogram of one of a lengthwise character size and a crosswise character size of a rectangle circumscribing the extracted character segment pattern and, concurrently, calculating an average character size and a first variance value based on the first histogram, wherein said character size calculating step comprises;

a size histogram step of calculating the first histogram of one of the lengthwise character size and the crosswise character size of the rectangle,

a first average size step of calculating a tentative average character size based on the calculated histograms in the character string,

a size area determining step of determining a character size calculating area based on the calculated tentative average character size, and

a second average size step of calculating an average character size in the determined character size area;

a character pitch calculating step of calculating second histogram of a pitch between the rectangles and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

an integrating step of integrating together the character segment patterns forming the character while changing character integrating conditions in accordance with the average character size, the first value, the average character pitch and the second variance value; and

a segment integrating step of integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size.

23. A character segmenting method of segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, and each segment pattern comprises one of a pattern formed by one character and a small segment pattern formed by a part of one character, said method comprising the steps of:

an extracting step of extracting the character segment pattern on the basis of the connection data;

a character size calculating step of calculating a first histogram of one of a lengthwise character size and a crosswise character size of a rectangle circumscribing the extracted character segment pattern and, concurrently, calculating an average character size and a first variance value based on the first histogram;

a character pitch calculating. Step of calculating second histogram of a pitch between the rectangles and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

an integrating step of integrating together the character segment patterns forming the character while changing character integrating conditions in accordance with the average character size, the first value, the average character pitch and the second variance value;

a segment integrating step of integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size; and

a stroke extracting step of extracting a small separation stroke which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern on the basis of a result of obtaining an area ratio or a height ratio of the average character size to the character size of the rectangle by use of the average character size, wherein said character pitch calculating step comprises;

a pitch histogram step of calculating, as a pitch, a distance between the rectangles with respect to the segment pattern other than the small separation stroke when calculating a pitch between the characters and, calculating a histogram of the pitch,

a first average pitch step of calculating a tentative average character pitch on the basis of the histogram of the pitch,

a pitch area determining step of determining a character calculating area on the basis of the tentative average character pitch, and

a second average pitch step of calculating an average character pitch in the determined character pitch area.

24. A character segmenting method segmenting a character based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, and each segment pattern comprises one of a pattern formed by one character and a small segment pattern formed by a part of one character, said method comprising the steps of:

an extracting step of extracting the character segment pattern on the basis of the connection data;

a character size calculating step of calculating a first histogram of one of a lengthwise character size and a crosswise character size of a rectangle circumscribing the extracted character segment pattern and, concurrently, calculating an average character size and a first variance value based on the first histogram;

a character pitch calculating step of calculating second histogram of a pitch between the rectangles and, concurrently, calculating an average character pitch and a second variance value based on the second histogram;

an integrating step of integrating together the character segment patterns forming the character while changing character integrating conditions in accordance with the average character size, the first value, the average character pitch and the second variance value;

a segment integrating step of integrating the small segment pattern by distinguishing the small segment pattern in the character segment pattern based on the average character size; and

a stroke extracting step of extracting a small separation stroke which a pattern being integrated to one character is separated in the small segment pattern from within the segment pattern in the character string pattern on the basis of a result of obtaining an area ratio or a height ratio of the average character size to the character size of the rectangle by use of the average character size, wherein said segment integrating step comprises;

a line density step of calculating line densities with respect to the extracted small separation stroke, the segment patterns located on the right and left sides thereof and also, in integrating them, a segment pattern;

an inclination calculating step of calculating an inclination of the small separation stroke; and

a distinguishing step of distinguishing which one of the segment patterns located on the right and left sides the small separation stroke should be integrated with on the basis of the line densities and an inclination of the small separation stroke.

25. The character segmenting method according to claim 24, wherein said line density step comprises equally dividing the rectangle of the segment pattern into equal intervals to 10 pieces in calculating the line density and taking a maximum value of the line densities counted from the 2nd line to the 8th line in the lines of the 10 pieces divided at the equal intervals.

26. The character segmenting method according to claim 24, wherein said inclination calculating step comprises dividing the segment pattern at equal intervals in a longer-size direction with respect to the lengthwise size and the crosswise size of the rectangle and calculating an inclination on the basis of intersections between the segment pattern and respective line divided at the equal intervals.

27. The character segmenting method according to claim 24, wherein said inclination calculating step comprises dividing the segment pattern at equal intervals in a longer-size direction with respect to the lengthwise size and the crosswise size of the rectangle and calculating an inclination on the basis of intersections between the segment pattern and respective line divided at the equal intervals.

28. A character string extracting method of extracting a character string based on connection data imparted to each segment pattern, and in which a character string pattern is formed by arranging a plurality of character segment patterns, said method comprising the steps of:

an extracting step of extracting the character segment pattern based on the connection data;

a weighting projection step of obtaining a projection histogram by performing a weighting projection on one of a lengthwise line segment and a crosswise line segment of a rectangle circumscribing the extracted segment pattern;

an axis determining step of determining a character string axis based on the projection histogram;

a character string extracting step of extracting a character string based on the character string axis determined in said axis determining step;

a rectangle integrating step of integrating, if the respective rectangles are overlapped with each other, overlapped rectangles;

a calculating step of calculating an average character size with respect to a result of integration by said rectangle integrating step; and

an eliminating step of eliminating, as a group of contact characters between upper-lower character strings, one of the rectangles that is not less than a predetermined-value-times as large as the average character size obtained by said calculating step and rectangles which spread over a plurality of character strings.

29. The character string extracting method according to claim 28, wherein said weighting projection step comprises effecting the weighting projection in accordance with a distance from a center of the line segment by centering a peak on one of the lengthwise line segment and the crosswise line segment of the rectangle of the segment pattern,

said axis determining step comprises extracting a character string to which the pattern belongs based on the central axis and a distance from the center of each rectangle.

30. The character string extracting method according to claim 28, further comprising:

a calculating step of calculating an average character height with respect to the rectangle; and

an eliminating step of eliminating, as a group of contact characters, the rectangles that are not less than a-predetermined-value-times as large as a size of the average character height.

31. The character string extracting method according to claim 28, further comprising:

an eliminating step of eliminating, as a group of contact characters, the rectangles that a plurality of character string axes traverse,

wherein said weighting projection step comprises setting, as peaks, the upper and lower ends of one of the lengthwise line segments and the crosswise line segment of the rectangle of the segment pattern and effecting the weighting projection in accordance with a distance from the upper end and a distance from the lower end,

said axis determining step comprises determining a central axis of the character string from a peak value of the upper end and a peak value of the lower end of the projection histogram, and

said character string extracting step comprises extracting the character string to which the pattern belongs based on a distance between the central axis and the center of each rectangle of the rectangles exclusive of the group of contact characters extracted by said eliminating step.

32. The character string extracting method according to claim 28, wherein said weighting projection step comprises effecting the weighting projection on the upper and lower ends of the rectangle of the segment pattern,

said axis determining step comprises determining a candidate position of the upper end and a candidate position of the lower end of the projection histogram and also determining a central axis of the character string from the upper end candidate position and the lower end candidate position, and

said character string extracting step comprises extracting the character string to which the pattern belongs based on a distance between the central axis and the center of each rectangle.

33. The character string extracting method according to claim 28, wherein said weighting projection step comprises obtaining each peak of the projection histogram by performing such a weighting projection that a weighting value attenuates from one end of the rectangle toward the other end and such a weighting projection that the weighting value attenuates from the other end toward one end and thus estimating a one-character central position and a one-character existing area from the respective peak values.