Image decomposition based on Constrained Inclusion-Exclusion Principle

基于约束包含-排除原理的图像分解

• 批准号: 15500012
• 负责人: ITO Akira
• 金额: $ 0.9万
• 依托单位: Yamaguchi University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500012/
• 关键词: image compression; region quadtree; state minimization; matrix L-system; two-dimensional finite automata; inkdot; pebble; rotated input; 交代性; 領域計算量; Pシステム; 2値画像; Lシステム; L-システム; 伝統的パターン; 断層画像; CTスキャン; 連結性; 4分木; 有限オートマトン; 状態遷移図; 簡略化; カ

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.

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

项目成果

Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs

具有旋转输入的三路二维确定性有限自动机

• 发表时间: 2005
• 期刊: IEICE Transactions on Information and Systems E88-D, No.1
• 作者: Y.Uno;et al.;H.Hirakawa
• 通讯作者: H.Hirakawa

Alternating Inkdot is Better than Nondeterministic Pebble over Two-Dimensional Languages

在二维语言上，交替墨点优于非确定性卵石

• 发表时间: 2004
• 期刊: Proceedings of the Third International Conference on Information
• 作者: A.Inoue;A.Ito;K.Hiraishi;K.Inoue
• 通讯作者: K.Inoue

Three-Way Two-Dimensional Alternating Finite Automata with Rotated Inputs

具有旋转输入的三路二维交替有限自动机

• 发表时间: 2006
• 期刊: Information Sciences 176
• 作者: Taro Suzuki;Satoshi Okui;H.Hirakawa
• 通讯作者: H.Hirakawa

A Note on One-pebble Two-dimensional Turing Machines

关于单卵石二维图灵机的注记

• 发表时间: 2004
• 期刊: Information Sciences 162
• 作者: 菊野亨;他;A.Inoue
• 通讯作者: A.Inoue

吉田憲司, 伊藤暁, 井上克司, 王躍: "4分木の簡略化に基づく画像圧縮方法について"電気・情報関連学会中国支部第54回連合大会講演論文集. 510-510 (2003)

Kenji Yoshida、Akira Ito、Katsushi Inoue、Yu Wang：“一种基于四叉树简化的图像压缩方法”中国电气和信息相关协会第54届会议论文集510-510（2003）。