1.1 - Introduction
Image segmentation is an important process in Computer Vision that is used for several operations as edge detection, classification, 3D reconstruction, etc.. The main goal of image segmentation is to cluster pixels into regions. This clustering image pixels into image regions in turns convert the image into a representation that is more meaningful and easier to analyse. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics. Image segmentation has broad range of applicability in different fields of science ans engineering.
In this lab work, we implement the region growing algorithm which is one of the basic process of partitioning a digital image and then analyse the design and implementation of it. Finally, we compare the region growing algorithm with other image segmentation algorithms. We describe also about the organization and development phase of the lab work.
1.2 - Problem definition
Our lab work problem asks for performing image segmentation over different image representation and check the result. We implement our image segmentation algorithm over gray level images and RGB color space images to cluster into different image regions. And then we compare our clustering result with Fuzzy C-Means (FCM) clustering algorithm.
2 - Algorithm analysis
Region growing is a pixel-based image segmentation process. Region growing works with a goal to map individual pixel to a set of pixels, based on the characteristics of the image. This set of pixels are called regions which can be an object or anything meaningful.
The approach to region growing algorithm starts with selecting the initial seed. Then it examines neighboring pixels of initial seed points and determines whether the pixel neighbors should be added to the region. The process is iterated on, in the same manner as general data clustering algorithms. A general discussion of the region growing algorithm is described below.
- Choose a starting single pixel or seed. Give the seed a region.
- Check the neighboring pixels considering neighborhood connectivity and add them to the queue if they have not been processed before.
- Add the pixels to the region if they are similar to the seed pixel.
- Change the seed position from the queue following right-hand rule and also considering neighboring connectivity.
- The step 2 continues for each new seed until there is no new pixel to become seed.
- The region $R_{i}$ and $R_{j}$ are different in the sense of predicate P.
\begin{equation}
|f(x, y) - \mu_{R_{i}}| < \triangle
\end{equation}
where $f(x, y)$ represents the current pixel intensity at (x, y), $\mu_{R_{i}}$ represents the mean value of the pixels in the same region, $\triangle$ represents the threshold value that is taken from the user.
If the previous condition is met then we add the current neighbour to the queue. Then, we need to calculate the new $\mu_{R_{i}}$ value. After checking all the neighbors of the current pixel, we mark it as a processed pixel. We check our queue sequentially for each pixel value in the queue and we continue it until the queue is empty. It means that we reach at the border for the current region. After that we increase the region counter and continue to traverse the image matrix until there are no further processed pixels.
Figure-1:4-neighborhood and 8-neighborhood connectivity
Let's show an example to understand the concept more clearly. Assume that we have initial R\_{counter} = 1, P\_{queue} = \{\}, $ \mu_{R_{i}} = 0$ values and an image matrix as follows:
\[
M_{image} = \begin{bmatrix}
202 & 201 & 202 & 102 & 104 \\
200 & 201 & 205 & 102 & 101 \\
204 & 102 & 106 & 101 & 102 \\
103 & 101 & 103 & 54 & 50 \\
12 & 13 & 11 & 52 & 53 \\
\end{bmatrix}
\]
Let, our initial seed is the first pixel of this image. So, we start from the top-left corner of the image matrix to iterate. First, we look at the pixel (1, 1) whether it is processed before or not. Since it is the initial seed, it is not processed before. Then we set the new $\mu_{R_{i}}$ value taking account the current pixel and look at its neigbors {(1, 2), (2, 1)}. For each neighbor, if the condition ($|f(x, y) - \mu_{R_{i}}| < \triangle$) is satisfied then we put the related neighbor pixel value to the queue. After traversing all it's neighbour pixels we set the current pixel as processed pixel.
\[
M_{region} =
\begin{bmatrix}[C]
1 & -1 & 0 & 0 & 0 \\
-1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\]
\[
$\mu_{R_{i}} = 0, R_{counter} = 1, P_{queue} = \{Pixel_{(1, 2)}, Pixel_{(2, 1)}\}$
\]
\[
M_{region} =
\begin{bmatrix}
1 & [C]1 & -1 & 0 & 0 \\
-1 & -1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\]
\[
mu_{R_{i}} = 0, R_{counter} = 2, P_{queue} = \{Pixel_{(1, 3)}, Pixel_{(2, 2)}\}
\]
mu_{R_{i}} = 0, R_{counter} = 2, P_{queue} = \{Pixel_{(1, 3)}, Pixel_{(2, 2)}\}
\]
After traversing the whole image pixels we get the label image. This is the label matrix for our example.
\[
M_{region} =
\begin{bmatrix}
1 & 1 & 1 & 2 & 2 \\
1 & 1 & 1 & 2 & 2 \\
1 & 1 & 2 & 2 & 2 \\
2 & 2 & 2 & 4 & 4 \\
3 & 3 & 3 & 4 & 4 \\
\end{bmatrix}
\]
Segmented matrix for our example. It has 4 regions. We put 4 different intensity values to show the segmented matrix.
\[
M_{\mu_{mean}} =
\begin{bmatrix}
202 & 202 & 202 & 102 & 102 \\
202 & 202 & 202 & 102 & 102 \\
202 & 102 & 102 & 102 & 102 \\
102 & 102 & 102 & 52 & 52 \\
12 & 12 & 12 & 52 & 52 \\
\end{bmatrix}
\]
Recursive implementation has some disadvantages due to the maximum number of recursive calls allowed. Therefore, the algorithm has been implemented in a sequential way and the segmentation labeling was performed over gray level and color images.
The flowchart for our region growing algorithm is shown below.
Figure-2: Flow chart of the region growing algorithm.
To segment RGB color space image we have to follow some extra steps.
- RGB color space images have 3 layers. First, extract the 3 different layers.
- For each layer, compute the mean value of each pixel and then using the Euclidean distance formula, compute the mean value for the image.
- The Euclidean distance between two points $P=(x, y, z)$and $Q=(a, b, c)$ in space is defined as $d(P, Q)= \sqrt{(x - a)^{2} + (y - b)^{2} + (z - c)^{2}}$.
- Perform Region growing algorithm over the image matrix to get the label image.
- Convert the label matrix to a RGB image using label2rgb(L) function.
The FCM algorithm is one of the most widely used fuzzy clustering algorithms. The FCM algorithm attempts to partition a finite collection of elements X = {,, ... ,} into a collection of c fuzzy clusters with respect to some given criterion. Given, a finite set of data, the algorithm returns a list of c cluster centers V, such that
V = $v_i$, $i =1, 2, ... , c$
and a partition matrix U such that
U = $u_{i,j}$ , $i =1, ..., c, j =1,..., n$
where $u_{i,j}$, is a numerical value in $[0, 1]$ that tells the degree to which the element $x_j$ belongs to the i-th cluster. $[3]$
3 - Design and implementation
In this section, we discuss about the design and the implementation phase of the lab work. The algorithm was implemented in a sequential way because of the maximum number of recursive calls.
We approached to our design and implementation phase by following few step. Our steps were
3.1 - Performing segmentation using Region growing algorithm
During the iteration, starting from the initial seed, we were looking for it's neighbors that were connected with each other through 4-neighborhood connectivity relationship.
Figure-3: 4-neighborhood and 8-neighborhood connectivity
If the gray scale value of the neighbour pixel was in the threshold range then we put all of these neighbors to the queue. We continued this until we reached the border for the current region. We created another region by iterating through the pixels one by one. But in that case we checked whether it was marked or not. If the current pixel was a processed one, then we passed it directly. If it was not the processed one, then we looked at its neighbour and if they were in the range then we put them in the queue. The algorithm continues until all the pixels were clustered into regions.
3.2 - Improving the result by applying more filters and other functionalities
Region growing algorithm has some disadvantages as it is prune to salt and pepper noise. This algorithm also produces result which can have some small meaningless regions. To overcome this constraint of Region growing, we applied $9 \times 9$ median filter. This filter reduced the salt and pepper noise and produced better result with accuracy.
3.3 - Comparing our results with Fuzzy C-Means clustering algorithm
To evaluate the performance of our Region growing algorithm we compared our result with the clustering result of Fuzzy C-Means clustering algorithm. Fuzzy C-Means clustering algorithm is a clustering algorithm that divides data into homogeneous classes to keep similar data in the same region and dissimilar data into different classes.
4 - Experimental section and results
After running the algorithm, the user was getting two images. First one represented the label matrix, L, and the second image was created by label2rgb(L) function and converted a label matrix, L, into the RGB color image for the purpose of visualizing the labeled regions.
Figure-4: No median filter, threshold = 20
Figure-5: Median filter with 9x9 kernel only one time, threshold = 20
Figure-6: Median filter with 9x9 kernel five times, threshold = 20
Few more experimental results
Figure-7: No median filter, threshold = 90
Figure-8: Median filter with 9x9 kernel only one time, threshold = 90
Figure-9: Median filter with 9x9 kernel only one time, threshold = 50
The comparison between our result and the clustering result from FCM algorithm
Figure-10: Comparison between the region growing algorithm(threshold = 20) and FCM
Figure-11: Comparison between the region growing algorithm(threshold = 70) and FCM
Comparison Results:
Region growing:
Parameters: Threshold: 20, Filtering: x2
Results: Time: 0.91316s.
Parameters: Threshold: 20, Filtering: x0
Results: Time: 0.9235s.
Fuzzy C-Means:
Parameters: Clusters: 5.
Results: Time: 0.91316s.
Parameters: Clusters: 20.
Results: Time: 9.9559s.
This comparison result shows that Region growing algorithm is faster than FCM but FCM has more accuracy in clustering images. The comparison results are shown in the following 2 images
Figure-12: Comparison between the region growing algorithm(threshold = 20) and FCM (Clusters = 20)
Figure-12: Comparison between the region growing algorithm(threshold = 20 and Filter $\times 2$) and FCM (Clusters = 5)
5 - A brief discussion regarding the algorithms
While we were working on the region growing algorithm we noticed some advantages of the this algorithm and also some of it's disadvantages. A brief pointing to the advantages and disadvantages of region growing is given below.
Advantages:
- Region growing methods can correctly separate the regions that have the same properties we define.
- Region growing methods can provide the original images which have clear edges with good segmentation results.
- The concept is simple. We only need a small number of seed points to represent the property we want, then grow the region.
- We can determine the seed points and the criteria we want to make.
- We can choose the multiple criteria at the same time.
- It performs well with respect to noise.
- The algorithm depends on the initial seed position.
- This algorithm is also not invariant of number of seeds.
- Threshold value plays a vital role, since if the threshold value is very small then the image would be undersegmented and if the threshold value is very large then the image would be oversegmented.
- The result also depends on the chosen neighborhood pattern, whether 4-connected or 8-connected.
6 - Organization and development
In this section, we have presented the management process we followed to organize and develop a deliverable as required by the lab work. To accomplish the assigned task, we made a plan to organize our lab work. We arranged and synchronized our management process considering several criteria such as
- Studying and analyzing the problem,
- Defining the approach,
- Coding the Region growing algorithm,
- Testing and comparing with FCM,
- Report writing.
7 - Conclusions
In summary, this paper has revealed that, region growing algorithm is a fast algorithm. But still it has some drawbacks as the algorithm depends on the initial seed position and also if the threshold value is very small then the image would be undersegmented and if the threshold value is very large then the image would be oversegmented. We can introduce Active region method to over some of the problems. We compared our result with FCM (Fuzzy C-Means) clustering algorithm. Our algorithm gave fast result comparing to FCM while FCM provided more accurate clustering results.
REFERENCES
1 - RG - http://www.cs.cf.ac.uk/Dave/Vision_lecture/node35.html
2 - FCM clustering - http://reference.wolfram.com/applications/fuzzylogic/Manual/12.html
3 - http : //reference.wolfram.com/applications/fuzzylogic/Manual/12.html
No comments:
Post a Comment