Chapter six

Chapter six
Image
Compression
Basic definition of image compression
 Digital images require huge amounts of space for storage and large
bandwidths for transmission.
• A 640 x 480 color image requires close to 1MB of space.
• the space required for a SD ( Standard Definition 720 * 480 x

24 bit pixel array ) movie of 2 hours running at 30 fps. 224 GB storage
space required.
 Data is used to convey information.
 Various amount of data may be used to represent the same information
 Image compression: reduces the amount of data required to represent a

digital image by removing redundant data.
Cont…
 Suppose that two representations have the same amount of information
one using n1 units of data and the other one n2 units of data.
• Compression ratio: Cr=n1/n2
 Relative data redundancy of the first set is defined as:
• Rd=1-1/ Cr
 n2<<n1, Cr approaches infinity and Rd approaches one. This means that the
data n1 has been highly redundant.
 n2>>n1, Cr approaches zero and Rd approaches minus infinity. This

means
that the data n2 contains more data (expansion instead of compression).
Cont…
 A typical compression ratio:
10
• Cr=10, Rd=1-1/10= 0.9
• 90% of the data in the first set is redundant
 Three forms of data redundancies exist in digital images
1. Coding redundancy
2. Spatial and temporal redundancy
3. Irrelevant information
Cont…
 A code is a system of symbols used to represent a body of information or set
of events.
 Each piece of information or event is assigned a sequence of code symbols

called code word.
 The number of symbols in each code word is called its length.
 E.g. Each pixel in a gray scale image is represented by 8-bits binary.

(Pixel
value = 255, code = 11111111, code length per pixel= 8).
 Spatial Redundancy means the neighbouring pixels are correlated in a 2-D
image and hence it is redundant to store all the pixel values.
 Temporal Redundancy is observed in case of videos where the adjacent

frames are similar to each other i.e. the frames are correlated in time.
Coding redundancy
 The gray-level histogram of an image can provide a great deal of
insight into the construction of codes to reduce the amount of data used to
represent the image.
 Assume that a discrete random variable rk, in the interval [0, L - 1] is used
to represent the intensities of an M x N image and that each rk occurs with a

probability pr(rk).
 Suppose that gray-level rk is represented by l(rk ) bits
 Average length of code words used for the image:
 Average length of a code is sometimes called the rate of that code

Cont…
 If the same number of bits is used for all gray levels (natural m-bit
binary code).
 If fewer bits are assigned to more probable gray-levels than to the less
probable ones, compression can be achieved.
 This is called Variable Length Coding

(VLC).
Cont…
 E.g.
 If the scheme designated as code 2 in above is used, the average length of

the encoded pixels is,
• Lavg = 0.25(2) + 0.47(1) + 0.25(3) + 0.03(3) = 1.81 bits
 The total number of bits needed to represent the entire image is
• MNLavg = 256 x 256 x 1.81 or 118,621 bits.
Spatial and temporal redundancy
 Codes designed based on histogram do not exploit the correlation
between pixels.
 These correlations result from the structural or geometrical relationships

between the objects in the image.
 The value of any pixel is highly correlated to its neighbors and the
information carried by individual pixels is small.
 How to reduce spatial and temporal redundancy?
 The image (which is a 2-D array) is transformed into a more efficient

format, this process is called mapping or transformations.
 The transformation should reduce the redundancy.

Irrelevant Information
 The eye does not response with equal sensitivity to all visual
information.
 Certain information has less relative importance than other.
 This information is said to be psychovisually redundant. It can be

eliminated without significantly impairing the quality of image
perception.
 Since the elimination of irrelevant information results in a loss of
quantitative information, it is commonly referred to as

quantization.
Elements of Information Theory
 Information source generates a random sequence of symbols.
 The set of source symbols (source alphabet) A:
 Average information per source output
 H: uncertainty or entropy of the source, it is the average amount of

information obtained by observing a single source output
 If the source symbols are equally probable, the entropy is maximized

Cont…
 The entropy of the image on the above Fig. can be estimated
by substituting the intensity probabilities from the above
Table:
Fidelity Criteria
 Since information may be lost during compression a means of
quantifying
the information loss is desirable.
 Two type of criteria:
• Objective fidelity criteria
• Subjective fidelity criteria
 Objective fidelity criteria: the information loss is expressed as a function of
input image (original image) and output image (compressed and

decompressed)
Cont…
 An example is the root-mean-square (rms) error between two images. Let
f(x,y)
be an input image and f(x, y) be an approximation of f(x,y) that results from
compressing and subsequently decompressing the input. For any value of x and
y, the error e(x, y) between f(x, y) and f(x, y) is:
Cont…
 Objective fidelity criteria: simple and convenient, sometimes misleading
 Subjective fidelity criteria: measuring image quality by the subjective

evaluation of a group of viewers and averaging their evaluations.
Image Compression Models
 A compression system consists of two distinct structure of blocks: encoder and
decoder.
 Encoder: creates a set of symbols from the input image
 Decoder: reconstructs an output image
Cont…
 Encoder: responsible for reducing or eliminating any coding, interpixel
or pschovisual redundancies in the input image.
 Encoding can be modeled by three independent operations.
 Each operation is designed to reduce one of the three redundancies.

Cont…
 Mapper (transform): transforms the input data into a format designed to spatial and
temporal redundancies.
• This operation generally is reversible.
• It may or may not reduce the amount of data required to represent the image.
 Quantizer: reduces the accuracy of the mapper’s output.
• This stage removes the irrelevant information.
• This operation is irreversible. It should be omitted when error-free (loss less) compression
is
desired.
 Symbol coder: creates a fixed or variable length code to represent the quantizer’s
output.
• In most cases a VLC is used (shortest code words to the most frequently occurring values
of
the quantizer’s output)
• The operation is reversible.
Cont…
 Decoder Contains two
components:
• Symbol decoder
• Inverse mapper
 They perform the inverse operations of symbol encoder and mapper.

 Lossy image compression: is useful in applications such as
broadcasting television and video conferencing (multimedia) in which
certain amount of error is acceptable trade off for increased compression
performance.
 Reconstructed data is approximation to the original data.
(Source coding)
 Examples Linear prediction,Transform coding
Lossless image compression: useful in image archiving such as legal and
medical records where the image will be compressed and decompressed
without losing any information.
 Reconstructed data is identical with the original data.
(Entropy coding)
 Examples-Huffmancoding,Arithemetic,Shanon-fano-coding
Image Formats, Compression
Standards
Cont…
Cont…
Cont…
Some basic compression methods
 Huffman coding
 Huffman coding is the most popular technique for VLC coding and removing
the coding redundancies.
 The first step in Huffman coding is to create a series of source reductions by
ordering the probabilities of the symbols and combining the lowest

probabilities into a single symbol that replaces them in the next source
 reduction.
The second step is to code each reduced source
 It is a variable-length coding technique.
 Optimal code (i.e., minimizes the number of code symbols per source symbol).
 Assumption: symbols are encoded one at a time!

Cont…
 Initialization: Put all symbols on a list sorted according to their frequency counts.
2. Repeat until the list has only one symbol left:
(a) From the list pick two symbols with the lowest frequency counts. Form a
Huffman subtree that has these two symbols as child nodes and create a
parent node.
(b) Assign the sum of the children's frequency counts to the parent and insert
it into the list such that the order is maintained.
(c) Delete the children from the list.
3. Assign a codeword for each leaf based on the path from the root
Code of:
D1 = 000
D2 = 001
D3 = 01
0 1
D4 = 1
D4
. 0 1
1 D3
0
D1 D2
Cont…
 Arithmetic Coding
 No assumption on encoding source symbols one at a time.
 Sequences of source symbols are encoded together.
 There is no one-to-one correspondence between source symbols and code words.
 Slower than Huffman coding but typically achieves better compression.
 A sequence of source symbols is assigned a single arithmetic code word which
corresponds to a sub-interval in [0,1].
 As the number of symbols in the message increases, the interval used to
represent it becomes smaller.
 Smaller intervals require more information units (i.e., bits) to be represented.

Chapter six

Uploaded by

Copyright:

Available Formats

Chapter six

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter six

Uploaded by

Copyright:

Available Formats

Chapter six

• A 640 x 480 color image requires close to 1MB of space.

• the space required for a SD ( Standard Definition 720 * 480 x

 Data is used to convey information.

 Various amount of data may be used to represent the same information

 Image compression: reduces the amount of data required to represent a

• Compression ratio: Cr=n1/n2

 Relative data redundancy of the first set is defined as:

 n2>>n1, Cr approaches zero and Rd approaches minus infinity. This

• 90% of the data in the first set is redundant

 Three forms of data redundancies exist in digital images

2. Spatial and temporal redundancy

 Each piece of information or event is assigned a sequence of code symbols

 The number of symbols in each code word is called its length.

 E.g. Each pixel in a gray scale image is represented by 8-bits binary.

image and hence it is redundant to store all the pixel values.

 Temporal Redundancy is observed in case of videos where the adjacent

to represent the intensities of an M x N image and that each rk occurs with a

 Average length of code words used for the image:

 Average length of a code is sometimes called the rate of that code

 This is called Variable Length Coding

 If the scheme designated as code 2 in above is used, the average length of

 These correlations result from the structural or geometrical relationships

 How to reduce spatial and temporal redundancy?

 The image (which is a 2-D array) is transformed into a more efficient

 The transformation should reduce the redundancy.

 This information is said to be psychovisually redundant. It can be

quantitative information, it is commonly referred to as

 The set of source symbols (source alphabet) A:

 Average information per source output

 H: uncertainty or entropy of the source, it is the average amount of

 If the source symbols are equally probable, the entropy is maximized

• Objective fidelity criteria

• Subjective fidelity criteria

 Objective fidelity criteria: the information loss is expressed as a function of

input image (original image) and output image (compressed and

 Subjective fidelity criteria: measuring image quality by the subjective

 Encoding can be modeled by three independent operations.

 Each operation is designed to reduce one of the three redundancies.

• This operation generally is reversible.

 Quantizer: reduces the accuracy of the mapper’s output.

• This stage removes the irrelevant information.

 They perform the inverse operations of symbol encoder and mapper.

the coding redundancies.

 The first step in Huffman coding is to create a series of source reductions by

ordering the probabilities of the symbols and combining the lowest

 It is a variable-length coding technique.

 Assumption: symbols are encoded one at a time!

 No assumption on encoding source symbols one at a time.

 Sequences of source symbols are encoded together.

 There is no one-to-one correspondence between source symbols and code words.

 Slower than Huffman coding but typically achieves better compression.

 A sequence of source symbols is assigned a single arithmetic code word which

corresponds to a sub-interval in [0,1].

 As the number of symbols in the message increases, the interval used to

represent it becomes smaller.

 Smaller intervals require more information units (i.e., bits) to be represented.

You might also like