Error diffusion using next scanline error impulse response

• US 7,057,773 B2
• Filed: 12/28/2001
• Issued: 06/06/2006
• Est. Priority Date: 12/29/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Ilbery, Peter William Mitchell
• Primary Examiner(s): Rogers, Scott A.
• Application Number:
  US10/029,267
• Publication Number:
  US 20020122210A1
• Time in Patent Office: 1,621 Days
• Field of Search: 358/1.9, 358/3.03, 358/3.04, 358/3.05, 358/3.26, 382/252, 382/275
• US Class Current: 358/3.05
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

An apparatus (1100) for halftoning an image is disclosed. The apparatus comprises means for determining an output value of a current pixel on a current scanline using a sum of an input value (1102) for the current pixel and a neighborhood error value (1150) at the current pixel, means (1124) for determining an error at the current pixel as the difference between (i) the sum of the input value (1102) for the current pixel and the neighborhood error value (1150) at the current pixel, and (ii) the output value (1120) of the current pixel; and means (1140) for adding a proportion of the error at the current pixel to neighborhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response; wherein said next scanline error impulse response approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.

Claims

1. A method of halftoning an image, said method comprising steps of:

determining an output value of a current pixel on a current scanline using a sum of an input value for the current pixel and a neighbourhood error value at the current pixel;

determining an error at the current pixel as the difference between (i) the sum of the input value for the current pixel and the neighbourhood error value at the current pixel, and (ii) the output value of the current pixel; and

adding a proportion of the error at the current pixel to neighbourhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response;

wherein said next scanline error impulse response;

approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.

2. A method of halftoning according to claim 1, wherein:

the next scanline error impulse response is a member of a plurality of next scanline error impulse responses, each of said plurality of next scanline error impulse responses approximating a function which spreads with self-convolution in proportion to the degree of self-convolution;

each said member of said plurality of next scanline error impulse responses is associated with a corresponding error diffusion mask; and

a corresponding size of each said error diffusion mask depends upon a grey value of a region to which said mask is applied.

3. A method of halftoning according to claim 1, wherein:

the next scanline error impulse response is a sampling of a Cauchy distribution, said sampling being normalised so that a sum of next scanline error impulse response values is unity.

4. A method of halftoning according to claim 1, wherein:

the next scanline error impulse response is left-right symmetric.

5. A method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, where pixels are processed scanline by scanline, and scanlines are processed one at a time from the top of the image to the bottom of the image, and where a scanline is processed pixel by pixel either from left to right or from right to left, and where the processing for each pixel comprises the steps of:

(a) determining the output value of a current pixel using a sum of the input value of the current pixel and a neighbourhood error value for the pixel;

(b) determining an error at the current pixel as the difference between, firstly, the sum of the input value of the current pixel and the neighbourhood error value for the pixel, and secondly the output value of the pixel;

(c) adding proportions of the error at the current pixel to the neighbourhood error values of yet to be processed pixels of the current and next scanline;

and where the said proportions of the error at a current pixel are designed so that the next scanline error impulse response, being that function which maps

(A) from a horizontal pixel offset;

(B) to the total proportion of the error at the current pixel added to the neighbourhood error of that pixel of the next scanline which is displaced by the horizontal pixel offset from the current pixel, following complete processing of the current scanline;

approximates a function which spreads with self-convolution in proportion to the degree of self-convolution.

6. A method as claimed in claim 5, where the next scanline error impulse response approximates a scaled sampling of a Cauchy distribution.

7. A method as claimed in claim 5, where the next scanline error impulse response approximates a function which has a Discrete Space Fourier Transform which is a replicated two-sided exponential function.

8. A method as claimed in any one of claims 5 to 7, where the output value of a current pixel is determined by comparison of the sum of the input value of the current pixel and the neighbourhood error value for the pixel against a threshold value.

9. A method as claimed in claim 8, where in step (c), for a current pixel at pixel position (i,j), being column i and scanline j, error at the current pixel is added to the neighbourhood error of only those pixels which are either:

i) on the current scanline ahead of the current pixel at a pixel position (i+current_offset, j), where, for left to right processing of the current scanline, current_offset is greater than zero, and, for right to left processing of the current scanline, current_offset is less than zero, or

(ii) on the next scanline below or behind the current pixel at a pixel position, (i−

next_offset, j+1), where, for left to right processing of the current scanline, next_offset is greater than or equal to zero, and, for fight to left processing of the current scanline, next_offset is less than or equal than zero.

10. A method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, where pixels are processed scanline by scanline and scanlines are processed one at a time from the top of the image to the bottom of the image, and where a scanline is processed pixel by pixel either from left to right or from right to left, and where the processing for each pixel comprises the steps of:

(a) determining the output value of a current pixel using a sum of the input value of the current pixel and a neighbourhood error value for the pixel;

(b) determining an error at the current pixel as the difference between, firstly, the sum of the input value of the current pixel and the neighbourhood error value for the pixel, and secondly the output value of the pixel;

(c) selecting, using the current pixel input value, a set of proportions and a set of corresponding pixel position offsets, from a family of sets of proportions and corresponding pixel position offsets;

(d) adding the selected proportions of the error at the current pixel to the neighbourhood error values of yet to be processed pixels at pixel positions offset from the current pixel by the selected corresponding pixel position offsets;

and where each set of the said family of sets of proportions and corresponding pixel offsets, is designed so that the next scanline error impulse response corresponding to that set, being that function which maps

(A) from a horizontal pixel offset;

(B) to the proportion of the error at the current pixel added to the neighbourhood error of that pixel of the next scanline displaced by the horizontal pixel offset from the current pixel, following complete halftone processing of the current scanline using only the said set of proportions and corresponding pixel offsets;

approximates a function which spreads with self-convolution in proportion to the degree of self-convolution.

11. A method as claimed in claim 10, where each next scanline error impulse response, corresponding to a set of proportions and pixel offsets, approximates a scaled sampling of a Cauchy distribution.

12. A method as claimed in claim 10, where each next scanline error impulse response, corresponding to a set of proportions and pixel offsets, approximates a function which has a Discrete Space Fourier Transform which is a replicated two-sided exponential function.

13. A method as claimed in claim 11 or 12, where the family of sets of proportions and pixel offsets together with the selection, using the current pixel input value, of a set of proportions and pixel offsets, are designed so as to minimise processing while also minimising the presence of artifacts in the halftone output artifacts including cross-over artifacts and poor spreading in sparse halftone patterns.

14. A method as claimed in claim 13, where the maximum absolute offset in each set of the family of sets of proportions and pixel offsets, varies so that the family of sets includes a set with small maximum absolute offset and a set with large maximum absolute offset and where intermediate input values primarily select sets with small maximum absolute offset, and extreme input values primarily select sets with large maximum absolute offset.

15. A method as claimed in claim 14, where the output value of a current pixel is determined by comparison of the sum of the input value of the current pixel and the neighbourhood error value for the pixel against a threshold value.

16. A method as claimed in claim 15, where in step (d), for a current pixel at pixel position (i,j), being column i and scanline j, error at the current pixel is added to the neighbourhood error of only those pixels which are either:

(i) on the current scanline ahead of the current pixel at a pixel position (i+current_offset, j), where, for left to right processing of the current scanline, current_offset is greater than zero, and, for right to left processing of the current scanline, current_offset is less than zero, or

(ii) on the next scanline below or behind the current pixel at a pixel position, (i−

next_offset, j+1) where, for left to right processing of the current scanline, next_offset is greater than or equal to zero, and, for right to left processing of the current scanline, next_offset is less than or equal than zero.

17. A method of halftoning an image, said image comprising a plurality of pixels each having an input value and an assignable output value that can take on one of at least two output values, where pixels are processed scanline by scanline and scanlines are processed one at a time from the top of the image to the bottom of the image, and where a scanline is processed pixel by pixel either from left to right or from right to left, and where the processing for each pixel comprises the steps of:

(a) determining the output value of a current pixel using a sum of the input value of the current pixel and a neighbourhood error value for the pixel;

(b) determining an error at the current pixel as the difference between, firstly, the sum of the input value of the current pixel and the neighbourhood error value for the pixel, and secondly the output value of the pixel;

(c) selecting, using the current pixel input value, a set of proportions and a set of corresponding pixel position offsets, from a family of sets of proportions and corresponding pixel position offsets, said set of proportions being in accordance with a next scanline error impulse response that approximates a function which spreads with self-convolution in proportion to a degree of self-convolution;

(d) adding the selected proportions of the error at the current pixel to the neighbourhood error values of yet to be processed pixels at pixel positions offset from the current pixel by the selected corresponding pixel position offsets;

and where each set of the said family of sets of proportions and corresponding pixel offsets, only includes pixel offsets corresponding to pixels on the same scanline as the current pixel or to pixels on the next scanline.

18. An apparatus for halftoning an image, said apparatus comprising:

means for determining an output value of a current pixel on a current scanline using a sum of an input value for the current pixel and a neighbourhood error value at the current pixel;

means for determining an error at the current pixel as the difference between (i) the sum of the input value for the current pixel and the neighbourhood error value at the current pixel, and (ii) the output value of the current pixel; and

means for adding a proportion of the error at the current pixel to neighbourhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response;

wherein said next scanline error impulse response;

approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.

19. An apparatus for halftoning an image, said apparatus comprising:

a memory for storing a program;

a processor for executing the program, said program comprising;

code for a determining step for determining an output value of a current pixel on a current scanline using a sum of an input value for the current pixel and a neighbourhood error value at the current pixel;

code for a determining step for determining an error at the current pixel as the difference between (i) the sum of the input value for the current pixel and the neighbourhood error value at the current pixel, and (ii) the output value of the current pixel; and

code for an adding step for adding a proportion of the error at the current pixel to neighbourhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response;

wherein said next scanline error impulse response;

approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.

20. A computer program product including a computer readable medium having recorded thereon a computer program for directing a processor to execute a method for halftoning an image, said program comprising:

code for a determining step for determining an output value of a current pixel on a current scanline using a sum of an input value for the current pixel and a neighbourhood error value at the current pixel;

code for a determining step for determining an error at the current pixel as the difference between (i) the sum of the input value for the current pixel and the neighbourhood error value at the current pixel, and (ii) the output value of the current pixel; and

code for an adding step for adding a proportion of the error at the current pixel to neighbourhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response;

wherein said next scanline error impulse response;

approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.

21. A computer program embodie on a computer readable medium for directing a processor to execute a method for halftoning an image, said program comprising:

code for a determining step for determining an output value of a current pixel on a current scanline using a sum of an input value for the current pixel and a neighbourhood error value at the current pixel;

code for a determining step for determining an error at the current pixel as the difference between (i) the sum of the input value for the current pixel and the neighbourhood error value at the current pixel, and (ii) the output value of the current pixel; and

code for an adding step for adding a proportion of the error at the current pixel to neighbourhood error values at as yet unprocessed pixels of a subsequent scanline in accordance with a next scanline error impulse response;

wherein said next scanline error impulse response;

approximates a function which spreads with self-convolution in proportion to a degree of self-convolution.