Adaptive coefficient scanning in video coding

• US 8,571,104 B2
• Filed: 06/04/2008
• Issued: 10/29/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): SEFCHECK, GREGORY B
• Application Number:
  US12/133,232
• Publication Number:
  US 20080310745A1
• Time in Patent Office: 1,973 Days
• Field of Search: None
• US Class Current: 375/240.14
• 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/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/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

This disclosure describes techniques for scanning coefficients of video blocks, e.g., quantized and transformed coefficients. Rather than use conventional zig-zag scanning, the techniques of this disclosure adapt the scanning order based on statistics associated with previously coded blocks that were coded in the same prediction mode. For each prediction mode, statistics of the coefficients are stored, e.g., indicating probabilities that given coefficients are zero or non-zero. Periodically, adjustments to the scanning order can be made in order to better ensure that non-zero coefficients are grouped together and zero value coefficients are grouped together, which can improve the effectiveness of entropy coding. The techniques of this disclosure provide thresholds and threshold adjustments that can reduce the frequency that the scanning order adjustments occur, yet still achieve desired improvements in compression due to such scanning order adjustments.

Claims

1. A method of coding coefficients of video blocks, the method comprising:

storing statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

counting the video blocks associated with each of the prediction modes;

scanning the coefficient values of the video blocks based on scan orders defined for each of the prediction modes;

evaluating a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

determining a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes;

adjusting the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes; and

entropy coding the coefficient values.

2. The method of claim 1, wherein storing the statistics comprises for each of the plurality of prediction modes:

storing statistics indicative of probabilities of the coefficient values being zero or non-zero.

3. The method of claim 1, further comprising:

determining a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes;

if the new scan order is the same as a previous scan order, increasing the threshold of the given one of the prediction modes;

if the new scan order is different than the previous scan order, decreasing the threshold of the given one of the prediction modes; and

re-setting the count value indicative of a plurality of blocks counted for the given one of the prediction modes.

4. The method of claim 1, wherein the plurality of prediction modes comprise a plurality of intra prediction modes and a plurality of inter prediction modes.

5. The method of claim 4,

wherein the intra prediction modes comprise a plurality of 4 by 4 luma intra prediction modes, a plurality of 8 by 8 luma intra prediction modes, a plurality of 16 by 16 luma intra prediction modes, and a plurality of 8 by 8 chroma intra prediction modes;

and

wherein the inter prediction modes comprise inter prediction modes corresponding to a 4 by 4 block size and an 8 by 8 block size.

6. The method of claim 1, wherein entropy coding comprises content adaptive variable length coding (CAVLC) or context adaptive binary arithmetic coding (CABAC).

7. The method of claim 1, further comprising generating the coefficient values via a transform of the video blocks from a pixel domain to a transformed domain.

8. The method of claim 1, wherein coding comprises encoding,

wherein scanning the coefficient values of the video blocks comprises generating one-dimensional vectors of coefficients from two-dimensional blocks of coefficients based on scan orders defined for each of the prediction modes, and

wherein entropy coding comprises entropy encoding the one-dimensional vectors after scanning the coefficient values.

9. The method of claim 1, wherein coding comprises decoding,

wherein scanning the coefficient values of the video blocks comprises generating two-dimensional blocks of coefficients from one-dimensional vectors of coefficients based on scan orders defined for each of the prediction modes, and

wherein entropy coding comprises entropy decoding the one-dimensional vectors prior to scanning the coefficient values.

10. The method of claim 1, further comprising examining the scan orders defined for each of the prediction modes at a pre-set update interval.

11. The method of claim 1, wherein the method is repeated for each of a plurality of coded units that form a video sequence, the method further comprising:

initializing the scan orders, the statistics and thresholds for each of the prediction modes prior to the method being repeated for each of the plurality of coded units.

12. An apparatus that codes coefficients of video blocks, the apparatus comprising:

a scan unit that;

stores statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

counts the video blocks associated with each of the prediction modes;

scans the coefficient values of the video blocks based on scan orders defined for each of the prediction modes;

an 4

evaluates a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

determines a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes;

adjusts the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes; and

an entropy coding unit that entropy codes the coefficient values.

13. The apparatus of claim 12, wherein the scan unit for each of the plurality of prediction modes:

stores statistics indicative of probabilities of the coefficient values being zero or non-zero.

14. The apparatus of claim 12, wherein the scan unit:

determines a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes;

if the new scan order is the same as a previous scan order, increases the threshold of the given one of the prediction modes;

if the new scan order is different than the previous scan order, decreases the threshold of the given one of the prediction modes; and

re-sets the count value indicative of a plurality of blocks counted for the given one of the prediction modes.

15. The apparatus of claim 12, wherein the plurality of prediction modes comprise a plurality of intra prediction modes and a plurality of inter prediction modes.

16. The apparatus of claim 15,

wherein the intra prediction modes comprise a plurality of 4 by 4 luma intra prediction modes, a plurality of 8 by 8 luma intra prediction modes, a plurality of 16 by 16 luma intra prediction modes, and a plurality of 8 by 8 chroma intra prediction modes;

and

wherein the inter prediction modes comprise inter prediction modes corresponding to a 4 by 4 block size and an 8 by 8 block size.

17. The apparatus of claim 12, wherein the entropy coding unit performs content adaptive variable length coding (CAVLC) or context adaptive binary arithmetic coding (CABAC).

18. The apparatus of claim 12, further comprising a transform unit that generates the coefficient values via a transform of the video blocks from a pixel domain to a transformed domain.

19. The apparatus of claim 12, wherein the apparatus encodes the video blocks,

wherein the scanning unit generates one-dimensional vectors of coefficients from two-dimensional blocks of coefficients based on scan orders defined for each of the prediction modes, and

wherein the entropy coding unit entropy encodes the one-dimensional vectors after the scanning unit scans the coefficient values.

20. The apparatus of claim 12, wherein the apparatus decodes the video blocks,

wherein the scanning unit generates two-dimensional blocks of coefficients from one-dimensional vectors of coefficients based on scan orders defined for each of the prediction modes, and

wherein the entropy coding unit entropy decodes the one-dimensional vectors prior to the scanning unit scanning the coefficient values.

21. The apparatus of claim 12, wherein the scanning unit examines the scan orders defined for each of the prediction modes at a pre-set update interval.

22. The apparatus of claim 12,

wherein the scanning unit repeats its store, count, scan and evaluate operations with respect to each of a plurality of coded units that form a video sequence, and

wherein the scan unit initializes the scan orders, the statistics and thresholds for each of the prediction modes before the scanning unit repeats its store, count, scan and evaluate operations for each of the plurality of coded units.

23. The apparatus of claim 12, wherein the apparatus comprises an integrated circuit.

24. The apparatus of claim 12, wherein the apparatus comprises a microprocessor.

25. A non-transitory computer-readable medium comprising instructions that upon execution in a video coding device cause the device to code coefficients of video blocks, wherein the instructions cause the device to:

store statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

count the video blocks associated with each of the prediction modes;

scan the coefficient values of the video blocks based on scan orders defined for each of the prediction modes;

evaluate a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

determine a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes;

adjust the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes; and

entropy code the coefficient values.

26. The non-transitory computer-readable medium claim 25, wherein for each of the plurality of prediction modes the instructions cause the device to:

store statistics indicative of probabilities of the coefficient values being zero or non-zero.

27. The non-transitory computer-readable medium claim 25, wherein the instructions cause the device to:

determine a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes;

if the new scan order is the same as a previous scan order, increase the threshold of the given one of the prediction modes;

if the new scan order is different than the previous scan order, decrease the threshold of the given one of the prediction modes; and

re-set the count value indicative of a plurality of blocks counted for the given one of the prediction modes.

28. The non-transitory computer-readable medium claim 25, wherein the plurality of prediction modes comprise a plurality of intra prediction modes and a plurality of inter prediction modes.

29. The non-transitory computer-readable medium claim 28,

wherein the intra prediction modes comprise a plurality of 4 by 4 luma intra prediction modes, a plurality of 8 by 8 luma intra prediction modes, a plurality of 16 by 16 luma intra prediction modes, and a plurality of 8 by 8 chroma intra prediction modes;

and

wherein the inter prediction modes comprise inter prediction modes corresponding to a 4 by 4 block size and an 8 by 8 block size.

30. The non-transitory computer-readable medium claim 25, wherein the entropy coding unit performs content adaptive variable length coding (CAVLC) or context adaptive binary arithmetic coding (CABAC).

31. The non-transitory computer-readable medium claim 25, wherein the instructions cause the device to:

generate the coefficient values via a transform of the video blocks from a pixel domain to a transformed domain.

32. The non-transitory computer-readable medium claim 25, wherein the instructions cause the device to encode the video blocks, wherein the instructions cause the device to:

generate one-dimensional vectors of coefficients from two-dimensional blocks of coefficients based on scan orders defined for each of the prediction modes, and

entropy encode the one-dimensional vectors after scanning the coefficient values.

33. The non-transitory computer-readable medium claim 25, wherein the instructions cause the device to decode the video blocks, wherein the instructions cause the device to:

generate two-dimensional blocks of coefficients from one-dimensional vectors of coefficients based on scan orders defined for each of the prediction modes, and

entropy decode the one-dimensional vectors prior to scanning the coefficient values.

34. The non-transitory computer-readable medium claim 25, wherein the instructions cause the device to:

examine the scan orders defined for each of the prediction modes at a pre-set update interval.

35. The non-transitory computer-readable medium claim 25,

wherein the instructions cause the device to repeat its store, count, scan and evaluate operations with respect to each of a plurality of coded units that form a video sequence, and

wherein the instructions cause the device to initialize the scan orders, the statistics and thresholds for each of the prediction modes before the instructions cause the device to repeat its store, count, scan and evaluate operations for each of the plurality of coded units.

36. A device that codes coefficients of video blocks, the device comprising:

means for storing statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

means for counting the video blocks associated with each of the prediction modes;

means for scanning the coefficient values of the video blocks based on scan orders defined for each of the prediction modes;

means for evaluating a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

means for determining a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes;

means for adjusting the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes; and

means for entropy coding the coefficient values.

37. The device of claim 36, wherein means for storing the statistics comprises for each of the plurality of prediction modes:

means for storing statistics indicative of probabilities of the coefficient values being zero or non-zero.

38. The device of claim 36, further comprising:

means for determining a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes;

means for increasing the threshold of the given one of the prediction modes if the new scan order is the same as a previous scan order;

means for decreasing the threshold of the given one of the prediction modes if the new scan order is different than the previous scan order; and

means for re-setting the count value indicative of a plurality of blocks counted for the given one of the prediction modes.

39. The device of claim 36, wherein the plurality of prediction modes comprise a plurality of intra prediction modes and a plurality of inter prediction modes.

40. The device of claim 39,

wherein the intra prediction modes comprise a plurality of 4 by 4 luma intra prediction modes, a plurality of 8 by 8 luma intra prediction modes, a plurality of 16 by 16 luma intra prediction modes, and a plurality of 8 by 8 chroma intra prediction modes;

and

wherein the inter prediction modes comprise inter prediction modes corresponding to a 4 by 4 block size and an 8 by 8 block size.

41. The device of claim 36, wherein means for entropy coding comprises means for content adaptive variable length coding (CAVLC) or means for context adaptive binary arithmetic coding (CABAC).

42. The device of claim 36, further comprising means for generating the coefficient values via a transform of the video blocks from a pixel domain to a transformed domain.

43. The device of claim 36, wherein the device encodes video blocks,

wherein means for scanning the coefficient values of the video blocks comprises means for generating one-dimensional vectors of coefficients from two-dimensional blocks of coefficients based on scan orders defined for each of the prediction modes, and

wherein means for entropy coding comprises means for entropy encoding the one-dimensional vectors after scanning the coefficient values.

44. The device of claim 36, wherein the device decodes video blocks,

wherein means for scanning the coefficient values of the video blocks comprises means for generating two-dimensional blocks of coefficients from one-dimensional vectors of coefficients based on scan orders defined for each of the prediction modes, and

wherein means for entropy coding comprises means for entropy decoding the one-dimensional vectors prior to scanning the coefficient values.

45. The device of claim 36, further comprising means for examining the scan orders defined for each of the prediction modes at a pre-set update interval.

46. The device of claim 36, wherein storing, counting, scanning and evaluating operations are repeated for each of a plurality of coded units that form a video sequence, the device further comprising means for initializing the scan orders, the statistics and thresholds for each of the prediction modes prior to the storing, counting, scanning and evaluating operations being repeated for each of the plurality of coded units.

47. A device comprising:

a scan unit that;

stores statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

counts the video blocks associated with each of the prediction modes;

scans the coefficient values of the video blocks from two-dimensional blocks to one-dimensional vectors based on scan orders defined for each of the prediction modes;

evaluates a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

determines a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes; and

adjusts the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes;

an entropy coding unit that entropy encodes the coefficient values of the one-dimensional vectors; and

a wireless transmitter that sends a bitstream comprising the entropy encoded coefficient values.

48. The device of claim 47, wherein the device comprises a wireless communication handset.

49. A device comprising:

a wireless receiver that receives a bitstream comprising entropy coded coefficient values of video blocks in one-dimensional vectors;

an entropy coding unit that entropy decodes the coefficient values of the video blocks; and

a scan unit that;

stores statistics associated with coefficient values of the video blocks for each of a plurality of prediction modes;

counts the video blocks associated with each of the prediction modes;

scans the coefficient values of the video blocks from the one-dimensional vectors to two-dimensional blocks based on scan orders defined for each of the prediction modes;

evaluates a given scan order associated with a given one of the prediction modes based on the statistics of the given one of the prediction modes when a count value indicative of a plurality of blocks counted for the given one of the prediction modes satisfies a threshold of the given one of the prediction modes;

determines a new scan order associated with the given one of the prediction modes based on the statistics of the given one of the prediction modes when the count value indicative of the plurality of blocks counted for the given one of the prediction modes satisfies the threshold of the given one of the prediction modes; and

adjusts the threshold of the given one of the prediction modes upon adjusting the given scan order of the given one of the prediction modes.

50. The device of claim 49, wherein the device comprises a wireless communication handset.