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

Fourier Transform in Digital Image Processing

The Fourier Transform (FT) converts an image from the spatial domain $f(x,y)$ into the frequency domain $F(u,v)$, representing the image as a sum of sinusoids of different frequencies, amplitudes and phases. Low frequencies correspond to slowly varying intensities (smooth regions/background) and high frequencies correspond to rapid changes (edges, noise, fine detail).

The 2-D Discrete Fourier Transform (DFT) of an $M \times N$ image is:

and its inverse:

Applications

• Frequency-domain filtering: low-pass (smoothing/noise removal), high-pass (sharpening/edge enhancement), band-reject (removing periodic noise).
• Image restoration via inverse and Wiener filtering of degradation/blur.
• Image compression (energy compaction into few frequency coefficients, basis of DCT/JPEG).
• Fast convolution using the convolution theorem ($f*h \Leftrightarrow F\cdot H$).
• Texture and pattern analysis, periodic-noise detection.

Properties of the 2-D DFT

1. Separability. The 2-D transform separates into two 1-D transforms (rows then columns):

This allows computing the 2-D DFT by successive 1-D DFTs, greatly reducing computation (and enables use of the FFT).

2. Translation (shifting). A spatial shift only adds a phase, leaving the magnitude unchanged:

Multiplying the image by $(-1)^{x+y}$ shifts the spectrum so that the origin (DC term) moves to the centre $(M/2,N/2)$ — used for display and centering of the spectrum.

3. Periodicity. Both $F(u,v)$ and the implied $f(x,y)$ are periodic with periods $M$ and $N$:

Hence the DFT describes one period of an infinite periodic function; this is why centering and proper windowing matter.

4. Symmetry / conjugate symmetry. For a real image $f(x,y)$:

The magnitude spectrum is symmetric about the origin, so only half the spectrum need be stored/computed.

Conclusion

The Fourier transform is fundamental to frequency-domain image processing; its separability makes computation efficient, while translation, periodicity and symmetry properties govern how filters are designed, how the spectrum is centered for display, and how storage is reduced.

Image Segmentation

Image segmentation is the process of partitioning a digital image into multiple meaningful, non-overlapping regions (sets of pixels) such that pixels within a region are similar with respect to some property (intensity, colour, texture) while adjacent regions differ. It is a key step that bridges low-level processing and high-level analysis (object detection, recognition). Two broad approaches are discontinuity-based (edges) and similarity-based (thresholding, region growing, split-and-merge).

Adaptive (Local) Thresholding

A single global threshold $T$ classifies a pixel as object or background:

Global thresholding fails when illumination is non-uniform, because one $T$ cannot suit the whole image.

In adaptive thresholding the threshold $T(x,y)$ varies with position, computed from a local neighbourhood around each pixel (e.g. local mean or median minus a constant $C$, or Otsu applied per sub-block):

where $W$ is a window centred at $(x,y)$.

Example. A document scanned with a shadow on one side: a global $T$ would turn the dark side fully black, but adaptive thresholding using a local mean correctly separates text from background across both bright and shaded areas.

Region Split-and-Merge

This is a region-based technique using a quadtree representation. A predicate $P(R)$ tests homogeneity of region $R$ (e.g. variance below a limit, or $\max-\min$ intensity $\le$ threshold).

Algorithm:

1. Split: Start with the whole image as one region $R$. If $P(R)$ is FALSE (region not homogeneous), split $R$ into four equal quadrants. Repeat recursively for each quadrant until every region satisfies $P$.
2. Merge: Merge any two adjacent regions $R_i, R_j$ for which $P(R_i \cup R_j)$ is TRUE.
3. Stop when no further split or merge is possible.

Example. For an image with a uniform object on a uniform background, splitting recursively divides mixed blocks straddling the boundary into smaller homogeneous blocks (forming a quadtree); merging then groups all object blocks into one region and all background blocks into another, giving two final segments.

Comparison

• Adaptive thresholding handles uneven illumination but ignores spatial connectivity.
• Split-and-merge guarantees connected, homogeneous regions but is sensitive to the homogeneity predicate and can produce blocky boundaries.

Butterworth High-Pass Filter (BHPF) for Image Sharpening

Image sharpening highlights fine detail and edges, which correspond to high spatial frequencies. A high-pass filter passes high frequencies and attenuates low frequencies (smooth background). Sharpening in the frequency domain follows:

where $F$ is the DFT of the image and $H$ the filter transfer function; the result is obtained by inverse DFT.

An ideal HPF has a sharp cutoff and produces ringing artifacts. The Butterworth filter gives a smooth, gradual transition, reducing ringing.

Transfer Function (Derivation)

The Butterworth low-pass filter (BLPF) of order $n$ with cutoff $D_0$ is:

where $D(u,v)=\sqrt{(u-M/2)^2+(v-N/2)^2}$ is the distance from the centre of the (centered) frequency rectangle.

A high-pass filter is the complement of the corresponding low-pass filter:

Substituting:

Multiplying numerator and denominator by $\left[D_0/D(u,v)\right]^{2n}$ gives the standard BHPF form:

Effect / Behaviour

• At $D(u,v)=D_0$, $H=0.5$ (the half-power cutoff), regardless of order $n$.
• For $D \ll D_0$ (low frequencies, near centre) $H \to 0$ → background/smooth areas are suppressed.
• For $D \gg D_0$ (high frequencies) $H \to 1$ → edges and fine detail are passed → sharpening.
• The order $n$ controls steepness: small $n$ gives a gentle transition (smooth result, almost no ringing); large $n$ approaches the ideal HPF (sharper cutoff, more ringing).
• Because the DC term is removed/attenuated, the output has near-zero average and edges appear on a dark background; adding a constant (high-frequency-emphasis filtering, $H'=a+bH$) restores overall brightness while keeping the sharpening.

Conclusion

The BHPF sharpens images by amplifying high-frequency edge content while smoothly attenuating low frequencies, offering a controllable trade-off (via $n$) between sharpness and ringing that the ideal HPF cannot provide.

Histogram of an Image

The histogram of a digital image is a discrete function that represents the frequency of occurrence of each intensity (gray) level. For an image with intensity levels $r_k$ ($k=0,1,\dots,L-1$):

where $n_k$ is the number of pixels having intensity $r_k$. The normalized histogram $p(r_k)=n_k/MN$ (with $MN$ = total pixels) gives the probability of each gray level. Plotted as gray level (x-axis) vs. count/probability (y-axis), it summarizes the tonal distribution but contains no spatial information.

Uses

• Brightness/contrast assessment: a histogram clustered at low values = dark image; at high values = bright image; spread over the full range = high contrast.
• Histogram equalization / stretching to enhance contrast.
• Histogram matching (specification) to give an image a desired tonal distribution.
• Thresholding/segmentation: a bimodal histogram suggests a good threshold between object and background.
• Image analysis & comparison (texture, exposure correction, content-based retrieval).

Types of Filters in Image Processing

Filters modify pixel values using a neighbourhood (spatial domain) or frequency components (frequency domain). Main types:

By domain

• Spatial-domain filters – operate directly on pixels via convolution with a mask/kernel.
• Frequency-domain filters – multiply the image's Fourier transform by a transfer function $H(u,v)$.

By effect / pass-band

• Low-pass (smoothing) filters – attenuate high frequencies → blur, noise removal. Examples: averaging/mean filter, Gaussian filter, ideal/Butterworth LPF.
• High-pass (sharpening) filters – attenuate low frequencies, pass high → enhance edges/detail. Examples: Laplacian, ideal/Butterworth HPF, high-boost.
• Band-pass / band-reject filters – pass or remove a range of frequencies, e.g. notch filter to remove periodic noise.

By linearity

• Linear filters – output is a weighted (convolution) sum, e.g. mean, Gaussian, Laplacian.
• Non-linear filters – order/rank based, e.g. median filter (excellent for salt-and-pepper noise), max/min filters.

By purpose

• Smoothing (noise reduction), sharpening (edge enhancement), edge-detection (Sobel, Prewitt, Laplacian), and restoration (Wiener) filters.

Smoothing vs. Sharpening

Summary: Smoothing is a low-pass / averaging operation that suppresses rapid intensity changes (noise, detail), whereas sharpening is a high-pass / differencing operation that amplifies them to make edges crisper. They are conceptually opposite: smoothing integrates, sharpening differentiates.

Image Negatives

An image negative is a point (intensity) transformation that reverses the intensity levels of an image, so that dark areas become light and light areas become dark — like a photographic negative. For an image with intensity range $[0, L-1]$, the transformation is:

where $r$ is the input intensity and $s$ the output. For an 8-bit image ($L=256$), $s = 255 - r$ (e.g. $0\to255$, $255\to0$, $100\to155$).

It is a linear, reversible transformation with a transformation curve that is a straight line of slope $-1$.

Applications

• Medical imaging: enhancing white/gray detail embedded in dark regions, e.g. examining tissue in X-rays / mammograms, where small bright structures are easier to see against a dark inverted background.
• Bringing out detail in the dark regions of an image where the eye perceives differences better after inversion.
• A pre-processing step in some enhancement and analysis pipelines, and for producing photographic-style negative effects.

Discrete Fourier Transform (DFT)

The Discrete Fourier Transform transforms a finite, discrete (sampled) signal/image from the spatial domain to the frequency domain, expressing it as a sum of complex sinusoids. It is the discrete, computable counterpart of the continuous Fourier transform.

1-D DFT of a sequence $f(x)$, $x=0,\dots,N-1$:

Inverse: $\displaystyle f(x)=\frac{1}{N}\sum_{u=0}^{N-1}F(u)\,e^{+j2\pi ux/N}$.

2-D DFT of an $M\times N$ image $f(x,y)$:

$F(u,v)$ is generally complex; its magnitude $|F(u,v)|$ is the frequency spectrum and $\arctan(\text{Im}/\text{Re})$ is the phase. $F(0,0)$ (the DC term) equals the average intensity times $MN$. The DFT is the basis of frequency-domain filtering and compression, and is computed efficiently using the Fast Fourier Transform (FFT) in $O(N\log N)$ instead of $O(N^2)$.

Boundary and Region in an Image

Region. A region $R$ is a connected set of pixels that share some common property (similar intensity, colour or texture). Formally, segmentation partitions an image $I$ into regions $R_1,R_2,\dots,R_n$ such that:

• $\bigcup_{i=1}^{n} R_i = I$ (they cover the whole image),
• each $R_i$ is connected,
• $R_i \cap R_j = \varnothing$ for $i\neq j$ (disjoint),
• $P(R_i)=\text{TRUE}$ (each region is homogeneous), and $P(R_i\cup R_j)=\text{FALSE}$ for adjacent regions (different regions are dissimilar).

A region is described by its interior properties (area, mean intensity, texture).

Boundary (border/contour). The boundary of a region is the set of pixels of that region which have at least one neighbour belonging to a different region (or to the background). It forms a closed curve that separates the region from its surroundings and defines the region's shape/outline.

Relationship: A region is defined by what is inside (interior, similarity-based), while a boundary is defined by the edge between regions (discontinuity-based). Together they are dual ways of describing an object — region-based and boundary-based segmentation.

Huffman Coding for Image Compression

Huffman coding is a lossless, variable-length, entropy coding technique that assigns shorter binary codes to more frequent intensity values and longer codes to rare ones, reducing coding redundancy. It produces an optimal prefix code (no code is a prefix of another, so decoding is unambiguous).

Algorithm

1. Compute the probability/frequency of each gray level (from the image histogram).
2. Treat each symbol as a leaf node; place all in a list.
3. Repeatedly take the two lowest-probability nodes, combine them into a new node whose probability is their sum, and put it back. (Build the binary Huffman tree bottom-up.)
4. Continue until a single root remains.
5. Assign 0 to one branch and 1 to the other at each node; read root-to-leaf to obtain each symbol's codeword.

Example

Symbols with probabilities $a=0.4, b=0.3, c=0.2, d=0.1$. Combining smallest pairs yields codes such as $a=0$, $b=10$, $c=110$, $d=111$. Average length $=0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9$ bits/symbol, versus 2 bits for fixed-length coding — a saving.

Notes

• Compression efficiency approaches the entropy $H=-\sum p_i \log_2 p_i$.
• It is lossless (exact reconstruction) and is used in JPEG (after DCT/quantization) and PNG.
• Requires the symbol probabilities (or a transmitted code table) to be known.

Structuring Element in Morphological Operations

A structuring element (SE) is a small set / mask of pixels (with a defined shape and a designated origin) that is moved across the image to probe and interact with its features during morphological operations (erosion, dilation, opening, closing, hit-or-miss). It plays the role analogous to the kernel in convolution, but works with set operations rather than weighted sums.

Characteristics

• Has a shape (square, rectangle, disk, cross/diamond, line) and a size, chosen to match the features being extracted/removed.
• Has an origin (reference pixel, usually the centre) that is positioned at each image pixel.
• For binary morphology its elements are 0/1 (foreground positions); some entries may be "don't care".
• A flat SE has no height values; a non-flat SE (used in grayscale morphology) assigns intensity values.

Role

• In erosion, a pixel is kept only if the SE fits entirely inside the object → shrinks objects, removes small noise.
• In dilation, a pixel is set if the SE hits (overlaps) the object → grows objects, fills gaps.
• The choice of SE shape/size determines which structures are preserved, removed or detected (e.g. a horizontal line SE extracts horizontal features).

Short Note: Discrete Sine Transform (DST)

The Sine Transform is an orthogonal, real-valued unitary transform that represents a signal/image as a weighted sum of sine basis functions. It is closely related to the Fourier and cosine transforms but uses only sine terms, making it suitable for signals/images that are (approximately) odd-symmetric at the boundaries.

1-D Discrete Sine Transform

For a sequence of length $N$:

The kernel is separable and symmetric, so the 2-D DST is obtained by applying the 1-D DST along rows then columns.

Properties / Uses

• Real, orthogonal transform (no complex arithmetic), so it is computationally convenient.
• Provides good energy compaction for certain signal statistics (low-correlation/first-order Markov sources with small correlation), where it can outperform the DCT.
• Used in image compression, transform coding, and fast solution of certain PDEs (it diagonalizes specific tridiagonal/Laplacian matrices).
• Being sine-based, it inherently assumes zero (odd) boundary values, which suits residual/difference images.