direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Source Coding

Prof. Dr.-Ing. Thomas Wiegand

Basic Course Information

  • Term: Winter Semester 2012/2013
  • Instructor: Prof. Dr.-Ing. Thomas Wiegand
  • Co-instructor: Dr.-Ing. Heiko Schwarz
  • Location of Lecture: FT 101
  • Time of Lecture: Thursday, 12:15-13:45
  • Location of Exercises: HHI Lecture Room
  • Time of Exercises: Monday, 14:15-15:45

 

Description

The principles of source coding for efficient transmission and storage are discussed. Based on the fundamentals of information and rate distortion theory, the most relevant techniques used in source coding algorithms are described: entropy coding, quantization as well as predictive and transform coding.

 
Topics

  • Probability, Random Variables, and Processes
  • Lossless Source Coding
  • Rate Distortion Theory
  • Quantization
  • Predictive Coding
  • Transform Coding
  • Sub-band Coding

 

Videos of Lectures and Exercises - Online

 

Textbook

T. Wiegand, H. Schwarz, "Source Coding: Part I of Fundamentals of Source and Video Coding, Foundations and Trends in Signal Processing", 2011

Exercises with Solutions

Source Coding Literature

Abramson, N. M. (1963). Information Theory and Coding. McGraw-Hill, New York, NY, USA.

Ahmed, N., Natarajan, T., and Rao, K. R. (1974). Discrete Cosine Transform. IEEE Transactions on Computers, 23(1):90–93. (PDF, 572,9 KB)

Arimoto, S. (1972). An Algorithm for Calculating the Capacity of an Arbitrary Discrete Memoryless Channel. IEEE Transactions on Information Theory, 18:14–20. (PDF, 808,9 KB)

T. Berger and J. D. Gibson (1998). Lossy Source Coding. IEEE Transactions on Information Theory. 44(6):2693-2723. (PDF, 731,0 KB)

Berger, T. (1971). Rate Distortion Theory. Prentice-Hall, Englewood Cliffs, NJ, USA.

Binia, J., Zakai, M., and Ziv, J. (1974). On the e-Entropy and the Rate-Distortion Function of Certain Non-Gaussian Processes. IEEE Transactions on Information Theory, 20:514–524. (PDF, 1,1 MB)

Blahut, R. E.(1972). Computation of Channel Capacity and Rate-Distortion Functions. IEEE Transactions on Information Theory,18:460–473. (PDF, 1,1 MB)

Bossen, F., Bross, B., Sühring, K., and Flynn, D., HEVC Complexity and Implementation Analysis, IEEE Transactions on Circuits and Systems for Video Technonoly, vol. 22, no. 12, December 2012. (PDF, 2,3 MB)

Burrows, M. and Wheeler, D. (1994). A Block-Sorting Lossless Data Compression Algorithm. Research Report 124, Digital Equipment Corporation, Palo Alto, CA, USA. (PDF, 75,4 KB)

Chang, P.-C. and Gray, R. M. (1986). Gradient Algorithms for Designing Predictive Vector Quantizers. IEEE Transactions on Acoustics, Speech and Signal Processing, 34(4):679–690. (PDF, 1,1 MB)

Chou, P. A., Lookabaugh, T., and Gray, R. M. (1989). Entropy-Constrained Vector Quantization. IEEE Transactions on Acoustics, Speech and Signal Processing, 37(1):31–42. (PDF, 1,3 MB)

Clarke, R. J. (1985). Transform Coding of Images. Academic Press, Orlando, Fla.

Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory. John Wiley and Sons, Hoboken, NJ, USA. 2nd edition.

D. L. Donoho, M. Vetterli, R. A. DeVore, and I. Daubechies (1998). Data Compression and Harmonic Analysis. IEEE Transactions on Information Theory. 44(6):2435-2476. (PDF, 1,1 MB)

Dony, R. D. and Haykin, S. (1995). Optimally, Adaptive Transform Coding. IEEE Transactions on Image Processing, 4(10):1358–1370. (PDF, 1,5 MB)

Effros, M., Feng, H., and Zeger, K. (2004). Suboptimality of the Karhunen-Lo`eve Transform for Transform Coding. IEEE Transactions on Information Theory, 50(8):1605–1619. (PDF, 337,2 KB)

N. Farvardin and J. W. Modestino (1985). Rate-Distortion Performance of DPCM Schemes for Autoregressive Sources. IEEE Transactions on Information Theory. IT-31(3):402-418. (PDF, 2,4 MB)

Gallager, R. G. (1968). Information Theory and Reliable Communication. John Wiley & Sons, New York, USA.

Gallager, R. G. (1978). Variations on a Theme by Huffman. IEEE Transactions on Information Theory, 24(6):668–674. (PDF, 1,1 MB)

Gersho, A. and Gray, R. M. (1992). Vector Quantization and Signal Compression. Kluwer Academic Publishers, Boston, Dordrecht, London.

Gish, H. and Pierce, J. N. (1968). Asymptotically Efficient Quantizing. IEEE Transactions on Information Theory, 14:676–683. (PDF, 950,4 KB)

Golub, G. H. and van der Vorst, H. A.(2000). Eigenvalue Computation in the 20th Century. Journal of Computational and Applied Mathematics, 123:35–65.

Goyal, V. K. (2000). High-Rate Transform Coding: How High is High, and Does it Matter? In Proceedings of the IEEE International Symposium on Information Theory, Sorento, Italy. (PDF, 181,4 KB)

Goyal, V. K. (2001). Theoretical Foundations of Transform Coding. IEEE Signal Processing Magazine, 18(5):9–21. (PDF, 2,0 MB)

Goyal, V. K., Zhuang, J., and Vetterli, M. (2000). Transform Coding with Backward Adaptive Updates. IEEE Transactions on Information Theory, 46(4):1623–1633. (PDF, 393,8 KB)

Gray, R. M. (1990). Source Coding Theory. Kluwer Academic Publishers, Norwell, MA, USA.

Gray, R. M. (2005). Toeplitz and Circulant Matrices: A Review. Foundations and Trends in Communication and Information Theory, 2(3):155–329. (PDF, 504,9 KB)

R. M. Gray (2007). Entropy and Information Theory. Information Systems Laboratory, Electrical Engineering Department. Stanford University. Springer Verlag. (PDF, 1,5 MB)

Gray, R. M. (2010). Linear Predictive Coding and the Internet Protocol. Now Publishers Inc, Boston-Delft. (PDF, 8,7 MB)

Gray, R. M. and Davisson, L. D. (1985). Random Processes: A Mathematical Approach for Engineers. Prentice Hall, Englewood Cliffs, NJ, USA.

Gray, R. M. and Davisson, L. D. (2004). An Introduction to Statistical Signal Processing. Cambridge University Press. (PDF, 2,9 MB)

Gray, R. M. and Gray, A. H. (1977). Asymptotically Optimal Quantizers. IEEE Transactions on Information Theory, 23:143–144. (PDF, 305,5 KB)

Gray, R. M. and Neuhoff, D. L. (1998). Quantization. IEEE Transactions on Information Theory, 44(6):2325–2383. (PDF, 1,4 MB)

Grenander, U. and Szeg¨o, G. (1958). Toeplitz Forms and Their Applications. University of California Press, Berkeley and Los Angeles, USA.

Helle, P., Oudin, S., Bross, B., Marpe, D., Bici, M. O., Ugur, K., Jung, J., Clare, G., and Wiegand, T., Block Merging for Quadtree-Based Partitioning in HEVC, IEEE Transactions on Circuits and Systems for Video Technonoly, vol.22, no. 12, December 2012. (PDF, 4,0 MB)

Huffman, D. A. (1952). A Method for the Construction of Minimum Redundancy Codes. Proc. IRE, pages 1098–1101. (PDF, 1,010,7 KB)

ISO/IEC (1999). Coding of Audio-Visual Objects — Part 2: Visual. ISO/IEC 14496-2.

ITU-T. Narrow-Band Visual Telephone Systems and Terminal Equipment. ITU-T Rec. H.320, 1999. (PDF, 173,6 KB)

ITU-T. Packet-Based Multimedia Communications Systems. ITU-T Rec. H.323, 1998. (PDF, 680,3 KB)

ITU-T. Terminal for Low Bit Rate Multimedia Communication. ITU-T Rec. H.324, 1996. (PDF, 220,9 KB)

ITU-T (1993). Video Codec for Audiovisual Services at px64 kbit/s. ITU-T Rec. H.261. (PDF, 204,4 KB)

ITU-T and ISO/IEC. Advanced Video Coding for Generic Audiovisual Services. ITU-T Rec. H.264 and ISO/IEC 14496-10 (MPEG-4 AVC), Mar. 2010. (PDF, 4,0 MB)

ITU-T and ISO/IEC. Generic Coding of Moving Pictures and Asociated Audio Information — Part 1: Systems. ITU-T Rec. H.222.0 and ISO/IEC 13818-1 (MPEG-2 Systems), Nov. 1994. (PDF, 626,1 KB)

ITU-T and ISO/IEC (1992). Digital Compression and Coding of Continuous-Tone Still Images. ITU-T Rec. T.81 and ISO/IEC 10918-1 (JPEG). (PDF, 1,0 MB)

ITU-T and ISO/IEC (1994). Generic Coding of Moving Pictures and Associated Audio Information — Part 2: Video.ITU-T Rec. H.262 and ISO/IEC 13818-2. (PDF, 1,1 MB)

ITU-T and ISO/IEC (1998). Lossless and Near-Lossless Compression of Continuous-Tone Still Images. ITU-T Rec.T.87 and ISO/IEC 14495-1 (JPEG-LS). (PDF, 476,3 KB)

ITU-T and ISO/IEC (2002). JPEG 2000 Image Coding System – Core Coding System. ITU-T Rec. T.800 and ISO/IEC 15444-1 (JPEG 2000). (PDF, 1,9 MB)

ITU-T and ISO/IEC (2009). JPEG XR Image Coding System – Image Coding Specification. ITU-T Rec. T.832 and ISO/IEC 29199-2 (JPEG XR). (PDF, 1,5 MB)

Jacobi, C. G. J. (1846). Über ein leichtes Verfahren, die in der Theorie der Säcularströmungen vorkommenden Gleichungen numerisch aufzulösen. Journal für reine und angewandte Mathematik, 30:51–94.

Jayant, N. S. and Noll, P. (1994). Digital Coding of Waveforms. Prentice-Hall, Englewood Cliffs, NJ, USA.

Kolmogorov, A. N. (1933). Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer, Berlin, Germany. An English translation by N. Morrison appeared under the title Foundations of the Theory of Probability (Chelsea, New York) in 1950, with a second edition in 1956. (PDF, 2,1 MB)

Linde, Y., Buzo, A., and Gray, R. M. (1980). An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications, 28(1):84–95.

Linder, T. and Zamir, R. (1994). On the Asymptotic Tightness of the Shannon Lower Bound. IEEE Transactions on Information Theory, 40(6):2026–2031.

Linkov, Y. N. (1965). Evaluation of Epsilon Entropy of Random Variables for Small Esilon. Problems of Information Transmission, 1:12–18.

Lloyd, S. P. (1982). Least Squares Quantization in PCM. IEEE Transactions on Information Theory, 28:127–135. Unpublished Bell Laboratories Technical Note, 1957.

Lookabaugh, T. D. and Gray, R. M. (1989). High-Resolution Quantization Theory and the Vector Quantizer Advantage. IEEE Transactions on Information Theory, 35(5):1020–1033. (PDF, 1,2 MB)

Makhoul, J. (1975). Linear Prediction: A Tutorial Review. Proceedings of the IEEE, 63(4):561–580.

Makhoul, J., Roucos, S., and Gish, H. (1985). Vector Quantization in Speech Coding. Proceedings of the IEEE, 73(11):1551–1587.

Malvar, H. S. (1992). Signal Processing with Lapped Transforms. Artech House, Norwood, MA, USA.

Marpe, D., Schwarz, H., and Wiegand, T. Probability Interval Partitioning Entropy Codes. Submitted to IEEE Transactions on Information Theory, 2010. Available at iphome.hhi.de/marpe/download/pipe-subm-ieee10.pdf.

Marpe, D., Schwarz, H., and Wiegand, T. (2003). Context-Adaptive Binary Arithmetic Coding for H.264/AVC. IEEE Transactions on Circuits and Systems for Video Technology, 13(7):620–636.

Max, J. (1960). Quantizing for Minimum Distortion. IRE Transactions on Information Theory, 6(1):7–12.

McDonald, R. A. and Schultheiss, P. M. (1964). Information Rates of Gaussian Signals under Criteria Constraining the Error Spectrum. Proceedings of the IEEE, 52:415–416.5

Moffat, A., Neil, R.M., and Witten, I. H. (1998). Arithmetic Coding Revisited. ACM Transactions on Information Systems, 16(3):256–294. (PDF, 475,8 KB)

Ohm, J.-R., Sullivan, G. J., Schwarz, H., Tan, T. K., and Wiegand, T., Comparison of the Coding Efficiency of Video Coding Standards—Including High Efficiency Video Coding (HEVC), IEEE Transactions on Circuits and Systems for Video Technonoly, vol.22, no. 12, December 2012. (PDF, 6,0 MB)

Ohm, J.-R., Sullivan, G. J., and Wiegand, T., Introduction to the Special Section on the HEVC Standard, IEEE Transactions on Circuits and Systems for Video Technonoly, vol.22, no. 12, December 2012. (PDF, 261,3 KB)

Panter, P. F. and Dite, W. (1951). Quantization Distortion in Pulse Code Modulation with Nonuniform Spacing of Levels. Proc. IRE, 39:44–48.

Papoulis, A. and Pillai, S. U. (2002). Probability, Random Variables and Stochastic Processes. McGraw-Hill, New York, NY, USA.

Pasco, R. (1976). Source Coding Algorithms for Fast Data Compression. Ph.D. dissertation, Stanford University. (PDF, 5,9 MB)

Queiroz, R. L. D. and Tran, T. D. (2001). Lapped Transforms for Image Compression. In The Transform and Data Compression Handbook, pages 197–265, Boca Raton, FL. CRC.

Rissanen, J. (1976). Generalized Kraft Inequality and Arithmetic Coding. IBM J. Res. Develop., 20:198–203. (PDF, 400,7 KB)

Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and Schooler, E. SIP: Session Initiation Protocol. IETF RFC 3261, 2002.

Said, A. (2003). Arithmetic Coding. In Sayood, K., editor, Lossless Compression Handbook. Academic Press, San Diego, CA.

Savari, S. A. and Gallager, R. G. (1997). Generalized Tunstall Codes for Soures with Memory. IEEE Transactions on Information Theory, 43(2):658–668.

Sayood, K., editor (2003). Lossless Compression Handbook. Academic Press, San Diego, CA.

Schulzrinne, H., Casner, S., Frederick, R., and Jacobson, V. RTP: A Transport Protocol for Real-Time Applications. IETF RFC 1889, 1996.

Shannon, C. E. (1948). A Mathematical Theory of Communication. The Bell System Technical Journal, 27(3):2163–2177. (PDF, 3,3 MB)

Shannon, C. E. (1959). Coding Theorems for a Discrete Source with a Fidelity Criterion. IRE National Convention Record, Part 4, pages 142–163.

Shoham, Y. and Gersho, A. (1988). Efficient Bit Allocation for an Arbitrary Set of Quantizers. IEEE Transactions on Acoustics, Speech and Signal Processing, 36:1445–1453. (PDF, 872,5 KB)

Sullivan, G. J., Ohm, J.-R., Han, W.-J., and Wiegand, T., Overview of the High Efficiency Video Coding (HEVC) Standard, IEEE Transactions on Circuits and Systems for Video Technonoly, vol.22, no. 12, December 2012 (PDF, 4,0 MB)

Taubman, D. S. and Marcellin, M. M.(2001). JPEG2000: Image Compression Fundamentals, Standards and Practice. Kluwer Academic Publishers.

Tunstall, B. P. (1967). Synthesis of Noiseless Compression Codes. Ph.D. dissertation, Georgia Inst. Technol.

Usevitch, B. E. (2001). A Tutorial on Mondern Lossy Wavelet Image Compression: Foundations of JPEG 2000. IEEE Signal Processing Magazine, 18(5):22–35.

Vaidyanathan, P. P. (2008). The Theory of Linear Prediction. Morgan & Claypool Publishers.

Vetterli, M. (2001). Wavelets, Approximation, and Compression. IEEE Signal Processing Magazine, 18(5):59–73.

Vetterli, M. and Kovacevic, J. (1995). Wavelets and Subband Coding. Prentice-Hall, Englewood Cliffs, NJ. (PDF, 5,0 MB)

Witten, I. H., Neal, R. M., and Cleary, J. G. (1987). Arithmetic Coding for Data Compression. Communications of the ACM, 30(6):520–540.
(PDF, 1,5 MB)


Ziv, J. and Lempel, A. (1977). A Universal Algorithm for Data Compression. IEEE Transactions on Information Theory, 23(3):337–343.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions