A Quadsection Algorithm for Grammar-Based Image Compression

• HAYASHIDA MORIHIRO

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• RUAN PEIYING

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• AKUTSU TATSUYA

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

Abstract

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.

Journal

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

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

Details

• CRID: 1570572702598115328
• NII Article ID: 110007993903
• NII Book ID: AN10505667
• ISSN: 09196072
• Text Lang: en
• Data Source:
  • CiNii Articles