Method and apparatus for motion compensated video coding

• US 6,721,359 B1
• Filed: 04/06/2001
• Issued: 04/13/2004
• Est. Priority Date: 01/14/1998
• Status: Expired due to Term

• Current Assignee: Skyworks Solutions Incorporated
• Original Assignee: Skyworks Solutions Incorporated
• Inventors: Wu, Wei, Hsueh, Albert A-Chuan, Bist, Anurag
• Primary Examiner(s): An, Shawn S.
• Application Number:
  US09/828,535
• Time in Patent Office: 1,103 Days
• Field of Search: 375/240.03, 375/240.12, 375/240.02, 375/240.26, 375/240.24, 375/240.23, 375/240.2, 348/405, 348/416, 348/699, 348/411-413, 348/700, 348/420, 348/390, 382/239, 382/232, 382/250, 382/246, 382/251
• US Class Current: 375/240.03
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• 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/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Apparatus and methods are provided for encoding video data in a manner which significantly reduces the computation performed by the video encoder and the video decoder without suffering any degradation in the perceived quality of the compressed video data. In particular, apparatus and methods are provided for determining which blocks might be zeroed out after quantization. This determination is performed after motion estimation, the classification of the frame as either an I frame, P frame, or a B frame, and the determination of a quantization step size (QP) for the block, but before DCT. If a given block is determined to be a “zero” quantized block, then the DCT, quantization, zig-zag scan and variable length coding steps are omitted, and a variable length code output is provided indicating that the block B is a “zero” quantized block. The present invention determines which blocks might be zeroed out after quantization by using one or more key features of the motion compensated blocks which will help in classifying these blocks into zero and nonzero blocks. Examples of these features include the mean absolute value of a block, the mean square error of a block, the block variance, the mean absolute difference of a block, and the maximum value in a block. Each feature is provided with a predetermined threshold that has been experimentally calculated.

Claims

1. A method of encoding video data, comprising the steps of:

performing motion estimation on a sequence of frames of video data, each frame comprised of a plurality of blocks, each block containing values representative of the video data to be encoded;

classifying each frame as either an I frame, a P frame, or a B frame;

determining a quantization size number for the block or a group of the plurality of blocks;

determining whether a given block in the frame is a zero quantized block using an optimal threshold value; and

performing DCT, quantization, zig-zag scan and variable length coding on the given block if the given block is not a zero quantized block;

wherein the optimal threshold value is determined experimentally using a plurality of experimental blocks and a plurality of experimental threshold values, and wherein an experimental result of encoding the plurality of experimental blocks using each of the plurality of experimental threshold values is compared with an actual result of encoding the plurality of blocks without using the plurality of experimental threshold values.

2. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

determining the mean absolute error of all the values in the given block; and

comparing the mean absolute error with a predetermined threshold.

3. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

determining the mean square error of all the values in the given block; and

comparing the mean square error with a predetermined threshold.

4. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

determining the block variance of all the values in the given block; and

comparing the block variance with a predetermined threshold.

5. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps;

determining the mean absolute difference of all the values in the given block; and

comparing the mean absolute difference with a predetermined threshold.

6. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

determining the maximum of all the values in the given block; and

comparing the maximum with a predetermined threshold.

7. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

determining the mean absolute error of all the values in the given block;

comparing the mean absolute error with a first predetermined threshold;

determining the mean square error of all the values in the given block;

comparing the mean square error with a second predetermined threshold;

determining the block variance of all the values in the given block;

comparing the block variance with a third predetermined threshold;

determining the mean absolute difference of all the values in the given block;

comparing the mean absolute difference with a fourth predetermined threshold;

determining the maximum of all the values in the given block;

comparing the maximum with a fifth predetermined threshold; and

classifying the given block as a zero-quantized block if the mean absolute value, the mean square error, the block variance, the mean absolute difference and the maximum are all less than or equal to each of their respective thresholds.

8. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

selecting a desired feature to be used in determining whether the given block is a zero quantized block;

computing the value of the selected feature for the given block; and

comparing the value of the selected feature for the given block with a threshold.

9. The method of claim 8, wherein the desired feature can be selected from a group consisting of:

the mean absolute value of the given block;

the mean square error of the given block;

the block variance;

the mean absolute difference of the given block; and

the maximum value in the given block.

10. The method of claim 1,

wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

calculating a value for a first feature of all the values in the given block;

comparing the value of the first feature with a first predetermined threshold;

calculating a value for a second feature of all the values in the given block;

comparing the value of the second feature with a second predetermined threshold; and

classifying the given block as a zero-quantized block if the values of the first and second features are all less than or equal to each of the first and second thresholds, respectively.

11. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the step of:

generating a first output indicative of the detection of a zero quantized block.

12. The method of claim 11, further including the step of:

generating a bitstream output representing the coded values of the given block.

13. The method of claim 1, wherein said step of determining whether the given block in the frame is a zero quantized block further includes the following steps:

computing a value for a feature for the given block;

comparing the value of the feature for the given block with a first threshold;

changing the first threshold to a second threshold;

computing a value for the feature for the next given block; and

comparing the value of the feature for the next given block with the second threshold.

14. A video encoder for processing a sequence of frames of video data, each frame comprising a plurality of blocks, with each block containing values representative of the video data to be encoded, comprising:

a motion estimation engine having an input for receiving the sequence of frames, and an output;

a frame type decision engine having an input coupled to the output of the motion estimation engine, and an output;

a QP decision engine having an input coupled to the output of the frame type decision engine, and an output;

a zero quantized block locator having an input coupled to the output of the QP engine, the zero quantized block locator operating to determined whether a given block is a zero quantized block using an optimal threshold value determined experimentally by using a plurality of experimental blocks and a plurality of experimental threshold values;

the zero quantized block locator producing a first output indicative of the detection of a zero quantized block, and a second output representative of the given block;

a DCT engine having an input coupled to the second output of the zero quantized block locator for receiving the values of the given block, the DCT engine further including an output;

a quantization engine having an input coupled to the output of the DCT engine, and an output; and

a variable length coding engine having an input coupled to the output of the quantization engine, and a bit stream output representing the coded values of the given block;

wherein an experimental result of encoding the plurality of experimental blocks using each of the plurality of experimental threshold values is compared with an actual result of encoding the plurality of blocks without using the plurality of experimental threshold values.

15. The video encoder of claim 14, wherein the zero quantized block locater further includes:

an engine for computing the mean absolute error of all the values in the given block; and

a comparator for comparing the mean absolute error with a predetermined threshold.

16. The video encoder of claim 14, wherein the zero quantized block locater further includes:

an engine for computing the mean square error of all the values in the given block; and

a comparator for comparing the mean square error with a predetermined threshold.

17. The video encoder of claim 14, wherein the zero quantized block locater further includes:

an engine for computing the block variance of all the values in the given block; and

a comparator for comparing the block variance with a predetermined threshold.

18. The video encoder of claim 14, wherein the zero quantized block locater further includes:

an engine for computing the mean absolute difference of all the values in the given block; and

a comparator for comparing the mean absolute difference with a predetermined threshold.

19. The video encoder of claim 14, wherein the zero quantized block locater further includes:

an engine for determining the maximum of all the values in the given block; and

a comparator for comparing the maximum with a predetermined threshold.

20. The video encoder of claim 14, wherein the zero quantized block locater further includes:

a first engine for determining the mean absolute error of all the values in the given block;

a first comparator for comparing the mean absolute error with a first predetermined threshold;

a second engine for determining the mean square error of all the values in the given block;

a second comparator for comparing the mean square error with a second predetermined threshold;

a third engine for determining the block variance of all the values in the given block;

a third comparator for comparing the block variance with a third predetermined threshold;

a fourth engine for determining the mean absolute difference of all the values in the given block;

a fourth comparator for comparing the mean absolute difference with a fourth predetermined threshold;

a fifth engine for determining the maximum of all the values in the given block;

a fifth comparator for comparing the maximum with a fifth predetermined threshold; and

means coupled to the first, second, third, fourth and fifth comparators for determining whether the mean absolute error, the mean square error, the block variance, the mean absolute difference and the maximum are all less than or equal to each of their respective thresholds.

21. The video encoder of claim 14,

wherein the zero quantized block locater further includes:

a selector which selects a desired feature to be used in determining whether the given block is a zero quantized block;

a first engine for computing the value of a first feature for the given block;

a first comparator for comparing the value of the first feature for the given block with a first threshold;

a second engine for computing the value of a second feature for the given block;

a second comparator for comparing the value of the second feature for the given block with a second threshold;

wherein the selector is coupled to the first and second engines for selectively enabling one of the first engine or the second engine.

22. The video encoder of claim 21, wherein the first and second features can be selected from a group consisting of:

the mean absolute value of the given block;

the mean square error of the given block;

the block variance;

the mean absolute difference of the given block; and

the maximum value in the given block.

23. The video encoder of claim 14, wherein the zero quantized block locater further includes:

a first engine for calculating a first feature of all the values in the given block;

a first comparator for comparing the value of the first feature with a first predetermined threshold;

a second engine for calculating a second feature of all the values in the given block;

a second comparator for comparing the value of the second feature with a second predetermined threshold;

means for classifying the given block as a zero-quantized block if the values of the first and second features are all less than or equal to each of the first and second thresholds, respectively.

24. A method of encoding video data, comprising the steps of:

performing motion estimation on a sequence of frames, each frame comprising a plurality of blocks;

classifying each frame as either an I frame, a P frame, or a B frame;

determining the quantization step size for each block or group of blocks;

classifying each block as a zero quantized block or a non-zero quantized block using an optimal threshold value;

performing DCT, quantization, zig-zag scan and variable length coding on the non-zero quantized blocks; and

skipping the DCT, quantization, zig-zag scan and variable length coding steps for the zero quantized blocks;

wherein the optimal threshold value is determined experimentally using a plurality of experimental blocks and a plurality of experimental threshold values, and wherein an experimental result of encoding the plurality of experimental blocks using each of the plurality of experimental threshold values is compared with an actual result of encoding the plurality of blocks without using the plurality of experimental threshold values.

25. A method of encoding video data, the method comprising the steps of:

performing motion estimation on a sequence of frames, each frame comprising a plurality of blocks;

determining the quantization step size for each block of the plurality of blocks;

selecting a feature of each block of the plurality of blocks;

selecting a constant value associated with the feature;

generating a threshold value by multiplying the quantization step size by the constant value;

classifying each block as a zero quantized block or a non-zero quantized block based on a comparison of the feature with the threshold value;

performing DCT, quantization, zig-zag scan and variable length coding on the non-zero quantized blocks; and

skipping the DCT, quantization, zig-zag scan and variable length coding steps for the zero quantized blocks;

wherein the constant value is determined experimentally using a plurality of experimental blocks and a plurality of experimental constant values, and wherein an experimental result of encoding the plurality of experimental blocks using each of the plurality of experimental threshold values is compared with an actual result of encoding the plurality of blocks without using the plurality of experimental threshold values.

26. The method of claim 25, wherein the feature is one of mean absolute value of the block, mean square error of the block, variance of the block, mean absolute difference of the block or maximum value in the block.