Créditos a Calvin's Hobbies por empujar mi idea de desafío en la dirección correcta.
Considere un conjunto de puntos en el plano, que llamaremos sitios , y asocie un color con cada sitio. Ahora puede pintar todo el plano coloreando cada punto con el color del sitio más cercano. Esto se llama un mapa de Voronoi (o diagrama de Voronoi ). En principio, los mapas de Voronoi se pueden definir para cualquier métrica de distancia, pero simplemente usaremos la distancia euclidiana habitual r = √(x² + y²)
. ( Nota: no necesariamente tiene que saber cómo calcular y representar uno de estos para competir en este desafío).
Aquí hay un ejemplo con 100 sitios:
Si observa cualquier celda, todos los puntos dentro de esa celda están más cerca del sitio correspondiente que de cualquier otro sitio.
Su tarea es aproximar una imagen dada con dicho mapa de Voronoi. Que le den la imagen en cualquier formato de gráficos de trama conveniente, así como un número entero N . Luego debe producir hasta N sitios y un color para cada sitio, de modo que el mapa de Voronoi basado en estos sitios se parezca lo más posible a la imagen de entrada.
Puede usar el Fragmento de pila al final de este desafío para representar un mapa de Voronoi a partir de su salida, o puede hacerlo usted mismo si lo prefiere.
Usted puede utilizar las funciones built-in o de terceros para calcular un mapa de Voronoi de un conjunto de sitios (si es necesario).
Este es un concurso de popularidad, por lo que gana la respuesta con más votos netos. Se alienta a los votantes a juzgar las respuestas por
- qué tan bien se aproximan las imágenes originales y sus colores.
- qué tan bien funciona el algoritmo en diferentes tipos de imágenes.
- lo bien que el algoritmo funciona para pequeñas N .
- si el algoritmo agrupa de forma adaptativa los puntos en regiones de la imagen que requieren más detalles.
Imágenes de prueba
Aquí hay algunas imágenes para probar su algoritmo (algunos de nuestros sospechosos habituales, algunos nuevos). Haga clic en las imágenes para versiones más grandes.
La playa en la primera fila fue dibujada por Olivia Bell , e incluida con su permiso.
Si quieres un desafío extra, prueba con Yoshi con un fondo blanco y acerta su línea del vientre.
Puede encontrar todas estas imágenes de prueba en esta galería de imágenes donde puede descargarlas todas como un archivo zip. El álbum también contiene un diagrama aleatorio de Voronoi como otra prueba. Como referencia, aquí están los datos que lo generaron .
Incluya diagramas de ejemplo para una variedad de imágenes diferentes y N , por ejemplo, 100, 300, 1000, 3000 (así como pastebins para algunas de las especificaciones de celda correspondientes). Puede usar u omitir bordes negros entre las celdas como mejor le parezca (esto puede verse mejor en algunas imágenes que en otras). Sin embargo, no incluya los sitios (excepto en un ejemplo separado, tal vez si desea explicar cómo funciona la ubicación de su sitio, por supuesto).
Si desea mostrar una gran cantidad de resultados, puede crear una galería en imgur.com , para mantener razonable el tamaño de las respuestas. Alternativamente, coloque miniaturas en su publicación y conviértalas en enlaces a imágenes más grandes, como hice en mi respuesta de referencia . Puede obtener las miniaturas pequeñas agregando s
el nombre del archivo en el enlace imgur.com (por ejemplo, I3XrT.png
-> I3XrTs.png
). Además, siéntase libre de usar otras imágenes de prueba, si encuentra algo bueno.
Renderizador
Pegue su salida en el siguiente fragmento de pila para representar sus resultados. El formato exacto de la lista es irrelevante, siempre que cada celda esté especificada por 5 números de coma flotante en el orden x y r g b
, dónde x
y y
son las coordenadas del sitio de la celda, y r g b
son los canales de color rojo, verde y azul en el rango 0 ≤ r, g, b ≤ 1
.
El fragmento proporciona opciones para especificar un ancho de línea de los bordes de la celda, y si los sitios de la celda deben mostrarse o no (esto último principalmente para fines de depuración). Pero tenga en cuenta que la salida solo se vuelve a representar cuando cambian las especificaciones de la celda, por lo que si modifica algunas de las otras opciones, agregue un espacio a las celdas o algo así.
Créditos masivos a Raymond Hill por escribir esta biblioteca realmente agradable de JS Voronoi .
Desafíos relacionados
fuente
Respuestas:
Python + scipy + scikit-image , muestreo de disco de Poisson ponderado
Mi solución es bastante compleja. Hago un preprocesamiento en la imagen para eliminar el ruido y obtener un mapeo de lo 'interesante' que es cada punto (usando una combinación de entropía local y detección de bordes):
Luego elijo los puntos de muestreo usando el muestreo de disco de Poisson con un giro: la distancia del círculo está determinada por el peso que determinamos anteriormente.
Luego, una vez que tengo los puntos de muestreo, divido la imagen en segmentos voronoi y asigno el promedio L * a * b * de los valores de color dentro de cada segmento a cada segmento.
Tengo muchas heurísticas y también debo hacer un poco de matemática para asegurarme de que el número de puntos de muestra sea cercano
N
. ObtengoN
exactamente sobrepasando un poco , y luego bajando algunos puntos con una heurística.En términos de tiempo de ejecución, este filtro no es barato , pero ninguna de las siguientes imágenes tardó más de 5 segundos en crearse.
Sin más preámbulos:
Imágenes
Respectivamente
N
es 100, 300, 1000 y 3000:fuente
C ++
Mi enfoque es bastante lento, pero estoy muy contento con la calidad de los resultados que brinda, particularmente con respecto a la preservación de los bordes. Por ejemplo, aquí están Yoshi y el Cornell Box con solo 1000 sitios cada uno:
Hay dos partes principales que lo hacen funcionar. El primero, incorporado en la
evaluate()
función, toma un conjunto de ubicaciones de sitios candidatos, establece los colores óptimos en ellas y devuelve una puntuación para el PSNR de la teselación de Voronoi representada frente a la imagen objetivo. Los colores para cada sitio se determinan promediando los píxeles de la imagen objetivo cubiertos por la celda alrededor del sitio. Utilizo el algoritmo de Welford para ayudar a calcular tanto el mejor color para cada celda como el PSNR resultante usando solo un solo paso sobre la imagen explotando la relación entre la varianza, MSE y PSNR. Esto reduce el problema a uno de encontrar el mejor conjunto de ubicaciones del sitio sin tener en cuenta el color.La segunda parte, incorporada
main()
, trata de encontrar este conjunto. Comienza eligiendo un conjunto de puntos al azar. Luego, en cada paso, elimina un punto (yendo por turnos) y prueba un conjunto de puntos candidatos aleatorios para reemplazarlo. El que produce el PSNR más alto del grupo es aceptado y mantenido. Efectivamente, esto hace que el sitio salte a una nueva ubicación y generalmente mejora la imagen bit por bit. Tenga en cuenta que el algoritmo intencionalmente no retiene la ubicación original como candidato. A veces esto significa que el salto disminuye la calidad general de la imagen. Permitir que esto suceda ayuda a evitar quedar atrapado en los máximos locales. También da un criterio de detención; el programa termina después de seguir un cierto número de pasos sin mejorar el mejor conjunto de sitios encontrados hasta ahora.Tenga en cuenta que esta implementación es bastante básica y puede llevar fácilmente horas de tiempo de núcleo de CPU, especialmente a medida que crece el número de sitios. Vuelve a calcular el mapa completo de Voronoi para cada candidato y la fuerza bruta prueba la distancia a todos los sitios para cada píxel. Como cada operación implica eliminar un punto a la vez y agregar otro, los cambios reales en la imagen en cada paso serán bastante locales. Hay algoritmos para actualizar de manera eficiente e incremental un diagrama de Voronoi y creo que le darían a este algoritmo una aceleración tremenda. Para este concurso, sin embargo, he elegido mantener las cosas simples y con fuerza bruta.
Código
Corriendo
El programa es autónomo y no tiene dependencias externas más allá de la biblioteca estándar, pero requiere que las imágenes estén en formato PPM binario . Utilizo ImageMagick para convertir imágenes a PPM, aunque GIMP y muchos otros programas también pueden hacerlo.
Para compilarlo, guarde el programa como
voronoi.cpp
y luego ejecute:Espero que probablemente funcione en Windows con versiones recientes de Visual Studio, aunque no lo he probado. Querrás asegurarte de que estás compilando con C ++ 11 o superior y OpenMP habilitado si lo haces. OpenMP no es estrictamente necesario, pero ayuda mucho a hacer que los tiempos de ejecución sean más tolerables.
Para ejecutarlo, haga algo como:
El archivo posterior se actualizará con los datos del sitio a medida que avanza. La primera línea tendrá el ancho y la altura de la imagen, seguida de líneas de valores x, y, r, g, b adecuadas para copiar y pegar en el renderizador de Javascript en la descripción del problema.
Las tres constantes en la parte superior del programa le permiten ajustarlo para velocidad versus calidad. El
decimation
factor engrosa la imagen de destino al evaluar un conjunto de sitios para color y PSNR. Cuanto más alto sea, más rápido se ejecutará el programa. Establecerlo en 1 usa la imagen de resolución completa. Lacandidates
constante controla cuántos candidatos probar en cada paso. Mayor da una mejor oportunidad de encontrar un buen lugar para saltar, pero hace que el programa sea más lento. Finalmente,termination
es cuántos pasos puede seguir el programa sin mejorar su salida antes de que se cierre. Aumentarlo puede dar mejores resultados, pero hace que demore un poco más.Imágenes
N
= 100, 300, 1000 y 3000:fuente
IDL, refinamiento adaptativo
Este método está inspirado en el refinamiento de malla adaptable de simulaciones astronómicas, y también en la superficie de subdivisión . Este es el tipo de tarea de la que se enorgullece IDL, que podrá ver por la gran cantidad de funciones integradas que pude usar. :RE
He mostrado algunos de los intermedios para la imagen de prueba yoshi de fondo negro, con
n = 1000
.Primero, realizamos una escala de grises de luminancia en la imagen (usando
ct_luminance
), y aplicamos un filtro Prewitt (prewitt
, ver wikipedia ) para una buena detección de bordes:Luego viene el verdadero trabajo gruñido: subdividimos la imagen en 4 y medimos la varianza en cada cuadrante de la imagen filtrada. Nuestra varianza está ponderada por el tamaño de la subdivisión (que en este primer paso es igual), de modo que las regiones "nerviosas" con alta varianza no se subdividen cada vez más y más. Luego, usamos la varianza ponderada para apuntar subdivisiones con más detalle, y subdividimos iterativamente cada sección rica en detalles en 4 adicionales, hasta alcanzar nuestro número objetivo de sitios (cada subdivisión contiene exactamente un sitio). Como estamos agregando 3 sitios cada vez que iteramos, terminamos con
n - 2 <= N <= n
sitios.Hice un .webm del proceso de subdivisión para esta imagen, que no puedo incrustar, pero está aquí ; El color en cada subsección está determinado por la varianza ponderada. (Hice el mismo tipo de video para el yoshi de fondo blanco, en comparación, con la tabla de colores invertida para que vaya hacia el blanco en lugar del negro; está aquí ). El producto final de la subdivisión se ve así:
Una vez que tenemos nuestra lista de subdivisiones, revisamos cada subdivisión. La ubicación final del sitio es la posición del mínimo de la imagen de Prewitt, es decir, el píxel menos "nervioso", y el color de la sección es el color de ese píxel; Aquí está la imagen original, con sitios marcados:
Luego, utilizamos el incorporado
triangulate
para calcular la triangulación de Delaunay de los sitios, y el incorporadovoronoi
para definir los vértices de cada polígono Voronoi, antes de dibujar cada polígono en un búfer de imagen en su color respectivo. Finalmente, guardamos una instantánea del búfer de imagen.El código:
Llame a esto a través de
voro_map, n, image, output_filename
. También incluí unwrapper
procedimiento, que revisaba cada imagen de prueba y funcionaba con 100, 500 y 1000 sitios.Salida recopilada aquí , y aquí hay algunas miniaturas:
n = 100
n = 500
n = 1000
fuente
Python 3 + PIL + SciPy, Fuzzy k-means
El algoritmo
La idea central es que k-significa agrupamiento divide naturalmente la imagen en celdas de Voronoi, ya que los puntos están vinculados al centroide más cercano. Sin embargo, necesitamos agregar de alguna manera los colores como una restricción.
Primero convertimos cada píxel al espacio de color Lab , para una mejor manipulación del color.
Luego hacemos una especie de "detección de bordes del pobre". Para cada píxel, observamos sus vecinos ortogonales y diagonales, y calculamos la diferencia cuadrática media en color. Luego clasificamos todos los píxeles por esta diferencia, con los píxeles más similares a sus vecinos al principio de la lista, y los píxeles más diferentes a sus vecinos en la parte posterior (es decir, más probable que sea un punto de borde). Aquí hay un ejemplo para el planeta, donde cuanto más brillante es el píxel, más diferente es de sus vecinos:
(Hay un patrón claro similar a una cuadrícula en la salida representada arriba. Según @randomra, esto probablemente se deba a la codificación JPG con pérdida o a la compresión de las imágenes).
A continuación, usamos este orden de píxeles para muestrear una gran cantidad de puntos que se agruparán. Utilizamos una distribución exponencial, dando prioridad a los puntos que son más similares a los bordes e "interesantes".
Para la agrupación, primero seleccionamos los
N
centroides, elegidos al azar utilizando la misma distribución exponencial que la anterior. Se realiza una iteración inicial y para cada uno de los grupos resultantes asignamos un color medio y un umbral de variación de color. Luego, para una serie de iteraciones, nosotros:(Haga clic para tamaño completo)
Finalmente, muestreamos una gran cantidad de puntos, esta vez usando una distribución uniforme. Usando otro árbol kd, asignamos cada punto a su centroide más cercano, formando grupos. Luego, aproximamos el color medio de cada grupo utilizando un algoritmo de escalada, dando nuestros colores finales de celda (idea para este paso gracias a @PhiNotPi y @ MartinBüttner).
Notas
Además de generar un archivo de texto para el fragmento (
OUTFILE
), siDEBUG
está configurado paraTrue
el programa también generará y sobrescribirá las imágenes de arriba. El algoritmo toma un par de minutos para cada imagen, por lo que es una buena forma de verificar el progreso que no agrega mucho al tiempo de ejecución.Resultados de muestra
N = 32:
N = 100:
N = 1000:
N = 3000:
fuente
Mathematica, celdas aleatorias
Esta es la solución de referencia, por lo que tiene una idea del mínimo que le pido. Dado el nombre del archivo (localmente o como una URL) en
file
y N enn
, el siguiente código simplemente selecciona N píxeles aleatorios y usa los colores encontrados en esos píxeles. Esto es realmente ingenuo y no funciona increíblemente bien, pero quiero que lo superen después de todo. :)Aquí están todas las imágenes de prueba para N = 100 (todas las imágenes enlazan a versiones más grandes):
Como puede ver, estos son esencialmente inútiles. Si bien pueden tener algún valor artístico, de manera expresionista, las imágenes originales son apenas reconocibles.
Para N = 500 , la situación mejora un poco, pero todavía hay artefactos muy extraños, las imágenes se ven borrosas y se desperdician muchas células en regiones sin detalles:
¡Tu turno!
fuente
Dimensions@ImageData
y noImageDimensions
? Puede evitar la lentitudImageData
por completo usandoPixelValue
.Mathematica
Todos sabemos que a Martin le encanta Mathematica, así que déjame probarlo con Mathematica.
Mi algoritmo usa puntos aleatorios de los bordes de la imagen para crear un diagrama de voronoi inicial. El diagrama se embellece mediante un ajuste iterativo de la malla con un filtro medio simple. Esto proporciona imágenes con alta densidad celular cerca de regiones de alto contraste y células visualmente agradables sin ángulos extraños.
Las siguientes imágenes muestran un ejemplo del proceso en acción. La diversión está un poco estropeada por el mal Antialiasing de Mathematicas, pero obtenemos gráficos vectoriales, que deben valer algo.
Este algoritmo, sin el muestreo aleatorio, se puede encontrar en la
VoronoiMesh
documentación aquí .Imágenes de prueba (100,300,1000,3000)
Código
fuente
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + maestro de ceremonias
El algoritmo que he usado es el siguiente:
El algoritmo parece funcionar muy bien. Desafortunadamente, solo puede ejecutarse sensiblemente en imágenes más pequeñas. No he tenido tiempo de tomar los puntos Voronoi y aplicarlos a las imágenes más grandes. Podrían ser refinados en este punto. También podría haber ejecutado el MCMC durante más tiempo para obtener mejores mínimos. El punto débil del algoritmo es que es bastante costoso. No he tenido tiempo de aumentar más allá de 1000 puntos y un par de las imágenes de 1000 puntos todavía se están refinando.
(haga clic derecho y vea la imagen para obtener una versión más grande)
Los enlaces a versiones más grandes son http://imgur.com/a/2IXDT#9 (100 puntos), http://imgur.com/a/bBQ7q (300 puntos) y http://imgur.com/a/rr8wJ (1000 puntos)
Las imágenes enmascaradas sin aspecto se parecen a las siguientes. Se seleccionan puntos aleatorios de la imagen si un número aleatorio es menor que el valor de la imagen (normalizado a 1):
Publicaré imágenes más grandes y los puntos Voronoi si tengo más tiempo.
Editar: si aumenta el número de caminantes a 100 * npts, cambie la función de costo para que sea uno de los cuadrados de las desviaciones en todos los canales y espere mucho tiempo (aumentando el número de iteraciones para salir del bucle a 200), es posible hacer algunas buenas imágenes con solo 100 puntos:
fuente
Usando la energía de la imagen como un mapa de peso en puntos
En mi enfoque de este desafío, quería una forma de mapear la "relevancia" de un área de imagen en particular con la probabilidad de que un punto en particular fuera elegido como un centroide de Voronoi. Sin embargo, todavía quería preservar la sensación artística del mosaico de Voronoi eligiendo puntos de imagen al azar. Además, quería operar en imágenes grandes, para no perder nada en el proceso de disminución de resolución. Mi algoritmo es más o menos así:
Resultados
N
= 100, 500, 1000, 3000fuente