BSc CSIT (TU) Science Image Processing (BSc CSIT, CSC413) Question Paper 2075 Nepal

Fourier Transform in Digital Image Processing

Definition

The Fourier Transform (FT) decomposes an image (a spatial-domain signal) into its constituent sinusoidal frequency components. It maps an image from the spatial domain $f(x,y)$ to the frequency domain $F(u,v)$.

For a digital image of size $M \times N$, the 2-D Discrete Fourier Transform (DFT) is:

and the inverse DFT is:

Each value $F(u,v)$ is complex: $F(u,v)=R(u,v)+jI(u,v)$, giving a magnitude (spectrum) $|F(u,v)|=\sqrt{R^2+I^2}$ and a phase $\phi(u,v)=\tan^{-1}(I/R)$.

Applications in Image Processing

• Frequency-domain filtering — low-pass (smoothing/blurring), high-pass (sharpening), band-pass and notch filtering.
• Image enhancement by suppressing/boosting selected frequencies.
• Image restoration — inverse and Wiener filtering for deblurring.
• Image compression (basis for transform coding; DCT used in JPEG).
• Texture analysis and pattern recognition via the spectrum.
• Fast convolution — convolution in spatial domain becomes multiplication in frequency domain.

Important Properties (with derivations)

1. Separability. The 2-D DFT separates into two successive 1-D DFTs (rows then columns):

This reduces computation from $O((MN)^2)$ to $O(MN(M+N))$, and allows the FFT.

2. Linearity. $\mathcal{F}\{af_1+bf_2\}=aF_1+bF_2$, directly from the linearity of the summation.

3. Translation (shift). Shifting in space introduces a phase factor:

and multiplying in space by an exponential shifts the spectrum. Setting $u_0=M/2, v_0=N/2$ gives $f(x,y)(-1)^{x+y}\leftrightarrow F(u-M/2,v-N/2)$, used to center the spectrum.

4. Periodicity. The DFT and IDFT are periodic with periods $M$ and $N$: $F(u,v)=F(u+M,v)=F(u,v+N)$, since $e^{-j2\pi(u+M)x/M}=e^{-j2\pi ux/M}$.

5. Conjugate symmetry. For real $f(x,y)$: $F(u,v)=F^*(-u,-v)$, hence $|F(u,v)|$ is symmetric about the origin.

6. Rotation. Rotating the image by an angle $\theta_0$ rotates its spectrum by the same angle (shown using polar coordinates $x=r\cos\theta,\,u=\omega\cos\varphi$).

7. Convolution theorem. $f(x,y)*h(x,y)\;\Longleftrightarrow\;F(u,v)H(u,v)$. Proof sketch: take the DFT of the convolution sum and apply the shift property to obtain the product of transforms. This is the foundation of frequency-domain filtering.

8. Average value. $F(0,0)=\sum_x\sum_y f(x,y)=MN\,\bar f$, i.e. the DC term equals the average intensity scaled by $MN$.

Spatial Filtering

Spatial filtering processes an image directly on its pixels by moving a small mask (kernel/window) over the image and replacing each pixel with a function of its neighbourhood. For a linear filter this is correlation/convolution:

where $w(s,t)$ are the mask coefficients. The behaviour depends entirely on the mask.

1. Low-Pass (Smoothing) Filtering

Passes low frequencies, attenuates high frequencies → blurs / smooths the image and reduces noise. All coefficients are positive and the mask sums to 1 (averaging). A $3\times3$ averaging mask:

Effect: removes fine detail and noise but blurs edges; useful before downsampling or for noise reduction.

2. High-Pass (Sharpening) Filtering

Passes high frequencies (edges, detail), attenuates low frequencies → sharpens / enhances edges. The mask has a positive centre, negative surround, and coefficients sum to 0:

Effect: highlights edges and fine detail; flat regions become near zero. Adding the high-pass result back to the original gives high-boost / unsharp masking.

3. Band-Pass Filtering

Passes a range (band) of frequencies between two cut-offs while attenuating both very low and very high frequencies. It is obtained as the difference of two low-pass filters (e.g. Difference of Gaussians):

Effect: retains features of a specific scale/size while removing slowly varying background and high-frequency noise; used in texture analysis and feature/blob detection.

Summary Table

Image Compression

Image compression reduces the number of bits required to represent an image by removing redundancy, lowering storage and transmission cost.

Types of redundancy: coding redundancy (inefficient code words), spatial/inter-pixel redundancy (neighbouring pixels are correlated), and psychovisual redundancy (information the human eye cannot perceive).

Categories: Lossless (e.g. RLE, Huffman, LZW — exact reconstruction) and Lossy (e.g. JPEG — higher compression with acceptable quality loss).

JPEG Compression Algorithm (step by step)

JPEG is a lossy, transform-based scheme operating on $8\times8$ blocks.

1. Colour transform & sub-sampling. Convert RGB → YCbCr. Because the eye is less sensitive to colour, the chrominance channels (Cb, Cr) are typically sub-sampled (e.g. 4:2:0).

2. Block partition. Divide each component into non-overlapping $8\times8$ blocks.

3. Level shift & 2-D DCT. Subtract 128 from each pixel, then apply the Forward Discrete Cosine Transform to each block:

with $C(0)=1/\sqrt2$, otherwise $1$. This concentrates energy in low-frequency coefficients (top-left, DC term).

4. Quantization (lossy step). Divide each DCT coefficient by a value from a quantization table $Q$ and round:

High-frequency coefficients (large $Q$ values) become zero — this is where compression and quality loss occur. A quality factor scales $Q$.

5. Zig-zag scanning. Read the $8\times8$ block in a zig-zag order to group the (now mostly zero) high-frequency coefficients into long runs of zeros, producing a 1-D sequence.

6. Entropy coding.

• DC coefficient: coded as the difference (DPCM) from the previous block's DC.
• AC coefficients: run-length encoded (run of zeros, value) then Huffman (or arithmetic) coded.

The result is the compressed bit-stream. Decompression reverses these steps: entropy decode → de-zig-zag → de-quantize ($F\approx F_q\cdot Q$) → inverse DCT → level shift → YCbCr→RGB.

Diagram (in words)

Input → Color/sub-sample → 8×8 blocks → DCT → Quantize → Zig-zag → RLE + Huffman → Bit-stream.

Relationship Between Pixels: Neighbours and Connectivity

Neighbours of a pixel $p$ at $(x,y)$:

• 4-neighbours $N_4(p)$: the 4 horizontal/vertical pixels $(x\pm1,y),(x,y\pm1)$.
• Diagonal neighbours $N_D(p)$: the 4 diagonal pixels $(x\pm1,y\pm1)$.
• 8-neighbours $N_8(p)=N_4(p)\cup N_D(p)$: all 8 surrounding pixels.

Connectivity decides whether two pixels belong to the same object. Let $V$ be the set of intensity values defining connectivity (e.g. $V=\{1\}$ for a binary image). Two pixels $p,q$ (with values in $V$) are:

• 4-connected: if $q\in N_4(p)$.
• 8-connected: if $q\in N_8(p)$.
• m-connected (mixed): if $q\in N_4(p)$, or $q\in N_D(p)$ and $N_4(p)\cap N_4(q)$ contains no pixel from $V$. Mixed connectivity removes the ambiguous multiple paths that arise with 8-connectivity.

Connectivity leads to paths, connected components, regions, and boundaries, and is fundamental to labelling and segmentation.

Contrast Stretching

Contrast stretching (normalization) is a point (intensity-transformation) enhancement technique that expands the range of intensity levels in a low-contrast image so that it spans the full available range (e.g. $0$–$255$), making the image clearer.

For an input intensity $r$ with minimum $r_{min}$ and maximum $r_{max}$, the linear stretch maps it to $[0,L-1]$:

A more general piecewise-linear transformation uses two control points $(r_1,s_1)$ and $(r_2,s_2)$ to control the slope: a steep slope between $r_1$ and $r_2$ increases contrast in that band, while the ends may be clipped.

Special cases:

• If $r_1=r_2$, $s_1=0$, $s_2=L-1$ at a threshold $\Rightarrow$ thresholding (binary image).
• A gentle S-shaped curve brightens mid-tones.

Effect: a dull, low-contrast image (histogram concentrated in a narrow band) becomes one whose histogram is spread across the full range, improving visual detail. Unlike histogram equalization, the mapping here is user-specified/linear rather than derived from the histogram.

Histogram Specification (Matching)

Histogram specification (matching) is an enhancement technique that transforms an input image so that its histogram matches a specified (target) histogram, rather than the uniform histogram produced by histogram equalization. It gives control to emphasise particular intensity ranges.

Procedure

Let $r$ be input intensities with PDF $p_r(r)$ and $z$ the desired output intensities with target PDF $p_z(z)$.

1. Equalize the input image: $\;s=T(r)=(L-1)\displaystyle\int_0^r p_r(w)\,dw$ (CDF of input).

2. Compute the equalizing transform of the target: $\;G(z)=(L-1)\displaystyle\int_0^z p_z(w)\,dw$ (CDF of target), with $G(z)=s$.

3. Map: $\;z=G^{-1}(s)=G^{-1}\!\big(T(r)\big)$.

Discrete steps

1. Compute the CDF $s_k$ of the input histogram.
2. Compute the CDF $G(z_q)$ of the specified histogram.
3. For each input level $r_k$, find the level $z_q$ whose $G(z_q)$ is closest to $s_k$, and map $r_k\to z_q$.

Use: when histogram equalization over-enhances or when matching one image's tonal distribution to a reference image is required.

Mean Filter vs Median Filter

Both are spatial smoothing filters applied over a neighbourhood (e.g. $3\times3$), but they differ in operation and behaviour.

Example (3×3 window, salt-pepper): values $\{12,15,255,14,16,13,11,0,17\}$ → mean $\approx 39.2$ (corrupted), median $= 14$ (correct). This shows the median's robustness to impulse noise.

Discrete Cosine Transform (DCT)

The DCT is a real-valued orthogonal transform that expresses a signal/image as a sum of cosine basis functions of different frequencies. Unlike the DFT it uses only cosines (no imaginary part), and it has strong energy compaction — most of the signal energy is packed into a few low-frequency coefficients — which makes it ideal for compression (used in JPEG and MPEG).

1-D DCT

where $\alpha(0)=\sqrt{1/N}$ and $\alpha(u)=\sqrt{2/N}$ for $u>0$.

2-D DCT (for images)

Properties / uses

• Real and orthogonal, separable, invertible.
• Energy compaction → excellent for transform coding/compression.
• The $C(0,0)$ term is the DC (average) coefficient.
• Reduces blocking and gives near-optimal decorrelation for highly correlated images, approaching the Karhunen–Loève transform.

Laplacian Operator for Edge Detection

The Laplacian is a second-order derivative operator used to detect edges. It is isotropic (rotation-invariant) and responds to intensity transitions (edges) as zero-crossings, where the second derivative changes sign.

For an image $f(x,y)$:

Using finite differences the discrete form is:

Common masks

Characteristics

• Produces double edges and detects edges via zero-crossings, giving precise localisation.
• It is very sensitive to noise (because it differentiates twice), so the image is usually smoothed first, e.g. the Laplacian of Gaussian (LoG / Marr–Hildreth) operator.
• Gives no edge direction information (unlike gradient operators).
• For sharpening: $\;g=f-\nabla^2 f\;$ (subtract when centre coefficient is negative) enhances edges.

Erosion vs Dilation

Both are fundamental morphological operations using a structuring element (SE) $B$ on a (usually binary) image set $A$.

Dilation $A\oplus B$

Grows / thickens objects:

The SE is placed at each pixel; output is 1 if the SE overlaps any foreground pixel. Effects: enlarges objects, fills small holes and gaps, connects nearby components.

Erosion $A\ominus B$

Shrinks / thins objects:

Output is 1 only if the SE fits completely within the foreground. Effects: shrinks objects, removes small isolated specks and thin protrusions, breaks thin bridges.

Comparison

Note: erosion and dilation are duals with respect to complementation and reflection. Combining them gives opening (erosion then dilation) and closing (dilation then erosion).

Image Degradation Model

The image degradation/restoration model describes how an original (true) image $f(x,y)$ is corrupted to produce the observed degraded image $g(x,y)$, so that restoration can recover an estimate $\hat f$.

The degradation is modelled as a degradation function $H$ (e.g. blur, motion, optical system) acting on $f$, followed by additive noise $\eta(x,y)$.

Spatial domain

where $*$ is convolution and $h$ is the point spread function (PSF) of the degradation.

Frequency domain

Using the convolution theorem:

Restoration applies the inverse/Wiener filter to $G$ using a knowledge or estimate of $H$ and the noise statistics to obtain $\hat F(u,v)$, and hence $\hat f(x,y)$ via the inverse transform.

Block diagram (in words)

f(x,y) → [Degradation H] →(+ noise η)→ g(x,y) → [Restoration filter] → f̂(x,y)

Hadamard Transform — Short Notes

The Hadamard (Walsh–Hadamard) transform is a real, orthogonal image transform whose basis functions take only values +1 and −1 (rectangular/square waves) instead of sinusoids. This makes it computationally very cheap — it needs only additions and subtractions, no multiplications.

Hadamard matrix

The matrix is built recursively (Sylvester construction). The smallest is

It is symmetric and orthogonal: $H_N H_N^{T}=I$, so the inverse equals the (scaled) transpose.

2-D transform

For an $N\times N$ image $f$:

Properties / uses

• Real, orthogonal, separable, energy-compacting (less than DCT).
• The number of sign changes per row is the sequency (analogous to frequency).
• Used in image compression, coding, feature extraction, and fast computation where speed matters more than optimal compaction.