Efficient Algorithms for Lossless Data and Image Compression

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Proposal 122293 U of Ill Urbana-Champaign PI: Bresler, Yoram In 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, and medical 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 it has 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 or PPM, 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 good compression 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 of transitions 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.