Advertisement
Published in:
2010 | OriginalPaper | Chapter
A Quadsection Algorithm for Grammar-Based Image Compression
Authors : Morihiro Hayashida, Peiying Ruan, Tatsuya Akutsu
Published in: Future Generation Information Technology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
). We also present results on computational experiments on the proposed algorithm.