Nota : Anders Kaseorg ha recibido la aceptación por ahora, para llamar la atención sobre su gran respuesta, ¡pero el desafío no ha terminado! Todavía hay una recompensa de 400 puntos en la oferta para cualquiera que obtenga el puntaje más alto sin usar la compresión incorporada.
A continuación se muestra una 386x320representación png de la noche estrellada de Van Gogh.
Su objetivo es reproducir esta imagen lo más cerca posible, en no más de 1024 bytes de código. Para los propósitos de este desafío, la cercanía de las imágenes se mide por las diferencias al cuadrado en los valores de píxeles RGB, como se explica a continuación.
Este es un desafío de código . Las puntuaciones se calculan utilizando el script de validación a continuación. El puntaje más bajo gana.
Su código debe obedecer las siguientes restricciones:
- Debe ser un programa completo.
- Debe generar una imagen en un formato que pueda leer el script de validación que se encuentra a continuación, ejecutándose en mi máquina. El script utiliza la biblioteca PIL de Python, que puede cargar una amplia variedad de formatos de archivo , incluidos png, jpg y bmp.
- Debe ser completamente autónomo, sin entrada ni carga de archivos (aparte de importar bibliotecas, lo cual está permitido)
- Si su idioma o biblioteca incluye una función que emite Starry Night, no puede usar esa función.
- Debe ejecutarse de manera determinista, produciendo la misma salida cada vez.
- Las dimensiones de la imagen de salida deben ser
386x320 - Para evitar dudas: las respuestas válidas deben usar lenguajes de programación según las reglas habituales de PPCG . Debe ser un programa que muestre una imagen, no solo un archivo de imagen.
Es probable que algunas presentaciones sean generadas por el código. Si este es el caso, incluya en su respuesta el código que se utilizó para generar su envío y explique cómo funciona. Las restricciones anteriores solo se aplican al programa generador de imágenes de 1kB que envíe; no se aplican a ningún código utilizado para generarlo.
Puntuación
Para calcular su puntaje, tome su imagen de salida y el original anterior y convierta los valores de píxeles RGB a números de coma flotante que van de 0 a 1. El puntaje de un píxel es (orig_r-img_r)^2 +(orig_g-img_g)^2 + (orig_b-img_b)^2, es decir, la distancia al cuadrado en el espacio RGB entre las dos imágenes. La puntuación de una imagen es la suma de las puntuaciones de sus píxeles.
A continuación se muestra un script de Python que realiza este cálculo; en caso de inconsistencia o ambigüedad, la puntuación definitiva es la calculada por ese script que se ejecuta en mi máquina.
Tenga en cuenta que la puntuación se calcula en función de la imagen de salida, por lo que si utiliza un formato con pérdida que afectará la puntuación.
Cuanto más bajo sea el puntaje, mejor. La imagen original de Starry Night tendría una puntuación de 0. En el caso astronómicamente improbable de un empate, la respuesta con más votos determinará el ganador.
Objetivos de bonificación
Debido a que las respuestas estaban dominadas por soluciones que usaban compresión incorporada, otorgué una serie de recompensas a las respuestas que usan otras técnicas. El próximo será una recompensa de 400 puntos , que se otorgará si y cuando una respuesta que no utiliza compresión incorporada ocupa el primer lugar en general.
Las recompensas de bonificación otorgadas anteriormente fueron las siguientes:
Se otorgó una recompensa de 100 puntos a la respuesta de nneonneo , por ser la respuesta de mayor puntaje que no utilizaba la compresión incorporada en ese momento. Tenía 4852.87 puntos en el momento en que fue otorgado. Las menciones honoríficas van a 2012 Arcampion, que hizo un valiente intento de vencer a nneonneo utilizando un enfoque basado en la teselación de Voronoi , anotando 5076 puntos, y a Sleafar, cuya respuesta estuvo a la cabeza hasta el final, con 5052 puntos, utilizando un método similar a nneonneo
Se otorgó una recompensa de 200 puntos a la entrada de Strawdog . Esto fue otorgado por ser una estrategia basada en la optimización que tomó la delantera entre las respuestas de compresión no integradas y la mantuvo durante una semana. Obtuvo 4749.88 puntos utilizando un método impresionantemente inteligente.
Guión de puntuación / validación
El siguiente script de Python debe colocarse en la misma carpeta que la imagen de arriba (que debe nombrarse ORIGINAL.png) y ejecutarse con un comando del formulario python validate.py myImage.png.
from PIL import Image
import sys
orig = Image.open("ORIGINAL.png")
img = Image.open(sys.argv[1])
if img.size != orig.size:
print("NOT VALID: image dimensions do not match the original")
exit()
w, h = img.size
orig = orig.convert("RGB")
img = img.convert("RGB")
orig_pix = orig.load()
img_pix = img.load()
score = 0
for x in range(w):
for y in range(h):
orig_r, orig_g, orig_b = orig_pix[x,y]
img_r, img_g, img_b = img_pix[x,y]
score += (img_r-orig_r)**2
score += (img_g-orig_g)**2
score += (img_b-orig_b)**2
print(score/255.**2)
Nota técnica: Las medidas objetivas de similitud de imagen son algo complicado. En este caso, he optado por uno que sea fácil de implementar para todos, con pleno conocimiento de que existen medidas mucho mejores.
Tabla de clasificación
fuente
pip unistall PIL, luegopip install pillow) y cambiar la primera línea afrom PIL import Image.Respuestas:
Pyth (sin compresión incorporada), puntaje
4695.074656.034444.82La única funcionalidad relacionada con la imagen de Pyth es una función para escribir una matriz de tripletas RGB como un archivo de imagen. Entonces, la idea loca aquí es entrenar una pequeña red neuronal profunda en la función ( x , y ) ↦ ( r , g , b ) que representa la imagen, y ejecutarla en las coordenadas de cada píxel.
El plan
La red actual está construida a partir de 45 neuronas sigmoideas, con cada neurona conectada a las entradas x , yy a cada neurona anterior, y las últimas tres neuronas interpretadas como r , g , b . Está entrenado usando el algoritmo Adam sin lotes. Los parámetros que ponderan las conexiones 1125 se cuantifican en un rango de 93 valores posibles (excepto los términos constantes, que tienen 93 2 valores posibles) utilizando una variante de cuantificación estocástica , la variación principal es que establecemos el gradiente para los parámetros cuantificados a cero.
El resultado
El código
1023 bytes, codificados con
xxd(decodificar conxxd -r). He utilizado la versión 1.22.2016 de Pyth que era corriente cuando este desafío fue puesto en libertad. Puede ejecutar el código directamente en Pyth, pero Pyth en PyPy3 (pypy3 pyth starry.pyth) lo ejecuta nueve veces más rápido, en aproximadamente 3 minutos. La imagen de salida se escribe eno.png.Cómo funciona
Formación
Durante mi carrera final de entrenamiento, utilicé un programa de cuantificación mucho más lento e hice algunos cambios interactivos con eso y la tasa de aprendizaje, pero el código que usé fue más o menos el siguiente.
Visualización
Esta imagen muestra las activaciones de las 45 neuronas en función de las coordenadas x , y . Click para agrandar.
fuente
Mathematica, puntaje 14125.71333
Guarda esta imagen:
a
a.png.fuente
Java, 7399.80678201
Esto me recordó un proyecto que tenía en mi clase de computación numérica unos semestres atrás, que consistía en dibujar una silueta del Monte Everest utilizando la interpolación polinómica. Eso se hizo en MATLAB, pero no soy muy aficionado a MATLAB, así que decidí trabajar en Java. La idea básica detrás de esto es que elegí puntos "inteligentes" (leídos aquí como "aleatorios") para la interpolación polinómica. Con los pocos bytes que me quedaban, creé una forma de dibujar las estrellas, lo que sucede antes del dibujo de la montaña. Es posible condensar el código y agregar otro polinomio para el fondo para ayudar a mejorar la puntuación.
Editar: agregué y cambié algunos de los polinomios y agregué todas las estrellas. Mi puntaje anterior fue 9807.7168935, así que como pueden ver es una gran mejora. Desafortunadamente, el código tuvo un impacto en su legibilidad porque tuve que exprimir los últimos bytes para obtener todas las estrellas y darles grupos.
9807.7168935 puntos: 7399.80678201 puntos:
fuente
Python3.4 +, 4697.26
Utilicé el mismo método que en mi respuesta de ImageMagick, pero con los siguientes parámetros:
Usando estos parámetros, generé el siguiente programa Python de 1003 bytes (no encontré ninguna mejora sobre el método de salida de @ kennytm):
Lo que a su vez genera esta imagen:
fuente
1delatin1y guardar un espacio en blanco deimport *, por lo menos. Pero el golf no era una prioridad (ya que tiene menos de 1024 bytes).Python 3, puntaje 5701.31
Simplemente cambie el tamaño de una imagen PNG de 18 × 13.
fuente
Java, 8748.95
Otro enfoque:
Creé una clase que calcula un diagrama de Voronoi a partir de un conjunto de puntos dado. Este conjunto de puntos se usa como el conjunto de parámetros que sirve como entrada para el Apache BOBYQAOptimizer . La función de evaluación del optimizador toma los puntos y crea un diagrama voronoi a partir de ellos. Las regiones voronoi se colorean con el color promedio de la región correspondiente de la imagen original.
El proceso de optimización se muestra aquí:
La imagen final es esta:
que logra son puntaje de 8748.95
(Esto se midió con mi propia función, pero debería ser igual que con el script de evaluación)
El resultado de este proceso es solo un conjunto de 8 puntos y los colores correspondientes. (Un mayor número de puntos causó peores resultados, pero no probé esto muy extensamente).
El código resultante se muestra aquí (lo siento, tuve que jugarlo un poco para exprimirlo hasta el límite de 1kB):
(Lo sé, hay algunas maneras fáciles que podrían haber logrado mejores resultados, pero ... de alguna manera fue divertido ...)
En respuesta al comentario, en relación con el estilo artístico de una imagen voronoi con un mayor número de puntos: esto realmente parece interesante, y algunas herramientas de imagen realmente ofrecen esto como un "Filtro de mosaico", por ejemplo, el Filtro de mosaico en GIMP ( aunque esto ofrece opciones para enfatizar los bordes, etc.).
Aquí hay un ejemplo de la imagen de Starry Night, con 256 puntos. (Estos se seleccionan al azar, pero con un mayor número de puntos, la mejora que podría lograrse mediante una optimización desaparecerá).
Esto no es parte del concurso (ya que no cabe en 1kB), solo para los curiosos:
fuente
import java.util.*;De hecho, cambie todas las clases de importación a asteriscos.AutoIt ,
9183.257882.53ACTUALIZAR
Por lo tanto, resulta que volver a dibujar la imagen como un niño pequeño (borracho) es más efectivo que almacenar cualquier versión de la imagen. (Más eficaz que mi solución anterior de todos modos).
Cada línea que dibuja un elemento es crucial para disminuir la puntuación. Sospecho que este programa es capaz de lograr puntajes muy por debajo de 7000 con modificaciones muy pequeñas, porque cada cambio tiene efectos enormes (~ 20 a 100 puntos) en el puntaje. El programa usa mi
processingbiblioteca de gráficos que proporciona nombres de funciones concisos para dibujar usando GDI.Como esta solución implica aleatoriedad, sembramos el PRNG usando el valor constante
0usandoSRandom(0). ¿Por qué 0? Porque es hasta 50 puntos mejor que cualquier otron<=100que probé.El lienzo comienza como un espacio en blanco
#587092.Generando el piso
La parte inferior de la imagen (que resulta que comienza exactamente a 233 px [nuevamente, debido a los puntos]) está llena de
int(1e4*2.9)puntos suspensivos exactos . Cambiar el factor aquí (o un lugar decimal del factor) puede reducir y aumentar la puntuación en cientos de puntos. Me conformé con 2.9 después de algunos intentos. Naturalmente, esto llevará algún tiempo (unos segundos).Se suministra una paleta de cinco colores:
Manchas en el suelo
Se usan cuatro puntos suspensivos para establecer acentos contrastantes dentro del área del piso (
$4es un puntero de función paraellipse()):Generando acentos en el cielo
Algunas líneas se dibujan con un bolígrafo más grueso para representar áreas de color significativas dentro del cielo que se estiraron demasiado para las elipses:
Pesar los píxeles
Después de lo anterior, todo se enjuaga y repite hasta que nos quedemos sin bytes. Luego se aplica un desenfoque para engañar al método de validación. Por fuerza bruta, se ha determinado que un radio de exactamente 20 proporciona el mejor resultado. Esto mejora la puntuación en alrededor de 1.5k (!).
Imagen final
Código, 985 bytes
ANTIGUA RESPUESTA
Esto almacena 80 valores de color que forman una imagen de 10x8 px. Esta imagen sin procesar tiene una puntuación de 10291. Dado que 10x8 es un factor de pixelación de 40px, se aplica un desenfoque gaussiano utilizando un radio de 40px para reducir la puntuación. Así es como el script logra 9183.25.
Estos son los datos almacenados:
El archivo producido es True.png:
El programa tiene una longitud de 998 bytes :
fuente
1e4*2.9igual a29e3?Archivo BAT de Windows, puntuación 4458.854
El tamaño del programa es de 1024 bytes.
Convierte de imagen BPG codificada en base64 a PNG.
Utiliza certutil.exe (utilidad estándar de Windows) y el decodificador de imágenes bpgdec.exe como bibliotecas.
Compresión:
fuente
C ++ 11,
7441.681261056997.654348335198.16107651Más actualizaciones
Me gustaron tanto las elipses de Perl que tuve que probarlas en C ++ 11. Utilicé la cadena sin procesar para insertar bytes allí, pero por un tiempo recibí una ligera discrepancia con la puntuación que esperaba y el código generado. Resulta que en realidad no puede poner un 0x0d (Carriage Return) sin procesar, ya que g ++ lo convertirá a 0x0a (Nueva línea). Sinceramente, no estoy seguro de cuán legítima es esta fuente generada, pero compila y funciona en un par de mis máquinas.
También probé otro algoritmo, Adaptive Dimensional Search después de que el GA parecía estancado, solo para tratar de pulir el mínimo local y tal vez tener suerte y caer en otro pozo.
Con esto, C ++ 11 ofrece una puntuación sorprendentemente competitiva (mucho mejor de lo que habría imaginado inicialmente) ... Estoy bastante sorprendido de que pueda hacer esto con fstream como la única inclusión.
Texto (sí, las nuevas líneas están en la fuente real ... supongo que podría eliminarlas):
Hexdump:
Esta respuesta combina varios enfoques de las respuestas anteriores, que explicaré a continuación, desafortunadamente terminé teniendo que jugar un poco al programa para encajar en
944949 caracteres (segúnwc -c), por lo que ya no se parece mucho a C ++ (disculpas si Esto va en contra de las reglas del desafío, voy a intentar algunas mejoras en breve). Al principio no planeé esto, así que todavía no es completamente indescifrable y todavía hay mucha fruta baja.Resultados actualizados
Simplemente ejecutar el algoritmo genético por más tiempo ha producido un resultado ligeramente mejor; Sin embargo, dado que la convergencia se ha desacelerado significativamente, diría que este método en particular probablemente está comenzando a alcanzar el máximo (o he caído en un mínimo local profundo). Jugué al programa final un poco más para exprimir un par de rectángulos más (el generador sigue siendo el mismo, excepto que se aumentó el tamaño máximo del genoma).
La implementación del cruce entre individuos ayudará si el problema es un mínimo local profundo, pero dado que se mantuvo en el mismo rango durante un tiempo, estoy empezando a pensar que es tan bueno como lo es para la cantidad de rectángulos.
Versión Voronoi, 7331.92407536, 989 caracteres
Solía idea de Voronoi de Marco13 con mi código de GA. En realidad, esto no funcionó tan bien como esperaba. Solo pude apretar unos pocos puntos más que los rectángulos. Creo que la naturaleza potencialmente disjunta de los rectángulos debido a la superposición ayuda un poco a la puntuación. De todos modos, en realidad me gusta la forma en que esto se ve significativamente mejor, a pesar de la puntuación similar a mi primera entrada.
Resultados anteriores, 7441.68126105, 944 caracteres
Al igual que algunas de las otras entradas, el programa solo dibuja rectángulos superpuestos. Utiliza PPM binario ya que el formato es simple (el resultado es
a.ppm, pero cargué una versión png ya que a SE no le gustaba el PPM), y es completamente determinista.Explicación
La generación del PPM tomó una buena parte del código repetitivo, lo que significaba que no podía tener demasiados rectángulos incluso después de jugar un poco al golf. Probablemente se puedan incluir algunos más aquí para mejorar aún más la puntuación.
La verdadera magia es la lista de rectángulos. Similar a la respuesta de Wolfgang, utilicé un algoritmo genético para encontrarlos. En realidad, la implementación es en gran parte incompleta, ya que la recombinación entre individuos aún no ocurre, pero la mutación aún ocurre y la clasificación de estilo de torneo por aptitud mantiene a los mejores organismos en la próxima ronda. También se usa elitismo, ya que una copia del mejor individuo de la última ronda se mantiene en la siguiente ronda, por lo que el organismo más en forma siempre está al menos tan en forma como en la ronda anterior.
No miré demasiado de cerca el código de Wolfgang desde que comencé esto ayer, pero parece que también permite que el color varíe, lo que puede explicar la diferencia de puntaje.
Para mantener el espacio de búsqueda más pequeño, solo miré la posición del rectángulo; el color se calcula por el promedio por canal de los píxeles visibles de ese rectángulo ya que tenemos la imagen de origen (no creo que podamos hacer algo mejor que esto para ese rectángulo en particular, ya que esto minimiza la distancia al cuadrado).
Pondré un repositorio de github en las próximas ediciones si sigo trabajando en él, pero por ahora el código (de un solo archivo) está en pastebin . Compílelo en modo C ++ 11, (nota al margen, estoy bastante avergonzado por lo desordenado que es incluso para una sola vez).
También necesitará una imagen P3 PPM de noche estrellada llamada así
ORIGINAL.ppmpara que funcione. Puede descargar el archivo desde este GitHub Gist .fuente
i r,g,blugar de por separado, y se pueden descartar muchos espacios). No estaba seguro de si el programa debería generar el archivo directamente o si la conexión a stdout / stderr estaba bien.#include <fstream>? Además, suelte las nuevas líneas y póngalas todas en una línea, ya que C ++ necesita punto y coma de todos modosImageMagick, 4551.71
Utiliza el lenguaje de 'programación' de ImageMagick, usando las siguientes opciones (puede que tenga que escapar del
!):Suponiendo el siguiente archivo fuente de 968 bytes (dado como hexdump):
Produciendo esta imagen:
Probablemente se esté preguntando cómo generé el archivo de entrada, y la respuesta es bastante simple. Cambie el tamaño a 48x40 con el filtro Lanczos, use una paleta indexada de 20 colores y optimice el PNG resultante.
Utiliza
convert,pngquant,optipngyadvdef.fuente
=(tail +2 $0)truco de mi respuesta , puede crear un solo script ZSH que contenga tanto el script ImageMagick como el archivo de entrada PNG.Python 2, 4749.88
1018 bytes
Es probable que todos ya se hayan olvidado de este problema, excepto yo ...
Este problema me interesó demasiado, especialmente porque rápidamente se hizo evidente que los enfoques que utilizan algoritmos de compresión de imágenes definitivamente estaban a la cabeza, pero de alguna manera eran insatisfactorios desde el punto de vista estético. Los enfoques basados en la optimización de un conjunto de primitivas de dibujo eran de alguna manera más agradables desde el punto de vista estético del código, pero parecían bloqueados justo por encima del puntaje de 5000.
El método de nneonneo que no utilizaba una compresión de imagen estándar supera la marca de 5000, pero lo hace codificando una pequeña imagen y ampliándola.
Aquí hay un programa que usa solo primitivas de dibujo, se genera automáticamente mediante un método de optimización y logra obtener una puntuación de 4749.88.
que se ve así:
y el hexdump del código:
Utiliza una serie de trucos utilizados anteriormente aquí:
Como primera primitiva, coloco una línea de horizonte, dividiendo la imagen en dos bloques de colores diferentes. Después, como primitivo básico, utilicé un círculo arrastrado entre dos puntos. Esto me pareció vagamente como una pincelada, pero fue posible expresarlo en 7 bytes. Para el proceso de búsqueda, utilicé una búsqueda guiada de patrones. Continúa agregando alternativamente un primitivo y optimizando sus parámetros. La primitiva se agrega en el punto donde el error con signo borroso es más alto. Los parámetros se optimizan mediante una exhaustiva optimización de línea en un dominio pequeño, uno tras otro. Se agregan entre cuarenta y cincuenta primitivas, y se optimizan individualmente. Luego, la lista de primitivas se reduce a tamaño desechando las primitivas que menos ayudan a la puntuación.
Esto todavía no supera el puntaje de nneonneo. Para superar ese puntaje, se requería una segunda etapa de optimización, que vuelve a pasar por el proceso de agregar primitivas en cada uno de los varios niveles de filtrado, y desechar las primitivas para recortar el programa generado a su tamaño. Lo que fue realmente interesante para mí fue la idea de aplicar esto a otras imágenes. Lo apliqué a un par de otras imágenes y proporciono más detalles y animación de las primitivas que se dibujan en mi blog aquí .
Los dos programas utilizados para generar esto en realidad no caben en el espacio permitido en las publicaciones de Stack Exchange, pero están en github: https://github.com/str4w/starrynight/tree/StackExchange
starrynight se ejecuta primero, seguido de stage2optimization. El programa resultante también está allí, en el mismo directorio.
fuente
Matlab, puntaje 5388.3
Sin ninguna compresión incorporada. La profundidad de color se reduce de manera que cada píxel se pueda representar con un carácter imprimible. Y la resolución se reduce. Esto se codifica como una cadena. El código en sí invierte todo el proceso. La operación de cambio de tamaño está utilizando un núcleo de interpolación Lanczos 3.
fuente
zsh + bpgdec, 4159.061760861207
Sí, otra solución de BPG. Creo que esto básicamente sirve para demostrar que BPG es la mejor utilidad de compresión de imágenes actualmente disponible. Considérelo una mejora sobre la solución BPG original de yallie .
El archivo tiene 1024 bytes de longitud, justo en el límite. Consiste en la linea
seguido de la salida de BPG sin procesar de
En hexadecimal, este es el script:
El archivo resultante es
out.png(labpgdecubicación predeterminada), que se ve así:Me parece bastante sorprendente que
bpg, en solo 996 bytes, haya reconstruido con precisión los contornos afilados del árbol, a la izquierda, y las colinas a la derecha. ¡Incluso tiene una aproximación aceptable para el campanario de la iglesia! El nivel de detalle es muy impresionante (para mí) para el pequeño tamaño de archivo. Por supuesto, enbpgdecsí mismo no es un programa pequeño, pero para mí está claro que BPG es un orden de magnitud mejor que JPEG para la compresión de imágenes.Debido a que esto usa
bpgdec, esta respuesta obviamente no es elegible para la recompensa.EDITADO:
-nargumento agregadotailpara hacerlo compatible con GNUtail.fuente
tail: cannot open ‘+2’ for reading. En Ubuntu necesita-n +2, lo que lo pone a 1025 bytes = /-n+2que lo coloca exactamente a 1024 bytes, pruébalo y avísame si eso funciona. Cambiaré mi respuesta por compatibilidad.C, 6641
999 bytes, usando solo
stdio.hymath.h.Hice una función de círculo relleno
d()que dibuja círculos concéntricos de colores RGB sobre valores de radio r..0. Aquí se usan 21 círculos. Podría exprimir un poco más si elimino más espacios en blanco, pero me gusta la relativa legibilidad tal como está.Descubrí la colocación aproximada del círculo usando capas Gimp en
Differencemodo. Busque los puntos brillantes, agregue un círculo, repita.HistogramHerramienta utilizada en la selección para determinar los colores iniciales a utilizar.Obtuve una puntuación de alrededor de 7700 usando lo anterior, pero pensé que podría hacerlo mejor ajustando los valores de color y radio, así que escribí un código de andamio para optimizar la fuerza bruta de cada valor al modificarlo -10 .. + 10, re renderizado, ejecutando el validador (que reescribí en C para velocidad) y guardando el valor que produjo la puntuación más baja. Al final, descarga la matriz de valores, que vuelvo a pegar en el código y recompilo. Realicé algunos pases y bajó el puntaje en aproximadamente 1000. Luego eliminé el código de andamio.
Código,
fuente
((x-xo)*(x-xo) + (y-yo)*(y-yo)) <= (r*r)) parece que sería más corta y eliminaría la dependenciamath.h. Con este tamaño de imagen, tampoco creo que nada tenga la posibilidad de desbordarse.Python 3, puntaje 5390.25, 998 bytes
Usé un programa de recocido simulado para ajustar rectángulos en la forma de Starry Night. Luego usa un desenfoque gaussiano para suavizar los bordes rectangulares rectos.
Para guardar algunos bytes, comprimí los datos del rectángulo en la base 94.
fuente
Python 2, 5238.59 puntos
Probablemente sea hora de publicar mi propia respuesta. Aquí está la imagen.
El código se ve así
O como un volcado hexadecimal:
Simplemente desempaqueta esa cadena larga en los parámetros para dibujar 95 elipses translúcidas.
Como muchas de las otras respuestas, el código se genera utilizando un algoritmo genético. Utiliza un tipo particular de algoritmo genético que inventé, al que llamo un "algoritmo de reserva genética", aunque es completamente posible que alguien más también lo haya inventado y le haya dado un nombre diferente. En lugar de tener una población de individuos, tenemos 95 "grupos genéticos", uno para cada gen. Cada grupo de genes contiene 10000 versiones diferentes del gen. Un gen contiene los parámetros para una elipse (posición, forma, color, alfa y su lugar en el orden z). En cada iteración creamos dos imágenes seleccionando un gen de cada uno de los 95 grupos, y los genes de la imagen con la puntuación más baja reemplazan los genes de la imagen con la peor puntuación, con una pequeña mutación.
Lo ejecuté hasta alrededor de la iteración 378000, que tomó un par de días. En ese momento, el puntaje seguía bajando, pero realmente muy lento, así que dudo que mejore mucho sin algunos cambios en el algoritmo.
Aquí está el código del algoritmo genético:
Finalmente, aquí hay una animación que muestra el algoritmo en funcionamiento. Muestra la mejor imagen generada hasta ahora después de cada 1000 iteraciones. (El archivo gif era demasiado grande para incrustarlo en esta publicación).
Probablemente se puede mejorar (1) usando el truco de codificación de nneonneo para meter más datos en la cadena; (2) agregar un desenfoque gaussiano al final del código de renderizado (pero eso lo hará más lento) y (3) mejorar aún más el algoritmo. Por el momento, alcanza un puntaje decente muy rápidamente, pero luego cambia muy lentamente después de eso; si de alguna manera reduzco la convergencia inicial, al final podría encontrar un mejor resultado. Quizás implemente estas cosas en algún momento.
fuente
Estrellado ,
11428.189450210904.307927710874.1307958Starry podría no ser el mejor lenguaje para hacer esto, sin embargo, es sin duda el más adecuado.
Puede probarlo en línea, sin embargo, parece que la salida está truncada, por lo que no obtendrá la imagen completa.
Este programa genera archivos ppm sin comprimir a la salida estándar.
Aquí está la salida del programa:
Explicación
Para que el programa produzca todos los 123.520 píxeles requeridos, dividí la imagen en 8 bandas horizontales y creé 7 bucles, los primeros 6 imprimen una banda, mientras que el último imprime dos bandas del mismo color. El código consiste en un encabezado, que le dice al archivo ppm cómo formatearse a sí mismo y los 7 bucles mencionados anteriormente.
fuente
Python 2, 4684.46
1021 bytes.
Esto usa un método de decodificación muy similar a un par de otras respuestas, pero está en Python 2, por lo que son datos codificados en base64 en lugar de base85.
Los datos codificados son una imagen de formato WebP de 64x48.
Aquí está el código que utilicé para encontrar la mejor configuración de tamaño y calidad de imagen. Restringí el espacio de búsqueda para que no demore más de unos minutos en ejecutarse.
fuente
Python 2,
5098.245080.044869.154852.874755.88589004¡No se utiliza descompresión incorporada! Solo la utilidad de cambio de tamaño de PIL y una imagen de 16 colores decodificada manualmente. Por lo tanto, debe ser elegible para la recompensa.
El programa contiene caracteres incrustados no ASCII. Tiene 1024 bytes de longitud y se ve así:
y en hexadecimal:
y genera esta imagen:
Este programa abusa del hecho de que básicamente puedes insertar bytes sin procesar en el código fuente de Python siempre que escapes de NUL y barras diagonales inversas.
El programa en sí consiste en una paleta de 16 entradas (la
|cadena separada) y una imagen de 40x41 de 16 colores (codificada con 4 bits por píxel, y decodificada por abuso.encode('hex')). La imagen se redimensiona al tamaño apropiado con un filtro bicúbico, y eso es todo.La imagen real se generó con ImageMagick:
y los datos de la paleta y la imagen se extrajeron del BMP resultante. (Tenga en cuenta que solicitamos 18 colores de ImageMagick, ya que IM inserta automáticamente algunas entradas no utilizadas).
La paleta se reorganizó ligeramente para reducir el número de caracteres escapados en los datos binarios, y los datos binarios finales se editaron un poco a mano para que todo encajara en 1024 bytes.
EDITADO: Golfé un poco el código y mejoré la precisión al solicitar 17 colores de ImageMagick.
EDITADO: Desactivar el dithering produjo una gran mejora en la puntuación. ¡Ahora tiene un puntaje muy por debajo de 5000 y se está volviendo competitivo con algoritmos de compresión estándar!
EDITADO: Agregar
-filter Cosineda otra mejora considerable. El golf agresivo, gracias a @primo por el truco BOM UTF-8, me permitió agregar otra fila a la imagen, mejorando aún más el puntaje.fuente
!realidad está flanqueado en ambos lados por caracteres no imprimibles. El color completo es#1d211e, que es un gris oscuro ligeramente azulado.#coding:latinlínea se puede reemplazar por una marca de orden de bytes UTF-8:(0xEF, 0xBB, 0xBF).zsh + FLIF + ImageMagick, 4358.14
Con BPG robando el foco de atención como un códec con pérdida, he refinado mi enfoque exclusivo sin pérdidas para usar FLIF en lugar de PNG, utilizando el truco zsh de @nneonneo. ImageMagick solo se usa aquí como escalador.
El hexdump (esta vez con
xxd, no me di cuenta que nohexdumpera estándar en mi última respuesta):He generado el script usando ... otro script:
fuente
Mathematica, 5076.54
Con un peso de exactamente 1024 bytes, finalmente logré superar el puntaje de nneonneo ... hasta que lo mejoró hace una hora = (
No utiliza algoritmos de compresión "listos para usar".
(Mejor descripción más adelante)
fuente
HTML / JavaScript,
10855.838000.55 (± ~ 5, basado en el navegador)Los puntajes pueden variar ligeramente debido a las diferencias de navegador o GPU.
Debe hacer clic con el botón derecho> Guardar imagen como para guardar los datos del lienzo como una imagen, pero esa es la única interacción que se requiere.
Utilicé GIMP para seleccionar ciertas áreas y encontrar su promedio. En particular, la herramienta de selección de color y la función de "diferencia de capa" fueron muy útiles.
Intento # 1 (10855.83)
Intento n. ° 2 (8000.55)
fuente
Scala, 6003.56
993 caracteres. Una importación es la biblioteca de imágenes scala . La segunda importación es el codificador base 91 .
Estos son los datos base91:
fuente
Java, puntaje 12251.19
Basado en esta respuesta de Mathematica , pero con más rectángulos. Probablemente continuaré modificando esto más tarde.
Resultados:
Algunas versiones anteriores:
fuente
Python 2 (sin compresión incorporada), puntaje 4497.730
Utiliza el mismo enfoque de imagen de 16 colores decodificado manualmente que mi respuesta anterior , pero esta vez en realidad apliqué una estrategia de optimización de descenso de gradiente para mejorar significativamente la puntuación. La presentación anterior obtuvo 4755.886 puntos, mientras que la nueva presentación obtuvo más de 250 puntos, superando muchos enfoques de compresión incorporados en el proceso.
Como antes, el programa final tiene exactamente 1024 bytes de longitud. De hecho, la salida sin formato del algoritmo de optimización contenía cuatro bytes que se escaparon (
\0), y que tuve que "falsificar" para reducir el recuento de bytes a 1024 bytes. Sin el dulce de azúcar, el programa de 1028 bytes obtendría 4490.685 - 7 puntos mejor.La idea básica es optimizar tanto la paleta como los datos conjuntamente. En una sola iteración, busco en todos los ajustes de la paleta (básicamente, cada paleta modificada que difiere en 1 en algún componente de color) y selecciono la paleta modificada que mejor mejora la puntuación. Luego, busco en todos los ajustes de los datos (cada matriz de índice modificada en la que un píxel se cambia a otra entrada de paleta) y elijo una modificación que reduce la puntuación (aquí no me importa lo mejor, porque no desea buscar infructuosamente el espacio completo de más de 25000 ajustes en cada iteración).
Finalmente, al generar la salida final del programa, ejecuto otra pasada de optimización que reorganiza la paleta para minimizar el número de barras invertidas requeridas en la salida final (por ejemplo, para el programa que se muestra a continuación, la paleta se reorganizó usando la tabla hexadecimal "0e3428916b7df5ca").
Este enfoque produjo una mejora numérica y perceptiva significativa sobre el enfoque anterior de ImageMagick. Salida de envío anterior:
Y nueva salida de envío:
El nuevo enfoque basado en la optimización tiene significativamente más detalles y una reproducción precisa del color.
Aquí está el hexdump del programa final:
Todavía hay espacio para mejorar. Por ejemplo, un histograma simple muestra que algunos colores apenas se usan:
Esto sugiere que una paleta reequilibrada podría mejorar la eficiencia, tal vez lo suficiente como para capturar la solución BPG de 5to lugar. Sin embargo, dudo mucho de que este enfoque de optimización (o realmente, cualquier cosa que no implique la maquinaria extraordinaria de H.265) pueda captar la implementación de BPG en primer lugar.
fuente
Perl
5955.968781245149.56218378Al observar el enfoque de "galimatías no imprimibles", decidí que también podría intentarlo en Perl. Nuevamente, no conozco realmente a Perl, así que estoy seguro de que esto puede mejorarse (en realidad, la mejora más obvia, la reducción a 7 bytes por elipse al omitir el canal alfa, ya se ha implementado para la próxima versión, pero yo ' Todavía estoy trabajando en otras partes de ese código; también estoy pensando que todo el negocio pop / push se puede jugar más).
No creo que esto realmente funcione en máquinas Windows (no puedo probar), ya que no pude encontrar una manera fácil de abrir la sección DATOS en modo binario, sin embargo, ha funcionado en mis máquinas Linux.
Básicamente pude seguir usando mi mismo código GA para crear:
Donde la salida xxd es:
Lo que genera la imagen:
Es interesante que a pesar de que obtiene mejores resultados, la imagen me parece algo peor: están pasando muchas cosas con todas las elipses adicionales, de alguna manera la imagen más simple es más fácil de manejar visualmente.
Resultados antiguos
Después de ver la respuesta de jamieguinan , usé elipses como un dibujo primitivo ya que en Perl tengo acceso a la biblioteca GD para dibujar. No soy un experto en Perl en absoluto, por lo que cualquier sugerencia sería útil. Utilicé un algoritmo genético que se modificó a partir de mi respuesta de C ++ .
Parece funcionar bien, pero honestamente estoy un poco decepcionado con el puntaje. Probablemente podría dejarlo funcionar un poco más, ya que puedes ver fácilmente que algunas elipses no están en posiciones óptimas. Sin embargo, incluso ahora se ve mejor a mis ojos en comparación con la solución basada en rectángulos.
fuente
Bash + Netpbm,
4558.54394.1ACTUALIZACIÓN: He mejorado el puntaje usando SPIHT en lugar de FIASCO.
SPIHT es un acrónimo de Particionamiento de conjuntos en árboles jerárquicos. Es un formato de compresión de imagen basado en wavelets altamente eficiente.
Me encogí el PNG original del trimestre, luego se convierte en PNM utilizando
pngtopnmdesde Netpbm v. 10.68, luego se retira la cabecera y se convierten los datos RAW a SPIHT concodecolr in.raw out.spi 80 96 0.95y obtuve el archivo de imagen de 913 bytes. Luego lo convertí de nuevo a RAW usandodecdcolr -s out.spi out.raw 0.95, luego convertí al formato PNMrawtoppm -bgr 96 80usandopamflip -tb, volteé usando , volví a escalar al tamaño original usandopamscale -xsize 386 -ysize 320 -filter sincy lo guardé en el archivo PNM, que es leído por PIL. Aquí está mi script (1 KB):Aquí está la salida PNG:
A continuación se muestra mi respuesta más simple:
FIASCO es un acrónimo de Fractal Image And Sequence COdec, es una implementación altamente eficiente de compresión fractal con pérdida .
Me encogí el PNG original del trimestre, luego se convierte en PNM utilizando
pngtopnmdesde Netpbm v. 10.68, luego se convierte en fiasco conpnmtofiasco -q=14 -z=3y obtuve el archivo de imagen de 969 bytes. Luego lo convertí de nuevo a PNM usandofiascotopnm, amplié al tamaño original usandopamscale -xyfill 386 320y lo guardé en el archivo PNM, que es leído por PIL. Aquí está mi script (1 KB):En realidad, primero hice esto en Windows
cmd, pero el script no cabía en 1 KB. Luego lo reescribíbash. Aquí está la salida PNG:fuente
Rubí, 7834.38
¡Esto fue divertido!
Utilicé un programa generador de ruby para escribir un script de ruby de la siguiente manera:
Mientras que el archivo ruby generado tiene menos de 1024 bytes:
Tenga en cuenta que mi algoritmo de puntuación muestra aleatoriamente un montón de colores y elige el que da como resultado la menor diferencia de ORIGINAL.png. Como es probabilístico, volví a ejecutar el guión varias veces y elegí el resultado de puntuación más bajo.
Aquí está mi mejor guión hasta ahora:
Generó la siguiente imagen, que obtuvo 7834 puntos:
Para ver cómo surgió mi algoritmo con esto, aquí hay un GIF animado que muestra cómo divide los rectángulos:
Mi código está en GitHub en https://github.com/jrotter/starry_night_contest
fuente
Java, 9215.38294502
Lectura de la imagen como GIF con un tamaño de 8x6 píxeles (!) De una cadena codificada en Base64 (que contiene 368 caracteres), y escalarla de forma bilineal.
EDITAR: El resultado, según lo solicitado en los comentarios, se muestra en esta imagen:
fuente
Python 3, 5797.125628604383
El programa de compresión primero trunca los bits de la imagen y luego convierte la base 2 en la base 36.
El programa de decodificación hace eso a la inversa y cambia el tamaño de la imagen.
fuente