2

I need to compute the DCT of a signal (in fact its a image). As I already have the DFT of that signal, I wonder if there is any cheap way to obtain the DCT in terms of the DFT.

Note that I am not asking if the DCT can be computed via the FFT, which has been answered here. The answers in the cited question perform modifications in the time domain. I have the additional constrain of "The FFT has been already computed with the input signal".

Obviously the task is possible in O(N²) time, because both transforms are orthonormal bases, so a possible way could be computing the transform matrix from one base to the other. This could be improved with dct(ifft(x)), where both operations have O(n log(n)) complexity.

Therefore, the question is if there is any linear time complexity algorithm that obtains the DCT of a signal from the Discrete Fourier Transform of that signal.

Oier Lauzirika Zarrabeitia
  • 21
  • 1
  • Is the DFT of "equal size" to the given signals / images? (e.g, given an 64x64 image, is the available DFT of size 64x64 too? ) – A_A Jan 17 '23 at 11:47
  • No, I do not store the symmetric part of the DFT. Therefore, the DFT has size 64x33. In any case, calculating the missing half is trivial. – Oier Lauzirika Zarrabeitia Jan 18 '23 at 07:59
  • If you are not storing the symmetric part, then that should have been a 32x32 matrix. Can you please talk a little bit more about the application you are dealing with? – A_A Jan 18 '23 at 10:11
  • The application would be fast image comparisons (comparing just the lower frequencies). I was getting better results using the DCT, but its computation its being a bottleneck. No, the FFT would have 64x33, it is symmetrical on a diagonal, so if it were 32x32 you'd throw away half of the information – Oier Lauzirika Zarrabeitia Jan 19 '23 at 11:02

0 Answers0