压缩细胞自动机

细胞自动机很酷的东西玩多变式相似康威生活游戏,阿别良沙比,兰顿循环并布赖恩脑,但在这个博客柱子中,我只谈最简单类型手机自动机:单维手机自动机

最简单类型一维自动机调用初级细胞自动机.运行数组,每个数组可有两种状态:开关或0从初始序列开始,下一个序列基于简单规则计算:细胞下一状态仅取决于细胞本身当前状态及其两个邻接

举例说,这里是初级细胞自动机 命名为“规则22”

内自动机细胞开机 上一代完全开机或关闭规则使用Wolfram代码介绍者斯蒂芬沃尔夫拉姆.基本细胞自动机只有8=2³特定单元格及其近邻的可能配置,对每种配置只有两种选择产生新状态,因此有256=2⁸不同的初级CAs可用8位数描述上图规则可用二进制数00010110或小数表示:22

一维细胞自动机进化二维图像,先从顶部几行单元格开始,再从下方数行画数代数规则22中,如果你从上行单黑格开始,512代后图如下:

有趣的是,结果图像看起来像很多塞尔宾斯基三角形.数个初级CA长成像最简单例子分形:图像在不同尺度上自迭结构

期望图像多重复性结构 从简单规则生成 必须很好压缩和它一样视图像格式而定

装模作样JPEG上图压缩得不好:它重79KB质量90,这甚至不是无损的即使是最小质量, 仍然16KB, 并在此质量设置上,压缩手工艺品相当差:

装模作样巴布亚新几内亚图像只有3.4KB 无损So取右格式可多问题,确实如此使用云化工具时,不必担心:使用f_aut,q_aut高山市阅读更多并自动获取最合适的图像格式和质量设置-在这种情况下,这将是无损PNG

例子中,PNG表现得非常好,因为图像中多次精确重复PNG基础变频算法用回引用替换完全复制数 保存多字节

并非所有细胞自动机都产生易压缩复用模式

规则30从单黑单元格启动时产生图像如下:

215KB质量为90JPEG,而PNG质量为24KB-而Sierpinski三角图像同维为3.4KB/

规则30创建模式引人入胜:左侧它重复性,但在右侧它变得更混乱三角结构出现,但它们定位似随机有趣的是,自然界中似乎有进程 引导相似模式,像外壳约束织物海螺:

Image版权c 2005Richard Ling,CC-BY-SA3.0

PNG运行良好 重复图像像规则22, 因为它“看到”重复并高效编码不见细胞自动机底层规则, 所以,如果那些规则导致混乱突发行为, 它会陷入麻烦GIF无损Web

但如果我告诉你有图像格式 基本上可以只读规则, 并压缩图像非常好, 不论那些规则实际导致什么?

MANIAC编码FLIF系统完全可以做到这一点MANIAC树完全匹配初级CA规则,确保规则8配置都对应算术编解码器的不同上下文概率直达0或1位数 编码比特近零成本

规则22图像为3.4KBPNG文件,仅83字节FLIF文件规则30图像即24KBPNG,仅92字节FLIF

上方两张CA图像(如果启动javascript)实际上是FLIF文件,用javascript解码多填充调用多边FLIF.

最小FLIF文件编码器命令行选项

flif-NX1

选项N级令编码器使用非互换格式, 编码自上而下, 和自动机进化相似默认为内插值, 表示编码器无法“ 看”结构, 因为它从图像上方编码像素, 导致差得多压缩 。选项X1无关紧要允许算术编解码器使用更多极端机率(1/4096而不是默认2/4096),使比特成本接近零

动画图显示规则22图像大小并用多行使用不同图像压缩格式注意Y轴对数

if you want an even experienceFLIF文件内含50兆像素规则30进化页面文件大小 :

令人惊讶的是,丢失格式在这个图像上表现多差,不是吗?PNG和无损WebP彼此如此近近 — — 这并不奇怪,如果你知道它们基于相似的entroy编码方法,但仍然是如此。对我而言(FLIF的作者)上表最美的一点是FLIF用几级大小击败任何其他

现在,当然你不应该从类似的东西中 画出太多结论这是一种非常特殊图像,表示FLIF最优例假想,而其他格式则接近最优例假想产生图像并非难事, 转表压缩优异PNG或WebP,

FLIF可学习所有初级细胞自动机,但也可处理一些复杂自动机举个例子,如果允许下一状态的单元格不仅依赖当前状态和邻接,而且还依赖当前状态前一状态细胞自动机

此处,我随机初始化顶行,FLIF文件略大点:269字节为第一张图像,240字节为第二张图像。相应的PNG文件为16KB和32KB

没有理由只使用两种颜色(或状态)。使用更多状态时,简洁描述规则会变得更难点,因为不同的自动机数快速增长3州76.25亿^27号)自动机,如果你只看细胞及其两个邻里,你需要一个27位数的永久数描述它们

简化事物可查看完全细胞自动机中子集完全CA中新状态仅依赖总和当前状态正考虑中迫使某些对称举例说,配置0,2,1必须产生与配置1,2,0或配置11,1等同的新状态结果,你需要少位数来指定全语CA3个单元格状态,总和介于0至6之间,7配置中每种都可能有3个新状态,7个定时数足够,2187全数3自动机

其中之一是规则1599,这是我最喜爱的全数CA看上去像这个

从单1单元格开始,规则1599生成复杂模式,持续约8000行并停位排序,留留留几条复用模式,约700列宽度,永久持续899字节FLIF文件编码整个趣味部分-720x9900图像, 所以我不让你浏览器解码

取文件大小动画图

在此图中,我限制MINIAC树数学习迭代可以看到文件大小开始随图像增长, 似乎花点时间FLIF“图解出”游戏规则完全化文件大小实际下降,同时学习规则, 并慢慢重发, 以近零成本编码额外像素3000行时FLIF文件仍然只有667字节,WebP和PNG约140千兆字节,损耗JPEG接近1兆字节

从所有这一切中得出一个显而易见的结论手机自动机图像不使用损压缩或泛型高结构人工图像 多细节无关新事,但我认为上举例子可以很好地推下点

期望新趣味是 不同无损图像压缩格式 可能大相径庭如果格式能以某种方式捕捉图像的“感知度”,它也许能极强压缩它对PNG(和无损WebP)来说,这种“最佳案例”假想精确重复.FLIF比较难描述何谓最佳案例,

LIF图片展示javascript多填我希望你喜欢它