Performance Evaluation of Image Segmentation Using Graph Theory

Performance Evaluation of Image Segmentation Using Graph Theory

Nitin B. Ukunde*, Dr. Sanjv K. Shrivastava**, Sheetal N. Ukunde***

*(Department of Electronics Engg., Nagpur

** (Department of Electronics Engg., Nagpur

*** (Department of Electronics & Telecommunication Engg., YCCE, Nagpur

ABSTRACT

Image segmentation is an elementary problem in computer vision and plays very important role in various image application domains. Regardless of years of research in the area of general purpose image segmentation, it is still a very challenging task since it is inherently ill-posed. Out of different segmentation schemes available today, graph theory based techniques have several excellent characteristics in practical applications. Such graph theory based image segmentation techniques explicitly organize the image objects into mathematically structures, making the computation of image segmentation problem more flexible and efficient. This research work basically employs fundamental concepts of graph theory for image segmentation. The PSNR and time taken for image segmentation has been used as a comparison parameter for proposed image segmentation method.

Keywords – Graph-based image segmentation, graph theoretical methods, graph cut, differential IFT.

1. INTRODUCTION

   Image segmentation refers to partitioning of an image into several disjoint subsets, where each subset corresponds to a meaningful part of the image. As image segmentation is often an integral part of many large vision problems, its quality influences the performance of the whole system. Large amount of literature has been published on image segmentation over last few decades. Most commonly used approaches for image segmentation are threshold techniques,

   edge-based methods, region-based techniques and connectivity-preserving relaxation methods [1]. Irrespective of the choice of approach, the complexity lies in formulating prior knowledge into the segmentation process.

   Threshold based image segmentation techniques take decisions depending on local pixel information and are hence more effective in situation where the intensity levels of the objects fall outside the range of levels in the background. Since the spatial information is ignored in these techniques they suffer through blurred region boundaries which create chaos. Edge-based methods are based on contour detection. Further most edge based image segmentation techniques are weak in connecting together broken contour lines which makes them prone to failure in the presence of blurring. In region-based methods the image is first partitioned into connected regions by grouping neighbouring pixels of similar intensity levels. Then the adjacent regions are merged based upon some criterion such as homogeneity or sharpness of region boundaries. A connectivity- preserving relaxation-based segmentation method begins with some initial boundary shape characterized in the form of spline curves, which is modified by applying various shrink and/or expansion operations depending upon some energy function.

   Within the last few decades, graph theoretic segmentation methods have gained popularity [2-3]. These segmentation methods utilize graph cuts as their global optimization technique. In

   [4] a graph based approach is presented consisting of the filtering process for the removal of noise and at the same time thin edges are preserved to smooth the boundaries of the regions. Grady and Schwartz in their work [5]

   have presented an approach that deals with the partitioning of the image, which is mapped into graph where the isoperimetric constant is used. Tao. Z, Wenxue. H and Jinjia. W in their work

   [6] have explained a novel concept of texture analysis method by using Graph Spectral Theory. Ming Zhang and Reda Alhajj have presented a modified the Graph-based image segmentation method [7]. In their work they have re-defined the internal difference used to define the property of the components and the threshold function, which is the key element to determine the size of the components.

2. GRAPH THEORETIC FORMULATION

   The graph theoretic segmentation problem is based on graph partitioning and optimization scheme and cane be formulated as follows [2]:

   1. The set of points in an arbitrary feature space are symbolized as a weighted undirected graph

      G = (V, E) (1)

   2. An edge is formed between every pair of nodes providing a complete graph.

   3. The weight on each edge, w(i,j) is a function of the similarity between nodes i and j.

   4. Partition the set of vertices into disjoint sets V1, V2, …, Vk where by some measure the similarity among the vertices in a set Vi is high and, across different sets Vi, Vj is low.

   To partition the graph in a meaningful way, we need to pick a suitable criterion such as optimize the output which would result in a good segmentation and finding an efficient way to achieve the optimization. Further the criterion should be easy to compute.

3. PROPOSED SEGMENTATION METHOD

   The used image segmentation algorithm starts with a initial minor segmentation, with each component containing one pixel, and repeatedly merges pairs of components based on the following merge condition:

   Diff (C1, C2) Int(C1) + T(C1) and

   Diff (C1, C2) Int(C2) + T(C2)

   where Diff(Cl, C2) is the difference between components Cl and C2; Int(Cl) and Int(C2) are

   the internal differences of Cl and C2, respectively; T(C) = k/|C| is the threshold function. Parameter k controls the size of the components in the segmentation. This stop- merging condition k is considered as proposed by Ming Zhang and Reda Alhajj [7] as:

   k<|C|min (W(et) W(et-1)) (3) where E = {e1, e2 . . . en) is the set of edges in non-decreasing weight order, W(ei) 5 W(ei + 1) for i=1,2.. . n – 1.

   Further in our work we have also employed discrete wavelet transform along with the above discussed graph theory based image segmentation algorithm. The use of DWT helps to facilitate the image segmentation process.

   The first DWT was invented by the Alfred Haar. For an input list of 2n numbers, the Haar wavelet transform may simply pairs up input values, storing the difference and passing the sum. This process is repeated recursively resulting 2n-1 in differences and one final sum. Another most commonly used wavelet transform is formulated Daubechies, which is based on the use of recurrence relations to generate progressively finer discrete samplings of an implicit mother wavelet function; each resolution is twice that of the previous scale. Both Haar and Daubechies (DB2, DB3, DB4 and DB5) wavelet transforms have been used in this work.

4. RESULTS AND DISCUSSION

   The above proposed algorithm which involves use of DWT along with graph theory based segmentation has been implemented using MATLAB. The designed GUI gives option to select for the wavelet to be applied during segmentation as in Figure 1. Consider the input image as in Figure 2. The outputs for different wavelets are shown in Figure 3.

   Figure 1: Designed GUI on matlab

   Figure 2: Input Image

   Figure 3(a): Segmented Image for None

   Figure 3(b): Segmented Image for Haar

   Figure 3(c): Segmented Image for DB2

   Figure 3(d): Segmented Image for DB3

   Figure 3(e): Segmented Image for DB4

   Figure 3(e): Segmented Image for DB5 The above results are summarized in table I

   below using PSNR (peak signal-to-noise ratio) and segmentation time required. The PSNR here is used as the quality metrics along with time taken for image sgmentation as comparison parameter. From table I for graph theory based image segmentation, the best PSNR is obtained for no DWT applied, but the time required for segmentation is large as compared to one with DWT. However the use of Haar wavelet has good values of PSNR and segmentation time.

   TABLE I

   GRAPH THEORY BASED IMAGE SEGMENTATION

   RESULTS

   Wavelet Used	Graph Theory Image Segmentation
   	PSNR	Time Required (s)
   None	12.97	3.58
   Haar	12.94	0.55
   DB2	12.91	0.54
   DB3	12.86	0.57
   DB4	12.83	0.56
   DB5	12.92	0.59

5. CONCLUSION

   In this project work graph theory based image segmentation has been evaluated. The proposed algorithm has been implemented using MATLAB. From the results it can be seen that simple graph based image segmentation technique requires more time in comparison to graph theory based segmentation along with DWT applied to technique. Further the use of Haar and DB2 wavelet for graph based segmentation has good PSNR and low segmentation time among other Daubechies wavelets considered in this work.

6. REFERENCES

Journal Papers:

1. Anders P. Eriksson, Olof Barr and Kalle Astrom, "Image Segmentation Using Minimal Graph Cuts", Lund University, Sweden.

2. P.F. Felzenszwalb and D.P. Huttenlocher, "Effiecient Graph-Based Image Segmentation," International Journal of Computer Vision, Vo.59, No.2, dependent of the edge weight scale. 2004.

   Proceedings Papers:

3. Scanlon, J., and Deo, N., Graph-Theorectic Algorithms for Image Segmentation, IEEE 1999, pp. VI-141-VI-144.

4. Chitwong, S., Cheevasuvit, F., Dejhan, K., Mitatha, S., Nokyoo, C., Paungma, T., Segmentation on Edge Preserving Smoothing Image Based on Graph Theory, IEEE, 2000, pp. 621-623.

5. Grady, L., Schwartz, E.L., Isoperimetric Graph Partitioning for Image Segmentation, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 28, No. 3, March 2006, pp. 469-475

6. Tao, Z., Wenxue, H., Jinjia, W., A Novel Texture Analysis Method Based on Graph Spectral Theory, Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2009, pp. 467-470.

7. Ming Zhang and Reda Alhajj, "Improving the Graph-Based Image Segmentation Method", Conference on Tools with Artificial Intelligence 20O6, IEEE 2006.

8. B. Kim, J. Shim and D. Park, "Fast Image Segmentation based on Multi-resolution Analysis and Wavelets," Pattern Recognition Letters, Vo1.24, N0.16, pp.2995-3006, 2003.

9. J. Liu, W. Li, and Y. Tian, Automatic thresholding of gray-level pictures using two- dimension otsu method, in Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on, 1991, pp. 325327 vol.1.

   Theses:

10. R.B. Ohlander, Analysis of natural scenes, PhD Thesis, Carnegie Institute of Technology, Dept. of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1975