A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Abstract We present a new, interactive tool called Intelligent Scissors which we use for image segmentation. Fully automated segmentation is an unsolved problem, while manual tracing is inaccurate and laboriously unacceptable. However, Intelligent Scissors allow objects within digital images to be extracted quickly and accurately using simple gesture motions with a mouse. When the gestured mouse position comes in proximity to an object edge, a live-wire boundary “snaps” to, and wraps around the object of interest. Live-wire boundary detection formulates boundary detection as an optimal path search in a weighted graph. Optimal graph searching provides mathematically piece-wise optimal boundaries while greatly reducing sensitivity to local noise or other intervening structures. Robustness is further enhanced with on-the-fly training which causes the boundary to adhere to the specific type of edge currently being followed, rather than simply the strongest edge in the neighborhood. Boundary cooling automatically freezes unchanging segments and automates input of additional seed points. Cooling also allows the user to be much more free with the gesture path, thereby increasing the efficiency and finesse with which boundaries can be extracted. <s> BIB001 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Abstract In multidimensional image analysis, there are, and will continue to be, situations wherein automatic image segmentation methods fail, calling for considerable user assistance in the process. The main goals of segmentation research for such situations ought to be (i) to provide effective control to the user on the segmentation process while it is being executed, and (ii) to minimize the total user's time required in the process. With these goals in mind, we present in this paper two paradigms, referred to as live wire and live lane , for practical image segmentation in large applications. For both approaches, we think of the pixel vertices and oriented edges as forming a graph, assign a set of features to each oriented edge to characterize its ``boundariness,'' and transform feature values to costs. We provide training facilities and automatic optimal feature and transform selection methods so that these assignments can be made with consistent effectiveness in any application. In live wire, the user first selects an initial point on the boundary. For any subsequent point indicated by the cursor, an optimal path from the initial point to the current point is found and displayed in real time. The user thus has a live wire on hand which is moved by moving the cursor. If the cursor goes close to the boundary, the live wire snaps onto the boundary. At this point, if the live wire describes the boundary appropriately, the user deposits the cursor which now becomes the new starting point and the process continues. A few points (live-wire segments) are usually adequate to segment the whole 2D boundary. In live lane, the user selects only the initial point. Subsequent points are selected automatically as the cursor is moved within a lane surrounding the boundary whose width changes as a function of the speed and acceleration of cursor motion. Live-wire segments are generated and displayed in real time between successive points. The users get the feeling that the curve snaps onto the boundary as and while they roughly mark in the vicinity of the boundary. We describe formal evaluation studies to compare the utility of the new methods with that of manual tracing based on speed and repeatability of tracing and on data taken from a large ongoing application. The studies indicate that the new methods are statistically significantly more repeatable and 1.5–2.5 times faster than manual tracing. <s> BIB002 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this paper we present a data structure that improves region segmentation of 2D images. This data structure provides an efficient access to both geometric features such as the set of pixels of a region and topological features like the frontier of a region, the neighbors of a region or the set of regions included in one region. It allows us to combine different segmentation algorithms without restriction. Interactive refinement or merge of regions can also be performed efficiently. <s> BIB003 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> The authors have been developing general user steered image segmentation strategies for routine use in applications involving a large number of data sets. In the past, they have presented three segmentation paradigms: live wire, live lane, and a three-dimensional (3-D) extension of the live-wire method. Here, they introduce an ultra-fast live-wire method, referred to as live wire on the fly for further reducing user's time compared to the basic live-wire method. In live wire, 3-D/four-dimensional (4-D) object boundaries are segmented in a slice-by-slice fashion. To segment a two-dimensional (2-D) boundary, the user initially picks a point on the boundary and all possible minimum-cost paths from this point to all other points in the image are computed via Dijkstra's algorithm. Subsequently, a live wire is displayed in real time from the initial point to any subsequent position taken by the cursor. If the cursor is close to the desired boundary, the live wire snaps on to the boundary. The cursor is then deposited and a new live-wire segment is found next. The entire 2-D boundary is specified via a set of live-wire segments in this fashion. A drawback of this method is that the speed of optimal path computation depends on image size. On modestly powered computers, for images of even modest size, some sluggishness appears in user interaction, which reduces the overall segmentation efficiency. In this work, the authors solve this problem by exploiting some known properties of graphs to avoid unnecessary minimum-cost path computation during segmentation. In live wire on the fly, when the user selects a point on the boundary the live-wire segment is computed and displayed in real time from the selected point to any subsequent position of the cursor in the image, even for large images and even on low-powered computers. Based on 492 tracing experiments from an actual medical application, the authors demonstrate that live wire on the fly is 1.331 times faster than live wire for actual segmentation for varying image sizes, although the pure computational part alone is found to be about 120 times faster. <s> BIB004 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this paper we describe a new technique for general purpose interactive segmentation of N-dimensional images. The user marks certain pixels as "object" or "background" to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and region information. Graph cuts are used to find the globally optimal segmentation of the N-dimensional image. The obtained solution gives the best balance of boundary and region properties among all segmentations satisfying the constraints. The topology of our segmentation is unrestricted and both "object" and "background" segments may consist of several isolated parts. Some experimental results are presented in the context of photo/video editing and medical image segmentation. We also demonstrate an interesting Gestalt example. A fast implementation of our segmentation method is possible via a new max-flow algorithm. <s> BIB005 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this paper we present a graph cuts based active contours (GCBAC) approach to object segmentation problems. Our method is a combination of active contours and the optimization tool of graph cuts and differs fundamentally from traditional active contours in that it uses graph cuts to iteratively deform the contour. Consequently, it has the following advantages. (1) It has the ability to jump over local minima and provide a more global result. (2) Graph cuts guarantee continuity and lead to smooth contours free of self-crossing and uneven spacing problems. Therefore, the internal force, which is commonly used in traditional energy functions to control the smoothness, is no longer needed, and hence the number of parameters is greatly reduced. (3). Our approach easily extends to the segmentation of three and higher dimensional objects. In addition, the algorithm is suitable for interactive correction and is shown to always converge. Experimental results and analyses are provided. <s> BIB006 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools. <s> BIB007 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Interactive or semi-automatic segmentation is a useful alternative to pure automatic segmentation in many applications. While automatic segmentation can be very challenging, a small amount of user input can often resolve ambiguous decisions on the part of the algorithm. In this work, we devise a graph cut algorithm for interactive segmentation which incorporates shape priors. While traditional graph cut approaches to interactive segmentation are often quite successful, they may fail in cases where there are diffuse edges, or multiple similar objects in close proximity to one another. Incorporation of shape priors within this framework mitigates these problems. Positive results on both medical and natural images are demonstrated. <s> BIB008 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> We present a graph cuts-based image segmentation technique that incorporates an elliptical shape prior. Inclusion of this shape constraint restricts the solution space of the segmentation result, increasing robustness to misleading information that results from noise, weak boundaries, and clutter. We argue that combining a shape prior with a graph cuts method suggests an iterative approach that updates an intermediate result to the desired solution. We first present the details of our method and then demonstrate its effectiveness in segmenting vessels and lymph nodes from pelvic magnetic resonance images, as well as human faces. <s> BIB009 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In the short time since publication of Boykov and Jolly's seminal paper [2001], graph cuts have become well established as a leading method in 2D and 3D semi-automated image segmentation. Although this approach is computationally feasible for many tasks, the memory overhead and supralinear time complexity of leading algorithms results in an excessive computational burden for high-resolution data. In this paper, we introduce a multilevel banded heuristic for computation of graph cuts that is motivated by the well-known narrow band algorithm in level set computation. We perform a number of numerical experiments to show that this heuristic drastically reduces both the running time and the memory consumption of graph cuts while producing nearly the same segmentation result as the conventional graph cuts. Additionally, we are able to characterize the type of segmentation target for which our multilevel banded heuristic yields different results from the conventional graph cuts. The proposed method has been applied to both 2D and 3D images with promising results. <s> BIB010 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Combinatorial graph cut algorithms have been successfully applied to a wide range of problems in vision and graphics. This paper focusses on possibly the simplest application of graph-cuts: segmentation of objects in image data. Despite its simplicity, this application epitomizes the best features of combinatorial graph cuts methods in vision: global optima, practical efficiency, numerical robustness, ability to fuse a wide range of visual cues and constraints, unrestricted topological properties of segments, and applicability to N-D problems. Graph cuts based approaches to object extraction have also been shown to have interesting connections with earlier segmentation methods such as snakes, geodesic active contours, and level-sets. The segmentation energies optimized by graph cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah style functionals. We present motivation and detailed technical description of the basic combinatorial optimization framework for image segmentation via s/t graph cuts. After the general concept of using binary graph cut algorithms for object segmentation was first proposed and tested in Boykov and Jolly (2001), this idea was widely studied in computer vision and graphics communities. We provide links to a large number of known extensions based on iterative parameter re-estimation and learning, multi-scale or hierarchical approaches, narrow bands, and other techniques for demanding photo, video, and medical applications. <s> BIB011 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> We describe a means to automatically and efficiently isolate the outer surface of the entire heart in computer tomography (CT) cardiac scans. Isolating the entire heart allows the coronary vessels on the surface of the heart to be easily visualized despite the proximity of surrounding organs such as the ribs and pulmonary blood vessels. Numerous techniques have been described for segmenting the left ventricle of the heart in images from various types of medical scanners but rarely has the entire heart been segmented. We make use of graph-cuts to do the segmentation and introduce a novel means of initiating and constraining the graph-cut technique for heart isolation. The technique has been tested on 70 patient data sets. Results are compares with hand labeled results. <s> BIB012 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> A novel method is proposed for performing multilabel, interactive image segmentation. Given a small number of pixels with user-defined (or predefined) labels, one can analytically and quickly determine the probability that a random walker starting at each unlabeled pixel will first reach one of the prelabeled pixels. By assigning each pixel to the label for which the greatest probability is calculated, a high-quality image segmentation may be obtained. Theoretical properties of this algorithm are developed along with the corresponding connections to discrete potential theory and electrical circuits. This algorithm is formulated in discrete space (i.e., on a graph) using combinatorial analogues of standard operators and principles from continuous potential theory, allowing it to be applied in arbitrary dimension on arbitrary graphs <s> BIB013 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Segmentation of medical images is an important step in many clinical and diagnostic imaging applications. Medical images present many challenges for automated segmentation including poor contrast at tissue boundaries. Traditional segmentation methods based solely on information from the image do not work well in such cases. Statistical shape information for objects in medical images are easy to obtain. In this paper, we propose a graph cuts-based segmentation method for medical images that incorporates statistical shape priors to increase robustness. Our proposed method is able to deal with complex shapes and shape variations while taking advantage of the globally efficient optimization by graph cuts. We demonstrate the effectiveness of our method on kidney images without strong boundaries. <s> BIB014 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this paper, we present a fast new fully dynamic algorithm for the st-mincut/max-flow problem. We show how this algorithm can be used to efficiently compute MAP solutions for certain dynamically changing MRF models in computer vision such as image segmentation. Specifically, given the solution of the max-flow problem on a graph, the dynamic algorithm efficiently computes the maximum flow in a modified version of the graph. The time taken by it is roughly proportional to the total amount of change in the edge weights of the graph. Our experiments show that, when the number of changes in the graph is small, the dynamic algorithm is significantly faster than the best known static graph cut algorithm. We test the performance of our algorithm on one particular problem: the object-background segmentation problem for video. It should be noted that the application of our algorithm is not limited to the above problem, the algorithm is generic and can be used to yield similar improvements in many other cases that involve dynamic change. <s> BIB015 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Capacity scaling is a hierarchical approach to graph representation that can improve theoretical complexity and practical efficiency of max-flow/min-cut algorithms. Introduced by Edmonds, Karp, and Dinic in 1972, capacity scaling is well known in the combinatorial optimization community. Surprisingly, this major performance improving technique is overlooked in computer vision where graph cut methods typically solve energy minimization problems on huge N-D grids and algorithms' efficiency is a widely studied issue. Unlike some earlier hierarchical methods addressing efficiency of graph cuts in imaging, e.g. (H. Lombaert, 2005), capacity scaling preserves global optimality of the solution. This is the main motivation for our work studying capacity scaling in the context of vision. We show that capacity scaling significantly reduces non-polynomial theoretical time complexity of the max-flow algorithm in (Y. Boykov and V. Kolmorogorov, 2004) to weakly polynomial O(m2n2log(U)) where U is the largest edge weight. While (Y. Boykov and V. Kolmorogorov, 2004) is the fastest method for many applications in vision, capacity scaling gives several folds speed-ups for problems with large number of local minima. The effect is particularly strong in 3D applications with denser neighborhoods. <s> BIB016 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> An important problem in medical image analysis is the segmentation of anatomical regions of interest. Once ::: regions of interest are segmented, one can extract shape, appearance, and structural features that can be analyzed ::: for disease diagnosis or treatment evaluation. Diffusion tensor magnetic resonance imaging (DT-MRI) is ::: a relatively new medical imaging modality that captures unique water diffusion properties and fiber orientation ::: information of the imaged tissues. In this paper, we extend the interactive multidimensional graph cuts segmentation ::: technique to operate on DT-MRI data by utilizing latest advances in tensor calculus and diffusion tensor ::: dissimilarity metrics. The user interactively selects certain tensors as object ("obj") or background ("bkg") to ::: provide hard constraints for the segmentation. Additional soft constraints incorporate information about both ::: regional tissue diffusion as well as boundaries between tissues of different diffusion properties. Graph cuts are ::: used to find globally optimal segmentation of the underlying 3D DT-MR image among all segmentations satisfying ::: the constraints. We develop a graph structure from the underlying DT-MR image with the tensor voxels ::: corresponding to the graph vertices and with graph edge weights computed using either Log-Euclidean or the ::: J-divergence tensor dissimilarity metric. The topology of our segmentation is unrestricted and both obj and bkg ::: segments may consist of several isolated parts. We test our method on synthetic DT data and apply it to real ::: 2D and 3D MRI, providing segmentations of the corpus callosum in the brain and the ventricles of the heart. <s> BIB017 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> This paper proposes a novel method to apply the standard graph cut technique to segmenting multimodal tensor valued images. The Riemannian nature of the tensor space is explicitly taken into account by first mapping the data to a Euclidean space where non-parametric kernel density estimates of the regional distributions may be calculated from user initialized regions. These distributions are then used as regional priors in calculating graph edge weights. Hence this approach utilizes the true variation of the tensor data by respecting its Riemannian structure in calculating distances when forming probability distributions. Further, the non-parametric model generalizes to arbitrary tensor distribution unlike the Gaussian assumption made in previous works. Casting the segmentation problem in a graph cut framework yields a segmentation robust with respect to initialization on the data tested. <s> BIB018 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this paper we present a graph cuts based active contours (GCBAC) approach to object segmentation. GCBAC approach is a combination of the iterative deformation idea of active contours and the optimization tool of graph cuts. It differs from traditional active contours in that it uses graph cuts to iteratively deform the contour and its cost function is defined as the summation of edge weights on the cut. The resulting contour at each iteration is the global optimum within a contour neighborhood (CN) of the previous result. Since this iterative algorithm is shown to converge, the final contour is the global optimum within its own CN. The use of contour neighborhood alleviates the well-known bias of the minimum cut in favor of a shorter boundary. GCBAC approach easily extends to the segmentation of three and higher dimensional objects, and is suitable for interactive correction. Experimental results on selected data sets and performance analysis are provided. <s> BIB019 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In this article, we presented a progressive-cut algorithm for background and foreground segmentation. We first analyzed the user intention behind the additional user-specified stroke, and then incorporated the user intention into the graph-cut framework: we derived an eroded graph to prevent overshrinkage, and added a user attention term to the energy function to compress overexpansion in low-interest areas. Experiments showed that the new algorithm outperforms existing graph-cut methods in both accuracy and speed, and it effectively removes the fluctuation effect, making results more controllable with fewer strokes. <s> BIB020 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Graph cut is a popular technique for interactive image segmentation. However, it has certain shortcomings. In particular, graph cut has problems with segmenting thin elongated objects due to the ldquoshrinking biasrdquo. To overcome this problem, we propose to impose an additional connectivity prior, which is a very natural assumption about objects. We formulate several versions of the connectivity constraint and show that the corresponding optimization problems are all NP-hard. For some of these versions we propose two optimization algorithms: (i) a practical heuristic technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition which provides a lower bound on the problem. We use the second technique to verify that for some practical examples DijkstraGC is able to find the global minimum. <s> BIB021 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In recent years, segmentation with graph cuts is increasingly used for a variety of applications, such as photo/video editing, medical image processing, etc. One of the most common applications of graph cut segmentation is extracting an object of interest from its background. If there is any knowledge about the object shape (i.e. a shape prior), incorporating this knowledge helps to achieve a more robust segmentation. In this paper, we show how to implement a star shape prior into graph cut segmentation. This is a generic shape prior, i.e. it is not specific to any particular object, but rather applies to a wide class of objects, in particular to convex objects. Our major assumption is that the center of the star shape is known, for example, it can be provided by the user. The star shape prior has an additional important benefit - it allows an inclusion of a term in the objective function which encourages a longer object boundary. This helps to alleviate the bias of a graph cut towards shorter segmentation boundaries. In fact, we show that in many cases, with this new term we can achieve an accurate object segmentation with only a single pixel, the center of the object, provided by the user, which is rarely possible with standard graph cut interactive segmentation. <s> BIB022 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> Global optimisation via s-t graph cuts is widely used in computer vision and graphics. To obtain high-resolution output, graph cut methods must construct massive N-D grid-graphs containing billions of vertices. We show that when these graphs do not fit into physical memory, current max-flow/min-cut algorithms-the workhorse of graph cut methods-are totally impractical. Others have resorted to banded or hierarchical approximation methods that get trapped in local minima, which loses the main benefit of global optimisation. We enhance the push-relabel algorithm for maximum flow [14] with two practical contributions. First, true global minima can now be computed on immense grid-like graphs too large for physical memory. These graphs are ubiquitous in computer vision, medical imaging and graphics. Second, for commodity multi-core platforms our algorithm attains near-linear speedup with respect to number of processors. To achieve these goals, we generalised the standard relabeling operations associated with push-relabel. <s> BIB023 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE 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> BIB024 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> A modified graph cut was proposed under the elliptical shape constraint to segment cervical lymph nodes on sonograms, and its effect on the measurement of short axis to long axis ratio (S/L) was investigated by using the relative ultimate measurement accuracy (RUMA). Under the same user inputs, the proposed algorithm successfully segmented all 60 sonograms tested, while the traditional graph cut failed. The mean RUMA resulted from the developed method was comparable to that resulted from the manual segmentation. Results indicated that utilizing the elliptical shape prior could appreciably improve the graph cut for nodes segmentation, and the proposed method satisfied the accuracy requirement of S/L measurement. <s> BIB025 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> In recent years, interactive methods for segmentation are increasing in popularity due to their success in different domains such as medical image processing, photo editing, etc. We present an interactive segmentation algorithm that can segment an object of interest from its background with minimum guidance from the user, who just has to select a single seed pixel inside the object of interest. Due to minimal requirements from the user, we call our algorithm semiautomatic. To obtain a reliable and robust segmentation with such low user guidance, we have to make several assumptions. Our main assumption is that the object to be segmented is of compact shape, or can be approximated by several connected roughly collinear compact pieces. We base our work on the powerful graph cut segmentation algorithm of Boykov and Jolly, which allows straightforward incorporation of the compact shape constraint. In order to make the graph cut approach suitable for our semiautomatic framework, we address several well-known issues of graph cut segmentation technique. In particular, we counteract the bias towards shorter segmentation boundaries and develop a method for automatic selection of parameters. We demonstrate the effectiveness of our approach on the challenging industrial application of transistor gate segmentation in images of integrated chips. Our approach produces highly accurate results in real-time. <s> BIB026 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> A new algorithm for interactive image segmentation is proposed. Besides the traditional appearance and gradient information, a new Generic Shape Prior (GSP) knowledge which implies the location and the shape information of the object is combined into the framework. The GSP can be further categorized into the Regional and the Contour GSP to fit the interactive application, where a hierarchical graph-cut based optimization procedure is established, for its global optimization using the regional GSP to obtain good global segmentation results, and the local one using the Contour GSP to refine boundaries of global results. Moreover, the global optimization is based on superpixels which significantly reduce the computational complexity but preserve necessary image structures; the local one only considers a subset pixels around a contour segment, they both speed up the system. Results show our method performs better on both speed and accuracy. <s> BIB027 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> We present a fast graph cut algorithm for planar graphs. It is based on the graph theoretical work and leads to an efficient method that we apply on shape matching and image segmentation. In contrast to currently used methods in computer vision, the presented approach provides an upper bound for its runtime behavior that is almost linear. In particular, we are able to match two different planar shapes of N points in O(N2 log N) and segment a given image of N pixels in O(N log N). We present two experimental benchmark studies which demonstrate that the presented method is also in practice faster than previously proposed graph cut methods: On planar shape matching and image segmentation we observe a speed-up of an order of magnitude, depending on resolution. <s> BIB028 </s> A Review on Graph Based Segmentation <s> III. INTERACTIVE METHODS <s> We introduce a framework for synergistic arc-weight estimation, where the user draws markers inside each object (including background), arc weights are estimated from image attributes and object information (pixels under the markers), and a visual feedback guides the user's next action. We demonstrate the method in several graph-based segmentation approaches as a basic step (which should be followed by some proper approach-specific adaptive procedure) and show its advantage over methods that do not exploit object information and over methods that recompute weights during delineation, which make the user to lose control over the segmentation process. We also validate the method using medical data from two imaging modalities (CT and MRI-T1). <s> BIB029
A large variety of interactive segmentation methods have been developed during the years. In general, none of them is superior to all the others. Also, some methods might be more suited for solving particular segmentation problem better than the others. In short, the main steps of an interactive graph based segmentation method are the following: (1) Get the user preferences and (2) generate an optimal solution (if not, a sub-optimal solution) according to the user preferences and show it. In situations where automatic segmentation is difficult and cannot guarantee correctness or reliability, these interactive methods are best opted. The interactive graph based segmentation methods take the advantage of reliability under users' control. Major research works in this category are live-wire methods BIB001 BIB004 BIB002 , a discrete map data structure by Braquelaire et al. BIB003 , an interactive graph cuts method BIB005 BIB011 , methods admitting shape priors into the interactive graph cuts method BIB008 BIB009 BIB025 BIB014 BIB012 BIB026 BIB021 BIB022 BIB027  , methods that improve running time of the interactive graph cuts method BIB010 BIB015 BIB016 BIB023 BIB028 and methods which use the interactive graph cuts method in some applications BIB017 BIB018 . Other research contributions in this category are the synergistic arch weight estimation approach by Miranda et al. BIB029 , a Grabcut algorithm by Rother et al. BIB007 , a random walker algorithm by Grady BIB013 , an active contours refining method by Xu et al. BIB006 BIB019 , and a progressive cut algorithm by Wang et al. BIB020  . These are briefly reviewed in the following. In the live-wire method BIB001 BIB002 , the user is required to specify some points in the desired object boundary. The shortest path (using Dijkstra's algorithm), which links all these pre-defined points, is determined. This shortest path makes up the boundary which encloses the desired object. A faster version of live-wire was later introduced by Falcao et al. BIB004 by devising a linear time graph searching algorithm. Based on segmentation results of 492 medical images, it was observed that this faster version is about 1.3 to 31 times faster than the live wire BIB004 . An example for the live wire is provided in Figure 7 . Braquelaire et al. [61] presented a discrete map data structure, which uses a region adjacency graph for merging operations, for interactive image segmentation. The discrete map permits a unified representation of both topology and geometry of a segmented image. The interactive graph cuts BIB005 BIB011 method is a popular method of this category. This method exploits two constraints for segmenting images: hard and soft. Consider ρ contains pixels and N contains unordered pairs of neighbouring pixels. be a segmentation such that A p can either belong to the "background" or "foreground". The soft constraints are defined in the form of a cost function E(A) that takes into account both boundary and region properties of segments. The coefficient R p (.) and B {p,q} are region and boundary terms that specifies the penalties for assigning pixel p to "object" and "background", and a penalty for a discontinuity between p and q respectively. The coefficient  , which specifies the relative importance of the region term against the boundary term, can have values greater than or equal to 0. The user has to tender hard constraints based on his intension by marking some pixels as foreground/background as The idea is to compute the global minimum of the soft constraints among all segmentations A satisfying the hard constraints. This is done using max-flow/min-cut analysis. From an image, a graph with two additional vertices, a "background" terminal and an "object" terminal, is built. The edge set comprises of two types of undirected edges: terminal links (t-links) and neighborhood links (n-links). Each vertex has two t-links connecting to the terminals and the link weights are defined by the regional term and hard constraints. Each pair of neighboring pixels is connected by an n-link and its weight is defined by the boundary term. The minimum cost cut of the graph forms the partition between the object and the background. It can be noted that this method also belongs to the classgraph cut based methods. Results of this method are recorded in Figure 8 . Apart from its obvious advantage of producing globally optimal solutions, the interactive graph cuts method gives rise to less satisfactory results on images dominated by desired weak contrast boundaries (meaning-these weak contrast boundaries are intended to be identified) and undesired strong contrast boundaries. Figure 8 . Segmentation of photographs using the interactive graph cuts method BIB011 . The dark red regions and blue regions are user marked hard constraints for foreground and background respectively, while the corresponding light colors represent segmentation using this method A few methods admitted shape priors into the interactive graph cuts method to improve its accuracy. Freedman and Zhang BIB008 embedded shape priors into weights of edges by using a level set formation. Slabaugh and Unal BIB009 incorporated an elliptical shape prior into the interactive graph cuts method. A user is expected to initialize the segmentation by marking a seed point in an image which evolves later as an ellipse on employing this approach. Zhang et al. BIB025 also integrated elliptical shape priors into the interactive graph cuts method, but in a different way from the earlier method, to segment cervical lymph nodes on sonograms. Zhu-Jacquot et al. BIB014 integrated geometric shape priors into the interactive graph cuts method for kidney segmentation from MRI. By making use of the shape information of the heartheart is a compact blob, Funka-Lea et al. BIB012 included blob constraints to isolate the heart from CT scans. The interactive graph cuts method biases towards shorter boundaries. Das et al. BIB026 , by adding compact shape priors to the interactive graph cuts method, altered its behavior to bias towards larger objects. The interactive graph cuts method is weak in segmenting thin elongated objects. To overcome this problem, Vicente et al. BIB021 enforced connectivity priors to it. The work also imposes topology BIB024 , specifically, 0-topology. It was shown that the connectivity constraint optimization problems are all NP-hard BIB021 . Veksler BIB022 introduced a star shape prior into the graph cuts method. Liu et al. BIB027 inserted a regional and contour generic shape prior into the graph cuts framework. Kumar et al.  formulated OBJ CUT, which uses a loopy belief propagation algorithm to incorporate shape priors into graph cuts. Aside improving the accuracy of the interactive graph cuts method, a few attempts have been made to improve its running time by means of multilevel banded heuristics BIB010 , flow recycling BIB015 , capacity scaling BIB016 , multi-scaling BIB023 , or by planar graph cuts BIB028 . Weldeselassie and Hamarneh BIB017 extended the interactive graph cuts to segment diffusion tensor MRI data by making use of tensor calculus and tensor dissimilarity metrics. Malcolm et al. BIB018 employed the interactive graph cuts method to segment multi-modal tensor valued images by taking into account the Riemannian geometry of the tensor space. Miranda et al. BIB029 introduced an interactive method for synergistic arch weight estimation, which considers both image attributes and object information. The arch weight estimation finds one of its applications as a basic step in the interactive graph cuts method. The Grabcut algorithm BIB007 extracts the foreground of an image, by utilizing a rectangular shaped user's input which roughly holds the foreground, by employing graph cut iteratively. In the random walker algorithm BIB013 , some pixels should be pre-classified by the user. In the subsequent steps, an unclassified pixel is assigned a classified pixel label when a random walker has been given the greatest probability on traversing first to the classified pixel from the unclassified pixel. An example of segmentation results obtained using this random walker algorithm is given in Figure 9 . Xu et al. BIB006 BIB019 suggested a segmentation method to refine active contours by iteratively deforming contours using graph cuts. This method also allows an interactive correction of the final boundary if it is not satisfactory. Examples of the segmentation found by the Graph cuts based active contours are displayed in Figure 10 object but not multiple objects and also, the graph that is used in this method must be constructed with appropriate pixel connectivity and edge weights. Wang et al. BIB020  proposed a progressive cut algorithm which explicitly considers user's intention into a graph cut framework for object cutout task. The interactive graph based methods demand user intervention which is not possible or desirable in many applications. Also, necessary training to the user for interacting to a real time system that uses any of these methods might be required to produce intended results. Figure 10 . Graph cuts based active contours BIB019 .The two images in the top row show the initialization for graph cuts based active contours. The two images in the bottom row show the corresponding segmentation results using this method