A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> This paper presents a new algorithm for partitioning a gray-level image into connected homogeneous regions. The novelty of this algorithm lies in the fact that, by constructing a minimum spanning tree representation of a gray-level image, it reduces a region partitioning problem to a minimum spanning tree partitioning problem, and hence reduces the computational complexity of the region partitioning problem. The tree-partitioning algorithm, in essence, partitions a minimum spanning tree into subtrees, representing different homogeneous regions, by minimizing the sum of variations of gray levels over all subtrees under the constraints that each subtree should have at least a specified number of nodes, and two adjacent subtrees should have significantly different average gray-levels. Two (faster) heuristic implementations are also given for large-scale region partitioning problems. Test results have shown that the segmentation results are satisfactory and insensitive to noise. <s> BIB001 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> We present a new graph-theoretic approach to the problem of image segmentation. Our method uses local criteria and yet produces results that reflect global properties of the image. We develop a framework that provides specific definitions of what it means for an image to be under- or over-segmented. We then present an efficient algorithm for computing a segmentation that is neither under- nor over-segmented according to these definitions. Our segmentation criterion is based on intensity differences between neighboring pixels. An important characteristic of the approach is that it is able to preserve detail in low-variability regions while ignoring detail in high-variability regions, which we illustrate with several examples on both real and synthetic images. <s> BIB002 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> This paper addresses the problem of segmenting an image into regions. We define a predicate for measuring the evidence for a boundary between two regions using a graph-based representation of the image. We then develop an efficient segmentation algorithm based on this predicate, and show that although this algorithm makes greedy decisions it produces segmentations that satisfy global properties. We apply the algorithm to image segmentation using two different kinds of local neighborhoods in constructing the graph, and illustrate the results with both real and synthetic images. The algorithm runs in time nearly linear in the number of graph edges and is also fast in practice. An important characteristic of the method is its ability to preserve detail in low-variability image regions while ignoring detail in high-variability regions. <s> BIB003 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> This paper presents a segmentation algorithm for gray-level images and addresses issues related to its performance on noisy images. It formulates an image segmentation problem as a partition of a weighted image neighborhood hypergraph. To overcome the computational difficulty of directly solving this problem, a multilevel hypergraph partitioning has been used. To evaluate the algorithm, we have studied how noise affects the performance of the algorithm. The α-stable noise is considered and its effects on the algorithm are studied. <s> BIB004 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> The paper presents a modification of a bottom up graph theoretic image segmentation algorithm to improve its performance. This algorithm uses Kruskal's algorithm to build minimum spanning trees for segmentation that reflect global properties of the image: a predicate is defined for measuring the evidence of a boundary between two regions and the algorithm makes greedy decisions to produce the final segmentation. We modify the algorithm by reducing the number of edges required for sorting based on two criteria. We also show that the algorithm produces an over segmented result and suggest a statistical region merge process that will reduce the over segmentation. We have evaluated the algorithm by segmenting various video clips Our experimental results indicate the improved performance and quality of segmentation. <s> BIB005 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> Sensor devices are widely used for monitoring purposes. Image mining techniques are commonly employed to extract useful knowledge from the image sequences taken by sensor devices. Image segmentation is the first step of image mining. Due to the limited resources of the sensor devices, we need time and space efficient methods of image segmentation. In this paper, we propose an improvement to the graph-based image segmentation method already described in the literature and considered as the most effective method with satisfactory segmentation results. This is the preprocessing step of our online image mining approach. We contribute to the method by re-defining 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. The conducted experiments demonstrate the efficiency and effectiveness of the adjusted method. <s> BIB006 </s> A Review on Graph Based Segmentation <s> IV. MINIMUM SPANNING TREE BASED METHODS <s> The main goal of this work is to compare pyramidal structures proposed to solve segmentation tasks. Segmentation algorithms based on regular and irregular pyramids are described, together with the data structures and decimation procedures which encode and manage the information in the pyramid. In order to compare the different segmentation algorithms, we have employed three types of quality measurements: the shift variance measure, the F function and the Q function. <s> BIB007
A spanning tree of a connected undirected graph is a subgraph which links all the vertices of the graph and there should be exactly a single path between any two vertices. For the graph, many spanning trees could be found. However, the minimum spanning tree (MST) is a spanning tree whose total weight of edges is less than or equal to the total weight of edges of every other spanning tree. A minimum spanning tree of a graph in which vertices are the pixels and edges represent the similarity between the vertices that it connects, constructed from an image, represents the possible weakest connections. By suitably removing the lowest weighted edges, different partitions that have stronger inherent affinities could be found. Major MST based approaches of segmentation are the method based on Gestalt theory by Zahn  , a tree partitioning algorithm by Xu et al. BIB004 BIB001 , an efficient MST algorithm by Felzenszwalb et al. BIB003 BIB002 and methods BIB005 BIB006 improving the performance of the efficient MST algorithm. A short discussion of these methods is as follow. Zahn  used an approach based on Gestalt theory  for detecting and describing clusters. From a given set of points, an MST is constructed first and inconsistent edges in the MST are then deleted to obtain a collection of connected components which in turn constitute clusters. In the method of Xu et al. BIB004 BIB001 , a tree partitioning algorithm splits up the MST built from an image into many sub-trees, which represent homogeneous regions, such that each sub-tree should have at least a specific number of vertices and any two nearby sub-trees should feature significantly dissimilar average gray levels. For noisy images, the method yields low quality results due to the incorrect configuration of the MST as an object might be contained in more than one sub-tree due to noise. Inspired by the work of Zahn, Felzenszwalb et al. BIB003 BIB002 presented an efficient graph based method for segmenting images using MST and is widely used as it runs in video rate in practice. The method works with the assumption that edges between vertices in the same segment should have relatively low weights than edges between vertices in different segments. Initially each vertex is considered as a segment. Then in a greedy way, two segments are repeatedly selected to consider for merging. Based on a comparison predicate, the decision of merging the two segments is made. The comparison predicate is defined based on the internal difference of a segment and difference between two segments. The internal difference of a segment(S) is the largest weight in the minimum spanning tree of the segment, which is given by The difference between two segments is calculated as the minimum weight edge connecting the two segments. When the difference between two segments is less than or equal to the minimum of any of the internal difference of the two segments, then the predicate allows the two segments to be merged. The authors showed that the segmentation produced by this method is neither too coarse nor too fine. Also, any attempt to change the definition of the difference between two segments (say, median edge weight instead of minimum weight edge between the two segments) to make the method more robust lead to the solution NP-hard. As the method merges two segments based on a single low weight edge between them, there are possibilities that the results could considerably be affected by noise if no initial filtering of the image is done. A sample result obtained using this method is shown in Figure 11 . Fahad et al. BIB005 and Zhang et al. BIB006 suggested some modifications to improve its performance. In practical scenarios, acquiring images without noise is almost impossible due to the perplexed imaging environment. Usage of this category of methods in those noisy images without pre-processing that includes filtering might yield unacceptable segmentation as the MST based methods are very much susceptible to noise. A review of pyramidal structures that are used for image segmentation can be found in BIB007 . The general framework involves the creation of a graph from the original image. From this base graph, a set of graphs defined in multi-level of resolution, which can be visualized as a pyramid, is built. The vertices and edges at level L+1 are formed from the reduction of vertices and edges at level L using a reduction function. A level of pyramid called as working level is chosen as the responsible level to yield segmentation. Based on the working principle to build pyramids, they can be classified into two categories: (1) regular pyramids and (2) irregular pyramids