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

Patent 8077779 Issued on December 13, 2011. Estimated Expiration Date:

January 10, 2027. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Video signal encoding apparatus
Patent #: 5394190
Issued on: 02/28/1995
Inventor: Yamada

Management of channel buffer in video decoders
Patent #: 5398072
Issued on: 03/14/1995
Inventor: Auld

Method for masking transmission errors of MPEG compressed pictures
Patent #: 5436664
Issued on: 07/25/1995
Inventor: Henry

Motion compensating apparatus
Patent #: 5483286
Issued on: 01/09/1996
Inventor: Kim

Variable length data decoder for use with MPEG encoded video data
Patent #: 5502493
Issued on: 03/26/1996
Inventor: Meyer

Video recording/reproducing apparatus which uses a differential motion vector determined using two other motion vectors
Patent #: 5647049
Issued on: 07/08/1997
Inventor: Odaka, et al.

Hierarchical motion estimation for interlaced video
Patent #: 5737023
Issued on: 04/07/1998
Inventor: Linzer

Image motion estimation system which derives candidate block from interpolated motion vectors
Patent #: 5745183
Issued on: 04/28/1998
Inventor: Lam

Scalable encoding apparatus and method with improved function of scaling motion vector
Patent #: 6018368
Issued on: 01/25/2000
Inventor: Kim, et al.

Adaptive real-time encoding of video sequence employing image statistics
Patent #: 6040861
Issued on: 03/21/2000
Inventor: Boroczky, et al.

More ...

Inventors

Assignee

Apple Inc.

Application

No. 11621977 filed on 01/10/2007

US Classes:

375/240.26Associated signal processing

Examiners

Primary: Philippe, Gims S

Attorney, Agent or Firm

Adeli & Tollen LLP

Foreign Patent References

2003256494 AU 02/01/2004
2003258142 AU 06/01/2004
2008201106 AU 04/01/2008
2009202255 AU 07/01/2009
2491741 CA 01/01/2004
2502004 CA 04/01/2011
1014729 EP 06/01/2000
1111934 EP 06/01/2001
1120969 EP 08/01/2001
1 406 453 EP 04/01/2004
1532746 EP 05/01/2005
1579689 EP 09/01/2005
1976299 EP 10/01/2008
03764499 EP 09/01/2010
2276180 EP 01/01/2011
2276181 EP 01/01/2011
11155447 EP 02/01/2011
11155484 EP 02/01/2011
11155497 EP 02/01/2011
08005966 EP 04/01/2011
2317662 EP 05/01/2011
2326019 EP 05/01/2011
2326020 EP 05/01/2011
10177289 EP 05/01/2011
1115547 EP 06/01/2011
2328277 EP 06/01/2011
2328278 EP 06/01/2011
2328279 EP 06/01/2011
2328280 EP 06/01/2011
2328281 EP 06/01/2011
2328282 EP 06/01/2011
2328283 EP 06/01/2011
2328284 EP 06/01/2011
10177276 EP 06/01/2011
11152144 EP 06/01/2011
11152174 EP 06/01/2011
11152176 EP 06/01/2011
11155376 EP 06/01/2011
11155377 EP 06/01/2011
11155378 EP 06/01/2011
11155381 EP 06/01/2011
11155383 EP 06/01/2011
11155384 EP 06/01/2011
11155385 EP 06/01/2011
11155386 EP 06/01/2011
11155387 EP 06/01/2011
11155388 EP 06/01/2011
11155408 EP 06/01/2011
11155409 EP 06/01/2011
11155414 EP 06/01/2011
11155431 EP 06/01/2011
11155434 EP 06/01/2011
11155437 EP 06/01/2011
11155440 EP 06/01/2011
11155441 EP 06/01/2011
11155442 EP 06/01/2011
11155444 EP 06/01/2011
11155445 EP 06/01/2011
11155448 EP 06/01/2011
11155462 EP 06/01/2011
11155463 EP 06/01/2011
11155464 EP 06/01/2011
11155467 EP 06/01/2011
11155479 EP 06/01/2011
11155487 EP 06/01/2011
11155489 EP 06/01/2011
11155490 EP 06/01/2011
11155491 EP 06/01/2011
11155492 EP 06/01/2011
11155493 EP 06/01/2011
11155494 EP 06/01/2011
11155496 EP 06/01/2011
11155498 EP 06/01/2011
2343815 EP 07/01/2011
2343816 EP 07/01/2011
2343817 EP 07/01/2011
2343818 EP 07/01/2011
2343819 EP 07/01/2011
2343820 EP 07/01/2011
2343821 EP 07/01/2011
2343822 EP 07/01/2011
2343823 EP 07/01/2011
2343824 EP 07/01/2011
2343825 EP 07/01/2011
2343826 EP 07/01/2011
2343827 EP 07/01/2011
2343828 EP 07/01/2011
2343829 EP 07/01/2011
2343830 EP 07/01/2011
2343896 EP 07/01/2011
2346177 EP 07/01/2011
2346178 EP 07/01/2011
2346179 EP 07/01/2011
2346180 EP 07/01/2011
2346181 EP 07/01/2011
2346182 EP 07/01/2011
2346183 EP 07/01/2011
2346184 EP 07/01/2011
2346185 EP 07/01/2011
2346186 EP 07/01/2011
2346187 EP 07/01/2011
06-319112 JP 11/01/1994
10-174065 JP 06/01/1998
10-215449 JP 08/01/1998
2001-005958 JP 01/01/2001
2001-069530 JP 03/01/2001
2001-136528 JP 05/01/2001
1999-0036646 KR 05/01/1999
10-0274434 KR 12/01/2000
2001112806 KR 12/01/2001
110332 SG 04/01/2007
WO 2004/008654 WO 01/01/2004
WO 2004/032357 WO 04/01/2004
WO 2004/054257 WO 06/01/2004

International Class

H04N 7/12

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.

Other References

U.S. Appl. No. 13/161,494, filed Jun. 15, 2011, Haskell, Berin Geoffry, et al.
U.S. Appl. No. 13/161,491, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,486, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,484, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,482, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,481, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,480, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,478, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,476, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,474, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 13/161,473, filed Jun. 15, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 11/779,660, Mailing Date May 9, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 11/779,615, Mailing Date May 13, 2011, Haskell, Barin Geoffry, et al.
Sullivan, Gary, “(Draft) Report of Fairfax Meeting,” Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, May 6-10, 2002, JVT-0001d3.
Kondo, Satoshi, et al., “Proposal of Minor Changes to Multi-Fram Buffering Syntax for Improving Coding Efficiency of B-pictures,” Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Jan. 29-Feb. 1, 2002, JVT-B057.
Kondo, Satoshi, et al., “New Prediction Method to Improve B-picture Coding Efficiency,” ITU-Telecommunications Standardization Sector, Dec. 2-6, 2001, VCEG-O26.
Jeon, B., “B picture coding for sequence with repeating scene changes,” Joint Video Team (JVT) of IOS/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6), May 6-10, 2002, JVT-C120.
Haskell, Barry G., et al.,“Variable Accuracy Inter-Picture Timing Specification for Video,” Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6), Jul. 22-26, 2002, JVT-D124r1.
Author Unknown, “Working Draft No. 2, Revision 0 (WD-2),” Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Jan. 29-Feb. 1, 2002, JVT-B118r1.
U.S. Appl. No. 11/621,980, Mailing Date May 13, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 11/621,979, Mailing Date May 13, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 11/835,732, Mailing Date May 6, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 11/835,727, Mailing Date Apr. 13, 2011, Haskell, Barin Geoffry, et al.
Author Unknown, “MPEG Continues its Work Across All Aspects of its Multimedia Charter,” Jul. 29, 2002, International Organisation for Standardisation, Klagenfurt, Austria.
SG Search Report and Written Opinion for SG 200702807-9, Jan. 6, 2010 (mailing date), Apple Inc.
EP Office Action of EP08005966.0, May 12, 2010 (mailing date), Apple Inc.
EP Office Action of EP03764499.4, Dec. 2, 2009 (mailing date), Apple Inc.
EP Office Action of EP03764499.4, May 5, 2010 (mailing date), Apple Inc.
AU Office Action of AU 2008201106, Sep. 13, 2010 (mailing date), Apple Computer, Inc.
Updated portions of prosecution history of U.S. Appl. No. 11/835,773, Dec. 12, 2008, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/835,732, Dec. 7, 2010, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 12/689,157, Jul. 29, 2010, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,971, May 10, 2010, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,969, Dec. 2, 2010, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 10/792,669, May 24, 2007, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 10/291,320, Jan. 12, 2005, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of EP03812763, Mar. 15, 2011 (mailing date), Apple Inc.
Updated portions of prosecution history of EP08005966, Mar. 10, 2011 (mailing date), Apple Inc.
Updated portions of prosecution history of EP03764499, Mar. 24, 2010 (mailing date), Apple Inc.
Portions of prosecution history of U.S. Appl. No. 12/972,419, Mar. 16, 2011, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,969, Mar. 16, 2011, Haskell, Barin Geoffry, et al.
SG Examination Report for SG 200702807-9, Jan. 10, 2010 (mailing date), Apple Inc.
Portions of prosecution history of U.S. Appl. No. 11/779,660, Mar. 8, 2011, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/779,615, Mar. 9, 2011, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,980, Jan. 12, 2011, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,979, Dec. 17, 2010, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/835,727, Jan. 19, 2011, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 12/972,419, filed Dec. 17, 2010, Haskell, Barin Geoffry, et al.
Updated portions of prosecution history of U.S. Appl. No. 11/621,969, Feb. 10, 2011, Haskell, Barin Geoffry, et al.
International Preliminary Examination Report for PCT/US2003/024953, Mar. 17, 2004 (mailing date), Apple Computer, Inc.
International Search Report for PCT/US2003/024953, Jan. 27, 2004 (mailing date), Apple Computer, Inc.
Written Opinion for PCT/US2003/021714, Apr. 21, 2004 (mailing date), Apple Computer, Inc.
International Preliminary Examination Report for PCT/US2003/021714, Sep. 2, 2004 (mailing date), Apple Computer, Inc.
International Search Report for PCT/US2003/021714, Nov. 14, 2003 (mailing date), Apple Computer, Inc.
Non-Final Office Action of U.S. Appl. No. 11/835,773, Aug. 8, 2008 (mailing date), Haskell, et al.
Non-Final Office Action of U.S. Appl. No. 11/835,739, Aug. 11, 2008 (mailing date) Haskell, et al.
Supplemental Notice of Allowability of U.S. Appl. No. 10/792,514, Nov. 5, 2007 (mailing date), Haskell, et al.
Notice of Allowance of U.S. Appl. No. 10/792,514, Sep. 25, 2007 (mailing date), Haskell, et al.
Notice of Allowance of U.S. Appl. No. 10/313,773, Dec. 2, 2003 (mailing date), Haskell, et al.
Notice of Allowance and Restriction Requirement of U.S. Appl. No. 10/792,669, Jun. 26, 2007 (mailing date), Haskell, et al.
Notice of Allowance of U.S. Appl. No. 10/291,320, Mar. 6, 2006 (mailing date), Haskell, et al.
Non-Final Office Action of U.S. Appl. No. 10/291,320, Aug. 15, 2005 (mailing date), Haskell, et al.
Final Office Action of U.S. Appl. No. 10/291,320, Jul. 12, 2004 (mailing date), Haskell, et al.
Non-Final Office Action of U.S. Appl. No. 10/291,320, Oct. 23, 2003 (mailing date), Haskell, et al.
Weigand, Thomas, “Working Draft No. 2, Revision 0 (WD-2)”, JVT of ISO/IEC MPEG and ITU-T VCEG, document JVT-B118, Mar. 13, 2002.
Weigand, Thomas, “Working Draft No. 2, Revision 0 (WD-2)”, JVT of ISO/IEC MPEG and ITU-T VCEG, document JVT-B118, Mar. 13, 2003.
Kwong-Keung Leung, Nelson H.C. Yung, Paul Y.S. Cheung, “Parallelization methodology for video coding—an implementation on TMS32OC8O,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 10, No. 8, pp. 1413-1425, Dec. 2000.
Michael Horowitz, Anthony Joch, and F. Kossentini, “H.264/AVC Baseline Profile Decoder Complexity Analysis,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, No. 7, pp. 704-716, Jul. 2003.
Chen, P. Zhou, and Y. He, “Fast motion estimation for JVT,” ISO/IEC JTC 1/SC29/WG11 and ITU-T SG16 Q.6, document JVT-G016, 2003.
ISO/IEC JTC 1/SC29/WG 11, “Report of the formal verification tests on AVC, document N6231,” Dec. 2003.
MPEG-4 Video Group, “MPEG-4 video verification model version 18.0,” ISO/IEC JTC1/SC29/WG11 N3908, Jan. 2001.
ISO/IEC 14496-10, “Advanced Video Coding: H.264/AVC—reference software,” 2002.
Multiple authors, “Special issue on the H.264/AVC video coding standard,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, No. 7, Jul. 2003.
ISO/IEC 14496-10, “Information technology—coding of audio-visual objects—Part 10: Advanced video coding”; also ITU-T Recommendation H.264: “Advanced video coding for generic audiovisual services”, 2003.
ISO/IEC 14496-2, “Information technology—coding of audio-visual objects—Part 2: Visual,” 2001.
ISO/IEC, “Information technology—generic coding of moving pictures and associated audio information: Video,” 13818-2, 1995.
ISO/IEC, “Information technology—coding of moving pictures and associated audio for digital storage media at up to about 1.5 mbits/s: Video,” 11172-2, 1993.
Weigand, Thomas, “Working Draft No. 2, Revision 0 (WD-2)”, JVT of ISO/IEC MPEG and ITU-T VCEG, document JVT-B118, Dec. 3, 2001.
ISO/IEC 14496-10, “Information technology—coding of audio-visual objects—Part 10: Advanced video coding,” Oct. 2004.
ITU-T Recommendation H.264: “Advanced video coding for generic audiovisual services”, May 2003; also ISO/IEC 14496-10, “Information technology—coding of audio-visual objects—Part 10: Advanced video coding”, 2003.
ISO/IEC, “Information Technology—coding of moving pictures and associated audio for digital storage media at up to about 1,5 mbits/s—Part 2: Video,” 11172-2:1993, Aug. 2006.
Communication for Canadian Application 2491741, Feb. 11, 2009 (mailing Date), Apple Inc.
Examiner's Report for Canadian Application 2491741, Jun. 9, 2008 (mailing Date), Apple Inc.
Extended European Search Report for EP08005966.0, Oct. 31, 2008 (mailing date), Apple Computer, Inc.
Communication for EP03764499.4, Feb. 12, 2009 (mailing date), Apple Inc.
Supplemental European Search Report for EP03764499.4, Oct. 31, 2008 (Mailing Date), Apple Computer, Inc.
Non-Final Office Action of U.S. Appl. No. 11/621,974, Mar. 12, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Restriction Requirement of U.S. Appl. No. 11/621,974, Jan. 12, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Non-Final Office Action of U.S. Appl. No. 11/621,971, Jun. 2, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Non-Final Office Action of U.S. Appl. No. 11/621,971, Jan. 2, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Restriction Requirement of U.S. Appl. No. 11/621,971, Oct. 17, 2008 (mailing Date), Haskell, Barin Geoffry et al.
Restriction Requirement of U.S. Appl. No. 11/621,969, Jun. 24, 2009 (mailing date), Haskell, Barin Geoffry et al.
Non-Final Office Action of U.S. Appl. No. 11/621,969, Dec. 29, 2008 (mailing date), Haskell, Barin Geoffry et al.
Notice of Allowance of U.S. Appl. No. 11/835,773, Feb. 6, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Notice of Allowance of U.S. Appl. No. 11/835,739, Feb. 13, 2009 (mailing Date), Haskell, Barin Geoffry et al.
Advisory Action of U.S. Appl. No. 10/291,320, Feb. 3, 2005 (mailing Date), Haskell, Barin Geoffry et al.
Author Unknown, “Text of Committee Draft of Joint Video Specification (ITU-T Rec. H.264/ ISO/IEC 14496-10 AVC)”, JVT, May 2002, Fairfax, VA.
Jeon, Byeong-Moon, “Clean Up for Temporal Direct Mode”, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6), Oct. 2002.
Schlockermann, Martin, “Improvement of Temporal Direct Mode”, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6), Oct. 18, 2002.
Wiegand, Thomas, “Text of Final Committee Draft of Joint video Specification (ITU-T Rec. H.264/ ISO/IEC 14496-10 AVC)”, JVT, Jul. 2002, Klagenfurt, AT.
Supplemental European Search Report for EP 03812763, Dec. 7, 2009 (mailing date), Apple Computer, Inc.
Portions of prosecution history of U.S. Appl. No. 11/621,980, May 11, 2007, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/621,979, May 11, 2007, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 10/792,514, Dec. 21, 2007, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/835,773, Nov. 10, 2008, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/835,739, Nov. 10, 2008, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/835,732, Dec. 18, 2007, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/835,727, Dec. 18, 2007, Haskell, Barin Geoffry, et al.
U.S. Appl. No. 12/689,157, filed Jan. 18, 2010, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/621,974, Sep. 30, 2009, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/621,971, Mar. 9, 2010, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 11/621,969, Mar. 11, 2010, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 10/792,669, Jul. 20, 2007, Haskell, Barin Geoffry, et al.
Portions of prosecution history of U.S. Appl. No. 10/291,320, Dec. 15, 2005, Haskell, Barin Geoffry, et al.
Guy Cote, Berna Erol, Michael Gallant, and Faouzi Kossentini, “H.263+: Video coding at low bit rates,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 8, No. 7, pp. 849-866, Nov. 1998.
ITU-T, “Video coding for low bit rate communication,” Recommendation H.263 Version 2, 1998.
ITU-T, “Video coding for low bit rate communication,” Recommendation H.263, 1996.
Rob Koenen, “Overview of the MPEG-4 standard,” in ISO/IEC JTC1/SC29/WG11 N4668, Mar. 2002.
U.S. Appl. No. 11/779,668, filed Jul. 2007, Haskell et al.
U.S. Appl. No. 11/779,660, filed Jul. 2007, Haskell et al.