Method for encoding and decoding video information, a motion compensated video encoder and a corresponding decoder

• US 6,711,211 B1
• Filed: 05/08/2000
• Issued: 03/23/2004
• Est. Priority Date: 05/08/2000
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Mobile Phones UK Limited (Nokia Corporation)
• Inventors: Lainema, Jani
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US09/566,020
• Time in Patent Office: 1,415 Days
• Field of Search: H04/N.712, H04/N 1.102, H04/N 1.104, 375/240.12, 375/240.24, 375/240.25, 375/240.26, 375/240.27, 382/238, 382/239, 348/394.1, 348/401.1, 348/417.1, 348/418.1
• US Class Current: 375/240.24
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/567 Motion estimation based on rate distortion criteria

Abstract

A method for encoding video information is presented, where a piece of current video information is segmented into macroblocks and a certain number of available macroblock segmentations for segmenting a macroblock into blocks is defined. Furthermore, for each available macroblock segmentation at least one available prediction method is defied, each of which prediction methods produces prediction motion coefficients for blocks within said macroblock, resulting in a certain finite number of available macroblock-segmentation—prediction-method pairs. For a macroblock, one of the available macroblock-segmentation—prediction-method pairs is selected, and thereafter the macroblock is segmented into blocks and prediction motion coefficients for the blocks within said macroblock are produced using the selected macroblock-segmentation—prediction-method pair. A corresponding decoding method, an encoder and a decoder are also presented.

Claims

1. A method for encoding video information including deriving prediction motion coefficients for blocks within a macroblock of a video frame being encoded from motion coefficients of at least one prediction block that is a previously encoded macroblock or block within said video frame, the method comprising:

segmenting the video frame into macroblocks;

defining a certain number of available macroblock segmentations that specify possible ways in which a macroblock can be segmented into blocks;

defining for each available macroblock segmentation at least one available prediction method thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

selecting for a macroblock one of the available macroblock-segmentation—

prediction-method pairs; and

segmenting the macroblock into blocks and deriving prediction motion coefficients for the blocks within said macroblock using the selected macroblock-segmentation—

prediction-method pair.

2. A method for encoding video information according to claim 1, wherein at least one of the available macroblock-segmentation—

prediction-method pairs defines the prediction motion coefficients for a block within said macroblock to be derived from the motion coefficients of only one prediction block.

3. A method for encoding video information according to claim 1, wherein at least one of the available macroblock-segmentation—

prediction-method pairs defines that the prediction motion coefficients for a block within said macroblock are derived from the motion coefficients of at least a first prediction block and a second prediction block.

4. A method for encoding video information according to claim 3, wherein the prediction motion coefficients for a block are derived from a median of the motion coefficients of at least a first prediction block and a second prediction block.

5. A method for encoding video information according to claim 1, wherein at least one of the available macroblock-segmentation—

prediction-method pairs specifies that the prediction motion coefficients for a block within said macroblock are derived from motion coefficients of prediction blocks within said macroblock.

6. A method for encoding video information according to claim 1, wherein a prediction block to be used in producing prediction motion coefficients for a block is defined as a block comprising a certain predetermined pixel, whose location is defined relative to said block.

7. A method for encoding video information according to claim 6, wherein the location of a predetermined pixel for a first block is different from the location of a predetermined pixel for a second block.

8. A method for encoding video information according to claim 1, wherein the number of prediction blocks per block is at most a certain number in any of the macroblock-segmentation—

prediction-method pairs.

9. A method for encoding video information according to claim 8, wherein the number of prediction blocks per block is at most three.

10. A method for encoding video information according to claim 9, wherein a prediction block to be used in producing prediction motion coefficients for a block is defined as a block comprising a certain predetermined pixel, whose location is defined relative to said block.

11. A method for encoding video information according to claim 10, wherein at least for certain first blocks relating to certain first macroblock-segmentation—

prediction-method pairs the predetermined pixels comprise the uppermost pixel adjacent to the block from the left, the leftmost pixel superjacent to the block and the pixel corner to corner with the upper right-hand pixel of the block.

12. A method for encoding video information according to claim 1, wherein the macroblocks and the blocks resulting from the macroblock segmentations are quadrilateral.

13. A method for encoding video information according to claim 12, wherein the blocks resulting from the macroblock segmentations are rectangular.

14. A method for encoding video information according to claim 12, wherein the available macroblock segmentations comprise a first macroblock segmentation resulting in one block, a second macroblock segmentation dividing a macroblock once with a vertical line, a third macroblock segmentation dividing a macroblock once with a horizontal line, a fourth macroblock segmentation dividing a macroblock once with a vertical line and once with a horizontal line, a fifth macroblock segmentation dividing a macroblock once with a vertical line and thrice with a horizontal line, and a sixth macroblock segmentation dividing a macroblock thrice with a vertical line and once with a horizontal line.

15. A method for encoding video information according to claim 12, wherein one prediction method is defined for each available macroblock segmentation, a prediction block for a block is defined as a block comprising a certain predetermined pixel, whose location is defined relative to said block, prediction coefficients for certain first blocks are derived from the motion coefficients of only one block-specific prediction block and prediction coefficients for certain second blocks are derived from the motion coefficients of more than one block-specific prediction blocks.

16. A method for encoding video information according to claim 1, wherein the macroblock segmentation of neighboring macroblocks affects the selection of a available macroblock-segmentation—

prediction-method pair for a macroblock.

17. A method for encoding video information according to claim 1, wherein selection of the macroblock-segmentation—

prediction-method pair is based on minimizing a cost function.

18. A method for encoding video information according to claim 1, wherein one macroblock-segmentation—

prediction-method pair is defined for each available macroblock segmentation.

19. A method for encoding video information according to claim 18, further comprising transmitting information indicating the selected macroblock segmentation to a decoder or storing information indicating the selected macroblock-segmentation—

prediction-method pair in a storage medium.

20. A method for encoding video information according to claim 1, further comprising transmitting information indicating the selected macroblock-segmentation—

prediction-method pair to a decoder or storing information indicating the selected macroblock-segmentation—

prediction-method pair in a storage medium.

21. A method for encoding video information according to claim 1, further comprising:

estimating the motion of blocks within a macroblock with respect to a reference video frame;

representing the motion of the blocks within the macroblock with a model comprising a set of basis functions and motion coefficients; and

representing the motion coefficients thus obtained as a sum of the prediction motion coefficients and difference motion coefficients.

22. A method for encoding video information according to claim 21, wherein the model used to represent the motion of a block is a translational motion model.

23. A method for encoding video information according to claim 21, wherein the selection of the macroblock-segmentation—

prediction-method pair is based on minimizing a cost function which includes at least a measure of a reconstruction error relating to a macroblock-segmentation—

prediction-method pair and a measure of an amount of information required to indicate the macroblock-segmentation—

prediction-method pair and to represent the difference motion coefficients of the blocks within said macroblock.

24. A method for encoding video information according to claim 21, further comprising:

transmitting information indicating the selected macroblock-segmentation—

prediction-method pair to a decoder or storing information indicating the selected macroblock-segmentation—

prediction-method pair in a storage medium; and

transmitting information about the difference motion coefficients to a decoder or storing information about the difference motion coefficients in a storage means.

25. A method for encoding video information according to claim 21, further comprising:

reconstructing the motion of the blocks using the motion coefficients, basis functions and information about the macroblock segmentation;

determining predicted video information using the reference video frame and the reconstructed motion of the blocks;

determining corresponding prediction error video information based on a difference between the predicted video information and the video information of the macroblock;

coding the prediction error video information and representing it with prediction error coefficients; and

transmitting information about the prediction error coefficients to a decoder or storing information about the prediction error coefficients in a storage means.

26. A method for decoding encoded video information, including deriving prediction motion coefficients for blocks within a macroblock of a video frame being decoded from motion coefficients of at least one prediction block that is a previously decoded macroblock or block within said video frame, the method comprising:

defining a certain number of available macroblock segmentations that specify possible ways in which a macroblock can be segmented into blocks;

defining for each available macroblock segmentation at least one available prediction method, thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

receiving information indicating at least the macroblock segmentation selected for a macroblock in said encoded video information; and

determining the prediction method relating to the macroblock segmentation of said macroblock with reference to the defined macroblock-segmentation—

prediction method pairs and producing prediction motion coefficients for blocks within said macroblock using the determined prediction method.

27. A method for decoding encoded video information according to claim 26, wherein at least two prediction methods relating to a certain available macroblock segmentation are defined.

28. A method for decoding encoded video information according to claim 26, wherein only one prediction method is defined for each available macroblock segmentation.

29. A method for decoding encoded video information according to claim 26, further comprising:

receiving information about difference motion coefficients describing motion of blocks within a macroblock; and

reconstructing motion coefficients for the blocks within said macroblock as a sum of the derived prediction motion coefficients and the difference motion coefficients.

30. A method for decoding encoded video information according to claim 29, further comprising;

receiving information about prediction error coefficients describing prediction error video information, and

determining a decoded piece of current video information using at least the motion coefficients and the prediction error video information.

31. A method for decoding encoded video information according to claim 26, wherein the step of receiving information indicating at least the macroblock segmentation selected for a macroblock in said encoded video information comprises receiving an indication of a selected macroblock-segmentation—

prediction method pair.

32. An encoder for performing motion compensated encoding of video information, said encoder being arranged to derive prediction motion coefficients for blocks within a macroblock of a video frame being encoded from motion coefficients of at least one prediction block that is a previously encoded macroblock or block within said video frame, the encoder comprising:

means for receiving a frame of video information;

means for segmenting the frame of video information into macroblocks;

means for specifying a certain number of available macroblock segmentations that define possible ways in which a macroblock can be segmented into blocks;

means for specifying at least one available prediction method for each available macroblock segmentation, thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

means for selecting one macroblock-segmentation—

prediction method pair among the available macroblock-segmentation—

prediction method pairs;

means for segmenting a macroblock using the macroblock segmentation specified by the selected macroblock-segmentation—

prediction-method pair; and

means for deriving macroblock-segmentation-specific prediction motion coefficients for blocks within said macroblock using the prediction method specified by the selected macroblock-segmentation—

prediction-method pair.

33. An encoder for performing motion compensated encoding of video information according to claim 32, further comprising:

memory means for storing a reference video frame;

means for estimating a motion field of blocks in the frame of video information using at least the reference video frame;

means for producing motion coefficients describing the estimated motion fields; and

means for producing difference motion coefficients using the motion coefficients and the prediction motion coefficients.

34. A storage device comprising an encoder according to claim 32.

35. A mobile station comprising an encoder according to claim 32.

36. A network element comprising an encoder according to claim 32.

37. A network element according to claim 36, wherein the network element is a network element of a mobile telecommunication network.

38. An encoder for performing motion compensated encoding of video information according to claim 32, wherein at least one of the available macroblock-segmentation—

prediction-method pairs defines the prediction motion coefficients for a block within said macroblock to be derived from the motion coefficients of only one prediction block.

39. An encoder for performing motion compensated encoding of video information according to claim 32, wherein at least one of the available macroblock-segmentation—

prediction-method pairs defines that the prediction motion coefficients for a block within said macroblock are derived from the motion coefficients of at least a first prediction block and a second prediction block.

40. An encoder for performing motion compensated encoding of video information according to claim 39, arranged to derive the prediction motion coefficients for a block from a median of the motion coefficients of at least a first prediction block and a second prediction block.

41. An encoder for performing motion compensated encoding of video information according to claim 32, wherein at least one of the available macroblock-segmentation—

prediction-method pairs specifies that the prediction motion coefficients for a block within said macroblock are derived from motion coefficients of prediction blocks within said macroblock.

42. An encoder for performing motion compensated encoding of video information according to claim 32, arranged to derive prediction motion coefficients for a block using a prediction block that comprises a certain predetermined pixel, whose location is defined relative to said block.

43. An encoder for performing motion compensated encoding of video information according to claim 32, arranged to select a macroblock-segmentation—

prediction-method responsive to minimizing a cost function.

44. An encoder for performing motion compensated encoding of video information according to claim 32, wherein one macroblock-segmentation—

prediction-method pair is defined for each available macroblock segmentation.

45. An encoder for performing motion compensated encoding of video information according to claim 44, further arranged to transmit information indicating the selected macroblock segmentation to a corresponding decoder.

46. An encoder for performing motion compensated encoding of video information according to claim 32, further arranged to transmit information indicating the selected macroblock-segmentation—

prediction-method pair to a corresponding decoder.

47. An encoder for performing motion compensated encoding of video information according to claim 32, further comprising:

means for estimating the motion of blocks within a macroblock with respect to a reference video frame;

means for representing the motion of the blocks within the macroblock with a model comprising a set of basis functions and motion coefficients; and

means for representing the motion coefficients thus obtained as a sum of the prediction motion coefficients and difference motion coefficients.

48. An encoder for performing motion compensated encoding of video information according to claim 47, arranged to select a macroblock-segmentation—

prediction-method pair by minimizing a cost function that includes at least a measure of a reconstruction error relating to the macroblock-segmentation—

prediction-method pair and a measure of an amount of information required to indicate the macroblock-segmentation—

prediction-method pair and to represent the difference motion coefficients of the blocks within said macroblock.

49. An encoder for performing motion compensated encoding of video information according to claim 47, further comprising:

means for reconstructing the motion of the blocks using the motion coefficients, basis functions and information about the macroblock segmentation;

means for determining predicted video information using the reference video frame and the reconstructed motion of the blocks;

means for determining corresponding prediction error video information based on a difference between the predicted video information and the video information of the macroblock;

means for coding the prediction error video information and representing it with prediction error coefficients; and

means for transmitting information about the prediction error coefficients to a corresponding decoder.

50. A decoder for performing motion compensated decoding of encoded video information, said decoder being arranged to derive prediction motion coefficients for blocks within a macroblock of a video frame being decoded from motion coefficients of at least one prediction block that is a previously decoded macroblock or block within said video frame, the decoder comprising:

means for defining a certain number of available macroblock segmentations that specify possible ways in which a macroblock can be segmented into blocks;

means for specifying at least one available prediction method for each available macroblock segmentation, thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

input means for receiving information indicating at least the macroblock segmentation selected for a macroblock;

means for determining the prediction method relating to the segmentation of the macroblock with reference to the defined macroblock-segmentation—

prediction-method pairs; and

means for producing prediction motion coefficients for blocks within said macroblock using the determined prediction method.

51. A decoder for performing decoding of encoded video information according to claim 50, further comprising:

input means for receiving information about difference motion coefficients of the blocks within said macroblock, and means for constructing motion coefficients using the prediction motion coefficients and the difference motion coefficients.

52. A mobile station comprising a decoder according to claim 50.

53. A decoder for performing motion compensated decoding of encoded video information according to claim 50, arranged to receive an indication of a selected macroblock-segmentation—

prediction method pair.

54. Computer program element for performing motion compensated encoding of video information, said computer program element being arranged to derive prediction motion coefficients for blocks within a macroblock of a video frame being encoded from motion coefficients of at least one prediction block that is a previously encoded macroblock or block within said video frame, the computer program element comprising:

program means for receiving a frame of video information;

program means for segmenting the frame of video information into macroblocks;

program means for specifying a certain number of available macroblock segmentation, that define possible ways in which a macroblock can be segmented into blocks;

program means for specifying at least one available prediction method for each available macroblock segmentation, thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

program means for selecting one macroblock-segmentation—

prediction method pair among the available macroblock-segmentation—

prediction method pairs;

program means for segmenting a macroblock using the selected macroblock segmentations specified by the selected macroblock-segmentation—

prediction-method pair; and

program means for deriving macroblock-segmentation-specific prediction motion coefficients for blocks within said macroblock using the selected prediction method specified by the selected macroblock-segmentation—

prediction-method pair.

55. Computer program element as specified in claim 54, embodied on a computer readable medium.

56. Computer program element for performing motion compensated decoding of encoded video information, said computer program element being arranged to derive prediction motion coefficients for blocks within a macroblock of a video frame being decoded from motion coefficients of at least one prediction block that is a previously decoded macroblock or block within said video frame, the computer program element comprising:

program means for defining a certain number of available macroblock segmentations that specify possible ways in which a macroblock can be segmented into blocks;

program means for specifying at least one available prediction method for each available macroblock segmentation, thereby providing a certain finite number of available macroblock-segmentation—

prediction-method pairs, each prediction method defining a method for deriving prediction motion coefficients for blocks within a macroblock using motion coefficients of at least one prediction block;

program means for receiving information indicating at least the macroblock-segmentation selected for a macroblock;

program means for determining the prediction-method relating to the segmentation of the macroblock with reference to the defined macroblock-segmentation—

prediction-method pairs; and

program means for producing prediction motion coefficients for blocks within said macroblock using the determined prediction method.

57. Computer program element as specified in claim 56, embodied on a computer readable medium.