Methods and devices for data compression with adaptive filtering in the transform domain

• US 8,577,159 B2
• Filed: 09/14/2011
• Issued: 11/05/2013
• Est. Priority Date: 09/14/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Yu, Xiang, He, Dake, Yang, En-hui
• Primary Examiner(s): Do, Anh
• Application Number:
  US13/232,057
• Publication Number:
  US 20120063691A1
• Time in Patent Office: 783 Days
• Field of Search: 382/232, 382/233, 382/236, 382/238, 382/248, 382/250, 382/260, 382/275, 382/279, 348/398.1, 348/411.1, 375/240, 379/406.1, 600/437, 600/443, 704/205, 704/229
• US Class Current: 382/232
• CPC Class Codes: H04N 19/117 Filters, e.g. for pre-processing or post-processing sub-band filter banks H04N19/635
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/463 by compressing encoding parameters before transmission
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/82 involving filtering within a prediction loop

Abstract

Methods and devices for encoding and decoding data using adaptive transform domain filtering are described. The encoder determines a set of transform domain filter coefficients to be applied to a transform domain prediction. The filtering may, in some cases, also apply to quantized transform domain coefficients. Rate-distortion optimization may be used to determine the optimal filter coefficients on a frame-based, coding-unit-basis, or other basis.

Claims

1. A method of encoding an image in an encoding device using a processor, the image including blocks of samples, the method comprising:

spectrally transforming the blocks of samples to obtain blocks of transform coefficients;

for each of the blocks of samples, spectrally transforming a block of prediction samples to obtain a block of prediction transform coefficients;

generating a block of transform domain filter coefficients based upon the blocks of transform coefficients and the blocks of prediction transform coefficients; and

for each of the blocks of transform coefficients, calculating filtered transform domain residuals by applying the block of transform domain filter coefficients to at least a portion of the block of prediction transform coefficients associated with that block of transform coefficients.

2. The method claimed in claim 1, wherein the image is part of a video, and wherein the method further comprises performing motion estimation to select the blocks of prediction samples, and wherein blocks of prediction samples are reference blocks of reconstructed pixels from one or more previously encoded frames.

3. The method claimed in claim 1, further comprising performing spatial compensation to select the blocks of prediction samples, and wherein the blocks of prediction samples are reference blocks of samples determined based upon values adjacent the block of samples in the image.

4. The method claimed in claim 1, wherein generating the block of transform domain filter coefficients comprises calculating, for at least some of the coefficient positions in the block, a ratio, a numerator of the ratio including a sum of the product of values in the corresponding position of the blocks of transform coefficients and values in the corresponding position of the blocks of prediction transform coefficients, and a denominator of the ratio including a sum of the square of the values in the corresponding position of the blocks of prediction transform coefficients.

5. The method claimed in claim 1, wherein generating the block of transform domain filter coefficients comprises calculating, for at least some of the coefficient positions in the block, a ratio in accordance with the expression:

6. The method claimed in claim 1, wherein the generating the block of transform domain filter coefficients, f, comprises finding the filter coefficients f that minimize the expression:

Σ

_k,ij|c_xk,ij−

f_ij*(c_pk,ij+Q<sup>−

1</sup>(u_k,ij))|²

wherein c_xk,ij comprises the value at the ij^th coefficient position in the kth block of transform coefficients, c_pk,ij comprises the value at the ij^th coefficient position of the kth block of prediction transform coefficients, u_k,ij comprises a ij^th quantized transform domain coefficient in the kth block, and Q<sup>−

1</sup>(•

) comprises a dequantization function.

7. The method claimed in claim 1, wherein the generating the block of transform domain filter coefficients, f, comprises finding the filter coefficients f that minimize the expression:

Σ

_k,ij|c_xk,ij−

f_ij*c_pk,ij|²

wherein c_xk,ij comprises the value at the ij^th coefficient position in the kth block of transform coefficients, and c_pk,ij comprises the value at the ij^th coefficient position of the kth block of prediction transform coefficients.

8. The method claimed in claim 1, wherein generating the block of transform domain filter coefficients is performed once per coding unit or frame.

9. The method claimed in claim 1, further comprising entropy encoding at least some of the transform domain filter coefficients within a bitstream, by, for each of the at least some of the transform domain filter coefficients, encoding an index based upon a difference between that transform domain filter coefficient and a prediction.

10. A non-transitory computer-readable medium storing computer-executable instructions which, when executed by a processor, configure the processor to perform the method claimed in claim 1.

11. The method claimed in claim 1, wherein calculating the filtered transform domain residual comprises calculating a filtered prediction by scaling at least a portion of the block of prediction transform coefficients by the filter coefficients, and wherein the filtered transform domain reconstruction comprises the difference between the filtered prediction and the block of transform coefficients.

12. A method of filtering for use in a decoder for reconstructing a block of samples for an image, wherein the decoder has a predictive block of samples associated with the block of samples, the method comprising:

spectrally transforming the predictive block of samples to obtain a transformed prediction block;

calculating a filtered transform domain reconstruction by applying a block of filter coefficients to at least a portion of the transformed prediction block.

13. The method claimed in claim 12, wherein calculating the filtered transform domain reconstruction comprises calculating a filtered prediction by scaling at least a portion of the transformed prediction block by the filter coefficients and dequantizing a block of quantized transform domain coefficients, and wherein the filtered transform domain reconstruction comprises the sum of the filtered prediction and the dequantized block of transform domain coefficients.

14. The method claimed in claim 12, wherein calculating the filtered transform domain reconstruction comprises:

dequantizing a block of quantized transform domain coefficients;

calculating a transform domain reconstruction block as the transformed prediction block plus the dequantized block of transform domain coefficients; and

scaling the transform domain reconstruction block using the filter coefficients.

15. The method claimed in claim 14, wherein scaling comprises element-wise multiplication.

16. The method claimed in claim 12, further comprising extracting the filter coefficients from an input bitstream, wherein extracting comprises entropy decoding the input bitstream to recover the filter coefficients.

17. A method of decoding a bitstream to reconstruct an image, the method comprising:

entropy decoding the bitstream to obtain a block of quantized transform domain coefficients, the filter coefficients, and prediction data;

identifying the predictive block of samples based on the prediction data;

obtaining the filtered transform domain reconstruction using the method claimed in claim 12; and

inverse transforming the filtered transform domain reconstruction to output a block of reconstructed samples.

18. The method claimed in claim 17, wherein the prediction data includes a motion vector, and wherein identifying the predictive block of samples includes performing motion compensation to select a reference block from a reference frame, and wherein spectrally transforming comprises transforming the reference block.

19. A non-transitory computer-readable medium storing computer-executable instructions which, when executed by a processor, configure the processor to perform the method claimed in claim 12.

20. An encoder for calculating filter coefficients for use in encoding an image, the image including blocks of samples, the encoder comprising:

a processor;

a memory storing the blocks of samples; and

an encoding application stored in memory and containing instructions for configuring the processor to

spectrally transform the blocks of samples to obtain blocks of transform coefficients,

for each of the blocks of samples, spectrally transform a block of prediction samples to obtain a block of prediction transform coefficients,

generate a block of transform domain filter coefficients based upon the blocks of transform coefficients and the blocks of prediction transform coefficients, and

for each of the blocks of transform coefficients, calculate filtered transform domain residuals by applying the block of transform domain filter coefficients to at least a portion of the block of prediction transform coefficients associated with that block of transform coefficients.

21. The encoder claimed in claim 20, wherein the image is part of a video, and wherein the processor is further configured to perform motion estimation to select the blocks of prediction samples, and wherein blocks of prediction samples are reference blocks of reconstructed pixels from one or more previously encoded frames.

22. The encoder claimed in claim 20, wherein the processor is further configured to perform spatial compensation to select the blocks of prediction samples, and wherein the blocks of prediction samples are reference blocks of samples determined based upon values adjacent the block of samples in the image.

23. The encoder claimed in claim 20, wherein the processor is further configured to generate the block of transform domain filter coefficients by calculating, for at least some of the coefficient positions in the block, a ratio, a numerator of the ratio including a sum of the product of values in the corresponding position of the blocks of transform coefficients and values in the corresponding position of the blocks of prediction transform coefficients, and a denominator of the ratio including a sum of the square of the values in the corresponding position of the blocks of prediction transform coefficients.

24. The encoder claimed in claim 20, wherein the processor is further configured to generate the block of transform domain filter coefficients by calculating, for at least some of the coefficient positions in the block, a ratio in accordance with the expression:

25. The encoder claimed in claim 20, wherein the processor is further configured to generate the block of transform domain filter coefficients by finding the filter coefficients f that minimize the expression:

Σ

_k,ij|c_xk,ij−

f_ij*(c_pk,ij+Q<sup>−

1</sup>(u_k,ij))|²

wherein c_xk,ij comprises the value at the ij^th coefficient position in the kth block of transform coefficients, c_pk,ij comprises the value at the ij^th coefficient position of the kth block of prediction transform coefficients, u_k,ij comprises a ij^th quantized transform domain coefficient in the kth block, and Q<sup>−

1</sup>(•

) comprises a dequantization function.

26. The encoder claimed in claim 20, wherein the processor is further configured to generate the block of transform domain filter coefficients by finding the filter coefficients f that minimize the expression:

Σ

_k,ij|c_xk,ij−

f_ij*c_pk,ij|²

wherein c_xk,ij comprises the value at the ij^th coefficient position in the kth block of transform coefficients, and c_pk,ij comprises the value at the ij^th coefficient position of the kth block of prediction transform coefficients.

27. The encoder claimed in claim 20, wherein the processor is configured to generate the block of transform domain filter coefficients once per coding unit or frame.

28. The encoder claimed in claim 20, wherein the processor is further configured to entropy encoding at least some of the transform domain filter coefficients within a bitstream, by, for each of the at least some of the transform domain filter coefficients, encoding an index based upon a difference between that transform domain filter coefficient and a prediction.

29. The encoder claimed in claim 20, wherein the processor is to calculate the filtered transform domain residual by calculating a filtered prediction by scaling at least a portion of the block of prediction transform coefficients by the filter coefficients, and wherein the filtered transform domain reconstruction comprises the difference between the filtered prediction and the block of transform coefficients.

30. A decoder for filtering during reconstruction of a block of samples for an image, wherein the decoder has a predictive block of samples associated with the block of samples, the decoder comprising:

a processor;

a memory; and

a decoding application stored in memory and containing instructions for configuring the processor to

spectrally transform the predictive block of samples to obtain a transformed prediction block, and

calculate a filtered transform domain reconstruction by applying a block of filter coefficients to at least a portion of the transformed prediction block.

31. The decoder claimed in claim 30, wherein the processor is configured to calculate the filtered transform domain reconstruction through calculating a filtered prediction by scaling at least a portion of the transformed prediction block by the filter coefficients and dequantizing a block of quantized transform domain coefficients, and wherein the filtered transform domain reconstruction comprises the sum of the filtered prediction and the dequantized block of transform domain coefficients.

32. The decoder claimed in claim 30, wherein the processor is configured to calculate the filtered transform domain reconstruction by:

dequantizing a block of quantized transform domain coefficients;

calculating a transform domain reconstruction block as the transformed prediction block plus the dequantized block of transform domain coefficients; and

scaling the transform domain reconstruction block using the filter coefficients.

33. The decoder claimed in claim 32, wherein scaling comprises element-wise multiplication.

34. The decoder claimed in claim 30, wherein the processor is further configured to extract the filter coefficients from an input bitstream by entropy decoding the input bitstream to recover the filter coefficients.

35. The decoder claimed in claim 30, wherein the processor is further configured to reconstruct the image by:

entropy decoding the bitstream to obtain a block of quantized transform domain coefficients, the filter coefficients, and prediction data;

identifying the predictive block of samples based on the prediction data; and

inverse transforming the filtered transform domain reconstruction to output a block of reconstructed samples.

36. The decoder claimed in claim 35, wherein the prediction data includes a motion vector, and wherein the processor is configured to identify the predictive block of samples by performing motion compensation to select a reference block from a reference frame, and to spectrally transform by transforming the reference block.