Rendering images utilizing adaptive error diffusion

Abstract

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 input 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 one or more properties including local properties of the input 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 a pixel and the filtered value at the pixel, said difference being a threshold input; 
 (D) generating the an 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) the generating an output state, the producing an error value, the multiplying said error value, and the combining the stored error value for each pixel in the input digital image thereby producing a halftone image; and 
 varying the threshold according to the one or more properties of the input digital image; and 
 selectively changing the coefficient in step (E) according to the local one or more properties of the input digital image. 
 
     
     
       2. The method of  claim 1  further comprising the step of:
 performing a histogram modification of the image pixels, before step (B) filtering the input digital image. 
 
     
     
       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) generating the output state. 
 
     
     
       4. The method of  claim 1  wherein the selectively changing of the coefficient comprises:
 dividing a first function of the local pixel values of the input digital image by a second function of the local pixel values of the input 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 pixel values of the input digital image. 
     
     
       7. The method of  claim 6  wherein said third function is a linear function of the local pixel values of the input 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 filtering comprises using a filter of finite extent, the extent of the filter, the first parameter, the second parameters parameter and the third parameters parameter being selected to produce the an 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) generating the output state. 
 
     
     
       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 input digital image represented by a multiplicity of pixels, each pixel having a given value, said values being stored in a memory, said apparatus system comprising:
 means for determining the one or more properties including local properties of said input 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 a 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 an 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 diffused 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 a threshold according to the one or more properties of the input digital image at the pixel value; and 
 means for selectively changing the adaptation coefficient according to the local one or more properties of the input 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 pixel values of the input digital image by a second function of the local pixel values of the input 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 adaptation coefficient. 
 
     
     
       18. A computer program product comprising:
 a computer usable storage medium having computer readable code embodied therein for generating a halftone image from an input digital image, said input digital image represented by a multiplicity of pixels, each pixel having a given value, said values being stored in a memory, said code causing comprising instructions for a computer system to:, the instructions comprising: 
 instructions to determine theone or more properties including local properties of said input digital image; and 
 instructions to retrieve the pixel values; and 
 instructions to filter the input digital image, said filtering having as output a filtered value at each pixel; and 
 instructions to obtain the difference between the value at thea pixel and the filtered value at the pixel, said difference being a threshold input; and 
 instructions to produce an error value, said error value being indicative of the deviation of said threshold input from thean output state; and 
 instructions to multiply said error value by an adaptation coefficient to obtain a diffused value; and 
 instructions to store the diffused value and delayingdelay said stored diffused value by one pixel; and 
 instructions to combine the stored delayed diffused value with the difference between the pixel value and the filtered value; and 
 instructions to vary thea threshold according to the one or more properties of the input digital image at the pixel value; and 
 instructions to selectively change the adaptation coefficient according to the localone or more properties of the input digital image. 
 
     
     
       19. The computer program product of  claim 18  where, the computer readable code further causes the computer system to wherein the instructions further comprise:
 instructions 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 wherein the instructions further comprise:
 instructions 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 wherein the instructions to selectively change the adaptation coefficient, further causes the computer system to comprise:
 instructions to divide a first function of the localpixel values of the input digital image by a second function of the localpixel values of the input digital image; and 
 instructions to multiply the absolute value of the result of said division by a first parameter; and 
 instructions to add a second parameter to the result of the multiplication, thereby obtaining the adaptation 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 input digital image is a filter of finite extent, the extent of the filter, the first parameter, the second parameters parameter and third parameters parameter being selected to produce the an 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 18 wherein the instructions further comprise:
 instructions 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 pixel values of the input digital image. 
     
     
       27. The computer program product of  claim 26  wherein said third function is a linear function of the local pixel values of the input 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. 
     
     
       31. The system of claim 14, further comprising: a rendering device. 
     
     
       32. The system of claim 31, wherein said rendering device is a binary output device. 
     
     
       33. The system of claim 31, wherein said rendering device is a M-ary display or a M-ary rendering device. 
     
     
       34. The system of claim 31, wherein said rendering device is a mobile phone display. 
     
     
       35. A mobile device capable of generating a halftone image from an input digital image, said input digital image represented by a multiplicity of pixels, each pixel having a given value, said mobile device comprising:
 means for determining one or more properties of said input digital image;   means for retrieving the pixel values;   means for filtering the input digital image, said filtering having as output a filtered value at each pixel;   means for obtaining the difference between the value at a pixel and the filtered value at the pixel, said difference being a threshold input;   means for producing an error value, said error value being indicative of the deviation of said threshold input from an output state;   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 diffused value by one pixel;   means for combining the stored delayed diffused value with the difference between the pixel value and the filtered value;   means for varying a threshold according to the one or more properties of the input digital image at the pixel value;   means for selectively changing the adaptation coefficient according to the one or more properties of the input digital image; and   a rendering device.