Image decomposition based on Constrained Inclusion-Exclusion Principle

我们所提出的约束重叠图像分解方法对于区域四叉树的归一化问题是有效的。研究了自动机理论中已知的状态最小化算法在四叉树压缩问题中的实用性。结果，与现有的图像压缩技术（如二进制图像的GIF或PNG）相比，我们获得了压倒性的高性能比。接下来，我们提出了矩形纸系统折叠过程的模型，称为矩阵l系统，并通过计算机仿真表明，它可以生成各种未知的惊人图像。在理论方面，我们解决了一个长期存在的开放性问题，即二维交替单墨点有限自动机是否比二维单卵石有限自动机更强大。此外，我们还表明，对于log n和log n之间的空间复杂性，单块交替图灵机比非确定性图灵机更强大。我们还获得了一些关于具有旋转输入的三维二维确定性交替有限自动机的接受能力的结果，例如基于组合自动机数量的层次结构或and型和or型组合之间的比较。

It is known that the image decomposition with constrained overlap proposed in our research is effective for the normalization problem of region quadtrees. We investigate the practicality of application of state minimization algorithm known in automata theory to quadtree compression problem. As the results, we obtained an overwhelming high performance ratio compared with the existing image compression techniques such as GIF or PNG for binary images. We next proposed the model for systematic folding process of rectangular papers, call matrix L-system and with computer simulation showed that it can generate various amazing images not known before.On theoretical part, we solved a long-standing open problem whether or not two-dimensional alternating one-inkdot finite automata are more powerful than two-dimensional one-pebble finite automata. Furthermore, we showed that one-pebble alternating Turing machines are more powerful than nondeterministic ones for space complexities between loglog n and log n. We also obtained some results on the accepting power of three-way two-dimensional deterministic and alternating finite automata with rotated inputs, such as hierarchy based on the number of combined automata or comparison between AND-type and OR-type combinations.