CSE464 & CSE468 : Image

Processing and Pattern

Recognition

Image Segmentation
by:
Hossam El Din Hassan Abd El Munim
‫حسام الدين حسن عبد المنعم‬
Computer & Systems Engineering Dept.,
Ain Shams University,
1 El-Sarayat Street, Abbassia, Cairo 11517

1
 Image Segmentation
The process of image segmentation/classification aims to partition the
image into regions of interest.

It is a key component in image analysis and computer vision

The literature is quite rich; early work started in late 1960’s.

Example: Separate/outline the kidney from surrounding tissues
in a low resolution MRI scan

2
 Image Segmentation Challenges
• Noise

• Inhomogeneities

• lack of Strong Edges

• Different Objects may Share Similar Colors or Gray levels

• Cluttered/Occluded/Overlapped Objects

3
 Segmentation Approaches
1. Boundary-Based

• Edge detectors (e.g., Marr-Hildreth 1980)

• Active contours/snakes (Kass et al., 1987)

• Active shape models (T.F. Cootes 1996)

2. Region-Based
• Deformable templates

• Statistical/clustering techniques

• MRF-based techniques (Besag 1974)

• Active appearance models (T.F. Cootes 1998)

4
 Thresholding

image with dark image with dark

background and background and
a light object two light objects

5
 Multilevel thresholding
• a point (x,y) belongs to
– to an object_1 class if f(x,y)  T1
– to another object_2 class if T2 ≥ f(x,y) > T1
– to background if f(x,y) > T2
• T depends on
– only f(x,y) : only on gray-level values  Global threshold
– both f(x,y) and p(x,y) : on gray-level values and its
neighbors  Local threshold

6
Example 1

7
 Example 2
Bone and Non-Bone Tissues

8
 Basic Global Thresholding
Algorithm
Based on visual inspection of histogram

1. Select an initial estimate for T.

2. Segment the image using T. This will produce two
groups of pixels: G1 consisting of all pixels with gray
level values > T and G2 consisting of pixels with gray
level values  T
3. Compute the average gray level values 1 and 2 for
the pixels in regions G1 and G2
4. Compute a new threshold value:-
T = (1 + 2)/2
5. Repeat steps 2 through 4 until the difference in T in
successive iterations is smaller than a predefined
parameter ϵo.
9
Example

note: object and

background intensities are
really separable which is
clear in the histogram.

ϵ0 = 0
3 iterations
with result T = 125

10
Example: Limitation (T=104.3327)

11
 The Role of Illumination: Another
Limitation
easily use global thresholding
object and background are separated

f(x,y) = i(x,y) r(x,y)

a). computer generated

reflectance function
b). histogram of
reflectance function
c). computer generated
illumination function
(poor)
d). product of a). and c).
e). histogram of product
image
difficult to segment 12
 Basic Adaptive Thresholding
As a Solution
• subdivide original image into small areas.
• utilize a different threshold to segment each
subimages.
• since the threshold used for each pixel
depends on the location of the pixel in terms
of the subimages, this type of thresholding is
adaptive.

13
Example : Adaptive Thresholding

14
Example: Global Thresholding
(T=157.5487)

15
Example: Adaptive Thresholding
10X10 Blocks

16
Optimal Global and Adaptive Thresholding
Object/Background Case

p( z )  P1 p1 ( z )  P2 p2 ( z )
P1  P2  1
P1 and P2 are called Prior Probabilities and p(z) is the
normalized histogram function 17
 Segmentation/Classification Decision

if P1 p1 ( z )  P2 p2 ( z )

Pixel is Classified as Object

Else
Pixel is Classified as Background

18
Total Segmentation Error

T
E1 (T )  

p 2 ( z ) dz

E2 (T )   p1 ( z )dz
T

E (T )  P2 E1 (T )  P1 E2 (T )
19
 Minimum Error

Differentiating E(T) with respect to T (using Leibniz’s

rule) and equating the result to 0

dE(T ) d ( P2 E1 (T )  P1 E2 (T ))
 0
dT dT if P = P then 1 2
the optimum threshold
is where the curve
find T which makes p1(z) and p2(z) intersect

P1 p1 (T )  P2 p2 (T )
20
 Gaussian Density

Example: use PDF = Gaussian density : p1(z) and p2(z)

p( z )  P1 p1 ( z )  P2 p2 ( z )
( z  1 ) 2 ( z 2 )2
 
P1 2 12 P2 2 22
 e  e
where 2  1 2  2
• 1 and 12 are the mean and variance of the Gaussian
density of the object
• 2 and 22 are the mean and variance of the Gaussian
density of the background 21
Solution: Quadratic Equation

 B  B  4 AC
2
T
2A
22
Solution: Quadratic Equation
Equal Variances

23
 Solution: Quadratic Equation
Equal Variances and Equal Priors

24
Example: Lung Segmentation from
CT Images

25
 Example: Object Parameters
Estimation (Mean=40, Variance=4.4)

26
 Example: Background Parameters
Estimation (Mean=223, Variance=8)

27
Example: Segmentation Results
P1=P2=0.5

28
Example: Isolate Lungs by flood-fill
Algorithm

29
Segmentation/Classification Decision of
Color Images
 Segmentation/Classification Decision of
Color Images(Same Rules but Feature
Vector )
if P1 p1 ( z )  P2 p2 ( z )
Pixel is Classified as Object
Else
Pixel is Classified as Background

z  [ R G B] T
31
Gaussian Density: Multivariate

32
 Computation Issues

log( p( x))  (d / 2) log(2 )  (1/ 2) log(|  |)  (1/ 2)(x   )t 1 ( x   )

Instead of

33
 Gaussian Density: Multivariate
Parameters Estimation
•Given n pixels with color vectors X1, X2, …,Xn: the mean vector
and covariance matrix can be estimated as follows:-

34
Example1: Object parameters Estimation
Example1: Background parameters
Estimation
Example1: Results
Example1: Results-Object Boundary
Example2: Object/Background parameters
Estimation
Example2: Results
Example2: Results-Object Boundary
Example3: Object/Background parameters
Estimation
Example3: Results
Example3: Results-Object Boundary
 Sources of Error

1. Feature is not appropriate

2. Object or background PDF is not appropriate

3. Parameters are not estimated correctly

4. Training samples are not enough