Compresión de Imágenes Digitales Aplicación de Algoritmos Genéticos en VQ

Trabajo de la Asignatura Procesamiento de Imágenes Digitales Departamento de Matemática Aplicada I Universidad de Sevilla. Curso 2002/2003

Manuel Blanco Guisado, David Martínez González, Raúl Palomino Sánchez

Índice

1. Introducción...............................................................................................................2 2. Objetivos....................................................................................................................3 3. Cuantización Vectorial ..............................................................................................4 3.1. Fundamentos de la Cuantización Vectorial.........................................................4 3.1.1. Cuantización Vectorial con tamaño de bloque variable ...............................5 3.1.2. Cuantización Vectorial con tamaño de bloque fijo ......................................6 3.2. Proceso de codificación VQ................................................................................7 3.3. Generación de codebooks ...................................................................................7 3.3.1. Tamaño del codebook ..................................................................................8 3.3.2. Dimensión del codebook..............................................................................8 3.3.3. Número de codebooks..................................................................................8 3.3.4. Algoritmo de generación del codebook .......................................................9 3.4. Evaluación del resultado ...................................................................................10 4. Algoritmos Genéticos ..............................................................................................12 4.1 Introducción.......................................................................................................12 4.2 Algoritmo empleado ..........................................................................................13 4.2.1 Representación............................................................................................13 4.2.2 Fitness .........................................................................................................13 4.2.3 Cruce...........................................................................................................14 4.2.4 Mutación .....................................................................................................14 4.2.5 Selección.....................................................................................................14 5. Implementación .......................................................................................................16 5.1. Descripción de las clases implementadas .........................................................16 5.2. Ejemplos de uso ................................................................................................19 5.3. Propuestas de ampliación..................................................................................20 6. Resultados................................................................................................................27 7. Componentes ...........................................................................................................30 8. Referencias ..............................................................................................................31 Anexos .........................................................................................................................32 Anexo I. Algoritmos de codificación VQ ................................................................32 Anexo II. Algoritmos de generación de codebooks .................................................33 Anexo III. Código fuente de VQ_Gen .....................................................................34

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 2

1. Introducción En el campo de la informática, la reducción del tamaño de la información ha sido uno de los principales objetivos sobre el cual se han aplicado grandes estudios y donde se han logrado grandes avances. En la actualidad existen multitud de algoritmos y aplicaciones que consiguen grandes resultados en compresión de imágenes digitales, audio, vídeo, archivos,… manteniendo la información contenida en ellos. Desde hace algunos años la implantación de productos multimedia en muchos aspectos de la sociedad es un hecho real que es necesario controlar desde el punto de vista del almacenamiento. A pesar de los recursos con los que se cuenta en la actualidad, muy superiores a los de hace tan sólo unos cuantos años, las enormes bases de datos con las que se trabaja hoy en día o, incluso, los soportes de almacenamiento estándar con los que se cuentan no podrían afrontar el problema planteado por las aplicaciones multimedia si no se contara con métodos para reducir el tamaño de esa información. Afortunadamente, archivos de imágenes, sonido y vídeo (así como muchos otros) son comprimidos con éxito en la actualidad y ofertan resultados sorprendentes. Sin embargo, en este punto es necesario reflexionar sobre dichos resultados. En este tipo de aplicaciones el factor que indica el grado de bondad de un proceso de compresión es el humano. Así, existen dos grandes ramas de estudio en este aspecto: compresión con y sin pérdida de información. Sin embargo, este punto vuelve a ser objeto de discusión y abre nuevas posibilidades de estudio. Es decir, ¿qué significa pérdida de información? Desde el punto de vista computacional perder información es la incapacidad del algoritmo de recomponer el producto original a partir de otro al que se le ha aplicado el proceso de compresión. Sin embargo, desde un punto de vista algo más práctico, se ha podido demostrar que aun sacrificando parte de la información original es posible comprimir la misma sin que el ser humano pueda apreciar los cambios, logrando así mejores factores de compresión (menos información). El aspecto tratado en el último párrafo queda fielmente reflejado en técnicas de compresión muy extendidas en la actualidad como MPEG o JPEG, que permiten incluso reducir considerablemente el tamaño de los archivos aun sacrificando en gran parte la información, algo que resulta útil para ciertas aplicaciones. En este documento se presenta un estudio dedicado a la compresión de imágenes digitales con pérdida de información.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 3

2. Objetivos En este documento se presenta un estudio novedoso en el campo de compresión de imágenes digitales. El objetivo será dar a conocer al lector las diferentes técnicas empleadas así como dar una visión más práctica a través de una aplicación software desarrollada a tal efecto. Este estudio estará basado en una técnica denominada cuantización vectorial, de la cual se ofrece una introducción en el capítulo siguiente. Esta técnica no está muy desarrollada en la actualidad. Aunque goza de buenos fundamentos teóricos, una implementación eficiente de la misma es muy difícil de llevar a cabo. Este documento propone el uso de un algoritmo genético para su resolución. En los siguientes puntos del documento se presentarán las dos técnicas descritas en el párrafo anterior y la aplicación de las mismas en este estudio, así como su implementación software.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 4

3. Cuantización Vectorial Vector Quantization (en adelante VQ) o cuantización vectorial es una técnica utilizada en compresión multimedia, que puede ser utilizada para tratar imágenes 2D y 3D, audio, vídeo, texturas, etc. Esta técnica es bien conocida en el mundo tecnológico actual, sin embargo plantea problemas de eficiencia que le han impedido instaurarse como estándar. Con VQ se logran grandes ratios de compresión1 y por este motivo, a pesar de los problemas que serán descritos a continuación, su estudio resulta una tarea muy interesante.

3.1. Fundamentos de la Cuantización Vectorial Toda imagen digital puede representarse como una matriz de N x M píxeles2. Dicha matriz puede dividirse en bloques de tamaño fijo o variable (según la aplicación). La técnica de cuantización vectorial permite asignar a cada bloque de la imagen un representante dentro de un diccionario de bloques previamente construido. De esta manera se logra de manera efectiva comprimir la información contenida dentro del archivo de imagen, sustituyendo bloques completos de píxeles por referencias al representante más significativo del mismo dentro un conjunto de bloques disponibles en un diccionario.

1 2

Relación de tamaño entre la imagen original y la imagen comprimida Punto de una imagen que representa su nivel de gris

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 5

El siguiente gráfico muestra el proceso descrito anteriormente:

Figura 1. Proceso General de VQ

En el siguiente punto se muestra una descripción de las diferentes variantes de la cuantización vectorial en función del tamaño de los bloques que se codifican.

3.1.1. Cuantización Vectorial con tamaño de bloque variable Esta técnica se basa en la división de la imagen original en bloques de tamaño variable en función de la similitud del nivel de gris de los puntos que los componen. De esta manera, la codificación de la imagen necesitará, por lo general, un codebook no demasiado grande, con lo que la ejecución de la misma será más rápida. Sin embargo esta técnica plantea problemas de implementación derivados de la variedad de tipos de individuos del codebook (codewords). En definitiva, los codebooks no podrán ser reutilizados para diferentes imágenes. Esta situación, especialmente problemática, será tratada en posteriores puntos, donde se planteará la dificultad y el coste que supone generar un codebook eficiente. Además, el uso de esta técnica introduce un nuevo problema que aumenta el coste computacional en la codificación de imágenes. La elección del tamaño de los bloques requiere una búsqueda intensiva dentro de los puntos de la imagen y que debería ser analizada convenientemente para llegar a una solución rápida y eficiente. A pesar de lo expuesto en párrafos anteriores no se puede dejar de un lado este modo de planificar la compresión mediante cuantización vectorial dado que en algunas aplicaciones puede resultar interesante su uso. Sin embargo, este estudio está basado en la técnica que se expone a continuación.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 6

3.1.2. Cuantización Vectorial con tamaño de bloque fijo Un tamaño de bloque fijo permite la construcción de codebooks caracterizados por el tamaño y, por tanto, reutilizables para imágenes que hayan sido codificadas con dichas características. Una imagen N x M puede ser dividida en bloques de tamaño n x n. Dicho tamaño se denomina k-dimensión, siendo k = n x n. Esta división de las imágenes plantea un primer problema, dado que las imágenes con las que luego se va a trabajar difícilmente contendrán un número entero de bloques n x n. En este estudio se ha optado por utilizar la solución más sencilla y descartar aquellos píxeles que no formen un bloque completo, dado que dicho problema queda fuera de los objetivos de este documento. Sin embargo, esta situación propone un nuevo caso de estudio dentro de la cuantización vectorial basada en bloques de tamaño fijo. El proceso de cuantización vectorial aplicado a imágenes digitales tiene como objetivo la compresión de las mismas. En este punto es interesante analizar la influencia del codebook en el tamaño final de los archivos comprimidos. En principio, existen dos maneras de almacenar el codebook. Si la portabilidad es esencial en los archivos generados será necesario almacenar la imagen junto con el codebook utilizado para generarla. La aplicación construida para consolidar las nociones expuestas en este documento utiliza esta técnica. Por otro lado, un mejor ratio de compresión puede lograrse si en lugar de almacenar la imagen junto con su codebook, se guardara simplemente un identificador del mismo. Esto plantea el problema de no poder decodificar las imágenes con el mismo codebook con el que se generaron si no se realizan ambos procesos en el mismo sistema. Sin embargo, esta solución puede resultar de gran interés en aplicaciones como bases de datos. Una base de datos que almacene imágenes que contengan rostros de personas (fotografías de carnet) es un ejemplo claro de lo expuesto en el párrafo anterior. En los siguientes puntos se tratará en profundidad la generación de codebooks, pero como adelanto para el ejemplo, si se logra construir un codebook adecuado para el tipo de imágenes de la base de datos, éste se podría almacenar de manera independiente liberando la carga que supondría guardarlo junto con las imágenes, reduciendo así considerablemente el tamaño de las imágenes y, por consiguiente, el tamaño total de la base de datos. Análogamente, este proceso podría repetirse para otros modelos de imágenes y así disponer de un conjunto de codebooks, cada uno adecuado para cada tipo de imagen, que permitirían reducir el tamaño de la base de datos. En la actualidad no se dispone de ningún formato de archivo estándar para compresión con cuantización vectorial, por ese motivo se ha decidido almacenar el codebook junto con las imágenes comprimidas para este estudio, de manera que las mismas puedan ser codificadas y decodificadas para su chequeo en diferentes sistemas.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 7

3.2. Proceso de codificación VQ La codificación de una imagen mediante la técnica de cuantización vectorial se reduce a un proceso de búsqueda dentro de los elementos del codebook seleccionado. Este proceso resulta bastante complejo y deriva en serios problemas de rapidez. Se han realizado muchos algoritmos para solucionar este problema, bien reduciendo los cálculos matemáticos o bien realizando un preprocesado al codebook con el que se va a trabajar. En el anexo I se incluye una lista de referencias a dichos algoritmos. Dentro de este campo el algoritmo más sencillo se basa en realizar una búsqueda completa dentro del codebook del elemento (codeword) más similar al bloque de la imagen con el que se trata en cada momento. Esto requiere realizar un recorrido completo del codebook por cada uno de los bloques de la imagen y redunda en un tiempo de ejecución elevado. Por razones de simplicidad este estudio hace uso del algoritmo descrito en el párrafo anterior en la aplicación construida, para el cual utiliza la siguiente función en el cálculo del codeword más apropiado para cada bloque: M

K

∑∑ ( x − c ) j

ij

2

i =1 j =1

donde M representa el número total de codewords, K la dimensión del bloque (n x n), x un bloque de la imagen y c el codebook. El codeword elegido para un determinado bloque será aquel que minimice el valor obtenido con la función anterior. Una vez elegido el representante apropiado para cada bloque, ésta será la información a almacenar en el fichero resultante, con lo que la compresión de datos queda realizada. El resultado final de la compresión dependerá en gran medida de la similitud entre los bloques de la imagen y los del codebook, por lo que la elección del mismo resulta fundamental. En este documento se propone un algoritmo para realizar un codebook global (es decir, para multitud de imágenes), sin embargo, para obtener buenos resultados es necesario tener en cuenta el grado de similitud del conjunto de entrenamiento usado para generar el codebook y las imágenes que serán codificadas con el mismo. Este último aspecto es el mayor reto de la cuantización vectorial, el cual no ha podido ser resuelto de manera general, aunque para aplicaciones locales (imágenes con rasgos similares) los ratios de compresión que se obtienen mejoran a los de otras técnicas estándar con una mínima pérdida de información. Esta problemática es tratada en el siguiente punto de este documento.

3.3. Generación de codebooks El proceso general de compresión con la técnica de cuantización vectorial consta de una base teórica sencilla que, sin embargo, plantea serios problemas de implementación. Como ya se ha visto, la división de las imágenes en bloques es un método no homogéneo, dado

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 8

que no todos los píxeles de una imagen podrán ser agrupados. Sin embargo, el principal problema de la cuantización vectorial es la generación de codebooks apropiados para cada aplicación. Este problema puede dividirse en varios aspectos como son el tamaño, dimensión, número y algoritmo de generación del codebook.

3.3.1. Tamaño del codebook El tamaño del codebook utilizado en la codificación influirá en la relación calidad/coste de la misma. Es decir, un codebook grande ofrecerá, por lo general, mejores resultados visuales de la imagen sin embargo también aumentará el tiempo de procesado de la misma. En este punto es importante elegir un tamaño adecuado que se adapte a las dos necesidades, sin embargo no existe ningún método para su cálculo a priori y su elección será fruto de la experimentación.

3.3.2. Dimensión del codebook Este parámetro, definido en este documento como k-dimensión, tendrá influencias similares al anterior en el resultado final del proceso de cuantización vectorial. Sin embargo, su relevancia es mayor dado que influye de manera determinante sobre el proceso de generación del codebook y, en menor medida, en la codificación de las imágenes. Desde el punto de vista de la calidad de la imagen y su codificación, una kdimensión pequeña proporcionará, generalmente, mejores resultados visuales, aunque menores ratios de compresión. Análogamente, un valor alto de k reducirá la calidad de la imagen, pero también su tamaño. Sin embargo, el valor de k tiene serias consecuencias en el algoritmo de generación del codebook. Un valor elevado aumentará la complejidad del proceso de generación del codebook, un proceso ya complicado de por sí. Así la combinación de los parámetros de tamaño y dimensión del codebook se convertirá en un factor fundamental en la eficiencia del algoritmo y, por lo tanto, la elección de ambos debe ser precisa y, para ello, la mejor herramienta de la que se dispone es la experiencia basada en conjuntos de prueba.

3.3.3. Número de codebooks Como se ha visto, la elección del codebook apropiado resulta fundamental a la hora de obtener resultados óptimos en la codificación. En este documento se estudia un algoritmo cuyo objetivo es lograr un codebook fiable para multitud de imágenes. Desde el punto de vista del parámetro analizado en este punto, el número de codebooks para la aplicación sería 1. Este valor resulta interesante para reducir la complejidad computacional, es decir, para este caso sólo es necesario calcular el codebook en una sola ocasión. Por otro lado, la generación de múltiples codebooks hace más flexible la codificación de las imágenes y permitiría reducir la carga en el algoritmo de generación de code-

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 9

books. En un caso extremo, si se lograra un método eficiente y rápido de construcción de codebooks con buenos resultados a nivel local una solución a la codificación de la cuantización vectorial permitiría asociar a cada imagen su propio y único codebook. Esto obligaría a almacenar cada codebook en el mismo fichero junto con la imagen. Sin embargo, teniendo en cuenta que la generación del codebook es el proceso más costoso en VQ, la solución planteada en el párrafo anterior resulta todavía más complicada que la basada en un único codebook. Así, se propone el uso de unos cuantos codebooks asignables a imágenes dividas en diferentes categorías clasificadas, por ejemplo, por la escala de grises de las mismas. Estos codebooks se calcularían en un principio para que la aplicación que haga uso de la cuantización vectorial pueda seleccionarlos en función de las imágenes objetivo a ser codificadas.

3.3.4. Algoritmo de generación del codebook Junto con el proceso de codificación, la generación de codebooks plantea un grave problema computacional que ha sido fruto de numerosas líneas de investigación. Cualquier algoritmo dedicado a construir codebooks toma como parámetros un conjunto de entrenamiento y el valor de k-dimensión. En otros casos es necesario aportar el tamaño final del codebook. En el anexo II se incluyen referencias a algunos de estos algoritmos. Para comprender el funcionamiento de este tipo de algoritmos, a continuación se mostrará el proceso seguido en LBG (Linde-Buzo-Gray), el algoritmo más conocido en este tipo de aplicaciones. En el siguiente capítulo de este documento se describe el algoritmo implementado para este estudio.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 10

LBG debe su nombre a los autores de dicho algoritmo. Los siguientes puntos ofrecen una breve descripción de su funcionamiento: 1. 2.

3.

Determinar el número de elementos del codebook (codewords), es decir, su tamaño: N Realizar una selección aleatoria de N bloques del conjunto de entrenamiento, que servirán como codebook inicial. En este punto se pueden emplear un o más imágenes diferentes. Aproximar los vectores de entrenamiento para cada codeword usando la distancia euclídea. Este paso se lleva a cabo tomando cada bloque de entrada y calculando la distancia euclídea para cada uno de los elementos del codebook. Un bloque será asignado al codeword cuya distancia euclídea sea la menor: k

∑ (x − y ) i

ij

2

j =1

4.

Recalcular el codebook, para lo cual se tiene en cuenta el número de bloques que han sido asignados a un determinado codeword. La siguiente función realiza el cálculo, siendo m el número de bloques asignados a un codebook:

1 m ∑ xij m j =1 5.

Repetir los pasos 2 y 3 hasta que no haya cambios en el codebook o que éstos sean insignificantes

LBG es uno de los algoritmos más sencillos utilizados para esta aplicación y, a pesar de obtener buenos resultados localmente, el coste computacional que supone no recomienda su uso en aplicaciones prácticas.

Figura 2. Asignación de bloques a codewords

3.4.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 11

Evaluación del resultado Una vez obtenido el resultado procedente del proceso de codificación, es necesario disponer de una medida del grado de bondad del mismo. Para ello se empleará la relación señalruido (SNR) entre los valores de la imagen original y los de la imagen codificada, según la siguiente fórmula: N

SNR =

M

∑∑ x N

i =1 j =1 M

∑∑ ( x

ij

2

ij

− yij ) 2

i =1 j =1

donde x representa a la imagen original, y a la imagen comprimida, y N x M el tamaño de ambas. Una vez definida esta medida se podrán obtener valores fiables para realizar la comparación de la calidad de diferentes métodos de compresión.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 12

4. Algoritmos Genéticos 4.1 Introducción Se denomina Computación Evolutiva a un amplio conjunto de técnicas de resolución de problemas complejos basados en la emulación de los procesos naturales de la evolución. La principal aportación de la Computación Evolutiva a la metodología de resolución de problemas consiste en el uso de mecanismos de selección de soluciones potenciales y de construcción de nuevos candidatos por recombinación de características de otros ya presentes, de modo parecido a como ocurre en la evolución de los seres vivos. Esta evolución se realiza hasta que se cumpla algún criterio de parada previamente establecido, que puede ser un número determinado de iteraciones u otro criterio. Begin Algoritmo P[0]=PoblacionInicial(); FitP[0]=Evaluar(P[0]); t=0; Mientras no(CondicionDeParada) Q[t]=SeleccionarPadres(P[t]); Q[t]=Reproducir(Q[t]); FitQ[t]=Evaluar(Q[t]); P[t]=Seleccionar(P[t],Q[t],FitP[t],FitQ[t]); FitP[t]=Evaluar(P[t]); FinMientras End Algoritmo Estructura general de un Algoritmo Evolutivo

Los Algoritmos Genéticos son uno de los paradigmas surgidos en el seno de la Computación Evolutiva. Se caracterizan por aplicar a una población de posibles soluciones al problema una serie de operadores de selección determinista y de cruce principalmente, y mutación en menor medida. Tradicionalmente se ha implementado una representación binaria de los individuos, aunque también se aplica representación real.

Los elementos clave de un Algoritmo Genético son:

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 13

Representación: Cada individuo es una estructura de datos que representa una posible solución al problema. Esta representación se realizaba en principio mediante un vector de bits, sin embargo, en la actualidad se suele utilizar una representación mediante vectores (llamados cromosomas) de valores reales. El conjunto de los individuos se denomina población. Fitness: Es una medida de la capacidad de un individuo para solucionar el problema, permite comparar la bondad de diferentes individuos. Reproducción: Es una transformación aplicada a los individuos de la población actual para generar otros individuos parecidos, candidatos a formar parte de la siguiente población. Existen dos tipos de reproducción: - Cruce: Se basa en la recombinación de la información de dos o más individuos para generar uno o más nuevos individuos. - Mutación: Se basa en la modificación de la información de un individuo para generar un nuevo individuo diferente. Selección: De los individuos de la población actual y los generados mediante reproducción se escogen los mejores (en base a su Fitness) para pasar a formar parte de la siguiente generación.

4.2 Algoritmo empleado 4.2.1 Representación Cada individuo de la población representa un codeword de n x n píxeles. Por simplicidad, en lugar de implementarse mediante una matriz de píxeles se ha implementado como un vector de tamaño k de bytes (que permiten 256 niveles de gris), siendo k = n x n. De acuerdo con la tendencia actual de programación de Algoritmos Evolutivos, cada individuo contiene su propia información de Fitness, en lugar de implementarse en un vector de fitness independiente. La población se representa mediante un vector de C individuos. Tanto k como C son parámetros ajustables por el usuario.

4.2.2 Fitness El fitness de cada individuo se calcula como el error cuadrático entre los píxeles del individuo y los píxeles de los bloques de la imagen para los cuales, el individuo es el más aproximado. M

Fitness =

K

∑∑ ( x − c ) j

ij

2

i =1 j =1

siendo M el número de bloques examinados y k el número de píxeles de cada bloque. Xij representa el valor del pixel j-ésimo del bloque i-ésimo de la imagen original, y Cj representa el pixel j-ésimo del individuo evaluado.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 14

4.2.3 Cruce Se ha aplicado un cruce de aridad 1,1 (de un padre se genera un hijo) basado en los genes movibles. Los genes movibles fueron descubiertos en 1940 por B. McCintock, ganador de un premio Nobel de biomedicina en 1983, en los Laboratorios de Cold Spring Harbor, EEUU. Son genes que tienen la capacidad de “saltar” de un cromosoma a otro y acoplarse en su interior, provocando de este modo potentes mutaciones en los seres vivos. El cruce de genes movibles se ha definido para Algoritmos Genéticos de codificación binaria del modo siguiente: Se definen dos genes, I-gen y D-gen, formados exclusivamente por unos y exclusivamente por ceros respectivamente, de un tamaño “a” determinado, generalmente 1 o 2. Para cada cromosoma a cruzar se escoge aleatoriamente I o D y se inserta el gen correspondiente siguiendo la siguiente regla: Los I-genes se deben insertar en la a-ésima posición a partir del primer cero (empezando por el bit menos significativo). Los D-genes se deben insertar en la a-ésima posición a partir del primer uno (empezando por el bit menos significativo). Los bits a la derecha de la inserción se desplazan hacia la derecha para dejar sitio al nuevo gen. Por ejemplo, supongamos el cromosoma 01001001 tras insertar un cromosoma I con a=2 quedaría 010001110 (01) Si insertamos un cromosoma D con a=2 quedaría 010001000 (01) En el algoritmo genético planteado en este estudio, se aplica el cruce a los píxeles cuyo fitness es peor que la media del individuo, tomando cada pixel (un unsigned char) como una cadena de 8 bits útiles.

4.2.4 Mutación La mutación se aplica sobre uno de los pixeles del individuo a mutar, eligiendo al azar un píxel del individuo, y dentro de este píxel, un bit concreto, y cambiando su valor.

4.2.5 Selección Tradicionalmente, los Algoritmos Genéticos se han utilizado para buscar al mejor individuo posible, que será el individuo de mejor fitness de la población final. En nuestro problema, cada individuo es un codeword, y la solución al problema es el conjunto de codewords que PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 15

forman el codebook. Por ello no se pueden aplicar los criterios tradicionales de selección, que se basan exclusivamente en el fitness. En el algoritmo implementado, se comienza la población inicial con un conjunto de codewords generados a partir de un histograma de la imagen, y se realizan n iteraciones. En cada iteración, para cada individuo de la población se generan un hijo procedente del cruce y otro hijo procedente de la mutación. Para cada terna de padre, hijo cruzado e hijo mutado, se elige al mejor de los tres y ése pasará a formar parte de la siguiente generación. De este modo se evita que un individuo particularmente bueno propague copias suyas por la población y el resultado final sea un conjunto de individuos con fitness muy bueno, pero que son similares entre sí y no sirven para sustituir a todos los bloques de la imagen original.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 16

5. Implementación Los aspectos tratados en este documento han sido implementados en un PC, con el lenguaje de programación C++. A continuación se detalla dicha implementación. Para el manejo de ficheros gráficos estándar se ha hecho uso de la librería gratuita DevIL (más información en el capítulo 8).

5.1. Descripción de las clases implementadas La construcción de la aplicación se basa en dos clases fundamentales: VQ_Codebook y VQ_Image. En el anexo III se ofrece un listado del código fuente de las mismas.

Clase VQ_Codebook La clase VQ_Codebook contiene toda la funcionalidad necesaria para un codebook. Almacena información referente a la k-dimensión, la longitud y los datos del codebook. Las siguientes funciones son realmente las únicas que un desarrollador que haga uso de esta clase debe usar:

VQ_Codebook::SetKDimension Antes de construir un nuevo codebook es necesario establecer su k-dimensión. Esta función proporciona la mejor manera de hacerlo, ya que hay que tener en cuenta que el número de filas y columnas de un bloque debe ser el mismo, es decir, que la raíz cuadrada de k-dimensión debe ser entera VQ_Codebook::MakeCodebook Esta función realiza el proceso de generación del codebook, bien con la función por defecto basada en un algoritmo genético o bien con otra definida por el usuario. Para poder llamar a esta función debe haberse establecido previamente la k-dimensión y el codebook no debe estar construido, es decir, solamente se puede llamar a esta función una vez por cada instancia de la clase VQ_Codebook::GetKDimensión Devuelve la k-dimensión actual del codebook

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 17

VQ_Codebook::GetNumberOfRows Devuelve la longitud del codebook, es decir el número de codewords que contiene Las restantes están orientadas para uso interno dentro de la aplicación: VQ_Codebook::Función LoadCodebook

GetCodebookIndex WriteCodebook

Descripción Carga un codebook desde el disco. Toma como parámetro de entrada un objeto ifstream, por lo que puede usarse para cargar un codebook desde el disco siempre y cuando se abra el fichero previamente Devuelve un puntero al comienzo de los datos del codebook Escribe el codebook en el disco. Toma como parámetro de entrada un objeto ofstream, por lo que puede usarse para salvar un codebook en el disco siempre y cuando se abra el fichero previamente

Clase VQ_Image La clase VQ_Image almacena los datos correspondientes a las imágenes y sus correspondientes codebooks.

VQ_Image::LoadImage Carga un fichero con formato VQ desde el disco, con su correspondiente codebook, tal y como se ha definido el almacenamiento del mismo en este documento VQ_Image::DecodeImage Escribe en el disco una imagen BMP con el resultado de la codificación de la imagen comprimida con VQ. Con este método se pueden comprobar los resultados visuales de la codificación, dado que no se ha definido ninguna manera de visualizar directamente una imagen con formato VQ VQ_Image::SetCodebook Asigna a una imagen VQ (sin construir) un codebook existente. El procedimiento general será llamar a las funciones SetKDimension y MakeCodebook de una instancia de VQ_Codebook y, a continuación, llamar a este método para hacer efectiva la asignación del codebook construido a la imagen actual. Si la imagen VQ ya está construida, una llamada a este método dará un error

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 18

VQ_Image::MakeImage Toma como entrada una imagen BMP y construye su correspondiente imagen VQ. Como precondición se exige que exista un codebook asignado a la imagen y que ésta no haya sido construida previamente. Este método se encarga de actualizar el número de bandas de la imagen, proporcionando así una manera de comprobar si una imagen ha sido construida correctamente VQ_Image::WriteImage Escribe en el disco una imagen con formato VQ, con la condición de que la misma y su codebook estén construidos VQ_Image::GetNumberOfBands Devuelve el número de bandas de la imagen VQ. Si tras llamar a MakeImage ocurre algún error, está función devolvería 0

El resto de clases que componen la aplicación están reservadas para uso interno y definen las estructuras de datos con las que se trabaja. En el anexo III se incluye el código fuente de la aplicación, donde se pueden encontrar los detalles específicos de implementación de cada uno de los métodos descritos. El algoritmo de codificación de una imagen VQ está definido en el fichero “VQ_Default.h”; su nombre es DefaultVQImageEncodingAlgorithm y refleja los conceptos descritos en el punto 3.2 de este documento.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 19

5.2. Ejemplos de uso Creación de un codebook El procedimiento general de creación de un codebook se define con las siguientes sentencias C++: // Declaración VQ_Codebook codebook; // Define la k-dimensión del codebook que se va a crear // Sus valores más habituales son 4 y 9 codebook.SetKDimension(K_DIMENSION); // Generación del codebook con el algoritmo por defecto descrito en este documento // IMAGEN_BMP es el nombre del fichero de entrenamiento para la generación del codebook // LONGITUD es el tamaño en filas del codebook ( de 1 a 65536 ) // Los otros dos parámetros son específicos del algoritmo genético // El valor de A varía entre 1 y 4; su valor más habitual es 2 codebook.MakeCodebook(IMAGEN_BMP,LONGITUD-1,NUMERO_DE_GENERACIONES,A);

Cargar un codebook desde el disco // Declaraciones VQ_Codebook codebook; ifstream ficheroCodebook (CODEBOOK_FILENAME, ios::in|ios::binary); codebook.LoadCodebook(ficheroCodebook);

Salvar un codebook en el disco // Declaraciones VQ_Codebook codebook; ofstream ficheroCodebook (CODEBOOK_FILENAME,ios::trunc|ios::binary); // Creación del codebook. Estas dos líneas pueden sustituirse por una llamada a LoadCodebook codebook.SetKDimension(K_DIMENSION); codebook.MakeCodebook(IMAGEN_BMP,LONGITUD-1,NUMERO_DE_GENERACIONES,A); codebook.WriteCodebook(ficheroCodebook);

Compresión de una imagen BMP // Declaraciones VQ_Codebook codebook; VQ_Image imagen; // Creación del codebook. Estas dos líneas pueden sustituirse por una llamada a LoadCodebook codebook.SetKDimension(K_DIMENSION); codebook.MakeCodebook(IMAGEN_BMP,LONGITUD-1,NUMERO_DE_GENERACIONES,A); // Establece el codebook a usar en la codificación imagen.SetCodebook(&codebook); // Procedimiento de compresion imagen.MakeImage(IMAGEN_BMP_A_COMPRIMIR); // Escritura del fichero VQ en disco imagen.WriteImage(IMAGEN_VQ);

Decodificación de una imagen VQ // Declaración VQ_Image imagen; // Carga una imagen VQ desde el disco imagen.LoadImage(IMAGEN_VQ); // Escritura del fichero BMP en disco imagen.DecodeImage(IMAGEN_BMP);

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 20

5.3. Propuestas de ampliación En este apartado se proponen unas líneas de mejora de la implementación descrita en el punto anterior. La generación del codebook es el proceso más costoso dentro del procedimiento general de la cuantización vectorial, sin embargo, es un factor que está suficientemente cubierto en la implementación propuesta con el uso de un algoritmo genético. Por otro lado, el tiempo empleado en la codificación de una imagen sí supone un problema serio, para el cual es necesario una solución más eficiente que la planteada en el punto 3.2 de este documento. En el anexo I se incluyen multitud de estudios relacionados con este problema. Como primera aproximación al mismo se planteará un algoritmo que reduce los tiempos de codificación de una imagen a través de algoritmo del apartado 3.2 entre 10 y 15 veces para valores de K-Dimensión de 4 y 9. Este algoritmo, cuyo código se incluye en este mismo apartado, consta de los siguientes pasos: • •

•

Calcular los valores de gris medios de cada elemento del codebook y almacenarlos en una matriz auxiliar Definir un umbral de nivel de gris sobre el que se realizarán las comparaciones entre los bloques de la imagen y del codebook. Por defecto, se toma un valor 10, lo que significa que un bloque solamente se comparará con aquellos elementos del codebook cuyo nivel de gris medio se sitúe en el intervalo [GRIS_MEDIO_DEL_BLOQUE - 10, GRIS_MEDIO_DEL_BLOQUE + 10] Localizar el elemento más parecido dentro del codebook para los valores del intervalo anterior. Si no existe ninguno, realizar una búsqueda completa dentro de todos los elementos del codebook

La implementación de este procedimiento no ha sido incluida dentro de la interfaz gráfica creada para facilitar el uso de las clases definidas anteriormente. Sin embargo, se han incluido los ficheros necesarios para que el lector pueda comprobar la funcionalidad de este algoritmo, así como para disponer de ejemplos de uso del código implementado y de base de conocimiento para la creación de nuevas funciones de codificación y generación de codebooks.

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 21

//--------------------------------------------------// // Proyecto VQ_Gen - optimized.h // // -------------------------------------------------// // Definición del parámetro de la función // optimizada de codificación de una imagen VQ // // Autor: Manuel Blanco (whitey(at)manuel-blanco.net) // Ultima modificacion: 18/01/2003 // //---------------------------------------------------#ifndef __VQ_OPTIMIZATIONS__ #define __VQ_OPTIMIZATIONS__ #include #include #define GRAY_SCALE_LIMIT 10 unsigned char OptimizedEncodingAlgorithm (char* fileName, VQ_Codebook* codebook, VQ_Matrix** matrix); #endif

//--------------------------------------------------// // Proyecto VQ_Gen - config.h // // -------------------------------------------------// // Parámetros para la compilación del fichero // de ejemplo para el uso de las funciones de // VQ_Gen desde la línea de comandos // // Autor: Manuel Blanco (whitey(at)manuel-blanco.net) // Ultima modificacion: 18/01/2003 // //---------------------------------------------------#ifndef __VQ_CONFIG__ #define __VQ_CONFIG__ typedef enum {STANDARD, ACC} CODEBOOK_GENERATION_ALGORITHM; typedef enum {DEFAULT, OPTIMIZED} IMAGE_ENCODING_ALGORITHM; #define #define #define #define

BMP_FILENAME "original.bmp" VQ_FILENAME "result.vq" BMP_TEST_IMAGE "test.bmp" CODEBOOK_TEST_IMAGE "codetest.bmp"

#define CODEBOOK_OUT_FILENAME "codebook.dic" #define CODEBOOK_IN_FILENAME "ccb-k4-g8-512.dic" #define IS_CODEBOOK_GENERATION_ENABLED false #define K_DIMENSION 9 #define IMAGE_ENCODER OPTIMIZED #define CODEBOOK_GENERATOR ACC #define NUMBER_OF_GENERATIONS 6 #define CODEBOOK_LENGTH 256 #define A 2 #endif

PID. Curso 02/03. Manuel Blanco Guisado. David Martínez González. Raúl Palomino Sánchez.

Compresión de Imágenes Digitales. Algoritmos Genéticos en VQ. 22

//--------------------------------------------------// // Proyecto VQ_Gen - optimized.cpp // // -------------------------------------------------// // Función optimizada de codificación de una imagen VQ // // Autor: Manuel Blanco (whitey(at)manuel-blanco.net) // Ultima modificacion: 18/01/2003 // //---------------------------------------------------#include "optimized.h" #include unsigned char OptimizedEncodingAlgorithm (char* fileName, VQ_Codebook* codebook, VQ_Matrix** matrix) { ILuint userImage; ILboolean errorCode; ILuint imageType; unsigned int numberOfRows, numberOfCols; unsigned int rowsToEncode, colsToEncode; unsigned char numberOfBands, b; unsigned int kDimension; unsigned int i,j,k1,k2,c; unsigned int rK; unsigned char** codebookIndex; unsigned char* pointer; unsigned char* block; VQ_MATRIX_TYPE minIndex; unsigned long acum, minF1; int meanGrayL, minGrayL, maxGrayL; VQ_Matrix* newMatrix; VQ_MATRIX_TYPE* codebookMap; assert(fileName != NULL); assert(codebook != NULL); assert(*matrix == NULL); // DevIL library initialization ilInit(); ilGenImages(1,&userImage); ilBindImage(userImage); // Loads a BMP image from disk errorCode = ilLoad(IL_BMP,fileName); if (errorCode != IL_COULD_NOT_OPEN_FILE) { imageType = ilGetInteger(IL_IMAGE_TYPE); codebookIndex = codebook->GetCodebookIndex(); kDimension = codebook->GetKDimension(); rK = (unsigned int)(sqrt(kDimension)); numberOfRows = ilGetInteger(IL_IMAGE_HEIGHT); numberOfCols = ilGetInteger(IL_IMAGE_WIDTH); numberOfBands = ilGetInteger(IL_IMAGE_BYTES_PER_PIXEL); switch (numberOfBands) { case 1: ilConvertImage(IL_LUMINANCE,IL_UNSIGNED_BYTE); break; case 3: ilConvertImage(IL_RGB,IL_UNSIGNED_BYTE); break; default: return 0; } newMatrix = new VQ_Matrix [numberOfBands]; // Initializes VQ_Image set of matrix for (b=0;b