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

Digital Image Processing

Digital image processing (DIP) is the use of computer algorithms to process a digital image (a 2-D function $f(x,y)$ where $x,y$ are spatial coordinates and the amplitude $f$ is the intensity/gray level at that point, with both coordinates and amplitude being finite, discrete quantities). Its purposes include image enhancement, restoration, compression, segmentation, and machine perception.

Fundamental Steps in Digital Image Processing

1. Image acquisition – capturing the image via a sensor (camera/scanner) and digitizing it (sampling + quantization).
2. Image enhancement – adjusting an image so the result is more suitable for a specific application (e.g., contrast stretching, histogram equalization).
3. Image restoration – improving an image by removing degradation using objective mathematical/probabilistic models (e.g., inverse, Wiener filtering).
4. Colour image processing – handling images in colour models such as RGB, HSI, CMY.
5. Wavelets and multiresolution processing – representing images at multiple resolutions; basis for compression.
6. Image compression – reducing storage/bandwidth (JPEG, PNG) using lossy/lossless techniques.
7. Morphological processing – tools for extracting image components (erosion, dilation, opening, closing).
8. Segmentation – partitioning the image into regions/objects (thresholding, edge/region based).
9. Representation and description – converting segmented data into a form suitable for computer processing (boundary/regional descriptors).
10. Object recognition – assigning a label (class) to an object based on its descriptors.

A knowledge base guides and coordinates all the above steps.

Components of an Image Processing System (Block Diagram)

Described as a block diagram, the components connected around a common image processing software/computer are:

• Image sensors / acquisition device – sensor (e.g., CCD) plus a digitizer to produce the digital image.
• Specialized image-processing hardware – performs fast primitive operations (e.g., ALU/arithmetic-logic unit, frame grabber) at video rates.
• Computer – general-purpose computer that runs the processing.
• Image-processing software – specialized modules/library implementing the algorithms.
• Mass storage – short-term (frame buffers), on-line (disks), and archival storage for large images.
• Image displays – colour monitors to view results.
• Hardcopy devices – printers, film cameras for permanent records.
• Network / cloud – for transmitting and sharing images.

All components communicate through the computer and are coordinated by the image-processing software.

Histogram Equalization

Histogram equalization is a contrast-enhancement technique that redistributes the gray levels of an image so that the output histogram is approximately uniform (flat), spreading intensities over the full available range. It improves the contrast of images that are too dark or too bright.

Mathematical Formulation

Let an image have $L$ gray levels $r_k$ ($k = 0,1,\dots,L-1$), with $n_k$ pixels at level $r_k$ and total pixels $n$.

1. Probability (normalized histogram):

2. Cumulative distribution function (CDF):

3. Round $s_k$ to the nearest integer to obtain the new gray level mapping.

The transformation $T(r)$ is single-valued and monotonically increasing, so it is invertible and preserves order.

Worked Example

A $4\times4$ image (16 pixels) with $L = 8$ gray levels ($0$–$7$):

Mapping: $0\to1,\;1\to2,\;2\to4,\;3\to5,\;4\to6,\;5\to7,\;6\to7$. Each original pixel is replaced by its mapped value, giving an image whose histogram is spread out and far more uniform, hence higher contrast.

Note: Because gray levels are discrete and rounding/merging occurs, the result is only approximately uniform.

Image Segmentation

Image segmentation partitions an image into multiple regions (sets of connected pixels) that are homogeneous with respect to some property (intensity, colour, texture) and correspond to objects or meaningful parts. Formally, segmentation produces regions $R_1,\dots,R_n$ such that $\bigcup_i R_i = R$ (the whole image), the regions are disjoint, each $R_i$ satisfies a homogeneity predicate $P(R_i)=\text{TRUE}$, and adjacent regions fail it: $P(R_i \cup R_j)=\text{FALSE}$. Approaches are based on discontinuity (edges) or similarity (thresholding, region growing, split-and-merge).

Region Split-and-Merge

This is a region-based technique using a quadtree representation.

Splitting:

1. Start with the whole image as one region $R$.
2. If $P(R) = \text{FALSE}$ (region not homogeneous, e.g., gray-level variance/range exceeds a threshold), split $R$ into four equal quadrants.
3. Recursively apply step 2 to each quadrant until every region satisfies $P(R_i)=\text{TRUE}$ or reaches the minimum block size.

Merging: 4. Merge any two adjacent regions $R_i, R_j$ for which $P(R_i \cup R_j) = \text{TRUE}$. 5. Repeat merging until no further merges are possible.

The result is a set of homogeneous, connected regions. Splitting handles regions that are too coarse; merging fixes over-segmentation caused by the rigid quadtree boundaries.

Adaptive (Local) Thresholding

A single global threshold $T$ fails when illumination is uneven. Adaptive thresholding computes a threshold that varies across the image:

where $T(x,y)$ depends on the local neighbourhood (sub-image/window) around $(x,y)$. Typically the image is divided into blocks (or a sliding window is used) and a threshold is computed per block from local statistics, e.g.

where $m_{xy}$ and $\sigma_{xy}$ are the local mean and standard deviation and $C,k$ are constants. This compensates for non-uniform lighting and shading, producing better object/background separation than a global threshold.

Sampling is the digitization of the spatial coordinates $(x,y)$ of a continuous image — selecting a finite grid of points (pixels) at which to record intensity. It determines the spatial resolution (number of rows $\times$ columns); more samples give a sharper image.

Quantization is the digitization of the amplitude/intensity values — mapping the continuous intensity at each sampled point to one of a finite set of $L = 2^k$ discrete gray levels ($k$ bits). It determines the gray-level (intensity) resolution; more levels give smoother tonal transitions and avoid false contouring.

Together, sampling and quantization convert a continuous image $f(x,y)$ into a digital image represented as an $M \times N$ matrix of integer gray levels.

Image enhancement is the process of adjusting/improving an image so that the result is more suitable than the original for a specific application or for human viewing — e.g., increasing contrast, sharpening edges, or removing noise. It is largely subjective (problem-oriented), not based on an objective degradation model.

Spatial vs Frequency Domain Enhancement

By the convolution theorem, spatial convolution corresponds to multiplication in the frequency domain, so the two are mathematically linked.

Histogram of an Image

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

where $r_k$ is the $k$-th gray level and $n_k$ is the number of pixels in the image having that gray level. Plotting $h(r_k)$ (or the normalized histogram $p(r_k)=n_k/n$, where $n$ is the total number of pixels) against $r_k$ gives the histogram.

Interpretation:

• It shows the frequency/distribution of intensities in the image.
• Levels concentrated to the left $\Rightarrow$ dark image; to the right $\Rightarrow$ bright image; a narrow spread $\Rightarrow$ low contrast; a wide, even spread over the full range $\Rightarrow$ high contrast.

Uses: image analysis and statistics, thresholding/segmentation, and the basis for enhancement techniques such as histogram equalization and histogram specification (matching).

Low-Pass Filter

A low-pass filter (LPF) is a filter that passes low spatial frequencies and attenuates high frequencies. Since high frequencies correspond to sharp transitions — edges, fine detail and noise — removing them blurs/smooths the image.

Frequency domain: $G(u,v) = H(u,v)\,F(u,v)$, where $H(u,v)$ is large near the origin (low frequencies) and small for high $(u,v)$ — e.g. the ideal, Butterworth, or Gaussian low-pass filter.

Spatial domain (smoothing): convolution with an averaging (mean) mask whose coefficients are positive and sum to 1, e.g. the $3\times3$ averaging kernel

Each output pixel is the average of its neighbourhood, so abrupt intensity changes (noise) are smoothed out.

Use for smoothing: low-pass filtering is used for noise reduction and to remove small irrelevant detail before further processing. The trade-off is blurring of edges, which increases with filter (mask) size or a lower cutoff frequency.

Lossy vs Lossless Compression

Summary: Lossless trades lower compression for perfect fidelity; lossy trades some quality for much smaller file size.

Properties of the 2-D Fourier Transform

For a 2-D image $f(x,y)$ with transform $F(u,v)$, key properties are:

1. Linearity: $\mathcal{F}\{a f_1 + b f_2\} = aF_1(u,v) + bF_2(u,v)$.
2. Separability: the 2-D DFT can be computed as two successive 1-D DFTs — first along rows, then along columns (greatly speeds computation with FFT).
3. Translation (shift): a spatial shift only changes the phase, not the magnitude:

Multiplying by $(-1)^{x+y}$ centres the spectrum at $(M/2,N/2)$. 4. Periodicity: the 2-D DFT and its inverse are periodic with periods $M$ and $N$: $F(u,v)=F(u+M,v)=F(u,v+N)$. 5. Conjugate symmetry: for a real image, $F(u,v)=F^*(-u,-v)$, so $|F(u,v)|=|F(-u,-v)|$ (the magnitude spectrum is symmetric). 6. Rotation: rotating $f(x,y)$ by an angle rotates $F(u,v)$ by the same angle. 7. Scaling: $f(ax,by) \Leftrightarrow \dfrac{1}{|ab|}F(u/a, v/b)$ — expansion in one domain compresses the other. 8. Convolution theorem: $f(x,y)*h(x,y) \Leftrightarrow F(u,v)H(u,v)$, and multiplication in space corresponds to convolution in frequency (basis of frequency-domain filtering). 9. Average value: $F(0,0)=\dfrac{1}{MN}\sum_x\sum_y f(x,y)$ equals the average gray level (DC component). 10. Distributivity over addition (but not over multiplication).

Edge Detection with the Sobel Operator

Edges are locations of rapid intensity change, detected using the gradient of the image. The Sobel operator is a discrete $3\times3$ derivative operator that estimates the gradient while smoothing (reducing noise) because of its weighted centre coefficients.

Sobel masks (horizontal and vertical):

Procedure:

1. Convolve the image with $G_x$ to get the horizontal gradient and with $G_y$ to get the vertical gradient at each pixel.
2. Compute the gradient magnitude:

3. Optionally compute the gradient direction: $\theta = \tan^{-1}\!\left(\dfrac{G_y}{G_x}\right)$.
4. Threshold the magnitude: pixels with $|\nabla f| > T$ are marked as edge pixels.

The centre weight of $2$ gives the Sobel operator better noise smoothing and edge detection than the simpler Prewitt operator, making it widely used for detecting both horizontal and vertical edges.

Image Restoration

Image restoration is the process of recovering or reconstructing an image that has been degraded by using a priori knowledge of the degradation phenomenon and an objective mathematical/probabilistic model of it. Unlike enhancement (which is subjective), restoration is objective — it tries to undo a known/estimated degradation to obtain an estimate $\hat{f}(x,y)$ as close as possible to the original $f(x,y)$.

Degradation model:

or in the frequency domain $G(u,v)=H(u,v)F(u,v)+N(u,v)$, where $h$ is the degradation function (e.g., blur PSF) and $\eta$ is additive noise.

Goal: apply a restoration filter to $g$ to estimate $\hat{f}$.

Common techniques: inverse filtering, Wiener (least-squares) filtering, constrained least-squares filtering, and noise-removal spatial filters (mean, median, order-statistic filters). Typical degradations addressed include motion blur, out-of-focus blur, and various types of noise.

RGB Colour Model

The RGB model represents a colour as an additive combination of three primaries — Red, Green, Blue. Each pixel is a triple $(R, G, B)$, and any colour is a point in a unit colour cube with black at the origin $(0,0,0)$ and white at $(1,1,1)$ (or $255,255,255$ for 8-bit/channel). Equal R, G, B values lie on the gray (diagonal) line.

• Hardware-oriented: matches how monitors, cameras and scanners capture/display colour.
• Drawback: the three components are highly correlated and the model is not intuitive for humans — it is hard to specify a desired colour directly.

HSI Colour Model

The HSI model describes colour the way humans perceive it, using three components:

• Hue (H): the dominant colour / wavelength (e.g., red, green); an angle $0^\circ$–$360^\circ$.
• Saturation (S): purity of the colour — how much white is mixed in (0 = gray, 1 = pure colour).
• Intensity (I): brightness, $I = \dfrac{R+G+B}{3}$.

Advantage: it decouples intensity (I) from colour (H, S), so grayscale-style processing (e.g., enhancement, edge detection) can be done on the intensity channel without distorting colour. This makes HSI ideal for image-processing algorithms based on human colour perception. RGB and HSI are inter-convertible by standard transformation equations.