Lossless video coding with sub-frame level optimal quantization values

• US 9,407,915 B2
• Filed: 01/15/2013
• Issued: 08/02/2016
• Est. Priority Date: 10/08/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gu, Qunshan, Cai, Xun
• Primary Examiner(s): Czekaj, Dave
• Assistant Examiner(s): SULLIVAN, TYLER
• Application Number:
  US13/741,927
• Publication Number:
  US 20140098856A1
• Time in Patent Office: 1,295 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• 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/124 Quantisation
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/159 Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A block of a frame of a video stream can be encoded using lossless coding that generates a transform domain residual block and a spatial domain difference block. The compression ratio of the coding may be improved by selecting an optimal quantization value on a per-block basis. The optimal quantization value can be selected by quantizing a residual block resulting from prediction of the block using a plurality of candidate quantization values and selecting the candidate quantization value that results in the fewest number of bits for the quantized residual block.

Claims

1. A method for encoding a video stream including a plurality of frames, the method comprising:

selecting a block of a plurality of blocks of the frame;

identifying, using a processor, an optimal quantization value, comprising;

performing a quantization optimization loop for a plurality of candidate quantization values using the block including;

identifying a candidate quantization value;

predicting the block to form a residual block;

partially encoding the residual block to form a partially encoded residual block;

quantizing the partially encoded residual block to form a quantized block using the candidate quantization value;

partially decoding the quantized block to form a decoded residual block;

subtracting the decoded residual block from the residual block to form a difference block; and

summing the bits included in the quantized block and the difference block to form an estimated number of bits; and

identifying the candidate quantization value that results in the smallest estimated number of bits as the optimal quantization value,

wherein the optimal quantization value is a quantization value for the block that minimizes a number of bits required to encode a residual block of the block and a difference block of the block, the residual block being a difference between the block and a prediction block for the block, and the difference block being a block including errors resulting from encoding the residual block;

encoding the block using the optimal quantization value to form an encoded residual block and an encoded difference block by;

quantizing and subsequently entropy coding the residual block to form the encoded residual block; and

entropy coding the difference block without quantizing the difference block to form the encoded difference block; and

including the encoded residual block, the encoded difference block and the optimal quantization value in an encoded video bitstream.

2. The method of claim 1, further comprising:

identifying an initial candidate quantization value for the quantization optimization loop by averaging optimal quantization values from previously encoded frames of the plurality of frames.

3. The method of claim 1, further comprising:

identifying an initial candidate quantization value for the quantization optimization loop by averaging optimal quantization values from previously encoded blocks of the frame.

4. The method of claim 1 wherein partially encoding the residual block further comprises:

forming a prediction block for the block using one of inter prediction or intra prediction;

generating the residual block by subtracting the prediction block from the block; and

transforming the residual block to form the partially encoded residual block.

5. The method of claim 1 wherein partially decoding the quantized block further comprises:

de-quantizing the quantized block to form a de-quantized block using the candidate quantization value; and

inverse transforming the de-quantized block to form the decoded residual block.

6. The method of claim 1 wherein the optimal quantization value is within a value of +/−

n from an initial candidate quantization value of the quantization loop; and

wherein n is a number between 0 and 7.

7. The method of claim 1, further comprising:

forming the prediction block for the block using one of inter prediction or intra prediction; and

generating the residual block by subtracting the prediction block from the block;

wherein identifying the optimal quantization value comprises testing each of a plurality of candidate quantization values by transforming the residual block to form a partially encoded block using each of the plurality of candidate quantization values; and

wherein the optimal quantization value is a one of the plurality of candidate quantization values forming a sparsest partially encoded block after transformation.

8. The method of claim 7 wherein the plurality of candidate quantization values comprises all available quantization values.

9. The method of claim 7 wherein the plurality of candidate quantization values comprises an initial candidate quantization value and at least one additional candidate quantization value dependent upon a result of transforming the residual block using the initial candidate quantization value.

10. An apparatus for encoding a video stream including a plurality of frames, the apparatus comprising:

a memory; and

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

select a block of a plurality of blocks of a frame;

identify an optimal quantization value wherein the identify the optimal quantization value comprises;

performing a quantization optimization loop for a plurality of candidate quantization values using the block including;

identifying a candidate quantization value;

predicting the block to form a residual block;

partially encoding the residual block to form a partially encoded residual block;

quantizing the partially encoded residual block to form a quantized block using the candidate quantization value;

partially decoding the quantized block to form a decoded residual block;

subtracting the decoded residual block from the residual block to form a difference block; and

summing the bits included in the quantized block and the difference block to form an estimated number of bits; and

identifying the candidate quantization value that results in the smallest estimated number of bits as the optimal quantization value,

wherein the optimal quantization value is a quantization value for the block that minimizes a number of bits required to encode a residual block of the block and a difference block of the block, the residual block being a difference between the block and a prediction block for the block, and the difference block being a block including errors resulting from encoding the residual block;

encode the block using the optimal quantization value to form an encoded residual block and an encoded difference block by;

quantizing and subsequently entropy coding the residual block to form the encoded residual block; and

entropy coding the difference block without quantizing the difference block to form the encoded difference block; and

include the encoded residual block, the encoded difference block and the optimal quantization value in an encoded video bitstream.

11. The apparatus of claim 10 wherein the processor is configured to:

form the prediction block for the block using one of inter prediction or intra prediction;

generate the residual block by subtracting the prediction block from the block; and

identify the optimal quantization value by;

testing each of a plurality of candidate quantization values by transforming the residual block to form a partially encoded block using each of the plurality of candidate quantization values;

wherein the optimal quantization value is a one of the plurality of candidate quantization values forming a sparsest partially encoded block after transformation.

12. The apparatus of claim 11 wherein the plurality of candidate quantization values comprises an initial candidate quantization value and at least one additional candidate quantization value dependent upon a result of transforming the residual block using the initial candidate quantization value.

13. The apparatus of claim 12 wherein the initial candidate quantization value comprises an average of optimal quantization values from previously encoded frames of the plurality of frames.

14. The apparatus of claim 12 wherein the initial candidate quantization value comprises an average of optimal quantization values from previously encoded blocks of the frame.

15. The apparatus of claim 12 wherein the optimal quantization value is within a value of +/−

n from the initial candidate quantization value, wherein n is an integer between 0 and 7, inclusive.

16. The apparatus of claim 11 wherein the plurality of candidate quantization values comprises an initial candidate quantization value and additional candidate quantization values between a minimum value and a maximum value;

and wherein the processor is configured to identify the optimal quantization value using a binary search beginning with the initial candidate quantization value.

17. The apparatus of claim 11 wherein the plurality of candidate quantization values comprises an initial candidate quantization value, the initial candidate quantization value being one of:

an average of optimal quantization values from previously encoded frames of the plurality of frames;

or

an average of optimal quantization values from previously encoded blocks of the frame.

18. A method for decoding an encoded video bitstream including a plurality of frames, the method comprising:

identifying, using a processor, an entropy coded quantized block and an entropy coded difference block associated with a block of a frame by reading bits in a block header associated with the block;

identifying an optimal quantization value for the quantized block by reading bits in a block header associated with the block, wherein the optimal quantization value was selected by an encoder performing a quantization optimization loop for a plurality of candidate quantization values using the block including;

identifying a candidate quantization value;

predicting the block to form a residual block;

partially encoding the residual block to form a partially encoded residual block;

quantizing the partially encoded residual block to form a candidate quantized block using the candidate quantization value;

partially decoding the candidate quantized block to form a decoded residual block;

subtracting the decoded residual block from the residual block to form a candidate difference block; and

summing the bits included in the candidate quantized block and the candidate difference block to form an estimated number of bits; and

identifying the candidate quantization value that results in the smallest estimated number of bits as the optimal quantization value for the block;

entropy decoding the entropy coded quantized block to form a quantized block;

entropy decoding the entropy coded difference block to form a difference block;

de-quantizing the quantized block using the optimal quantization value to form a transformed block;

inverse transforming the transformed block to form a first residual block;

adding the difference block to the first residual block to form a second residual block;

predicting the block to form a prediction block; and

adding the second residual block to the predicted block to form a decoded block.