Image Compression Papers and Notes



Multiresolutional/Fractal Compression of Still and Moving Pictures

The scope of the present dissertation is deep lossy compression of still and moving grayscale pictures while maintaining their fidelity. Its specific goal is creating a working prototype of a software system for use in low bandwidth transmission of still satellite imagery and weather briefings with the best preservation of features considered important by end users.

The dissertation proposes a set of pyramidal compression algorithms over a loose wavelet basis, designed to minimize the entropy of the image representation. We discuss design principles and trade-offs.

The dissertation also proposes a non-uniform wavelet compression, which lets the user control the amount of distortion and compression in particular, arbitrarily specified, parts of the image: bringing some parts of the image into a sharp focus while progressively blurring the rest.

We develop a regularized discrete derivative of an image, which effectively removes the local background and fine-scale noise. Therefore, it may be used for localizing image patterns regardless of the lighting conditions, etc.

A discovery of the property of self-similarity of the pyramidal image transform has opened up an entirely new approach to compression: zooming out from a (possibly shrunken) low-resolution image producing a sharp and crisp ``natural looking'' high-resolution view. Thin lines remain thin upon expansion, translational invariance in maintained, and gradient fill is perfectly reproduced at any scale.

The multiresolutional transform algorithms and smart image magnification developed for still images are generalized to deal with moving pictures as a three-dimensional, spatio-temporal frame sequence, which permits rapid compression, and has potential for use in video transmission in real time.

The current version is December 1993
Thesis.pdf [1557K]
Ph.D. Thesis, University of North Texas, Denton, TX, December 1993, 134 pp., 3 tables, 51 illustrations, bibliography, 30 titles.

Pyramidal Image Decompositions: A New Look
A poster presented at Data Compression Conference, Snowbird, Utah, 1993

Self-similarity of the Multiresolutional Image/Video Decomposition: Smart Expansion as Compression of Still and Moving Pictures
Data Compression Conference, Snowbird, Utah, 1994


Multiresolutional piecewise-linear image decompositions

The paper introduces a new approach to design of stable tile-effect-free multiresolutional image compression schemes. Rather than discussing convergence and other formal mathematical properties of multiresolutional analysis, the paper focuses on: (i) how quantization errors in decomposition coefficients affect the quality of the decompressed picture; (ii) how the errors propagate in a multiresolutional decomposition; and (iii) how to design a compression scheme where the effect of quantization errors is minimized (visually and quantitatively). The paper also introduces and analyzes the simplest family of Laplacian pyramids which yield multiresolutional piecewise-linear image decompositions. The error propagation analysis presented in the paper has lead to discovery of particular Laplacian pyramids where quantizations errors do not amplify as they propagate, but quickly decay. We discuss extensions to piecewise-quadratic approximations.
The current version is March 1995
DCC95PaperSubmitted.pdf [152K]
The full text of the paper ``Multiresolutional Piecewise-Linear Image Decompositions: Quantization Error Propagation and Design of "Stable" Compression Schemes'' presented as poster at Data Compression Conference, Snowbird, Utah, 1995


Notes on Data Compression Conference '95

This article collects notes and comments on a few presentations at the conference. A sizable part is devoted to a fascinating image compression technique by Dr. Karel Culik. His method achieves 100:1 compression of grayscale pictures without any noticeable distortion. I took a stab at explaining how it works in signal-processing terms, without resorting to finite automata. Culik's method turns out to be related to both fractal compression and zero-tree encoding.
DCC95Impressions.pdf [51K]
The formatted notes

Compression with Iterated Function Systems, Finite Automata and Zerotrees: an elaboration of the relationship between Culik's algorithm, fractal compression and zero-tree encoding


Compression with Iterated Function Systems, Finite Automata and Zerotrees

Fractal image compression, Culik’s image compression and zerotree prediction coding of wavelet image decomposition coefficients succeed solely because typical images possess a significant degree of self-similarity. This commonality is not easy to see, in part due to the vastly differing terminologies used to describe these techniques. The relationship among them turns out not only conceptual similarity but algorithmic reducibility.

The paper offers a plain-term interpretation of Culik’s image compression, a very capable yet undeservingly underrepresented method giving spectacular results. We explain Culik’s technique in image processing rather than formal automata terms. We demonstrate how closely it relates to Iterated Function System (IFS) fractal image compression: an IFS can be exactly transformed into Culik’s image code. Using this transformation, we prove that in a self-similar (part of an) image any zero wavelet coefficient is the root of a zerotree, or its branch.

The paper discusses the zerotree coding of (wavelet/projection) coefficients as a common predictor/corrector, applied vertically through different layers of a multiresolutional decomposition, rather than within the same view. This interpretation leads to an insight into the evolution of image compression techniques: from a causal single-layer prediction, to non-causal same-view predictions (wavelet decomposition among others) and to a causal cross-layer prediction (zerotrees, Culik’s method). A non-causal cross-level prediction appears to be the next step. Will someone take it?

DCC96PaperSubmitted.pdf [64K]
The full text of the paper ``Compression with Iterated Function Systems, Finite Automata and Zerotrees: Grand Unification'', presented as poster at DCC'96: Data Compression Conference, Snowbird, Utah, 1996

Notes on Data Compression Conference '96, with detailed explanations of Culik's algorithm.


Notes on Data Compression Conference '96

This article describes a few most memorable DCC'96 presentations, along with my notes, references, and impressions of them. I talk about compression of images using Weighted Finite Automata (WFA), state of the art in the lossless coding of text, a (near)lossless compression of images, and wavelet coding.

A better half of the notes is devoted to a remarkable and stunning method of compressing images using Finite Automata, which was invented/discovered by Dr. Karel Culik. The notes are the result of pondering over Culik's presentation and paper. Along the way, I noticed and corrected a few typos in his paper. I really took a stab at "reverse-engineering" of the compression and decompression algorithms, showing how they work step-by-step, to the point of showing pseudo-code and tracing through it.

Dr. Culik's website shows examples of WFA (Weighted Finite Automata) compression and contains his bibliography.

DCC96Impressions.pdf [83K]


Dissemination of compressed satellite imagery within the Navy SPAWAR Central Site Product Display environment

This presentation is a case study of integration of compression techniques within a satellite image communication component of an actual tactical weather information dissemination system. The paper describes history and requirements of the project, and discusses the information flow, request/reply protocols, error handling, and, especially, system integration issues. We make a case for non-uniform compression of satellite imagery and demonstrate its implementation. We pay special attention to challenges of moving the system towards standard, non-proprietary protocols (smtp and http).
The paper, published in the proceedings of the NASA Science Information Management and Data Compression Workshop SIMDCW'95, James C. Tilton, Ed. - pp.123-130. (NASA Conference publication 3315)

The presentation at the NASA workshop: a collection of web pages. I indeed presented the paper in a browser (Netscape). It was 1995; the Web was new.