Image segmentation

Image segmentation

1. IMAGE SEGMENTATION

2. Introduction
Image segmentation divides an image into regions
that are connected and have some similarity within
the region and some difference between adjacent
regions.
The goal is usually to find individual objects in an
image.
For the most part there are fundamentally two kinds
of approaches to segmentation: discontinuity and
similarity.
Similarity may be due to pixel intensity, color or texture.
Differences are sudden changes (discontinuities) in any of these, but
especially sudden changes in intensity along a boundary line, which is
called an edge.

3. Detection of Discontinuities
There are three kinds of discontinuities of intensity:
points, lines and edges.
The most common way to look for discontinuities is
to scan a small mask over the image. The mask
determines which kind of discontinuity to look for. 


9
1
992211 ...
i
iizwzwzwzwR
General 3x3
Mask

4. Point Detection thresholdenonnegativ a: whereT
TR

5. Line Detection
Only slightly more common than point detection is to
find a one pixel wide line in an image.
For digital images the only three point straight lines are
only horizontal, vertical, or diagonal (+ or –45).

Line Masks

6. Line detection

7. Edge Detection

8. Edge Detection

9. Gradient operators

Roberts cross-gradient operators
Prewitt operators
Sobel operators

10. Edge Linking and Boundary Detection
Local Processing

Two properties of edge points are useful for edge linking:
the strength (or magnitude) of the detected edge points
their directions (determined from gradient directions)
This is usually done in local neighborhoods.
Adjacent edge points with similar magnitude and direction are
linked.
For example, an edge pixel with coordinates (x
0,y
0) in a
predefined neighborhood of (x,y) is similar to the pixel at (x,y)
if
thresholdenonnegativ a: ,),(),(
00 EEyxyxf  thresholdangle nonegative a: ,),(),(
00 AAyxyx 

11. Example
In this example,
we can find the
license plate
candidate after
edge linking
process.

12. Thresholding
•Intensity histogram in Fig. 10.35(a) corresponds to an image f(x,y) composed of light
object on dark background.
•To extract object from the background, we have to set a threshold T, such that any point
(x, y) in image at which f(x, y) > T is called object point; otherwise, background point.
•The segmented image g(x, y) is given by:


(10.3-1)

13. Thresholding
•Intensity histogram in Fig. 10.35(b) corresponds to an image f(x,y) composed of two
types of light objects on a dark background.
•The segmented image g(x, y) is given by:


(10.3-2)


where, a, b and c are three distinct intensity values.

14. Basic Global Thresholding
The following iterative algorithm is used for obtaining basic global threshold.













Parameter ∆T controls the number of iterations. Larger ∆T is, fewer iterations the algorithm
will perform.

15. Optimum Global Thresholding OTSU
•The Otsu’s method is optimum in the sense that it maximizes the between-class variance.
•In addition, Otsu method is based entirely on computations performed on image
histogram, an easily obtainable 1D array.
•Otsu’s algorithm may be summarized as follows:

16. Segmentation using Otsu

17. Segmentation using Otsu

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

19. Basic Formulation
 Let R represent the entire image region.
Segmentation is a process that partitions R into subregions,
R
1,R
2,…,R
n, such that






where P(R
k): a logical predicate defined over the points in set
R
k
For example: P(R
k)=TRUE if all pixels in R
k have the same
gray level.
RR
i
n
i

1
(a) niR
i ,...,2,1 region, connected a is (b)  jijiRR
ji  , and allfor (c)  niRP
i ,...,2,1for TRUE)( (d)  jiji RRRRP and regionsadjacent any for FALSE)( (e) 

20. Region Growing

21. Region splitting and merging
Region splitting is the opposite of region growing.
First there is a large region (possible the entire image).
Then a predicate (measurement) is used to determine if the
region is uniform.
If not, then the method requires that the region be split into
two regions.
Then each of these two regions is independently tested by
the predicate (measurement).
This procedure continues until all resulting regions are
uniform.

22. Region splitting and merging
The main problem with region splitting is determining where
to 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.

23. Region splitting and merging
The split and merge procedure:
Split into four disjoint quadrants any region R
i for which P(R
i) =
FALSE.
Merge any adjacent regions R
j and R
k for which P(R
j U R
k) = TRUE.
(the quadtree structure may not be preserved)
Stop when no further merging or splitting is possible.