Implementación rápida de DCT

Tengo problemas para descubrir cómo seguir los rápidos diagramas del algoritmo DCT 8x8 que se encuentran en los siguientes dos documentos:

(1) Un algoritmo computacional rápido para la transformación discreta del coseno por Chen et al.

y

(2) Algoritmos prácticos rápidos de DCT 1-D con 11 multiplicaciones de Loeffler et al.

En particular, el segundo diagrama que muestra el algoritmo en (2) tiene el siguiente aspecto:

La descripción de las operaciones en este algoritmo son:

Hay algunas preguntas que tengo sobre esta formulación, y no estoy seguro de dónde encontrar las respuestas:

1. (2) sugiere que este algoritmo genera un DCT que se escala en algún valor . Menciona que este fue elegido arbitrariamente para evitar cualquier multiplicación en el cálculo del coeficiente DC. Realmente el único requisito es que . Entonces mi pregunta es esta: ¿Cuál es el factor de escala de los coeficientes de salida usando este algoritmo? Parece que son diferentes a la definición original de DCT, pero no sé cuánto (principalmente porque realmente no veo ninguna relación entre este diagrama y la formulación original de DCT): donde$C = \sqrt{2}$$C$$C_{DCT} * C_{IDCT} = \frac{4}{N^2}$

   $$F(k) = \frac{2c(k)}{N}\sum_{n = 0}^{N - 1}f(n)\cos\left(\frac{\left(2n + 1\right)\pi k}{2N}\right)$$ $c(k) = \frac{1}{\sqrt{2}}$para y para .$k = 0$$c(k) = 1$$k \neq 0$

2. El documento establece que la realización del IDCT se puede hacer usando exactamente el mismo algoritmo pero transformando las salidas en entradas y viceversa. Primero, ¿deben ordenarse los coeficientes DCT en orden de inversión de bits antes de ejecutarlos a través del IDCT? Segundo, para los bloques de rotación (los cuadrados en el diagrama), la operación inversa no debería ser: Mi razonamiento es este: la inversa de una rotación por es una rotación por . Por lo tanto, simplemente reemplazamos el ángulo por su inverso y usamos las identidades y

   $$\begin{align} O_0 = I_0 \cdot k \cdot \cos\frac{n\pi}{2N} - I_1 \cdot k \cdot \sin\frac{n\pi}{2N} \\ O_1 = I_1 \cdot k \cdot \sin\frac{n\pi}{2N} + I_1 \cdot k \cdot \cos\frac{n\pi}{2N} \\ \end{align}$$ $\theta$$-\theta$$\cos(-\theta) = \cos(\theta)$$\sin(-\theta) = -\sin(\theta)$ . Tercero, ¿cuál es el factor de escala de los valores transformados después del IDCT? (2) dice , pero empíricamente, esto no ha producido resultados correctos.$\frac{2}{N^2}$

3. Supongamos que después de ejecutar el algoritmo, tengo el resultado de cada carril almacenado en los valores d0 ... d7. Cual de los siguientes es correcto:

   salida [0] = d0 o salida [0] = d0
   salida [4] = d1 salida [1] = d4
   salida [2] = d2 salida [2] = d2
   salida [6] = d3 salida [3] = d6
   salida [7] = d4 salida [4] = d7
   salida [3] = d5 salida [5] = d3
   salida [5] = d6 salida [6] = d5
   salida [1] = d7 salida [7] = d1 

Si hay alguna forma de mejorar esta pregunta, o si debo preguntar en otro lado, hágamelo saber.

Muy bien, después de algunos días de mirar este problema, espero poder brindar un poco de orientación a la próxima pobre alma.

1. Sí, la escala es diferente. En comparación con scipy.fftpack.dctel término DC es y los otros términos . Pero aparentemente todo se cancela muy bien en la transformación inversa.$\frac{1}{2}$$\frac{\sqrt{2}}{2}$
2. El orden de entrada inverso es exactamente como sale: bit invertido. Literalmente como si voltea la figura y conecta las líneas. Y sí, tienes razón en que el pecado tiene un signo menos. Estoy viendo un factor de escala de 8, FWIW.
3. El orden de salida de la inversa es el mismo que el orden de entrada de la transformación directa. Entonces$x[n]=\frac{\mathrm{IDCT}(\mathrm{DCT}(x[n]))}{8}$

También tenga en cuenta que hay un error en el gráfico y es para el bloque de rotación del lado par.$\sqrt{2}c6$