 Open Access
 Total Downloads : 670
 Authors : Nitin B. Ukunde, Dr. Sanjv K. Shrivastava, Sheetal N. Ukunde
 Paper ID : IJERTV1IS6323
 Volume & Issue : Volume 01, Issue 06 (August 2012)
 Published (First Online): 30082012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 illposed. 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 – Graphbased image segmentation, graph theoretical methods, graph cut, differential IFT.

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,
edgebased methods, regionbased techniques and connectivitypreserving 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. Edgebased 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 regionbased 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 relaxationbased 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 [23]. 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 Graphbased image segmentation method [7]. In their work they have redefined 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. 
GRAPH THEORETIC FORMULATION
The graph theoretic segmentation problem is based on graph partitioning and optimization scheme and cane be formulated as follows [2]:

The set of points in an arbitrary feature space are symbolized as a weighted undirected graph
G = (V, E) (1)

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

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

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.


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<Cmin (W(et) W(et1)) (3) where E = {e1, e2 . . . en) is the set of edges in nondecreasing 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 2n1 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.

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 signaltonoise 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

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.

REFERENCES
Journal Papers:

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

P.F. Felzenszwalb and D.P. Huttenlocher, "Effiecient GraphBased Image Segmentation," International Journal of Computer Vision, Vo.59, No.2, dependent of the edge weight scale. 2004.
Proceedings Papers:

Scanlon, J., and Deo, N., GraphTheorectic Algorithms for Image Segmentation, IEEE 1999, pp. VI141VI144.

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. 621623.

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. 469475

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 (IIHMSP), 2009, pp. 467470.

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

B. Kim, J. Shim and D. Park, "Fast Image Segmentation based on Multiresolution Analysis and Wavelets," Pattern Recognition Letters, Vo1.24, N0.16, pp.29953006, 2003.

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

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