Reto de codificación de imágenes de Twitter [cerrado]

Si una imagen vale más que 1000 palabras, ¿cuánto de una imagen puede caber en 140 caracteres?

Nota : ¡Eso es todo amigos! La fecha límite de la recompensa está aquí, y después de algunas duras deliberaciones, he decidido que la entrada de Boojum apenas superó a la de Sam Hocevar . Publicaré notas más detalladas una vez que haya tenido la oportunidad de escribirlas. Por supuesto, todos deberían sentirse libres de continuar presentando soluciones y mejorar las soluciones para que las personas voten. Gracias a todos los que presentaron y la entrada; Los disfruté todos. Ha sido muy divertido para mí correr, y espero que haya sido divertido tanto para los participantes como para los espectadores.

Me encontré con esta publicación interesante sobre tratar de comprimir imágenes en un comentario de Twitter, y muchas personas en ese hilo (y un hilo en Reddit ) tenían sugerencias sobre las diferentes formas en que puedes hacerlo. Entonces, supongo que sería un buen desafío de codificación; deje que las personas pongan su dinero donde está su boca y muestre cómo sus ideas sobre la codificación pueden conducir a más detalles en el espacio limitado que tiene disponible.

Te reto a que encuentres un sistema de propósito general para codificar imágenes en mensajes de Twitter de 140 caracteres y decodificarlas nuevamente en una imagen. Puede usar caracteres Unicode, por lo que obtiene más de 8 bits por carácter. Sin embargo, incluso teniendo en cuenta los caracteres Unicode, deberá comprimir las imágenes en una cantidad muy pequeña de espacio; esto sin duda será una compresión con pérdida, por lo que tendrá que haber juicios subjetivos sobre qué tan bien se ve cada resultado.

Aquí está el resultado que el autor original, Quasimondo , obtuvo de su codificación (la imagen está licenciada bajo una licencia Creative Commons Reconocimiento-No comercial ):

¿Puedes hacerlo mejor?

Reglas

1. Su programa debe tener dos modos: codificación y decodificación .
2. Al codificar :
   1. Su programa debe tomar como entrada un gráfico en cualquier formato gráfico de trama razonable que elija. Diremos que cualquier formato de trama admitido por ImageMagick cuenta como razonable.
   2. Su programa debe generar un mensaje que se pueda representar en 140 o menos puntos de código Unicode; 140 puntos de código en el rango de U+0000- U+10FFFF, con exclusión de los no caracteres ( U+FFFE, U+FFFF, U+nFFFE , U+nFFFF , donde n es 1- 10hexadecimal, y la gama U+FDD0- U+FDEF) y puntos de código de sustitución ( U+D800- U+DFFF). Puede salir en cualquier codificación razonable de su elección; cualquier codificación admitida por GNUiconv se considerará razonable, y la codificación nativa de su plataforma o codificación local probablemente sea una buena opción. Consulte las notas de Unicode a continuación para obtener más detalles.
3. Al decodificar :
   1. Su programa debe tomar como entrada la salida de su modo de codificación .
   2. Su programa debe generar una imagen en cualquier formato razonable de su elección, como se definió anteriormente, aunque para los formatos de vector de salida también están bien.
   3. La salida de la imagen debe ser una aproximación de la imagen de entrada; cuanto más se acerque a la imagen de entrada, mejor.
   4. El proceso de decodificación puede no tener acceso a ninguna otra salida del proceso de codificación que no sea la salida especificada anteriormente; es decir, no puede cargar la imagen en algún lugar y generar la URL para que se descargue el proceso de decodificación, o algo así de tonto.

4. En aras de la coherencia en la interfaz de usuario, su programa debe comportarse de la siguiente manera:

   1. Su programa debe ser un script que pueda configurarse como ejecutable en una plataforma con el intérprete apropiado, o un programa que pueda compilarse en un ejecutable.
   2. Su programa debe tomar como primer argumento encodeo decodepara establecer el modo.

   3. Su programa debe recibir información de una o más de las siguientes maneras (si implementa el que toma nombres de archivos, también puede leer y escribir desde stdin y stdout si faltan nombres de archivo):

      1. Tome la entrada de entrada estándar y produzca salida en salida estándar.

         my-program encode <input.png >output.txt
         my-program decode <output.txt >output.png
         

      2. Tome datos de un archivo nombrado en el segundo argumento y produzca resultados en el archivo nombrado en el tercero.

         my-program encode input.png output.txt
         my-program decode output.txt output.png
         

5. Para su solución, publique:
   1. Su código, en su totalidad, y / o un enlace a él alojado en otro lugar (si es muy largo, o requiere muchos archivos para compilar, o algo así).
   2. Una explicación de cómo funciona, si no es inmediatamente obvio por el código o si el código es largo y las personas estarán interesadas en un resumen.
   3. Una imagen de ejemplo, con la imagen original, el texto que comprime y la imagen decodificada.
   4. Si está construyendo sobre una idea que alguien más tuvo, por favor atribuyala. Está bien intentar refinar la idea de otra persona, pero debe atribuirla.

Pautas

Estas son básicamente reglas que pueden romperse, sugerencias o criterios de puntuación:

1. La estética es importante. Estaré juzgando, y sugeriré que otras personas juzguen, en base a:
   1. Qué bien se ve la imagen de salida y cuánto se parece al original.
   2. Qué bonito se ve el texto. Gobbledigook completamente al azar está bien si tienes un esquema de compresión realmente inteligente, pero también quiero ver respuestas que conviertan las imágenes en poemas multilingües, o algo así. Tenga en cuenta que el autor de la solución original decidió usar solo caracteres chinos, ya que se veía mejor de esa manera.
   3. El código interesante y los algoritmos inteligentes siempre son buenos. Me gusta el código corto y directo, pero los algoritmos realmente inteligentes y complicados también están bien siempre que produzcan buenos resultados.
2. La velocidad también es importante, aunque no tan importante como lo bueno que es comprimir la imagen que haces. Prefiero tener un programa que pueda convertir una imagen en una décima de segundo que algo que ejecute algoritmos genéticos durante días.
3. Preferiré soluciones más cortas a las más largas, siempre que sean razonablemente comparables en calidad; la concisión es una virtud.
4. Su programa debe implementarse en un lenguaje que tenga una implementación disponible gratuitamente en Mac OS X, Linux o Windows. Me gustaría poder ejecutar los programas, pero si tienes una gran solución que solo se ejecuta bajo MATLAB o algo así, está bien.
5. Su programa debe ser lo más general posible; debería funcionar para tantas imágenes diferentes como sea posible, aunque algunas pueden producir mejores resultados que otras. En particular:
   1. Tener algunas imágenes integradas en el programa con las que coincide y escribe una referencia, y luego produce la imagen coincidente después de la decodificación, es bastante aburrido y solo cubrirá unas pocas imágenes.
   2. Un programa que puede tomar imágenes de formas simples, planas y geométricas y descomponerlas en un vector primitivo es bastante ingenioso, pero si falla en imágenes más allá de una cierta complejidad, probablemente sea insuficientemente general.
   3. Un programa que solo pueda tomar imágenes de una relación de aspecto fija particular pero que haga un buen trabajo con ellas también estaría bien, pero no es ideal.
   4. Puede encontrar que una imagen en blanco y negro puede obtener más información en un espacio más pequeño que una imagen en color. Por otro lado, eso puede limitar los tipos de imagen a los que es aplicable; las caras salen bien en blanco y negro, pero los diseños abstractos pueden no funcionar tan bien
   5. Está perfectamente bien si la imagen de salida es más pequeña que la entrada, mientras que es aproximadamente la misma proporción. Está bien si tiene que escalar la imagen para compararla con el original; Lo importante es cómo se ve.
6. Su programa debe producir resultados que realmente puedan pasar por Twitter y salir ilesos. Esto es solo una guía en lugar de una regla, ya que no pude encontrar ninguna documentación sobre el conjunto preciso de caracteres admitidos, pero probablemente debería evitar los caracteres de control, los caracteres combinados invisibles funky, los caracteres de uso privado y similares.

Rúbrica de puntuación

Como una guía general sobre cómo clasificaré las soluciones al elegir mi solución aceptada, digamos que probablemente evaluaré las soluciones en una escala de 25 puntos (esto es muy aproximado, y no voy a puntuar nada directamente, solo usando esto como una guía básica):

• 15 puntos sobre qué tan bien el esquema de codificación reproduce una amplia gama de imágenes de entrada. Este es un juicio subjetivo y estético.
  • 0 significa que no funciona en absoluto, devuelve la misma imagen cada vez, o algo
  • 5 significa que puede codificar algunas imágenes, aunque la versión decodificada se ve fea y es posible que no funcione en imágenes más complicadas
  • 10 significa que funciona en una amplia gama de imágenes y produce imágenes de aspecto agradable que en ocasiones pueden distinguirse
  • 15 significa que produce réplicas perfectas de algunas imágenes, e incluso para imágenes más grandes y complejas, proporciona algo que es reconocible. O, tal vez, no crea imágenes que sean bastante reconocibles, sino que produce bellas imágenes que se derivan claramente del original.
• 3 puntos por el uso inteligente del juego de caracteres Unicode
  • 0 puntos por simplemente usar todo el conjunto de caracteres permitidos
  • 1 punto por usar un conjunto limitado de caracteres que son seguros para transferir a través de Twitter o en una variedad más amplia de situaciones
  • 2 puntos por usar un subconjunto temático de caracteres, como solo ideógrafos Han o solo caracteres de derecha a izquierda
  • 3 puntos por hacer algo realmente bueno, como generar texto legible o usar caracteres que se parezcan a la imagen en cuestión
• 3 puntos para enfoques algorítmicos inteligentes y estilo de código
  • 0 puntos para algo que son 1000 líneas de código solo para reducir la imagen, tratarla como 1 bit por píxel y codificar en base64
  • 1 punto para algo que usa una técnica de codificación estándar y está bien escrito y es breve
  • 2 puntos para algo que introduce una técnica de codificación relativamente novedosa, o que es sorprendentemente corta y limpia
  • 3 puntos para un trazador de líneas que realmente produce buenos resultados, o algo que abre nuevos caminos en la codificación de gráficos (si esto parece un número bajo de puntos por abrir nuevos caminos, recuerde que un resultado tan bueno probablemente tendrá una puntuación alta en estética) también)
• 2 puntos por velocidad. Todo lo demás es igual, más rápido es mejor, pero los criterios anteriores son más importantes que la velocidad
• 1 punto por ejecutarse en software libre (de código abierto), porque prefiero el software libre (tenga en cuenta que C # seguirá siendo elegible para este punto siempre que se ejecute en Mono, del mismo modo el código MATLAB sería elegible si se ejecuta en GNU Octave)
• 1 punto por seguir realmente todas las reglas. Estas reglas se han vuelto un poco grandes y complicadas, por lo que probablemente acepte respuestas buenas que de otra manera obtendrían un pequeño detalle incorrecto, pero daré un punto adicional a cualquier solución que realmente siga todas las reglas

Imágenes de referencia

Algunas personas han pedido algunas imágenes de referencia. Aquí hay algunas imágenes de referencia que puede probar; Aquí se incrustan versiones más pequeñas, todas se vinculan a versiones más grandes de la imagen si las necesita:

Premio

Estoy ofreciendo una recompensa de 500 repeticiones (más las 50 que inicia StackOverflow) para la solución que más me gusta, según los criterios anteriores. Por supuesto, también animo a todos los demás a votar sobre sus soluciones favoritas aquí.

Nota sobre plazo

Este concurso se extenderá hasta que se acabe la recompensa, alrededor de las 6 PM del sábado 30 de mayo. No puedo decir la hora exacta en que terminará; Puede ser de 5 a 7 PM. Garantizaré que miraré todas las entradas enviadas antes de las 2 PM, y haré todo lo posible para mirar todas las entradas enviadas antes de las 4 PM; Si se presentan soluciones después de eso, es posible que no tenga la oportunidad de darles un vistazo justo antes de tener que tomar una decisión. Además, cuanto antes envíe, más posibilidades tendrá de votar para ayudarme a elegir la mejor solución, así que intente enviarlo antes que en la fecha límite.

Notas Unicode

También ha habido cierta confusión sobre exactamente qué caracteres Unicode están permitidos. El rango de posibles puntos de código Unicode es U+0000a U+10FFFF. Hay algunos puntos de código que nunca son válidos para usar como caracteres Unicode en cualquier intercambio abierto de datos; Estos son los no caracteres y los puntos de código sustituto . Noncharacters se definen en el 5.1.0 sección Unidode Standard 16.7 como los valores U+FFFE, U+FFFF, U+nFFFE , U+nFFFF , donde n es 1- 10hexadecimal, y la gama U+FDD0-U+FDEF. Estos valores están destinados a ser utilizados para uso interno específico de la aplicación, y las aplicaciones conformes pueden quitar estos caracteres del texto procesado por ellos. Los puntos de código sustituto, definidos en la sección 3.8 de Unicode Standard 5.1.0 como U+D800- U+DFFF, se utilizan para codificar caracteres más allá del plano multilingüe básico en UTF-16; por lo tanto, es imposible representar estos puntos de código directamente en la codificación UTF-16, y no es válido codificarlos en ninguna otra codificación. Así, para el propósito de este concurso, voy a permitir que cualquier programa que codifica imágenes en una secuencia de no más de 140 puntos de código Unicode de la gama U+0000- U+10FFFF, excluyendo todos los noncharacters y pares suplentes como se definió anteriormente.

Voy a preferir soluciones que utilizan únicamente caracteres asignados, y los aún mejores que utilizan subconjuntos inteligente de caracteres asignados o hacer algo interesante con el juego de caracteres que utilizan. Para obtener una lista de los caracteres asignados, consulte la base de datos de caracteres Unicode ; tenga en cuenta que algunos caracteres se enumeran directamente, mientras que otros se enumeran solo como el inicio y el final de un rango. También tenga en cuenta que los puntos de código sustituto se enumeran en la base de datos, pero están prohibidos como se mencionó anteriormente. Si desea aprovechar ciertas propiedades de los caracteres para hacer que el texto que imprime sea más interesante, hay una variedad de bases de datos de información de caracteres disponibles, como una lista de bloques de código con nombre y varias propiedades de caracteres..

Como Twitter no especifica el conjunto exacto de caracteres que admiten, seré indulgente con las soluciones que en realidad no funcionan con Twitter porque ciertos caracteres cuentan más o se eliminan ciertos caracteres. Se prefiere, pero no es obligatorio, que todas las salidas codificadas se puedan transferir sin daños a través de Twitter u otro servicio de microblogging como identi.ca . He visto cierta documentación que indica que la entidad de Twitter codifica <,> y &, y por lo tanto los cuenta como 4, 4 y 5 caracteres respectivamente, pero no lo he probado yo mismo, y su contador de caracteres de JavaScript no parece contarlos de esa manera.

Consejos y enlaces

• La definición de caracteres Unicode válidos en las reglas es un poco complicada. Elegir un solo bloque de caracteres, como los ideógrafos unificados CJK (U + 4E00 – U + 9FCF) puede ser más fácil.
• Puede utilizar bibliotecas de imágenes existentes, como ImageMagick o Python Imaging Library , para la manipulación de su imagen.
• Si necesita ayuda para comprender el juego de caracteres Unicode y sus diversas codificaciones, consulte esta guía rápida o estas Preguntas frecuentes detalladas sobre UTF-8 en Linux y Unix .
• Cuanto antes obtenga su solución, más tiempo tendré que verla (y otras personas que voten). Puede editar su solución si la mejora; Basaré mi recompensa en la versión más reciente cuando eche un vistazo a las soluciones.
• Si desea un formato de imagen fácil de analizar y escribir (y no desea simplemente usar un formato existente), le sugiero que use el formato PPM . Es un formato basado en texto con el que es muy fácil trabajar, y puede usar ImageMagick para convertir ay desde él.

Muy bien, aquí está el mío: nanocrunch.cpp y el archivo CMakeLists.txt para construirlo usando CMake. Se basa en la API Magick ++ ImageMagick para la mayor parte de su manejo de imágenes. También requiere la biblioteca GMP para aritmética bignum para su codificación de cadena.

Basé mi solución en la compresión de imágenes fractales, con algunos giros únicos. La idea básica es tomar la imagen, reducir una copia al 50% y buscar piezas en varias orientaciones que se parezcan a bloques no superpuestos en la imagen original. Se necesita un enfoque de fuerza bruta para esta búsqueda, pero eso hace que sea más fácil introducir mis modificaciones.

La primera modificación es que en lugar de solo mirar rotaciones y volteos de noventa grados, mi programa también considera orientaciones de 45 grados. Es un bit más por bloque, pero ayuda inmensamente a la calidad de imagen.

La otra cosa es que almacenar un ajuste de contraste / brillo para cada componente de color de cada bloque es demasiado costoso. En cambio, almaceno un color muy cuantificado (la paleta tiene solo 4 * 4 * 4 = 64 colores) que simplemente se mezcla en cierta proporción. Matemáticamente, esto es equivalente a un brillo variable y un ajuste de contraste constante para cada color. Desafortunadamente, también significa que no hay contraste negativo para voltear los colores.

Una vez que se calcula la posición, orientación y color para cada bloque, lo codifica en una cadena UTF-8. Primero, genera un bignum muy grande para representar los datos en la tabla de bloques y el tamaño de la imagen. El enfoque de esto es similar a la solución de Sam Hocevar: una especie de gran número con una raíz que varía según la posición.

Luego lo convierte en una base de cualquier tamaño del juego de caracteres disponible. De manera predeterminada, hace uso completo del conjunto de caracteres unicode asignado, menos los caracteres menores, mayores que, ampersand, control, combinando, y sustitutos y privados. No es bonito pero funciona. También puede comentar la tabla predeterminada y seleccionar ASCII de 7 bits para imprimir (excluyendo nuevamente <,> y & caracteres) o Ideógrafos unificados CJK en su lugar. La tabla de códigos de caracteres disponibles se almacena en una longitud de ejecución codificada con ejecuciones alternas de caracteres no válidos y válidos.

De todos modos, aquí hay algunas imágenes y tiempos (medidos en mi antiguo P4 de 3.0 GHz), y comprimidos a 140 caracteres en el conjunto unicode asignado completo descrito anteriormente. En general, estoy bastante satisfecho con cómo resultaron todos. Si tuviera más tiempo para trabajar en esto, probablemente trataría de reducir el bloqueo de las imágenes descomprimidas. Aún así, creo que los resultados son bastante buenos para la relación de compresión extrema. Las imágenes descomprimidas son poco impresionistas, pero me resulta relativamente fácil ver cómo los bits corresponden al original.

Logotipo de desbordamiento de pila (8.6s para codificar, 7.9s para decodificar, 485 bytes):
http://i44.tinypic.com/2w7lok1.png

Lena (32.8s para codificar, 13.0s para decodificar, 477 bytes):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

Mona Lisa (43.2s para codificar, 14.5s para decodificar, 490 bytes):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

Editar: CJK Unified Characters

Sam preguntó en los comentarios sobre el uso de esto con CJK. Aquí hay una versión de la Mona Lisa comprimida a 139 caracteres del conjunto de caracteres CJK Unified:

http://i43.tinypic.com/2yxgdfk.png 咏 璘 驞 凄 脒 鵚 据 蛥 鸂 拗 朐 朖 辿 韩 瀦 魷 歪 痫 栘 璯 緍 脲 蕜 抱 揎 頻 蓼 債 鑡 嗞 靊 寞 柮 嚛 嚵 籥 聚隤 慛 絖 銓 馿 渫 櫰 矍 昀 鰛 掾 撄 粂 敽 牙 稉 擎 蔍 螎 葙 峬 覧 絀 蹔 抆 惫 冧 笻 哜 搀 澐 芯 譶 辍 澮 垝 黟 偞 媄 童 竽 梀 韠 镰 猳 閺 狌 而 羶 閺伆 杇 婣 唆 鐤 諽 鷍 鴞 駫 搶 毤 埙 誖 萜 愿 旖 鞰 萗 勹 鈱 哳 垬 濅 鬒 秀 瞛 洆 认 気 狋 異 闥 籴 珵 仾 氙 熜 謋 繴 茴 晋 髭 杍 嚖 熥 勳 縿 餅 珝 勳擸 萿

Los parámetros de ajuste en la parte superior del programa que utilicé para esto fueron: 19, 19, 4, 4, 3, 10, 11, 1000, 1000. También comenté la primera definición de number_assigned y códigos, y descomenté el últimas definiciones de ellos para seleccionar el juego de caracteres unificado CJK.

archivos de imagen y fuente de python (versiones 1 y 2)

Versión 1 Aquí está mi primer intento. Actualizaré a medida que avance.

Tengo el logotipo SO hasta 300 caracteres casi sin pérdidas. Mi técnica utiliza la conversión al arte vectorial SVG, por lo que funciona mejor en el arte lineal. En realidad es un compresor SVG, aún requiere que el arte original pase por una etapa de vectorización.

Para mi primer intento, utilicé un servicio en línea para la traza PNG, sin embargo, hay MUCHAS herramientas gratuitas y no gratuitas que pueden manejar esta parte, incluida potrace (código abierto).

Aquí están los resultados

Logotipo SO original http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Logotipo SO decodificado original http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png Después de codificar y descodificación

Caracteres : 300

Tiempo : no medido pero prácticamente instantáneo (sin incluir los pasos de vectorización / rasterización)

La siguiente etapa será incrustar 4 símbolos (puntos de ruta SVG y comandos) por carácter unicode. Por el momento, mi compilación de Python no tiene compatibilidad con caracteres anchos UCS4, lo que limita mi resolución por carácter. También he limitado el rango máximo al extremo inferior del rango reservado unicode 0xD800, sin embargo, una vez que construyo una lista de caracteres permitidos y un filtro para evitarlos, teóricamente puedo empujar el número requerido de caracteres tan bajo como 70-100 para el logo arriba.

Una limitación de este método en la actualidad es que el tamaño de salida no es fijo. Depende del número de nodos / puntos del vector después de la vectorización. Automatizar este límite requerirá pixelar la imagen (lo que elimina el beneficio principal de los vectores) o repetir las rutas a través de una etapa de simplificación hasta alcanzar el recuento de nodos deseado (que actualmente estoy haciendo manualmente en Inkscape).

Versión 2

ACTUALIZACIÓN : v2 ahora está calificado para competir. Cambios:

• Entrada / salida de control de línea de comando y depuración
• Utiliza el analizador XML (lxml) para manejar SVG en lugar de expresiones regulares
• Paquetes de 2 segmentos de ruta por símbolo Unicode
• Documentación y limpieza
• Soporte style = "fill: color" y fill = "color"
• Ancho / alto del documento empaquetado en un solo carácter
• Color de ruta empaquetado en un solo carácter
• La compresión de color se logra al tirar 4 bits de datos de color por color y luego empaquetarlos en un personaje a través de la conversión hexadecimal.

Caracteres : 133

Tiempo : unos segundos

v2 decodificado http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png Después de codificar y decodificar (versión 2)

Como puede ver, hay algunos artefactos esta vez. No es una limitación del método, sino un error en alguna parte de mis conversiones. Los artefactos ocurren cuando los puntos están fuera del rango 0.0 - 127.0 y mis intentos de restringirlos han tenido un éxito mixto. La solución es simplemente reducir la imagen, sin embargo, tuve problemas para escalar los puntos reales en lugar de la mesa de trabajo o la matriz de grupo y ahora estoy demasiado cansado para preocuparme. En resumen, si sus puntos están en el rango admitido, generalmente funciona.

Creo que el pliegue en el medio se debe a un mango que se mueve hacia el otro lado de un mango al que está vinculado. Básicamente, los puntos están demasiado juntos en primer lugar. Ejecutar un filtro simplificado sobre la imagen de origen antes de comprimirlo debería solucionar esto y eliminar algunos caracteres innecesarios.

ACTUALIZACIÓN : Este método está bien para objetos simples, por lo que necesitaba una forma de simplificar caminos complejos y reducir el ruido. Solía Inkscape para esta tarea. He tenido suerte con la preparación de caminos innecesarios con Inkscape, pero no tuve tiempo de intentar automatizarlo. Hice algunos svgs de muestra usando la función 'Simplificar' de Inkscape para reducir el número de rutas.

Simplificar funciona bien, pero puede ser lento con tantos caminos.

ejemplo de autotrace http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png cornell box http://www.warriorhut.com/graphics/svg_to_unicode/cornell_box_simplified.png lena http://www.warriorhut.com/graphics /svg_to_unicode/lena_std_washed_autotrace.png

miniaturas rastreadas http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png

Aquí hay algunas tomas de ultra baja resolución. Estos estarían más cerca del límite de 140 caracteres, aunque también puede ser necesaria una compresión de ruta inteligente.

arreglado http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Simplificado y despejado.

trianglulated http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png Simplificado, despeckled y triangulado.

autotrace --output-format svg --output-file cornell_box.svg --despeckle-level 20 --color-count 64 cornell_box.png

ARRIBA: Rutas simplificadas usando autotrace .

Desafortunadamente, mi analizador no maneja la salida de autotrace, así que no sé cómo se pueden usar los puntos o hasta qué punto simplificar, lamentablemente hay poco tiempo para escribirlo antes de la fecha límite. Sin embargo, es mucho más fácil analizar que la salida de inkscape.

Mi solución completa se puede encontrar en http://caca.zoy.org/wiki/img2twit . Tiene las siguientes características:

• Tiempo de compresión razonable (alrededor de 1 minuto para alta calidad)
• Descompresión rápida (una fracción de segundo)
• Mantiene el tamaño de imagen original (no solo la relación de aspecto)
• Calidad de reconstrucción decente (en mi humilde opinión)
• La longitud del mensaje y el conjunto de caracteres (ASCII, CJK, símbolos) se pueden elegir en tiempo de ejecución
• La longitud del mensaje y el juego de caracteres se detectan automáticamente en el momento de la descompresión
• Embalaje de información muy eficiente.

http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png

蜥 秓 鋖 筷 聝 诿 缰 偺 腶 漷 庯 祩 皙 靊 谪 獜 岨 幻 寤 厎 趆 脘 搇 梄 踥 桻 理 戂 溥 欇 渹 裏 軱 骿 苸 髙 骟 市 簶 璨 粭 浧 鱉 捕 弫 潮 衍 蚙 瀹 潮玧 霫 鏓 蓕 戲 債 鼶 襋 躻 弯 袮 足 庭 侅 旍 凼 飙 驅 據 嘛 掔 倾 诗 籂 阉 嶹 婻 椿 糢 墤 渽 緛 赐 更 儅 棫 武 婩 縑 逡 荨 璙 杯 翉 珸 齸 陁 颗 鳣 齸擲 舥 攩 寉 鈶 兓 庭 璱 篂 鰀 乾 丕 耓 庁 錸 努 樀 肝 亖 弜 喆 蝞 躐 葌 熲 谎 蛪 曟 暙 刍 镶 媏 嘝 驌 慸 盂 氤 缰 殾 譑

Aquí hay una descripción general del proceso de codificación:

• El número de bits disponibles se calcula a partir de la longitud de mensaje deseada y el conjunto de caracteres utilizables
• La imagen de origen se segmenta en tantas celdas cuadradas como lo permiten los bits disponibles.
• Se afecta un número fijo de puntos (actualmente 2) a cada celda, con coordenadas iniciales y valores de color.
• Lo siguiente se repite hasta que se cumpla una condición de calidad:
  • Un punto se elige al azar
  • Se realiza una operación al azar en este punto (moviéndola dentro de su celda, cambiando su color)
  • Si la imagen resultante (ver el proceso de decodificación a continuación) está más cerca de la imagen de origen, la operación se mantiene
• El tamaño de la imagen y la lista de puntos están codificados en UTF-8

Y este es el proceso de decodificación:

• El tamaño de la imagen y los puntos se leen desde la transmisión UTF-8
• Para cada píxel en la imagen de destino:
  • Se calcula la lista de vecinos naturales.
  • El color final del píxel se establece como un promedio ponderado de los colores de sus vecinos naturales.

Lo que creo que es la parte más original del programa es el flujo de bits. En lugar de empaquetar valores alineados con bits ( stream <<= shift; stream |= value), empaque valores arbitrarios que no están en rangos de potencia de dos ( stream *= range; stream += value). Esto requiere cálculos bignum y, por supuesto, es mucho más lento, pero me da 2009.18 bits en lugar de 1960 cuando utilizo los 20902 caracteres CJK principales (son tres puntos más que puedo poner en los datos). Y cuando uso ASCII, me da 917.64 bits en lugar de 840.

Decidí optar por un método para el cálculo inicial de la imagen que hubiera requerido armamento pesado (detección de esquinas, extracción de características, cuantización de color ...) porque al principio no estaba seguro de que realmente ayudaría. Ahora me doy cuenta de que la convergencia es lenta (1 minuto es aceptable pero no obstante es lenta) y puedo tratar de mejorar eso.

El bucle de ajuste principal está ligeramente inspirado en el algoritmo de interpolación Direct Binary Seach (donde los píxeles se intercambian o voltean aleatoriamente hasta obtener un tono medio mejor). El cálculo de la energía es una simple distancia cuadrática media, pero primero realizo un filtro mediano de 5x5 en la imagen original. Un desenfoque gaussiano probablemente representaría mejor el comportamiento del ojo humano, pero no quería perder bordes afilados. También decidí no realizar recocidos simulados u otros métodos difíciles de ajustar porque no tengo meses para calibrar el proceso. Por lo tanto, el indicador de "calidad" solo representa el número de iteraciones que se realizan en cada punto antes de que finalice el codificador.

http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png

苉 憗 揣 嶕 繠 剳 腏 篮 濕 茝 霮 墧 蒆 棌 杚 蓳 縳 樟 赒 肴 飗 噹 砃 燋 任 朓 峂 釰 靂 陴 貜 犟 掝 喗 讄 荛 砙 矺 敨 鷾 瓔 亨 髎 芟 氲 簵 鸬 嫤 鉸 簵激 躙 憮 鄴 甮 槺 骳 佛 愚 猪 駪 惾 嫥 綖 珏 矯 坼 堭 颽 箽 赭 飉 訥 偁 箝 窂 蹻 熛 漧 衆 橼 愀 航 玴 毡 裋 頢 羔 恺 墎 嬔 鑹 楄 瑥 鶼 呍 蕖 抲 鸝 呍苾 绒 酯 嵞 脔 婺 污 囉 酼 俵 菛 琪 棺 则 辩 曚 鸸 職 銛 蒝 礭 鱚 蟺 稿 纡 醾 陴 鳣 尥 蟀 惘 鋁 髚 忩 祤 脤 养 趯 沅 况

Aunque no todas las imágenes se comprimen bien, me sorprenden los resultados y realmente me pregunto qué otros métodos existen para comprimir una imagen a 250 bytes.

También tengo pequeñas películas sobre la evolución del estado del codificador desde un estado inicial aleatorio y desde un estado inicial "bueno" .

Editar : así es como se compara el método de compresión con JPEG. A la izquierda, la imagen superior de 536 bytes de jamoes. A la derecha, Mona Lisa se comprimió a 534 bytes usando el método descrito aquí (los bytes mencionados aquí se refieren a bytes de datos, por lo tanto, ignorando los bits desperdiciados al usar caracteres Unicode):

http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png

Editar : acaba de reemplazar el texto CJK con las versiones más recientes de las imágenes.

Lo siguiente no es una presentación formal, ya que mi software no ha sido diseñado de ninguna manera para la tarea indicada. DLI puede describirse como un códec de imagen con pérdida de propósito general optimizador. Es el soporte de registro PSNR y MS-SSIM para la compresión de imágenes, y pensé que sería interesante ver cómo funciona para esta tarea en particular. Utilicé la imagen de Mona Lisa de referencia proporcionada y la reduje a 100x150, luego utilicé DLI para comprimirla a 344 bytes.

Mona Lisa DLI http://i40.tinypic.com/2md5q4m.png

Para comparar con las muestras comprimidas JPEG e IMG2TWIT, también utilicé DLI para comprimir la imagen a 534 bytes. El JPEG es de 536 bytes y el IMG2TWIT es de 534 bytes. Las imágenes se han ampliado a aproximadamente el mismo tamaño para facilitar la comparación. JPEG es la imagen de la izquierda, IMG2TWIT es el centro y DLI es la imagen de la derecha.

Comparación http://i42.tinypic.com/302yjdg.png

La imagen DLI logra preservar algunas de las características faciales, en particular la famosa sonrisa :).

La descripción general de mi solución sería:

1. Comienzo con el cálculo de la cantidad máxima de datos sin procesar que puede caber en 140 caracteres utf8.
   • (Supongo que utf8, que es lo que el sitio web original afirmaba que Twitter almacenaba en sus mensajes. Esto difiere de la declaración del problema anterior, que pide utf16).
   • Usando este utf8 faq , calculo que el número máximo de bits que puede codificar en un solo carácter utf8 es de 31 bits. Para hacer esto, usaría todos los caracteres que están en el rango U-04000000 - U-7FFFFFFF. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, hay 31 x, por lo que podría codificar hasta 31 bits).
   • 31 bits por 140 caracteres equivalen a 4340 bits. Divide eso entre 8 para obtener 524.5, y redondea eso a 542 bytes .
   • (Si nos limitamos a utf16, entonces solo podríamos almacenar 2 bytes por carácter, lo que equivaldría a 280 bytes).
2. Comprima la imagen hacia abajo utilizando la compresión jpg estándar.
   • Cambie el tamaño de la imagen para que sea aproximadamente 50x50px, luego intente comprimirla en varios niveles de compresión hasta que tenga una imagen lo más cercana posible a 542 bytes sin pasar.
   • Este es un ejemplo de la mona lisa comprimida a 536 bytes.
3. Codifique los bits sin procesar de la imagen comprimida en caracteres utf-8.
   • Reemplace cada x en los siguientes bytes: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, con los bits de la imagen.
   • Esta parte probablemente sería la parte donde la mayoría del código necesitaría ser escrito, porque actualmente no existe nada que haga esto.

Sé que pedías código, pero realmente no quiero pasar el tiempo para codificarlo. Pensé que un diseño eficiente al menos podría inspirar a alguien más a codificar esto.

Creo que el principal beneficio de mi solución propuesta es que está reutilizando la mayor cantidad posible de tecnología existente. Puede ser divertido intentar escribir un buen algoritmo de compresión, pero se garantiza que habrá un mejor algoritmo, probablemente escrito por personas que tienen un título en matemáticas superiores.

Sin embargo, otra nota importante es que si se decide que utf16 es la codificación preferida, entonces esta solución se desmorona. Los archivos JPEG realmente no funcionan cuando se comprimen a 280 bytes. Aunque, tal vez hay un mejor algoritmo de compresión que jpg para esta declaración de problema específica.

Bien, llego tarde al juego, pero sin embargo hice mi proyecto.

Es un algoritmo genético de juguete que utiliza círculos de colores translúcidos para recrear la imagen inicial.

caracteristicas:

• pura Lua Se ejecuta en cualquier lugar donde se ejecuta un intérprete de Lua.
• utiliza el formato netpbm P3
• viene con un conjunto completo de pruebas unitarias
• conserva el tamaño original de la imagen

Mis feautres:

• lento
• con estas limitaciones de espacio, conserva solo el esquema de color básico de la imagen inicial y un resumen general de algunas características de la misma.

Aquí hay un ejemplo de twit que representa a Lena: 犭 楊 谷 杌 蒝 螦 界 匘 玏 扝 匮 俄 归 晃 客 猘 摈 硰 划 刀 萕 码 摃 斢 嘁 蜁 嚎 耂 澹 簜 僨 砠 偑 婊 內 團 揕 忈 義 倨 襠 凁 梡岂 掂 戇 耔 攋 斘 眐 奡 萛 狂 昸 箆 亲 嬎 廙 栃 兡 塅 受 橯 恰 应 戞 优 猫 僘 瑩 吱 賾 卣 朸 杈 腠 綍 蝘 猕 屐 稱 悡 ​​詬 來 噩 压 罍 尕 熚 帤 厥 虤 熚虲 兙 罨 縨 炘 排 叁 抠 堃 從 弅 慌 螎 熰 標 宑 簫 柢 橙 拃 丨 蜊 缩 昔 儻 舭 勵 癳 冂 囤 璟 彔 榕 兠 摈 侑 蒖 孂 埮 槃 姠 璐 哠 眛 嫡 琠 枀 訜 苄 琠厇 廩 焛 瀻 严 啘 刱 垫 仔

El código está en un repositorio de Mercurial en bitbucket.org. Echa un vistazo a http://bitbucket.org/tkadlubo/circles.lua

El siguiente es mi enfoque del problema y debo admitir que este fue un proyecto bastante interesante para trabajar, definitivamente está fuera de mi ámbito normal de trabajo y me ha dado algo nuevo sobre lo que aprender.

La idea básica detrás de la mía es la siguiente:

1. Reduzca la muestra de la imagen en escala de grises de modo que haya un total de 16 tonos diferentes
2. Preforma RLE en la imagen
3. Empaquete los resultados en los caracteres UTF-16
4. Realice RLE en los resultados empaquetados para eliminar cualquier duplicación de caracteres

Resulta que esto funciona, pero solo hasta cierto punto, como puede ver en las imágenes de muestra a continuación. En términos de salida, lo que sigue es un tweet de muestra, específicamente para la imagen de Lena que se muestra en las muestras.

乤 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 2 企 伂 8 企 伂 3 企 伂 5 企 倂 倃 伂 倁 3 企 儁 企 2 伂 倃 5 企 倁 3 企 倃 4 企 倂 企 倁 企伂 2 企 伂 5 企 倁 企 伂 쥹 皗 鞹 鐾 륶 䦽 阹 럆 䧜 椿 籫 릹 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 㞳 鞷 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 殞 焻 乹 Ꮛ 靆 䍼

Como puede ver, intenté restringir un poco el conjunto de caracteres; Sin embargo, me encontré con problemas al hacer esto al almacenar los datos de color de la imagen. Además, este esquema de codificación también tiende a desperdiciar un montón de bits de datos que podrían usarse para obtener información adicional de la imagen.

En términos de tiempos de ejecución, para imágenes pequeñas el código es extremadamente rápido, aproximadamente 55 ms para las imágenes de muestra proporcionadas, pero el tiempo aumenta con imágenes más grandes. Para la imagen de referencia de 512x512 de Lena, el tiempo de ejecución fue de 1182 ms. Debo señalar que las probabilidades son bastante buenas de que el código en sí no esté muy optimizado para el rendimiento (por ejemplo, todo funciona como un mapa de bits ), por lo que los tiempos podrían disminuir un poco después de una refactorización.

No dude en ofrecerme cualquier sugerencia sobre lo que podría haber hecho mejor o lo que podría estar mal con el código. La lista completa de tiempos de ejecución y salida de muestra se puede encontrar en la siguiente ubicación: http://code-zen.info/twitterimage/

Actualización uno

He actualizado el código RLE utilizado al comprimir la cadena de tweets para hacer una revisión básica y, de ser así, usarlo para la salida. Esto solo funciona para los pares de valores numéricos, pero guarda un par de caracteres de datos. El tiempo de ejecución es más o menos igual que la calidad de la imagen, pero los tweets tienden a ser un poco más pequeños. Actualizaré la tabla en el sitio web a medida que complete la prueba. Lo que sigue es una de las cadenas de tweets de ejemplo, nuevamente para la versión pequeña de Lena:

乤 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 5 企 倂 倃 伂 倁 グ 儁 企 2 伂 倃 ガ 倁 ジ 倃 4 企 倂 企 倁 企 伂 ツ 伂 ス 倁企 伂 쥹 皗 鞹 鐾 륶 䦽 阹 럆 䧜 椿 籫 릹 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 㞳 鞷 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 殞 焻 乹 Ꮛ 靆 䍼

Actualización dos

Otra pequeña actualización, pero modifiqué el código para empaquetar los tonos de color en grupos de tres en lugar de cuatro, esto usa un poco más de espacio, pero a menos que me falte algo, debería significar que los caracteres "extraños" ya no aparecen donde el color los datos son Además, actualicé la compresión un poco más para que ahora pueda actuar sobre toda la cadena en lugar de solo el bloque de recuento de colores. Todavía estoy probando los tiempos de ejecución, pero parecen estar nominalmente mejorados; sin embargo, la calidad de la imagen sigue siendo la misma. Lo que sigue es la versión más nueva del tuit de Lena:

2 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 5 企 倂 倃 伂 倁 グ 儁 企 2 伂 倃 ガ 倁 ジ 倃 4 企 倂 企 倁 企 伂 ツ 伂 ス 倁企 伂 坹 坼 坶 坻 刾 啩 容 力 吹 婩 媷 劝 圿 咶 坼 妛 啭 奩 嗆 婣 冷 咛 啫 凃 奉 佶 坍 均 喳 女 媗 决 兴宗 喓 夽 兴 唹 屹 冷 圶 埫 奫 唓 坤 喝 奎 似 坤商 嗉 乃

Logotipo de StackOverflow http://code-zen.info/twitterimage/images/stackoverflow-logo.bmp Cornell Box http://code-zen.info/twitterimage/images/cornell-box.bmp Lena http: // code-zen .info / twitterimage / images / lena.bmp Mona Lisa http://code-zen.info/twitterimage/images/mona-lisa.bmp

Este algoritmo genético que Roger Alsing escribió tiene una buena relación de compresión, a expensas de largos tiempos de compresión. El vector resultante de vértices podría comprimirse aún más utilizando un algoritmo con o sin pérdida.

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Sería un programa interesante de implementar, pero lo echaré de menos.

En el desafío original, el límite de tamaño se define como lo que Twitter aún le permite enviar si pega su texto en su cuadro de texto y presiona "actualizar". Como algunas personas notaron correctamente, esto es diferente de lo que podría enviar como mensaje de texto SMS desde su teléfono móvil.

Lo que no se menciona explícitamente (pero cuál era mi regla personal) es que debería poder seleccionar el mensaje twitteado en su navegador, copiarlo en el portapapeles y pegarlo en un campo de entrada de texto de su decodificador para que pueda mostrarlo. Por supuesto, también puede guardar el mensaje como un archivo de texto y volver a leerlo o escribir una herramienta que acceda a la API de Twitter y filtre cualquier mensaje que parezca un código de imagen (¿hay marcadores especiales para alguien? Guiño guiño ). Pero la regla es que el mensaje debe haber pasado por Twitter antes de que se le permita decodificarlo.

Buena suerte con los 350 bytes. Dudo que pueda utilizarlos.

Publicar una imagen monocromática o en escala de grises debería mejorar el tamaño de la imagen que puede codificarse en ese espacio ya que no le importa el color.

Posiblemente aumente el desafío de cargar tres imágenes que, cuando se combinan, le brindan una imagen a todo color sin dejar de mantener una versión monocromática en cada imagen separada.

Agregue un poco de compresión a lo anterior y podría comenzar a verse viable ...

¡¡¡Agradable!!! Ahora ustedes han despertado mi interés. No se trabajará durante el resto del día ...

En cuanto a la codificación / decodificación parte de este desafío. base16b.org es mi intento de especificar un método estándar para codificar de forma segura y eficiente los datos binarios en los planos Unicode superiores.

Algunas caracteristicas :

• Utiliza solo las áreas de usuario privadas de Unicode
• Codifica hasta 17 bits por carácter; casi tres veces más eficiente que Base64
• Se proporciona una implementación Javascript de codificación / decodificación de referencia
• Se incluyen algunas codificaciones de muestra, como Twitter y Wordpress.

Lo sentimos, esta respuesta llega demasiado tarde para la competencia original. Comencé el proyecto independientemente de esta publicación, que descubrí a mitad de camino.

La idea de almacenar un montón de imágenes de referencia es interesante. ¿Sería tan incorrecto almacenar unos 25 Mb de imágenes de muestra y hacer que el codificador intente componer una imagen usando bits de esas? Con una tubería tan minúscula, la maquinaria en cada extremo será necesariamente mucho mayor que el volumen de datos que pasan, entonces, ¿cuál es la diferencia entre 25Mb de código y 1Mb de código y 24Mb de datos de imagen?

(tenga en cuenta que las pautas originales descartaron restringir la entrada a las imágenes que ya están en la biblioteca; no estoy sugiriendo eso).

Estúpida idea, pero sha1(my_image)daría como resultado una representación "perfecta" de cualquier imagen (ignorando colisiones). El problema obvio es que el proceso de decodificación requiere cantidades excesivas de fuerza bruta.

Monocromo de 1 bit sería un poco más fácil. Cada píxel se convierte en 1 o 0, por lo que tendría 1000 bits de datos para una imagen de 100 * 100 píxeles. Como el hash SHA1 tiene 41 caracteres, podemos incluir tres en un solo mensaje, solo tenemos que forzar 2 conjuntos de 3333 bits y un conjunto de 3334 (aunque incluso eso probablemente todavía sea excesivo)

No es exactamente práctico. Incluso con la imagen de 100 bits y 100 píxeles de longitud fija, existe ... suponiendo que no calculo mal, 49995000 combinaciones o 16661667 cuando se dividen en tres.

def fact(maxu):
        ttl=1
        for i in range(1,maxu+1):
                ttl=ttl*i
        return ttl

def combi(setsize, length):
    return fact(length) / (fact(setsize)*fact(length-setsize))

print (combi(2, 3333)*2) + combi(2, 3334)
# 16661667L
print combi(2, 10000)
# 49995000L

Aquí esta compresión es buena.

http://www.intuac.com/userport/john/apt/

http://img86.imageshack.us/img86/4169/imagey.jpg http://img86.imageshack.us/img86/4169/imagey.jpg

Usé el siguiente archivo por lotes:

capt mona-lisa-large.pnm out.cc 20
dapt out.cc image.pnm
Pause

El tamaño de archivo resultante es de 559 bytes.

Idea: ¿Podría usar una fuente como paleta? Intente dividir una imagen en una serie de vectores tratando de describirlos con una combinación de conjuntos de vectores (cada carácter es esencialmente un conjunto de vectores). Esto está usando la fuente como diccionario. ¿Podría, por ejemplo, usar al para una línea vertical y a - para una línea horizontal? Solo una idea.