Identification, characterization, and segmentation of Halftone or stippled regions of binary images by growing a seed to a clipping mask

• US 5,131,049 A
• Filed: 12/08/1989
• Issued: 07/14/1992
• Est. Priority Date: 12/08/1989
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Crocca, William T., Bloomberg, Dan S.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Stellrecht, Barry
• Application Number:
  US07/448,193
• Time in Patent Office: 949 Days
• Field of Search: 358/447, 358/448, 358/453, 358/455, 358/456, 358/457, 358/458, 358/461, 358/463, 358/462, 358/452, 358/454, 358/464, 358/465, 358/466, 382/54, 382/31, 382/27, 382/28, 382/55, 382/9
• US Class Current: 382/257
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/155 Removing patterns interfering with the pattern to be recognised, such as ruled lines or underlines
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

A method for creating a mask for separating halftone regions in a binary image from other regions comprises: constructing a seed image that includes pixels only in halftone regions and at least one pixel in every halftone region (67); constructing a clipping mask that covers in a connected manner all ON pixels in halftone regions (70); and filling the seed while clipping to the mask (72). Thresholded reductions and morphological operations are preferred.

Claims

1. A method performed in a digital processor for identifying and processing halftone regions in a binary input image, comprising the steps of:

determining whether halftone regions exist in the input image; and

only if halftone regions exist, constructing a representation of a separation mask by performing the substeps of

constructing a seed,

constructing a clipping mask, and

growing the seed and clipping the seed, thus grown, to the clipping mask.

6. The method of claim 1 or 2 or 4 or 5 wherein said steps of growing and clipping comprise:

(a) on a first pass, copying the seed to define a current version;

(b) dilating the current version;

(c) ANDing the clipping mask and the current version to define an iterated version;

(d) comparing the copy of the current version with the iterated version; and

(e) only if they are unequal, copying the iterated version to redefine the current version and repeating steps (b) through (d).

7. The method of claim 1 or 2 or 4 or 5 wherein said step of constructing a clipping mask comprises subjecting the image to a set of operations that eliminates OFF pixels that are near ON pixels.

8. The method of claim 7 wherein said set of operations includes at least one thresholded reduction to solidify textured areas.

9. The method of claim 1 or 2 or 4 or 5, and further comprising the step of logically combining the separation mask and the original binary image to extract image separations.

10. The method of claim 1 or 2 or 4 or 5, and further comprising the steps of:

providing a set of spatial filters, each of which corresponds to a particular respective set of halftone characteristics;

selecting at least a portion of the original binary image, called the selected portion;

applying each of the spatial filters to the selected portion to provide a respective indication of the extent to which the selected portion exhibits the respective set of halftone characteristics; and

selecting the spatial filter that provides the greatest indication.

11. The method of claim 10 wherein said step of constructing a seed comprises:

eroding the input image with the selected spatial filter;

subjecting the image, thus eroded, to at least one thresholded reduction to provide a resulting image; and

subjecting the resulting image to an open operation.

12. The method of claim 10 wherein each of the filters is a hit-miss structuring element having a pattern of five ON pixels located at the center and corners of a square and four OFF pixels located generally midway between the center and corners of the square.

13. The method of claim 1 or 2 or 4 or 5 wherein said step of constructing a clipping mask comprises at least one thresholded reduction to solidify textured areas.

14. The method of claim 1 or 2 or 4 or 5, and further comprising the step of determining the halftone characteristics.

15. The method of claim 14 wherein said step of determining the halftone characteristics comprises the steps of:

providing a set of narrow bandpass filters, each of which corresponds to a particular respective set of halftone characteristics;

eroding at least a portion of the image with each of the filters;

counting the ON pixels for each erosion; and

choosing the filter that gives the largest number.

16. The method of claim 15 wherein each of the filters is a hit-miss structuring element having a pattern of five ON pixels located at the center and corners of a square and four OFF pixels located generally midway between the center and corners of the square.

17. The method of claim 1 wherein said step of determining whether halftone regions exist comprises the steps of:

dividing the input image into subregions;

determining the approximate number of pixel transitions in each subregion;

picking the subregion with the greatest number of pixel transitions; and

comparing that number to a threshold, above which a subregion is considered to be largely halftoned.

18. The method of claim 17 wherein said step of determining the approximate number of pixel transitions comprises the steps of:

duplicating the subregion so that there are first and second copies of the subregion;

eroding one copy of the subregion with a horizontal SE of adjacent ON pixels;

XORing the copy of the subregion, thus eroded, with the other copy of the subregion; and

counting ON pixels remaining.

19. The method of claim 17 or 4, and further comprising the steps of:

providing a set of narrow bandpass filters;

eroding the subregion with the greatest number of pixel transitions with each of these filters;

counting the ON pixels for each erosion; and

choosing the filter that gives the largest number.

20. The method of claim 19 wherein each of the filters is a hit-miss structuring element having a pattern of five ON pixels located at the center and corners of a square and four OFF pixels located generally midway between the center and corners of the square.

21. The method of claim 1 or 4 or 5 wherein said step of constructing a seed comprises the steps of:

providing a set of spatial filters, each of which corresponds to a particular respective set of halftone characteristics;

selecting at least a portion of the input image;

applying each of the spatial filters to the selected portion to provide a respective indication of the extent to which the selected portion exhibits the respective set of halftone characteristics;

selecting the spatial filter that provides the greatest indication;

eroding the input image with the selected spatial filter;

subjecting the image, thus eroded, to at least one thresholded reduction to provide a resulting image; and

subjecting the resulting image to an open operation.

22. The method of claim 21 wherein each of the filters is a hit-miss structuring element having a pattern of five ON pixels located at the center and corners of square and four OFF pixels located generally midway between the center and corners of the square.

23. The method of claim 1 or 4 or 5 wherein said step of constructing a seed comprises the steps of:

subjecting the input image to at least one thresholded reduction at a low threshold value to provide a resulting image;

subjecting the resulting image to at least one thresholded reduction at a high threshold level to provide a further resulting image; and

subjecting the further resulting image to an open operation.

24. The method of claim 1 or 5 wherein said step of determining whether halftone regions exist comprises the steps of:

dividing the image into subregions;

determining the approximate number of pixel transitions in each subregion;

picking the subregion with the greatest number; and

comparing that number to a threshold, above which a subregion is considered to be largely halftoned.

25. The method of claim 24 wherein said step of determining the approximate number of pixel transitions comprises the steps of:

duplicating the subregion so that there are first and second copies of the subregion;

eroding one copy of the subregion with a horizontal SE of adjacent ON pixels;

XORing the copy of the subregion, thus eroded, with the other copy of the subregion; and

counting ON pixels remaining.

2. A method performed in a digital processor for processing halftone regions in an original binary image, comprising the steps of:

subjecting the input image to at least one thresholded reduction at a low threshold value to provide a resulting image;

subjecting the resulting image to at least one thresholded reduction at a high threshold level to provide a further resulting image;

subjecting the further resulting image to an open operation to provide a seed;

constructing a clipping mask; and

growing the seed and clipping the seed, thus grown, to the clipping mask.

3. A method performed in a digital processor for processing halftone regions in binary input image, comprising the steps of:

constructing a seed;

constructing a clipping mask; and

growing the seed and clipping the seed, thus grown, to the clipping mask;

wherein said step of constructing a clipping mask comprises subjecting the image to a set of operations that eliminates OFF pixels that are near ON pixels, said set of operations including at least one thresholded reduction to solidify textured areas.

4. A method performed in a digital processor for processing halftone regions in a binary input image, comprising the steps of:

processing the input image to construct a seed image, the seed image having the property that it contains pixels only in the halftone regions and that it contains at least one pixel in every halftone region;

processing the input image to form a clipping mask, the clipping mask having the property that it covers all ON pixels in the halftone regions and that any part of the clipping mask that covers a non-halftone region does not touch a part of the clipping mask that covers a halftone region; and

processing the seed image and the clipping mask so as to grow the seed and clip the seed, thus grown, to the clipping mask;

whereby the seed, thus grown and clipped, provides a representation of a separation mask.

5. A method performed in a digital processor for processing halftone regions in a binary input image, comprising the steps of:

determining whether halftone regions exist in the input image; and

only if halftone regions exist, constructing a representation of a separation mask by performing the substeps of

processing the input image to construct a seed image, the seed image having the property that it contains pixels only in the halftone regions and that it contains at least one pixel in every halftone region,

processing the input image to form a clipping mask, the clipping mask having the property that it covers all ON pixels in the halftone regions and that any part of the clipping mask that covers a non-halftone region does not touch a part of the clipping mask that covers a halftone region, and

processing the seed image and the clipping mask so as to grow the seed and clip the seed, thus grown, to the clipping mask.