Twitter 图像编码挑战

597
如果一张图片价值1000个单词,那么你能在140个字符中放多少图片呢?
注意:就是这样了!赏金截止日期已经到了,在经过一些艰难的考虑后,我已经决定Boojum的参赛作品仅仅超过了Sam Hocevar的。一旦我有机会写下详细的笔记,我将发布更多详细信息。当然,每个人都应该随意提交解决方案,并改进供人们投票的解决方案。感谢所有提交和参与的人;我喜欢他们所有人。对我来说,这是一次很有趣的运行,我希望对参赛者和观众来说也是如此。
我看到了这篇有趣的文章,关于尝试将图像压缩成Twitter评论,那个线程中有很多人(以及Reddit上的一个线程)提出了不同的建议,你可以用不同的方式来做。所以,我认为这将是一个很好的编码挑战;让人们把钱放在嘴巴里,展示他们关于编码的想法如何导致在有限的空间中获得更多的细节。
我向你发起挑战,设计一种通用的系统,将图像编码为 140 个字符的 Twitter 消息,并将其解码为图像。您可以使用 Unicode 字符,因此每个字符可以获得超过 8 位。然而,即使允许使用 Unicode 字符,您仍需要将图像压缩到非常小的空间中;这肯定是有损压缩,因此必须对每个结果看起来好坏做出主观判断。
以下是原始作者 Quasimondo 从他的编码中获得的结果(该图像的许可证为 Creative Commons Attribution-Noncommercial license): Mona Lisa 你能做得更好吗?
规则:
  1. Your program must have two modes: encoding and decoding.
  2. When encoding:
    1. Your program must take as input a graphic in any reasonable raster graphic format of your choice. We'll say that any raster format supported by ImageMagick counts as reasonable.
    2. Your program must output a message which can be represented in 140 or fewer Unicode code points; 140 code points in the range U+0000U+10FFFF, excluding non-characters (U+FFFE, U+FFFF, U+nFFFE, U+nFFFF where n is 110 hexadecimal, and the range U+FDD0U+FDEF) and surrogate code points (U+D800U+DFFF). It may be output in any reasonable encoding of your choice; any encoding supported by GNU iconv will be considered reasonable, and your platform native encoding or locale encoding would likely be a good choice. See Unicode notes below for more details.
  3. When decoding:
    1. Your program should take as input the output of your encoding mode.
    2. Your program must output an image in any reasonable format of your choice, as defined above, though for output vector formats are OK as well.
    3. The image output should be an approximation of the input image; the closer you can get to the input image, the better.
    4. The decoding process may have no access to any other output of the encoding process other than the output specified above; that is, you can't upload the image somewhere and output the URL for the decoding process to download, or anything silly like that.
  4. For the sake of consistency in user interface, your program must behave as follows:

    1. Your program must be a script that can be set to executable on a platform with the appropriate interpreter, or a program that can be compiled into an executable.
    2. Your program must take as its first argument either encode or decode to set the mode.
    3. Your program must take input in one or more of the following ways (if you implement the one that takes file names, you may also read and write from stdin and stdout if file names are missing):

      1. Take input from standard in and produce output on standard out.

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

指南

这些基本上是可以打破的规则、建议或评分标准:

美学很重要。我将评判,并建议其他人根据以下标准进行评判:
  1. 输出图像的外观和与原始图像的相似程度。
  2. 文本的美观程度。如果您有非常聪明的压缩方案,完全随机的胡言乱语也可以,但我还想看到将图像转换为多语诗歌或类似聪明的答案。请注意,原始解决方案的作者决定仅使用中文字符,因为这样看起来更漂亮。
  3. 有趣的代码和聪明的算法总是好的。我喜欢简短、简明的代码,但真正聪明复杂的算法也可以,只要它们产生良好的结果。
速度也很重要,尽管不如压缩图像的效果重要。我宁愿拥有一个可以在十分之一秒内转换图像的程序,而不是运行遗传算法数天的程序。
我更喜欢较短的解决方案而不是较长的解决方案,只要它们在质量上合理可比;简洁是一种美德。
您的程序应该使用在 Mac OS X、Linux 或 Windows 上有免费实现的语言实现。我希望能够运行程序,但如果您有一个只在 MATLAB 或其他某些语言下运行的好解决方案,那也没关系。
您的程序应该尽可能地通用;它应该适用于尽可能多的不同图像,尽管有些图像可能比其他图像产生更好的结果。特别是:
  1. 程序内置了一些图像,它匹配并写入引用,然后在解码时生成匹配的图像,这相当无聊,并且只涵盖了一些图像。
  2. 能够将简单、平面、几何形状的图像分解成一些向量基元的程序非常棒,但如果在某种复杂度之外的图像上失败,则可能不够通用。
  3. 只能处理特定固定长宽比的图像,但对它们处理得很好也可以,但并不理想。
  4. 黑白图像可以将更多信息压缩到更小的空间中。另一方面,这可能限制了它适用的图像类型;人脸在黑白图像中表现良好,但抽象设计可能不那么出色。
  5. 输出图像比输入图像小,但比例大致相同是完全可以的。如果必须将图像放大以与原始图像进行比较,则可以。重要的是它的外观。
您的程序应该产生可以通过 Twitter 的输出,并且不会受到损坏。这只是一个指南,而不是规则,因为我找不到关于支持的精确字符集的任何文档,但您应该避免控制字符、奇怪的不可见组合字符、专用字符等。

评分标准

作为选择我接受的解决方案时的一般指南,我将按照25分制来评估解决方案(这只是一个非常粗略的指南,我不会直接给任何东西评分,只是使用它作为基本指导):

  • 15分,用于衡量编码方案对各种输入图像的复制效果。这是一种主观的审美判断。
    • 0分表示完全无法工作,每次都返回相同的图像,或者其他情况
    • 5分表示它可以编码一些图像,尽管解码版本看起来很丑,并且在更复杂的图像上可能根本不起作用
    • 10分表示它适用于各种图像,并产生令人愉悦的图像,有时可能是可辨认的
    • 15分表示它可以完美地复制某些图像,即使对于更大更复杂的图像,也会给出可识别的东西。或者,它可能不会生成完全可识别的图像,但会生成从原始图像明显派生出来的美丽图像。
  • 3分,用于评估Unicode字符集的巧妙使用
    • 如果只是使用允许的所有字符,则得0分
    • 使用一组安全传输到Twitter或更广泛应用场景的字符,得1分
    • 只使用汉字或只使用从右到左的字符等主题子集,得2分
    • 通过生成可读文本或使用类似于所讨论的图像的字符等方式,得3分
  • 3分,用于评估巧妙的算法方法和代码风格
    • 如果只是使用1000行代码来缩小图像,将其视为每个像素1位,并对其进行base64编码,则得0分
    • 使用标准编码技术并且代码简洁规范,得1分
    • 引入相对较新的编码技术或非常简短干净的代码,得2分
    • 使用一行代码实际上可以产生良好结果,或者在图形编码方面开创新局(如果这看起来是一个低分数的点数,记住这种好的结果通常也会在美学方面获得高分数),则得3分
  • 2分,用于评估速度。其他条件相同,速度越快越好,但上述标准比速度更重要。
  • 1分,用于评估是否在免费(开源)软件上运行,因为我更喜欢免费软件(请注意,只要在Mono上运行,C#仍然有资格获得此分数,同样,如果它在GNU Octave上运行,MATLAB代码也将有资格获得此分数)
  • 1分,用于评估是否实际遵守所有规则。这些规则变得有点大而复杂,因此我可能会接受其他方面良好但有一些小细节错误的答案,但对于实际遵守所有规则的解决方案将给予额外的1分。

参考图片

有些人要求提供一些参考图片。以下是几张你可以尝试的参考图片;这里嵌入了较小版本,如果需要,它们都链接到图像的较大版本:

Lena Mona Lisa Cornell Box StackOverflow Logo

奖励

我提供500分赏金(加上StackOverflow提供的50分),以最符合以上标准的解决方案为获胜者。当然,我鼓励大家在这里投票选出自己最喜欢的解决方案。

截止日期说明

本次比赛将一直持续到赏金用完为止,即5月30日星期六下午6点左右。我无法确定具体结束时间;可能在下午5点至7点之间。我保证会查看所有在下午2点前提交的条目,并尽力查看在下午4点前提交的所有条目;如果解决方案是在那之后提交的,则可能没有机会在做出决定之前公正地审查它们。此外,您提交得越早,就越有机会让投票帮助我选择最佳解决方案,因此请尽量在截止日期之前提交。

Unicode备注

有些人对允许使用哪些Unicode字符存在困惑。可能的Unicode代码点范围是U+0000U+10FFFF。有些代码点在任何开放数据交换中都不能用作Unicode字符,这些是非字符(noncharacters)代理编码点(surrogate code points)Unicode标准5.1.0第16.7节将非字符定义为值U+FFFEU+FFFFU+nFFFEU+nFFFF,其中n是十六进制的110,以及范围U+FDD0U+FDEF。这些值旨在用于应用程序特定的内部使用,并且符合规范的应用程序可以从它们处理的文本中删除这些字符。代理编码点在Unicode标准5.1.0第3.8节中定义为U+D800U+DFFF,用于在UTF-16中编码超出基本多语言平面(Basic Multilingual Plane)的字符;因此,无法直接表示这些代码点,并且在任何其他编码中对其进行编码都是无效的。因此,在本次比赛中,我将允许任何将图像编码为不超过140个Unicode代码点序列的程序,这些代码点来自于范围U+0000U+10FFFF,并排除上述所有非字符和代理对。

我更喜欢使用仅指定字符的解决方案,甚至更好的是使用巧妙的子集或利用所使用的字符集做一些有趣的事情。要查看已指定字符的列表,请参见Unicode Character Database;请注意,某些字符直接列出,而某些字符仅列为范围的开头和结尾。还要注意,代理代码点在数据库中列出,但如上所述是被禁止的。如果您想利用某些字符属性使输出的文本更加有趣,则有各种字符信息数据库可用,例如命名代码块列表各种字符属性
由于Twitter没有明确指定其支持的确切字符集,因此对于不实际与Twitter一起使用的解决方案,我将宽容处理,因为某些字符计数额外或某些字符被剥离。最好但不是必需的是,所有编码输出都应能够通过Twitter或其他微博服务(例如identi.ca)无损传输。我看到一些文档说明Twitter实体编码<、>和&,因此将其分别计为4、4和5个字符,但我自己没有进行测试,而他们的JavaScript字符计数器似乎并没有这样计算。

提示和链接

  • 规则中有效的Unicode字符定义有些复杂。选择一个字符块,例如CJK统一汉字(U+4E00-U+9FCF)可能更容易。
  • 您可以使用现有的图像库,如ImageMagickPython Imaging Library,进行图像处理。
  • 如果您需要帮助理解Unicode字符集及其各种编码,请参阅这个快速指南此详细的关于Linux和Unix中UTF-8的FAQ
  • 您越早提交您的解决方案,我(以及其他投票的人)就会有更多的时间来查看它。如果您改进了解决方案,可以编辑它;当我最后查看解决方案时,我将基于最新版本来评估奖励。
  • 如果您想要一个易于解析和编写的图像格式(而不仅仅是使用现有格式),我建议使用PPM格式。它是一种文本格式,非常易于处理,并且您可以使用ImageMagick进行转换。

6
上传图片到服务器并发布其URL不被视为有效。 - Shay Erlichmen
2
@Shay 我不是已经说过了吗?“解码过程可能无法访问编码过程的任何其他输出,除了上面指定的输出;也就是说,您不能将图像上传到某个地方并输出URL以供解码过程下载,或者做任何愚蠢的事情。” - Brian Campbell
1
@Konrad Rudolph 我同意;我并不是从实际角度(显然,从实际角度来看,整个比赛都很荒谬)考虑“愚蠢”,我是从这个比赛的背景下考虑“愚蠢”。在信息论意义上,使用URI并不是真正的压缩算法,因为它不能让你在不使用替代通道的情况下传输更多的信息。你可以给编码器和解码器一个大型图像数据库,并称其为仅适用于有限图像集的压缩,但我指定你需要能够处理任意图像。 - Brian Campbell
我喜欢这个挑战。不过,这里有一个替代想法,既然我们可以将图像的数据编码成文本,那么如果我们做相反的事情呢?比如,随机选择1000条推文,将它们解码成图像,看看我们会得到什么。 - Nick Radford
显示剩余10条评论
15个回答

288

图片文件和Python源代码(版本1和2)

版本1 这是我的第一次尝试。我会随着进展更新。

我已经将SO标志压缩到了几乎无损的300个字符。我的技术使用转换成SVG矢量图,所以对线条艺术品效果最好。实际上,它是一个SVG压缩器,仍需要原始艺术品经过矢量化阶段。

在我的第一次尝试中,我使用了一个在线服务进行PNG跟踪,但是有许多免费和非免费的工具可以处理此部分,包括potrace(开源)。

以下是结果

原始SO标志 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png 原始 编码解码后的SO标志 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png

字符数: 300

时间: 未测量,但实际上是瞬间完成的(不包括矢量化/光栅化步骤)

下一阶段将是每个Unicode字符嵌入4个符号(SVG路径点和命令)。目前我的Python版本不支持宽字符UCS4,这限制了每个字符的分辨率。我还将unicode保留范围的最大范围限制在0xD800的较低端,但一旦我建立了允许使用的字符列表并过滤以避免使用它们,我可以理论上将所需的字符数推到70-100个,适用于上面的标志。

目前这种方法的一个限制是输出大小不固定,它取决于向量化后的向量节点/点数。自动限制需要像素化图像(这将移除向量图形的主要优势),或者反复运行路径通过简化阶段,直到达到所需的节点计数(我正在Inkscape中手动完成此操作)。

版本2

更新: v2 现在有资格竞争。更改:

  • 命令行控制输入/输出和调试
  • 使用 XML 解析器 (lxml) 处理 SVG,而不是正则表达式
  • 每个 Unicode 符号打包 2 条路径段
  • 文档和清理
  • 支持 style="fill:color" 和 fill="color"
  • 将文档宽度/高度打包成单个字符
  • 路径颜色打包成单个字符
  • 通过舍弃每个颜色数据的4位来压缩颜色数据,然后通过十六进制转换将其打包成单个字符来实现颜色压缩。

字符: 133

时间: 几秒钟

v2 解码后的图像 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png(版本2编码和解码之后)

如您所见,这次出现了一些伪影。这不是该方法的限制,而是我转换中的某个错误。当点超出0.0-127.0范围时,伪影会发生,而我约束它们的尝试取得了部分成功。解决方案很简单,就是缩小图像,但我遇到了问题,无法缩小实际点而不是画板或组矩阵,而且我现在太累了,不想再费心。简而言之,如果您的点在支持的范围内,它通常可以正常工作。

我认为中间的扭曲是由于一个手柄移动到与其连接的另一侧引起的。基本上,这些点在一开始就太靠近了。在压缩源图像之前运行简化过滤器应该可以解决这个问题并减少一些不必要的字符。

更新: 对于简单的对象,这种方法很好用,但我需要一种简化复杂路径和减少噪音的方法。我使用Inkscape完成了这项任务。我已经尝试使用Inkscape清除不必要的路径,但还没有时间来自动化它。我使用Inkscape的“简化”功能制作了一些示例svg文件,以减少路径数量。

简化效果还可以,但处理这么多路径会变得很慢。

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

这里有一些超低分辨率的截图。这些将更接近于140个字符的限制,但也可能需要一些聪明的路径压缩。

修整后的 http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png 简化并去噪。

三角形化后的 http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png 简化、去噪和三角形化。

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

以上是使用autotrace简化路径的示例。

不幸的是,我的解析器不能处理autotrace的输出,因此我不知道有多少点在使用或需要进行多少简化。可悲的是,在截止日期之前写这个功能的时间非常有限。不过,相比inkscape的输出,它要容易解析得多。


2
太好了!起初我想创建一个混合向量解决方案,既有锐利的边缘又有平滑的区域,但是没有使用追踪库(我不想使用)的情况下,这证明过于复杂。我期待着看看你用你的方法能走多远! - sam hocevar
不错!我希望我们能看到一些通过矢量化实现近无损方法的尝试。这意味着它具有较低的通用性,但对于它所涵盖的图像质量更高。使用在线服务进行矢量化是可以的。祝你进一步缩小文件大小好运! - Brian Campbell
我认为图像压缩和字符编码是两个不同的步骤 - Sam的技术似乎对于编码来说是最优的,并且可以轻松地构建成一个独立的程序。如果你集中精力于解决方案的独特部分(即压缩部分),并只输出一串比特,你将获得更多的回报。 - Mark Ransom
70
哇,这些图片看起来真的很时尚。 - Rinat Abdullin

244
好的,这是我的代码: nanocrunch.cpp 和构建它所需的CMakeLists.txt文件,使用CMake。它主要依赖于Magick++ ImageMagick API来处理大部分图像。它还需要GMP库进行大数算术以进行字符串编码。
我基于分形图像压缩的解决方案,加入了一些独特的变化。基本思路是将图像缩小到50%,并查找在原始图像中非重叠块看起来相似的各种方向上的块。它采用非常暴力的方法进行搜索,但这使得更容易引入我的修改。
第一个修改是,程序不仅考虑90度旋转和翻转,而且还考虑45度的方向。这对每个块增加了一个位,但它极大地提高了图像质量。
另一个问题是为每个颜色块的每个颜色分量存储对比度/亮度调整太过昂贵。相反,我存储了一个大量量化的颜色(调色板仅有4 * 4 * 4 = 64种颜色),以某种比例简单地混合在一起。从数学上讲,这相当于每种颜色的可变亮度和恒定对比度调整。不幸的是,这也意味着没有负对比度来翻转颜色。
一旦计算出每个块的位置、方向和颜色,它就会将其编码为UTF-8字符串。首先,它生成一个非常大的大数来表示块表中的数据和图像大小。这种方法类似于Sam Hocevar的解决方案——一种基数随位置变化的大数。
然后将其转换为可用字符集大小的基数。默认情况下,它充分利用已分配的Unicode字符集,减去小于、大于、和号、控制、组合和代理字符。虽然不太美观,但它确实有效。您还可以注释掉默认表并选择可打印的7位ASCII(再次排除<、>和&字符)或CJK统一表意符号。可用字符代码的表以交替的无效和有效字符运行长度编码存储。
无论如何,这里有一些图片和时间(根据我旧的3.0GHz P4测量),并且压缩到上面描述的完整分配的unicode集合中的140个字符。总体而言,我对它们的表现相当满意。如果我有更多时间来处理这个问题,我可能会尝试减少解压缩图像的方块状。不过,我认为在极端压缩比下,结果还是相当不错的。解压后的图像有点印象派风格,但我觉得相对容易看出位与原始内容的对应关系。
Stack Overflow Logo(编码8.6秒,解码7.9秒,485字节):
http://i44.tinypic.com/2w7lok1.png Lena(编码32.8秒,解码13.0秒,477字节):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

蒙娜丽莎(43.2秒编码,14.5秒解码,490字节):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

编辑:CJK统一字符

Sam在评论中询问是否可以与CJK一起使用。这是从CJK统一字符集压缩为139个字符的蒙娜丽莎版本:

http://i43.tinypic.com/2yxgdfk.png 咏璘驞凄脒鵚据蛥鸂拗朐朖辿韩瀦魷歪痫栘璯緍脲蕜抱揎頻蓼債鑡嗞靊寞柮嚛嚵籥聚隤慛絖銓馿渫櫰矍昀鰛掾撄粂敽牙稉擎蔍螎葙峬覧絀蹔抆惫冧笻哜搀澐芯譶辍澮垝黟偞媄童竽梀韠镰猳閺狌而羶喙伆杇婣唆鐤諽鷍鴞駫搶毤埙誖萜愿旖鞰萗勹鈱哳垬濅鬒秀瞛洆认気狋異闥籴珵仾氙熜謋繴茴晋髭杍嚖熥勳縿餅珝爸擸萿

我用的程序顶部的调整参数是:19、19、4、4、3、10、11、1000、1000。我还注释掉了 number_assigned 和 codes 的第一个定义,并取消注释了它们的最后一个定义以选择 CJK 统一字符集。

哇!做得好。我对于这么小的图像使用分形图像压缩持怀疑态度,但是它确实能够产生相当不错的结果。而且编译和运行也相当容易。 - Brian Campbell
1
谢谢大家!Sam,你是指只有140个CJK字符的结果吗?如果是这样,那么是的,你需要调整顶部的数字。最终的位数大约是log2(steps_in_x * steps_in_y * steps_in_red * steps_in_green * steps_in_blue)* blocks_in_x * blocks_in_y + log2(maximum_width * maximum_height)。 - Boojum
编辑:我漏掉了第一个log2()中的*16。这是为了可能的方向。 - Boojum
20
有人使用这个推特账号分享过这张图片吗? - dbr

199

我的完整解决方案可以在http://caca.zoy.org/wiki/img2twit找到。它具有以下特点:

  • 压缩时间合理(高质量约1分钟)
  • 快速解压缩(仅需几分之一秒)
  • 保持原始图像大小(不仅是长宽比例)
  • 良好的重建质量(在我看来)
  • 可在运行时选择消息长度和字符集(ASCII、CJK、符号)
  • 可以在解压缩时自动检测消息长度和字符集
  • 非常高效的信息打包技术

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

以下是编码过程的大致概述:

  • 从所需消息长度和可用字符集计算可用位数
  • 源图像被分割为尽可能多的正方形单元,取决于可用的位数
  • 每个单元都有固定数量的点(目前为2个),其具有初始坐标和颜色值
  • 重复以下步骤,直到满足质量条件:
    • 随机选择一个点
    • 对该点执行一个随机操作(将其移动到单元格内,改变其颜色)
  • 如果产生的图像(请参见下面的解码过程)更接近源图像,则保留该操作
  • 图像大小和点列表以UTF-8编码
  • 以下是解码过程:

    • 从UTF-8流中读取图像大小和点
    • 对于目标图像中的每个像素:
      • 计算自然邻居的列表
      • 将像素的最终颜色设置为其自然邻居颜色的加权平均值

    我认为该程序最原始的部分是位流。我不是将位对齐的值打包(stream <<= shift; stream |= value),而是打包不在2的幂范围内的任意值(stream *= range; stream += value)。这需要大数运算,当然速度要慢得多,但它给了我2009.18比特,而不是使用20902个主CJK字符时的1960比特(这是我可以放入数据的三个额外点)。当使用ASCII时,它给我917.64位,而不是840。

    我放弃了一种需要重型武器进行初始图像计算的方法(角点检测,特征提取,颜色量化...),因为一开始我不确定它真的会有帮助。现在我意识到收敛速度很慢(1分钟是可以接受的,但仍然很慢),我可能会试着改进它。

    主要拟合循环松散地借鉴了直接二进制搜索抖动算法(在像素随机交换或翻转直到获得更好的半色调)。能量计算是一个简单的均方根距离,但我先对原始图像进行了5x5中值滤波。高斯模糊可能更好地表示人眼行为,但我不想失去锐利的边缘。我还决定不使用模拟退火或其他难以调整的方法,因为我没有几个月来校准这个过程。因此,“质量”标志只代表在编码器结束之前对每个点执行的迭代次数。

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

    尽管并非所有图像都可以很好地压缩,但我对结果感到惊讶,并且我真的很想知道是否存在其他可以将图像压缩至250字节的方法。

    我还有编码器状态演变的小电影,一个是从随机初始状态开始,另一个是从“好”的初始状态开始

    编辑:以下是该压缩方法与JPEG的比较。左边是jamoes的536字节图片,右边是使用此处描述的方法将蒙娜丽莎压缩到534字节(这里提到的字节是数据字节,因此忽略了使用Unicode字符浪费的位):

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

    编辑:刚刚用最新版本的图像替换了CJK文本。


    2
    好的,这是我的解决方案(源代码):http://caca.zoy.org/browser/libpipi/trunk/examples/img2twit.cpp我尝试解释并提供了一些示例:http://caca.zoy.org/wiki/img2twit - sam hocevar
    太好了!这是第一个完整的解决方案。你觉得你能否编辑你的答案(你提出第一个问题的那个答案),包括一些或所有的解释和一两张示例图片?在这里内联显示比从评论中链接更好。 - Brian Campbell
    2
    我真的很喜欢你的解决方案。你应该尝试减少分配给蓝色通道的值的数量,因为人眼无法很好地分辨蓝色:http://nfggames.com/games/ntsc/visual.shtm;这将允许你在某种程度上牺牲一些颜色信息的情况下获得更多的细节。或者也可以尝试分配到绿色通道? - rpetrich
    5
    不错。我尝试了一些这个想法的变化(请参见RANGE_X定义之前的注释),但没有非常彻底地尝试。正如您所看到的,使用5个蓝色值而不是6个,增加的误差略小于使用7个绿色值减少的误差。由于懒惰,我没有尝试同时使用两者。我还有另一个问题,就是我没有一个非常好的误差函数。我目前使用的是∑(∆r²+∆g²+∆b²)/3,效果还可以。我尝试使用基于YUV的Y分量的∑(0.299∆r²+0.587∆g²+0.114∆b²)(没有物理根据),但它对蓝色错误太宽容了。我会尝试找一些关于这个问题的论文。 - sam hocevar
    2
    @rpetrich:我修改了程序,使其在有足够位数的情况下动态增加r/g/b范围。这确保我们在整个比特流中不浪费超过13位(但实际上通常只有1或2位)。图片看起来稍微好一些。 - sam hocevar
    显示剩余10条评论

    45
    以下不是正式提交,因为我的软件没有针对所示任务进行任何定制。 DLI 可以被描述为一种优化的通用有损图像编解码器。它是图像压缩的 PSNR 和 MS-SSIM 记录保持者,我认为看看它在这个特定任务中的表现会很有趣。我使用提供的参考蒙娜丽莎图像并将其缩小到 100x150,然后使用 DLI 将其压缩为 344 字节。

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

    为了与 JPEG 和 IMG2TWIT 压缩样本进行比较,我也使用 DLI 将图像压缩到了 534 字节。JPEG 是 536 字节,IMG2TWIT 是 534 字节。为了方便比较,已将图像缩放到大致相同的大小。JPEG 是左图像,IMG2TWIT 是中心,DLI 是右图像。

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

    DLI 图像成功地保留了一些面部特征,尤其是著名的微笑:)。

    6
    抱歉,以上内容应该归功于Dennis Lee,他最初提交了它。我只是编辑了一下,将图片嵌入其中,并链接到我通过谷歌搜索找到的参考资料。我必须说,哇,我对压缩效果印象深刻。我将要去了解DLI的压缩技术。 - Brian Campbell
    1
    顺便提一下,DLI的作者提到了“长处理时间”。由于我无法运行他的软件,您能给我们提供大致的压缩时间数字吗? - sam hocevar
    1
    使用AMD Athlon64 2.4Ghz,100x150的蒙娜丽莎图像压缩需要38秒,解压需要6秒。将压缩最大值限制在251字节以内更加困难,输出质量显著降低。使用参考蒙娜丽莎图像,将其缩小至60x91,然后使用DLI将其压缩至243字节(最接近251但不超过)。这是输出i43.tinypic.com/2196m4g.png尽管比特率仅降低了约50%,但细节与534字节的DLI相比差距较大。然而,图像的结构保持得相当好。 - Dennis Lee
    1
    决定让比较250字节压缩样本更容易。将243字节的DLI放大并放在IMG2TWIT样本旁边。左边是IMG2TWIT,右边是DLI。这是图片i40.tinypic.com/30ndks6.png。 - Dennis Lee
    1
    DLI使用像JPEG一样的质量参数,因此如果需要目标输出大小,则需要进行试错。 - Dennis Lee
    显示剩余5条评论

    21
    我的解决方案的概述如下:
    1. 首先计算可以放入140个UTF8字符中的最大原始数据量。
      • (我假设使用UTF8,因为原网站声称Twitter将其消息存储在其中。这与上面的问题陈述不同,它要求使用UTF16。)
      • 使用这个UTF8 FAQ,我计算出单个UTF8字符中可以编码的最大位数为31位。为了实现这一点,我会使用U-04000000 – U-7FFFFFFF范围内的所有字符。(1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx,有31个x,因此我可以编码高达31位)。
      • 31位乘以140个字符等于4340位。将其除以8得到524.5,向下舍入为542字节
      • (如果我们限制自己只使用UTF16,则每个字符只能存储2个字节,相当于280个字节。)
    2. 使用标准jpg压缩将图像压缩。
    3. 将压缩后的图像的原始位编码为UTF-8字符。
      • 将以下字节中的每个x替换为图像中的位:1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx。
  • 这部分可能是需要编写大部分代码的部分,因为目前还没有任何现有的东西可以完成这个任务。
  • 我知道你在要求代码,但是我不想花时间编写它。我觉得一个高效的设计至少可以激发其他人编写它的灵感。

    我认为我提出的解决方案的主要优点是尽可能重用现有技术。尝试编写一个好的压缩算法可能很有趣,但肯定会有更好的算法存在,很可能是由拥有更高数学学位的人编写的。

    另外一个重要的注意事项是,如果决定utf16是首选编码,则此解决方案将失败。将JPEG压缩到280字节以下并不是很可行。不过,也许有更好的压缩算法能够解决这个特定的问题陈述。


    我现在正在工作,但我一定会在回家后实现这个解决方案。 - Paulo Santos
    2
    从我的实验来看,Twitter计算字符数的方式似乎是UTF-16;BMP字符计为1个字符,而高位平面字符计为2个字符。虽然这并没有被记录下来,但这就是他们的JavaScript字符计数器在你输入到输入框时所计算的方式。这也在原始线程的评论中提到过。我还没有尝试通过API提交以查看计数器是否有问题;如果有问题,我将更新实际约束的问题。但由于许多较长的UTF-8序列不是有效的Unicode,因此您可能无法使用任意UTF-8。 - Brian Campbell
    4
    在使用他们的API进行测试后,发现他们是按Unicode字符(代码点)计数的,而不是UTF-16代码单元(因为显然JavaScript长度方法所做的就是这个)。因此,你可以在那里获得更多信息;有效的Unicode字符范围在U+0000到U+10FFFF之间(每个字符略多于20位,每个字符可能有2^20 + 2^16种可能值)。UTF-8允许编码比Unicode允许的更多的值,因此如果限制自己只使用Unicode,则可以获得约350字节的空间,而不是542字节。 - Brian Campbell
    3
    那个只有536字节的蒙娜丽莎画像,尽管被极度压缩,看起来还是出奇地好! - Chris
    3
    目前我们可以编码129,775个不同的(指已指定、非控制、非私有)Unicode字符。如果我们限制自己只使用这个子集,那么总共需要2377位或297字节来编码。代码在这里:http://porg.es/blog/what-can-we-fit-in-140-characters - porges
    显示剩余2条评论

    20

    好的,我来晚了,但是我还是完成了我的项目。

    这是一个玩具遗传算法,使用半透明彩色圆圈来重新创建初始图像。

    特点:

    • 纯Lua。可以在任何有Lua解释器的地方运行。
    • 使用netpbm P3格式
    • 带有全面的单元测试套件
    • 保留原始图像大小

    缺点:

    • 速度慢
    • 在这种空间限制下,它仅保留了初始图像的基本颜色方案和一些特征的概要轮廓。

    这是一个代表Lena的推文示例:

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

    original lena encoded Lena

    这段代码存储在Mercurial代码仓库中,位于bitbucket.org。请访问http://bitbucket.org/tkadlubo/circles.lua以查看。


    2
    太棒了!可以创建整洁、艺术感十足的图像。我很高兴人们仍在致力于这个领域;看到各种不同的方法非常有趣。 - Brian Campbell
    1
    我希望将其用作原始图像的透明叠加层,从而产生类似于浅景深效果的效果。 - Nick Radford

    19
    以下是我的解决问题的方法,我必须承认这是一个非常有趣的项目,它绝对超出了我的正常工作领域,并使我学到了一些新东西。
    我的基本想法如下:
    1.将图像灰度下采样,使其总共有16种不同的阴影 2.对图像执行RLE压缩 3.将结果打包成UTF-16字符 4.对打包后的结果执行RLE压缩,以删除任何字符的重复
    事实证明,这确实有效,但仅在一定程度上,就像您可以从下面的示例图像中看到的那样。在输出方面,以下是一条样本推文,特别针对示例中显示的Lena图像。
    乤乤万乐唂伂倂倁企儂2企倁3企倁2企伂8企伂3企伂5企倂倃伂倁3企儁企2伂倃5企倁3企倃4企倂企倁企伂2企伂5企倁企伂쥹皗鞹鐾劉䦽阹럆䧜椿籫릹靭욶옷뎷歩㰷歉䴗鑹㞳鞷㬼獴鏙돗鍴祳㭾뤶殞焻�乹Ꮛ靆䍼
    正如您所看到的,我确实尝试了一些控制字符集的方法;然而,在存储图像颜色数据时,我遇到了问题。此外,这种编码方案还倾向于浪费大量数据位,这些位可以用于附加的图像信息。

    就运行时间而言,对于小图像,代码非常快,提供的样本图像约为55ms,但是随着图像变大,时间会增加。 对于512x512 Lena参考图像,运行时间为1182ms。 我要指出的是,很有可能代码本身并没有针对性能进行优化(例如,一切都被处理为Bitmap),因此在进行一些重构后,时间可能会稍微缩短一些。

    请随时向我提供任何建议,以便我做得更好或代码存在的问题。 可以在以下位置找到完整的运行时间列表和示例输出:http://code-zen.info/twitterimage/

    更新一

    我已经更新了用于压缩推文字符串时使用的RLE代码,以进行基本回溯,如果可以,则将其用于输出。 这仅适用于数字值对,但确实可以节省一些数据字符。 运行时间或图像质量基本相同,但推文倾向于更小。 我将在完成测试后更新网站上的图表。以下是一个示例推文字符串,再次针对小版本的Lena:

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

    更新二

    又是一个小更新,但我修改了代码以将颜色阴影分成三组而不是四组,这会使用更多的空间,但除非我漏掉了什么,否则它应该意味着颜色数据出现“奇怪”的字符已经不再出现了。此外,我进一步更新了压缩功能,使其现在可以作用于整个字符串,而不仅是颜色计数块。我仍在测试运行时间,但它们似乎有所改善;但是图像质量仍然相同。以下是最新版本的Lena推文:

    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


    1
    太好了,感谢您的参与!对于大多数这些图像,灰度实际上效果相当不错,尽管 Lena 有点难以辨认。我在寻找您的源代码时得到了 404 错误,请确保它已经存在。 - Brian Campbell
    现在请再检查一遍,我正在更新网站,你可能正好赶上了我的更新过程。 - rjzii
    是的,我现在可以下载它了。当然,现在我需要弄清楚是否可以让Mono编译它。 - Brian Campbell
    没错!可以在Mono下运行,我使用“gmcs -r System.Drawing TwitterImage.cs Program.cs”进行编译,并使用“mono TwitterImage.exe encode lena.png lena.txt”运行。 - Brian Campbell
    太棒了!我确保我使用的库都被列为Mono可用的,但我还没有真正使用过Mono,所以我不确定它是否适用。 - rjzii
    示例图像不可见。 - Jakub Narębski

    15

    12

    在原始挑战中,大小限制定义为如果您将文本粘贴到Twitter的文本框中并按“更新”按钮发送,则仍允许发送的内容。正如一些人正确地注意到的那样,这与您可以从手机发送的短信文本消息不同。

    虽然没有明确说明(但我个人的规则是),您应该能够在浏览器中选择推文信息,将其复制到剪贴板并将其粘贴到解码器的文本输入字段中,以便它可以显示出来。当然,您也可以将消息保存为文本文件并进行读取或编写一个工具,该工具访问Twitter API并过滤掉任何看起来像图像代码的消息(有特殊标记吗?wink wink)。但规则是消息必须通过Twitter才能允许您解码它。

    祝您在350字节内好运 - 我怀疑您能否利用它们。


    1
    是的,我已经添加了一个评分标准,表明更严格的字符集限制是首选但不是必需的。我想要一个规则,要求消息通过Twitter时不受影响,但这需要大量的试错来确定确切的细节,我希望留下一些余地以允许对代码空间进行创造性的使用。因此,在我的挑战中唯一的要求是140个有效的Unicode字符。顺便说一句,感谢您的光临!我真的很喜欢您的解决方案,并希望看到任何评论者是否能够改进它。 - Brian Campbell

    12

    发布一张单色或灰度图像可以提高可编码到该空间内的图像大小,因为您不需要考虑颜色。

    可能会增加上传三个图像的挑战,当重新组合时可以给您一个完整的彩色图像,同时仍然保持每个单独图像的单色版本。

    在上述基础上添加一些压缩,它看起来可能是可行的......

    太棒了!!!现在你们已经引起了我的兴趣。接下来的一天我都不会工作了...


    9
    s/peaked/piqued/g - eleven81
    1
    我喜欢三张图片的想法,将这样的想法应用到Twitter上是可行的,结果会非常不错。 - Makis

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接