# Fast DCT from DFT

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.

• 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
Commented Jan 17, 2023 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. Commented Jan 18, 2023 at 7: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
Commented Jan 18, 2023 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 Commented Jan 19, 2023 at 11:02