The Set Partitioning in
Hierarchical Trees (SPIHT)
Algorithm
by
William A. Pearlman
Rensselaer Polytechnic Institute
Presented to JPEG2000 Working Group
1 November 1997
The SPIHT Algorithm
• Inherent Characteristics-
– efficient
– completely embedded
– precise rate control
– idempotent
– simple and fast
– self-adaptive: no training required
• Supports
– images of 8, 16, or larger bit depth
– images of unrestricted dimensions
– progressive lossy to lossless compression
– multiresolution encoding or decoding
– modularity
Modularity
Transform
SPIHT
Compress
Optional
Lossless
Entropy
Coding
Transform: wavelet, wavelet packet (subband),
S+P, lifting, DCT, LOT
Entropy coding: none, Huffman, arithmetic
Goal of SPIHT
• Sort transform coefficients by msb -
– progressive selection of coefficients such that
• Use transform characteristics to identify
efficiently groups with same msb
• Send remaining bits by order of importance
– first those identifying msb
– then those of same bit plane with larger msb’s
• Binary results of msb tests sent to decoder
– enables decoder to duplicate encoder’s
execution path
|
,
|, , , ,...
cnnnn
ij
n
≥= −−212
00 0
Sorting by Magnitude and Bit-
Plane Transmission
Transmission of magnitude-sorted coefficients
signsssssssssssss
msb5 1100000000000
4
→→
11000000000
3
→→→→
111100000
2
→→→→→→→→
11111
1
→→→→→→→→→→→→→
lsb 0
→→→→→→→→→→→→→