INTRODUCTION
Dr. – CS576 Lecture 5 Page 1
IIMMAAGGEESS –– CCOOMMPPRREESSSSIIOONN
AANNDD DDIITTHHEERRIINNGG
Dr. – CS576 Lecture 5 Page 2
TTOOPPIICCSS TTOO BBEE CCOOVVEERREEDD
Introduction
• Image Types
• Image Representation
• Applications where images are used
Need for Compression and Standards
Overview of Image Compression Algorithms and Formats
JPEG
• Needs and Requirements
• Compression Algorithms for supported modes
• Performance Issues
JPEG 2000
• Wavelet Compression
Drawbacks of Image Compression – Image Dithering
Dr. – CS576 Lecture 5 Page 3
TTYYPPEESS OOFF IIMMAAGGEESS
We consider here still images, for example:
• Photographs (color or grayscale)
• Fax (bi-level and multilevel)
• Documents (text, handwriting, graphics and
photographs)
• Mosaics
• Stereo Images
Representation of Images –
Consists of components
Gray Images – single component
Color Images – r, g, b components
Sometimes images also have an alpha component.
Each component is represented as a number of
bits per pixel (application dependent).
Dr. – CS576 Lecture 5 Page 4
EEXXAAMMPPLLEE OOFF AALLPPHHAA CCHHAANNNNEELL
+ =
Final[i][j] = Foreground[i][j]* α [i][j] + Background[i][j]*(1-α[i][j])
Foreground Final Background
α R G B
Dr. – CS576 Lecture 5 Page 5
AAPPPPLLIICCAATTIIOONNSS
Application examples – variety of low/medium
resolutions (usually 8 bits per component or less)
• Information – news,
• Entertainment – Slide-show on the Internet,
games
• Commerce – ecommerce (catalogs, home
shopping), real-estate viewing
Application examples – high resolution (more than 8 bits
per component)
• Medical applications – (X-rays, CAT scans, etc.)
• Film Applications
• Remote Sensing.
Dr. – CS576 Lecture 5 Page 6
NNEEEEDD FFOORR CCOOMMPPRREESSSSIIOONN
Multimedi
a Image
Data
Size
Of
Image
Bits/Pixel
or
Bits/Sample
Uncompressed
Size
(B for bytes)
Band
Width
(b for
bits)
Transmission
Time
56K
Modem
780Kb
DSL
Grayscale
Image
512 x 512
8 bpp
262 KB
2.1
Mb/im
age
42
seconds
3
seconds
Color
Image
512 x 512 24 bpp
786 KB
6.29
Mb/im
age
110
seconds
7.9
seconds
Medical
Image
2048 x
1680
12 bpp
5.16 MB
41.3
Mb/im
age
12 min 51.4
seconds
SHD
Image
2048 x
2048
24 bpp 12.58 MB 100
Mb/im
age
29 min 2 min
Dr. – CS576 Lecture 5 Page 7
SSOOMMEE CCOOMMPPRREESSSSIIOONN FFOORRMMAATTSS
There are many different uncompressed and
compressed formats used in the industry! Some of
commonly used compressed formats are
• RIFF – Resource Interchange File Format
• GIF – Graphics Interchange File Format
• PNG – Portable Network Graphics
• JPEG – Joint Photographic Expert Groups
• JPEG 2000
• MPEG4-VTC – Visual Texture Coding
Dr. – CS576 Lecture 5 Page 8
IIMMAAGGEE RREEDDUUNNDDAANNCCYY
• Spatial Redundancy
• Spectral Redundancy
Dr. – CS576 Lecture 5 Page 9
TTYYPPEESS OOFF IIMMAAGGEE CCOOMMPPRREESSSSIIOONN
Makes use of Lossless and Lossy Schemes or a
combination of both (Hybrid)
Lossless Schemes
Already discussed in Information Theory Lecture
Lossy Schemes
Frequency Domain Based
• Discrete Fourier
• Discrete Cosine
• Wavelet Transforms
Fractal Based Compression
http://pi4.informatik.uni-
mannheim.de/pi4.data/content/animations
http://pi4.informatik.uni-mannheim.de/pi4.data/content/animations
http://pi4.informatik.uni-mannheim.de/pi4.data/content/animations/msa/index.html
Dr. – CS576 Lecture 5 Page 10
JJPPEEGG BBAACCKKGGRROOUUNNDD –– RREEQQUUIIRREEMMEENNTTSS AANNDD
SSEELLEECCTTIIOONN PPRROOCCEESSSS
Be at or near the state of art with regards to
compression rate and accompanying fidelity
Make no assumptions about the type of image – should
be applicable to practically any kind of continuous-tone
digital source image.
Have a tractable computational complexity
Support flexibility by allowing the following modes of
operation
• Lossless and Lossy Encoding
• Sequential Encoding
• Progressive Encoding
• Hierarchical Encoding
Dr. – CS576 Lecture 5 Page 11
JJPPEEGG IIMMAAGGEE CCOODDIINNGG
JPEG is the standard algorithm for compression of still
images
• Started in June 1987
• Finalized and Accepted in 1991
It is of reasonably low computational complexity, is
capable of producing compressed images of high
quality, and can provide both lossless and lossy
compression of arbitrarily sized grayscale and color
images
Dr. – CS576 Lecture 5 Page 12
JJPPEEGG LLOOSSSSYY CCOODDEECC SSCCHHEEMMEE
Dr. – CS576 Lecture 5 Page 13
JJPPEEGG CCOOMMPPRREESSSSIIOONN AALLGGOORRIITTHHMMIICC
OOVVEERRVVIIEEWW
The RGB color vectors of the input image are converted
into YCrCb values and each channel is encoded
independently
Each channel image is converted into a series of 8-by-8
pixel blocks, which are then processed in a raster scan
sequence from left to right and from top to bottom
Each 8×8 block of pixels is spectrally analyzed using
DCT (transform coding) and coefficients are quantized
After DCT coding and quantization, coefficients are
entropy coded
Dr. – CS576 Lecture 5 Page 14
DDCCTT FFOORRMMUULLAA IINN 22DD
Discrete Cosine Transform
( ) ( )
++
=
=
=
=
=
7
0
7
0 16
12
cos
16
12
cos),()()(
4
1
),(
x
x
y
y
vyux
yxfvCuCvuF
Inverse Discrete Cosine Transform
( ) ( )
++
=
=
=
=
=
7
0
7
0 16
12
cos
16
12
cos),()()(
4
1
),(
x
u
y
v
vyux
vuFvCuCyxf
2
1)(),(: =vCuCwhere
, for u, v =0
1)(),( =vCuC otherwise
Dr. – CS576 Lecture 5 Page 15
WWHHAATT DDOO TTHHEE DDCCTT CCOOEEFFFFIICCIIEENNTTSS
RREEPPRREESSEENNTT
The DCT coefficients represent the spatial frequency
content within a 8×8 image block
The (0, 0) coefficient contains is called DC coefficient,
and is equal to a measure of the average of the 64 image
values in the block
As we move to the right of the block, the coefficients
represent the energy in higher horizontal frequencies
As we move down the block, the coefficients represent
the energy in higher vertical frequencies
Dr. – CS576 Lecture 5 Page 16
EEXXAAMMPPLLEESS OOFF 88XX88 DDCCTTSS
Dr. – CS576 Lecture 5 Page 17
EEXXAAMMPPLLEE OOFF 88XX88 DDCCTT BBAASSIISS FFUUNNCCTTIIOONNSS
Dr. – CS576 Lecture 5 Page 18
DDCCTT CCOOEEFFFFIICCIIEENNTT QQUUAANNTTIIZZAATTIIOONN
Each DCT coefficient is quantized independently using a
uniform quantizer
The number of quantization intervals per each DCT
channel is chosen independently for each coefficient
After quantization, the DC coefficient of a block is
encoded as the difference from the DC term of the
previous block in the processing order.
This is because there is usually strong correlation
between the DC coefficients of adjacent blocks
Dr. – CS576 Lecture 5 Page 19
RRUULLEESS FFOORR DDCCTT CCOOEEFFFFIICCIIEENNTT QQUUAANNTTIIZZAATTIIOONN
Low-frequency coefficients usually have more energy
than high-frequency coefficients – therefore require
more quantization intervals
The Human Visual System is more sensitive to low
frequencies. Hence, low-frequency coefficients require
more quantization intervals
The Human Visual System is more sensitive to
luminance channels than to chrominance channels.
Hence, luminance channels require more quantization
intervals than chrominance channels
“Note: the quantization table is not standardized!”
Dr. – CS576 Lecture 5 Page 20
EEXXAAMMPPLLEE
Dr. – CS576 Lecture 5 Page 21
EENNTTRROOPPYY CCOODDIINNGG OOFF DDCCTT CCOOEEFFSS
The quantized DCT coefficients are first processed in
zigzag order
Dr. – CS576 Lecture 5 Page 22
IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN
Zigzag ordering of coefficients places low frequency
coefficients before high-frequency coefficients.
• Low frequency coefficients are more likely to be
non-zero
• High frequency coefficients are more likely to be
null after quantization
In this way, the sequence of quantized coefficients is
such that there often are long sequences of null values
AC coefficients are represented in an intermediate run-
length representation, which encodes the runs of zero
preceding any non-null coefficient
Dr. – CS576 Lecture 5 Page 23
IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN ((22))
Each non-zero AC coefficient is represented in
combination with the run-length of the null coefficients
before it, using a pair of symbols:
• Symbol-1 (RUNLENGTH,SIZE)
• Symbol-2 (AMPLITUDE)
RUNLENGTH is the number of consecutive null
coefficients before the non-zero symbol; SIZE is the size
of the symbol used to encode the non-null symbol
AMPLITUDE is the actual (encoded) value
Dr. – CS576 Lecture 5 Page 24
IINNTTEERRMMEEDDIIAATTEE RREEPPRREESSEENNTTAATTIIOONN ((33))
RUNLENGTH must be 15. To represent a run of > 15
zeros, there can be up to 3 consecutive (15,0) symbol-1
extensions
If the last run of zeros contains the last DCT coefficient,
then the special EOB (End-Of-Block) symbol-1 value
(0,0) terminates the representation
DC coefficients are represented by only one pair:
• Symbol-1 (SIZE)
• Symbol-2 (AMPLITUDE)
Dr. – CS576 Lecture 5 Page 25
EENNTTRROOPPYY CCOODDIINNGG
For both DC and AC coefficients, each symbol-1 is
Huffman encoded (variable length prefix code)
• Huffman tables are not specified in the standard
and must be input to the encoder
Each symbol-2 is encoded with a Variable Length
Integer (VLI) code
• It is different from a Huffman code because the
symbol length is known in advance
• The coding table is hard-wired in the proposal
Dr. – CS576 Lecture 5 Page 26
LLOOSSSSLLEESSSS JJPPEEGG MMOODDEE
It is wholly independent of DCT processing
Each sample value is predicted from a combination of
nearby sample values, and the prediction residual is
entropy coded (Huffman)
Prediction effectively reduces the entropy of the
residual, so that small average symbol length can be
achieved
Dr. – CS576 Lecture 5 Page 27
PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG MMOODDEESS
Layering or progressive encoding: an image can be
transmitted at a low rate (and a low quality) and then
progressively improved by subsequent transmission
Convenient for browsing applications, where a low-
quality or low-resolution image is adequate browsing
Three forms of JPEG progressive encoding:
• Spectral selection
• Successive bit approximation (SNR scalability)
• Hierarchical (pyramidal) mode
Dr. – CS576 Lecture 5 Page 28
PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG ((22))
Spectral selection
• Initial transmission sends low-frequency DCT
coefficients, followed progressively by the higher
frequency coefficients, according to the zig-zag
scan
• Simple to implement but reconstructed images
from the early scans are blurred
Successive approximation (SNR scalability)
• Only the most significant bits of each coefficient
are sent in the first scan, followed by the next
most significant bits and so on until all bits have
been transmitted
Dr. – CS576 Lecture 5 Page 29
Dr. – CS576 Lecture 5 Page 30
PPRROOGGRREESSSSIIVVEE EENNCCOODDIINNGG ((33))
Hierarchical (pyramidal) mode
• Image can be sent in one of several resolution
modes to accommodate different kinds of
displays
• Different resolution modes achieved by filtering
and down sampling the image in multiples of two
in each direction. The resulting image is
interpolated and subtracted from the next level to
create a residual
• The different resolution modes are transmitted
together with the residuals
Dr. – CS576 Lecture 5 Page 31
PPYYRRAAMMIIDD DDEECCOOMMPPOOSSIITTIIOONN
Dr. – CS576 Lecture 5 Page 32
PPYYRRAAMMIIDD DDEECCOOMMPPOOSSIITTIIOONN((22))
Dr. – CS576 Lecture 5 Page 33
JJPPEEGG PPEERRFFOORRMMAANNCCEESS
Assume the pixels of an arbitrary color image are
digitized to 8 bits for luminance and chrominance
channels with 4:2:2 color sampling scheme.
Then effectively the source image has 16 bits/pixel
BBiittss//PPiixxeell QQuuaalliittyy CCoommpprreessssiioonn
RRaattiioo
0.25 Fair 64:1
0.5 Good 32:1
0.75 Very Good 21:1
1.5 Excellent 10:1
2 Indistinguishable 8:1
Dr. – CS576 Lecture 5 Page 34
AARRTTIIFFAACCTTSS OOFF JJPPEEGG –– OORRIIGGIINNAALL ((338800KKBB))
Dr. – CS576 Lecture 5 Page 35
AARRTTIIFFAACCTTSS OOFF JJPPEEGG –– CCOOMMPPRREESSSSEEDD ((4400KKBB))
Dr. – CS576 Lecture 5 Page 36
Original – 24 bits per pixel Compressed – 1.0 bits per pixel
Compressed – 0.5 bit per pixel Compressed – 0.15 bits per pixel
Dr. – CS576 Lecture 5 Page 37
DDRRAAWWBBAACCKKSS OOFF DDCCTT –– SSTTAATTIIOONNAARRYY SSIIGGNNAALLSS
The DCT Transform is good for stationary signals –
frequencies are present all the time
Dr. – CS576 Lecture 5 Page 38
DDRRAAWWBBAACCKKSS OOFF DDCCTT –– NNOONN SSTTAATTIIOONNAARRYY
Non stationary signals have frequencies that vary with time.
Dr. – CS576 Lecture 5 Page 39
TTIIMMEE FFRREEQQUUEENNCCYY AANNAALLYYSSIISS
Dr. – CS576 Lecture 5 Page 40
JJPPEEGG–22000000
Dr. – CS576 Lecture 5 Page 41
IINNTTRROODDUUCCTTIIOONN
Image compression should not only reduce storage and
bandwidth requirements, but also allow extraction for
editing and processing – one of the primary motives of
JPEG-2000: International Standard by 12/2000
JPEG-2000 has better compression performances than
JPEG; more importantly, from a single bit-stream, JPEG-
2000 allows extraction of
• Different resolution
• Different pixel fidelities
• Different regions of interest
• Different color component
Dr. – CS576 Lecture 5 Page 42
JJPPEEGG–22000000 FFEEAATTUURREESS
State-of-the-art low bit-rate compression
Progressive transmission by quality, resolution,
component, or spatial locality
Lossy and Lossless compression (with Lossless
decompression available naturally through all types of
progression)
Random (spatial) access to the bit stream
Pan and zoom (with decompression of only a subset of
the compressed data)
Compressed domain processing (e.g., rotation and
cropping)
Region of interest coding by progression
Dr. – CS576 Lecture 5 Page 43
JJPPEEGG–22000000 CCOOMMPPRREESSSSIIOONN SSTTEEPPSS
An image is first divided into tiles
Each tile is subband-transformed and quantized
Each subband of a tile is divided into packet partitions;
each packet partition is divided into code-blocks
Each code-block is entropy-coded independently (using
arithmetic coding)
The image is encoded “naturally” progressively: if we
decode all of the bit-stream, we obtain the Lossless
version of the image
Dr. – CS576 Lecture 5 Page 44
WWAAVVEELLEETT EENNCCOODDIINNGG OOFF AA SSIINNGGLLEE TTIILLEE
Dr. – CS576 Lecture 5 Page 45
SSPPAATTIIAALL AACCCCEESSSSIIBBIILLIITTYY
A client may wish to obtain compressed data for only a
particular portion of the image.
If Regions of Interest (ROI) are known in advance (at
encoding time) JPEG-2000 can provide greater image
quality to the foreground. (exploits image tiling)
Dr. – CS576 Lecture 5 Page 46
PPEERRFFOORRMMAANNCCEE
Typically JPEG-2000 provides (with respect to JPEG)
only a few dB improvements from 0.5 to 1.0 bits/pixel
but substantial improvement below 0.25 bits/pixel and
above 1.5 bits/pixel
JPEG progressive is not optimized (i.e. has worse
performance than JPEG sequential) because the DCT
coefficients stay the same but the entropy coding
changes
• With JPEG-2000 the progressive performance is almost
identical to the single layer performance (because the
encoded bits do not change)
Dr. – CS576 Lecture 5 Page 47
EEXXAAMMPPLLEESS –– OORRIIGGIINNAALL
Dr. – CS576 Lecture 5 Page 48
EEXXAAMMPPLLEESS
JPEG2000 JPEG
Dr. – CS576 Lecture 5 Page 49
CCOONNCCLLUUSSIIOONN
JPEG-2000 is unlikely to replace JPEG in low complexity
applications at bit-rates in the range where JPEG
performs well
However, for applications requiring either higher quality
or lower bit rates, or any of the features provided, JPEG-
2000 should be a welcome standard.
The main reasons why it will be welcomed in the future
• Better qualitative performance at same bitrate with
JPEG
• Random Access of Bitstream – supports features
such as Region of Interest.
• Compressed Image Domain Manipulation
• Encode once – decode depending on platform
Dr. – CS576 Lecture 5 Page 50
Dr. – CS576 Lecture 5 Page 51
DDIITTHHEERRIINNGG
Dr. – CS576 Lecture 5 Page 52
TTHHEE PPRROOBBLLEEMM
Suppose that an image uses N intensity levels (or uses
N colors) to represent its content.
Suppose that the rendering device on which this is to be
displayed can use only n colors, and
n
th row and j-th column
Dr. – CS576 Lecture 5 Page 58
DDIITTHHEERRIINNGG ((EEXXAAMMPPLLEE))
Dr. – CS576 Lecture 5 Page 59
EERRRROORR DDIIFFFFUUSSIIOONN
When trying to display an image having colors more in
number than the display device (or printer device), a
selection has to be made to approximate the value of the
display color, which is done using
• Precomputed Lookup Tables (LUT)
• Dynamic Color Quantization
Either way the difference in the selector color value and
the original value results in an error
Large color errors degrade the quality of the displayed
image. If the error is diffused in the neighborhood, such
effects are minimized. Error Diffusion Algorithms do this
by distributing the color errors among all the pixels
such that the total color error for the entire image is zero
(or very close to zero).
Dr. – CS576 Lecture 5 Page 60
EERRRROORR DDIIFFFFUUSSIIOONN AALLGGOORRIITTHHMM
Let A be the original image and B be the final image
• Pick up the palette color that is nearest the
original pixel’s color. This palette color is stored
in the destination bitmap B [i,j ].
• Calculate the color error A [i,j ] – B [i,j ]for the
pixel.
• Distribute this error to four of A [i,j ]’s nearest
neighbors that haven ’t been scanned yet (the
one on the right and the three ones centered
below) according to a filter. Eg – Floyd- . – CS576 Lecture 5 Page 61
EERRRROORR DDIIFFFFUUSSIIOONN –– EEXXAAMMPPLLEE