Twitter图像编码挑战
如果一张图片的价值是1000字,那么您可以在140个字符中填入多少图片?
注意 :这就是人! 赏金截止日期在这里,并经过一些艰难的审议后,我决定Boojum的入场只是几乎削弱了山姆胡塞瓦的。 一旦我有机会将它们写出来,我会发布更详细的说明。 当然,每个人都应该随时继续提交解决方案并改善人们投票的解决方案。 感谢所有提交和输入的人; 我喜欢他们。 这对我来说运行起来非常有趣,我希望对于参赛者和观众来说都很有趣。
我偶然发现了一篇关于尝试将图像压缩为Twitter评论的有趣文章,该主题中的许多人(以及Reddit上的一个主题)都提供了有关可以执行此操作的不同方式的建议。 所以,我认为这将是一个很好的编码挑战; 让人们把钱放在他们的嘴巴上,并且展示他们对编码的想法如何能够在你有限的空间中获得更多的细节。
我向你提出一个通用的系统,用于将图像编码成140个字符的Twitter消息,并将它们再次解码为图像。 您可以使用Unicode字符,因此每个字符的字符数超过8位。 但是,即使允许使用Unicode字符,您也需要将图像压缩成非常小的空间; 这肯定会是一种有损压缩,因此必须对每个结果的外观做出主观判断。
这是原作者Quasimondo从他的编码中得到的结果(图像是根据知识共享署名 - 非商业性许可授权的):
你能做得更好吗?
规则
U+0000
- U+10FFFF
,排除非字符( U+FFFE
, U+FFFF
, U+
Ñ FFFE
, U+
Ñ FFFF
,其中n为1
- 10
十六进制和范围U+FDD0
- U+FDEF
)和替代码点( U+D800
- U+DFFF
)。 它可以用您选择的任何合理编码输出; GNU iconv
支持的任何编码都将被认为是合理的,并且您的平台本地编码或区域设置编码可能是一个不错的选择。 有关更多详细信息,请参见以下Unicode注释 为了保持用户界面的一致性,您的程序必须具有以下行为:
encode
或decode
来设置模式。 您的程序必须以下列一种或多种方式进行输入(如果您实现了获取文件名的文件名,那么如果缺少文件名,还可以从stdin和stdout中读取和写入):
从标准中输入并在标准输出上产生输出。
my-program encode <input.png >output.txt
my-program decode <output.txt >output.png
从第二个参数中指定的文件获取输入,并在第三个文件中指定的文件中生成输出。
my-program encode input.png output.txt
my-program decode output.txt output.png
方针
这些基本上是可能被破坏的规则,建议或评分标准:
评分标准
作为在选择我接受的解决方案时如何排名解决方案的一般指南,可以说我可能会在25分制评估解决方案(这非常粗糙,我不会直接评分任何东西,只是使用这作为基本指导):
参考图像
一些人已经要求参考图像。 这里有一些你可以尝试的参考图片; 如果您需要这些版本,则会嵌入更小的版本,它们都链接到较大版本的图像:
奖
基于上述标准,我提供了500个代表奖金 (加上StackOverflow启用的50个),以满足我最喜欢的解决方案。 当然,我鼓励其他人也在这里投票选出他们最喜欢的解决方案。
关于截止日期的说明
这场比赛将持续到5月30日星期六下午6点为止,但我不能说明它的结束时间。 它可能在5点到7点的任何地方。 我保证我会查看下午2点前提交的所有参赛作品,我将尽我所能查看下午4点之前提交的所有参赛作品; 如果在那之后提交解决方案,在我必须作出决定之前,我可能没有机会给他们一个公平的看法。 此外,您提交的越早,投票的机会越多,能够帮助我选择最佳解决方案,因此请尽早提交,而不是在截止日期之前提交。
Unicode笔记
在允许使用哪些Unicode字符方面也存在一些混淆。 可能的Unicode代码点的范围是U+0000
到U+10FFFF
。 有一些代码点永远不会在任何公开的数据交换中用作Unicode字符; 这些是非字符和替 代码点 。 Noncharacters都在Unidode标准5.1.0节16.7定义为值U+FFFE
, U+FFFF
, U+
Ñ FFFE
, U+
Ñ FFFF
,其中n为1
- 10
十六进制和范围U+FDD0
- U+FDEF
。 这些值旨在用于特定于应用程序的内部使用,并且符合的应用程序可能会将这些字符从它们处理的文本中去除。 代码代码点在Unicode标准5.1.0第3.8节中定义为U+D800
- U+DFFF
,用于UTF-16基础多语言平面以外的字符编码; 因此,不可能直接用UTF-16编码来表示这些代码点,并且用任何其他编码对它们进行编码是无效的。 因此,为了本次比赛的目的,我将允许任何将图像编码为U+0000
- U+10FFFF
范围内不超过140个Unicode代码点的程序,但不包括上述定义的所有非字符和代理对。
我更喜欢只使用分配字符的解决方案,甚至使用分配字符的聪明子集或使用他们使用的字符集做一些有趣的事情的更好的解决方案。 有关指定字符的列表,请参阅Unicode字符数据库; 请注意,某些字符是直接列出的,而有些字符仅作为范围的开始和结束列出。 还请注意,代理代码点在数据库中列出,但如上所述被禁止。 如果您想利用字符的某些属性来使输出的文本更加有趣,可以使用各种可用的字符信息数据库,例如指定的代码块列表和各种字符属性。
由于Twitter没有指定它们支持的确切字符集,因此对于实际上并未与Twitter一起使用的解决方案,我会宽松,因为某些字符会计算额外或某些字符被剥离。 最好但不要求所有的编码输出应该能够通过Twitter或其他微博服务(如identi.ca)无损地传输。 我看到一些文档声明Twitter实体对<,>和&进行编码,因此分别将它们计为4个,4个和5个字符,但我没有对自己进行测试,并且他们的JavaScript字符计数器看起来不像以这种方式来计算它们。
提示和链接
好吧,这里是我的:nanocrunch.cpp和CMakeLists.txt文件,使用CMake来构建它。 它的大部分图像处理都依赖于Magick ++ ImageMagick API。 它还需要用于字符编码的GMP库,用于算术运算。
我将我的解决方案从分形图像压缩中解放出来,并带有一些独特的曲折。 基本思路是拍摄图像,将副本缩小到50%,然后在各个方向上查找与原始图像中的非重叠块类似的碎片。 这种搜索需要采取非常暴力的方法,但这样可以更容易地引入我的修改。
第一个修改是,我的程序并不只是看90度旋转和翻转,而是考虑了45度的方向。 它每块更多一块,但它极大地有助于图像质量。
另一方面是为每个块的每个颜色分量存储对比度/亮度调节太昂贵。 取而代之的是,我存储了一个高度量化的颜色(调色板只有4 * 4 * 4 = 64种颜色),它只是以某种比例混合在一起。 在数学上,这相当于每种颜色的可变亮度和恒定对比度调整。 不幸的是,这也意味着翻转颜色没有负面对比。
一旦计算出每个块的位置,方向和颜色,它就会将其编码为UTF-8字符串。 首先,它会生成一个非常大的bignum来表示块表中的数据和图像大小。 这种做法与Sam Hocevar的解决方案类似 - 一种根据位置而变化的大数字。
然后它将其转换为任何可用字符集大小的基础。 默认情况下,它充分利用指定的Unicode字符集,减去小于,大于,和号,控制,组合,代理和私人字符。 它不漂亮,但它的工作原理。 您也可以将默认表注释掉,然后选择可打印的7位ASCII(不包括<,>和&字符)或CJK Unified Ideographs。 可用的字符代码表存储一个运行长度编码,交替运行无效和有效字符。
无论如何,下面是一些图像和时间(以我的旧3.0GHz P4测量),并在上述完整分配的unicode集中压缩为140个字符。 总的来说,我很满意他们是如何结果的。 如果我有更多时间来处理这个问题,我可能会尝试减少解压缩图像的块度。 不过,我认为这个结果对于极端压缩比来说非常好。 解压缩的图像是有点印象的,但我发现相对容易看到位如何对应于原件。
堆栈溢出标志(8.6s编码,7.9s解码,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
编辑:CJK统一字符
Sam在有关使用CJK的评论中问道。 以下是Mona Lisa的一个版本,压缩为CJK Unified字符集的139个字符:
i tin驞凄凄凄蛥拗隤慛絖铨馿渫櫰矍昀鰛掾撄粂敽牙粳擎蔍螎葙峬覧绌蹔抆惫冧筇哜搀沄芯譶辍浍垝黟偞媄童竽梀韠镰猳閺狌而膻喙伆杇婣唆鐤諽鷍鸮駫抢毤埙悖萜愿旖鞰萗勹鈱哳垬濅鬒秀瞛洆认気狋异闼籴珵仾氙熜謋繴茴晋髭杍嚖熥勋縿饼珝爸擸萿
在我使用的程序顶部的调整参数是:19,19,4,4,3,10,11,1000,1000。我还评论了number_assigned和code的第一个定义,并且未注释掉最后定义它们以选择CJK Unified字符集。
图像文件和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现在有资格参与竞争。 变化:
人物 : 133
时间 :几秒钟
v2解码http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png编码和解码后(版本2)
正如你所看到的,这次有一些文物。 这不是对方法的限制,而是我转换中某处的错误。 当点数超出范围0.0 - 127.0时,这些文物就会发生,并且我试图限制它们的尝试取得了不同的结果。 解决方法是简单地缩小图像,但是我无法缩放实际点而不是美工板或组矩阵,现在我太累了,现在无法照顾。 简而言之,如果你的积分处于支持范围内,它通常会起作用。
我相信中间的扭结是由于把手移动到与其相关的手柄的另一侧。 基本上,这些点在一开始就太靠近了。 在压缩之前对源图像运行简化过滤器应该修复这个问题并修剪一些不必要的字符。
更新 :这种方法适用于简单的对象,所以我需要一种简化复杂路径和减少噪音的方法。 我使用Inkscape来完成这项任务。 使用Inkscape梳理出不必要的路径,但我没有时间去尝试自动化。 我使用Inkscape的“简化”功能制作了一些示例svgs,以减少路径数量。
简化工作确定,但它可以用这么多路径慢。
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简化和despeckled。
trianglelulated 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输出要容易得多。
我的完整解决方案可以在http://caca.zoy.org/wiki/img2twit找到。 它具有以下特点:
http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png
蜥秓鋖筷聝诿缰咱腶漷庯祩皙靊谪獜岨幻寤厎趆脘搇梄踥桻理戂溥欇渹里軱骿苸髙骟市簶璨粭浧鳖捕弫潮衍蚙瀹岚玧霫鏓蓕戏债鼶襋躻弯袮足庭侅旍凼飙驱据嘛掔倾诗籂阉嶹婻椿模墤渽緛赐更当棫武婩缣逡荨璙杯翉珸齸陁颗鳣悯掷舥攩寉鈶兓庭璱篂鰀干丕耓庁铼努樀肝亖弜喆蝞躐葌熲谎蛪曟暙刍镶媏嘝骕慸盂氤缰殾譑
以下是对编码过程的粗略概述:
这是解码过程:
我相信这个程序最原始的部分就是比特流。 我不打包位对齐值( stream <<= shift; stream |= value
),而是打包不在两个幂范围内的任意值( stream *= range; stream += value
)。 这需要数字计算,当然要慢很多,但当使用20902主要CJK字符时(这是我可以放入数据的三点),它给了我2009.18位而不是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字节以上的图片。 在右边,Mona Lisa使用这里描述的方法压缩到534字节(这里提到的字节是指数据字节,因此忽略了使用Unicode字符浪费的位):
http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png
编辑 :用最新版本的图像替换CJK文本。
链接地址: http://www.djcxy.com/p/20559.html