0

I successfully computed 2d dct of an image using the classic algorithm and also using as a combination of 1d arrays. Those 2 methods have a time complexity of n^4 and n^3 respectively. While implementing on an image it takes a very long time to compute. like 7 minutes for a 512 x 512 image using the one with n^3 complexity.

Is there any other algorithms to compute DCT having a minimal time complexity?

How does matlab do it so quickly though?

Spektre
  • 49,595
  • 11
  • 110
  • 380
Kush Raj Rimal
  • 1
  • 1
  • 3
    Matlab computes the DCT via the DFT, using the `fft` function. This function uses very effficient algorithms (usually O(_n_ log(_n_)). The algorithm selected depends on the input size. Internally, `fft` calls [`fftw`](https://es.mathworks.com/help/matlab/ref/fftw.html), which defines [those algorithms](https://es.mathworks.com/help/matlab/ref/fftw.html#inputarg_method), and is based on the [FFTW library](http://www.fftw.org/) – Luis Mendo Aug 07 '17 at 10:54

1 Answers1

3

there are 2 common approaches for fast DCT.

  1. DCT from DFT

    1D DCT can be derived from 1D DFT in O(n) so when FFT algorithm is applied you got O(n.log(n)) for 1D and O(n^2.log(n)) for 2D. For more info see:

    This approach is more used as it is a bit more easy to implement. There are more ways on how to derive DCT from DFT some use the same array size and the other uses double size for DFT.

  2. Fast DCT

    There are also fast DCT equations out there but they are not commonly used because they are not very well known and not well documented online. Another more inmportant point is that the recursive breakdown involves both DCT and DST and the split is done usually into 3 therms instead of 2 which makes the implementation much harder. And also we need fast DST implementation which is analogy to DCT so it also breaks down to 3 therms and is using both DCT and DST. The bright side is that it does not involve complex domain but as you can imagine there is much more code needed in comparison to #1.

    From a quick search I found this

    But to find relevant info about fast DCT in real domain is a problem because most articles are either hard wired (constant n) implementations or are using approach #1. And when you find something it usually does contains errors and does not work. Your best bet for this approach is to find some old paper or book on computer graphics or discrete math.

Spektre
  • 49,595
  • 11
  • 110
  • 380