Module 6: Image Segmentation,

Feature Extraction
 FEATURE DETECTION: POINT, LINE & EDGE
DETECTION

These techniques are key aspects of feature detection in image

processing, which is the process of identifying significant structures or
patterns in an image.
[Link] DETECTION
Detect individual pixels in an image that differ significantly in
intensity from their surroundings. These pixels often indicate features
like corners, small bright spots, or isolated noise.

Method
• Use convolution filters or masks that enhance intensity variations
over a local region.
• A typical mask for point detection is based on the second
derivative of intensity, such as a Laplacian operator.
Example: The Laplacian mask:
Steps:
1. Convolve the mask with the image.
2. Threshold the result to identify significant intensity differences.
• If the output of the mask is above a certain threshold, the
pixel is considered a point.
Applications
• Detecting stars in astronomical images.
• Identifying key points in computer vision for further processing, such
as feature matching.

2. LINE DETECTION
Identify lines in an image with specific orientations such as
horizontal, vertical, or diagonal.
Method
• Use masks designed to highlight intensity variations along
particular orientations.
• A high response to the mask indicates the presence of a line in
the corresponding direction.
 • Vertical Line:

• Diagonal Line ():

Steps:
1. Convolve the image with each mask to detect lines in specific orientations.
2. Threshold the result to identify strong responses corresponding to lines.
Applications
• Road and lane detection in self-driving cars.
• Structural analysis of engineering blueprints.
• Text recognition (detecting baselines or handwritten strokes).
ter padding Given Filter
This is an example of a Horizontal Line
Detector. The large positive values (2) in
the middle row will amplify (brighten) any
pixels that form a bright horizontal line.

For Pixel at (0,0)

Repeating this process for all 16

x
pixels
The final 4x4 output result is:

The high positive values like 32 in the output matrix strongly indicate
the presence of the horizontal line
The surrounding negative and smaller positive values indicate regions
that do not match the target horizontal line pattern.
2. EDGE DETECTION
Identify the boundaries or edges of objects in an image, where the intensity of
pixels changes sharply. This is essential for segmenting objects and understanding
shapes.
Steps:
The three steps performed typically for edge detection are:
1. Image smoothing for noise reduction.
2. Detection of edge points. This is a local operation that extracts from an
image all points that are potential edge-point candidates.
3. Edge localization. The objective of this step is to select from the candidate
points only the points that are members of the set of points comprising an edge.

Types of Edge Detection

1. Gradient-based Edge Detection
Calculate the first derivative of intensity to find regions of sharp change.
Popular methods:
• Sobel Operator: Uses two masks to detect horizontal (Gx​) and vertical (Gy​)
intensity gradients.
 • Prewitt Operator: Similar to Sobel but simpler weights.
• Roberts Cross Operator: Computes gradients diagonally.
Steps:
1. Apply Gx and Gy​masks to calculate gradients.
2. Compute the gradient magnitude:

A sharpened image can be computed by:

3. Compute the gradient direction: This calculates the direction of
the edge

4. Threshold the gradient magnitude to highlight significant edges.

2. Second Derivative Edge Detection:
• Uses Laplacian operator (second derivative) to detect zero-crossings
(places where the intensity goes from positive to negative or vice
versa).
Steps: 1. Convolve the mask with the image.
2. Identify points where the result changes sign (zero-crossings).
3. Canny Edge Detection:
A widely used multi-step process for edge detection:
1. Smooth the image using a Gaussian filter to reduce noise.
2. Compute gradients using the Sobel operator.
3. Apply non-maximum suppression to thin edges: This step
removes thick edges and keeps only the sharpest part of
the edge.
4. Use double thresholding to detect strong and weak edges.
i.e We now decide which edges to keep by using two thresholds:
High threshold: Marks strong edges (real edges).
Low threshold: Marks weak edges (maybe edge or noise).
 Above high threshold →Consider it as strong edge
 Between high & low thresholds→ Consider it as strong
weak edge
 Below low threshold → Consider it as not an edge
Applications
• Object segmentation in computer vision.
• Detecting boundaries in medical imaging.
• Feature extraction in machine learning applications.
import cv2
import numpy as np
import [Link] as plt

image = [Link]('inputs/[Link]',
cv2.IMREAD_GRAYSCALE)

# Canny edge detection (without blur)

edges = [Link](image, 100, 200)

[Link](figsize=(8, 5))
[Link](1, 2, 1)
[Link](image, cmap='gray')
[Link]('Original Image')
[Link]('off')

[Link](1, 2, 2)
[Link](edges, cmap='gray')
[Link]('Canny Edges')
[Link]('off')
 THRESHOLDING
•Thresholding is a widely used image segmentation technique in image
processing that converts a grayscale image I(x,y) into a binary image
B(x,y).
•The goal is to separate objects (foreground: important objects) from the
background(irrelevant areas) based on pixel intensity values.

The binary image B(x,y) is generated using the following rule:

where:
• I(x,y): Intensity of the pixel at location (x,y) in the grayscale
image.
• T: Threshold value.
• B(x,y): Resultant binary pixel value (1 for foreground, 0 for
Types of Thresholding:
[Link] Thresholding:
• A single threshold T is applied to the entire image.
• Suitable for images with uniform illumination.

[Link] Thresholding:
• The threshold T is computed locally for smaller regions of the
image. Each region gets its own threshold.
where 𝑓 is a function of the local region's pixel
intensities.
• Useful for images with varying illumination.

• Automatically calculates the optimal threshold 𝑇 by minimizing

[Link]’s Method:

intra-class variance.
𝑇 where the
• We divide all pixels into two classes: Background (class 0),
Picks Foreground two
(class 1)classes
(foreground/background) are most
Find Optimal Threshold

Gray Level 10 20 30 40 50
Frequency 8 11 13 7 7

l pixels N=46
l calculate σ²w(T) for each threshold T=10,20,30,40 and
ose the T for which σ²w is minimum.
 Threshold T = 10

+ Class 0: [10]  frequency = 8

Since all pixels in this class have the same value (10):

+ Class 1: [20, 30, 40, 50]  frequency = 38


 Threshold T = 20

+ Class 0: [10,20]  frequency = 19

+ Class 1: [30, 40, 50]  frequency = 27


Threshold T = 30

+ Class 0: [10,20,30]  frequency = 32

+ Class 1: [40, 50]  frequency = 14


 Threshold T = 40

+ Class 0: [10,20,30,40]  frequency = 39

+ Class 1: [50]  frequency = 7


 Threshold
T
σ²w
10 81.10
20 50.65
30 54.63
40 86.42
The minimum σ²w occurs at T = 20, making it the optimal threshold.

Point, Line, and Edge Detection are Discontinuous Operations, Because

they respond to abrupt intensity jumps. Mathematically, they rely on
derivatives, which react strongly at discontinuities.
Global Thresholding (including Otsu) and Adaptive Thresholding are
continuous methods.
• They do not detect sudden changes in intensity.
• They do not use derivatives or masks for discontinuity detection.
• They compute a threshold using continuous statistical measures
Thresholding is an essential image segmentation technique
but is sensitive to factors like noise, illumination, and
acceptance. To ensure robust performance:
• Noise should be minimized using filters.
• Illumination variations should be corrected using
normalization or adaptive methods.
• The threshold value must be optimally selected to
balance detail retention and noise rejection.
Mathematical models like Otsu’s method, adaptive
thresholding, and morphological operations enhance the
effectiveness of thresholding under challenging conditions.
 IMAGE SEGMENTATION BY REGION GROWING &
REGION SPLITTING & MERGING
Image segmentation divides an image into meaningful regions based on
certain characteristics such as intensity, texture, or color. Among segmentation
techniques, region growing and region splitting and merging are widely used
methods based on pixel connectivity and region homogeneity.
1. Region Growing
Region growing is a pixel-based image segmentation method that starts with a
set of seed points and grows regions by appending neighboring pixels that satisfy a
predefined similarity criterion. It works by grouping pixels with similar properties
(e.g., intensity, color, or texture).
Algorithm
1. Initialization:
 Select one or more seed points manually or automatically.
 Define a similarity criterion, such as intensity difference ∣I(x,y)−Iseed∣<T,
where T is a threshold.
2. Region Growing:
 For each seed point, evaluate its neighboring pixels.
 Add a neighboring pixel to the region if it satisfies the similarity criterion.
import cv2
import numpy as np
from collections import deque
from matplotlib import pyplot as plt

# Load the grayscale image

image = [Link]('inputs/[Link]',
cv2.IMREAD_GRAYSCALE)
height, width = [Link]

segmented = [Link]((height, width), dtype=np.uint8)

visited = [Link]((height, width), dtype=bool)

seed_x, seed_y = 100, 100

seed_value = image[seed_y, seed_x]

threshold = 10
queue = deque()

[Link]((seed_x, seed_y))
while queue:
x, y = [Link]()
if visited[y, x]:
continue
visited[y, x] = True
current_value = image[y, x]
if abs(int(current_value) - int(seed_value)) <= threshold:
segmented[y, x] = 255 # Mark pixel in region
if x > 0:
[Link]((x - 1, y))
if x < width - 1:
[Link]((x + 1, y))
if y > 0:
[Link]((x, y - 1))
if y < height - 1:
[Link]((x, y + 1))
[Link](1, 2, 1)
[Link](image, cmap='gray')
[Link]('Original Image')
[Link]('off')
[Link](1, 2, 2)
[Link](segmented, cmap='gray')
[Link]('Segmented Region')
[Link]('off')
[Link]()
Mathematical Representation:
Let R represent a growing region, and P(x,y) be a pixel in the image. The
condition for a pixel to be added to R is:

Advantages:
• Produces connected regions.
• Can handle noisy images with proper seed selection and thresholds.
Disadvantages:
• Sensitive to seed selection.
• Computationally expensive for large images.
• Poor performance if the regions have varying intensity.

2. Region Splitting and Merging

Region splitting and merging is a hierarchical segmentation method that divides
an image into smaller regions (splitting) and combines adjacent regions (merging)
based on a homogeneity criterion.
Algorithm
[Link]:
• Start with the entire image as a single region.
 [Link] Splitting:
• If a region does not satisfy the homogeneity criterion, split it
into four quadrants (quad-tree decomposition).
[Link] Merging:
• Merge adjacent regions if their combined region satisfies the
homogeneity criterion.
[Link]:
• Stop when no further splitting or merging is possible.
Mathematical Representation:

• Splitting: If 𝐻(𝑅)>𝑇, split 𝑅 into subregions 𝑅1, 𝑅2, 𝑅3, 𝑅4.

Let R be a region and H(R) the homogeneity criterion (e.g., variance):

• Merging: If 𝐻(𝑅𝑖∪𝑅𝑗)≤𝑇, merge regions 𝑅𝑖 and 𝑅𝑗.

Advantages:
• Does not depend on seed points.
• Combines global and local analysis for better segmentation.
Disadvantages:
• Computationally intensive.
The splitting technique has a convenient representation in the form of
a structure called a quadtree as shown in Fig. below.
In a quadtree, the root of the tree corresponds to the entire image and
each node corresponds to a subdivision.
Assuming the Seed pixel as Center Pixel and T=2

Pixel Intensity |Intensity-7| Within Threshold

(row,col) (≤2)?
(1,1) 1 6 ❌ No
(1,2) 0 7 ❌ No
(1,3) 7 0 Yes
(1,4) 8 1 Yes
(1,5) 7 0 Yes
(2,1) 0 7 ❌ No
(2,2) 1 6 ❌ No
(2,3) 8 1 Yes
(2,4) 9 2 Yes
(2,5) 8 1 Yes
(3,1) 0 7 ❌ No
 Pixel Intensity |Intensity-7| Within Threshold (≤2)?
(row,col)
(3,2) 0 7 ❌ No
(3,3) 7 0 Yes
(3,4) 9 2 Yes
(3,5) 8 1 Yes
(4,1) 0 7 ❌ No
(4,2) 1 6 ❌ No
(4,3) 8 1 Yes
(4,4) 8 1 Yes
(4,5) 9 2 Yes
(5,1) 1 6 ❌ No
(5,2) 2 5 ❌ No
(5,3) 8 1 Yes
(5,4) 8 1 Yes
(5,5) 9 2 Yes
First, the image is split up into four
regions R1, R2 , R3, and R4.
 Then the regions which are homogenous
are merged together.
 In this case, the regions R1 and R3 are
homogeneous.
Similarly, the regions R2 and R4 are
homogeneous.
First, the input image is split into four regions R1, R2, R3
and R4.
 Only two homogeneous regions are identified which are
R1 and R4.
 Hence, the regions R1 and R4 are not disturbed.
 The regions to be splitted further are R2 and R3.
After this step, the homogeneous regions are
merged together.

Quadtree representation
ple 3: Apply the split-and-merge technique for the given image

Result after first iteration

Result after second iteration

mage after third iteration

Quadtree representation
 Split the Region R in to four 4x4quadrants
• R11(Top-Left),
• R12(Top-Right),
• R13(Bottom Left),
• R14(Bottom Right)

Split If the difference between the darkest and brightest pixels in a

region (max − min) ≤ 3
R11)
Max=7, Min=4  Difference=3R12)
(≤T)
Max=6, Min=1 → Difference=5 (>T)
→ No need to split
→ Split this into 4 smaller (2×2) par

R13)
Max=3, Min=0 → Difference=3R14)
(≤T) Max=7, Min=0 → Difference=7 (>T)
→ No need to split → Split into 4 smaller (2×2) parts
 Split R12)

Split R14)

egion Count = 2(4x4 regions)+3(2*2 regions)+ 20(1*1 regions)

=25 regions
All 20 fragmented pixels must remain as 1*1 regions, because
merging any four of them back into a 2*2 regions immediately violates
the T<=3 rule.
 R2,1 region with in R12,
R4,3 or R4,4 region with in R1,4
can’t be merged with 1x1 regions, because the region splitting and merging
algorithm is hierarchical

No further merging is possible among the five large uniform

regions or the 20 individual pixels.
 Watershed algorithm
Assume a grayscale image like a mountain map with dark areas are called
valleys with slope, bright areas are mountains.
Assuming rain falls everywhere on this landscape with valleys and mountains.
• Water starts collecting in the lowest points/valleys (dark regions).
• Each valley gets filled with water, these are called catchment basins.
A marker is simply a starting point (seed). “marker 1”, “marker 2”, and
“marker 3” are initial pixels placed in low regions (valleys).
 As the rain continues, water level in each basin rises upward, At some
point, two basins get close to each other
When the water from two different basins is about to merge, you build
a dam between them so that the waters don’t mix. That dam is the
boundary between two regions in the image.
After the whole area is filled and all dams are built, you’ll see:
• The water regions are the segments or objects
Symb
Meaning
• The dams are the boundaries between objectsol
(s,t) Coordinates of a pixel
All the pixels that are below the water g(s,t)
Grayscale intensity (height) at
that pixel
level n are already submerged.
n Current water level
T[n] represents the flooded region at
The set (or collection) of all
that stage. T[n] pixels where height < current
water level
M1, M2,M3….MR are the lowest valleys, where water will start filling
here first.
represent the part of the flooded area that still belongs to this valley
 Union of all basins at stage n

Let q be a new connected component of T[n] where to basins

meet each other.
If q∩C[n−1] ⊆ multiple basins (say Cn−1(Mi) and Cn−1​(Mj​)),
where basins meet.
If so, Consider that q as dam and treat it as a boundary between
Over-segmentation
Watershed uses all local minima as starting points for flooding.
segments
Even small noise (small pits) are treated as meaningful regions and
leads to over segmentation
Instead of letting the algorithm flood from every minimum, we
manually (or automatically) select only a few important minima
to start flooding.
These are called markers.
There are two types of markers:
Internal markers: Pixels that are definitely inside each object.