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

Digital Image Processing Fundamentals

A digital image is a two-dimensional function $f(x,y)$, where $x,y$ are spatial coordinates and the value of $f$ at any point is the intensity (gray level). When $x$, $y$, and the amplitude are all finite and discrete, the image is digital. Each discrete element is a pixel (picture element).

Image Acquisition Pipeline

A continuous scene is converted to a digital image in two steps:

1. Sampling – digitizing the spatial coordinates $(x,y)$.
2. Quantization – digitizing the amplitude (intensity) values.

1. Image Sampling

Sampling divides the continuous image into a grid of $M \times N$ points, producing the pixel array:

• More samples → higher spatial resolution → finer detail.
• Insufficient sampling causes aliasing (the Nyquist criterion: sampling rate must be at least twice the highest spatial frequency).

2. Quantization

Each sampled value is mapped to one of $L = 2^{k}$ discrete intensity levels, where $k$ is the number of bits per pixel. For an 8-bit image, $L = 256$ levels ($0$–$255$). Too few levels produce false contouring. Storage of an image is $M \times N \times k$ bits.

3. Basic Relationships Between Pixels

For a pixel $p$ at $(x,y)$:

• Neighbors:
  • 4-neighbors $N_4(p)$: $(x\pm1,y),(x,y\pm1)$.
  • Diagonal neighbors $N_D(p)$: $(x\pm1,y\pm1)$.
  • 8-neighbors $N_8(p) = N_4(p) \cup N_D(p)$.
• Adjacency: 4-, 8-, and m-adjacency (mixed adjacency, used to remove path ambiguity).
• Connectivity / Region / Boundary: pixels are connected if adjacent and their values satisfy a similarity criterion $V$; a maximal connected set forms a region.
• Distance measures between $p(x,y)$ and $q(s,t)$:
  • Euclidean: $D_e = \sqrt{(x-s)^2+(y-t)^2}$
  • City-block ($D_4$): $|x-s|+|y-t|$
  • Chessboard ($D_8$): $\max(|x-s|,|y-t|)$

Conclusion

Sampling and quantization determine an image's spatial resolution and intensity resolution respectively, while pixel relationships (neighborhood, adjacency, connectivity, distance) form the basis of region-level operations such as segmentation and morphology.

Histogram Processing

The histogram of a digital image with intensity levels in $[0, L-1]$ is the discrete function

where $r_k$ is the $k$-th intensity and $n_k$ is the number of pixels with that intensity. The normalized histogram is $p(r_k)=n_k/MN$, which approximates the probability of occurrence of level $r_k$. Histogram processing modifies this distribution to improve contrast.

Histogram Equalization

Goal: spread intensities to produce an approximately uniform histogram, maximizing global contrast. The transformation is the cumulative distribution function (CDF):

Example. A 3-bit ($L=8$) $64\times64$ image ($MN=4096$):

Pixels are remapped using the round column, stretching the originally dark image across the full range.

Histogram Specification (Matching)

Instead of a uniform output, we force the histogram to match a specified target shape $p_z(z)$. Steps:

1. Equalize the input: $s = T(r) = (L-1)\sum_{j=0}^{r} p_r(r_j)$.
2. Equalize the target: $G(z) = (L-1)\sum_{i=0}^{z} p_z(z_i)$.
3. For each $s$, find $z = G^{-1}(s)$, i.e. the level whose equalized value is closest to $s$.

This gives the mapping $z = G^{-1}(T(r))$.

Equalization vs Specification

Fourier Transform in Image Processing

The Fourier transform (FT) decomposes an image into its sinusoidal frequency components, moving from the spatial domain $f(x,y)$ to the frequency domain $F(u,v)$. Slowly varying regions map to low frequencies; edges and fine detail map to high frequencies.

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

and its inverse:

Frequency-Domain Filtering

Filtering is performed by point-wise multiplication with a transfer function $H(u,v)$:

General steps: (1) shift origin by multiplying $f(x,y)$ by $(-1)^{x+y}$, (2) compute the DFT, (3) multiply by $H(u,v)$, (4) inverse DFT, (5) take real part and undo the shift. Let $D(u,v)$ be the distance of $(u,v)$ from the centred origin and $D_0$ the cutoff.

1. Ideal Low-Pass Filter (ILPF)

It passes all frequencies inside a circle of radius $D_0$ and blocks the rest. Although it gives the sharpest possible cut, its abrupt transition causes ringing artifacts (concentric ripples) because of the sinc nature of its spatial response.

2. Butterworth Low-Pass Filter (BLPF)

where $n$ is the filter order. The transition is smooth and controllable:

• Low order $n$ → gentle roll-off, little ringing.
• High order $n$ → approaches the ideal filter (more ringing).

Examples / Effect

• Low-pass (ILPF/BLPF) → blurring and noise smoothing (removes high frequencies).
• High-pass (obtained as $H_{HP}=1-H_{LP}$) → edge sharpening (removes low frequencies). The Butterworth high-pass is $H(u,v)=\dfrac{1}{1+[D_0/D(u,v)]^{2n}}$.

Comparison

Thus the Butterworth filter is generally preferred in practice because it trades a small amount of sharpness for greatly reduced ringing.

Resolution is the amount of detail an image holds, given by its number of pixels, written as $\text{width} \times \text{height}$ (e.g. $1920\times1080$). Spatial resolution refers to the smallest discernible detail (pixel density, often dpi), while intensity (gray-level) resolution refers to the number of distinct intensity levels $L=2^k$. Higher resolution means finer detail.

Aspect ratio is the proportional relationship between an image's width and height, expressed as $W{:}H$ (e.g. $4{:}3$, $16{:}9$). It must be preserved when resizing to avoid distortion (stretching/squashing).

Log Transformation

The log transformation is a point (intensity) transformation given by

where $r$ is the input intensity ($r \ge 0$), $s$ is the output, and $c$ is a scaling constant (often $c = \frac{L-1}{\log(1+R_{max})}$ to fit the output to $[0,L-1]$).

Characteristics & Use

• It maps a narrow range of low (dark) input values to a wider range of output values, and compresses high (bright) values.
• Therefore it expands the dark regions and brightens the image while compressing the dynamic range.
• Main use: displaying images with a very large dynamic range, such as the Fourier spectrum, where a few very large values would otherwise dominate and hide low-magnitude detail. Applying the log lets all components become visible on a normal display.
• The inverse-log (exponential) transformation does the opposite, enhancing bright regions.

Convolution in Spatial Filtering

Spatial filtering processes a pixel using a small mask (kernel) $w$ of size $m \times n$ slid over the image. Convolution is the core operation that computes each output pixel as a weighted sum of the input pixel and its neighbours.

For a kernel of size $(2a+1)\times(2b+1)$, the 2-D convolution is

Key Points

• The kernel is rotated by 180° before sliding (this distinguishes convolution from correlation, which uses the kernel as-is).
• For each position, multiply overlapping kernel and image values, sum them, and place the result at the centre pixel.
• Borders are handled by padding (zero, replicate, or mirror).

Example: convolving with $\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$ averages each $3\times3$ neighbourhood, producing a smoothing (blur) effect. Different kernels produce smoothing, sharpening, or edge detection. Convolution is linear and shift-invariant, which is why the same kernel applies uniformly across the image.

DFT vs DCT

1-D DCT: $\;C(u)=\alpha(u)\displaystyle\sum_{x=0}^{N-1} f(x)\cos\!\left[\frac{(2x+1)u\pi}{2N}\right]$.

Summary: The DFT is general-purpose (complex, used for filtering/analysis), whereas the DCT is real-valued with superior energy compaction, making it the transform of choice for image and video compression.

Watershed Segmentation

The watershed transform is a region-based segmentation method that treats a grayscale image as a topographic surface, where intensity is interpreted as elevation. Bright pixels are hills/ridges and dark pixels are valleys (catchment basins).

Flooding Analogy

Imagine piercing a hole at each local minimum and slowly flooding the surface from below:

1. Water rises uniformly and fills each catchment basin.
2. Where waters from two different basins are about to merge, a dam (watershed line) is built.
3. When flooding completes, the dams form closed contours that segment the image into regions.

It is usually applied to a gradient image, so basins correspond to homogeneous regions and watershed lines lie along strong edges.

Over-segmentation and the Fix

Noise and small intensity fluctuations create many spurious minima, causing over-segmentation (too many tiny regions). This is controlled by marker-controlled watershed: internal and external markers are defined first, and flooding starts only from those markers, yielding meaningful regions.

Advantages: produces continuous, closed boundaries; intuitive. Disadvantage: sensitive to noise → over-segmentation without markers.

Canny Edge Detector

The Canny edge detector (J. Canny, 1986) is an optimal multi-stage algorithm designed to satisfy three criteria: good detection (low error rate), good localization (edges close to true edges), and single response per edge. Its steps are:

1. Smoothing – convolve the image with a Gaussian filter to reduce noise.
2. Gradient computation – find intensity gradient magnitude and direction (e.g. using Sobel):

3. Non-maximum suppression – thin the edges by keeping only pixels that are local maxima of $M$ along the gradient direction, suppressing all others.
4. Double thresholding – classify pixels using two thresholds $T_{high}$ and $T_{low}$ into strong ($>T_{high}$), weak ($T_{low}$–$T_{high}$), and non-edge ($<T_{low}$).
5. Edge tracking by hysteresis – keep weak edges only if they are connected to a strong edge; discard isolated weak edges.

Significance

Canny produces thin, continuous, well-localized edges and is robust to noise, making it one of the most widely used edge detectors compared with simpler operators (Sobel, Prewitt) that lack thinning and hysteresis.

Dilation and Erosion (Morphological Operations)

Morphological operations process a binary (or grayscale) image $A$ with a small structuring element (SE) $B$, based on set theory.

Dilation $A \oplus B$

The SE is slid over the image; if it touches (overlaps) any foreground pixel, the centre is set to foreground. Effect: grows / thickens objects, fills small holes and gaps, and connects nearby components.

Example: with a $3\times3$ SE, an isolated foreground pixel expands into a $3\times3$ block; a one-pixel gap in a line is bridged.

Erosion $A \ominus B$

The centre stays foreground only if the entire SE fits inside the object. Effect: shrinks / thins objects, removes small isolated noise pixels and thin protrusions.

Example: with a $3\times3$ SE, an object's boundary layer is stripped off by one pixel; an isolated single foreground pixel is removed entirely.

Duality and Combinations

They are duals: $(A \ominus B)^c = A^c \oplus \hat{B}$.

• Opening = erosion then dilation ($A\circ B$) → removes small objects/noise, smooths contours.
• Closing = dilation then erosion ($A\bullet B$) → fills small holes and gaps.

JPEG Compression Standard

JPEG (Joint Photographic Experts Group) is the most widely used lossy compression standard for continuous-tone still images. It exploits the human visual system's reduced sensitivity to high-frequency detail and to colour (chrominance).

Baseline Encoding Steps

1. Colour transform & subsampling – convert RGB to $YC_bC_r$; subsample the chroma channels (e.g. 4:2:0) since the eye is less sensitive to colour detail.
2. Block splitting – divide each channel into $8\times8$ pixel blocks; level-shift by subtracting 128.
3. Forward DCT – apply the 2-D Discrete Cosine Transform to each block, concentrating energy in the top-left (low-frequency) coefficients.
4. Quantization – divide each DCT coefficient by a value from a quantization table and round. This is the lossy step; higher-frequency coefficients (less visible) are quantized more coarsely. A quality factor scales the table.
5. Entropy coding – reorder coefficients in a zig-zag scan (groups zeros together), apply run-length encoding plus DPCM on the DC term, then Huffman (or arithmetic) coding.

Decoding

The inverse steps (entropy decode → dequantize → inverse DCT → colour reconstruct) recover the image. Because quantization discards data, the result is an approximation; lower quality → higher compression and more blocking artifacts.

Note: JPEG also defines a lossless mode, while JPEG 2000 uses the wavelet transform instead of the DCT.

Colour Image Processing Models

A colour model is a specification of a coordinate system in which each colour is represented as a point. The main models used in image processing are:

1. RGB (Red, Green, Blue)

An additive model where colours are formed by combining the three primaries. Represented as a unit cube; suited to hardware such as monitors, cameras, and scanners. A pixel is a triplet $(R,G,B)$; 24-bit colour gives $\approx16.7$M colours.

2. CMY / CMYK (Cyan, Magenta, Yellow, blacK)

A subtractive model used for printing. Related to RGB by $\begin{bmatrix}C\\M\\Y\end{bmatrix}=\begin{bmatrix}1\\1\\1\end{bmatrix}-\begin{bmatrix}R\\G\\B\end{bmatrix}$. Black (K) is added for true black and ink economy.

3. HSI (Hue, Saturation, Intensity)

Separates colour information (hue, saturation) from intensity. Because it decouples intensity from chromaticity, it matches human colour perception and is ideal for image-processing algorithms (e.g. you can enhance brightness or segment by hue independently). Related variants: HSV/HSB and HSL.

4. $YC_bC_r$ / YUV

$Y$ = luminance, $C_b,C_r$ = chrominance. Used in video and JPEG/MPEG compression because chroma can be subsampled with little perceived loss.

Summary