Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2006-09-12
2006-09-12
Diep, Nhon (Department: 2621)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
07106797
ABSTRACT:
An improved method and block transform for image or video encoding and decoding, wherein transformation and inverse transformation matrixes are defined such that computational complexity is significantly reduced when encoding and decoding. For example, in the two-dimensional inverse transformation of de-quantized transform coefficients into output pixel information during decoding, only four additions plus one shift operation are needed, per co-efficient transformation, all in sixteen-bit arithmetic. Transformations provide correct results because quantization during encoding and de-quantization (sixteen bit) during decoding, via the use of one of three tables selected based on each coefficient's position, have parameter values that already compensate for factors of other transformation multiplications, except for those of a power of two, (e.g., two or one-half), which are performed by a shift operation during the transformation and inverse transformation processes. Computational complexity is significantly reduced with respect to other known transforms without adversely impacting compression or quality.
REFERENCES:
patent: 5325215 (1994-06-01), Shibata et al.
patent: 5357594 (1994-10-01), Fielder
patent: 5379351 (1995-01-01), Fandrianto et al.
patent: 5430556 (1995-07-01), Ito et al.
patent: 5590066 (1996-12-01), Ohki
patent: 5864637 (1999-01-01), Liu et al.
patent: 5970173 (1999-10-01), Lee et al.
patent: 5995539 (1999-11-01), Miller
patent: 6002801 (1999-12-01), Strongin et al.
patent: 6029126 (2000-02-01), Malvar
patent: 6073153 (2000-06-01), Malvar
patent: 6115689 (2000-09-01), Malvar
patent: 6154762 (2000-11-01), Malvar
patent: 6301304 (2001-10-01), Jing et al.
patent: 6324560 (2001-11-01), Malvar
patent: 6363117 (2002-03-01), Kok
patent: 6370502 (2002-04-01), Wu et al.
patent: 6473534 (2002-10-01), Merhav et al.
patent: 6487574 (2002-11-01), Malvar
patent: 6496795 (2002-12-01), Malvar
patent: 6507614 (2003-01-01), Li
patent: 6600785 (2003-07-01), Nishigori et al.
patent: 6687726 (2004-02-01), Schneider
patent: 6694342 (2004-02-01), Mou
patent: 6701019 (2004-03-01), Wu et al.
patent: 6728317 (2004-04-01), Demos
patent: 6831951 (2004-12-01), Yamada
patent: 6882685 (2005-04-01), Malvar
patent: 2002/0154693 (2002-10-01), Demos et al.
patent: 2452343 (2003-01-01), None
patent: 4133460 (1993-04-01), None
patent: 854653 (1998-07-01), None
patent: 2003-348598 (2003-12-01), None
U.S. Appl. No. 60/341,674, filed Dec. 17, 2001, Lee et al.
Liang et al., “Fast Multiplierless Approximation of the DCT with the Lifting Scheme,”Proc. SPIE Apps. of Digital Image Procesing XXIII, 12 pp. (Aug. 2000).
Reader, “History of MPEG Video Compression—Ver. 4.0,”99 pp., document marked Dec. 16, 2003.
ISO/IEC, “ISO/IEC 11172-2, Information technology—Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s—Part 2: Video,” 112 pp. (1993).
ISO/IEC, “JTC1/SC29/WG11 N2202, Information Technology—Coding of Audio-Visual Objects: Visual, ISO/IEC 14496-2,” 329 pp. (1998).
ITU-T, “ITU-T Recommendation H.261, Video Codec for Audiovisual Services at p x 64 kbits,” 25 pp. (1993).
ITU-T, “ITU-T Recommendation H.262, Information Technology—Generic Coding of Moving Pictures and Associated Audio Information: Video,” 205 pp. (1995).
ITU-T, “ITU-T Recommendation H.263, Video coding for low bit rate communication,” 162 pp. (1998).
Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, “Final Joint Committee Draft of Joint Video Specification (ITU-T Recommendation H.264, ISO/IEC 14496-10 AVC,” 206 pp. (Aug. 2002).
Printouts of FTP directories from http://ftp3.itu.ch , 8 pp. (downloaded from the World Wide Web on Sep. 20, 2005.).
Li et al., “On Implementing Transforms from Integers to Integers,”Department of Electrical Engineering, Princeton University, pp. 881-885, Jun. 1998.
Rubino et al., “Improved Chen-Smith Image Coder,”Electrical Engineering Department, Iniversity of Texas at Arlington, pp. 267-270, 1993.
J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,”Math. Computation, vol. 19, pp. 297-301, 1965.
W. Chen, C. H. Smith, and S. C. Fralick, “A fast computational algorithm for the discrete cosine transform,”IEEE Trans. Commun., vol. 25, pp. 1004-1009, Sep. 1977.
H. Malvar, “Fast computation of the discrete cosine transform and the discrete Hartley transform,”IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-35, pp. 1484-1485, Oct. 1987.
C. Loeffler et al., “Practical fast 1-D DCT algorithms with 11 multiplications,”Proc. IEEE ICASSP, vol. 2, pp. 988-991, Feb. 1989.
Arai, et al., “A Fast DCT-SQ Scheme for Images,” The Transactions of the IEICE, vol. E 71, No. 11, Nov. 1988, pp. 1095-1097.
Bjontegaard, “H.26L Test Model Long Term No. 8 (TML-8) Draft 0,”Video Coding Experts Group(VCEG), pp. 1-46.
Calderbank et al., “Wavelet Transforms that Map Integers to Integers,” pp. 1-39 (Aug. 1996).
Cham, “Development of Integer Cosine Transforms by the Principle of Dyadic Symmetry,”IEE Proceedings, vol. 136, Pt. 1, No. 4, pp. 276-282 (Aug. 1989).
Liang et al., “A 16-bit Architecture for H.26L, Treating DCT Transforms and Quantization,”Thirteenth Meeting: Austin, Texas, USA, pp. 1-17 (Apr. 2001).
Ishii et al., “Parallel Variable Length Decoding with Inverse Quantization for Software MPEG-2 Decoders, ” Signal Processing Systems 1997, IEEE, pp. 500-509 (1997).
Jeong et al., “A Fast Algorithm Suitable for DCT Implementation with Integer Multiplication,” Tencon '96, vol. 2, IEEE, pp. 784-787 (1996).
Liang et al., “Approximating the DCT with the Lifting Scheme: Systematic Design and Applications,” Conference Record of the 34thAsilomar Conference, vol. 1, IEEE, pp. 192-196 (Oct. 2000).
Malvar, “Low-complexity Length-4 Transform and Quantization with 16-bit Arithmetic,” Proposal, ITU Study Group 16 Question 6, Video Coding Experts Group, 14thmeeting held Sep. 24-27, 2001 in Santa Barbera, CA, 24 pp.
Pei et al., “The Integer Transforms Analogous to Discrete Trigonometric Transforms,” IEEE Transactions on Signal Processing, vol. 48, No. 12, pp. 3345-3364 (Dec. 2000).
Sriram et al., “MPEG-2 Video decoding on the TMS320C6X DSP Architecture,” Conference Record of the 32ndAsilomar Conference, vol. 2, IEEE, pp. 1735-1739 (1998).
Trac D. Tran, “The BinDCT: Fast Multiplierless Approximation of the DCT,” IEEE Signal Processing Letters, vol. 7, No. 6, pp. 141-144 (Jun. 2000).
Diep Nhon
Klarquist & Sparkman, LLP
Microsoft Corporation
LandOfFree
Block transform and quantization for image and video coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block transform and quantization for image and video coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block transform and quantization for image and video coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3598356