Image encoding using reordering and blocking of wavelet coefficients combined with adaptive encoding
View Patent ↗An encoder reorders quantized wavelet coefficients to cluster large and small wavelet coefficients into separate groups without requiring the use of data-dependent data structures. The coefficients are then adaptively encoded based on a run-length code which continuously modifies a parameter that controls the codewords uses to represent strings of quantized coefficients, seeking to minimize the number of bits spent in the codewords. A matrix of indices contains the coarsest coefficients in the upper left corner, and filling in low high and high low sub bands in larger and larger blocks in an alternating manner, such that low high sub bands comprise the top of the matrix and the high low sub bands comprise the left side of the matrix. The shortest codewords are assigned to represent a run of the most likely character having length of 2 k , where k is a parameter. k is adjusted based on successive characters being encountered. k is increased when the character is the same, and decreased when the character is different. A decoder applies the above in reverse order. Decoding of the encoded coefficients is first performed, followed by an unshuffling of the coefficients. The unshuffled coefficients are then subjected to an inverse wavelet transform to recover the transformed and compressed data, such as image pixels.
1. A method of encoding image data comprising:
generating coefficients via a wavelet transformation;
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner; and
encoding the reordered coefficients using an adaptive run-length encoder.
2. The method of claim 1 wherein the reordering is selected to increase the likelihood of clustering large and small wavelet coefficients into separate groups without requiring the use of data-dependent data structures.
3. The method of claim 1 wherein portions of the reordering alternates quadrants when ordering blocks from low-high and high-low subbands at each wavelet tree level.
4. The method of claim 1 wherein the run-length encoding of the reordered coefficients is an adaptive run-length Golomb-Rice encoder controlled by a parameter k, which determines the maximum run lengths.
5. The method of claim 4 wherein the encoding parameter k increases each time the most frequent character is encountered.
6. The method of claim 4 wherein the encoding parameter k decreases each time the most frequent character is not encountered.
7. The method of claim 1 wherein the coefficients are arranged in blocks, and wherein portions of the reordering alternates quadrants when ordering blocks from low-high and high-low subbands at each wavelet tree level.
8. The method of claim 7 wherein the image has a size of M by N with a corresponding number of wavelet coefficients.
9. The method of claim 8 wherein the block size is M/2 J by N/2 J , where J is selected such that a zero level block contains all wavelet coefficients at the coarsest resolution.
10. A computer readable medium having instructions stored thereon causing a computer to perform the method of claim 1 .
11. The method of claim 1 wherein the coefficients are arranged in blocks, and wherein the blocks are grouped to ensure that pairs of blocks from a low-high and high-low subband corresponding to a same spatial location are proximate each other.
12. A method of encoding wavelet coefficients corresponding to image data comprising:
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner; and
encoding the reordered coefficients by means of an adaptive run-length encoder.
13. A method of encoding wavelet coefficients corresponding to image data comprising:
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner; and
performing arithmetic encoding of the reordered coefficients to provide an encoded bit stream.
14. The method of claim 13 wherein the coefficients are arranged in blocks, and wherein portions of the reordering alternates quadrants when ordering blocks from low-high and high-low subbands at each wavelet tree level.
15. The method of claim 14 wherein the image has a size of M by N with a corresponding number of wavelet coefficients.
16. The method of claim 15 wherein the block size is M/2 J by N/2 J , where J is selected such that a zero level block contains all wavelet coefficients at the coarsest resolution.
17. A computer readable medium having instructions stored thereon causing a computer to perform the method of claim 13 .
18. A method of decoding compressed pixel image data comprising:
receiving a bit stream compressed using an adaptive run-length Golomb-Rice encoding scheme;
decoding the received bit stream to produce wavelet transform coefficients which have been reordered to increase the likelihood of groupings of similar data in a data independent manner; and
changing the order of the coefficients back to an original order resulting from the wavelet transform of pixel data.
19. The decoder of claim 18 and further comprising means for inverse transforming the wavelet coefficients.
20. A method of encoding image data comprising:
generating coefficients via a wavelet transformation;
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner;
initializing a maximum string length for an adaptive run-length encoder;
modifying the maximum string length based on a control parameter; and
run-length encoding the symbols to provide a compressed output bit stream.
21. A computer readable medium having instructions stored thereon causing a computer to perform a method of encoding image data comprising:
generating coefficients via a wavelet transformation;
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner;
initializing a maximum string length for an adaptive run-length encoder;
modifying the maximum string length based on a control parameter; and
run-length encoding the symbols to provide a compressed output bit stream.
22. A method of encoding image data comprising:
generating coefficients via a wavelet transformation;
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner;
initializing a maximum string length for an adaptive run-length encoder;
modifying the maximum string length based on the occurrence of the most frequent symbol; and
run-length encoding the symbols to provide a compressed output bit stream.
23. The method of claim 22 wherein the symbols are encoded on a bit plane basis.
24. The method of claim 23 wherein the least significant bit planes are encoded using binary encoding.
25. A method of encoding image data comprising:
generating coefficients via a wavelet transformation;
reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner;
initializing a string length for an adaptive run-length encoder;
modifying the string length by a power, k, wherein k is based on the occurrence of the most frequent symbol;
increasing k each time the most frequent symbol is encoded; and
decreasing k each time a symbol other than the most frequent symbol is encoded, wherein the symbols are encoded on a bit plane basis.
26. The method of claim 25 wherein k is an integer, and wherein a scaling factor, L, is used to increment k a fraction at a time.
27. An encoder for encoding finite-alphabet data comprising:
means for generating coefficients via a wavelet transformation;
means for reordering the coefficients to increase the likelihood of groupings of similar data in a data independent manner;
means for initializing a maximum string length for an adaptive run-length encoder;
means for modifying the maximum string length by a power, k, wherein k is based on the occurrence of the most frequent symbol;
means for increasing k each time the most frequent symbol is encoded; and
means for decreasing k each time a symbol other than the most frequent symbol is encoded, wherein the symbols are encoded on a bit plane basis.
28. A method of decoding compressed pixel image data comprising:
receiving a bit stream compressed using an adaptive run-length Golomb-Rice encoding scheme;
decoding selected portions of the received bit stream to produce a set of most significant wavelet transform coefficients which have been reordered to increase the likelihood of groupings of similar data in a data independent manner; and
changing the order of the coefficients back to an original order resulting from the wavelet transform of pixel data.
29. A decoder for decoding compressed pixel image data comprising:
means for receiving a bit stream compressed using an adaptive run-length Golomb-Rice encoding scheme;
means for decoding selected portions of the received bit stream to produce a set of most significant wavelet transform coefficients which have been reordered to increase the likelihood of groupings of similar data in a data independent manner; and
means for changing the order of the coefficients back to an original order resulting from the wavelet transform of pixel data.