Method and apparatus for coding motion information

• US 20040264573A1
• Filed: 06/28/2004
• Published: 12/30/2004
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Bossen, Frank Jan
• Granted Patent: US 7,978,769 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/52 by predictive encoding
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Video compression algorithms typically represent visual information by a combination of motion and texture data. Motion data describes the temporal relationship between the content of a frame and that of a previous frame. This invention describes a method and apparatus for efficiently encoding motion data, particularly in the presence of horizontal and/or vertical motion boundaries.

Claims

1. A method for coding a data element, the method comprising:

computing a plurality of predictions from a first plurality of previously coded data elements;

computing a context based on a second plurality of previously coded data elements;

selecting one of the plurality of predictions to obtain a selected prediction;

encoding an indication of the selected prediction using the context; and

encoding a data element difference between the selected prediction and the data element.

2. The method defined in claim 1 wherein the data element comprises a motion vector.

3. The method defined in claim 1 wherein the plurality of predictions comprises two predictions.

4. The method defined in claim 3 wherein the two predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded and a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being coded.

5. The method defined in claim 4 wherein the data element is a motion vector.

6. The method defined in claim 4 wherein the first and second sides comprise above and to the left, respectively, of the block containing the data element being coded.

7. The method defined in claim 1 wherein the plurality of predictions is three or more predictions, and wherein the three or more predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded, a second prediction that is equal to a data element associated with a block located on a second side of the block associated the data element being coded, and one or more additional predictions that are equal to data elements associated with blocks located in proximity to the first block.

8. The method defined in claim 1 wherein the first plurality of previously coded data elements is not equal to the second plurality of previously coded data elements.

9. The method defined in claim 1 wherein the context is based on data elements associated with neighboring blocks.

10. The method defined in claim 9 wherein the neighboring blocks include a first block located above a block associated with the data element being coded, a second block located to the left of the block associated the data element being coded, and a third block located above the second block

11. The method defined in claim 1 wherein encoding the data element difference between the selected prediction and the data element comprises subtracting the selected prediction from the data element.

12. The method defined in claim 1 wherein encoding the indication of the selected prediction occurs if the plurality of predictions are not equal to each other.

13. The method defined in claim 1 wherein encoding the indication of the selected prediction and encoding the data element difference are performed using an arithmetic encoder.

14. An encoder for outputting zero or more bits in response to an input of a data element, the encoder comprising:

a prediction generator to generate a plurality of predictions from a first plurality of previously coded data elements;

a context generator to compute a context based on a second plurality of previously coded data elements;

a prediction selector to select one of the plurality of predictions to obtain a selected prediction;

a prediction comparator to compare the plurality of predictions;

a differentiator to compute a data element difference between the selected prediction and the data element; and

an entropy encoder to encode an indication of the selected prediction using the context and to decode the data element difference.

15. The encoder defined in claim 14 wherein the data element comprises a motion vector.

16. The encoder defined in claim 14 wherein the plurality of predictions comprises two predictions.

17. The encoder defined in claim 16 wherein the two predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded and a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being coded.

18. The encoder defined in claim 17 wherein the data element is a motion vector.

19. The encoder defined in claim 17 wherein the first and second sides comprise above and to the left, respectively, of the block containing the data element being coded.

20. The encoder defined in claim 14 wherein the plurality of predictions is three or more predictions, and wherein the three or more predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded, a second prediction that is equal to a data element associated with a block located on a second side of the block associated the data element being coded, and one or more additional predictions that are equal to data elements associated with blocks located in proximity to the first block.

21. The encoder defined in claim 14 wherein the first plurality of previously coded data elements is not equal to the second plurality of previously coded data elements.

22. The encoder defined in claim 14 wherein the context is based on data elements associated with neighboring blocks.

23. The encoder defined in claim 22 wherein the neighboring blocks include a first block located above a block associated with the data element being coded, a second block located to the left of the block associated the data element being coded, and a third block located above the second block

24. The encoder defined in claim 14 wherein the differentiator generates the data element difference by subtracting the selected prediction from the data element.

25. The encoder defined in claim 14 wherein the entropy encoder encodes the indication of the selected prediction only if the plurality of predictions are not equal to each other.

26. The encoder defined in claim 14 wherein entropy encoder comprises an arithmetic encoder.

27. An article of manufacture having one or more recordable media storing instructions thereon which, when executed by a system, cause the system to perform a method comprising:

computing a plurality of predictions from a first plurality of previously coded data elements;

computing a context based on a second plurality of previously coded data elements;

selecting one of the plurality of predictions to obtain a selected prediction;

encoding an indication of the selected prediction using the context; and

encoding a data element difference between the selected prediction and the data element.

28. An apparatus comprising:

means for computing a plurality of predictions from a first plurality of previously coded data elements;

means for computing a context based on a second plurality of previously coded data elements;

means for selecting one of the plurality of predictions to obtain a selected prediction;

means for encoding an indication of the selected prediction using the context; and

means for encoding a data element difference between the selected prediction and the data element.

29. A method for decoding a data element, the method comprising:

computing a plurality of predictions from a first plurality of previously decoded data elements;

computing a context based on a second plurality of previously decoded data elements;

decoding an indication of a selected prediction using the context;

selecting the selected prediction, from the plurality of predictions based on the indication;

decoding a data element difference; and

adding the data element difference to the selected prediction to obtain the data element.

30. The method defined in claim 29 further comprising:

comparing the plurality of predictions, wherein decoding the indication of the selected prediction occurs if the plurality of predictions are not equal to each other.

31. The method defined in claim 29 wherein the data element comprises a motion vector.

32. The method defined in claim 29 wherein the plurality of predictions comprises two predictions.

33. The method defined in claim 32 wherein the two predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being decoded and a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being decoded.

34. The method defined in claim 33 wherein the data element is a motion vector.

35. The method defined in claim 33 wherein the first and second sides comprise above and to the left, respectively, of the block containing the data element being decoded.

36. The method defined in claim 29 wherein the plurality of predictions is three or more predictions, and wherein the three or more predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded, a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being coded, and one or more additional predictions that are equal to data elements associated with blocks located in proximity to the first block.

37. The method defined in claim 29 wherein the first plurality of previously decoded data elements is not equal to the second plurality of previously decoded data elements.

38. The method defined in claim 29 wherein the context is based on data elements associated with neighboring blocks.

39. The method defined in claim 38 wherein the neighboring blocks include a first block located above a block associated with the data element being coded, a second block located to the left of the block associated the data element being coded, and a third block located above the second block

40. The method defined in claim 29 wherein decoding the indication of the selected prediction and decoding a data element difference are performed using an arithmetic decoder.

41. A decoder to output a data element in response to an input of zero or more bits representing a data element, the decoder comprising:

a prediction generator to compute a plurality of predictions from a first plurality of previously decoded data elements;

a context generator to compute a context based on a second plurality of previously decoded data elements;

an entropy decoder to decode an indication of a selected prediction using the context and a data element difference;

a prediction selector to select the selected prediction, from the plurality of predictions, based on the indication;

an adder to add the data element difference to the selected prediction to obtain the data element.

42. The decoder defined in claim 41 further comprising:

a comparator to compare the plurality of predictions, wherein the entropy decoder decodes the indication of the selected prediction if the comparator indicates that the plurality of predictions are not equal to each other.

43. The decoder defined in claim 41 wherein the data element comprises a motion vector.

44. The decoder defined in claim 41 wherein the plurality of predictions comprises two predictions.

45. The decoder defined in claim 44 wherein the two predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being decoded and a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being decoded.

46. The decoder defined in claim 45 wherein the data element is a motion vector.

47. The decoder defined in claim 45 wherein the first and second sides comprise above and to the left, respectively, of the block containing the data element being decoded.

48. The decoder defined in claim 41 wherein the plurality of predictions is three or more predictions, and wherein the three or more predictions comprises a first prediction that is equal to a data element associated with a first block located on a first side of a block associated with the data element being coded, a second prediction that is equal to a data element associated with a block located on a second side of the block associated with the data element being coded, and one or more additional predictions that are equal to data elements associated with blocks located in proximity to the first block.

49. The decoder defined in claim 41 wherein the first plurality of previously decoded data elements is not equal to the second plurality of previously decoded data elements.

50. The decoder defined in claim 41 wherein the context is based on data elements associated with neighboring blocks.

51. The decoder defined in claim 50 wherein the neighboring blocks include a first block located above a block associated with the data element being coded, a second block located to the left of the block associated the data element being coded, and a third block located above the second block

52. The decoder defined in claim 41 wherein the entropy decoder comprises an arithmetic decoder.

53. An article of manufacture having one or more recordable media storing instructions thereon which, when executed by a system, cause the system to perform a method comprising:

computing a plurality of predictions based on a first plurality of previously decoded data elements;

computing a context based on a second plurality of previously decoded data elements;

decoding an indication of a selected prediction using the context;

selecting the selected prediction, from the plurality of predictions, based on the indication;

decoding a data element difference; and

adding the data element difference to the selected prediction to obtain the data element.

54. An apparatus comprising:

means for computing a plurality of predictions based on a first plurality of previously decoded data elements;

means for computing a context based on a second plurality of previously decoded data elements;

means for decoding an indication of a selected prediction using the context;

means for selecting the selected prediction, from the plurality of predictions, based on the indication;

means for decoding a data element difference; and

means for adding the data element difference to the selected prediction to obtain the data element.

55. A prediction generator comprising:

a memory for storing a first prediction and a second prediction;

a comparator coupled to the memory to compare the first prediction and the second prediction; and

a controller coupled to the comparator to update the second prediction while the first and second predictions are equal and a stop condition is not satisfied.

56. A method comprising:

setting first and second predictions;

comparing the first and second predictions; and

updating the second prediction if the first and second predictions are equal and a stop condition is not satisfied.