35

Module 5
Image Segmentation and Representation

Dr. Poonam Bari

Introduction
What is Image Segmentation?
• Image segmentation divides an image into regions that are
connected and have some similarity within the region and
some difference between adjacent regions.
• The goal is usually to find individual objects in an image.
• For the most part there are fundamentally two kinds of
approaches to segmentation: discontinuity and similarity.
– Similarity may be due to pixel intensity, color or texture.
– Differences are sudden changes (discontinuities) in any of
these, but especially sudden changes in intensity along a
boundary line, which is called an edge
 Image segmentation fundamentals
• Segmentation subdivides an image into its constituent regions or objects,
until the objects of interest in an application have been isolated.
• Segmentation partitions image R into subregions R1, R2, …, Rn such that:
1. R1∪R2∪…∪Rn=R
2. Each Ri is a connected set, i = 1,2,…..,n 1. Every pixel is included
3. Ri∩Rj = Ø for all i, j where i # j 2. Each region is connected
3. Regions don’t overlap
4. Q(Ri)=TRUE for every i 4. Each region is internally similar
5. Q(Ri ∪ Rj)=FALSE for any two adjacent regions 5. Adjacent regions are meaningfully
different

Segmentation: to partition the image into regions satisfying above conditions.

1. Every pixel is included
2. Each region is connected
3. Regions don’t overlap
4. Each region is internally similar
5. Adjacent regions are meaningfully different
Two principal approaches:
 Edge-based Segmentation
• - Partition an image based
on abrupt changes in
intensity(edges).

 Region-based
Segmentation
• - Partition an image into
regions that are similar
according to a set of pre-
defined criteria.
Image Segmentation

(Point, Line & Edge)

Image SegmentationFor
:
the most part there are fundamentally two
kinds of approaches to segmentation:
discontinuity and similarity.
 Discontinuity
The strategy is to partition an image based on abrupt
changes in intensity
 Detection of gray level discontinuities:
– Point detection
– Line detection
– Edge detection
• Gradient operators
• Gaussian based operators
 Similarity
The strategy is to partition an image into regions that
are similar according to a set of predefined criteria.
Detection of Discontinuities
• Detect the three basic types of gray-level discontinuities
– points , lines , edges
• Use the image sharpening techniques
– The first order derivatives produce thicker edges
– The second order derivatives(Laplacian operation) have a strong response
to fine detail, such as thin lines and isolated points, and noise.

• Can be done by running a mask through the image

Point detection
• Steps for point detection:
1. Apply Laplacian filter to the image to obtain R(x, y).
2. Create binary image by threshold.

where T is a non-negative threshold.

 Point Detection
• Point detection can be achieved with simple high frequency (sharpening)
mask given below.
• Point is a high frequency signal.
• Two types of points can be detected.
• Bright point on dark background. for e.g. 10 10 10 10 10 240 10 10 10
10 10
• Dark point on bright background. for e.g. 240 240 240 240 240 10 240
240 240 240 240
• Threshold is used.
• Pixels are detected as Points that are above a set threshold
 T = 150

• |R| > T • R = 80 - 1600 = - 1520 = 1520 = 255

• R = 1600 - 80 = 1520 = 255 • R = 1520/9 = 169
• R = 1520/9 = 169 • T = 150
image

[0 0 0 0 0 0 0 0 0]
Original Image Point Detection [0 0 0 0 1 0 0 0 0]
mask
[0 1 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0]
[0 1 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0]

T=120
Line detection
• A special mask is needed to detect a special type of line.
• Examples:
- Horizontal mask has high response when a line is passed through
the middle row of the mask.

• Horizontal Mask: Respond more strongly to horizontally oriented lines

• Vertical Mask: Respond more strongly to vertically oriented lines
• 45° Mask: Respond more strongly to 45° inclined lines
• -45° Mask: Respond more strongly to 45° inclined lines
Line detection
• R1, R2, R3 & R4: Response of four masks
• if |Ri|>|Rj| for i!=j
• e. g. i=1, j=2,3,4.
• |R1|>|Rj|, j=2,3, 4
• Then Point is more likely associated with horizontal lines

When 𝑅1=𝑅2​:It indicates multi-directional intensity change

Typically classified as:
Corner
Intersection
Non-directional feature
Line detection
• Apply horizontal and vertical line detection mask on the following
image. Use appropriate threshold value. Assume virtual rows and
columns by repeating border pixel values.
Image after replication

Line detection Mask

Horizontal
Vertical
• Response of Horizontal Line Mask

• Response of Vertical Line Mask

• RH: Response of Horizontal mask.

• Rv: Response of Vertical mask
• | RH |>| Rv|: Point is more likely associated with a line in direction of mask.
• Horizontal line is present
• T=500 can be set
• Isolated points, thin lines (one pixelthick) not frequent occurrences in
most practical application
• Edge detection: The most common approach for detecting meaningful
discontinuities in gray level
Edge detection:
• Edge detection is the approach for segmenting images based on
abrupt changes in intensity. It is used to detect the boundaries or to
find size or location of an object in an image.

• What is an edge?
- an edge is a set of connected pixels that lie on the boundary
between two regions.
- an edge is a “local” concept whereas a region boundary, owing
to the way, it is defined, is a more global idea.
Image Gradient (1st order derivatives)
Image Gradient Operator
Consider 3 x 3 neighbourhood with z5 as the point of consideration

z1 z2 z3
z4 z5 z6
z7 z8 z9

X gradient: horizontal Y- gradient: vertical

Image Gradient Operator
Steps to compute the gradient of an image are as follows
• Convolve the original image with mask1. This gives us the gradient
along x-direction.
• . Convolve the original image with mask2. This gives us the gradient
along y direction.
• Add results 1 & 2
• Add: We can see the effect of each mask separately.
• Add two mask2
Robert Mask
• Better results could be obtained if cross differences were taken instead
of the straight differences.
x-1 x x+1
y-1 z1 z2 z3
y z4 z5 z6
y+1 z7 z8 z9
Prewitt Operator
• It assigns similar weights to all the neighbours of the candidate pixel
value whose edge strength is being calculated.

z1 z2 z3
z4 z5 z6
z7 z8 z9
Prewitt Operator
Sobel Operator
• Higher weights are assigned to the pixel close to the candidate pixels.

x-1 x x+1
y-1 z1 z2 z3
y z4 z5 z6
y+1 z7 z8 z9
 Sobel Operator
• Higher weights are assigned to the pixel close to the candidate pixels.

x-1 x x+1
y-1 z1 z2 z3
y z4 z5 z6
y+1 z7 z8 z9
Gradient (1st order derivatives) Operators and Masks
 Example
Detect edge in the following image using strength (magnitude) and direction of gradient.
Use Prewitt operator.
M(x, y) Find an edge in horizontal direction
M(x, y) Find an edge in vertical direction
• Gx =22
• 𝐺𝑦=171
• Magnitude ≈ 172.4 (strong edge)
• Direction ≈ 83° (almost vertical edge)
• Since Gy is much larger than 𝐺𝑥
• change is mostly left ↔ right
• so edge is vertical
Prewitt and Sobel masks for Diagonal edges
Example of use of Gradient
Second order derivative
• In first order derivative, edges are considered to be present when edge
magnitude is large compared to the threshold value
• In case of second derivative, edge is present at that location where the
second derivative is zero
• It is like zero crossing, which can be observed as a sign change

Zero crossing:
Zero crossing is a situation
20 40 20 where pixels in
neighbourhood differ from
each other pixel in sign
Laplacian operator
 Laplacian (Second order derivative) for edge detection
LoG approximation kernel where σ = 1.4. This is just an example of one convolution kernel that can be
used.
apply line detection mask on following image
Example
1. If Gx=12 Gy=5, find the gradient magnitude.
2. If Gx=6, Gy=6, find the edge direction.
3. Apply sobel operator and interpret the result
10 20 30
20 30 40
30 40 50
4. Apply the Prewitt operator to the following image and find 𝐺𝑥, Gy,
and gradient magnitude.
10 10 10
20 20 20
30 30 30
Edge Linking
• An edge detection algorithm (Roberts, Sobel, Prewitt, LoG etc.) enhance
the edges. When implemented, there are normally breaks in lines. Due
to this reason, these are generally followed by linking procedures to
assemble edge pixels into meaningful edges.
Input Gradient Edge A good edge
Image operator Linking output image

• There are two basic approaches for edge linking:

(1) Local Processing. This is a simplest approach for linking pixels in a small
neighborhood
(2) Global Processing via the Hough Transform. Here, we attempt to link edge
pixels that lie on specified curves. The Hough transform is designed to detect lines, using the
parametric representation of a line.
 Local Processing
• Analyze the characteristics of pixels in pixels (s,t) and (x,y) are similar and linked if,
a small neighborhood Sxy (say, 3x3,
5x5) about every edge pixels (x, y) in
an image that have undergone edge
detection.
• All points that share some common
properties are linked together. These
are:
a) Strength/magnitude of the gradient. This local processing is expensive. A record
has to be kept of all linked points by, for
b) Direction of the gradient. example, assigning a different label to every
set of linked points.
 Example of local processing:
Local Processing : Example
• Given Threshold E=40 and A=10
• pixel = (2,2) with G = 60, θ = 48°
• (2,1) G = 48, θ = 50° , Difference = |50 − 48| = 2°
• (2,3) G = 50, θ = 52°, Difference = |52 − 48| = 4°
• (1,2) G = 52, θ = 45°, Difference = |45 − 48| = 3°
• (3,2) G = 45, θ = 47°, Difference = |47 − 48| = 1°
Example
• Threshold - E=50 and A=20
Hough transform
• The Hough transform is a feature extraction technique

• The Hough transform (HT) can be used to detect lines, circles or .

• The idea of the Hough transform is, that every edge point in the edge
map is transformed to all possible lines that could pass through that
point.
Hough transform
• Mapping of one unique line with Hough space
 Hough transform
• The Hough's transform is all about converting points in the xy space to
lines in the mc space.
• Straight line y = mx + c can be represented as a point (c, m) in the
parameter space.
• y = mx + c
• c = y - mx
• Image Space: Multiple points (1, 2, 3, 4)
lie on the same straight line.
• Parameter Space:
• Each of those points is plotted as a unique
line. Because the points in the image space
were collinear, their corresponding lines in
the parameter space all intersect at a single
point
• This intersection point tells us the exact
slope and intercept of the line in the xу sрасе
mc space
original image. image space Hough (parameter) space
Hough transform
Hough transform
x 1 3
• 2 points (1,2) and (3,4)
y 2 4
7
• y = mx + c 6
• c = y - mx 5
(3,4)
y 4
3
(1,2)
2
1
1 2 3 4 5 6 7 8 9
x

Image Space
Hough transform x 1 3
• For Equation c = 2-m y 2 4
Equation of line c = 2-m c = 4-3m
• If c=0, m=2 and
m=0, c=2
• For Equation c = 4-3m 7
• If c=0, m=4/3= 1.33 and 6
5
m=0, c=4
c 4
3
• (m,c)=(1,1) 2
(1,1)
• y=mx+c 1
• When x=1 y=1*1+1 =2 1 2 3 4 5 6 7 8 9
m
• When x=3 y=1*3+1 =4
Hough Space
 Hough transform
• Given 5 points use Hough transform to draw a line joining these
points. (1,4) (2,3) (3,1) (4,1) (5,0)

x 1 2 3 4 5
y 4 3 1 1 0

• y = mx + c
• c = y - mx

x 1 2 3 4 5
y 4 3 1 1 0
Equation
c = 4-m c = 3-2m c = 1-3m c = 1-4m c = 0-5m
of line
Hough transform
• Given 5 points use Hough transform to draw a line joining these
points. (1,4) (2,3) (3,1) (4,1) (5,0)

x 1 2 3 4 5
y 4 3 1 1 0

• y = mx + c
• c = y - mx
x 1 2 3 4 5
y 4 3 1 1 0

Equation of line c = 4-m c = 3-2m c = 1-3m c = 1-4m c = 0-5m

Hough transform
x 1 2 3 4 5
y 4 3 1 1 0
Equation of line c = 4-m c = 3-2m c = 1-3m c = 1-4m c = 0-5m
m c
x y Equation of line
if c=0 if m=0 7
1 4 c = 4-m 4 4 6
(-1,5)
5
2 3 c = 3-2m 1.5 3
4
3 1 c = 1-3m 0.33 1
3
4 1 c = 1-4m 0.25 1 2
5 0 c = 0-5m 0 0
1
When m=-1 and c=5 Equation y= -x + 5 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7
m
x 1 2 3 4 5
y -1 + 5 -2 + 5 -3 + 5 -4 + 5 -5 + 5
Hough Space
Hough transform
 Hough Transform Steps
1) Load the image
2) Find the edges of the image using any edge detector
3) Quantize the parameter space P
4) Repeat the following for all the pixels of the image:
if the pixel is an edge pixel, then
(a) c =(-x)m +y or calculate ρ
(b) P(c,m) =P(c,m) +1 or increment position in P
5) Show the Hough Space
6) Find the local maxima in the parameter space
7) Draw the line using the local maxima
• The major problem with this algorithm is that it does not work for vertical lines, as they
have a slope of infinity.
• Solution is, convert line into polar coordinates ρ = x cosӨ + ysinӨ, where Ө is the angle
between the line and x-axis, and ρ is the diameter.
Example
• Apply Hough transform on following image with Threshold =50 and
Prewitt detector

• Apply Prewitt operator

• Find x and y gradient
• Find gradient magnitude
• Apply thresholding
• Apply Hough transform
Graph Theoretic Method
Graph Theoretic Method
• Global Processing via Graph-Theoretic Techniques

• A global approach 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.

• The procedure is considerably more complicated and requires more processing

time.
Graph Theoretic Method
• Edge Elements:
• An edge element is the boundary between two pixels p and q, such that
p and q are 4-neighbors

. . .
. . .
p q
. . .
Edge Element Costs

• Each edge element defined by pixels p and q has an associated cost,

defined as

• c(p,q) = max(I) - [f(p)-f(q)]

• where max(I) is the highest intensity value in the image, f(p) is the
intensity value of p, and f(q) is the intensity value of q.

• p and q are 4-neighbors.

Example
• Assume two pixels at a time...
5 6 1
• Let p & q. - 4 neighbors.
6 7 0
• P and q shows edge element, has associated cost
7 1 3
• c(p, q)= Max (I) - [f(p)-f(q)]

where, Max (I) = maximum gray level in image

• c(p, q)= Max (I) - [f(P)-f(9)]
5 6 1 5 6 1 5 6 1
6 7 0 6 7 0 6 7 0
7 1 3 7 1 3 7 1 3
5 6 1 5 6 1
5 6 1 5 6 1
6 7 0 6 7 0
6 7 0 6 7 0
7 1 3 7 1 3
7 1 3 7 1 3
5 6 1
6 7 0
7 1 3
p q
5 6 1
q 6 7 0
p 7 1 3
p

q
• A cost (p, q) = max I - [f(p) –f(q))
• (5,6)= 7-[5-6]=7+1=8
5 6 1
• (6,7) = 7-[6-7] = 8 6 7 0
• (7,1) =7-(7-1)=1
• total cost A = 8+8+1=17 7 1 3

• B=16
5 6 1
• C=23, D=38,E=ll, F=36
• G=11 6 7 0
• H=4
• Least cost path is H... 7 1 3
• B=16, C=23, D=38, E=11 , F=36
• G=11, H=4
• Least cost path is H
• Using graph theoretic approach find the edge with least cost

1 2 0
2 6 4
4 3 3
Thresholding segmentation
Contrast stretching Thresholding
T function T function
 Segmentation by thresholding
• Thresholding is the simplest segmentation method. Thresholding is used to
produce regions of similarity within the given image, based on some threshold
criteria T. Hence it partitions/segments an image into different objects.
• The pixels are partitioned depending on their intensity value.
• Single thresholding:
g(x, y) = 1, if f (x, y) > T
0, if f (x, y) ≤ T
• Multiple thresholding:
g(x, y) = a, if f (x, y) > T2
b, if T1 < f (x, y) ≤ T2
c, if f (x, y) ≤ T1
 Thresholding types:
• Thresholding operation can be thought of as an operation, such that,
T=T[x, y, p(x, y), f(x, y)], where f(x, y) is the gray level of input pixel at (x, y) and
p(x, y) denotes some local property of this point (x, y), e.g. the average level of a
neighborhood centered on (x, y).

Thresholding

Global Local
T = T [ f(x, y) ] T=T [ p(x, y), f(x, y) ]
Global Thresholding
• If the thresholding operation depends only on the gray scale value, it is
called global thresholding.

• Let threshold T=100

• Apply to every pixel:
• Values > 100 → 1 (white)
• Values ≤ 100 → 0 (black)

T=(local mean or weighted mean)−C

Local Thresholding
• neighborhood matters
• If the neighborhood property is also taken into account, it is
• called local thresholding.
Dynamic/Adaptive thresholding
• If T depends on pixel coordinates also, T is called dynamic/adaptive
thresholding. Thresholding is called adaptive when a different
threshold is used for different regions in the image.
 How to select T ? OR How to choose Threshold value T ?
• Assuming that the background and the object occupy comparable
areas in the image, a good initial value of T is the average gray level of
the image.
1. Select an initial estimate for T.
2. Segment the image into two group of pixels G1 and G2 using T.
3. Compute the average gray level values of G1 and G2, say the values
obtained are μ1 and μ2.
4. Compute a new threshold value as Tnew=(μ1+μ2)/2,
5. Compare if |T new -T|>z 0 ( predefined threshold z0) then T=Tnew and go
to step 2, else stop
• Initial 𝑇=100T=100
• After calculation → 𝑇new=92
• 𝑧0​=1
• ∣92−100∣=8>1
• Set 𝑇=92
• New iteration gives
• 𝑇new=91.5
• |91.5−92∣=0.5<1
 Basic Global Thresholding
• Global thresholding having a single threshold (T) is used when the objects are
easily differentiated from each other.
 Adaptive (Local) thresholding

• Global thresholding often fails

in the case of uneven
illumination.

• The solution is to divide the

image into sub-images, and
determine T for each sub-
image. This method is known
as adaptive(local) thresholding.
 Adaptive (Local) thresholding
 Basic Adaptive Thresholding:
• Subdivide original image into
small areas.
• 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-
images, this type of thresholding
is adaptive(local).
Region based segmentation
 Region-Based Segmentation-Basic Formulation
• Let R represent the entire image region.
• Segmentation is a process that partitions R into subregions, R1,R2,…,Rn,
such that

• where P(Rk): a logical predicate defined over the points in set Rk.
• For example: P(Rk)=TRUE if all pixels in Rk have the same gray level.
 Region-Growing
• Edges and thresholds sometimes do not give good results for segmentation.
Thresholding still produces isolated image.
• Region growing algorithms works on principle of similarity.
• It states that a region is coherent if all the pixels of that region are
homogeneous with respect to some characteristics such as colour, intensity,
texture, or other statistical properties.
• Thus idea is to pick a pixel inside a region of interest as a starting point (also
known as a seed point) and allowing it to grow.
• Seed point is compared with its neighbours, and if the properties match , they
are merged together.
• This process is repeated till the regions converge to an extent that no further
merging is possible.
 Region-Growing Algorithm
• It is a process of grouping the pixels or subregions to get a bigger
region present in an image.
• Selection of the initial seed: Initial seed that represent the ROI
should be given typically by the user. Can be chosen automatically.
The seeds can be either single or multiple.
• Seed growing criteria: Similarity criterion denotes the minimum
difference in the grey levels or the average of the set of pixels. Thus,
the initial seed ‘grows’ by adding the neighbours if they share the
same properties as the initial seed.
• Terminate process: If further growing is not possible then terminate
region growing process.
• Threshold=3
 Example
• Apply region growing on following image with initial point at (2,2)
and threshold value as 2. Use 4 connectivity
0 1 2 0
• 7-6=1 <=2
2 5 6 1
• 7-5 =2 <=2 b b b b 1 4 7 3
0 0 0 0 b a a b 0 2 5 1
0 1 1 0 b a a b
0 1 1 0 b b a b
0 0 1 0
 Example
• Apply region growing on following image with pixel value 6 and
threshold value as 3.
5 6 6 7 6 7 6 6
a1 a1 a1 a1 a1 a1 a1 a1 6 7 6 7 5 5 4 7
a1 a1 a1 a1 a1 a1 a1 a1
1 1 1 1 0 0 1 1
6 6 4 4 3 2 5 6
a a a a b b a a
1 1 1 0 0 0 1 1 5 4 5 4 2 3 4 6
a a a b b b a a
0 0 0
b b b b b b a
0 0 0 1 1
a 0 3 2 3 3 2 4 7
0 0 0 0 0 0 1 1
b1 b0 b0 b0 b0 b0 a1 a1 0 0 0 0 2 2 5 6
a1 b0 b0 b0 b0 b0 a0 a0 1 1 0 1 0 3 4 4
a b b b b b b b 1 0 1 0 2 3 5 4
 Region Splitting
• Entire image is assumed as a single region. Then the
homogeneity(similarity) test is applied, where pixels that are similar are
grouped together. If the conditions are not met, then the regions are split
into four quadrants, else leave the region as it is.

• Split and continue the subdivision process until some stopping criteria is
fulfilled. The stopping criteria often occur at a stage where no further
splitting is possible.

• This process is repeated for each quadrant until all the regions meet the
required homogeneity criteria. If the regions are too small, then the
division process is stopped.
 Region Splitting
• To explain this in terms of graph theory, we call each region a node.
• This technique has a convenient representation in the form of a
quadtree structure.
• Quadtree: a tree in which nodes have exactly four descendants.
 Region Merging
• Region merging is opposite to region splitting.
• Here we start from the pixel level and consider each of them as a
homogeneous region.
• At any level of merging, we check if the four adjacent regions satisfy the
homogeneity property. If yes, they are merged to form a bigger region,
otherwise the regions are left as they are.
• This is repeated until no further region exits that requires merging.
 Region Splitting and Merging
• Splitting or merging might not produce good results when applied
separately. Better results can be obtained by interleaving merge and
split operations.
• The split and merge procedure is as follows:
• First there is a large region (possible the entire image).
a) Split into four disjoint quadrants any region Ri for which P(Ri) =
FALSE.
b) Merge any adjacent regions Rj and Rk for which P(Rj U Rk) =
TRUE. (the quadtree structure may not be preserved).
c) Stop when no further merging or splitting is possible.
• Apply splitting and merging on following image with threshold value
as 3. Region R
• Threshold =3
5 6 6 6 7 7 6 6
• Condition Max-Min<=T
• If condition is not satisfied then 6 7 6 7 5 5 4 7
split image in 4 quadrant 6 6 4 4 3 2 5 6
• Repeat the step
5 4 5 4 2 3 4 6
• Region R
• Max=7 0 3 2 3 3 2 4 7
• Min=0 0 0 0 0 2 2 5 6
• Difference= 7
1 1 0 1 0 3 4 4
• 7>3 then split
1 0 1 0 2 3 5 4
• Apply splitting and merging on following image with threshold value as 3.
• Threshold =3 Region R
Region R1 Region R2
• Condition Max-Min<=3
5 6 6 6 7 7 6 6
• R1 Region R21 Region R22
• Max=7 6 7 6 7 5 5 4 7
• Min=4
• Difference= 3 6 6 4 4 3 2 5 6
Region R23 Region R24
• 3<=3 5 4 5 4 2 3 4 6
• R2 R21:7-5=2
0 3 2 3 3 2 4 7
• Max=7 R22:7-4=3
• Min=2 R23:3-2=1 0 0 0 0 2 2 5 6
• Difference= 5 R24:6-4=1
• 5>=3 1 1 0 1 0 3 4 4
• Split 1 0 1 0 2 3 5 4
Region R3 Region R4
• Apply splitting and merging on following image with threshold value as 3.
• Threshold =3 Region R
Region R1 Region R2
• Condition Max-Min<=3
5 6 6 6 7 7 6 6
• R3 Region R21 Region R22
• Max=3 6 7 6 7 5 5 4 7
• Min=0
• Difference= 3 6 6 4 4 3 2 5 6
Region R23 Region R24
• 3<=3 5 4 5 4 2 3 4 6
• R4
0 3 2 3 3 2 4 7
• Max=7 R41:3-2=1
• Min=0 R42:7-4=3 0 0 0 0 2 2 5 6
• Difference= 7 R43:3-0=3
• 5>=3 1 1 0 1 0 3 4 4
R44:5-4=1
• Split 1 0 1 0 2 3 5 4
Region R3 Region R4
• Let us take region a and region b Merging
• If Condition: Max(a)- Min(b)<=T and Max(b)- Min(a)<=T then merge
• Check R1 and R3
• R1 : Max: 7 Min=4 Region R
• R3: Max: 3 Min=0 Region R1 Region R2
• Max(R1)-Min(R3)= 7-0>3
• Thus can not merge R1 and R3 5 6 6 6 7 7 6 6
Region R21 Region R22
• Check R1 and R21 6 7 6 7 5 5 4 7
• R1 : Max: 7 Min=4 Region Ra
• R21: Max: 7 Min=5
• Max(R1)-Min(R21)= 7-5=2<=3
6 6 4 4 3 2 5 6
Region R23 Region R24
• Max(R21)-Min(R1)= 7-4=3<=3
• Thus can merge R1 and R21 5 4 5 4 2 3 4 6
• Check Ra and R22 0 3 2 3 3 2 4 7
• R1 : Max: 7 Min=4
• R21: Max: 7 Min=4 0 0 0 0 2 2 5 6
• Max(R1)-Min(R21)= 7-4=3<=3
• Max(R21)-Min(R1)= 7-4=3<=3
• Thus can merge Ra and R22
1 1 0 1 0 3 4 4
1 0 1 0 2 3 5 4
Region R3 Region R4
 Merging
Region R
Region R1 Region R2

5 6 6 6 7 7 6 6
Region R21 Region R22
6 7 6 7 5 5 4 7
Region Ra
6 6 4 4 3 2 5 6
Region R23 Region R24
5 4 5 4 2 3 4 6
0 3 2 3 3 2 4 7
0 0 0 0 2 2 5 6
Region Rb
1 1 0 1 0 3 4 4
1 0 1 0 2 3 5 4
Region R3 Region R4
Representation
• Representation: Make a decision whether the data should be
represented as a boundary or as a complete region. It
almost always follows the output of a segmentation stage.
- Boundary Representation: Focus on external shape
characteristics, such as corners and inflections.
- Region Representation: Focus on internal properties, such as texture
or skeleton shape.
 Steps of the Boundary following process:
1) Select a Starting Point: The process begins by
selecting a starting point on the object's
boundary. This point can be any pixel
belonging to the object.
2) Tracing the Boundary: Starting from the
chosen starting point, the algorithm follows a
set of predefined rules to trace the boundary.
The rules determine the order in which
neighboring pixels are examined and selected
to continue tracing.
1) For the 4-connected boundary following,
the algorithm examines the four immediate
neighbors (top, bottom, left, right).
2) For the 8-connected boundary following,
the algorithm examines all eight neighbors,
including the diagonals.
 Steps of the Boundary following process:
3) Decision Rules: At each step of the tracing
process, the algorithm makes decisions based on
the following rules:
• It selects the next boundary pixel from the
adjacent neighbors in a specific order (e.g.,
clockwise or counterclockwise).
• It ensures that the selected neighbor is part of
the object (i.e., its pixel intensity corresponds
to the object's intensity).
4) Tracing Completion: The process continues
until the algorithm returns to the starting point,
forming a closed loop and completing the
boundary trace.
5) Representation: As the boundary is traced, the
coordinates of the boundary pixels are recorded.
These coordinates can then be used to represent
the contour of the object.
 Chain codes
• The boundary code formed as a sequence of such directional numbers is
referred to as a Freeman chain code.
• Different starting points gives different chain codes.
• To normalize the chain codes with respect to starting point, we have to treat
the chain codes as a circular sequence.
• Also, whichever number gives the smaller magnitude will be considered as
the chain code.
 Advantages of Chain codes:
• Compactness: Chain codes can significantly reduce the storage space
required to represent a boundary compared to storing the individual
coordinates of boundary pixels.

• Rotation Invariance: Chain codes are rotation invariant since they represent
only the relative directions between boundary pixels, not their absolute
positions.

• Simple Processing: Chain codes are straightforward to generate and process,

making them useful in various image processing tasks, such as pattern
recognition, shape matching, and object tracking.
 Shape number :
• The shape number is defined as the first difference (difference code) of smallest
magnitude. Order(n) of a shape number is the number of digits in the
representation. n is even for a closed boundary.