Image Compression

By
Mrs. R. Sorna Keerthi
Asst. Prof., Dept. of ECE,
Anna University,
University College of Engineering,
Ramanathapuram

12/27/2025 1
Topics to be Covered
 Introduction
 Need for Image Compression
 Image Compression Techniques
 Huffman Coding
 Run – Length Coding
 Shift Coding
 Arithmetic Coding

12/27/2025 2
 Introduction

 Image compression – reduce no. of bits required to

represent an image.
 Sampling of band limited images – infinite no. of
pixels per unit area reduced to one sample without
any loss of information.
 Reduce no. of samples per unit area.
 Used in transmission and storage of information.

12/27/2025 3
Need for Image Compression

 To minimize the storage space.

 To enable higher rate of data transfer.
 To develop a newer and faster algorithms
adapted to image data.

12/27/2025 4
Classification of Image Compression

 Lossless Image Compression

 Lossy Image Compression

12/27/2025 5
How to achieve compression?

 By minimizing the redundancy in the

image.
 Redundancy
◦ Inter pixel redundancy
◦ Psycho visual redundancy
◦ Coding redundancy

12/27/2025 6
Data Vs Bandwidth Compression
 Converting analog to digital results in
increased bandwidth requirement for
transmission.
 Advantages of digital
◦ Flexibility
◦ Random access in storage
◦ High SNR (errorless transmission)
 Data Compression techniques
◦ Minimize cost
◦ Reduce bandwidth
12/27/2025 7
Disadvantages

 Distortion due to accompanying ADC

with compression results in significant
loss of information.
 Shannon’s noiseless coding theorem –
code without distortion.

12/27/2025 8
 Applications

 Image Transmission  Image Storage

◦ Broadcast television ◦ Educational and business
◦ Remote sensing through documents
satellite ◦ Medical images – computer
◦ Military communication tomography (CT)
through aircraft ◦ Magnetic Resonance Imaging
◦ Radar and sonar (MRI)
◦ Teleconferencing ◦ Digital radiology
◦ Computer communications ◦ Motion pictures
◦ Facsimile transmission ◦ Satellite images
◦ Weather maps
◦ Geological Surveys

12/27/2025 9
Categories of Image Compression
 Predictive coding
◦ Exploit redundancy in data
◦ Predictability, randomness and smoothness in
data
◦ Can use DM and DPCM
 Transform coding
◦ Transforms the given image into an array
◦ Large amt. of info. Packed into small no. of
samples.

12/27/2025 10
Predictive coding Transform coding
 Delta modulation  Zonal coding
 Line-by-line DPCM  Threshold coding
 2D-DPCM  Multidimensional techniques
 Inter frame Techniques  Adaptive
 Adaptive

Pixel coding Other methods

 PCM/Quantization  Hybrid coding
 Run-length coding
 2-tone/graphics coding
 Color image coding
 Bit-plane coding
 Vector quantization
 miscellaneous

12/27/2025 11
Pixel coding
 Each pixel processed independently,
ignoring inter pixel dependencies.

 Methods:
◦ PCM
◦ Entropy coding - Huffman Coding Algorithm
◦ Run – length coding
◦ Bit – plane coding

12/27/2025 12
PCM
 Incoming video signal is sampled, quantized and coded
 Quantizer output coded by fixed length binary code
word having B bits.
E.g.: (i) Monochrome broadcast or video
conferencing of quality images =8 bits/pixel
(ii) Medical images/color video
signals = 10 or 12 bits/pixel
 Companding/contrast quantization/dithering techniques
– reduce the number of quantizing bits.
 Compression ratio < 2:1

12/27/2025 13
Entropy Coding

 Encode a block of M pixels containing MB bits

with probabilities pi , i=0,1,…L-1
 Average bit rate,
 Variable length codes: highly probable blocks
small length codes, low probable blocks 
large length codes.
 Huffman coding – most efficient fixed to
variable length encoding method.

12/27/2025 14
Huffman Coding
 Popular method to remove coding redundancy.
 Gives smallest possible number of code symbols per
source symbol, if coding the symbols of an information
source individually.
 Source symbols  intensities of an image or output of
intensity operations like pixel difference, run-lengths
etc.
 Creates optimal code but codes one symbol at a time.
 Uses a simple look-up table manner.
 Instantaneous uniquely decodable block code.

12/27/2025 15
Huffman Coding Algorithm

 Arrange Symbol probabilities in decreasing

order (leaf nodes of the tree).
 If more than one node,
◦ Merge two nodes with smallest probability to form a
new node whose probability is the sum of two nodes.
◦ Assign 1 and 0 to each pair of branches merging to a
node.
 Read sequentially from root node to leaf node
where the symbol is located.

12/27/2025 16
Huffman Coding

12/27/2025 17
Huffman Coding…

12/27/2025 18
Huffman Coding…

12/27/2025 19
Huffman Coding…

12/27/2025 20
Huffman - Example

12/27/2025 21
Huffman Coding…
 Buffer needed since code words are
variable length codes.
 Information transmitted over a constant
rate channel.
 Truncated Huffman code - Practical
version
◦ Select L1 < L
◦ First L1 symbols  Huffman coded
◦ Remaining symbols  By prefix coding by
suitable fixed length code

12/27/2025 22
Huffman Coding…

 Modified Huffman Code

◦ Integer i=qL1+j,
◦ First L1 symbols  Huffman coded.
◦ Remaining symbols  By prefix codes
representing quotient q.
◦ Terminator code  same as Huffman but for
remainder j, 0≤j≤L1-1.

12/27/2025 23
Disadvantage of Huffman coding

 Hard to construct optimal Huffman code if

large number of symbols are coded.
◦ J source symbols, J symbol probabilities, J-2 source
reductions, J-2 code assignments.

12/27/2025 24
Use of Entropy Coding

 Not practical for raw image data.

 Useful in predictive and transform coding
algorithms.
 Used in coding of binary data such as
graphics and facsimile images.

12/27/2025 25
Run – length Coding (RLC)
 Consider binary source whose output is coded as
number of 0s between two successive 1s, length of runs
of 0s are encoded.
 Used when large runs of 0s expected.
 Used in printed documents, graphics and whether maps.
 The probability of 0 (representing white pixel)=p.
 If runs coded in maximum length of M=2m-1
 m bits to code each run by a fixed length code.
 If successive 0s occur independently, the prob. Distr. Of
run lengths (geometric distribution)

12/27/2025 26
RLC…
 If run-length l≤M-1, sequence of l 0s followed by a 1.
 Consists of l+1 symbols.
 Average number of symbols per run,

 Takes m bits to establish run-length code for a sequence of µ

binary symbols on average.
 Compression is
 Example: Given, p=0.9, M=15,
then m=4, µ=7.94, C=1.985
Average Rate, Ba = m/µ=0.516 bits/pixel
Code efficiency=H/Ba=91%

12/27/2025 27
RLC…

 For a given p, determine optimum value of M to give

highest efficiency.
 Can improve efficiency by variable length coding (E.g.
Huffman Coding for block length m).
 Can use arithmetic coding instead of run-length coding.

12/27/2025 28
RLC - Procedure
 Binary image viewed as a sequence of alternating strings
of 0s (black) and 1s (white).
 Length of black and white runs on scan lines are coded.
 Use run-length codes to represent these strings or
runs.
 For raster scanned images, simple run-length code has
start address of each string of 1s (or 0s) followed by
length of that string.
 Used to minimize the number of bits required to
represent binary images.

12/27/2025 29
RLC…

12/27/2025 30
RLC for Binary Image Boundary
Representation

12/27/2025 31
RLC…
 Advantage:
◦ Representation in a single raster scan, even
the region is complex.
 Disadvantages:
◦ Does not give region boundary points
ordered along its contours, same as chain
coding.
◦ Difficult to segment different regions if several
present in image.

12/27/2025 32
 Limitation of RLC
Black (0) and white (1) runs alternate, Color of
run is not coded

First run always a white run with length 0, if

necessary.

Run lengths coded by fixed length m-bit code

words

Each representing a block of maximum run length

M-1.

Optimize M to maximize compression.

Can use truncated/modified Huffman codes if

large code book

12/27/2025 33
RLC and White Block Skipping

12/27/2025 34
Variable Length Codes – AN & BN Codes

◦ AN codes:
 Also called LN codes
 Multiple fixed length codes
 Nearly optimal for exponentially distributed run lengths
 Class of linear codes
 Length increases approximately linearly with the number of messages
 If lk are run lengths for k=1,2,…, then AN code of block size N by k=q(2N-1)+r,
where 1≤r≤2N-1 and q – non negative integer.
 Codeword for lk has (q+1)N bits, first qN bits are 0 and last N bits are binary
representation of r
 Example: If N=2,A2 code for l8 (8=2 X 3 + 2) is 000010
 Geometric distribution with mean µ, optimum N is integer nearest to
(1+log2µ)
 Long run length common than predicted by exponential distribution
 Run – length distribution form, P(l)=c/lα , α>0 and c-constant
 P(l) decreases less rapidly with l than exp. Distr.

12/27/2025 35
AN & BN Codes
◦ BN codes:
 Also called HN codes
 Multiples of fixed length codes
 Word length increases as log N
 Fixed block length = N+1 bits
 Constructed by listing all possible N-bit words, 2N-bit words, 3N-bit words…
 Additional bit inserted after every block of N bits
 Inserted bit is 0 except for bit inserted after last block, which is 1

Run-Length kN – bit Words B1 Code

1 0 01
2 1 11
3 00 0001
4 01 0011
5 10 1001
6 11 1011
7 000 000001
. . .
. . .
. . .

12/27/2025 36
RLC methods
 Modified Huffman Code
◦ One dimensional standard code for Fax transmission.
◦ Typical values, Lw = Lb = 63
◦ Run-length < 64  Huffman coded to give terminator code
◦ Remaining runs  two code words, make-up code and
terminator code.
◦ E.g.: A3 size paper – need 2560 pixels/line, use extended code
table and end-of-line (EOL) code.
 Truncated Huffman Code
◦ Assign separate Huffman code words for white and black runs
up to lengths Lw and Lb
◦ Typical values, Lw =47 and Lb = 15.
◦ Longer lengths  lower probabilities.
◦ Assign fixed length code word, consists of prefix code plus11-bit
binary code of run length.

12/27/2025 37
White Block Skipping Algorithm
 Simple form of truncated Huffman code
 Works well if image contains large white areas
 Very simple and effective compression algorithm
 Each scan line divided into blocks of N pixels
 If block contains all white pixels, it is coded by a 0
 Else, code word has N+1 bits, first bit is 1 followed by
binary pattern of block
 Bit rate is
 Where pN – probability that a block contains all white
pixels
 Rate depends on block size N (N=10)

12/27/2025 38
Adaptive WBS Scheme
 Codes all-white scan lines separately
 Assign 0 to all-white scan line
 If a line has at least one black pixel, 1 precedes
regular WBS code for that line
 Extended to 2D by MXN block of pixels
 All-white block coded by 0 & other block
coded by (MN+1) bits, first bit followed by
block bit pattern

12/27/2025 39
Adaptive WBS-Variable block size

 If initial block contains all white pixels, it is

represented by 0.
 Else prefix of 1 is assigned & block subdivided
into several sub-blocks , each treated similarly.
 Above process continues until elementary block
reached, coded by regular WBS method.

12/27/2025 40
Bit – Plane Coding
 256 – gray level image as set of eight 1-bit
planes.
 Each plane is run-length coded.
 For 8-bit monochrome images,
compression ratio is 1.5:2.
 Sensitive to channel errors if the
significant bit-planes are not protected.

12/27/2025 41
Shift Coding
 A type of variable length coding.
1. Arrange the source symbols so that their probabilities are
monotonically decreasing.
2. Divide the total number of symbols into symbol blocks of
equal size.
3. Code the individual elements within all blocks identically.
4. Add special shift up and/or shift down symbols to identify each
symbol.
 Each Time a shift up or shift down symbol is recognized
at the decoder, it moves one block up or down with
respect to a predefined – reference block.

12/27/2025 42
Shift Coding, E.g. Binary Shift Code

 Consider 21 source symbols.

 Arrange the source symbols so that their
probabilities are monotonically decreasing and
divide into three blocks of seven symbols.
 The individual symbols (a1 thro’ a7) of upper
block can be considered as the reference block.
Code the symbols in reference block with the
binary codes 000 thro’ 110.

12/27/2025 43
Binary Shift Code
 The 8th binary code is obtained by single shift
up control symbol 11 followed by 000.
 The 9th binary code is obtained by single shift
up control symbol 11 followed by 001 and so
on. . .
 This procedure continues to find the code
word of the next symbol.
 The code word for each symbol is control
symbol followed by binary sequence of
corresponding earlier block symbol codeword.

12/27/2025 44
Huffman Shift Code

 Select one reference block.

 Sum up the probabilities of all other blocks and
use it to determine the shift symbol by Huffman
method (here,“00”)

12/27/2025 45
Arithmetic Coding
 Generates non-block codes.
 One-to-one correspondence between source symbols and
code words does not exist.
 Entire sequence of source symbols is assigned a single
arithmetic code word.
 Code word defines an interval of real numbers between 0
and 1.
 As no. of symbols in message increases, smaller interval no. of
bits needed to represent interval is large.
 Each symbol reduces size of interval with prob. Of
occurrence.
 Not the symbols coded one at a time, but achieves bound
established by Shannon’s first theorem.

12/27/2025 46
Arithmetic Coding - Example
 Five symbol sequence – a1a2a3a3a4.
 Need four source symbols to be coded.
 Starting of coding  assume message to occupy entire half
open interval [0,1)
 Interval subdivided into 4 regions based on prob. of symbols.

12/27/2025 47
Arithmetic Coding – Procedure
 Symbol a1 (first symbol of message to be coded) with
subinterval [0,0.2).
 Interval [0,0.2) is expanded to full height of figure and
end points labeled by values of narrowed range.
 Narrowed range subdivided in accordance with source
symbol probabilities and process continues with next
message symbol.
 Symbol a2 narrows to [0.04,0.08) and a3 to
[0.056,0.072).
 Final message symbol which is reversed as a special end-
of-message indicator, narrows to [0.06752,0.0688).
 Any no. within this interval used to represent the image.

12/27/2025 48
Arithmetic Coding – Procedure

12/27/2025 49
Arithmetic Coding…
 Three decimal digits used to represent five-symbol
message.
 Translates into 0.6 decimal digits per source symbol and
compares with entropy of source symbol which is 0.58
decimal digits per source symbol.
 As length of code increases, the arithmetic code
approaches bound of Shannon’s first theorem.
 Two factors to cause coding performance to fall short
of bound:
◦ Addition of end-of-message indicator needed to separate one
message from another.
◦ Use of finite precision arithmetic.

12/27/2025 50
Arithmetic Coding…
 Use of finite precision arithmetic  by introducing
scaling and rounding strategy.
 Scaling strategy  renormalizes each subinterval into
[0,1) range before subdividing it in accordance with the
symbol probabilities.
 Rounding strategy  guarantees that the truncation
associated with finite precision arithmetic don’t prevent
coding subintervals from being represented accurately.
 Accurate probability model (Huffman coding) – near
optimal code to minimize the average number of code
symbols to represent the symbols coded.
 Inaccurate probability  non-optimal codes.
12/27/2025 51
Adaptive Context Dependent
Probability Estimates
 Improve the accuracy of probabilities employed.
 Update symbol probabilities while coding.
 Probabilities adapt to local statistics of symbol coded.
 Context dependent models  provide prob. Based on
predefined neighborhood of pixels (called context).
 Two arithmetic coding techniques that use adaptive and
context dependent probability models JBIG,
JPEG2000 : Q Coder and MQ Coder.
 Q-coder updates symbol probabilities dynamically
during interval renormalizations.
 Same model in Golomb coding – JPEG-LS compression
standard.

12/27/2025 52
Adaptive Context – Based
Arithmetic Coding Approach

12/27/2025 53
Adaptive Context Dependent
Probability Estimates
 Use arithmetic coding if binary source symbols are coded.
 As each symbol or bit begins coding process, context is
formed in Context Determination block.
 Fig. (a)  Immediately preceding symbol
 Fig. (b)  Group of preceding symbols
◦ Conditional probabilities P(0|a=0), P(1|a=0), P(0|a=1) and P(1|a=1)
are tracked.
◦ The appropriate probabilities are passed to arithmetic coding block
as a function of current context, drive the generation of
arithmetically coded output sequence.
◦ The probability updated to reflect the fact that another symbol
within the context is processed.
 Fig. (c)  some number of preceding symbol plus symbols
on previous scan line
 Probability estimation block manage 21, 28 and 25 contexts
and their associated probabilities.

12/27/2025 54
Thank You

12/27/2025 55