Question: Explain image segmentation based on similarity with the help of examples.
0

Subject : Digital Image Processing

Topic: Chap 3: Image Segmentation and Representation

Difficulty: Medium

mumbai university dip(47) • 474 views
 modified 6 months ago  • written 6 months ago by
0

Image segmentation based on similarity can be carried out in four different ways.

(i) Region growing

(ii) Region splitting

(iii) Region merging

(iv) Spilt & Merge

Region growing:

• Region growing is a procedure in which pixels are grouped into larger regions based on some predefined condition.
• The basic approach is to select a seed point (a pixel from where we begin) and grow regions from this seed pixel.
• Let us pick up an arbitrary pixel $(x_{1} , y_{1} )$ from the image that needs to be segmented.
• This pixel is called the seed pixel.
• Examine the nearest neighbors (4 or 8 neighbors depending on whether we assume 4-connectivity or 8-connectivity) of $(x_{1} , y_{1} )$ one by one.
• The neighboring pixel is accepted in the same region as $(x_{1} , y_{1} )$ if they together satisfy till homogeneity property of a region i.e., if both of them satisfy the predefined condition.
• Once a new pixel $(x_{2} , y_{2} )$ is accepted as a member of the current region, the neighbor of this new pixel are examined (again, 4 or 8 neighbors, depending on the connectivity assumed).
• This procedure goes on recursively until no new pixel is accepted.
• All the pixels of the current region arc given a unique label.
• Now a new seed pixel is chosen and the same procedure is repeated.
• Continue doing this until all the pixels are assigned to some region.
• Example: Consider an 8 x 8 image, the grey levels range from 0 to 7. Segment this image is using the region growing technique.

First we need to define two things.

(1) What is the predicate?

(2) Which do we take as the seed pixel?

Both these conditions are fed in by the user.

Let the predicate be

max {g(x, y)} - min {g(x, y)} < th

where th is the threshold.

In this case let the threshold be $\leq$ 3

P($R_{1}$ ) = max {g(x, y)} - min {g(x, y)} $\leq$ 3

(x, y $\epsilon$ R) $\hspace{20mm}$ (x, y $\beta$ R)

Assume 4-connectivity.

Use the above equation to get the image shown

The shaded portion gets labeled as ‘a’ (say).

Is segmentation complete? The answer is NO. For segmentation, to be complete, all the pixels have to be assigned to some region.

Now select 0 (encircled) as the seed pixel and label the new area as b.

Hence, we get following image

Region Splitting:

• Consider a small region at a time instead of single pixel. We divide the region into four equal quadrants.
• If the grey levels present in the region do not satisfy the property, we divide the region into four equal quadrants. If the property is satisfied, we leave the region as it is.
• This is done recursively until all the regions satisfy- the property)
• To explain this in terms of graph theory, we call each region a node.
• This node (parent node) is split into its four children (leaf nodes) if it does not satisfy the given property. If the node satisfies the property, it is left as it is.
• Check each leaf node and see if these leaf nodes satisfy' the given property. If yes, they are left unaltered and if no, there are further split.

• In this, image R represents the entire image and hence R is the parent node. This parent node is split into four leaf node R1, R2, R3, R4. Of these leaf nodes only R4 does not satisfy the common property as defined and hence is split again.

Region Merging:

• The region merging method is exactly opposite to the region splitting method.
• In this method, the pixel level and consider each of them as a homogenous region.
• At any level of merging, check if the four adjacent homogenous regions arranged in a 2 x 2 fashion together satisfy the homogeneity property.
• If yes, they are merged to form a bigger region, otherwise the regions are left as they are.
• Let us take the same 8x8 image as an example and perform region merging, we use the predicate

max {g(x, y)} - min {g(x, y)} $\leq$ 3

(x, y $\epsilon$ R) $\hspace{20mm}$ (x, y $\beta$ R)

• Merge this image in 22 regions.
• Image after first step of merging

• We check the four adjacent homogeneous regions. Image obtained after the second step of merging is shown below :

Split & Merge

• In the split and merge technique we start with a rectangular regions of size a x b pixels.
• Check the homogeneity property for each region.
• If the homogeneity property fails, we split up the region into four quadrants each of size a/2 x b/2.
• If the region satisfies the homogeneity property, we merge it with the adjacent region forming a 2a x 2b size region.