Escriba un programa que tome una imagen RGB en color verdadero I , el número máximo de líneas para dibujar L y la longitud mínima m y máxima M de cada línea. Salida a la imagen O que las miradas tanto como sea posible como I y se dibuja con L o menos líneas rectas, todos los cuales tienen longitud euclidiana entre m y M .
Cada línea debe ser de un color sólido, tener ambos puntos finales en los límites de O y dibujarse utilizando el algoritmo de línea de Bresenham (que la mayoría de las bibliotecas de gráficos ya lo harán por usted). Las líneas individuales solo pueden tener 1 píxel de grosor.
Todas las líneas, incluso las de longitud 0, deben ocupar al menos un píxel. Las líneas pueden dibujarse una encima de la otra.
Antes de dibujar cualquier línea, puede inicializar el fondo de O a cualquier color sólido (que puede depender de I ).
Detalles
- O debe tener las mismas dimensiones que I .
- L siempre será un entero no negativo. Puede que sea mayor que el área de I .
- m y M son números de coma flotante no negativos con M > = m . La distancia entre dos píxeles es la distancia euclidiana entre sus centros. Si esta distancia es menor que m o mayor que M , entonces no se permite una línea entre esos píxeles.
- Las líneas no deben estar suavizadas.
- La opacidad y el alfa no deben usarse.
- Su programa no debería demorar más de una hora en ejecutarse en una computadora moderna decente en imágenes con menos de un millón de píxeles y L menos de 10,000.
Imágenes de prueba
Por supuesto, debe mostrarnos sus imágenes de salida más precisas o interesantes (que espero que ocurran cuando L es entre 5% y 25% del número de píxeles en I , ym y M son alrededor de una décima parte del tamaño diagonal).
Aquí hay algunas imágenes de prueba (haga clic para ver los originales). También puede publicar el suyo.
Imágenes más simples:
Este es un concurso de popularidad. La presentación más votada gana.
Notas
- Puede ser útil dejar que L se derive de un porcentaje del total de píxeles en I , así como de un valor absoluto. por ejemplo
>>> imageliner I=img.png L=50% m=10 M=20
, sería lo mismo que>>> imageliner I=img.png L=32 m=10 M=20
siimg.png
fuera una imagen de 8 por 8 píxeles. Algo similar se podría hacer para m y M . Esto no es requerido. - Ya que las líneas no pueden salir de los límites, las líneas más largas posibles serán la longitud diagonal de I . Sin embargo, tener M más alto que esto no debería romper nada.
- Naturalmente, si m es 0 y L es mayor o igual que el número de píxeles en I , O podría ser idéntico a I al tener una longitud de 0 "líneas" en cada ubicación de píxeles. Este comportamiento no es obligatorio.
- Podría decirse que reproducir la forma de I es más importante que reproducir el color. Es posible que desee examinar la detección de bordes .
fuente
Respuestas:
C ++: líneas algo aleatorias y algo más
Primero algunas líneas aleatorias
El primer paso del algoritmo genera líneas al azar, toma para la imagen objetivo un promedio de los píxeles a lo largo de este, y luego calcula si el cuadrado sumado de las distancias espaciales rgb de todos los píxeles sería menor si pintamos la nueva línea (y solo píntalo, si es así). El nuevo color de las líneas para esto se elige como el promedio de los valores rgb, con una adición aleatoria de -15 / + 15.
Cosas que noté e influyeron en la implementación:
Estaba experimentando con algunos números, y elegí
L=0.3*pixel_count(I)
y me fuim=10
yM=50
. Se va a producir resultados agradables a partir de alrededor0.25
de0.26
para el número de líneas, pero optó por 0,3 para tener más espacio para los detalles precisos.Para la imagen de la puerta dorada de tamaño completo, esto resultó en 235929 líneas para pintar (para lo cual tomó 13 segundos aquí). Tenga en cuenta que todas las imágenes aquí se muestran en tamaño reducido y debe abrirlas en una nueva pestaña / descargarlas para ver la resolución completa.
Borrar lo indigno
El siguiente paso es bastante costoso (para las líneas de 235k tomó aproximadamente una hora, pero eso debería estar dentro del requisito de "una hora para líneas de 10k en 1 megapíxel"), pero también es un poco sorprendente. Reviso todas las líneas pintadas previamente y elimino las que no mejoran la imagen. Esto me deja en esta carrera con solo 97347 líneas que producen la siguiente imagen:
Probablemente necesite descargarlos y compararlos en un visor de imágenes apropiado para detectar la mayoría de las diferencias.
y empezar de nuevo
Ahora tengo muchas líneas que puedo pintar nuevamente para tener un total de 235929 nuevamente. No hay mucho que decir, así que aquí está la imagen:
análisis corto
Todo el procedimiento parece funcionar como un filtro borroso que es sensible al contraste local y al tamaño de los objetos. Pero también es interesante ver dónde se pintan las líneas, por lo que el programa también las registra (para cada línea, el color del píxel se hará un paso más blanco, al final se maximiza el contraste). Aquí están los correspondientes a los tres colores anteriores.
animaciones
Y como a todos nos encantan las animaciones, aquí hay algunos gifs animados de todo el proceso para la imagen más pequeña de Golden Gate. Tenga en cuenta que existe un gran dithering debido al formato gif (y dado que los creadores de formatos de archivos de animación en color verdadero y los fabricantes de navegadores están en guerra por sus egos, no hay un formato estándar para animaciones en color verdadero, de lo contrario podría haber agregado un .mng o similar )
Algo mas
Según lo solicitado, aquí hay algunos resultados de las otras imágenes (de nuevo, es posible que deba abrirlas en una nueva pestaña para no reducirlas)
Pensamientos futuros
Jugar con el código puede dar algunas variaciones interesantes.
El código
Estas son solo las dos funciones útiles principales, el código completo no cabe aquí y se puede encontrar en http://ideone.com/Z2P6Ls
Las
bmp
clasesraw
y laraw_line
función acceden a píxeles y líneas, respectivamente, en un objeto que se puede escribir en formato bmp (fue solo un truco y pensé que eso lo hace algo independiente de cualquier biblioteca).El formato del archivo de entrada es PPM
fuente
Java - líneas aleatorias
Una solución muy básica que dibuja líneas aleatorias y calcula para ellas el color promedio de la imagen de origen. El color de fondo se establece en el color promedio de origen.
L = 5000, m = 10, M = 50
L = 10000, m = 10, M = 50
EDITAR
He agregado un algoritmo genético que maneja una población de líneas. En cada generación, conservamos solo el 50% de las mejores líneas, descartamos las demás y generamos nuevas al azar. Los criterios para mantener las líneas son:
Para mi gran decepción, el algoritmo realmente no parece mejorar la calidad de la imagen :-( solo las líneas se vuelven más paralelas.
Primera generación (5000 líneas)
Décima generación (5000 líneas)
Jugando con parámetros
fuente
C - líneas rectas
Un enfoque básico en C que opera en archivos ppm. El algoritmo intenta colocar líneas verticales con una longitud de línea óptima para llenar todos los píxeles. El color de fondo y los colores de línea se calculan como un valor promedio de la imagen original (la mediana de cada canal de color):
L = 5000, m = 10, M = 50
L = 5000, m = 10, M = 50
L = 100000, m = 10, M = 50
fuente
Python 3 basado en "líneas algo aleatorias y algo más", además de detección de bordes sobel.
teóricamente, el código puede ejecutarse para siempre (por lo que puedo ejecutarlo durante la noche por diversión), pero registra su progreso, por lo que todas las imágenes se toman de la marca de 1-10 min.
Primero lee la imagen, y luego usa la detección de bordes sobel para encontrar el ángulo de todos los bordes, para asegurarse de que las líneas no traspasen otro color. Una vez que se establece una línea de la longitud aleatoria dentro de (lengthmin, lengthmax), se prueba para ver si contribuye a la imagen general. Si bien las líneas más pequeñas son mejores, configuro la longitud de la línea de 10 a 50.
fuente