Unit-6

Morphological image processing: preliminaries Erosion and dilation, opening and closing, the Hit-or-miss transformation, some
Basic Morphological algorithms, grey –scale morphology
Image segmentation: Fundamentals, point, line, edge detection thresholding, region –based segmentation, segmentation using
Morphological watersheds, the use of motion in segmentation.

Morphological image processing

Introduction

► Morphology: a branch of biology that deals with the form and structure of animals and plants

► Morphological image processing is used to extract image components for representation and description of region shape,
such as boundaries, skeletons, and the convex hull
► Reflection

The reflection of a set B , denoted B, is defined as

► Translation

The translation of a set B by point z (z1,z2) denoted (B )Z , is defined as

GVPCEW DIGITAL IMAGE PROCESSING Page 1

 Example: Reflection and Translation

► Structure elements (SE)

Small sets or sub-images used to probe an image under study for properties of interest
Examples: Structuring Elements (1)

GVPCEW DIGITAL IMAGE PROCESSING Page 2

 Erosion

With A and B as sets in Z2 , the erosion of A by B , denoted defined as

The set of all points z such that B, translated by z, is contained by A.

Example of Erosion

GVPCEW DIGITAL IMAGE PROCESSING Page 3

 Dilation

With A and B as sets in Z2 , the dilation of A by B , denoted

defined as

Examples of Dilation

GVPCEW DIGITAL IMAGE PROCESSING Page 4

 Duality
► Erosion and dilation are duals of each other with respect to set complementation and reflection

and

Opening and Closing

► Opening generally smoothes the contour of an object, breaks narrow isthmuses, and eliminates thin protrusions

► Closing tends to smooth sections of contours but it generates fuses narrow breaks and long thin gulfs, eliminates small holes,
and fills gaps in the contour

The opening of set A by structuring element B, denoted A○ B, is defined as

GVPCEW DIGITAL IMAGE PROCESSING Page 5

The closing of set A by structuring element B, denoted A ● B, is defined as

A ●B

Example: Opening

Example: Closing

GVPCEW DIGITAL IMAGE PROCESSING Page 6

 The Hit-or-Miss Transformation

If B denotes the set composed of D and its background, the match (or set of matches) of B in A, denoted ,

Example:

GVPCEW DIGITAL IMAGE PROCESSING Page 7

 Some Basic Morphological Algorithms

► Boundary Extraction
The boundary of a set A, can be obtained by first eroding A by B and then performing the set difference between A and its
erosion.

Example

GVPCEW DIGITAL IMAGE PROCESSING Page 8

 ► Hole Filling
A hole may be defined as a background region surrounded by a connected border of foreground pixels.

Let A denote a set whose elements are 8-connected boundaries, each boundary enclosing a background region (i.e., a hole).
Given a point in each hole, the objective is to fill all the holes with 1s.

1. Forming an array X0 of 0s (the same size as the array containing A), except the locations in X0 corresponding to the
given point in each hole, which we set to 1.
2.

Stop the iteration if Xk = Xk-1

Example

GVPCEW DIGITAL IMAGE PROCESSING Page 9

 ► Extraction of Connected Components
Central to many automated image analysis applications.
Let A be a set containing one or more connected components, and form an array X0 (of the same size as the array containing
A) whose elements are 0s, except at each location known to correspond to a point in each connected component in A, which
is set to 1.

B: Structurimg Element
Example:

GVPCEW DIGITAL IMAGE PROCESSING Page 10

 ► Convex Hull
A set A is said to be convex if the straight line segment joining any two points in A lies entirely within A.

The convex hull H or of an arbitrary set S is the smallest convex set containing S.

Let B i , i=1, 2, 3, 4, represent the four structuring elements.

The procedure consists of implementing the equation:

with X 0i=A.
When the procedure converges, or X ki = X ki-1, let Di= X ki
the convex hull of A is

GVPCEW DIGITAL IMAGE PROCESSING Page 11

Example

► Thinning
The thinning of a set A by a structuring element B, defined

► A more useful expression for thinning A symmetrically is based on a sequence of structuring elements:

GVPCEW DIGITAL IMAGE PROCESSING Page 12

 Example:

GVPCEW DIGITAL IMAGE PROCESSING Page 13

 Image segmentation

Fundamentals

► Let R represent the entire spatial region occupied by an image. Image segmentation is a process that partitions R into
n sub-regions, R1, R2, …, Rn, such that

GVPCEW DIGITAL IMAGE PROCESSING Page 14

 Background

► First-order derivative

► Second-order derivative

GVPCEW DIGITAL IMAGE PROCESSING Page 15

 Characteristics of First and Second Order Derivatives

► First-order derivatives generally produce thicker edges in image

► Second-order derivatives have a stronger response to fine detail, such as thin lines, isolated points, and noise

► Second- order derivatives produce a double-edge response at ramp and step transition in intensity

The sign of the second derivative can be used to determine whether a transition into an edge is from light to dark or
dark to light

Detection of Isolated Points

► The Laplacian

GVPCEW DIGITAL IMAGE PROCESSING Page 16

 Line Detection

► Second derivatives to result in a stronger response and to produce thinner lines than first derivatives

► Double-line effect of the second derivative must be handled properly

GVPCEW DIGITAL IMAGE PROCESSING Page 17

 Detecting Line in Specified Directions

► Let R1, R2 , R3, and R4 denote the responses of the masks. If, at a given point in the image, |Rk|>|Rj|, for all j≠k, that point is said to be
more likely associated with a line in the direction of mask k.

GVPCEW DIGITAL IMAGE PROCESSING Page 18

 Edge Detection

► Edges are pixels where the brightness function changes abruptly

► Edge models

GVPCEW DIGITAL IMAGE PROCESSING Page 19

 Basic Edge Detection by Using First-Order Derivative

GVPCEW DIGITAL IMAGE PROCESSING Page 20

GVPCEW DIGITAL IMAGE PROCESSING Page 21
GVPCEW DIGITAL IMAGE PROCESSING Page 22
 Advanced Techniques for Edge Detection

► The Marr-Hildreth edge detector

GVPCEW DIGITAL IMAGE PROCESSING Page 23

 Marr-Hildreth Algorithm

1. Filter the input image with an nxn Gaussian lowpass filter. N is the smallest odd integer greater than or equal to 6

2. Compute the Laplacian of the image resulting from step1

3. Find the zero crossing of the image from step 2

The Canny Edge Detector

► Optimal for step edges corrupted by white noise.

► The Objective

► Low error rate

The edges detected must be as close as possible to the true edge

Edge points should be well localized

The edges located must be as close as possible to the true edges
Single edge point response
The number of local maxima around the true edge should be minimum

GVPCEW DIGITAL IMAGE PROCESSING Page 24

 The Canny Edge Detector: Algorithm
Let f ( x , y) denote the input image and G (x , y) denote the Gaussian function:

We form a smoothed image,fs ( x , y ) by convolving G and f:

The Canny Edge Detector: Algorithm

The gradient M (x , y) typically contains wide ridge around local maxima. Next step is to thin those ridges.
Nonmaxima suppression:
Let d1 , d 2 , d 3 , and d4 denote the four basic edge directions for a3X 3 region: horizontal, -45o , vertical,+45 , respectively.
1. Find the direction d k that is closest to α(x , y).
2. If the value of M (x , y) is less than at least one of its two neighbors along d k , let g N (x , y)=0 (suppression);
otherwise, let g N (x , y )=M (x , y)

GVPCEW DIGITAL IMAGE PROCESSING Page 25

 The final operation is to threshold g N (x , y) to reduce false edge points.

Hysteresis thresholding:

g NH (x , y ) = g N (x , y ) > TH
g NL (x , y ) = g N (x , y ) > TL

and
g NL (x , y ) = g NL (x, y ) - g NH (x , y)

GVPCEW DIGITAL IMAGE PROCESSING Page 26

 Depending on the value of TH , the edges in g NH (x , y) typically have gaps. Longer edges are formed
using the following procedure:
(a). Locate the next unvisited edge pixel, p , in g NH (x , y).
(b). Mark as valid edge pixel all the weak pixels in g NL (x , y) that are connected to p using 8-connectivity.
(c). If all nonzero pixel in g NH (x , y) have been visited go to step (d), else return to (a).
(d). Set to zero all pixels in g NL (x , y) that were not marked as valid edge pixels.

The Canny Edge Detection: Summary

► Smooth the input image with a Gaussian filter

► Compute the gradient magnitude and angle images

► Apply nonmaxima suppression to the gradient magnitude image

► Use double thresholding and connectivity analysis to detect and link edges

GVPCEW DIGITAL IMAGE PROCESSING Page 27

 Region-Based Segmentation

► Region Growing
► Region growing is a procedure that groups pixels or subregions into larger regions.
► The simplest of these approaches is pixel aggregation, which starts with a set of “seed ” points and from these grows
regions by appending to each seed points those neighboring pixels that have similar properties (such as gray level, texture,
color, shape).
Region growing based techniques are better than the edge-based techniques in noisy images where edges are difficult to
detect.

Example: Region Growing based on 8-connectivity

f(x , y) : input image array

S (x , y): seed array containing 1s (seeds) and 0s
Q ( x , y): predicate

1. Find all connected components in S ( x, y) and erode each connected components to one pixel; label all such
pixels found as 1. All other pixels in S are labeled 0.
2. Form an image fQ such that, at a pair of coordinates (x,y),
let f Q (x , y )=1 if the Q is satisfied otherwise f Q (x , y)=0.

GVPCEW DIGITAL IMAGE PROCESSING Page 28

 3. Let g be an image formed by appending to each seed point in S all the 1-value points in fQ that are 8-connected to that
seed point.
4. Label each connected component in g with a different region label. This is the segmented image obtained by region growing.

GVPCEW DIGITAL IMAGE PROCESSING Page 29

 Region Splitting and Merging

R : entire image
Ri :region
Q: predicate

1. For any region Ri , If Q ( Ri ) = FALSE, we divide the image Ri into quadrants.

2. When no further splitting is possible, merge any adjacent regions R j and Rk for which Q ( R j Rk ) = TRUE.
3. Stop when no further merging is possible.

GVPCEW DIGITAL IMAGE PROCESSING Page 30