System and method for dynamically shifting error diffusion data
View Patent ↗Error diffusion is performed using a Floyd-Steinberg-like approach. A integer-representation of a running error is compressed by storing only its most significant bits and returning any remainder to the error diffusion processor. The running error is shifted to the right until only the desired number of significant bits remain, and this compressed error is stored. Any portion of the original running error that is lost due to the shifting is treated as a remainder and is returned to the error diffusion processor for use in calculating an adjusted current pixel value. The amount of the shift is retained in compressed form to keep track of the number of shifts needed to form a truncated running error from the compressed running error.
1. An error diffusion system configured to perform halftoning of image pixel data, the system comprising:
an error diffusion processor configured to receive a current pixel from a current image line and output an error diffused current pixel in response thereto;
a first decompressor connected to the error diffusion processor and configured to decompress a compressed previous running error of a pixel belonging to a previous line of said image for use in calculating an adjusted pixel value of said current pixel; and
a first compressor connected to the error diffusion processor and configured to compress a current running error of said current pixel to thereby form a compressed current running error for said current pixel.
2. The error diffusion system according to claim 1 , further comprising:
a second compressor configured to compress first information received from the first compressor, the first information sufficient to decompress said compressed current running error.
3. The error diffusion system according to claim 2 , wherein:
the second compressor employs run length encoding to compress said first information.
4. The error diffusion system according to claim 1 , wherein:
said current running error comprises N bits;
said first compressor retains a maximum of m most significant bits of the N bits to form said compressed current running error; and
N and m are both integers greater than 0 with N>m.
5. The error diffusion system according to claim 4 , wherein N is 16 and m is 8.
6. The error diffusion system according to claim 4 , wherein:
the first compressor shifts said current running error by a corresponding shift value so as to retain a maximum of m most significant bits.
7. The error diffusion system according to claim 4 , further comprising a second compressor configured to compress first information received from the first compressor, the first information sufficient to decompress said compressed current running error.
8. The error diffusion system according to claim 7 , wherein:
the first compressor shifts said current running error by a corresponding shift value so as to retain a maximum of m most significant bits; and
said first information comprises said corresponding shift value.
9. The error diffusion system according to claim 8 , wherein:
the second compressor employs run length encoding to compress said first information.
10. The error diffusion system according to claim 1 , further comprising:
a compressed running error buffer having a size sufficient to store a compressed running error for each image data pixel belonging to a line of image data.
11. The error diffusion system according to claim 1 , further comprising:
an error spread coefficient subsystem configured to provide error spread coefficients to the error diffusion processor.
12. The error diffusion system according to claim 11 , wherein the error spread coefficient subsystem comprises:
a first lookup table indexed by a pixel value of a current pixel being processed, each entry in the lookup table comprising a set of four error spread coefficients.
13. The error diffusion system according to claim 11 , wherein the error spread coefficient subsystem further comprises:
a coefficient spread buffer having a size sufficient to store three error spread coefficients for each pixel belonging to a line of image data.
14. The error diffusion system according to claim 13 , wherein the error spread coefficient subsystem further comprises:
a third compressor configured to compress a plurality of sets of at least three of said four error spread coefficients to thereby form compressed error spread data; and
a decompressor configured to selectively decompress said compressed error spread data.
15. The error diffusion system according to claim 11 , wherein the error spread coefficient subsystem further comprises:
a first lookup table indexed by a pixel value of a current pixel being processed, each entry in the first lookup table comprising a pointer to error spread data;
a third compressor configured to compress a plurality of said painters to thereby form compressed error spread pointer information;
a decompressor configured to selectively decompress said compressed error spread pointer information to thereby form at least one decompressed pointer; and
a coefficient array indexable by said at least one decompressed pointer.
16. The error diffusion system according to claim 1 , wherein:
the error diffusion processor, the first decompressor and the first compressor all belong to a single integrated circuit.
17. A method for handling running error values during a halftoning operation on an image, the method comprising:
decompressing a compressed previous running error of a pixel belonging to a previous line of said image to form a truncated previous running error for use in calculating an adjusted pixel value of a current pixel in a current line of an image; and
compressing a current running error of said current pixel in a current line of an image to thereby form a compressed running error for that pixel.
18. The method according to claim 17 , wherein:
said current running error comprises N bits;
said compressing step comprises retaining a maximum of m most significant bits of the N bits to form said compressed running error, where N and m are both integers greater than 0 with N>m.
19. The method according to claim 18 , wherein:
said compressing step comprises shifting said current running error by a corresponding shift value so as to retain a maximum of in most significant bits.
20. The method according to claim 19 , wherein:
N is 16 so that the current running error has bit positions in the range [15:0] with 0 designating the least significant bit; and
said compressing step comprises:
shifting the current running error to the right by 4 bits, if the most significant bit of the current running error is in a bit position lower than 12; and
shifting the current running error to the right by a number of bits sufficient to leave only in bits, if the most significant bit of the current running error is in bit position 12 or higher.
21. The method according to claim 19 , further comprising: compressing said corresponding shift value.