Efficient Algorithms for Lossless Data and Image Compression

Ill Urbana-ChampaignPI：Bresler，York的提案122293U尽管近年来关注音频、图像和视频的有损压缩，但无损数据压缩在文本文件、传真、软件可执行文件和医学成像等应用中仍然至关重要。处理统计信息未知的信源的通用信源编码算法尤其重要。通用编码方法被设计用于在广泛类别的可能源上的通用性能。在这些方法中，隐式或显式地估计源参数，并且相应地对序列本身进行编码。因此，通用方法的编码长度大于熵；额外的编码长度称为冗余度，满足Rissanen的一个基本下界。通用数据压缩的研究重点一直是减少冗余。从这个意义上讲，上下文树加权达到了重要树源的最终目的，因为它本质上达到了Rissanen的S界。然而，除了低冗余之外，通用编码方法必须在计算上快速，并且消耗很少的内存。CTW和PPM这两种主要的压缩方法都不是在这些方面表现得特别好，这是一种通过各种启发式方法进行了微调的压缩方法。因此，提出的研究的主要目标是开发具有快速计算和低内存使用的算法，同时提供接近Rissanen的S界的压缩。与迄今为止一些最高效的高性能通用压缩算法一样，该方法基于Burrow Wheeler变换(BWT)。BWT是一种可逆变换，其输出包含符号近似独立同分布的段。由于这一点与分段身份证明相似。(PIID)，使用PIID方法对BWT输出进行压缩可获得较好的压缩效果。然而，这种方法不能实现接近Rissanen的S界的通用编码冗余，因为它们需要(无论是隐式的还是显式的)额外比特来编码BWT输出中分段之间的过渡位置。认识到这种隐藏的开销，该项目建议重新审视基于BWT的方法及其与基本冗余界的关系。该项目将探索如何在保持BWT的计算效率的同时缩小传统BWT方法与Rissanen的S界之间的差距。一个特别的挑战将是将这种方法应用于无损图像压缩。所得到的算法将具有线性复杂性，并且在计算和/或内存使用方面优于任何具有类似渐近压缩性能的当前算法。这些算法的一些版本也将具有简单的结构，允许快速的硬件实现。此外，本研究还将揭示上下文建模在通用无损图像压缩中的作用。由于线性复杂度的近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.