Video coding using adaptive source variance based partitioning

• US 9,392,272 B1
• Filed: 06/02/2014
• Issued: 07/12/2016
• Est. Priority Date: 06/02/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yunqing
• Primary Examiner(s): Bailey, Frederick
• Assistant Examiner(s): Nawaz, Talha M
• Application Number:
  US14/293,304
• Time in Patent Office: 771 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04N 19/105 Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock

Abstract

Frames of a video stream can be partitioned using source difference variance based partitioning before encoding. Variances between blocks of a current video frame and blocks of a previous unencoded video frame are determined. The current video frame can be partitioned into varying block sizes depending upon the magnitude of the variances. Blocks with low variance may be combined with other low variance blocks to form larger blocks, while blocks with high variance may be further partitioned into smaller blocks to improve encoding efficiency of the blocks. In cases where partitioning of a frame is unlikely to provide improved efficiency, the variation calculations may be skipped in favor of using fixed partitioning.

Claims

1. A method, comprising:

periodically sampling a plurality of frames of a video stream to obtain a current frame for partitioning at a frame interval;

performing source difference variance based partitioning of the current frame, the source difference variance based partitioning including, for each block of a plurality of blocks of the current frame;

partitioning the block into a plurality of first partitioned blocks having a first partition size, the block having a size at least as large at the first partition size and the first partition size corresponding to one of at least two available partition sizes;

for each first partitioned block having the first partition size;

calculating a variance value based on differences between pixels of the first partitioned block and pixels of a spatially correspondent block in a previous frame;

if the variance value for the first partitioned block is within a first defined range, selecting the first partition size for the pixels of the first partitioned block; and

if the variance value for the first partitioned block is outside the first defined range, selecting a smaller partition size than the first partition size for the pixels of the first partitioned block;

partitioning the current frame according to one or more selected partition sizes for each of the plurality of blocks to form a partitioned current frame; and

encoding the partitioned current frame for inclusion in a bitstream.

2. The method of claim 1 wherein the frame interval is greater than one, the method further comprising, for each intervening frame of the plurality of frames between the frame interval:

comparing a number of the blocks of a previously-partitioned frame of the plurality of frames having a minimum partition size to a threshold value, the previously-partitioned frame partitioned using the source difference variance based partitioning;

if the number is below the threshold, selecting a fixed partitioning size for pixels of the intervening frame;

if the number is at or above the threshold, performing the source difference variance based partitioning of the intervening frame as the current frame to select at least one partition size for the pixels of the intervening frame;

partitioning the pixels of the intervening frame according to one or more selected partition sizes to form a partitioned intervening frame; and

encoding the partitioned intervening frame.

3. The method of claim 2 wherein the number is a percentage of a total number of blocks of the previously-partitioned frame having the minimum partition size.

4. The method of claim 3 wherein the percentage is 15%.

5. The method of claim 1 wherein performing the source difference variance based partitioning further includes, for each block of the plurality of blocks of the current frame:

partitioning the block into at least one second partitioned block having a second partition size, the block having a size at least as large at the second partition size and each second partitioned block encompassing at least two adjacent first partitioned blocks of the plurality of first partitioned blocks;

for each second partitioned block having the second partition size;

if each variance value for the at least two adjacent first partitioned blocks encompassed within the second partitioned block is within a second defined range, selecting the second partition size for pixels of the second partitioned block; and

if at least one variance value for the at least two adjacent first partitioned blocks encompassed within the second partitioned block is outside the second defined range, selecting one or more partition sizes for pixels of the at least two adjacent first partition blocks encompassed within the second partitioned block for the pixels of the second partitioned block, wherein the second defined range defines a lower average per-pixel variance than the first defined range.

6. The method of claim 5 wherein the at least one second partitioned block comprises a plurality of second partitioned blocks, and wherein performing the source difference variance based partitioning further includes, for each block of the plurality of blocks of the current frame:

partitioning the block into a plurality of third partitioned blocks having a third partition size, the block having a size at least as large at the third partition size and each third partitioned block encompassing at least two adjacent second partitioned blocks of the plurality of second partitioned blocks;

for each third partitioned block having the third partition size;

if each variance value for the at least two adjacent second partitioned blocks encompassed within the third partitioned block is within a third defined range, selecting the third partition size for pixels of the third partitioned block; and

if at least one variance value for the at least two adjacent second partitioned blocks encompassed within the third partitioned block is outside the third defined range, selecting one or more partition sizes for pixels of the at least two adjacent second partition blocks encompassed within the third partitioned block for the pixels of the third partitioned block, wherein the third defined range defines a lower average per-pixel variance than the second defined range.

7. The method of claim 6 wherein each block of the plurality of blocks comprises 64 pixels×

64 pixels, the first partition size is 16 pixels×

16 pixels, the second partition size is 32×

32 pixels, the third partition size is 64 pixels×

64 pixels, and the smaller partition size is 8 pixels×

8 pixels.

8. The method of claim 6 wherein the first defined range, the second defined range and the third defined range depend on a noise level of the video stream.

9. The method of claim 8 wherein the first defined range is 0 to 10000, inclusive, the second defined range is 0 to 360, inclusive, and the third defined range is 0 to 720, inclusive.

10. The method of claim 6 wherein calculating a variance value between the pixels of the second partitioned block and pixels of a spatially correspondent block in the previous frame comprises combining each variance value for the at least two adjacent first partitioned blocks encompassed within the second partitioned block into a single variance value.

18. The apparatus of claim 1 wherein the previous frame is an unencoded video frame immediately preceding the current frame in a sequence of the plurality of frames of the video stream.

11. An apparatus, comprising:

a memory; and

a processor configured to execute instructions stored in the memory to;

periodically sample a plurality of frames of a video stream to obtain a current frame for partitioning at a frame interval;

perform source difference variance based partitioning of the current frame, the source difference variance based partitioning including, for each block of a plurality of blocks of the current frame;

partitioning the block into a plurality of first partitioned blocks having a first partition size, the block having a size at least as large at the first partition size and the first partition size corresponding to one of at least two available partition sizes;

for each first partitioned block having the first partition size;

calculating a variance value based on differences between pixels of the first partitioned block and pixels of a spatially correspondent block in a previous frame;

if the variance value for the first partitioned block is within a first defined range, selecting the first partition size for the pixels of the first partitioned block; and

if the variance value for the first partitioned block is outside the first defined range, selecting a smaller partition size than the first partition size for the pixels of the first partitioned block;

partition the current frame according to one or more selected partition sizes for each of the plurality of blocks to form a partitioned current frame; and

encode the partitioned current frame for inclusion in a bitstream.

12. The apparatus of claim 11 wherein the processor is configured to perform the source difference variance based partitioning by, for each block of the plurality of blocks of the current frame:

partitioning the block into at least one second partitioned block having a second partition size, the block having a size at least as large at the second partition size and each second partitioned block encompassing at least two adjacent first partitioned blocks of the plurality of first partitioned blocks;

for each second partitioned block having the second partition size;

if each variance value for the at least two adjacent first partitioned blocks encompassed within the second partitioned block is within a second defined range, selecting the second partition size for pixels of the second partitioned block; and

if at least one variance value for the at least two adjacent first partitioned blocks encompassed within the second partitioned block is outside the second defined range, selecting one or more partition sizes for pixels of the at least two adjacent first partition blocks encompassed within the second partitioned block for the pixels of the second partitioned block, wherein the second defined range defines a lower average per-pixel variance than the first defined range.

13. The apparatus of claim 12 wherein the first partition size is 16 pixels×

16 pixels, the second partition size is 32×

32 pixels, and the smaller partition size is 8 pixels×

8 pixels.

14. The apparatus of claim 12 wherein the frame interval is greater than one and the processor is configured to, for each intervening frame of the plurality of frames between the frame interval:

compare a number of the blocks of a previously-partitioned frame of the plurality of frames having a minimum partition size to a threshold value, the previously-partitioned frame partitioned using the source difference variance based partitioning;

if the number is below the threshold, select a fixed partitioning size for pixels of the intervening frame;

if the number is at or above the threshold, perform the source difference variance based partitioning of the intervening frame as the current frame to select at least one partition size for the pixels of the intervening frame;

partition the pixels of the intervening frame according to one or more selected partition sizes to form a partitioned intervening frame; and

encode the partitioned intervening frame.

15. The apparatus of claim 14 wherein the number is a percentage of a total number of blocks of the previously-partitioned frame having the minimum partition size.

16. The apparatus of claim 14 wherein the at least one second partitioned block comprises a plurality of second partitioned blocks, and the processor is configured to configured to perform the source difference variance based partitioning by, for each block of the plurality of blocks of the current frame:

partitioning the block into a plurality of third partitioned blocks having a third partition size, the block having a size at least as large at the third partition size and each third partitioned block encompassing at least two adjacent second partitioned blocks of the plurality of second partitioned blocks;

for each third partitioned block having the third partition size;

if each variance value for the at least two adjacent second partitioned blocks encompassed within the third partitioned block is within a third defined range, selecting the third partition size for pixels of the third partitioned block; and

if at least one variance value for the at least two adjacent second partitioned blocks encompassed within the third partitioned block is outside the third defined range, selecting one or more partition sizes for pixels of the at least two adjacent second partition blocks encompassed within the third partitioned block for the pixels of the third partitioned block, wherein the third defined range defines a lower average per-pixel variance than the second defined range.

17. The apparatus of claim 16 wherein the first partition size is 16 pixels×

16 pixels, the second partition size is 32×

32 pixels, the third partition size is 64 pixels×

64 pixels, and the smaller partition size is 8 pixels×

8 pixels.

19. The apparatus of claim 11 wherein the processor is configured to calculate the variance value using source differences between the pixels of the first partitioned block and the pixels of the spatially correspondent block in the previous frame.

20. The apparatus of claim 11, further comprising:

a two-frame circular buffer storing each of the current frame and the previous frame in an unencoded state.