Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
A Quadsection Algorithm for Grammar-Based Image Compression
verfasst von : Morihiro Hayashida, Peiying Ruan, Tatsuya Akutsu
Erschienen in: Future Generation Information Technology
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.