Content deleted Content added
No edit summary |
m →External links: HTTP to HTTPS for SourceForge |
||
| (6 intermediate revisions by 3 users not shown) | |||
Line 286:
\qquad \text{ for } ~ k = 0,\ \ldots\ N-1 ~.</math>
Some authors further multiply the <math>x_0 </math> and <math> x_{N-1} </math> terms by <math> \sqrt{2\,}\
The DCT-I is exactly equivalent (up to an overall scale factor of 2), to a DFT of <math> 2(N-1) </math> real numbers with even symmetry. For example, a DCT-I of <math>N = 5 </math> real numbers <math> a\ b\ c\ d\ e </math> is exactly equivalent to a DFT of eight real numbers {{not a typo|<math> a\ b\ c\ d\ e\ d\ c\ b </math>}} (even symmetry), divided by two. (In contrast, DCT types II-IV involve a half-sample shift in the equivalent DFT.)
Note, however, that the DCT-I is not defined for <math>
Thus, the DCT-I corresponds to the boundary conditions: <math>
=== DCT-II ===
Line 301:
The DCT-II is probably the most commonly used form, and is often simply referred to as the ''DCT''.<ref name="pubDCT"/><ref name="pubRaoYip"/>
This transform is exactly equivalent (up to an overall scale factor of 2) to a DFT of <math>4N</math> real inputs of even symmetry, where the even-indexed elements are zero. That is, it is half of the DFT of the <math>4N</math> inputs <math> y_n ,</math> where <math> y_{2n} = 0
Some authors further multiply the <math>
The DCT-II implies the boundary conditions: <math>
=== DCT-III ===
Line 313:
\qquad \text{ for } ~ k = 0,\ \ldots\ N-1 ~.</math>
Because it is the inverse of DCT-II up to a scale factor (see below), this form is sometimes simply referred to as
Some authors divide the <math>x_0</math> term by <math>\sqrt{2}</math> instead of by 2 (resulting in an overall <math>x_0/\sqrt{2}</math> term) and multiply the resulting matrix by an overall scale factor of <math display="inline"> \sqrt{2/N}</math> (see above for the corresponding change in DCT-II), so that the DCT-II and DCT-III are transposes of one another. This makes the DCT-III matrix [[orthogonal matrix|orthogonal]], but breaks the direct correspondence with a real-even DFT of half-shifted output.
Line 328:
A variant of the DCT-IV, where data from different transforms are ''overlapped'', is called the [[modified discrete cosine transform]] (MDCT).<ref>{{harvnb|Malvar|1992}}</ref>
The DCT-IV implies the boundary conditions: <math>
=== DCT V-VIII ===
Line 506:
Specialized DCT algorithms, on the other hand, see widespread use for transforms of small, fixed sizes such as the {{nobr| 8 × 8 }} DCT-II used in [[JPEG]] compression, or the small DCTs (or MDCTs) typically used in audio compression. (Reduced code size may also be a reason to use a specialized DCT for embedded-device applications.)
In fact, even the DCT algorithms using an ordinary FFT are sometimes equivalent to pruning the redundant operations from a larger FFT of real-symmetric data, and they can even be optimal from the perspective of arithmetic counts. For example, a type-II DCT is equivalent to a DFT of size <math>~ 4N ~</math> with real-even symmetry whose even-indexed elements are zero. One of the most common methods for computing this via an FFT (e.g. the method used in [[FFTPACK]] and [[Fastest Fourier Transform in the West|FFTW]]) was described by {{harvtxt|Narasimha|Peterson|1978}} and {{harvtxt|Makhoul|1980}}, and this method in hindsight can be seen as one step of a radix-4 decimation-in-time Cooley–Tukey algorithm applied to the "logical" real-even DFT corresponding to the DCT-II.{{efn|
The radix-4 step reduces the size <math>~ 4N ~</math> DFT to four size <math>~ N ~</math> DFTs of real data, two of which are zero, and two of which are equal to one another by the even symmetry. Hence giving a single size <math>~ N ~</math> FFT of real data plus <math>~ \mathcal{O}(N) ~</math> [[butterfly (FFT algorithm)|butterflies]], once the trivial and / or duplicate parts are eliminated and / or merged.
}}
Line 517:
==Example of IDCT==
[[File:DCT filter comparison.png|thumb|right|An example showing eight different filters applied to a test image (top left) by multiplying its DCT spectrum (top right) with each filter.]]
Consider this {{resx|8x8}} [[grayscale image]] of capital letter A.
[[File:letter-a-8x8.png|frame|center|Original size, scaled 10x (nearest neighbor), scaled 10x (bilinear).]]
Line 633:
* Takuya Ooura: General Purpose FFT Package, [http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html FFT Package 1-dim / 2-dim]. Free C & FORTRAN libraries for computing fast DCTs (types II–III) in one, two or three dimensions, power of 2 sizes.
* Tim Kientzle: Fast algorithms for computing the 8-point DCT and IDCT, [http://drdobbs.com/parallel/184410889 Algorithm Alley].
* [
{{Compression Methods|state=expanded}}
Line 646:
[[Category:Data compression]]
[[Category:Image compression]]
[[Category:H.26x]]
[[Category:JPEG]]
| |||