Strategies for producing quantized image information

• US 7,308,151 B2
• Filed: 03/14/2006
• Issued: 12/11/2007
• Est. Priority Date: 08/01/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Evans, Glenn F., Spears, Stacey L., Munsil, Donald J.
• Primary Examiner(s): Couso; Jose L.
• Application Number:
  US11/276,788
• Publication Number:
  US 20060147109A1
• Time in Patent Office: 637 Days
• Field of Search: 382/252, 382270-275, 348254-256, 341/120, 341/131, 358/1.9, 358/3.03, 358/3.06, 358/465, 358/466, 358/519, 358/531, 358/536
• US Class Current: 382/252
• CPC Class Codes: H04N 1/4053 with threshold modulated relative to input image data or vice versa

Abstract

Strategies are set forth herein for quantizing and dithering original image information to produce quantized image information. According to one exemplary implementation, the strategies involve: quantizing a sum that combines an original value taken from the original image information, a noise value, and an error term, to produce a quantized value; and calculating an error term for a subsequent quantizing operation by computing a difference between the quantized value and the original value. By virtue of his process, the strategies essentially add noise information to the quantization process, not the original image information, which results in quantized image information having reduced artifacts. The strategies can be used in conjunction with the Floyd-Steinberg error dispersion algorithm. According to another feature, the noise value is computed using a random number generator having a long repeat period, which further reduces artifacts.

Claims

1. A computer-implemented method for quantizing and dithering original image information to produce quantized image information, comprising:

quantizing for a first pixel in an image a sum that combines an original value taken from the original image information, a noise value, and an error term, to produce a high-precision quantized value;

rounding the high-precision quantized value to a nearest low-precision number;

storing the nearest low-precision number in a pixel array;

calculating an error term by computing a difference between the stored nearest low-precision number and the original value; and

utilizing the calculated error term from the first pixel to quantize a sum for a second pixel.

2. The method of claim 1, wherein the calculating further comprises dispersing the calculated error term accordingly to an error dispersion algorithm, wherein the error term that is quantized is based on a component of the dispersed error term.

3. The method of claim 2, wherein the error dispersion algorithm is a Floyd-Steinberg error dispersion algorithm.

4. The method of claim 1, further comprising computing the noise value using a random number generator.

5. The method of claim 4, wherein the random number generator has a repeat period that is sufficiently long so that quantized image information is substantially free of artifacts.

6. The method of claim 4, wherein the random number generator is an R250 random noise generator.

7. One or more computer readable media storing machine-readable instructions configured to implement the method of claim 1.

16. The apparatus of claim 1, wherein the means for calculating comprises means for dispersing the calculated error term accordingly to an error dispersion algorithm, wherein the error term that is quantized is based on a component of the dispersed error term.

17. The apparatus of claim 16, wherein the error dispersion algorithm is a Floyd-Steinberg error dispersion algorithm.

8. An apparatus for quantizing and dithering original image information to produce quantized image information, comprising:

a noise generator configured to produce noise values; and

a dithering module configured to produce the quantized image information iteratively by;

quantizing for a first pixel in an image a sum that combines an original value taken from the original image information, a noise value from the noise generator, and an error term, to produce a high-precision quantized value;

rounding the high-precision quantized value to a nearest low-precision number;

storing the nearest low-precision number in a pixel array;

calculating an error term by computing a difference between the stored nearest low-precision number and the original value; and

utilizing the calculated error term from the first pixel to quantize a sum for a second pixel.

9. The apparatus of claim 8, wherein the calculating further comprises dispersing the calculated error term accordingly to an error dispersion algorithm, wherein the error term that is quantized is based on a component of the dispersed error term.

10. The apparatus of claim 9, wherein the error dispersion algorithm is a Floyd-Steinberg error dispersion algorithm.

11. The apparatus of claim 8, wherein the noise generator is a random number generator.

12. The apparatus of claim 11, wherein the random number generator has a repeat period that is sufficiently long so that the noise generator does not repeat its numbers when processing the image.

13. The apparatus of claim 11, wherein the random number generator is an R250 random noise generator.

14. An image processing pipeline that incorporates the apparatus of claim 8.

15. An apparatus for quantizing and dithering original image information to produce quantized image information, comprising:

means for quantizing for a first pixel in an image a sum that combines an original value taken from the original image information, a noise value, and an error term, to produce a high-precision quantized value;

means for rounding the high-precision quantized value to a nearest low-precision number;

means for storing the nearest low-precision number in a pixel array;

means for calculating an error term by computing a difference between the stored nearest low-precision number and the original value; and

means for utilizing the calculated error term from the first pixel to quantize a sum for a second pixel.

18. The apparatus of claim 15, further comprising means for computing the noise value using a random number generating process.

19. The apparatus of claim 18, wherein the random number generating process that has a repeat period that is sufficiently long so that the noise generator does not repeat its numbers when processing the image.

20. One or more computer readable media storing machine-readable instructions configured to implement each of the means of claim 15.