Method and apparatus identifying halftone regions within a digital image

• US 20070165281A1
• Filed: 06/02/2006
• Published: 07/19/2007
• Est. Priority Date: 01/13/2006
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Agrawal, Ram
• Granted Patent: US 7,702,154 B2
• Time in Patent Office: Days
• US Class Current: 358/3.30
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

One embodiment of the present invention provides a system that identifies halftone regions within a digital image. During operation, the system receives a region from the digital image, wherein the digital image is a bi-level image, wherein each pixel has two possible color values. Next, the system computes a variation index for a region of the digital image, wherein the variation index indicates how frequently adjacent pixel values in the region differ. If the variation index for the region is greater than an upper threshold, the system determines that the region is a halftone region.

Claims

1. A method for identifying halftone regions within a digital image, comprising:

receiving a region from the digital image, wherein the digital image is a bi-level image, wherein each pixel has two possible color values;

computing a variation index for a region of the digital image, wherein the variation index indicates how frequently adjacent pixel values in the region differ; and

if the variation index for the region is greater than an upper threshold, determining that the region is a halftone region.

2. The method of claim 1, wherein if the variation index for the region is smaller than a lower threshold, the method further comprises:

testing to determine there exist black patches in the region;

if not, determining that the region is a symbol region containing text and/or symbols; and

if so, determining that the region is a generic region which is neither a halftone region nor a symbol region.

3. The method for claim 2, wherein if the variation index for the region is between the lower threshold and the upper threshold, the method further comprises:

testing to determine whether there exist black patches in the region;

if so,

testing to determine if the variation index is greater than a middle threshold,

if so, determining that the region is a halftone region,

if not, determining that the region is a generic region; and

if no black patches exist in the region,

performing a morphological erosion on the region,

computing a new variation index for the eroded region, and

if the new variation index is greater than a post-erosion threshold, determining that the region is a halftone region,

otherwise, determining that the region is a generic region.

4. The method of claim 1, wherein computing the variation index for the region involves:

scanning through pixels in the region row-by-row in a horizontal direction counting transitions from zero-to-one and from one-to-zero;

scanning through pixels in the region column-by-column in a vertical direction counting transitions from zero-to-one and from one-to-zero; and

dividing the total number of transitions by twice the number of pixels in the region.

5. The method of claim 1, further comprising encoding the halftone region using a different encoding technique than is used to encode a generic region or a symbol region.

6. The method of claim 5, wherein encoding the halftone region involves encoding the halftone region as a grayscale image with an associated halftone pattern dictionary.

7. The method of claim 1, wherein prior to receiving the region from the digital image, the method further comprises partitioning the digital image into different regions.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for identifying halftone regions within a digital image, the method comprising:

receiving a region from the digital image, wherein the digital image is a bi-level image, wherein each pixel has two possible color values;

computing a variation index for a region of the digital image, wherein the variation index indicates how frequently adjacent pixel values in the region differ; and

if the variation index for the region is greater than an upper threshold, determining that the region is a halftone region.

9. The computer-readable storage medium of claim 8, wherein if the variation index for the region is smaller than a lower threshold, the method further comprises:

testing to determine whether there exist black patches in the region;

if not, determining that the region is a symbol region containing text and/or symbols; and

if so, determining that the region is a generic region which is neither a halftone region nor a symbol region.

10. The computer-readable storage medium for claim 9, wherein if the variation index for the region is between the lower threshold and the upper threshold, the method further comprises:

testing to determine whether there exist black patches in the region;

if so

testing to determine whether the variation index is greater than a middle threshold,

if so, determining that the region is a halftone region,

if not, determining that the region is a generic region; and

if no black patches exist in the region,

performing a morphological erosion on the region,

computing a new variation index for the eroded region, and

if the new variation index is greater than a post-erosion threshold, determining that the region is a halftone region,

otherwise, determining that the region is a generic region.

11. The computer-readable storage medium of claim 8, wherein computing the variation index for the region involves:

scanning through pixels in the region row-by-row in a horizontal direction counting transitions from zero-to-one and from one-to-zero;

scanning through pixels in the region column-by-column in a vertical direction counting transitions from zero-to-one and from one-to-zero; and

dividing the total number of transitions by twice the number of pixels in the region.

12. The computer-readable storage medium of claim 8, wherein the method further comprises encoding the halftone region using a different encoding technique than is used to encode a generic region or a symbol region.

13. The computer-readable storage medium of claim 12, wherein encoding the halftone region involves encoding the halftone region as a grayscale image with an associated halftone pattern dictionary.

14. The computer-readable storage medium of claim 8, wherein prior to receiving the region from the digital image, the method further comprises partitioning the digital image into different regions.

15. An apparatus that identifies halftone regions within a digital image, comprising:

a receiving mechanism configured to receive a region from the digital image, wherein the digital image is a bi-level image, wherein each pixel has two possible color values;

an index-computing mechanism configured to compute a variation index for a region of the digital image, wherein the variation index indicates how frequently adjacent pixel values in the region differ; and

an identification mechanism, wherein if the variation index for the region is greater than an upper threshold, the identification mechanism is configured to determining that the region is a halftone region

16. The apparatus of claim 15, wherein if the variation index for the region is smaller than a lower threshold, the identification mechanism is configured to:

test to determine whether there exist black patches in the region;

if not, to determine that the region is a symbol region containing text and/or symbols; and

if so, to determine that the region is a generic region which is neither a halftone region nor a symbol region.

17. The apparatus for claim 16, wherein if the variation index for the region is between the lower threshold and the upper threshold, the identification mechanism if configured to:

test to determine whether there exist black patches in the region;

wherein if black patches exist in the region, the identification mechanism is configured to,

test to determine whether the variation index is greater than a middle threshold,

if so, to determine that the region is a halftone region,

if not, to determine that the region is a generic region; and

wherein if no black patches exist in the region, the identification mechanism is configured to,

perform a morphological erosion on the region,

compute a new variation index for the eroded region, and

if the new variation index is greater than a post-erosion threshold, to determine that the region is a halftone region,

otherwise, to determine that the region is a generic region.

18. The apparatus of claim 15, wherein while computing the variation index for the region, the index-computing mechanism is configured to:

scan through pixels in the region row-by-row in a horizontal direction counting transitions from zero-to-one and from one-to-zero;

scan through pixels in the region column-by-column in a vertical direction counting transitions from zero-to-one and from one-to-zero; and

to

divide the total number of transitions by twice the number of pixels in the region.

19. The apparatus of claim 15, further comprising a encoding mechanism configured to encode the halftone region using a different encoding technique than is used to encode a generic region of a symbol region.

20. The apparatus of claim 19, wherein the encoding mechanism is configured to encode the halftone region as a grayscale image with an associated halftone pattern dictionary.