jueves, 4 de agosto de 2011

Prácticas C++: compresión de imágenes mediante el código Huffman


Desarrolla un compresor/descompresor de imágenes BMP de 8 bits empleando programación orientada a objetos. Para ello, considera los siguientes puntos:
  • Investiga las funciones de ejemplo pasa_a_blanco_y_negro(TBMP &bmp) y pasa_a_nColores(TBMP &bmp, int n) de la librería imagenBMP.h que se te proporcionará en clase para comprender cómo manipular la matriz de colores de la fotografía de 8 bits. Asimismo, debes escudriñar bien todas las declaraciones del archivo de cabecera para entender las estructuras de datos empleadas al procesar la imagen.
  • Deberás crear una clase con todos la funcionalidad necesaria para cubrir los distintos subprocesos del algoritmo de Huffman.
  • Empieza añadiendo como atributo de la clase un vector que permita almacenar la frecuencia de aparición de cada uno de los 256 colores que pueden conformar la imagen. Desarrolla todos los métodos necesarios para llevar a cabo el conteo de frecuencias.
  • Crea un TDA Arbol que permita construir el árbol binario característico del algoritmo de Huffman a partir de un vector de frecuencias de colores. Desestima los colores que no aparezcan en la imagen, esto es, aquellos colores con frecuencia cero.
  • Construye una clase Diccionario que sea capaz, con sus métodos, de asociar a cada color el código Huffman correspondiente a partir del árbol anterior teniendo en cuenta que las ramas izquierdas se etiquetarán con '0' y las derechas con '1'.
  • Crea un TDA CampoDeBits que permita codificar cada color mediante el código determinado por el diccionario ocupando sólo un bit para representar cada valor '0' o '1'. Observa que el almacenamiento en disco de la matriz de colores codificada se hará como una secuencia de bytes pero el almacenamiento final debe materializarse bit a bit, sin desperdiciar ningún bit de cada byte, exceptuando, claro, los posibles bits sobrantes del último octeto.
  • Añade a las clases creadas los métodos necesarios para guardar y recuperar en disco. Para almacenar la imagen comprimida guardaremos, en este orden: primero, las cabeceras BMP y la paleta de colores (sin comprimir); luego, el diccionario de Huffman asociado a la imagen (sin comprimir) y finalmente, la matriz de colores (comprimida mediante el código Huffman)
  • Crea un menú simple para llevar a cabo las tareas de compresión y descompresión que me permita indicar la ruta de la imagen origen y la imagen destino en cada caso.
  • Observa, una vez programada la aplicación, que a pesar de no haber comprimido las cabeceras ni el diccionario (sólo la matriz de colores), casi siempre hay una ahorro importante de espacio... y, además, sin pérdida de información.
  • Si el proceso de compresión o descompresión resultan muy lentos, trata de crear índices en el diccionario de Huffman o cualquier otra mejora en las estructuras de datos que permita acelerar la operación.

SOLUCIÓN

No hay comentarios:

Publicar un comentario