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

Simuladores de los algoritmos de ordenación

Haz clic en la imagen para acceder al simulador

Algoritmos de Prim y de Kruskal.

Esquema del algoritmo de Kruskal usando particiones:


Simulador del algoritmo de Prim

Simulador del algoritmo de Kruskal

EJERCICIO: Implementa en C++ los algoritmos de Prim y Kruskal partiendo del mismo grafo de ejemplo del post anterior ("Un tal Prim asfaltando caminos") para verificar que la salida es correcta. Muestra el grafo de partida, el árbol de recubrimiento mínimo obtenido y el coste total de las aristas de dicha solución. Apóyate en los tipos abstractos de datos "Grafo" y, para el algoritmo de Kruskal también "Particion", basados en el paradigma orientado a objetos.

SOLUCIÓN (Prim y Kruskal)

Un tal Prim asfaltando caminos.

Seguramente todos de pequeños jugasteis a aquello de unir varios puntos sin levantar el lápiz del papel para formar una figura. Lo curioso es que ese juego tan inocente, con una pequeña variación, tiene una aplicación muy similar en la vida real que nos permite ahorrar mucho dinero. Imaginaos que hubiera una vieja red de carreteras donde cada una conecta dos pueblos. El ayuntamiento, ante las quejas de sus vecinos por el mal estado de las mismas, está dispuesto a dotar presupuesto suficiente para asfaltarlas de nuevo, de tal manera que todos los pueblos se puedan seguir comunicando mediante los nuevos viales, independientemente de que queden multitud de viejos caminos sin asfaltar. Las únicas condiciones impuestas son que el gasto ha de ser el mínimo posible y que se pueda viajar entre dos pueblos cualesquiera sin necesidad de circular por trazados bacheados. Entonces, llega el ingeniero de turno y realiza un estudio del coste estimado para asfaltar cada vieja carretera. Sólo queda saber elegir cuáles se asfaltarán y cuáles no para comunicar todos los pueblos con el mínimo gasto posible. ¿Quién dijo que era fácil ser alcalde de un ayuntamiento!

Este problema se puede resolver utilizando algoritmos voraces, es decir, algoritmos que seleccionan en cada momento uno de entre varios candidatos (“pueblos”) para optimizar una función objetivo (“el gasto en asfaltado”) sin retractarse de ninguna decisión tomada con anterioridad (“sin levantar el lápiz del papel”). En términos más formales, la red de carreteras es un grafo no dirigido y conexo y lo que pretendemos calcular es el llamado árbol de recubrimiento mínimo. Existen básicamente dos aproximaciones para resolver este problema: el algoritmo de Prim y el algoritmo de Kruskal. Hoy vamos a ver el algoritmo de Prim porque como ya dije es el que más se parece a ese inocente juego de hacer trazados sin levantar el lápiz del papel. Consiste en lo siguiente:

1. Consideramos siempre dos conjuntos, el conjunto de vértices (“pueblos”) que forman parte del recubrimiento mínimo en construcción (“red de carreteras que se asfaltará”) y el de los vértices aún no considerados (“pueblos candidatos”).
2. Inicialmente, el primer conjunto incluye un vértice arbitrario.
3. A continuación, se consideran todas las aristas o carreteras (u,v) tales que u está en el primer conjunto y v en el segundo para seleccionar la de menor coste. Dicha arista se incorpora a la solución (“esa carretera será definitivamente asfaltada”). Obviamente, la arista escogida ya no será considerada de nuevo y el vértice v se elimina del conjunto de candidatos y se incluye en el de vértices pertenecientes al recubrimiento.
4. El algoritmo acaba cuando ya no queden vértices candidatos.
5. La mala noticia para el alcalde es que hay casos en que existe más de un recubrimiento mínimo para un mismo grafo y, dependiendo del vértice que se escoja al principio o de la arista que se tome en caso de haber varias con el mismo coste, obtendremos uno u otro. Eso quiere decir que determinados vecinos pueden reclamar soluciones alternativas con el mismo coste que les resulten más ventajosas. Por ejemplo, podrían preferir un trazado A frente a otro B, a pesar de costar lo mismo y ser igualmente óptimos, por el simple hecho de que A los mantiene más cerca del único pueblo con supermercado que el trazado B. Para este tipo de problemas, la algoritmia no nos sirve. ¡Lo siento, señor alcalde!
   

Aquí tenéis un traceado del algoritmo sobre un grafo de ejemplo por si os habéis perdido en algún punto de la explicación.

Referencias:

El grafo de ejemplo ha sido extraído del punto 11.4.1 de los apuntes de algorítmica de A. Marzal, M.J. Castro y P. Aibar. También podéis encontrar en su obra las soluciones a este y otros muchos problemas implementados en Python, con detallados análisis de su corrección y complejidad.

Algoritmo de Dijkstra. Caminos de coste mínimo.

Aplica el algoritmo de Dijkstra al siguiente grafo de ejemplo para que calcule los costes mínimos para ir del nodo origen (nodo cero) hasta el resto de nodos del grafo.

PROPUESTA: trata de mejorar el algoritmo parametrizándolo de manera que pueda servir para calcular los costes mínimos desde cualquier nodo tomado como origen. Asimismo, añade las estructuras de datos y funciones necesarias para visualizar, no solo el coste de los caminos mínimos, sino también los propios caminos, viendo todos los nodos intermedios por los que se va pasando con el coste asociado a cada arista.

SOLUCIÓN

Ejemplo resuelto de Backtracking recursivo. Agencia matrimonial.

Una agencia matrimonial quiere garantizar a sus clientes el mejor servicio y proporcionar garantías de poder encontrar una pareja estable. Para ello dispone de dos matrices de números naturales: H[1..n][1..N] y M[1..N][1..N] tales que H[i][j] indica la preferencia de un hombre i por una mujer j y M[i][j] la preferencia de una mujer i por un hombre j, para i y j entre 1 y N. Establecida una asignación de N parejas, si existe algún hombre y alguna mujer que, sin estar emparejados entre sí, se prefieren mutuamente a sus respectivas parejas, entonces la asignación es inestable; si no se da tal caso la asignación es estable. Desarrollar un algoritmo que encuentre los emparejamientos estables.

SOLUCIÓN: Descargar código C++

Esquema general del backtracking recursivo

Como ejemplo véase el ejercicio de generar todas la permutaciones de los primeros n números naturales.

Ejemplos básicos de programas C++

Diseño de los programas utilizando:

• Diagramas de flujo
• Diagramas Nassi Shneiderman
• Pseudocódigo

Fundamentos de diseño de programas mediante diagramas de flujo