Efficient Algorithms for Lossless Data and Image Compression

无损数据和图像压缩的高效算法

• 批准号: 0122293
• 负责人: Yoram Bresler
• 金额: $ 8.29万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0122293&HistoricalAwards=false
• 关键词: Efficient; Algorithms; Lossless; Data; Image

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.

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