A quadsection algorithm for grammar-based image compression
A quadsection algorithm for grammar-based image compression
复制标题
DOI：
10.3233/ica-2012-0389
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
M. Hayashida;Peiying Ruan;T. Akutsu
中科院分区：
文献类型：
--
作者：
M. Hayashida;Peiying Ruan;T. Akutsu
基于语法的压缩是找到一个小的语法，生成一个给定的数据，并已在文本压缩研究。在本文中，我们应用这种方法来压缩矩形图像数据。首先，我们定义了一个上下文无关的矩形图像文法CFRIG通过扩展上下文无关文法。然后，我们提出了一个四分型算法，通过扩展的二分法算法的基于语法的文本数据压缩。我们证明了该算法在多项式时间内近似于最小CFRIG，其因子为On^{4/3}，其中输入图像数据的大小为On × On。此外，我们实际上改进了该算法，增加了一些关于子图像的规则。我们还提出了所提出的算法的计算实验结果。
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 On^{4/3}, where an input image data is of size On × On. 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.