Image Segmentation

Objectives

• Understand the basics about image segmentation.

• Apply topics such as derivatives, gradients, histograms

and morphological operations with applications on
segmentation.
 Introduction

• Segmentation: divide an image into regions or objects

• Find regions or objects based on:
a) Discontinuities (abrupt changes in intensity)

b) Similarities (some common criteria, e.g. texture)

3
 Outline

1.Point, Line and Edge Detection

(Features Detection)
2.Hough Transform
3.Thresholding
4.Region-Based Segmentation
5.Morphological Watersheds

4
Edge Detection
• Convert a 2D image into a set of curves
●Extracts salient features of the scene
●More compact than pixels

5
Edges
• Edges are caused by a variety of factors

surface normal
discontinuity

depth
discontinuity

surface color
discontinuity
illumination
discontinuity
6
Edges
• Edge is Where Change Occurs
• Change is measured by derivative in 1D
• Biggest change, derivative has maximum magnitude
• Or 2nd derivative is zero.

7
Image Gradient
• The gradient of an image:
• The gradient points in the direction of most rapid change
in intensity

Horizontal Edge Vertical Edge

8
Image Gradient
• gradient direction

• The edge strength

• Discrete Gradient: by finite differences

f(x+1,y) – f(x,y)
f(x, y+1) – f(x,y)

9
Types of Edges

10
 Point, Line and Edge Detection

• Detection & Segmentation

- Segmentation based on local changes in intensity (points, lines,
edges)
- Detection of those features helps in segmentation

• Detection using spatial filtering

11
 Point, Line and Edge Detection
Background

• Detect changes in intensity using derivatives

• In 1-D:
- First-order derivative
f
 f '(x)  f (x 1)  f (x)
x
- Second-order derivative

2 f
 f (x 1)  f (x 1)  2 f (x)
x 2

• In 2-D:
- Filtering with a mask (e.g. Sobel, Laplacian)

12
Point, Line and Edge Detection
Background

Intensity profile
along the line

13
 Point, Line and Edge Detection
Background

• Characteristics of first-order derivatives

- Generally produce thicker edges in image ‫ينتج بشكل عام حواف‬
‫أكثر سم ًكا في الصورة‬

• Characteristics of second-order derivatives

- Stronger response to fine detail (thin lines, isolated points, noise)
- Double-edge ‫استجابة أقوى للتفاصيل‬
(-2___________________-4) ‫ نقاط‬، ‫الدقيقة (خطوط رفيعة‬
(-6___________________-12) ‫ ضوضاء(منعزلة‬،
response at ramp and step transition
- The sign (+or -) determines whether a transition is light to dark or
dark to light

14
 Point, Line and Edge Detection
Point Detection

• Procedure: use Laplacian and then detect highest values

• The Laplacian

 2
f  2
f
2 f (x, y)  2  2
x y

 f (x 1, y)  f (x 1, y)  f (x, y 1)  f (x, y 1)  4 f (x, y)

• Detection of highest values (points):

1 if | R(x, y) | T 9
R   wk z k
g(x, y)  
0 otherwise k 1

T: threshold
15
 Point, Line and Edge Detection
Point Detection
Point Detection
Mask(Laplacian)

Showing single
point using
‫شفرة التوربينات ذات المسامية‬ a threshold
contains a single black
technique
pixel

X-ray image Laplacian Threshold

16
 Point, Line and Edge Detection
Line Detection

• Possibilities: first derivative or second derivative

• Second derivatives:
- Stronger response and thinner lines (than first derivatives)
- Double-line effect (must be handled properly)

Laplacian of image

Note: +ve / -ve double

Line effect

Absolute value Positive values

of Laplacian Of Laplacian

17
 Point, Line and Edge Detection
Line Detection

• First Derivatives:
- Use line detection masks

- Then, threshold the result

18
 Point, Line and Edge Detection
Line Detection

• First Derivatives:
‫قالب‬ Mask 1 st
‫السندات‬ derivative
‫السلكية‬ of image

Zoomed
view of
Zoomed view of the
the top left region bottom
Right
region
ALL
Point
Satisfied
The image in (b) with all The
Negative values set to condition
zero Of (e)
Points
enlarged 19
 Point, Line and Edge Detection
Edge Models

• Edges: pixels where brightness function changes abruptly

• Edge models

Step (ideal edge) Ramp Roof edge

• Edges vs Boundaries
- Edge: local
- Boundary: global (encompasses a region)
- Edges often must be “linked” to form a boundary

20
 Point, Line and Edge Detection
Edge Models

2 pixels

9 pixels 3 pixels

21
 Point, Line and Edge Detection
Edge Models

• Properties of derivatives:

- 1st Derivative
• Detect using threshold
• Thick

- 2nd Derivative
• Two values for edge
• Detect zero-crossing
• Result is thinner

22
 Point, Line and Edge Detection
Edge Models

• Noise sensitivity:
- Derivative increasingly sensitive to noise with order derivative
- 1st derivative (gradient) better than 2nd derivative for noisy images

23
 Point, Line and Edge Detection
Edge Detection

• 1st derivative detection

- Image gradient  f 
 g x   x  edge normal
f  grad ( f )      
g f
 y  
 y 

- Magnitude
M (x, y)  mag(f )  g x  g y 2 2

f f
approximation: mag(f )  +
x y

- Direction
 gx 
 (x, y)  tan 1  
g
 y 
- Direction of the edge
   - 90∘
24
 Point, Line and Edge Detection
Edge Detection

• 1st derivative detection

25
 Point, Line and Edge Detection
Edge Detection

• 1st derivative detection

f
 f (x 1, y)  f (x, y)
x

f
 f (x, y 1)  f (x, y)
y
- Gradient operators (filters)

vertical & horizontal diagonal 26

 Point, Line and Edge Detection
Edge Detection

• Example (Sobel)

27
 Point, Line and Edge Detection
Edge Detection

• Example (Sobel, smooth first 5x5)

28
 Point, Line and Edge Detection
Edge Detection

• Example (Sobel, diagonal edges)

29
 Point, Line and Edge Detection
Edge Detection

• Example: thresholding

Gradient Threshold at 33%

approximation of highest value

Gradient Threshold at 33%

approximation of highest value
(from smoothed
image)

30
 Point, Line and Edge Detection
Edge Detection

• Laplacian of Gaussian (LoG)

- Usually smooth before using Laplacian
- Gaussian function
x2  y 2

G(x, y)  e 2 2

- Laplacian of Gaussian
 2 G(x, y)  2 G(x, y)
 G(x, y) 
2

x 2
y2
  x  2 2     y  2 2 
x2  y 2 x2  y 2

  2e   2 e 
x    y   
x y 2 2
x y 2 2
 x2 1   2 2  y 2 1   2 2
  4  2 e   4  2 e
     

x2  y 2
 x  y  
2 2 2 
2 G(x, y)   e
2 2

  4
 31
 Point, Line and Edge Detection
Edge Detection

• Laplacian of Gaussian (LoG)

32
 Point, Line and Edge Detection
Edge Detection

• Laplacian of Gaussian (LoG): Marr-Hildreth edge detector

1. Filter the input image with a Gaussian lowpass filter.

2. Compute the Laplacian of the image resulting from step1
3. Find the zero crossing of the image from step 2

• Can be written as:

g(x, y)   2 G(x, y)  f (x, y)

33
 Point, Line and Edge Detection
Edge Detection

• Laplacian of Gaussian (LoG): Marr-Hildreth edge detector

34
 Point, Line and Edge Detection
Edge & Boundary Detection

• Edges seldom connect to form a boundary (noise, non-uniform

illumination, etc)

• Edges can be linked based on similarities in:

- Magnitude of Gradient

- Direction of Gradient

• Once linked, edges can be assigned a unique color or grayscale value

(so they are not reused)

35
Point, Line and Edge Detection
Edge & Boundary Detection

36
 Point, Line and Edge Detection
Canny Edge Detector

• Used for step edges corrupted by white noise

• Goals
- Good detection: locate and mark all real edges
- Good localization: edges as close as possible to true edge
- Clear response: only one response per edge

• Stages

1. Smoothing (with Gaussian): f s (x, y)  G(x, y)  f (x, y)

2. Gradient detection (gradient magnitude and angle)
M (x, y)  g x 2  g 2 ,
y  (x, y)  atan(g y / g x )
3. Non-maxima suppression (of gradient magnitude) → to thin edges
4. Double thresholding and connectivity analysis → to detect and link edges

37
 Point, Line and Edge Detection
Canny Edge Detector

• Nonmaxima suppression
- Possible directions: d1: horizontal, d2 : -45, d3 : vertical, d4 : +45

Example of
“horizontal” edge

- For a 3x3 region centered at (x, y):

1. Find direction dk closest to α(x, y)
2. If M(x, y) < at least one of its 2 neighbors along dk, suppress it.

α(x, y): gradient angle, M(x, y): gradient magnitude 32

 Point, Line and Edge Detection
Canny Edge Detector

• Double (hysteresis) thresholding

- Two thresholds: TH (high/strong), TL (low/weak)
TL < TH
- Procedure
1. If M(x, y) > TH : accept as part of the boundary
→ This is a “strong” pixel

1. If TL < M(x, y) < TH: accept as part of the boundary only if it is connected
to a strong pixel (e.g. 8-connectivity).
→ This is a “weak” pixel

1. If M(x, y) < TL: reject as part of the boundary

M(x, y): gradient magnitude 33

 Point, Line and Edge Detection
Canny Edge Detector

• Example: using 2 different sets of thresholds

40
Point, Line and Edge Detection
Canny Edge Detector

41
 Outline

1.Point, Line and Edge Detection

2.Hough Transform
3.Thresholding
4.Region-Based Segmentation
5.Morphological Watersheds

42
Hough Transform ‫هاف ترنسفورم‬
 Hough Transform
‫هاف ترنسفورم‬
• Objective: detect lines

• Consider a point (xi, yi) (with different a and b)

- Infinitely many lines pass through (xi, yi) and all satisfy: yi  axi  b
- Considering the ab-plane: b  yi  axi single line for (xi, yi)

Image space Parameter space (Hough Space)

y b

(xi , yi ) b  yi  axi

x
a
Infinite lines through point (xi, yi) Single line for point (xi, yi)
Each line has a different a, b Infinitely many (a, b) along the line

46
 Hough Transform

• A line through 2 points (xi, yi), (xj, yj) is unique

- In parameter space, the line for (xi, yi) and the line for (xj, yj) intersect.

Image space Parameter space

- The (unique) intersection (in parameter space) defines the parameters (a’, b’)
of the line

• Problem: slope (a) approaches infinity as line approaches vertical

47
 Hough Transform y

• Solution: normal representation of a line

x
Line passing
through x cos   y sin   
(xi, yi), (xj, yj)
90    90

Two points >>> every point is sinusoid (curve)

• Parameter space for all lines passing through (xi, yi), (xj, yj) 


Intersection (ρ’, θ’) corresponds to
line passing through both (xi, yi)
and (xj, yj)

48
 Hough Transform

• Parameter space is divided into finite accumulator cells

• Divide parameter space into finite number of
cells
• Algorithm:

- Initially set cells to zero

- For every non-background point (xk, yk) increment
(+1) the cells that satisfy:   xk cos  yk sin
- At the end, a value P for cell (ρj, θj) means that P
points in the xy-plane line on the line defined by
(ρj, θj)

49
 These lines
Not exist in the
Hough Transform
Image , we
Set these lines
To imagine that
• Example These point align

- All lines passing through

each point are mapped
to sinusoids ρj
- Intersecting sinusoids
indicate a line
through points
o A indicates a line
passing through points
1, 3, 5.
o B indicates a line
passing through points
2,3,4

θj
50
 Hough Transform

• Example

Edge
detection

Hough
transform Detected
(strong
accumulations
lines
indicate lines)

51
Hough Transform

52
 Hough Transform
Other Curves

• Hough transform can link any curve defined as:

g(v, c)  0
- v: set of coordinates
- c: vector of coefficients

• Example: linking edges on a circle (x  c1 ) 2  ( y  c2 ) 2  c32

- Infinite circles passing through a point
- Parameter space has 3 components: c1, c2, c3 (3-D space)
- Accumulator cells are “cubes”

• With more parameters, complexity increases

53
 Outline

1.Point, Line and Edge Detection

2.Hough Transform
3.Thresholding
4.Region-Based Segmentation
5.Morphological Watersheds

54
 Thresholding

• Global threshold: applied to all the image

• Variable (local, regional) threshold: varies with neighborhood

• Simple thresholds:
- Two-level threshold

- Three-level threshold

55
 Thresholding
Role of Noise

• Noise alters the histogram → hard to find good threshold

56
 Thresholding
Role of Illumination

• Non-uniform illumination distorts the histogram

57
 Thresholding
Basic Global Thresholding

• Algorithm
- Guess an initial threshold T
(e.g. image mean)
- Segment using T
- Calculate a mean for each region:
m 1, m 2
- Update T:
m  m2
T 1
2
- Repeat until change in T < T0

• Works well if “reasonable” valley Segmented

separating object – background using global
thresholding
- Not always the case

58
 Thresholding
Optimum Global Thresholding: Otsu’s Method

• Optimum because it maximizes between-class variance

• Idea: intensity values of well-thresholded classes are distinct

Procedure
1. Normalized histogram:
ni L: intensity levels
pi  MxN: image size
MN ni: pixels with intensity i
2. Cumulative sums

- Set a threshold value k that defines 2 classes: C1  [0, k ], C2  [k 1, L -1]

- Cumulative sum for each class:
k L1
P1 (k )   pi P2 (k )  p i  1 P1 (k )
i0 ik 1

59
 Thresholding
Optimum Global Thresholding: Otsu’s Method

Procedure
3. Cumulative means
k
1 k
- Mean intensity of pixels in class C1: m1 (k )   iP(i | C1 )   ipi
i0 P1 (k ) i0
L1
1 L1
- Mean intensity of pixels in class C2: m2 (k )   iP(i | C2 )   ipi
ik 1 P2 (k ) ik 1

4. Global intensity mean

mG  P1m1  P2m2
5. Between-class variance
 P2 (m2  m ) 2
  P1 (m1  mG )
2
B
2
G

m P
2  G 1
 m 2

where
k
m(k )  ipi
B
P1 (1 P1 ) i0

60
 Thresholding
Optimum Global Thresholding: Otsu’s Method

Procedure
6. Otsu’s threshold
- It is the value k* that maximizes between-class variance
 B2 (k*)  max  B2 (k )
0k  L1

- How? Evaluate for all integer values of k and choose the “best” one
- Threshold with k*
1, if f (x, y)  k *
g(x, y)  
0, if f (x, y)  k *
7. Evaluate the separability measure
 B2
 2 𝜎𝐺2 : Global variance (all the image)
G

61
 Thresholding
Optimum Global Thresholding: Otsu’s Method

• Example:

Basic global Otsu’s

threshold method

62
 Thresholding
Image Smoothing to Improve Global Thresholding

• Smoothing can produce a bimodal histogram

63
 Thresholding
Edge Information to Improve Global Thresholding

• Procedure:
- Compute edges (magnitude of gradient or absolute value of Laplacian)
- Generate a “mask thresholding the edges (e.g. using high 90s percentile)
- Use the mask to select regions in the original image, then threshold the image

64
 Thresholding
Edge Information to Improve Global Thresholding

• Detect bright points

65
 Thresholding
Multiple Thresholds

• Extension of Otsu’s threshold method

• For K classes (C1, C2, …, CK), the between-class variance is:

K
   Pk mk  mG 
2 2
B
k 1

where Pk   pi and mk 
1
Pk
 ip i
iCk iCk

• Optimum threshold values k1*, k2*, …, kK-1* maximize

 B2 (k1 *, k 2 *, ..., k K 1 *)  max  B2 (k1 , k 2 , ..., k K 1 )

0k  L1

66
 Thresholding
Multiple Thresholds

• Example: dual Otsu threshold

67
 Thresholding
Variable Thresholding

• Subdivide image into nonoverlapping rectangles

• Rectangles chosen small enough so that illumination is uniform

68
 Thresholding
Multivariable Thresholding

• For color images use the color space

Histogram

Using a plane
in 3D

69
 Thresholding
Multivariable Thresholding

• A pixel has 3 values (colors): vector z in 3-D

• Example:

• Thresholding can be a distance computation

1, if D(z, a)  T z : color pixel

g
0, otherwise a : desired color

70
 Thresholding
Multivariable Thresholding

• Distance:
- Euclidean distance (hyper-sphere)
1
D(z, a)  (z  a)T (z  a)  2

- Mahalanobis distance (hyper-ellipse)

1
D(z, a)  (z  a)T C 1 (z  a)  2

 z z  aa
K
1
where C  k k
T T
is the covariance matrix
K k 1
K
1
Note: sometimes a is the mean of a region: a 
K
z k
k 1

71
 Outline

1.Point, Line and Edge Detection

2.Hough Transform
3.Thresholding
4.Region-Based Segmentation
5.Morphological Watersheds

72
 Region-Based Segmentation
Region Growing

• Idea: merge pixels (or regions) if they are similar (gray level intensity, color,
texture, …( and connected

• Homogeneity criterion (predicate) Q:

Q(Ri )  True i  1, 2, , N R Ri: region i
NR: number of regions
Q(Ri  R j )  False i  j and Ri adjacent to R j

• General procedure
- Start with set of “seed” points (with predetermined or distinct properties)
- From seed point grow regions: append neighbor pixels with properties similar
to the seed

73
 Region-Based Segmentation
Region Growing

• Example:
The seed for the object is the center of the image. Region is grown when the
difference between two pixel values is less than or equal to 5

Using 4-connectivity Using 8-connectivity

74
 Region-Based Segmentation
Region Growing

• Example

Region Growing

75
 Region-Based Segmentation
Region Growing

• Example

76
 Region-Based Segmentation
Region Splitting and Merging

• Idea: subdivide an image and then merge or split regions

• Procedure:
- For any region Ri, if Q(Ri)=False, divide the region into quadrants
- When no further splitting is possible, merge adjacent regions Rj and Rk if
Q(R j  Rk ) = True
- Stop when no further merging is possible

77
 Region-Based Segmentation
Region Splitting and Merging

• Example

78
 Outline

1.Point, Line and Edge Detection

2.Hough Transform
3.Thresholding
4.Region-Based Segmentation
5.Morphological Watersheds

79
 Morphological Watersheds

• Visualize the image in 3-D (topographic interpretation)

Watershed lines

• Types of points:
- Points in a regional minimum
- Points where a drop of water would fall to a single minimum (catchment
basin or watershed)
- Points where a drop of water would (equally likely) fall to more than one
minimum (divide lines or watershed lines)

80
 Morphological Watersheds

• Objective: find watershed lines

• Idea:
- Punch hole at each regional minimum & flood from bottom
- Construct “dams” at watershed lines to prevent merging
- Stop when maximum gray level is reached

81
 Morphological Watersheds

• Example

82
 Morphological Watersheds

• Often applied to image gradients (rather than images themselves)

83
 Conclusions

• Image segmentation is an essential preliminary step in

most automatic pattern recognition and scene analysis
applications.
• The choice of one segmentation technique over
another depends on the application.
 References

Gonzalez, Rafael C., and Richard E. Woods. Digital Image

Processing 3rd edition, 2008. (Chapter 10)

76