Digital halftoning with correlated minimum visual modulation patterns

Claim 1

A method of generating a halftone image from a digital image with an electronic digital computer, comprising the steps of: A) providing a set of correlated minimal visual noise binary patterns of all desired density levels, determined by employing a stochastic annealing process, a human visual system modulation transfer function (MTF) weighting function, and a constraint to insure that the patterns are correlated, to generate a halftone bit pattern for each density level of a multilevel digital input signal, the patterns being correlated in a manner that reduces visual noise resulting from transitions between patterns, with said annealing process comprises the steps of: a) determining sets D inf , D sup and 5 D from the boundary patterns P inf , P sup , where D.sub.inf =("on" dots in the pattern P.sub.inf) D.sub.sup =("on" dots in the pattern P.sub.sup) D=Dsup-Dinf in a set-theoretic sense; b) initializing a pattern P mid with the "on" dots in the set P inf and a random selection of half the dots in the set D so that the number of "on" dots is proportional to the density level of the pattern; c) defining subsets D on and D off of set D, where D on is the set of dots in the D that are set "on" in the pattern P mid , and D off is the set of dots in D that are set "off" in the pattern P mid ; d) calculating a cost function according to the equation ##EQU7## where i,j are the spatial frequency indices, V ij is a visual MTF scaled to those indices, P ij is the discrete Fourier Transform (DFT) of the pattern P mid , and * represents complex conjugation; e) randomly switching at least a pair of dots from subsets D on and D off to form a new pattern and calculating the cost function of the new pattern according to step d; f) calculating a test statistic q to determine if the cost function at step e) is statistically a lower cost than the cost of step d) according to the process ##EQU8## where Δcost=cost of step e)-cost of step d), and T is a normalization parameter initially set such that about 80% of new patterns will be determined to be from a lower cost random process even when Δcost is greater than zero; g) replacing the pattern with P mid generated in step c) with new pattern generated in step e) if q>1 or if ξ<q where ξ is a uniform pseudo-random number between 0 and 1, otherwise, reject the new pattern and retain the pattern P mid ; h) repeating steps e) through g) a sufficient number of times; i) decreasing T to kT where k<1 and repeating steps e) through h) until the cost of successive decreases in T are no longer changing. j) substitute P mid for P inf and repeat steps a) through i); k) substitute P mid for P sup and repeat steps a) through i); l) repeat steps j) and k) with the P mid that results from steps j) and k); m) repeat steps l) until all desired density levels are formed. B) providing a pixel value representing the density level of a digital image. C) for each pixel value of the digital image, modularly selecting a portion of the binary bit pattern from the corresponding pattern of the same density level form the set of binary bit patterns by addressing the bit pattern with the lower significant bits of an (x,y) pixel address associated with each pixel to select a lot and employing the selected bit to form a halftone image.

Claim 2

A method of generating a halftone image from a digital image with an electronic digital computer, comprising the steps of: A) providing a set of correlated minimal visual noise binary patterns of all desired density levels, determined by employing a stochastic annealing process, a human visual system modulation transfer function (MTF) weighting function, and a constraint to insure that the patterns are correlated, to generate a halftone bit pattern for each density level of a multilevel digital input signal, the patterns being correlated in a manner that reduces visual noise resulting from transitions between patterns, with said annealing process comprises the steps of: a) determining sets D inf , D sup and 5 D from the boundary patterns P inf , P sup , where D.sub.inf =("on" dots in the pattern P.sub.inf) D.sub.sup =("on" dots in the pattern P.sub.sup) D=Dsup-Dinf in a set-theoretic sense; b) initializing a pattern P mid with the "on" dots in the set P inf and a random selection of half the dots in the set D so that the number of "on" dots is proportional to the density level of the pattern; c) defining subsets D on and D off of set D, where D on is the set of dots in the D that are set "on" in the pattern P mid , and D off is the set of dots in D that are set "off" in the pattern P mid ; d) calculating a cost function according to the equation ##EQU7## where i,j are the spatial frequency indices, V ij is a visual MTF scaled to those indices, P ij is the discrete Fourier Transform (DFT) of the pattern P mid , and * represents complex conjugation; e) randomly switching at least a pair of dots from subsets D on and D off to form a new pattern and calculating the cost function of the new pattern according to step d; f) calculating a test statistic q to determine if the cost function at step e) is statistically a lower cost than the cost of step d) according to the process ##EQU8## where Δcost=cost of step e)-cost of step d), and T is a normalization parameter initially set such that about 80% of new patterns will be determined to be from a lower cost random process even when Δcost is greater than zero; g) replacing the pattern with P mid generated in step c) with new pattern generated in step e) if q>1 or if ξ<q where ξ is a uniform pseudo-random number between 0 and 1, otherwise, reject the new pattern and retain the pattern P mid ; h) repeating steps e) through g) a sufficient number of times; i) decreasing T to kT where k<1 and repeating steps e) through h) until the cost of successive decreases in T are no longer changing. j) substitute P mid for P inf and repeat steps a) through i); k) substitute P mid for P sup and repeat steps a) through i); l) repeat steps j) and k) with the P mid that results from steps j) and k); m) repeat steps l) until all desired density levels are formed. B) providing a pixel value representing the density level of a digital image. C) for each pixel value of the digital image, modularly selecting a portion of the binary bit pattern from the corresponding pattern of the same density level form the set of binary bit patterns by addressing the bit pattern with the lower significant bits of an (x,y) pixel address associated with each pixel to select a lot and employing the selected bit to form a halftone image.