HELP! * GREY=local Full HTML for

LOCAL foilset Master Foils for Compression Presentation for HPDC95 Tutorial

Given by Roman Markowski and Geoffrey Fox at HPDC95 Pentagon City on August 1,1995. Foils prepared July 28,1995
Abstract * Foil Index for this file

See also color IMAGE
This set of foils describes image and video compression schemes concentrating on Wavelets which seem most powerful although JPEG and MPEG using related but less efficient Fourier technology will be used much more widely initially
JPEG, JBIG, Fractal for images and MPEG, H.261 schemes for video clips are briefly reviewed
Wavelets are described in detail

Table of Contents for full HTML of Master Foils for Compression Presentation for HPDC95 Tutorial

1 HPDC95 Module on
Compression
August 1,1995
2 Abstract of Compression Module
3 Compressing Still and Moving Images
4 Image Compression
5 Performance Measures
6 JPEG - Joint Photographic Experts Group
7 JBIG - Joint-bi-level Image Experts Group
8 Fractal Compression
9 Introduction to Wavelets
10 Discrete Wavelet Transform
11 Wavelet Transform Characteristics
12 Daubechie's Mother wavelets
13 Mathematical Structure of Discrete Wavelet Transform-I
14 Matrix Structure of a Simple Wavelet Transformation
15 Mathematical Structure of Discrete Wavelet Transform-II
16 How Image wavelet compression works
17 How wavelet compression works
Pictorially
18 2D Forward/inverse wavelet transform
19 2D Forward wavelet transform
20 2D Inverse wavelet transform
21 Wavelets -- Quantization
22 Wavelets -- Coding
23 Wavelets in Telemedicine
24 Comparison W6+VLC, Biorthogonal+VLC, JPEG image coders
25 Video Compression -- I
26 Video Compression -- II
27 MPEG - Moving Picture Experts Group
28 H.261 - similar to but not compatible with MPEG
29 Wavelets -- Video compression
30 Block diagram of the video encoder
31 Block diagram of the video decoder
32 Wavelet references

This table of Contents Abstract

HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 1 HPDC95 Module on
Compression
August 1,1995

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
Roman Markowski
NPAC
Syracuse University
111 College Place
Syracuse
NY 13244-4100
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 2 Abstract of Compression Module

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
This set of foils describes image and video compression schemes concentrating on Wavelets which seem most powerful although JPEG and MPEG using related but less efficient Fourier technology will be used much more widely initially
JPEG, JBIG, Fractal for images and MPEG, H.261 schemes for video clips are briefly reviewed
Wavelets are described in detail
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 3 Compressing Still and Moving Images

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
image 2000x2000x24 bpp = 12MB
one second of NTSC-quality video requires 23 MB
compression - eliminating of redundant or less critical information
  • Spatial redundancy: values of neighboring pixels are strongly correlated
  • Spectral redundancy: the spectral values for the same pixel location are correlated
  • temporal redundancy: frames show very little change in the sequence
decreases the time and cost of transmission and the requirements for storage
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 4 Image Compression

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
lossless - removes the redundancy in the signal; ratio 3:1; the heights of every pixel are perfectly reproduced
lossy - selectively discards "less important" information; ratio 100:1
controversy: the critical feature of any lossy compression is what is important and what is not.
evaluation of several image compression technologies
  • JPEG - the leading standard in visual compression (compresses the image block by block), lossy, full color, block by block
  • JBIG - binary images, lossless, gray scale
  • Fractal - compression slow, decompression fast, lossy, 1000:1, bad quality
  • PhotoCD - Kodak, 96x64, 192x128, 384x256, 768x512, 1536x1024,3072x2048
  • Wavelet - discovered in 1987, lossy, ratio 100:1 and more , compresses the image as a whole
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 5 Performance Measures

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
compression ratio is
PSNR = Peak-signal-to-noise ratio (in dB)
RMSE is Root Mean Standard Error
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 6 JPEG - Joint Photographic Experts Group

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
current international standard for image compression
lossy algorithm: the threshold of visible difference 20:1; ratio can be varied
designed for compression of full-color (24 bit) or gray-scale digitized images of "natural" scenes (continuous tone)
exploits the known limitations of the human eye (10,000 colors simultaneously)
DCT (Discrete Cosine Transformation) -- converts the spatial image representation (8x8 blocks) into frequency map
Huffman coding -- input is sliced into fixed units while the corresponding output comes in chunks of variable size
source available (Independent JPEG Group)
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 7 JBIG - Joint-bi-level Image Experts Group

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
Losslessly compresses binary images (one bit/pixel)
Effective for bi-level images (black and white)
Extended to gray scales with upto 8 bits per pixel with good results upto 6 bits per pixel
Based on IBM's Q-coder - patented technology (no source)
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 8 Fractal Compression

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
lossy algorithm
patented technology by Barnsley ("Fractals Everywhere", 1988)
in the forward direction fractal mathematics is good for generating natural looking images (trees, clouds, mountains)
in reverse direction can be used to compress images
compression extremely slow (many hours)
decompression fast
theoretically very high ratio - 1000:1
based on Iterated Function Theory (J.Hutchinson, 1981) and Partitioned Iterated Function Theory
for compression ratio up to 40:1 JPEG is better; quality worse than wavelets or JPEG
details are generated when zooming in the advanced form of interpolation
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 9 Introduction to Wavelets

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
new technology -- rediscovered by I. Daubechies in 1987
signal analysis - weighted sum of basis functions
infinitely many possible sets of wavelets (= small waves)
coefficients contain information about the signal
basis functions
  • impulse function reveals information only about the time domain behavior of the signal because of infinitesimally small support of impuls function
  • Fourier representation reveals information about signal's frequency domain behavior because of infinite support of sines and cosines
  • we want to have representation which contains info about both the time and frequency (frequency content of the signal at the particular instant of time)
Heisenberg inequality - resolution in time and in frequency cannot both be made arbitrarily small
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 10 Discrete Wavelet Transform

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
FFT vs DWT -
  • Individual wavelet localized pretty well in both time (space) and frequency
  • Fourier expansion functions localized very well in frequency but not all in space or time
Both fast, linear operations; invertible and orthogonal
rotation in function space
  • From Impulse (delta function) space to that of coefficients of Fourier or Wavelet functions
  • Wavelet Transformation on N points performed as log2N rotations in multiresolution fashion
wavelet - localized in space and frequency;
  • Basis consists of scalings and translations of Mother functions
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 11 Wavelet Transform Characteristics

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
decorrelates the pixel values of the image and concentrates the image info into a relatively small number of coefficients
can be implemented as a pair of Quadrature Mirror Filters (QMF) which splits a signal's bandwidth in half
  • lowpass or smoothing
  • filter (H)
  • highpass filter (G)
  • which expresses detail
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 12 Daubechie's Mother wavelets

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 13 Mathematical Structure of Discrete Wavelet Transform-I

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
Transform can be written for one of log2N steps as a matrix operation given on following foil. As we will see each step deals with half of data from previous step and resolution examined doubles at each step
In this way we look at ALL resolutions i.e. all length scales
Each smoothing is constructed in this particular wavelet formulation as an average over 4 points
The matrix is orthogonal if:
The matrix will zero first two moments on sets of four points if:
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 14 Matrix Structure of a Simple Wavelet Transformation

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
This is basic matrix for 1D Wavelet transform where points are smoothed in groups of four
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 15 Mathematical Structure of Discrete Wavelet Transform-II

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
The solution of these 4 equations is:
The Smoothing Filter H is the average:
The detail is contained in operator G:
First step produces N/2 smooth and N/2 detail values.
  • Then we take N/2 smooth values and repeat step getting
  • N/4 smooth and N/4 further detail results at double spatial resolution
This recursively leads to pyramid algorithm
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 16 How Image wavelet compression works

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
We have reviewed 1D Wavelet Transform
There are Three steps in 2D Image Case
  • transformation of the image data using a predefined set of basis functions (multiresolution and orthogonal)
  • quantization of the basis function coefficients (lossy)
  • coding of the resulting data set to remove redundancy (Huffman lossless encoding)
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 17 How wavelet compression works
Pictorially

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 18 2D Forward/inverse wavelet transform

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
Best methods use direct 2D methods starting with 2 by 2 or similar pixel blocks. However one can compose in several ways 1D transforms. It is NOT best to first transform in x and then transform in y. Rather ...
A nice method uses two separate but INTERMIXED 1D transforms
  • Image filtered along the x dimension
  • Downsample by 2 along x
  • Filter along the y dimension
  • Downsample by 2 along y
Recursively transform the average signal (depending on required ratio)
We have matrix of coefficients (average signal and detail signals of each scale); no compression has been accomplished yet; in fact there has been an increase in amount of storage required
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 19 2D Forward wavelet transform

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 20 2D Inverse wavelet transform

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 21 Wavelets -- Quantization

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
compression is achieved by quantizing and encoding wavelet coefficients
coefficients that corresponds to smooth parts of data become small and can be set to 0 without creating significant distortion in the reconstructed image
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 22 Wavelets -- Coding

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
codec = encoder/decoder
losslessly compressing and decompressing the sparse matrix of quantized coefficients
wide variety of schemes (Huffman, arithmetic)
compromise between: memory, execution speed, available bandwidth, reconstructed image quality
example: Shapiro's Zero Tree encoding
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 23 Wavelets in Telemedicine

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
Massachusetts General Hospital: no clinically significant image degradation was identified in radiology images up to 30:1
wavelet-based compression technology is superior to all other compression technologies (keeps details, high compression ratio)
from a signal processing standpoint, one may view the image as a signal that has high-frequency (high-spatial detail) and low-frequency (smooth) components.The algorithm filters the signal and then iterates the process.
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 24 Comparison W6+VLC, Biorthogonal+VLC, JPEG image coders

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 25 Video Compression -- I

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
MPEG - Motion Picture Experts Group; lossy algorithm;
  • standard for compression synchronized audio and video; full screen,
  • 30 fps playback at 352x240 resolution
H.261 - similar but not compatible with MPEG; videocodec for audiovisual services at px64 Kbps (p=1..30);
  • describes videosource coder, video multiplex coder and the transmission coder;
  • video for ISDN
CellB - lossy algorithm, intra-frame compression; very efficient to decode in software;
  • motion sensitive compression scheme (compresses across frames); SunVideo Board
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 26 Video Compression -- II

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
Indeo - Intel lossy compression;
  • Currently15 fps, 320x240;
  • Indeo 4.0 full-screen 30fps on 90MHz Pentium
InSoft DVE 1- intraframe algorithm; InSoft's proprietary; very efficient to decode quickly in software; VideoPix or RasterOP cards
Motion JPEG - higher quality than CellB;
  • lossy algorithm; we can control balance between compression and quality; very complex - difficult and time consuming to decode in software; Parallax Card
Other: HDCC, H.221, H.242, QuickTime, Cinepak, TrueMotion-S
Wavelet-based compression
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 27 MPEG - Moving Picture Experts Group

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
standard for compression (synchronized) audio and video
4 parts: video encoding, audio encoding, "systems" (synchronization) and compliance testing
defines 352x240 pixels (30 fps in USA, 25fps in Europe)
MPEG-1- designed for bandwidth up to 1.5 Mbps
MPEG-2 - higher quality; designed for bandwidth 4-10 Mbps
MPEG-3 - does not longer exist; MPEG-4 - very low bitrate coding
DCT (Discrete Cosine Transform ) done on 8x8 blocks
lossy algorithm with compression in space (DCT) and time (frame to frame)
3 types of frames
  • I (Intra) frames - sent every 10-12 frames as still images
  • P (Predicted) frames - deltas from the most recent I or P frame
  • B (Bidirectional) frames - interpolation between I and P frames
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 28 H.261 - similar to but not compatible with MPEG

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
CCITT standard
VideoCodec for Audiovisual Services at px64 Kbps (p=1..30)
describes videosource coder, video multiplex coder and the transmission coder
designed for ISDN
defines two picture formats:
  • CIF (Common Intermedia Format) - 288x360 luminance, 144x180 chrominance
  • QCIF (Quarter CIF) - 144x180 of luminance and 72x90 of chrominance
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 29 Wavelets -- Video compression

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
exploiting the temporal redundancies present in an image sequence (as done by MPEG)
techniques: hierarchical motion compression, 3D subband coding
very time consuming - 256x256x8bpp image on 66MHz 80486 - 0.25 sec inverse wavelet transform of a single full frame (4 frames per second)
it is necessary to perform the complete inverse transform for each frame (in a slowly varying image sequence)
16 frames per second if just transform changes in image -- fewer nonzero pixels and so faster
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 30 Block diagram of the video encoder

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 31 Block diagram of the video decoder

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * Critical Information in IMAGE
Full HTML Index
HELP! * GREY=local HTML version of LOCAL Foils prepared July 28,1995

Foil 32 Wavelet references

From Master Foils for HPDC95 Compression Presentation HPDC95 Pentagon City -- August 1,1995. * See also color IMAGE
Full HTML Index
wavelet@math.scarolina.edu
http://www.mathsoft.com/wavelets.html
"Numerical recipes", WH Press, SA Teukolsky, WT Veterling, BP Flannery
"Ten Lectures on Wavelets", Ingrid Daubechies, 1992
Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Tue Feb 18 1997