5

Image Segmentation

5.1. INTRODUCTION

Segmentation:
The process of subdividing an image into its constituent parts is known as
segmentation. This is the first step in the image analysis. Segmentation should be
stopped when object of interest in an application have been isolated.
Segmentation algorithms for monochrome images generally based on two
important properties known as,
(i) Discontinuity (to partition an image based on abrupt changes in gray level.
The main areas of interest in this category are detection of isolated points, the
detection of lines and edges of an image).
(ii) Similarity (principal approach based on threshold, region growing, region
splitting & merging)
The concept of segmenting an image based on discontinuity or similarity of the
gray level values of its pixels is applicable to both static and dynamic images.

5.2. DETECTION OF DISCONTINUITIES

The various techniques based on gray level discontinuity are given below.
(i) Detection of isolated points,
(ii) Detection of line,
(iii) Detection of edges.
5.2 Digital Image Processing

The way to look for discontinuities is to run a mask through the image. The
representation of mask is given below.
w1 w2 w3
w4 w5 w6
w7 w8 w9
wi = Coefficient in the mask.
Zi = Gray level of the pixel associated with mask coefficient wi.
R = The response of mask at any point in an image.
R  w 1 z1  w 2 z 2  ...  w 9 z 9
9
R w
i 1
i zi

It involves computing sum of products of the coefficients with the gray levels
contained in the region encompassed by the mask.
The response of the mask is defined with respect to its center location when the
mask is centered on a boundary pixel. The response is calculated by using appropriate
partial neighbourhood.

5.2.1. Point Detection

–1 –1 –1
–1 8 –1
–1 –1 –1
This mask is used to detect the isolated points due to noise or interference. It
consists of coefficients ‘–1’ every where except at the center (center coefficient is 8).
The sum of all the coefficients is 0. When, the mask is placed over an image, it covers
a pixels in the image. The average response to the mask is given as R.
R  w 1 z 1  ...  w 9 z 9 
1
9
1 9
R   w i zi
9 i 1
If the mask is over a uniform intensity area, then, the response due to this mask is
0 (zero). Because, there are no isolated pixels with different gray level values.
If the isolated points are just below the center of the mask, then, the average
response will be maximum.
The same mask is used for high frequency spatial filtering.
Image Segmentation 5.3

5.2.2. Line Detection

The next level of complexity is detection of lines in an image.

–1 –1 –1
2 2 2
–1 –1 –1
Figure 5.1 Mask used for horizontal line
This mask is moved around an image it respond more strongly to lines oriented
horizontally.
The response is high when the line passes through the middle row of the mask
with constant background. When the mask is moved over an image which consists of
all ‘1’s as background and with a lie of different gray level ‘5’s. Then, the response
due to the first mask is computed as
1*  1  1*  1  1*  1  5* 2  5* 2  5* 2  1*  1  1*  1  1*  1 24
–1 2 –1
–1 2 –1
–1 2 –1
Figure 5.2 Mask for vertical line detection
This mask gives high response to vertical lines.
–1 –1 2
–1 2 –1
2 –1 –1
Figure 5.3 Mask for +45 slanting line detection
This mask gives high response to the lines in the +45 direction.
2 –1 –1
–1 2 –1
–1 –1 2
Figure 5.4 Mask for –45 slanting line detection
This mask results high response to the lines in the – 45 direction.
For example, all the masks are applied to an image and the responses are R 1, R2,
R3, R4. If R i  R j for j  i. then the point is more likely to be associated with the
line in the direction of mask i.
5.4 Digital Image Processing

5.2.3. Edge Detection

Edge detection is used for detecting meaningful discontinuities in gray level. First
and second order digital derivatives are implemented to detect the edges in an image.
Edge:
An edge is a boundary between two regions with relatively distinct gray level
properties.
Model of an ideal digital edge is shown here.

Gray level profile of a

horizontal line
through the image
Figure 5.5 Model of an ideal digital image
According to this model, an ideal edge is a set of connected pixels.
But, practically, edges are blurred due to optics, sampling and other image
acquisition imperfections. So, edges are more closely modeled as in figure given
below

Figure 5.6 Model of a ramp image

Model of a ramp image is shown here. The slope of the ramp is inversely
proportional to the degree of blurring in the edge.
Figure shows the images of light object in a dark background. The gray level
profile along the horizontal line of the image is shown here. The first derivative of the
gray level profile is positive at the trailing edge, zero in the constant gray level area,
and negative at the leading edge of the transistor. The magnitude of the first derivative
is used to identify the presence of an edge in the image.
The second derivative is positive for the part of the transition which is associated
with the dark side of the edge. It is zero for pixel which lies exactly on the edge. It is
negative for the part of transition which is associated with the light side of the edge.
The sign of the second derivative is used to find that whether the edge pixel lies on the
light side or dark side.
Image Segmentation 5.5

The second derivative has a zero crossing at the mid point of the transition in gray
level. The first and second derivative at any point in an image can be obtained by
using the magnitude of the gradient operators at that point and laplacian operator.
These are explained below.

5.2.3.1. Gradient Operators

The gradient of an image f(x, y) at the location (x, y) is defined as

 f 
G x   x 
f      f 
G y   
 y 
The gradient vector points in the direction of maximum rate of change of f at
(x, y) co-ordinates.
mag f   G 2
x  G 2y 
mag (f) = Magnitude of the vector f
f is commonly known as gradient
f  G x  G y
The direction of the gradient vector is given as,
 Gy 
 x, y   tan 1  
 Gx 
Here, the angle is measured with respect to x axis.
Prewift operators can be used to find Gx and Gy.
The masks used in this method are given below.

P1 P2 P3 –1 –1 –1 –1 0 1
P4 P5 P6 0 0 0 –1 0 1
P7 P8 P9 –1 –1 –1 –1 0 1
3  3 image Prewift mask for Prewift mask for
horizontal detection vertical detection
Figure 5.7 Prewift masks

G x  P7  P8  P9   P1  P2  P3 
5.6 Digital Image Processing

G y  P3  P6  P9   P1  P4  P7 

P1, … P9 are pixel values in a subimage prewift masks are simpler to implement
compared with sobel operators.
Sobels masks are given below.
P1 P2 P3 –1 –2 –1 –1 0 1
P4 P5 P6 0 0 0 –2 0 2
P7 P8 P9 1 2 1 –1 0 1
(a) 3  3 image (b) Mask for (c) Mask for
horizontal detection vertical detection
Figure 5.8 Sobal masks
Fig. (b) is used to find Gx.

G x  P7  2P8  P9   P1  2P2  P3 

Fig. (c) is used to find Gy

G y  P3  2P6  P9   P1  2P4  P7 

By using Roberts operators, the partial derivative at the center of the 3  3 mask
can be implemented.

G x  P9  P5
G y  P8  P6

5.2.3.2. Laplacian Operator

The laplacian of a 2D function f(x, y) is a second order derivative. It is defined as

2 f 2 f
2 f  
x 2 y 2
The laplacian response is sensitive to noise. It is rarely used for edge detection.
P1 P2 P3 0 –1 0
P4 P5 P6 –1 4 –1
P7 P8 P9 0 –1 0
3  3 image Laplacian mask
Figure 5.9 Laplacian masks
Image Segmentation 5.7

For a 3  3 image, digital equivalent of laplacian operator is given below.

 2 f  4 P5  P2  P4  P6  P8 
The coefficient associated with the center pixels should be positive. The
coefficients associated with the outer pixels should be negative. The sum of the
coefficients is zero.

5.3. EDGE LINKING AND BOUNDARY DETECTION

Practically, the set of pixels detected by the gradient operators will not form a
complete boundary due to noise, non-uniform illumination etc. The following
techniques are used for edge linking and boundary detection.
(i) Local processing,
(ii) Global processing using Hough transform
(iii) Global processing via Graph theoretic approach
Some of these techniques are explained below.

5.3.1. Local Processing

The edge pixels are determined by using the gradient operators. The boundary is
not completely defined by the edge pixels. Small gaps are there. To fill these gaps, we
consider the characteristics of pixels in a small neighbourhood. The neighbourhood
pixels similar to the boundary pixels are linked.
Two properties are used to check the similarity of the neighbourhood pixels with
respect to the edge pixels. These are given below.
The strength of the gradient operator response to produce the edge pixel.
The direction of the gradient
(x, y) – Edge pixel
(x1, y1) Neighbourhood pixel.
If neighbourhood pixel is similar to the edge pixel, then,

f x, y  f x1 , y1   T
T – Non-negative threshold value.
The neighbourhood pixel with respect to the edge pixel has an angle similar to the
edge pixel if
 x, y   x1 , y1   Q
5.8 Digital Image Processing

Gy
x, y   tan 1
Gx

 - Angle of threshold
If above equations are satisfied, then, the neighbourhood pixel is linked to the
edge pixel. This procedure is repeated for every edge pixel location.

5.3.2. Global Processing Via Graph Theoretic Technique

This technique based on representing the edge elements in the form of a graph and
searching the graph for the low-cost path.
This technique can provide good result in the presence of noise. The graph is
given as G = (N, V)
N = Set of non-empty nodes
V = Set of unordered pairs of nodes in N.
The pair (Ni, Nj) of V is known as edge.
The graph in which the edges are directed is known as directed graph.
Ni = parent node if an edge is directed from the node Ni to Nj.
Expansion of the node: The process of identifying the successor of a node is
known as expansion of the node.
Start node (or) Root node: The node at level 0.
Goal node: The node in the least level.
C(ni, nj) – the cost associated with the edges between 2 nodes ni and nj.
The cost of entire path is given as
K
C  Cn
i2
i 1 , ni 

Edge element between pixels p and q are given below.

Figure 5.10 Edge element between pixel p and q

Here, edge elements are defined as the boundary between the pixels p and q. the
associated cost is given as,

Cp, q  H  f p  f q 
H = Highest grey level of in the image.
Image Segmentation 5.9

5.4. THRESHOLDING

Thresholding is an important technique used for image segmentation.

5.4.1. Basic Concepts

We can consider the histogram of an image f(x, y) which consists of light objects
on a dark background.

Figure 5.11 Histogram of an image which consists of dark background and a light
object.
This histogram consists of two dominant regions. One for the dark background
and another for the object.
T is used to represent the threshold value. If separates object and background
region. If f(x, y) > T, then, the corresponding point is known as object point.
Otherwise, that point is known as background point.
We can see the histogram which correspond to two different light objects on a
dark background. Here two threshold values T1 and T2 are shown.

Figure 5.12 Histogram for two objects on a dark background (Multilevel

thresholding)
If T1 < f(x, y)  T2, then the point (x, y) correspond to object 1
If f(x, y) > T2, then the point (x, y) correspond to object 2
If f(x, y)  T1, then the point (x, y) correspond to background.
5.10 Digital Image Processing

Here, two threshold values are used. So it is known as multilevel thresholding. It

is not so reliable compared with single thresholding.
The associated parameters of T are given below.
f(x, y) is the gray level at any point (x, y)
P(x, y) is the local property at any point.
The threshold image g(x, y) is given as,
1 for f x, y   T
gx, y   
0 for f x, y   T
In the thresholded image 1 is used to indicate the object. 0 is used to indicate the
background.
If the threshold value T depends only f(x, y). Then, the threshold technique is
known as global. If T depends f(x, y) and P(x, y) then, the threshold technique is
known as local. If T depends (x, y), P(x, y), f(x, y) then the threshold technique is
known as dynamic.
Local (or) regional thresholding is used to denote variable thresholding in which
the value T at any point (x, y) in an image depend the properties of a neighbourhood of
(x, y)

5.4.2. Optimal Thresholding

If an image has 2 main brightness regions, then,

P(z) = Probability density function (histogram) of the gray level values in an image.
Overall P(z) = Sum of two densities.
= (density for light region + density for dark region)
If the density function is a known value then, optimal threshold for segmenting
the image into two brightness regions can be determined.
Overall P(z) = P1  P1(z) + P2  P2(z)
m1, m2 – Mean values for two brightness level.
1, 2 – Standard deviations of the mean.
P1, P2 – Probabilities of two gray levels.
   z  m1 2     z  m 2 2 
   
overall Pz  
P1  2 12  P2  2 22 
e  
 e  

2  1 2  2
Image Segmentation 5.11

The probability of error to classify an object point as background point is given as

T

 P z  dz .

2

The probability of error to classify the background point as an object point is

T
given as  P1 z  dz .

T 
The overall probability of error is given as, P2 .  P2 z dz  P1 .  P1 z dz
 T

If P1 = P2, then the nth optimal threshold is the mean average. It is given as
m1  m 2
T
2

T is the optimal threshold.

5.4.3. Threshold Selection Based on Boundary Characteristics

The threshold value selection depend the peaks in the histogram. The pixels lie on
or near the boundary between the objects and backgrounds are considered to improve
the histogram. Because of doing this, the threshold selection will be improved.
A three level image can be formed using the gradient f and 2f at (x, y)
It is given as,
0, for f  T

G x , y   , for f  T &  2 f  0
, for f  T &  2 f  0

0 is used to represent the pixels that are not on the edge.
+ is used to represent the pixels that are on the dark side of an edge.
– is used to represent the pixels that are on the light side of an edge.
The transition from light background to dark object is represented by the
occurrence of ‘–’ followed by ‘+’.
The transition from object to the background is represented by the occurrence ‘+’
followed by ‘–’.
Use of Motion in segmentation process:
Generally two approaches are used to apply motion in segmentation process. They
are
(i) Spatial domain approach and (ii) Frequency domain approach
5.12 Digital Image Processing

5.5. REGION BASED SEGMENTATION

Here, similarity of neighbouring pixels is considered. Similar pixels are grouped

together to form regions. There is a common factor between each pixel within the
region.
The process of dividing an image into smaller regions is based upon some
predetermined rule that how to group the pixels into one logical region.
Example: All pixels within the region must be exactly the same gray level.
Example: All pixels greater than a given threshold are combined together to form
one region. The basic rules in this approach are given below.

5.5.1. Basic Rules for Segmentation

R – Entire image region.

R is subdivided into n number of subregions.
R1, R2, … Rn = Sub regions
n
(i) R i  R , segmentation process is complete.
i 1

(ii) Ri is a connected region for i = 1, 2, … n

(iii) R i  R k   for all i and k, where i  k. It shows that, the region must be
disjoint.
(iv) P(Ri) = True for i = 1, 2, … n. It shows that, all the pixels in the region Ri
have the same intensity.
(v) PR i  R k  = False for i  k. It shows that, the regions Ri and Rk are
different in the sense of the predicate P.

5.5.2. Region Growing by Pixel Aggregation

Here, a set of seed points are used as starting points. From the starting point,
regions grow by appending (neighbouring pixels which have similar properties) to
each seed point.
The algorithm starts with the selection of the seed pixel and desired predicate
P(R1) to compare with neighbouring pixels. Then, the initial seed is assigned to region
RL. Then, the eight neighbouring pixels of the seed pixel are assigned to region R1, if
these pixels meet the predicate requirement. The process of comparing the eight
neighbouring pixels continues until no further pixels can be added to the region. Then,
Image Segmentation 5.13

the region R1 is completely defined. Pixels belong to this region are removed from the
original image.
A new seed pixel is located within another area of the image and the same
procedure is repeated until all pixels defining region R2 are determined. The same
procedure is repeated again and again until all regions have been defined.
Seed pixel is located by scanning the image pixel by pixel and to use the first
pixel found which has the minimum or maximum gray level.
After that, the region growing process started.
We can see the example for the threshold value of 3 (Th = 3)
1 0 5 6 7
1 0 5 5 5
0 1 6 7 6
1 2 5 6 7
1 1 7 6 5
Here, 5  5 image pixels are shown. The values inside the boxes are the gray
levels.
Here, 2 seeds are 2 and 7.
The location of 2 is (4, 2)
The location of 7 is (3, 4)
These are the starting points. Then, the regions are grown here, Th = 3.
Th = Threshold value.
The absolute difference between the gray level of that pixel and the gray level of
the seed must be less than the threshold value.

R1 R1 R2 R2 R2
R1 R1 R2 R2 R2
R1 R1 R2 R2 R2
R1 R1 R2 R2 R2
R1 R1 R2 R2 R2

Region 1 Region 2
Figure 5.13 Region based segmentation. Region growing by pixel aggregation
This technique is simple. But, it is difficult to select the initial seed which
properly represent the region of interest. It is difficult to select the suitable properties
for including points as various regions during region growing process.
5.14 Digital Image Processing

5.5.3. Region Splitting and Merging

In this technique, an image is divided into various subimages of disjoint regions

and then merge the connected regions together.
R = Entire region of an image
The predicate P(Ri) is used to check the conditions. In any region, P(Ri) = True
An image is subdivided into various sub images. If P(Ri) = False. Then, divide the
image into quadrants. If P(Ri) = False. Then, further divide the quadrant into sub-
quadrant.
R1
R11 R12
R2
R13 R14

R3 R4

Region R1 is divided into quadrants.

It is shown by using quad tree.

Figure 5.14 Quad tree representations

Example for split and merge algorithm is shown below

Initially an, image is divided into four regions, R1, R2, R3, R4.
Image Segmentation 5.15

R1, R2, R3, R4 are divided into 16 sub regions.

Here in region R2, R23 can be further subdivided.

Its corresponding quad tree representation is given below.

Quad tree gives the region division of the image. R is the region of the original
image. In the next level, original image is divided into four non-overlapping regions.
The next level is the subdivision of these four regions into four smaller regions.
The final level shows the subdivision of R23 into four regions.
After the image has been split into regions that meet the logical predicate
requirement, regions which have the same predicate requirement are merged to form a
new enlarged region. The process of splitting an image into small regions and then
merging connected regions together is known as region segmentation by splitting and
merging.

5.6. IMAGE REPRESENTAITON

In image analysis, the 1st step is image segmentation. Then, the next step is image
representation and description methods. The output of the segmentation process is the
5.16 Digital Image Processing

boundary pixels of objects. The representation of object boundaries is very important.

Generally, two methods are used for image representation.
(i) External characteristics of the object (or) region are used for image
representation.
(ii) Internal characteristics are used for image representation.
The description of the shape of an image is needed to recognize one object from
another.
The discrimination of a rectangular object from a circular object can be easily
done by using the shape of the object contours. An object with a smooth reflective
surface can be easily separated from an object with a rough surface by comparing their
surface textures. So, region and contour methods of describing objects within an image
are very important.
The edges of an object give its size and shape.

5.6.1. Boundary Representation Using Chain Codes

Chain codes are used to represent a boundary by a connected sequence of straight

line segments of specified length and direction. This representation is based on four or
eight connectivity of the segments.
Connectivity defines the relationship between neighbouring pixels and it is used
to locate the borders between objects within an image. Connectivity defines the
similarity between the gray levels of neighbouring pixels. There are three types of
connected pixels which describe how two neighbouring pixels are related. These are,
(i) 4-connected
(ii) 8-connected
(iii) m-connected.

0 6 6 (b) 0 6 6 (b) 0 6 6
0 6 0 0 6 0 0 6 0
(a) 6 6 0 (a) 6 0 0 (a) 6 0 0 (b)
Pixel (a) is a neighbour (ii) 8-connectivity (iii) m-connectivity
of pixel (b)
(i) 4-connectivity
Here, 6 is the gray level of the pixel
The direction of each segment is coded by using a numbering method.
Direction numbers for 4 directional code and 8-directional code are given below
Image Segmentation 5.17

Digital images are processed in a grid format with equal spacing in x and y
directions.

Figure 5.15 Boundary of object Figure 5.16 4-directional chain code

Figure 5.17 8-bit directional code

(30103323212110) (7276543220)
Figure 5.18. 4-directional chain code Figure 5.19 8-directional code
5.18 Digital Image Processing

The accuracy of the resulting code depends on the grid spacing. If, the grids are
closed, then, the accuracy is good. The chain code will be varied depend on the
starting point. This method has two problems.
(i) The resulting chain of codes is long.
(ii) If there is any small disturbances along the boundary due to noise, then there
is a change in the code which may not related to the boundary shape.

5.6.2. Polygonal Approximation

In this technique, a digital boundary is approximated with arbitrary accuracy by a

polygon. Exact approximation can be obtained if a number of segments in the polygon
is equal to the number of points in the boundary. The aim of polygonal approximation
is to capture the essence of the boundary shape with few possible polygonal segments.
Various polygonal approximation techniques are explained below.
Minimum Perimeter Polygons:

Object is enclosed by a set of concatenated cells. So an object is visualized as two

walls corresponding to the outside and inside boundaries of the strip of cells. If object
boundary is assumed as rubber band, then it is allowed to shrink. Then, it takes the
shape as in figure (b)
It is the polygon of minimum perimeter that fits the geometry established by the
cell strip. If each cell encompasses only one point on the boundary, then, the error in
each cell between the original boundary and the rubber band approximation is 2 d.
Here d = minimum possible distance between different pixels. If each cell is forced to
be centered on its corresponding pixel, then the error is reduced by half.
Image Segmentation 5.19

5.6.3. Merging Technique

This technique is to merge points along a boundary until the least square error line
fit of the points merged so far exceeds a preset threshold. Finally, the intersections of
adjacent line segments form the vertices of the polygon.

5.6.4. Splitting Technique

In this technique, a segment is subdivided into two parts until a required criterion
is satisfied. The maximum perpendicular distance from a boundary segment to the line
joining its two end points not exceed a preset threshold.

Q = Farthest point from the top boundary segment to line AB

P = Farthest point from the down segment to line AB

5.7. BOUNDARY SEGMENTS

It is very important to decompose a boundary into the segment. It reduces the

boundary is complexity.
Set A is convex if the straight line segment joining any two points in A lies
entirely within A.
Convex hull H of an arbitrary set S is the smallest convex set containing S. The
set difference H – S is called the convex deficiency of S.
5.20 Digital Image Processing

So description process is simplified. It is very attractive when the boundary

contains concavities which carry the shape information. The use of the convex hull of
the region enclosed by the boundary is an excellent tool for robust decomposition of
the boundary.

(a) (b)
The region boundary is partitioned by following the contour of S and the points
are marked at which a transition is made. This technique is independent of region size
and orientation. Description of a region is based on its area, the area of its convex
deficiency and the number components in the convex deficiency.

5.8. BOUNDARY DESCRIPTORS

5.8.1. Simple Descriptors

The length of a boundary is simple descriptors. The number of pixels along a

boundary is used to give the rough estimation of its length.
Diameter of a boundary is defined as given below.
D = max (D (P1, P2))
P1, & P2 are points on the boundary.
Eccentricity of the boundary is nothing but the ratio of major to the minor axis.
Curvature is the rate of change of slope.

5.8.2. Shape Number

The shape number of the boundary is based on the 4-directional code (or) 8-
directional code. Shape number is defined as the first difference of smallest
magnitude. The number of digits is the shape number is known as the order of the
boundary.
Image Segmentation 5.21

S – Starting point.
Chain code : 0 3 2 1
Difference:

Difference: 3 3 3 3

1st difference from 0 to 3 in counter clockwise direction is shown. Count the

 mark. Here 3 marks are shown. So the difference between 0 and 3 is 3.

Difference between 3 and 2 = 3

Shape no. is determined by shifting the sequence 3 times.
Shape No. 3 3 3 3

Order = 4
5.22 Digital Image Processing

Example:

S – Starting point
Chain code: 0 0 0 3 2 2 2 1

Difference:
Difference : 3 0 0 3 3 0 0 3
Shape No.: 0 0 3 3 0 0 3 3
(shift difference by times)

5.8.3. Fourier Descriptors

The Fourier descriptors are used to represent a boundary. The continuous

boundary can be represented as the digital boundary. Let us assume that it consists of
N number of points (x0, y0), (x1, y1) … (xN–1, yN–1). These are shown below

Figure 5.20 The continuous boundary Figure 5.21 Digital representation

(x0, y0), (x1, y1), (x2, y2) points
are shown here
All these coordinates can be expressed as a sequence.
Sk   xk , yk  for k = 0, 1, 2, … N – 1
The coordinate pairs are represented in the complex number form as given below.
Sk   xk   j yk  for k = 0, 1, 2, … N – 1
Image Segmentation 5.23

Discrete Fourier transform of S(k) is given by

1 N 1
u.k
 j2 
A u    Sk  . e N for u = 0, 1, 2, … N – 1
N k 0
The complex coefficients A(u) are known as Fourier descriptors of the given
boundary.
By using the inverse discrete Fourier transform, S(k) can be obtained.
N 1  j2 
u.k

Sk    Au  . e N

u 0

N – Total no. of points in the digital boundary

Instead of using all the Fourier coefficients, only M number of coefficients is
used. M is much less than N. If M is too low then, the reconstructed boundary
shape is deviated from the original. Example for various M values shown below.
Approximation to the original boundary is given as,
M 1 j2 
uk

Ŝk    Au  . e N

u 0

Example:

Original N = 24 M=2 M = 20 M = 22
(M is too low, (M < N) (Shape is
so reconstruction more like original)
shape is different
from original)
Some basic properties of Fourier descriptors are shown below.
Transformation Boundary Fourier Descriptors
Identity S(k) A(u)
j
Rotation Sr(k) = S(k) e Ar(u) = A(u) ej
Translation St(k) = S(k) + xy At(u) = A(u) + xy (u)
Scaling Ss(k) = C S(k) As(u) = C . A(u)
5.24 Digital Image Processing

5.9. REGIONAL DESCRIPTORS

5.9.1. Some Simple Descriptors

Area and the perimeter can be used as descriptor initially.

The area of a region is defined as the number of pixels in the region.
The perimeter of a region is the length of its boundary.
Compactness of a region is defined as (perimeter)2/area.
Mean and median of the gray levels are also used as descriptors.

5.9.2. Topological Descriptors

Topology is the study of properties of a figure that are unaffected by any

deformation, as long as there is no tearing or joining of the figure.
Number of holes is one of the topological properties. Another topological property
is number of connected components. Euler number E is also one of the topological
descriptor Euler number E can be given as,
ECH
C – Number of connected components
H – Number of holes
The Euler number can be applied to straight line segments such as polygonal
networks. Polygonal network can be described by a number of vertices V, the number
of edges A, and the number of faces F.
E=V–A+F

E=C–H =V–A+F
Example:

Here connected component C = 1

Image Segmentation 5.25

H=2
E = C – H = –1
E = –1

Example 2:

Connected components, C = 2
Holes = 0
So, E = C – H = 2 – 0
E=2

Example 3:

Here, H = 2
Connected components, c = 1
So, E = C – H = 1 – 2
E = –1

Example 4:

Here, connected components, C = 3

5.26 Digital Image Processing

Example 5:
Find number of vertexes and Holes?

Here, V=6
A=6
C=1
H=1
Example 6:
Find E value?

Here, H = 2, C = 1
E = C – H = –1
E = –1

Example 7: Find E value?

Vertices, V = 7
Edges, A = 11
Faces, F = 2
Holes, H = 3
C=1
Image Segmentation 5.27

E=V–A+F
= 7 – 11 + 2 = –2
E = C – H = 1 – 3 = –2
E=2
Example 8: Obtain Euler number for letter A.

H=1
C=1
E=C–H=1–1=0
E=0

5.10. TEXTURE

Texture refers to repetition of basic texture elements known as texels (or) texture
primitives (or) texture elements. It contains several pixels whose placement will be
periodic, quasi periodic (or) random. The artificial textures are periodic natural
textures are random.

Figure 5.22 Artificial textures

The texture may be in the form of fine, smooth, regular, irregular linear etc.
Texture can be described in two main approaches which are given below.
(i) Statistical approach
(ii) Structural approach

5.10.1. Statistical Approach

This approach is very simple. Here, texture is described using statistical moments
of the gray level histogram of an image.
r = random variable to denote he gray level in the image.
P(ri) = Corresponding histogram
i = 0, 1, … L – 1
5.28 Digital Image Processing

L = Number of distinct gray levels.

n(r) = nth moment of r with respect to mean
L 1
 n r    r  mean  Pr 
n
i i
i0
L 1
mean   r Pr 
i 0
i i

0 and 1 can be calculated using above equation (0 = 1, 1 = 0)

0 = zeroth moment
1 = First moment
2(r) = Second moment (or) variance
Variance is used to describe the contrast of an image. It represents the smoothness
of the texture property.
Measure of smoothness is given as R.
1
R  1
1   2 r 

For constant intensity, R = 0

R  1 for larger values of gray levels.
L 1
 3 r    r  mean  Pr 
3
i i
i0

3(r), the third moment is a measure of the skewness of the histogram.

4th moment is a measure of its relative flatness. 5th and 6th moments can provide
further quantitative discrimination of texture content. Additional texture measures
based on histograms include a measure of uniformity. It is given by
L 1
  P r 
i0
2
i

 is maximum for an image in which all the gray levels are equal.
Entropy is also used as a measure of variability. It is zero for constant gray level
images.
Measure of texture computed using histogram suffer from the limitation that they
carry no information regarding relative position of pixels with respect to each other.
This problem is over come by using co-occurrence matrix method.
Image Segmentation 5.29

5.10.2. Co-occurrence Matrix Method

In this technique, distribution of intensities and intensity values are used. For
texture analysis, relative positions of pixels in an image are also considered.
Q is an operator which defines the position of two pixels relative to each other.
Co-occurrence matrix is denoted as C. Cij is the number of times that pixel pairs with
intensities zi and zj occur in an image, 1  i, j  L.
Q is a position operator. It is defined as ‘one pixel immediately to the right’.
Image is given as L = 2, 1  i, j  2.

4  4 image size
Co-occurrence matrix Cij is given as
C11 C12
C21 C22
Here, Q defined as one pixel immediately the right.

C11  (0-pixel with 0 neighbour) 6

C12  (0-pixel with 1 neighbour in right) 0

C21  (1-pixel with 0 neighbour in right) 0

5.30 Digital Image Processing

C22  (1-pixel with 1 neighbour in right) 6

Now, Co-occurrence matrix is given as,

5.10.3. Structural Approach

Its other name is syntactic approach. This technique uses the structure and inter
relationship among components in a pattern.
The block diagram of structural approach for pattern description is shown below.
The input is divided into simple subpatterns and given to the primitive extraction
block. Good primitives are used as basic elements to provide compact description of
patterns. Grammar construction block is used to generate a useful pattern description
language.

Figure 5.23 Block diagram of structural approach

The texture description can be explained using structural approach.
It represents a circle. Then a a a … means circles to the right. So the rule S  as
allows the generation of picture as given below.

Some new rules can be added

S  dA (d means ‘circle down’)
A  lA (l means ‘circle to the left’)
Al
A  dA
Sa
The string a a a d l l d a a can generate 3  3 matrix of circles.
Image Segmentation 5.31

Problems:
What is the order of the shape number of the figure which is given below

Solution:

S  Starting point
Chain code : 0 0 0 3 3 2 1 2 3 2 1 1

Difference: 3 0 0 3 0 3 3 1 1 3 3 0
Shape No. (Shift the difference by 3 times)
330300303311
Order of the shape no. 12
5.32 Digital Image Processing

5.11. TWO MARK QUESTION AND ANSWER

1. What is meant by segmentation process?

The process of subdividing an image into its constituent parts is known as
segmentation.
2. How will you detect isolated points in an image?
To detect the isolated points due to noise or interference, the general mask
which is shown below.
w1 w2 w3 –1 –1 –1
w4 w5 w6 –1 8 –1
w7 w8 w9 –1 –1 –1
3. Draw the masks used for detecting horizontal, vertical and 45 slanting lines.
–1 –1 –1 –1 2 –1
2 2 2 –1 2 –1
–1 –1 –1 –1 2 –1
Mask for horizontal Mask for vertical
line detection line detection
–1 –1 2 2 –1 –1
–1 2 –1 –1 2 –1
2 –1 –1 –1 –1 2
Mask for +45slanting Mask for –45 slanting
line detection line detection
4. What is the role of gradient operator and laplacian operator in segmentation?
The first derivative and second derivative at any point in an image can be
obtained by using the magnitude of gradient at that point and laplacian operator.
5. What is role of first derivative and second derivative in segmentation?
The magnitude of the first derivative is used to detect the preserve of an edge
in an image. The sign of the second derivative is used to find whether the edge
pixel lies on the dark side (or) light side of an edge. If it is positive, it shows that
corresponding pixel lies in the dark side of the edge.
6. Draw the sobel mask for horizontal and vertical direction.
–1 –2 –1 –1 0 –1
0 0 0 –2 0 2
–1 2 –1 –1 0 –1
Sobel Mask for Sobel mask for
horizontal direction vertical direction
Image Segmentation 5.33

7. Draw the prewift mask for horizontal and vertical direction.

–1 –1 –1 –1 0 1
0 0 0 –1 0 1
1 1 1 –1 0 1
Mask for Mask for
horizontal direction vertical direction
8. Draw the laplacian mask
0 –1 0
–1 4 –1
0 –1 0
9. What are the various techniques used for edge linking and boundary detection?
(i) Local processing,
(ii) Global processing using Hough transform,
(iii) Global processing via graph theoric approach.
10. What is directed graph?
The graph in which the edges are directed is known as directed graph.
11. What is the use of local thresholding?
Local (or) regional thresholding is used to denote variable thresholding in
which the value T at any point (x, y) in an image depend the properties of a
neighbourhood of (x, y)
12. What is the process of region growing by pixel aggregation?
Here, a set of seed points are used as starting points. From the starting point,
regions grow by appending neighbouring pixels which have similar properties.
13. What is the need of representation of object boundary?
The representation of the object boundaries is important for the analysis of
shape.
14. What is the use of chain code technique?
The chain code technique is simple and effectively used to represent the
boundary of an object.
15. What is Euler number?
E=C–H
C – Number of connected components,
H – Number of holes
5.34 Digital Image Processing

3.12. REVIEW QUESTIONS

1. Explain the topic of detection of discontinuities.

2. Write short notes on
(i) Local processing,
(ii) Optimal thresholding
3. Write short notes on,
(i) Basic rules for segmentation,
(ii) Region growing by pixel aggregation
4. Write short notes on,
(i) Boundary representation using chain codes.
(ii) Polygonal approximation
5. Explain about boundary descriptors.
6. Explain about regional descriptors.
7. Explain about ‘texture’.