Error diffusion method and apparatus

• US 6,678,073 B1
• Filed: 02/08/2000
• Issued: 01/13/2004
• Est. Priority Date: 02/08/2000
• Status: Expired due to Term

• Current Assignee: Zoran Corporation (Qualcomm, Inc.)
• Original Assignee: Oak Technology Inc (Qualcomm, Inc.)
• Inventors: Jewitt, Thomas W.
• Primary Examiner(s): ROGERS, SCOTT A
• Application Number:
  US09/500,146
• Time in Patent Office: 1,435 Days
• Field of Search: 358/3.04, 358/3.03, 358/3.02, 358/1.9, 358/3.26, 382/252
• US Class Current: 358/3.04
• CPC Class Codes: H04N 1/4052 by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions

Abstract

The invention relates to a method of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location (n, l) within the image, and having an original greyscale value associated therewith. The method includes the steps of adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value, comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel, calculating a second error term having a value that is the difference between the output value and the modified greyscale value, and distributing the second error term to a preselected plurality of neighboring pixels at positions (n+1, l), (n−1, l+1), (n, l+1), (n+1, l+1) using a linear phase filter algorithm having a set of distribution coefficients with a sum less than one, wherein one coefficient within the set of coefficients is combined with the second error term for each pixel position. The method also includes these steps being repeated for each pixel within the image. In another embodiment, the portion of the second error term distributed to the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (n−1, l+1).

Claims

1. A method of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location (n, l) within the image, and having an original greyscale value associated therewith, the method comprising:

(a) adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value;

(b) comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel;

(c) calculating a second error term having a value that is the difference between the output value and the modified greyscale value;

(d) distributing the second error term to a preselected plurality of neighboring pixels at positions (n+1, l), (n−

1, l+1), (n, l+1), (n+1, l+1) using a linear phase filter algorithm having a set of distribution coefficients with a sum less than one, wherein one of the coefficients within the set of coefficients is combined with the second error term for each pixel position; and

(e) repeating steps (a)-(d) for each pixel within the image.

2. The method of claim 1 wherein the linear phase filter algorithm uses finite impulse response techniques.

3. The method of claim 1 wherein the combining of one coefficient with the second error term for each pixel position is accomplished by multiplying each coefficient by the second error term.

4. The method of claim 1 wherein the portion of the second error term distributed to the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (n−

1, l+1).

5. The method of claim 4 wherein the portion of the second error term distributed to the pixel at position (n−

1, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1).

6. The method of claim 5 wherein the portion of the second error term distributed to the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combine d with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (n−

1, l+1).

7. The method of claim 6, wherein the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (n−

1, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375.

8. The method of claim 1 wherein the order in which the pixels are processed is determined using raster scanning.

9. The method of claim 1 wherein the order in which the pixels are processed is determined using serpentine scanning.

10. A method of diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location within the image, and having an original greyscale value associated therewith, the method comprising:

(a) adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value;

(b) comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel;

(c) calculating a second error term having a value that is less than the difference between the output value and the modified greyscale value;

(d) distributing the second error term to a preselected plurality of neighboring pixels at positions (n+1, l), (n−

1, l+1), (n, l+1), (n+1, l+1), wherein the portion of the second error term distributed to the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (n−

1, l+1), and the portion of the second error term distributed to the pixel at position (n−

1, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1), and the portion of the second error term distributed to the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combined with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (n−

1, l+1); and

(e) repeating steps (a)-(d) for each pixel within the image.

11. The method of claim 10 wherein the order in which the pixels are processed is determined using raster scanning.

12. The method of claim 10 wherein the order in which the pixels are processed is determined using serpentine scanning.

13. The method of claim 10 wherein the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (n−

1, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375.

14. An apparatus for diffusing error caused by quantizing each pixel within an image formed of a plurality of pixels, each pixel representing a greyscale value of the image at a location (n, l) within the image, and having an original greyscale value associated therewith, the apparatus comprising:

a first summing module for adding to the original greyscale value of a pixel having a position (n, l) within the image a first error term resulting from quantization of previously processed pixels to derive a modified greyscale value;

a second summing module operatively connected to the output of the first summing module and the output of the quantizer for calculating a second error term having a value that is less than the difference between the output value and the modified greyscale value;

a quantizer operatively connected to the output of the first module comparing the modified greyscale value of the pixel with a threshold to select an output value representing the pixel; and

an error filter module operatively connected to the input of the first summing module and the output of the second summing module for distributing the second error term, to preselected plurality of neighboring pixels at positions (n+1, l), (n−

1, l+1), (n, l+1), (n+1, l+1) using a linear phase filter algorithm having a set of distribution coefficients with a sum less than one, wherein one of the coefficients within the set of coefficients is combined with the second error term for each pixel position.

15. The apparatus of claim 14 wherein the linear phase filter algorithm of the error filter module uses finite impulse response techniques.

16. The apparatus of claim 14 wherein the combining of one coefficient with the second error term for each pixel position is accomplished by multiplying each coefficient by the second error term.

17. The apparatus of claim 14 wherein the error filter module further distributes the second error term such that the pixel at position (n+1, l+1) equals the portion of the second error term distributed to the pixel at position (n−

1, l+1).

18. The apparatus of claim 17 wherein the error filter module further distributes the second error term such that the pixel at position (n−

1, l+1) combined with the portion of the second error term for the pixel at position (n+1, l+1) equals the portion of the second error term for the pixel at position (n, l+1).

19. The apparatus of claim 18 wherein the error filter module further distributes the second error term such that the pixel at position (n+1, l) equals the sum of the portion of the second error term of the pixel at position (n+1, l+1) combined with the portion of the second error term of the pixel at position (n, l+1) and combined with the portion of the second error term of the pixel at position (n−

1, l+1).

20. The apparatus of claim 19 wherein the error filter module further distributes the second error term to preselected plurality of pixels, including pixels at positions (n+1, l), (n−

1, l+1), (n, l+1), (n+1, l+1), such that the portion of the second error term distributed to the pixel at position (n+1, l) is about 0.484375, the portion of the second error term distributed to the pixel at position (n−

1, l+1) is about 0.12109375, the portion of the second error term distributed to the pixel at position (n, l+1) is about 0.2421875 and the portion of the second error term distributed to the pixel at position (n+1, l+1) is about 0.12109375.

21. The apparatus of claim 14 wherein the order in which the pixels are processed is determined using raster scanning.

22. The apparatus of claim 14 wherein the order in which the pixels are processed is determined using serpentine scanning.

23. The apparatus of claim 14 wherein the output of the quantizer is operatively connected to a device used to print the image.

24. The apparatus of claim 14 further comprising:

a memory element, including a storage location for at least some of the pixels in the plurality of pixels of an image, wherein the portion of the second error term distributed to a particular pixel is added to contents of the designated storage location of that particular pixel.