Method for reconstructing a dithered image

• US 6,185,334 B1
• Filed: 01/30/1998
• Issued: 02/06/2001
• Est. Priority Date: 01/30/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Iyengar, Giridharan, Ulichney, Robert A., Cheung, Shiufun, MacNamara, Robert
• Primary Examiner(s): Tran, Phuoc
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/015,934
• Time in Patent Office: 1,103 Days
• Field of Search: 382/166, 382/170, 382/199, 382/260, 382/266, 382/264
• US Class Current: 382/199
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: H04N 1/40075 Descreening, i.e. converting a halftone signal into a corresponding continuous-tone signal; Rescreening, i.e. combined descreening and halftoning

Abstract

A method of reconstructing an image from a dithered image. A predefined set of filters having different regions of support is established. Each filter is defined by a number of filter coefficients and an impulse response function which defines the filter response for a region of support outside of which the impulse response is zero. Filters are organized according to indexes and this organization represents the order in which the filters are considered during a filter selection process. The filter selection process selects a filter constrained by the rule that the filter selected must only perform low-pass filtering on a region of support that does not contain edges of an image. Due to the organization of the filter set, the filter selection process first selects the largest filter from the filter set that fits within the region about the current processed pixel. If there is an edge of an image within the support region of the first selected filter, the next smaller filter is selected. If there is no edge in the selected smaller filter, the dithered image is reconstructed using the selected smaller filter.

Claims

1. A method for reconstructing a dithered image, comprising the steps of:

selecting a first filter from a set of filters, the selected first filter having a first filter coefficient and the selected first filter operable on a first region of support;

determining that an image edge exists within the first region of support;

responsive to determining that an image edge exists within the first region of support, selecting a second filter from the set of filters, the selected second filter having a second filter coefficient and the selected second filter operable on a second region of support, the second region of support being smaller than the first region of support;

determining if an image edge exists within the second region of support; and

responsive to determining that no image edge exists within the second region of support, reconstructing the dithered image using the second filter coefficient.

2. The method of claim 1, wherein the step of determining if an image edge exists within the second region of support further includes the step of generating a difference map for the second region of support.

3. The method of claim 2, wherein the step of determining if an image edge exists within the second region of support further includes the step of searching the difference map for at least one of a series of (a) 1'"'"'s and 0'"'"'s, (b) −

1'"'"'s and 0'"'"'s, and (c) all 0'"'"'s to determine that the region of support excludes the image edge therefrom.

4. The method of claim 2 further comprising the step of comparing the difference map of the second filter to a table of valid difference map patterns to determine if the image edge exists within the second region of support.

5. The method of claim 4 further comprising the step of pregenerating a table of valid difference map patterns indicating that an image edge is excluded from the second region of support.

6. The method of claim 4, wherein the step of pregenerating further includes the step of pregenerating the table using a dither template of the originally dithered image thereby reducing a number of entries in the table.

7. An article of manufacture for processing a dithered image, comprising:

computer readable storage medium; and

a computer program stored on said storage medium;

wherein said computer program is configured to be readable from said computer readable storage medium by a processor and thereby causing said processor to operate so as to;

select a first filter from a set of filters, the selected first filter having a first filter coefficient and the selected first filter operable on a first region of support;

determine that an image edge exists within the first region of support;

responsive to determining that an image edge exists within the first region of support, select a second filter from the set of filters, the selected second filter having a second filter coefficient and the selected second filter operable on a second region of support, the second region of support being smaller that the first region of support;

determine if an image edge exists within the second region of support; and

responsive to determining that no image edge exists within the second region of support, reconstruct the dithered image using the second filter coefficient.

8. The article of manufacture of claim 7, wherein the computer program is further configured to cause said processor to generate a difference map for the second region of support of the filter.

9. The article of manufacture of claim 8, wherein the computer program is further configured to cause said processor to search the difference map for at least one of a series of (a) 1'"'"'s and 0'"'"'s, (b) −

1'"'"'s and 0'"'"'s, and (c) all 0'"'"'s, to determine that the second region of support excludes the edge therefrom.

10. The article of manufacture of claim 8, wherein the computer program is further configured to cause said processor to compare the difference map of the second filter to a table of valid difference map patterns to determine if the image edge exists within the second region of support.

11. The article of manufacture of claim 10, wherein the computer program is further configured to cause said processor to pregenerate a table of valid difference map patterns indicating the image edge is excluded from the second region of support.

12. The article of manufacture of claim 10, wherein the computer program is further configured to cause said processor to pregenerate the table using a dither template of the original dithered image to reduce a number of entries in the table.