A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense. graphs, achieving an O(n)) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O(nm log(n'/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efticient distributed and parallel implementations. A parallel implementation running in O(n'log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin <s> BIB001 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Abstract For X ⊆ V ( G ), let ∂X denote the set of edges of the graph G having one end in X and the other end in V ( G ) βX . The quantity i(G)≔ min { |∂X| |X| } , where the minimum is taken over all non-empty subsets X of V ( G ) with |X| ≤ |V(G)| 2 , is called the isoperimetric number of G . The basic properties of i ( G ) are discussed. Some upper and lower bounds on i ( G ) are derived, one in terms of | V ( G )| and | E ( G )| and two depending on the second smallest eigenvalue of the difference Laplacian matrix of G . The upper bound is a strong discrete version of the wellknown Cheeger inequality bounding the first eigenvalue of a Riemannian manifold. The growth and the diameter of a graph G are related to i ( G ). The isoperimetric number of Cartesian products of graphs is studied. Finally, regular graphs of fixed degree with large isoperimetric number are considered. <s> BIB002 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ( approximately 2000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm (1961). However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. The new clustering algorithm is applied to the image segmentation problem. The segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours. > <s> BIB003 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We develop a image segmentation algorithm in which the segmented region has both an exterior boundary cost and an interior benefit associated with it. Our segmentation method proceeds by minimizing the ratio between the exterior boundary cost and the enclosed interior benefit using a computationally efficient graph partitioning algorithm. Our interest is motivated by very efficient algorithms for finding the globally optimum solution, and a desire to investigate how weak smoothness constraints may be globally imposed without disallowing very high local curvature. We analyze the performance of the approach, indicating both strengths and weaknesses, and discuss its connections with prior image partitioning algorithms. The relationship with snakes is discussed in detail and it is shown how to efficiently compute an approximation to common snakes under the additional constraint that it enclose a given point. When user interaction is available, there is a clear advantage to minimizing user interaction for purposes of improved speed and ease of use and for robustness. "Ratio regions" can accommodate several levels of user interaction and it is empirically shown that very coarse initializations can be tolerated. User interaction not only guides the algorithm to perceptually salient regions but can also be exploited to significantly reduce the computational cost. <s> BIB004 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging. <s> BIB005 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We propose a method for segmenting gray-value images. By segmentation, we mean a map from the set of pixels to a small set of levels such that each connected component of the set of pixels with the same level forms a relatively large and "meaningful" region. The method finds a set of levels with associated gray values by first finding junctions in the image and then seeking a minimum set of threshold values that preserves the junctions. Then it finds a segmentation map that maps each pixel to the level with the closest gray value to the pixel data, within a smoothness constraint. For a convex smoothing penalty, we show the global optimal solution for an energy function that fits the data can be obtained in a polynomial time, by a novel use of the maximum-flow algorithm. Our approach is in contrast to a view in computer vision where segmentation is driven by intensity, gradient, usually not yielding closed boundaries. <s> BIB006 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> An important application of graph partitioning is data clustering using a graph model - the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering. In this paper, we propose a new algorithm for graph partitioning with an objective function that follows the min-max clustering principle. The relaxed version of the optimization of the min-max cut objective function leads to the Fiedler vector in spectral graph partitioning. Theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bounds are derived. The min-max cut algorithm is tested on newsgroup data sets and is found to out-perform other current popular partitioning/clustering methods. The linkage-based refinements to the algorithm further improve the quality of clustering substantially. We also demonstrate that a linearized search order based on linkage differential is better than that based on the Fiedler vector, providing another effective partitioning method. <s> BIB007 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We introduce a new graph-theoretic approach to image segmentation based on minimizing a novel class of 'mean cut' cost functions. Minimizing these cost functions corresponds to finding a cut with minimum mean edge weight in a connected planar graph. This approach has several advantages over prior approaches to image segmentation. First, it allows cuts with both open and closed boundaries. Second, it guarantees that the partitions are connected. Third, the cost function does not introduce an explicit bias, such as a preference for large-area foregrounds, smooth or short boundaries, or similar-weight partitions. This lack of bias allows it to produce segmentations that are better aligned with image edges, even in the presence of long thin regions. Finally, the global minimum of this cost function is largely insensitive to the precise choice of edge-weight function. In particular, we show that the global minimum is invariant under a linear transformation of the edge weights and thus insensitive to image contrast. Building on algorithms by Ahuja et al. (1993), we present a polynomial-time algorithm for finding a global minimum of the mean-cut cost function and illustrate the results of applying that algorithm to several synthetic and real images. <s> BIB008 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> This paper proposes a new cost function, cut ratio, for segmenting images using graph-based methods. The cut ratio is defined as the ratio of the corresponding sums of two different weights of edges along the cut boundary and models the mean affinity between the segments separated by the boundary per unit boundary length. This new cost function allows the image perimeter to be segmented, guarantees that the segments produced by bipartitioning are connected, and does not introduce a size, shape, smoothness, or boundary-length bias. The latter allows it to produce segmentations where boundaries are aligned with image edges. Furthermore, the cut-ratio cost function allows efficient iterated region-based segmentation as well as pixel-based segmentation. These properties may be useful for some image-segmentation applications. While the problem of finding a minimum ratio cut in an arbitrary graph is NP-hard, one can find a minimum ratio cut in the connected planar graphs that arise during image segmentation in polynomial time. While the cut ratio, alone, is not sufficient as a baseline method for image segmentation, it forms a good basis for an extended method of image segmentation when combined with a small number of standard techniques. We present an implemented algorithm for finding a minimum ratio cut, prove its correctness, discuss its application to image segmentation, and present the results of segmenting a number of medical and natural images using our techniques. <s> BIB009 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry. <s> BIB010 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We consider data clustering problems where partial grouping is known a priori. We formulate such biased grouping problems as a constrained optimization problem, where structural properties of the data define the goodness of a grouping and partial grouping cues define the feasibility of a grouping. We enforce grouping smoothness and fairness on labeled data points so that sparse partial grouping information can be effectively propagated to the unlabeled data. Considering the normalized cuts criterion in particular, our formulation leads to a constrained eigenvalue problem. By generalizing the Rayleigh-Ritz theorem to projected matrices, we find the global optimum in the relaxed continuous domain by eigendecomposition, from which a near-global optimum to the discrete labeling problem can be obtained effectively. We apply our method to real image segmentation problems, where partial grouping priors can often be derived based on a crude spatial attentional map that binds places with common salient features or focuses on expected object locations. We demonstrate not only that it is possible to integrate both image structures and priors in a single grouping process, but also that objects can be segregated from the background without specific object knowledge. <s> BIB011 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Minimum cut/maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push -relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes. <s> BIB012 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available. <s> BIB013 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Humans usually can effortlessly find coherent regions even in noisy visual images, a task that is crucial for object recognition. Computer algorithms have been less successful at doing this in natural viewing conditions, in part because early work on the problem used only local computations on the image. Now a new approach has been developed, based on an image segmentation strategy that analyses all salient regions of an image and builds them into a hierarchical structure. This method is faster and more accurate than previous approaches, but the resulting algorithm is relatively simple to use. It is demonstrated in action by using it to find items within a large database of objects that match a target item. Computer algorithms have not been successful at finding coherent regions in noisy visual images under natural viewing conditions. A new approach can now determine all salient regions of an image and build them into a hierarchical structure faster and more accurately than previous approaches. Finding salient, coherent regions in images is the basis for many visual tasks, and is especially important for object recognition. Human observers perform this task with ease, relying on a system in which hierarchical processing seems to have a critical role1. Despite many attempts, computerized algorithms2,3,4,5 have so far not demonstrated robust segmentation capabilities under general viewing conditions. Here we describe a new, highly efficient approach that determines all salient regions of an image and builds them into a hierarchical structure. Our algorithm, segmentation by weighted aggregation, is derived from algebraic multigrid solvers for physical systems6, and consists of fine-to-coarse pixel aggregation. Aggregates of various sizes, which may or may not overlap, are revealed as salient, without predetermining their number or scale. Results using this algorithm are markedly more accurate and significantly faster (linear in data size) than previous approaches. <s> BIB014 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Spectral graph partitioning provides a powerful approach to image segmentation. We introduce an alternate idea that finds partitions with a small isoperimetric constant, requiring solution to a linear system rather than an eigenvector problem. This approach produces the high quality segmentations of spectral methods, but with improved speed and stability. <s> BIB015 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> This paper presents a new method for solving clustering problem. We treat clustering as a graph-partitioning problem and propose a new global criterion, the optimum cut, for segmenting the graph. An important feature is that optimizing the optimum cut criterion can ensure that the intra-cluster similarity is maximized while the inter-cluster similarity is minimized. We show that an efficient computational technique based on an eigenvalue problem can be used to optimize this criterion. The experimental results on a number of hard artificial and real-world data sets show the effectiveness of the approach. <s> BIB016 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Recently, image-based, high throughput genome-wide RNA interference (RNAi) experiments are increasingly carried out to facilitate the understanding of gene functions in intricate biological processes. Effective automated segmentation technique is significant in analysis of RNAi images. Traditional graph cuts based active contours (GCBAC) method is impractical in automated segmentation. Here, we present a modified GCBAC approach to overcome this shortcoming. The whole process is implemented as follows: First, extracted nuclei are used in region-growing algorithm to get the initial contours for segmentation of cytoplasm. Second, constraint factor obtained from rough segmentation is incorporated to improve the performance of segmenting shapes of cytoplasm. Then, control points are searched to correct inaccurate parts of segmentation. Finally, morphological thinning algorithm is implemented to solve the touching problem of clustered cells. Our approach is capable of automatically segmenting clustered cells with low time-consuming. The excellent results verify the effectiveness of the proposed approach. <s> BIB017 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Efficient global optimization techniques such as graph cut exist for energies corresponding to binary image segmentation from low-level cues. However, introducing a high-level prior such as a shape prior or a color-distribution prior into the segmentation process typically results in an energy that is much harder to optimize. The main contribution of the paper is a new global optimization framework for a wide class of such energies. The framework is built upon two powerful techniques: graph cut and branch-and-bound. These techniques are unified through the derivation of lower bounds on the energies. Being computable via graph cut, these bounds are used to prune branches within a branch-and-bound search. ::: ::: We demonstrate that the new framework can compute globally optimal segmentations for a variety of segmentation scenarios in a reasonable time on a modern CPU. These scenarios include unsupervised segmentation of an object undergoing 3D pose change, category-specific shape segmentation, and the segmentation under intensity/color priors defined by Chan-Vese and GrabCut functionals. <s> BIB018 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Topology is an important prior in many image segmentation tasks. In this paper, we design and implement a novel graph-based min-cut/max-flow algorithm that incorporates topology priors as global constraints. We show that the optimization of the energy function we consider here is NP-hard. However, our algorithm is guaranteed to find an approximate solution that conforms to the initialization, which is a desirable property in many applications since the globally optimum solution does not consider any initialization information. The key innovation of our algorithm is the organization of the search for maximum flow in a way that allows consideration of topology constraints. In order to achieve this, we introduce a label attribute for each node to explicitly handle the topology constraints, and we use a distance map to keep track of those nodes that are closest to the boundary. We employ the bucket priority queue data structure that records nodes of equal distance and we efficiently extract the node with minimal distance value. Our methodology of embedding distance functions in a graph-based algorithm is general and can also account for other geometric priors. Experimental results show that our algorithm can efficiently handle segmentation cases that are challenging for graph-cut algorithms. Furthermore, our algorithm is a natural choice for problems with rich topology priors such as object tracking. <s> BIB019 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> This paper proposes a new clothing segmentation method using foreground (clothing) and background (non-clothing) estimation based on the constrained Delaunay triangulation (CDT), without any pre-defined clothing model. In our method, the clothing is extracted by graph cuts, where the foreground seeds and background seeds are determined automatically. The foreground seeds are found by torso detection based on dominant colors determination, and the background seeds are estimated based on CDT. With the determined seeds, the color distributions of the foreground and background are modeled by Gaussian mixture models and filtered by a CDT-based noise suppression algorithm for more robust and accurate segmentation. Experimental results show that our clothing segmentation method is able to extract different clothing from static images with variations in backgrounds and lighting conditions. <s> BIB020 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Normalized cut is a widely used technique for solving a variety of problems. Although finding the optimal normalized cut has proven to be NP-hard, spectral relaxations can be applied and the problem of minimizing the normalized cut can be approximately solved using eigen-computations. However, it is a challenge to incorporate prior information in this approach. In this paper, we express prior knowledge by linear constraints on the solution, with the goal of minimizing the normalized cut criterion with respect to these constraints. We develop a fast and effective algorithm that is guaranteed to converge. Convincing results are achieved on image segmentation tasks, where the prior knowledge is given as the grouping information of features. <s> BIB021 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: they can be equivalently defined by their "catchment basinsrdquo (through a steepest descent property) or by the "dividing linesrdquo separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations. <s> BIB022 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Understanding neural connectivity and structures in the brain requires detailed 3D anatomical models, and such an understanding is essential to the study of the nervous system. However, the reconstruction of 3D models from a large set of dense nanoscale medical images is very challenging, due to the imperfections in staining and noise in the imaging process. Manual segmentation in 2D followed by tracking the 2D contours through cross-sections to build 3D structures can be a solution, but it is impractical. In this paper, we propose an automated tracking and segmentation framework to extract 2D contours and to trace them through the z direction. The segmentation is posed as an energy minimization problem and solved via graph cuts. The energy function to be minimized contains a regional term and a boundary term. The regional term is defined over the flux of the gradient vector fields and the distance function. Our main idea is that the distance function should carry the information of the segmentation from the previous image based on the assumption that successive images have a similar segmentation. The boundary term is defined over the gray-scale intensity of the image. Experiments were conducted on nanoscale image sequences from the Serial Block Face Scanning Electron Microscope (SBF-SEM). The results show that our method can successfully track and segment densely packed cells in EM image stacks. <s> BIB023 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Skin segmentation is widely used in many computer vision tasks to improve automated visualization. This paper presents a graph cuts algorithm to segment arbitrary skin regions from images. The detected face is used to determine the foreground skin seeds and the background non-skin seeds with the color probability distributions for the foreground represented by a single Gaussian model and for the background by a Gaussian mixture model. The probability distribution of the image is used for noise suppression to alleviate the influence of the background regions having skin-like colors. Finally, the skin is segmented by graph cuts, with the regional parameter γ optimally selected to adapt to different images. Tests of the algorithm on many real world photographs show that the scheme accurately segments skin regions and is robust against illumination variations, individual skin variations, and cluttered backgrounds. <s> BIB024 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Mammograms are X-ray images of human breast which are normally used to detect breast cancer. The presence of pectoral muscle in mammograms may disturb the detection of breast cancer as the pectoral muscle and mammographic parenchyma appear similar. So, the suppression or exclusion of the pectoral muscle from the mammograms is demanded for computer-aided analysis which requires the identification of the pectoral muscle. The main objective of this study is to propose an automated method to efficiently identify the pectoral muscle in medio-lateral oblique-view mammograms. This method uses a proposed graph cut-based image segmentation technique for identifying the pectoral muscle edge. The identified pectoral muscle edge is found to be ragged. Hence, the pectoral muscle is smoothly represented using Bezier curve which uses the control points obtained from the pectoral muscle edge. The proposed work was tested on a public dataset of medio-lateral oblique-view mammograms obtained from mammographic image analysis society database, and its performance was compared with the state-of-the-art methods reported in the literature. The mean false positive and false negative rates of the proposed method over randomly chosen 84 mammograms were calculated, respectively, as 0.64% and 5.58%. Also, with respect to the number of results with small error, the proposed method out performs existing methods. These results indicate that the proposed method can be used to accurately identify the pectoral muscle on medio-lateral oblique view mammograms. <s> BIB025 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> In partitioning, clustering, and grouping problems, a typical goal is to group together similar objects, or pixels in the case of image processing. At the same time, another goal is to have each group distinctly dissimilar from the rest and possibly to have the group size fairly large. These goals are often combined as a ratio optimization problem. One example of such a problem is a variant of the normalized cut problem, another is the ratio regions problem. We devise here the first polynomial time algorithms solving optimally the ratio region problem and the variant of normalized cut, as well as a few other ratio problems. The algorithms are efficient and combinatorial, in contrast with nonlinear continuous approaches used in the image segmentation literature, which often employ spectral techniques. Such techniques deliver solutions in real numbers which are not feasible to the discrete partitioning problem. Furthermore, these continuous approaches are computationally expensive compared to the algorithms proposed here. The algorithms presented here use as a subroutine a minimum s,t-cut procedure on a related graph which is of polynomial size. The output consists of the optimal solution to the respective ratio problem, as well as a sequence of nested solutions with respect to any relative weighting of the objectives of the numerator and denominator. <s> BIB026 </s> A Review on Graph Based Segmentation <s> II. GRAPH CUT BASED METHODS <s> Indisputably Normalized Cuts is one of the most popular segmentation algorithms in pattern recognition and computer vision. It has been applied to a wide range of segmentation tasks with great success. A number of extensions to this approach have also been proposed, including ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. However, what is common for all these methods is that they are noticeably limited in the type of constraints that can be incorporated and can only address segmentation problems on a very specific form. In this paper, we present a reformulation of Normalized Cut segmentation that in a unified way can handle linear equality constraints for an arbitrary number of classes. This is done by restating the problem and showing how linear constraints can be enforced exactly in the optimization scheme through duality. This allows us to add group priors, for example, that certain pixels should belong to a given class. In addition, it provides a principled way to perform multi-class segmentation for tasks like interactive segmentation. The method has been tested on real data showing good performance and improvements compared to standard normalized cuts. <s> BIB027
Graph cuts started with the work of Greig  . The graph G can be partitioned into two connected components A and B such that by omitting the edges linking these two components. The degree of association between A and B can be inferred from the total weight of the discarded edges, which is simply called as a graph cut (a pictorial representation of the graph cut is shown in Figure 2 . An optimal bi-partition minimizes this graph cut value BIB005 . By suitably and repeatedly partitioning the graph constructed from an image using the graph cut, different homogeneous regions could be obtained. In another way, each vertex could be considered as a region. By utilising graph cut values, which is a measure to show how much two neighboring regions are homogeneous, regions could be united repeatedly to form image partitions. Major works in this category are the minimum cut algorithm introduced by Wu and Leahy BIB003 , a normalized cut algorithm by Shi and Malik BIB005 BIB005 , a variant of normalized cut suggested by Sharon et al. BIB014 , a polynomial time solution to the variant of normalized cut by Hochbaum BIB026 , methods BIB011 BIB027 BIB021 incorporating priors to improve performance of the normalized cut, the average cut by Sarkar et al.  , the min-max cut by Ding et al. BIB007 , and the optimum cut by Li and Tian BIB016 . The other important contributions in this category are the minimum mean cut BIB008 and ratio cut BIB009 by Wang et al., two methods to determine the global minima of an energy function by Jermyn and Ishikawa  , an active contours based method by Boykov et al. BIB010 , a heuristic isoperimetric ratio algorithm by Grady and Schwartz BIB015 , a branch-and-bound based technique by Lempitsky et al. BIB018 , Watershed cuts by Cousty et al. BIB022 , ratio regions by Cox et al. BIB004 , min-cut/max-flow algorithms BIB001  BIB012 BIB019 and a few application focused methods BIB017 BIB023 BIB024 BIB020 [56] BIB025 . These methods are surveyed briefly in the following. Wu and Leahy BIB003 introduced minimum cut for image segmentation in such a way that the smallest (k-1) cuts among all possible cuts are selected and the corresponding edges are deleted to form k-subgraph partitions. This method favors the formation of very smaller regions, which results in over-segmentation. To overcome this problem, Shi and Malik BIB005 BIB005 proposed a segmentation method based on normalized cut, the cut cost function that is computed as a fraction of the total edge connections to all the vertices in the graph. The normalized cut, which is a partition criterion of a graph and reflects the global impression of an image, is given as is the total link from vertices in A to all vertices in the graph. has similar definition. The authors showed that exact minimization of normalized cut is NPcomplete. Also, they proposed an approximation algorithm for the minimization of the cut cost function by solving a generalized eigenvalue problem. There are four steps in the algorithm: (1) a graph is formed out of an image where vertices are pixels and weight of an edge is a function of similarity between two neighboring pixels. . Also, x and  are the eignvector and eignvalue respectively. (3) The graph is bi-partitioned using the second smallest eignvector. (4) The above three steps are recursively applied to the two partitions until the normalized cut value is below a threshold. This approximation algorithm is computationally expensive. Also, the normalized cut tends to produce equally sized regions which rarely occur in natural images. The results obtained using this approximation algorithm is presented in Figure 3 . A variant of normalized cut was discussed by Sharon et al. BIB014 . It is to minimize the ratio of similarity between the set of regions and its complement and the similarity within the set of regions. Recently, Hochbaum BIB026 devised a polynomial time solution for this problem which uses a graph cut procedure. A few methods have also been proposed to improve the performances of the normalized cut by incorporating priors. Yu and Shi BIB011 included a smoothed partial grouping constraint to the normalized cut. Eriksson et al. BIB027 admitted linear grouping constraints through a Lagrangian dual formation. A constraint normalized cut, which adds prior information in data with explicit linear constraints using an iterative algorithm, was proposed by Xu et al. BIB021 . The eigenvectors of graph Laplacian or their deviations are normally used to partition a graph in spectral graph partitioning. Sarkar et al.  presented a spectral clustering technique based on average cut. This measure is defined as the proposition of the total cut-link weight normalized by the size of the partitions. Ding et al. BIB007 presented a segmentation technique based on minmax cut criterion. Li et al. BIB016 suggested optimum cut criterion for partitioning a graph. The optimal solutions to the min-max cut criterion and the optimal cut criterion are all NP-complete BIB016 . In BIB008 , Wang and Siskind presented a polynomial time algorithm for finding a minimum mean cut. An illustration is given in Figure 4 . Later on Wang and Siskind BIB009 examined the minimization of cut ratio cost function and discovered that finding a minimum cut ratio in an arbitrary graph is NP-hard. Hence, they generalized the polynomial time algorithm for finding a minimum mean cut to obtain a polynomial time algorithm for finding a cut that minimizes the cut ratio cost function in connected planar graphs. This solution repeatedly calls an inefficient nonbipartite matching algorithm BIB026 . Figure 5 shows some results obtained on pepper and medical images. Jermyn and Ishikawa  suggested two methods to determine the global minima of an energy function for the identification of homogeneous regions in images. This energy function is defined on the space of boundaries in the image domain and can incorporate information both from the boundaries and interior of regions. One limitation of this method is that it fails to detect multiply-connected regions. Boykov et al. BIB010 proposed a method by fusing both active contours and graph cuts. This method demands the extraction of object and background seeds which is hard to obtain for many applications. It can be noted from BIB002 that determining isoperimetric sets is a NP-hard problem. Grady and Schwartz BIB015 employed a heuristic algorithm for finding a set with a low isoperimetric ratio in polynomial time, which uses graph cuts, for image segmentation. An instance is given in Figure 6 . Lempitsky et al. BIB018 gave a global optimization framework for image segmentation using the graph cut and branch-and-bound techniques. The worst case running time of this framework is higher. Cousty et al. BIB022 studied watersheds in edge-weighted graphs under the name watershed cuts. Graph cuts play a significant role in defining these watershed cuts. As the method has a drawback of forming numerous irrelevant smaller regions, it is required to employ a pre-processing and\or a post-processing to obtain the desired outcome. Cox et al. BIB004 introduced ratio regions for image segmentation. It is to minimize the ratio of the similarity between the set of regions and its complement and the number of regions within the set. A recent study by Hochbaum BIB026 showed that this problem has a polynomial time solution using graph cuts. The min-cut/max-flow algorithms, which can be employed for energy functions' minimization, have been used to achieve image segmentation. Kolmogorov et al. BIB013 provided necessary and sufficient conditions for such energy functions. Geometric properties of regions formed by graph cut methods are detailed in BIB010 . A few suggested min-cut/max-flow methods for image segmentation in the literature are: push-relabel methods BIB001 , the Dinic algorithm  , the Boykov method BIB012 and topological cuts BIB019 . The push relabel methods BIB001 maintain a preflow, a flow function. The methods run as long as there is an active vertex in the graph. The push operation increases the flow on a residual edge. A height function on vertices controls which residual edges can be pushed. The height function is altered with relabel operations. The push and relabel operations guarantee that the resulting flow is a maximum flow. A direct application of this method to image segmentation can be seen in the work of Ishikawa and Geiger BIB006 . The Dinic algorithm  pushes flow on non-saturated paths from the source to the sink until the maximum flow in the graph is achieved. The Boykov method BIB012 works by iteratively repeating the three stages: growing, augmentation and adoption. This method was found to be 2 to 5 times faster than the push-relabel methods and the Dinic algorithm. The drawback of this method is that the augmenting paths found are not necessarily the shortest augmenting paths. Zeng et al. BIB019 was the first to study about a min-cut/max-flow algorithm that incorporates a topological constraint: the topological cuts problem. It was shown that any optimal solution to the topological cuts problem is NP-hard. Hence, an approximation solution BIB019 was suggested to solve the topological cuts problem. Chen et al. BIB017 used a modified graph cuts based active contours as a fully automatic segmentation method for RNAi fluorescence images. Yang et al. BIB023 segmented densely packed cells in electron microscopic images via graph cuts. Zhilan et al. BIB024 This method works based on several assumptions which include cloth arms are similar in color to the torso, which in turn contains dominant colors. These assumptions are not always true as a cloth with sleeves in different colors to the torso is quite common now. Han et al. [56] applied a graph cut based segmentation method to extract white mater, gray matter, and cerebral spinal fluid from brain diffusion tensor image data. Camilus et al. BIB025 proposed an approach to identify the pectoral muscle in mammograms using a graph cut based merging method and a Bezier curve algorithm. The result of this approach is influenced by the order in which regions are merged in the graph cut based merging method. An unacceptable running time of a method could prevent its usage in real time applications. Most of the methods in this category are computationally expensive as they are proved to be NP complex and might not be suitable for many real time usages.