A Quadsection Algorithm for Grammar-Based Image Compression
スポンサーリンク
概要
- 論文の詳細を見る
For the purpose of text compression, grammar-based compression, which is to find a small grammar that generates a given data, has been well-studied. In this technical report, we apply this methodology to compression of rectangular image data. We first define a context-free rectangular image grammar (CFRIG) by extending the context-free grammar. Then we propose a quadsection type algorithm by extending a bisection type algorithm for grammar-based compression of text data. We show that our proposed algorithm approximates in polynomial time the smallest CFRIG within a factor of O(n4/3), where an input image data is of size O(n) × O(n). We also present results on computational experiments on the proposed algorithm.
- 一般社団法人情報処理学会の論文
- 2010-05-14
著者
-
Tatsuya Akutsu
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Morihiro Hayashida
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Peiying Ruan
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Peiying Ruan
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Tatsuya Akutsu
Bioinformatics Center Institute For Chemical Research Kyoto University
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- RNA-RNA Interaction Prediction Using Integer Programming with Threshold Cut
- A Quadsection Algorithm for Grammar-Based Image Compression
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- Conditional Random Field Approach to Prediction of Protein-protein Interactions Using Domain Information
- Integer Programming and Dynamic Programming-based Methods of Optimizing Control Policy in Probabilistic Boolean Networks with Hard Constraints
- An Improved Clique-Based Method for Computing Edit Distance between Rooted Unordered Trees
- Prediction of protein residue contacts using discriminative random field
- Prediction of protein residue contacts using discriminative random field