Codificador De Imágenes Basado En Cuantización
Vectorial
Alexandro López Franco
Salvador Gómez Oliver
Fermín Cruz Mata
INDICE• Introducción• Compresión
– Quadtree– Transformada discreta del coseno– Clasificación de bloques– Cuantización vectorial– Imagen resultado
• Descompresión• Referencias
Introducción
• Algoritmo de compresión• Compresión con pérdidas• Bloques de tamaño variable• Transformada discreta del coseno• Cuantización vectorial
Introducción
IMG QT DCT
CLSF
VQ1
VQ2
VQ3
VQ4
CODEBOOK
IMGCUANTIZADA
IMG RESULTADO
Quadtree
Quadtree
• Estructura en árbol que representa la división en regiones de una imagen.
• Estructura:1
1 0 0 0
0 0 0 1
0 0 0 0
Quadtree
• Criterio de división:– Niveles de intensidad– Umbral (parámetro del programa)
• Tamaño mínimo de bloque: 8x8 • Ventajas:
– Compacto– Fácil de manipular
• Algoritmo• La estructura es usada para
almacenar más información
Transformada Discreta Del Coseno
• Transformada directa:
• Transformada inversa:
donde...
)2
12·)·cos(
2
12·)·cos(,()·()·(),(
1
0
1
0 N
Ym
N
XnYXfmknkmnC
N
Y
N
X
)2
12·)·cos(
2
12·)·cos(,()·()·(),(
1
0
1
0 N
Ym
N
XnmnCmknkYXf
N
n
N
m
coceN
nNnk
...2
01
)(
Clasificación de Bloques
• Clasificación de bloques según la información que contiene.
• Criterio de clasificación: borde, fondo o interior de objeto.
• Objetivo: Mejorar los resultados de la cuantización vectorial.
Clasificación de Bloques• Método de clasificación:
• Umbral T:– Parámetro del programa
O O V V V V V V
O O DV V V V V V
H DH D D O O O O
H H D D D O O O
H V O D D D O O
H V O O D D O O
H V O O O O O O
H V O O O O O O
Sumas(H, V, D)
E = max (V,H,D)
E>=T
E = V
E = H
Fondo
Vertical
Horizontal
Diagonal
Cuatización Vectorial
• Objetivo: Obtener un pequeño conjunto de vectores (codebook) que representen a la imagen de forma que cada bloque se pueda representar por el índice de su vector asociado (codevector).
• Aplicado sobre cada conjunto de bloques por separado:– Mayor eficacia del algoritmo
• Dos aproximaciones posibles:– Codebook fijo– Codebook variable
• Mayor calidad de la imagen.• Hay que calcular el codebook para cada imagen = Más cálculo.• Hay que guardar el codebook con la imagen = Más tamaño.
Obtención del Codebook 1
1) Se calcula un codevector inicial como la media de todos los vectores de la imagen.
Obtención del Codebook 2
2) Se dividen los codevectors actuales en dos, sumando y restando una cantidad pequeña
3) Se asocia a cada vector su codevector más cercano.
Obtención del Codebook 3
4) Se recalculan los codevectors como la media aritmética de los vectores asociados a él.
5) Si la variación en la distorsión media es menor que un valor umbral, volver al paso 3.
Si no, repetir a partir del paso 2 hasta tener el número de codevectors requeridos (parámetro del programa)
Obtención del Codebook 4
Seguimos una iteración más:
Dividimos los codevectors actuales en dos y asociamos a cada vector su codevector más cercano.
Obtención del Codebook 5
Recalculamos los codevectors como la media de sus asociados y volvemos a asociar cada vector a los codevectors más cercanos.
Obtención del Codebook 6
Seguimos recalculando los codevectors y obteniendo la nueva correspondencia hasta que no se consiga mejora en la medida de distorsión.
Obtención del Codebook 7
Se observa como se van desplazando los codevectors en cada iteración.
Obtención del Codebook 8
Hasta que no se consigan mejoras considerables en la medida de distorsión.
Obtención del Codebook 9
Veamos un ejemplo completo para ver como evoluciona el algoritmo.
Se obtendrá un codebook de 32 vectores.
Imagen Resultado
• Formada por los codebooks y la imagen cuantizada (vector de correspondencia entre vectores y codevectors)
CODEBOOKS
IMAGENCUANTIZADA
Referencias
• Estructura general del sistema:– VQ based on a main Feature classification in images. K
Panusopone and K.R. Rao. Journal of Visual Communication and Image Representation 11, 1-16 (2000).
• Cuantización Vectorial:– Data Compression (www.data-compression.com/vq.html)– Cuantificación Vectorial: (
http://grial.uc3m.es/~ffernand/publicaciones/proyecto/node37.html)
– Vector Cuantization: (www.geocities.com/mohamedqasem/vectorquantization/vq.html)
• Transformada discreta del coseno:– The pocket handbook of image processing algorithms in C
(Harley R. Myler, Arthur R. Weeks)