Departamento de Matemática Aplicada ICurso 2002/2003. Universidad de Sevilla
Manuel Blanco GuisadoDavid Martínez GonzálezRaúl Palomino Sánchez
Procesamiento de Imágenes DigitalesProcesamiento de Imágenes Digitales
Compresión de Imágenes Digitales
Aplicación de Algoritmos Genéticos en Cuantización Vectorial
Contenidos
Cuantización Vectorial Algoritmos Genéticos Resultados Conclusiones Referencias
Cuantización Vectorial
Introducción Fundamentos Proceso de codificación Generación de codebooks Evaluación del resultado
Introducción a VQ
Vector Quantization (VQ) Técnica de compresión aplicable en
muchos campos: audio, vídeo, imágenes digitales,…
Aún no se ha logrado una implementación eficiente de manera globlal
Fundamentos de VQ
División de la imagen original en bloques Cada bloque es asignado a un
representante, dentro de un diccionario de bloques (codebook)
La compresión se consigue sustituyendo bloques de píxeles por índices al codebook
Fundamentos de VQ.Tamaño de bloque variable El tamaño de cada bloque se escoge en
función de la similitud del nivel de gris de sus píxeles
Aumenta el coste computacional en la elección de los bloques
Codebook más pequeño Codebook no reutilizable
Fundamentos de VQ.Tamaño de bloque fijo Codebooks reutilizables K-dimensión Almacenamiento del
codebook junto con la imagen Almacenamiento
independiente Ejemplo: bases de datos
Proceso de codificación VQ
Búsqueda en el codebook Gran coste computacional Full-search
Líneas de investigación:- Pretratamiento del codebook- Reducción de cálculos matemáticos
M
i
K
j
ijj cx1 1
2)(
Generación de codebooks
Proceso más costoso de VQ Influencia del tamaño Dimensión Número de codebooks Algoritmo de generación
(Linde-Buzo-Gray)
Generación de codebooks: LBG
Evaluación del resultado
Comparación entre técnicas y algoritmos
N
i
M
j
ijij
N
i
M
j
ij
yx
x
SNR
1 1
2
1 1
2
)(
Algoritmos Genéticos
Reproducción
Reproducción
Evaluación
Selección
¿Fin?
No
Si
AG general
ACC (Algoritmo de Codificación del Codebook)
RRepresentación
n
n
K = nxn
Fitness =
M
i
K
j
ijj cx1 1
2)(
ACCCCruce (genes movibles)
00110101
00111101
11
00
0011010000110101
00110101
a
ACCMMutación
1011010100110101
ACCSSelección
Padres
ACCSSelección
Padres CruzadosMutados
ACC
Selección
Padres CruzadosMutados
Programa
Conclusiones
Imagen original
Conclusiones
Imagen VQ con codebook de 256 elementos y k-dimension = 4
Conclusiones
Imagen VQ con codebook de 256 elementos y k-dimension = 9
Conclusiones
Imagen VQ con codebook de 512 elementos y k-dimension = 4
Conclusiones Peores resultados que métodos como JPEG. Mucho
tiempo de computación. Código abierto. Propuesta de ampliación: Velocidad del algoritmo de codificación (preprocesado
del codebook). Reducción del pixelado de la imagen. Almacenar el codebook de manera independiente Parametrización del tipo de los elementos de las
matrices VQ
Referencias
Digital Image Compression Using a Genetic Algorithm.Cheng Yimin, Wang Yixiao, Sun Qibin and Sun Longxiang.Division of Electronics, University of Science & Technology of China. Academic Press, 1999.
Vector Quantization. M. Qasem.http://www.geocities.com/mohamedqasem/vectorquantization/vq.html
Developer’s Image Library (DevIL). D. Woods.http://www.imagelib.org