Method and apparatus for identifying and/or removing combs from scanned images
Methods and apparatus for detecting the presence of combs, determining their shape and removing the combs from a scanned form in an automated manner are described. Horizontal and vertical line feature analysis is combined with knowledge of the usual size, shape, and spacing characteristics of lines which form a comb. Vertical and horizontal lines failing to meet certain characteristics, e.g., size or shape characteristics, are eliminated from consideration. Vertical lines which do not intersect a horizontal line are also eliminated from consideration. Confidence measures for different possible comb shapes are generated and the most probable comb shapes as indicated by the confidence measures are included in a comb list. The comb list may be output for use in further processing, e.g., comb removal and/or data extraction processing.
1. A method of processing an image to detect combs in the image, the method comprising:
operating a processor to analyze at least some vertical lines in said image to detect periodicity of at least some sets of vertical lines included in said image;
determining a plurality of possible comb vertical line spacings from the detected periodicity of different ones of said at least some sets of vertical lines;
generating confidence levels, for at least some of said determined possible comb vertical line spacings, said confidence level being indicative of the probability that the determined possible comb vertical line spacing corresponds to a comb included in said image; and
generating a list of comb shapes based on the generated confidence levels.
2. The method of claim 1 , further comprising:
prior to analyzing said at least some vertical lines, processing a list of lines to identify horizontal lines which may be part of a comb.
3. The method of claim 2 , wherein said horizontal lines which may be part of a comb include lines which are longer than a threshold minimum length and excludes horizontal lines which are shorter than said threshold minimum length.
4. The method of claim 3 , further comprising:
prior to analyzing at least some vertical lines, identifying vertical lines in said image which may be part of a comb, said step of identifying vertical lines which may be part of a comb including:
discarding from consideration vertical lines which do not touch a horizontal line; and
selecting, as identified vertical lines, one or more vertical lines which exceed a minimum vertical line length and touch at least one horizontal line, said at least some vertical lines being a selected vertical lines.
5. The method of claim 4 , further comprising:
filtering the list of comb shapes based on the generated confidence levels to remove at least some combs shapes which overlap other comb shapes in said generated list of comb shapes.
6. The method of claim 5 , further comprising:
outputting the filtered list of comb shapes.
7. The method of claim 6 , further comprising:
limiting the filtered list of comb shapes to a predetermined number of combs shapes which are determined to have the highest confidence levels.
8. An apparatus for processing an image to detect combs in the image, the apparatus comprising:
a memory for storing image data representing said image;
a vertical line analysis module for analyzing at least some vertical lines in said image to detect periodicity of at least some sets of vertical lines included in said image;
a comb vertical line spacing determination module for determining a plurality of possible comb vertical line spacings from the detected periodicity of different ones of said at least some sets of vertical lines;
a confidence level generation module for generating confidence levels, for at least some of said determined possible comb vertical line spacings, said confidence level being indicative of the probability that the determined possible comb vertical line spacing corresponds to a comb included in said image; and
a comb shape module for generating a list of comb shapes based on the generated confidence levels.
9. The apparatus of claim 8 , further comprising:
a horizontal line comb candidate determination module for processing a list of lines to identify horizontal lines which may be part of a comb.
10. The apparatus of claim 9 , wherein said horizontal lines which may be part of a comb include lines which are longer than a threshold minimum length and excludes horizontal lines which are shorter than said threshold minimum length, the apparatus further comprising:
stored line evaluation threshold criteria.
11. The apparatus of claim 10 , further comprising:
a vertical line comb candidate identification module for identifying vertical lines in said image which may be part of a comb.
12. The apparatus of claim 11 , wherein said vertical line comb candidate identification module further comprises:
a vertical line discard module for discarding from consideration vertical lines which do not touch a horizontal line; and
a vertical line selection module for selecting, as identified vertical lines, one or more vertical lines which exceed a minimum vertical line length and touch at least one horizontal line, said at least some vertical lines being a selected vertical lines.
13. The apparatus of claim 11 , further comprising:
a comb filtering module for filtering the list of comb shapes based on the generated confidence levels to remove at least some combs shapes which overlap other comb shapes in said generated list of comb shapes.
14. The apparatus of claim 13 , further comprising:
an output module for outputting the filtered list of comb shapes.
15. The apparatus of claim 14 , further comprising:
stored information used for limiting the filtered list of comb shapes to a predetermined number of combs shapes which are determined to have the highest confidence levels.
16. The apparatus of claim 14 , further comprising:
a comb removal module for removing detected combs from an image being processed.