A Review on Graph Based Segmentation <s> INTRODUCTION <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> INTRODUCTION <s> A fast and flexible algorithm for computing watersheds in digital gray-scale images is introduced. A review of watersheds and related motion is first presented, and the major methods to determine watersheds are discussed. The algorithm is based on an immersion process analogy, in which the flooding of the water in the picture is efficiently simulated using of queue of pixel. It is described in detail provided in a pseudo C language. The accuracy of this algorithm is proven to be superior to that of the existing implementations, and it is shown that its adaptation to any kind of digital grid and its generalization to n-dimensional images (and even to graphs) are straightforward. The algorithm is reported to be faster than any other watershed algorithm. Applications of this algorithm with regard to picture segmentation are presented for magnetic resonance (MR) imagery and for digital elevation models. An example of 3-D watershed is also provided. > <s> BIB002 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB003 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB004 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB005 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB006 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB007 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB008 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> The notion of fuzzy connectedness captures the idea of “hanging-togetherness” of image elements in an object by assigning a strength of connectedness to every possible path between every possible pair of image elements. This concept leads to powerful image segmentation algorithms based on dynamic programming whose effectiveness has been demonstrated on thousands of images in a variety of applications. In a previous framework, we introduced the notion of relative fuzzy connectedness for separating a foreground object from a background object. In this framework, an image element c is considered to belong to that among these two objects with respect to whose reference image element c has the higher strength of connectedness. In fuzzy connectedness, a local fuzzy relation called affinity is used on the image domain. This relation was required for theoretical reasons to be of fixed form in the previous framework. In the present paper, we generalize relative connectedness to multiple objects, allowing all objects (of importance) to compete among themselves to grab membership of image elements based on their relative strength of connectedness to reference elements. We also allow affinity to be tailored to the individual objects. We present a theoretical and algorithmic framework and demonstrate that the objects defined are independent of the reference elements chosen as long as they are not in the fuzzy boundary between objects. Examples from medical imaging are presented to illustrate visually the effectiveness of multiple object relative fuzzy connectedness. A quantitative evaluation based on 160 mathematical phantom images demonstrates objectively the effectiveness of relative fuzzy connectedness with object-tailored affinity relation. <s> BIB009 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> The watershed transform has interesting properties that make it useful for many different image segmentation applications: it is simple and intuitive, can be parallelized, and always produces a complete division of the image. However, when applied to medical image analysis, it has important drawbacks (oversegmentation, sensitivity to noise, poor detection of thin or low signal to noise ratio structures). We present an improvement to the watershed transform that enables the introduction of prior information in its calculation. We propose to introduce this information via the use of a previous probability calculation. Furthermore, we introduce a method to combine the watershed transform and atlas registration, through the use of markers. We have applied our new algorithm to two challenging applications: knee cartilage and gray matter/white matter segmentation in MR images. Numerical validation of the results is provided, demonstrating the strength of the algorithm for medical image segmentation. <s> BIB010 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB011 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> The image foresting transform (IFT) is a graph-based approach to the design of image processing operators based on connectivity. It naturally leads to correct and efficient implementations and to a better understanding of how different operators relate to each other. We give here a precise definition of the IFT, and a procedure to compute it-a generalization of Dijkstra's algorithm-with a proof of correctness. We also discuss implementation issues and illustrate the use of the IFT in a few applications. <s> BIB012 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB013 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> Active Shape Models (ASM) are widely employed for recognizing ::: anatomic structures and for delineating them in medical images. In ::: this paper, we present a novel strategy called Oriented Active ::: Shape Models (OASM) in an attempt to overcome the following three ::: major limitations of ASM: (1) poor delineation accuracy, (2) the ::: requirement of a large number of landmarks, (3) the problem of ::: sensitivity to search range to recognize the object boundary. OASM ::: effectively combines the rich statistical shape information ::: embodied in ASM with the boundary orientedness property and the ::: globally optimal delineation capability of the live wire ::: methodology of boundary segmentation. The latter allow live wire ::: to effectively separate an object boundary from other non object ::: boundaries with similar properties that come very close in the ::: image domain. Our approach leads us to a 2-level dynamic ::: programming method, wherein the first level corresponds to ::: boundary recognition and the second level corresponds to boundary ::: delineation. Our experiments in segmenting breast, liver, bones of ::: the foot, and cervical vertebrae of the spine in MR and CT images ::: indicate the following: (1) The accuracy of segmentation via OASM ::: is considerably better than that of ASM. (2) The number of ::: landmarks can be reduced by a factor of 3 in OASM over that in ::: ASM. (3) OASM becomes largely independent of search range. All ::: three benefits of OASM ensue mainly from the severe constraints ::: brought in by the boundary-orientedness property of live wire and ::: the globally optimal solution of dynamic programming. <s> BIB014 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB015 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB016 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB017 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB018 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> An interactive algorithm for soft segmentation and matting of natural images and videos is presented in this paper. The technique follows and extends Protiere et al. (2007), where the user first roughly scribbles/labels different regions of interest, and from them the whole data is automatically segmented. The segmentation and alpha matte are obtained from the fast, linear complexity, computation of weighted distances to the user-provided scribbles. These weighted distances assign probabilities to each labeled class for every pixel. The weights are derived from models of the image regions obtained from the user provided scribbles via kernel density estimation. The matting results follow from combining this density and the computed weighted distances. We present the underlying framework and examples showing the capability of the algorithm to segment and compute alpha mattes, in interactive real time, for difficult natural data. <s> BIB019 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> An interactive algorithm for soft segmentation of natural images is presented in this paper. The user first roughly scribbles different regions of interest, and from them, the whole image is automatically segmented. This soft segmentation is obtained via fast, linear complexity computation of weighted distances to the user-provided scribbles. The adaptive weights are obtained from a series of Gabor filters, and are automatically computed according to the ability of each single filter to discriminate between the selected regions of interest. We present the underlying framework and examples showing the capability of the algorithm to segment diverse images <s> BIB020 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> Abstract In this paper we present a new theory and an algorithm for image segmentation based on a strength of connectedness between every pair of image elements. The object definition used in the segmentation algorithm utilizes the notion of iterative relative fuzzy connectedness, IRFC. In previously published research, the IRFC theory was developed only for the case when the segmentation was involved with just two segments, an object and a background, and each of the segments was indicated by a single seed. (See Udupa et al. [J.K. Udupa, P.K. Saha, R.A. Lotufo, Relative fuzzy connectedness and object definition: theory, algorithms, and applications in image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 24 (2002) 1485–1500] and Saha and Udupa [P.K. Saha, J.K. Udupa, Iterative relative fuzzy connectedness and object definition: theory, algorithms, and applications in image segmentation, in: Proceedings of IEEE Workshop on Mathematical Methods in Biomedical Image Analysis, Hilton Head, South Carolina, 2002, pp. 28–35].) Our theory, which solves a problem of Udupa and Saha from [J.K. Udupa, P.K. Saha, Fuzzy connectedness in image segmentation, Proc. IEEE 91 (10) (2003) 1649–1669], allows simultaneous segmentation involving an arbitrary number of objects. Moreover, each segment can be indicated by more than one seed, which is often more natural and easier than a single seed object identification. The first iteration step of the IRFC algorithm gives a segmentation known as relative fuzzy connectedness, RFC, segmentation. Thus, the IRFC technique is an extension of the RFC method. Although the RFC theory, due to Saha and Udupa [P.K. Saha, J.K. Udupa, Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation, Comput. Vis. Image Understand. 82 (1) (2001) 42–56], is developed in the multi object/multi seed framework, the theoretical results presented here are considerably more delicate in nature and do not use the results from [P.K. Saha, J.K. Udupa, Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation, Comput. Vis. Image Understand. 82 (1) (2001) 42–56]. On the other hand, the theoretical results from [P.K. Saha, J.K. Udupa, Relative fuzzy connectedness among multiple objects: theory, algorithms, and applications in image segmentation, Comput. Vis. Image Understand. 82 (1) (2001) 42–56] are immediate consequences of the results presented here. Moreover, the new framework not only subsumes previous fuzzy connectedness descriptions but also sheds new light on them. Thus, there are fundamental theoretical advances made in this paper. We present examples of segmentations obtained via our IRFC-based algorithm in the multi-object/multi-seed environment, and compare it with the results obtained with the RFC-based algorithm. Our results indicate that, in many situations, IRFC outperforms RFC, but there also exist instances where the gain in performance is negligible. <s> BIB021 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> This paper proposes a novel algorithm for the problem of structural image segmentation through an interactive model-based approach. Interaction is expressed in the model creation, which is done according to user traces drawn over a given input image. Both model and input are then represented by means of attributed relational graphs derived on the fly. Appearance features are taken into account as object attributes and structural properties are expressed as relational attributes. To cope with possible topological differences between both graphs, a new structure called the deformation graph is introduced. The segmentation process corresponds to finding a labelling of the input graph that minimizes the deformations introduced in the model when it is updated with input information. This approach has shown to be faster than other segmentation methods, with competitive output quality. Therefore, the method solves the problem of multiple label segmentation in an efficient way. Encouraging results on both natural and target-specific color images, as well as examples showing the reusability of the model, are presented and discussed. <s> BIB022 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB023 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> We propose an approach for data clustering based on optimum-path forest. The samples are taken as nodes of a graph, whose arcs are defined by an adjacency relation. The nodes are weighted by their probability density values (pdf) and a connectivity function is maximized, such that each maximum of the pdf becomes root of an optimum-path tree (cluster), composed by samples “more strongly connected” to that maximum than to any other root. We discuss the advantages over other pdf-based approaches and present extensions to large datasets with results for interactive image segmentation and for fast, accurate, and automatic brain tissue classification in magnetic resonance (MR) images. We also include experimental comparisons with other clustering approaches. © 2009 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 19, 50–68, 2009. <s> BIB024 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> We present improvements to a recently proposed model-based segmentation strategy, called Clouds. We demonstrate the usefulness of the new model Cloud Bank in the automatic MR-image segmentation of the brain (without medulla and spinal cord), the cerebellum, and each brain hemisphere. These structures are connected in several parts, imposing serious challenges for segmentation. The results indicate that the new model is a fast and accurate tool to eliminate user's intervention or, at least, reduce it to simple corrections, in the context of brain image segmentation. <s> BIB025 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <s> Image segmentation can be elegantly solved by optimum-path forest and minimum cut in graph. Given that both approaches exploit similar image graphs, some comparative analysis is expected between them. We clarify their differences and provide their comparative analysis from the theoretical point of view, for the case of binary segmentation (object/background) in which hard constraints (seeds) are provided interactively. Particularly, we formally prove that some optimum-path forest methods from two distinct region-based segmentation paradigms, with internal and external seeds and with only internal seeds, indeed minimize some graph-cut measures. This leads to a proof of the necessary conditions under which the optimum-path forest algorithm and the min-cut/max-flow algorithm produce exactly the same segmentation result, allowing a comparative analysis between them. <s> BIB026 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB027 </s> A Review on Graph Based Segmentation <s> INTRODUCTION <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> BIB028
Image segmentation can simply result an image partition composed by relevant regions, but the most fundamental challenge in segmentation is to precisely define the spatial extent of some object, which may be represented by the union of multiple regions. In this sense, examples of possible strategies are: (i) The image is divided into regions and then the object is composed by the union of some of these regions BIB022 BIB024 . (ii) The approximate location of the object/boundary is found and its spatial extent is defined from that location BIB004 BIB007 BIB027 BIB019 BIB020 BIB008 . In any case, the strategies are composed by (a) Object recognition tasks (e.g., regions that compose the object, a point on its boundary, a line inside it, the verification of a segmentation result, the matching between the image and an object model, etc). (b) Object delineation tasks (e.g., the image partition into regions, pixel classification, optimum boundary tracking, region growing from internal and external seeds, an image-graph cut, etc). Humans and object models, such as a probabilistic atlas  or an active shape model  , are better for object recognition than computers, but the other way around is true for object delineation. For instance, humans can easily select a point inside the object, but they have difficulties in manual tracing the same boundary several times. In this sense, the most effective approaches are interactive, because they combine the best model for object recognition (the user expert) with the best model for object delineation (some good algorithm). This also makes important the combination of object models for recognition with delineation algorithms for automatic segmentation BIB010 BIB014 BIB025 . Note that, in this scenario, graph-based methods present different graph representations, where the nodes may be pixels BIB004 BIB027 BIB026 BIB019 BIB020 BIB022 BIB024 BIB008 , pixel vertices BIB005 BIB007 , regions BIB015 , or even user-drawn markers BIB028 . They also differ in the graph algorithm used to solve the problem: graph matching BIB028 , random walker BIB016 , the min-cut/max-flow algorithm BIB001  BIB011 BIB023 BIB008 , Dijkstra's algorithm BIB004 BIB005 BIB007 BIB012 BIB026 BIB019 BIB020 , 2], Kruskal's or Prim's algorithm BIB013 BIB006 BIB017 BIB018 , etc. Note also that, a same graph-search algorithm (e.g., Dijkstra's algorithm) can be used for region-based and boundary-based segmentation, besides other image operators BIB012 . Therefore, the best way to differ graphbased segmentation methods is by taking into account the graph model and algorithm that they use to solve the segmentation problem. Besides, there are several other approaches in the literature BIB009 BIB021 BIB002 , which were not presented as graph-based approaches, but they use similar concepts and can be more efficiently and/or effectively implemented as a graph-based approach   . Image segmentation produces a set of homogeneous regions of an image such that all pixels of a region are desired to be connected. The integration of all these regions constitutes the entire image. Each region has a set of pixels and each pixel is characterized by its position and feature vector. All pixels of a region are similar with respect to a set of features. The basic principle of most of the graph based segmentation methods is graph partitioning. Each method treats an image as a graph G in which vertices are composed of pixels. Each edge has a weight generally determined based on the vertices it relates. In graph theory sense, the above segmentation concept is similar to finding a set of sub-graphs Figure 1 . The graph partitioning to achieve image segmentation is a challenging problem due to the following questions BIB003 : 1. What is the precise criterion for a good partition? 2. How can such a partition be computed efficiently? Due to the subjective nature, defining a good partitioning in segmentation still remains in debate. Assuming this is done, determining a criterion that optimally does this is challenging. Methods that use graphs for image segmentation have been widely investigated within the fields of image processing and image understanding. In these methods, segmentation problems by analogy are translated into graph based problems and that are solved as the graph partitioning problem. These graph based segmentation methods might be grouped as (1) graph cut based methods, (2) interactive methods, (3) minimum spanning tree based methods and (4) pyramid based methods. The review is organized into eight sections. Section 1, being this introduction describing the graph based approach of segmentation problem. Sections 2 to 5 respectively reviews exhaustively the four classes of methods, namely, graph cut based methods, interactive methods, minimum spanning tree based methods and pyramid based methods. Graph based methods not belonging to the above four categories are briefly reviewed in Section 6. The need for creating a database of images and its ground truth for benchmarking an algorithm in intensity based segmentation research is highlighted in Section 7, and finally the paper is concluded in Section 8 highlighting the major outcome of the review and suggestions for future direction of research.