DCT

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 5

Transformada Discreta del Coseno DCT

UNIVERSIDAD DE LAS FUERZAS ARMADAS - ESPE


Departamento de Elctrica y Electrnica
Sangolqu, Ecuador
Autores: Aguinaga Diana, Cachago Francis, Carchi Mara, Estvez Alexis, Guzmn Diego
dsaguinaga@espe.edu.ec
facachago@espe.edu.ec
mbcarchi@espe.edu.ec
adestevez1@espe.edu.ec
ddguzman1@espe.edu.ec

Abstract.- This paper discusses the Discrete Cosine Transform,


DCT coming from the English language Discrete Cosine Transform,
is an operation based on the Discrete Fourier Transform, but this
only works on periodic functions symmetrical pair, and the result
is a sequence of real numbers. The resulting DCT presents a finite
sequence of several points as the amount of solution various signals
in multiple frequency cosenoidades.
It is usually used to represent the most representative records
using spectral components so that the reconstructed signal still has
similarity to the original signal.
I.

I NTRODUCCIN

Este documento trata sobre la Transformada Coseno Discreta,


DCT que proviene del idioma ingls Discrete Cosine Transform, es
una operacin basada en la Transformada Discreta de Fourier, pero
esta solo acta sobre funciones peridicas con simetra par y el
resultado es una secuencia de nmeros reales. La DCT nos presenta
como resultado una secuencia finita de varios puntos como solucin
de la suma de distintas seales cosenoidades en frecuencias mltiplo.
Suele ser usada para la representacin de registros empleando las
componentes espectrales ms representativas de tal forma que
la seal reconstruida an tenga semejanza con la seal original.
Algunos algoritmos que usan la DCT son:
Dv
AC-3
JPEG
MJEPG
MJEPG-1
MJEPG-2
MJEPG-4
Vorbis
El proceso de descomponer un conjunto de muestras, en un
conjunto ponderado de funciones base cosenoidales de denomina
DCT y al mtodo de reconstruir el conjunto de muestras a partir
del conjunto ponderado de funciones base cosenoidales se le conoce
como IDCT que es la transformada discreta del coseno inversa. Si
la secuencia muestreada es mayor de 8 muestras, puede dividirse en
grupos de 8 muestras y la DCT puede calcularse independientemente
para cada grupo.
Debido a que las funciones base cosenoidales siempre tienen el
mismo conjunto de valores en cada uno de los puntos de muestreo
discretos, solamente cambian los valores de los coeficientes.
La DCT provee coeficientes de frecuencias correspondientes a
una seal discreta variable en el tiempo.
Dado que aplica la DFT en el sentido horizontal y vertical, los
valores en el tiempo de cada pixelm tendr coeficientes muy precisos
de frecuencias verticla y horizontal.

A. Transformada Discreta del Coseno Unidimensional DCT1D


La respuesta del sistema visual humano depende de la frecuencia
espacial. Si pudiramos, de algn modo descomponer una imagen
en un conjunto de imgenes, cada una con una frecuencia espacial
particular, podramos separar la estructura de la imagen que el ojo
puede ver a partir de la estructura que es imperceptible. La DCT
puede proporcionar una buena aproximacin a esta descomposicin.
La Transformada Discreta del Coseno Directa (DCT) es un tipo
de transformada real y ortogonal, encargada de compactar la energa
para datos altamente correlacionados. Sea una matriz cuadrada
ortogonal C, entonces la inversa de dicha matriz ser completamente
igual a la transpuesta de la misma. O bien, si multiplicamos la
matriz ortogonal C con su respectiva transpuesta, el resultado es la
matriz identidad.
C CT = I
El conjunto ponderado de funciones base cosinusoidales son
representados mediante formas de onda con una propiedad de
ortogonalidad, es decir si multiplicamos dos funciones base
cosinusoidales cualesquiera, el resultado ser nulo. De igual forma,
si multiplicamos una funcin base cosinusoidal por s misma, el
resultado del producto dar una constante.

B. Transformada Discreta del Coseno Biidimensional DCT2D


La DCT es ortogonal y separable. Esto implica que una DCT
bidimensional pueda implementarse mediante dos transformadas
unidimensionales. Esta propiedad permite que los algoritmos
desarrollados para una dimensin puedan extenderse directamente
a dos dimensiones. Esto es una ventaja desde el punto de vista de
simulacin y tambin para la realizacin del hardware.
La Transformada Discreta del Coseno Bidimensional o DCT-2D
se obtiene a partir de una extensin de la DCT-1D. Es decir, es
aplicado sobre imgenes digitales que no vienen hacer otra cosa
que matrices representando un conjunto de pixels. Por esta razn es
necesario aplicar la DCT-1 consecutivamente, primero a cada una
de las filas, y luego a cada una de las columnas.

II .

C ARACTERISTICAS SOBRESALIENTES DE LA DCT

La DCT posee una buena capacidad de compactacon de la


energa al dominio transformado, es decir, que la transformada de
coseno discreta consigue concentrar la mayor parte de la informacin
en pocos coeficientes transformados tal y como podemos visualizar
en la Figura1, adems de poseer la capacidad de ser independiente
a los datos. Presenta un algoritmo el cual no da como resultado
variaciones con los datos que recibe al ser comparados con otros
mtodos.

Tiene una interpretacin frecuencial de los componentes


transformados. La capacidad de interpretar los coeficientes desde
el punto de vista frecuencial permite aprovechar al mximo la
capacidad de compresin.
La DCT est bastante relacionada con la DFT , con la diferencia
de que es una transformada real, debido a que los vectores base
se componen exclusivamente de funciones coseno muestreadas.
Adems la DCT minimiza algunos de los problemas que surgen
con la aplicacin de la DFT a series de datos, como veremos ms
adelante.
La DCT tiene una buena capacidad de compactacin de la energa
al dominio transformado, es decir, que la transformada de coseno
discreta consigue concentrar la mayor parte de la informacin en
pocos coeficientes transformados tal y como muestra la imagen.
La transformacin es independiente de los datos. El algoritmo
aplicado no vara con los datos que recibe, como si sucede en otros
algoritmos de compresin.

G(r) =

k=0

r = 0,1,...,N-1
Donde:
1
c(r) = para r =0
2
y c(r) = 1 para r=1,2,...,N-1
Esta transformada tiene aplicaciones en procesamiento de
imagenes. El mtodo convensional para aplicar la DCT usa un
algoritmo de la DFT de 2N muestras.
Aplicaremos un mtodo mas eficiente de evaluar la DCT.
Concidere el clculo de:

Hay frmulas para el clculo rpido del algoritmo, como podra


ser la FFT para la DFT.
Produce pocos errores en los lmites de los bloques imagen. La
minimizacin de los errores a los bloques imagen permite reducir el
efecto de bloque en la imgenes reconstruidas.
Tiene una interpretacin frecuencial de los componentes transformados. La capacidad de interpretar los coeficientes en el punto
de vista frecuencial permite aprovechar al mximo la capacidad de
compresin.

N 1
h
2c(r) X
r i
x(k) cos (2k + 1)
N
2N

N
1
X

F (r) =

x(k) cos[(2k + 1)

k=0

r
]
2N

Para: r = 0,1,...,N-1
Si asumimos que N es parm definimos una nueva secuencia y(k)
por:
y(k) = x(2k)
y(N 1 k) = x(2k + 1)
con k = 0,1,...,(N/2)-1.
Con esto F(r)se reescribe y nos queda de la siguiente manera:
(N/2)1

F (r) =

y(k) cos[(4k + 3)

k=0

r
]+
2N

(N/2)1

y(N 1 k) cos[(4k + 3)

k=0

r
]
2N

Si decimos que k0 = N 1 k en la segunda sumatoria,


simplificando las dos ecuaciones obtenemos:

F (r) =

Figura 1. Concentracin de pontencia de una DCT-II bidimensional comparada con la concentracin de potencia de una DFT tambin bidemensional.

N
1
X

y(k) cos[(4k + 3)

k=0

r
]
2N

y F(r) puede ser evaluada como F (r) = Re[H(r)]


III .

C UANTIFICACIN Y REPRESENTACIN DE LA DCT


ENTERA

La DCT trabaja con un conjunto de muestras de una seal par y


peridica, al usar la DCT se compactan seales con informacin,
pero estas seales no son peridicas, no son pares y almacenarlas
ocupara un gran espacio.
La decorrelacion de coeficientes es muy importante para la
compresin de imagenes ,ya que, el posterior tratamiento de cada
coeficiente se puede realizar de forma independietne, sin prdida
de eficiencia de compresin. Otro aspecto importante de la DCT
es la capacidad de cuantificar los coeficientes utilizando valores de
cuantificacin que se eligen de forma visual.
La DCT de una secuencia x(k), k=0,1,...,N-1 est definida por:

Donde:

H(r) = ejr/2N

N
1
X

y(k)ej2rk/2N

k=0

Transformada Discreta del Coseno Inversa


Si denotamos a Y(r) a la IDCT de la secuencia y(k), la ecuacion
anterior pasa a ser:
H(r) = ejr/2N Y (r)
Se puede verificar facilmente que:

H(N r) = j[H(r)]
Donde * denota una conjugacion compleja. Y separando las
partes real e imaginaria tenemos:
F (r) = Re[H(r)]
F (N r) = Im[H(r)] Para:
r=0,1,...,(N/2)
El clculo de la IDTC se puede realizar de la siguiente manera:

x(k) =

N
1
X
r=0

h
r i
c(r)G(r) cos (2k + 1)
2N

,
para k=0,1,2,...,N-1
Las muestras pares son evaluadas como:

x(2k) =

N
1
X

[c(r)G(r)ejr/2N ]ej2rk/N

r=0

,
para k=0,1,2,...,N-1
Para obtener los puntos impares note que:
x(2k + 1) = x[2(N 1 k)]

Despues de obtener los coeficientes de la DCT, se procede a


realizar la cuantificacin con la finalidad de conseguir an mas
compresion representando los coeficientes DCT sin mas precision
que la que es necesaria para conseguir la calidad de la imagen
deseada.
Lo que se pretende con este proceso es descartar la informacion
que no es visualmente relevante. La cuantificacion en una aplicacion
de muchos a uno, y entonces tiene perdidas, de hecho es la principal
fuente de perdidas en los codificadores basados en la DCT.
En el proceso de cuantificaicon de la DCT los coeficientes de
alta frecuencia son divididos por un valor n > 1 y el resultado
se redondea al entero mas cercano, el valor de n varia con la
relacion de que a frecuencias mas altas, se asignan valores mas altos,
estos se cuantifican con pasos grandes y tienen una S/N baja, como
resultado los coeficientes que representas frecuencias espaciales bajas
son cuantificados con pasos relativamente bajos y tienen una S/N alta.
IV .

A LGORITMOS DCT

Para trabajar con seales que no son pares, peridicas y cuyo


registro requiere de gran almacenamiento se recurre al siguiente
algoritmo:
1. Se toman espacios muestrales de corta duracin
2. Cada espacio muestral se considera la mitad de una seal par y
peridica. Al respecto hay cuatro estrategias que pueden usarse
para convertir el espacio muestral en una seal par y peridica.
La figura 2 ilustra estas estrategias.
3. Se aplica un una DCT modificada segn la estrategia usada
para convertir el espacio muestral en una seal par y peridica.

y entonces la secuencia x(k), k0,1,...,N-1 puede obtenerse calculando


la parte real de la IDFT de la secuencia.
c(r)G(r)ejr/2N
, r=0,1,...,N-1
El nmero de operaciones requeridas para calcular la Inversa de
la DCT es el mismo que para calcurar la DCT.

A.

Cuantificacin

La cuantificacin nos permite reducir la precisin con la que los


coeficientes de la DCT se representan cuando se convierte la DCT
a una representacin entera.
Esto puede ser muy importante en compresin de imagen, en donde
se tiende a anular muchos coeficientes- especialmente los de altas
frecuencias espaciales.
Los valores cuantificados pueden ser asignados individualmente para
cada coeficiente DCT, utilizando el criterio basado en la visibilidad
de las funciones base.
Si medimos el umbralde visibilidad de una funcin base determinada,
la amplitud del coeficiente a partir de la cual la funcin base es
detectable por el ojo humano, podemos dividir (cuantificar) los
coeficientes por ese valor.
Si multiplicamos (decuantificar) los coeficientes as obtenidos por
ese valor antes de la reconstruccin, crearemos una condicin
en la que el ojo no podra detectar ninguna diferencia entre los
coeficientes DCT cuantificados y sin cuantificar.
Si estamos dispuestos a tolerar algunos defectos visibles en la
imagen reconstruida, podramos dividir por un valor ms grande que
el correspondiente al umbral de visibilidad.
Este proceso de ponderacin y truncamiento de los coeficientes
de la DCT a valores enteros se denomina cuantificacin, y el
restablecimiento aproximado de la magnitud de los coeficientes
originales de la DCT recibe el nombre de decuantificacin.

Figura 2. Extensiones par e impar de la DCT para muestras N=11 (puntos


rojos). Cada tipo de extensin origina una modificacin especial a la DCT
que se nombra en forma numrica

De la figura 2 podemos observar distintas estrategias para convertir


un conjunto de muestras en una seal con cierta simetra consiste
en concatenar una extensin de muestras. Esta extensin es una
versin reflejada del conjunto original. Segn el tipo de extensin
se pueden generar diferentes versiones de la DCT numeradas con
nmeros romanos del I al IV. Finalmente, cada versin de la DCT
debe deducirse a partir de la DFT.

A.

Relacin de la DCT con la DFT

Existe una relacin entre ambas transformadas, donde aparece


un factor complejo de proporcionalidad. Su mdulo, no obstante,
es unitario, de forma que las propiedades de compactacin de
energa no se ven afectadas por el mismo (ntese que en trminos
estrictos esta igualdad es slo cierta para los coeficientes [k, l] con
(k, l) 6= (0, 0) no para la componente continua. Pero, como es obvio
es en estos trminos en quienes nos centramos para analizar la
compactacin de energa pues sabemos a priori que la componente
continua de cualquier imagen es muy elevada).
A modo de resumen destacaremos las propiedades ms
importantes de la DCT:
1. La DCT es real y ortogonal, es decir, C = C y C 1 = C T
2. La DCT no es la parte real de la DFT unitaria. Sin embargo,
la DCT de una secuencia est relacionada con la DFT de su
extensin simtrica.
3. La DCT es una transformada rpida. La DCT de un vector de N
elementos puede calcularse en (N log2 N) operaciones a travs
de una FFT de N-puntos. Para demostrar esto definimos una
nueva secuencia Fo (n) en la que reordenamos los elementos
pares e impares de F(n).
4. La transformada discreta del coseno tiene una excelente compactacin de energa para datos altamente correlados. Esto es
debido a las siguientes propiedades:
Los vectores base de la transformada discreta del coseno
(es decir, filas de C) son los vectores base de la matriz
QC con tridiagonal simtrica.
La transformada discreta del coseno NxN esta muy
relacionada con la transformada KL de una secuencia
estacionaria de Markov de primer orden de longitud N
(siendo R su matriz de covarianza), cuando el parmetro
de correlacin D es prximo a la unidad. La razn es que
R -1, es una matriz de diagonal simtrica.
V.

E JEMPLO DCT-1

Extension peridica de tipo 1 para la DCT-1 de una secuencia


de cuatro puntos Para la DCT-1, x[n] se modifica primero en sus

en donde x [n] es la secuencia modificada x = [n]x[n], con


1

, n=0 y N-1
2
[n] =

1 ,1 n N 2
Para encontrar
x
1 [n] = x [((n))2N 2 ] + x [((n))2N 2 ]
Se necesita
1
x [n] = [( )(4) 1(3)
2
Con 2N 2 se tiene 8 2 = 6

1
0 0]
2
1
2 3]
x [n6 ] = [2 0 0
2
x
1 [n] = [4 3 2 1 2 3]
x [n6 ] = [2

La DCT-1 se define mediante :


xc1 [k] = 2

N
1
X

[n]x[n]cos(

n=0

xc1 [k] = 2

3
X

kn
)
N 1

[n]x[n]cos(

n=0

kn
)
3

Figura 3. Extensin peridica de tipo 1 para la DCT-1

x
1 [n] = x [((n))2N 2 ] + x [((n))2N 2 ]

0nN 1

0n3

1
1
xc1 [0] = 2( (4))cos(0)+1(3)cos(0)+1(2)cos(0)+ (1)cos(0) = 15
2
2

2
1
1
c1
x [1] = 2( (4))cos(0)+1(3)cos( )+1(2)cos( )+ (1)cos() = 4
2
3
3
2
1
2
4
1
c1
x [2] = 2( (4))cos(0)+1(3)cos( )+1(2)cos( )+ (1)cos(2) = 0
2
3
3
2
1
1
c1
x [3] = 2( (4))cos(0)+1(3)cos()+1(2)cos(2)+ (1)cos(3) = 1
2
2
xc1 [k] = [15

extremos y despus se extiende para que su periodo sea 2N 2 y


la secuencia resultante es

1
( )(1)]
2

1(2)

Figura 4. DCT-1 de la secuencia de 4 puntos

1]

A.

Relacin de la DCT-1 con la DFT

La DCT-1 de una secuencia de N puntos es idntica a la DFT de


(2N 2) puntos de la secuencia ampliada simtricamente x1 [n] ,
con:
x
1 [n] = [4 3 2 1 2 3]

para que al visualizarla se pueda responder de modo interactivo.


Otras consideraciones, tales como la complejidad de la tcnica y la
robustez frente al ruido asociado al canal, juegan papeles importantes
en las ventajas de un mtodo. Las aplicaciones de la transmisin
progresiva de imagen incluyen teleconferencia, telediagnstico
mdico, videotexto, servicios de seguridad, etc...

Utilizando la DFT con 2N 2 = 2(4) 2 = 6:


x[k] =

N
1
X

xN [n]ej

2kn
N

0k N 1

n=0

x[k] =

5
X

x6 [n]ej

2kn
6

0k5

n=0

x[k] = [15
Confirmando que:

1]

La transmisin progresiva de imgenes basada en la DCT se


realiza de la siguiente manera, en general una imagen NxM se
divide en bloques, cada uno de tamao KxL. Despus de conformar
los bloques en el dominio transformado, los coeficientes de la
transformada cuantificados son transmitidos en una cierta secuencia
al receptor. El receptor reconstruye la imagen conformando la
inversa de los grupos de coeficientes de la transformada y aadiendo
sucesivamente a la imagen informacin basada en las etapas previas.
Los detalles y la fidelidad de la imagen se mejoran sucesivamente,
casi sin prdidas en la imagen, en la etapa final.

xc1 [k] = x[k]


Reconocimiento de Patrones
VI .

A PLICACIONES

La DCT es una de las principales herramientas de compresin


de datos para aplicaciones en teleconferencia, videotelfonos,
transmisin de imagen progresiva, videotexto, HDTV, etc... En lo
que se refiere al tratamiento digital de imgenes, repasaremos las
principales aplicaciones en orden de importancia.
Codificacin de Imagenes
La DCT (al igual que las dems transformadas discretas) puede
aplicarse a codificacin de imagen, desde un punto de vista de
reduccin de ancho de banda o compresin de datos. El objetivo
es conseguir que una imagen(dominio espacial) o secuencia de
imgenes(dominios espacial-temporal), se traslade a un dominio
transformado de tal forma que se reduzca el ancho de banda para
la transmisin o losrequerimientos para elalmacenamiento; de
talforma que la subsiguiente recuperacin de la imagen o secuencia
de imgenes mediante la transformada inversa, no presente una
distorsin perceptible.
Filtrado de Imagen
Algunos ejemplos de filtrado basado en la DCT se ilustran en
la Figura 3 Conformando la respuesta del filtro, se puede obtener
la imagen filtrada deseada. Si elegimos un filtro para realzar las
altas frecuencias (filtro pasa altos), Figura 3 , se obtienen imgenes
con mayor nitidez (detalles de alta frecuencia) sin errores debidos a
efectos de bloque (tambin denominados efectos de borde).

Figura 5. Filtrado de imgenes basado en la DCT

Transmisin Progresiva de Imagenes


Otra aplicacin de la DCT, que se deriva de la compresin, es
la transmisin de imgenes sobre canales con un ancho de banda
pequeo, tales como lneas telefnicas. Si una imagen se enva en
su forma original sobre canales de banda estrecha, la transmisin de
la imagen completa puede llevar un tiempo considerable.
El objetivo que persiguen estos mtodos es desarrollar las
caracteristicas significativas de la imagen en una etapa inicial,

VII .

C ONCLUSIONES

Dado que la DCT aplica la DFT en el sentido horizontal


y vertical, los valores en el tiempo de cada pixelm tendr
coeficientes muy precisos de frecuencias verticla y horizontal.
Una DCT es equivalente a una DFT de una secuencia de tamao
doble.
VIII .

B IBLIOGRAFA

1. TRANSFORMADA DISCRETA DEL COSENO, Autor:


Alfonso Martin
2. ETAPAS DE COMPRESIN DE IMGENES
3. PROCESAMIENTO
DIGITAL
DE
IMGENES
UTILIZANDO FILTROS, Autor: Gustavo Aguilar Carrera
4. Transformada discreta del coseno
5. TRANSFORMADA COSENO DISCRETA, Autor: MI. Mario
Alfredo Ibarra Carrillo
6. Procesamiento de imgenes utilizando la transformada discreta
coseno, Autor: Antonio Lloris, P. G. Fernndez, J. Ramrez

También podría gustarte