Défi d’encodage d’image Twitter

Bon, voici le mien: nanocrunch.cpp et le fichier CMakeLists.txt pour le construire en utilisant CMake. Il s’appuie sur l’API Magick ++ ImageMagick pour la majeure partie de son traitement d’image. Il nécessite également la bibliothèque GMP pour l’arithmétique de bignum pour son codage de chaîne.

J’ai basé ma solution sur la compression d’images fractales, avec quelques changements uniques. L’idée de base est de prendre l’image, de réduire une copie à 50% et de rechercher des pièces dans différentes orientations qui ressemblent à des blocs ne se chevauchant pas dans l’image d’origine. Cette recherche nécessite une approche très brutale, mais cela facilite l’introduction de mes modifications.

La première modification est que, au lieu de simplement regarder les rotations et les retournements à quatre-vingt-dix degrés, mon programme considère également les orientations à 45 degrés. C’est un bit de plus par bloc, mais cela aide énormément la qualité de l’image.

L’autre chose est que stocker un ajustement de contraste / luminosité pour chaque composant de couleur de chaque bloc est beaucoup trop cher. Au lieu de cela, je stocke une couleur fortement quantifiée (la palette ne contient que 4 * 4 * 4 = 64 couleurs) qui se mélange simplement dans une certaine proportion. Mathématiquement, cela équivaut à une luminosité variable et à un réglage de contraste constant pour chaque couleur. Malheureusement, cela signifie également qu’il n’y a pas de contraste négatif pour retourner les couleurs.

Une fois la position, l’orientation et la couleur calculées pour chaque bloc, celui-ci est encodé en une chaîne UTF-8. Tout d’abord, il génère un très grand nombre pour représenter les données dans la table de blocs et la taille de l’image. L’approche est similaire à celle de Sam Hocevar – une sorte de grand nombre avec une base 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 atsortingbué, à l’exception des caractères moins, plus grand que esperluette, contrôle, combinaison et substitution et privé. Ce n’est pas joli mais ça marche. Vous pouvez également commenter le tableau par défaut et sélectionner les caractères ASCII 7 bits imprimables (à nouveau sans les caractères <,> et &) ou les idéogrammes unifiés CJK. La table dont les codes de caractères sont disponibles est stockée dans une longueur codée avec des exécutions alternées de caractères non valides et valides.

Quoi qu’il en soit, voici quelques images et heures (mesurées sur mon ancien P4 de 3,0 GHz), et compressées à 140 caractères dans l’unité d’ensemble définie ci-dessus. Dans l’ensemble, je suis assez satisfait de la façon dont ils se sont tous avérés. Si j’avais plus de temps pour y travailler, j’essaierais probablement de réduire le blocage des images décompressées. Pourtant, je pense que les résultats sont plutôt bons pour le taux de compression extrême. Les images décompressées sont peu impressionnistes, mais je trouve relativement facile de voir comment les bits correspondent à l’original.

Stack Overflow Logo (8.6s à encoder, 7.9s à décoder, 485 octets):
http://i44.tinypic.com/2w7lok1.png

Lena (32.8s à encoder, 13.0s à décoder, 477 octets):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

Mona Lisa (43.2s à encoder, 14.5s à décoder, 490 octets):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

Modifier: caractères unifiés CJK

Sam a demandé dans les commentaires sur l’utilisation de ceci avec CJK. Voici une version de Mona Lisa compressée à 139 caractères du jeu de caractères CJK Unified:

http://i43.tinypic.com/2yxgdfk.png咏 璘 驞 凄 脒 鵚 据 蛥 鸂 拗 朐 朖 抱 韩 頻 蓼 債 栘 嗞 鑡 寞 靊 聚慛 絖 銓 馿 渫 櫰 矍 昀 鰛 掾 撄 蹔 抆 惫 冧 笻 哜 搀 峬 覧 絀 蹔 垝 黟 偞 哜 童 竽 芯 喙 喙杇 婣 唆 鐤 諽 鷍 鴞 駫 搶 毤 埙 鬒 秀 瞛 洆 认 気 狋 哳 垬 濅 鬒 氙 熜 謋 気 茴 晋 闥 爸 爸擸 萿

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

fichiers image et source python (version 1 et 2)

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

J’ai le logo SO réduit à 300 caractères presque sans perte. Ma technique utilise la conversion en images vectorielles SVG, donc elle fonctionne mieux sur les dessins au trait. Il s’agit en fait d’un compresseur SVG, il faut quand même que l’art original passe par une phase de vectorisation.

Pour ma première tentative, j’ai utilisé un service en ligne pour la trace PNG, mais il existe BEAUCOUP d’outils gratuits et non-libres qui peuvent gérer cette partie, y compris potrace (open-source).

Voici les résultats

Logo SO original http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Logo SO original décodé http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png Après encodage et décodage

Caractères : 300

Temps : Non mesuré mais pratiquement instantané (sans les étapes de vectorisation / rasterisation)

L’étape suivante consistera à intégrer 4 symboles (points de chemin SVG et commandes) par caractère Unicode. À l’heure actuelle, ma version python ne prend pas en charge les caractères UCS4, ce qui limite ma résolution par caractère. J’ai également limité la scope maximale à l’extrémité inférieure de la plage réservée unicode 0xD800, mais une fois que je construis une liste de caractères autorisés et un filtre pour les éviter, je peux théoriquement pousser le nombre de caractères requirejs jusqu’à 70-100 pour le logo ci-dessus.

Une limitation de cette méthode à l’heure actuelle est que la taille de sortie n’est pas fixe. Cela dépend du nombre de noeuds / points vectoriels après la vectorisation. L’automatisation de cette limite nécessite soit de pixelliser l’image (ce qui supprime le principal avantage des vecteurs), soit de répéter l’exécution des chemins via une étape de simplification jusqu’à ce que le nombre de nœuds souhaité soit atteint (que je fais actuellement manuellement dans Inkscape).

Version 2

MISE À JOUR : v2 est maintenant qualifié pour concurrencer. Changements:

• Contrôle / entrée de ligne de commande et débogage
• Utilise un parsingur XML (lxml) pour gérer SVG au lieu de regex
• Packs 2 segments de chemin par symbole Unicode
• Documentation et nettoyage
• Support style = “fill: color” et fill = “color”
• Largeur / hauteur du document emballé dans un seul caractère
• Couleur du chemin d’access empaquetée dans un seul caractère
• La compression des couleurs est obtenue en jetant 4 bits de données de couleur par couleur puis en les emballant dans un personnage via une conversion hexadécimale.

Caractères : 133

Temps : quelques secondes

v2 décodé http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png Après encodage et décodage (version 2)

Comme vous pouvez le voir, il y a des 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 dépassent les limites de 0,0 à 127,0 et que mes tentatives pour les contraindre ont eu un succès mitigé. La solution consiste simplement à réduire l’image, mais j’ai eu du mal à mettre à l’échelle les points réels plutôt que la masortingce de la planche graphique ou du groupe et je suis trop fatiguée maintenant pour m’en soucier. En bref, si vos points sont dans la plage prise en charge, cela fonctionne généralement.

Je crois que le kink au milieu est dû à une poignée se déplaçant de l’autre côté d’une poignée à laquelle il est lié. Fondamentalement, les points sont trop proches les uns des autres en premier lieu. L’exécution d’un filtre simplifié sur l’image source avant la compression devrait résoudre ce problème et raser certains caractères inutiles.

UPDATE : Cette méthode convient parfaitement aux objects 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 de la chance avec la recherche de chemins inutiles avec 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 Inkscape ‘Simplify’ pour réduire le nombre de chemins.

Simplifier fonctionne bien mais cela peut être lent avec beaucoup de chemins.

exemple d’autotrace http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png box cornell 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

vignettes tracées http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png

Voici quelques photos ultra-basse résolution. Celles-ci seraient plus proches de la limite de 140 caractères, bien que certaines compressions astucieuses soient également nécessaires.

soigné http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Simplifié et dépouillé.

Trianglulated http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_sortingangulated.png Simplifié, dépouillé et sortingangulé.

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

CI-DESSUS: Chemins simplifiés avec autotrace .

Malheureusement, mon parsingur ne gère pas la sortie d’autotrace, donc je ne sais pas comment les points peuvent être utilisés ou dans quelle mesure ils doivent être simplifiés. Malheureusement, il rest peu de temps pour les écrire avant la date limite. C’est beaucoup plus facile à parsingr que la sortie inkscape.

Ma solution complète peut être trouvée à http://caca.zoy.org/wiki/img2twit . Il a 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 de l’image d’origine (pas seulement le format d’image)
• 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 détectés automatiquement au moment de la décompression
• Emballage d’information très efficace

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

秓 鋖 筷 聝 诿 缰 偺 腶 漷 庯 祩 梄 踥 桻 理 戂 溥 欇 趆 脘 搇 梄 髙 骟 市 溥 璨 粭 裏 岚 岚霫 鏓 蓕 戲 債 鼶 襋 躻 弯 袮 足 籂 阉 嶹 婻 椿 糢 墤 掔 倾 诗 籂 棫 武 婩 糢 逡 荨 緛 憫 憫舥 攩 寉 鈶 兓 庭 亖 篂 喆 蝞 躐 葌 熲 努 蛪 曟 亖 弜 媏 蝞 盂 蛪 盂 氤 譑 殾 譑

Voici un aperçu du processus de codage:

• Le nombre de bits disponibles est calculé à partir de la longueur de message souhaitée 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 les coordonnées initiales et les valeurs de couleur
• Ce qui suit est répété 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 (en le déplaçant dans sa cellule, en changeant de 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 conservée
• La taille de l’image et la liste des points sont encodées en UTF-8

Et c’est le processus de décodage:

• La taille de l’image et les points sont lus à partir du stream 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 pense est la partie la plus originale du programme est le bitstream. Au lieu de regrouper les valeurs alignées sur les bits ( stream <<= shift; stream |= value ), je compresse des valeurs arbitraires qui ne sont pas à des intervalles de puissance de deux ( stream *= range; stream += value ). Cela nécessite des calculs bignum et est bien sûr beaucoup plus lent, mais cela me donne 2009.18 bits au lieu de 1960 en utilisant les caractères principaux CJK 20902 (c'est trois autres points que je peux mettre dans les données). Et en utilisant ASCII, cela me donne 917,64 bits au lieu de 840.

J'ai opté pour une méthode de calcul d'image initiale qui aurait nécessité des armes lourdes (détection de coin, extraction de caractéristiques, quantification des couleurs ...) car je n'étais pas certain au départ que cela aiderait vraiment. Maintenant, je me rends compte que la convergence est lente (1 minute est acceptable mais elle est néanmoins lente) et je vais peut-être essayer d’y remédier.

La boucle d'ajustement principale est largement inspirée de l'algorithme de tramage Direct Binary Seach (où les pixels sont échangés de manière aléatoire jusqu'à ce qu'un meilleur demi-ton soit obtenu). Le calcul de l'énergie est une simple distance quadratique moyenne, mais j'effectue d'abord un filtre médian de 5x5 sur l'image d'origine. Un flou gaussien représenterait probablement mieux le comportement de l’œil humain, mais je ne voulais pas perdre de netteté. J'ai également décidé d'éviter les recuits simulés ou d'autres méthodes difficiles à régler, car je n'ai pas de mois pour calibrer le processus. Ainsi, le drapeau "qualité" représente simplement le nombre d'itérations effectuées sur chaque point avant la fin du codeur.

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

憗 揣 嶕 繠 剳 腏 篮 濕 茝 霮 墧 燋 任 朓 峂 釰 靂 陴 飗 噹 砃 燋 荛 砙 矺 靂 鷾 瓔 犟 俇 俇躙 憮 鄴 甮 槺 骳 佛 愚 猪 駪 惾 偁 箝 窂 蹻 熛 漧 衆 赭 飉 訥 偁 裋 頢 羔 漧 墎 嬔 愀 秓 秓绒 酯 嵞 脔 婺 污 銛 酼 礭 鱚 蟺 稿 纡 曚 陴 鳣 銛 蒝 鋁 鱚 脤 陴 脤 养 况 沅 况

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 de petits films sur l'évolution de l' état de l'encodeur à partir d'un état initial aléatoire et d'un "bon" état initial .

Edit : voici comment la méthode de compression se compare au JPEG. À gauche, l'image de 536 octets de jamoes. À droite, Mona Lisa a été compressée à 534 octets en utilisant la méthode décrite ici (les octets mentionnés ici se réfèrent à des octets de données, ignorant ainsi les bits gaspillés en utilisant des caractères Unicode):

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

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

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 ressortingct 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.

Caractéristiques:

• 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:

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

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 ssortingng 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 ssortingngs, 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 ssortingng 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…

Nice!!! 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 ressortingcting 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? Just an idea.