ENE 461 Class 11 (1/2008), August 29, 2008

Werapon Chiracharit, Ph.D.

werapon.chi@kmutt.ac.th

Object Segmentation
Binalization: Object = “1” and Background = “0”
• Global Thresholding ⇒ Histogram
• Adaptive Thresholding
- Separate image into many blocks and
threshold each block
- Local threshold, T(x,y) = IOpen(x,y) + TTophat
where IOpen is morphological opened image
TTophat is global threshold of ITophat
ITophat is top-hat operated image
2

1
 Region-Based Segmentation
Let Ri is a connected region
- Complete segmentation, R = ∪i Ri
- Disjoint region, Ri ∩ Rj = ∅ for ∀j ≠ i
- Same intensity in a region, P(Ri) = TRUE
- Different adjacent intensity, P(Ri∪Rj) = FALSE

R1

R2

Region Growing
1. Set seed points up to the nature of problem,
If I(x,y) = S, then R(x,y) = 1, else R(x,y) = 0
2. Growing from seed by 8-connected neighbors,
If R(x,y) = 1, then
If R(x±i,y ±j) = 0, then
If | R(x±i,y ±j) - S | ≤ T, then R(x±i,y±j) = 1
3. Repeat until no more growing
1 1 3 3 1 1 1 3 3 1 1 1 3 3 1 1 1 3 3 1
2 4 6 8 5 2 4 6 8 5 2 4 6 8 5 2 4 6 8 5
4 6 7 7 6 4 6 7 7 6 4 6 7 7 6 4 6 7 7 6
5 6 6 5 4 5 6 6 5 4 5 6 6 5 4 5 6 6 5 4
5 2 3 3 5 5 2 3 3 5 5 2 3 3 5 5 2 3 3 5

Original Seed 1st Growing 2nd Growing

Grayscale If I(x,y) = 7 If | Ineighbor - 7 | ≤ 2 5 ≤ Ineighbor ≤ 9 4
Or 5 ≤ Ineighbor ≤ 9

2
 Region Growing (Cont’d)

Original Grayscale Image Seeded Image

Growing Region Growing Region 5

(Intensity 225-255) (Intensity 190-255)

Region Splitting and Merging

1. For any connected region,
If P(Ri)=FALSE, then
divide the image into quadrants Rij, j=1,2,3,4
R1 R41
R1 R2
R2 R42
R
R41 R42 R3
R3 R43
R43 R44 R4 R44
Quadimages Quadtree
2. If no further decomposition is possible, then
merge adjacent regions that P(Rm∪Rn)=TRUE
3. Stop when no further merging
6

3
 Region Splitting and Merging (Cont’d)
1 1 1 1 4 1 1 1 4 1 1 1
1 1 1 1 4 1 1 1 1 1 1 1
1 4 4 4 4 4 1 1 4 4 1 1
1 4 4 4 4 4 1 1 1 4 4 4
1 4 4 4 3 3 2 1
1 4 4 4 3 3 2 1 1 4 4 4 3 3 2 1
1 2 4 4 3 3 2 1
1 2 4 4 3 3 2 1 1 2 4 4 3 3 2 1
1 4 4 4 4 4 2 1 1 4 4 4 4 4 2 1
1 4 4 4 4 4 2 1
1 4 4 4 4 4 4 1 1 4 4 4 4 4 4 1
1 4 4 4 4 4 4 1
1 2 3 3 2 4 1 4 1 2 3 3 2 4 1 4
2 4 1 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3
1 1 1 1
Original Region, I(x,y) ≥ 3 1st Splitting 1 1 1 1

4 1 1 1 2nd Splitting
1 1 1 1 1 1
4 4 1 1 1 1 1 1 4 1
1 4 4 4 1 1 0 0 0 0 1 0 0 0
1 4 4 4 3 3 2 1 1 4 4 4 4 4
3 3 2 1 0 1 1 1 1 1 0 0
1 2 4 4 3 3 2 1 1 4 4 4
3 3 2 1 0 1 1 1 2 2 0 0
1 2 4 4
0 0 1 1 2 2 0 0
1 4 4 4 4 4 2 1 1 4 4 4 4 4 2 1
0 1 1 1 1 1 0 0
1 4 4 4 4 4 4 1 1 4 4 4 4 4 4 1
0 1 1 1 1 1 1 0
2 4 1 4 2 4 1 4
1 2 3 3 1 2 3 3 0 0 3 3 0 1 0 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 0 0 0 07 0
1st Merging 2nd Merging 3 Output Regions

Region Splitting and Merging (Cont’d)

Check if a region should be split into four or not.
Any quadregion that passes predicate function
is filled with 1s, otherwise it is filled with 0s.

Split-and-Merge Image
Original Grayscale Image
(Smallest Block is 8×8 pixels)

Split-and-Merge Image Split-and-Merge Image 8

(Smallest Block is 4×4 pixels) (Smallest Block is 2×2 pixels)

4
 Geodesy
dA(a ,a )
• Geodesic Distance, a 1
1 2

dA(a1,a2) is the shortest path linking A

a
between point a1 and a2 a 3
2

dA(a ,a ) = ∞
• Zone of Influence of B in A, 1 3

ZA(Bi) is all points in A that dA(a,Bi) is finite

and dA(a,Bi) < dA(a,Bj) , ∀j ≠ i
Therefore, IZA(B) = ∪i ZA(Bi) B
Z (B ) A 1

• Skeleton by Zones of Influence, A SKIZ (B) A

B
SKIZA(B), is the boundaries Z (B )
2

A 2

between various zones. IZ (B) = Z (B ) ∪ Z (B )

A A 1 A 2
9

Watershed Transform
• Consider an image I(x,y) as a topographic surface
• Simulate a flooding process by plunge the surface in
to a lake with a constant speed

Ridges Dam

Original Image Topographic Surface

Minima

10
Flooding Segmentation Result

5
 Watershed Transform (Cont’d)
Bi is the catchment basin or area that I(x,y) ≤ i
3 3 3 2 3 3 3 3
3 3 3 2 2 2 3 3
Intensity
Flooding
3 3 3 3 3 3 3 3
4
2 2 2 2 2 2 2 3
3
2 1 1 2 2 2 1 2
2
2 1 1 2 2 2 2 2
1
2 2 2 2 2 3 3 3
3 3 3 3
0
3 3 3 3 Spatial
Original Image

11
B1 B2 B3

Watershed Transform (Cont’d)

• Two or more floods coming from different
minima may merge
• Build a dam on that point the floods would
merge Intensity Building Dams
4
3
2
1
Spatial
0

W1 W2 W3
“Dam”
“Dam”

12

6
 Watershed Transform (Cont’d)
• Watershed, Wi = IZB i (Bi-1) ∪ Mini
where i = 0,1,2,…,255
B-1 = ∅
Mini = Regional Minima that I(x,y)=i
• It causes “Over-Segmentation”

Input Output (W1∪W2∪W3) 13

Watershed Transform (Cont’d)

Other way is to detect directly watershed points.
(find the points that cannot be flooded)
3 3 3 2 3 3 3 3
3 3 3 2 2 2 3 3
3 3 3 3 3 3 3 3

Original 2 2 2 2 2 2 2 3
Flooding
Image 2 1 1 2 2 2 1 2 Direction
2 1 1 2 2 2 2 2
2 2 2 2 2 3 3 3
3 3 3 3 3 3 3 3

Connected
Ridges Watershed
(No Flood)
14

7
 Watershed Transform (Cont’d)
e.g.

Original Grayscale Watershed Transformed

15

Watershed Segmentation
To make a topographic surface,
• Using Negative Distance Transform
Original Grayscale

Binarization

Distance Transform

Complementation

Watershed Transform

Segmented Output

16

8
 Watershed Segmentation (Cont’d)
• Using Smoothened Gradients

Original Grayscale

Finding Gradient Magnitude

Smoothening

Watershed Transform

Segmented Output

17

Watershed Segmentation (Cont’d)

• Marker-Controlled Compute regional minima that are
deeper less than height threshold
(H-minima Transform)
Original Grayscale

Internal Marking Finding Gradient Magnitude

Distance-Transform-Based Compute external markers by

Watershed Transform taking watershed transform of the
distance transform of the markers
Minima Imposition

Watershed Transform
Modify gradient magnitude image so that
Segmented Output regional minima occur only in the markers,
while the others are pushed up.
18

9
 Watershed Segmentation (Cont’d)
• Marker-Controlled Watershed Segmentation

Original Grayscale Internal Markers External Markers

Modified Gradient Segmentation Result

19

MATLAB Functions
• regiongrow(I,Seed,Threshold)
• qtdecomp(), qtgetblk(), predicate(Region)
• splitmerge(I,Smallest_Block, Predicate)
• watershed(I)
• imregionalmin(I)
• imextendedmin(I,Heigh)
• imimposemin(I,Mask)

20

10
 References
• http://cmm.ensmp.fr/~beucher/wtshed.html
• Wikipedia
• Image Processing Place

21

11