A Quadsection Algorithm for Grammar-Based Image Compression

• Morihiro Hayashida

  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

抄録

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.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.

収録刊行物

• 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告

  情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 78 S1-S6, 2010-05-21

詳細情報

• CRID: 1570572702598115328
• NII論文ID: 110007993903
• NII書誌ID: AN10505667
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles