Buscando un pseudocódigo de transformada de coseno discreta (DCT)/IDCT 8x8 (o nxn) [cerrado]

Question

He estado buscando en Google por un tiempo para encontrar un pseudocódigo de un algoritmo DCT 8x8 (o nxn) decentemente eficiente, ¡y no puedo encontrar nada!

Implementé el enfoque ingenuo y me llevó demasiado tiempo ejecutarlo.

Si pudiera publicar algún pseudocódigo o hacer referencia a un buen libro/documento/sitio web, sería útil.

¡Los ejemplos de C o C++ serían aún mejores!

Answer 1

Como se solicita en los comentarios, fuente (tenga cuidado, está en C#, pero la diferencia con C++ debería ser mínima, y ​​sí, sé que el código es poco convincente):

Bucle principal (A = resultado, B = entrada):

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];
    }
}

Cosas de soporte:

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);
     }
}

editar:Lo cronometré: para 512 por 512 píxeles (un solo canal), se necesita medio segundo.Claro que es lento, pero ni mucho menos "para siempre".

Answer 2

Fftw tiene una implementación eficiente de código abierto