Image Segmentation

• Module – 4 Image Segmentation:

• Introduction, Detection of isolated points, line detection,
• Edge detection, Edge linking,
• Region based segmentation- Region growing,
• split and merge technique,
• local processing, regional processing,
• Hough transform,
• Segmentation using Threshold.
8 Hours

Aug 6, 2025 1
 Image Segmentation
• Introduction:

• So far we saw image processing methods whose input and output are images,
but now let us see those methods in which the inputs are images, but the
outputs are attributes extracted from those images

• Segmentation subdivides an image into its constituent regions or objects.

• The level to which the subdivision is carried depends on the problem being
solved.
• Segmentation should stop when the objects of interest have been isolated.

Aug 6, 2025 2
• Segmentation accuracy determines the eventual success or failure of
computerized analysis procedures.

• Hence, care should be taken to improve the probability of segmentation.

Aug 6, 2025 3
 Image Segmentation
• In industrial inspection applications, at least some measure of control over the environment is
possible at times.

• The experienced image processing system designer invariably pays considerable attention to such
opportunities.
• Let 𝑅 represent the entire image. Segmentation is a process that divides 𝑅 into 𝑛 subregions 𝑅1 , 𝑅2 ,
… , 𝑅𝑛 such that:

• 1. 𝑅𝑖 𝑛 𝑖=1 = 𝑅.

• 2. 𝑅𝑖 is a connected set for each 𝑖 = 1, 2, … , 𝑛.

• 3. 𝑅𝑖 ∩ 𝑅𝑗 = ∅ for all 𝑖 and 𝑗, 𝑗 ≠ 𝑖.

• 4. 𝑄 𝑅𝑖 = 𝑇𝑅𝑈𝐸 for each 𝑖 = 1, 2, … , 𝑛.

• 5. 𝑄 𝑅𝑖 ∪ 𝑅𝑗 = 𝐹𝐴𝐿𝑆𝐸 for any adjacent regions 𝑅𝑖 and 𝑅𝑗 . Here 𝑄 𝑅𝑘 is a predicate that indicates
Aug 6, 2025 4
 Image Segmentation
• In other applications, such as autonomous target acquisition, the system designer
has no control of the environment.

• Then the usual approach is to focus on selecting the types of sensors which could
enhance the objects of interest while diminishing the contribution of irrelevant
image detail.

• E.g. : the use of infrared imaging by the military to detect objects with strong
heat signatures, such as equipment and troops in motion.

Aug 6, 2025 5
 Image Segmentation
• Image segmentation algorithms are based on one of two basic properties of intensity
values:
• Discontinuity and
• Similarity.

• Discontinuity:

• Approach is to partition an image based on abrupt changes in intensity, such as edges in

an image.

• Similarity:

• These are based on partitioning an image into regions that are similar according to a set
of predefined criteria. Aug 6, 2025 6
• The segmentation algorithms for monochrome images are based on either
discontinuity or similarity of pixel intensities

• In first category assumption is that boundaries of regions are sufficiently

different from each other and from the background to allow boundary
detection based on local intensity discontinuity

• E.g. Edge based segmentation

• In the second category, idea is to partition the image into regions that are
similar according to a set of predefined criteria.

• E.g.: region based segmentation

Aug 6, 2025 7
Image Segmentation

Aug 6, 2025 8
• (a) shows an image having a region of constant intensity superimposed on darker
background.

• These two region comprise the entire image

• (b) shows the result of computing boundary of the inner region based on intensity
discontinuity

• Points inside and outside the boundary are zero because there are no discontinuities
in those regions.

• To segment the image, we assign one level (say white) to the pixels on or interior
to boundary and another level (black) to the pixels exterior to boundary
Aug 6, 2025 9
 Image Segmentation

• These three images represent region based segmentation

• In first image inner region intensities form texture pattern

Aug 6, 2025 10
• Next figure shows the result of computing edges of the previous image

• Due to the continuously varying intensities it is difficult to detect unique

boundary. Thus edge based segmentation is not suitable

• But we see that, outer region is of uniform intensities

• So to do segmentation, we need to differentiate between constant region and

textured region

Aug 6, 2025 11
• We may compute standard deviation of pixels to achieve this

• This is because, SD is non-zero in texture region and zero in constant region

• The original image may be subdivided into region of 4X4 and labeled white if
the SD of the pixels are positive and zero otherwise.

• This can be seen as shown in the figure

Aug 6, 2025 12
• We know local changes in intensity can be detected using derivatives.

• For reasons that will become evident , first-and second-order derivatives

are particularly well suited for this purpose.

Aug 6, 2025 13
• Background:
• Basics of derivatives
• The rules to be satisfied
• Equations for first and second order derivatives

• E.g.:

Aug 6, 2025 14
Image Segmentation

Aug 6, 2025 15
 Image Segmentation
• Figure has
• Solid objects, straight line and single noise point
• Horizontal Intensity profile of a scan line is shown in (b)
• We can notice ramp edges and step edges
• (c) shows how simplified view of profile to analyze numerically how 1 st and 2nd
order derivatives behave as they encounter noise point, line and edge
• Transition in ramp – 4 pixel,
• Transition on noise point – 1 pixel
• Transition on line 3 - pixels and
• Transition on step – adjacent pixels
• By using the properties of derivatives we can see that, first order derivative is non-
zero at the onset and along the ramp

Aug 6, 2025 16
• 2nd order derivative is non-zero only at the onset and end of the ramp

• Since the edges of digital images show this type of transition, we can say that 1st order
derivatives produce thick edges and second order derivatives produce fine edges

• For noise point, magnitude of 2nd order derivative is larger than 1st order derivative

• Reason is 2nd order derivatives are more capable of enhancing fine details

• Similar arguments hold good for line which is also thin in this case

• 2nd order derivative in both ramp and step has opposite signs as it transitions into and
out of edge.

• This double edge effect can be used to detect the edges.

Aug 6, 2025 17
• Using the segmentation methods we can extract three features – isolated points,
lines and edges

• Edge pixels are those at which intensity of an image function changes abruptly

• Edge - connected set of edge pixels.

• Edge detectors - local image processing methods used to detect edge pixels

• A line - an edge element, in which intensity of the background on the either

side of the line is either much larger or much lower than the line pixel intensity

Aug 6, 2025 18
• Detection of Discontinuities:
Three basic types of gray-level discontinuities in a digital image:
points,lines, and edges
• The most common way to look for discontinuities is to run a mask through the image
is by computing the sum of products of the coefficients with the gray levels
contained in the region encompassed by the mask,
• where Zi is the gray level of the pixel associated with mask coefficient W i

Aug 6, 2025 19
• Detection of isolated points
• Point detection could be based on 2nd derivative
• So we can use Laplacian equation seen earlier

• where partial derivatives are obtained as below

Aug 6, 2025 20
• Then the Laplacian will be

• This expression can be implemented using the mask (a) shown below

• (b) represents the mask with diagonal terms

Aug 6, 2025 21
• The detection of isolated points in an image is straightforward in
principle.

• we say that a point has been detected at the location on which the
mask is centered if
|R| > T
where T is a nonnegative threshold and R is given by

Aug 6, 2025 22
• Basically, this formulation measures the weighted differences between
the center point and its neighbors.

• The idea is that an isolated point (a point whose gray level is

significantly different from its background and which is located in a
homogeneous or nearly homogeneous area) will be quite different from
its surroundings, and thus be easily detectable by this type of mask.

Aug 6, 2025 23
• The output is obtained by using the expression

• where g is output image,

• T – non-negative threshold
• R is the response given by

Aug 6, 2025 24
• The Laplacian mask is as shown below

• Using this mask we can say that a point is detected at location (x, y) on which mask
is centered, if the absolute value of the response of the mask at that point exceeds the
specified threshold.

• All such points are labeled as 1 and all other are with 0 resulting in binary image

Aug 6, 2025 25
• Line detection:
• We have seen that, second order derivative produces stronger response and could
result in thinner line than 1st order derivative.
• Thus we can use Laplacian mask used for point detection here also

• But care is to be given to handle the double line effect similar to double edge of
point detection

Aug 6, 2025 26
• Laplacian mask seen earlier is isotropic- its response is independent of
directions (vertical, horizontal and two diagonals)
• But in reality lines may not be always in these four directions
• Consider the following masks

Aug 6, 2025 27
• Suppose that an image with constant background, containing various lines.

• If the first mask were moved around an image, it would respond more
strongly to lines (one pixel thick) oriented horizontally.

• The maximum response would occur at image locations where the

horizontal line is passed through the middle row of the mask

Aug 6, 2025 28
• Similarly second mask gives best response to line which are oriented +45°,
third mask for vertical lines and last mask for -45°.

• Let Rl, R2 , R3 , and R4 denote the responses of the masks in Fig. from left to
right, where the R's are given by

where zk is the gray level of the

pixel associated with mask
coefficient wk

Aug 6, 2025 29
• Suppose that the four masks are run individually through an image.

• If, at a certain point in the image, |Ri| > |Rj|, for all j != i, that point is said to be
more likely associated with a line in the direction of mask i.

Aug 6, 2025 30
• E.g.:

• if at a point in the image, |R1|> |Rj| for j = 2, 3, 4 that particular point is said to
be more likely associated with a horizontal line.

• Alternatively, we may be interested in detecting lines in a specified direction.

• In this case, we would use the mask associated with that direction and
threshold its output as per the equation .

Aug 6, 2025 31
• In other words, if we are interested in detecting all the lines in an image in
the direction defined by a given mask, we run the mask through the image
and threshold the absolute value of the result.

Aug 6, 2025 32
• Edge detection:
• Edge models:
• Classified according to their intensity profiles
• Step edge: transition between two intensities occur ideally over a distance of
one pixel
• Figure below shows the section of vertical step edge and horizontal intensity
profile along the edge

• These clean ideal edges occur over distance of 1 pixel

• They need no processing (smoothing) to make them look “real”

Aug 6, 2025 33
• Ramp edge: In practice, images contain edges that are blurred and noisy

• Degree of blurring depends on focusing mechanism such as lenses and degree of noise
depends on electronic components of imaging system

• In these cases, edges are modeled as ramp as shown below

• Here there will not be any thin path (1 pixel)

• Instead, edge point is any point contained in the ramp and edge segment would be set
of connected edge points.
• This makes sense: Blurred edges tend to be thick and sharp edges tend to be thin.
Aug 6, 2025 34
• Roof edge: These have characteristics as shown in figure below

• These are models of lines through a region with base of the roof edge is determined
by the thickness and sharpness of the line

• If the base thickness is 1 pixel, then edge will be one line running through the region

• E.g.: in range imaging, when thin objects are closer to the sensors than the
background. ( pipe and wall- pipes appear bright and create
Aug 6, 2025 35
• Note that, single image may contain all three types of edges

• There may be a little deviation from the ideal shape due to noise and blurring

• The ideal edge models discussed allow us to write mathematical expressions to

develop edge detection algorithms

• Performance of these algorithms depend on differences between actual edge

and the model used in developing algorithm

Aug 6, 2025 36
• Figure 10.6(b) shows a horizontal gray-level profile of the edge
between the two regions.

• This figure also shows the first and second derivatives of the gray-
level profile.

• The first derivative is positive at the points of transition into and out of
the ramp as we move from left to right along the profile: it is constant
for points in the ramp: and is zero in areas of constant gray level.

Aug 6, 2025 37
• The second derivative is positive at the transition associated with
the dark side of the edge, negative at the transition associated with
the light side of the edge, and zero along the ramp and in areas of
constant gray level.

• The signs of the derivatives in Fig. 10.6(b) would be reversed for an

edge that transitions from light to dark.

Aug 6, 2025 38
Aug 6, 2025 39
• We conclude from these observations that the magnitude of the first
derivative can be used to detect the presence of an edge at a point in an
image (i.e.. to determine if a point is on a ramp).

• Similarly, the sign of the second derivative can be used to determine

whether an edge pixel lies on the dark or light side of an edge.

Aug 6, 2025 40
• We note two additional properties of the second derivative around an edge:

(1) It produces two values for every edge in an image (an undesirable

feature):

and

(2) an imaginary straight line joining the extreme positive and negative values
of the second derivative would cross zero near the midpoint of the edge. This
zero-crossing property of the second derivative is quite useful for locating the
centers of thick edges

Aug 6, 2025 41
• Basic Edge Detection

• Gradient operators:

• The image gradient is used to find edge strength and direction at location (x,y) of
image, and defines as the vector.

• Gradient vector is always perpendicular to the edge direction .

Aug 6, 2025 42
• The magnitude(length)of vector ,denoted as M(x,y)

• This quantity gives the maximum rate of increase of f(x, y) per unit distance in the direction
of . It is a common (although not strictly correct) practice to refer to also as the
gradient.

• The direction of the gradient vector is given by the angle

• The direction of an edge at an arbitrary point (x, y) is orthogonal to the direction.

Aug 6, 2025 43
• Computation of the gradient of an image is based on obtaining the partial
derivatives ∂f/ ∂x and ∂f/ ∂y at every pixel location.

• Let the 3 x 3 area shown below represent the gray levels in a neighborhood
of an image.

Aug 6, 2025 44
• one of the simplest ways to implement a first-order partial derivative at
point z5, is to use the following Roberts cross-gradient operators:

Gx =(z9-z5) and Gy =(z8-z6)

• Masks of size 2 x 2 arc awkward to implement because they do not have a

clear center.
Aug 6, 2025 45
• An approach using masks of size 3 x 3 is given by
Gx =(z7 + z8 + z9) - (z1 + z2 + z3)
And
Gy =(z3 + z6 + z9) - (z1 + z4 + z7)

• In this formulation, the difference between the first and third rows of the 3
X 3 image region approximates the derivative in the x-direction,

• and the difference between the third and first columns approximates the
derivative in the y-direction.

Aug 6, 2025 46
• The masks called the Prewitt operators, can be used to implement these
two equations.

Aug 6, 2025 47
• A slight variation of these two equations uses a weight of 2 in the center
coefficient:
Gx =(z7 + 2z8 + z9) - (z1 + 2z2 + z3)
And
Gy =(z3 + 2z6 + z9) - (z1 + 2z4 + z7)

• A weight value of 2 is used to achieve some smoothing by giving more

importance to the center point.

• The Sobel operators, are used to implement these two equations.

Aug 6, 2025 48
• The Prewitt masks are simpler to implement than Sobel masks, but the
Sobel masks have better noise-suppression(smoothing) characteristics
makes them preferable.

Aug 6, 2025 49
• In the previous discussion, we just discuss to obtain the Gx and Gy.

• However, this implementation is not always desirable, so an approach used

frequently is to approximately the magnitude of the gradient by
absolute values.

• This equation is much more attractive computationally, and it still

preserves relative changes in gray levels.
Aug 6, 2025 50
Aug 6, 2025 51
• The Laplacian
• The Laplacian generally is not used in its original form for edge detection
for several reasons:

• As a second-order derivative, the Laplacian typically is unacceptably

sensitive to noise.

• The magnitude of the Laplacian produces double edges, an undesirable

effect because it complicates segmentation.

• Finally, the Laplacian is unable to detect edge direction.

Aug 6, 2025 52
• The Laplacian
• For these reasons, the role of the Laplacian in segmentation consists of

(1) Using its zero-crossing property for edge location, as mentioned earlier
in this section,

or (2) using it for the complementary purpose of establishing whether a pixel

is on the dark or light side of an edge

Aug 6, 2025 53
• The Laplacian
• For these reasons, the role of the Laplacian in segmentation consists of

(1) Using its zero-crossing property for edge location, as mentioned earlier
in this section,

or (2) using it for the complementary purpose of establishing whether a pixel

is on the dark or light side of an edge

Aug 6, 2025 54
• Advanced Edge detection
• The basic edge detection method is based on simple filtering without
taking note of image characteristics and other information.
• More advanced techniques make attempt to improve the simple
detection by taking into account factors such as noise, scaling etc.
• We introduce 2 techniques:
• Marr-Hildreth Edge Detector
• Canny Edge detector

Aug 6, 2025 55
• Marr and Hildreth argued that:
• Intensity of changes is not independent of image scale
• Sudden intensity change will cause a zero crossing of the second derivative
• Therefore, an edge detection operator should:
Be capable of being tuned to any scale
Be capable of computing the first and second derivatives

Aug 6, 2025 56
• The Marr-Hildreth edge detector/ Laplacian of Gaussian/
Mexican hat function

5x5 mask of LOG

Aug 6, 2025 57
• The Marr-Hildreth algorithm consists of convolving the LoG filter
with an input image, f(x,y)

• And then finding a zero crossing of g(x,y) to determine the locations

of edges in f(x,y).

• Because these are linear process, the above equation can be written
also as

Aug 6, 2025 58
• It’s edge-detection algorithm may be summarized as follow:

1. Filter the input image with an n x n Gaussian lowpass filter (It can
smooth the large numbers of small spatial details).

2. Compute the Laplacian of the image resulting from Step1.

3. Finding the zero crossings of the image from Step2.

Aug 6, 2025 59
 The Canny Edge Detector
• Three basic objectives:
1.Low error rate – Edge detected must be as close as possible to the true
edge.
2.Edge points should be well localized—The edges located must be as close
as possible to the true edges.ie the distance between a point marked as an
edge by the detector and the centre of the true edge should be minimum.
3.Single edge point response – The detector should return only one point for
each true edge point.ie number of local maxima around the true edge
should be minimum.The detector should not identify multiple edge pixels
where only a single edge point exists.

Aug 6, 2025 60
• Canny Edge algorithm consists of the following steps
1.Smooth the input image with a Gauussian filter.
2.Compare the Gradient magnitude and angle images.
3.Apply Nonmaxximum supression to the gradient magnitude image
4.Use double thresholding and connectivity analysis to detect and link edges.

Aug 6, 2025 61
• Step 2 – Compute Gradient
• locate the edges using direction of the point with the same method as
basic edge detection – gradient:

Step 3 – Nonmaxima suppression

Edges generated using gradient typically contain wide ridges around local
maxima.
Locate the local maxima using nonmaxima suppression method.
We will define a number of discrete orientations. For example in a 3x3 region
Aug 6, 2025 62
4 direction can be defined.
Aug 6, 2025 63
• Step 4 – Double Thresholding
• The received image may still contain false edge points.

• Let 𝑇𝐿 , 𝑇𝐻 be low and high thresholds. The suggested ratio is 1:3 or 2:3.
• We will reduce them using hysteresis (or double) thresholding.

• We will define 𝑔𝑁𝐻 𝑥, 𝑦 and 𝑔𝑁𝐿 𝑥, 𝑦 to be 𝑔𝑁 𝑥, 𝑦 after threshloding

it with 𝑇𝐿 , 𝑇𝐻.
• It is clear that 𝑔𝑁𝐿 𝑥, 𝑦 contains all the point located in 𝑔𝑁𝐻 𝑥, 𝑦 .
• We will separate them by substruction: 𝑔𝑁𝐿 𝑥, 𝑦 = 𝑔𝑁𝐻 𝑥, 𝑦 − 𝑔𝑁𝐿 𝑥,
𝑦 Now 𝑔𝑁𝐿 𝑥, 𝑦 and 𝑔𝑁𝐻 𝑥, 𝑦 are the “weak” and the “strong” edge
pixels.

Aug 6, 2025 64
• Edge Linking and Boundary Detection
• Ideally, the methods discussed in the previous section should yield pixels lying
only on edges.

• In practice, this set of pixels seldom characterizes an edge completely because

of noise, breaks in the edge from nonuniform illumination, and other effects
that introduce spurious intensity discontinuities.

• Thus edge detection algorithms typically are followed by linking procedures

to assemble edge pixels into meaningful edges and/or region boundaries.

Aug 6, 2025 65
• Local processing
• This edge linking is to analyze the characteristics of pixels in a small
neighborhood about every point(x,y) that has been declared an edge point by
previous techniques.

• The two principle properties used for establishing similarity of edge pixels are
1. the strength of the response of the gradient operator used to produce the edge
pixel
2. the direction of the gradient vector.

Aug 6, 2025 66
• Thus an edge pixel with coordinates (x0, y0) in a predefined neighborhood of (x, y) is
similar in magnitude to the pixel at (x, y) if

• where E is a nonnegative threshold.

• An edge pixel at (x0, y0) in the predefined neighborhood of (x, y) has an angle similar to
the pixel at (x. y) if

• where A is a nonnegative angle threshold.

• the direction of the edge at (x, y) is perpendicular to the direction of the gradient vector
at that point.
Aug 6, 2025 67
• A point in the predefined neighborhood of (x, y) is linked to the pixel at (x, y) if
both magnitude and direction criteria are satisfied.

• This process is repeated at every location in the image.

• A record must be kept of linked points as the center of the neighborhood is

moved from pixel to pixel.

• A simple bookkeeping procedure is to assign a different gray level to each set

of linked edge pixels.

Aug 6, 2025 68
 Edge Linking and Boundary Detection
Local Processing: Example

In this example,
we can find the
license plate
candidate after
edge linking
process.
• Regional processing
• Often, the location of regions of interest in an image are known or can be
determined.

• In such situations ,we can use techniques for linking pixels on a regional basis,
with the desired result being an approximation to the boundary of the region.

• We discuss the mechanics of the procedure using the following figure

illustration of the iterative polygonal fit algorithm

Aug 6, 2025 70
• The figure shows set of points representing an open curve having end points A
and B.

• Initially we compute the parameters of a straight line passing through A and B.

• Then compute the perpendicular distance from all other points in the curve to
this line and select the point that yielded maximum distance.

• If this distance exceeds a specified threshold, T, the corresponding point

labeled C, is declared a vertex.

Aug 6, 2025 71
• Lines from A to C and from C to B are then established, and distances from all
the points between A and C to line AC are obtained.

• If this distance exceeds a specified threshold, T, the corresponding point

labeled D, is declared a vertex.

• Similar procedure is applied to points between C and B.

Aug 6, 2025 72
Global processing using the Hough transform

• Here global relationships between pixels are considered.

• Given n points in an image, suppose that we want to find subsets of these

points that lie on straight lines.

• One possible solution is to first find all lines determined by every pair of
points and

• then find all subsets of points that are close to particular lines.

Aug 6, 2025 76
Global processing using the Hough transform

• The problem with this procedure is that it involves finding n(n - 1)/2
(approx. n2 ) lines and then performing (n)(n(n - 1))/2 (approx. n3)
comparisons of every point to all lines.

• This approach is computationally prohibitive.

Aug 6, 2025 77
Global processing using the Hough transform

• The problem with this procedure is that it involves finding n(n - 1)/2
(approx. n2 ) lines and then performing (n)(n(n - 1))/2 (approx. n3)
comparisons of every point to all lines.

• This approach is computationally prohibitive.

Aug 6, 2025 78
Aug 6, 2025 79
Global processing using the Hough transform

• Consider a point (xi, yi) and the general equation of a straight line in slope-intercept

form, yi = axi + b.

• Infinitely many lines pass through (xi, yi) ,but they all satisfy the equation yi = axi +
b. for varying values of a and b.

• However, writing this equation as b = -xia + yi, and considering the ab-plane (also

called parameter space) yields the equation of a single line for a fixed pair (x i, yi)
Aug 6, 2025 80
Aug 6, 2025 81
Global processing using the Hough transform

• Furthermore, a second point (xj ,yj) also has a line in parameter space associated with

it, and this line intersects the line associated with (x i, yi) at (a', b'), where a' is the

slope and b' the intercept of the line containing both (xi, yi) and (xj ,yj) in the xy-
plane.

• In fact, all points contained on this line have lines in parameter space that intersect at
(a', b').

• The computational attractiveness of the Hough transform arises from subdividing

the parameter space into so-called accumulator cells.

Aug 6, 2025 82
Aug 6, 2025 83
• At the end of this procedure, a value of Q in A(i, j) corresponds to Q points
in the xy-plane lying on the line y = aix + bj .

• The number of subdivisions in the ab-plane determines the accuracy of the

colinearity of these points.

Aug 6, 2025 84
Global processing using the Hough transform

• A problem with using the equation y = ax + b to represent a line is that the

slope approaches infinity as the line approaches the vertical.

• One way around this difficulty is to use the normal representation of a line:

Aug 6, 2025 85
Aug 6, 2025 86
Edge Linking and Boundary Detection
Hough Transform Example
The intersection of the curves
corresponding to points 1,3,5

2,3,4

1,4
Aug 6, 2025 88
Global processing using the Hough transform

An approach for edge linking based on the Hough transform is as follows:

1. Compute the gradient of an image and threshold it to obtain a binary image.

2. Specify subdivisions in the p theta-plane.

3. Examine the counts of the accumulator cells for high pixel concentrations.

4. Examine the relationship (principally for continuity) between pixels in a

Chosen cell.

5. Link these pixels if the gaps are smaller than the threshold.

Aug 6, 2025 89
Global Processing via Graph-Theoretic Techniques

• It is a global approach for edge detection and linking based on

representing edge segments in the form of a graph and searching the graph
for low-cost paths that correspond to significant edges.

• This representation provides a strong approach that performs well in the

presence of noise.

• But the procedure is considerably more complicated and requires more

processing time than the methods discussed so far.

Aug 6, 2025 90
• We begin the development with some basic definitions.

• A graph G = (N, U) is a finite nonempty set of nodes N, together with a set U

of unordered pairs of distinct elements of N.

• Each pair (ni,nj) of U is called an arc.

• A graph in which the arcs, are directed is called a directed graph, If an arc
is directed from node ni, to node nj.

• then nj, is said to be a successor of the parent node nj.

Aug 6, 2025 91
Aug 6, 2025 92
Global processing Via Graph
Theoretic Techniques
• A global approach for edge detection and linking
based on representing edge segments in the form of a
graph and searching the graph for low-cost paths that
correspond to significant edges.
• This representation provides a rugged approach that
performs well in the presence of noise.
• As might be expected,the procedure is considerably
more complicated and requires more processing time
than the methods discussed so far.
Aug 6, 2025 93
Aug 6, 2025 94
Aug 6, 2025 95
 A 3x3 Image region
Aug 6, 2025 96
Aug 6, 2025 97
Aug 6, 2025 98
Aug 6, 2025 99
Aug 6, 2025 100
Aug 6, 2025 101
Aug 6, 2025 102
Aug 6, 2025 103
Aug 6, 2025 104
Region-Based Segmentation
• Segmentation techniques that are based on finding the regions directly.
• Basic Formulation
• Let R represent the entire image region.
• We may view segmentation as a process that partitions R into n subregions,
R1 , R2, ... , Rn , such that

Aug 6, 2025 105

Region-Based Segmentation
• Condition (a) indicates that the segmentation must be complete; that is. Every pixel must
be in a region.

• Condition (b) requires that points in a region must be connected in some predefined sense

• Condition (c) indicates that the regions must he disjoint.

• Condition (d) deals with the properties that must be satisfied by the pixels in a segmented
region-for example

• P( Ri,) = TRUE if all pixels in Rj have the same gray level. Finally, condition

• (e) indicates that regions Ri, and Rj, are different in the sense of predicate P.

Aug 6, 2025 106

• As its name implies region growing is a procedure that groups pixels or
subregions into larger regions based on predefined criteria.

• The basic approach is to start with a set of "seed" points and from these grow
regions by appending to each seed those neighboring pixels that have
properties similar to the seed.

Aug 6, 2025 107

• Step1. Selecting a set of one or more starting point (seed) often can be based
on the nature of the problem.

• Step2. The region are grown from these seed points to adjacent point
depending on a threshold or criteria(8-connected) we make.

• Step3. Region growth should stop when no more pixels satisfy the criteria
for inclusion in that region

Aug 6, 2025 108

Figure 3.1(a)Original image (b)Use step 1 to find seed based on the nature problem.(c) Use
Step 2(4-connected here)to growing the region and finding the similar point. (d)(e) repeat
Step 2. Until no more pixels satisfy the criteria. (f) The final image.
Aug 6, 2025 109
• We briefly conclude the advantages and disadvantages of region growing.

• Advantages ：

• 1. Region growing methods can correctly separate the regions that have the same properties
we define.

• 2. Region growing methods can provide the original images which have clear edges the good
segmentation results.

• 3. The concept is simple. We only need a small numbers of seed point to represent the
property we want, then grow the region.

• 4. We can choose the multiple criteria at the same time.

• It performs well with respect to noise, which means it has a good shape matching of its result.

Aug 6, 2025 110

• Disadvantage ：

• 1. The computation is consuming, no matter the time or power.

• 2. This method may not distinguish the shading of the real images.

• In conclusion, the region growing method has a good performance with the good shape
matching and connectivity. The most serious problem of region growing method is the
time consuming.

Aug 6, 2025 111

• Region Splitting and Merging
• An alternative method is to subdivide an image initially into a set of
arbitrary, disjoint regions and then merge and/or split the region.
• The quadtrees means that we subdivide that quadrant into subquadrants as
specified below,

Aug 6, 2025 112

Aug 6, 2025 113
• Advantage of region splitting and merging ：

• We can split the image by choosing the criteria we want, such as segment
variance or mean of the pixel-value. And the splitting criteria can be different
from the merging criteria.

• Disadvantage of it ：

1. Computation is intensive.

2. Probably producing the blocky segments.

• The blocky segment problem effect can be reduce by splitting for higher
resolution, but at the same time, the computational problem will be more serious.
Aug 6, 2025 114
 Then any point (x, y) for which f( x, y) > T is
called an object point; otherwise, the point is
called a background point.

Aug 6, 2025 115

 multilevel thresholding

Aug 6, 2025 116

Aug 6, 2025 117
Segmentation using Threshold
• Basic Global Thresholding

• The simplest of all thresholding techniques is to partition the image

histogram by using a single global threshold, T.

• Segmentation is then accomplished by,

-- scanning the image pixel by pixel and

-- labeling each pixel as object or background,

• depending on whether the gray level of that pixel is greater or less than the
value of T.
Aug 6, 2025 118
Segmentation using Threshold
• When the intensity distributions of objects and background pixels are sufficiently distinct, it
is possible to use a single(global) threshold applicable over the entire image.
• The following algorithm can be used to obtain T automatically:

1. Select an initial estimate for the global threshold, T.

2. Segment the image using T as 1

if f(x,y)>T
g(x,y)=
0
This will produce two groups of pixels: if f(x,y)<=T

G1 consisting of all pixels with intensity values > T,

and G2 consisting of pixels with values <=T.

Aug 6, 2025 119
Segmentation using Threshold
3. Compute the average gray level values μ1, and μ2 for the pixels in regions G1 and

G2 .

4. Compute a new threshold value:

T = 1/2 (μ1 + μ2 )

5. Repeat steps 2 through 4 until the difference in T in successive iterations is

smaller than a predefined parameter To.
• The parameter To is used to stop the algorithm after changes become small in terms of
this parameter. This is used when speed of iteration is an important issue.
Aug 6, 2025 120
• The type of global thresholding just described can be expected to be
successful in highly controlled environments.

• One of the areas in which this often is possible is in industrial inspection

applications, where control of the illumination usually is feasible.

Aug 6, 2025 121

Optimum Global thresholding Using Ostu’s method

Algorithm is given below

Aug 6, 2025 122