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.

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