Methods and devices for data compression using adaptive reconstruction levels
View Patent ↗Encoding and decoding methods that perform quantization using adaptive reconstruction levels are presented. The reconstruction levels for a given partitioning of the data space may be selected based upon the distribution of data points within each sub-part defined by the partitioning. In some cases, the adaptive reconstruction levels may be based upon an average of the data points within each sub-part. In some cases, the adaptive reconstruction levels may be selected using a rate-distortion analysis including the quantization distortion associated with the levels versus the data points and the rate associated with transmitting the encoded adaptive reconstruction levels. The methods relate to data compression in a range of applications including audio, images and video.
1. A method for encoding of a sequence of data points using a lossy data compression process implemented by a processor, the method comprising:
assigning, with the processor, a quantization index u to each data point based on quantizing that data point using a quantizer for each quantization index u of at least some of the quantization indices, calculating, with the processor, an adaptive reconstruction level q u for that quantization index u that minimizes the joint cost of total distortion from quantization of the data points to that quantization index u and the rate of transmitting the adaptive reconstruction level q u , wherein the adaptive reconstruction level is based upon the actual data points quantized to that quantization index u;
encoding, using the processor, the adaptive reconstruction levels q u ; and
encoding, using the processor, for each data point, its respective assigned quantization index u,
wherein the sequence of data points comprise one of audio data, image data, and video data.
2. The method claimed in claim 1 , wherein quantizing each data point comprises quantizing that data point using a quantization step size specified by the quantizer.
3. The method claimed in claim 1 , wherein assigning a quantization index u to each data point comprises performing soft-decision quantization based on minimizing a rate-distortion cost expression given a fixed set of reconstruction levels.
4. The method claimed in claim 3 , wherein minimizing the rate-distortion cost expression comprises calculating:
min
u
c
-
u
·
q
2
+
λ
·
r
(
u
)
wherein u are the indices, c are the data points, q is the quantization step size, and r(u) is
the rate associated with transmitting the encoded indices.
5. The method claimed in claim 3 , wherein the fixed set of reconstruction levels comprise the respective products of each quantization index u and a quantization step size.
6. The method claimed in claim 3 , wherein the assigning and calculating operations are repeated, and wherein the adaptive reconstruction levels are used in place of the fixed set of reconstruction levels when repeating the assigning, and wherein the repeating occurs until a change in adaptive reconstruction level is less than a threshold amount.
7. The method claimed in claim 1 , wherein calculating the adaptive reconstruction levels is based upon minimizing the rate-distortion cost expression:
( c u,1 −u·q u ) 2 +( c u,2 −u·q u ) 2 + . . . +(c u,m −u·q u ) 2 +λ·r ( q u )
wherein c are the data points, u are the indices assigned, r( )is a rate function based on an entropy encoding scheme for the adaptive reconstruction levels q u , and m is an integer representing the number of data points assigned index u.
8. The method claimed in claim 1 , wherein the data points comprise transform domain coefficients, and wherein the method further comprises obtaining the transform domain coefficients by determining residual data in a prediction operation and transforming the residual data in a video encoding process.
9. The method claimed in claim 1 , wherein the data points comprise video data, and the sequence of data points comprise one of a slice, a frame, and a group-of-pictures.
10. A method of decoding encoded compressed data using a processor, wherein the compressed data results from a lossy data compression process, the method comprising:
entropy decoding, using the processor, the encoded compressed data to obtain indices u and adaptive reconstruction levels q u , wherein each index u obtained is a quantized data point from the lossy data compression process, and wherein each adaptive reconstruction level q u specifies a reconstruction level for dequantizing one of the indices u and is based upon the actual data points quantized to that index u; and
reconstructing, using the processor, each data point as the product of a respective index u obtained and the adaptive reconstruction level q u associated with that index, to produce a sequence of decoded data,
wherein the sequence of decoded data comprises one of audio data, image data, and video data.
11. The method claimed in claim 10 , wherein the compressed data comprises compressed video data, wherein the lossy data compression process comprises a video encoding process, and wherein the method further comprises inverse transforming the reconstructed sequence of decoded data to produce residual data, and performing a compensation operation on the residual data to produce reconstructed video data.
12. The method claimed in claim 10 , wherein the encoded compressed data includes a set of the adaptive reconstruction levels q u for use in reconstructing the sequence of decoded data, and wherein the sequence of decoded data represents a reconstruction of an input data sequence.
13. An encoder for encoding a sequence of data points using a lossy data compression process, the encoder comprising:
a processor;
a memory storing the data points; and
an encoding application stored in memory and containing instructions for configuring the processor to encode the data points by
assigning a quantization index u to each data point based on quantizing that data point using a quantizer for each quantization index u of at least some of the quantization indices, calculating an adaptive reconstruction level q u for that quantization index u that minimizes the joint cost of total distortion from quantization of the data points to that quantization index u and the rate of transmitting the adaptive reconstruction level q u , wherein the adaptive reconstruction level is based upon the actual data points quantized to that quantization index u;
encoding the adaptive reconstruction levels q u ; and
encoding, for each data point, its respective assigned quantization index u.
14. The encoder claimed in claim 13 , wherein quantizing each data point comprises quantizing that data point using the a quantization step size specified by the quantizer.
15. The encoder claimed in claim 13 , wherein the encoding application contains instructions for configuring the processor to assign the quantization indices u based on minimizing a rate-distortion cost expression given a fixed set of reconstruction levels.
16. The encoder claimed in claim 15 , wherein the encoding application contains instructions for configuring the processor to minimize the rate-distortion cost expression by calculating:
min
u
c
-
u
·
q
2
+
λ
·
r
(
u
)
wherein u are the indices, c are the data points, q is the quantization step size, and r(u) is the rate associated with transmitting the encoded indices.
17. The encoder claimed in claim 15 , wherein the fixed set of reconstruction levels comprise the respective products of each quantization index u and a quantization step size.
18. The encoder claimed in claim 15 , wherein instructions configure the processor to perform the assigning and calculating operations repeatedly, and wherein the adaptive reconstruction levels are used in place of the fixed set of reconstruction levels when repeating the assigning, and wherein the repeating occurs until a change in adaptive reconstruction level is less than a threshold amount.
19. The encoder claimed in claim 13 , wherein the encoding application contains instructions for configuring the processor to calculate the adaptive reconstruction levels based upon minimizing the rate-distortion cost expression:
( c u,1 −u·q u ) 2 +( c u,2 −u·q u ) 2 + . . . +(c u,m −u·q u ) 2 +λ·r ( q u )
wherein c are the data points, u are the indices assigned, r( )is a rate function based on an entropy encoding scheme for the adaptive reconstruction levels q u , and m is an integer representing the number of data points assigned index u.
20. The encoder claimed in claim 13 , wherein the data points comprise transform domain coefficients, and wherein the encoding application contains instructions for configuring the processor to obtain the transform domain coefficients by determining residual data in a prediction operation and to transform the residual data in a video encoding process.
21. The encoder claimed in claim 13 , wherein the sequence of data points comprise one of audio data, image data, and video data.
22. The encoder claimed in claim 21 , wherein the data points comprise video data, and the sequence of data points comprise one of a slice, a frame, and a group-of- pictures.
23. A decoder for decoding encoded compressed data, wherein the compressed data results from a lossy data compression process, the decoder comprising:
a processor;
a memory; and
a decoding application stored in memory and containing instructions for configuring the processor to decode the encoded compressed data using by
entropy decoding the encoded compressed data to obtain indices u and adaptive reconstruction levels q u , wherein each index u obtained is a quantized data point from the lossy data compression process, and wherein each adaptive reconstruction level q u specifies a reconstruction level for_dequantizing one of the indices u and is based on the actual data points quantized to that index u, and
reconstructing each_data point as the product of a respective index u obtained and the adaptive reconstruction level q u associated with that index, to produce a sequence of decoded data.
24. The decoder claimed in claim 23 , wherein the compressed data comprises compressed video data, wherein the lossy data compression process comprises a video encoding process, and wherein the decoding application contains instructions for configuring the processor to inverse transform the reconstructed sequence of decoded data to produce residual data, and to perform a compensation operation on the residual data to produce reconstructed video data.
25. The decoder claimed in claim 23 , wherein the encoded compressed data includes a set of the adaptive reconstruction levels q u for use in reconstructing the sequence of decoded data, and wherein the sequence of decoded data represents a reconstruction of an input data sequence.
26. The decoder claimed in claim 25 , wherein the input data sequence comprises one of an audio sample, an image frame, an image slice, a video frame, a video slice, and a video group-of-pictures.