Image Compression Basis

(1)

Image Compression Basis

Sebastiano Battiato, Ph.D.

battiato@dmi.unict.it

(2)

Compression and Image Processing

Fundamentals;

Overview of Main related techniques;

JPEG tutorial;

Jpeg vs Jpeg2000;

SVG

(3)

Bits and Bytes

The following terminology is often used when referring to digital image sizes (bit is abbreviation for binary digit):

bit (b) 1 bit 1 bit

byte (B) 8 bits 8 bits

kilobyte (KB) 2¹⁰ bytes 10³ + 2.4%

megabyte (MB) 2²⁰ bytes 10⁶ + 4.9%

gigabyte (GB) 2³⁰ bytes 10⁹ + 7.4%

terabyte (TB) 2⁴⁰ bytes 10¹² + 10%

(4)

Bit Plane Representation

An image with n x m pixels each with a bit-depth of N bits can be represented by N binary bit planes of size n x m ranging from the Most Significant Bit (MSB) to the Least Significant Bit (LSB).

(5)

Lena – Bit Planes

Most Significant bit (MSB) Least Significant bit (LSB)

(6)

Bit Plane coding

(7)

Image Compression

Num True Color (RGB – 24 bit) images MxN require:

3 Num MxN bytes

Example:

Num =10

MxN= 1712x1368 ≈ 2.2 Mpixel

3 10 2.2Mb ≈ 67 Mbyte !!!

Num True Color (RGB – 24 bit) images MxN require:

3 Num MxN bytes

Example:

Num =10

MxN= 1712x1368 ≈ 2.2 Mpixel

3 10 2.2Mb

3 10 2.2Mb ≈≈ 67 67 MbyteMbyte !!!!!!

(8)

Signal Compression: WHY?

Data Rate Application

Uncompressed Compressed Voice

8 ksample/s, 8 bits/sample

64 kbps 2 – 4 kbps Slow-motion video (10fps)

framesize 176X120, 24bit/pixel

5,07 Mbps 8 – 16 kbps Audio conference

8 ksample/s, 16 bits/sample

128 kbps 6 – 64 kbps Video conference (15fps)

framesize 352x240, 24bit/pixel

30.41 Mbps 64 – 768 kbps Digital audio

44,1 ksample/s, 16 bits/sample

1,5 Mbps 1,5 – 4 Mbps Digital video on CD-ROM (30 fps)

60,83 Mbps 3 – 8 Mbps Broadcast video (30fps)

1,33 Gbps 20Mbps

(9)

6

(10)

Aims at finding methods for reducing the number of bits needed to represent a digital image without compromising the required image quality for a given application.

Image compression (e.g. art/science of finding efficient representation for digital images) is used to:

Reduce memory for image storage.

Reduce the bandwidth/time required for image transmission.

Increase effective data transfer rate.

Definition

(11)

Data Compression

Several Classifications of Compression Methods are possible:

Based on Data Type (Generic, Audio, Image, Video);

Based on Compression Type :

- Lossless : The decoded (uncompressed) data will be exactly equal to the original (modest compression ratios).

- Lossy: The decoded data will be a replica of the original, but not necessarily the same (higher compression ratios).

(12)

Fundamentals

Information Theory (Shannon 1948) was developed to provide a mathematical tool to better design data compression algorithms and introduced a revolutionary new probabilistic way of thinking about communication. Simultaneously it was created the first truly mathematical theory of entropy (Measure of randomness).

Entropy of the source generating the data: it is impossible to compress data in a lossless way with a bitrate less than the entropy of the source that generated it.

The entropy H the source generating a data is in general impossible to measure in practice, due to the larger amount of interdependencies (of infinite order) and the non-stationarities.

(13)

Entropy: measure of uncertainty

Given a random variable X and probability distribution p(X) the following assumptions must be granted:

1 - H(X) exists;

2 - H(X) has a continuous functional dependence on the probability distribution p(X);

3 - If p(x_i) = 1/n i=1, 2, ….. , n then H(X) should be a monotonic increasing function of n;

4 - H(X) must be obeys to the composition or additivity law

(14)

Shannon’s Entropy

Theorem:

The only function H that satisfies the properties 1-4 above is of the form:

where k is a positive constant. It is common to set k to 1. H is called Entropy or Information Entropy. Usually, a zero- order entropy measure is used to estimate the entropy of the source.

H₀ = − k ∑ p_i log₂ (p_i) i ∈ S H₀ = − k ∑ p_i log₂ (p_i) i ∈ S

(15)

The Entropy function of two events with probability p and (1-p)

(16)

Fundamentals

For lossy coding, the rate-distortion theory was developed. Its main goal is summarized by Rate-Distortion optimization criterion:

Find the lowest bitrate for a certain distortion, or the lowest distortion for a given bitrate.

Find the

Find the lowest lowest bitratebitrate for a certain for a certain distortion

distortion, or the lowest distortion, or the lowest distortion for a for a given

given bitratebitrate..

(17)

Fundamentals

The most popular distortion measure is the mean square error (MSE):

The MSE (Mean Squared Error) does not always reflect the real distortion perceived by human visual system. For practical purposes the PSNR (Peak Signal to Noise Ratio) is used:

PSNR = k log_k (255²/ MSE) PSNR = k log_k (255²/ MSE)

MSE = 1/N ∑_i [x(i) - x*(i)]² i=1,2,…., N MSE = 1/N ∑_i [x(i) - x*(i)]² i=1,2,…., N

(18)

Rate-Distortion

(19)

Fundamentals

The performance of an image compression technique must be evaluated considering three different aspects:

Compression efficiency (Compression Ratio/Factor, bit per pixel bpp or bit rate);

Image quality (Distortion Measurement);

Computational cost.

(20)

Redundancies

Interpixel

Interpixel Redundancy relates to the statistical properties of an image Redundancy (e.g., pixel-to-pixel correlation, spectral (RGB) correlation, frame-to- frame similarity, etc.) and is a function of resolution, bit-depth, image noise, and image detail. It could be Spatial/Temporal Typical techniques used in this case: Huffman/Run Length

Coding Redundancy Coding Redundancy

Coding efficiency (DCT)

Psychovisual

Psychovisual Redundancy relates to an observer viewing an image Redundancy (HVS spatial and temporal CSF, visual masking, etc.) and is a function of image resolution, noise, detail, and viewing conditions. Discards Less important information, Quantization, ….

(21)

Spatial Redundancy

(22)

Spatial Redundancy

(23)

HVS Response

The frequency-dependent behavior of the human visual system (HVS) can be characterized by its response to harmonic (sinusoidal) functions.

For each sinusoid with a given frequency, the amount of contrast needed to elicit a criterion level of response from a neuron is called the contrast threshold.

The inverse of the contrast threshold is called the contrast sensitivity and when plotted as a function of frequency is referred to as the contrast sensitivity function (CSF).

The luminance CSF peaks at around 5 cycles/degree, and rapidly drops off to almost zero at 50 cycles/degree. The chrominance CSF drops even faster.

(24)

CSF Picture test

(25)

Luminance CSF

(26)

Visual Masking

(27)

Masking Effects

The local surround of the feather is very active and the HVS needs more time to pick up the distortion

(28)

Lossless (Reversible) Compression

The image after compression and decompression is identical to the original.

Only the statistical redundancy is exploited to achieve compression.

Data compression techniques such as LZW or LZ77 are used in GIF, PNG, and TIFF file formats and the Unix “Compress” command.

Image compression techniques such as lossless JPEG or JPEG-LS perform slightly better.

Compression ratios are typically ~2:1 for natural imagery but can be much larger for document images.

(29)

Lossy (Irreversible) Compression

The reconstructed image contains degradations with respect to the original image.

Both the statistical redundancy and the perceptual irrelevancy of image data are exploited.

Much higher compression ratios compared to lossless.

Image quality can be traded for compression ratio.

The term visually lossless is often used to characterize lossy compression schemes that result in no visible degradation under a set of designated viewing conditions..

(30)

Compression Methods

Lossy/Lossless data compression in Image Processing are mainly based on the following coding approaches:

Differential Coding: Pulse Code Modulation (PCM), Palette based;

Quad Trees

Huffman/Run-length;

Arithmetic;

Transform Domain (DCT, DWT,…).

(31)

Compression-Decompression process

Source Coder

Channel Coder

Source Decoder

Channel Decoder Encoder

Decoder Data

Data*

(32)

Lossless

S source that generates random s_i

self-information of s_i: I( s_i) = log( 1/p_i) = - log( p_i) Entropy (~ randomness) of source S: H( S ) = Σ ^p_i ^log₂ ^{( 1/p}_i ⁾

H( S ) bounds the coding efficiency

Delay

Probability Model

Symbol to Codeword

Mapping

ENTROPY ENTROPY

CODING CODING

In

Codeword

(33)

Differential Coding

0 255 -255 0 255

y_i = ( x_i-x_i-1) y_i x_i

- Based on Interpixel correlation - y_iare prediction residual

(34)

DPCM

AA BB

CC XX

p1 = A

p ₂^{= (A+C)/2} p ₃= (A+C-B)/3

p 4= w₁ A + w₂ B + w₃ C

with w₁+w₂+w₃=1 p1 = A

p ₂^{= (A+C)/2} p ₃= (A+C-B)/3

p 4= w₁ A + w₂ B + w₃ C

with w₁+w₂+w₃=1

In DPCM, a combination of previously encoded pixels (A, B, C) is used as a prediction (p) for the current pixel (X).

The difference between the actual value and the prediction (p - X) is encoded.

Low complexity

High quality (limited compression) Low memory requirements

(35)

Differential coding

Original DPCM Output

(36)

Delta Modulation

e_ij > 0 q_ij =

P_ij = α ŷ_{ij -1}

otherwise

+ξ e_ij

-ξ

(37)

Indexed images

To find an indexing that optimizes entropy of differences

Gray-level

Random

Heuristic Original

(38)

Histogram of the differences in the original image

Entropy = 5.25

(39)

Histogram of the differences in the random image

Entropy = 5.85

(40)

Histogram of the differences in the “heuristic” image

Entropy = 4.65

(41)

Entropy of differences

5.25 db Gray-level

5.85 db Random

4.65 db Heuristic

(42)

Quad Trees

Matlab Demo…

(43)

Variable Length coding

(44)

Symbol Modeling and Encoding

Symbol modeling and encoding involves the process of defining a statistical model for the symbols to be encoded (e.g., quantizer output levels or indices) and assigning a binary codeword to each possible output symbol based on its statistics.

• The resulting code should be uniquely decodable, i.e., each string of input symbols should be mapped into a unique string of output binary symbols.

• Examples are fixed-length coding, Huffman coding, Arithmetic coding, Golomb-Rice coding, Lempel-Ziv-Welch (LZW) coding.

(45)

Huffman Coding

Probability model and symbol-to-codeword are combined Input: sequence of symbols.

Order the symbols according to their probabilities.

Apply a contraction to the two symbols with the smaller probabilities.

Repeat the previous step until the final set has only one member.

Construction of a binary tree:

The codeword for each symbol is obtained traversing the binary tree from its root to the leaf corresponding to the symbol.

(46)

Huffman Process

l_avg =

Σ

^l_i ^p_i

H( S ) ≤ l_avg ≤ H( S )+1

(47)

Run-Length coding

(pixel, value)

(0,4) (255,11) (128,5)

The combination of a run-length coding scheme followed by a Huffman coder forms the basis of image compression standards.

These compression standards yield good compression (20:1 to 50:1)

(48)

Arithmetic Coding

An arithmetic coder accepts at its input the symbols in a source sequence along with their corresponding probability estimates, and produces at its output a code stream with a length equal to the combined ideal code-lengths of the input symbols.

Some implementations of arithmetic coding adaptively update the symbol probability estimate in each context as the symbols get encoded.

Practical implementations of AC, such as the JBIG/JPEG QM- Coder or MQ-Coder

(49)

Codifica Aritmetica:

MQ-Coder

0 1

A E G H L O #

Code Point A E G H L O #

A E G H L O #

coding “H”

coding “E”

coding “L”

coding “O”

coding “#”

0. 35 0. 65

A E G H L O #

0. 365 0. 44

0. 41375 0. 42125

0. 418625 0. 419375

0. 4191875 0. 4193375

: 0. 41933

(50)

Quantization

A many-to-one mapping that reduces the number of possible signal values at the cost of introducing errors.

• The simplest form of quantization (also used in all the compression standards) is scalar quantization (SQ), where each signal value is individually quantized.

(51)

Not-Uniform Scalar quantization

(52)

Vector Quantization

(53)

Vector Quantization

The joint quantization of a block of signal values is called vector quantization (VQ). It has been theoretically shown that the performance of VQ can get arbitrarily close to the rate- distortion (R-D) bound by increasing the block size.

(54)

A Typical Compression System

Transform

Coding Quantization Entropy Encoding

I I’

Most of the compression occurs in the quantization stage.

Lossless compression/entropy coding, typically involves run- length coding combined with Huffman codes, further save bits in an invertible fashion.

(55)

DCT formulas

( )

otherwise

1 ) ( ), (

; 0 ,

for 2

) 1 ( ), (

: where

16 1 cos 2

16 ) 1 2

cos ( )

, ( ) ( ) 4 (

) 1 , (

16 1 cos 2

16 ) 1 2

cos ( )

, ( )

( ) 4 (

) 1 , (

7

0 7

0

7

0 7

0

=

⎥⎦

⎢ ⎤

⎣

⎡ + +

=

⎥⎦

⎢ ⎤

⎣

⎡ + +

=

∑∑

= =

v C u C

v u v

C u C

v y

u v x

u F v C u C y

x f

v y

u y x

x f v

C u C v

u F

u v

x y

π π

(56)

DCT basis

The 64 (8 x 8) DCT basis functions:

DC Coefficient

AC Coefficients

(57)

Image Representation with DCT

DCT coefficients can be viewed as weighting functions that, when applied to the 64 cosine basis functions of various spatial frequencies (8 x 8 templates), will reconstruct the original block.

Original image block DC (flat) basis function AC basis functions

(58)

DCT Coefficients Quantization

The DCT coefficients are quantized to limited number of possible levels.

The Quantization is needed to reduce the number of bits per sample.

Formula:

F( u, v) = round[ F( u, v) / Q( u, v)]

– Q( u, v) = constant => Uniform Quantization.

– Q( u, v) = variable => Non-uniform Quantization.

Formula:

F( u, v) = round[ F( u, v) / Q( u, v)]

–– Q( u, v) = constant => Uniform Quantization.Q( u, v) = constant => Uniform Quantization.

–– Q( u, v) = variable => Non-Q( u, v) = variable => Non-uniform Quantization.uniform Quantization.

Example:

101000 = 40 (6 bits precision) → Truncates to 4 bits = 1000 = 8 (4 bits precision).

i.e. 40/5 = 8, there is a constant N=5, or the quantization or quality factor .

(59)

DCT example

(60)

1-D Discrete Wavelet Transform (DWT)

The forward discrete wavelet transform (DWT) decomposes a one-dimensional (1-D) sequence (e.g., line of an image) into two sequences (called subbands), each with half the number of samples, according to the following procedure:

– The 1-D sequence is separately low-pass and high-pass filtered.

– The filtered signals are downsampled by a factor of two to form the low-pass and high-pass subbands.

– The two filters are called the analysis filter bank.

(61)

The 1-D Two-Band DWT

(62)

2-D Wavelet decomposition

(63)

DWT benefits

•Multiple resolution representation

•Lossless representation with integer filters

•Better decorrelation than DCT, resulting in higher compression efficiency

•Use of visual models: DWT provides a frequency band decomposition of the image where each subband can be quantized according to its visual importance (similar to the quantization table specification in JPEG-DCT)

(64)

Scalable Vector Graphics

An Overview

Scalable Vector Graphics Scalable Vector Graphics

An Overview An Overview

(65)

Introduction

zz SVG is a language for describing twoSVG is a language for describing two--dimensional dimensional graphics in

graphics in XMLXML. .

zz SVG allows for three types of graphic objects: SVG allows for three types of graphic objects:

–– Vector graphic shapesVector graphic shapes (e.g., paths consisting of straight (e.g., paths consisting of straight lines and curves),

lines and curves),

–– ImagesImages;;

–– Text (also called glyphs). Text (also called glyphs).

(66)

Standards

zz SVG 1.0SVG 1.0 is a Web standard is a Web standard (a W3C (a W3C Recommendation).

Recommendation).

zz Work continues on the modular Work continues on the modular SVG 1.1/1.2SVG 1.1/1.2 and on and on the the Mobile SVG profilesMobile SVG profiles..

zz Powerful portability (display resolution Powerful portability (display resolution independence

independence) )

(67)

SVG Document 1/2

zzAll tags must have a start and end tag, All tags must have a start and end tag,

<rect>

… …

</rect>; </rect>; <text><text>

… …

</text>; </text>; <g><g>

… …

^</g>^</g>

or must be noted as an empty tag. Empty tags are closed with a or must be noted as an empty tag. Empty tags are closed with a

backslash, as in backslash, as in

<rect

… …

/>; <circle />; <circle

… …

/>; <path />; <path

… …

^/>^/>

zzTags must be nested properly. If a tag is opened within another Tags must be nested properly. If a tag is opened within another tag, it must be

tag, it must be closed within that same tag. For example, closed within that same tag. For example,

<g><text>Hello there!</text></g>

<g><text>Hello there!</text></g> is correctis correct, , but but <g><text>Hello there!</g></text><g><text>Hello there!</g></text> is notis not..

An SVG document is an XML document. That means that SVG documents have certain basic attributes:

An SVG document is an

An SVG document is an XMLXML document. That means that SVG document. That means that SVG documents have certain basic attributes:

documents have certain basic attributes:

(68)

SVG Document 2/2

z The document must have a single root. Just as a single

<html></html> element contains all content for an HTML page, single <svg></svg> element contains all content for an SVG

document.

z The document should start with the XML declaration, ^<?xml

version="1.0"?>

z The document should contain a DOCTYPE declaration, which points to a list of allowed elements:

<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN“

"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">

(69)

SVG Example 1/3

<?xml version="1.0"?>

<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"

"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">

<desc>All SVG documents should have a description</desc>

<defs>

</defs>

<g>

</g>

</svg>

(70)

SVG Example 2/3

<?xml version="1.0" standalone="no"?>

<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN” "http://www.w3.org/TR/2001/REC-SVG- 20010904/DTD/svg10.dtd">

xmlns:xlink="http://www.w3.org/1999/xlink">

<defs>

</defs>

Text travels along any path that you define for it.

</textPath>

</text>

</svg>

(71)

SVG Example 3/3

<?xml version="1.0"?>

<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN” "http://www.w3.org/TR/2001/REC-SVG- 20010904/DTD/svg10.dtd">

<desc>Colors</desc>

<defs>

</linearGradient>

</defs>

<g>

</g>

</svg>

a

(72)

SVG Raster vs. Vectorial 1/2

Comparison between Comparison between raster image and

raster image and vectorial image.

vectorial image.

(73)

SVG Raster vs. Vectorial 2/2

Comparison between

Comparison between rasterraster image and image and vectorialvectorial image.image.

(74)

Possible Optimization

z Use of pattern gradient detection instead of

multiple color surfaces;

z Better edge detection;

zPreprocessing filtering (Noise Reduction, Color Enhancement, Sharpness);

zBetter use of “style” and “transform” tags.