Twitter图像编码挑战
如果一张图片的价值是1000字，那么你可以在140个字符中填入多less图片？
注意 ：这是人！ 赏金截止date在这里，经过一番艰难的考虑后，我决定Boojum的入场只是Sam Hocevar的 。 一旦我有机会写出更详细的笔记，我会发布。 当然，每个人都可以随时继续提交解决scheme，改善人们投票的解决scheme。 感谢提交和录入的每一个人; 我喜欢所有这些。 这对我来说运行起来非常有趣，我希望对于参赛者和观众来说都是有趣的。
我偶然发现了一个有趣的post ，试图将图片压缩成一个Twitter评论，该post中的很多人（以及Reddit上的一个post ）都提出了不同的方法。 所以，我认为这将是一个很好的编码挑战; 让人们把他们的钱放在他们的口中，并展示他们的编码思想如何在有限的空间里得到更多的细节。
我挑战你想出一个通用的系统，将图像编码成140个字符的Twitter消息，并将它们再次解码成一个图像。 你可以使用Unicode字符，所以你每个字符超过8位。 但是，即使允许使用Unicode字符，也需要将图像压缩到非常小的空间内。 这肯定是一个有损压缩，所以必须有主观判断每个结果有多好。
以下是原作者Quasimondo从他的编码中得到的结果（图像是根据知识共享署名 – 非商业性许可授权的 ）： 
你能做得更好吗？
规则
- 你的程序必须有两种模式： 编码和解码 。
- 编码时 ：
- 您的程序必须以您select的任何合理的光栅graphics格式inputgraphics。 我们会说ImageMagick支持的任何格式都是合理的。
- 您的程序必须输出一个可以用140个或更less的Unicode代码点表示的消息; 除了非字符（
U+FFFE，U+FFFF，U+nFFFE，U+nFFFF，其中n是10hex数）和范围U+FDD0–U+FDEF之外的140个代码点在U+0000–U+10FFFFU+FDEF）和替代码点（U+D800–U+DFFF）。 它可以用您select的任何合理编码输出; GNUiconv支持的任何编码都将被认为是合理的，并且您的平台本地编码或区域设置编码可能是一个不错的select。 有关更多详细信息，请参阅以下Unicode注释
- 解码时 ：
- 你的程序应该把你的编码模式的输出作为input。
- 您的程序必须以您select的任何合理格式输出图像，如上所述，但对于输出vector格式也是如此。
- 图像输出应该是input图像的近似值; 越接近input图像越好。
- 除了上面指定的输出之外，解码过程可能不能访问编码过程的任何其他输出; 也就是说，你不能上传图像的地方，输出解码过程的URL下载，或者任何愚蠢的东西。
-
为了保持用户界面的一致性，您的程序的行为如下：
- 您的程序必须是一个脚本，可以将其设置为在具有适当的解释器的平台上执行，或者可以编译为可执行文件的程序。
- 你的程序必须以
encode或decode第一个参数来设置模式。 -
您的程序必须以下列一种或多种方式进行input（如果您实现了获取文件名的文件名，那么如果缺less文件名，则还可以从stdin和stdout读取和写入）：
-
从标准中input并输出标准输出。
my-program encode <input.png >output.txt my-program decode <output.txt >output.png -
从第二个参数中指定的文件获取input，并在第三个文件中指定的文件中生成输出。
my-program encode input.png output.txt my-program decode output.txt output.png
-
- 为了您的解决scheme，请张贴：
- 您的代码完整，和/或链接到其他地方（如果它很长，或需要很多文件进行编译，或其他东西）。
- 解释它是如何工作的，如果代码不是很明显，或者代码很长，那么人们会对摘要感兴趣。
- 示例图像，包含原始图像，压缩的文本以及解码的图像。
- 如果你正在build立一个别人的想法，请归因于他们。 尝试改进别人的想法是可以的，但是你必须把它们归因于它们。
方针
这些基本上是可以被破坏的规则，build议或评分标准：
- 美学是重要的。 我会判断，并build议其他人判断，基于：
- 输出图像的外观如何，看起来像原来的样子。
- 这个文本看起来好多了。 如果你有一个非常聪明的压缩scheme，完全随机的gobbledigook是可以的，但是我也想看到把图像转换成多种语言的答案，或者像这样聪明的东西。 请注意，原来的解决scheme的作者决定只使用汉字，因为它看起来更好。
- 有趣的代码和聪明的algorithm总是好的。 我喜欢简短，明确的代码，但只要能产生好的结果，真正聪明的复杂algorithm也可以。
- 速度也很重要，虽然不如压缩图像的效果好得多。 我宁愿有一个程序可以在十分之一秒内转换一个图像，而不是将要运行遗传algorithm几天的东西。
- 只要在质量上有相当的可比性，我宁愿select较长的解决scheme。 简洁是一种美德。
- 您的程序应该使用在Mac OS X，Linux或Windows上可以自由使用的语言来实现。 我希望能够运行这些程序，但是如果你有一个很好的解决scheme，只能在MATLAB或者什么的的基础上运行的话，没关系。
- 你的程序应该尽可能通用; 它应该为尽可能多的不同图像工作，尽pipe有些可能产生比其他更好的结果。 尤其是：
- 在程序中内置几张图像，并对其进行匹配和写入，然后在解码时产生匹配的图像，这是相当蹩脚的，只会覆盖一些图像。
- 一个可以将简单，平坦，几何形状的图像分解成一些vector图元的程序是非常漂亮的，但是如果图像失败超出一定的复杂度，则可能不够普遍。
- 一个只能拍摄特定固定长宽比的图像，但能够很好地处理这些图像的程序也可以，但并不理想。
- 您可能会发现，黑白图像可以将更多信息放入比彩色图像更小的空间中。 另一方面，这可能会限制它适用的图像types; 黑白的面孔出来很好，但抽象的devise可能不会那么好。
- 如果输出图像小于input，而比例大致相同，则完全没有问题。 如果您必须缩放图像以将其与原始图像进行比较，则可以。 重要的是它的外观。
- 你的程序应该产生可以真正通过Twitter的输出，并且毫发无损。 这只是一个指导，而不是一个规则，因为我找不到任何关于支持的字符集合的文档，但是您应该避免使用控制字符，时髦的不可见组合字符，私人使用字符等等。
评分标题
作为在select我接受的解决scheme时如何排名解决scheme的一般指南，可以说我可能会在25分制评估解决scheme（这是非常粗糙的，而且我不会直接评分任何东西，只是使用这作为一个基本的准则）：
- 编码scheme再现大范围的input图像有多好15分 。 这是一个主观的审美判断
- 0意味着它根本不起作用，它每次都会返回相同的图像，或者其他东西
- 5意味着它可以编码几个图像，虽然解码版本看起来很丑，对于更复杂的图像可能根本不起作用
- 10意味着它可以处理各种各样的图像，并产生令人愉悦的图像，偶尔也可以区分
- 15意味着它产生了一些图像的完美复制品，即使对于更大和更复杂的图像，也给出了可识别的东西。 或者，也许它不会使很容易辨认的图像，而是产生清晰地从原始图像中获得的美丽图像。
- 巧妙使用Unicode字符集3分
- 简单地使用整个允许的字符集0点
- 使用一组有限的字符，通过Twitter或更广泛的情况下安全转移的1点
- 使用汉字字符的专题子集2点，如汉字或只有从右到左的字符
- 3分做一些非常简洁的事情，比如生成可读的文字或者使用看起来像图片的字符
- 聪明的algorithm方法和代码风格3分
- 0点的东西是1000行的代码只是为了缩放图像，把它当作每像素1位，base64编码
- 1分使用标准编码技术，写得很好，简洁
- 2分的东西引入了一种相对新颖的编码技术，或者是令人惊讶的短而干净
- 实际上可以产生好的结果的一个class轮3分，或者是在graphics编码方面打破了一个新的领域（如果这看起来是打破新的领域的一小部分，请记住，这样的结果很可能会在美学上有很高的分数以及）
- 速度2点 。 其他条件相同，速度越快越好，但是上述标准比速度更重要
- 因为我更喜欢自由软件（请注意，只要它在Mono上运行，C＃仍然符合这一点），同样，如果它运行在GNU Octave上，那么MATLAB代码也是合格的。
- 实际遵循所有规则1分 。 这些规则已经变得大而复杂了，所以我可能会接受其他的好的答案，但是我会给出一个额外的观点来解决所有的规则
参考图像
一些人已经要求一些参考图像。 这里有一些你可以尝试的参考图片; 这里embedded了更小的版本，如果你需要的话，它们都链接到较大版本的图像：
奖
基于上述标准，我提供了500个代表奖金 （加上StackOverflow的50个启动函数），用于我最喜欢的解决scheme。 当然，我鼓励其他人也在这里投票选出他们最喜欢的解决scheme。
关于截止date的说明
5月30日星期六下午6点左右，这场比赛将一直持续到奖金结束。我不能说明这个时间到了什么时候， 它可能在5点到7点的任何地方。 我保证会看到下午2点之前提交的所有参赛作品，我将尽我所能查看下午4点之前提交的所有参赛作品; 如果在这之后再提交解决scheme的话，在我必须作出决定之前，我可能没有机会给他们一个公平的看法。 而且，您提交的越早，投票的机会就越多，能够帮助我select最佳的解决scheme，所以请在截止date前尽早提交而不是提交。
Unicode笔记
对于哪些Unicode字符是允许的也有一些混淆。 可能的Unicode代码点的范围是U+0000到U+10FFFF 。 有一些代码点在任何公开的数据交换中都不能用作Unicode字符; 这些是非字符和替 代码点 。 非字符在Unidode Standard 5.1.0第16.7节中定义为值U+FFFE ， U+FFFF ， U+ n FFFE ， U+ n FFFF ，其中n是10hex数，范围U+FDD0 – U+FDEF 。 这些值旨在用于特定于应用程序的内部使用，符合的应用程序可能会将这些字符从它们处理的文本中剥离。 在Unicode标准5.1.0第3.8节定义的替代码点用作U+D800 – U+DFFF ，用于UTF-16基本多语言平面以外的字符的编码; 因此，不可能直接用UTF-16编码来表示这些编码点，并且用其他编码对它们进行编码是无效的。 因此，就本次比赛而言，我将允许任何将图像编码为U+0000 – U+10FFFF范围内的不超过140个Unicode代码点的程序，但不包括上述定义的所有非字符和代理对。
我更喜欢只使用分配字符的解决scheme，甚至使用分配字符的聪明子集或者使用他们使用的字符集来做一些有趣的事情。 有关指定字符的列表，请参阅Unicode字符数据库 ; 请注意，某些字符是直接列出的，而有些字符仅作为范围的开始和结束列出。 还请注意，代理点代码点在数据库中列出，但是如上所述被禁止。 如果您想利用字符的某些属性来使输出的文本更加有趣，可以使用各种各样的字符信息数据库 ，例如指定的代码块列表和各种字符属性 。
由于Twitter没有指定他们支持的确切字符集，因此对于实际上并不与Twitter一起工作的解决scheme，我会宽松的，因为某些字符数额外或某些字符被剥离。 所有编码的输出应该能够通过Twitter或其他微博服务（如identi.ca）无损地传输，这是首选但不是必须的。 我看到一些文档指出Twitter实体对<，>和＆进行编码，因此分别将它们计数为4，4和5个字符，但是我没有对自己进行testing，并且他们的JavaScript字符计数器看起来不像以这种方式来计算他们。
提示和链接
- 规则中有效Unicode字符的定义有点复杂。 select一个字符块，如中日韩统一表意文字（U + 4E00-U + 9FCF）可能会更容易。
- 您可以使用现有的图像库，如ImageMagick或Python图像库 ，进行image processing。
- 如果您在理解Unicode字符集及其各种编码方面需要一些帮助，请参阅本快速指南或有关Linux和Unix中UTF-8的详细FAQ 。
- 你越早得到解决scheme，我（和其他人投票）就会有更多的时间来看待它。 如果您改进了解决scheme，您可以编辑解决scheme 当我通过解决scheme进行最后的审视时，我会根据最新的版本来获得我的赏金。
- 如果你想要一个简单的图像格式来parsing和编写（而不想只是使用现有的格式），我build议使用PPM格式 。 这是一个基于文本的格式，非常容易使用，您可以使用ImageMagick来进行转换。
好吧，这里是我的： nanocrunch.cpp和CMakeLists.txt文件，使用CMake来构build它。 它的大部分image processing都依赖于Magick ++ ImageMagick API。 它也需要用于字符编码的GMP库用于算术运算。
我基于分形图像压缩的解决scheme，有一些独特的曲折。 基本思路是拍摄图像，将副本缩小到50％，然后在各个方向上查找与原始图像中的非重叠块类似的块。 这个search需要一个非常暴力的方法，但是这只是让我更容易介绍我的修改。
第一个修改是，我的程序不是只看90度旋转和翻转，而是考虑45度的方向。 这是每块多一位，但它非常有助于图像质量。
另一方面是为每个块的每个颜色分量存储对比度/亮度调节太昂贵。 相反，我存储了大量的颜色（调色板只有4 * 4 * 4 = 64种颜色），只是按一定的比例混合在一起。 在math上，这相当于每种颜色的可变亮度和恒定对比度调整。 不幸的是，这也意味着翻转颜色没有负面对比。
一旦计算出每个块的位置，方向和颜色，它就会将其编码成一个UTF-8string。 首先，它会生成一个非常大的数字来表示块表中的数据和图像大小。 这种方法类似于Sam Hocevar的解决scheme – 一种根据位置而变化的大数字。
然后将其转换为任何可用字符集的大小的基础。 默认情况下，它充分利用分配的Unicode字符集，减去小于，大于，和号，控制，组合，代理和专用字符。 这不是漂亮，但它的作品。 您也可以将默认表注释掉，然后select可打印的7位ASCII（不包括<，>和＆字符）或CJK Unified Ideographs。 可用的字符代码表存储一个运行长度编码，交替运行无效和有效的字符。
无论如何，这里是一些图像和时间（以我的旧3.0GHz P4测量），并在上述完整分配的unicode集中压缩为140个字符。 总的来说，我很满意他们是如何结果的。 如果我有更多的时间来处理这个问题，我可能会尝试减less解压缩图像的块状。 不过，我认为这个结果对于极端压缩比来说是相当不错的。 解压缩的图像是有点印象的，但我觉得比较容易看到如何对应于原来的位。
堆栈溢出标志（8.6s编码，7.9s解码，485字节）： 
160wpb4.png
Lena（32.8s编码，13.0s解码，477字节）：
160wpb4.png 160wpb4.png
蒙娜丽莎（43.2s编码，14.5s解码，490字节）：
160wpb4.png 160wpb4.png
编辑：CJK统一字符
山姆在有关使用CJK的意见中问道。 下面是Mona Lisa的一个版本，压缩到CJK Unified字符集的139个字符：
在我使用的程序的顶部的调整参数是：19,19,4,4,3,10,11,1000,1000。我还评论了number_assigned和代码的第一个定义，并注释掉最后定义它们来selectCJK Unified字符集。
图像文件和python源 （版本1和2）
版本1这是我第一次尝试。 我会随时更新。
我已经把SO标识减less到了300个字符，几乎没有任何损失。 我的技术使用转换为SVGvector艺术，所以它最适合线条艺术。 它实际上是一个SVG压缩器，它仍然需要原始的艺术经历一个vector化阶段。
对于我的第一次尝试，我使用了PNG跟踪的在线服务 ，但有许多免费和非免费的工具可以处理这部分，包括potrace （开源）。
这是结果
人物 ：300
时间 ：没有测量，但实际上是即时的（不包括vector化/光栅化步骤）
下一个阶段是为每个unicode字符embedded4个符号（SVGpath点和命令）。 目前我的python版本没有宽字符支持UCS4，这限制了我每个字符的分辨率。 我也将最大范围限制在unicode保留范围0xD800的低端，但是一旦我build立了一个允许的字符和一个filter的列表来避免它们，理论上我可以将所需的字符数量推到70-100上面的标志。
目前这种方法的限制是输出大小不固定。 这取决于vector化之后的vector节点/点的数量。 自动化此限制将需要对图像进行像素化（这消除了vector的主要优点），或者重复运行通过简化阶段的path，直到达到所需的节点数（我目前在Inkscape中手动执行）。
版本2
更新 ：v2现在有资格参与竞争。 变化：
- 命令行控制input/输出和debugging
- 使用XMLparsing器（lxml）来处理SVG，而不是正则expression式
- 为每个unicode符号打包2个path段
- 文档和清理
- 支持style =“fill：color”和fill =“color”
- 文档宽度/高度打包成单个字符
- path颜色包装成单个字符
- 通过丢弃每种颜色的4位颜色数据，然后通过hex转换将其打包到一个字符中来实现颜色压缩。
人物 ： 133
时间 ：几秒钟
v2解码http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png编码和解码（版本2）;
正如你所看到的，这次有一些文物。 这不是方法的限制，而是我转换的某个地方的错误。 当点数超出范围0.0 – 127.0时，会出现文物，而我限制它们的尝试取得了不同的结果。 解决方法是简单地缩小图像，但是我无法缩放实际点而不是画板或组matrix，现在我太累了，现在无法照顾。 总之，如果你的观点在支持的范围内，它通常是有效的。
我相信中间的扭结是由于把手移动到与其相连的把手的另一侧。 基本上这些要点太靠近了。 在压缩之前对源图像运行简化filter应该修复这个问题并修剪一些不必要的字符。
更新 ：这种方法适用于简单的对象，所以我需要一种简化复杂path和减less噪音的方法。 我用Inkscape来完成这个任务。 我已经有了运用Inkscape梳理不必要的path的一些运气，但没有时间尝试自动化。 我已经使用Inkscape的“简化”function制作了一些示例SVG，以减lesspath数量。
简化工作好，但它可以用这么多的path慢。
autotrace示例http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png 康奈尔盒子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
缩略图追踪http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png
这是一些超低分辨率的镜头。 尽pipe可能还需要一些聪明的path压缩，但这些会更接近140个字符的限制。
修饰http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png简化和despeckled。;
autotrace --output-format svg --output-file cornell_box.svg --despeckle-level 20 --color-count 64 cornell_box.png
上图：使用自动跟踪的简化path。
不幸的是我的parsing器不处理autotrace输出，所以我不知道如何使用点或简化多less，可悲的是没有多less时间写在截止date之前。 虽然parsing比inkscape输出要容易得多。
我的完整解决scheme可以在http://caca.zoy.org/wiki/img2twitfind。; 它具有以下特点：
- 合理的压缩时间（高质量大约1分钟）
- 快速解压缩（几分之一秒）
- 保持原始图像的大小（不只是长宽比）
- 体面重build质量（恕我直言）
- 消息长度和字符集（ASCII，CJK，符号）可以在运行时select
- 消息长度和字符集在解压缩时自动检测
- 非常有效的信息包装
stackoverflow/challenge/so-logo.png raw-attachment/wiki/img2twit/twitter4.png
蜥秓鋖筷聝诿缰咱腶漷庯祩皙靊谪獜岨幻寤厎趆脘搇梄踥桻理戂溥欇渹里軱骿苸髙骟市簶璨粭浧鳖捕弫潮衍蚙瀹岚玧霫鏓蓕戏债鼶襋躻弯袮足庭侅旍凼飙驱据嘛掔倾诗籂阉嶹婻椿模墤渽緛赐更当棫武婩缣逡荨璙杯翉珸齸陁颗鳣悯掷舥攩寉鈶兓庭璱篂鰀干丕耓庁铼努樀肝亖弜喆蝞躐葌熲谎蛪曟暙刍镶媏嘝骕慸盂氤缰殾譑
以下是对编码过程的粗略概述：
- 可用比特的数量根据期望的消息长度和可用的字符集来计算
- 源图像被分割成可用位允许的方格数量
- 固定数量的点（当前为2）受到每个像元的影响，包括初始坐标和颜色值
- 重复以下步骤直到满足质量条件：
- 一个点是随机select的
- 在这个点上随机执行一个操作（在单元格内移动它，改变它的颜色）
- 如果生成的图像（参见下面的解码过程）更接近源图像，则操作保持不变
- 图像大小和点列表以UTF-8编码
这是解码过程：
- 图像大小和点是从UTF-8stream中读取的
- 对于目标图像中的每个像素：
- 计算自然界的列表
- 像素的最终颜色被设置为其自然邻居颜色的加权平均值
我相信这个程序最原始的部分就是比特stream。 我不打包位alignment的值（ stream <<= shift; stream |= value ），我打包任意不在两个幂范围内的值（ stream *= range; stream += value ）。 这需要计算大量的数据，当然要慢很多，但是当使用20902个主要的CJK字符时（这是我可以放入数据的三个点），它给了我2009.18位而不是1960。 而当使用ASCII，它给了我917.64位，而不是840。
我决定不采用初始图像计算的方法，因为我不确定起初是否真的有所帮助，所以需要重型武器（angular点检测，特征提取，色彩量化…）。 现在我意识到收敛速度很慢（1分钟是可以接受的，但速度还是很慢），我可能会试着改进。
主要拟合循环从直接二进制search抖动algorithm（其中像素被随机交换或翻转直到获得更好的半色调）松散地启发。 能量计算是一个简单的均方根距离，但我首先对原始图像执行5×5中值滤波。 高斯模糊可能会更好地代表人眼的行为，但我不想失去尖锐的边缘。 我也决定不采用模拟退火或其他难以调整的方法，因为我没有几个月来校准过程。 因此，“质量”标志仅代表在编码器结束之前在每个点上执行的迭代次数。
raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg raw-attachment/wiki/img2twit/twitter2.png
苉憗揣嶕繠剳腏篮湿茝霮墧蒆棌杚蓳缚樟赒肴飗当砃燋任朓峂釰雳陴貜犟掝喗讄荛砙矺敨鷾璎亨髎芟氲簵鸬嫤铰俇激躙怃邺甮槺骳佛愚猪駪惾嫥綖珏矫坼堭颽箽赭飉讷偁钳窂蹻熛漧众橼愀航玴毡裋頢羔恺墎嬔鑹楄瑥鹣呍蕖抲鹂秓苾绒酯嵞脔婺污啰酼俵菛琪棺则辩曚鸸职铦蒝礭鱚蟺稿纡醾陴鳣尥蟀惘铝髚忩祤脤养趯沅况
即使并不是所有的图像都能很好地压缩，但是我对结果感到惊讶，我真的不知道还有什么其他方法可以将图像压缩到250字节。
编码器状态从一个随机初始状态和一个“良好”初始状态演变而来的小电影也有。
编辑 ：这里是压缩方法如何与JPEG比较。 在左边，jamoes的536字节以上的图片。 在右边，蒙娜丽莎使用这里描述的方法压缩到534字节（这里提到的字节是指数据字节，因此忽略了使用Unicode字符浪费的位）：
raw-attachment/wiki/img2twit/minimona.jpg raw-attachment/wiki/img2twit/minimona2.png
编辑 ：用最新版本的图像replaceCJK文本。
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 160wpb4.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 160wpb4.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:
- 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).
- 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.
- 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.
特征：
- 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:
- 慢
- 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:
- Down-sample the image gray-scale such that there were a total of 16 different shades
- Preform RLE on the image
- Pack the results into the UTF-16 characters
- 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/twitterimagehttp://img.dovov.comstackoverflow-logo.bmp Cornell Box http://code-zen.info/twitterimagehttp://img.dovov.comcornell-box.bmp Lena http://code-zen.info/twitterimagehttp://img.dovov.comlena.bmp Mona Lisa http://code-zen.info/twitterimagehttp://img.dovov.commona-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 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? 只是一个想法。
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}
;){kind=link}