Technique for producing a fine grained dithered halftone image having an increased number of gray levels

Claim 1

A method for generating a halftone pel pattern for depicting a continuous tone image, wherein said pattern is to be reproduced on a binary output device, said method comprising the step of: establishing a correspondence between identically shaped tiles that form a pre-defined tile pattern and individual pixel values that collectively form at least a portion of a continuous tone gray level image; determining, for each of said tiles, a gray value, g 0 , of the pixel values that correspond to that tile; determining, for each of said tiles, one, t 0 , of a plurality of pre-defined threshold values that has a highest value less than or equal to said gray values g 0 for that tile; determining, for each of said tiles, a gray level value, g 3 , of the pixels that correspond to that tile wherein said gray level value is formed in response to both the gray value, g 0 , of that tile and propagated gray level error established therewith and propagated thereto; determining, for each of said tiles, whether the gray level value, g e , for that tile equals or exceeds the value of a successively larger threshold value, contained within said plurality of pre-defined threshold values, than threshold value t 0 associated with that tile; setting, in response to said determining step, a threshold value, t s , for each of said tiles as either said threshold value t 0 for that tile or said successively larger threshold value; ascertaining, for each of said tiles, an amount of gray value error, e, as equalling the gray level value, g e , for said each tile less the set threshold value, t s , associated therewith; partitioning, for each of said tiles, the gray value error, e, into a plurality of pre-defined components; propagating the value of each of the components for each of said tiles to a pre-determined corresponding one of a plurality of tiles situated adjacent to said each tile, wherein the gray value error is collectively propagated along identical paths from tile to tile throughout the tile pattern; and dithering the pixel values corresponding to each one of said tiles using either a first or second matrix of pre-defined threshold values to form a halftone dithered pel pattern spatially corresponding thereto wherein the matrix to be used for said one tile is selected in response to the set threshold value t s associated therewith, such that a dithered halftone pel pattern that corresponds to said one tile is formed within the halftone image and which, when viewed with other such dithered halftone patterns appearing in said halftone image and associated with tiles adjacent thereto, spatially depicts a discrete gray level that can not be obtained through use of dithering said pixel values using either said first or second matrix alone.

Claim 2

A method for generating a halftone pel pattern for depicting a continuous tone image, wherein said pattern is to be reproduced on a binary output device, said method comprising the step of: establishing a correspondence between identically shaped tiles that form a pre-defined tile pattern and individual pixel values that collectively form at least a portion of a continuous tone gray level image; determining, for each of said tiles, a gray value, g 0 , of the pixel values that correspond to that tile; determining, for each of said tiles, one, t 0 , of a plurality of pre-defined threshold values that has a highest value less than or equal to said gray values g 0 for that tile; determining, for each of said tiles, a gray level value, g 3 , of the pixels that correspond to that tile wherein said gray level value is formed in response to both the gray value, g 0 , of that tile and propagated gray level error established therewith and propagated thereto; determining, for each of said tiles, whether the gray level value, g e , for that tile equals or exceeds the value of a successively larger threshold value, contained within said plurality of pre-defined threshold values, than threshold value t 0 associated with that tile; setting, in response to said determining step, a threshold value, t s , for each of said tiles as either said threshold value t 0 for that tile or said successively larger threshold value; ascertaining, for each of said tiles, an amount of gray value error, e, as equalling the gray level value, g e , for said each tile less the set threshold value, t s , associated therewith; partitioning, for each of said tiles, the gray value error, e, into a plurality of pre-defined components; propagating the value of each of the components for each of said tiles to a pre-determined corresponding one of a plurality of tiles situated adjacent to said each tile, wherein the gray value error is collectively propagated along identical paths from tile to tile throughout the tile pattern; and dithering the pixel values corresponding to each one of said tiles using either a first or second matrix of pre-defined threshold values to form a halftone dithered pel pattern spatially corresponding thereto wherein the matrix to be used for said one tile is selected in response to the set threshold value t s associated therewith, such that a dithered halftone pel pattern that corresponds to said one tile is formed within the halftone image and which, when viewed with other such dithered halftone patterns appearing in said halftone image and associated with tiles adjacent thereto, spatially depicts a discrete gray level that can not be obtained through use of dithering said pixel values using either said first or second matrix alone.