5 ms·

FFT is the real magic there and has been since the 90s. Convince me otherwise.

by Iv 7y ago

boapnuaput 7y ago
Very well. I would like to correct two misconceptions that you carry. Not only is the Fast Fourier Transform not magical, but it comes out of a straightforward elaboration of the question of how multiplication of two numbers might be done quickly. The technique was discovered before the (19)90s, too; Gauss discovered it over two centuries ago.
- sjwright 7y ago
  I think you are intentionally misunderstanding the OP's point. He is talking about FFT as applied to lossy video compression. In direct response to the OP, I would suggest that motion estimation and entropy coding are up there on equal footing with FFT.
ChrisLomont 7y ago
The FFT is lossless, so there’s no compression as a result of using it. 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).
- acchow 7y ago
  "FFT is lossless" - is this true without infinite precision values?
  - hoseja 7y ago
    https://en.wikipedia.org/wiki/Nyquist_rate https://en.wikipedia.org/wiki/Nyquist_rate
    - tntn 7y ago
      I don't see how this is relevant. Certainly related, but not immediately relevant. The Nyquist rate / frequency (depending on where you stand) determines whether the process of sampling is invertible, but the FFT exists independent of the process of sampling and is always invertible (in the maths). 'acchow's question is whether this holds in practical systems, like computing the FFT and IFFT with the finite precision + finite range numbers that we can use.
  - gsich 7y ago
    Yes.
  - ChrisLomont 7y ago
    The FFT using real numbers is not lossless (except in certain numerically coincidental cases that are not mush practical use), but there are lossless approximations used routinely in compression to avoid error at this point. 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.
    - tntn 7y ago
      Can you give some details re: > The FFT using real numbers is not lossless The DFT over the reals is invertible, right? How can it be invertible but not lossless?
      - ChrisLomont 7y ago
        > The FFT using real numbers is 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
  - sp332 7y ago
    No, but it's close enough to be round-trippable which is all most applications need. That is, if you do an FFT with enough precision to use the same number of bits as the original representation, you will get values that are close enough to the correct values that if you do it again, you will get the same numbers back, to the limits of whatever precision you were using.
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

FFT is the real magic there and has been since the 90s. Convince me otherwise.

by Iv 7y ago

FFT is the real magic there and has been since the 90s. Convince me otherwise.

Very well. I would like to correct two misconceptions that you carry. Not only is the Fast Fourier Transform not magical, but it comes out of a straightforward elaboration of the question of how multiplication of two numbers might be done quickly. The technique was discovered before the (19)90s, too; Gauss discovered it over two centuries ago.

sjwright 7y ago
I think you are intentionally misunderstanding the OP's point. He is talking about FFT as applied to lossy video compression. In direct response to the OP, I would suggest that motion estimation and entropy coding are up there on equal footing with FFT.

ChrisLomont 7y ago

The FFT is lossless, so there’s no compression as a result of using it. 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).

acchow 7y ago
"FFT is lossless" - is this true without infinite precision values?
- hoseja 7y ago
  https://en.wikipedia.org/wiki/Nyquist_rate https://en.wikipedia.org/wiki/Nyquist_rate
  - tntn 7y ago
    I don't see how this is relevant. Certainly related, but not immediately relevant. The Nyquist rate / frequency (depending on where you stand) determines whether the process of sampling is invertible, but the FFT exists independent of the process of sampling and is always invertible (in the maths). 'acchow's question is whether this holds in practical systems, like computing the FFT and IFFT with the finite precision + finite range numbers that we can use.
- gsich 7y ago
  Yes.
- ChrisLomont 7y ago
  The FFT using real numbers is not lossless (except in certain numerically coincidental cases that are not mush practical use), but there are lossless approximations used routinely in compression to avoid error at this point. 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.
  - tntn 7y ago
    Can you give some details re: > The FFT using real numbers is not lossless The DFT over the reals is invertible, right? How can it be invertible but not lossless?
    - ChrisLomont 7y ago
      > The FFT using real numbers is 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
- sp332 7y ago
  No, but it's close enough to be round-trippable which is all most applications need. That is, if you do an FFT with enough precision to use the same number of bits as the original representation, you will get values that are close enough to the correct values that if you do it again, you will get the same numbers back, to the limits of whatever precision you were using.

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