Transformada de coseno discreta

La transformada de coseno discreta o TCD (del inglés : DCT o Transformada de coseno discreta ) es una transformación cercana a la transformada discreta de Fourier (DFT). El núcleo de proyección es un coseno y por lo tanto crea coeficientes reales, a diferencia de la DFT, cuyo núcleo es un exponencial complejo y por lo tanto crea coeficientes complejos. Sin embargo, la DCT se puede expresar en función de la DFT, que luego se aplica a la señal balanceada.

La variante más común de la transformada de coseno discreta es la DCT tipo II , a menudo denominada simplemente "la DCT". Su inverso, que corresponde al tipo III, a menudo se denomina simplemente "IDCT".

Aplicaciones

DCT, y en particular DCT- II, se usa ampliamente en el procesamiento de señales e imágenes, y especialmente en la compresión. De hecho, el DCT tiene una propiedad excelente de "reagrupar" de energía: la información es transportada esencialmente por los coeficientes de baja frecuencia. Para imágenes naturales, la DCT es la transformación que más se asemeja a la transformada de Karhunen-Loève que proporciona una descorrelación óptima de los coeficientes para una señal de Markov . En la práctica, los métodos de compresión asumen, por tanto, que una imagen natural puede modelarse como la realización de un proceso de Markov y aproximarse a la transformada de Karhunen-Loève , demasiado compleja en el cálculo y dependiente de los datos, mediante un DCT. El interés de una transformación se ve particularmente bien en una figura (ver al lado). Solo una pequeña cantidad de coeficientes son distintos de cero y se pueden usar para reconstruir la imagen de transformada inversa (IDCT) durante la descompresión. La ganancia en términos de compresión proviene de la eliminación de coeficientes cero o cercanos a cero. Este tipo de mecanismo se utiliza en los estándares JPEG y MPEG , que utilizan un DCT 2D en bloques de píxeles de tamaño 8 × 8 (por razones de complejidad).

Los formatos de sonido de compresión con pérdida AAC , Vorbis y MP3 utilizan una versión modificada de esta técnica, la transformada de coseno discreta modificada (in) , MDCT (MDCT English).

DCT también se utiliza para resolver sistemas de ecuaciones diferenciales mediante métodos espectrales.

Definición

La DCT es una función lineal invertible R N → R N o equivalentemente una matriz cuadrada N × N invertible . Hay varias variaciones leves de DCT. Aquí están los cuatro tipos más famosos.

El desarrollo de algoritmos para el cálculo rápido de transformadas DCT se basa en la posibilidad de descomponer la matriz de definición en forma de un producto de matrices cuyo cálculo es más sencillo, y permite reducir el número de multiplicaciones escalares, aprovechando identidades notable periodicidad y simetrías de funciones sinusoidales. Por tanto, se puede descomponer cualquier transformación DCT de R N en transformaciones más simples descomponiendo N en un producto de factores primos y componiendo subtransformaciones en R n donde n es uno de estos factores. En particular, se han desarrollado muchas optimizaciones cuando N es una potencia de 2.

Esto equivale a reescribir la matriz N × N en la forma del producto de submatrices idénticas (dispuestas en mosaicos regulares y, por lo tanto, utilizando coeficientes reales comunes o diferenciados solo por su signo) y matrices con coeficientes unitarios o cero (-1, 0 o 1), esta última no requiere multiplicación.

DCT- I

{\ Displaystyle X_ {k} = {\ frac {1} {2}} \ left (x_ {0} + (- 1) ^ {k} x_ {N-1} \ right) + \ sum _ {n = 1} ^ {N-2} {x_ {n} \ cos \ left [{\ frac {\ pi} {N-1}} nk \ right]}}

Podemos hacer que esta transformación sea ortogonal ( excepto por una constante multiplicativa) multiplicando x 0 y x N -1 por √2 y recíprocamente X 0 y X N -1 por 1 / √2. Sin embargo, esta normalización rompe la correspondencia con una DFT .

Tenga en cuenta que el DCT- I no está definido para , a diferencia de los otros tipos que se definen para cualquier N. positivo . ${\ Displaystyle N \ leq 2}$

DCT- II

{\ Displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac {1} {2}} \ right) k \ right]}}

Esta variante DCT es la más común y ampliamente utilizada. Por lo general, se le conoce simplemente como "el DCT". De la misma manera que para la DCT- I , podemos hacer esta transformación ortogonal multiplicando X 0 por 1 / √2. Esta forma estandarizada se usa ampliamente en la práctica pero rompe la correspondencia con la DFT .

Ejemplo para N = 8

Un desarrollo optimizado de esta transformada para el caso N = 8 (utilizado en JPEG y MPEG) se obtiene reescribiendo la transformada en forma matricial y factorizando la descomposición, para reducir el número de multiplicaciones escalares necesarias. Por ejemplo, la siguiente descomposición se utiliza para la factorización mediante el algoritmo de Chen, aquí ortogonalizado (consulte la observación anterior):

Coeficientes de cálculo constante

{\ Displaystyle {\ begin {pmatrix} C_ {1} \\ C_ {2} \\ C_ {3} \\ C_ {4} \\ C_ {5} \\ C_ {6} \\ C_ {7} \ end {pmatrix}} = {\ sqrt {\ frac {2} {N}}}. {\ begin {pmatrix} \ cos {\ frac {\ pi} {16}} \\\ cos {\ frac {2 \ pi} {16}} \\\ cos {\ frac {3 \ pi} {16}} \\\ cos {\ frac {4 \ pi} {16}} \\\ cos {\ frac {5 \ pi} {16}} \\\ cos {\ frac {6 \ pi} {16}} \\\ cos {\ frac {7 \ pi} {16}} \\\ end {pmatrix}} \ approx {\ begin { pmatrix} 0.49039 \\ 0.46194 \\ 0.41573 \\ 0.35355 \\ 0.27779 \\ 0.19134 \\ 0.09755 \ end {pmatrix}}}

DCT (8) (método de cálculo rápido)

{\ displaystyle {\ begin {pmatrix} X_ {0} \\ X_ {2} \\ X_ {4} \\ X_ {6} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {4} & C_ {4} & C_ {4} \\ C_ {2} & C_ {6} & - C_ {6} & - C_ {2} \\ C_ {4} & - C_ {4} & - C_ {4} & C_ {4} \\ C_ {6} & - C_ {2} & C_ {2} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} x_ {0} + x_ {7} \\ x_ {1} + x_ {6} \\ x_ {2} + x_ {5} \\ x_ {3} + x_ {4} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}} = {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \\ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7} & - C_ {5} & C_ {3} & - C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} x_ {0} - x_ {7} \\ x_ {1} -x_ {6} \\ x_ {2} -x_ {5} \\ x_ {3} -x_ {4} \ end {pmatrix}}}

La fórmula optimizada para un DCT unidimensional se usa a menudo tal cual para su uso en un espacio bidimensional (por transposición y composición); esta fórmula permite reducir notablemente el cálculo de 1024 multiplicaciones (fórmula básica) a 512 multiplicaciones solo en el procesamiento de un bloque de imagen de 8 × 8 (dos pasadas de 32 multiplicaciones por cada fila de 8 valores, que hacen 512 multiplicaciones); sin embargo, las optimizaciones aún son posibles optimizando la composición en sí de las dos pasadas (horizontal y vertical) para reducir aún más de 256 a 91 multiplicaciones solamente (o incluso menos según investigaciones más recientes).

Tenga en cuenta también que la primera matriz anterior también permite una reescritura de muchas multiplicaciones comunes (y, por lo tanto, la fórmula anterior requiere mucho menos que las 32 multiplicaciones, 16 si agrupamos las subexpresiones comunes). Todavía podríamos descomponer fácilmente la primera matriz porque es en sí misma una transformada DCT en R 4 , que se puede descomponer en dos submatrices de R 2 .

Numerosos estudios han demostrado cómo esta transformada se puede optimizar en función de las tensiones, en particular cuando la transformada se utiliza para compresión , porque la transformada permite concentrar la mayor parte de la energía en los coeficientes obtenidos x i de índice bajo, el otros que concentran poca energía tienen una contribución baja a la señal espacial inicial y se reducen a cero durante los pasos de cuantificación . Así, la precisión necesaria para representar los últimos coeficientes es menor o incluso cero, y los coeficientes constantes C i utilizados para el cálculo de las multiplicaciones escalares pueden ser objeto de optimización específica, fijando su precisión y utilizando técnicas de multiplicación por un número reducido de adiciones-turnos sin la necesidad de utilizar una multiplicación genérica.

Sin embargo, este algoritmo de cálculo (presentado tal como está, calcula la DCT unidimensional de 8 puntos con 16 multiplicaciones) es la base de todas las siguientes optimizaciones por factorización de las submatrices. El algoritmo de Loeffler es actualmente el más eficiente publicado (con 11 multiplicaciones para la misma DCT de 8 puntos en lugar de 16 con el algoritmo de Chen, sin embargo, algunos coeficientes se someten a dos multiplicaciones y esto podría hacer que el algoritmo sea menos estable). Incluso se ha demostrado que el número mínimo teórico de multiplicaciones requeridas para la transformación DCT de 8 puntos no puede ser menor que 11, lo que hace que los algoritmos de multiplicación de 11 escalares sean óptimos en términos de rendimiento bruto (difieren solo en términos de estabilidad de acuerdo con el orden en que se realizan las multiplicaciones y, por tanto, la precisión necesaria para los productos intermedios).

Sin embargo, el algoritmo de Loeffler agrupa 8 de las 11 multiplicaciones escalares en las salidas, lo que permite agrupar estas multiplicaciones con el siguiente paso de cuantificación (que hace que sea todo el punto): para una transformada 2D 8 × 8, es 8 × 11 se necesitan multiplicaciones para la transformación de filas y solo 8 × 3 multiplicaciones para las columnas, es decir, un total de 112 multiplicaciones (en lugar de 256 con el algoritmo de Chen) si las últimas 64 multiplicaciones escalares se realizan con cuantificación. Más detalles están disponibles en los estándares de compresión JPEG y MPEG .

DCT- III

{\ Displaystyle X_ {k} = {\ frac {1} {2}} x_ {0} + \ sum _ {n = 1} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} n \ left (k + {\ frac {1} {2}} \ right) \ right]}}

DCT- III es la transformada inversa de DCT-II. Es más conocido con el nombre de "DCT Inverse" y sus siglas (en inglés) "IDCT".

De la misma manera que para DCT-I, podemos hacer esta transformación ortogonal multiplicando x 0 por √2. Esta forma estandarizada se usa ampliamente en la práctica pero rompe la correspondencia con la DFT .

Ejemplo para N = 8

Al tomar el ejemplo anterior, obtenemos una descomposición inversa (aquí ortogonalizada) también utilizada en el algoritmo de Chen:

IDCT (8) (método de cálculo rápido)

{\ displaystyle {\ begin {pmatrix} x_ {0} \\ x_ {1} \\ x_ {2} \\ x_ {3} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {2} & C_ {4} & C_ {6} \\ C_ {4} & C_ {6} & - C_ {4} & - C_ {2} \\ C_ {4} & - C_ {6} & - C_ {4} & C_ {2} \\ C_ {4} & - C_ {2} & C_ {4} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {0} \ \ X_ {2} \ \ X_ {4} \\ X_ {6} \ end {pmatrix}} + {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \ \ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7 } & - C_ {5} & C_ {3} & -C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} x_ {7} \\ x_ {6} \\ x_ {5} \\ x_ {4} \ end {pmatrix}} = {\ begin {bmatrix} C_ {4} & C_ {2} & C_ {4} & C_ {6} \\ C_ {4} & C_ {6} & - C_ {4} & - C_ {2} \\ C_ {4} & - C_ {6} & - C_ {4} & C_ {2} \\ C_ {4} & - C_ {2} & C_ {4} & - C_ {6} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {0} \ \ X_ {2} \ \ X_ {4} \\ X_ {6} \ end {pmatrix}} - {\ begin {bmatrix} C_ {1} & C_ {3} & C_ {5} & C_ {7} \ \ C_ {3} & - C_ {7} & - C_ {1} & - C_ {5} \\ C_ {5} & - C_ {1} & C_ {7} & C_ {3} \\ C_ {7 } & - C_ {5} & C_ {3} & -C_ {1} \ end {bmatrix}}. {\ Begin {pmatrix} X_ {1} \\ X_ {3} \\ X_ {5} \\ X_ {7} \ end {pmatrix}}}

Nuevamente, la evaluación escalar de este producto de matriz contiene muchas subexpresiones comunes que permiten reducciones en el número de multiplicaciones escalares requeridas.

DCT- IV

{\ Displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} {x_ {n} \ cos \ left [{\ frac {\ pi} {N}} \ left (n + {\ frac {1} {2}} \ derecha) \ izquierda (k + {\ frac {1} {2}} \ derecha) \ derecha]}}

El DCT- IV es una matriz ortogonal .

Referencias

W. Chen, CH Smith y SC Fralick, “Un algoritmo computacional rápido para la transformada de coseno discreta”, IEEE Trans. Común. , Vuelo. COM-25, pág. 1004-1009, septiembre 1977.
C. Loeffler, A. Ligtenberg y G. Moschytz, “Algoritmos DCT prácticos y rápidos 1D con 11 multiplicaciones”, en Actas de la Conferencia internacional sobre acústica, habla y procesamiento de señales , p. 988--991, 1989

(en) [PDF] Un DCT basado en Cordic de alta calidad computacionalmente eficiente , B. Heyne, CC Sun, J. Goetze y SJ Ruan : mejora del algoritmo de cálculo de Loeffler mediante la transformación Cordic, análisis de complejidad y comparación de los rendimientos obtenidos , para el cálculo de la transformada DCT de 8 puntos (PDF).

Bibliografía

KR Rao y P. Yip, Transformada discreta del coseno: algoritmos, ventajas, aplicaciones (Academic Press, Boston, 1990).
AV Oppenheim, RW Schafer y JR Buck, Procesamiento de señales en tiempo discreto , segunda edición (Prentice-Hall, Nueva Jersey, 1999).
SA Martucci, “Convolución simétrica y transformaciones discretas de seno y coseno”, IEEE Trans. Sig. Processing SP-42 , 1038-1051 (1994).
Matteo Frigo y Steven G. Johnson: FFTW , http://www.fftw.org/ . Una biblioteca C gratuita ( GPL ) que puede calcular DCT rápidos (tipos I-IV) en una o más dimensiones, de tamaño arbitrario. También M. Frigo y SG Johnson, " The Design and Implementation of FFTW3 ", Proceedings of the IEEE 93 (2), 216-231 (2005).
E. Feig, S. Winograd. "Algoritmos rápidos para la transformada de coseno discreta", IEEE Transactions on Signal Processing 40 (9), 2174-2193 (1992).
P. Duhamel y M. Vetterli, “Transformadas rápidas de Fourier: una revisión tutorial y un estado del arte”, Signal Processing 19 , 259-299 (1990).
John Makhoul, "Una transformación rápida de coseno en una y dos dimensiones", IEEE Trans. Acoust. Speech Sig. Proc. 28 (1), 27 - 34 (1980).

Ver también

Transformada de Fourier
Transformada discreta de Fourier
JPEG : compresión DCT aplicada en formato JPEG

enlaces externos