Introduction to Image Processing: 2.Frequ

Digital Image Processing Frequency domain processing (Week 4,5) NHSM -
4th year - Fall 2024 - Prof. Mohammed Hachama [email protected] http://hachama.github.io/home/

Outline Fourier series and Transform Discrete Fourier Transform (DFT) Filtering
in the frequency domain Sampling, FT and Shannon theorem Other transforms NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 2/28

Motivation • A significant part of image analysis involves the
use of filters. • Fourier transform: enables replacing computationally intensive operations with faster alternatives. • 1960, FFT: fast algorithm allowing the computation of the Fourier transform (of images). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 3/28

Motivation • Convert from spatial domain to frequency domain. •
Perform manipulations in the frequency domain. • (Re)convert the solution back to the spatial domain. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 3/28

Fourier series and Transform NHSM - 4th year: Digital Image
Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 4/28

Periodic functions Sum of sine waves • A sine wave
(or sinusoidal) f (t) = a cos(2πut + ϕ) is periodic • ∀t, f (t + T) = f (t) ; T is the period and u = 1/T is the frequency ; • a: amplitude ; ϕ: phase (ϕ = −2πus) ; s: shift NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Periodic functions Sum of sine waves NHSM - 4th year:
Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Periodic functions Decomposition of a T-periodic function • Harmonics =
sinusoidal waves with a frequency that is a positive integer multiple of the fundamental frequency of a periodic signal NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Periodic functions Decomposition of a T-periodic function Changing representation using
Fourier series NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Periodic functions Decomposition of a T-periodic function NHSM - 4th
year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Periodic functions Decomposition of a T-periodic function Image = weighted
sum of sine waves NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 5/28

Fourier series • Decomposition of a real T-periodic function into
harmonics. f (x) = a0 2 + +∞ n=1 an cos( 2π T nx) + bn sin( 2π T nx) an = 2 T T 2 − T 2 f (t) cos( 2π T nt) dt bn = 2 T T 2 − T 2 f (t) sin( 2π T nt) dt NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 6/28

Fourier series • Decomposition of a complex T-periodic function. f
(x) = +∞ n=−∞ cn ei 2π T nx , cn = 1 T T 2 − T 2 f (t)e−i 2π T nt dt. • Fourier bases: {ei 2π T nt, n ∈ Z} is an orthonormal basis of the Hilbert space L2([−π, π]), endowed with the scalar product ⟨f |g⟩ = 1 T T 2 − T 2 f (t)¯ g(t) dt. • Convergences: in L2 norm. Pointwise convergence? NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 6/28

Fourier series • In image processing (or in general) •
Functions (images) are not cyclic in general. • Little Use for Fourier Series. • Any L2 (or L1) function (even aperiodic) can be written as the integral of sine and cosine functions multiplied by coefficients. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 6/28

Fourier transform Direct and Inverse Fourier Transform • f ∈
L1(R): F(u) = +∞ −∞ f (x) e−i u x dx. F is bounded and continuous. • Inverse transform: If f , F ∈ L1(R): f (x) = 1 2π +∞ −∞ F(u) ei u x du. • Extension to L2(R) by density of L1(R) ∩ L2(R). FT generalizes FS to non-periodic functions → Continuous frequency spectrum. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 7/28

Fourier transform Direct and Inverse Fourier Transform • Example: f
= 1[−1,+1] ∈ L2(R) F(u) = +1 −1 e−i u t dt = 2 sin u u . F is not necessarily integrable. We cannot apply the inverse transform. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 7/28

Fourier transform Direct and Inverse Fourier Transform • Theorem (Convolution)
If f , h ∈ L1(R). Then, g = h ∗ f ∈ L1(R) and G(u) = H(u)F(u). • Theorem (Parseval and Plancherel) If f and h are two functions of L1(R) ∩ L2(R) ∞ −∞ f (t)¯ h(t) dt = 1 2π ∞ −∞ F(t)¯ H(t) dt ∞ −∞ |f (t)|2 dt = 1 2π ∞ −∞ |F(t)|2 dt NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 7/28

Fourier transform Direct and Inverse Fourier Transform • Properties NHSM
- 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 7/28

Fourier transform Direct and Inverse Fourier Transform • For f
∈ L1(R2): F(u1, u2 ) = +∞ −∞ +∞ −∞ f (x1, x2 ) e−i u x dx dy. • Inverse transform f , F ∈ L1(R2) f (x1, x2 ) = 1 4π2 +∞ −∞ +∞ −∞ F(u1, u2 ) ei u x du dv. • Parseval, Plancherel and Convolution. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 7/28

Discrete Fourier Transform (DFT) NHSM - 4th year: Digital Image
Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 8/28

Discrete Fourier Transform (1) • DFT (Discrete Fourier transform): f
∈ CN F(k) = N−1 n=0 f [n] exp −i 2π N kn , k ∈ {0, 1, ..., N − 1} • We can show that (Inverse transform): f (n) = 1 N N−1 k=0 F[k] exp i 2π N kn , n ∈ {0, 1, ..., N − 1} • Circular Convolution: f ∗ h[n] = N p=0 f [p]h[n − p] , n ∈ {0, 1, ..., N − 1} NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • DFT (Example for N =
4) • Coefficients of the matrix: F(m, n) = wmn, with w = e−j 2π N . NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • iDFT (Example for N =
4) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • The DFT is defined for
any length N. However, N is often assumed to be a power of 2 because efficient algorithms exist for these values. • If N is not a power of 2, the signal is padded with zeros. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • The family {ek [n] =
exp 2π N ikn , 0 ≤ k ≤ N} is an orthogonal basis of the space of N-periodic signals, endowed with the scalar product ⟨f , h⟩ = N−1 k=0 f [k]¯ h[k] • Parseval: ∥f ∥2= N−1 k=0 |f [k]|2 = 1 N N−1 k=0 |F[k]|2 • Convolution: If g = f ∗ h, then : G[k] = F[k]H[k] NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • Magnitude or spectrum (F =
R + iI): |F(u)|= R(u)2 + I(u)2 1/2 • Power spectrum, spectral density (Energy measurement): |F(u)|2= R(u)2 + I(u)2 • Angle or phase: Φ(u) = arctan( I(u) R(u) ) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) Examples NHSM - 4th year: Digital
Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • DFT in 2D (DFT2): F(u,
v) = M−1 x=0 N−1 y=0 f (x, y) e−i 2π(ux/M+vy/N) with u = 0, ..., M − 1; v = 0, ..., N − 1. • Inverse transform: f (x, y) = 1 MN M−1 u=0 N−1 v=0 F(u, v) ei 2π(ux/M+vy/N) with x = 0, ..., M − 1; y = 0, ..., N − 1. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • The centered format of the
2D Discrete Fourier Transform (DFT2), with N even: X(k, l) = M 2 −1 m=− M 2 N 2 −1 n=− N 2 x(m, n) e−i 2π(km/M+ln/N) with k = 0, ..., M − 1; l = 0, ..., N − 1. x(m, n) = 1 MN M 2 −1 k=− M 2 N 2 −1 l=− N 2 X(k, l) ei 2π(km/M+ln/N) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) Bases Bu,v (x, y) = 1
√ M √ N e2πj(ux N + vy M ), u = 1, ..., N − 1, v = 1, ..., M − 1 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • Each term of F(u, v)
is a function of ALL the values of f (x, y) weighted by the exponent. • The Fourier transform presents • Average at the origin (DC component) • Low frequencies • High frequencies NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • The DFT is conjugate symmetric
F(u, v) = F(−u, −v) • If f (x, y) is real |F(u, v)|= |F(−u, −v)| The spectrum is symmetric! • In many Fourier transforms, there are residual vertical and horizontal lines passing through the origin. They come from the edge effects of the discrete transform. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • Discrete Convolution f ∗ h(x,
y) = 1 MN M m=0 N n=0 f (m, n)h(x − m, y − n) • Correspondence between spatial and spectral filters. • Convolution and product for direct and inverse transforms. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • Properties of the DFT2 •
Linearity: ax1 (m, n) + bx2 (m, n) ↔ aX1 (k, l) + bX2 (k, l) • Periodicity x(m, n) = x(m + aM, n + bN), for all m, n X(k, l) = X(k + aM, l + bN), for all k, l • Circular Shift of the image x(m − m0, n − n0 ) ↔ X(k, l)e−j 2π N (km0+ln0) • Circular Shift of the spectrum x(m, n)ej 2π N (k0m+l0n) ↔ X(k − k0, l − l0 ) The centered spectrum is obtained pour odd N and k0 = l0 = N/2. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) • Properties of the DFT2 •
Circular convolution in the spatial domain x(m, n) ∗ h(m, n) ↔ X(k, l) H(k, l) y(m, n) = N−1 p=0 N−1 q=0 x(p, q)h(m − p, n − q), m, n = 0, 1, . . . , N − 1 • Circular convolution in the frequency domain x(m, n) h(m, n) ↔ 1 N2 N−1 p=0 N−1 q=0 X(p, q)H(m − p, n − q) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (1) Python code % Import libraries import
cv2 as cv import numpy as np % Read data im = cv.imread(’leopard.jpg’,0) % Compute the FFT of the image fft = np.fft.fft2(image) % Shift the zero frequency component to the center fft˙shifted = np.fft.fftshift(fft) % Compute the magnitude (spectrum) and phase magnitude˙spectrum = np.log(np.abs(fft˙shifted) + 1) # Add 1 to avoid log(0) phase˙spectrum = np.angle(fft˙shifted) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 9/28

Discrete Fourier Transform (2) Interpretation of the spectrum • Shifting
the zero frequency NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (2) Interpretation of the spectrum NHSM -
4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (2) Interpretation of the spectrum • A
small object in space has a large frequency extent and vice-versa. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (2) Interpretation of the spectrum • Interpretation
of the spectrum NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (2) Interpretation of the spectrum • The
Fourier Transform of an Edge NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (2) Interpretation of the spectrum • The
Fourier Transform of a bar NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 10/28

Discrete Fourier Transform (3) Examples NHSM - 4th year: Digital

Discrete Fourier Transform (3) Reconstruction NHSM - 4th year: Digital

Discrete Fourier Transform (3) Numerical examples • Calculate the DFT2,
iDFT2, DFT row-wise and then column-wise, DFT column-wise and then row-wise. We assume that the origin (0, 0) is at the top left corner. 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 , 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Calculate the DFT2
column-wise and then row-wise. 1 2 3 1 −2 3 1 4 1 1 2 2 3 1 2 4 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Calculate the 1D
DFT row-wise, column-wise, 2D DFT, and centered 2D DFT NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Example: DFT1 row-wise
• Example: DFT1 column-wise NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Example: DFT2 •
Example: centered DFT2 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Example: DFT2 -
magnitude NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Discrete Fourier Transform (3) Numerical examples • Example: DFT2 -
magnitude - logarithmic scale NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 11/28

Filtering in the frequency domain NHSM - 4th year: Digital

Filtering in the frequency domain (1) Convolution ≈ multiplication NHSM

Filtering in the frequency domain (1) Example: Laplacian Filter x(m,
n) = 1 −1 3 2 2 1 2 4 1 −1 2 −2 3 1 2 2 , h(m, n) = 0 −1 0 −1 5 −1 0 −1 0 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 13/28

Filtering in the frequency domain (1) Example: Laplacian Filter •
Border replication x = 1 −1 3 2 2 1 2 4 1 −1 2 −2 3 1 2 2 , X = 1 1 −1 3 2 2 0 0 1 1 −1 3 2 2 0 0 2 2 1 2 4 4 0 0 1 1 −1 2 −2 −2 0 0 3 3 1 2 2 2 0 0 3 3 1 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 13/28

Zero-padding h = 0 −1 0 −1 5 −1 0 −1 0 , H = 5 −1 0 0 0 0 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 0 0 0 0 0 0 0 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 13/28

Result y(m, n) = 2 −9 9 −1 5 3 0 14 0 −10 9 −16 7 0 3 6 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 13/28

Filtering in the frequency domain (2) Frequency domain filters •
Band-Stop Filtering (Notch Filtering): Remove specific frequencies or bands ; Often used to eliminate periodic noise. • Low-pass filters: Eliminate high frequencies ; Remove details. • High-pass filters: Eliminate low frequencies ; Preserve the outline of objects. • Band-Pass Filtering: Retain frequencies within a specific range (band) ; Remove frequencies outside this range. • Homomorphic Filtering: Enhances the contrast of an image by manipulating both high and low frequencies. • Unsharp Masking: To sharpen an image by subtracting a blurred version from the original. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 14/28

Filtering in the frequency domain (2) Band-Stop Filtering (Notch Filtering)
• Band-stop filtering removes frequencies within a specific range, often used to eliminate periodic noise or interference. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 15/28

• Remove the DC component: subtract the average intensity H(u, v) = 0 (u, v) = (0, 0) 1 Elsewhere • Emphasize the high-frequency components (edges and fine textures). • Sometimes, normalize the image for further processing steps. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 15/28

• Periodic noise NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 15/28

• Moir´ e Patterns: wavy lines (curves), grids, stripes, ripples, or repetitive patterns. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 15/28

• Moir´ e Patterns: wavy lines (curves), grids, stripes, ripples, or repetitive patterns. • Origins • Interference patterns created when two regular grids or patterns overlap. • Scanner Artifacts: Regular grid structures in scanners. • Optical Issues: Lens imperfections or optical filters. • Moir´ e patterns are periodic and can be removed using frequency domain techniques. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 15/28

Filtering in the frequency domain (2) Low-pass filter • Ideal
low-pass filter: Cuts off all high frequencies beyond a distance D0 (cutoff frequency) from the center. H(u, v) = 1 (u − u0 )2 + (v − v0 )2 < D0 0 Elsewhere NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

low-pass filter: Cuts off all high frequencies beyond a distance D0 (cutoff frequency) from the center. • Removes high-frequency components and retains low-frequency components → results in a blurred image, reducing detail and noise. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

low-pass filter: Cuts off all high frequencies beyond a distance D0 (cutoff frequency) from the center. H(u, v) = 1 (u − u0 )2 + (v − v0 )2 < D0 1/2 Elsewhere NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

low-pass filter: Reverberation phenomenon NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

Filtering in the frequency domain (2) Low-pass filter • Butterworth
low-pass filter: Gradually cuts off high frequencies based on the selection of D0 and the exponent n H(u, v) = 1 1 + Dist((u,v);(u0,v0)) D0 2n . NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

Filtering in the frequency domain (2) Low-pass filter • Butterworth
low-pass filter: Gradually cuts off high frequencies based on the selection of D0 and the exponent n NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

Filtering in the frequency domain (2) Low-pass filter • Gaussian
low-pass filter: Gradually cuts off high frequencies based on the selection of D0 H(u, v) = e − D(u,v)2 2D2 0 . NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

Filtering in the frequency domain (2) Low-pass filter • Gaussian
low-pass filter: Gradually cuts off high frequencies based on the selection of D0 H(u, v) = e − D(u,v)2 2D2 0 . • Less aggressive than the ideal filter or Butterworth filter. • Less control over the precise selection of D0 . • But provides protection against reverberation! • Matches the human model. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 16/28

Filtering in the frequency domain (2) High-pass filter • Exactly
the opposite function of low-pass filters Hph = 1 − Hpb • Ideal, Butterworth, Gaussian NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 17/28

the opposite function of low-pass filters Hph = 1 − Hpb • Ideal, Butterworth, Gaussian • Ideal High-pass 0 — 1 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 17/28

the opposite function of low-pass filters Hph = 1 − Hpb • Ideal, Butterworth, Gaussian • Ideal High-pass 1/2 — 1 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 17/28

the opposite function of low-pass filters Hph = 1 − Hpb • Ideal, Butterworth, Gaussian • Gaussian High-pass NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 17/28

Filtering in the frequency domain (2) Band-pass filter Retain frequencies
within a specific range and remove those outside this range (useful for isolating certain details or patterns). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 18/28

Filtering in the frequency domain (2) Homomorphic filter Enhance the
contrast of an image by modifying both high and low frequencies (useful for dynamic range compression and contrast enhancement). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 19/28

Filtering in the frequency domain (2) Homomorphic filter 1. Take
the logarithm of the image. 2. Apply a high-pass filter to attenuate low-frequency components and boost high-frequency components. H(u, v) = (γH − γL ) · 1 − e−c·((u−u0)2+(v−v0)2) + γL where γH, γL : Gain for high frequencies (reflectance) and low frequencies (illumination), c controls the filter’s sharpness, 3. Take the inverse Fourier transform and exponentiate the result. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 19/28

Filtering in the frequency domain (2) Homomorphic filter • ⇝
A gradual change in illumination in the left image (original) has been corrected in the image on the right (filtered image). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 19/28

Filtering in the frequency domain (2) Homomorphic filter • Enhancing
images with uneven lighting, • Improving contrast in images with shadows or bright areas, • Biomedical image enhancement, particularly for visualizing tissue details in medical scans. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 19/28

Filtering in the frequency domain (2) Spectral filtering – Image
sharpening • Image sharpening = Re-enforce edges • How: Keep low frequencies + Amplify high frequencies • y = x + αDx, D: derivative filter, α > 0 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 20/28

Filtering in the frequency domain (2) Spectral filtering – Image
sharpening • Drawback: Amplify noise NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 20/28

Sampling, FT and Shannon theorem NHSM - 4th year: Digital

Sampling and FT Aliasing • Original image NHSM - 4th
year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Aliasing • Sampled image: Aliasing effect NHSM

Sampling and FT Aliasing • Sampling a signal: Aliasing effect
• Undersampling a signal: different frequencies. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Sampling and reconstruction NHSM - 4th year:

Sampling and FT Sampling and reconstruction ˆ fd (w) =
∞ n=−∞ f (ns)e−insw fd (t) = ∞ n=−∞ f (ns)δ(t − ns) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Sampling and reconstruction ˆ fd (w) =
∞ n=−∞ f (ns)e−insw fd (t) = ∞ n=−∞ f (ns)δ(t − ns) ˆ fd (w) = 1 s ∞ k=−∞ ˆ f (w − 2kπ s ) NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Sampling and reconstruction • Shannon Sampling Theorem:
If Supp(ˆ f ) = −π s , π s , then: f (t) = ∞ n=−∞ f (ns)Φs (t − ns), Φs (t) = sin(πt/s) πt/s . NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Statement of Shannon’s Theorem A band-limited continuous
signal can be completely represented by its samples and fully reconstructed if it is sampled at a rate greater than twice its highest frequency: fs > 2fmax where: • fs is the sampling frequency. • fmax is the maximum frequency of the signal. This rate is known as the Nyquist Rate. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Shannon’s Theorem and Aliasing • Sampling below
the Nyquist rate leads to aliasing. • Correct sampling ensures that the original signal can be perfectly reconstructed from its samples. • Anti-Aliasing Techniques • Technique 1: • Technique 2: NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

the Nyquist rate leads to aliasing. • Correct sampling ensures that the original signal can be perfectly reconstructed from its samples. • Anti-Aliasing Techniques • Technique 1: Higher Sampling Rates: Ensuring sampling is above the Nyquist rate. • Technique 2: NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

the Nyquist rate leads to aliasing. • Correct sampling ensures that the original signal can be perfectly reconstructed from its samples. • Anti-Aliasing Techniques • Technique 1: Higher Sampling Rates: Ensuring sampling is above the Nyquist rate. • Technique 2: Filtering: Applying a low-pass filter before sampling to remove high-frequency components. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Sampling and FT Anti-Aliasing filter Input Reconst. without AA Reconst.
with AA NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 22/28

Other transforms NHSM - 4th year: Digital Image Processing -
Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 23/28

Discrete Cosine Transform (DCT) What is DCT? • The Discrete
Cosine Transform (DCT) transforms a signal or image from the spatial domain to the frequency domain. • The DCT is similar to the Fourier Transform, but it uses only cosine functions and is real function, making it more efficient for image compression. • DCT is widely used in image processing, especially in compression techniques like JPEG, due to its ability to concentrate energy in the lower frequencies. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) Formulas • 1D DCT formula for
a sequence x[n] of length N: X[k] = α(k) N−1 n=0 x[n] cos π N n + 1 2 k , k = 0, 1, . . . , N − 1 α(k) =    1 N for k = 0 2 N for k = 1, 2, . . . , N − 1 • Inverse 1D DCT x[n] = N−1 k=0 α(k)X[k] cos π N n + 1 2 k , n = 0, 1, . . . , N − 1. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) Formulas • The 2D DCT of
an M × N image x[m, n] X[k, l] = α(k)β(l) M−1 m=0 N−1 n=0 x[m, n] cos π M m + 1 2 k cos π N n + 1 2 l where k = 0, . . . , M − 1, l = 0, . . . , N − 1, and the normalization factors: α(k) =    1 M for k = 0 2 M for k = 1, . . . , M − 1 , β(l) =    1 N for l = 0 2 N for l = 1, . . . , N − 1 • The 2D DCT of an (8 × 8) image x[m, n] X(k, l) = 1 4 7 m=0 7 n=0 x(m, n) · cos (2m + 1)kπ 16 · cos (2n + 1)lπ 16 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) Formulas • Inverse 2D DCT x[m,
n] = M−1 k=0 N−1 l=0 α(k)α(l)X[k, l] cos π M m + 1 2 k cos π N n + 1 2 l where m = 0, 1, . . . , M − 1 and n = 0, 1, . . . , N − 1. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) DCT basis • DCT basis are
cosine functions that represent different frequencies. • Low-frequency components (coarse features) and high-frequency components (fine details). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) DCT and Image Compression • After
transformation to the frequency domain, most of the energy is concentrated in the lower frequencies. • The high-frequency components, which correspond to small details, can be quantized more coarsely or discarded, leading to compression. • A simple compression method: apply a threshold on the DCT coefficients. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Discrete Cosine Transform (DCT) DCT and Image Compression • DCT
compression: Apply a threshold on the DCT coefficients Original (154401 coeffs.) DCT (5214 coeffs.) Compressed 3.38% NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

compression: Apply a threshold on the DCT coefficients Compression rate: 3.38% NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

compression: Apply a threshold on the DCT coefficients Compression rate: 20% NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

in JPEG Compression 1. Convert the image to the YCbCr color space. 2. Split the image into 8 × 8 blocks. 3. Apply the 2D DCT to each block. 4. Quantize the DCT coefficients. 5. Encode the quantized coefficients using entropy coding. →Chapter 4 NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 24/28

Wavelets What are Wavelets? • A wavelet is a small
wave, localized in time • Decompose data into different frequency components. • Unlike Fourier transform, which uses sinusoids, wavelet transform uses functions that are localized in both time and frequency. • Effective for analyzing non-stationary signals and images. • Wavelets provide a multi-resolution analysis of images. • Many applications: compression (like JPEG 2000), denoising, feature extraction and texture analysis. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 25/28

Wavelet Transforms Continuous Wavelet Transforms • 1D Continuous Wavelet Transform
(CWT) Wx (a, b) = ∞ −∞ x(t) 1 |a| ψ t − b a dt where a, b represent scaling and translation and ψ is a wavelet mother satisfying +∞ −∞ ψ(t)dt = 0, ||ψ||= 1. • {ψa,b (t) = 1 √ |a| ψ t−b a }a,b is a dictionary (overcomplete and redundant). Reconstruction, Bases? CWT = a magnifying glass. You adjust the scale to zoom in on specific parts of the signal, and you translate to examine different time instances. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

Wavelet Transforms Continuous Wavelet Transforms • 1D Continuous Wavelet Transform
(CWT) Wx (a, b) = ∞ −∞ x(t) 1 |a| ψ t − b a dt CWT: Uses the mother wavelet to analyze the signal continuously across different scales and positions. • Examples • Haar Wavelet • Daubechies Wavelet • Symlets • Coiflets • ... NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

Wavelet Transforms Discrete Wavelet Transforms (DWT) • 1D Wavelet Transform:
decomposes a signal into approximation and detail coefficients. A1 [n] = k x[k] · g[2n − k], D1 [n] = k x[k] · h[2n − k] • g[n] is the low-pass filter, producing the approximation coefficients. • h[n] is the high-pass filter, producing the detail coefficients. • The subsampling by 2 (represented by 2n) reduces the resolution, capturing the signal at a coarser level. DWT: Uses both the mother wavelet (for details) and the father wavelet (for approximations) to decompose and reconstruct the signal in a multi-resolution framework. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

Wavelet Transforms Discrete Wavelet Transforms (DWT) • Multiresolution Analysis (MRA)
NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

applied separately to the rows and the columns. • LL: Low-pass filtering in both dimensions, capturing the approximation. • LH: Low-pass filtering along the rows and high-pass filtering along the columns, capturing horizontal details. • HL: High-pass filtering along the rows and low-pass filtering along the columns, capturing vertical details. • HH: High-pass filtering in both dimensions, capturing diagonal details. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

applied separately to the rows and the columns. LL = M−1 x=0 N−1 y=0 f (x, y) · g(2x − u) · g(2y − v) LH = M−1 x=0 N−1 y=0 f (x, y) · g(2x − u) · h(2y − v) HL = M−1 x=0 N−1 y=0 f (x, y) · h(2x − u) · g(2y − v) HH = M−1 x=0 N−1 y=0 f (x, y) · h(2x − u) · h(2y − v) • g and h are the low and high-pass filters, respectively. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

Wavelet Transforms Discrete Wavelet Transforms (DWT) NHSM - 4th year:

Wavelet Transforms Discrete Wavelet Transforms (DWT) • Haar Wavelet •
Simplest wavelet, piecewise constant. • Scaling function (father wavelet) and wavelet function (mother wavelet) defined as: ϕ(t) = 1 0 ≤ t < 1, 0 otherwise. ; ψ(t) =      1 0 ≤ t < 0.5, −1 0.5 ≤ t < 1, 0 otherwise. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 26/28

Wavelets applications Image Compression • Wavelet transform is used in
image compression standards like JPEG 2000. • It provides a multi-resolution representation, allowing for progressive transmission and high compression ratios. • Simple method 1. Decompose the image using the Discrete Wavelet Transform (DWT). 2. Threshold the coefficients, keeping only the significant ones. 3. Reconstruct the compressed image using the Inverse Discrete Wavelet Transform (IDWT). NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 27/28

Wavelets applications Image Denoising with Wavelets 1. Decompose the noisy
signal using the DWT. 2. Threshold the detail coefficients to remove the noise. • Hard thresholding sets coefficients below the threshold to zero. • Soft thresholding reduces coefficients by the threshold value. 3. Reconstruct the denoised signal using the IDWT. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 27/28

Wavelets applications Edge Detection using Wavelets • Wavelet transform can
be used to detect edges in images. • The high-pass components (LH, HL, HH) contain the edge information. • By analyzing these components, we can detect edges at multiple scales. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 27/28

Assignment 3 Write a python code that depends on the
OpenCV library and that performs all the methods of this lecture: 1. Fourier transform: illustrate the properties of the FT. 2. DFT and DFT2 and their inverses: compute and visualize some examples. 3. Illustrate the reconstruction from DFT and DFT2. 4. Frequency domain filters and their applications. 5. Sampling and FT: illustrate the aliasing, use of anti-aliasing filter. 6. DCT1 and DCT2 and application to denoising and compression. 7. DWT1 and DWT2 and application to denoising, compression and edge detection. Simulations should be conducted to evaluate (qualitative and quantitative) and compare the methods with various parameters. NHSM - 4th year: Digital Image Processing - Frequency Processing (Week 4,5) - M. Hachama ([email protected]) 28/28

Introduction to Image Processing: 2.Frequ

Introduction to Image Processing: 2.Frequ

More Decks by Mohammed Hachama

Other Decks in Science

Featured

Transcript