Programación lúdica: ecualización del histograma de una imagen

El proceso digital de imágenes tiene una serie de técnicas para poder manipular los pixeles de una imagen. En un artículo pasado vimos la manera de ajustar el contraste a partir de estirar el histograma de frecuencias de valores de los pixeles en una imagen de tonos de gris. Cabe señalar que en una imagen de grises solamente puede haber 256 tonos diferentes, cuyas componentes de color son: (0,0,0) que es el negro; (1,1,1) que es menos negro... y así hasta (255,255,255), que es blanco.

Desafortunadamente el estirar el histograma no sirve cuando la diferencia entre el contraste mínimo y máximo es de 255, porque la fórmula para cada nuevo pixel sería: (TonoDeGris / 255) * 255, lo cual sería dividir entre 255 y multiplicar entre 255, lo que dejaría el resultado como el pixel original. Por ello, es necesaria otra técnica y ésta es lo que se llama la "ecualización de un histograma".

Cuando uno "ecualiza" algo, por ejemplo, una señal de audio, lo que hacemos es que los bajos y los altos se igualen. En lo que se refiere a gráficas, cuando hay muchos pixeles oscuros entonces se reduce esa cantidad y si hay pocos pixeles claros, se incrementan estos.

Para "ecualizar" (o igualar) los valores del histograma, lo que tenemos que hacer es simplemente crear algo que se llama CDF (Cumulative Distribution Frequency), lo cual es simplemente un arreglo de 256 bytes que contienen la suma de los valores de las frecuencias de los valores previos. Por ejemplo, si tenemos valores de frecuencias para los tones de grises: 52 tenemos 1, 53 tenemos 3, 58 tenemos 2 y 59 tenemos 3, entonces el CDF será 1, 4, 6, 9, etcétera, para el CFD[52], CDF[58] y CDF[59]. Simplemente sumamos el valor actual con el anterior y listo. Teniendo este valor, solamente nos falta calcular la ecualización de cada pixel, la cual es una función como ésta, para cada pixel en la imagen: NuevoPixel = round(((CDF[R]-1) / CDF[255]) * 255).

Para ver si esto funciona, tomemos la siguiente imagen de Lena:

Y procesemos de acuerdo a lo que hemos dicho:

Puede observarse que la imagen se ecualizó y el contraste cambió significativamente. Nótese cómo el histograma se "estiró" de alguna manera.

Cabe señalar que esta técnica puede no ser necesariamente la mejor pero todo dependerá de qué queremos hacer y por qué queremos ecualizar una imagen.

A quien le interese este tema, escríbame a morsa@la-morsa.com y le enviaré el software ejecutable y el código fuente escrito en Delphi.

Programación lúdica: generación de laberintos

Hay muchas tareas en programación que las consideramos sencillas… hasta que tenemos que programarlas. Una idea que lleva tiempo en mi cabeza es la que se refiere a la creación y resolución de laberintos. ¿Qué tan difícil será crear un laberinto y más aún, hacer un programa que dé con la solución?

Esta es pues el nuevo reto de la programación lúdica: Escríbase un programa que genere un laberinto, y además, lo resuelva satisfactoriamente. Las dos partes son obligatorias.

Para esto, es interesante entender algunas ideas sobre este tema. Dice la Wikipedia: “Un laberinto es un pasatiempo gráfico consistente en trazar una línea desde un punto de origen situado en el exterior de un laberinto a uno de destino situado generalmente en el centro o bien en el lado opuesto. La dificultad consiste en encontrar un camino directo hasta el lugar deseado. El laberinto, por su propia configuración, contiene diferentes vías sin salida (de mayor o menor longitud) y sólo un recorrido correcto. Puede adoptar diferentes formas: cuadrado, ovalado, redondo, cuadrangular, etcétera”.

Crear un laberinto se puede hacer de la siguiente manera:

Considérese que el laberinto es una cuadrícula de celdas. Con esto en mente, empiece en cualquier celda (al azar incluso). Marque la celda actual como visitada y obtenga una lista de sus vecinos. Para cada vecino, puede empezar con uno de ellos al azar y: si el vecino no ha sido visitado, quite la pared entre esta celda y la del vecino, y entonces recursivamente con ese vecino como la celda actual, genérese el mismo algoritmo para los otros vecinos. Desde luego es una sugerencia. Cada quien puede usar la técnica que deseé.

Este programa, probablemente puedan encontrarlo en la red. No se trata pues de copiarlo de algún sitio. Si descubro una copia o si tengo dudas, me tomo la libertad de preguntarle al autor directamente cómo hizo, para garantizar así que la solución fue escrita y no copiada por el autor del programa. Juguemos pues limpiamente y aprendamos todos de estos retos.

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución, en donde los criterios serán qué tan versátil es el programa: ¿Puedo cambiar el tamaño del laberinto creado? ¿Es muy lento, es muy rápido? ¿Qué opciones da al usuario para la creación del laberinto? Cabe decir que no ganará el primero que envíe su solución (aunque en caso de tener que desempatar, se dará prioridad a quien lo haya entregado antes)



Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de 8 GBytes al menos y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero mientras no tengamos patrocinadores, esto es lo que hay.

¡A darle entonces!