SEGMENTATION OF A WORD BITMAP INTO INDIVIDUAL CHARACTERS OR GLYPHS DURING AN OCR PROCESS

• US 20110274354A1
• Filed: 05/10/2010
• Published: 11/10/2011
• Est. Priority Date: 05/10/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nijemcevic, Djordje
• Granted Patent: US 8,571,270 B2
• Time in Patent Office: Days
• US Class Current: 382/177
• 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

An image processing apparatus is provided that includes a character chopper component that segments words into individual characters in a bitmap of a textual image undergoing an OCR process. The Character chopper component is configured to produce a set of (possibly curved) chop-lines which divide a bitmap of any given word into its individual character or glyph candidates. Cases where an input bitmap contains two separate words are handled by marking a place where those words should be split. The character segmentation algorithm computes the set of vertically oriented, curved chop-lines by considering glyph and background colors in a given word bitmap. The set is filtered afterwards using various heuristics, in order to preserve those lines that indeed do separate a word'"'"'s glyphs and minimize the number of those that do not.

Claims

1. An apparatus that generates characters or glyphs from a bitmap of text, comprising:

an input component for receiving a bitmap of an image comprising at least one textual line that is identified by a base-line and a mean-line;

a character chopper component that includes a candidate chop line generator component for generating a plurality of chop lines that each separate a pair of adjacent characters or glyphs in the textual line, wherein the candidate chop line generator component is configured to produce a candidate chop line through each pixel in at least one row extending along and within the textual line, said character chopper component further including a chop line selection component for selecting a subset of the candidate chop lines that correspond to the plurality of chop lines that each separate a pair of adjacent characters or glyphs in the textual line; and

an output component that applies the chop line to the textual line to produce the characters or glyphs.

2. The apparatus of claim 1 wherein the candidate chop line generator component generates candidate chop lines that each maximize a fitness function that increases as a total path lightness of the respective candidate chop lines increases and decreases as an intersection number increases, wherein the intersection number denotes a number of white-to-black and black to white transitions that the respective candidate chop line crosses.

3. The apparatus of claim 1 wherein the candidate chop line component extends each of the character chop lines for additional pixel rows extending along and within the textual line while continuing to maximize each character chop line.

4. The apparatus of claim 3 wherein the additional pixel rows include all pixel rows within the textual line.

5. The apparatus of claim 1 wherein the at least one row is a central row halfway between a base line and a mean line of the textual line and the character chopper component is configured to separately produce candidate chop half-lines above and below the central row which are subsequently joined together.

6. The apparatus of claim 1 wherein the character chop line generator component generates a confidence measure associated with each chop line which reflects how accurately the chop line separates a character or glyph.

7. The apparatus of claim 6 wherein the confidence measure depends on a product of a scaled path lightness and the intersection number, wherein the scaled path lightness is assigned a value of zero for path lightness values below a threshold level.

8. The apparatus of claim 1 wherein the chop line selection component selects the subset of candidate chop lines by:

assigning each of the candidate chop lines to a plurality of groups, wherein the candidate chop lines in each group are all within a threshold logical distance from one another, said logical distance between two candidate chop lines being proportional to a sum of inverted pixel values lying between the two candidate chop lines;

selecting a candidate chop line from each group that has a maximum confidence measure;

eliminating any of the selected candidate chop lines if their confidence measure is below a threshold level to thereby provide a first set of candidate chop lines; and

comparing pairs of candidate chop lines in the first set candidate chop lines and eliminating a first member of the pair if its confidence measure is less than a confidence measure of a second member of the pair and if a product of the confidence measure of the second member and a decreasing function of the logical distance between the first and second members is greater than the confidence measure of the second member to thereby provide a second set of candidate chop lines which are designated to be the subset of the candidate chop lines that correspond to the plurality of chop lines.

9. The apparatus of claim 8 wherein the logical distance between two candidate chop lines is proportional to a weighted sum of the inverted pixel values lying between the two candidate chop lines, wherein inverted pixel values of pixels closer to a central line through the textual line are weighted more than inverted pixel values of pixels more remote from the central line toward either the mean-line or the base-line.

10. The apparatus of claim 8 wherein the chop line selection component eliminates selected candidate chop lines that do not overlap any background regions of the image that do not contain text and for which there are no additional candidate chop lines within a specified distance of the of the selected candidate chop lines such that the additional candidate chop lines do not overlap any background regions of the image that do not contain text.

11. The apparatus of claim 1 wherein the character chopper component includes a first pre-processing component for detecting adjacent glyphs or characters that are in contact with one another such that they share a vertical portion of text, said detection component being configured to identify top and bottom contours defined by y-coordinates of non-background pixels in top and bottom rows of the image and detect a local minima in the top contour and a local maxima in the bottom contour having a common x-coordinate, said character detection component being further configured to lighten a value of pixels located on a vertical line connecting the local minima to the local maxima.

12. The apparatus of claim 11 wherein the character chopper component includes a second pre-processing component that detects italicized characters in the textual line based on a measure of oscillations in a sum of pixel values in columns of the image.

13. A method for segmenting words in a bitmap of an image into characters or glyphs, comprising:

receiving a bitmap of an image comprising at least one textual line that is identified by a base-line and a mean-line;

generating a plurality of chop lines that each separate a pair of adjacent characters or glyphs in the textual line by producing a candidate chop line through each pixel in at least one row extending along and within the textual line; and

selecting a subset of the candidate chop lines that correspond to the plurality of chop lines that each separate a pair of adjacent characters or glyphs in the textual line.

14. The method of claim 13 wherein generating the plurality of chop lines includes generating the candidate chop lines so that they each maximize a fitness function that increases as a total path lightness of the respective candidate chop lines increases and decreases as an intersection number increases, wherein the intersection number denotes a number of white-to-black and black to white transitions that the respective candidate chop line crosses.

15. The method of claim 13 further comprising extending each of the character chop lines for each pixel row extending along and within the textual line while continuing to maximize each character chop line.

16. The method of claim 13 wherein the at least one row is a central row halfway between a base line and a mean line of the textual line and the character chopper component is configured to separately produce candidate chop half-lines above and below the central row which are subsequently joined together.

17. The method of claim 13 further comprising generating a confidence measure associated with each chop line which reflects how accurately the chop line separates a character or glyph, the confidence measure depending on a product of a scaled path lightness and the intersection number, wherein the scaled path lightness is assigned a value of zero for path lightness values below a threshold level.

18. A medium comprising instructions executable by a computing system, wherein the instructions configure the computing system to perform a method for segmenting words in a bitmap of an image into characters or glyphs, comprising:

receiving a bitmap of an image comprising at least one textual line that is identified by a base-line and a mean-line;

generating a plurality of candidate chop lines that each maximize a fitness function that increases as a total path lightness of the respective candidate chop lines increase and decreases as an intersection number increases, wherein the intersection number denotes a number of white-to-black and black to white transitions that the respective candidate chop line crosses; and

selecting at least one chop line from among the candidate chop lines, wherein the chop line separates a pair of adjacent characters or glyphs in the textual line.

19. The medium of claim 18 wherein each of the candidate chop lines pass through a different pixel in at least one row extending along and within the textual line.

20. The medium of claim 18 wherein the at least one chop line includes:

assigning each of the candidate chop lines to a plurality of groups, wherein the candidate chop lines in each group are all within a threshold logical distance from one another, said logical distance between two candidate chop lines being proportional to a sum of inverted pixel values lying between the two candidate chop lines;

selecting a candidate chop line from each group that has a maximum confidence measure;

eliminating any of the selected candidate chop lines if their confidence measure is below a threshold level to thereby provide a first set of candidate chop lines; and

comparing pairs of candidate chop lines in the first set candidate chop lines and eliminating a first member of the pair if its confidence measure is less than a confidence measure of a second member of the pair and if a product of the confidence measure of the second member and a decreasing function of the logical distance between the first and second members is greater than the confidence measure of the second member to thereby provide a second set of candidate chop lines which are designated to be the subset of the candidate chop lines that correspond to the at least one chop line.