Full HTML for

Basic foilset Theory and Practice of Wavelet compression

Given by Czeslaw Jedrzejek, Tomasz Major at Rome Lab Quarterly Review for CIV on June 28 96. Foils prepared 23 February 97
Outside Index Summary of Material

This covers both basic Theory and NPAC projects with examples
Wavelet compression activity: goals
Compression of still images:
improving quality for fixed bitrate
decreasing encoding time (currently encoding still image takes 2 seconds on SGI Challenge; similar problem exists for DCT like H.263 based systems - currently no real-time encoding exists in software)
parallelizing: decomposition, quantization and arithmetic coding (important in view of emergence of multiprocessor PentiumPro systems)
Compression of video:
we verified that motion estimation in wavelet space does not work
plan: hybrid video method
Web and other functionalities:
progressive still image plug-in (implemented)
in progress - zoom, local window, chroma key
plans: transparency, pre- and post-processing, access key file protection, error recovery

Table of Contents for full HTML of Theory and Practice of Wavelet compression

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Wavelet compression (1) Czeslaw Jedrzejek, Tomasz Major
2 Wavelet compression (2)
3 Wavelet compression (3)
4 Wavelet compression (4): Algorithm
5 Wavelet compression (5)
6 Compression(6): Wavelet decomposition
7 Compression(7): Reorganization of wavelet trees into wavelet blocks
8 Compression (8): Principle of zerotree quantization
9 Compression (9): Choice of filter normalization
10 Compression (10): Statistics of zerotrees in subbands vs pass number for Lenna
11 Compression (11): Motion Estimation in Real Space - Block Matching
12 Compression (12): Multiresolution Motion Estimation (1)
13 Compression (13): Implementation of Multiresolution Motion Estimation (2)
14 Compression (14): Multiresolution Motion Estimation (3)
15 Compression (15): Coding of I-Frame
16 Compression (16): Demonstration of deficiency of motion estimation scheme in wavelet space
17 Compression (17): Compensated frame
18 Compression (18): Wavelet decomposition of frame #1
19 Compression (19): Wavelet decomposition of frame #2
20 Compression (20): Conclusion
21 Compression (21): Hybrid wavelet video encoder

Outside Index Summary of Material

HTML version of Basic Foils prepared 23 February 97

Foil 1 Wavelet compression (1) Czeslaw Jedrzejek, Tomasz Major

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Wavelet compression activity: goals
  • Compression of still images:
    • improving quality for fixed bitrate
    • decreasing encoding time (currently encoding still image takes 2 seconds on SGI Challenge; similar problem exists for DCT like H.263 based systems - currently no real-time encoding exists in software)
    • parallelizing: decomposition, quantization and arithmetic coding (important in view of emergence of multiprocessor PentiumPro systems)
  • Compression of video:
    • we verified that motion estimation in wavelet space does not work
    • plan: hybrid video method
  • Web and other functionalities:
    • progressive still image plug-in (implemented)
    • in progress - zoom, local window, chroma key
    • plans: transparency, pre- and post-processing, access key file protection, error recovery
HTML version of Basic Foils prepared 23 February 97

Foil 2 Wavelet compression (2)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Available advanced commercial wavelet software for still images (only executables)
  • AccuPress for Multimedia (Aware, Inc., Bedford MA) - installed and tested in NPAC. Mature market product, algorithm: probably subband coding with vector quantization, many platforms supported, used for implementation of the FBI's Wavelet Scalar Quantization fingerprint compression standard
  • CREW (Ricoh Company, Ltd., Menlo Park, CA Research Center) - compression with reversible embedded wavelets, used in Ricoh printers
  • Summus, Ltd (Irmo, SC) - optimized wavelet image codec ready to plug in to Netscape
  • Lightning Strike (Infinop, Denton, TX), ready to plug in to Netscape
HTML version of Basic Foils prepared 23 February 97

Foil 3 Wavelet compression (3)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Existing academic and research software
  • Said & Pearlman (RPI), source available, better than Embedded Zerotree Wavelet (EZW)
Existing but unavailable software (some also for wavelet video)
  • Based on methods known in literature, significantly better than EZW, but of much greater complexity (e.g. wavelet packets, UICC & Princeton, encoding one frame takes several minutes; several minor modifications of EZW adding up to significant final effect, UC Davis)
  • Hybrid encoding: wavelet coding of key frame, Motion estimation in real space, wavelet coding of the displaced frame difference (Sarnoff/Lehigh scheme) (executables might appear with regard to MPEG-4 activities)
Our software
  • of the quality comparable with Lightning Strike, little worse than AccuPress due to lack of pre- and postprocessing, ready to plug in to Netscape (demo)
HTML version of Basic Foils prepared 23 February 97

Foil 4 Wavelet compression (4): Algorithm

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Transformation of the image:
  • reversible (lossless) fast wavelet transform in float-point arithmetic (inferior to JPEG)
  • BiOrt (9/7 tap), QMF (5,7,9 tap) or BIP (15,21 tap) filters;
  • asymmetric horizontal and vertical filters - search for automatic method of implementation
Quantization of transform coefficients:
  • study of zeroroot statistics revealed potential for further optimization
  • fully embedded codestream
Regular lossless coding:
  • fast implementation of arithmetic coder (speeding up the execution time by 2.5 times in period between the reviews)
  • contextual modelling of any order
HTML version of Basic Foils prepared 23 February 97

Foil 5 Wavelet compression (5)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Investigation of various video compression technologies: H.263, H263+, L and MPEG-4
Wavelet compression of binary terrain data for VRML applications
  • current methods allow only 5:1 compression due to lettering
  • solution: binary image estimation in separate color spaces, binary image extraction, difference encoding
Available implementation
  • Intel's Indeo Video 4.1 employs partly wavelet-based motion estimation and compensation technologies, QSIF (160x120)
  • Horizons Technology Power!Video, Intel's competition
  • Summus, Ltd (Irmo, SC) - several platforms, no video yet
  • VDOLive by VDOnet - wavelet based video codec, QSIF, gray scale, delivery over 28.8 Kbps
Our focus: decoding, wavelet player
  • video server with scalable wavelet compressor
  • motion estimation and prediction techniques needed to satisfy real time, low bandwidth and quality requirements
HTML version of Basic Foils prepared 23 February 97

Foil 6 Compression(6): Wavelet decomposition

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
LHn indicates subband subjected to low-pass (L)
or high-pass (H) filtering at the nth scale
HTML version of Basic Foils prepared 23 February 97

Foil 7 Compression(7): Reorganization of wavelet trees into wavelet blocks

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Useful for hybrid schemes
HTML version of Basic Foils prepared 23 February 97

Foil 8 Compression (8): Principle of zerotree quantization

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
HTML version of Basic Foils prepared 23 February 97

Foil 9 Compression (9): Choice of filter normalization

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Transform and inverse transform have to be normalized in both directions such that if the transform coefficients are scaled by 1/s the inverse transform has to be scaled by s. This leaves the freedom for selection of s through all scales . Quality (PSNR- the highest the better) can be affected, since relative band magnitudes are then differently quantized. The same effect for DCT has not been exploited.
For Lenna:
We search for automatic selection criterion (and even for band specific s).
Hor Ver PSNR Hor Ver PSNR Hor Ver PSNR Hor Ver PSNR Hor Ver PSNR
0.50 0.67 27.7 0.50 0.80 27.9 0.50 1.00 28.1 0.50 1.25 27.2 0.50 1.5 27.0
0.57 0.67 - 0.57 0.80 30.1 0.57 1.00 29.7 0.57 1.25 29.1 0.57 1.5 28.7
0.60 0.67 - 0.67 0.80 30.3 0.67 1.00 30.5 0.67 1.25 30.2 0.67 1.5 30.4
0.80 0.67 30.4 0.80 0.80 30.4 0.80 1.00 31.2 0.80 1.25 30.6 0.80 1.5 30.7
1.00 0.67 30.6 1.00 0.80 30.2 1.00 1.00 30.5 1.00 1.25 30.7 1.00 1.5 30.3
1.25 0.67 29.9 1.25 0.80 29.9 1.25 1.00 29.7 1.25 1.25 30.1 1.25 1.5 29.7
1.50 0.67 29.7 1.50 0.80 29.1 1.50 1.00 29.2 1.50 1.25 29.7 1.50 1.5 28.8
1.75 0.67 28.6 1.75 0.80 28.6 1.75 1.00 28.8 1.75 1.25 28.4 1.75 1.5 28.6
2.00 0.67 28.3 2.00 0.80 28.7 2.00 1.00 28.1 2.00 1.25 28.4 2.00 1.5 28.3
HTML version of Basic Foils prepared 23 February 97

Foil 10 Compression (10): Statistics of zerotrees in subbands vs pass number for Lenna

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Zerotree pass
Band 1 2 3 4 5 6 7 8 9
LL5 194 105 60 24 6 2 0 0 0
HL5 62 135 131 122 86 51 27 6 0
LH5 62 151 189 192 169 105 56 21 7
HH5 62 151 191 204 174 137 96 54 27
HL4 0 64 260 423 555 50 432 340 215
LH4 0 0 28 159 301 9 569 519 394
HH4 0 0 20 112 295 500 477 490 426
HL3 0 0 0 68 404 422 167 1976 1963
LH3 0 0 0 4 92 117 859 1413 1777
HH3 0 0 0 0 36 383 632 1121 1526
HL2 0 0 0 0 0 184 1047 2609 4605
LH2 0 0 0 0 0 140 260 1076 2384
HH2 0 0 0 0 0 4 80 604 1727
HL1 0 0 0 0 0 0 0 0 0
LH1 0 0 0 0 0 0 0 0 0
HH1 0 0 0 0 0 0 0 0 0
Need for more efficient coding of upper right zeros. Statistics of zerotrees in differential image may differ.
HTML version of Basic Foils prepared 23 February 97

Foil 11 Compression (11): Motion Estimation in Real Space - Block Matching

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
An image is divided into fixed size blocks.
The basic assumption is that all the pixels in a block have the same displacement.
For each block in frame t, a search is done to try to find its equivalent in frame t-1 and to find the displacement vector of this block.
The scheme works for any key frame compression method.
HTML version of Basic Foils prepared 23 February 97

Foil 12 Compression (12): Multiresolution Motion Estimation (1)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
The frames are decomposed in a pyramidal representation.
The basis assumption is the existence of a high correlation of the movement of the objects in the different levels of this decomposition.
General principle: doing a normal estimation in the first band, and then refining with the found vectors in the higher subbands.
HTML version of Basic Foils prepared 23 February 97

Foil 13 Compression (13): Implementation of Multiresolution Motion Estimation (2)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
An Example: MRME - Zhang and Zafar [92]:
  • The frame is decomposed in the wavelet domain
  • The bi-orthogonal wavelet transform is used:
Representation of a wavelet-decomposed frame
HTML version of Basic Foils prepared 23 February 97

Foil 14 Compression (14): Multiresolution Motion Estimation (3)

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
HTML version of Basic Foils prepared 23 February 97

Foil 15 Compression (15): Coding of I-Frame

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
DWT: Discrete Wavelet Transform
EZW: Embedded Zerotree Wavelet
TRANS: Channel
ARITH: Arithmetic Coder
HTML version of Basic Foils prepared 23 February 97

Foil 16 Compression (16): Demonstration of deficiency of motion estimation scheme in wavelet space

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
The binary square in
image sequence:
Frame #1: This square
Frame #2: The square
shifted 1 pel in x and y
directions
HTML version of Basic Foils prepared 23 February 97

Foil 17 Compression (17): Compensated frame

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
HTML version of Basic Foils prepared 23 February 97

Foil 18 Compression (18): Wavelet decomposition of frame #1

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
HTML version of Basic Foils prepared 23 February 97

Foil 19 Compression (19): Wavelet decomposition of frame #2

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
Edge motion causes the change of sign of wavelet coefficients in higher subbands. The process cannot be approximated by motion in wavelet space.
HTML version of Basic Foils prepared 23 February 97

Foil 20 Compression (20): Conclusion

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
The MRME algorithm doesn't work. This is one of the reasons the wavelet transform lost in the first rounds of the MPEG-4 video compression standard although it is better than DCT for still image compression (the other two reasons: relatively immature technology and difficulty of encoding objects)
New solution (hybrid scheme):
  • Wavelet coding of I frame
  • Motion estimation in real space
  • Wavelet coding of the displaced frame difference (Sarnoff/Lehigh scheme)
HTML version of Basic Foils prepared 23 February 97

Foil 21 Compression (21): Hybrid wavelet video encoder

From Theory and Practice of Wavelet compression Rome Lab Quarterly Review for CIV -- June 28 96. *
Full HTML Index
© 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 Thu Aug 14 1997