VC 14/15 – TP9
Region-Based Segmentation
Mestrado em Ciência de Computadores
Mestrado Integrado em Engenharia de Redes e
Sistemas Informáticos
Miguel Tavares Coimbra
Outline
• Region-based Segmentation
• Morphological Filters
VC 14/15 - TP9 - Region-Based Segmentation
Topic: Region-based Segmentation
• Region-based Segmentation
• Morphological Filters
VC 14/15 - TP9 - Region-Based Segmentation
Why Region-Based Segmentation?
• Segmentation
– Edge detection and
Thresholding not
always effective.
• Homogenous regions
– Region-based
segmentation.
– Effective in noisy
images.
VC 14/15 - TP9 - Region-Based Segmentation
Definitions
• Based on sets.
• Each image R is a set R7
R6
of regions Ri.
– Every pixel belongs to R1
R5
one region.
– One pixel can only R2 R3
belong to a single R4
region.
S
R Ri Ri R j
i 1
VC 14/15 - TP9 - Region-Based Segmentation
R7
R6
R1
R5
R2
R3
R4
VC 14/15 - TP9 - Region-Based Segmentation
Basic Formulation
Let R represent the entire image a) Every pixel must be in a
region. Segmentation partitions R
into n subregions, R1, R2, ..., Rn, region
such that: b) Points in a region must
n
a) R R
i 1
i be connected.
b) R is a connected region, i 1, 2, ..., n.
c) Regions must be
i
disjoint.
c) Ri R j for all i and j , i j d) All pixels in a region
satisfy specific
d) P( Ri ) TRUE for i 1,2,..., n. properties.
e) P( Ri R j ) FALSE for i j.
e) Different regions have
different properties.
VC 14/15 - TP9 - Region-Based Segmentation
How do we form regions?
• Region Growing
• Region Merging
• Region Splitting
• Split and Merge
• Watershed
• ...
What a computer sees
VC 14/15 - TP9 - Region-Based Segmentation
Region growing
• Groups pixels into • Iterative process
larger regions. – How to start?
• Starts with a seed – How to iterate?
region. – When to stop?
• Grows region by
merging neighboring Finish
pixels.
Initial Stop
Iterations
Regions Condition
VC 14/15 - TP9 - Region-Based Segmentation
VC 14/15 - TP9 - Region-Based Segmentation
Region merging
• Algorithm
– Divide image into an initial set of regions.
• One region per pixel.
– Define a similarity criteria for merging
regions.
– Merge similar regions.
– Repeat previous step until no more merge
operations are possible.
VC 14/15 - TP9 - Region-Based Segmentation
Similarity Criteria
• Homogeneity of regions is used as the
main segmentation criterion in region
growing.
– gray level
Choice of criteria
– color, texture
affects segmentation
– shape results dramatically!
– model
– etc.
VC 14/15 - TP9 - Region-Based Segmentation
Gray-Level Criteria
• Comparing to Original Seed Pixel
– Very sensitive to choice of seed point.
• Comparing to Neighbor in Region
– Allows gradual changes in the region.
– Can cause significant drift.
• Comparing to Region Statistics
– Acts as a drift dampener.
• Other possibilities!
VC 14/15 - TP9 - Region-Based Segmentation
Region splitting
• Algorithm
R1 R2
– One initial set that
R1
includes the whole
R3 R4
image.
– Similarity criteria.
– Iteratively split regions
into sub-regions.
R1 R2
– Stop when no more R1 R2 R3
splittings are possible. R4 R5
R6 R7
R3
R4 R5 R6 R7
VC 14/15 - TP9 - Region-Based Segmentation
VC 14/15 - TP9 - Region-Based Segmentation
[Machine Vision; David Vernon]
Split and Merge
• Combination of both
algorithms.
• Can handle a larger
variety of shapes.
– Simply apply previous
algorithms
consecutively.
VC 14/15 - TP9 - Region-Based Segmentation
The Watershed Transform
• Geographical inspiration.
– Shed water over rugged
terrain.
– Each lake corresponds to a
region.
• Characteristics
– Computationally complex.
– Great flexibility in
segmentation.
– Risk of over-segmentation.
VC 14/15 - TP9 - Region-Based Segmentation
The Drainage Analogy
• Two points are in the same region if they
drain to the same point.
Courtesy of Dr. Peter Yim at National Institutes of Health, Bethesda, MD
VC 14/15 - TP9 - Region-Based Segmentation
The Immersion Analogy
VC 14/15 - TP9 - Region-Based Segmentation
[Milan Sonka,
Vaclav Hlavac,
and Roger Boyle]
VC 14/15 - TP9 - Region-Based Segmentation
Over-Segmentation
• Over-segmentation.
– Raw watershed segmentation produces a
severely oversegmented image with hundreds
or thousands of catchment basins.
• Post-Processing.
– Region merging.
– Edge information.
– Etc.
VC 14/15 - TP9 - Region-Based Segmentation
Topic: Morphological Filters
• Region-based Segmentation
• Morphological Filters
VC 14/15 - TP9 - Region-Based Segmentation
Mathematical Morphology
• Provides a • What is this used for?
mathematical – Binary images.
description of – Can be used for post-
geometric structures. processing
segmentation results!
• Based on sets.
– Groups of pixels which • Core techniques
define an image – Erosion, Dilation.
region. – Open, Close.
VC 14/15 - TP9 - Region-Based Segmentation
Tumor Segmentation using Morphologic Filtering
VC 14/15 - TP9 - Region-Based Segmentation
Dilation, Erosion
• Two sets:
– Image
– Morphological kernel.
• Dilation (D)
– Union of the kernel with
the image set.
– Increases resulting area.
• Erosion (E)
– Intersection.
– Decreases resulting area.
VC 14/15 - TP9 - Region-Based Segmentation
Dilation
• Example using a 3x3 morphological kernel
VC 14/15 - TP9 - Region-Based Segmentation
Erosion
• Example using a 3x3 morphological kernel
VC 14/15 - TP9 - Region-Based Segmentation
Opening, Closing
• Opening
– Erosion, followed by
dilation.
– Less destructive than an
erosion.
– Adapts image shape to
kernel shape.
• Closing
– Dilation, followed by
erosion.
– Less destructive than a
dilation.
– Tends to close shape
irregularities.
VC 14/15 - TP9 - Region-Based Segmentation
Opening
• Example using a 3x3 morphological kernel
VC 14/15 - TP9 - Region-Based Segmentation
Closing
• Example using a 3x3 morphological kernel
VC 14/15 - TP9 - Region-Based Segmentation
Core morphological operators
Dilation Erosion
Closing Opening
VC 14/15 - TP9 - Region-Based Segmentation
Example: Opening
Opening
Tresholding
VC 14/15 - TP9 - Region-Based Segmentation
Example: Closing
Closing
VC 14/15 - TP9 - Region-Based Segmentation
Connected Component Analysis
• Define ‘connected’.
– 4 neighbors.
– 8 neighbors.
• Search the image for
seed points.
• Recursively obtain all
connected points of
the seeded region.
VC 14/15 - TP9 - Region-Based Segmentation
Resources
• Gonzalez & Woods - Chapter 7 and 8
VC 14/15 - TP9 - Region-Based Segmentation