DIGITAL IMAGE PROCESSING
TUTORIAL 5
Image Segmentation
AGENDA
❑ Image Segmentation.
❑ Edge-based Approches (Canny Edge Detector).
❑ Region-based Approaches (Thresholding).
❑ Sheet 4.
Image Segmentation
➢ Image Segmentation
▪ Segmentation is to subdivide an image into its
constituent regions or objects.
▪ Typically, it is the first step in any automated
computer vision application.
▪ It is the association of a segment label with each
pixel
Image Segmentation Algorithms
➢ Discontinuity of Intensity (Edge-based) Approaches
▪ Use the boundaries of regions to segment the
image → edge detection
➢ Similarity of Intensity (Region-based) Approaches
▪ Use similarity among pixels to partition an image
into regions according to a set of predefined
criteria. → thresholding
Discontinuity of Intensity (Edge-based) Approaches
➢ Discontinuity Sources
▪ Point Detection.
▪ Line Detection.
▪ Edge Detection.
➢ Discontinuity Detectors
▪ First Derivative (Gradient).
▪ Second Derivative (Laplacian).
Point Detection
➢ Point Detection
▪ A point is detected at the location (x,y) on which
the mask is centered if the absolute value of the
response of the mask at that point exceeds a
specified threshold (between 7 x 255 and 8 x 255).
Line Detection
➢ Line Detection
▪ To detect lines in specified directions.
▪ The preferred direction of each mask is weighted with a larger
coefficient (i.e., 2) than other possible directions.
▪ The coefficients in each mask sum to zero, indicating a zero
response in areas of constant intensity.
▪ Threshold can be set to a value between 5 x 255 and 6 x 255.
Edge Detection
➢ Edge Detection
▪ Edges correspond to sharp changes of intensity
➢ Edge Models
Edge Detectors
➢ First Derivative (Gradient)
An edge is detected by local max or local min
in the magnitude of the first derivative.
➢ Second Derivative (Laplacian)
An edge is detected by zero-crossing in the
second derivative.
First Derivative (Gradient)
➢ First Derivative Operators (Filter)
1. Roberts → mag = | First filter result | + | Second filter result |
2. Prewitt
3. Sobel
▪ Sobel operators is a joint
Gaussian smoothing plus Sobel mask for detecting horizontal and vertical edges Prewitt mask for detecting horizontal
and vertical edges
differentiation
operation, so it is more
resistant to noise.
Sobel mask for detecting diagonal edges Prewitt mask for detecting diagonal edges
First Derivative (Gradient)
➢ First Derivative Rules
f
Gx x
f = = f
G y
y
▪ The direction of the edge is perpendicular to
the direction of the gradient.
▪ The gradient gives the direction of maximal
growth of the image function from black to
white
Second Derivative (Laplacian)
➢ Second Derivative Operators (Filter)
3. Laplacian also known as Laplacian of
Gaussian (LoG).
Laplacian mask for detecting edges
Effect of noise
Derivative-based edge detectors are extremely sensitive to noise.
Image Smoothing
▪ Image smoothing should be a serious consideration prior to the use of derivatives in
applications where noise is likely to be present.
▪ Signal (f).
▪ Gaussian mask.
▪ Smoothed signal
by Gaussian.
▪ Gradient of
smoothed signal.
Derivative Theorem of Convolution
▪ Signal (f).
▪ Gradient of
Gaussian mask.
▪ Result of applying
gradient of
Gaussian mask.
Derivative Theorem of Convolution
▪ Signal (f).
▪ Laplacian of
Gaussian mask.
▪ Result of applying
Laplacian of
Gaussian mask.
Gaussian Function
▪ Gaussian function is represented
by:
▪ Sigma is called spread, scale or
width of Gaussian mask.
▪ The higher the value of sigma,
the smoother the resulting
image.
➢ Effect of sigma on derivatives
▪ Small sigma detects fine features.
▪ Large sigma detects large scale
edges.
Optimal Edge Detection
1. Good Detection
▪ Minimize the probability of false positive
(detecting spurious edges caused by noise).
▪ Minimize the probability of false negative
(missing real edges).
2. Good Localization
▪ Edges must be detected as close as possible to
the true edges.
3. Single Response Constraint
▪ Minimize the number of local maxima around
the true edge.
Canny Edge Detector
It satisfies the three previous objectives of an optimal edge detector through:
1. Noise Filtering.
2. Finding intensity gradient of images.
3. Non-maximum suppression.
▪ Thin multi‐pixel wide down to single pixel width.
4. Hysteresis Thresholding.
▪ Define two thresholds: low and high.
▪ Use the high threshold to start edge curves and the low threshold to continue them.
1. Noise Filtering
▪ Remove the noise in the image with a Gaussian filter.
As edge detection is sensitive to noise in the image
2. Finding Intensity Gradient
▪ Compute the x and y derivatives of the smoothed image.
Compute the gradient magnitude and direction.
Noise Filtering + Finding Intensity Gradient
The derivative theorem of convolution can be used to perform
the noise filtering and intensity gradient.
The derivative of Gaussian is the Sobel filter.
3. Non-Maximum Suppression
▪ Check if each pixel is a local maximum in its
neighborhood in the direction of gradient.
➢ Example:
▪ Point A is on the edge ( in vertical direction).
Gradient direction is normal to the edge.
Point B and C are in gradient directions.
So, point A is checked with point B and C to see if
it forms a local maximum. If so, it is considered
for next stage, otherwise, it is suppressed (put to
zero).
4. Hysteresis Thresholding
▪ Decide which are really edges and which are not.
▪ Define two threshold values, low threshold (minVal) and high threshold (maxVal).
1. Edges with intensity gradient more than maxVal are “sure-edge” pixels.
2. Edges below minVal are sure to be non-edges, so discarded.
3. Edges that lie between these two thresholds are classified edges or non-edges based
on their connectivity.
If they are connected to “sure-edge” pixels, they are considered to be part of edges.
➢ Example:
▪ Edge A is “sure-edge”.
▪ Edge C is connected to edge A, it is considered part of the edge.
▪ Edge B isn’t connected to “sure-edge” pixels, it is discarded.
Similarity of Intensity (Region-based) Approaches
➢ Thresholding
1. Global Thresholding.
2. Adaptive Thresholding.
3. Optimal Global Adaptive Thresholding.
1. Global Thresholding
➢ Algorithm
▪ Based on visual inspection of histogram:
1. Select an initial estimate for T.
2. Segment the image using T.
This will produce two groups of pixels: G1 consisting of all pixels with gray
level values > T and G2 consisting of pixels with gray level values <= T.
3. Compute the average gray level values u1 and u2 for the pixels in regions G1
and G2.
4. Compute a new threshold value: T = (u1 + u2 )/2.
5. Repeat steps 2 through 4 until the difference in T in successive iterations is
smaller than a predefined parameter ϵo .
Illumination Effect
➢ Conditions
▪ The addition of the shading pattern to the image corrupt the histogram.
▪ The separation of the objects without additional processing is no longer possible.
2. Adaptive Thresholding
➢ Algorithm
1. Subdivide original image into small
areas (sub-images).
2. Utilize a different threshold to
segment each sub-image.
▪ As the threshold used for each pixel
depends on the location of the pixel
in terms of the sub-image, this type
of thresholding is adaptive.
▪ In the shown example, a better result
can be obtained by dividing the
image to smaller sub-images.
3. Optimal Global Adaptive Thresholding
▪ It is like basic global thresholding but
automatically calculates a threshold value
from image histogram for a bimodal image
using probability.
Question 1
Question 1
Question 2
Question 2
▪ The filter yields 0 if it is centered on a pixel of an unbroken 3-pixel segment
oriented in the direction favored by that filter.
▪ The filter yields +2 when a mask is centered on a one-pixel gap in a 3-pixel
segment oriented in the direction favored by that filter.
Question 3
Question 3
Question 3
Question 4
Question 4
Question 5
▪ Non-maximum suppression:
Thin multi‐pixel wide down to single pixel width. (Good Localization)
▪ Hysteresis Thresholding:
Define two thresholds: low and high.
Use the high threshold to start edge curves and the low threshold to continue
them. Thus, it is used to detect the best edges. (Good Detection)
Question 6
▪ It is not suitable if the histogram of image doesn’t clearly separate between
different objects for example due to illumination effects.
▪ To solve it, we can apply adaptive thresholding in which the image is divided
into sub-images and thresholding is applied to each sub-image separately.