Desafío de encoding de imágenes de Twitter

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

Nota : ¡Eso es gente! La fecha límite de Bounty 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 deben sentirse libres de seguir presentando soluciones y mejorar las soluciones para que las personas voten. Gracias a todos los que enviaron y entrada; Los disfruté a 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 interesante publicación 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 maneras en que podría hacerlo. Entonces, me imagino que sería un buen desafío de encoding; permita que las personas pongan su dinero donde está su boca, y muestre cómo sus ideas sobre la encoding pueden llevar 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 decodificarlos en una imagen nuevamente. 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, tendrá que 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 bueno se ve cada resultado.

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

¿Puedes hacerlo mejor?

Reglas

  1. Su progtwig debe tener dos modos: encoding y deencoding .
  2. Cuando se codifica :
    1. Su progtwig debe tomar como entrada un gráfico en cualquier formato gráfico raster razonable de su elección. Diremos que cualquier formato de ttwig soportado por ImageMagick cuenta como razonable.
    2. Su progtwig debe generar un mensaje que se puede representar en 140 o menos puntos de código Unicode; 140 puntos de código en el rango U+0000U+10FFFF , excluyendo los caracteres ( U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF donde n es 110 hexadecimal, y el rango U+FDD0U+FDEF ) y puntos de código sustitutos ( U+D800U+DFFF ). Puede mostrarse en cualquier encoding razonable de su elección; cualquier encoding soportada por GNU iconv se considerará razonable, y la encoding nativa de la plataforma o la encoding local probablemente sea una buena opción. Ver notas Unicode a continuación para más detalles.
  3. Al decodificar :
    1. Su progtwig debe tomar como entrada la salida de su modo de encoding .
    2. Su progtwig debe mostrar una imagen en cualquier formato razonable de su elección, como se define anteriormente, aunque para formatos de salida de vectores también están bien.
    3. La salida de la imagen debe ser una aproximación de la imagen de entrada; cuanto más cerca se pueda llegar a la imagen de entrada, mejor.
    4. El proceso de deencoding puede no tener acceso a ninguna otra salida del proceso de encoding que no sea la salida especificada anteriormente; es decir, no puede cargar la imagen en algún lugar y generar la URL para el proceso de deencoding para descargar, o algo así de tonto.
  4. En aras de la coherencia en la interfaz de usuario, su progtwig debe comportarse de la siguiente manera:

    1. Su progtwig debe ser una secuencia de comandos que se puede establecer en ejecutable en una plataforma con el intérprete adecuado, o un progtwig que se puede comstackr en un archivo ejecutable.
    2. Su progtwig debe tomar como primer argumento encode o decode para establecer el modo.
    3. Su progtwig debe tomar entrada de una o más de las siguientes maneras (si implementa la que toma los nombres de archivo, también puede leer y escribir desde stdin y stdout si faltan nombres de archivo):

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

         my-program encode output.txt my-program decode output.png 
      2. Tome entrada 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, por favor publique:
    1. Su código, en su totalidad, y / o un enlace alojado en otro lugar (si es muy largo, o requiere muchos archivos para comstackr, o algo así).
    2. Una explicación de cómo funciona, si no es inmediatamente obvio desde 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 al que se comprime y la imagen decodificada.
    4. Si está construyendo sobre una idea que alguien más tenía, por favor atribuirlos. Está bien intentar hacer un refinamiento de la idea de otra persona, pero debes atribuirlos.

Lineamientos

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

  1. La estética es importante. Voy a juzgar y sugerir que otras personas juzguen, con base en:
    1. Qué bueno se ve la imagen de salida y cuánto se parece al original.
    2. Qué lindo se ve el texto. Completamente al azar gobbledigook está bien si tienes un esquema de compresión realmente inteligente, pero también quiero ver respuestas que conviertan imágenes en poemas mutli-linguales, o algo así de inteligente. 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 gustan los códigos cortos, claros y claros, pero los algoritmos realmente inteligentes también están bien, siempre y cuando 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 progtwig que puede convertir una imagen en una décima de segundo que algo que ejecutará 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 progtwig debe implementarse en un lenguaje que tenga una implementación libremente disponible en Mac OS X, Linux o Windows. Me gustaría poder ejecutar los progtwigs, pero si tienes una gran solución que solo funciona bajo MATLAB o algo así, está bien.
  5. Tu progtwig 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 progtwig que coincida y escriba una referencia, y luego produzca la imagen correspondiente al decodificar, es bastante cojo y solo cubrirá algunas imágenes.
    2. Un progtwig que puede tomar imágenes de formas geométricas simples, planas y descomponerlas en algún vector primitivo es bastante ingenioso, pero si falla en imágenes más allá de una cierta complejidad, es probablemente insuficientemente general.
    3. Un progtwig que solo puede tomar imágenes de una determinada relación de aspecto fija pero que hace 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, aunque tiene 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 progtwig debería producir resultados que en realidad podrían pasar por Twitter y salirse 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ías evitar los caracteres de control, los personajes combinados invisibles, los personajes de uso privado y demás.

Tabla de puntuación

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

  • 15 puntos por lo bien que el esquema de encoding 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 parece fea y puede no funcionar en absoluto en imágenes más complicadas
    • 10 significa que funciona en una amplia gama de imágenes y produce imágenes agradables que ocasionalmente pueden distinguirse
    • 15 significa que produce réplicas perfectas de algunas imágenes, e incluso para imágenes más grandes y complejas, da algo que es reconocible. O, tal vez, no crea imágenes que sean bastante reconocibles, pero 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 transferirlos 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 ideogtwigs Han o solo caracteres de derecha a izquierda
    • 3 puntos por hacer algo realmente limpio, como generar texto legible o usar personajes que se parecen a la imagen en cuestión
  • 3 puntos por enfoques algorítmicos inteligentes y estilo de código
    • 0 puntos para algo que son 1000 líneas de código solo para escalar la imagen, trátela como 1 bit por píxel, y base64 codifique esa
    • 1 punto para algo que utiliza una técnica de encoding estándar y está bien escrito y breve
    • 2 puntos por algo que introduce una técnica de encoding relativamente nueva, o que es sorprendentemente corta y limpia
    • 3 puntos por un trazador de líneas que realmente produce buenos resultados, o algo que abre nuevos caminos en la encoding de gráficos (si esto parece un número bajo de puntos para abrir nuevos caminos, recuerde que un resultado así de bueno probablemente tendrá un puntaje alto 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 para ejecutar en software libre (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 que de otro modo serían incorrectas, pero daré un punto extra 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 puedes probar; las versiones más pequeñas están integradas aquí, todas se vinculan a versiones más grandes de la imagen si las necesita:

Lena Mona Lisa Cornell Box StackOverflow Logo

Premio

Ofrezco una recompensa de 500 rep. (Más los 50 que StackOverflow activa) para la solución que más me gusta, según los criterios anteriores. Por supuesto, animo a todos los demás a votar aquí sobre sus soluciones favoritas.

Nota sobre la fecha límite

Este concurso se extenderá hasta que se acabe la recompensa, alrededor de las 6 p. M. Del sábado 30 de mayo. No puedo decir la hora exacta en que terminará; puede ser de 5 a 7 PM. Garantizaré que veré todas las entradas enviadas antes de las 2 PM, y haré todo lo posible para ver 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 una buena imagen antes de tomar una decisión. Además, cuanto antes envíe, más posibilidades tendrá de votar para poder ayudarme a elegir la mejor solución, así que intente enviarla antes en lugar de hacerlo 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+0000 a 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 noncaracters y los puntos de código sustituto . Los noncharacters se definen en el EstándardeDefault 5.1.0 sección 16.7 como los valores U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF donde n es 110 hexadecimal, y el rango U+FDD0U+FDEF . Estos valores están destinados a ser utilizados para el 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 Norma Unicode 5.1.0 sección 3.8 como U+D800U+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 encoding UTF-16, y no es válido codificarlos en cualquier otra encoding. Por lo tanto, a los fines de este concurso, permitiré que cualquier progtwig que codifica imágenes en una secuencia de no más de 140 puntos de código Unicode del rango U+0000U+10FFFF , excluyendo todos los noncharacters y pares sustitutos como se definió anteriormente.

Preferiré soluciones que usen solo caracteres asignados, e incluso mejores que utilicen subconjuntos inteligentes de caracteres asignados o hagan algo interesante con el conjunto de caracteres que usan. Para obtener una lista de los caracteres asignados, consulte la base de datos de caracteres Unicode ; tenga en cuenta que algunos personajes se enumeran directamente, mientras que algunos 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 prohibido como se mencionó anteriormente. Si desea aprovechar ciertas propiedades de los caracteres para hacer que el texto generado sea más interesante, hay una variedad de bases de datos de información de caracteres disponibles, como una lista de bloques de códigos 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 personajes cuentan con caracteres extra o ciertos se eliminan. Se prefiere pero no es obligatorio que todas las salidas codificadas puedan transferirse sin daños a través de Twitter u otro servicio de microblogging como identi.ca . He visto documentación que dice 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 complicado. Elegir un solo bloque de caracteres, como CJK Unified Ideographs (U + 4E00-U + 9FCF) puede ser más fácil.
  • Puede usar bibliotecas de imágenes existentes, como ImageMagick o Python Imaging Library , para la manipulación de su imagen.
  • Si necesita ayuda para comprender el conjunto 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 .
  • Mientras más pronto obtenga su solución, más tiempo tendré que mirar (y otras personas que voten). Puede editar su solución si la mejora; Voy a basar mi recompensa en la versión más reciente cuando eche un último vistazo a las soluciones.
  • Si quiere un formato de imagen fácil de analizar y escribir (y no quiere 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 convertirlo desde y hacia él.

Bien, aquí está el mío: nanocrunch.cpp y el archivo CMakeLists.txt para comstackrlo 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 la aritmética de bignum para su encoding 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 parecen a bloques que no se superponen 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 progtwig también considera las orientaciones de 45 grados. Es un bit más por bloque, pero ayuda muchísimo a la calidad de la imagen.

La otra cosa es que almacenar un ajuste de contraste / brillo para cada componente de color de cada bloque es demasiado caro. En cambio, almaceno un color muy cuantizado (la paleta tiene solo 4 * 4 * 4 = 64 colores) que simplemente se mezcla en alguna 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 de cada bloque, se codifica en una cadena UTF-8. En primer lugar, 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 base que varía según la posición.

Luego convierte eso en una base de cualquier tamaño del conjunto de caracteres disponible. De forma predeterminada, utiliza al máximo el conjunto de caracteres Unicode asignado, menos los caracteres menos, más que, ampersand, control, combinación y sustituto y privado. No es bonito, pero funciona. También puede comentar la tabla predeterminada y seleccionar ASCII imprimible de 7 bits (nuevamente excluyendo los caracteres <,> y &) o los Ideogtwigs unificados CJK. La tabla de los códigos de caracteres disponibles está almacenada en una longitud de ejecución codificada con ejecuciones alternas de caracteres inválidos y válidos.

De todos modos, aquí hay algunas imágenes y tiempos (como se midió en mi anterior P4 de 3.0 GHz), y comprimí a 140 caracteres en el conjunto unicode asignado completo descrito anteriormente. En general, estoy bastante satisfecho de cómo resultaron todos. Si tuviera más tiempo para trabajar en esto, probablemente trataría de reducir el carácter obsceno 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 un poco impresionistas, pero me resulta relativamente fácil ver cómo los bits se corresponden con el original.

Logotipo de desbordamiento de stack (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 juego de caracteres CJK Unified:

http://i43.tinypic.com/2yxgdfk.png咏 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 ng ng 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚 聚隤 慛 慛 慛 慛 隤 隤 隤 隤 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛 慛伆 杇 杇 杇 杇 伆 伆 伆 伆 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇 杇擸 萿

Los parámetros de ajuste en la parte superior del progtwig 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 se eliminó el comentario del últimas definiciones de ellos para seleccionar el conjunto de caracteres CJK Unified.

archivos de imagen y fuente de python (versión 1 y 2)

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

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

Para mi primer bash, utilicé un servicio en línea para el trazado 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

Original SO Logo http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Logotipo Original SO Descodificado http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png Después de la encoding y desencoding

Personajes : 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 versión python no tiene un amplio carácter compatible con UCS4, lo que limita mi resolución por personaje. También he limitado el rango máximo al extremo inferior del rango reservado de Unicode 0xD800; sin embargo, una vez que construyo una lista de caracteres permitidos y un filtro para evitarlos, teóricamente puedo presionar 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 vectoriales / puntos después de la vectorización. La automatización de 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 que se llegue al recuento de nodos deseado (que 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 comandos y depuración
  • Utiliza el analizador XML (lxml) para manejar SVG en lugar de regex
  • Paquetes 2 segmentos de ruta por símbolo unicode
  • Documentación y limpieza
  • Estilo de soporte = “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 tirando 4 bits de datos de color por color y luego empaquetándolos en un carácter mediante conversión hexadecimal.

Personajes : 133

Tiempo : unos segundos

v2 decoded http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png Después de la encoding y deencoding (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 salen del rango 0.0 – 127.0 y mis bashs de restringirlos han tenido un éxito mixto. La solución es simplemente escalar 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 al otro lado de un mango al que está vinculado. Básicamente, los puntos están demasiado juntos en primer lugar. Ejecutar un filtro de simplificación sobre la imagen de origen antes de comprimirlo debería solucionarlo y eliminar algunos caracteres innecesarios.

ACTUALIZACIÓN : Este método está bien para objetos simples, así que necesitaba una forma de simplificar rutas complejas y reducir el ruido. Usé Inkscape para esta tarea. He tenido un poco de suerte al preparar rutas innecesarias usando Inkscape, pero no tuve tiempo de intentar automatizarlo. He hecho 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 muchas rutas.

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 podría ser necesaria alguna compresión de ruta inteligente.

preparado http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Simplificado y despeinado.

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

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

ARRIBA: Trayectorias simplificadas usando autotrace .

Lamentablemente, mi analizador no maneja la salida de autotrace, por lo que no sé cómo se pueden usar los puntos o hasta qué punto se simplifica, lamentablemente hay poco tiempo para escribirlo antes de la fecha límite. Sin embargo, es mucho más fácil de 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 la 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 conjunto 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 aproximada del proceso de encoding:

  • La cantidad de bits disponibles se calcula a partir de la longitud de mensaje deseada y el juego de caracteres utilizable
  • La imagen de origen está segmentada en tantas celdas cuadradas como permitan los bits disponibles
  • Un número fijo de puntos (actualmente 2) se ve afectado en cada celda, con las coordenadas iniciales y los valores de color
  • Lo siguiente se repite hasta que se cumpla una condición de calidad:
    • Se elige un punto al azar
    • Una operación se realiza al azar en este punto (moviéndolo dentro de su celda, cambiando su color)
    • Si la imagen resultante (ver el proceso de deencoding 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 deencoding:

  • El tamaño de la imagen y los puntos se leen desde la secuencia UTF-8
  • Para cada píxel en la imagen de destino:
    • La lista de vecinos naturales se calcula
    • 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 progtwig es el flujo de bits. En lugar de empaquetar valores alineados con los bits ( stream <<= shift; stream |= value ), empaco valores arbitrarios que no están en los rangos de potencia-de-dos ( stream *= range; stream += value ). Esto requiere cálculos de bignum y, por supuesto, es mucho más lento, pero me da 2009.18 bits en lugar de 1960 cuando uso 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í no utilizar 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, cuantificación del 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 es lenta, no obstante) y puedo tratar de mejorar en eso.

El bucle de ajuste principal está ligeramente inspirado en el algoritmo de dithering Direct Binary Seach (donde los píxeles se intercambian aleatoriamente o se voltean hasta que se obtiene un mejor tono medio). El cálculo de la energía es una distancia raíz-media-cuadrado simple, pero primero realizo un filtro de mediana de 5x5 en la imagen original. Un desenfoque gaussiano probablemente representaría mejor el comportamiento del ojo humano, pero no quería perder los bordes afilados. También decidí evitar el recocido simulado u otros métodos difíciles de sintonizar porque no tengo meses para calibrar el proceso. Por lo tanto, el indicador de "calidad" simplemente 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, estoy sorprendido por 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 de la evolución del estado del codificador desde un estado inicial aleatorio y desde un estado inicial "bueno" .

Editar : aquí es cómo el método de compresión se compara con JPEG. A la izquierda, la imagen anterior de 536 bytes de jamoes. A la derecha, Mona Lisa se comprimió a 534 bytes utilizando el método descrito aquí (los bytes mencionados aquí se refieren a bytes de datos, ignorando así los bits desperdiciados usando 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.

The following isn’t a formal submission, since my software hasn’t been tailored in any way for the indicated task. DLI can be described as an optimizing general purpose lossy image codec. It’s the PSNR and MS-SSIM record holder for image compression, and I thought it would be interesting to see how it performs for this particular task. I used the reference Mona Lisa image provided and scaled it down to 100×150 then used DLI to compress it to 344 bytes.

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

For comparison with the JPEG and IMG2TWIT compressed samples, I used DLI to compress the image to 534 bytes as well. The JPEG is 536 bytes and IMG2TWIT is 534 bytes. Images have been scaled up to approximately the same size for easy comparison. JPEG is the left image, IMG2TWIT is center, and DLI is the right image.

Comparison http://i42.tinypic.com/302yjdg.png

The DLI image manages to preserve some of the facial features, most notably the famous smile :).

The general overview of my solution would be:

  1. I start with calculating the maximum amount of raw data that you can fit into 140 utf8 characters.
    • (I am assuming utf8, which is what the original website claimed twitter stored it’s messages in. This differs from the problem statement above, which asks for utf16.)
    • Using this utf8 faq , I calculate that the maximum number of bits you can encode in a single utf8 character is 31 bits. In order to do this, I would use all characters that are in the U-04000000 – U-7FFFFFFF range. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, there are 31 x’s, therefore I could encode up to 31 bits).
    • 31 bits times 140 characters equals 4340 bits. Divide that by 8 to get 524.5, and round that down to 542 bytes .
    • (If we restrict ourselves to utf16, then we could only store 2 bytes per character, which would equal 280 bytes).
  2. Compress the image down using standard jpg compression.
    • Resize the image to be approximately 50x50px, then attempt to compress it at various compression levels until you have an image that is as close to 542 bytes as possible without going over.
    • This is an example of the mona lisa compressed down to 536 bytes.
  3. Encode the raw bits of the compressed image into utf-8 characters.
    • Replace each x in the following bytes: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, with the bits from the image.
    • This part would probably be the part where the majority of the code would need to be written, because there isn’t anything that currently exists that does this.

I know that you were asking for code, but I don’t really want to spend the time to actually code this up. I figured that an efficient design might at least inspire someone else to code this up.

I think the major benefit of my proposed solution is that it is reusing as much existing technology as possible. It may be fun to try to write a good compression algorithm, but there is guaranteed to be a better algorithm out there, most likely written by people who have a degree in higher math.

One other important note though is that if it is decided that utf16 is the preferred encoding, then this solution falls apart. jpegs don’t really work when compressed down to 280 bytes. Although, maybe there is a better compression algorithm than jpg for this specific problem statement.

Okay, I’m late to the game, but nevertheless I made my project.

It’s a toy genetic algorithm that uses translucent colorful circles to recreate the initial image.

caracteristicas:

  • pure Lua. Runs anywhere where a Lua interpreter runs.
  • uses netpbm P3 format
  • comes with a comprehensive suite of unit tests
  • preserves original image size

Mis-feautres:

  • lento
  • at this space constraints it preserves only the basic color scheme of the initial image and a general outline of few features thereof.

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

original lenaencoded Lena

The code is in a Mercurial repository at bitbucket.org. Check out http://bitbucket.org/tkadlubo/circles.lua

The following is my approach to the problem and I must admit that this was quite an interesting project to work on, it is definitely outside of my normal realm of work and has given me a something new to learn about.

The basic idea behind mine is as follows:

  1. Down-sample the image gray-scale such that there were a total of 16 different shades
  2. Preform RLE on the image
  3. Pack the results into the UTF-16 characters
  4. Preform RLE on the packed results to remove any duplication of characters

It turns out that this does work, but only to a limited extent as you can see from the sample images below. In terms of output, what follows is a sample tweet, specifically for the Lena image shown in the samples.

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

As you can see, I did try and constrain the character set a bit; however, I ran into issues doing this when storing the image color data. Also, this encoding scheme also tends to waste a bunch of bits of data that could be used for additional image information.

In terms of run times, for small images the code is extremely fast, about 55ms for the sample images provided, but the time does increase with larger images. For the 512×512 Lena reference image the running time was 1182ms. I should note that the odds are pretty good that the code itself isn’t very optimized for performance (eg everything is worked with as a Bitmap ) so the times could go down a bit after some refactoring.

Please feel free to offer me any suggestions on what I could have done better or what might be wrong with the code. The full listing of run times and sample output can be found at the following location: http://code-zen.info/twitterimage/

Update One

I’ve updated the the RLE code used when compressing the tweet string to do a basic look back and if so so use that for the output. This only works for the number value pairs, but it does save a couple of characters of data. The running time is more or less the same as well as the image quality, but the tweets tend to be a bit smaller. I will update the chart on the website as I complete the testing. What follows is one of the example tweet strings, again for the small version of Lena:

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

Update Two

Another small update, but I modified the code to pack the color shades into groups of three as opposed to four, this uses some more space, but unless I’m missing something it should mean that “odd” characters no longer appear where the color data is. Also, I updated the compression a bit more so it can now act upon the entire string as opposed to just the color count block. I’m still testing the run times, but they appear to be nominally improved; however, the image quality is still the same. What follows is the newest version of the Lena tweet:

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

StackOverflow Logo 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

This genetic algorithm that Roger Alsing wrote has a good compression ratio, at the expense of long compression times. The resulting vector of vertices could be further compressed using a lossy or lossless algorithm.

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

Would be an interesting program to implement, but I’ll give it a miss.

In the original challenge the size limit is defined as what Twitter still allows you to send if you paste your text in their textbox and press “update”. As some people correctly noticed this is different from what you could send as a SMS text message from your mobile.

What is not explictily mentioned (but what my personal rule was) is that you should be able to select the tweeted message in your browser, copy it to the clipboard and paste it into a text input field of your decoder so it can display it. Of course you are also free to save the message as a text file and read it back in or write a tool which accesses the Twitter API and filters out any message that looks like an image code (special markers anyone? wink wink ). But the rule is that the message has to have gone through Twitter before you are allowed to decode it.

Good luck with the 350 bytes – I doubt that you will be able to make use of them.

Posting a Monochrome or Greyscale image should improve the size of the image that can be encoded into that space since you don’t care about colour.

Possibly augmenting the challenge to upload three images which when recombined give you a full colour image while still maintaining a monochrome version in each separate image.

Add some compression to the above and It could start looking viable…

¡¡¡Bonito!!! Now you guys have piqued my interest. No work will be done for the rest of the day…

Regarding the encoding/decoding part of this challenge. base16b.org is my attempt to specify a standard method for safely and efficiently encoding binary data in the higher Unicode planes.

Some features :

  • Uses only Unicode’s Private User Areas
  • Encodes up to 17 bits per character; nearly three times more efficient than Base64
  • A reference Javascript implementation of encode/decode is provided
  • Some sample encodings are included, including Twitter and WordPress

Sorry, this answer comes way too late for the original competition. I started the project independently of this post, which I discovered half-way into it.

The idea of storing a bunch of reference images is interesting. Would it be so wrong to store say 25Mb of sample images, and have the encoder try and compose an image using bits of those? With such a minuscule pipe, the machinery at either end is by necessity going to be much greater than the volume of data passing through, so what’s the difference between 25Mb of code, and 1Mb of code and 24Mb of image data?

(note the original guidelines ruled out restricting the input to images already in the library – I’m not suggesting that).

Stupid idea, but sha1(my_image) would result in a “perfect” representation of any image (ignoring collisions). The obvious problem is the decoding process requires inordinate amounts of brute-forcing..

1-bit monochrome would be a bit easier.. Each pixel becomes a 1 or 0, so you would have 1000 bits of data for a 100*100 pixel image. Since the SHA1 hash is 41 characters, we can fit three into one message, only have to brute force 2 sets of 3333 bits and one set of 3334 (although even that is probably still inordinate)

It’s not exactly practical. Even with the fixed-length 1-bit 100*100px image there is.., assuming I’m not miscalculating, 49995000 combinations, or 16661667 when split into three.

 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 

Here this compression is good.

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

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

I used the following batch file:

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

The resulting filesize is 559 bytes.

Idea: Could you use a font as a palette? Try to break an image in a series of vectors trying to describe them with a combination of vector sets (each character is essentially a set of vectors). This is using the font as a dictionary. I could for instance use al for a vertical line and a – for a horizontal line? Solo una idea.