Methods of controlling dot size in digital halftoning with multi-cell threshold arrays

• US 5,305,118 A
• Filed: 08/18/1993
• Issued: 04/19/1994
• Est. Priority Date: 02/08/1991
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Knuth, Donald E., Schiller, Stephen N.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Stoll, Thomas L.
• Application Number:
  US08/109,398
• Time in Patent Office: 244 Days
• Field of Search: 358/455, 358/456, 358/457, 358/459
• US Class Current: 358/3.07
• CPC Class Codes: H04N 1/4058 with details for producing a halftone screen at an oblique angle H04N1/4056 takes precedence

Abstract

A method of equalizing the shape and size of halftone dots in a supertile having digital cells, corresponding ideal cells and pixels to faithfully reproduce an image having predetermined gray levels. Various techniques include: (1) adding offset vectors to the coordinates of pixels in digital cells; (2) determining twice as many smaller digital cells as original digital cells; and (3) determining a model digital cell and ranking pixels in remaining digital cells to mimic the ranking of pixels in the model cell.

Claims

1. A method of displaying a high quality image on a raster display device having predetermined gray levels made up of halftone dots of substantially equal shape and size in a supertile that includes K digital cells, each supertile having a geometric center of gravity, K corresponding ideal cells each having geometric centers and a plurality of pixels having coordinates to reproduce the image by applying a spot function selected from a wide range of spot functions to the coordinates of a selected list of pixels, comprising the steps of:

a) creating a list of pixels in a digital cell;

b) determining the x and y coordinates in cell space of the pixels in the said digital cell;

c) determining an offset vector having x and y coordinates to be applied to said pixel coordinates in cell space of that digital cell;

d) adding said offset vector to the coordinates of said pixels in said list;

e) selecting a spot function from a wide variety of spot functions;

f) ranking said pixels in said list according to the value resulting from applying said selected spot function to their coordinates;

g) selecting pixels for display according to the results of said ranking in order to properly reproduce said predetermined gray levels of the image being reproduced; and

h) displaying a high quality image including the pixels that have been selected for display using a ranking resulting from applying a spot function selected from a wide range of spot functions.

2. The technique of claim 1 wherein the pixels are selected in rank order until the ratio of black to white pixels provides a predetermined gray level.

3. The technique of claim 1 wherein said offset vector is the difference between the geometric center of the ideal cell associated with said digital cell and the geometric center of gravity of said digital cell.

4. The technique of claim 3 wherein said center of gravity is computed by converting device coordinate values of said pixels to ideal cell space coordinates and averaging the resulting coordinate values separately to obtain the respective average coordinate values.

5. The technique of claim 1 wherein the x and y coordinates of said offset vector are determined by a random number generator.

6. The technique of claim 1 wherein said offset vector has the same value for all digital cells in said supertile, and after adding said offset vector to said coordinates of said pixels, if the total is outside a predetermined range, the sum is adjusted to lie within said predetermined range.

7. The method of claim 6 where said offset vector is (1/2, 1/2) and said predetermined range is from -1 to +1.

8. The technique of claim 1 wherein said supertile further includes translation vectors that are used to translate the pixel coordinates in said digital cell that lie further away than a predetermined distance from the center of the ideal cell associated with said digital cell so that the resultant translated pixel coordinates result in pixels having a distance from said center of said ideal cell smaller than said predetermined distance.

9. The technique of claim 8 wherein said center of gravity is computed by converting said resultant translated pixel coordinates to ideal cell space coordinate values and averaging the resulting ideal cell space coordinate values to obtain the average coordinate values.

10. A method of displaying an image on a raster display device having predetermined gray levels made up of halftone dots of substantially equal shape and size in a supertile which represent predetermined gray levels of the image being displayed, said supertile including a predetermined number of digital cells of a first type in a first digital halftone grid and twice said predetermined number of digital cells of a second type in a second digital halftone grid, each of said digital cells having a plurality of pixels, comprising the steps of:

a) assigning an equal number of pixels to each of said second type of digital cells;

b) computing a threshold value for each pixel in each of said digital cells of said second type; and

c) comparing said threshold values to said gray levels and on the basis of the results of that comparison, selecting the pixels for display in order to properly reproduce said predetermined gray levels of the image; and

d) displaying the image including the pixels selected for display.

11. The technique of claim 10 wherein said second ideal halftone grid (1) is rotated by 45°

relative to said first ideal halftone grid; and

(2) has its corners lying at the midpoints of the sides of said first ideal halftone grid.

12. The method of claim 10 wherein the coordinates of a pixel in one of the digital cells of said second type are transformed to coordinates in the cell space of a cell of said first type.

13. The method of claim 12 where, after the transformation, the transformed coordinates of said first type are inputted to a mathematical function to compute said threshold values.

14. The technique of claim 13 where said threshold values are assigned evenly over a portion of an available range of threshold values.

15. A method of displaying an image on a raster display device having predetermined gray levels made up of halftone dots of substantially equal shape and size in a supertile that includes a predetermined number of digital cells, each digital cell having a plurality of pixels, a first of said digital cells and each remaining digital cell having a cell data structure representing pixels which allows the operations of sorting, ranking and selecting pixels of predetermined rank, comprising the steps of:

a) selecting a spot function from a wide variety of spot functions;

b) ranking the plurality of pixels in said first digital cell according to the value resulting from applying said selected spot function to their cell space coordinates to establish for the plurality of pixels for such cell a first rank order;

c) ranking the plurality of pixels in the remaining digital cells in the same manner as for said first digital cell to provide a first ranking for the plurality of pixels of each said remaining digital cells;

d) for each of said remaining digital cells, selecting one pixel from the plurality of pixels in each such cell which was assigned the lowest rank in step c), above, and assigning said one pixel, a second rank which is as low as possible;

e) iteratively ranking the remaining pixels in each of said remaining digital cells so that a given pixel of each such remaining cell is assigned a given second rank, where the number of previously second-ranked pixels contiguous to said given pixel is approximately equal to a number of pixels in said first digital cell which are;

(1) contiguous to a pixel whose first rank in said first rank order is equal to said given second rank of said given pixel; and

(2) which itself has a rank less than or equal to said given second rank, thereby establishing a second ranking of pixels;

f) selecting pixels for display according to the results of said given second ranking for the purpose of properly reproducing said predetermined gray levels of the image; and

g) displaying the image including the pixels that have been selected for display using a ranking resulting from applying a spot function selected from a wide range of spot functions.

16. The technique of claim 15 wherein said second ranking of pixels is established consecutively starting with pixels with smaller ranks and moving to pixels with larger ranks.

17. The technique of claim 15 wherein said second ranking is established consecutively starting with pixels with larger ranks and moving to pixels with smaller ranks.

18. The technique of claim 15 wherein said second ranking is established by assigning pixel ranks alternately, one from the smallest and one from the largest available unused second ranking.

19. The technique of claim 15 wherein each pixel has coordinates in cell space and wherein said first ranking is established according to the values returned by a spot function applied to said cell space coordinates of each of said pixels.