Two-dimensional Source Coding by means of Subblock Enumeration
Two-dimensional Source Coding by means of Subblock Enumeration
复制标题
通过子块枚举的二维源编码
DOI：
10.1109/isit.2017.8006540
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Takahiro Ota and Hiroyoshi Morita
中科院分区：
文献类型：
--
作者：
Takahiro OTA;Hiroyoshi MORITA;and Akiko MANADA;Takahiro Ota and Hiroyoshi Morita
通过子串枚举（CSE）的无损压缩技术是一种众所周知的一维（1D）源的无损压缩算法。CSE使用从输入源的圆形字符串构建的概率模型对源进行编码。CSE通过将二维源的一行像素作为扩展字母表的符号来处理，适用于图像等二维源。在CSE编码过程的初始阶段，我们需要输出扩展字母表中所有符号的出现次数，因此当源的规模变大时，时间复杂度呈指数增长。为了降低时间复杂度，我们提出了一种新的CSE，它可以逐块编码而不是逐行编码。该算法使用二维输入源的平面环面作为概率模型，而不是源的圆形串。此外，我们还证明了该算法对于二维一般源的渐近最优性。
A technique of lossless compression via substring enumeration (CSE) is a well-known lossless compression algorithm for a one-dimensional (1D) source. The CSE uses a probabilistic model built from the circular string of an input source for encoding the source. The CSE is applicable to two-dimensional (2D) sources such as images by dealing with a line of pixels of 2D source as a symbol of an extended alphabet. At the initial step of the CSE encoding process, we need to output 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 the time complexity, we propose a new CSE which can encode a 2D source in block-by-block instead of line-by-line. 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.