1 Departamento de Matemática Aplicada I Curso 2002/2003. Universidad de Sevilla Manuel Blanco Guisado David Martínez González Raúl Palomino Sánchez Procesamiento de Imágenes Digitales

2 Compresión de Imágenes Digitales Aplicación de Algoritmos Genéticos en Cuantización Vectorial

3 Contenidos Cuantización Vectorial Algoritmos Genéticos Resultados Conclusiones Referencias

4 Cuantización Vectorial Introducción Fundamentos Proceso de codificación Generación de codebooks Evaluación del resultado

5 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

6 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

7 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

8 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

9 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

10 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)

11 Generación de codebooks: LBG

12 Evaluación del resultado Comparación entre técnicas y algoritmos

13 Algoritmos Genéticos Reproducción Evaluación Selección ¿Fin? No Si AG general

14 ACC (Algoritmo de Codificación del Codebook) RRepresentación n n K = nxn Fitness =

15 ACC CCruce (genes movibles) 00110101 00111101 11 00 0011010000110101 a

16 ACC MMutación 1011010100110101

17 ACC SSelección Padres

18 ACC SSelección PadresCruzadosMutados

19 ACC Selección PadresCruzadosMutados

20 Programa

21 Conclusiones Imagen original

22 Conclusiones Imagen VQ con codebook de 256 elementos y k-dimension = 4

23 Conclusiones Imagen VQ con codebook de 256 elementos y k-dimension = 9

24 Conclusiones Imagen VQ con codebook de 512 elementos y k-dimension = 4

25 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

26 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 http://www.geocities.com/mohamedqasem/vectorquantization/vq.html Developer’s Image Library (DevIL). D. Woods. http://www.imagelib.org http://www.imagelib.org