Fractales

28 08 2013

Hace varios años hice un programa para dibujar el conjunto de Mandelbrot, pues acababa de ver la teoría en mi clase de Matemáticas Avanzadas, pero no le puse colores ni zoom, así que algo de tiempo después decidí completarlo y además me puse a jugar con la función que genera el fractal. El conjunto de Mandelbrot es una serie de puntos en el espacio complejo que cumple la condición de que:

z[1]=0+0i;

c=x+yi;

z[n]=z[n-1]^2+c

|z[∞]|<∞

O sea que después de repetir el proceso de asignar z[n] infinitas veces, si el módulo del resultado es menor a infinito, el punto forma parte del conjunto de Mandelbrot y se colorea de un color, si no, se colorea de otro. Si queremos que tenga colores más interesantes, se colorea dependiendo de cuánto tarde en llegar a infinito. El problema es que hay que decidir a partir de cuándo ya es infinito, y qué número de veces de repetir el proceso se puede llamar infinito. Para facilitar esto se decide que si el módulo de z es mayor a 2, ya no pertenece al conjunto, pues es seguro que para iteraciones posteriores tenderá a infinito. El número máximo de iteraciones depende de la definición que se quiera tener de la imagen. En el primer ejemplo el número máximo era de 10 iteraciones, en la segunda imagen es de 55.

intento2 intento3

Después me puse a modificar la forma en que se definía z[n], y obtuve figuras tan diferentes y extrañas como un ojo, una flor, una especia de luna o algo totalmente extraño.

ojo

florcosa

El código aquí.luna

Anuncios




Algoritmos geneticos e imagenes 2

5 08 2013

Hace ya algún tiempo hice un programa para generar imágenes con algoritmos genéticos, que tendieran hacia una imagen dada, de modo que no tuvieran el mismo color, pero sí la misma sensación de luz. El problema era que con el algoritmos genético tardaba mucho en procesar todas las imágenes que usaba, por lo que tenía que usar imágenes demasiado pequeñas (el ejemplo que puse es una de 20×20). Después leí sobre comprimir imágenes con pixeles de tamaños distintos, lo que me hizo pensar en el algoritmo genético que había hecho, pues al tener pixeles de distintos tamaños, entre ellos algunos grandes, con un sólo campo se ocupaba un bueno trozo de la imagen, por lo que debía ser mucha menos la información que debía manejar y se podría trabajar con imágenes de tamaños más normales (tal vez 600×400, no lo sabía). Entonces decidí hacer mi implementación con python, y ya que estuvo lista hice un nuevo programa para generar imágenes con algoritmos genéticos y fue lo que estuve probando ayer. Obtuve un programa que con varias versiones mejoré (o probé), y con casi todas tardaba muchísimo tiempo (hasta 8 horas), pero que obtenía un resultado bastante bueno. cara-1000gen-mutvar300

Algo de lo que no me acordé cuando hice ese programa, es que se comparaba la imagen con la imagen original tomando en cuenta los colores, por lo que el resultado no es tan colorido. Pero para la siguiente versión que hice, evolucionando pixel por pixel no olvidé esa parte, y las imágenes salen más coloridas. Y es muchísimo más rápido, pues la evolución de cada pixel por separado pasa en muy pocas generaciones.

evolucion pixel por pixel

 

 

 

 

 

 

El código aquí





Compresión de imágenes con pixeles desiguales

3 08 2013

Hace un tiempo leí algo sobre compresión de imágenes usando pixeles desiguales, que se trata de analizar el color de zonas de la imagen y si es lo suficientemente parecido en toda la zona, se crea un pixel que abarque esa zona. Así, si se tienen imágenes con muchas zonas de color hasta cierto punto plano, se puede reducir de gran manera el número de los pixeles, usando pixeles de distintos tamaños, y así también reducir el espacio ocupado por la imagen. Si se desea tener la misma calidad y se tiene una imagen con muchos cambios de color, en realidad no conviene porque la información que necesita cada pixel es mayor, incluyendo las coordenadas, el tamaño y el color, mientras que la manera convencional sólo necesita el color, pues lo pixeles van en orden.

Hace unos días decidí implementarlo con python y python-imaging, analizando primero la imagen completa y si la variancia de la imagen es mayor que cierto umbral se divide esa zona en dos, y se analizan luego las dos zonas, y si la variancia de alguna de las dos imágenes es mayor que el umbral, esta se divide nuevamente en dos (intermitentemente horizontalmente o verticalmente) hasta que el área de la imagen no alcanza para dividirla (o sea que sea sólo un pixel).

El resultado:

Imagen introducida                                                         Resultado

azotea-lluviaazotea-lluvia-px





Algoritmos genéticos e imágenes

3 08 2013

Hace ya bastante tiempo vi la película Tron: The legacy, y escuché que decían algo sobre algoritmos genéticos. Le pregunté a mi hermano, que entonces seguía viviendo aquí y me explicó que son bastante simples y sirven para encontrar algo así como una solución a cierto problema, tal vez no óptima pero intentando serlo, con un método un poco más simple que el que implicaría encontrar una solución óptima.

La idea era la siguiente: Se crea una población inicial random y se evalúa con el objetivo al que se quiere llegar, se toma el mejor o un conjunto de los mejores elementos de la población y se mezclan para generar una nueva generación, poniendo partes de uno y de otro aleatoriamente y añadiendo un pequeño cambio aleatorio también, que es lo que le permite evolucionar, y se sigue el proceso una y otra vez.

Después de eso decidí hacer un programa simple, que de un conjunto de series de letras aleatorias, llegara por medio de un algoritmo genético a mi nombre. En realidad no siempre llegaba porque a veces faltaba alguna letra, pero llegaba a algo bastante parecido.

El programa genera una población inicial de 50 000 cadenas de caracteres y elije las 2 que más se parecen a mi nombre y las combina, haciendo 400 nuevas cadenas de caracteres, y esas cifras hacen que converga muy rápidamente, pero también que le hagan falta letras para formar la palabra final. Un ejemplo:

$ python ejemplo1.py
GENERACION 0
Padre: elbtwro (8)    Madre: aeborkt (8)
GENERACION 1
Padre: albtrko (10)    Madre: albelro (10)
GENERACION 2
Padre: alberko (11)    Madre: alberro (11)
GENERACION 3
Padre: alberko (11)    Madre: alberro (11)

A la tercera generación llega al resultado final, pero no es la solución óptima. Con eso aprendí que el diseño de la función de evaluación y la función de apareamiento es muy importante para que el algoritmo converja.

Después de ese primer programa ya tenía una idea de cómo funcionaban los algoritmos genéticos y decidí hacer otro que generara una imagen que diera la misma sensación luminosa que una imagen dada. Es decir, que si se transformara a escala de grises fuera igual que la original transformada a escala de grises también, sólo que la nueva imagen hecha con colores aleatorios.

Usando una imagen de 20×20 pixeles, después de más de 700 generaciones y N horas de procesamiento, el resultado es el siguiente:

Imagen Introducida                                       Resultado

imagen-original   geneticos

 

 

 

 

 

 

Como reflexión sobre el proceso, creo que podría mejorar si se evalúa cada siguiente generación conforme van “naciendo” los hijos, y si es mejor que los padres pasar a la siguiente generación, lo que generaría generaciones de diferentes tamaños cada vez, y lo que podría agilizar el programa. También podría ser que se evolucione la imagen pixel por pixel, y quizá podría ser más rápido, pues tal vez sea más rápido alcanzar 400 combinaciones de 3 números que una combinación de 1200 números. Cosa de probar…