Separable directional transforms

• US 8,619,853 B2
• Filed: 06/04/2008
• Issued: 12/31/2013
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Ye, Yan, Karczewicz, Marta
• Primary Examiner(s): Hamza, Faruk
• Assistant Examiner(s): DECKER, CASSANDRA L
• Application Number:
  US12/133,257
• Publication Number:
  US 20080310512A1
• Time in Patent Office: 2,036 Days
• Field of Search: None
• US Class Current: 375/240.02
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/11 among a plurality of spatial predictive coding modes
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• 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/157 Assigned coding mode, i.e. the coding mode being predefined or preselected to be further used for selection of another element or parameter
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• 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/197 including determination of the initial value of an encoding parameter H04N19/56 takes precedence
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• 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/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]
• CPC Class Codes: H04N 19/70 : characterised by syntax aspects related to video coding, e.g. related to compression standards

Abstract

This disclosure describes techniques for transforming residual blocks of video data. In particular, a plurality of different transforms selectively applied to the residual blocks based on the prediction mode of the video blocks. At least a portion of the plurality of transforms are separable directional transform specifically trained for a corresponding prediction mode to provide better energy compaction for the residual blocks of the given prediction mode. Using separable directional transforms offers the benefits of lower computation complexity and storage requirement than use of non-separable directional transforms. Additionally, a scan order used to scan the coefficients of the residual block may be adjusted when applying separable directional transforms. In particular, the scan order may be adjusted based on statistics associated with one or more previously coded blocks to better ensure that non-zero coefficients are grouped near the front of the one-dimensional coefficient vector to improve the effectiveness of entropy coding.

Claims

1. A method of coding video data, the method comprising:

selecting at least one transform of a plurality of transforms for a video block based on a directional prediction mode for predicting the video block, the directional prediction mode for the video block being one of a plurality of directional prediction modes, the plurality of transforms being used for transforming between residual pixel values of the video block and residual transform coefficients of the video block, wherein each of the plurality of transforms is associated with at least one directional prediction mode of the plurality of directional prediction modes and at least a portion of the plurality of transforms are separable directional transforms;

applying the selected at least one transform to the video block to transform between the residual pixel values of the video block and the residual transform coefficients of the video block; and

entropy coding the residual transform coefficients of the video block.

2. The method of claim 1, wherein the separable directional transforms each include a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

3. The method of claim 1, wherein the plurality of transforms further include a discrete cosine transform (DCT) or an integer transform, and selecting the at least one transform of the plurality of transforms for the video block comprises:

selecting the discrete cosine transform (DCT) or the integer transform to apply to the video block when the directional prediction mode for the video block exhibits limited directionality; and

selecting one of the plurality of the separable directional transforms to apply to the video block when the directional prediction mode for the video block exhibits significant directionality.

4. The method of claim 1, wherein coding video data comprises encoding the video data, wherein the plurality of transforms are transforms for use in transforming residual pixel values of the video block to residual transform coefficients, wherein the method further comprises:

generating a predicted video block based on the directional prediction mode for the video block; and

generating residual pixel values of the video block based on the predicted video block, and wherein;

applying the selected at least one transform comprises applying the selected at least one transform to the video block to transform the residual pixel values of the video block to the residual transform coefficients; and

entropy coding comprises entropy encoding the residual transform coefficients of the video block.

5. The method of claim 1, wherein coding video data comprises decoding the video data, wherein the plurality of transforms are inverse transforms for use in transforming residual transform coefficients to residual pixel values of the video block,

wherein entropy coding comprises entropy decoding the residual transform coefficients of the video block,

wherein applying the selected at least one transform comprises applying a selected inverse transform to the video block to transform the decoded residual transform coefficients to the residual pixel values of the video block, and

wherein the method further comprises:

generating a predicted video block based on the directional prediction mode for the video block; and

generating a reconstructed video block based on the residual pixel values of the video block and the predicted video block.

6. The method of claim 1, wherein each of the separable directional transforms is associated with respective directionality characteristics of one or more of the plurality of the directional prediction modes.

7. The method of claim 1, wherein selecting the at least one of the plurality of transforms based on the directional prediction mode comprises selecting, based on the directional prediction mode, at least one of a separable directional transform, a different separable transform, or a combination thereof.

8. The method of claim 7, wherein the different separable transform comprises one of a discrete cosine transform (DCT) or a DCT-like integer transform.

9. The method of claim 7, wherein the separable directional transform comprises a separable Karhunen—

Loè

ve Transform.

10. The method of claim 7, wherein the separable directional transform includes a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

11. The method of claim 1, wherein each of the plurality of directional prediction modes is associated with a scan order in a plurality of scan orders, the method further comprising:

selecting a scan order for the video block based on the directional prediction mode for the video block; and

scanning the residual transform coefficients of the video block using the selected scan order.

12. A device for coding video data, the device comprising:

a memory configured to;

store a plurality of transforms for use in transforming between residual pixel values of a video block and residual transform coefficients of the video block, wherein each of the plurality of transforms is associated with at least one directional prediction mode of a plurality of directional prediction modes and at least a portion of the plurality of transforms are separable directional transforms; and

a processor configured to;

select at least one transform of the plurality of transforms for the video block based on a directional prediction mode for predicting the video block, the directional prediction mode for the video block being one of the plurality of directional prediction modes;

apply the selected at least one transform to the video block to transform between the residual pixel values of the video block and the residual transform coefficients of the video block; and

entropy code the residual transform coefficients of the video block.

13. The device of claim 12, wherein the separable directional transforms each include a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

14. The device of claim 12, wherein the plurality of transforms further include a discrete cosine transform (DCT) or an integer transform, and the processor is further configured to:

select the discrete cosine transform (DCT) or the integer transform to apply to the video block when the directional prediction mode for the video block exhibits limited directionality, and

select one of the plurality of the separable directional transforms to apply to the video block when the directional prediction mode for the video block exhibits significant directionality.

15. The device of claim 12, wherein the plurality of transforms are transforms for use in transforming residual pixel values of the video block to residual transform coefficients, and further wherein:

the processor generates a predicted video block based on the directional prediction mode for the video block;

the processor generates the residual pixel values of the video block based on the predicted video block;

the processor applies the selected at least one transform to the video block to transform the residual pixel values of the video block to the residual transform coefficients; and

the processor entropy encodes the residual transform coefficients of the video block.

16. The device of claim 12, wherein the plurality of transforms are inverse transforms for use in transforming residual transform coefficients to residual pixel values of the video block and the selected at least one transform is a selected inverse transform, and further wherein:

the processor is configured to entropy decode the residual transform coefficients of the video block;

the processor is configured to apply the selected inverse transform to the video block to transform the residual transform coefficients to the residual pixel values of the video block; and

the processor is configured to generate a predicted video block based on the directional prediction mode for the video block; and

the processor is configured to generate a reconstructed video block based on the residual pixel values of the video block and the predicted video block.

17. The device of claim 12, wherein the device comprises a wireless communication device having a display.

18. The device of claim 12, wherein the device comprises an integrated circuit device.

19. The device of claim 12, wherein each of the separable directional transforms is associated with respective directionality characteristics of one or more of the plurality of the directional prediction modes.

20. The device of claim 12, wherein the processor is further configured to select, based on the directional prediction mode, at least one of a separable directional transform, a different separable transform, or a combination thereof.

21. The device of claim 20, wherein the different separable transform comprises one of a discrete cosine transform (DCT) or a DCT-like integer transform.

22. The device of claim 20, wherein the separable directional transform comprises a separable Karhunen—

Loè

ve Transform.

23. The device of claim 20, wherein the separable directional transform includes a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

24. The device of claim 12, wherein each of the plurality of directional prediction modes is associated with a scan order in a plurality of scan orders, and wherein the processor is further configured to:

select a scan order for the video block based on the directional prediction mode for the video block; and

scan the residual transform coefficients of the video block using the selected scan order.

25. A non-transitory computer-readable medium upon which is stored instructions that upon execution in a device cause the device to code video blocks, wherein the instructions cause the device to:

store a plurality of transforms for use in transforming between residual pixel values of a video block and residual transform coefficients of the video block, wherein each of the plurality of transforms is associated with at least one directional prediction mode of a plurality of directional prediction modes and at least a portion of the plurality of transforms are separable directional transforms;

select at least one transform of the plurality of transforms for the video block based on a directional prediction mode for predicting the video block, the directional prediction mode for the video block being one of the plurality of directional prediction modes;

apply the selected at least one transform to the video block to transform between the residual pixel values of the video block and the residual transform coefficients of the video block; and

entropy code the residual transform coefficients of the video block.

26. The non-transitory computer-readable medium of claim 25, wherein the separable directional transforms each include a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

27. The non-transitory computer-readable medium of claim 25, wherein the plurality of transforms further include a discrete cosine transform (DCT) or an integer transform, and the instructions cause the device to:

select the discrete cosine transform (DCT) or the integer transform to apply to the video block when the directional prediction mode for the video block exhibits limited directionality; and

select one of the plurality of the separable directional transforms to apply to the video block when the directional prediction mode for the video block exhibits significant directionality.

28. The non-transitory computer-readable medium of claim 25, wherein the device comprises an encoder device, wherein the plurality of transforms are transforms for use in transforming residual pixel values of the video block to residual transform coefficients, and further wherein the instructions cause the encoder device to:

apply the selected at least one transform to the video block to transform the residual pixel values of the video block to the residual transform coefficients; and

entropy encode the residual transform coefficients of the video block after applying the selected at least one transform.

29. The non-transitory computer-readable medium of claim 25, wherein the device comprises a decoder device, wherein the plurality of transforms are inverse transforms for use in transforming residual transform coefficients to residual pixel values of the video block and the selected at least one transform is a selected inverse transform, and further wherein the instructions cause the decoder device to:

apply the selected inverse transform to the video block to transform the residual transform coefficients to the residual pixel values of the video block; and

entropy decode the residual transform coefficients of the video block prior to applying the selected inverse transform.

30. The non-transitory computer-readable medium of claim 25, wherein each of the separable directional transforms is associated with respective directionality characteristics of one or more of the plurality of the directional prediction modes.

31. The non-transitory computer-readable medium of claim 25, wherein the instructions cause the device to select, based on the directional prediction mode, at least one of a separable directional transform, a different separable transform, or a combination thereof.

32. The non-transitory computer-readable medium of claim 31, wherein the different separable transform comprises one of a discrete cosine transform (DCT) or a DCT-like integer transform.

33. The non-transitory computer-readable medium of claim 31, wherein the separable directional transform comprises a separable Karhunen—

Loè

ve Transform.

34. The non-transitory computer-readable medium of claim 31, wherein the separable directional transform includes a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

35. The non-transitory computer-readable medium of claim 25, wherein each of the plurality of directional prediction modes is associated with a scan order in a plurality of scan orders, and wherein the instructions cause the device to:

select a scan order for the video block based on the directional prediction mode for the video block; and

scan the residual transform coefficients of the video block using the selected scan order.

36. A device for coding video data, the device comprising:

means for storing a plurality of transforms for use in transforming between residual pixel values of a video block and residual transform coefficients of the video block, wherein each of the plurality of transforms is associated with at least one directional prediction mode of a plurality of directional prediction modes and at least a portion of the plurality of transforms are separable directional transforms;

means for selecting at least one transform of the plurality of transforms for the video block based on a directional prediction mode for predicting the video block, the directional prediction mode for the video block being one of the plurality of directional prediction modes;

means for applying the selected at least one transform to the video block to transform between the residual pixel values of the video block and the residual transform coefficients of the video block; and

means for entropy coding the residual transform coefficients of the video block.

37. The device of claim 36, wherein the separable directional transforms each include a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

38. The device of claim 36, wherein the plurality of transforms further include a discrete cosine transform (DCT) or an integer transform, and the transform selecting means selects the discrete cosine transform (DCT) or the integer transform to apply to the video block when the directional prediction mode for the video block exhibits limited directionality and selects one of the plurality of the separable directional transforms to apply to the video block when the directional prediction mode for the video block exhibits significant directionality.

39. The device of claim 36, wherein the plurality of transforms are transforms for use in transforming residual pixel values of the video block to residual transform coefficients, and further wherein:

the applying means apply the selected at least one transform to the video block to transform the residual pixel values of the video block to the residual transform coefficients; and

the entropy coding means entropy encode encodes the residual transform coefficients of the video block after the applying means applies the selected at least one transform.

40. The device of claim 36, wherein the plurality of transforms are inverse transforms for use in transforming residual transform coefficients to residual pixel values of the video block and the selected at least one transform is a selected inverse transform, and further wherein:

the applying means apply the selected inverse transform to the video block to transform the residual transform coefficients to the residual pixel values of the video block; and

the entropy coding means entropy decodes the residual transform coefficients of the video block prior to the applying means applying the selected inverse transform.

41. The device of claim 36, wherein each of the separable directional transforms is associated with respective directionality characteristics of one or more of the plurality of the directional prediction modes.

42. The device of claim 36, wherein the means for selecting the at least one of the plurality of transforms based on the directional prediction mode comprises means for selecting, based on the directional prediction mode, at least one of a separable directional transform, a different separable transform, or a combination thereof.

43. The device of claim 42, wherein the different separable transform comprises one of a discrete cosine transform (DCT) or a DCT-like integer transform.

44. The device of claim 42, wherein the separable directional transform comprises a separable Karhunen—

Loè

ve Transform.

45. The device of claim 42, wherein the separable directional transform includes a column transform matrix of size N×

N and a row transform matrix of size N×

N, where N×

N is a dimension of the video block.

46. The device of claim 36, wherein each of the plurality of directional prediction modes is associated with a scan order in a plurality of scan orders, the device further comprising:

means for selecting a scan order for the video block based on the directional prediction mode for the video block; and

means for scanning the residual transform coefficients of the video block using the selected scan order.