Video coding system

• US 7,200,174 B2
• Filed: 05/19/2003
• Issued: 04/03/2007
• Est. Priority Date: 01/21/2000
• Status: Expired due to Term

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Nokia Corporation
• Inventors: Karczewicz, Marta, Lainema, Jani
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US10/440,841
• Publication Number:
  US 20030202596A1
• Time in Patent Office: 1,415 Days
• Field of Search: 348/699, 348/700, 348/701, 348/394.1, 348/408.1, 348/407.1, 348/416.1, 375/240.12, 375/240.08, 375/240.16, 375/240.21, 375/240.01
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/52 by predictive encoding
• CPC Class Codes: H04N 19/521 for estimating the reliability of the determined motion vectors or motion vector field, e.g. for smoothing the motion vector field or for correcting motion vectors
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 19/557 Motion estimation characterised by stopping computation or iteration based on certain criteria, e.g. error magnitude being too large or early exit
• 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 motion estimation method and system for a video coder are disclosed. The system comprises an input for a video image to be coded. It also comprises a hierarchical series of motion estimators of varying complexity, for estimating a motion vector field between the received image and a reference image. The subsequent motion estimator in the series is selected by a control means if a prediction error associated with the motion vector field estimated by the currently selected motion estimator exceeds a predetermined threshold. When available, inherited and predicted motion information is used to improve prediction quality.

Claims

1. An encoder for performing motion compensated encoding of a sequence of video frames having picture elements, the encoder comprising:

a memory for storing a reference frame;

a motion field estimation block arranged to refine a set of prediction motion coefficients, previously estimated for an at least one first picture element of a current frame, by using a series of motion estimation methods of varying complexity to generate a first candidate set of motion coefficients for a second picture element of the current frame, and arranged to select either a set of initial motion coefficients or motion coefficients estimated using the reference frame as a selected set of motion coefficients, and to refine the set of selected motion coefficients by using a series of motion estimation methods of varying complexity to generate a second candidate set of motion coefficients for the at least one second picture element of the current frame; and

a motion field coding block for comparing the first candidate set of motion coefficients and the second candidate set of motion coefficients in order to choose one set of motion coefficients to be used to represent motion of the second picture element.

2. An encoder according to claim 1, wherein a refinement motion field estimation block is arranged to generate the first candidate set of motion coefficients by using a series of motion estimation methods of varying complexity and a full motion field estimation block is arranged to generate the second candidate set of motion coefficients by using a series of motion estimation methods of varying complexity.

3. An encoder according to claim 2, wherein the refinement motion field estimation block is arranged to generate the first candidate set of motion coefficients and an associated measure of prediction error and the full motion field estimation block is arranged to generate the second candidate set of motion coefficients and an associated measure of prediction error.

4. An encoder according to claim 3, wherein the motion field coding block is arranged to compare the measure of prediction error associated with the first candidate set of motion coefficients and the measure of prediction error associated with the second candidate set of motion coefficients in order to choose the one set of motion coefficients to be used to represent motion of the second picture element.

5. An encoder according to claim 1, wherein the motion field estimation block inherits the set of initial motion coefficients from motion estimation performed previously for a master segment overlapping the current segment.

6. An encoder according to claim 1, wherein the set of prediction motion coefficients refined by the motion field estimation block is a set of motion coefficients previously estimated for at least one picture element neighbouring the second picture element.

7. An encoder according to claim 1, wherein the set of prediction motion coefficients refined by the motion field estimation block is a set of motion coefficients calculated by using a set of motion coefficients previously estimated for more than one picture element neighbouring the second picture element.

8. An encoder according to claim 1, wherein the set of prediction motion coefficients refined by the motion field estimation block is a set of motion coefficients averaged from motion information previously estimated for more than one picture element neighbouring the second picture element.

9. An encoder according to claim 1, further comprising segmentation means for segmenting a video frame into picture elements.

10. A method according to claim 1, wherein if a set of prediction motion coefficients is not available the motion field coding block is arranged to choose the second candidate set of motion coefficients as the one set of motion coefficients to be used to represent the motion of the second picture element.

11. An encoder according to claim 1, wherein if a set of initial coefficients is not available, the motion field estimation block is arranged to select a set of motion coefficients estimated using the reference frame as the selected set of motion coefficients.

12. An encoder according to claim 1, wherein the motion field estimation block is arranged to refine respectively the set of prediction motion coefficients and the selected set of motion coefficients in steps and to choose a motion model, and a minimisation method for minimising the measure of prediction error.

13. An encoder according to claim 1, wherein the motion field estimation block is arranged to select a subsequent motion estimation method in the series of motion methods if the measure of prediction error obtained by using a currently selected motion estimation method exceeds a predetermined threshold.

14. An encoder according to claim 1, wherein the series of motion estimation methods used by the motion field estimation block to refine the set of prediction motion coefficients comprises a hierarchy of motion models of different complexities.

15. An encoder according to claim 14, wherein the hierarchy of motion models comprises a zero motion model, a translational motion model and an affine motion model.

16. An encoder according to claim 1, wherein the measure of prediction error is any one of the following:

a mean square prediction error, a mean absolute prediction error, and a rate-distortion Lagrangian.

17. A codec comprising an encoder according to claim 1 and a decoder.

18. A mobile terminal comprising an encoder according to claim 1.

19. A data communications network comprising an encoder according to claim 1.

20. A method for performing motion compensated encoding of a sequence of video frames having picture elements, the method comprising the steps of:

storing a reference frame;

when a set of prediction motion coefficients previously estimated for an at least one first picture element of a current frame is available, refining the set of prediction motion coefficients by using a series of motion estimation methods of varying complexity to generate a first candidate set of motion coefficients for a second picture element of the current frame;

selecting either a set of initial motion coefficients or motion coefflcients estimated using the reference frame as a selected set of motion coefficients, refining the set of selected motion coefficients by using a series of motion estimation methods of varying complexity to generate a second candidate set of motion coefficients for the second picture element of the current frame; and

comparing the first candidate set of motion coefficients and the second candidate set of motion coefficients in order to choose one set of motion coefficients to be used to represent motion of the second picture element.

21. A method according to claim 20, wherein the first candidate set of motion coefficients and an associated measure of prediction error and the second candidate set of motion coefficients and an associated measure of predicLion error is generated.

22. An method according to claim 21, wherein the measure of prediction error associated with the first candidate set of motion coefficients is compared with the measure of prediction error associated with the second candidate set of motion coefficients in order to choose the one set of motion coefficients to be used to represent motion of the second picture element.

23. A method according to claim 20, wherein the set of initial motion coefficients is inherited from motion estimation performed previously for a master segment overlapping the current segment.

24. A method according to claim 20, wherein the set of prediction motion coefficients is a set of motion coefficients previously estimated for at least one picture element neighbouring the second picture element.

25. A method according to claim 20, wherein the set of prediction motion coefficients is a set of motion coefficients calculated by using a set of motion coefficients previously estimated for more than one picture of element neighbouring the second picture element.

26. A method according to claim 20, wherein the set of prediction motion coefficients is a set of motion coefficients averaged from motion information previously estimated for more than one picture element neighbouring the second picture element.

27. A method according to claim 20, wherein once the one set of motion coefficients to be used to represent the motion of the second picture element has been chosen, steps 2, 3 and 4 are repeated for another picture element of the current frame.

28. A method according to claim 20, wherein if a set of prediction motion coefficients is not available, steps 2 and 4 are not performed and the second candidate set of motion coefficients is chosen as the one set of motion coefficients to be used to represent the motion of the second picture element.

29. A method according to claim 20, wherein if a set of initial coefficients is not available, operation 3 comprises selecting a set of motion coefficients estimated using the reference frame as the selected set of motion coefficients, refining the set of selected motion coefficients by using a series of motion estimation methods of varying complexity to generate the second candidate set of motion coefficients and an associated measure of prediction error for the second picture element of the current frame.

30. A method according to claim 20, wherein refinement of the set of prediction motion coefficients in step 2 and refinement of the set of selected motion coefficients in step 3 is performed in steps and at each step of refinement a motion model and a minimisation method for minimising the measure of prediction error.

31. A method according to claim 20, wherein a subsequent motion estimation method in the series of motion methods used in step 2 to refine the set of prediction motion coefficients is selected for use if the measure of prediction error obtained by using a currently selected motion estimation method exceeds a predetermined threshold.

32. A method according to claim 20, wherein a subsequent motion estimation method in the series of motion methods used in step 3 to refine the set of selected motion coefficients is selected for use if the measure of prediction error obtained by using a currently selected motion estimation method exceeds a predetermined threshold.

33. A method according to claim 20, wherein the series of motion estimation methods used in step 2 to refine the set of prediction motion coefficients and the series of motion estimation methods used in step 3 to refine the set of selected motion coefficients comprise a hierarchy of motion models of different complexities.

34. A method according to claim 20, wherein the measure of prediction error is any one of the following:

a mean square prediction error, a mean absolute prediction error, and a rate-distortion Lagrangian.