5

I've been searching Google for a while now to find pseudo-code of a decently efficient 8x8 (or nxn) DCT algorithm, and I can't find anything!

I implemented the naive approach, and it took far too long to execute.

If you could post some pseudo-code or reference a good book/document/website, that would be helpful.

C or C++ examples would be better yet!

Daniel
  • 141
  • 1
  • 10
user904963
  • 1,520
  • 2
  • 15
  • 33
  • That's odd, a quite naive approach runs quite fast here, how long is "too long"? – harold Dec 02 '11 at 23:02
  • I was processing a 512x512 image with 3 channels, and it was taking minutes before I turned it off. Perhaps I implemented it incorrectly or got stuck in an infinite loop somehow. Let me try again. – user904963 Dec 02 '11 at 23:04
  • I had precomputed the cosine tables of course, but other than that it was just the naive approach of doing it exactly like the definition suggests. But even with those cosines it shouldn't take long. – harold Dec 02 '11 at 23:09
  • Are you using separability? @harold – user904963 Dec 02 '11 at 23:16
  • I don't know, to be honest I'm not an expert on DCT's - I'm using two nested loops both going from 0 to 8, instead of doing it first in one dimension and then in the other, is that what that means? – harold Dec 02 '11 at 23:22
  • Yes. Could you post your source code? I am trying to do some steganography, and I need a simple dct and idct to hide information in that space. @harold – user904963 Dec 02 '11 at 23:28

2 Answers2

5

As requested in the comments, source (be slightly warned, it's in C#, but the difference with C++ should be minimal, and yes I know the code is lame):

Main loop (A = result, B = input):

for (int y = 0; y < 8; y++)
{
    for (int x = 0; x < 8; x++)
    {
        A[y * 8 + x] = 0;
        for (int u = 0; u < 8; u++)
            for (int v = 0; v < 8; v++)
                A[y * 8 + x] += alpha(u) * alpha(v) * B[u, v] *
                    cosine[u, x] * cosine[v, y];
    }
}

Support stuff:

static double alpha(int i)
{
    if (i == 0)
        return SQRT2o2 * 0.5;
    return 0.5;
}
const double SQRT2o2 = 1.414213562373095048801688724209 * 0.5;
cosine = new double[8, 8];
const double inv16 = 1.0 / 16.0;
for (int i = 0; i < 8; i++)
{
     for (int j = 0; j < 8; j++)
     {
         cosine[j, i] = Math.Cos(Math.PI * j * (2.0 * i + 1) * inv16);
     }
}

edit: I timed it - for 512 by 512 pixels (single channel) it takes half a second. Sure that's slow, but nowhere near "forever".

harold
  • 61,398
  • 6
  • 86
  • 164
1

FFTW has an open source efficient implementation

TJD
  • 11,800
  • 1
  • 26
  • 34