Method and apparatus for generating a halftone pattern for a multi-level output device

Claim 3

The method claimed in claim 1, wherein the cost for a single threshold value is defined as: ##EQU15## where, C t is the cost for a single threshold value; M x and M y are the dimensions of the dither matrix; R t ,ij is the (i,j) th element of the discrete Fourier transform of the halftone pattern formed by thresholding the dither matrix at t; and V ij 2 is the square of the of the value of the visual modulation transfer function for the frequency corresponding to element ( ij ); t is an individual threshold value; and P is a constant.

Claim 4

The method claimed in claim 1, wherein said visual cost function is minimized by stochastic annealing.

Claim 5

The method claimed in claim 1, wherein said visual cost function is minimized by a genetic algorithm.

Claim 6

The method claimed in claim 1, wherein said digital image is a color digital image having a plurality of color channels, and wherein a separate dither matrix is applied to each color channel.

Claim 7

The method claimed in claim 1, further comprising the step of multiplying the addressed dither value by a scale factor that is a function of the input pixel value before adding the addressed dither value to the input pixel value, to thereby provide a non-linear mapping between input n-bit pixel values and output halftone values.

Claim 8

Apparatus for halftoning a digital image having an x,y array of pixel valves, each pixel having N o levels for output to a device having N q levels, where N o >N q >1, comprising: a. a digital image source of pixel values and corresponding pixel addresses; b. a memory containing a matrix of dither values generated by minimizing a visual cost function, wherein said visual cost function is a combination of costs for a plurality of threshold values; c. means for modularly addressing said memory with a pixel address to produce a dither value; d. an adder connected to said digital image source to receive an input pixel value and connected to said memory to receive said dither value to produce a sum of said input pixel value and said dither value; and e. a quantizer having N q levels connected to said adder to receive said sum and producing an N q level halftoned digital image.

Claim 9

Apparatus for halftoning a digital image having an x,y array of pixel valves, each pixel having N o levels for output to a device having N q levels, where N o >N q >1, comprising: a. a digital image source of pixel values and corresponding pixel addresses; b. a memory containing a matrix of dither values generated by minimizing a visual cost function, wherein said visual cost function is a combination of costs for a plurality of threshold values; c. means for modularly addressing said memory with a pixel address to produce a dither value; d. an adder connected to said digital image source to receive an input pixel value and connected to said memory to receive said dither value to produce a sum of said input pixel value and said dither value; and e. a quantizer having N q levels connected to said adder to receive said sum and producing an N q level halftoned digital image.

Claim 10

The apparatus claimed in claim 7, wherein the cost for a single threshold value is defined as follows: ##EQU16## where, C t is the cost for a single threshold value; M x and M y are the dimensions of the dither matrix; R t ,ij is the (i,j) th element of the discrete Fourier transform of the halftone pattern formed by thresholding the dither matrix at t; and V ij 2 is the square of the of the value of the visual modulation transfer function for the frequency corresponding to element (i j ); t is and individual threshold value; and p is a constant.

Claim 11

The apparatus claimed in claim 7, wherein said visual cost function is minimized by stochastic annealing.

Claim 12

The apparatus claimed in claim 7, wherein said visual cost function is minimized by a genetic algorithm.

Claim 13

The apparatus claimed in claim 7, wherein said digital image is a color digital image having a plurality of color channels, and wherein said apparatus comprises a separate memory, addressing means, adder and quantizer for each channel.

Claim 14

The apparatus claimed in claim 7, further comprising means for multiplying the dither value by a function of the input pixel value prior to the adder, whereby a non-linear mapping is provided between the input pixel values and the output halftone values.

Claim 15

The method claimed in claim 2, wherein said visual cost function is defined as: ##EQU17## where Ct is the cost for a single threshold value; <C to > is the average cost for a series of random variations of dither matrix values thresholded at value t; t is an individual threshold value; and p is a constant equal to or greater than 1.

Claim 16

The apparatus claimed in claim 8, wherein said visual cost function is defined as: ##EQU18## where Ct is the cost for a single threshold value; <C to > is the average cost for a series of random variations of dither matrix values thresholded at value t; t is an individual threshold value; and p is a constant equal to or greater than 1.

Claim 17

The method claimed in claim 2, wherein said visual cost function is a variance of the costs C t for the threshold values.

Claim 18

The apparatus claimed in claim 8, wherein said visual cost function is a variance of the costs C t for the threshold values.