A Universal Two-Dimensional Source Coding by Means of Subblock Enumeration
- 1 February 2019
- journal article
- research article
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Vol. E102.A (2) , 440-449
Abstract
The technique of lossless compression via substring enumeration (CSE) is a kind of enumerative code and uses a probabilistic model built from the circular string of an input source for encoding a one-dimensional (1D) source. CSE is applicable to two-dimensional (2D) sources, such as images, by dealing with a line of pixels of a 2D source as a symbol of an extended alphabet. At the initial step of CSE encoding process, we need to output the number of occurrences of all symbols of the extended alphabet, so that the time complexity increases exponentially when the size of source becomes large. To reduce computational time, we can rearrange pixels of a 2D source into a 1D source string along a space-filling curve like a Hilbert curve. However, information on adjacent cells in a 2D source may be lost in the conversion. To reduce the time complexity and compress a 2D source without converting to a 1D source, we propose a new CSE which can encode a 2D source in a block-by-block fashion instead of in a line-by-line fashion. The proposed algorithm uses the flat torus of an input 2D source as a probabilistic model instead of the circular string of the source. Moreover, we prove the asymptotic optimality of the proposed algorithm for 2D general sources.Keywords
This publication has 15 references indexed in Scilit:
- Compression by Substring Enumeration with a Finite Alphabet Using Sorting2018
- A Compact Tree Representation of an AntidictionaryIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2017
- Lossless Data Compression via Substring Enumeration for k-th Order Markov Sources with a Finite AlphabetIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2016
- Efficient Implementation and Empirical Evaluation of Compression by Substring EnumerationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2016
- Improving Compression via Substring Enumeration by Explicit Phase Awareness2014
- The universality and linearity of compression by substring enumeration2011
- Asymptotic Optimal Lossless Compression via the CSE Technique2011
- Handbook of Data Compression2010
- Lossless Data Compression via Substring Enumeration2010
- Information-Spectrum Methods in Information Theory2003