Video coding using statistical-based spatially differentiated partitioning

• US 9,578,324 B1
• Filed: 06/27/2014
• Issued: 02/21/2017
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Yunqing
• Primary Examiner(s): Czekaj, Dave
• Assistant Examiner(s): Pham, Nam
• Application Number:
  US14/317,749
• Time in Patent Office: 970 Days
• US Class Current: 1/1
• 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/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock

Abstract

Frames of a video data stream can be encoded using statistically-based spatially differentiated partitioning. Statistically-based spatially differentiated partitioning involves forming a difference frame between a current video frame and a temporally nearby video frame and then calculating the variance of the difference frame on a block-by-block basis. A histogram can be formed from the calculated variances and a threshold determined on the histogram. The determined threshold can be used to select parameters for the encoding process that will more efficiently encode static or slow-motion areas without a significant loss in resulting quality.

Claims

1. A method, comprising:

forming a difference frame comprising differences between pixel values of a first video frame and a second video frame of a video stream;

calculating, using a processor, a variance for blocks of the difference frame;

forming a variance histogram using at least some of the calculated variances;

determining a threshold variance value to separate static or low motion areas from fast motion areas wherein a portion of the blocks of the variance histogram representing static or low motion areas have variances less than or equal to the threshold variance value;

selecting at least one encoding parameter for a block of the first video frame based on a comparison of a variance of a spatially-correspondent block in the difference frame with the threshold variance value; and

encoding the block of the first video frame using the at least one encoding parameter.

2. The method of claim 1, further comprising:

defining a stop threshold; and

wherein

forming the variance histogram comprises adding the calculated variance of a block of the difference frame to a bin of the variance histogram only when the calculated variance is below the stop threshold.

3. The method of claim 1 wherein determining the threshold variance value comprises calculating the threshold variance value T using a formula:

T=μ

+k*σ

;

wherein

μ

is a mean of the at least some of the calculated variances;

σ

is a standard deviation of the at least some of the calculated variances; and

k is a positive integer.

4. The method of claim 1 wherein the variance histogram is a cumulative variance histogram that plots the at least some of the calculated variances against a plurality of normalized frequency values;

and wherein determining the threshold variance value comprises selecting a cutoff frequency value of the plurality of normalized frequency values, the threshold variance value corresponding to the cutoff frequency value on the cumulative variance histogram.

5. The method of claim 1 wherein determining the threshold variance value comprises:

selecting a cutoff block count, wherein the cutoff block count is less than a total number of blocks forming the variance histogram;

sequentially accumulating a block count of a plurality of histogram bins of the variance histogram from a lowest variance range to a highest variance range to form a sum, each of the plurality of histogram bins having a fixed bin width, until the sum is greater than the cutoff block count; and

calculating the threshold variance value by multiplying the fixed bin width by a number of the plurality of histogram bins whose block count was included in the sum.

6. The method of claim 1, further comprising:

forming a second difference frame comprising differences between pixel values of the second video frame and a third video frame of the video stream;

calculating a variance for blocks of the second difference frame;

forming a second variance histogram using at least some of the calculated variances of the second difference frame;

selecting a cutoff block count, wherein the cutoff block count is less than a total number of blocks forming the second variance histogram;

sequentially accumulating a block count of a plurality of histogram bins of the second variance histogram from a lowest variance range to a highest variance range to form a sum, each of the plurality of histogram bins having a fixed bin width, until one of the sum is greater than the cutoff block count or the block count of each of the plurality of histogram bins is included in the sum and the sum is less than or equal to the cutoff block count;

calculating a second threshold variance value, when the sum is greater than the cutoff block count, by multiplying the fixed bin width by a number of the plurality of histogram bins whose block count was included in the sum;

defining the second threshold variance value to a null value when the block count of each of the plurality of histogram bins is included in the sum and the sum is less than or equal to the cutoff block count; and

when the second threshold variance value is other than the null value, selecting at least one encoding parameter for a block of the second video frame based on a comparison of a variance of a spatially-correspondent block in the second difference frame with the second threshold variance value.

7. The method of claim 6 wherein selecting the at least one encoding parameter comprises selecting a first setting for a first encoding parameter for the block when the variance of the spatially-correspondence block is less than the second threshold variance value and selecting a second setting for the first encoding parameter for the block when the variance of the spatially-correspondence block is greater than the second threshold variance value, the first setting increasing encoding efficiency as compared to the second setting for image data exhibiting static or slow motion.

8. The method of claim 7, further comprising:

selecting the second setting for the first encoding parameter for the block when the second threshold variance value is the null value.

9. The method of claim 1 wherein the second video frame is temporally-adjacent to the first video frame in a sequence defined by the video stream and each block of the difference frame has a same size.

10. The method of claim 1 wherein selecting the at least one encoding parameter comprises at least one of:

selecting a first motion search parameter when the variance of the spatially-correspondent block is less than the threshold variance value and selecting a second motion search parameter when the variance of the spatially-correspondent block is greater than the threshold variance value;

or

selecting a first quantization value when the variance of the spatially-correspondent block is less than the threshold variance value and selecting a second quantization value when the variance of the spatially-correspondent block is greater than the threshold variance value.

11. The method of claim 1 wherein selecting the at least one encoding parameter comprises:

providing a first group of partition sizes for prediction of the block of the first video frame when the variance of the spatially-correspondent block is less than the threshold variance value; and

providing a second group of partition sizes for prediction of the block of the first video frame when the variance of the spatially-correspondent block is greater than the threshold variance value, wherein at least one partition size of the second group of partition sizes is smaller than all partition sizes within the first group of partition sizes.

12. An apparatus, comprising:

a memory; and

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

form a difference frame comprising differences in pixel values between a first video frame and a second video frame of a video stream;

calculate a variance for blocks of the difference frame;

form a variance histogram using at least some of the calculated variances;

determine a threshold variance value to separate static or low motion areas from fast motion areas wherein a portion of the blocks of the variance histogram representing static or low motion areas have variances less than or equal to the threshold variance value;

select at least one encoding parameter for a block of the first video frame based on a comparison of a variance of a spatially-correspondent block in the difference frame with the threshold variance value; and

encode the block of the first video frame using the at least one encoding parameter.

13. The apparatus of claim 12 wherein the processor is configured to:

define a stop threshold; and

form the variance histogram by adding the calculated variance of a block of the difference frame to a bin of the variance histogram only when the calculated variance is below the stop threshold.

14. The apparatus of claim 12 wherein the processor is configured to determine the threshold variance value by:

calculating the threshold variance value T using a formula;

T=μ

+k*σ

;

wherein

μ

is a mean of the at least some of the calculated variances;

σ

is a standard deviation of the at least some of the calculated variances; and

k is a positive integer.

15. The apparatus of claim 12 wherein the variance histogram is a cumulative variance histogram that plots the at least some of the calculated variances against a plurality of normalized frequency values;

and wherein the processor is configured to determine the threshold variance value by;

selecting a cutoff frequency value of the plurality of normalized frequency values, the threshold variance value corresponding to the cutoff frequency value on the cumulative variance histogram.

16. The apparatus of claim 12 wherein the processor is configured to determine the threshold variance value by:

selecting a cutoff block count, wherein the cutoff block count is less than a total number of blocks whose variances form the variance histogram;

sequentially accumulating a block count of a plurality of histogram bins of the variance histogram from a lowest variance range to a highest variance range to form a sum, each of the plurality of histogram bins having a fixed bin width, until the sum is greater than the cutoff block count; and

calculating the threshold variance value by multiplying the fixed bin width by a number of the plurality of histogram bins whose block count was included in the sum.

17. The apparatus of claim 16 wherein the variance histogram is a cumulative variance histogram that plots the at least some of the calculated variances against a plurality of normalized frequency values;

and wherein the processor is configured to select the cutoff block count by;

selecting a cutoff frequency value of the plurality of normalized frequency values; and

multiplying the cutoff frequency value by the total number of blocks.

18. The apparatus of claim 12 wherein the processor is configured to select the at least one encoding parameter by:

selecting a first setting for a first encoding parameter for the block of the first video frame when the variance of the spatially-correspondence block is less than the threshold variance value; and

selecting a second setting for the first encoding parameter for the block of the first video frame when the variance of the spatially-correspondence block is greater than the threshold variance value, the first setting increasing encoding efficiency as compared to the second setting for image data exhibiting static or slow motion.

19. The apparatus of claim 12 wherein the processor is configured to calculate the variance for blocks of the difference frame by, for each block:

forming distributions of pixel values of the block, each distribution having a mean and a standard deviation; and

combining the distributions to calculate the variance for the block.

20. The apparatus of claim 12 wherein the processor is configured to:

form a second difference frame comprising differences in pixel values between the second video frame and a third video frame of a video stream;

calculate a variance for blocks of the second difference frame;

form a second variance histogram using at least some of the calculated variances of the second difference frame;

select a cutoff block count, wherein the cutoff block count is less than a total number of blocks forming the second variance histogram;

sequentially accumulate a block count of a plurality of histogram bins of the second variance histogram from a lowest variance range to a highest variance range to form a sum, each of the plurality of histogram bins having a fixed bin width, until one of the sum is greater than the cutoff block count or the block count of each of the plurality of histogram bins is included in the sum and the sum is less than or equal to the cutoff block count;

calculate a second threshold variance value, when the sum is greater than the cutoff block count, by multiplying the fixed bin width by a number of the plurality of histogram bins whose block count was included in the sum;

define the second threshold variance value to a null value when the block count of each of the plurality of histogram bins is included in the sum and the sum is less than or equal to the cutoff block count; and

when the second threshold variance value is other than the null value, select at least one encoding parameter for a block of the second video frame based on a comparison of a variance of a spatially-correspondent block in the second difference frame with the second threshold variance value.