Patent US5557709A successfully refreshed from Google Patents.
US5557709A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dither array generation to reduce artifacts in halftoned images
Assignee: Seiko Epson Corp
•
Filing: 1994-07-01
•
Granted: 1996-09-17
•
Expires: 2014-07-01
Abstract
Abstract An existing void-and-cluster method for generating dither arrays for halftoning grayscale images on binary printing devices is improved by including additional steps which both homogenize the starting pattern used in the void-and-cluster method and correct the starting pattern for the effects of oversized dots generated by the printing devices. More particularly, a constant gray starting pattern is first subjected to an error diffusion halftoning process before void and cluster processing to produce a starting binary pattern as a more homogeneous starting point. In addition, after the starting binary pattern has been created, it can be modified to take into account that most printers print "oversized dots" in order to avoid white areas between dots. In particular, from the starting binary pattern, a starting gray pattern is created which uses oversized dot information to assign grayscale values to the "0" pixels surrounding a "1" pixel. Then cluster-finding and void-finding filters are used on both the starting binary pattern and the starting gray pattern to locate "clusters" and "voids". Pixels are transferred from the clusters to the voids to homogenize the arrays and generate an initial binary pattern and an initial gray pattern. The initial binary pattern and the initial gray pattern are then used to assign threshold values to the dither array.
Inventors
- 👤 Joseph S. Shu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:48
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
214 words
Apparatus for generating an improved dither array for halftone image generation by a printing device, the printing device for outputting a matrix of dots representing an image, each of the dots being oversized with relation to the outputted matrix, the apparatus comprising: prototype apparatus for generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising an equal constant value; error diffusion means, responsive to the prototype gray pattern, for applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers having one of a first value and a second value; homogenizing apparatus, responsive to the starting binary pattern, for locating clusters of first-value binary numbers and voids between first-value binary numbers and homogenizing the starting binary pattern to generate an initial binary pattern by repetitively moving first-value binary numbers from the clusters to the voids; oversize adjusting means, responsive to the starting binary pattern, for generating a starting gray pattern in accordance the oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern; and assignment apparatus, responsive to the initial binary pattern and the initial gray pattern, for assigning threshold numbers to generate the improved dither array.
Claim 2
Dependent Claim
214 words
Apparatus for generating an improved dither array for halftone image generation by a printing device, the printing device for outputting a matrix of dots representing an image, each of the dots being oversized with relation to the outputted matrix, the apparatus comprising: prototype apparatus for generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising an equal constant value; error diffusion means, responsive to the prototype gray pattern, for applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers having one of a first value and a second value; homogenizing apparatus, responsive to the starting binary pattern, for locating clusters of first-value binary numbers and voids between first-value binary numbers and homogenizing the starting binary pattern to generate an initial binary pattern by repetitively moving first-value binary numbers from the clusters to the voids; oversize adjusting means, responsive to the starting binary pattern, for generating a starting gray pattern in accordance the oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern; and assignment apparatus, responsive to the initial binary pattern and the initial gray pattern, for assigning threshold numbers to generate the improved dither array.
Claim 3
Dependent Claim
107 words
Apparatus for generating an improved dither array according to claim 1, wherein said homogenizing apparatus comprises: a first apparatus responsive to the starting binary pattern for adding correction amounts to each second-value binary number that borders a first-value binary number in order to create the starting gray pattern which corrects for overlap of printing dots used by the printing device; and a second apparatus responsive to the starting gray pattern for locating clusters of first-value binary numbers and voids between first-value binary numbers and homogenizing the starting gray pattern to generate the initial gray pattern by repetitively moving first-value binary numbers from the clusters to the voids.
Claim 4
Dependent Claim
50 words
Apparatus for generating an improved dither array according to claim 2, wherein said assignment apparatus is responsive to the initial binary pattern and to the initial gray pattern for sequentially assigning threshold numbers to each of the binary numbers in the initial binary pattern to generate the improved dither array.
Claim 5
Dependent Claim
140 words
Apparatus for generating an improved dither array according to claim 2, wherein said assignment apparatus comprises: a first Gaussian filter responsive to the initial gray pattern for locating a center first-value element in a cluster of first-value binary numbers; a second Gaussian filter responsive to the initial gray pattern for locating a center second-value element in a void between first-value binary numbers; a first mechanism for replacing the number in the initial binary pattern at a location corresponding to the center first-value element with a second-value number; a second mechanism for replacing the number in the initial binary pattern at a location corresponding to the center second-value element with a first-value number to generate a new initial binary pattern; and means for assigning a threshold number in the improved dither array to a location corresponding to the center first-value element.
Claim 6
Dependent Claim
38 words
Apparatus for generating an improved dither array according to claim 4, wherein said oversize adjusting means adds correction amounts to each second-value binary number that borders a first-value binary number in order to create the starting gray pattern.
Claim 7
Dependent Claim
62 words
Apparatus for generating an improved dither array according to claim 2, wherein the correction amounts comprise: a first correction amount for correcting for dot overlap and a horizontal and a vertical direction; a second correction amount for correcting for dot overlap in a diagonal direction; and a third correction amount for correcting for dot overlap caused by overlap of two adjacent dots.
Claim 8
Dependent Claim
38 words
Apparatus for generating an improved dither array according to claim 1, wherein said homogenizing apparatus comprises a Gaussian filter responsive to the starting binary pattern for locating clusters of first-value binary numbers and voids between first-value binary numbers.
Claim 9
Dependent Claim
104 words
Apparatus for generating an improved dither array according to claim 1, wherein said error diffusion means comprises: a comparator responsive to the prototype gray pattern for comparing the number in each of the elements in the prototype gray pattern to a predetermined threshold number to generate an output binary value; error generation apparatus responsive to the output binary value and to the constant value for generating an error value; filter apparatus responsive to the error value for generating a plurality of error diffusion values; and a mechanism for applying the error diffusion values to the number in selected elements of the prototype gray pattern.
Claim 10
Independent Claim
139 words
A method for generating a dither array for halftone image generation by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers each having one of a first value and a second value; C. generating an initial binary pattern in response to the starting binary pattern; D. adjusting the starting binary pattern to compensate for oversized dots to generate a starting gray pattern; E. generating an initial gray pattern in response to the starting binary pattern; and F. generating the dither array in accordance with the initial binary pattern and the initial gray pattern.
Claim 11
Independent Claim
139 words
A method for generating a dither array for halftone image generation by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers each having one of a first value and a second value; C. generating an initial binary pattern in response to the starting binary pattern; D. adjusting the starting binary pattern to compensate for oversized dots to generate a starting gray pattern; E. generating an initial gray pattern in response to the starting binary pattern; and F. generating the dither array in accordance with the initial binary pattern and the initial gray pattern.
Claim 12
Dependent Claim
58 words
A method for generating a dither array according to claim 9, wherein step D comprises the step of: D1. adding correction amounts in the starting binary pattern to each second-value binary number that borders a first-value binary number in order to create the starting gray pattern which corrects for overlap of printing dots used by the printing device.
Claim 13
Dependent Claim
69 words
A method for generating dither array according to claim 10, wherein step D1 comprises the steps of: D1a. adding a first correction amount for correcting for dot overlap and a horizontal and a vertical direction; D2b. adding a second correction amount for correcting for dot overlap in a diagonal direction; and D3c. adding a third correction amount for correcting for dot overlap caused by overlap of two adjacent dots.
Claim 14
Dependent Claim
92 words
A method for generating dither array according to claim 9, wherein step B comprises the steps of: B1. comparing the number in each of the elements in the prototype gray pattern to a predetermined threshold number to generate an output binary value; B2. error generation apparatus responsive to the output binary value and to the constant value for generating an error value; B3. generating a plurality of error diffusion values from the error value; and B4. applying the error diffusion values to the number in selected elements of the prototype gray pattern.
Claim 15
Dependent Claim
32 words
A method for generating dither array according to claim 9, wherein steps D and F comprises the initial binary pattern and the initial gray pattern, respectively, using a void and cluster process.
Claim 16
Independent Claim
171 words
A method for generating dither array for halftone image generation by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising a number having an equal constant value; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers having one of a first value and a second value; C. locating clusters of first-value binary numbers and voids between first-value binary numbers in the starting binary pattern and homogenizing the starting binary pattern to generate an initial binary pattern by repetitively moving first-value binary numbers from the clusters to the voids; D. adjusting the starting binary pattern to compensate for oversized dots to generate a starting gray pattern; E. homogenizing the starting gray pattern to generate an initial gray pattern; and F. assigning threshold numbers in response to the initial binary pattern and the initial gray pattern to generate the improved dither array.
Claim 17
Independent Claim
171 words
A method for generating dither array for halftone image generation by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of elements, each element comprising a number having an equal constant value; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional array of binary numbers having one of a first value and a second value; C. locating clusters of first-value binary numbers and voids between first-value binary numbers in the starting binary pattern and homogenizing the starting binary pattern to generate an initial binary pattern by repetitively moving first-value binary numbers from the clusters to the voids; D. adjusting the starting binary pattern to compensate for oversized dots to generate a starting gray pattern; E. homogenizing the starting gray pattern to generate an initial gray pattern; and F. assigning threshold numbers in response to the initial binary pattern and the initial gray pattern to generate the improved dither array.
Claim 18
Independent Claim
186 words
An apparatus for generating a dither array for halftone image generation by an output device, the output device for outputting a matrix of dots representing an image, each of the dots being oversized with relation to the outputted matrix, the apparatus comprising: gray pattern generation means for generating a prototype gray pattern matrix comprising m×n elements, wherein m and n are each positive integers, wherein each of the m×n elements comprise equal predetermined values; error diffusion means for performing error diffusion processing on the gray pattern matrix to form a starting binary pattern comprising m×n elements, each of the m×n elements comprising one of a first value and a second value; initial binary pattern generating means for generating an initial binary pattern in response to the starting binary pattern; oversize adjusting means, responsive the starting binary pattern, for generating a starting gray pattern in accordance the oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern; and assigning means for generating the dither array in accordance with the initial binary pattern and the initial gray pattern.
Claim 19
Independent Claim
186 words
An apparatus for generating a dither array for halftone image generation by an output device, the output device for outputting a matrix of dots representing an image, each of the dots being oversized with relation to the outputted matrix, the apparatus comprising: gray pattern generation means for generating a prototype gray pattern matrix comprising m×n elements, wherein m and n are each positive integers, wherein each of the m×n elements comprise equal predetermined values; error diffusion means for performing error diffusion processing on the gray pattern matrix to form a starting binary pattern comprising m×n elements, each of the m×n elements comprising one of a first value and a second value; initial binary pattern generating means for generating an initial binary pattern in response to the starting binary pattern; oversize adjusting means, responsive the starting binary pattern, for generating a starting gray pattern in accordance the oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern; and assigning means for generating the dither array in accordance with the initial binary pattern and the initial gray pattern.
Claim 20
Dependent Claim
35 words
The apparatus of claim 15, wherein said initial binary pattern generating means generates the initial binary pattern and the initial gray pattern generating means generates the initial gray pattern using a void and cluster process.
Claim 21
Dependent Claim
42 words
The apparatus of claim 15, wherein said oversize adjusting means adds correction amounts to each one of the m×n elements comprising the second value that borders one of the m×n elements that comprises the first value to create the starting gray pattern.
Claim 22
Dependent Claim
56 words
The apparatus of claim 17, wherein the correction amounts comprise: a first correction amount for correcting for dot overlap and a horizontal and a vertical direction; a second correction amount for correcting for dot overlap in a diagonal direction; and a third correction amount for correcting for dot overlap caused by overlap of two adjacent dots.
Claim 23
Dependent Claim
101 words
The apparatus of claim 15, wherein said error diffusion means comprises: a comparator responsive to the prototype gray pattern matrix for comparing the number in each of the elements in the prototype gray pattern matrix to a predetermined threshold number to generate an output binary value; error generation apparatus responsive to the output binary value and to the constant value for generating an error value; filter apparatus responsive to the error value for generating a plurality of error diffusion values; and a mechanism for applying the error diffusion values to the number in selected elements of the prototype gray pattern matrix.
Claim 24
Dependent Claim
203 words
An input/output apparatus comprising: input means for inputting an image: dither generating means for generating a dither matrix comprising: gray pattern generation means for generating a prototype gray pattern matrix comprising m×n elements, wherein m and n are each positive integers, wherein each of the m×n elements comprise equal predetermined values, error diffusion means for performing error diffusion processing on the gray pattern matrix to form a starting binary pattern comprising m×n elements, each of the m×n elements comprising one of a first value and a second value, initial binary pattern generating means for generating an initial binary pattern in response to the starting binary pattern, oversize adjusting means, responsive to the starting binary pattern, for generating a starting gray pattern in accordance oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern, and assigning means for generating the dither array in accordance with the initial binary pattern and the initial gray scale pattern; dither processing means for performing a dither process of the inputted image in accordance with the dither matrix generated by said dither generating means; and output means for outputted with the input image dithered by said dither processing means.
Claim 25
Dependent Claim
203 words
An input/output apparatus comprising: input means for inputting an image: dither generating means for generating a dither matrix comprising: gray pattern generation means for generating a prototype gray pattern matrix comprising m×n elements, wherein m and n are each positive integers, wherein each of the m×n elements comprise equal predetermined values, error diffusion means for performing error diffusion processing on the gray pattern matrix to form a starting binary pattern comprising m×n elements, each of the m×n elements comprising one of a first value and a second value, initial binary pattern generating means for generating an initial binary pattern in response to the starting binary pattern, oversize adjusting means, responsive to the starting binary pattern, for generating a starting gray pattern in accordance oversized dots; initial gray pattern generating means for generating an initial gray pattern in response to the starting gray pattern, and assigning means for generating the dither array in accordance with the initial binary pattern and the initial gray scale pattern; dither processing means for performing a dither process of the inputted image in accordance with the dither matrix generated by said dither generating means; and output means for outputted with the input image dithered by said dither processing means.
References Cited (Backward Citations)
US4196454A
Cited
US4339774A
Cited
US4345313A
Cited
US4449150A
Cited
US4752822A
Cited
US4668995A
Cited
US4680645A
Cited
US4955065A
Cited
US5111302A
Cited
US5201013A
Cited
US5315669A
Cited
US5134667A
Cited
US5077615A
Cited
US5031050A
Cited
US5278671A
Cited
US5341228A
Cited
US5363210A
Cited
US5276535A
Cited
US5313287A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-17 | 2000-03-18 | 2000-09-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-17 | 2004-03-18 | 2004-09-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-17 | 2008-03-18 | 2008-09-17 | $7700.00 | Window Closed / Lapsed |