Ingeniería Informática
Estructuras de Datos
Laboratorio
Curso 1998/99
Universitat de València

PRÁCTICA Nš 5: 1 sesión

(del 3 de Mayo al 7 de Mayo de 1999)

Arboles Binarios
Recodificación de Imágenes Digitales en Niveles de Gris

0.- Objetivos

El objetivo de esta práctica es la utilización de árboles binarios para la reducción de colores en imágenes digitales en niveles de gris.

1.- Definiciones previas

Imagen Digital: Una imagen digital es una matriz en donde cada elemento representa la intensidad de la luz en cada uno de los puntos de la escena. A cada uno de estos puntos se le llama pixel, y sus valores estarán comprendidos entre 0 (negro) y 63 (blanco).

Histograma: El histograma de una imagen es un vector que continene en cada uno de sus elementos el número de pixels cuya intensidad corresponde a la posición (nivel de gris) en el vector. Por ejemplo: Si en una imagen hay 312 pixels con intensidad 45 entonces histograma[45]=312.

2.- Unidad Para la manipulación de Imágenes (proporcionada por el profesor)

La unidad que se proporciona (Uni_Imag.tpu) es la de manipulación de imágenes.

Los tipos definidos en esta unidad son:

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;

Como se puede observar Imagen es una estructura compuesta por la información sobre los niveles de gris y el número de filas y de columnas de la imagen, es decir, su tamaño.

Los procedimientos que podremos utilizar sobre estos tipos serán::

Procedure Inicio_Graficos;
 Inicia el modo gráfico. 
Procedure Lee_Imagen ( fichero: String; Var Im: Imagen );
 Lee el fichero y almacena su contenido en la variable Im. 
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 linea 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.

3.- Tareas a realizar

En esta práctica se tienen que realizar básicamente dos tareas:

a. Unidad de manipulación de árboles binarios.

b. Programa de reducción de niveles de gris de una imagen en niveles de gris.

a. Unidad de Manipulación de árboles binarios.

La unidad que se debe realizar es la que represente el tipo arbol binario con las operaciones habituales sobre árboles binarios. Los tipos son:

Type
    Valor = Record
                inicio      : Integer;
                final       : Integer;
                color       : Grises;
                porcentaje  : Real;
            End;

   Arbol = ^Nodo;

   Nodo  = Record
               Info    : Valor;
               Izq,Der : Arbol;
           End;

Un nodo contiene cierta información sobre la porción del histograma que se está procesando (inicio y final), contiene información sobre el color con el que se representará toda esa banda del histograma (color), contiene el porcentaje de puntos con color predominante sobre el total de puntos de esa banda (porcentaje) y por supuesto dos punteros a cada uno de los hijos.

Las operaciones sobre los árboles serán, tal y como se vió en teoría:

Function Crear_Arbol: Arbol;
Function Vacio_Arbol ( arb: Arbol                ): Boolean;
Function Dato_Arbol  ( arb: Arbol; Var dat: Valor): Boolean;
Function Hijo_Izq    ( arb: Arbol; Var izq: Arbol): Boolean;
Function Hijo_Der    ( arb: Arbol; Var der: Arbol): Boolean;
Function Hacer_Arbol ( izq: Arbol; dat: Valor; der : Arbol): Arbol;

b. Programa de reducción de niveles de gris de una imagen en niveles de gris (programa principal).

El programa principal debe realizar secuencialmente las siguientes tareas:

1. Pedir el nombre del fichero con la imagen (nom_fich)
2. Pedir el umbral que representará el tanto por ciento del color predominante con el cual representaremos esa zona.
3. Iniciar el modo gráfico (Inicio_Graficos)
4. Leer la imagen (Lee_Imagen ( nom_fich; imagen ))
5. Mostrar la imagen (Muestra_Imagen ( imagen, 0 ))
6. Calcular el histograma (Calcula_Histograma ( imagen, hist ))
7. Mostrar el histograma (Muestra_Histograma ( hist ))
8. Construir el arbol.
9. Obtener la tabla de transformación.
10. Informar sobre los niveles con los que representamos la nueva imagen.
11. Obtener la nueva imagen.
12. Mostrar la nueva imagen (Muestra_Imagen ( imagen2, 150 ))
13. Finalizar el modo gráfico (Fin_Graficos)

Los puntos 8, 9, 10 y 11 los deberá realizar el alumno.

Construcción del árbol

Supongamos, por ejemplo, un umbral introducido por el usuario del 60%. En primer lugar consideramos todo el intervalo [0,MAX_GRISES]. Para el ejemplo mostrado en la figura, el valor máximo en ese intervalo es 2055 y el total de puntos es 21964, por lo que representa el 9,35% del total. Puesto que el valor calculado es menor que el umbral (60%), dividimos el intervalo en dos partes iguales, [0..MAX_GRISES div 2] y [MAX_GRISES div 2 + 1..MAX_GRISES], repitiendo el proceso para cada uno de estos subintervalos hasta que el porcentaje sea mayor que el umbral.

Cada nodo del árbol representa cada uno de estos intervalos y sus hijos representan las subdivisiones realizadas, si éstas se hicieron.

Obtener la tabla de transformación

Una vez construido el árbol se crea una tabla de transformación de colores con la información de las hojas del árbol. Esta tabla nos dará la equivalencia entre los colores de la imagen original y los colores de la nueva imagen. Aplicando esta tabla a la imagen podremos obtener la nueva imagen con los colores reducidos.

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 sesión de prácticas correspondiente.
Última actualización: 28 de Abril de 1999