twitter - Twitter 图像编码挑战

Question

如果一张图片值 1000 个字，那么 140 个字符可以容纳多少张图片？

注意：就是这样，伙计们！赏金截止日期到了，经过深思熟虑后，我决定Boojum 的参赛作品勉强超过了Sam Hocevar 的参赛作品。一旦我有机会写出来，我会发布更详细的笔记。当然，每个人都应该随时继续提交解决方案并改进解决方案供人们投票。感谢所有提交和参赛的人；我很喜欢他们所有人。这对我来说很有趣，我希望对参赛者和观众来说都很有趣。

我遇到了一篇关于尝试将图像压缩到 Twitter 评论中的有趣帖子，该帖子中的很多人（以及 Reddit 上的一个帖子）都对不同的方法提出了建议。所以，我认为这将是一个很好的编码挑战；让人们把钱放在嘴边，并展示他们关于编码的想法如何在您可用的有限空间中带来更多细节。

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

以下是原作者Quasimondo从他的编码中得到的结果（图像是在知识共享署名-非商业性许可下获得许可的）：蒙娜丽莎

你能做得更好吗？

规则

你的程序必须有两种模式：编码和解码。
编码时：
1. 您的程序必须将您选择的任何合理光栅图形格式的图形作为输入。我们会说ImageMagick支持的任何光栅格式都是合理的。
2. 您的程序必须输出一条可以用 140 个或更少的 Unicode 代码点表示的消息；–<code>U+10FFFF范围内的 140 个代码点U+0000，不包括非字符 ( U+FFFE, U+FFFF, U+nFFFE , U+nFFFF其中n是1–<code>10 十六进制，范围U+FDD0–<code>U+FDEF) 和代理代码点 ( U+D800–<代码>U+DFFF）。它可以以您选择的任何合理编码输出；GNUiconv支持的任何编码都将被认为是合理的，您的平台本机编码或语言环境编码可能是一个不错的选择。有关更多详细信息，请参阅下面的Unicode 注释。
解码时：
1. 您的程序应将编码模式的输出作为输入。
2. 您的程序必须以您选择的任何合理格式输出图像，如上所述，尽管输出矢量格式也可以。
3. 图像输出应该是输入图像的近似值；离输入图像越近越好。
4. 除了上面指定的输出之外，解码过程可能无法访问编码过程的任何其他输出；也就是说，您不能将图像上传到某处并输出 URL 以供解码过程下载，或者任何类似的愚蠢行为。
为了用户界面的一致性，您的程序必须表现如下：
1. 您的程序必须是可以在具有适当解释器的平台上设置为可执行的脚本，或者是可以编译为可执行文件的程序。
2. 您的程序必须将encode或decode设置模式作为其第一个参数。
3. 您的程序必须通过以下一种或多种方式获取输入（如果您实现了获取文件名的方式，如果缺少文件名，您也可以从 stdin 和 stdout 读取和写入）：
  1. 从标准输入获取输入并在标准输出上产生输出。
```
my-program encode <input.png >output.txt
my-program decode <output.txt >output.png
```
  2. 从第二个参数命名的文件中获取输入，并在第三个参数命名的文件中产生输出。
```
my-program encode input.png output.txt
my-program decode output.txt output.png
```
对于您的解决方案，请发布：
1. 您的完整代码和/或在其他地方托管的指向它的链接（如果它很长，或者需要很多文件来编译，或其他）。
2. 如果代码不是很明显，或者代码很长并且人们会对摘要感兴趣，则说明它是如何工作的。
3. 示例图像，包含原始图像、压缩后的文本和解码图像。
4. 如果您正在建立其他人的想法，请归因于他们。尝试对别人的想法进行提炼是可以的，但你必须归因于他们。

指导方针

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

审美很重要。我将根据以下内容进行判断，并建议其他人进行判断：
1. 输出图像看起来有多好，它看起来与原始图像有多少相似之处。
2. 文字看起来多好。如果你有一个非常聪明的压缩方案，完全随机的 gobbledigook 是可以的，但我也希望看到将图像变成多语言诗歌的答案，或者类似的聪明东西。请注意，原始解决方案的作者决定只使用汉字，因为这样看起来更好。
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 行代码的 0 点仅用于缩小图像，将其视为每像素 1 位，然后 base64 对其进行编码
- 使用标准编码技术且写得好且简短的东西得 1 分
- 引入相对新颖的编码技术，或者令人惊讶的短而干净的东西，得 2 分
- 实际产生良好结果或在图形编码中开辟新天地的单行线 3 分（如果这似乎是开辟新天地的低分，请记住，这种好结果可能会在美学方面获得高分以及）
速度2分。在其他条件相同的情况下，越快越好，但以上标准都比速度更重要
在免费（开源）软件上运行得1 分，因为我更喜欢免费软件（请注意，只要 C# 在 Mono 上运行，它仍然有资格获得这一点，同样，如果 MATLAB 代码在 GNU Octave 上运行，它也有资格）
实际遵守所有规则得1 分。这些规则变得有点大和复杂，所以我可能会接受其他好的答案，但会错误地回答一个小细节，但我会为任何确实遵循所有规则的解决方案加分

参考图像

有些人要求提供一些参考图像。以下是一些您可以尝试的参考图像；此处嵌入了较小的版本，如果您需要，它们都链接到图像的较大版本：

奖

根据上述标准，我为我最喜欢的解决方案提供500 个代表赏金（加上 StackOverflow 启动的 50 个）。当然，我鼓励其他人也在这里投票选出他们最喜欢的解决方案。

截止日期注意事项

这场比赛将一直持续到赏金用完，大约在 5 月 30 日星期六下午 6 点左右。我不能说它结束的确切时间；它可能是下午 5 点到 7 点之间的任何时间。我保证我会查看下午 2 点之前提交的所有参赛作品，我会尽力查看所有下午 4 点之前提交的参赛作品；如果在那之后提交了解决方案，我可能没有机会在做出决定之前给他们一个公平的审视。此外，您越早提交，您就越有机会投票以帮助我选择最佳解决方案，因此请尝试尽早提交，而不是在截止日期前提交。

Unicode 注释

对于究竟允许使用哪些 Unicode 字符，也存在一些混淆。可能的 Unicode 代码点的范围U+0000是U+10FFFF. 在任何开放的数据交换中，有些代码点永远不能用作 Unicode 字符；这些是非字符和代理代码点。非字符在Unidode 标准 5.1.0 第 16.7 节中定义为值U+FFFE, U+FFFF, U+nFFFE , U+nFFFF其中n是1–<code>10 十六进制，范围U+FDD0–<代码>U+FDEF。这些值旨在用于特定于应用程序的内部使用，并且符合标准的应用程序可能会从它们处理的文本中去除这些字符。代理代码点，在Unicode 标准 5.1.0 第 3.8 节中定义为U+D800–<code>U+DFFF，用于对 UTF-16 中基本多语言平面之外的字符进行编码；因此，不可能直接用 UTF-16 编码来表示这些代码点，并且用任何其他编码对它们进行编码都是无效的。因此，出于本次竞赛的目的，我将允许任何程序将图像编码为不超过 140 个 Unicode 代码点的序列，范围为U+0000–<code>U+10FFFF，不包括上面定义的所有非字符和代理对。

我会更喜欢只使用指定字符的解决方案，甚至更喜欢使用指定字符的聪明子集或使用他们使用的字符集做一些有趣的事情的更好的解决方案。有关分配字符的列表，请参阅Unicode 字符数据库；请注意，有些字符是直接列出的，而有些字符仅作为范围的开始和结束列出。另请注意，代理代码点已在数据库中列出，但如上所述是禁止的。如果您想利用字符的某些属性使输出的文本更有趣，可以使用各种字符信息数据库，例如命名代码块列表和各种字符属性.

由于 Twitter 没有指定它们支持的确切字符集，因此我将对实际上不适用于 Twitter 的解决方案宽容，因为某些字符会额外计数或某些字符会被删除。最好但不要求所有编码输出都应该能够通过 Twitter 或其他微博服务（如identi.ca ）不受损害地传输。我看过一些文档说明 Twitter 实体编码 <、> 和 &，因此分别将它们计为 4、4 和 5 个字符，但我自己没有测试过，他们的 JavaScript 字符计数器似乎没有以这种方式计算它们。

提示和链接

规则中有效 Unicode 字符的定义有点复杂。选择单个字符块，例如 CJK 统一表意文字 (U+4E00–U+9FCF) 可能更容易。
您可以使用现有的图像库，例如ImageMagick或Python Imaging Library来进行图像处理。
如果您在理解 Unicode 字符集及其各种编码方面需要帮助，请参阅此快速指南或有关 Linux 和 Unix 中的 UTF-8 的详细常见问题解答。
你越早得到你的解决方案，我（和其他投票的人）就会有越多的时间来研究它。如果您改进它，您可以编辑您的解决方案；当我最后一次浏览这些解决方案时，我会以最新版本为基础。
如果您想要一种简单的图像格式来解析和写入（并且不想只使用现有格式），我建议使用PPM 格式。它是一种基于文本的格式，非常易于使用，您可以使用ImageMagick进行转换。

score 288 · Accepted Answer

图像文件和 python 源（版本 1 和 2）

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

我已将 SO 徽标缩减至 300 个字符，几乎无损。我的技术使用转换为 SVG 矢量艺术，因此它在线条艺术上效果最佳。它实际上是一个 SVG 压缩器，它仍然需要原始艺术经过矢量化阶段。

对于我的第一次尝试，我使用了 PNG 跟踪的在线服务，但是有许多免费和非免费工具可以处理这部分，包括potrace（开源）。

这是结果

原始 SO Logo http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png原始解码 SO Logo 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，以减少路径的数量。

简化工作正常，但有这么多路径可能会很慢。

自动跟踪示例 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 莉娜 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的简化路径。

不幸的是，我的解析器不处理自动跟踪输出，所以我不知道使用的点数或简化的程度，遗憾的是在截止日期之前几乎没有时间编写它。不过，它比inkscape 输出更容易解析。

score 244 · Accepted Answer

好的，这是我的：nanocrunch.cpp和CMakeLists.txt文件，以使用 CMake构建它。它的大部分图像处理依赖于Magick++ ImageMagick API。它的字符串编码还需要用于 bignum 算法的GMP库。

我的解决方案基于分形图像压缩，并带有一些独特的曲折。基本思想是拍摄图像，将副本缩小到 50%，然后在不同方向寻找与原始图像中的非重叠块相似的片段。这种搜索需要一种非常暴力的方法，但这只会让我更容易介绍我的修改。

第一个修改是，我的程序不仅考虑了 90 度的旋转和翻转，还考虑了 45 度的方向。每块多一位，但它极大地提高了图像质量。

另一件事是为每个块的每个颜色分量存储对比度/亮度调整太昂贵了。相反，我存储了一种高度量化的颜色（调色板只有 4 * 4 * 4 = 64 种颜色），它只是以某种比例混合在一起。从数学上讲，这相当于对每种颜色进行可变亮度和恒定对比度调整。不幸的是，这也意味着翻转颜色没有负面对比。

一旦计算出每个块的位置、方向和颜色，它就会将其编码为 UTF-8 字符串。首先，它生成一个非常大的 bignum 来表示块表中的数据和图像大小。解决这个问题的方法类似于 Sam Hocevar 的解决方案——一种带有随位置变化的基数的大数。

然后它将其转换为可用字符集大小的基础。默认情况下，它充分利用分配的 unicode 字符集，减去小于、大于、&、控制、组合、代理和私有字符。它不漂亮，但它有效。您还可以注释掉默认表并选择可打印的 7 位 ASCII（同样不包括 <、> 和 & 字符）或 CJK 统一表意文字。哪些字符代码可用的表存储了一个用无效和有效字符交替运行编码的游程长度。

无论如何，这里有一些图像和时间（在我的旧 3.0GHz P4 上测量），并在上述完整分配的 unicode 集中压缩为 140 个字符。总的来说，我对他们的结果感到相当满意。如果我有更多时间来解决这个问题，我可能会尝试减少解压缩图像的块状。尽管如此，我认为极端压缩比的结果还是相当不错的。解压缩后的图像有点印象派，但我发现比较容易看出位与原始图像的对应关系。

Stack Overflow 徽标（编码 8.6 秒，解码 7.9 秒，485 字节）： http ://i44.tinypic.com/2w7lok1.png

Lena（编码 32.8s，解码 13.0s，477 字节）：http ://i42.tinypic.com/2rr49wg.png
http://i40.tinypic.com/2rhxxyu.png

蒙娜丽莎（43.2s 编码，14.5s 解码，490 字节）：http ://i41.tinypic.com/ekgwp3.png
http://i43.tinypic.com/ngsxep.png

编辑：中日韩统一字符

Sam 在评论中询问了如何将其与 CJK 一起使用。这是蒙娜丽莎的一个版本，从 CJK 统一字符集中压缩为 139 个字符：

http://i43.tinypic.com/2yxgdfk.png 咏璞驞凄脒鵚蛥鸂拗搚蛥鸂拗搚朖辿韩拗搽朖辿韩拗拜歪致畸聚栘璯瘍频蕜抱揎蓼蓼债鑡嗞靊孤柮嚛嚵籥隤慛絖渫矍昀掾撄掾撄蔍螎峬覧绌蹔绌蹔抆惫冧筇哜冧筇哜搀沄芯譶辍浍垝黟黟偞偞媄媄媄童佟鹆鹆鰬懆懇鐤杞鷍駫駫駫诬懇搤斞芍嚅鹆鹬谬爇搤斳垤珵揬谬氬愿秀氬笗瞛洞认珵笥笹熹熜珫珵珲狰珺熜珫珰珰珰珰珰珰珰珰珰珰珬珬珰珰珰珰珰杍呬珰搵珰珰珰杍埬搱笠珰珰珰杍呬珲笠珰珰杍呬珰珰珰珰杍呫擸萿</p>

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

score 199 · Accepted Answer

我的完整解决方案可以在 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)，而是打包不在二次幂范围内的任意值 ( stream *= range; stream += value)。这需要 bignum 计算，当然速度要慢得多，但是当使用 20902 主要 CJK 字符时，它给了我 2009.18 位而不是 1960 位（我可以在数据中再输入三个点）。当使用 ASCII 时，它给了我 917.64 位而不是 840。

我决定反对一种需要重型武器（角检测、特征提取、颜色量化......）的初始图像计算方法，因为起初我不确定它是否真的有帮助。现在我意识到收敛速度很慢（1 分钟是可以接受的，但它仍然很慢），我可能会尝试改进它。

主要拟合循环的灵感来自 Direct Binary Seach 抖动算法（其中像素随机交换或翻转，直到获得更好的半色调）。能量计算是一个简单的均方根距离，但我首先对原始图像执行 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 文本。

score 45 · Accepted Answer

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

蒙娜丽莎 DLI http://i40.tinypic.com/2md5q4m.png

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

比较 http://i42.tinypic.com/302yjdg.png

DLI 图像设法保留了一些面部特征，最著名的是著名的微笑:)。

score 21 · Accepted Answer

我的解决方案的一般概述是：

我首先计算可以放入 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 个字节）。
使用标准 jpg 压缩压缩图像。
- 将图像大小调整为大约 50x50 像素，然后尝试以不同的压缩级别对其进行压缩，直到您的图像尽可能接近 542 字节，而不会超过。
- 这是一个将蒙娜丽莎压缩到 536 字节的示例。
将压缩图像的原始位编码为 utf-8 字符。
- 将以下字节中的每个 x 替换为图像中的位：1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx。
- 这部分可能是需要编写大部分代码的部分，因为目前没有任何东西可以做到这一点。

我知道您在要求代码，但我真的不想花时间实际编写代码。我认为一个高效的设计至少可以激发其他人编写代码。

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

另一个重要的注意事项是，如果确定 utf16 是首选编码，那么这个解决方案就会失败。当压缩到 280 字节时，jpegs 并不能真正工作。虽然，对于这个特定的问题陈述，也许有比 jpg 更好的压缩算法。

score 20 · Accepted Answer

好吧，我迟到了，但我还是做了我的项目。

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

特征：

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

误区：

慢的
在这个空间限制下，它只保留了初始图像的基本配色方案和几个特征的大致轮廓。

下面是一个代表Lena的例子：犭杨谷杌蒝螦界匘玑扝俄归刀客猘摈硰划萕码抱斢嘁蜁晃耂澹婊内簜偾砠偑婊内簜偾砠偑臀簜偾砠偑臀簜偾翈义倨裆凁梡岂戆耆耋斘爆耆耋攋斘爔戡蔋昸箔奡萋昸箔奡嬎廩栃兆塅嬎廩栃兆塅僘称赜千戞优称赜卐戞优杈杈赜蝈蝈杈杈芶蝽蝽杈杈赜綍蝈杈杈赜戣杈杈芶蝊猫扪昜昜压盩悡诟来眉屐搡诟来昜压籐悡诟来瘜压琛悡诟来眉屐昸皕嘜彍傩吆别虲兙罨縨炘排抠堃从弅芅芎熰标宑箫柢橙拃枀缩昔傥舭励癳冂堆积璟彝兠摔摔侑蒖孂埮槃姠哠榕眛嫡砠枀訜柬芠枀訜厇廪焛瀻严啘刱垫仔

原来的莉娜编码莉娜

该代码位于 bitbucket.org 的 Mercurial 存储库中。查看http://bitbucket.org/tkadlubo/circles.lua

score 19 · Accepted Answer

以下是我解决这个问题的方法，我必须承认这是一个非常有趣的项目，它绝对超出了我的正常工作范围，并且给了我一些新的东西来学习。

我的基本思想如下：

对图像灰度进行下采样，使得总共有 16 种不同的色调
在图像上预制 RLE
将结果打包成 UTF-16 字符
对打包结果执行 RLE 以删除任何重复的字符

事实证明，这确实有效，但只是在有限的范围内，正如您从下面的示例图像中看到的那样。在输出方面，下面是一条示例推文，专门针对示例中显示的 Lena 图像。

乤乤万乐唂伂倂倁企侬2企倁3企倁2伂8企伂3企伂5企倂倃伂倁3企俊2伂倃5企企倁3企倃4企倂企倁倁伂2企伂5企倁企伂쥹阹럆䧜椿籫릹韧욶옷뎷歩㰷伴鑹㞳鞷㽴獴鏙돗鍴獴鏙돗鍴祳㭾뤶殒焻乹䏋叇似</pp>

如您所见，我确实尝试对字符集进行了一些限制；但是，我在存储图像颜色数据时遇到了问题。此外，这种编码方案还倾向于浪费大量可用于附加图像信息的数据位。

在运行时间方面，对于小图像，代码非常快，提供的示例图像大约需要 55 毫秒，但随着图像的增大，时间确实会增加。对于 512x512 Lena 参考图像，运行时间为 1182 毫秒。我应该注意到，代码本身并没有针对性能进行优化的可能性很大（例如，所有内容都作为Bitmap使用），因此在进行一些重构后时间可能会下降一点。

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

更新一

我更新了压缩推文字符串时使用的 RLE 代码以进行基本回顾，如果是这样，则将其用于输出。这仅适用于数字值对，但它确实保存了几个字符的数据。运行时间与图像质量或多或少相同，但推文往往要小一些。完成测试后，我将更新网站上的图表。以下是示例推文字符串之一，同样适用于小版本的 Lena：

乤乤万乐唂伂倂倁企侬2企倁3企倁ウ伂8企伂エ伂5企倂倃伂倁グ俊企2伂倃ガ倁ジ倃4企倂企倁企伂ツ伂ス倁伂쥹痗鞟鐾륶䦽阹럱䧜椿皫릹韧욶옷뎷歩㰷䴗鑹㞳鞷ぼ獴鏙돗鍴獴鏙돗鍴祳㭾涮焻乹Ꮛ叇䍼</p>

更新二

另一个小更新，但我修改了代码以将颜色阴影打包成三个而不是四个一组，这会占用更多空间，但除非我遗漏了什么，否则它应该意味着“奇数”字符不再出现在颜色的位置数据是。此外，我对压缩进行了更多更新，因此它现在可以作用于整个字符串，而不仅仅是颜色计数块。我仍在测试运行时间，但它们似乎在名义上有所改善；但是，图像质量仍然相同。以下是莉娜推文的最新版本：

2乤万乐唂伂倂倁企永2企倁3企倁ウ伂8企伂エ伂5企倂倃伂倁グ俊企2伂倃ガ倁ジ倃4企倂企倁企伂ツ伂ス倁伂坹坼坼坶坻刾啩容力吹婩媷劝圿奁婣妛啭奁婣冷咛啫涂奉奉宗宗坍塌似奎喳女媗决兴喓夽兴唹冷圶埫唓坤商嗉乃

StackOverflow 徽标 http://code-zen.info/twitterimage/images/stackoverflow-logo.bmp 康奈尔盒子 http://code-zen.info/twitterimage/images/cornell-box.bmp 莉娜 http://code-zen .info/twitterimage/images/lena.bmp 蒙娜丽莎 http://code-zen.info/twitterimage/images/mona-lisa.bmp

score 15 · Accepted Answer

Roger Alsing 编写的这种遗传算法具有良好的压缩比，但代价是压缩时间较长。可以使用有损或无损算法进一步压缩得到的顶点向量。

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

将是一个有趣的程序来实现，但我会错过它。

score 12 · Accepted Answer

在最初的挑战中，大小限制被定义为如果您将文本粘贴到他们的文本框中并按“更新”，Twitter 仍然允许您发送的内容。正如一些人正确地注意到的那样，这与您可以通过手机发送的 SMS 文本消息不同。

没有明确提及（但我个人的规则是）是您应该能够在浏览器中选择推文消息，将其复制到剪贴板并将其粘贴到解码器的文本输入字段中，以便它可以显示它。当然，您也可以自由地将消息保存为文本文件并将其读回或编写一个工具来访问 Twitter API 并过滤掉任何看起来像图像代码的消息（特殊标记任何人？眨眼眨眼）。但规则是消息必须先通过 Twitter，然后才能被允许对其进行解码。

祝你好运 350 字节 - 我怀疑你是否能够使用它们。

score 12 · Accepted Answer

发布单色或灰度图像应该会提高可以编码到该空间的图像的大小，因为您不关心颜色。

可能会增加上传三张图像的挑战，这些图像在重新组合时会为您提供全彩色图像，同时在每个单独的图像中仍保持单色版本。

在上面添加一些压缩，它可能开始看起来可行......

好的！！！现在你们引起了我的兴趣。剩下的时间不会做任何工作...

score 9 · Accepted Answer

关于这个挑战的编码/解码部分。 base16b.org是我尝试指定一种标准方法，用于在更高的 Unicode 平面中安全有效地编码二进制数据。

一些特点：

仅使用 Unicode 的私有用户区
每个字符最多编码 17 位；效率是 Base64 的近三倍
提供了编码/解码的参考 Javascript 实现
包括一些示例编码，包括 Twitter 和 Wordpress

抱歉，这个答案对于最初的比赛来说来得太晚了。我独立于这篇文章开始了这个项目，我在这篇文章中发现了这篇文章。

score 8 · Accepted Answer

存储一堆参考图像的想法很有趣。存储 25Mb 的样本图像并让编码器尝试使用其中的一些位组成图像会不会有这么大的错误？有了这么小的管道，两端的机器必然会比通过的数据量大得多，那么 25Mb 的代码、1Mb 的代码和 24Mb 的图像数据有什么区别呢？

（请注意，原始指南排除了将输入限制为库中已有图像的可能性——我不建议这样做）。

score 8 · Accepted Answer

愚蠢的想法，但sha1(my_image)会导致任何图像的“完美”表示（忽略碰撞）。明显的问题是解码过程需要大量的暴力破解。

1 位单色会更容易一些。每个像素变成 1 或 0，因此对于 100*100 像素的图像，您将拥有 1000 位数据。由于 SHA1 哈希是 41 个字符，我们可以将三个信息合二为一，只需要暴力破解 2 组 3333 位和一组 3334 （尽管即使这样可能仍然是过度的）

这并不完全实用。即使使用固定长度的 1 位 100*100px 图像，也有..，假设我没有计算错误，49995000 个组合，或 16661667 拆分为三个。

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

score 8 · Accepted Answer

这里的压缩很好。

http://www.intuac.com/userport/john/apt/

http://img86.imageshack.us/img86/4169/imagey.jpg http://img86.imageshack.us/img86/4169/imagey.jpg

我使用了以下批处理文件：

capt mona-lisa-large.pnm out.cc 20
dapt out.cc image.pnm
Pause

生成的文件大小为 559 字节。

score 0 · Accepted Answer

想法：你能用字体作为调色板吗？尝试将图像分解为一系列向量，尝试用向量集的组合来描述它们（每个字符本质上都是一组向量）。这是使用字体作为字典。例如，我可以将 al 用于垂直线，将 - 用于水平线？只是一个想法。