Digital Image Processing - COMP4173

Lecture 12: Image Segmentation

Prof. Hongjian Shi (时红建）

Department of Computer Science and Technology
BNU-HKBU United International University
Email: shihj@uic.edu.cn
Office: T3-601-R3;
Office Hours: Tues., Wed., Thur. 9:00-11:50; Wed. 16:00-16:50
1
Global Thresholding
• If there is an object clearly inside the scene like the above third
one, one may use the global thresholding:

• This method is much better than histogram method, since you do

not need to check the separation level, while automatically
generate one.
Finished

Segmentation has been the most important research topic in image processing
Optimum Thresholding – Bayes Decision Rule
• Minimizing error of assigning pixels in an image to two or more
groups

- Probability of classifying a BG pixel

as FG by mistake

- Probability of classifying a FG pixel

as BG by mistake
Overall probability of error:
Optimal threshold minimizes the probability of misclassification:
Gaussian densities case:
Optimal Thresholding – Otsu’s Method
• Otsu’s method maximizes the “between-class variance” – well known method in
statistical discriminant analysis:
Class 𝐶1 : 𝑎𝑙𝑙 𝑝𝑖𝑥𝑒𝑙𝑠 𝑤𝑖𝑡ℎ 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑟𝑎𝑛𝑔𝑒 [0, 𝑘]
Class 𝐶2 : 𝑎𝑙𝑙 𝑝𝑖𝑥𝑒𝑙𝑠 𝑤𝑖𝑡ℎ 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑟𝑎𝑛𝑔𝑒 [𝑘 + 1, 𝐿 − 1]
• In order to evaluate the “goodness” of the threshold at level k, we need to
maximize the intra-class variance:

where 𝜔1 and 𝜔2 are the probabilities of two classes separated by 𝑘. 𝜇1 and 𝜇2

are the means of the two classes, 𝜇 𝑇 is the total mean.
 function level = otsu(histogramCounts) total =
sum(histogramCounts);
Otsu’s algorithm sumB = 0; wB = 0; maximum = 0.0;
sum1 = ( (0:255), histogramCounts);
• Compute histogram and for ii=1:256
probabilities at each wB = wB + histogramCounts(ii);
intensity level wF = total - wB;
if (wB == 0 || wF == 0)
• Set the initial 𝜔𝑖 (0) and 𝜇𝑖
continue;
• Step through all threshold end
𝑘 = 0,1,2, … , 𝐿 − 1 sumB = sumB + (ii-1) * histogramCounts(ii);
• Update 𝜔𝑖 , 𝜇𝑖 mF = (sum1 - sumB) / wF;
• Compute 𝜎𝑏2 (𝑘) between = wB * wF * ((sumB / wB) - mF) * ((sumB / wB) -
mF);
• Obtain the desired if ( between >= maximum )
threshold 𝑘 corresponding level = ii;
to the maximum 𝜎𝑏2 (𝑘) maximum = between;
end
end
end
Smoothing before using global thresholding
Otsu’s method fails for some noisy images
 Otsu’s method fails

Otsu’s method works

Using edges to improve global thresholding

Multiple Thresholding – Extension of Otsu’s Method
• Otsu’s method works to search one optimal threshold but can be extended to
multiple thresholds if necessary. In practice, Otsu’s method can work for two
thresholds effectively. Search for 𝑘1∗ and 𝑘2∗ : . The
threshold image is:
 Variable Thresholding – Image Partitioning
• Subdivide an image into small nonoverlapping rectangles so that the illumination
of each rectangle is uniform
• The method compensates the non-uniformities in illumination and/or reflectance

Using iterative
global algorithm

Partitioning
Otsu’s and applying
method Otsu’s method
on each part
 Histograms for the six small partition sub-images

Histogram for the entire image

 Local Property Based Thresholding
• Local properties (usually mean and standard) can be used for adapting
the threshold
• For example, or
• The segmentation is operated using a suitable predicate, 𝑄𝑥𝑦 :

Where 𝑄𝑥𝑦 can be 𝑓 𝑥, 𝑦 > 𝑇𝑥𝑦 or 𝑓 𝑥, 𝑦 > 𝑎𝜎𝑥𝑦 AND 𝑓 𝑥, 𝑦 > 𝑏𝑚𝑥𝑦
• This technique can be generalized to multiple thresholds
Moving Average Thresholding
• During scanning, pixels are visited in a zigzag path, so we compute the
average of the intensity of last 𝑛 visited pixels. The segmentation can be
performed using a threshold 𝑇𝑥𝑦 = 𝑏𝑚𝑥𝑦 , b can be a suitable constant such
as 𝑏 = 0.5. Such method is best used for document thresholding
Region Growing
• Goal: group pixels or sub-regions into larger regions based on predefined
criteria for growth
• Method:
• Start with a set of “seed” points
• Grow regions by appending to each seed those neighboring pixels that have
predefined properties similar to the seed (e.g., gray level, texture…)

• The selection of the seeds can be operated manually or using automatic

procedures based on appropriate criteria:
• A-priori knowledge can be included
• It is strictly application-dependent
• The growing is controlled by the connectivity
• The stop rule is another parameter of the algorithm. It can depend on the a-
priori knowledge on the problem or geometric structures
Example
• Use points (3, 2) and (3, 4) are seeds; property: gray level
difference < 3:
Region Splitting and Merging
• Iterative subdivision of the image in homogeneous regions (splitting).
• Joining of the adjacent homogeneous regions (merging).
• Given an image f and a predicate Q, the basic algorithm is:
• R1 = f
• Subdivision in quadrants of each region Ri for which Q(Ri) = FALSE.
• If Q(Ri) = TRUE for every regions, merge those adjacent regions Ri and Rj
such that Q(Ri ∪ Rj) = TRUE; otherwise, repeat step 2.
• Repeat the step 3 until no merging is possible.
Moving Object Detection
• Main goal: detecting moving objects from a video sequence of a fixed
camera
• Background – static scene
• Foreground – moving objects
• Approach: detect the moving objects as the difference between the current
frame and the image of the scene background

Background image Current image Foreground scene

Challenges
• How to automatically obtain the background image?
• Foreground processing
• The background image must adapt to:
• Illumination (lighting) changes (gradual and sudden）
• Distracting motions (camera shake, swaying tree, moving elevators …)
• Scene changes (parked car)
• Others:
Shadows
Black/blue screen
Bad weathers
Foreground fragment
Basic Ideas
• Pixels belongs to foreground if | Current Frame – BG Image| >
Threshold
• BG image can be just the previous frame or the average image of a
number of frames
• Works only in particular conditions of objects’ speed and frame rate
• Use the frame rate and scene change in distance to detect the
motion speed
• Very sensitive to the threshold