Method and apparatus for generating digital halftone images using a rotated dispersed dither matrix

Claim 1

A method for producing digital halftone screens, the screens being composed of a plurality of repetitive screen patterns, all having a predetermined screen angle; said screen patterns being obtained by applying threshold comparisons between input image intensity levels and threshold values contained in a rotated threshold dither matrix; said rotated threshold dither matrix being obtained by applying a discrete one-to-one rotation to a well-dispersed non-rotated square threshold dither matrix composed of multiple well-dispersed non-rotated square threshold sub-matrices; said rotated threshold dither matrix being composed of a multiple of rotated sub-matrices of different shapes; the method being characterized by the fact that all said rotated sub-matrices contain exactly the same number of elementary cells as said non-rotated sub-matrices, that their elementary cell positions are defined by said discrete one-to-one rotation and that the threshold values associated with elementary cells of said non-rotated sub-matrices are identical to corresponding threshold values associated with elementary cells of said rotated sub-matrices, so that said rotated threshold dither matrix can be seen as a spatial reorganization of the non-rotated threshold dither matrix, without modifying the threshold values of said threshold dither matrix; the method comprising the steps of (a) creating and storing in memory said well-dispersed non-rotated square threshold dither matrix by replicating said well-dispersed non-rotated square threshold sub-matrices each of size n by n, c by c times vertically and horizontally, in a threshold matrix coordinate system (i,j), where n and c are integers; (b) creating and storing in memory said rotated threshold dither matrix in an output coordinate system (x,y); every elementary cell of said rotated threshold dither matrix which contains the threshold value having the coordinates (x t ,y t ) in the output coordinate system (x,y) computed according to the following formula which specifies said discrete one-to-one rotation of angle α=arctan(b/a): x.sub.t =round((a*(i.sub.t -i.sub.0)-b*(j.sub.t -j.sub.0))/c)+x.sub.0 y.sub.t =round((b*(i.sub.t -i.sub.0)-a*(j.sub.t -j.sub.0))/c)+y.sub.0 where (i t ,j t ) define the coordinates of an elementary cell of said non-rotated threshold dither matrix in the threshold matrix coordinate system (i,j) having the same threshold value as the elementary cell (x t , y t ) of the rotated threshold dither matrix; (i 0 ,j 0 ) respectively (x 0 ,y 0 ) define the positions of said non-rotated threshold matrix respectively rotated threshold matrix in the coordinate systems (i,j) respectively (x,y) and wherein a, b and c are integers, members of Pythagorean triplets {a,b,c} satisfying Diophantine equation a 2 +b 2 =c 2 and said screen angle being α=arctan(b/a) to said output coordinate system (x,y); (c) scanning the input gray-scale image pixel by pixel, finding the appropriate rectangular area of each pixel, in said output coordinate system (x,y); then applying, for every elementary dot inside said rectangular area, a comparison between the input gray level and the corresponding threshold value, in the rotated threshold dither matrix defined in step (b), and producing for each elementary dot inside said rectangular area an active (white) pixel respectively inactive (black) pixel, according to the result of said comparison.

Claim 2

A method for producing digital halftone screens, the screens being composed of a plurality of repetitive screen patterns, all having a predetermined screen angle; said screen patterns being obtained by applying threshold comparisons between input image intensity levels and threshold values contained in a rotated threshold dither matrix; said rotated threshold dither matrix being obtained by applying a discrete one-to-one rotation to a well-dispersed non-rotated square threshold dither matrix composed of multiple well-dispersed non-rotated square threshold sub-matrices; said rotated threshold dither matrix being composed of a multiple of rotated sub-matrices of different shapes; the method being characterized by the fact that all said rotated sub-matrices contain exactly the same number of elementary cells as said non-rotated sub-matrices, that their elementary cell positions are defined by said discrete one-to-one rotation and that the threshold values associated with elementary cells of said non-rotated sub-matrices are identical to corresponding threshold values associated with elementary cells of said rotated sub-matrices, so that said rotated threshold dither matrix can be seen as a spatial reorganization of the non-rotated threshold dither matrix, without modifying the threshold values of said threshold dither matrix; the method comprising the steps of (a) creating and storing in memory said well-dispersed non-rotated square threshold dither matrix by replicating said well-dispersed non-rotated square threshold sub-matrices each of size n by n, c by c times vertically and horizontally, in a threshold matrix coordinate system (i,j), where n and c are integers; (b) creating and storing in memory said rotated threshold dither matrix in an output coordinate system (x,y); every elementary cell of said rotated threshold dither matrix which contains the threshold value having the coordinates (x t ,y t ) in the output coordinate system (x,y) computed according to the following formula which specifies said discrete one-to-one rotation of angle α=arctan(b/a): x.sub.t =round((a*(i.sub.t -i.sub.0)-b*(j.sub.t -j.sub.0))/c)+x.sub.0 y.sub.t =round((b*(i.sub.t -i.sub.0)-a*(j.sub.t -j.sub.0))/c)+y.sub.0 where (i t ,j t ) define the coordinates of an elementary cell of said non-rotated threshold dither matrix in the threshold matrix coordinate system (i,j) having the same threshold value as the elementary cell (x t , y t ) of the rotated threshold dither matrix; (i 0 ,j 0 ) respectively (x 0 ,y 0 ) define the positions of said non-rotated threshold matrix respectively rotated threshold matrix in the coordinate systems (i,j) respectively (x,y) and wherein a, b and c are integers, members of Pythagorean triplets {a,b,c} satisfying Diophantine equation a 2 +b 2 =c 2 and said screen angle being α=arctan(b/a) to said output coordinate system (x,y); (c) scanning the input gray-scale image pixel by pixel, finding the appropriate rectangular area of each pixel, in said output coordinate system (x,y); then applying, for every elementary dot inside said rectangular area, a comparison between the input gray level and the corresponding threshold value, in the rotated threshold dither matrix defined in step (b), and producing for each elementary dot inside said rectangular area an active (white) pixel respectively inactive (black) pixel, according to the result of said comparison.