SEPARABLE DIRECTIONAL TRANSFORMS

• US 20080310512A1
• Filed: 06/04/2008
• Published: 12/18/2008
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Karczewicz, Marta, Ye, Yan
• Granted Patent: US 8,619,853 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• 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 encoding video data, the method comprising:

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 prediction mode and at least a portion of the plurality of transforms are separable directional transforms;

selecting one of the plurality of transforms for the video block based on a prediction mode of the video block;

applying the selected 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 one 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 selected prediction mode exhibits limited directionality; and

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

4. The method of claim 3, further comprising

selecting the prediction mode of the video block from a set of prediction modes that include unidirectional prediction modes and multi-directional prediction modes that combine at least two unidirectional prediction modes,

wherein selecting the DCT or the integer transform comprises selecting the DCT or the integer transform to apply to the video block when the selected prediction mode is either a DC unidirectional prediction mode or a multi-directional prediction mode that combines at least two prediction modes that point in substantially orthogonal directions.

5. The method of claim 4, wherein the set of prediction modes includes unidirectional prediction modes and a subset of possible bidirectional prediction modes, the subset of bidirectional prediction modes including at least one combination that includes each of the unidirectional prediction modes.

6. The method of claim 1, wherein the selected transform is a separable transform and the video block comprises a first video block, the method further comprising:

scanning the residual transform coefficients of the first video block using a coefficient scan order;

collecting statistics associated with at least a portion of the coefficients;

adjusting the coefficient scan order in accordance with the collected statistics; and

scanning coefficients of at least one subsequent video block using the adjusted coefficient scan order when the at least one subsequent video block exists in a coding unit of the first video block.

7. The method of claim 6, wherein:

collecting statistics for at least a portion of the coefficients comprises maintaining a count value corresponding to each position within the portion of the two-dimensional representation of the coefficients that tracks a number of times that each of the positions within the portion of the two-dimensional representation of the coefficients has a non-zero coefficient; and

adjusting the coefficient scan order comprises adjusting the coefficient scan order to generate an adjusted coefficient scan order that scans the coefficient positions in descending order based on count values of the coefficient positions.

8. The method of claim 7, further comprising normalizing the collected statistics when one of the count values reaches a threshold count value, wherein normalizing the collected statistics comprises one of reducing each of the count values by a factor and resetting the count values to a set of initial count values.

9. The method of claim 6, further comprising selecting the prediction mode of the video block from a plurality of prediction modes, wherein collecting statistics and adjusting the coefficient scan order comprises collecting statistics and adjusting the coefficient scan order separately for each of the plurality of prediction modes.

10. The method of claim 6, wherein the first video block and the at least one subsequent video block belong to a first coding unit, the method further comprising re-initializing the scan order for a second coding unit.

11. The method of claim 1, wherein the transforms are transforms for use in transforming residual pixel values of the video block to residual transform coefficients, and further wherein:

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

entropy coding comprise entropy encoding the residual transform coefficients of the video block after applying the selected transform.

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

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

entropy coding comprise entropy decoding the residual transform coefficients of the video block prior to applying the selected transform.

13. A device for encoding video data, the device comprising:

a transform unit that;

stores a plurality of transforms for use in transforming between residual pixel values of a video block and residual transform coefficients of the video block,

selects one of the plurality of transforms for the video block based on a prediction mode of the video block, and

applies the selected 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,

wherein each of the plurality of transforms is associated with at least one prediction mode and at least a portion of the plurality of transforms are separable directional transforms; and

an entropy coding unit that entropy encodes the residual transform coefficients of the video block.

14. The device of claim 13, 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.

15. The device of claim 13, wherein the plurality of transforms further include a discrete cosine transform (DCT) or an integer transform, and the transform unit:

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

selects one of the plurality of the separable directional transforms to apply to the video block when the selected prediction mode exhibits directionality.

16. The device of claim 15, further comprising:

a prediction unit that selects the prediction mode of the video block from a set of prediction modes that include unidirectional prediction modes and multi-directional prediction modes that combine at least two unidirectional prediction modes,

wherein transform unit selects the DCT or the integer transform to apply to the video block when the selected prediction mode is either a DC unidirectional prediction mode or a multi-directional prediction mode that combines at least two prediction modes that point in substantially orthogonal directions.

17. The device of claim 16, wherein the set of prediction modes includes unidirectional prediction modes and a subset of possible bidirectional prediction modes, the subset of bidirectional prediction modes including at least one combination that includes each of the unidirectional prediction modes.

18. The device of claim 13, wherein the selected transform is a separable transform and the video block comprises a first video block, the device further comprising a scanning unit that:

scans the residual transform coefficients of the first video block using a coefficient scan order,

collects statistics associated with at least a portion of the coefficients;

adjusts the coefficient scan order in accordance with the collected statistics; and

scans coefficients of at least one subsequent video block using the adjusted coefficient scan order when the at least one subsequent video block exists in a coding unit of the first video block.

19. The device of claim 18, wherein the scanning unit:

maintains a count value corresponding to each position within the portion of the two-dimensional representation of the coefficients that tracks a number of times that each of the positions within the portion of the two-dimensional representation of the coefficients has a non-zero coefficient; and

adjusts the coefficient scan order comprises adjusting the coefficient scan order to generate an adjusted coefficient scan order that scans the coefficient positions in descending order based on count values of the coefficient positions.

20. The device of claim 19, wherein the scanning unit normalizes the collected statistics when one of the count values reaches a threshold count value, wherein normalizing the collected statistics comprises one of reducing each of the count values by a factor and resetting the count values to a set of initial count values.

21. The device of claim 18, wherein:

the prediction unit selects the prediction mode of the video block from a plurality of prediction modes, and

the scanning unit collects statistics and adjusts the coefficient scan order separately for each of the plurality of prediction modes.

22. The device of claim 18, wherein the first video block and the at least one subsequent video block belong to a first coding unit and the scanning unit re-initializes the scan order for a second coding unit.

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

the transform unit applies the selected transform to the video block to transform residual pixel values of the video block to the residual transform coefficients; and

the entropy coding unit entropy encodes the residual transform coefficients of the video block after applying the selected transform.

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

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

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

25. The device of claim 13, wherein the device comprises a wireless communication device.

26. The device of claim 13, wherein the device comprises an integrated circuit device.

27. A computer-readable medium upon which is stored instructions that upon execution in a video coding 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 prediction mode and at least a portion of the plurality of transforms are separable directional transforms;

select one of the plurality of transforms for the video block based on a prediction mode of the video block;

apply the selected 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 encode the residual transform coefficients of the video block.

28. The computer-readable medium of claim 27, 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.

29. The computer-readable medium of claim 27, 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 selected prediction mode exhibits limited directionality; and

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

30. The computer-readable medium of claim 29, wherein the instructions cause the device to:

select the prediction mode of the video block from a set of prediction modes that include unidirectional prediction modes and multi-directional prediction modes that combine at least two unidirectional prediction modes,

select the DCT or the integer transform to apply to the video block when the selected prediction mode is either a DC unidirectional prediction mode or a multi-directional prediction mode that combines at least two prediction modes that point in substantially orthogonal directions.

31. The computer-readable medium of claim 27, wherein the selected transform is a separable transform and the video block comprises a first video block, and the instructions cause the device to:

scan the residual transform coefficients of the first video block using a coefficient scan order;

collect statistics associated with at least a portion of the coefficients;

adjust the coefficient scan order in accordance with the collected statistics; and

scan coefficients of at least one subsequent video block using the adjusted coefficient scan order when the at least one subsequent video block exists in a coding unit of the first video block.

32. The computer-readable medium of claim 31, wherein the instructions cause the device to:

maintain a count value corresponding to each position within the portion of the two-dimensional representation of the coefficients that tracks a number of times that each of the positions within the portion of the two-dimensional representation of the coefficients has a non-zero coefficient; and

adjust the coefficient scan order comprises adjusting the coefficient scan order to generate an adjusted coefficient scan order that scans the coefficient positions in descending order based on count values of the coefficient positions.

33. The computer-readable medium of claim 32, wherein the instructions cause the device to normalize the collected statistics when one of the count values reaches a threshold count value, wherein normalizing the collected statistics comprises one of reducing each of the count values by a factor and resetting the count values to a set of initial count values.

34. The computer-readable medium of claim 31, wherein the instructions cause the device to collect statistics and adjust the coefficient scan order separately for each of the plurality of prediction modes.

35. The computer-readable medium of claim 31, wherein the first video block and the at least one subsequent video block belong to a first coding unit, and the instructions cause the device to re-initialize the scan order for a second coding unit.

36. The computer-readable medium of claim 27, wherein the 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 device to:

apply the selected transform to the video block to transform 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 transform.

37. The computer-readable medium of claim 27, wherein the transforms are inverse transforms for use in transforming residual transform coefficients to residual pixel values of the video block, and further wherein the instructions cause the device to:

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

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

38. A device for encoding 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 prediction mode and at least a portion of the plurality of transforms are separable directional transforms;

means for selecting one of the plurality of transforms for the video block based on a prediction mode of the video block;

means for applying the selected 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.

39. The device of claim 38, 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.

40. The device of claim 38, 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 selected prediction mode exhibits limited directionality and selects one of the plurality of the separable directional transforms to apply to the video block when the selected prediction mode exhibits directionality.

41. The device of claim 40, further comprising:

means for selecting the prediction mode of the video block from a set of prediction modes that include unidirectional prediction modes and multi-directional prediction modes that combine at least two unidirectional prediction modes,

wherein the transform selecting means selects the DCT or the integer transform to apply to the video block when the selected prediction mode is either a DC unidirectional prediction mode or a multi-directional prediction mode that combines at least two prediction modes that point in substantially orthogonal directions.

42. The device of claim 41, wherein the set of prediction modes includes unidirectional prediction modes and a subset of possible bidirectional prediction modes, the subset of bidirectional prediction modes including at least one combination that includes each of the unidirectional prediction modes.

43. The device of claim 38 wherein the selected transform is a separable transform and the video block comprises a first video block, the device further comprising:

means for scanning the residual transform coefficients of the first video block using a coefficient scan order;

means for collecting statistics associated with at least a portion of the coefficients; and

means for adjusting the coefficient scan order in accordance with the collected statistics,

wherein the coefficient scanning means scans coefficients of at least one subsequent video block using the adjusted coefficient scan order when the at least one subsequent video block exists in a coding unit of the first video block.

44. The device of claim 43, wherein:

the statistics collecting means maintains a count value corresponding to each position within the portion of the two-dimensional representation of the coefficients that tracks a number of times that each of the positions within the portion of the two-dimensional representation of the coefficients has a non-zero coefficient; and

the adjusting means adjusts the coefficient scan order to generate an adjusted coefficient scan order that scans the coefficient positions in descending order based on count values of the coefficient positions.

45. The device of claim 44, further comprising means for normalizing the collected statistics when one of the count values reaches a threshold count value, wherein the normalizing means normalizes the collected statistics by one of reducing each of the count values by a factor and resetting the count values to a set of initial count values.

46. The device of claim 43, further comprising means for selecting the prediction mode of the video block from a plurality of prediction modes, wherein the statistics collecting means and the adjusting means collect statistics and adjust the coefficient scan order separately for each of the plurality of prediction modes.

47. The device of claim 43, wherein the first video block and the at least one subsequent video block belong to a first coding unit, and the adjusting means re-initializes the scan order for a second coding unit.

48. The device of claim 38, wherein the 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 transform to the video block to transform residual pixel values of the video block to the residual transform coefficients; and

the entropy coding means entropy encode the residual transform coefficients of the video block after applying the selected transform.

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

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

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