A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequencies. The DCT, first proposed by Nasir Ahmed in 1972, is a widely used transformation technique in signal processing and data compression. It is used in most digital media, including digital images (such as JPEG and HEIF), digital video (such as MPEG and ), digital audio (such as Dolby Digital, MP3 and AAC), digital television (such as SDTV, HDTV and VOD), digital radio (such as AAC+ and DAB+), and speech coding (such as AAC-LD, Siren and Opus). DCTs are also important to numerous other applications in science and engineering, such as digital signal processing, telecommunication devices, reducing network bandwidth usage, and spectral methods for the numerical solution of partial differential equations.
A DCT is a Fourier-related transform similar to the discrete Fourier transform (DFT), but using only real numbers. The DCTs are generally related to Fourier series coefficients of a periodically and symmetrically extended sequence, whereas DFTs are related to Fourier series coefficients of only periodically extended sequences. DCTs are equivalent to DFTs of roughly twice the length, operating on real data with even symmetry (since the Fourier transform of a real and even function is real and even), whereas in some variants the input or output data are shifted by half a sample.
From the perspective of algebraic signal processing, the relationship between the DCT and the DFT reflects their different underlying algebraic structures: the DFT basis functions are the irreducible representations of the cyclic group, making the DFT the natural spectral transform for signals with periodic (circular) boundary conditions, while the DCT basis functions are the irreducible representations of the dihedral group, making the DCT natural for signals with symmetric (even) boundary conditions.
There are eight standard DCT variants, of which four are common. The most common variant of discrete cosine transform is the type-II DCT, which is often called simply the DCT. This was the original DCT as first proposed by Ahmed. Its inverse, the type-III DCT, is correspondingly often called simply the inverse DCT or the IDCT. Two related transforms are the discrete sine transform (DST), which is equivalent to a DFT of real and odd functions, and the modified discrete cosine transform (MDCT), which is based on a DCT of overlapping data. Multidimensional DCTs (MD DCTs) are developed to extend the concept of DCT to multidimensional signals. A variety of fast algorithms have been developed to reduce the computational complexity of implementing DCT. One of these is the integer DCT (IntDCT), an integer approximation of the standard DCT, used in several ISO/IEC and ITU-T international standards.
DCT compression, also known as block compression, compresses data in sets of discrete DCT blocks. DCT block sizes include pixels for the standard DCT, and varied integer DCT sizes between and pixels. The DCT has a strong energy compaction property, capable of achieving high quality at high data compression ratios. However, blocky compression artifacts can appear when heavy DCT compression is applied.
History The DCT was first conceived by Nasir Ahmed while working at Kansas State University. The concept was proposed to the National Science Foundation in 1972. The DCT was originally intended for image compression. Ahmed developed a practical DCT algorithm with his PhD students T. Raj Natarajan and K. R. Rao at the University of Texas at Arlington in 1973. They presented their results in a January 1974 paper, titled Discrete Cosine Transform. It described what is now called the type-II DCT (DCT-II), as well as the type-III inverse DCT (IDCT).
Since its introduction in 1974, there has been significant research on the DCT. In 1977, Wen-Hsiung Chen published a paper with C. Harrison Smith and Stanley C. Fralick presenting a fast DCT algorithm. Further developments include a 1978 paper by M. J. Narasimha and A. M. Peterson, and a 1984 paper by B. G. Lee. These research papers, along with the original 1974 Ahmed paper and the 1977 Chen paper, were cited by the Joint Photographic Experts Group as the basis for JPEG's lossy image compression algorithm in 1992.
The discrete sine transform (DST) was derived from the DCT, by replacing the Neumann condition at x=0 with a Dirichlet condition. The DST was described in the 1974 DCT paper by Ahmed, Natarajan and Rao. A type-I DST (DST-I) was later described by Anil K. Jain in 1976, and a type-II DST (DST-II) was then described by H.B. Kekra and J.K. Solanka in 1978.
In 1975, John A. Roese and Guner S. Robinson adapted the DCT for inter-frame motion-compensated video coding. They experimented with the DCT and the fast Fourier transform (FFT), developing inter-frame hybrid coders for both, and found that the DCT is the most efficient due to its reduced complexity, capable of compressing image data down to 0.25 bit per pixel for a videotelephone scene with image quality comparable to an intra-frame coder requiring 2 bits per pixel. In 1979, Anil K. Jain and Jaswant R. Jain further developed motion-compensated DCT video compression, also called block motion compensation. This led to Chen developing a practical video compression algorithm, called motion-compensated DCT or adaptive scene coding, in 1981. Motion-compensated DCT later became the standard coding technique for video compression from the late 1980s onwards.
A DCT variant, the modified discrete cosine transform (MDCT), was developed by John P. Princen, A.W. Johnson and Alan B. Bradley at the University of Surrey in 1987, following earlier work by Princen and Bradley in 1986. The MDCT is used in most modern audio compression formats, such as Dolby Digital (AC-3), MP3 (which uses a hybrid DCT-FFT algorithm), Advanced Audio Coding (AAC), and Vorbis (Ogg).
Nasir Ahmed also developed a lossless DCT algorithm with Giridhar Mandyam and Neeraj Magotra at the University of New Mexico in 1995. This allows the DCT technique to be used for lossless compression of images. It is a modification of the original DCT algorithm and incorporates elements of inverse DCT and delta modulation. It is a more effective lossless compression algorithm than entropy coding. Lossless DCT is also known as LDCT.
Applications The DCT is the most widely used transformation technique in signal processing, and by far the most widely used linear transform in data compression. Uncompressed digital media as well as lossless compression have high memory and bandwidth requirements, which is significantly reduced by the DCT lossy compression technique, capable of achieving data compression ratios from 8:1 to 14:1 for near-studio-quality, up to 100:1 for acceptable-quality content. DCT compression standards are used in digital media technologies, such as digital images, digital photos, digital video, streaming media, digital television, streaming television, video on demand (VOD), digital cinema, high-definition video (HD video), and high-definition television (HDTV).
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. 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 widely employed in solving partial differential equations by spectral methods, where the different variants of the DCT correspond to slightly different even and odd boundary conditions at the two ends of the array.
DCTs are 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.
General applications The DCT is widely used in many applications, which include the following.
Visual media standards The DCT-II is an important image compression technique. It is used in image compression standards such as JPEG, and video compression standards such as , MJPEG, MPEG, DV, Theora and Daala. There, the two-dimensional DCT-II of blocks is computed and the results are quantized and entropy coded. In this case, is typically 8 and the DCT-II formula is applied to each row and column of the block. The result is an 8 × 8 transform coefficient array in which the element (top-left) is the DC (zero-frequency) component and entries with increasing vertical and horizontal index values represent higher vertical and horizontal spatial frequencies.
The integer DCT, an integer approximation of the DCT, is used in Advanced Video Coding (AVC), introduced in 2003, and High Efficiency Video Coding (HEVC), introduced in 2013. The integer DCT is also used in the High Efficiency Image Format (HEIF), which uses a subset of the HEVC video coding format for coding still images. AVC uses 4 x 4 and 8 x 8 blocks. HEVC and HEIF use varied block sizes between 4 x 4 and 32 x 32 pixels. , AVC is by far the most commonly used format for the recording, compression and distribution of video content, used by 91% of video developers, followed by HEVC, which is used by 43% of developers.
Image formats Image compression standard Year Common applications JPEG 1992 The most widely used image compression standard and digital image format. JPEG XR 2009 Open XML Paper Specification WebP 2010 A graphic format that supports the lossy compression of digital images. Developed by Google. High Efficiency Image Format (HEIF) 2013 Image file format based on HEVC compression. It improves compression over JPEG, and supports animation with much more efficient compression than the animated GIF format. BPG 2014Based on HEVC compression JPEG XL 2020 A royalty-free raster-graphics file format that supports both lossy and lossless compression.
Video formats Video coding standard Year Common applications 1988 First of a family of video coding standards. Used primarily in older video conferencing and video telephone products. Motion JPEG (MJPEG) 1992 QuickTime, video editing, non-linear editing, digital cameras MPEG-1 Video 1993 Digital video distribution on CD or Internet video MPEG-2 Video () 1995 Storage and handling of digital images in broadcast applications, digital television, HDTV, cable, satellite, high-speed Internet, DVD video distribution DV 1995 Camcorders, digital cassettes H.263 (MPEG-4 Part 2) 1996 Video telephony over public switched telephone network (PSTN), , Integrated Services Digital Network (ISDN) Advanced Video Coding (AVC, , MPEG-4) 2003 Popular HD video recording, compression and distribution format, Internet video, YouTube, Blu-ray Discs, HDTV broadcasts, web browsers, streaming television, mobile devices, consumer devices, Netflix, video telephony, FaceTime Theora 2004 Internet video, web browsers VC-1 2006 Windows media, Blu-ray Discs Apple ProRes 2007 Professional video production. VP92010 A video codec developed by Google used in the WebM container format with HTML5. High Efficiency Video Coding (HEVC, ) 2013 Successor to the standard, having substantially improved compression capability Daala 2013 Research video format by Xiph.org AV1 2018 An open source format based on VP10 (VP9's internal successor), Daala and Thor; used by content providers such as YouTube and Netflix.
MDCT audio standards
General audio