Basado en el exitoso desafío de codificación de imágenes de Twitter en Stack Overflow.
Si una imagen vale más que 1000 palabras, ¿qué cantidad de una imagen puede caber en 114.97 bytes?
Te reto a que encuentres un método de propósito general para comprimir imágenes en un comentario estándar de Twitter que contenga solo texto ASCII imprimible .
Reglas:
- Debe escribir un programa que pueda tomar una imagen y generar el texto codificado.
- El texto creado por el programa debe tener como máximo 140 caracteres y solo debe contener caracteres cuyos puntos de código estén en el rango de 32-126, inclusive.
- Debe escribir un programa (posiblemente el mismo programa) que pueda tomar el texto codificado y generar una versión decodificada de la fotografía.
- Su programa puede usar bibliotecas y archivos externos, pero no puede requerir una conexión a Internet o una conexión a otras computadoras.
- El proceso de decodificación no puede acceder o contener las imágenes originales de ninguna manera.
- Su programa debe aceptar imágenes en al menos uno de estos formatos (no necesariamente más): mapa de bits, JPEG, GIF, TIFF, PNG. Si algunas o todas las imágenes de muestra no están en el formato correcto, puede convertirlas usted mismo antes de la compresión por su programa.
Juzgando:
Este es un desafío algo subjetivo, por lo que el ganador será (eventualmente) juzgado por mí. Centraré mi juicio en un par de factores importantes, enumerados a continuación en importancia decreciente:
- Capacidad para hacer un trabajo razonable de comprimir una amplia variedad de imágenes, incluidas las que no figuran como imagen de muestra
- Capacidad para preservar los contornos de los elementos principales de una imagen.
- Capacidad para comprimir los colores de los elementos principales de una imagen.
- Capacidad para preservar contornos y colores de los detalles menores en una imagen.
- Tiempo de compresión. Aunque no es tan importante como qué tan bien se comprime una imagen, los programas más rápidos son mejores que los programas más lentos que hacen lo mismo.
Su envío debe incluir las imágenes resultantes después de la descompresión, junto con el comentario de Twitter generado. Si es posible, también puede dar un enlace al código fuente.
Respuestas:
He mejorado mi método agregando compresión real. Ahora funciona haciendo iterativamente lo siguiente:
Reduzca el tamaño de la imagen conservando la relación de aspecto (si la imagen es en color, el croma se muestrea a 1/3 del ancho y alto de la luminancia)
Reduzca la profundidad de bits a 4 bits por muestra
Aplique la predicción mediana a la imagen, haciendo que la distribución de la muestra sea más uniforme
Aplique compresión de rango adaptativo a la imagen.
Vea si el tamaño de la imagen comprimida es <= 112
La imagen más grande que cabe en los 112 bytes se usa como la imagen final, con los dos bytes restantes para almacenar el ancho y la altura de la imagen comprimida, más una bandera que indica si la imagen está en color. Para la decodificación, el proceso se invierte y la imagen se amplía para que la dimensión más pequeña sea 128.
Hay margen de mejora, es decir, no todos los bytes disponibles se usan normalmente, pero creo que estoy a punto de disminuir significativamente los retornos para la disminución de resolución + compresión sin pérdidas.
Fuente C ++ rápida y sucia
Windows exe
Mona Lisa (13x20 luminancia, 4x6 croma)
Hindenburg (21x13 luminancia)
Montañas (luminancia 19x14, croma 6x4)
Formas 2D (21x15 luminancia, 7x5 croma)
fuente
Ir
Funciona dividiendo la imagen en regiones de forma recursiva. Intento dividir regiones con alto contenido de información y elegir la línea divisoria para maximizar la diferencia de color entre las dos regiones.
Cada división se codifica utilizando unos pocos bits para codificar la línea divisoria. Cada región de la hoja está codificada como un solo color.
La imagen de Hindenburg se ve bastante horrible, pero las otras me gustan.
fuente
Pitón
La codificación requiere numpy , SciPy y scikit-image .
La decodificación requiere solo PIL .
Este es un método basado en la interpolación de superpíxeles. Para comenzar, cada imagen se divide en 70 regiones de tamaño similar de color similar. Por ejemplo, la imagen del paisaje se divide de la siguiente manera:
El centroide de cada región está ubicado (hasta el punto ráster más cercano en una cuadrícula que no contiene más de 402 puntos), así como su color promedio (de una paleta de 216 colores), y cada una de estas regiones está codificada como un número de 0 a 86832 , capaz de almacenarse en 2.5 caracteres ascii imprimibles (en realidad 2.497 , dejando suficiente espacio para codificar un bit en escala de grises).
Si estás atento, es posible que hayas notado que 140 / 2.5 = 56 regiones, y no 70 como dije anteriormente. Sin embargo, tenga en cuenta que cada una de estas regiones es un objeto único y comparable, que puede enumerarse en cualquier orden. Debido a esto, podemos usar la permutación de las primeras 56 regiones para codificar las otras 14 , además de tener algunos bits restantes para almacenar la relación de aspecto.
Más específicamente, cada una de las 14 regiones adicionales se convierte en un número, y luego cada uno de estos números se concatenan juntos (multiplicando el valor actual por 86832 y sumando el siguiente). Este número (gigantesco) se convierte en una permutación en 56 objetos.
Por ejemplo:
dará salida:
La permutación resultante se aplica luego a las 56 regiones originales . El número original (y, por lo tanto, las 14 regiones adicionales ) también se puede extraer convirtiendo la permutación de las 56 regiones codificadas en su representación numérica.
Cuando
--greyscale
se usa la opción con el codificador, se usan 94 regiones en su lugar (separadas 70 , 24 ), con 558 puntos de trama y 16 tonos de gris.Al decodificar, cada una de estas regiones se trata como un cono 3D extendido hasta el infinito, con su vértice en el centroide de la región, como se ve desde arriba (también conocido como Diagrama de Voronoi). Los bordes se mezclan para crear el producto final.
Mejoras futuras
Las dimensiones de la Mona Lisa son un poco diferentes, debido a la forma en que estoy almacenando la relación de aspecto. Necesitaré usar un sistema diferente.Solucionado, suponiendo que la relación de aspecto original está en algún lugar entre 1:21 y 21: 1, lo que creo que es una suposición razonable.El Hindenburg podría mejorarse mucho. La paleta de colores que estoy usando solo tiene 6 tonos de gris. Si introdujera un modo solo en escala de grises, podría usar la información adicional para aumentar la profundidad del color, el número de regiones, el número de puntos de trama o cualquier combinación de los tres.He agregado una--greyscale
opción al codificador, que hace las tres.Las formas 2D probablemente se verían mejor con la mezcla desactivada. Probablemente agregaré una bandera para eso.Se agregó una opción de codificador para controlar la relación de segmentación y una opción de decodificador para desactivar la mezcla.y
El segundo codificado con la
--greyscale
opción.Codificado con la
--greyscale
opción.Codificado
--ratio 60
y decodificado con--no-blending
opciones.encoder.py
decoder.py
my_geom.py
fuente
PHP
OK, me tomó un tiempo, pero aquí está. Todas las imágenes en escala de grises. Los colores tomaron demasiados bits para codificar para mi método: P
Mona Lisa
47 colores monocromo cadena de
101 bytes.
Formas 2D
36 colores Monocromo Cadena de
105 bytes.
Hindenburg
62 colores monocromo
112 caracteres.
Montañas
63 Colores Monocromo
122 caracteres.
Mi metodo
Codifico mi flujo de bits con un tipo de codificación base64. Antes de que se codifique en texto legible, esto es lo que sucede.
Cargo la imagen de origen y la redimensiono a una altura o anchura máxima (según la orientación, vertical / horizontal) de 20 píxeles.
A continuación, vuelvo a colorear cada píxel de la nueva imagen para que coincida más en una paleta de 6 colores en escala de grises.
Una vez hecho esto, creo una cadena con cada color de píxel representado por las letras [AF].
Luego calculo la distribución de las 6 letras diferentes dentro de la cadena y selecciono el árbol binario más optimizado para la codificación en función de las frecuencias de las letras. Hay 15 posibles árboles binarios.
Comienzo mi flujo de bits con un solo bit,
[1|0]
dependiendo de si la imagen es alta o ancha. Luego uso los siguientes 4 bits en la secuencia para informar al decodificador qué árbol binario se debe utilizar para decodificar la imagen.Lo que sigue es la corriente de bits que representan la imagen. Cada píxel y su color está representado por 2 o 3 bits. Esto me permite almacenar al menos 2 y hasta 3 píxeles de información para cada carácter ASCII impreso. Aquí hay una muestra de árbol binario
1110
, que utiliza la Mona Lisa:Las letras E
00
y F10
son los colores más comunes en la Mona Lisa. A010
, B011
, C110
y D111
son los menos frecuentes.Los árboles binarios funcionan así: ir de bit a bit,
0
significa ir a la izquierda,1
significa ir a la derecha. Continúa hasta que golpees una hoja en el árbol o un callejón sin salida. La hoja en la que terminas es el personaje que deseas.De todos modos, codifico la picadura binaria en caracteres base64. Al decodificar la cadena, el proceso se realiza en reversa, asignando todos los píxeles al color apropiado, y luego la imagen se escala dos veces el tamaño codificado (máximo 40 píxeles, X o Y, lo que sea mayor) y luego se genera una matriz de convolución aplicado a todo para suavizar los colores.
De todos modos, aquí está el código actual: " enlace de pastebin "
Es feo, pero si ve algún margen de mejora, avíseme. Lo pirateé juntos como quiero. Aprendí mucho de este desafío. Gracias OP por publicarlo!
fuente
Mi primer intento Esto tiene margen de mejora. Creo que el formato en sí funciona, el problema está en el codificador. Eso, y me faltan bits individuales de mi salida ... mi (un poco más de calidad que aquí) el archivo terminó en 144 caracteres, cuando debería haber quedado algo. (y realmente desearía que hubiera, las diferencias entre estos y aquellos son notables). Sin embargo, aprendí, nunca sobreestimes lo grandes que son 140 caracteres ...
Lo reduzco a una versión modificada de la paleta RISC-OS, básicamente, porque necesitaba una paleta de 32 colores, y eso parecía un buen lugar para comenzar. Esto podría hacer con algunos cambios también, creo.
Lo divido en las siguientes formas: y divido la imagen en bloques de paleta (en este caso, 2x2 píxeles) de un color frontal y posterior.
Resultados:
Los siguientes son los tweets, los originales y cómo se decodifica el tweet
Sé que los colores están mal, pero en realidad me gusta la Monalisa. Si eliminé el desenfoque (que no sería demasiado difícil), es una impresión cubista razonable: p
Necesito trabajar en
Le daré un poco más de trabajo más tarde para tratar de arreglarlos, y mejoré el codificador. Esos 20 personajes extra más o menos hacen una gran cantidad de diferencia. Me gustaría que volvieran.
La fuente de C # y la paleta de colores están en https://dl.dropboxusercontent.com/u/46145976/Base96.zip , aunque, en retrospectiva, puede no funcionar perfectamente cuando se ejecuta por separado (ya que los espacios en los argumentos de los programas no funcionan) bien).
El codificador tarda menos de un par de segundos en mi máquina bastante promedio.
fuente
Dejé de tratar de mantener el color y me puse blanco y negro, ya que todo lo que probé con el color era irreconocible.
Básicamente, todo lo que hace es dividir píxeles en 3 partes aproximadamente iguales: negro, gris y blanco. Tampoco mantiene el tamaño.
Hindenburg
Mona Lisa
Montañas
Formas
Aquí está el programa.
python compress.py -c img.png
Comprimeimg.png
e imprime el tweet.python compress.py -d img.png
toma el tweet de stdin y guarda la imagen enimg.png
.fuente
Mi modesta contribución en R:
La idea es simplemente reducir el ráster (el archivo debe estar en png) a una matriz cuyo número de celdas sea inferior a 140, los tweets son entonces una serie de colores (en 64 colores) precedidos por dos caracteres que indican el número de filas y columnas de la trama.
fuente
No es una solución completa, solo poner el método por ahí. (Matlab)
Utilicé una paleta de 16 colores y 40 posiciones para crear un diagrama de voronoi ponderado . Se utilizó un algoritmo genético y un algoritmo simple de escalada para adaptarse a la imagen.
Álbum con imagen original y también tengo una versión de 16 bytes con 4 colores y posiciones fijas allí. :)
(¿Puedo cambiar el tamaño de la imagen aquí?)
fuente
C#
Actualización - Versión 2
Hice otro intento de esto, ahora usando MagickImage.NET ( https://magick.codeplex.com/ ) para codificar los datos JPEG, también escribí un código básico para procesar mejor los datos del encabezado JPEG (como sugirió primo), también usó GuassianBlur en la salida que ayuda a suavizar parte de la compresión JPEG. A medida que la nueva versión se adapta mejor, he actualizado mi publicación para reflejar el nuevo método.
Método
He intentado algo único (con suerte), en lugar de tratar de manipular la profundidad del color o la identificación del borde, o tratar de usar diferentes formas para reducir el tamaño de las imágenes, he usado el algoritmo JPEG con la máxima compresión en versiones reducidas de las imágenes, luego eliminando todo menos el "StartOfScan" ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) y algunos elementos clave del encabezado, puedo reducir el tamaño a una cantidad aceptable. Los resultados son realmente impresionantes para 140 caracteres, me da un nuevo respeto por los JPEG:
Hindenburg
Montañas
Mona Lisa
Formas
Código
Versión 2 - http://pastebin.com/Tgr8XZUQ
Realmente estoy empezando a extrañar ReSharper + Tengo muchas cosas que mejorar, todavía hay un montón de codificación difícil aquí, aunque es interesante meterse con eso (recuerda que necesitas MagickImage dll para que esto funcione en VS)
Original (en desuso): http://pastebin.com/BDPT0BKT
Todavía un poco desordenado.
fuente
Python 3
Método
Lo que el programa hace primero es reducir la imagen, disminuyendo considerablemente su tamaño.
En segundo lugar, convierte los valores rgb en binarios y corta los últimos dígitos.
Luego convierte los datos de la base 2 en la base 10, donde agrega las dimensiones de la imagen.
Luego convierte los datos en la base 10 a la base 95, utilizando todos los ascii que pude encontrar. Sin embargo, no pude usar / x01 y similares debido a su capacidad para negar la función que escribió el archivo de texto.
Y (para mayor ambigüedad), la función de decodificación lo hace a la inversa.
comprimir.py
decode.py
El grito
Mona Lisa
Esferas
fuente