Efficient Algorithms for Lossless Data and Image Compression

尽管近年来人们关注于音频、图像和视频的有损压缩，但无损数据压缩在文本文件、传真、软件可执行文件和医学成像等应用中仍然至关重要。通用源编码算法，处理统计未知的源，是特别重要的。通用编码方法是为在广泛的可能源上实现通用性能而设计的。在这些方法中，对源参数进行隐式或显式估计，并相应地对序列本身进行编码。因此，通用方法的编码长度大于熵；额外的编码长度，称为冗余，满足Rissanen的基本下界。通用数据压缩的研究重点一直是减少冗余。从这个意义上说，上下文树加权（CTW）已经达到了重要的一类树源的最终目标，因为它本质上达到了Rissanen的界。然而，除了低冗余之外，通用编码方法还必须计算速度快，并且占用很少的内存。两种主要的方法，CTW或ppm（一种通过各种启发式方法对实际使用进行微调的压缩方法）在这些方面都不是特别出色。因此，提出的研究的主要目标是开发具有快速计算和低内存使用的算法，同时提供接近Rissanen边界的压缩。与目前一些最有效的高性能通用压缩算法一样，本文提出的方法基于Burrows Wheeler变换（BWT）。BWT是一种可逆变换，其输出包含符号近似独立同分布的段。由于这种与分段识别码（PIID）的相似性，使用PIID方法压缩BWT输出可以产生良好的压缩结果。然而，这种方法不能实现接近Rissanen界的普遍编码冗余，因为它们需要（无论是隐式的还是显式的）额外的比特来编码BWT输出中段之间的转换位置。认识到这种隐藏的开销，本项目建议重新审视基于BWT的方法及其与基本冗余界限的关系。该项目将探索如何缩小传统的基于BWT的方法与Rissanen的界限之间的差距，同时保持BWT的计算效率。将这种方法应用于无损图像压缩是一个特别的挑战。由此产生的算法将具有线性复杂性，并且在计算和/或内存使用方面优于任何具有可比渐近压缩性能的当前算法。这些算法的一些版本也将具有简单的结构，允许快速的硬件实现。此外，本研究将揭示上下文建模在通用无损图像压缩中的作用。由于线性复杂性的近rissanen冗余很难被击败，我们期望通用编码文献从压缩改进转向实现和实用性。

Proposal 122293U of Ill Urbana-ChampaignPI: Bresler, YoramIn spite of the focus in recent years on lossy compression of audio, images, and video, lossless data compression remains crucial in applications such as text files, facsimiles, software executables, andmedical imaging. Universal source coding algorithms, which deal with sources whose statistics are unknown, are of particular importance. Universal coding methods are designed for universal performance over a broad class of possible sources. In these methods the source parameters are estimated, either implicitly or explicitly, and the sequence itself is encoded accordingly. Therefore the coding length for universal methods is g eater than the entropy; the extra coding length, called the redundancy satisfies a fundamental lower bound by Rissanen. The focus of research in universal data compression has been on reducing redundancies. In this sense, context tree weighting (CTW) has achieved the ultimate goal for the important class of tree sources, because ithas essentially achieved Rissanen 's bound. However, in addition to low redundancies, a universal coding method must be computationally fast, and consume little memory. Neither of the two leading methods, CTW orPPM, a compression method that has been fine-tuned by various heuristics for practical use, are particularly strong performers in these respects. Therefore, the main goal of the proposed research is to develop algorithms featuring fast computation and low memory use, while providing compression near Rissanen 's bound. Like some of the most efficient high-performance universal compression algorithms to-date, the proposed approach is based on the Burrows Wheeler transform (BWT). The BWT is an invertible transform whose output contains segments in which symbols are approximately independent identically distributed. Owing to this similarity to piecewise i.i.d. (PIID), compressing the BWT output using PIID methods yields goodcompression results. However, such methods cannot achieve universal coding redundancies close to Rissanen 's bound because they require (whether implicitly or Explicitly) extra bits to encode the positions oftransitions between segments in the BWT output. Recognizing this hidden overhead, this project proposes to take a fresh look at BWT based-methods and the relationship to the fundamental redundancy bounds.The project will explore ways to close the gap between traditional BWT-based methods and Rissanen 's bound while retaining the computational efficiency of the BWT. A particular challenge will be to apply this approach to lossless image compression. The resulting algorithms will have linear complexity, and be better than any current algorithm with comparable asymptotic compression performance, in terms of computation and/or memory use. Some versions of these algorithms will also have simple structure, admitting fast hardware implementations. Furthermore, this research will reveal the role of context modeling in universal lossless image compression. Since near-Rissanen redundancies with linear complexity are hard to beat, we expect a shift in the universal coding literature from compression improvement to implementation and practicality.