Discrete Cosine Transform DCT on Each 8×8 Block of the Image

The discrete cosine transform (DCT) represents an image as a sum of sinusoids of varying magnitudes and frequencies. The DCT computes the two-dimensional discrete cosine transform (DCT) of an image. The DCT has the property that, for a typical image, most of the visually significant information about the image is concentrated in just a few coefficients of the DCT. For this reason, the DCT is often used in image compression applications. For example, the DCT is at the heart of the international standard lossy image compression algorithm known as JPEG. (The name comes from the working group that developed the standard: the Joint Photographic Experts Group).

The 64 Basis Functions of an 8-by-8 Matrix

The image down shows a combination of horizontal and vertical frequencies for an 8 x 8 ( $N_1 = N_2 = 8$ ) two-dimensional DCT. Each step from left to right and top to bottom is an increase in frequency by 1/2 cycle. For example, moving the right one from the top-left square yields a half-cycle increase in the horizontal frequency. Another move to the right yields two half-cycles. A move down yields two half-cycles horizontally and a half-cycle vertically. The source data (8×8) is transformed to a linear combination of these 64 frequency squares.

Horizontal frequencies increase from left to right, and vertical frequencies increase from top to bottom. The constant-valued basis function at the upper left is often called the DC basis function, and the corresponding DCT coefficient B₀₀ is often called the DC coefficient.

The two-dimensional DCT of an M-by-N matrix A is defined as follows.

The values B_pq are called the DCT coefficients of A. (Note that matrix indices in MATLAB^® always start at 1 rather than 0; therefore, the MATLAB matrix elements A(1,1) and B(1,1) correspond to the mathematical quantities A₀₀ and B₀₀, respectively.)

The DCT is an invertible transform, and its inverse is given by

The inverse DCT equation can be interpreted as meaning that any M-by-N matrix A can be written as a sum of MN functions of the form

These functions are called the basis functions of the DCT. The DCT coefficients B_pq, then, can be regarded as the weights applied to each basis function. For 8-by-8 matrices, the 64 basis functions are illustrated by this image.

Applications

The DCT is the most widely used transformation technique in signal processing,^[9] and by far the most widely used linear transform in data compression.^[10] DCT data compression has been fundamental to the Digital Revolution.^[8] Uncompressed digital media as well as lossless compression had impractically high memory and bandwidth requirements, which was significantly reduced by the highly efficient DCT lossy compression technique,^[7]^[8] capable of achieving data compression ratios from 8:1 to 14:1 for near-studio-quality,^[7] up to 100:1 for acceptable-quality content.^[8] The wide adoption of DCT compression standards led to the emergence and proliferation of digital media technologies, such as digital images, digital photos,^[10] digital video,^[6] streaming media,^[7] digital television, streaming television, video-on-demand (VOD),^[8] digital cinema,^[2] high-definition video (HD video), and high-definition television (HDTV).^[7]

The DCT, and in particular the DCT-II, is often used in signal and image processing, especially for lossy compression, because it has a strong “energy compaction” property:^[5]^[6] in typical applications, most of the signal information tends to be concentrated in a few low-frequency components of the DCT. For strongly correlated Markov processes, the DCT can approach the compaction efficiency of the Karhunen-Loève transform (which is optimal in the decorrelation sense). As explained below, this stems from the boundary conditions implicit in the cosine functions.

DCTs are also widely employed in solving partial differential equations by spectral methods, where the different variants of the DCT correspond to slightly different even/odd boundary conditions at the two ends of the array.

DCTs are also closely related to Chebyshev polynomials, and fast DCT algorithms (below) are used in Chebyshev approximation of arbitrary functions by series of Chebyshev polynomials, for example in Clenshaw–Curtis quadrature.

The DCT is the coding standard for multimedia telecommunication devices. It is widely used for bit rate reduction, and reducing network bandwidth usage.^[1] DCT compression significantly reduces the amount of memory and bandwidth required for digital signals.^[8]

References:

Stanković, Radomir S.; Astola, Jaakko T. (2012). “Reminiscences of the Early Work in DCT: Interview with K.R. Rao” (PDF). Reprints from the Early Days of Information Sciences. 60. Retrieved 13 October 2019.
Britanak, Vladimir; Yip, Patrick C.; Rao, K. R. (2010). Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations. Elsevier. pp. ix, xiii, 1, 141–304. ISBN 9780080464640.
Alikhani, Darya (April 1, 2015). “Beyond resolution: Rosa Menkman’s glitch art”. POSTmatter. Retrieved 19 October 2019.
Thomson, Gavin; Shah, Athar (2017). “Introducing HEIF and HEVC” (PDF). Apple Inc. Retrieved 5 August 2019.
Ahmed, Nasir; Natarajan, T.; Rao, K. R. (January 1974), “Discrete Cosine Transform” (PDF), IEEE Transactions on Computers, C-23 (1): 90–93, doi:10.1109/T-C.1974.223784
Rao, K. R.; Yip, P. (1990), Discrete Cosine Transform: Algorithms, Advantages, Applications, Boston: Academic Press, ISBN 978-0-12-580203-1
Barbero, M.; Hofmann, H.; Wells, N. D. (14 November 1991). “DCT source coding and current implementations for HDTV”. EBU Technical Review. European Broadcasting Union (251): 22–33. Retrieved 4 November 2019.
Lea, William (1994). “Video on demand: Research Paper 94/68”. House of Commons Library. 9 May 1994. Retrieved 20 September 2019.
Ahmed, Nasir (January 1991). “How I Came Up With the Discrete Cosine Transform”. Digital Signal Processing. 1 (1): 4–5. doi:10.1016/1051-2004(91)90086-Z.
“T.81 – Digital compression and coding of continuous-tone still images – Requirements and guidelines” (PDF). CCITT. September 1992. Retrieved 12 July2019.