algorithm - graficas - animar grafico barras powerpoint

Reproducción de imágenes con formas primitivas.(Problema de optimización de gráficos)

Question

Basado en esta idea original, que muchos de ustedes probablemente han visto antes: http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Quería intentar adoptar un enfoque diferente:

Tienes una imagen de destino. Digamos que puedes agregar un triángulo a la vez. Existe un triángulo (o triángulos en caso de empate) que maximiza la similitud de la imagen (función de aptitud). Si pudieras utilizar la fuerza bruta en todas las formas y colores posibles, lo encontrarías. Pero eso es prohibitivamente caro. Buscar en todos los triángulos es un espacio de 10 dimensiones: x1, y1, x2, y2, x3, y3, r, g, b, a .

Utilicé recocido simulado con muy buenos resultados. Pero me pregunto si puedo seguir mejorando esto. Un pensamiento fue analizar realmente la diferencia de imagen entre la imagen de destino y la imagen actual y buscar "puntos calientes" que podrían ser buenos lugares para colocar un nuevo triángulo.

¿Qué algoritmo utilizarías para encontrar el triángulo óptimo (u otra forma) que maximice la similitud de la imagen?

¿Debería variar el algoritmo para manejar detalles gruesos y detalles finos de manera diferente? No lo he dejado correr el tiempo suficiente para comenzar a refinar los detalles más finos de la imagen. Parece que se muestra "tímido" al agregar nuevas formas a medida que se ejecuta ... usa valores alfa bajos (formas muy transparentes).

Imagen de objetivo e imagen reproducida (28 triángulos):

¡Editar! Tuve una nueva idea. Si se dan las coordenadas de la forma y el valor alfa, el color RGB óptimo para la forma se puede calcular analizando los píxeles de la imagen actual y la imagen de destino. ¡Así que eso elimina 3 dimensiones del espacio de búsqueda, y sabe que el color que está usando siempre es óptimo! He implementado esto, y he intentado otra carrera utilizando círculos en lugar de triángulos.

300 círculos y 300 triángulos:

Answer 1

Comenzaría a experimentar con colores de vértice (tendría un valor RGBA diferente para cada vértice), esto aumentará ligeramente la complejidad pero aumentará enormemente la capacidad de igualar rápidamente la imagen de destino (asumiendo imágenes fotográficas que tienden a tener gradientes naturales en ellas).

Su pregunta parece sugerir alejarse de un enfoque genético (es decir, tratar de encontrar un buen triángulo para encajar en lugar de evolucionarlo). Sin embargo, podría interpretarse de ambas maneras, por lo que responderé desde un enfoque genético.

Una forma de enfocar sus mutaciones sería aplicar una cuadrícula sobre la imagen, calcular qué cuadrícula-cuadrada es la mejor concordancia con la cuadrícula-cuadrada correspondiente en la imagen objetivo y determinar qué triángulos se intersecan con esa cuadrícula, luego marcarlos Para una mayor probabilidad de mutación.

También podría (al mismo tiempo) mejorar el detalle fino haciendo una comprobación más pequeña basada en la cuadrícula en el mejor cuadrante de cuadrícula correspondiente.

Por ejemplo, si está utilizando una cuadrícula de 8x8 sobre la imagen:

• Determine cuál de los 64 cuadrados de la cuadrícula es el peor emparejamiento y los triángulos que se intersecan (o están cerca) alrededor de la bandera para una mayor probabilidad de mutación.
• Determine cuál de las 64 cuadrículas es la mejor coincidencia y repita con otra cuadrícula de 8x8 más pequeña dentro de ese cuadrado solamente (es decir, cuadrícula de 8x8 dentro de esa cuadrícula mejor). Se pueden marcar para los lugares probables para agregar nuevos triángulos, o simplemente para ajustar el detalle.

Answer 2

Creo que ese algoritmo es en realidad muy simple.

P = 200 # size of population
max_steps = 100
def iteration
create P totally random triangles (random points and colors)
select one triangle that has best fittness
#fitness computing is described here: http://rogeralsing.com/2008/12/09/genetic-programming-mona-lisa-faq/
put selected triangle on the picture (or add it to array of triangles to manipulate them in future)
end
for i in 1..max_steps {iteration}

Answer 3

Problema muy interesante por cierto! Mi forma de analizar este problema fue el uso del algoritmo de optimización de la estrategia evolutiva . No es rápido y es adecuado si el número de triángulos es pequeño. No he logrado buenas aproximaciones de la imagen original, pero eso se debe en parte a que mi imagen original era demasiado compleja, por lo que no probé muchos reinicios de algoritmos para ver qué otros resultados subóptimos EVO podría producir ... caso - esto no es malo como método de generación de arte abstracto :-)

Answer 4

Una idea utilizando múltiples ejecuciones:

• Use su algoritmo original como la primera ejecución y deténgalo después de un número predeterminado de pasos.
  • Analizar el resultado de la primera carrera. Si el resultado es bastante bueno en la mayor parte de la imagen pero le fue mal en una pequeña parte de la imagen, aumente el énfasis de esta parte.
• Al ejecutar la segunda ejecución, duplique la contribución de error de la parte resaltada (vea la nota). Esto hará que la segunda ejecución haga una mejor coincidencia en esa área. Por otro lado, lo hará peor en el resto de la imagen, en relación con la primera ejecución.
• Repetidamente realizar muchas carreras.

Finalmente, use un algoritmo genético para fusionar los resultados: se le permite elegir entre los triángulos generados de todas las ejecuciones anteriores, pero no se le permite generar ningún triángulo nuevo.

Nota: De hecho, hubo algunos algoritmos para calcular cuánto se debe aumentar la contribución de error. Se llama http://en.wikipedia.org/wiki/Boosting . Sin embargo, creo que la idea seguirá funcionando sin utilizar un método matemáticamente preciso.