Method and apparatus for variable accuracy inter-picture timing specification for digital video encoding with reduced requirements for division operations

• US 6,728,315 B2
• Filed: 12/06/2002
• Issued: 04/27/2004
• Est. Priority Date: 07/24/2002
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Haskell, Barin Geoffry, Dumitras, Adriana, Singer, David William, Puri, Atul
• Primary Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US10/313,773
• Publication Number:
  US 20040017851A1
• Time in Patent Office: 508 Days
• Field of Search: 375/240.16, 375/240.02, 375/240.24, 375/240.03, 375/240.08, 375/240.15, 382/236, 382/250, 382/253, 348/402.1, 348/413.1, 348/416.1, 348/420.1, 348/584, 348/581
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• 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/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/159 Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/463 by compressing encoding parameters before transmission
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• 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/577 : Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/587 : involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 : in combination with predictive coding
• CPC Class Codes: H04N 19/625 : using discrete cosine transform [DCT]

Abstract

A method and apparatus for performing motion estimation in a digital video system is disclosed. Specifically, the present invention discloses a system that quickly calculates estimated motion vectors in a very efficient manner. In one embodiment, a first multiplicand is determined by multiplying a first display time difference between a first video picture and a second video picture by a power of two scale value. This step scales up a numerator for a ratio. Next, the system determines a scaled ratio by dividing that scaled numerator by a second first display time difference between said second video picture and a third video picture. The scaled ratio is then stored calculating motion vector estimations. By storing the scaled ratio, all the estimated motion vectors can be calculated quickly with good precision since the scaled ratio saves significant bits and reducing the scale is performed by simple shifts.

Claims

1. A method of performing motion estimation in a digital video system, said method comprising:

determining a first multiplicand by multiplying a first display time difference between a first video picture and a second video picture by a power of two value;

determining a scaled ratio by dividing said multiplicand by a second first display time difference between said second video picture and a third video picture; and

storing said scaled ratio for calculating motion vector estimations.

2. The method of performing motion estimation in a digital video system as claimed in claim 1, said method further comprising:

determining a scaled motion vector by multiplying said scaled ratio by a motion vector associated with said first video picture.

3. The method of performing motion estimation in a digital video system as claimed in claim 2, said method further comprising:

dividing said scaled motion vector by said power of two value.

4. The method of performing motion estimation in a digital video system as claimed in claim 3 wherein said dividing is performed by shifting bits of said scaled motion vector.

5. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said power of two value comprises two-hundred and fifty-six.

6. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said power of two value is periodically transmitted across a communication channel.

7. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said determining said scaled ratio by dividing is only performed once per video picture.

8. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said scaled ratio is truncated.

9. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said scaled ratio is rounded to a nearest integer.

10. The method of performing motion estimation in a digital video system as claimed in claim 1 wherein said power of two value comprises a constant.

11. A computer readable medium, said computer readable medium comprising a set of computer instructions for performing motion estimation, said set of computer instructions implementing a set of steps comprising:

determining a first multiplicand by multiplying a first display time difference between a first video picture and a second video picture by a power of two value;

determining a scaled ratio by dividing said multiplicand by a second first display time difference between said second video picture and a third video picture; and

storing said scaled ratio for calculating motion vector estimations.

12. The computer readable medium as claimed in claim 11 wherein said computer instructions further perform the step of:

determining a scaled motion vector by multiplying said scaled ratio by a motion vector associated with said first video picture.

13. The computer readable medium as claimed in claim 12 wherein said computer instructions further perform the step of:

dividing said scaled motion vector by said power of two value.

14. The computer readable medium as claimed in claim 13 wherein said dividing is performed by shifting bits of said scaled motion vector.

15. The computer readable medium as claimed in claim 11 wherein said power of two value comprises two-hundred and fifty-six.

16. The computer readable medium as claimed in claim 11 wherein said power of two value is periodically transmitted across a communication channel.

17. The computer readable medium as claimed in claim 11 wherein said determining said scaled ratio by dividing is only performed once per video picture.

18. The computer readable medium as claimed in claim 11 wherein said scaled ratio is truncated.

19. The computer readable medium as claimed in claim 11 wherein said scaled ratio is rounded to a nearest integer.

20. The computer readable medium as claimed in claim 11 wherein said power of two value comprises a constant.