Image Segmentation

1
In previous modules w e tried to improve t h e
i m a g e for b e t t e r visualization

N o w w e will t r y t o r e t r i e v e s o m e i n f o r m a t i o n
f r o m i m a g e for h i g h level a n a l y s i s

2
Image segmentation
● Division of a n i m a g e i nt o r e g i o n s o r c a t e g o r i e s , w h i c h
c o r r e s p o n d t o d i ff e r e n t o b j e c t s o r p a r t s of o b j e c t s

To r e p r e s e n t m e a n i n g f u l
areas

Other applications such a s n u m b e r

Plate detection, satelite imaging etc.

3
Image segmentation

Discontinuity b a s e d Similarity b a s e d
● P a r t i t i o n is c a r r i e d o u t ● G r o u p t h o s e pixels

based on abrupt change w h i c h a r e similar in

in i n t e n s i t y v a l u e s some sense
F o c u s is o n identifying Te c h n i q u e s u s e d s u c h a s
1. Points 1. Thresholding
2 . Lines 2. Region growing
3. Edges 3 . R e g i o n splitting a n d m e r g i n g

4
Discontinuity b a s e d i m a g e s e g m e n t a t i o n
M a i n f o cu s is t o find i s o l a t e d p o i n t s , lin es a n d
●
e d g e s in t h e i m a g e
This c a n b e a c h i e v e d b y a p p l i ca t i o n of m a s k
●
like w e h a v e d i s c u s s e d in s p a t i a l filtering

OR

5
Discontinuity b a s e d i m a g e s e g m e n t a t i o n
● Isolated point detection
|R| > T
T is t h r e s h o l d v a l u e
(non negative)

6
Discontinuity b a s e d i m a g e s e g m e n t a t i o n
● Line d e t e c t i o n
Moving first m a s k o v e r e n t i r e i m a g e
D e t e c t s p o i n t s lying o n h o r i z o n t a l
line
We can a p p l y all m a s k s o v e r i m a g e
a n d Find th e R value

7
Detection of Discontinuities Line Detection

8
Discontinuity b a s e d i m a g e s e g m e n t a t i o n
● Edge detection:
D e t e c t i n g t h e d isco n tin u ity in i m a g e
●
Edge: Boundary between two regions having
d i s t i n c t i n t e n s i ty v a l u e s

9
Detection of Discontinuities Edge Detection

10
Detection of Discontinuities Edge Detection

11
Detection of Discontinuities Edge Detection

12
Detection of Discontinuities Edge Detection

13
Detection of Discontinuities Edge Detection

14
 Detection of Discontinuities Gradient Operators

• First-order derivatives:
– The gradient of an image f(x,y) at location (x,y)is
defined as the vector:
G x 
f = =
G y 
– The magnitude of this vector: f = mag(f) =

– The direction of this vector:  Gx 

 (x, y) = tan  
−1

Gy 
– It points in the direction of the greatest rate of change of f
at location (x,y) 15
Detection of Discontinuities Gradient Operators

16
 Detection of Discontinuities Gradient Operators

Roberts cross-gradient operators

Prewitt operators

Sobel operators

17
 Detection of Discontinuities Gradient Operators

Prewitt masks for

detecting diagonal edges

Sobel masks for detecting

diagonal edges

18
 Output Image
Input Image By h o r i z o n t a l
Sobel operator

Output Image Output Image

By ve rt i c a l By c o m b i n e d
Sobel operator Sobel operator

19
 Detection of Discontinuities Gradient Operators:
Example

f  Gx + G y

20
 Detection of Discontinuities Gradient Operators:
Example

21
 Detection of Discontinuities Gradient Operators:
Example

22
 Detection of Discontinuities Gradient Operators:
Example

23
 Detection of Discontinuities Gradient
Operators

• Second-order derivatives: (The Laplacian)

– The Laplacian of an 2D function f(x,y) is defined as
2 f 2 f
 f = 2 + 2
2
x y

– Two forms in practice:

24
Edge detection
● S e c o n d d e r i v a t iv e o p e r a t o r - L a p l a c i a n
2 ∂2 f ∂2 f
∇ f = +
∂x 2
∂ y2

● G e n e r a l l y n o t u s e d , b e c a u s e it is v e r y
s e n s e t i v e t o noi se
● To r e d u c e t h e effect of n o i s e first i m a g e
is s m o o t h e n e d

25
Edge detection
● For smoothening purpose Gaussian operator
is u s e d
● After s m o o t h e n i n g L a p l a c i a n o p e r a t o r is a p p l i e d
● This is c a l l e d a s L a p l a c i a n of G a u s s i a n (LoG)
● This will r e d u c e s t h e effect of n o i s e

26
 Edge detection
● Gaussian mask:
2
−x2 + y
2 σ2
h( x , y) = e

● L a p l a c i a n of G a u s s i a n
2
−x2 + y
2 (r − σ ) 2 2
2 σ2
∇ h( x , y) = ⋅e
σ 4

Ref: https: //en.wikipedia.org/wiki/Laplace%27s_equation

27
 LoG i de nt ifies l oc a t i on
Of e d g e in i m a g e
Edge detection

LoG m a s k Input Image Sobel Output LoG O u t p u t

Image Image

28
Local P r o c e s s i n g A p p r o a c h
● Apply e d g e o p e r a t o r o n i m a g e t o g e t e d g e d e t e c t e d i m a g e .
● A n a l y s e e a c h pixel in s m a l l n e i g h b o r h o o d of (x,y)
1. All p o i n t s s i m i l a r in n a t u r e a r e l i n k e d
2 . This f o r m s a b o u n d a r y of p ix els t h a t a r e s i m i l a r in n a t u r e
● S i mi l a r i t y m e a s u r e s
3 . S t r e n g t h of t h e r e s p o n s e of g r a d i e n t
4 . D i r e c t i o n of g r a d i e n t

29
Local P r o c e s s i n g A p p r o a c h
(x' , y' ) ∈ N
(x , y )

(x' , y' ) a n d (x , y) a r e similar if

| ∇ f ( x , y ) − ∇ f ( x' , y' )| < T S t r e n g t h of g r a d i e n t a t lo catio n (x,y)

a n d a t lo c a tio n (x’,y’) m u s t b e c l o s e

| α ( x , y) − α ( x' , y' )| < A Angle of g r a d i e n t a t lo c a tio n (x,y)

a n d a t lo c a tio n (x’,y’) m u s t b e c l o s e

T is g r a d i e n t s t r e n g t h t h r e s h o l d a n d Alpha is g r a d i e n t a n g l e
threshold 30
Global P r o c e s s i n g A p p r o a c h
● Ideally d is co n tin uity d e t e c t i o n t e c h n i q u e s s h o u l d idetify pixels
lying b o u n d a r y
● B o u n d a r y is a r e g i o n w h e r e t r a n s i t i o n f r o m low i n t e n s i ty v a l u e t o
h i g h i n t e n s i ty v a l u e
● B u t in p r a c t i c e o f t e n t h e s e b o u n d a r y p o i n t s a r e n o t c o n n e c t e d d u e
t o p o o r illumination o r n o i s e
● Local p r o c e s s i n g is b a s e d o n n e i g h b o r h o o d s , b u t it is a v e r y s ma l l
region
● This m a y n o t link t h e pixels w h i c h a r e f a r a w a y t h a n n e i g h b o r h o o d

31
E d g e linking
● H o u g h Tr a n s f o r m : M a p p i n g of a s p a t i a l d o m a i n
in to p a r a m e t e r d o m a i n
Y
F o r a p a r t i c u l a r s t r a i g h t line s l o p e a n d
y = mx + c I n t e r c e p t is c o n s t a n t y = m 1 x + c 1

m 1 is s l o p e of t h e line a n d
c 1 is t h e i n t e r c e p t of t h e line
X

Slope intercept form

32
E d g e linking
● H o u g h Tr a n s f o r m : M a p p i n g of a s p a t i a l d o m a i n
in to p a r a m e t e r d o m a i n
Y c

y1 = mx1 + c
c1 ● (m1, c1)
Line is m a p p e d
t o single p o i n t
X m
m1
Slope intercept form Parameter space

33
E d g e linking
● H o u g h Tr a n s f o r m : M a p p i n g of a s p a t i a l d o m a i n
in to p a r a m e t e r d o m a i n
Y c

● (x1, y 1) Poi nt is m a p p e d c 1 = -m1x + y

t o line

X m
Slope intercept form Parameter space

34
E d g e linking
Y c
(x2, y 2) c = -mx1 + y 1
c = -mx2 + y 2
2 Points a r e
M a p p e d t o 2 line s ● ( c 1, m 1 )
(x1, y 1)
X m

Slope intercept form Parameter space

35
E d g e linking
c = - 3m + 3
c c = - 2m + 2
Y
(0 ,3 )
(3, 3 )
2 Points a r e (0 ,2 )
M a p p e d t o 2 l i ne s
(2, 2 ) (1, 0) = ( m , c )
m
X
c = - 2m + 2
Slope intercept form c = - 3m + 3

36
E d g e linking
● U s i n g H o u g h t r a n s f o r m w e find w h e t h e r p o i n t s a r e
colinear or not.
● Problem:
C h e c k w h e t h e r t h e p o i n t s (1,1), (2,2), ( 3 , 3 ) a r e
colinear or not

37
E d g e linking H o u g h T r a n s f o r m E x a m p l e
● S t e p 1 C o n v e r t p o i n t s f r o m (x,y) p l a n e t o ( m, c ) p l a n e
E q u a t i o n of line is y = m x + c
g i v e n p o i n t s (1,1), (2,2), ( 3 , 3 )
1 . (x,y) = ( 1 , 1 ) = > 1 = 1 m + c = > c = -m + 1
if m = 0 t h e n c = 1
if c = 0 t h e n m = 1 t h e r e f o r e ( m, c ) = ( 1 , 1 )

38
E d g e linking H o u g h T r a n s f o r m E x a m p l e
● S t e p 1 C o n v e r t p o i n t s f r o m (x,y) p l a n e t o ( m, c ) p l a n e
E q u a t i o n of line is y = m x + c
g i v e n p o i n t s (1,1), (2,2), ( 3 , 3 )
2 . (x,y) = ( 2 , 2 ) = > 2 = 2 m + c = > c = - 2 m + 2
if m = 0 t h e n c = 2
if c = 0 t h e n m = 1 t h e r e f o r e ( m, c ) = ( 1 , 2 )

39
E d g e linking H o u g h T r a n s f o r m E x a m p l e
● S t e p 1 C o n v e r t p o i n t s f r o m (x,y) p l a n e t o ( m, c ) p l a n e
E q u a t i o n of line is y = m x + c
g i v e n p o i n t s (1,1), (2,2), ( 3 , 3 )
3 . (x,y) = ( 3 , 3 ) = > 3 = 3 m + c = > c = - 3 m + 3
if m = 0 t h e n c = 3
if c = 0 t h e n m = 1 t h e r e f o r e ( m, c ) = ( 1 , 3 )

40
E d g e linking H o u g h T r a n s f o r m E x a m p l e
● S t e p 2: U s i n g ( m , c ) p o i n t s d r a w lines in m-c p l a n e
c

3
Points a r e
(1,1), (1,2), ( 1 , 3 ) In te r s e c t ion
2 Poi nt (1, 0)

1 All lines i n t e r s e c t a t
1 ( m, c ) = ( 1 , 0 )
m

41
E d g e linking H o u g h T r a n s f o r m E x a m p l e
● S t e p 3 : P u t t h e v a l u e of ( m , c ) = ( 1 , 0 ) in t h e ori gi nal
e q u a t i o n of line
y = mx + c = > y = x
● S t e p 4 : C h e c k t h e ori gi nal p o i n t s ( f r o m x-y p l a n e )
satisfy t h e e q u a t i o n y = x
(1,1), (2 , 2 ), ( 3 , 3 ) p o i n t s satisfy t h e e q u a t i o n h e n c e
these points a r e colinear

42
E d g e linking H o u g h T r a n s f o r m E x a m p l e
S t e p 4: C h e c k t h e or i gi nal p o i n t s ( f r o m x-y p l a n e )
satisfy t h e e q u a t i o n y = x
(1,1), (2,2), ( 3,3) p o i n t s satisfy t h e e q u a t i o n h e n c e
these points a r e colinear
y
y= x

43
Hough
Transform

44
 Thick e d g e s
a n d noise
Canny Edge detection
Op t im a l

Thick e d g e s

??
45
C a n n y E d g e D e t e c t i o n A lg o rithm
● S mo o t h i n g : B lurring of t h e i m a g e t o r e m o v e n o ise .
● Finding gradients: The e d g e s should b e ma rk e d w h e re
t h e g r a d i e n t s of t h e i m a g e h a s l a rg e m a g n i t u d e s .
● N o n - m a x i m u m s u p p r e s s i o n : Only local m a x i m a s h o u l d b e
marked as edges.
● D o u b le t h r e s h o l d i n g : P o t e n t i a l e d g e s a r e d e t e r m i n e d by
thresholding.
● E d g e t r a c k i n g by h y s t e r e s i s : F in a l e d g e s a r e d e t e r m i n e d
by s u p p r e s s i n g all e d g e s t h a t a r e n o t c o n n e c t e d t o a v e ry
certain (strong) edge.
46
C a n n y E d g e D e t e c t i o n A lg o rithm
1. S m o o t h i n g : B l u r r i n g of t h e i m a g e t o r e m o v e n o i s e .
● E g . Apply G a u s s i a n filter t o s m o o t h e n t h e i m a g e

47
C a n n y E d g e D e t e c t i o n A lg o rithm
2. F i n d i n g g r a d i e n t s : To find t h e e d g e s u s e s o b e l
o p e r a t o r s in X a n d Y d i r e c t i o n Gx a n d G y

C a l c u l a t e s t r e n g t h of t h e g r a d i e n t G
|G| =

48
C a n n y E d g e D e t e c t i o n A lg o rithm
2. F i n d i n g g r a d i e n t s : O u t p u t s h o w i n g G r a d i e n t m a g n i t u d e s
in i m a g e i.e e d g e s in i m a g e
Thick e d g e s

E d g e s a r e ve ry t hi c k a n d b r o a d
H e n e e x a c t l oc a t i on is u n k n o w n ! !

49
C a n n y E d g e D e t e c t i o n A lg o rithm
2. F i n d i n g g r a d i e n t s a n g l e : To find t h e e x a c t l ocat i on of t h e
e d g e a n g l e of g r a d i e n t is i m p o r t a n t
C a l c u l a t e a n g l e of t h e g r a d i e n t G u s i n g

θ = tan−1
|Gy|
|G x|
This a n g l e i n f o r ma t i o n is u s e d in n o n m a x i m a l s u p p r e s s i o n

50
C a n n y E d g e D e t e c t i o n A lg o rithm
3 . N o n - m a x i m u m s u p p r e s s i o n : T h e p u r p o s e of t h i s s t e p is t o
c o n v e r t t h e “ b l u r r e d ” e d g e s in t h e i m a g e of t h e g r a d i e n t
magnitudes to “sharp” edges
● P r e s e r v e local m a x i m a in g r a d i e n t
i m a g e a n d r e m o v e e v e r y t h i n g else.
● A p p r o x i m a t e a n g l e of g r a d i e n t a t
e v e r y pixel by its n e a r e s t 4 5 d e g r e e
mu l t i p l e

51
C a n n y E d g e D e t e c t i o n A lg o rithm
3 . N o n - m a x i m u m s u p p r e s s i o n : C o m p a r e t h e pixels in + v e a n d -ve
d i r e c t i o n of g r a d i e n t
● If m a x i m u m a n d its m a g n i t u d e is g r e a t e r t h a n t h e u p p e r
t h r e s h o l d t h e n m a r k it a s a e d g e pixel

52
C a n n y E d g e D e t e c t i o n A lg o rithm
3 . N o n - m a x i m u m s u p p r e s s i o n : C o m p a r e t h e pixels in + v e a n d -ve
d i r e c t i o n of g r a d i e n t
● If m a x i m u m a n d its m a g n i t u d e is g r e a t e r t h a n t h e u p p e r
t h r e s h o l d t h e n m a r k it a s a e d g e pixel

53
C a n n y E d g e D e t e c t i o n A lg o rithm
4. D o u b l e T h r e s h o l d i n g : M a n y of t h e e d g e s in t h e i m a g e
a f t e r n o n m a x i m a l s u p p r e s s i o n a r e t r u e b u t s o m e a r e fal s e
d u e t o n o i s e in i m a g e
● E d g e pixels s t r o n g e r t h a n t h e h i g h t h r e s h o l d a r e m a r k e d
a s s t r o n g e d g e pixels; w e a k e r t h a n t h e low t h r e s h o l d a r e
s u p p r e s s e d a n d e d g e pixels b e t w e e n t h e t w o t h r e s h o l d s
ar e marked as weak.

54
C a n n y E d g e D e t e c t i o n A lg o rithm
5. E d g e t r a c k i n g by h y s t e r e s i s : We a k e d g e s a r e k e p t only if
they a r e connected to strong edges

55
S e g m e n t a t i o n u s i n g Similarity B a s e d
Approach
● Similarity b a s e d s e g m e n t a t i o n
Only local a n d gl oba l
● Thresholding are to be reviewed

1. Global t h r e s h o l d i n g
2. Dynamic or adaptive threshold
3. Optimal threshold
4.Local t h r e s h o l d i n g
● Region growing technique
● R e g i o n s pl i t t ing a n d m e r g i n g t e c h n i q u e
56
 Similarity b a s e d S e g m e n t a t i o n
Th r e s h o ld in g Ob jec t Background

● S u p p o s e a n i m a g e f(x,y) is
having a dark object against
bright background
● Such image g e n e r a t e bimodal
histogram
f ( x , y) < T implies object
f ( x , y) ≥ T implies background Threshold T
57
Similarity b a s e d S e g m e n t a t i o n
● Thresholding example

Th r e s h o ld in g

Input image Segmented output image

58
 Similarity b a s e d S e g m e n t a t i o n
Thresholding
Tr i mo d a l h i s t o g r a m

f ( x , y) > T 2 implies object 2

T 1 < f ( x , y) ≤ T 2 implies object 1

f ( x , y) < T 1 implies background

T1 T2
59
 Similarity b a s e d S e g m e n t a t i o n
● S e l e c t i o n of t h r e s h o l d v a l u e
● Thresholding function which test t h e image
against threshold value
T = T [ x , y , p( x , y), f ( x , y)] Depending on combination
Of t h e s e t h r e e v a l u e s
Thresholding can b e
(x,y) = c o o r d i n a t e s of t h e pixels 1. Local
2. Global
f(x,y) = i n t e n s i t y v a l u e of t h e pixels 3. Ada pt i ve
4. Optimal
p(x,y) = local p r o p e r t y in n e i g h b o r h o o d
C e n t e r e d a t (x,y)
60
Similarity b a s e d S e g m e n t a t i o n
● If T[f(x,y)] t h e n it is global t h r e s h o l d i n g
● If T[f(x,y), p(x,y)] t h e n it is local t h r e s h o l d i n g
● If T[(x,y), f(x,y), p(x,y)] t h e n it is Ad ap tiv e
thresholding
g(x , y ) = 0 if f (x , y) > T O b j e c t pixel

g( x , y ) = 1 if f (x , y) ≤ T B a c k g r o u n d pixel

61
Similarity b a s e d S e g m e n t a t i o n
● H o w t o find t h r e s h o l d v a l u e ?
● E v e r y t i m e looking a t t h e h i s t o g r a m a n d
d e c i d i n g is n o t f e a s ib l e
● N e e d s o m e a u t o m a t e d p r o c e s s for
threshold selection

62
Similarity b a s e d S e g m e n t a t i o n
● A u t o m a t i c g lo b a l t h r e s h o l d i n g :
1. Initialize v a l u e of t h r e s h o l d T
2. Perform segmentation using threshold
value T to get two regions G1 a n d G2

Pixel i n t e n s i ty v a l u e s f r o m g r o u p G 1 a n d G 2
a r e s imila r b u t t w o g r o u p s d i ff e r e n t

63
Similarity b a s e d S e g m e n t a t i o n
● A u t o ma t i c g l o b a l t h r e s h o l d i n g :
1. Initialize v a l u e of t h r e s h o l d T
2. Perform segmentation using threshold value T to get two
regions G1 a n d G2
3 . C o m p u t e m e a n M 1 a n d M 2 u s i n g pixel i n t e n s i t y v a l u e s of
G1 a n d G2
4 . N e w threshold value T = (M1 + M2)/2 T’ is s o m e
tolarance value
5. If (|Ti – T(i+1)| < = T’) t h e n STOP
6. else goto step 2
64
Similarity b a s e d S e g m e n t a t i o n
● A u t o m a t i c global t h r e s h o l d i n g e x a m p l e :

Input Image

Output Image after

a p p l i c a t i o n of
A u t o m a t i c gl oba l
thresholding

65
Similarity b a s e d S e g m e n t a t i o n
● A u t o m a t i c global t h r e s h o l d i n g :
Gobal t h r e s h o l d i n g gives v e r y g o o d r e s u l t s if
i n t e n s i t y of illumination is u n i f o r m
● I n s u c h c a s e g e t t i n g a global t h r e s h o l d v a l u e is
difficult

66
 Similarity b a s e d S e g m e n t a t i o n
A u t o ma t i c global
t h r e s h o l d i n g for
p o o r i l l u mi n a t e d
image

I m a g e in n o n
u n i f o r m i l l umi nati on
source

67
 Similarity b a s e d S e g m e n t a t i o n
A u t o ma t i c global
t h r e s h o l d i n g for
p o o r i l l u mi n a t e d
im a g e
H i s t o g r a m is b i m o d a l
B u t valley is n o t
Well d e f i n e d
I m a g e in n o n
u n i f o r m i l l umi nati on
source

68
 Similarity b a s e d S e g m e n t a t i o n
A u t o ma t i c global
t h r e s h o l d i n g for
p o o r i l l u mi n a t e d
image

A u t o ma t i c gl obal
thresholding
is likely t o fail!!!

69
 Similarity b a s e d S e g m e n t a t i o n
● S o l u t i on for p o o r illumination p r o b l e m of g l o b a l t h r e s h o l d i n g
Divide t h e i m a g e into n u m b e r of s u b - i m a g e s s o t h a t
illumination c a n b e u n i f o r m
● F i n d t h e g l o b a l t h r e s h o l d v a l u e for s u b - i m a g e s
● U n i o n of all t h r e s h o l d v a l u e s gives t h e final t h r e s h o l d
● This is c a l l e d a s a n a d a p t i v e t h r e s h o l d i n g a s t h e t h r e s h o l d
v a l u e is d e p e n d o n t h e l o c a t i o n in i m a g e

70
 Similarity b a s e d S e g m e n t a t i o n
● Sol ut i on for p o o r i l lumination p r o b l e m of gl obal
t h r e s h old in g

71
 Similarity b a s e d S e g m e n t a t i o n
● Sol ut i on for p o o r i l lumination p r o b l e m of gl obal
t h r e s h old in g Threshold is d o m i n a t e d
By t h i s r e g i o n

72
 Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g

Global t h r e s h o l d i n g
is likely t o fail h e r e ! ! ! Solution:
C o n s i d e r local i m a g e a n d a p p l y t h e t h r e s h o l d i n g
This c o n v e r t s t h e h i s t o g r a m in to b i mo d a l
a n d e q u a lly d i s t r i b u t e d in o b j e c t a n d b a c k g r o u n d
region

73
 Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g

Global t h r e s h o l d i n g Local t h r e s h o l d i n g
is likely t o fail h e r e ! ! ! Wo r k s h e r e

74
 Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g

Global t h r e s h o l d i n g Local t h r e s h o l d i n g
is likely t o fail h e r e ! ! ! Wo r k s h e r e

BUT H O W TO DETECT LOCAL BOUNDARY

BE T W EEN OBJECT AND BACKGROUND?
75
Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g – B o u n d a r y d e t e c t i o n u s i n g
Gradient a n d Laplacian

G r a d i e n t g iv e s p o s ition of
The edge whereas

Laplacian Determines
w h e t h e r p o i n t Lies o n
darker side or brighter
S i d e of t h e e d g e

76
Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g – B o u n d a r y d e t e c t i o n u s i n g
Gradient a n d Laplacian

G r a d i e n t g iv e s p o s ition of
The edge whereas

Laplacian Determines
w h e t h e r p o i n t Lies o n
+ ve darker side or brighter
- ve S i d e of t h e e d g e

77
 Similarity b a s e d S e g m e n t a t i o n
● Local T h r e s h o l d i n g – B o u n d a r y d e t e c t i o n u s i n g
Gradient a n d Laplacian
using three properties f ( x , y) ∇ f ( x) ∇ 2 f ( x , y )
s( x , y) = 0 if ∇ f ( x , y ) < T Not belong to boundary

= +ve if ∇ f ( x , y) ≥ T ∇ 2 f ( x , y) ≥ 0 B e l o n g s to Object

= − ve if ∇ f ( x , y) ≥ T ∇ 2 f ( x , y) < 0 B e l o n g s to Background

78
 Similarity b a s e d S e g m e n t a t i o n
Local T h r e s h o l d i n g –
Boundary detection using Gradient
a n d Laplacian

This i m a g e is u s e d t o
Findout object region
And b a c k g r o u n d i m a g e

79
 Similarity b a s e d S e g m e n t a t i o n
Local T h r e s h o l d i n g –
Boundary detection using Gradient
a n d Laplacian

S c a n e a c h r o w of t h e i m a g e f r o m left t o r i g h t
● (- , + ) i n d i c a t e s t r a n s i t i o n f r o m b a c k g r o u n d t o
object
● ( + , -) i n d i c a t e s t r a n s i t i o n f r o m o b j e c t t o
background
● (......***)(-, + ) ( 0 o r + ) ( + , -) (***.....)

80
 Similarity b a s e d S e g m e n t a t i o n
Local T h r e s h o l d i n g –
Boundary detection using Gradient
a n d Laplacian

(......***)(-, + ) ( 0 o r + ) ( + , -) (***.....)

Ob jec t Any c o m b i n a t i o n of
-, + o r 0

81
 Region-Based Segmentation

• Edges and thresholds sometimes do not give good

results for segmentation.
•
Region-based segmentation is based on the
connectivity of similar pixels in a region.
– Each region must be uniform.
– Connectivity of the pixels within the region is very
• important.
There are two main approaches to region-based
segmentation: region growing and region splitting. 82
 Region-Based Segmentation
Basic Formulation
Let R represent the entire imageregion.
• Segmentation is a process that partitions R into subregions,
• R1,R2,…,Rn, such that

where P(Rk): a logical predicate defined over the points inset Rk

For example: P(Rk)=TRUE if all pixels in Rkhave the samegray level. 83
 Region Growing
• 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
84
 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
85
Similarity b a s e d S e g m e n t a t i o n
● Region growing segmentation
G r o u p i n g t h e pixels t o m a k e l a r g e r s u b r e g i o n s
s u c h t h a t p r o p e r t i e s of n e w l y a d d e d pixels m u s t b e
sa m e

S e e d points

86
 Similarity b a s e d S e g m e n t a t i o n
● Region growing segmentation
M a k e 3X3 n e i g h b o r h o o d (4, 8 o r m - c o n n e c t e d )
a r o u n d s e e d p o i n t a n d c h e c k for t h e i n t e n s i ty
values

If d i ff e r e n c e in i n t en s ity v a l u e s
is v er y l a r g e t h e n Don’t in c lu d e
in t h e s e t Seed points

87
 Similarity b a s e d S e g m e n t a t i o n
● Region growing segmentation
T h re s h o ld in g
Output

X-Ray i m a g e of Cracks a r e indicated

We l d e d p a r t N e a r 255 value

88
 Similarity b a s e d S e g m e n t a t i o n
● Region growing segmentation

X-Ray i m a g e of
We l d e d p a r t

Perform region
Select seed points Growing operations
With v a l u e 2 5 5 On e a c h s e e d point
I n O r ig inal I m a g e

89
 Region Growing Algorithm
• Consider image shown in figure:

•Assume seed point indicated by underlines. Let the seed pixels 1 and 9
represent the regions C and D, respectively

•Subtract pixel from seed value

•If the difference is less than or equal to 4 (i.e. T=4), merge the pixel with that
region. Otherwise, merge the pixel with the other region.
90
 Split and Merge Algorithm
• Region growing algorithm is slow
• So seed point can be extended to a seed region
• Instead of a single pixel, a node of a Regional adjacency graph (RAG)
a region itself is now considered as a starting point.

• The split process can be stated as follows:

1)Segment the image into regions R1, R2,….Rn using a set of thresholds
2)Create RAG. Use a similarity measure and formulate a homogeneity test
3)The homogeneity test is designed based on the similarity criteria such as
intensity or any image statistics
4) Repeat step 3 until no further region exits that requires merging
91
 Split and Merge Algorithm
•

8 8 8
8 8 8

92
Region-Based Segmentation
Region Growing

93
 Region-Based Segmentation
Region Growing
• (a). It is difficult to segment the defects by thresholding methods.
(Applying region growing methods are better in thiscase.)

94
 Split and Merge using Quadtree

•Entire image is assumed as a single region. Then the homogeneity test is

applied. If the conditions are not met, then the regions are split into four
quadrants.

•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.

•1) 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.
•2) Merge adjacent regions if the regions share any common criteria. Stop the
95
process when no further merging is possible
 Region-Based Segmentation
Region Splitting and Merging
• Region splitting is the opposite of regiongrowing.
– First there is a large region (possible the entire
image).
– Then a predicate (measurement) is used to
determine if the regionis uniform.
– If not, then the method requires that the region be
split into two regions.
– Then each of these two regions isindependently
tested by the predicate (measurement). 96
 Region-Based Segmentation
Region Splitting
• The main problem with region splitting is determining whereto split
a region.
• One method to divide a region is to use a quadtree structure.
• Quadtree: a tree in which nodes have exactly four descendants.

97
 Region-Based Segmentation
Region Splitting and Merging
The split and merge procedure:
– Split into four disjoint quadrants any region Ri which P(Ri) =FALSE.
– Merge any adjacent regions Rj and Rk for which P(RjURk) = TRUE.
(the quadtree structure may not be preserved)
– Stop when no further merging orsplitting is possible.

98
 Expected Questions..

- Short Notes on Image Segmentation Types- Discontinuity

based and similarity based
- Discontinuity based operators- Robert, Sobel, Prewitt
- Discontinuity based Canny Edge Detection Algorithm

- Short note on similarity based segmentation and Thresholding

- Short note on similarity based segmentation and Region
Growing Technique
- Short note on similarity based segmentation and Splitting-
Merging Technique
99