Method and apparatus for dither array generation to reduce artifacts in halftoned image data utilizing ink reduction processing

Claim 1

Apparatus for generating a dither array for halftone image generation of every other pixel of n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, 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 k×l elements, each element comprising an equal constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; error diffusion, apparatus 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 k×l array of binary numbers having one of a first value and a second value, and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; 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 with 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 11

A method for generating a dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, 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 wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers each having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; 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

A method for generating a dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, 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 wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype gray pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers each having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; 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 18

A method for generating a dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixel comprising n/2×m pixels by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of k×l elements, each element comprising a number having an equal constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; 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 to each of the binary numbers in the initial binary pattern and the initial gray pattern to generate the improved dither array.

Claim 19

A method for generating a dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixel comprising n/2×m pixels by a printing device, the method comprising the steps of: A. generating a prototype gray pattern comprising a two-dimensional array of k×l elements, each element comprising a number having an equal constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; 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 to each of the binary numbers in the initial binary pattern and the initial gray pattern to generate the improved dither array.

Claim 21

An apparatus for generating a dither array for halftone image generation of every other pixel, i×j representing an image, i and j being positive integers, the every other pixels comprising i/2×j pixels, 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 and wherein each of the m×n elements is in corresponding relation to only the i/2×j pixels; 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 22

An apparatus for generating a dither array for halftone image generation of every other pixel, i×j representing an image, i and j being positive integers, the every other pixels comprising i/2×j pixels, 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 and wherein each of the m×n elements is in corresponding relation to only the i/2×j pixels; 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 30

A method for generating a starting pattern for use by a void and cluster dither array generation process for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; C. applying the void and cluster dither array generation process to the starting binary pattern to generate an improved dither array; and D. 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 a starting gray pattern which corrects for overlap of printing dots used by the printing device.

Claim 31

A method for generating a starting pattern for use by a void and cluster dither array generation process for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; C. applying the void and cluster dither array generation process to the starting binary pattern to generate an improved dither array; and D. 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 a starting gray pattern which corrects for overlap of printing dots used by the printing device.

Claim 34

A method for generating a starting pattern for use by a void and cluster dither array generation process for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels, wherein step B comprises the steps of: B1. comparing the number in each of the elements in the prototype binary 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 binary pattern; and C. applying the void and cluster dither array generation process to the starting binary pattern to generate an improved dither array.

Claim 35

A method for generating a starting pattern for use by a void and cluster dither array generation process for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixels comprising n/2×m pixels, by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary pattern to generate a starting binary pattern comprising a two-dimensional k×l array of binary numbers having one of a first value and a second value, wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels, wherein step B comprises the steps of: B1. comparing the number in each of the elements in the prototype binary 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 binary pattern; and C. applying the void and cluster dither array generation process to the starting binary pattern to generate an improved dither array.

Claim 36

A method for generating an improved dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixel comprising n/2×m pixels by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of k×l elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary 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; and D. assigning threshold numbers to each of the binary numbers in the initial binary pattern to generate the improved dither array, wherein each of the pixels comprises a corresponding dot having a radius r in the range of 1/dpi≦r≦√2/dpi, and dpi is a resolution of the pixels in dots per inch.

Claim 37

A method for generating an improved dither array for halftone image generation of every other pixel of an n×m pixel data representing an image, n and m being positive integers, the every other pixel comprising n/2×m pixels by a printing device, the method comprising the steps of: A. generating a prototype binary pattern comprising a two-dimensional array of k×l elements, each element comprising a number having a constant value wherein k and l are positive integers and wherein each of the k×l elements is in corresponding relation to only the n/2×m pixels; B. applying an error diffusion halftoning process to the prototype binary 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; and D. assigning threshold numbers to each of the binary numbers in the initial binary pattern to generate the improved dither array, wherein each of the pixels comprises a corresponding dot having a radius r in the range of 1/dpi≦r≦√2/dpi, and dpi is a resolution of the pixels in dots per inch.