推特图像编码挑战

如果一张图片值1000个单词，那么在140个字符中你能容纳多少图片?

伙计们，就是这样!赏金的最后期限到了，经过一番艰难的思考，我决定Boojum的条目勉强超过萨姆·霍瑟瓦尔的。一旦我有机会把它们写下来，我会张贴更详细的笔记。当然，每个人都应该自由地继续提交解决方案，并改进解决方案以供人们投票。感谢所有提交和参赛的人;我都很喜欢。这次跑步对我来说很有趣，我希望对参赛者和观众来说都很有趣。

我看到这篇有趣的文章在尝试将图片压缩到Twitter评论中，许多人在那个线程(和Reddit上的帖子)对不同的方法提出了建议。所以，我认为这将是一个很好的编码挑战;让人们把他们的钱放在他们的嘴巴上，并展示他们关于编码的想法如何在有限的空间内带来更多细节。

我向您提出一个通用系统，将图像编码为140个字符的Twitter消息，然后再将它们解码为图像。您可以使用Unicode字符，因此每个字符可以获得8位以上的字节。然而，即使允许使用Unicode字符，也需要将图像压缩到非常小的空间;这肯定是一种有损压缩，因此必须对每个结果看起来有多好进行主观判断。

你能做得更好吗?

规则

1. 你的程序必须有两种模式:编码和解码。
<李>当# EYZ0:
1. 您的程序必须以您选择的任何合理的光栅图形格式作为输入。我们认为ImageMagick支持的任何光栅格式都是合理的。
2. 你的程序必须输出一个可以用140或更少的Unicode码位表示的消息;在U+0000 - U+10FFFF范围内的140个代码点，不包括非字符(U+FFFE， U+FFFF， U+U+10FFFF5FFFE， U+U+10FFFF5FFFF，其中U+10FFFF5是1 - 10十六进制，范围U+10FFFF0 - U+10FFFF1)和代理代码点(U+10FFFF2 - U+10FFFF3)。它可以以您选择的任何合理编码输出;U+10FFFF8支持的任何编码都是合理的，平台原生编码或本地编码可能是一个不错的选择。详见U+10FFFF9。
李< / ol > < / > <李>当# EYZ0:
1. 您的程序应该将编码模式的输出作为输入。
2. 你的程序必须输出你选择的任何合理的格式的图像，如上所定义的，虽然输出矢量格式也是可以的。
3. 图像输出应该是输入图像的近似值;越接近输入图像越好。
4. 译码过程除了上述指定的输出外，不能访问编码过程的任何其他输出;也就是说，你不能把图像上传到某个地方，然后输出URL供解码过程下载，或者类似的傻事。
李< / ol > < / >
5. 为了用户界面的一致性，你的程序必须如下所示:
   1. 您的程序必须是一个脚本，可以在平台上使用适当的解释器设置为可执行文件，或者是一个可以编译为可执行文件的程序。
   2. 您的程序必须将encode或decode作为第一个参数来设置模式。
   3. 你的程序必须以以下一种或多种方式获取输入(如果你实现了接受文件名的方式，如果文件名缺失，你也可以从stdin和stdout中读写):

      1. 从标准输入和在标准输出输出。

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

      2. Take input from a file named in the second argument, and produce output in the file named in the third.

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

6. For your solution, please post:
   1. Your code, in full, and/or a link to it hosted elsewhere (if it's very long, or requires many files to compile, or something).
   2. An explanation of how it works, if it's not immediately obvious from the code or if the code is long and people will be interested in a summary.
   3. An example image, with the original image, the text it compresses down to, and the decoded image.
   4. If you are building on an idea that someone else had, please attribute them. It's OK to try to do a refinement of someone else's idea, but you must attribute them.

Guidelines

These are basically rules that may be broken, suggestions, or scoring criteria:

1. Aesthetics are important. I'll be judging, and suggest that other people judge, based on:
   1. How good the output image looks, and how much it looks like the original.
   2. How nice the text looks. Completely random gobbledigook is OK if you have a really clever compression scheme, but I also want to see answers that turn images into mutli-lingual poems, or something clever like that. Note that the author of the original solution decided to use only Chinese characters, since it looked nicer that way.
   3. Interesting code and clever algorithms are always good. I like short, to the point, and clear code, but really clever complicated algorithms are OK too as long as they produce good results.
2. Speed is also important, though not as important as how good a job compressing the image you do. I'd rather have a program that can convert an image in a tenth of a second than something that will be running genetic algorithms for days on end.
3. I will prefer shorter solutions to longer ones, as long as they are reasonably comparable in quality; conciseness is a virtue.
4. Your program should be implemented in a language that has a freely-available implementation on Mac OS X, Linux, or Windows. I'd like to be able to run the programs, but if you have a great solution that only runs under MATLAB or something, that's fine.
5. Your program should be as general as possible; it should work for as many different images as possible, though some may produce better results than others. In particular:
   1. Having a few images built into the program that it matches and writes a reference to, and then produces the matching image upon decoding, is fairly lame and will only cover a few images.
   2. A program that can take images of simple, flat, geometric shapes and decompose them into some vector primitive is pretty nifty, but if it fails on images beyond a certain complexity it is probably insufficiently general.
   3. A program that can only take images of a particular fixed aspect ratio but does a good job with them would also be OK, but not ideal.
   4. You may find that a black and white image can get more information into a smaller space than a color image. On the other hand, that may limit the types of image it's applicable to; faces come out fine in black and white, but abstract designs may not fare so well.
   5. It is perfectly fine if the output image is smaller than the input, while being roughly the same proportion. It's OK if you have to scale the image up to compare it to the original; what's important is how it looks.
6. Your program should produce output that could actually go through Twitter and come out unscathed. This is only a guideline rather than a rule, since I couldn't find any documentation on the precise set of characters supported, but you should probably avoid control characters, funky invisible combining characters, private use characters, and the like.

Scoring rubric

As a general guide to how I will be ranking solutions when choosing my accepted solution, lets say that I'll probably be evaluating solutions on a 25 point scale (this is very rough, and I won't be scoring anything directly, just using this as a basic guideline):

• 15 points for how well the encoding scheme reproduces a wide range of input images. This is a subjective, aesthetic judgement
  • 0 means that it doesn't work at all, it gives the same image back every time, or something
  • 5 means that it can encode a few images, though the decoded version looks ugly and it may not work at all on more complicated images
  • 10 means that it works on a wide range of images, and produces pleasant looking images which may occasionally be distinguishable
  • 15 means that it produces perfect replicas of some images, and even for larger and more complex images, gives something that is recognizable. Or, perhaps it does not make images that are quite recognizable, but produces beautiful images that are clearly derived from the original.
• 3 points for clever use of the Unicode character set
  • 0 points for simply using the entire set of allowed characters
  • 1 point for using a limited set of characters that are safe for transfer over Twitter or in a wider variety of situations
  • 2 points for using a thematic subset of characters, such as only Han ideographs or only right-to-left characters
  • 3 points for doing something really neat, like generating readable text or using characters that look like the image in question
• 3 points for clever algorithmic approaches and code style
  • 0 points for something that is 1000 lines of code only to scale the image down, treat it as 1 bit per pixel, and base64 encode that
  • 1 point for something that uses a standard encoding technique and is well written and brief
  • 2 points for something that introduces a relatively novel encoding technique, or that is surprisingly short and clean
  • 3 points for a one liner that actually produces good results, or something that breaks new ground in graphics encoding (if this seems like a low number of points for breaking new ground, remember that a result this good will likely have a high score for aesthetics as well)
• 2 points for speed. All else being equal, faster is better, but the above criteria are all more important than speed
• 1 point for running on free (open source) software, because I prefer free software (note that C# will still be eligible for this point as long as it runs on Mono, likewise MATLAB code would be eligible if it runs on GNU Octave)
• 1 point for actually following all of the rules. These rules have gotten a bit big and complicated, so I'll probably accept otherwise good answers that get one small detail wrong, but I will give an extra point to any solution that does actually follow all of the rules

Reference images

Some folks have asked for some reference images. Here are a few reference images that you can try; smaller versions are embedded here, they all link to larger versions of the image if you need those:



Prize

I am offering a 500 rep bounty (plus the 50 that StackOverflow kicks in) for the solution that I like the best, based on the above criteria. Of course, I encourage everyone else to vote on their favorite solutions here as well.

Note on deadline

This contest will run until the bounty runs out, about 6 PM on Saturday, May 30. I can't say the precise time it will end; it may be anywhere from 5 to 7 PM. I will guarantee that I'll look at all entries submitted by 2 PM, and I will do my best to look at all entries submitted by 4 PM; if solutions are submitted after that, I may not have a chance to give them a fair look before I have to make my decision. Also, the earlier you submit, the more chance you will have for voting to be able to help me pick the best solution, so try and submit earlier rather than right at the deadline.

Unicode notes

There has also been some confusion on exactly what Unicode characters are allowed. The range of possible Unicode code points is U+0000 to U+10FFFF. There are some code points which are never valid to use as Unicode characters in any open interchange of data; these are the noncharacters and the surrogate code points. Noncharacters are defined in the Unidode Standard 5.1.0 section 16.7 as the values U+FFFE, U+FFFF, U+nFFFE, U+nFFFF where n is 1–10 hexadecimal, and the range U+FDD0–U+FDEF. These values are intended to be used for application-specific internal usage, and conforming applications may strip these characters out of text processed by them. Surrogate code points, defined in the Unicode Standard 5.1.0 section 3.8 as U+D800–U+DFFF, are used for encoding characters beyond the Basic Multilingual Plane in UTF-16; thus, it is impossible to represent these code points directly in the UTF-16 encoding, and it is invalid to encode them in any other encoding. Thus, for the purpose of this contest, I will allow any program which encodes images into a sequence of no more than 140 Unicode code points from the range U+0000–U+10FFFF, excluding all noncharacters and surrogate pairs as defined above.

I will prefer solutions that use only assigned characters, and even better ones that use clever subsets of assigned characters or do something interesting with the character set they use. For a list of assigned characters, see the Unicode Character Database; note that some characters are listed directly, while some are listed only as the start and end of a range. Also note that surrogate code points are listed in the database, but forbidden as mentioned above. If you would like to take advantage of certain properties of characters for making the text you output more interesting, there are a variety of databases of character information available, such as a list of named code blocks and various character properties.

Since Twitter does not specify the exact character set they support, I will be lenient about solutions which do not actually work with Twitter because certain characters count extra or certain characters are stripped. It is preferred but not required that all encoded outputs should be able to be transferred unharmed via Twitter or another microblogging service such as identi.ca. I have seen some documentation stating that Twitter entity-encodes <, >, and &, and thus counts those as 4, 4, and 5 characters respectively, but I have not tested that out myself, and their JavaScript character counter doesn't seem to count them that way.

Tips & Links

• The definition of valid Unicode characters in the rules is a bit complicated. Choosing a single block of characters, such as CJK Unified Ideographs (U+4E00–U+9FCF) may be easier.
• You may use existing image libraries, like ImageMagick or Python Imaging Library, for your image manipulation.
• If you need some help understanding the Unicode character set and its various encodings, see this quick guide or this detailed FAQ on UTF-8 in Linux and Unix.
• The earlier you get your solution in, the more time I (and other people voting) will have to look at it. You can edit your solution if you improve it; I'll base my bounty on the most recent version when I take my last look through the solutions.
• If you want an easy image format to parse and write (and don't want to just use an existing format), I'd suggest using the PPM format. It's a text based format that's very easy to work with, and you can use ImageMagick to convert to and from it.