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

High-Frequency Emphasis Filter vs Laplacian Filter

In short, the high-frequency emphasis filter is essentially a high-pass filter with an added offset so the result is not a bare edge map, whereas the Laplacian is an isotropic second-derivative operator whose raw output is an edge map that is normally combined with the original for sharpening.

Histogram Equalization ($L=8$)

Input image ($5\times5$):

3 3 3 3 3
2 3 4 3 2
2 4 4 4 2
2 3 4 3 2
3 3 3 3 3

Total pixels $MN = 25$, levels $L=8$ so the scaling factor is $L-1=7$.

Step 1 – Histogram (count of each gray level):

(All other levels 0, 1, 5, 6, 7 have count 0.)

Step 2 – PDF, CDF and transformation $s_k=\text{round}\big[(L-1)\,\text{CDF}\big]$:

Step 3 – Mapping: $2\to2,\; 3\to6,\; 4\to7$.

Output (equalized) image:

6 6 6 6 6
2 6 7 6 2
2 7 7 7 2
2 6 7 6 2
6 6 6 6 6

The original values were clustered in $\{2,3,4\}$; after equalization they are spread across $\{2,6,7\}$, increasing the global contrast.

Definition of Noise

Noise in an image is any unwanted random variation in pixel intensity that is not part of the true scene. It is introduced during acquisition (sensor thermal noise, low light), digitization (quantization), or transmission (channel errors). Noise degrades quality and is usually modelled as a random process described by its probability density function (PDF).

Common noise models include Gaussian, Rayleigh, Erlang (gamma), exponential, uniform, and salt-and-pepper (impulse) noise.

Image Degradation / Restoration Model

The goal of restoration is to recover an estimate $\hat{f}(x,y)$ of the original image from a degraded observation $g(x,y)$, using knowledge of the degradation process. (Restoration is objective, based on a model, unlike enhancement which is subjective.)

Degradation Model

Degradation is modelled as a degradation function $H$ acting on the input image $f(x,y)$, followed by the addition of noise $\eta(x,y)$:

 f(x,y) ---->[ H ]----> (+) ----> g(x,y) ----->[ Restoration ]----> f^(x,y)
 degradation ^ filter(s)
 function |
 noise η(x,y)

Spatial domain (H is linear and position-invariant ⇒ convolution):

Frequency domain (convolution becomes multiplication):

Restoration Process

Given $g$, an estimate of $H$, and statistics of $\eta$, restoration applies an inverse/restoration filter $R$ to obtain $\hat{f}$. Typical filters:

• Inverse filtering: $\hat{F}(u,v)=G(u,v)/H(u,v)$ — simple but amplifies noise where $H$ is small.
• Wiener (minimum mean-square error) filter: balances inverse filtering against noise using the signal/noise power ratio:

• Mean / order-statistic (median) filters when only noise (no blur, $H=1$) is present.

Summary

The more that is known about $H$ and $\eta$, the better the restoration. When $H$ is identity, the problem reduces to noise removal; when noise is negligible, it reduces to deblurring.

Spatial Domain vs Frequency Domain

2-D DFT of the Image

Input image ($4\times4$, all ones):

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

The 2-D DFT is

DC term ($u=v=0$): the exponential is 1, so

All other terms ($u\neq0$ or $v\neq0$): since $f$ is constant, each is the sum of a full period of a complex exponential, which is zero:

so $F(u,v)=0$ for every $(u,v)\neq(0,0)$.

Result:

F = 16 0 0 0
 0 0 0 0
 0 0 0 0
 0 0 0 0

Interpretation: a constant (uniform) image has no variation, so all its energy lies in the DC (zero-frequency) component $F(0,0)=16$ (equal to total intensity = average $\times$ $MN = 1\times16$), with no higher-frequency content.

Chain Code

A chain code is a boundary (contour) representation that encodes a connected sequence of straight-line segments of specified length and direction. Starting from a chosen boundary pixel and tracing the boundary, each move to the next pixel is recorded as a direction number.

• 4-directional code uses directions 0–3 (E, N, W, S).
• 8-directional code uses directions 0–7 (counter-clockwise, with diagonals):

 3 2 1
 \ | /
 4 -- P -- 0
 / | \
 5 6 7

Advantages: compact boundary description; disadvantages: depends on the starting point and is not rotation-invariant, which is fixed by the difference code and shape number.

Shape Number of {0, 7, 5, 4, 3, 1}

Step 1 – First difference (number of counter-clockwise direction changes between consecutive codes, treating the code as circular, mod 8):

Differences for $\{0,7,5,4,3,1\}$ (also wrapping last→first):

First difference (rotation-invariant): 7 6 7 7 6 7

Step 2 – Shape number = the first difference of smallest magnitude when treated as a circular sequence (rotate to the smallest possible integer):

Rotations of 7 6 7 7 6 7: the smallest starts with the smaller digit 6: 6 7 6 7 7 7 and 6 7 7 7 6 7. The numerically smallest is

Its order (length) is 6.

Logic Operations on Binary Images for Masking & Feature Detection

On binary images (pixels are 0 or 1), the basic logic operations AND, OR, NOT (complement), XOR are applied pixel-by-pixel between an image and a second image or mask. Because they are functionally complete, they let us select, combine, and isolate regions.

Masking (region selection)

A mask is a binary image whose foreground (1) marks the region of interest (ROI).

• AND with a mask keeps only the pixels where the mask is 1 and forces everything else to 0 — i.e. it extracts/crops the ROI:

• OR is used to insert/merge a region or combine two binary shapes.
• NOT inverts foreground and background (useful to build the complementary mask).

Example: to keep a circular object, AND the image with a circular mask of 1's; pixels outside the circle (mask = 0) become 0.

Feature Detection

• XOR (difference): $f_1 \oplus f_2$ is 1 only where the two images differ, so XOR between two frames detects change / moving features, and XOR between an object and its eroded version yields the boundary.
• AND with a template highlights where a pattern matches; combined with morphology (hit-or-miss) it detects specific shapes/corners.
• AND/OR of bit-planes or thresholded feature maps isolates pixels satisfying multiple conditions simultaneously.

Summary

Thus logic operations provide a simple, fast mechanism for isolating regions (masking) and for detecting features such as boundaries, changes, and template matches.

Pattern and Pattern Class

• A pattern is an arrangement of descriptors (features) that characterise an object. It is usually written as a feature vector $\mathbf{x}=(x_1,x_2,\dots,x_n)^T$ in an $n$-dimensional feature space (it may also be a string or a tree for structural recognition).
• A pattern class is a family/category of patterns that share common properties, denoted $\omega_1,\omega_2,\dots,\omega_W$ for $W$ classes. Pattern recognition assigns each pattern to its correct class.

Decision-Theoretic Methods and Minimizing Misclassification

Decision-theoretic recognition uses decision (discriminant) functions $d_i(\mathbf{x})$, one per class. A pattern $\mathbf{x}$ is assigned to class $\omega_i$ if

The boundary between classes $i$ and $j$ is $d_i(\mathbf{x})-d_j(\mathbf{x})=0$.

Bayes Classifier — minimum-error decision

The probability of misclassification is minimized by the Bayes classifier, which assigns $\mathbf{x}$ to the class with the largest posterior probability. Using Bayes' rule the decision function becomes

and we choose $\omega_i$ if $p(\mathbf{x}\mid\omega_i)P(\omega_i) > p(\mathbf{x}\mid\omega_j)P(\omega_j)$ for all $j\neq i$.

Why it is optimal: at every point in feature space the classifier picks the most probable class, so the conditional error at that point is the smallest possible. Integrating over all $\mathbf{x}$, the total average error (Bayes risk) is the minimum achievable by any classifier. Equivalently it places the decision boundary exactly where the posteriors of two classes are equal, allocating each region to the class that is more likely there.

(For Gaussian classes this reduces to comparing Mahalanobis distances; equal covariance gives linear, otherwise quadratic, boundaries.)

Edge Detection with the Prewitt Operator

Prewitt masks:

($G_x$ detects vertical edges / horizontal change; $G_y$ detects horizontal edges / vertical change.)

Input image ($3\times3$):

 0 30 60
 5 32 62
 10 38 64

We compute the gradient at the centre pixel (value 32), where the full mask fits.

Horizontal gradient $G_x$ (right column − left column)

Vertical gradient $G_y$ (bottom row − top row)

Gradient Magnitude

Gradient Direction

Interpretation

The large magnitude ($\approx172$) indicates a strong edge at the centre pixel. Since $G_x \gg G_y$, the intensity changes mainly in the horizontal direction (values increase left→right), so the edge is essentially vertical, with the gradient pointing almost horizontally ($\approx7^{\circ}$ above horizontal).

Image Segmentation

Image segmentation is the process of partitioning an image into multiple regions (sets of pixels) that are meaningful for analysis, so that pixels within a region are similar and adjacent regions differ. Formally, segmentation divides image $R$ into regions $R_1,\dots,R_n$ such that:

1. $\bigcup_i R_i = R$ (complete),
2. each $R_i$ is connected,
3. $R_i \cap R_j = \varnothing$ for $i\neq j$ (disjoint),
4. a predicate $P(R_i)=\text{TRUE}$ (each region is homogeneous), and
5. $P(R_i\cup R_j)=\text{FALSE}$ for adjacent regions.

Approaches are based on discontinuity (points, lines, edges) or similarity (thresholding, region growing).

Detecting Horizontal and Vertical Lines

Lines are detected by convolving the image with directional line masks that give a strong response when the local pattern matches that orientation.

Horizontal line mask (responds to a row of high values):

 -1 -1 -1
 2 2 2
 -1 -1 -1

Vertical line mask (responds to a column of high values):

 -1 2 -1
 -1 2 -1
 -1 2 -1

Procedure

1. Convolve the image with the mask to obtain response $R(x,y)$.
2. The mask coefficients sum to zero, so flat regions give $R\approx0$ and a matching line gives a large $|R|$.
3. Threshold the response: if $|R(x,y)| \ge T$, mark the pixel as a line point of that orientation.

Applying the horizontal mask isolates horizontal lines and the vertical mask isolates vertical lines; ±45° masks similarly detect diagonal lines.

Steps (Fundamental Stages) in Digital Image Processing

The standard pipeline (Gonzalez & Woods) proceeds as follows, with the knowledge base guiding every stage:

1. Image Acquisition — capture the image with a sensor and digitize it (sampling + quantization). May include simple pre-processing like scaling.
2. Image Enhancement — improve appearance subjectively (e.g. contrast stretch, histogram equalization, sharpening) to highlight features of interest.
3. Image Restoration — objectively recover a degraded image using a mathematical model of the degradation and noise (e.g. inverse, Wiener filtering).
4. Colour Image Processing — handle colour models (RGB, HSI, CMYK) and colour-based operations; important for web and multimedia.
5. Wavelets and Multiresolution Processing — represent the image at multiple resolutions; basis for compression and pyramidal analysis.
6. Compression — reduce storage/bandwidth by removing redundancy (e.g. JPEG, run-length, Huffman coding).
7. Morphological Processing — extract structure/shape using set operations (dilation, erosion, opening, closing); bridges processing and analysis.
8. Segmentation — partition the image into objects/regions (thresholding, edge/region methods). A critical and difficult step.
9. Representation and Description — represent segmented regions by boundary (chain code) or region (texture) and compute descriptors/features.
10. Object Recognition — assign a label to an object based on its descriptors (decision-theoretic or structural recognition).

Throughout, the Knowledge Base stores prior information that controls and coordinates the interaction between the modules.

Acquisition -> Enhancement -> Restoration -> Colour -> Wavelets
 -> Compression -> Morphology -> Segmentation
 -> Representation/Description -> Recognition
 (all guided by the Knowledge Base)

Measuring Distance Between Pixels

For pixels $p$ at $(x,y)$ and $q$ at $(s,t)$, the common distance measures are:

1. Euclidean distance $D_e$:

Points within $D_e\le r$ form a disk of radius $r$.

2. City-block / Manhattan distance $D_4$ (moves along 4-neighbours):

Equidistant points form a diamond.

3. Chessboard distance $D_8$ (moves along 8-neighbours):

Equidistant points form a square.

A valid distance metric satisfies $D(p,q)\ge0$ (=0 iff $p=q$), $D(p,q)=D(q,p)$, and the triangle inequality $D(p,q)\le D(p,z)+D(z,q)$.

Region-Oriented Segmentation

Region-based methods group pixels directly into regions using a similarity (homogeneity) predicate $P$, rather than detecting edges.

1. Region Growing

Start from one or more seed pixels and iteratively append neighbouring pixels that satisfy the predicate (e.g. intensity difference below a threshold). Growth stops when no neighbour qualifies. Pros: produces connected regions; cons: result depends on seed and threshold choice, sensitive to noise.

2. Region Splitting and Merging

Uses a quadtree:

• Split: if a region is not homogeneous ($P(R_i)=\text{FALSE}$), divide it into four quadrants; repeat recursively.
• Merge: combine adjacent regions whose union is homogeneous ($P(R_i\cup R_j)=\text{TRUE}$).

The process stops when no region can be split or merged, yielding a final segmentation. Region methods guarantee connected, closed regions but can be computationally heavy.

Clipping and Contrast Stretching

• Clipping is a point operation that forces all intensities outside a chosen range $[r_1,r_2]$ to fixed limits — values below $r_1$ become $0$ (or $r_1$) and values above $r_2$ become $L-1$ (or $r_2$). It is a special case of contrast stretching with the slope set to 0 outside the band, used to suppress unwanted background/noise levels and isolate a feature band.

• Contrast stretching expands a narrow range of input intensities to span the full available range $[0,L-1]$, increasing contrast. Using control points $(r_1,s_1)$ and $(r_2,s_2)$, the piecewise-linear transform stretches the mid-range while compressing the dark and bright ends. With $s_1=0,\,s_2=L-1$ it maps $[r_1,r_2]\to[0,L-1]$:

Hadamard Transform of {1, 2, 0, 3}

The order-4 (natural-ordered) Hadamard matrix is $H_4=H_2\otimes H_2$:

With input vector $\mathbf{f}=[1,\,2,\,0,\,3]^T$, the transform is $\mathbf{F}=H_4\,\mathbf{f}$:

If the normalized form $\frac{1}{N}H_4\mathbf{f}$ (with $N=4$) is required:

Forward vs Inverse Transform

In processing we apply the forward transform, modify coefficients (filter/quantize), then apply the inverse transform to obtain the result.

Pixel Coding, Run Length, Bit Plane

• Pixel (PCM) coding: the basic representation where each pixel's intensity is coded independently using a fixed number of bits (e.g. 8 bits/pixel). It removes coding redundancy by assigning shorter codes to more frequent gray levels (variable-length / Huffman coding) instead of equal-length codes.

• Run-length encoding (RLE): a lossless method that replaces sequences (runs) of identical pixels with a (value, run-length) pair. Highly effective for images with long uniform stretches (binary/fax images). Example: 0 0 0 0 1 1 → (0,4)(1,2).

• Bit plane (slicing): an $k$-bit image is decomposed into $k$ binary planes, one per bit position. The most significant bit-plane holds the major structure, while lower planes hold fine detail/noise. Coding only the high-order planes (often with RLE) achieves compression; bit-plane slicing also aids analysis and watermarking.