PRÁCTICA Nº 6: 2 sesiones
(del 10 de Mayo al 21 de Mayo de 1999)Aplicación de Arboles Binarios
a la Compresión de Imágenes Mediante la Utilización de los Códigos de Huffman
0.- Objetivos
El objetivo de esta práctica es la utilización de los códigos de Huffman para la compresión de imágenes.
1.- Los Códigos de Huffman
Supóngase que se tiene una imagen en distintos niveles de gris. En la imagen, los valores de los niveles de gris de cada pixel son independientes entre sí y aparecen con una determinada probabilidad conocida a priori (histograma). Se desea codificar cada valor de gris mediante una secuencia de ceros y unos, de manera que ningún código de un color sea prefijo del código de otro color. Esta propiedad de prefijos evitará cualquier tipo de ambigüedad en el proceso de decodificación de la imagen.
El problema de codificación que se plantea sería: dado un conjunto de colores, en nuestro caso supongamos desde 0 hasta MAX_GRISES, y sus probabilidades de aparición en una imagen (relacionado directamente con su histograma), encontrar un código para esos colores que cumpla la propiedad de prefijos y tal que la longitud media del código de un carácter sea mínima. La razón por la que se desea minimizar la longitud media de un código es que ello permitirá comprimir la longitud de la imagen codificada.
El algoritmo de Huffman permite encontrar un código con las propiedades especificadas. La idea del algoritmo consiste en llegar a formar un árbol binario que represente el código. En los nodos terminales (hojas) de este árbol se almacenarán los colores que se desea codificar junto con la probabilidad de aparición de cada uno de ellos, cumpliéndose que los colores más probables están más próximos a la raíz que los menos probables. De manera que el camino desde la raíz del árbol a cualquier hoja del mismo representará el código para el color de esa hoja, de acuerdo con el criterio de que los subárboles izquierdos se etiquetan con un 0 y los subárboles derechos lo hacen con un 1. Según este criterio, los colores con mayor probabilidad de aparición tendrán los códigos de menor longitud, mientras que los que tengan una probabilidad de aparición menor tendrán asociado un código de mayor longitud.
El algoritmo de Huffman consiste en lo siguiente:
Suponiendo conocida la probabilidad de aparición de un color en la imagen (sea pi) hacer:
1) Crear un bosque formado por tantos árboles independientes como colores se vayan a codificar. Cada color será la raíz de un árbol independiente, almacenándose junto a él su probabilidad de aparición.
2) Buscar en el bosque los dos árboles que presenten las menores probabilidades de aparición.
3) Agrupar los dos árboles encontrados en el paso 2) en un solo árbol que tenga como subárbol izquierdo el árbol que tenía menor valor pi asociado y como subárbol derecho el otro árbol. En la raíz de este nuevo árbol no se almacena ningún color, pero sí la probabilidad de aparición de los colores agrupados, que será la suma de sus dos probabilidades de aparición (pi + pj).
4) Repetir desde el paso 2) hasta que en el bosque sólo quede un árbol que agrupe a todos los colores.
2.- Realización de la práctica
En esta práctica trataremos de codificar y guardar en archivo, imágenes comprimidas mediante la utilización de la reducción de colores propuesta en la práctica anterior y la recodificación mediante la utilización de los códigos de Huffman, y después decodificaremos esas imágenes y las mostraremos por pantalla.
Programa principal
Codificación
Para codificar imágenes, habrá que realizar las siguientes tareas:
Tarea 1: Reducir el número de colores de la imagen (Práctica 5). Realizar una tabla de conversión de colores y determinar el histograma de la nueva imagen.
Tarea 2: Generar el código de Huffman a partir de la nueva tabla de frecuencias.
Esta tarea se realizará después de la tarea 1 y su esquema será:
1) Generar el árbol de Huffman según el algoritmo dado anteriormente, utilizando el histograma de la tarea 1 y sin considerar aquellos colores que no aparecen ninguna vez (frecuencia de aparición cero).
2) Recorrer el árbol para guardar, en forma de vector (Tabla_Conversion), el código que representa cada color, de manera que sea fácil consultarlo usando los colores como índices.
Tarea 3: Guardar en un fichero, con un formato adecuado, la siguiente información:
1) El árbol de códigos de Huffman. Se utilizará para ello una ligera variación de la notación empleada en otros casos: Se recorre en orden prefijo el árbol, escribiendo en el archivo la siguiente información:
(a) Si el nodo contiene un color, se guarda el color.
(b) Si el nodo NO contiene un color, se guarda un "sostenido" (#).
(c) Si el puntero apunta a NIL, se guarda un "." (Aunque este paso podría obviarse si consideramos que los nodos que contienen colores son terminales u hojas).
2) La información de la imagen:
(a) Número de filas y columnas de la imagen.
(b) Información codificada de la imagen.
2) Para cada pixel del fichero original hacer:
2.1) Buscar en el vector de transformación la cadena de
2.2) Almacenar en el fichero binario la secuencia de
0 y 1 determinada en el paso anterior.En esta fase habrá que estimar cuanto ocuparía el fichero binario si cada 0 y 1 escrito en él fuese un bit, en vez de un color. ¿Se conseguiría comprimir el fichero original? ¿Y si consideramos lo que ocupa la cabecera con el árbol de códigos?
Es conveniente, una vez realizada la codificación, liberar el espacio reservado para el árbol, y que ya no vamos a utilizar en el programa.
Decodificación
Tarea 4: Decodificar un fichero de ceros y unos para obtener la imagen correspondiente, a partir del código de Huffman que tiene almacenado.
El esquema de la rutina será el siguiente:
1) Leer y reconstruir en memoria el árbol de códigos.
2) Leer la imagen del fichero comprimido:
(a) Leer del fichero el número de filas y columnas de la imagen.
(b) Leer carácter a carácter el fichero "binario" y recorrer el árbol simultáneamente. Si se encuentra en el árbol el código de un color, escribir ese color en la parte de información de la imagen.
Los procesos de Codificación y Decodificación se englobarán en un mismo programa que permita ejecutar la tarea deseada. Se deja a criterio del alumno la conveniencia de realizar un diseño del programa en forma de módulos independientes, utilizando Unidades o ficheros Include.
Unidades para la manipulación de árboles
Para la manipulación de los árboles se utilizarán dos unidades distintas que trabajarán con los dos tipos distintos de árboles con los que trataremos en esta práctica.
La primera unidad será la misma que se utilizó en la práctica anterior.
La segunda unidad será similar a la primera, pero cambiaremos los tipos de la información contenida en los nodos y los nombre de las funciones a utilizar. Para unificar criterios, vamos a establecer la forma de los tipos de datos y los nombres de las funciones fundamentales para la realización de la segunda unidad de la práctica:
{* Definición de la matriz que almacenará el código generado por el método de Huffman *}
Tabla_Codigos = Array [ Grises ] Of String;
{ Las cadenas contendrán solo ‘0’s o ‘1’s }{* Definición del tipo árbol *}
{* Un nodo del árbol constará de la siguiente información:
Frec : Indica la frecuencia de aparición de los caracteres que forman el árbol del cual
el nodo es raíz.
Simbolo : Indica si el nodo almacena un color o está formado por la agrupación de colores.
Sólo los nodos terminales tendrán este campo puesto a
TRUE. En ese caso, sedefine un campo más, Info que almacena el color.
*}
ValorHuf= Record
Frec : Integer;
Case Simbolo: Boolean of
TRUE : (info: char);
FALSE: ();
end;
end;
ArbolHuf= ^NodoHuf;
NodoHuf= Record
Dato : Valor;
Izq , Der : Arbol;
End;
{* Un bosque será una agrupación de árboles, tantos como posibles colores tengamos *}
Bosque = array [ Grises ] of ArbolHuf;
{* Tipos fichero que se utilizarán para manipular archivos de disco *}
Fichero = file of char;
{* No se utiliza
text porque sólo interesan los caracteres individualmente *}
Function Crear_Arbol_Huf: ArbolHuff;
Function Vacio_Arbol_Huf ( arb: ArbolHuff ): Boolean;
Function Dato_Arbol_Huf ( arb: ArbolHuff; Var dat: ValorHuff): Boolean;
Function Hijo_Izq_Huf ( arb: ArbolHuff; Var izq: ArbolHuff): Boolean;
Function Hijo_Der_Huf ( arb: ArbolHuff; Var der: ArbolHuff): Boolean;
Function Hacer_Arbol_Huf ( izq: ArbolHuff; dat: Valor; der : ArbolHuff): ArbolHuff;
3.- Unidad de Manipulación de Imágenes
La unidad que se proporciona es la misma que en la práctica anterior, Uni_Imag:
Const MAX_GRISES;Type
Grises = 0 .. MAX_GRISES;
Imagen = Record Info : Array[1..100,1..100] of Grises; Filas : Integer; Columnas : Integer; End;
Histograma = Array[ Grises ] of Integer;
Procedure Inicio_Graficos;
Inicia el modo gráfico.
Procedure Lee_Imagen ( fichero: String; Var imag: Imagen );
Lee el fichero y almacena su contenido en la variable imag.
Procedure Muestra_Imagen ( imag: Imagen; pos: Integer );
Muestra la imagen en la columna pos.
pos = 0
para la imagen original. / pos = 150 para la imagen transformada.Procedure Calcula_Histograma ( imag: Imagen; Var hist: Histograma );
Calcula el histograma de la imagen.
Procedure Muestra_Histograma ( hist: Histograma );
Muestra el histograma en la pantalla.
Procedure Muestra_Division ( x: Integer );
Muestra una línea vertical en el eje x del histograma.
Procedure Muestra_Cadena ( cad: String );
Muestra una cadena por pantalla.
Procedure Fin_Graficos;
Cierra el modo gráfico.
4.- Entrega de Programas
Al finalizar la práctica correspondiente se entregarán al profesor al menos tres programas diferentes:
1) Programa principal de codificación y decodificación (Huffman.pas).
2) Unidad de árboles de la práctica 5 (Uni_Arbo.pas).
3) Unidad de árboles de Huffman (Uni_Huff.pas)
En caso de utilizar alguna unidad adicional para estructurar mejor el programa, se entregarán también estas unidades al profesor.
Nota Muy Importante
Antes de poder empezar a realizar cualquiera de las prácticas es necesario presentar al profesor un pequeño esquema de las tareas que va a realizar la práctica, explicando brevemente y en lenguaje natural como van a solucionarse los problemas que se plantean.
Una vez entregado al profesor el esquema se procederá a realizar la práctica, entregándose la práctica resuelta al profesor en el plazo previsto para ello, no pudiéndose prorrogar este plazo en ningún caso.
ENTREGA DE PROGRAMAS:
Al finalizar la segunda sesión de prácticas correspondiente.