Patent EP0762734A2 successfully refreshed from Google Patents.
EP0762734A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for halftoning using stochastic dithering with minimum density variance
Assignee: Lexmark International Inc
•
Filing: 1996-09-02
•
Granted: —
•
Expires: 2016-09-02
Abstract
Abstract A dispersed-dot stochastic dither array is provided for rendering halftone images having excellent visual quality and are created by a minimum density variance method. The minimum density variance method considers the statistical distribution of the pixels in the image, and is unrelated to previous techniques based on either spatial frequencies or spatial distances, such as the blue noise mask and the void and cluster algorithm. By minimizing the variance in the number of dots within each local region (10) of the image, a smooth and dispersed distribution of dots may be obtained. The method of the present invention also offers the flexibility to accommodate particular design considerations, through the selection of the size and shape of the image regions, the weighting of the cost function, and the option of guiding the selection of dots with "target" dot profile images.
Inventors
- 👤 Brian Edward Cooper
- 👤 Thomas Anthony Knight
- 👤 Shaun Timothy Love
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 15:47
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
210 words
A method for creating a gray level dot profile with minimum density variance for halftoning digital images in a computer system having a processing circuit and a memory storage device, 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 2
Dependent Claim
113 words
The method as recited in claim 1, wherein the step of creating a dot profile array and a delta density sum array is for a mid-gray level, and the step of determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations is repeated to create a succession of higher gray levels until the dot profile is completely filled with 1's, then the step of determining an available set of dot locations and randomly selecting a pre-determined number of said available dot locations is repeated, from the mid-gray level, to create a succession of lower gray levels until the dot profile is completely filled with 0's.
Claim 3
Dependent Claim
22 words
The method as recited in claim 1 or 2, wherein said delta density array uses a function of regions of various sizes.
Claim 4
Dependent Claim
21 words
The method as recited in claim 1, 2 or 3 wherein said delta density array uses regions having a square shape.
Claim 5
Dependent Claim
24 words
The method as recited in claim 1, 2 or 3 wherein said delta density array uses regions having a shape other than a square.
Claim 6
Dependent Claim
16 words
The method as recited in claim 5, wherein the shape of said regions is substantially circular.
Claim 7
Dependent Claim
16 words
The method as recited in claim 5, wherein the shape of said regions is substantially diamond-shaped.
Claim 8
Independent Claim
57 words
The method as recited in any preceding claim, wherein the step of performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations includes, to create the next higher gray level, the addition of said randomly selected dots at dot locations where the dot profile is equal to 0.
Claim 9
Independent Claim
57 words
The method as recited in any preceding claim, wherein the step of performing one of an addition and a subtraction to said dot profile array at said randomly selected dot locations includes, to create the next lower gray level, the subtraction of said randomly selected dots at dot locations where the dot profile is equal to 1.
Claim 10
Independent Claim
30 words
The method as recited in any preceding claim, wherein the step of minimizing the variance of the density of said dot profile comprises an iterative process equivalent to simulated annealing.
Claim 11
Independent Claim
178 words
The method as recited in any preceding claim, further comprising the steps of assigning a threshold value to locations in a threshold array that correspond to said selected dot locations; and repeatedly, for adjacent gray levels 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; thereby creating said threshold array.
Claim 12
Independent Claim
44 words
The method as recited in any preceding claim, wherein the step of 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 is constrained by a target dot profile.
Claim 13
Independent Claim
267 words
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) repeating steps (iv) to (vii) for each gray level until all gray levels have been completed; (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 14
Dependent Claim
21 words
The method as recited in claim 13, wherein said incoming data signal contains black and white gray scale digital image information.
Claim 15
Dependent Claim
17 words
The method as recited in claim 13, wherein said incoming data signal contains color digital image information.
Claim 16
Dependent Claim
32 words
The method as recited in claim 13, 14 or 15, further comprising the step of providing a print engine and printing a hard-copy halftoned image based upon said halftoned output data signal.
Claim 17
Dependent Claim
210 words
Apparatus for creating a gray level dot profile with minimum density variance for halftoning digital images, comprising: (a) means for creating a delta density sum array and for creating a dot profile array for one pre-determined gray level; (b) means for shifting said delta density sum array to be centered at each location where the dot profile is equal to 1; (c) means for creating an initially cleared cumulative density sum array and for adding said delta density sum array to the cumulative density sum array for each location where the dot profile is equal to 1; (d) means for determining an available set of dot locations and for randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; (e) means for 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, for shifting said delta density sum array to be centered at that location, and for adding said delta density sum array to said cumulative density sum array; and (f) means for minimizing the variance of the density of said dot profile.
Claim 18
Dependent Claim
272 words
Apparatus for halftoning digital images, comprising: (a) means for creating, as a pre-processing step, a threshold array with minimum density variance, comprising: (i) means for creating a delta density sum array and for creating a dot profile array for one pre-determined gray level; (ii) means for shifting said delta density sum array to be centered at each location where the dot profile is equal to 1; (iii) means for creating an initially cleared cumulative density sum array and for adding said delta density sum array to the cumulative density sum array for each location where the dot profile is equal to 1; (iv) means for determining an available set of dot locations and for randomly selecting a pre-determined number of said available dot locations needed to create the next gray level; (v) means for 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, for shifting said delta density sum array to be centered at that location, and for adding said delta density sum array to said cumulative density sum array; (vi) means for minimizing the variance of the density of said dot profile; (vii) means for assigning a threshold value to locations in the threshold array that correspond to said selected dot locations; (b) a processing circuit for receiving an incoming data signal containing digital image information; and (c) means for comparing, using said processing circuit, said threshold array to said incoming data signal, thereby creating a halftoned output data signal.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.