IMAGES – COMPRESSION
IMAGES – COMPRESSION
AND DITHERING
AND DITHERING
Dr. – CS576 Lecture 5 Page 1
TOPICS TO BE COVERED
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 2
TYPES OF IMAGES
TYPES OF IMAGES
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 3
EXAMPLE OF ALPHA CHANNEL
EXAMPLE OF ALPHA CHANNEL
+
=
Foreground
Background
Final
RGBα
Final[i][j] = Foreground[i][j]* α [i][j] + Background[i][j]*(1-α[i][j])
Dr. – CS576 Lecture 5 Page 4
APPLICATIONS
APPLICATIONS
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 5
NEED FOR COMPRESSION
NEED FOR COMPRESSION
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 6
SOME COMPRESSION FORMATS
SOME COMPRESSION FORMATS
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 7
IMAGE REDUNDANCY
IMAGE REDUNDANCY
• Spatial Redundancy • Spectral Redundancy
Dr. – CS576 Lecture 5 Page 8
TYPES OF IMAGE COMPRESSION
TYPES OF IMAGE COMPRESSION
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
Dr. – CS576 Lecture 5 Page 9
JPEG BACKGROUND – REQUIREMENTS AND
JPEG BACKGROUND – REQUIREMENTS AND SELECTION PROCESS
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 10
JPEG IMAGE CODING
JPEG IMAGE CODING
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 11
JPEG LOSSY CODEC SCHEME
JPEG LOSSY CODEC SCHEME
Dr. – CS576 Lecture 5 Page 12
JPEG COMPRESSION ALGORITHMIC
JPEG COMPRESSION ALGORITHMIC OVERVIEW
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 13
Discrete Cosine Transform
DCT FORMULA IN 2D
DCT FORMULA IN 2D
1 x=7 y=7 (2x+1)u F(u,v)= C(u)C(v)f(x,y)cos
(2y+1)v cos
4 x=0y=0 16 Inverse Discrete Cosine Transform
16 (2y+1)v
1x=7 y=7 (2x+1)u f(x,y)= 4C(u)C(v)F(u,v)cos 16
1
cos 16
u=0 v=0
where :C(u),C(v) =
C(u),C(v) =1 otherwise
2 , for u, v =0
Dr. – CS576 Lecture 5 Page 14
WHAT DO THE DCT COEFFICIENTS
WHAT DO THE DCT COEFFICIENTS REPRESENT
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 15
EXAMPLES OF 8X8 DCTS
EXAMPLES OF 8X8 DCTS
Dr. – CS576 Lecture 5 Page 16
EXAMPLE OF 8X8 DCT BASIS FUNCTIONS
EXAMPLE OF 8X8 DCT BASIS FUNCTIONS
Dr. – CS576 Lecture 5 Page 17
DCT COEFFICIENT QUANTIZATION
DCT COEFFICIENT QUANTIZATION
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 18
RULES FOR DCT COEFFICIENT QUANTIZATION
RULES FOR DCT COEFFICIENT QUANTIZATION
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 19
EXAMPLE
EXAMPLE
Dr. – CS576 Lecture 5 Page 20
ENTROPY CODING OF DCT COEFS
ENTROPY CODING OF DCT COEFS
The quantized DCT coefficients are first processed in
zigzag order
Dr. – CS576 Lecture 5 Page 21
INTERMEDIATE REPRESENTATION
INTERMEDIATE REPRESENTATION
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 22
INTERMEDIATE REPRESENTATION (2)
INTERMEDIATE REPRESENTATION (2)
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 23
INTERMEDIATE REPRESENTATION (3)
INTERMEDIATE REPRESENTATION (3)
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 24
ENTROPY CODING
ENTROPY CODING
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 25
LOSSLESS JPEG MODE
LOSSLESS JPEG MODE
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 26
PROGRESSIVE ENCODING MODES
PROGRESSIVE ENCODING MODES
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 27
PROGRESSIVE ENCODING (2)
PROGRESSIVE ENCODING (2)
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 28
Dr. – CS576 Lecture 5 Page 29
PROGRESSIVE ENCODING (3)
PROGRESSIVE ENCODING (3)
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 30
PYRAMID DECOMPOSITION
PYRAMID DECOMPOSITION
Dr. – CS576 Lecture 5 Page 31
PYRAMID DECOMPOSITION(2)
PYRAMID DECOMPOSITION(2)
Dr. – CS576 Lecture 5 Page 32
JPEG PERFORMANCES
JPEG PERFORMANCES
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
Bits/Pixel
Quality
Compression Ratio
0.25 0.5 0.75 1.5
Fair 64:1 Good 32:1 Very Good 21:1 Excellent 10:1
2
Indistinguishable
8:1
Dr. – CS576 Lecture 5 Page 33
ARTIFACTS OF JPEG – ORIGINAL (380KB)
ARTIFACTS OF JPEG – ORIGINAL (380KB)
Dr. – CS576 Lecture 5 Page 34
ARTIFACTS OF JPEG – COMPRESSED (40KB)
ARTIFACTS OF JPEG – COMPRESSED (40KB)
Dr. – CS576 Lecture 5 Page 35
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 36
DRAWBACKS OF DCT – STATIONARY SIGNALS
DRAWBACKS OF DCT – STATIONARY SIGNALS
The DCT Transform is good for stationary signals – frequencies are present all the time
Dr. – CS576 Lecture 5 Page 37
DRAWBACKS OF DCT – NON STATIONARY
DRAWBACKS OF DCT – NON STATIONARY
Non stationary signals have frequencies that vary with time.
Dr. – CS576 Lecture 5 Page 38
TIME FREQUENCY ANALYSIS
TIME FREQUENCY ANALYSIS
Dr. – CS576 Lecture 5 Page 39
JPEG-2000
JPEG-2000
Dr. – CS576 Lecture 5 Page 40
INTRODUCTION
INTRODUCTION
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 41
JPEG-2000 FEATURES
JPEG-2000 FEATURES
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 42
JPEG-2000 COMPRESSION STEPS
JPEG-2000 COMPRESSION STEPS
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 43
WAVELET ENCODING OF A SINGLE TILE
Dr. – CS576 Lecture 5 Page 44
SPATIAL ACCESSIBILITY
SPATIAL ACCESSIBILITY
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 45
PERFORMANCE
PERFORMANCE
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 46
EXAMPLES – ORIGINAL
EXAMPLES – ORIGINAL
Dr. – CS576 Lecture 5 Page 47
JPEG2000
JPEG
EXAMPLES
EXAMPLES
Dr. – CS576 Lecture 5 Page 48
CONCLUSION
CONCLUSION
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 49
Dr. – CS576 Lecture 5 Page 50
DITHERING
DITHERING
Dr. – CS576 Lecture 5 Page 51
THE PROBLEM
THE PROBLEM
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
Dr. – CS576 Lecture 5 Page 57
DITHERING (EXAMPLE)
DITHERING (EXAMPLE)
Dr. – CS576 Lecture 5 Page 58
ERROR DIFFUSION
ERROR DIFFUSION
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 59
ERROR DIFFUSION ALGORITHM
ERROR DIFFUSION ALGORITHM
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 60
ERROR DIFFUSION – EXAMPLE
ERROR DIFFUSION – EXAMPLE
Dr. – CS576 Lecture 5 Page 61