Transformada de coseno discreta

Este artículo puede citar incorrectamente o tergiversar muchas de sus fuentes. Consulte la página de limpieza para obtener más información. Editores: eliminen esta advertencia solo después de que se haya verificado la precisión de las diferencias enumeradas [[Wikipedia discusión:Solicitudes de comentario/Jagged 85/{{{subpage}}}|aquí]]. ( julio de 2022 )

Una transformada discreta del coseno ( DCT ) expresa una secuencia finita de puntos de datos en términos de una suma de funciones coseno que oscilan a diferentes frecuencias . La DCT, propuesta por primera vez por Nasir Ahmed en 1972, es una técnica de transformación ampliamente utilizada en el procesamiento de señales y la compresión de datos . Se utiliza en la mayoría de los medios digitales , incluidas las imágenes digitales (como JPEG y HEIF ), el vídeo digital (como MPEG y H.26x ), el audio digital (como Dolby Digital , MP3 y AAC ), la televisión digital (como SDTV , HDTV y VOD ), la radio digital (como AAC+ y DAB+ ) y la codificación de voz (como AAC-LD , Siren y Opus ). Las DCT también son importantes para numerosas otras aplicaciones en ciencia e ingeniería , como el procesamiento de señales digitales , los dispositivos de telecomunicaciones , la reducción del uso del ancho de banda de la red y los métodos espectrales para la solución numérica de ecuaciones diferenciales parciales .

Una DCT es una transformada relacionada con Fourier similar a la transformada discreta de Fourier (DFT), pero que utiliza solo números reales . Las DCT generalmente están relacionadas con los coeficientes de la serie de Fourier de una secuencia extendida periódica y simétricamente, mientras que las DFT están relacionadas con los coeficientes de la serie de Fourier de solo secuencias extendidas periódicamente. Las DCT son equivalentes a las DFT de aproximadamente el doble de longitud, que operan en datos reales con simetría par (ya que la transformada de Fourier de una función real y par es real y par), mientras que en algunas variantes los datos de entrada o salida se desplazan en media muestra.

Existen ocho variantes estándar de la DCT, de las cuales cuatro son comunes. La variante más común de la transformada discreta del coseno es la DCT de tipo II, que a menudo se denomina simplemente DCT . Esta fue la DCT original propuesta por primera vez por Ahmed. Su inversa, la DCT de tipo III, a menudo se denomina simplemente DCT inversa o IDCT . Dos transformadas relacionadas son la transformada discreta del seno (DST), que es equivalente a una DFT de funciones reales e impares , y la transformada discreta del coseno modificada (MDCT), que se basa en una DCT de datos superpuestos. Las DCT multidimensionales (MD DCT) se desarrollan para extender el concepto de DCT a señales multidimensionales. Se han desarrollado diversos algoritmos rápidos para reducir la complejidad computacional de la implementación de la DCT. Una de ellas es la DCT entera (IntDCT), ^[1] una aproximación entera de la DCT estándar, ^{[2] : ix, xiii, 1, 141–304} utilizada en varias normas internacionales ISO/IEC e ITU-T . ^{[1] [2]}

La compresión DCT, también conocida como compresión de bloques, comprime datos en conjuntos de bloques DCT discretos. ^[3] Los tamaños de bloques DCT incluyen 8x8 píxeles para la DCT estándar y tamaños de DCT enteros variados entre 4x4 y 32x32 píxeles. ^{[1] [4]} La DCT tiene una fuerte propiedad de compactación de energía , ^{[5] [6]} capaz de lograr alta calidad en altas relaciones de compresión de datos . ^{[7] [8]} Sin embargo, pueden aparecer artefactos de compresión en bloques cuando se aplica una compresión DCT pesada.

La DCT fue concebida por primera vez por Nasir Ahmed , T. Natarajan y KR Rao mientras trabajaban en la Universidad Estatal de Kansas . El concepto fue propuesto a la Fundación Nacional de Ciencias en 1972. La DCT fue pensada originalmente para la compresión de imágenes . ^{[9] [1]} Ahmed desarrolló un algoritmo DCT práctico con sus estudiantes de doctorado T. Raj Natarajan, Wills Dietrich y Jeremy Fries, y su amigo el Dr. KR Rao en la Universidad de Texas en Arlington en 1973. ^[9] Presentaron sus resultados en un artículo de enero de 1974, titulado Transformada Discreta del Coseno . ^{[5] [6] [10]} Describía lo que ahora se llama la DCT de tipo II (DCT-II), ^{[2] : 51} así como la DCT inversa de tipo III (IDCT). ^[5]

Desde su introducción en 1974, se han realizado importantes investigaciones sobre la DCT. ^[10] En 1977, Wen-Hsiung Chen publicó un artículo con C. Harrison Smith y Stanley C. Fralick presentando un algoritmo DCT rápido. ^{[11] [10]} Otros desarrollos incluyen un artículo de 1978 de MJ Narasimha y AM Peterson, y un artículo de 1984 de BG Lee. ^[10] Estos artículos de investigación, junto con el artículo original de Ahmed de 1974 y el artículo de Chen de 1977, fueron citados por el Joint Photographic Experts Group como base para el algoritmo de compresión de imágenes con pérdida de JPEG en 1992. ^{[10] [12]}

La transformada sinusoidal discreta (DST) se derivó de la DCT, al reemplazar la condición de Neumann en x=0 con una condición de Dirichlet . ^{[2] : 35-36} La DST fue descrita en el artículo de 1974 sobre DCT por Ahmed, Natarajan y Rao. ^[5] Una DST de tipo I (DST-I) fue descrita posteriormente por Anil K. Jain en 1976, y una DST de tipo II (DST-II) fue descrita posteriormente por HB Kekra y JK Solanka en 1978. ^[13]

En 1975, John A. Roese y Guner S. Robinson adaptaron la DCT para la codificación de vídeo con compensación de movimiento entre fotogramas . Experimentaron con la DCT y la transformada rápida de Fourier (FFT), desarrollando codificadores híbridos entre fotogramas para ambos, y descubrieron que la DCT es la más eficiente debido a su complejidad reducida, capaz de comprimir datos de imagen hasta 0,25 bits por píxel para una escena de videoteléfono con una calidad de imagen comparable a un codificador intrafotograma que requiere 2 bits por píxel. ^{[14] [15]} En 1979, Anil K. Jain y Jaswant R. Jain desarrollaron aún más la compresión de vídeo DCT con compensación de movimiento, ^{[16] [17]} también llamada compensación de movimiento en bloque. ^[17] Esto llevó a Chen a desarrollar un algoritmo práctico de compresión de video, llamado DCT con compensación de movimiento o codificación de escena adaptativa, en 1981. ^[17] La ​​DCT con compensación de movimiento luego se convirtió en la técnica de codificación estándar para la compresión de video desde fines de la década de 1980 en adelante. ^{[18] [19]}

Una variante de DCT, la transformada de coseno discreta modificada (MDCT), fue desarrollada por John P. Princen, AW Johnson y Alan B. Bradley en la Universidad de Surrey en 1987, ^[20] siguiendo el trabajo previo de Princen y Bradley en 1986. ^[21] La MDCT se utiliza en la mayoría de los formatos de compresión de audio modernos , como Dolby Digital (AC-3), ^{[22] [23]} MP3 (que utiliza un algoritmo híbrido DCT- FFT ), ^[24] Advanced Audio Coding (AAC), ^[25] y Vorbis ( Ogg ). ^[26]

Nasir Ahmed también desarrolló un algoritmo DCT sin pérdida con Giridhar Mandyam y Neeraj Magotra en la Universidad de Nuevo México en 1995. Esto permite que la técnica DCT se utilice para la compresión sin pérdida de imágenes. Es una modificación del algoritmo DCT original e incorpora elementos de DCT inversa y modulación delta . Es un algoritmo de compresión sin pérdida más eficaz que la codificación de entropía . ^[27] La ​​DCT sin pérdida también se conoce como LDCT. ^[28]

La DCT es la técnica de transformación más utilizada en el procesamiento de señales , ^[29] y, con diferencia, la transformación lineal más utilizada en la compresión de datos . ^[30] Los medios digitales sin comprimir, así como la compresión sin pérdida , tienen unos requisitos elevados de memoria y ancho de banda , que se reducen significativamente con la técnica de compresión con pérdida DCT, ^{[7] [8]} capaz de conseguir relaciones de compresión de datos de 8:1 a 14:1 para una calidad cercana a la de un estudio, ^[7] hasta 100:1 para un contenido de calidad aceptable. ^[8] Los estándares de compresión DCT se utilizan en tecnologías de medios digitales, como imágenes digitales , fotografías digitales , ^{[31] [32]} vídeo digital , ^{[18] [33]} transmisión de medios , ^[34] televisión digital , transmisión de televisión , vídeo a la carta (VOD), ^[8] cine digital , ^[22] vídeo de alta definición (vídeo HD) y televisión de alta definición (HDTV). ^{[7] [35]}

La DCT, y en particular la DCT-II, se utiliza a menudo en el procesamiento de señales e imágenes, especialmente para la compresión con pérdida, porque tiene una fuerte propiedad de compactación de energía . ^{[5] [6]} En aplicaciones típicas, la mayor parte de la información de la señal tiende a concentrarse en unos pocos componentes de baja frecuencia de la DCT. Para procesos de Markov fuertemente correlacionados , la DCT puede acercarse a la eficiencia de compactación de la transformada de Karhunen-Loève (que es óptima en el sentido de decorrelación). Como se explica a continuación, esto se deriva de las condiciones de contorno implícitas en las funciones coseno.

Las DCT se emplean ampliamente para resolver ecuaciones diferenciales parciales mediante métodos espectrales , donde las diferentes variantes de la DCT corresponden a condiciones de contorno pares e impares ligeramente diferentes en los dos extremos de la matriz.

Las DCT están estrechamente relacionadas con los polinomios de Chebyshev , y los algoritmos DCT rápidos (abajo) se utilizan en la aproximación de Chebyshev de funciones arbitrarias mediante series de polinomios de Chebyshev, por ejemplo en la cuadratura de Clenshaw-Curtis .

La DCT se utiliza ampliamente en muchas aplicaciones, que incluyen las siguientes.

La DCT-II es una técnica de compresión de imágenes importante. Se utiliza en estándares de compresión de imágenes como JPEG y estándares de compresión de vídeo como H.26x , MJPEG , MPEG , DV , Theora y Daala . Allí, se calcula la DCT-II bidimensional de bloques y los resultados se cuantifican y codifican por entropía . En este caso, normalmente es 8 y se aplica la fórmula DCT-II a cada fila y columna del bloque. El resultado es una matriz de coeficientes de transformación de 8 × 8 en la que el elemento (arriba a la izquierda) es el componente DC (frecuencia cero) y las entradas con valores de índice verticales y horizontales crecientes representan frecuencias espaciales verticales y horizontales más altas.${\displaystyle N\veces N}$${\estilo de visualización N}$${\estilo de visualización (0,0)}$

La DCT entera, una aproximación entera de la DCT, ^{[2] [1]} se utiliza en la codificación de vídeo avanzada (AVC), ^{[52] [1]} introducida en 2003, y en la codificación de vídeo de alta eficiencia (HEVC), ^{[4] [1]} introducida en 2013. La DCT entera también se utiliza en el formato de imagen de alta eficiencia (HEIF), que utiliza un subconjunto del formato de codificación de vídeo HEVC para codificar imágenes fijas. ^[4] AVC utiliza bloques de 4 x 4 y 8 x 8. HEVC y HEIF utilizan tamaños de bloque variados entre 4 x 4 y 32 x 32 píxeles . ^{[4] [1]} A partir de 2019 ^[actualizar], AVC es, con diferencia, el formato más utilizado para la grabación, compresión y distribución de contenido de vídeo, utilizado por el 91% de los desarrolladores de vídeo, seguido de HEVC, que es utilizado por el 43% de los desarrolladores. ^[43]

Las DCT multidimensionales (MD DCT) tienen varias aplicaciones, principalmente DCT 3-D como la DCT-II 3-D, que tiene varias aplicaciones nuevas como sistemas de codificación de imágenes hiperespectrales, ^[85] codificación DCT 3-D de longitud temporal variable, ^[86] algoritmos de codificación de video , ^[87] codificación de video adaptativa ^[88] y compresión 3-D. ^[89] Debido a la mejora en el hardware, software y la introducción de varios algoritmos rápidos, la necesidad de usar DCT MD está aumentando rápidamente. La DCT-IV ha ganado popularidad por sus aplicaciones en la implementación rápida de bancos de filtrado polifásico de valor real, ^[90] transformada ortogonal superpuesta ^{[91] [92]} y bases wavelet moduladas por coseno. ^[93]

La DCT desempeña un papel importante en el procesamiento de señales digitales , específicamente en la compresión de datos . La DCT se implementa ampliamente en procesadores de señales digitales (DSP), así como en software de procesamiento de señales digitales. Muchas empresas han desarrollado DSP basados ​​en la tecnología DCT. Las DCT se utilizan ampliamente para aplicaciones como codificación , decodificación, video, audio, multiplexación , señales de control, señalización y conversión de analógico a digital . Las DCT también se utilizan comúnmente para chips codificadores/decodificadores de televisión de alta definición (HDTV) . ^[1]

Un problema común con la compresión DCT en medios digitales son los artefactos de compresión en bloques , ^[94] causados ​​por bloques DCT. ^[3] En un algoritmo DCT, una imagen (o fotograma en una secuencia de imágenes) se divide en bloques cuadrados que se procesan independientemente unos de otros, luego los bloques DCT se toman dentro de cada bloque y los coeficientes DCT resultantes se cuantifican . Este proceso puede causar artefactos de bloqueo, principalmente en altas relaciones de compresión de datos . ^[94] Esto también puede causar el efecto de ruido de mosquito , que se encuentra comúnmente en el video digital . ^[95]

Los bloques DCT se utilizan a menudo en el arte glitch . ^[3] La artista Rosa Menkman hace uso de artefactos de compresión basados ​​en DCT en su arte glitch, ^[96] particularmente los bloques DCT que se encuentran en la mayoría de los formatos de medios digitales como imágenes digitales JPEG y audio MP3 . ^[3] Otro ejemplo es Jpegs del fotógrafo alemán Thomas Ruff , que utiliza artefactos JPEG intencionales como base del estilo de la imagen. ^{[97] [98]}

Al igual que cualquier transformada relacionada con Fourier, las transformadas discretas del coseno (DCT) expresan una función o una señal en términos de una suma de senos con diferentes frecuencias y amplitudes . Al igual que la transformada discreta de Fourier (DFT), una DCT opera sobre una función en un número finito de puntos de datos discretos . La distinción obvia entre una DCT y una DFT es que la primera utiliza solo funciones coseno, mientras que la segunda utiliza tanto cosenos como senos (en forma de exponenciales complejas ). Sin embargo, esta diferencia visible es meramente una consecuencia de una distinción más profunda: una DCT implica diferentes condiciones de contorno de la DFT u otras transformadas relacionadas.

Las transformadas relacionadas con Fourier que operan sobre una función sobre un dominio finito , como la DFT o la DCT o una serie de Fourier , pueden considerarse como la definición implícita de una extensión de esa función fuera del dominio. Es decir, una vez que escribes una función como una suma de senos, puedes evaluar esa suma en cualquier , incluso para donde no se especificó el original. La DFT, al igual que la serie de Fourier, implica una extensión periódica de la función original. Una DCT, al igual que una transformada del coseno , implica una extensión par de la función original.${\estilo de visualización f(x)}$${\estilo de visualización x}$${\estilo de visualización x}$${\estilo de visualización f(x)}$

Sin embargo, debido a que las DCT operan en secuencias discretas finitas , surgen dos problemas que no se aplican para la transformada continua del coseno. Primero, uno tiene que especificar si la función es par o impar en los límites izquierdo y derecho del dominio (es decir, los límites min- n y max- n en las definiciones a continuación, respectivamente). Segundo, uno tiene que especificar alrededor de qué punto la función es par o impar. En particular, considere una secuencia abcd de cuatro puntos de datos igualmente espaciados, y digamos que especificamos un límite izquierdo par . Hay dos posibilidades sensatas: o bien los datos son pares sobre la muestra a , en cuyo caso la extensión par es dcbabcd , o bien los datos son pares sobre el punto a medio camino entre a y el punto anterior, en cuyo caso la extensión par es dcbaabcd ( a se repite).

Estas opciones dan lugar a todas las variantes estándar de las DCT y también a las transformadas sinusoidales discretas (DST). Cada límite puede ser par o impar (2 opciones por límite) y puede ser simétrico respecto de un punto de datos o del punto intermedio entre dos puntos de datos (2 opciones por límite), para un total de 2 × 2 × 2 × 2 = 16 posibilidades. La mitad de estas posibilidades, aquellas en las que el límite izquierdo es par, corresponden a los 8 tipos de DCT; la otra mitad son los 8 tipos de DST.

Estas diferentes condiciones de contorno afectan fuertemente las aplicaciones de la transformada y conducen a propiedades excepcionalmente útiles para los diversos tipos de DCT. De manera más directa, cuando se utilizan transformadas relacionadas con Fourier para resolver ecuaciones diferenciales parciales mediante métodos espectrales , las condiciones de contorno se especifican directamente como parte del problema que se está resolviendo. O, para la MDCT (basada en la DCT de tipo IV), las condiciones de contorno están íntimamente involucradas en la propiedad crítica de la MDCT de cancelación de aliasing en el dominio del tiempo. De una manera más sutil, las condiciones de contorno son responsables de las propiedades de "compactación de energía" que hacen que las DCT sean útiles para la compresión de imágenes y audio, porque los límites afectan la tasa de convergencia de cualquier serie de tipo Fourier.

En particular, es bien sabido que cualquier discontinuidad en una función reduce la tasa de convergencia de la serie de Fourier, de modo que se necesitan más senos para representar la función con una precisión dada. El mismo principio rige la utilidad de la DFT y otras transformadas para la compresión de señales; cuanto más suave es una función, menos términos en su DFT o DCT se requieren para representarla con precisión, y más se puede comprimir. (Aquí, pensamos en la DFT o DCT como aproximaciones para la serie de Fourier o la serie de cosenos de una función, respectivamente, para poder hablar de su "suavidad"). Sin embargo, la periodicidad implícita de la DFT significa que las discontinuidades suelen ocurrir en los límites: es poco probable que cualquier segmento aleatorio de una señal tenga el mismo valor tanto en los límites izquierdo como derecho. (Un problema similar surge para la DST, en la que la condición de contorno izquierdo impar implica una discontinuidad para cualquier función que no sea cero en ese contorno.) En contraste, una DCT donde ambos contornos son pares siempre produce una extensión continua en los contornos (aunque la pendiente es generalmente discontinua). Esta es la razón por la que las DCT, y en particular las DCT de tipos I, II, V y VI (los tipos que tienen dos contornos pares) generalmente funcionan mejor para la compresión de señales que las DFT y las DST. En la práctica, una DCT de tipo II suele ser la preferida para tales aplicaciones, en parte por razones de conveniencia computacional.

Formalmente, la transformada discreta del coseno es una función lineal invertible (donde denota el conjunto de números reales ), o equivalentemente una matriz cuadrada N × N invertible . Existen varias variantes de la DCT con definiciones ligeramente modificadas. Los N números reales se transforman en los N números reales según una de las fórmulas: ${\displaystyle f:\mathbb {R} ^{N}\to \mathbb {R} ^{N}}$${\displaystyle \mathbb {R}}$ ${\displaystyle ~x_{0},\ \ldots \ x_{N-1}~}$${\displaystyle X_{0},\,\ldots ,\,X_{N-1}}$

${\displaystyle X_{k}={\frac {1}{2}}(x_{0}+(-1)^{k}x_{N-1})+\sum _{n=1}^{N-2}x_{n}\cos \left[\,{\tfrac {\ \pi }{\,N-1\,}}\,n\,k\,\right]\qquad {\text{ para }}~k=0,\ \ldots \ N-1~.}$

Algunos autores multiplican además los términos y por y, en consecuencia, multiplican los términos y por lo que, si se multiplica además por un factor de escala general de , la matriz DCT-I es ortogonal pero rompe la correspondencia directa con una DFT real-par .$estilo de visualización x_{0}}$$estilo de visualización x_{N-1}}$${\displaystyle {\sqrt {2\,}}\,,}$$Estilo de visualización X_{0}$$Estilo de visualización X_{N-1}}$${\displaystyle 1/{\sqrt {2\,}}\,,}$${\displaystyle {\sqrt {{\tfrac {2}{N-1\,}}\,}},}$

La DCT-I es exactamente equivalente (hasta un factor de escala total de 2) a una DFT de números reales con simetría par. Por ejemplo, una DCT-I de números reales es exactamente equivalente a una DFT de ocho números reales (simetría par), dividida por dos. (En cambio, las DCT de tipo II a IV implican un desplazamiento de media muestra en la DFT equivalente).${\estilo de visualización 2(N-1)}$${\estilo de visualización N=5}$${\estilo de visualización a\ b\ c\ d\ e}$${\estilo de visualización a\b\c\d\e\d\c\b}$

Sin embargo, tenga en cuenta que la DCT-I no está definida para menos de 2, mientras que todos los demás tipos de DCT están definidos para cualquier valor positivo.${\estilo de visualización N}$${\estilo de visualización N.}$

Por lo tanto, la DCT-I corresponde a las condiciones de contorno: es par alrededor y par alrededor de ; de manera similar para$Estilo de visualización x_{n}$${\estilo de visualización n=0}$${\displaystyle n=N-1}$${\displaystyle X_{k}.}$

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(n+{\tfrac {1}{2}}\right)k\,\right]\qquad {\text{ para }}~k=0,\ \puntos \ N-1~.}$

La DCT-II es probablemente la forma más utilizada y a menudo se la denomina simplemente "la DCT". ^{[5] [6]}

Esta transformación es exactamente equivalente (hasta un factor de escala total de 2) a una DFT de entradas reales de simetría par donde los elementos de índice par son cero. Es decir, es la mitad de la DFT de las entradas donde para y para la transformación DCT-II también es posible utilizando una señal 2 N seguida de una multiplicación por medio desplazamiento. Esto lo demuestra Makhoul .${\estilo de visualización 4N}$${\estilo de visualización 4N}$${\displaystyle y_{n},}$${\displaystyle y_{2n}=0,}$ ${\displaystyle y_{2n+1}=x_{n}}$${\displaystyle 0\leq n<N,}$ ${\displaystyle y_{2N}=0,}$${\ Displaystyle y_ {4N-n} = y_ {n}}$${\displaystyle 0<n<2N.}$

Algunos autores multiplican además el término por y multiplican el resto de la matriz por un factor de escala general de (ver más abajo el cambio correspondiente en DCT-III). Esto hace que la matriz DCT-II sea ortogonal , pero rompe la correspondencia directa con una DFT real-par de entrada semidesplazada. Esta es la normalización utilizada por Matlab , por ejemplo, ver. ^[99] En muchas aplicaciones, como JPEG , la escala es arbitraria porque los factores de escala se pueden combinar con un paso computacional posterior (por ejemplo, el paso de cuantificación en JPEG ^[100] ), y se puede elegir una escala que permita calcular la DCT con menos multiplicaciones. ^{[101] [102]}$Estilo de visualización X_{0}$${\displaystyle 1/{\sqrt {N\,}}\,}$${\textstyle {\sqrt {{2}/{N}}}}$

La DCT-II implica las condiciones de contorno: es par alrededor y par alrededor es par alrededor y impar alrededor${\displaystyle x_{n}}$${\displaystyle n=-1/2}$${\displaystyle n=N-1/2\,;}$ ${\displaystyle X_{k}}$${\displaystyle k=0}$${\displaystyle k=N.}$

${\displaystyle X_{k}={\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(k+{\tfrac {1}{2}}\right)n\,\right]\qquad {\text{ for }}~k=0,\ \ldots \ N-1~.}$

Debido a que es la inversa de la DCT-II hasta un factor de escala (ver más abajo), a esta forma a veces se la denomina simplemente "la DCT inversa" ("IDCT"). ^[6]

Algunos autores dividen el término por en lugar de por 2 (lo que da como resultado un término general) y multiplican la matriz resultante por un factor de escala general de (consulte más arriba el cambio correspondiente en DCT-II), de modo que la DCT-II y la DCT-III sean transpuestas entre sí. Esto hace que la matriz DCT-III sea ortogonal , pero rompe la correspondencia directa con una DFT real-par de salida semidesplazada.${\displaystyle x_{0}}$${\displaystyle {\sqrt {2}}}$${\displaystyle x_{0}/{\sqrt {2}}}$${\textstyle {\sqrt {2/N}}}$

La DCT-III implica las condiciones de contorno: es par alrededor y impar alrededor es par alrededor y par alrededor${\displaystyle x_{n}}$${\displaystyle n=0}$${\displaystyle n=N;}$ ${\displaystyle X_{k}}$${\displaystyle k=-1/2}$${\displaystyle k=N-1/2.}$

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\,\left(n+{\tfrac {1}{2}}\right)\left(k+{\tfrac {1}{2}}\right)\,\right]\qquad {\text{ for }}k=0,\ \ldots \ N-1~.}$

La matriz DCT-IV se vuelve ortogonal (y por lo tanto, al ser claramente simétrica, su propia inversa) si se multiplica además por un factor de escala general de${\textstyle {\sqrt {2/N}}.}$

Una variante de la DCT-IV, donde se superponen los datos de diferentes transformaciones , se denomina transformada de coseno discreta modificada (MDCT). ^[103]

La DCT-IV implica las condiciones de contorno: es par alrededor y es impar alrededor de manera similar para${\displaystyle x_{n}}$${\displaystyle n=-1/2}$${\displaystyle n=N-1/2;}$${\displaystyle X_{k}.}$

Las DCT de los tipos I a IV tratan ambos límites de manera consistente en cuanto al punto de simetría: son pares/impares alrededor de un punto de datos para ambos límites o a medio camino entre dos puntos de datos para ambos límites. Por el contrario, las DCT de los tipos V a VIII implican límites que son pares/impares alrededor de un punto de datos para un límite y a medio camino entre dos puntos de datos para el otro límite.

En otras palabras, las transformadas discretas de coseno de tipo I a IV son equivalentes a las transformadas discretas de coseno de tipo par real de orden par (sin importar si es par o impar), ya que la transformada discreta de coseno correspondiente es de longitud (para la transformada discreta de coseno I) o (para la transformada discreta de coseno II y III) o (para la transformada discreta de coseno IV). Los cuatro tipos adicionales de transformada discreta de coseno ^[104] corresponden esencialmente a las transformadas discretas de coseno de tipo par real de orden lógicamente impar, que tienen factores de en los denominadores de los argumentos de coseno.${\displaystyle N}$${\displaystyle 2(N-1)}$${\displaystyle 4N}$${\displaystyle 8N}$${\displaystyle N\pm {1}/{2}}$

Sin embargo, estas variantes parecen rara vez usarse en la práctica. Una razón, quizás, es que los algoritmos FFT para DFT de longitud impar son generalmente más complicados que los algoritmos FFT para DFT de longitud par (por ejemplo, los algoritmos de base 2 más simples son solo para longitudes pares), y esta mayor complejidad se traslada a las DCT como se describe a continuación.

(La matriz real-par trivial, una DFT de longitud uno (longitud impar) de un solo número a  , corresponde a una DCT-V de longitud )${\displaystyle N=1.}$

Utilizando las convenciones de normalización anteriores, la inversa de DCT-I es DCT-I multiplicada por 2/( N  − 1). La inversa de DCT-IV es DCT-IV multiplicada por 2/ N . La inversa de DCT-II es DCT-III multiplicada por 2/ N y viceversa. ^[6]

Al igual que en el caso de la DFT , el factor de normalización que se encuentra delante de estas definiciones de transformada es simplemente una convención y difiere entre tratamientos. Por ejemplo, algunos autores multiplican las transformadas por de modo que la inversa no requiere ningún factor multiplicativo adicional. Combinado con factores apropiados de √ 2 (ver arriba), esto se puede utilizar para hacer que la matriz de transformada sea ortogonal .${\textstyle {\sqrt {2/N}}}$

Las variantes multidimensionales de los diversos tipos de DCT se derivan directamente de las definiciones unidimensionales: son simplemente un producto separable (equivalentemente, una composición) de DCT a lo largo de cada dimensión.

Por ejemplo, una DCT-II bidimensional de una imagen o una matriz es simplemente la DCT-II unidimensional, desde arriba, realizada a lo largo de las filas y luego a lo largo de las columnas (o viceversa). Es decir, la DCT-II 2D se obtiene mediante la fórmula (omitiendo la normalización y otros factores de escala, como se indicó anteriormente):

${\displaystyle {\begin{aligned}X_{k_{1},k_{2}}&=\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\right)\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\\&=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right].\end{aligned}}}$

La inversa de una DCT multidimensional es simplemente un producto separable de las inversas de las DCT unidimensionales correspondientes (ver arriba), por ejemplo, las inversas unidimensionales aplicadas a lo largo de una dimensión a la vez en un algoritmo de fila-columna.

La DCT-II 3-D es solo la extensión de la DCT-II 2-D en el espacio tridimensional y se puede calcular matemáticamente mediante la fórmula

${\displaystyle X_{k_{1},k_{2},k_{3}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}\sum _{n_{3}=0}^{N_{3}-1}x_{n_{1},n_{2},n_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}k_{i}=0,1,2,\dots ,N_{i}-1.}$

La inversa de la DCT-II 3-D es la DCT-III 3-D y se puede calcular a partir de la fórmula dada por

${\displaystyle x_{n_{1},n_{2},n_{3}}=\sum _{k_{1}=0}^{N_{1}-1}\sum _{k_{2}=0}^{N_{2}-1}\sum _{k_{3}=0}^{N_{3}-1}X_{k_{1},k_{2},k_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}n_{i}=0,1,2,\dots ,N_{i}-1.}$

Técnicamente, el cálculo de una DCT bidimensional, tridimensional (o multidimensional) mediante secuencias de DCT unidimensionales a lo largo de cada dimensión se conoce como algoritmo de fila-columna . Sin embargo, al igual que con los algoritmos FFT multidimensionales , existen otros métodos para calcular lo mismo mientras se realizan los cálculos en un orden diferente (es decir, intercalando/combinando los algoritmos para las diferentes dimensiones). Debido al rápido crecimiento de las aplicaciones basadas en la DCT 3-D, se han desarrollado varios algoritmos rápidos para el cálculo de la DCT-II 3-D. Los algoritmos Vector-Radix se aplican para calcular la DCT MD para reducir la complejidad computacional y aumentar la velocidad computacional. Para calcular la DCT-II 3-D de manera eficiente, se desarrolló un algoritmo rápido, el algoritmo Vector-Radix Decimation in Frequency (VR DIF).

Para aplicar el algoritmo VR DIF, los datos de entrada se deben formular y reorganizar de la siguiente manera. ^{[105] [106]} Se supone que el tamaño de la transformación N × N × N es 2.

${\displaystyle {\begin{array}{lcl}{\tilde {x}}(n_{1},n_{2},n_{3})=x(2n_{1},2n_{2},2n_{3})\\{\tilde {x}}(n_{1},n_{2},N-n_{3}-1)=x(2n_{1},2n_{2},2n_{3}+1)\\{\tilde {x}}(n_{1},N-n_{2}-1,n_{3})=x(2n_{1},2n_{2}+1,2n_{3})\\{\tilde {x}}(n_{1},N-n_{2}-1,N-n_{3}-1)=x(2n_{1},2n_{2}+1,2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,n_{2},n_{3})=x(2n_{1}+1,2n_{2},2n_{3})\\{\tilde {x}}(N-n_{1}-1,n_{2},N-n_{3}-1)=x(2n_{1}+1,2n_{2},2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,n_{3})=x(2n_{1}+1,2n_{2}+1,2n_{3})\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,N-n_{3}-1)=x(2n_{1}+1,2n_{2}+1,2n_{3}+1)\\\end{array}}}$

dónde${\displaystyle 0\leq n_{1},n_{2},n_{3}\leq {\frac {N}{2}}-1}$

La figura adyacente muestra las cuatro etapas que intervienen en el cálculo de la DCT-II 3-D utilizando el algoritmo VR DIF. La primera etapa es la reordenación 3-D utilizando el mapeo de índices ilustrado por las ecuaciones anteriores. La segunda etapa es el cálculo de la mariposa. Cada mariposa calcula ocho puntos juntos como se muestra en la figura que se encuentra justo debajo, donde .${\displaystyle c(\varphi _{i})=\cos(\varphi _{i})}$

La DCT-II 3-D original ahora se puede escribir como

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{N-1}\sum _{n_{2}=1}^{N-1}\sum _{n_{3}=1}^{N-1}{\tilde {x}}(n_{1},n_{2},n_{3})\cos(\varphi k_{1})\cos(\varphi k_{2})\cos(\varphi k_{3})}$

dónde${\displaystyle \varphi _{i}={\frac {\pi }{2N}}(4N_{i}+1),{\text{ and }}i=1,2,3.}$

Si se consideran las partes pares e impares de y y , la fórmula general para el cálculo de la DCT-II 3-D se puede expresar como${\displaystyle k_{1},k_{2}}$${\displaystyle k_{3}}$

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{2}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}{\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})\cos(\varphi (2k_{1}+i)\cos(\varphi (2k_{2}+j)\cos(\varphi (2k_{3}+l))}$

dónde

${\displaystyle {\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})={\tilde {x}}(n_{1},n_{2},n_{3})+(-1)^{l}{\tilde {x}}\left(n_{1},n_{2},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{j}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}\right)+(-1)^{j+l}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{i}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}\right)+(-1)^{i+j}{\tilde {x}}\left(n_{1}+{\frac {n}{2}}+{\frac {n}{2}},n_{2},n_{3}\right)}$

${\displaystyle +(-1)^{i+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}+{\frac {n}{3}}\right)}$

${\displaystyle +(-1)^{i+j+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right){\text{ where }}i,j,l=0{\text{ or }}1.}$

Todo el cálculo de la DCT 3-D necesita etapas, y cada etapa implica mariposas. Todo el cálculo de la DCT 3-D requiere mariposas para ser calculado. Cada mariposa requiere siete multiplicaciones reales (incluidas las multiplicaciones triviales) y 24 sumas reales (incluidas las sumas triviales). Por lo tanto, el número total de multiplicaciones reales necesarias para esta etapa es y el número total de sumas reales, es decir, incluidas las sumas posteriores (sumas recursivas) que se pueden calcular directamente después de la etapa de mariposa o después de la etapa de inversión de bits, se da por ^[106].${\displaystyle ~[\log _{2}N]~}$${\displaystyle ~{\tfrac {1}{8}}\ N^{3}~}$${\displaystyle ~\left[{\tfrac {1}{8}}\ N^{3}\log _{2}N\right]~}$${\displaystyle ~\left[{\tfrac {7}{8}}\ N^{3}\ \log _{2}N\right]~,}$ ${\displaystyle ~\underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N\right]} _{\text{Real}}+\underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]} _{\text{Recursive}}=\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]~.}$

El método convencional para calcular MD-DCT-II utiliza un enfoque de marco de fila-columna (RCF), que es computacionalmente complejo y menos productivo en las plataformas de hardware más recientes y avanzadas. La cantidad de multiplicaciones necesarias para calcular el algoritmo VR DIF en comparación con el algoritmo RCF es bastante pequeña. La cantidad de multiplicaciones y sumas involucradas en el enfoque RCF se dan por y respectivamente. De la Tabla 1, se puede ver que la cantidad total${\displaystyle ~\left[{\frac {3}{2}}N^{3}\log _{2}N\right]~}$${\displaystyle ~\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]~,}$

El número de multiplicaciones asociadas con el algoritmo 3-D DCT VR es menor que el asociado con el enfoque RCF en más del 40%. Además, el enfoque RCF implica transposición de matriz y más indexación e intercambio de datos que el nuevo algoritmo VR. Esto hace que el algoritmo 3-D DCT VR sea más eficiente y más adecuado para aplicaciones 3-D que involucran el 3-D DCT-II, como la compresión de video y otras aplicaciones de procesamiento de imágenes 3-D.

La consideración principal al elegir un algoritmo rápido es evitar complejidades computacionales y estructurales. A medida que avanza la tecnología de las computadoras y los DSP, el tiempo de ejecución de las operaciones aritméticas (multiplicaciones y sumas) se está volviendo muy rápido, y la estructura computacional regular se convierte en el factor más importante. ^[107] Por lo tanto, aunque el algoritmo 3-D VR propuesto anteriormente no alcanza el límite inferior teórico en el número de multiplicaciones, ^[108] tiene una estructura computacional más simple en comparación con otros algoritmos 3-D DCT. Se puede implementar en su lugar utilizando una sola mariposa y posee las propiedades del algoritmo Cooley-Tukey FFT en 3-D. Por lo tanto, el 3-D VR presenta una buena opción para reducir las operaciones aritméticas en el cálculo de la DCT-II 3-D, al tiempo que mantiene la estructura simple que caracteriza a los algoritmos Cooley-Tukey FFT de estilo mariposa .

La imagen de la derecha muestra una combinación de frecuencias horizontales y verticales para una DCT bidimensional de 8 × 8. Cada paso de izquierda a derecha y de arriba a abajo es un aumento de frecuencia de 1/2 ciclo. Por ejemplo, moverse un paso hacia la derecha desde el cuadrado superior izquierdo produce un aumento de medio ciclo en la frecuencia horizontal. Otro movimiento hacia la derecha produce dos medios ciclos. Un movimiento hacia abajo produce dos medios ciclos horizontales y un medio ciclo vertical. Los datos de origen (8×8) se transforman en una combinación lineal de estos 64 cuadrados de frecuencia.${\displaystyle (~N_{1}=N_{2}=8~)}$

La DCT-IV MD es simplemente una extensión de la DCT-IV 1-D en el dominio M  -dimensional. La DCT-IV 2-D de una matriz o una imagen se obtiene mediante

${\displaystyle X_{k,\ell }=\sum _{n=0}^{N-1}\;\sum _{m=0}^{M-1}\ x_{n,m}\cos \left(\ {\frac {\,(2m+1)(2k+1)\ \pi \,}{4N}}\ \right)\cos \left(\ {\frac {\,(2n+1)(2\ell +1)\ \pi \,}{4M}}\ \right)~,}$

para y${\displaystyle ~~k=0,\ 1,\ 2\ \ldots \ N-1~~}$${\displaystyle ~~\ell =0,\ 1,\ 2,\ \ldots \ M-1~.}$

Podemos calcular la DCT-IV MD utilizando el método de fila-columna regular o podemos utilizar el método de transformada polinómica ^[109] para un cálculo rápido y eficiente. La idea principal de este algoritmo es utilizar la transformada polinómica para convertir la DCT multidimensional en una serie de DCT 1-D directamente. La DCT-IV MD también tiene varias aplicaciones en varios campos.

Aunque la aplicación directa de estas fórmulas requeriría operaciones, es posible calcular lo mismo con solo complejidad factorizando el cálculo de manera similar a la transformada rápida de Fourier (FFT). También se pueden calcular DCT mediante FFT combinadas con pasos de preprocesamiento y posprocesamiento. En general, los métodos para calcular DCT se conocen como algoritmos de transformada rápida de coseno (FCT).${\displaystyle ~{\mathcal {O}}(N^{2})~}$${\displaystyle ~{\mathcal {O}}(N\log N)~}$${\displaystyle ~{\mathcal {O}}(N)~}$${\displaystyle ~{\mathcal {O}}(N\log N)~}$

En principio, los algoritmos más eficientes suelen ser aquellos que están especializados directamente para la DCT, en lugar de utilizar una FFT ordinaria más operaciones adicionales (véase más adelante una excepción). Sin embargo, incluso los algoritmos DCT "especializados" (incluidos todos los que alcanzan los recuentos aritméticos más bajos conocidos, al menos para tamaños de potencia de dos ) suelen estar estrechamente relacionados con los algoritmos FFT; dado que las DCT son esencialmente DFT de datos reales-par, se puede diseñar un algoritmo DCT rápido tomando una FFT y eliminando las operaciones redundantes debido a esta simetría. Esto incluso se puede hacer de forma automática (Frigo y Johnson 2005). Los algoritmos basados ​​en el algoritmo Cooley-Tukey FFT son los más comunes, pero también se puede aplicar cualquier otro algoritmo FFT. Por ejemplo, el algoritmo Winograd FFT conduce a algoritmos de multiplicación mínima para la DFT, aunque generalmente a costa de más adiciones, y un algoritmo similar fue propuesto por (Feig y Winograd 1992a) para la DCT. Debido a que los algoritmos para DFT, DCT y transformaciones similares están tan estrechamente relacionados, cualquier mejora en los algoritmos para una transformada conducirá teóricamente a ganancias inmediatas también para las otras transformaciones (Duhamel y Vetterli 1990).${\displaystyle ~{\mathcal {O}}(N)~}$

Si bien los algoritmos DCT que emplean una FFT no modificada suelen tener cierta sobrecarga teórica en comparación con los mejores algoritmos DCT especializados, los primeros también tienen una clara ventaja: hay una amplia disponibilidad de programas FFT altamente optimizados. Por lo tanto, en la práctica, suele ser más fácil obtener un alto rendimiento para longitudes generales N con algoritmos basados ​​en FFT. ^[a] Por otro lado, los algoritmos DCT especializados se utilizan ampliamente para transformadas de tamaños pequeños y fijos, como la DCT-II de 8 × 8 utilizada en la compresión JPEG , o las DCT pequeñas (o MDCT) que se utilizan normalmente en la compresión de audio. (El tamaño reducido del código también puede ser una razón para utilizar una DCT especializada para aplicaciones de dispositivos integrados).

De hecho, incluso los algoritmos DCT que utilizan una FFT ordinaria son a veces equivalentes a podar las operaciones redundantes de una FFT más grande de datos simétricos reales, e incluso pueden ser óptimos desde la perspectiva de los recuentos aritméticos. Por ejemplo, una DCT de tipo II es equivalente a una DFT de tamaño con simetría real-par cuyos elementos de índice par son cero. Uno de los métodos más comunes para calcular esto a través de una FFT (por ejemplo, el método utilizado en FFTPACK y FFTW ) fue descrito por Narasimha y Peterson (1978) y Makhoul (1980), y este método en retrospectiva puede verse como un paso de un algoritmo Cooley-Tukey de diezmado en el tiempo de radix-4 aplicado a la DFT real-par "lógica" correspondiente a la DCT-II. ^[b] Debido a que los elementos de índice par son cero, este paso de radix-4 es exactamente el mismo que un paso de radix dividido. Si la FFT de datos reales de tamaño posterior también se realiza mediante un algoritmo de base dividida de datos reales (como en Sorensen et al. (1987)), entonces el algoritmo resultante en realidad coincide con lo que durante mucho tiempo fue el recuento aritmético publicado más bajo para la DCT-II de potencia de dos ( operaciones aritméticas reales ^[c] ).${\displaystyle ~4N~}$${\displaystyle ~N~}$${\displaystyle ~2N\log _{2}N-N+2~}$

Una reducción reciente en el conteo de operaciones también utiliza una FFT de datos reales. ^[110] Por lo tanto, no hay nada intrínsecamente malo en calcular la DCT a través de una FFT desde una perspectiva aritmética: a veces es simplemente una cuestión de si el algoritmo FFT correspondiente es óptimo. (En la práctica, la sobrecarga de llamadas de función al invocar una rutina FFT separada puede ser significativa para pequeñas, pero esta es una implementación más que una cuestión algorítmica, ya que se puede resolver mediante desenrollado o inserción en línea).${\displaystyle ~{\tfrac {17}{9}}N\log _{2}N+{\mathcal {O}}(N)}$${\displaystyle ~N~,}$

Considere esta imagen en escala de grises de 8x8 de la letra mayúscula A.

Cada función base se multiplica por su coeficiente y luego este producto se suma a la imagen final.

• Transformada wavelet discreta
• JPEG  - Transformada de coseno  discreta    :  contiene un ejemplo potencialmente más fácil de entender de la transformación DCT
• Lista de transformadas relacionadas con Fourier
• Transformada de coseno discreta modificada