3 ms·

You mean DCT? Please see my other comment under this post: H.264 has no "real magic", the magic comes from multiple small-gain tricks combined together.

by jwr 7y ago

jacobolus 7y ago
DCT is basically a type of DFT (for functions with symmetries in the values). You can easily implement a fast DCT using the FFT at the expense of a constant performance penalty (because the more general code can’t skip doing the redundant work implied by the symmetries in the data). The techniques used to implement a fast DCT are pretty well the same ones used for an FFT. The basic concept of the DCT as used in compression applications is that the FFT only works for periodic data, but the arbitrary data in a block of pixels are not periodic, so we pretend that it is part of a periodic function with double the period where we mirror the data back-to-front on the other half. If we didn’t have a DCT implementation per se we could explicitly mirror the data into a larger array and then run an FFT, and then just look at half of the coefficients (the others are zero). This still creates some artifacts since the interval of our data is not actually periodic, and derivatives aren’t necessarily matching between the two ends. But it turns out to be more-or-less good enough. An alternative approach to approximating a function sampled on a uniform grid over a non-periodic interval using the FFT is to first estimate the first few derivatives at the endpoints and then subtract off a polynomial matching that data. Then we can more safely pretend that the remainder is periodic. cf. http://zindajaved.com/data/publications/javedTrefethen2014b.pdf http://zindajaved.com/data/publications/javedTrefethen2014b....
- jolmg 7y ago
  For those wondering what all the acronyms are: FFT: https://en.wikipedia.org/wiki/Fast_Fourier_transform https://en.wikipedia.org/wiki/Fast_Fourier_transform DCT: https://en.wikipedia.org/wiki/Discrete_cosine_transform https://en.wikipedia.org/wiki/Discrete_cosine_transform DFT: https://en.wikipedia.org/wiki/Discrete_Fourier_transform https://en.wikipedia.org/wiki/Discrete_Fourier_transform

You mean DCT? Please see my other comment under this post: H.264 has no "real magic", the magic comes from multiple small-gain tricks combined together.

by jwr 7y ago

You mean DCT? Please see my other comment under this post: H.264 has no "real magic", the magic comes from multiple small-gain tricks combined together.

jacobolus 7y ago

DCT is basically a type of DFT (for functions with symmetries in the values). You can easily implement a fast DCT using the FFT at the expense of a constant performance penalty (because the more general code can’t skip doing the redundant work implied by the symmetries in the data). The techniques used to implement a fast DCT are pretty well the same ones used for an FFT. The basic concept of the DCT as used in compression applications is that the FFT only works for periodic data, but the arbitrary data in a block of pixels are not periodic, so we pretend that it is part of a periodic function with double the period where we mirror the data back-to-front on the other half. If we didn’t have a DCT implementation per se we could explicitly mirror the data into a larger array and then run an FFT, and then just look at half of the coefficients (the others are zero). This still creates some artifacts since the interval of our data is not actually periodic, and derivatives aren’t necessarily matching between the two ends. But it turns out to be more-or-less good enough. An alternative approach to approximating a function sampled on a uniform grid over a non-periodic interval using the FFT is to first estimate the first few derivatives at the endpoints and then subtract off a polynomial matching that data. Then we can more safely pretend that the remainder is periodic. cf. http://zindajaved.com/data/publications/javedTrefethen2014b.pdf http://zindajaved.com/data/publications/javedTrefethen2014b....

jolmg 7y ago
For those wondering what all the acronyms are: FFT: https://en.wikipedia.org/wiki/Fast_Fourier_transform https://en.wikipedia.org/wiki/Fast_Fourier_transform DCT: https://en.wikipedia.org/wiki/Discrete_cosine_transform https://en.wikipedia.org/wiki/Discrete_cosine_transform DFT: https://en.wikipedia.org/wiki/Discrete_Fourier_transform https://en.wikipedia.org/wiki/Discrete_Fourier_transform