Method and apparatus for video coding

• US 20020025001A1
• Filed: 04/27/2001
• Published: 02/28/2002
• Est. Priority Date: 05/11/2000
• Status: Active Grant

• Current Assignee: Cisco Systems Canada Co. (Cisco Systems, Inc.)
• Original Assignee: UB Video, Inc. (Cisco Systems, Inc.)
• Inventors: Kossentini, Faouzi, Docef, Alen, Ismaeil, Ismaeil R.
• Granted Patent: US 6,876,703 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search

Abstract

A video coding method progressively refines a predicted motion vector to obtain an estimated motion vector. Subsequent steps are omitted if the estimated motion vector matches a current macroblock. Variable matching thresholds can permit dynamic adjustment of image quality and computational cost to optimize encoding performance for available computational resources. The method permits control of desired encoding speed and bit rate by adjusting encoding parameters. Video coders according to the invention may comprise a motion estimator, transform computer and coder each of which operates according to one or more parameters. A speed rate control and/or a bit rate control may adjust the parameters to maintain a desired encoding speed and output bit rate. A coder according to the invention may be implemented in software running on a general purpose computer. The method may be used in block-based video encoders including MPEG-2 and H.263 encoders.

Claims

1. A method for obtaining an estimated motion vector for use in block-based video encoding, the method comprising:

refining a predicted motion vector for a current block to obtain an estimated motion vector in a sequence comprising a plurality of steps; and

,

before each of a plurality of the steps in the sequence,

computing a similarity value between the block and another block indicated by the current estimated motion vector,

comparing the similarity value to a threshold, and

not performing subsequent steps in the sequence if the comparison indicates that the current estimated motion vector provides a match between the current block and the another block which is better than a match corresponding to the threshold.

2. The method of claim 1 wherein the similarity measure is a sum of absolute differences.

3. The method of claim 1 comprising obtaining the predicted motion vector by computing a similarity measure between the block and each of a plurality of other blocks indicated by prior estimated motion vectors previously computed for a plurality of previously encoded nearby blocks and using as the predicted motion vector one of the prior estimated motion vectors for which the similarity measure indicates a best match for the current block.

4. The method of claim 3 wherein the similarity measure used in obtaining the predicted motion vector is a sum of absolute differences.

5. The method of claim 3 wherein the plurality of nearby blocks comprise a block immediately to the left of the current block, a block immediately above the current block and a block above and to the right of the current block.

6. The method of claim 5 wherein the plurality of nearby blocks comprise a block in the same position as the current block in an immediately preceding frame.

7. The method of claim 1 wherein refining the predicted motion vector comprises performing one or more frame motion estimation steps followed by one or more field motion estimation steps.

8. The method of claim 7 wherein the frame motion estimation steps include a low resolution frame motion estimation step, a full pel frame motion estimation step and a half pel frame motion estimation step.

9. The method of claim 7 wherein the field motion estimation steps comprise a low resolution field motion estimation step, a full pel field motion estimation step and a half pel field motion estimation step.

10. The method of claim 1 wherein refining the predicted motion vector comprises performing one or more frame motion estimation steps and, before the frame motion estimation steps, computing a first similarity value between the current block and a block identified by the predicted motion vector, comparing the first similarity value to a first threshold, and using the predicted motion vector as the estimated motion vector if the comparison indicates that the block identified by the predicted motion vector provides a better match than the first threshold.

11. The method of claim 10 wherein the frame motion estimation steps comprise a low resolution frame motion estimation step and a full pel frame motion estimation step and the method comprises computing a second similarity value between the current block and a block identified by the estimated motion vector of the low resolution frame motion estimation step, comparing the second similarity value to a second threshold, and not performing the full pel frame motion estimation step if the comparison indicates that the block identified by estimated motion vector of the low resolution frame motion estimation step provides a better match than the second threshold.

12. The method of claim 11 wherein the frame motion estimation steps comprise a half pel frame motion estimation step and the method comprises computing a third similarity value between the current block and a block identified by the estimated motion vector of the full pel frame motion estimation step, comparing the third similarity value to a third threshold, and not performing the half pel frame motion estimation step if the comparison indicates that the block identified by estimated motion vector of the full pel frame motion estimation step provides a better match than the third threshold.

13. The method of claim 12 comprising computing a fourth similarity value between the current block and a block identified by the estimated motion vector of the frame motion estimation steps, comparing the fourth similarity value to a fourth threshold, and performing one or more field motion estimation steps if the comparison indicates that the block identified by estimated motion vector of the frame motion estimation steps provides a match poorer than the fourth threshold.

14. The method of claim 13 wherein the field motion estimation steps comprise a low resolution field motion estimation step and a full pel field motion estimation step and the method comprises computing a fifth similarity value between the current block and a block identified by the estimated motion vector of the low resolution field motion estimation step, comparing the fifth similarity value to a fifth threshold, and not performing the full pel field motion estimation if the comparison indicates that the block identified by estimated motion vector of the low resolution field motion estimation step provides a better match than the fifth threshold.

15. The method of claim 14 wherein the field motion estimation steps comprise a half pel field motion estimation step and the method comprises computing a sixth similarity value between the current block and a block identified by the estimated motion vector of the full pel field motion estimation step, comparing the sixth similarity value to a sixth threshold, and not performing the half pel field motion estimation step if the comparison indicates that the block identified by estimated motion vector of the full pel frame motion estimation step provides a better match than the sixth threshold.

16. The method of any one of claims 1 to 15 comprising computing a seventh similarity value between the current block and a block identified by the estimated motion vector, comparing the seventh similarity value to a seventh threshold, and not performing a quantized DCT operation on the current block if the comparison indicates that the block identified by estimated motion vector provides a match better than the seventh threshold.

17. The method of claim 1 wherein obtaining the estimated motion vector comprises a full pel motion estimation step followed by a half pel motion estimation step and the method comprises computing a first similarity value between a current block and another block indicated by the current estimated motion vector prior to the full pel motion estimation step comparing the first similarity value to a threshold, and, if the comparison indicates a match better than the threshold not carrying out either the full pel motion estimation step or the half pel motion estimation step.

18. The method of claim 17 comprising computing a second similarity value between a current block and another block indicated by the current estimated motion vector after the full pel motion estimation step and prior to the half pel motion estimation step, comparing the second similarity value to a second threshold, and, if the comparison indicates a match better than the second threshold not carrying out the half pel motion estimation step.

20. A program product comprising a medium carrying a set of computer-readable signals containing computer-executable instructions which, when run by a computer, cause the computer to execute the method of claim 1.

21. A video coding method comprising:

providing a video encoder comprising at least a motion vector estimator, a transformation computer and a coder, running on a computer platform, the video encoder operating in a manner determined by a plurality of parameters;

providing a plurality of sets of parameters, each set of parameters causing the video encoder to provide a different balance between output quality and computation;

configuring the video encoder with a first one of the sets of parameters;

measuring a time taken for the video encoder to encode a series of blocks;

if the time taken exceeds a predetermined time, configuring the video encoder with a second one of the sets of parameters;

wherein the video encoder encodes with less computation when configured with the second set of parameters than it does when configured with the first set of parameters.

22. The video coding method of claim 21 wherein the parameters comprise a plurality of thresholds, and the method includes obtaining estimated motion vectors for blocks by performing a plurality of motion estimation steps;

and, before at least two of the plurality of motion estimation steps computing a similarity value between the block and another block indicated by the current estimated motion vector, comparing the similarity value to a threshold, and not performing one or more subsequent motion estimation steps if the comparison indicates that the current estimated motion vector provides a match between the current block and the another block which is better than a match corresponding to a corresponding one of the thresholds.

23. The video coding method of claim 22 wherein the motion estimation steps are performed in a sequence and each of the motion estimation steps requires more computation than the motion estimation step which precedes it.

24. The video coding method of claim 21 wherein the transformation computer performs a quantized discrete cosine transformation and the method comprises:

determining a volume of output encoded video data corresponding to a quantity of input video data, comparing the volume to a threshold and, if the volume exceeds the threshold, increasing a value for a quantum step used in the discrete cosine transformation so as to reduce a bit rate of the output encoded video data.

25. A program product comprising a medium carrying a set of computer-readable signals containing computer-executable instructions which, when run by a computer, cause the computer to execute the method of claim 21.

27. The method of claim 26 wherein the transformation step comprises performing a quantized discrete cosine transform operation.

28. The method of claim 27 comprising computing a second similarity measure between the current block and a block identified by the estimated motion vector for the current block, comparing the first similarity measure to a threshold;

and, if the comparison indicates that the match between the current block and a block identified by the estimated motion vector for the current block is better than the threshold, in the transformation step setting the transformed residual to zero.

29. A program product comprising a medium carrying a set of computer-readable signals containing computer-executable instructions which, when run by a computer, cause the computer to execute the method of claim 26.

30. The method of claim 26 comprising tracking a number of computations and terminating the encoding for a current block if the number of computations exceeds a threshold value.

26. A video coding method comprising sequentially processing a plurality of blocks in an input video signal to produce an encoded output video signal, the processing for each of the blocks comprising obtaining an estimated motion vector for each block by taking each block, in turn, as a current block and:

a) for each current block determining an initial estimated motion vector, computing a first similarity measure between the current block and a block identified by the initial estimated motion vector and comparing the first similarity measure to a threshold;

b) if the comparison indicates that the match between the current block and a block identified by the initial estimated motion vector is better than the threshold, using the initial estimated motion vector as an estimated motion vector for the current block and proceeding to a transformation step; and

,

c) if the comparison indicates that the match between the current block and a block identified by the initial estimated motion vector is worse than the threshold, performing one or more motion vector refinement steps on the initial estimated motion vector to produce an estimated motion vector for the current block before proceeding to the transformation step.

31. A video coder comprising

a motion vector estimator;

a transformation computer;

a coder;

a memory holding a plurality of sets of parameters, a selected one of the sets of parameters causing the motion vector estimator, transformation computer and coder to encode an input video signal with a balance between output quality and computation; and

,

a speed control comprising a timer connected to measure a time taken for the video encoder to encode a series of one or more blocks, the speed control adapted to select an alternative one of the sets of parameters which encodes with less computation than a currently selected one of the sets of parameters in response to detecting that the time taken is longer than a threshold time.