Compression of two-dimensional data
Compression of two-dimensional data
复制标题
二维数据的压缩
DOI：
--
复制
发表时间：
1986
影响因子：
2.5
通讯作者：
J. Ziv
中科院分区：
文献类型：
--
作者：
A. Lempel;J. Ziv
研究了有限状态编码器对单个图像，即数据的二维阵列的无失真可压缩性。对于每一幅无限大的图片i，一个量
HO(I)被定义为i的可压缩性，它被证明是任何有限状态信息无损编码器对i所能达到的压缩比的渐近可达下界。这是通过构造性编码定理和相反的编码定理来证明的，除了它们的渐近意义之外，还可以为有限的和实际的数据压缩任务提供有用的标准。所提出的图像可压缩性还具有人们期望和要求的性质，即对于无限图像的任意概率集合，适当定义了二维熵的概念。虽然定义是
HO(I)允许对不同的图像使用不同的机器，构造性编码定理导致了对每一幅图像渐近最优的通用压缩方案。结果可以很容易地扩展到任意有限维的数据数组。
Distortion-free compressibility of individual pictures, i.e., two-dimensional arrays of data, by finite-state encoders is investigated. For every individual infinite picture I , a quantity
ho(I) is defined, called the compressibility of I , which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved for I by any finite-state information-lossless encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, might also provide useful criteria for finite and practical data-compression tasks. The proposed picture compressibility is also shown to possess the properties that one would expect and require of a suitably defined concept of two-dimensional entropy for arbitrary probabilistic ensembles of infinite pictures. While the definition of
ho(I) allows the use of different machines for different pictures, the constructive coding theorem leads to a universal compression scheme that is asymptotically optimal for every picture. The results are readily extendable to data arrays of any finite dimension.