Image decomposition based on Constrained Inclusion-Exclusion Principle

点击翻译按钮获取中文摘要

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.