Halftoning with gradient-based selection of dither matrices

• US 5,701,366 A
• Filed: 09/04/1996
• Issued: 12/23/1997
• Est. Priority Date: 09/04/1996
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Information Systems Incorporated (Canon Inc.)
• Inventors: Ostromoukhov, Victor, Nehab, Smadar
• Primary Examiner(s): Rogers, Scott A.
• Application Number:
  US08/707,753
• Time in Patent Office: 475 Days
• Field of Search: 382/237, 395/109, 358/455, 358/456, 358/457, 358/458, 358/460, 358/298, 358/534, 358/535, 358/536
• US Class Current: 382/237
• CPC Class Codes: H04N 1/4055 producing a clustered dots or a size modulated halftone pattern
• CPC Class Codes: H04N 1/4058 with details for producing a halftone screen at an oblique angle H04N1/4056 takes precedence

Abstract

Halftoning gray scale image data includes selection of one of plural dither matrices based on an analysis of local tonality gradient for each target pixel. Plural different but reciprocally compatible dither matrices are defined, and for each target pixel in the gray scale image data, a local gradient for tonality is calculated. One of the dither matrices is selected in accordance with the calculated gradient, and the target pixel is thresholded using the selected dither matrix. Enhanced dithering according to the invention improves smoothness of gradations present in the invention, diminishes the "banding" or "contouring" effect found in natural images, and improves visual appearance and stability of business graphics, particularly in cases where a complex image contains both natural and computer generated business graphics.

Claims

1. A method for obtaining halftone image data from corresponding gray scale image data, the gray scale image data being representative of pixels in an image and arbitrarily including values representative of both highlights and midtones for the image, said method comprising the steps of:

calculating a local tonality gradient of gray scale image data for a target pixel, the tonality gradient being calculated based on a comparison between at least the gray scale image data for the target pixel and gray scale image data for a pixel adjacent the target pixel;

selecting one dither matrix from among plural dither matrices based on the calculated tonality gradient, each of the plural dither matrices containing threshold values which differ from others of the plural dither matrices; and

thresholding the gray scale image data for the target pixel using the selected dither matrix so as to obtain halftone image data for the target pixel.

2. A method according to claim 1, wherein the plural dither matrices are reciprocally compatible.

3. A method according to claim 2, wherein the plural dither matrices all originate from a common basic dither matrix, have a common relative phase, and include at least one supercell dither matrix and a basic dither matrix such that normalized relative inter-tile differences in the supercell dither matrices are smaller than the normalized inter-pixel differences in the basic dither matrix.

4. A method according to claim 1, wherein said plural dither matrices are comprised by first and second dither matrices, and wherein the tonality gradient is calculated by comparing the gray scale image data for the target pixel with gray scale image data for all immediately adjacent pixels, and wherein the first dither matrix is selected in a case where all gray scale data is the same and the second dither matrix is selected if any of the gray scale image data is different.

5. A method according to claim 1, wherein said plural dither matrices are comprised by first, second and third dither matrices, wherein the local tonality gradient is calculated by identifying the presence of a large gradient, no gradient, and at least one intermediate gradient, and wherein the first dither matrix is selected in a case where a large gradient is identified, the second dither matrix is selected in a case where no gradient is identified, and the third dither matrix is selected in a case where an intermediate dither matrix is identified.

6. A halftone printing method for printing a halftone image corresponding to a gray scale image, comprising the steps of:

accepting a selection to halftone according to error diffusion or according to dithering;

halftoning by error diffusion in a case where a selection to halftone according to error diffusion is selected;

halftoning by dithering in a case where a selection to halftone according to dithering is selected;

wherein in a case where halftoning according to error diffusion is selected (a) a local tonality gradient of gray scale image data for a target pixel is calculated based on a comparison between at least the gray scale image data for the target pixel and gray scale image data for a pixel adjacent the target pixel, (b) one dither matrix is selected from among plural dither matrices based on the calculated tonality gradient, each of the plural dither matrices containing threshold values which differ from others of the plural dither matrices, and (c) the gray scale image data is thresholded for the target pixel using the selected dither matrix so as to obtain halftone image data for the target pixel.

7. A method according to claim 6, wherein the plural dither matrices are reciprocally compatible.

8. A method according to claim 7, wherein the plural dither matrices all originate from a common basic dither matrix, have a common relative phase, and include at least one supercell dither matrix and a basic dither matrix such that normalized relative inter-tile differences in the supercell dither matrices are smaller than the normalized inter-pixel differences in the basic dither matrix.

9. A method according to claim 6, wherein said plural dither matrices are comprised by first and second dither matrices, and wherein the tonality gradient is calculated by comparing the gray scale image data for the target pixel with gray scale image data for all immediately adjacent pixels, and wherein the first dither matrix is selected in a case where all gray scale data is the same and the second dither matrix is selected if any of the gray scale image data is different.

10. A method according to claim 6, wherein said plural dither matrices are comprised by first, second and third dither matrices, wherein the local tonality gradient is calculated by identifying the presence of a large gradient, no gradient, and at least one intermediate gradient, and wherein the first dither matrix is selected in a case where a large gradient is identified, the second dither matrix is selected in a case where no gradient is identified, and the third dither matrix is selected in a case where an intermediate dither matrix is identified.

11. An apparatus for obtaining halftone image data from corresponding gray scale image data, the gray scale image data being representative of pixels in an image and arbitrarily including values representative of both highlights and midtones for the image, said apparatus comprising:

a memory for storing computer executable process steps, and for storing plural dither matrices, each of the plural dither matrices containing threshold values which differ from others of the plural dither matrices; and

a processor for executing the process steps stored in said memory;

wherein said process steps include steps to (a) calculate a local tonality gradient of gray scale image data for a target pixel, the tonality gradient being calculated based on a comparison between at least the gray scale image data for the target pixel and gray scale image data for a pixel adjacent the target pixel, (b) select one dither matrix from among plural dither matrices based on the calculated tonality gradient, and (d) threshold the gray scale image data for the target pixel using the selected dither matrix so as to obtain halftone image data for the target pixel.

12. An apparatus according to claim 11, wherein the plural dither matrices are reciprocally compatible.

13. An apparatus according to claim 12, wherein the plural dither matrices all originate from a common basic dither matrix, have a common relative phase, and include at least one supercell dither matrix and a basic dither matrix such that normalized relative inter-tile differences in the supercell dither matrices are smaller than the normalized inter-pixel differences in the basic dither matrix.

14. An apparatus according to claim 11, wherein said plural dither matrices are comprised by first and second dither matrices, and wherein the tonality gradient is calculated by comparing the gray scale image data for the target pixel with gray scale image data for all immediately adjacent pixels, and wherein the first dither matrix is selected in a case where all gray scale data is the same and the second dither matrix is selected if any of the gray scale image data is different.

15. An apparatus according to claim 11, wherein said plural dither matrices are comprised by first, second and third dither matrices, wherein the local tonality gradient is calculated by identifying the presence of a large gradient, no gradient, and at least one intermediate gradient, and wherein the first dither matrix is selected in a case where a large gradient is identified, the second dither matrix is selected in a case where no gradient is identified, and the third dither matrix is selected in a case where an intermediate dither matrix is identified.

16. A halftone printing apparatus for printing a halftone image corresponding to a gray scale image, comprising:

accepting means for accepting a selection to halftone according to error diffusion or according to dithering;

halftoning means for halftoning by error diffusion in a case where a selection to halftone according to error diffusion is selected;

halftoning means for halftoning by dithering in a case where a selection to halftone according to dithering is selected;

wherein, in a case where halftoning according to dithering is selected, said process steps include steps to (a) calculate a local tonality gradient of gray scale image data for a target pixel, the tonality gradient being calculated based on a comparison between at least the gray scale image data for the target pixel and gray scale image data for a pixel adjacent the target pixel, (b) select one dither matrix from among plural dither matrices based on the calculated tonality gradient, each of the plural dither matrices containing threshold values which differ from others of the plural dither matrices, and (c) threshold the gray scale image data for the target pixel using the selected dither matrix so as to obtain halftone image data for the target pixel.

17. An apparatus according to claim 16, wherein the plural dither matrices are reciprocally compatible.

18. An apparatus according to claim 17, wherein the plural dither matrices all originate from a common basic dither matrix, have a common relative phase, and include at least one supercell dither matrix and a basic dither matrix such that normalized relative inter-tile differences in the supercell dither matrices are smaller than the normalized inter-pixel differences in the basic dither matrix.

19. An apparatus according to claim 16, wherein said plural dither matrices are comprised by first and second dither matrices, and wherein the tonality gradient is calculated by comparing the gray scale image data for the target pixel with gray scale image data for all immediately adjacent pixels, and wherein the first dither matrix is selected in a case where all gray scale data is the same and the second dither matrix is selected if any of the gray scale image data is different.

20. An apparatus according to claim 16, wherein said plural dither matrices are comprised by first, second and third dither matrices, wherein the local tonality gradient is calculated by identifying the presence of a large gradient, no gradient, and at least one intermediate gradient, and wherein the first dither matrix is selected in a case where a large gradient is identified, the second dither matrix is selected in a case where no gradient is identified, and the third dither matrix is selected in a case where an intermediate dither matrix is identified.

21. Computer-executable process steps stored on a computer readable medium, said process steps for obtaining halftone image data from corresponding gray scale image data, the gray scale image data being representative of pixels in an image and arbitrarily including values representative of both highlights and midtones for the image, said process steps comprising:

a calculating step to calculate a local tonality gradient of gray scale image data for a target pixel, the tonality gradient being calculated based on a comparison between at least the gray scale image data for the target pixel and gray scale image data for a pixel adjacent the target pixel;

a selecting step to select one dither matrix from among plural dither matrices based on the calculated tonality gradient, each of the plural dither matrices containing threshold values which differ from others of the plural dither matrices; and

a thresholding step to threshold the gray scale image data for the target pixel using the selected dither matrix so as to obtain halftone image data for the target pixel.

22. Computer-executable process steps according to claim 21, wherein the plural dither matrices are reciprocally compatible.

23. Computer-executable process steps according to claim 22, wherein the plural dither matrices all originate from a common basic dither matrix, have a common relative phase, and include at least one supercell dither matrix and a basic dither matrix such that normalized relative inter-tile differences in the supercell dither matrices are smaller than the normalized inter-pixel differences in the basic dither matrix.

24. Computer-executable process steps according to claim 21, wherein said plural dither matrices are comprised by first and second dither matrices, and wherein the tonality gradient is calculated by comparing the gray scale image data for the target pixel with gray scale image data for all immediately adjacent pixels, and wherein the first dither matrix is selected in a case where all gray scale data is the same and the second dither matrix is selected if any of the gray scale image data is different.

25. Computer-executable process steps according to claim 21, wherein said plural dither matrices are comprised by first, second and third dither matrices, wherein the local tonality gradient is calculated by identifying the presence of a large gradient, no gradient, and at least one intermediate gradient, and wherein the first dither matrix is selected in a case where a large gradient is identified, the second dither matrix is selected in a case where no gradient is identified, and the third dither matrix is selected in a case where an intermediate dither matrix is identified.