Method for halftoning using stochastic dithering with minimum density variance

Claim 1

In a computer system having a processing circuit and a memory storage device, a method for creating a gray level dot profile with minimum density variance useful for halftoning digital images, comprising the steps of: (a) creating a delta density sum array and creating a dot profile array for one pre-determined gray level; (b) shifting said delta density sum array to be centered at each location where the dot profile is equal to 1; (c) creating an initially cleared cumulative density sum array and adding said delta density sum array to the cumulative density sum array for each location where the dot profile is equal to 1; (d) determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; (e) performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations, then at each said randomly selected dot location where the dot profile is equal to one of 1 and 0, respectively, shifting said delta density sum array to be centered at that location, and adding said delta density sum array to said cumulative density sum array; and (f) minimizing the variance of the density of said dot profile.

Claim 14

A method for halftoning digital images, comprising: (a) creating, as a pre-processing step, a threshold array with minimum density variance, by (i) creating a delta density sum array and creating a dot profile array for one pre-determined gray level; (ii) shifting said delta density sum array to be centered at each location where the dot profile is equal to 1; (iii) creating an initially cleared cumulative density sum array and adding said delta density sum array to the cumulative density sum array for each location where the dot profile is equal to 1; (iv) determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; (v) performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations, then at each said randomly selected dot location where the dot profile is equal to one of 1 and 0, respectively, shifting said delta density sum array to be centered at that location, and adding said delta density sum array to said cumulative density sum array; (vi) minimizing the variance of the density of said dot profile; (vii) assigning a threshold value to locations in the threshold array that correspond to said selected dot locations; (viii) repeatedly, until all gray levels have been completed: determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations, then at each said randomly selected dot location where the dot profile is equal to one of 1 and 0, respectively, shifting said delta density sum array to be centered at that location, and adding said delta density sum array to said cumulative density sum array for each gray level; minimizing the variance of the density of said dot profile for each gray level; and assigning a threshold value to locations in the threshold array that correspond to said selected dot locations for each gray level; (b) providing a processing circuit and an incoming data signal containing digital image information; and (c) comparing, using said processing circuit, said threshold array to said incoming data signal, thereby creating a halftoned output data signal.

Claim 15

A method for halftoning digital images, comprising: (a) creating, as a pre-processing step, a threshold array with minimum density variance, by (i) creating a delta density sum array and creating a dot profile array for one pre-determined gray level; (ii) shifting said delta density sum array to be centered at each location where the dot profile is equal to 1; (iii) creating an initially cleared cumulative density sum array and adding said delta density sum array to the cumulative density sum array for each location where the dot profile is equal to 1; (iv) determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; (v) performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations, then at each said randomly selected dot location where the dot profile is equal to one of 1 and 0, respectively, shifting said delta density sum array to be centered at that location, and adding said delta density sum array to said cumulative density sum array; (vi) minimizing the variance of the density of said dot profile; (vii) assigning a threshold value to locations in the threshold array that correspond to said selected dot locations; (viii) repeatedly, until all gray levels have been completed: determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations, then at each said randomly selected dot location where the dot profile is equal to one of 1 and 0, respectively, shifting said delta density sum array to be centered at that location, and adding said delta density sum array to said cumulative density sum array for each gray level; minimizing the variance of the density of said dot profile for each gray level; and assigning a threshold value to locations in the threshold array that correspond to said selected dot locations for each gray level; (b) providing a processing circuit and an incoming data signal containing digital image information; and (c) comparing, using said processing circuit, said threshold array to said incoming data signal, thereby creating a halftoned output data signal.