Chapter 5 Segmentation

Overview

	Threshold detection methods
	Multispectral thresholding
	Thresholding in hierarchical data structures

Segmentation

Segmentation is one of the most important steps leading to the analysis of processed image data, its main goal is to divide an image into parts that have a strong correlation with objects or areas of the real world contained in the image

	complete segmentation - set of disjoint regions uniquely corresponding with objects in the input image cooperation with higher processing levels which use specific knowledge of the problem domain is necessary
	partial segmentation - regions do not correspond directly with image objects image is divided into separate regions that are homogeneous with respect to a chosen property such as brightness, color, reflectivity, texture, etc. In a complex scene, a set of possibly overlapping homogeneous regions may result. The partially segmented image must then be subjected to further processing, and the final image segmentation may be found with the help of higher level information.
	Simple segmentation problems: contrasted objects on a uniform background simple assembly tasks, blood cells, printed characters, etc.

Totally correct and complete segmentation of complex scenes usually cannot be achieved in this processing phase. A reasonable aim is to use partial segmentation as an input to higher level processing.

Segmentation methods
global knowledge, e.g. using histogram of image features
edge-based segmentations
region-based segmentations

Characteristics used in edge detection or region growing: brightness, texture, velocity field

Thresholding

	Gray level thresholding is the simplest segmentation process. Many objects or image regions are characterized by constant reflectivity or light absorption of their surface.
	Thresholding is computationally inexpensive and fast and can easily be done in real time using specialized hardware.
	A complete segmentation of an image R is a finite set of regions R₁, . . .R_S, For binary images, there is a single threshold:

Thresholding algorithm
Search all the pixels f(i,j) of the image f. An image element g(i,j) of the segmented image is an object pixel if f(i,j) >=T, and is a background pixel otherwise.

Practical Experiment 5.A - Grey-level Thresholding

Save the rabbit.jpg image to your directory. Open Matlab and download threshgl.m. Load the image into matlab. Run this function with the command:

>xt=threshgl(x,Tlo,Thi);%where x is the image matrix

By trial and error, determine the threshold segmenting the rabbit from the background. To do this, adjust the upper and lower thresholds (upperT, lowerT) of this function. Determine the interval in which the threshold has to be defined to perform the desired segmentation. Now, apply the same approach to segmentation of the airplane use the image airplane.jpg - did you find a suitable threshold?

Correct threshold selection is crucial for successful threshold segmentation. Threshold selection can be interactive or can be the result of some threshold detection method

Single global threshold ... successful only under very unusual circumstances gray level variations are likely - due to non-uniform lighting, non-uniform input device parameters or a number of other factors.

Variable thresholding (also adaptive thresholding), in which the threshold value varies over the image as a function of local image characteristics, can produce the solution in these cases.
image f is divided into subimages fc
a threshold is determined independently in each subimage
if a threshold cannot be determined in some subimage, it can be interpolated from thresholds determined in neighboring subimages.
each subimage is then processed with respect to its local threshold.

Practical Experiment 5.B Adaptive Thresholding

Open Matlab and download threshgl.m. Using the airplane.jpg image, modify threshold.m to perform adaptive thresholding - divide the image in blocks and use the local mean-the local variance as the threshold. Did the segmentation improve, what happens for different block sizes?

Thresholding modifications:

Band-thresholding: segment an image into regions of pixels with gray levels from a set D and into background otherwise

Can also serve as border detection

Practical Experiment 5.C - Band Thresholding

Open Matlab and download threshgl.m
Using the rabbit.jpg image, select appropriate thresholds to perform band-thresholding-based border detection.

Apply this idea to the airplane.jpg image and textsheet.jpg.

	Multithresholding resulting image is no longer binary
	Semithresholding aims to mask out the image background leaving gray level information present in the objects

Practical Experiment 5.D - Semi-Thresholding

Open Matlab and invoke semithreshgl.m
Using the rabbit.jpg image, select an appropriate threshold to perform semi-thresholding - segment the background and keep the rabbit gray level information.

Thresholding can also be applied to gradient, local texture or any other image decomposition criterion

Threshold detection methods

If some property of an image after segmentation is known a priori, the task of threshold selection is simplified, since the threshold is chosen to ensure this property is satisfied.

P-tile-thresholding

	A printed text sheet may be an example if we know that characters of the text cover 1/p of the sheet area.
	Choose a threshold T (based on the image histogram) such that 1/p of the image area has gray values less than T and the rest has gray values larger than T
	if such a priori information is not available - another property, for example the average width of lines in drawings, etc. can be used - the threshold can be determined to provide the required line width in the segmented image

More complex methods of threshold detection based on histogram shape analysis
bimodal histogram - if objects have approximately the same gray level that differs from the gray level of the background

Threshold-based segmentation ... minimum segmentation error requirements
it makes intuitive sense to determine the threshold as the gray level that has a minimum histogram value between the two maxima.

	multimodal histogram - more thresholds may be determined at minima between any two maxima.
	Bimodality of histograms- It may not be easy in practice to tell if a histogram is bimodal or multimodal. In reality it is often impossible to interpret the significance of local histogram maxima
	Bimodal histogram threshold detection algorithms Mode method - find the highest local maxima first and detect the threshold as a minimum between them to avoid detection of two local maxima belonging to the same global maximum, a minimum distance in gray levels between these maxima is usually required or techniques to smooth histograms are applied
	Histogram bimodality itself does not guarantee correct threshold segmentation

Optimal thresholding

	Based on approximation of the histogram of an image using a weighted sum of two or more probability densities with normal distributions
	The threshold is set as the closest gray level corresponding to the minimum probability between the maxima of two or more normal distributions, which results in minimum error segmentation
	Problems - estimating normal distribution parameters together with the uncertainty that the distribution may be considered normal.
	Example - Brain MR image segmentation

A combination of optimal and adaptive thresholding determines optimal gray level segmentation parameters in local subregions for which local histograms are constructed gray-level distributions corresponding to n individual (possibly non-contiguous) regions are fitted to each local histogram that is modeled as a sum of n Gaussian distributions so that the difference between the modeled and the actual histogram is minimized

Variable g represents gray level values from the set G of images gray levels, ai, &sigmai and �i denote parameters of the Gaussian distribution for the region i. The optimal parameters of the Gaussian distributions are determined by minimizing the fit function F