Défi de l'encodage des images Twitter

Question

Si une image vaut 1000 mots, quelle quantité d'image pouvez-vous faire tenir en 140 caractères ?

Note : C'est fini les gars ! La date limite pour le Bounty est arrivée, et après quelques délibérations difficiles, j'ai décidé que Entrée de Boojum a été devancé de justesse Sam Hocevar's . Je publierai des notes plus détaillées dès que j'aurai eu l'occasion de les rédiger. Bien sûr, chacun doit se sentir libre de continuer à soumettre des solutions et à les améliorer pour que les gens puissent voter. Merci à tous ceux qui ont soumis une participation ; je les ai tous appréciés. J'ai pris beaucoup de plaisir à organiser ce concours, et j'espère qu'il en a été de même pour les participants et les spectateurs.

Je suis tombé sur ce post intéressant à propos de la compression d'images dans un commentaire Twitter, et de nombreuses personnes dans ce fil de discussion (et une sur Reddit ) avait des suggestions sur les différentes façons de procéder. Je me suis donc dit que cela ferait un bon défi de codage ; laissez les gens joindre l'acte à la parole et montrer comment leurs idées sur le codage peuvent conduire à plus de détails dans l'espace limité dont vous disposez.

Je vous mets au défi de trouver un système général permettant de coder des images dans des messages Twitter de 140 caractères et de les décoder en une image. Vous pouvez utiliser les caractères Unicode, ce qui vous permet d'obtenir plus de 8 bits par caractère. Cependant, même en tenant compte des caractères Unicode, vous devrez comprimer les images dans un espace très réduit ; il s'agira certainement d'une compression avec perte, et il faudra donc porter un jugement subjectif sur la qualité de chaque résultat.

Voici le résultat que l'auteur original a obtenu, Quasimondo de son encodage (l'image est protégée par une licence de Licence Creative Commons Attribution-Non Commerciale ) :

Pouvez-vous faire mieux ?

Règles

1. Votre programme doit avoir deux modes : codage et décodage .

2. Lorsque codage :

   1. Votre programme doit prendre en entrée un graphique dans n'importe quel format raisonnable. trame format graphique de votre choix. Nous dirons que tout format matriciel pris en charge par ImageMagick compte comme raisonnable.
   2. Votre programme doit produire un message qui peut être représenté par 140 points de code Unicode ou moins ; 140 points de code dans la plage suivante U+0000 - U+10FFFF à l'exclusion des non caractères ( U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF où n est 1 - 10 hexadécimal, et la plage U+FDD0 - U+FDEF ) et les points de code de substitution ( U+D800 - U+DFFF ). Il peut être édité dans n'importe quel encodage raisonnable de votre choix ; tout encodage supporté par GNU iconv sera considéré comme raisonnable, et l'encodage natif de votre plateforme ou l'encodage local sera probablement un bon choix. Voir Notes sur l'Unicode ci-dessous pour plus de détails.

3. Lorsque décodage :

   1. Votre programme devrait prendre comme entrée la sortie de votre codage mode.
   2. Votre programme doit produire une image dans le format raisonnable de votre choix, tel que défini ci-dessus, bien que les formats vectoriels soient également acceptables.
   3. L'image de sortie doit être une approximation de l'image d'entrée ; plus vous pouvez vous rapprocher de l'image d'entrée, mieux c'est.
   4. Le processus de décodage ne peut avoir accès à aucune autre sortie du processus de codage que celle spécifiée ci-dessus ; autrement dit, vous ne pouvez pas télécharger l'image quelque part et envoyer l'URL pour que le processus de décodage la télécharge, ou quelque chose de stupide de ce genre.

4. Pour des raisons de cohérence de l'interface utilisateur, votre programme doit se comporter comme suit :

   1. Votre programme doit être un script qui peut être défini comme exécutable sur une plate-forme dotée de l'interpréteur approprié, ou un programme qui peut être compilé en un exécutable.
   2. Votre programme doit prendre comme premier argument soit encode ou decode pour régler le mode.

   3. Votre programme doit prendre en entrée une ou plusieurs des manières suivantes (si vous implémentez celle qui prend les noms de fichiers, vous pouvez également lire et écrire à partir de stdin et stdout si les noms de fichiers sont manquants) :

      1. Prendre l'entrée d'une norme d'entrée et produire la sortie d'une norme de sortie.

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

      2. Prendre l'entrée d'un fichier nommé dans le deuxième argument, et produire la sortie dans le fichier nommé dans le troisième.

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

5. Pour votre solution, veuillez poster :

   1. Votre code, dans son intégralité, et/ou un lien vers celui-ci hébergé ailleurs (s'il est très long, ou nécessite de nombreux fichiers à compiler, ou autre).
   2. Une explication de son fonctionnement, si cela n'est pas immédiatement évident à partir du code ou si le code est long et que les gens seront intéressés par un résumé.
   3. Un exemple d'image, avec l'image originale, le texte qu'elle compresse, et l'image décodée.
   4. Si vous vous basez sur une idée que quelqu'un d'autre a eue, veuillez l'attribuer. Vous pouvez essayer de perfectionner l'idée de quelqu'un d'autre, mais vous doit les attribuer.

Directives

Il s'agit essentiellement de règles qui peuvent être enfreintes, de suggestions ou de critères de notation :

1. L'esthétique est importante. Je jugerai, et suggérerai que d'autres personnes jugent, en fonction de :
   1. La qualité de l'image de sortie, et sa ressemblance avec l'original.
   2. Comme le texte est beau. Un charabia complètement aléatoire est acceptable si vous disposez d'un système de compression vraiment intelligent, mais je veux aussi voir des réponses qui transforment des images en poèmes multilingues, ou quelque chose de ce genre. Notez que l'auteur de la solution originale a décidé d'utiliser uniquement des caractères chinois, car c'était plus joli ainsi.
   3. Un code intéressant et des algorithmes intelligents sont toujours bons. J'aime les codes courts, précis et clairs, mais les algorithmes complexes et intelligents ne posent pas de problème tant qu'ils donnent de bons résultats.
2. La vitesse est également importante, mais pas autant que la qualité de la compression de l'image. Je préfère avoir un programme capable de convertir une image en un dixième de seconde plutôt qu'un programme qui fera tourner des algorithmes génétiques pendant des jours.
3. Je préférerai les solutions courtes aux solutions plus longues, pour autant qu'elles soient de qualité raisonnablement comparable ; la concision est une vertu.
4. Votre programme doit être implémenté dans un langage dont l'implémentation est librement disponible sur Mac OS X, Linux ou Windows. J'aimerais être en mesure d'exécuter les programmes, mais si vous avez une excellente solution qui ne fonctionne que sous Mac OS X, Linux ou Windows, vous pouvez l'utiliser. MATLAB ou autre, c'est bien.
5. Votre programme doit être aussi général que possible ; il doit fonctionner pour autant d'images différentes que possible, bien que certaines puissent produire de meilleurs résultats que d'autres. En particulier :
   1. Le fait d'avoir quelques images intégrées dans le programme, qu'il fait correspondre et auxquelles il écrit une référence, puis qu'il produit l'image correspondante lors du décodage, est assez faible et ne couvrira que quelques images.
   2. Un programme capable de prendre des images de formes géométriques simples et plates et de les décomposer en une primitive vectorielle est plutôt intéressant, mais s'il échoue sur des images dépassant une certaine complexité, il n'est probablement pas assez général.
   3. Un programme qui ne peut prendre que des images d'un rapport d'aspect fixe particulier, mais qui fait du bon travail avec elles, serait également acceptable, mais pas idéal.
   4. Vous constaterez peut-être qu'une image en noir et blanc permet de faire entrer plus d'informations dans un espace plus restreint qu'une image en couleur. D'un autre côté, cela peut limiter les types d'images auxquels elle s'applique ; les visages ressortent bien en noir et blanc, mais les dessins abstraits ne s'en sortent pas aussi bien.
   5. Il n'y a pas de problème si l'image de sortie est plus petite que celle d'entrée, tout en ayant à peu près les mêmes proportions. Il n'y a pas de problème si vous devez mettre l'image à l'échelle pour la comparer à l'original ; ce qui est important, c'est son aspect.
6. Votre programme doit produire des résultats qui pourraient passer par Twitter et en sortir indemnes. Il s'agit plus d'une directive que d'une règle, car je n'ai pas pu trouver de documentation sur l'ensemble précis des caractères pris en charge, mais vous devriez probablement éviter les caractères de contrôle, les caractères de combinaison invisibles funky, les caractères d'usage privé, etc.

Rubrique de notation

En guise de guide général sur la façon dont je vais classer les solutions lors du choix de la solution acceptée, disons que j'évaluerai probablement les solutions sur une échelle de 25 points (c'est très approximatif, et je ne vais pas noter quoi que ce soit directement, je l'utilise juste comme une ligne directrice de base) :

• 15 points pour la façon dont le système de codage reproduit un large éventail d'images d'entrée. Il s'agit d'un jugement subjectif et esthétique.
  • 0 signifie qu'il ne fonctionne pas du tout, qu'il renvoie la même image à chaque fois, ou quelque chose comme ça.
  • 5 signifie qu'il peut coder quelques images, bien que la version décodée soit moche et qu'il puisse ne pas fonctionner du tout sur des images plus complexes.
  • 10 signifie qu'il fonctionne sur une large gamme d'images, et produit des images d'aspect agréable qui peuvent parfois être distinguées.
  • 15 signifie qu'il produit des répliques parfaites de certaines images, et même pour des images plus grandes et plus complexes, il donne quelque chose qui est reconnaissable. Ou bien, peut-être qu'il ne produit pas d'images tout à fait reconnaissables, mais de belles images qui sont clairement dérivées de l'original.
• 3 points pour une utilisation intelligente du jeu de caractères Unicode
  • 0 point pour l'utilisation de l'ensemble des caractères autorisés.
  • 1 point pour l'utilisation d'un ensemble limité de caractères qui sont sûrs pour être transférés sur Twitter ou dans une plus grande variété de situations.
  • 2 points pour l'utilisation d'un sous-ensemble thématique de caractères, par exemple uniquement les idéogrammes Han ou uniquement les caractères de droite à gauche.
  • 3 points pour faire quelque chose de vraiment bien, comme générer un texte lisible ou utiliser des caractères qui ressemblent à l'image en question.
• 3 points pour des approches algorithmiques astucieuses et un style de code
  • 0 point pour quelque chose qui représente 1000 lignes de code uniquement pour réduire l'échelle de l'image, la traiter comme un bit par pixel, et la coder en base64.
  • 1 point pour quelque chose qui utilise une technique d'encodage standard et qui est bien écrit et bref.
  • 2 points pour quelque chose qui introduit une technique de codage relativement nouvelle, ou qui est étonnamment court et propre.
  • 3 points pour un one liner qui produit réellement de bons résultats, ou quelque chose qui innove dans l'encodage graphique (si cela semble un faible nombre de points pour innover, rappelez-vous qu'un résultat aussi bon aura probablement un score élevé pour l'esthétique également).
• 2 points pour la vitesse. Toutes choses égales par ailleurs, la rapidité est préférable, mais les critères ci-dessus sont tous plus importants que la vitesse.
• 1 point pour l'exécution sur un logiciel libre (open source), parce que je préfère les logiciels libres (notez que C# sera toujours éligible pour ce point tant qu'il fonctionne sur Mono, de même que le code MATLAB serait éligible s'il fonctionne sur GNU Octave)
• 1 point pour avoir respecté toutes les règles. Ces règles sont devenues un peu grandes et compliquées, donc je vais probablement accepter des réponses autrement bonnes qui ont un petit détail de travers, mais je donnerai un point supplémentaire à toute solution qui suit réellement toutes les règles.

Images de référence

Certaines personnes ont demandé des images de référence. Voici quelques images de référence que vous pouvez essayer ; des versions plus petites sont intégrées ici, elles renvoient toutes à des versions plus grandes de l'image si vous en avez besoin :

Prix

J'offre un Prime de 500 points (plus les 50 que StackOverflow ajoute) pour la solution qui me plaît le plus, sur la base des critères ci-dessus. Bien sûr, j'encourage tous les autres à voter pour leurs solutions préférées ici aussi.

Note sur le délai

Ce concours se déroulera jusqu'à ce que la prime soit épuisée, soit vers 18 heures le samedi 30 mai. Je ne peux pas dire l'heure précise à laquelle il se terminera ; cela peut être entre 17 et 19 heures. Je vous garantis que je regarderai toutes les contributions soumises avant 14 heures, et je ferai de mon mieux pour regarder toutes les contributions soumises avant 16 heures ; si les solutions sont soumises après cela, je n'aurai peut-être pas la chance de les regarder équitablement avant de devoir prendre ma décision. En outre, plus vous soumettez tôt votre solution, plus vous aurez de chances de voter pour m'aider à choisir la meilleure solution, alors essayez de soumettre votre solution plus tôt plutôt que juste à la date limite.

Notes sur l'Unicode

Il y a également eu une certaine confusion sur les caractères Unicode autorisés. L'éventail des points de code Unicode possibles est le suivant U+0000 à U+10FFFF . Certains points de code ne sont jamais valables pour être utilisés comme caractères Unicode dans un échange ouvert de données ; il s'agit des points de code suivants non-caractères et le points de code de substitution . Les non-caractères sont définis dans le Norme Unidode 5.1.0 section 16.7 comme les valeurs U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF où n est 1 - 10 hexadécimal, et la plage U+FDD0 - U+FDEF . Ces valeurs sont destinées à être utilisées pour un usage interne propre à l'application, et les applications conformes peuvent supprimer ces caractères du texte qu'elles traitent. Les points de code de substitution, définis dans le Norme Unicode 5.1.0 section 3.8 comme U+D800 - U+DFFF sont utilisés pour encoder les caractères au-delà du plan multilingue de base dans l'UTF-16 ; il est donc impossible de représenter ces points de code directement dans l'encodage UTF-16, et il est invalide de les encoder dans tout autre encodage. Ainsi, pour les besoins de ce concours, j'autoriserai tout programme qui code des images en une séquence de 140 points de code Unicode au maximum parmi les suivants U+0000 - U+10FFFF à l'exclusion de tous les non-caractères et des paires de substituts tels que définis ci-dessus.

Je vais préférez les solutions qui n'utilisent que des caractères assignés, et encore mieux celles qui utilisent des sous-ensembles intelligents de caractères assignés ou qui font quelque chose d'intéressant avec le jeu de caractères qu'elles utilisent. Pour obtenir une liste des caractères attribués, consultez la page Base de données des caractères Unicode ; notez que certains caractères sont listés directement, tandis que d'autres ne sont listés que comme début et fin d'une plage. Notez également que les points de code de substitution sont répertoriés dans la base de données, mais sont interdits comme mentionné ci-dessus. Si vous souhaitez tirer parti de certaines propriétés des caractères pour rendre le texte que vous produisez plus intéressant, il existe un certain nombre de possibilités. diverses bases de données d'informations sur les caractères disponible, tel qu'un liste des blocs de code nommés et diverses propriétés des personnages .

Étant donné que Twitter ne précise pas le jeu de caractères exact qu'il prend en charge, je serai indulgent à l'égard des solutions qui ne fonctionnent pas réellement avec Twitter parce que certains caractères comptent en plus ou que certains caractères sont supprimés. Il est préférable, mais pas obligatoire, que toutes les sorties codées puissent être transférées sans dommage via Twitter ou un autre service de microblogging tel que identi.ca . J'ai vu une documentation indiquant que Twitter codait en entités <, > et &, et les comptait donc comme 4, 4 et 5 caractères respectivement, mais je n'ai pas testé cela moi-même, et leur compteur de caractères JavaScript ne semble pas les compter de cette façon.

Conseils et liens

• La définition des caractères Unicode valides dans les règles est un peu compliquée. Il peut être plus facile de choisir un seul bloc de caractères, comme les idéogrammes unifiés du CJK (U+4E00-U+9FCF).
• Vous pouvez utiliser des bibliothèques d'images existantes, comme ImageMagick ou Bibliothèque d'imagerie Python pour la manipulation de vos images.
• Si vous avez besoin d'aide pour comprendre le jeu de caractères Unicode et ses différents codages, consultez le site suivant ce guide rapide ou cette FAQ détaillée sur UTF-8 dans Linux et Unix .
• Plus tôt vous enverrez votre solution, plus j'aurai le temps (et les autres votants) de l'examiner. Vous pouvez modifier votre solution si vous l'améliorez ; je baserai ma prime sur la version la plus récente lorsque je jetterai un dernier coup d'œil aux solutions.
• Si vous voulez un format d'image facile à analyser et à écrire (et que vous ne voulez pas simplement utiliser un format existant), je vous suggère d'utiliser la fonction Format PPM . Il s'agit d'un format texte très facile à utiliser, et vous pouvez vous servir des éléments suivants ImageMagick pour convertir vers et à partir de celui-ci.

Journal d'édition

30 mai : date limite de remise des prix, sélection du gagnant.
28 mai : détails plus précis sur la date limite
28 mai : Nettoyage des liens, mention de PPM
Le 27 mai : Réorganisation et nettoyage des règles et directives ; ajout de conseils et de liens.
Le 26 mai : Mention des problèmes de délais et suppression du plafond souple de 100 lignes.
22 mai : Ajout d'images de référence, de clarifications sur Unicode et d'une ébauche de grille de notation.
21 mai : mise à jour pour autoriser 140 caractères Unicode arbitraires. Alors que le formulaire web Twitter compte par unités de code UTF-16, l'API autorise 140 caractères Unicode arbitraires, nous allons donc utiliser cette définition pour permettre plus de flexibilité.
21 mai : Ajout d'informations sur la date limite
21 mai : publication du défi original

Answer 1

fichiers d'image et source python (version 1 et 2)

Version 1 Voici ma première tentative. Je mettrai à jour au fur et à mesure.

J'ai réussi à réduire le logo de la SO à 300 caractères presque sans perte. Ma technique utilise la conversion en art vectoriel SVG, elle fonctionne donc mieux sur l'art linéaire. Il s'agit en fait d'un compresseur SVG, mais il faut quand même que l'image originale passe par une étape de vectorisation.

Pour ma première tentative, j'ai utilisé un service en ligne pour la trace PNG, mais il existe de nombreux outils gratuits et non gratuits qui peuvent gérer cette partie, notamment potrace (open-source).

Voici les résultats

Original Après le codage et le décodage

Personnages : 300

Temps : Non mesuré mais pratiquement instantané (hors étapes de vectorisation/rastérisation)

L'étape suivante consistera à intégrer 4 symboles (points de cheminement et commandes SVG) par caractère unicode. Pour le moment, ma version de python ne supporte pas les caractères UCS4, ce qui limite ma résolution par caractère. J'ai également limité la plage maximale à l'extrémité inférieure de la plage réservée de l'unicode 0xD800. Cependant, une fois que j'aurai établi une liste des caractères autorisés et un filtre pour les éviter, je pourrai théoriquement réduire le nombre de caractères requis à 70-100 pour le logo ci-dessus.

Une des limites de cette méthode est que la taille de la sortie n'est pas fixe. Elle dépend du nombre de nœuds/points vectoriels après vectorisation. Pour automatiser cette limite, il faudra soit pixeliser l'image (ce qui supprime le principal avantage des vecteurs), soit faire passer les chemins par une étape de simplification jusqu'à ce que le nombre de nœuds souhaité soit atteint (ce que je fais actuellement manuellement dans Inkscape).

Version 2

UPDATE : v2 est maintenant qualifié pour la compétition. Changements :

• Entrée/sortie de contrôle par ligne de commande et débogage
• Utilise l'analyseur XML (lxml) pour gérer le SVG au lieu de la regex.
• Packs 2 segments de chemin par symbole unicode
• Documentation et nettoyage
• Prise en charge de style="fill:color" et fill="color".
• Largeur/hauteur du document exprimée en un seul caractère
• Couleur du chemin emballée dans un seul caractère
• La compression des couleurs est obtenue en en éliminant 4bits de données de couleur par couleur, puis en l'intégrant dans un caractère via la conversion hexadécimale.

Personnages : 133

Temps : Quelques secondes

Après codage et décodage (version 2)

Comme vous pouvez le voir, il y a quelques artefacts cette fois. Ce n'est pas une limitation de la méthode mais une erreur quelque part dans mes conversions. Les artefacts se produisent lorsque les points sortent de la plage 0.0 - 127.0 et mes tentatives pour les contraindre ont eu un succès mitigé. La solution consiste simplement à réduire l'échelle de l'image, mais j'ai eu du mal à mettre à l'échelle les points réels plutôt que le tableau ou la matrice de groupe et je suis trop fatigué pour m'en soucier. En bref, si vos points sont dans la plage supportée, cela fonctionne généralement.

Je pense que le coude au milieu est dû au déplacement d'une poignée de l'autre côté de la poignée à laquelle elle est liée. En fait, les points sont trop proches les uns des autres. L'utilisation d'un filtre simplifié sur l'image source avant de la compresser devrait résoudre ce problème et supprimer quelques caractères inutiles.

UPDATE : Cette méthode est très bien pour les objets simples, il me fallait donc un moyen de simplifier les chemins complexes et de réduire le bruit. J'ai utilisé Inkscape pour cette tâche. J'ai eu un peu de chance avec le toilettage des chemins inutiles en utilisant Inkscape mais je n'ai pas eu le temps d'essayer de l'automatiser. J'ai fait quelques exemples de svgs en utilisant la fonction 'Simplify' d'Inkscape pour réduire le nombre de chemins.

Simplify fonctionne bien mais il peut être lent avec autant de chemins.

Voici quelques photos en très basse résolution. Elles seraient plus proches de la limite des 140 caractères, mais une compression intelligente des chemins d'accès pourrait également être nécessaire.

Simplifié et déspécifié.

Simplifié, déspécifié et triangulé.

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

CI-DESSUS : Chemins simplifiés utilisant autotrace .

Malheureusement, mon analyseur ne gère pas la sortie d'autotrace, donc je ne sais pas combien de points sont utilisés ou jusqu'où il faut simplifier, malheureusement il y a peu de temps pour l'écrire avant la date limite. C'est beaucoup plus facile à analyser que la sortie inkscape.

Answer 2

Très bien, voici le mien : nanocrunch.cpp et le CMakeLists.txt pour le construire en utilisant CMake. Il s'appuie sur le Magick++ ImageMagick API pour la plupart de ses manipulations d'images. Il requiert également l'API BPF pour l'arithmétique du bignum pour son encodage des chaînes de caractères.

J'ai basé ma solution sur la compression d'images fractales, avec quelques variantes uniques. L'idée de base est de prendre l'image, d'en réduire une copie à 50 % et de rechercher des morceaux dans diverses orientations qui ressemblent à des blocs non superposés dans l'image originale. L'approche de cette recherche est très brutale, mais cela facilite l'introduction de mes modifications.

La première modification est qu'au lieu de ne considérer que les rotations et les retournements à 90 degrés, mon programme prend également en compte les orientations à 45 degrés. C'est un bit de plus par bloc, mais cela améliore considérablement la qualité de l'image.

Par ailleurs, le stockage d'un ajustement du contraste et de la luminosité pour chaque composante de couleur de chaque bloc est beaucoup trop coûteux. Au lieu de cela, je stocke une couleur fortement quantifiée (la palette n'a que 4 * 4 * 4 = 64 couleurs) qui est simplement mélangée dans une certaine proportion. Mathématiquement, cela équivaut à un ajustement variable de la luminosité et constant du contraste pour chaque couleur. Malheureusement, cela signifie également qu'il n'y a pas de contraste négatif pour inverser les couleurs.

Une fois qu'il a calculé la position, l'orientation et la couleur de chaque bloc, il les encode dans une chaîne UTF-8. Tout d'abord, il génère un très grand bignum pour représenter les données de la table des blocs et la taille de l'image. L'approche est similaire à la solution de Sam Hocevar - une sorte de grand nombre avec un radix qui varie selon la position.

Ensuite, il le convertit en une base de la taille du jeu de caractères disponible. Par défaut, il utilise pleinement le jeu de caractères unicode attribué, sans les caractères moins que, plus que, esperluette, contrôle, combinaison, et caractères de substitution et privés. Ce n'est pas très joli, mais ça fonctionne. Vous pouvez également commenter la table par défaut et sélectionner l'ASCII 7 bits imprimable (en excluant les caractères <, > et &) ou les idéogrammes unifiés CJK à la place. La table des codes de caractères disponibles est stockée sous forme de run-length encodée avec une alternance de séries de caractères invalides et valides.

Quoi qu'il en soit, voici quelques images et temps (tels que mesurés sur mon vieux P4 3.0GHz), et compressés en 140 caractères dans l'ensemble complet d'unicode attribué décrit ci-dessus. Dans l'ensemble, je suis assez satisfait de la façon dont tout cela a tourné. Si j'avais plus de temps pour travailler sur ce projet, j'essaierais probablement de réduire le blocage des images décompressées. Néanmoins, je pense que les résultats sont assez bons pour le taux de compression extrême. Les images décompressées sont un peu impressionnistes, mais je trouve qu'il est relativement facile de voir comment les bits correspondent à l'original.

Logo Stack Overflow (8,6s pour le codage, 7,9s pour le décodage, 485 octets) :

Lena (32.8s pour encoder, 13.0s pour décoder, 477 octets) :

Mona Lisa (43,2 s pour le codage, 14,5 s pour le décodage, 490 octets) :

Edit : Caractères unifiés CJK

Sam a demandé dans les commentaires comment l'utiliser avec le CJK. Voici une version de la Joconde compressée en 139 caractères du jeu de caractères unifié CJK :

C'est également la forme la plus populaire et la plus répandue de la langue chinoise. Les tactiques de l'entreprise sont très bonnes, mais elles ne sont pas aussi bonnes que celles des autres.

Les paramètres de réglage en haut du programme que j'ai utilisés pour cela étaient les suivants : 19, 19, 4, 4, 3, 10, 11, 1000, 1000. J'ai également commenté la première définition de number_assigned et des codes, et décommenté leurs dernières définitions pour sélectionner le jeu de caractères CJK Unified.

Answer 3

Ma solution complète se trouve à l'adresse suivante http://caca.zoy.org/wiki/img2twit . Il présente les caractéristiques suivantes :

• Temps de compression raisonnable (environ 1 minute pour une haute qualité)
• Décompression rapide (une fraction de seconde)
• Conserve la taille originale de l'image (pas seulement le rapport hauteur/largeur)
• Qualité de reconstruction décente (IMHO)
• La longueur du message et le jeu de caractères (ASCII, CJK, Symboles) peuvent être choisis au moment de l'exécution.
• La longueur du message et le jeu de caractères sont autodétectés au moment de la décompression.
• Emballage des informations très efficace

L'activité principale de l'entreprise consiste à fournir une large gamme de services et de prestations au public. 蝺蝺蝺 蝺蝺 蝺 蝺 蝺 蝺 蝺 蝺 蝺 蝺

Voici un aperçu du processus d'encodage :

• Le nombre de bits disponibles est calculé à partir de la longueur souhaitée du message et du jeu de caractères utilisable.
• L'image source est segmentée en autant de cellules carrées que les bits disponibles le permettent.
• Un nombre fixe de points (actuellement 2) est affecté à chaque cellule, avec des coordonnées et des valeurs de couleur initiales.
• La procédure suivante est répétée jusqu'à ce qu'une condition de qualité soit remplie :
  • Un point est choisi au hasard
  • Une opération est effectuée au hasard sur ce point (le déplacer dans sa cellule, changer sa couleur).
  • Si l'image résultante (voir le processus de décodage ci-dessous) est plus proche de l'image source, l'opération est maintenue.
• La taille de l'image et la liste des points sont codées en UTF-8.

Et c'est le processus de décodage :

• La taille de l'image et les points sont lus à partir du flux UTF-8.
• Pour chaque pixel de l'image de destination :
  • La liste des voisins naturels est calculée.
  • La couleur finale du pixel est définie comme une moyenne pondérée des couleurs de ses voisins naturels.

Ce que je crois être la partie la plus originale du programme est le flux binaire. Au lieu d'empaqueter des valeurs alignées sur des bits ( stream <<= shift; stream |= value ), j'emballe des valeurs arbitraires qui ne sont pas dans des plages de puissances de deux ( stream *= range; stream += value ). Cela nécessite des calculs de bignum et est bien sûr beaucoup plus lent, mais cela me donne 2009,18 bits au lieu de 1960 en utilisant les 20902 caractères CJK principaux (cela fait trois points de plus que je peux mettre dans les données). Et en utilisant l'ASCII, il me donne 917,64 bits au lieu de 840.

Pour le calcul initial de l'image, j'ai renoncé à une méthode qui aurait nécessité un armement lourd (détection des coins, extraction de caractéristiques, quantification des couleurs...) car je n'étais pas sûr au départ que cela soit vraiment utile. Maintenant, je me rends compte que la convergence est lente (1 minute est acceptable mais c'est quand même lent) et je vais peut-être essayer d'améliorer cela.

La boucle d'ajustement principale est librement inspirée de l'algorithme de tramage Direct Binary Seach (où les pixels sont échangés ou retournés de manière aléatoire jusqu'à ce qu'une meilleure demi-teinte soit obtenue). Le calcul de l'énergie est une simple distance Root-mean-square, mais j'effectue d'abord un filtre médian 5x5 sur l'image originale. Un flou gaussien représenterait probablement mieux le comportement de l'œil humain, mais je ne voulais pas perdre les bords nets. J'ai également renoncé au recuit simulé ou à d'autres méthodes difficiles à régler, car je n'ai pas le temps de calibrer le processus. Ainsi, le drapeau "qualité" représente simplement le nombre d'itérations effectuées sur chaque point avant que l'encodeur ne se termine.

C'est un excellent moyen de tirer le meilleur parti de votre vie. Le premier d'entre eux est l'affichage du premier d'entre eux est l'affichage du premier d'entre eux.

Même si toutes les images ne se compressent pas bien, je suis surpris par les résultats et je me demande vraiment quelles autres méthodes existent pour compresser une image à 250 octets.

J'ai aussi des petits films sur l'évolution de l'état de l'encodeur. à partir d'un état initial aléatoire et à partir d'un "bon" état initial .

Modifier Voici comment la méthode de compression se compare au JPEG. A gauche, l'image de jamoes ci-dessus de 536 octets. À droite, Mona Lisa compressée à 534 octets en utilisant la méthode décrite ici (les octets mentionnés ici font référence aux octets de données, ignorant donc les bits gaspillés par l'utilisation des caractères Unicode) :

Modifier : vient de remplacer le texte CJK par les dernières versions des images.

Answer 4

Ce qui suit n'est pas une soumission formelle, puisque mon logiciel n'a pas été adapté de quelque façon que ce soit à la tâche indiquée. DLI peut être décrit comme un codec d'image avec perte à usage général optimisant. C'est le détenteur du record PSNR et MS-SSIM pour la compression d'images, et j'ai pensé qu'il serait intéressant de voir comment il se comporte pour cette tâche particulière. J'ai utilisé l'image de référence de Mona Lisa fournie, je l'ai réduite à 100x150 puis j'ai utilisé DLI pour la compresser à 344 octets.

Pour comparer avec les échantillons compressés JPEG et IMG2TWIT, j'ai utilisé DLI pour compresser l'image à 534 octets également. Le JPEG est de 536 octets et IMG2TWIT de 534 octets. Les images ont été mises à l'échelle à peu près à la même taille pour faciliter la comparaison. JPEG est l'image de gauche, IMG2TWIT est au centre, et DLI est l'image de droite.

L'image DLI parvient à préserver certains traits du visage, notamment le fameux sourire :).

Answer 5

L'aperçu général de ma solution serait le suivant :

1. Je commence par calculer la quantité maximale de données brutes que vous pouvez faire tenir dans 140 caractères utf8.
   • (Je suppose que c'est utf8, ce qui est ce que l'original site web dans lequel Twitter stockait ses messages. Cela diffère de l'énoncé du problème ci-dessus, qui demande l'utf16).
   • Utilisation de cette faq utf8 J'ai calculé que le nombre maximum de bits que l'on peut encoder dans un seul caractère utf8 est de 31 bits. Pour ce faire, j'utiliserais tous les caractères qui se trouvent dans la plage U-04000000 - U-7FFFFFFF. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, il y a 31 x, donc je pourrais encoder jusqu'à 31 bits).
   • 31 bits fois 140 caractères égalent 4340 bits. Divisez ce chiffre par 8 pour obtenir 524,5, et arrondissez-le à l'unité inférieure. 542 octets .
   • (Si nous nous limitons à utf16, nous ne pourrions stocker que 2 octets par caractère, soit 280 octets).
2. Compresser l'image en utilisant la compression standard jpg.
   • Redimensionnez l'image pour qu'elle soit d'environ 50x50px, puis essayez de la compresser à différents niveaux de compression jusqu'à ce que vous obteniez une image qui soit aussi proche que possible de 542 octets sans les dépasser.
   • Voici un exemple de la mona lisa compressée à 536 octets.
3. Encode les bits bruts de l'image compressée en caractères utf-8.
   • Remplacez chaque x dans les octets suivants : 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, par les bits de l'image.
   • C'est probablement dans cette partie qu'il faudrait écrire la majorité du code, car il n'existe actuellement rien qui fasse cela.

Je sais que vous avez demandé du code, mais je n'ai pas vraiment envie de prendre le temps de le coder. Je me suis dit qu'un design efficace pourrait au moins inspirer quelqu'un d'autre à le coder.

Je pense que le principal avantage de la solution que je propose est qu'elle réutilise autant que possible les technologies existantes. Il peut être amusant d'essayer d'écrire un bon algorithme de compression, mais il est certain qu'il existe un meilleur algorithme, très probablement écrit par des personnes ayant un diplôme en mathématiques supérieures.

Une autre remarque importante est que si l'on décide que l'utf16 est l'encodage préféré, alors cette solution s'écroule. Les jpegs ne fonctionnent pas vraiment lorsqu'ils sont compressés à 280 octets. Cependant, il existe peut-être un meilleur algorithme de compression que le jpg pour ce problème spécifique.