Rendering images utilizing adaptive error diffusion
View Patent ↗An adaptive halftoning method where the difference between a digital image and a filtered digital image is introduced into the system on a pixel by pixel basis is disclosed. In this method, each input difference pixel has a corresponding error value of the previous pixel added to the input value at a summing node, resulting in modified image difference data; the modified image difference data is passed to a threshold comparator where the modified image difference data is compared to a threshold value, the threshold value varying according to the properties of the digital image, to determine the appropriate output level; the output level is subtracted from the modified image difference value to produce the input to an error filter; the output of the error filter is multiplied by an adaptation coefficient, where the adaptation coefficient varies according to the properties of the digital image, to generate the error level for the subsequent input pixel; and, the cyclical processing of pixels is continued until the end of the input data is reached.
1. A method of generating a halftone image from an input digital image, said digital image represented by a multiplicity of pixels, each pixel having a given value, said values being stored in a memory, said method comprising the steps of:
(A) determining the properties including local properties of the digital image;
(B) filtering the input digital image, said filtering having as output a filtered value at each pixel;
(C) obtaining the difference between the value at the pixel and the filtered value at the pixel, said difference being a threshold input;
(D) generating the output state for the pixel depending upon the relationship of the value of said threshold input relative to a threshold;
(E) producing an error value, said error value being indicative of the deviation of said threshold input from the output state;
(F) multiplying said error value by a coefficient, the result of said multiplication being stored;
(G) combining the stored value with the difference between the next pixel value and the next filtered value to produce a new threshold input;
(H) repeating steps (D) through (G) for each pixel in the digital image thereby producing a halftone image; and
varying the threshold according to properties of the digital image; and
selectively changing the coefficient in step (E) according to the local properties of the digital image.
2. The method of claim 1 further comprising the step of:
performing a histogram modification of the image pixels, before step (B).
3. The method of claim 1 further comprising the step of:
performing a histogram modification of the difference between the value at the pixel and the filtered value at the pixel, before step (D).
4. The method of claim 1 wherein the selectively changing of the coefficient comprises:
dividing a first function of the local values of the digital image by a second function of the local values of the digital image; and
multiplying the absolute value of the result of said division by a first parameter; and
adding a second parameter to the result of the multiplication, thereby obtaining the coefficient.
5. The method of claim 4 wherein said first function is the difference between the value at the pixel and the filtered value at the pixel and said second function is the filtered value at the pixel.
6. The method of claim 4 wherein the threshold is a third function of the local values of the digital image.
7. The method of claim 6 wherein said third function is a linear function of the local values of the digital image.
8. The method of claim 6 wherein said third function is a linear function of the local values of the digital image.
9. The method of claim 4 wherein the threshold is the filtered value at the pixel multiplied by a third parameter.
10. The method of claim 9 wherein the filter in step (B) is a filter of finite extent, the extent of the filter, the first, second parameters and third parameters being selected to produce the image of highest perceptual quality at a specific output device.
11. The method of claim 9 further comprising the step of:
performing a histogram modification of the difference between the value at the pixel and the filtered value at the pixel, before step (D).
12. The method of claim 1 wherein the input digital image is a monochrome image.
13. The method of claim 1 wherein the input digital image is a color image.
14. A system for generating a halftone image from an input digital image, said digital image represented by a multiplicity of pixels, each pixel having a given value, said values being stored in a memory, said apparatus comprising:
means for determining the properties including local properties of said digital image; and
means for retrieving the pixel values; and
means for filtering the input digital image, said filtering having as output a filtered value at each pixel; and
means for obtaining the difference between the value at the pixel and the filtered value at the pixel, said difference being a threshold input; and
means for producing an error value, said error value being indicative of the deviation of said threshold input from the output state; and
means for multiplying said error value by an adaptation coefficient to obtain a diffused value and
means for storing the diffused value and delaying said stored value by one pixel; and
means for combining the stored delayed diffused value with the difference between the pixel value and the filtered value; and
means for varying the threshold according to the properties of the digital image at the pixel value; and
means for selectively changing the adaptation coefficient according to the local properties of the digital image.
15. The system of claim 14 further comprising:
means performing a histogram modification of the image pixels.
16. The system of claim 14 further comprising:
means for performing a histogram modification of the difference between the value at the pixel and the filtered value at the pixel.
17. The system of claim 14 wherein the means for selectively changing of the adaptation coefficient comprise:
means for dividing a first function of the local values of the digital image by a second function of the local values of the digital image; and
means for multiplying the absolute value of the result of said division by a first parameter; and
adding a second parameter to the result of the multiplication, thereby obtaining the coefficient.
18. A computer program product comprising:
a computer usable medium having computer readable code embodied therein for generating a halftone image from an input digital image, said digital image represented by a multiplicity of pixels, each pixel having a given value, said values being stored in a memory, said code causing a computer system to:
determine the properties including local properties of said digital image; and
retrieve the pixel values; and
filter the digital image, said filtering having as output a filtered value at each pixel; and
obtain the difference between the value at the pixel and the filtered value at the pixel, said difference being a threshold input; and
produce an error value, said error value being indicative of the deviation of said threshold input from the output state; and
multiply said error value by an adaptation coefficient to obtain a diffused value; and
store the diffused value and delaying said stored value by one pixel; and
combine the stored delayed diffused value with the difference between the pixel value and the filtered value; and
vary the threshold according to the properties of the digital image at the pixel value; and
selectively change the adaptation coefficient according to the local properties of the digital image.
19. The computer program product of claim 18 where, the computer readable code further causes the computer system to:
perform a histogram modification of the image pixels.
20. The computer program product of claim 18 where, the computer readable code further causes the computer system to:
perform a histogram modification of the difference between the value at the pixel and the filtered value at the pixel.
21. The computer program product of claim 18 where, the computer readable code in causing the computer system to selectively change the adaptation coefficient, further causes the computer system to:
divide a first function of the local values of the digital image by a second function of the local values of the digital image; and
multiply the absolute value of the result of said division by a first parameter; and
add a second parameter to the result of the multiplication, thereby obtaining the coefficient.
22. The computer program product of claim 21 wherein said first function is the difference between the value at the pixel and the filtered value at the pixel and said second function is the filtered value at the pixel.
23. The computer program product of claim 22 wherein said the threshold is the filtered value at the pixel multiplied by a third parameter.
24. The computer program product of claim 23 wherein the filter used to filter the digital image is a filter of finite extent, the extent of the filter, the first, second parameters and third parameters being selected to produce the image of highest quality at a specific output device.
25. The computer program product of claim 25 where, the computer readable code further causes the computer system to:
perform a histogram modification of the difference between the value at the pixel and the filtered value at the pixel.
26. The computer program product of claim 21 wherein the threshold is a third function of the local values of the digital image.
27. The computer program product of claim 26 wherein said third function is a linear function of the local values of the digital image.
28. The computer program product of claim 26 wherein said third function is a linear function of the local values of the digital image.
29. The computer program product of claim 18 wherein the input digital image is a color image.
30. The computer program product of claim 18 wherein the input digital image is a monochrome image.