Transformations in

Digital Image Processing

Saadman Sakib
Assistant Professor, Department of CSE, CUET
What is Transform & Why is it Required?
A way of changing something!

Move an object where it is hard to work with to a place where it is simpler.

Fourier Series
 Fourier Series
• Image Pattern and Shape Analysis

Outlines can be analyzed to identify the objects

Any digital image, including the objects inside it, can be represented as a weighted sum of 2D sinusoids.
 Removing
Noise

Some image problems are difficult in the spatial domain but simple in the frequency domain.
Example: periodic stripe noise becomes isolated peaks in the spectrum, so the peaks can be
removed directly.
After filtering in frequency domain, IFT reconstructs the cleaned image.

3
 Fourier Transform
• A Tool!
 What is Fourier Transform?
Convert the time domain signal into frequency domain signal!
What is Fourier Transform?
What is Fourier Transform?
 What it means on an image?
The response of the Fourier Transform to periodic patters in the spatial
domain images can be seen in the following images:
 What is DFT?
• The Discrete Fourier Transform (DFT) converts a signal from the
spatial domain (or time domain) to the frequency domain. For images,
this means transforming the pixel values into frequencies.
• In mathematical terms, for a signal (or image) with N points (or
pixels), the DFT equation is given by:
 Kernel
•
 Inverse DFT (IDFT)
• The Inverse DFT (IDFT) converts the signal back from the frequency
domain to the spatial (or time) domain. The IDFT equation is given
by:

• The main difference from the DFT equation is the sign in the exponent
(which is now positive), and the result is divided by N to normalize the
transformation.
 Example
• Let’s go through a simple 1D example with 4 samples (N=4).
x = [1, 2, 3, 4] and Compute the DFT and IDFT.
 Example
Calculating DFT:
Formula:

Thus X [1] = -2 + 2j
 Example

Thus, the DFT of the signal is X=[10, −2+2j, −2 , −2−2j ]

 Example
X=[10, −2+2j, −2 , −2−2j ]
 Exercise

Apply DFT on the signal x[n]=[2,0,1,3]

Find the Magnitude Spectrum
 Exercise

Apply DFT on the signal x[n]=[2,0,1,3]

Find the Magnitude Spectrum
IDFT
IDFT
 2D DFT
•
 2D DFT
• Step 1: Calculate X[0,0]
For u=0 and v=0:

This simplifies to: X[0,0] = 1+2+3+4=10

• Step 2: Calculate X[0,1]
For u=0 and v=1:
This simplifies to:
 2D DFT
• Step 3: Calculate X[1,0]
For u=1 and v=0:

This simplifies to:

X[1,0] = 1+2−3−4 = −4
 2D DFT
•

X[1,1] = 1−2−3+4 = 0
Inverse 2D DFT
 Separability Property
• The separability property of the 2D Discrete Fourier Transform (DFT)
means that the 2D DFT can be computed by performing two 1D DFTs in
sequence
— First along the rows and then along the columns, or vice versa.
This property reduces the computational complexity of the 2D DFT.

Anything Better?
The savior is FFT! Divide and Conquer
Noise Reduction
Compression and Data Reduction?
 DCT
❑ The Discrete Cosine Transform (DCT) is a mathematical technique that
transforms a signal or image from the spatial domain (pixel values) into the
frequency domain (coefficients).
The discrete cosine transform is a transform associated with the Fourier
transform
It is widely used in image processing, especially in compression algorithms
like JPEG, due to its excellent energy compaction properties.
❑ The most important values to our eyes will be placed in the upper left
corner of the matrix.
❑ The least important values will be mostly in the lower right corner of the
matrix.
 Relationship between DCT and FFT
DCT (Discrete Cosine Transform) is similar to the DFT since it decomposes a
signal into a series of harmonic cosine functions. DCT is actually a cut-down
version of the Fourier Transform or the Fast Fourier Transform (FFT):
• Only the real part of FFT (less data overheads).
• Computationally simpler than FFT.
• DCT— effective for multimedia compression (energy compaction).
• DCT much more commonly used (than FFT) in multimedia image/video
compression
• FT captures more frequency “fidelity” (e.g . phase)
 DCT
❑ The general formula for the 1D DCT is:

❑ The formula for the 1D IDCT is:

Where
f(x) is the original data value at index x
N is the length of the data
u is the frequency index ranging from 0 to N−1
α(u) is a normalization factor:
DCT
 DCT
❑ DC represents average intensity of a block
❑ Use zig-zag ordering of coefficients
• orders frequency components from low->high
• produce maximal series of 0s at the end
 DCT
❑ Consider a some sample values:

Here, N = 8
Calculating 𝐶(0) :
For 𝑢=0:
 DCT

Calculating 𝐶(1) :
For 𝑢=1:

The calculated sum after all terms:

C(1) = −112.54
 DCT

Repeat for u = 2 to u = 7
 2D DCT
(No need to apply 2D form directly):
• As with 2D Fourier Transform.
• Apply 1D DCT (vertically) to columns.
• Apply 1D DCT (horizontally) to resultant vertical DCT.
• Or alternatively horizontal to vertical.
 2D DCT on Image Block
Image is partitioned into 8 x8 regions —
• The DCT input is an 8 x 8 array of integers.
• So in N = M = 8, substitute these in DCT formula.
 Visualization: 2D DCT Basis Images
Each DCT coefficient tells how much of one cosine pattern is present in the block.
2D IDCT
 Energy Compaction Property
The energy compaction property refers to the ability of the transform to
concentrate most of the signal's energy into a few coefficients. This is essential
for image compression, as it allows us to keep only the most significant
coefficients and discard the less significant ones.
Zig-zag Scan: Turning 2D Coefficients into a Compressible
Sequence
After quantization, coefficients are read from low frequency to high frequency.

Why zig-zag?

• Low-frequency coefficients are usually nonzero and important.

• High-frequency coefficients often become zero after quantization.
• Zig-zag order places long runs of zeros near the end of the sequence.
• Run-length coding can store those zeros compactly.

Example idea:
[large, small, small, 0, 0, 0, 0, ...]
 2D DCT on Images: From Pixels to
Compression
DCT transforms an image block into cosine-frequency coefficients; compression reduces less important high-frequency data.

Split into Level Shift 2D DCT Quantize Zig-zag + Run Compressed

Image Length coding bitstream
8x8 blocks -128

Core idea Compression idea

Reconstruction
Most natural image energy is Quantize coefficients so many
Inverse DCT gives an
concentrated in low-frequency high-frequency values become
approximate image block.
DCT coefficients. zero.
 8×8 Block → DCT → Quantization →
IDCT

Level shifting DCT Quantization IDCT

Subtract 128 so values are Concentrates energy near the Nonzero coefficients: 20/64 Approximate visual
centered around zero. top-left coefficients. Many become 0. reconstruction.
How Quantization Helps
Compression
Quantization divides each coefficient by a step size and rounds it to an integer.

Qcoeff[u,v] = round( C[u,v] / Qtable[u,v] )

Ĉ[u,v] = Qcoeff[u,v] × Qtable[u,v]

Small quantization step → better quality, less compression.

Large quantization step → stronger compression, lower quality.
JPEG uses larger steps for high frequencies because human
vision is less sensitive to fine detail.
 Example 3: Quantization on an 8×8 DCT Block
Low-frequency coefficients are near the top-left; high-frequency coefficients are toward the bottom-right.
Example 4: Divide by Q Table, Then Round
This is the exact place where many coefficients become small integers or zero.
Example 5: Quantization Strength vs Image Quality
More aggressive quantization increases compression but also increases reconstruction error.
 Compression Trade-off: Keep Fewer DCT Coefficients
The fewer coefficients we keep, the higher the compression — but the reconstructed block loses detail.

Keep all coefficients

Keep 1 coefficient Keep several coefficients
Perfect reconstruction if no
Only average brightness. Smooth structure is recovered.
quantization.
 Advantages
❑ It is a real transform with better computational efficiency because it uses
only real numbers.
❑ DCT has excellent energy compaction properties.
❑ DCT is the standard for data compression because of high correlation in
adjacent coefficients and We can reconstruct a sequence very accurately from
very few DCT coefficients
❑ DCTs are important tool for lossy compression of audio (e.g. MP3) and
images (e.g. JPEG) (where small high frequency components can be discarded)
 Disadvantages
❑ Disadvantage with DCT is that only spatial correlation of the pixels inside
the single 2D block is considered and the correlation from the pixels of the
neighboring blocks is neglected
 Practice Problem
Solve the quantization and dequantization steps using the given DCT coefficients and Qtable.

Given DCT coefficient matrix: Given quantization table:

C[u,v] = Qtable[u,v] =
[ 160 −34 12 5 ] [ 8 10 16 20 ]
[ −28 18 −9 3 ] [ 10 16 20 24 ]
[ 10 −6 4 2 ] [ 16 20 24 32 ]
[ 3 2 −1 1 ] [ 20 24 32 40 ]

Quantization: Dequantization:
Qcoeff[u,v] = round( C[u,v] / Qtable[u,v] ) Ĉ[u,v] = Qcoeff[u,v] × Qtable[u,v]

Questions
1. Compute the quantized coefficient matrix Qcoeff[u,v].
2. Compute the dequantized/approximately reconstructed DCT matrix Ĉ[u,v].
3. Compute the quantization error matrix: E[u,v] = Ĉ[u,v] − C[u,v].
4. Count how many coefficients become zero after quantization.
5. Explain briefly why these zeros help image compression.
 Wavelet
❑ FFT, basis functions: sinusoids
❑ Wavelet transforms: small waves, called wavelet
❑ FFT can only offer frequency information
❑ Wavelet: frequency + temporal information
❑ Fourier analysis doesn’t work well on discontinuous, “bursty” data
--- music, video, power, earthquakes,…
 Wavelet Definition
❑ “The wavelet transform is a tool that cuts up data, functions or operators into
different frequency components, and then studies each component with a
resolution matched to its scale”
--- Dr. Ingrid Daubechies, Lucent, Princeton U
 Fourier transform
Fourier transform:
 Continuous Wavelet transform
for each Scale
for each Position
Coefficient (S,P) = Signal x Wavelet (S,P)
all time
end
end
Scale
Coefficient
 Wavelet Transform
• Scale and shift original
waveform
• Compare to a wavelet
• Assign a coefficient of
similarity
Wavelet Transform
 Five Easy Steps to a Continuous
Wavelet Transform
1. Take a wavelet and compare it to a section at the start of the original signal.
2. Calculate a correlation coefficient c
3. Shift the wavelet to the right and repeat steps 1 and 2 until you've covered the whole signal.
4. Scale (stretch) the wavelet and repeat steps 1 through 3.
5. Repeat steps 1 through 4 for all scales.
 Discrete Wavelet Transform
1.“Subset” of scale and position based on power of two
a) rather than every “possible” set of scale and position in continuous wavelet
transform
[Link] like a filter bank: signal in, coefficients out
MultiResolution Approximation
MultiResolution Approximation
MultiResolution Approximation
MultiResolution Approximation
MultiResolution Approximation
Haar Transform
Low Frequency
• LL : Represents the approximated version of the original at half the
resolution.
High Frequency
• LH: The LH block contains horizontal edges
• HL: The HL block contains vertical edges
• HH: we find edges of the original image in diagonal direction
2D Haar Transform Mother Basis
 Haar Matrix
Haar transform coefficients for an image are given by:

And the Inverse transform is given by:

 Advantages
❑ Higher flexibility: Wavelet function can be freely chosen. Such as Haar,
Morlet and Daubechies
❑ No need to divide the input coding into non-overlapping 2-D blocks and it
has higher compression ratios avoid blocking artifacts.
❑ Transformation of the whole image
❑ Better identification of which data is relevant to human perception.
 Disadvantages
❑ The cost of computing DWT as compared to DCT is higher.
❑ The use of larger DWT basis functions produces blurring and ringing noise
near edge regions in images or video frames
❑ Longer compression time
❑ Lower quality than JPEG at low compression rates
Hadamard Transform
Hadamard Matrix
Sequence in HT
Hadamard Transform for 1D and 2D
2D HT

Sequence
0
3
1
2
2D HT
Sequence
0
1
2
3
2D HT
 Advantages
❑ Good energy compaction property
❑ Low loss in image information (higher image fidelity)
❑ Greater reliability of watermark detection.
❑ Higher data hiding capacity than others.
❑ Hadamard transform is faster than sinusoidal transforms. The fast
Hadamard transform (FHT) has been used for high speed applications. The
Hadamard only requires additions, but no multiplication.
❑ The Hadamard is used in image compression when DCT is too costly and
cannot be done in real-time.
 Disadvantages
❑ Depends on N×N (Square size) Hadamard matrix, N= 2n, n=1,2,3…,
No other size is allowed.
❑ It performs well on block wise signal such as 8×8 or 4 × 4
 Singular Value Decomposition
Simple Basic Linear Transformations
 Singular Value Decomposition
Rotation and Scaling !
 Singular Value Decomposition
Intuition:
 Singular Value Decomposition
Rotation, Scaling and Rotation!
 Singular Value Decomposition
For Calculating V: For Calculating U:
Compute ATA Compute AAT
Eigen Vectors?
Eigen Vectors (Intuition)
Eigen Vectors (Characteristic Equation)
Eigen Vectors (Finding Eigen Values)
Eigen Vectors
Eigen Vectors
SVD STEPS
SVD STEPS
SVD STEPS
SVD STEPS
SVD STEPS
 SVD STEPS
Calculate AAT
And do the similar process to obtain U matrix!

Finally!
SVD on Image
SVD on Image
SVD on Image
SVD on Image
SVD on Image
THANK YOU