Segmentation

2- Edged-Based Methods
Edged-Based Methods try to establish the boundary between two regions depending on certain criteria such as image intensities or gray levels. A boundary can be defined as locations in an image where there is a sudden and rapid variation in the brightness or gray level value. In general, those variations are detected using the image derivative (Gradient and Laplacian) which are very noise-sensitive. Consequently, three steps should be performed.
1- Noise reduction: suppression of as much noise as possible, without smoothing away the meaningful edges.
2- Edge enhancement: application of filters responding strongly at edges and weakly elsewhere. Edges may be identified as local maxima in the filter s output.
3- Edge localization: decision about which of the local maxima are meaningful edges and which are caused by noise.
1. Derivatives of an Image
There are two kinds of derivatives that have been largely used in edge detection.
A. Gradient
The gradient operator applied to a continuous two dimensional function f(x,y)
produces a vector of two elements at each point as follows:

The direction of this vector its magnitude are respectively given by:
dir( =tan …(1)
mag …(2)
the gradient direction (Equation (1) ) is the direction of maximum change of the function at the point (x,y) and its magnitude (Equation (2) ) is the magnitude of this maximum change.
A digital value of the gradient may be computed by convolving two window masks on some neighborhood; one window gives the x component, the other gives the y component of the gradient as illustrated the following formula:

Where n(i,j) is some neighborhood of (I,j) ( generally a 3×3 or 5×5)and represents the convolution operator.
Some common masks are:
Sobel operator mask¬¬x = , Sobel operator mask¬¬y =
Prewitt operator mask¬¬x = , Prewitt operator mask¬¬y =
The result of applying the gradient operator to an image is two new images one of which contains vertical edges and the other horizontal edges.

B. Laplacian
The Laplacian gives a single quantify for a two dimensional function at each point
(x,y) as defined in the following equation:
… (3)
The Laplacian is also calculated using a convolution mask. Two common masks are:
– Plus-shaped mask¬ =
– Square-shaped mask¬ =
Notes:
– The gradient gives both magnitude and direction information about the change in pixel values at appoint, whereas the Laplacian gives only magnitude.
– In order to get a binary image containing only edges, a thresholding operation must follow the convolution. Selection of an appropriate global threshold is often difficult, sometimes impossible. Figure(1) is an illustration of this operation.
– The most common problems of edge-based segmentation are: missing true edge, detecting false edges, delocalizing edges, edge thickness, edge discontinuity, and detecting several edges instead of one.
– Image resulting from edge detection cannot be used as a segmentation result, rather supplementary processing must follow to produce segments(combine edge-chains and form closed boundaries)which is very difficult task.

e(i,j)




Figure(1) isolation of edges after the filter is applied

3- Region-Based Method
Region-based methods are complementary of edge-based methods. The objective is to form uniform connected regions of pixels based on some uniformity predicate present in a logical statement that is true only if pixels in the region are sufficiently similar in terms of gray scales or some other property. A common uniformity predicate is:
…(4)
Where f(j,k) is the gray level of the pixel (j,k) in the region R and ?R is the mean of R-{(j,k)}. This equation asserts that a region R is Uniform if neighboring pixels in R are close to one another, so that the deviation of a pixel about the mean does not exceed a little amount . The choice of the threshold is problematic because thresholds always depend on the image data that are often noisy. This effect renders the method noise-sensitive.
Common algorithms using a region approach are described in the following:
1. Region growing
The region growing strategy is a bottom-up algorithm. Starting with a set of seed pixels, it grows a uniform connected region from each seed pixel. A pixel is added to region if it satisfied the following conditions:
1- it has not been assigned to any other region.
2- It is neighbor of that region.
3- The new region created by adding this pixel is still uniform.
This procedure is repeated until the whole image is exhausted. Figure(2) illustrate this procedure for one seed pixel and where the 4-neighbor is considered (from a pixel only four neighbors are visited and not all the eight neighbors).
























Seed pixel Grown pixel
Figure(2) Region growing principle based on 4-neighbor
2. Split and merge
The split-and-merge algorithm is divide-and-conquer method. First of all, it takes the whole image as an area of interest. After that an area of interest is processed based on the following notions:
– Region merging: two adjacent regions are merged into a single region if they satisfy equation (4) with R taken as the union of these two regions.
– Region splitting: a region is subdividing into smaller regions(usually four sub-regions) if it does not satisfy the similarity equation (4).
These two notions are alternatively used; one after the other until no further merging or splitting could be performed.
Figure(3) shows an example of using this procedure.
The split-and-merge procedure iteration could be described using a tree structure. Each node has at most four descendants or less due to merging. Figure(4) represents the corresponding tree for the result of figure(3).

I1 I2
I3 I4




(a)whole Image (b)First Split

I1 I2
I3 I4 I42
I43
I1 I2
I3 I4 I42
I43 I44






(c) Second Split (d) Merge
Figure(3) Example of region splitting and merging





I1 I2 I3


I41 I42 I43
Figure(4) Region splitting and merging tree of figure(3)
4-Hybrid Method
Hybrid methods refer to both regions and edges. They detect regions based on pre-extracted edges or vice versa. In general, these methods are computationally very expensive and highly data driven. An important example of this type of methods is the watershed.
Best Wishes
Shaymaa