Working with the DCT
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