Affiliations: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto, Japan
Correspondence:
[*]
Corresponding author: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan. E-mail: takutsu@kuicr.kyoto-u.ac.jp.
Abstract: Grammar-based compression is to find a small grammar that generates a given data and has been well-studied in text compression. In this paper, 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(n)4/3, where an input image data is of size O(n) × O(n). Furthermore, we practically improve the proposed algorithm by adding several rules concerning sub-images. We also present results on computational experiments on the proposed algorithms.
