FFT is the real magic there and has been since the 90s.
Convince me otherwise.
Convince me otherwise.
The compression is gained by perceptual modeling and dumping parts, and by powerful entropy modeling, like CABAC and such.
Also more advanced things are usually used in modern compression: DCTs, sliding window stuff, wavelets, CABAC stuff, motion prediction schemes, etc., none of which were used in the 90s (except DCT and rudimentary prediction).
For fixed input and output (say 8 bit to 8 bit data), it's easy to make lossless FFTs, since the final truncation or rounding can be designed to never lose information. So in these cases, even a FFT based on , say, IEEE 754 doubles can be made lossless when using integral input and output.
A similar example is converting 8 bit RGB to 0-1 floating point by dividing the color channel by 255.0, which is lossy as real numbers since the resulting floating point is truncated (except precisely for inputs 0 and 255). However, multiplying the result by 255.0, and rounding appropriately, you can recover each input without loss. So this is an example of a lossless transformation that has lossy steps in between. This can be done in almost any case you need to do it.
FFTs in compression are not used to lose values, but to change signal domain, where perhaps interesting and lossy things can be done.
Google lossless FFT or reversible FFT and dig around.
At the end of the day, however, it's not FFTs that are useful very much in compression. They're only used for signal changes at best, and they've been made obsolete for the most pary by other techniques.
> The FFT using real numbers is not lossless
The DFT over the reals is invertible, right? How can it be invertible but not lossless?
FFTs use terms of the form e^(2 pi i k / n), and these terms cannot be represented exactly except in rare cases with finite precision floating point numbers (follows from Gelfand's Theorem).
Thus, as soon as you try to use or compute such a term, you've made an approximation, losing information.
The transform is approximately invertible using finite precision, and if your inputs are some fixed set you can make sure and do error analysis to ensure those terms come back out via careful rounding.
But the FFT, and it's inverse, involve infinitely precise real numbers that cannot be represented as floating point.
The DFT fails for the same reason.
However
As I explained above, if you have a limited set of inputs, say byte values 0-255, that get converted to floating point via these approximations, then the inverse approximation is applied, then the final values are appropriately rounded, you can make the DFT and FFT (and almost any approximation algorithm) on this limited subset of inputs 0-255.
As a simple example, consider turning a byte color channel 0-255 into a 32 bit float in 0.0f - 1.0f via dividing by 255.0. Now every one of the values except 0.0f and 1.0f are approximations, since the only exactly representable floats are dyadic (denominator is power of 2) and these denominators are 255 (no powers of 2).
So this is lossy. But the limited inputs means there are 255 different floats possible.
Now multiplying by 255.0, which is (int this case) not lossy on floats, puts each back to close to an integer (but not all are integers). Rounding to closest will restore the original 0255 byte values.
So the roundtrip is lossless here. But the same transforms dividing by 255.0f then multiplying by 255.0f are not lossless for all floating point inputs.
In each case for any algorithm, one needs to carefully design the inputs and outputs and transforms carefully to ensure it behaves as desired.
This is the tip of the iceberg when dealing with floating point algorithms :)
The DFT over the reals is not lossless. Using floats, for example, and applying it to max_float overflows, so cannot be inverted. It's not even bit invertible for almost any set of inputs. It's only invertible on very limited specialized sets of inputs
Like this:
> The DFT over the reals is not lossless. Using floats, for example, and applying it to max_float overflows, so cannot be inverted.
I don't see why you make statements about the reals based on what happens with floats. They aren't the same, and the DFT exists independently of actually computing it.
Please see my other comment under this post: H.264 has no "real magic", the magic comes from multiple small-gain tricks combined together.
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....
FFT: https://en.wikipedia.org/wiki/Fast_Fourier_transform
DCT: https://en.wikipedia.org/wiki/Discrete_cosine_transform
DFT: https://en.wikipedia.org/wiki/Discrete_Fourier_transform
In direct response to the OP, I would suggest that motion estimation and entropy coding are up there on equal footing with FFT.