Method and structure for separating joined patterns for use in pattern and character recognition system

• US 5,046,114 A
• Filed: 10/01/1985
• Issued: 09/03/1991
• Est. Priority Date: 10/01/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp.
• Inventors: Zobel, David H.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/782,744
• Time in Patent Office: 2,163 Days
• Field of Search: 382/9, 382/18, 382/22, 382/48
• US Class Current: 382/171
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques

Abstract

A method and structure is provided which allows for a plurality of patterns or characters which are joined to be separated for further processing. For characters which are determined not to have a fixed pitch, a first approximation cleavage point is determined based on the width of the segment. Next, a caliper histogram is formed plotting the distance between the uppermost and bottommost "on" pixel in each column of the segment. If a satisfactory minimum in the caliper histogram is found, this segment is cleaved into left and right segments at this point. It not, a raw histogram, indicating the total number of "on" pixels in each column of the segment, is formed. If an adequate minimum of the raw histogram is found, the segment is cleaved into right and left segments at this point. In one embodiment of this invention, the caliper histogram operation is not performed if it is determined that the segment includes top and bottom serifs. Characters determined to be of fixed pitch are separated if a suitable minimum is found in the raw histogram of the segment and, if not, if a satisfactory minimum is found in the caliper histogram for the segment. In one embodiment of this invention, two adjacent segments are compared and, if necessary, joined to form a single segment. This allows separate segments which in fact form a single pattern or character to be combined into a single segment representing that pattern or character for a more accurate analysis.

Claims

1. A method for separating a data segment representing an array of pixels having a plurality of rows and columns into a plurality of segments comprising the steps of:

fetching a data segment;

creating a first histogram selected from the group of histograms consisting of a caliper histogram indicating the distance between the topmost and bottommost "on" pixels for a plurality of columns of said array of pixels and a raw histogram indicating the number of "on" pixels in a plurality of columns of said array of pixels;

determining if a satisfactory minimum of said first histogram exists;

if a satisfactory minimum of said first histogram does not exist, creating a second histogram of a type other than said first histogram, said second histogram selected from said group of histograms consisting of a caliper histogram and a raw histogram, and determining if a satisfactory minimum of said second histogram exists; and

cleaving said data segment about said satisfactory minimum of said first histogram or said satisfactory minimum of said second histogram, thereby forming a left segment and a right segment.

2. The method as in claim 1 wherein said caliper histogram is created for all said columns of said array of pixels.

3. The method as in claim 1 wherein said caliper histogram is created which does not include data associated with columns located near the edge of said array of pixels.

4. The method as in claim 1 wherein said caliper histogram is created which includes data associated with columns located within a selected number of columns from a first approximation cleavage point.

5. The method as in claim 4 wherein said first approximation cleavage point is the horizontal center of said array of pixels.

6. The method as in claim 4 wherein said first approximation cleavage point is located a selected distance from a selected horizontal edge of said array of pixels equal to the average width of one or more of said single patterns.

7. The method as in claim 4 wherein said single patterns are characters and said first approximation point is located a selected distance from a selected horizontal edge of said array of pixels equal to value selected from the set of values consisting of average character pitch and average character width.

8. The method as in claim 6 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

9. The method as in claim 7 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

10. The method as in claim 1 wherein said satisfactory minimum of said caliper histogram must be no greater than a selected fraction of the height of said array of pixels.

11. The method as in claim 10 wherein said selected fraction is selected from the group of fractions consisting of 13/16 and 15/16.

12. The method as in claim 1 wherein said satisfactory minimum of said caliper histogram must be no greater than a selected fraction of the greatest vertical distance between the topmost and bottommost "on" pixel in said array of pixels.

13. The method as in claim 12 wherein said selected fraction is selected from the group of fractions consisting of 13/16, 1/8, and 15/16.

14. The method as in claim 1 wherein said raw histogram is created for all said columns of said array of pixels.

15. The method as in claim 1, wherein said raw histogram is created which does not include data associated with columns located near the edge of said array of pixels.

16. The method as in claim 1 wherein said raw histogram is created which includes data associated with columns located within a selected number of columns from a first approximation cleavage point.

17. The method as in claim 16 wherein said first approximation point is the horizontal center of said array of pixels.

18. The method as in claim 16 wherein said first approximation point is located a selected distance from a selected horizontal edge of said array of pixels equal to the average width of one or more of said single patterns.

19. The method as in claim 16 wherein said single patterns are characters and said first approximation point is located a selected distance from a selected horizontal edge of said array of pixels equal to a value selected from the set of values consisting of average character pitch and average character width.

20. The method as in claim 18 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

21. The method as in claim 19 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

22. The method as in claim 1 wherein said satisfactory minimum of said raw histogram must be no greater than a selected fraction of the height of said array of pixels.

23. The method as in claim 22 wherein said selected fraction is selected from the group of fractions consisting of 1/8 and 1/10.

24. The method as in claim 1 wherein said satisfactory minimum of said raw histogram must be no greater than a selected fraction of the vertical distance between the topmost and bottommost "on" pixels in said array of pixels.

25. The method as in claim 24 wherein said selected fraction is selected from the group of fractions consisting of 1/8 and 1/10.

26. The method as in claim 1 wherein said single patterns are characters and said caliper histogram is not created if said segment contains serifs.

27. The method as in claim 26 wherein said caliper histogram is not created if said array of pixels contains a string of columns of a selected width having an "on" pixel in one or more of a selected number of uppermost rows of said array of pixels and a string of columns of said selected width having an "on pixel" in one or more of said selected number of bottommost rows of said array of pixels.

28. The method as in claim 27 wherein said selected width is equal to a selected fraction of the number of columns in said array of pixels.

29. The method as in claim 28 wherein said selected fraction is 5/8.

30. The method as in claim 27 wherein said selected width is equal to a selected fraction of the greatest horizontal distance between the leftmost and the rightmost "on" pixel in the rows of said array of pixels.

31. The method as in claim 30 wherein said selected fraction is 5/8.

32. The method as in claim 27 wherein said selected number of uppermost rows and bottommost rows is equal to a selected fraction of the number of rows of said array of pixels.

33. The method as in claim 32 wherein said selected fraction is 5/32.

34. The method as in claim 27 wherein said selected number of uppermost rows and bottommost rows is equal to a selected fraction of the greatest distance between the uppermost and bottommost "on" pixels of said array of pixels.

35. The method as in claim 34 wherein said selected fraction is 5/32.

36. The method as in claim 1 wherein said data segment is formed by combining two segments prior to creating said first histogram.

37. A method for separating a data segment representing an array of pixels having a plurality of rows and columns into a plurality of segments comprising the steps of:

fetching a data segment;

creating a caliper histogram indicating the distance between the topmost and bottommost "on" pixels for a plurality of columns of said array of pixels;

determining if a satisfactory minimum of said caliper histogram exists; and

cleaving said data segment about said satisfactory minimum of said caliper histogram, thereby forming a left segment and a right segment.

38. The method as in claim 37 wherein said caliper histogram is created for all said columns of said array of pixels.

39. The method as in claim 37 wherein said caliper histogram is created which does not include data associated with columns located near the edge of said array of pixels.

40. The method as in claim 37 wherein said caliper histogram is created which includes data associated with columns located within a selected number of columns from a first approximation cleavage point.

41. The method as in claim 40 wherein said first approximation cleavage point is the horizontal center of said array of pixels.

42. The method as in claim 40 wherein said first approximation cleavage point is located a selected distance from a selected horizontal edge of said array of pixels equal to the average width of one or more of said single patterns.

43. The method as in claim 40 wherein said single patterns are characters and said first approximation point is located a selected distance from a selected horizontal edge of said array of pixels equal to value selected from the set of values consisting of average character pitch and average character width.

44. The method as in claim 42 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

45. The method as in claim 43 wherein said selected number of columns is equal to one fourth the number of columns in said array of pixels.

46. The method as in claim 37 wherein said satisfactory minimum of said caliper histogram must be no greater than a selected fraction of the height of said array of pixels.

47. The method as in claim 46 wherein said selected fraction is selected from the group of fractions consisting of 13/16 and 15/16.

48. The method as in claim 37 wherein said satisfactory minimum of said caliper histogram must be no greater than a selected fraction of the greatest vertical distance between the topmost and bottommost "on" pixel in said array of pixels.

49. The method as in claim 48 wherein said selected fraction is selected from the group of fractions consisting of 13/16, 1/8, and 15/16.

50. The method as in claim 37 wherein said data segment is formed by combining two segments prior to creating said histogram.