Working with the DCT I am having a very hard time to implement the DCT algorithm. I have quite a few requirements like it has to work with NxN matrix or at least power of 2, it has to be 2D, it has to produce same output as FFTW fftwf_plan_r2r_2d(FFTW_REDFT10) it has to use real data and I need DCT I, II and III. And it has to be fast!

1) I could use FFT to compute DCT and wikipedia mentions this:

"One can also compute DCTs via FFTs combined with O(N) pre- and post-processing steps. In general, O(N log N) methods to compute DCTs are known as fast cosine transform (FCT) algorithms."

What are those 2 steps?

2) If I use Apples vDSP library is that even a good idea? since it needs an array twice as big as the DCT array (2N with radix2). And also vDSP is 1D only so I would end up doing it for each row and column to get a 2D result.

3) Is it possible to use an algorithm that works on 8x8 blocks and adapt it for my needs?

I am very new to learning about DSP so any help is appreciated! Thanks!

ps: Does anyone have any sample code for what I need? would help me a lot
While this is not much of an answer, here's a few comments while you wait for an expert to reply.

If this is one of your first DSP projects, it might be a bit ambitious just to dive straight into the fast implementations - you might want to start out with a naive implementation and then work your way up to the faster algorithms.

For the FFT-based approaches, you could check out how scipy does it:
http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.fftpack.dct.html

There's a lot of papers on the subject, but they might be a bit tricky to chew through. A couple of examples through some brief searches:


http://www.cin.ufpe.br/~vak/tg/papers/Chen-dct.pdf (1977 paper on a fast DCT)
http://arxiv.org/pdf/1203.3442.pdf (fast DCT-II)


It would probably be easier to understand from a book - I recall reading about the DCT and some fast algorithms with pretty elaborate explanations in "JPEG Still image data compression standard" by W. B. Pennebaker and J. L. Mitchell (I'm sure you can find loads of books on the DCT, specifically, though).

Also, this seems to be how they do it over at FFmpeg: http://www.ffmpeg.org/doxygen/2.1/dct_8c_source.html