A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> Abstract : A technique for recognizing systems of lines is presented, in which the heuristic of the problem is not embedded in the recognition algorithm but is expressed in a figure of merit. A multistage decision process is then able to recognize in the input picture the optimal system of lines according to the given figure of merit. Due to the global approach, greater flexibility and adequacy in the particular problem is achieved. The relation between the structure of the figure of merit and the complexity of the optimization process is then discussed. (Modified author abstract) <s> BIB001 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> This paper presents a method for detecting edges in a digitized picture. The problem of edge detection is reduced to the problem of finding an optimal path in a weighted graph. The properties of the edge are embedded in the structure of the graph. Graph searching techniques are then used to find the optimal solution. Usually, the optimality of the solution is not important, and several heuristics can be introduced to reduce the search. Because of the global approach, this method, has great flexibility. Some experimental results are given, which show the performance of this method with noisy pictures. <s> BIB002 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> This paper presents a method for detecting edges and contours in noisy pictures. The properties of an edge are embedded in a figure of merit and the edge detection problem becomes the problem of minimizing the given figure of merit. This problem can be represented as a shortest path problem on a graph and can be solved using well-known graph search algorithms. The relations between this representation of the minimization problem and a dynamic programming approach are discussed, showing that the graph search method can lead to substantial improvements in computing time. Moreover, if heuristic search methods are used, the computing time will depend on the amount of noise in the picture. Some experimental results are given; these show how various information about the shape of the contour of an object can be embedded in the figure of merit, thus allowing the extraction of contours from noisy pictures and the separation of touching objects. <s> BIB003 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> Visual estimation of coronary obstruction severity from angiograms suffers from poor inter- and intraobserver reproducibility and is often inaccurate. In spite of the widely recognized limitations of visual analysis, automated methods have not found widespread clinical use, in part because they too frequently fail to accurately identify vessel borders. The authors have developed a robust method for simultaneous detection of left and right coronary borders that is suitable for analysis of complex images with poor contrast, nearby or overlapping structures, or branching vessels. The reliability of the simultaneous border detection method and that of the authors' previously reported conventional border detection method were tested in 130 complex images, selected because conventional automated border detection might be expected to fail. Conventional analysis failed to yield acceptable borders in 65/130 or 50% of images. Simultaneous border detection was much more robust (p<.001) and failed in only 15/130 or 12% of complex images. Simultaneous border detection identified stenosis diameters that correlated significantly better with observer-derived stenosis diameters than did diameters obtained with conventional border detection (p<0.001), Simultaneous detection of left and right coronary borders is highly robust and has substantial promise for enhancing the utility of quantitative coronary angiography in the clinical setting. <s> BIB004 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <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 1,000s of images in a variety of applications. In the previous framework, a fuzzy connected object is defined with a threshold on the strength of connectedness. We introduce the notion of relative connectedness that overcomes the need for a threshold and that leads to more effective segmentations. The central idea is that an object gets defined in an image because of the presence of other co-objects. Each object is initialized by a seed element. An image element c is considered to belong to that object with respect to whose reference image element c has the highest strength of connectedness. In this fashion, objects compete among each other utilizing fuzzy connectedness to grab membership of image elements. We present a theoretical and algorithmic framework for defining objects via relative connectedness and demonstrate utilizing the theory that the objects defined are independent of reference elements chosen as long as they are not in the fuzzy boundary between objects. An iterative strategy is also introduced wherein the strongest relative connected core parts are first defined and iteratively relaxed to conservatively capture the more fuzzy parts subsequently. Examples from medical imaging are presented to illustrate visually the effectiveness of relative fuzzy connectedness. A quantitative mathematical phantom study involving 160 images is conducted to demonstrate objectively the effectiveness of relative fuzzy connectedness. Disclaimer A claim of priority in research and publication appeared on page 1486 in the paper "Relative Fuzzy Connectedness and Object Definition: Theory, Algorithms, and Applications in Image Segmentation" by J.K. Udupa, P.K. Saha, and' R.A. Lotufo (IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 11, pp. 1485-1500,Nov. 2002) with respect to the paper "Multiseeded Segmentation Using Fuzzy Connectedness by G.T. Herman and B.M. Carvalho" (IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 5, pp. 460-474, May 2001). Furthermore, the wording of this claim suggests professional misconduct on the part of G.T. Herman and B.M. Carvalho. Responsibility for the content of published papers rests with the authors. The peer review process is intended to determine the overall significance of the technical contribution of a manuscript. The peer review process does not provide a way to validate every statement in a manuscript. In particular, the IEEE has not validated the claim referred to in the first paragraph above. The IEEE regrets publishing this unauthenticated statement and the pain that such publication may have caused to G.T. Herman and B.M. Carvalho. <s> BIB005 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <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> BIB006 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> In this paper we develop a segmentation scheme for digital images based upon an iterative binary coloring technique that takes into account changing behavior of adjacent pixels. The output is a hierarchical structure of images which allows a better understanding of complex images. In particular, we propose two algorithms that should be considered as image preprocessing techniques. <s> BIB007 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> We propose an extended graph-shifts algorithm for image segmentation and labeling. This algorithm performs energy minimization by manipulating a dynamic hierarchical representation of the image. It consists of a set of moves occurring at different levels of the hierarchy where the types of move, and the level of the hierarchy, are chosen automatically so as to maximally decrease the energy. Extended graph-shifts can be applied to a broad range of problems in medical imaging. In this paper, we apply extended graph-shifts to the detection of pathological brain structures: (i) segmentation of brain tumors, and (ii) detection of multiple sclerosis lesions. The energy terms in these tasks are learned from training data by statistical learning algorithms. We demonstrate accurate results, precision and recall in the order of 93%, and also show that the algorithm is computationally efficient, segmenting a full 3D volume in about one minute. <s> BIB008 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> In this work, we extend a common framework for seeded image segmentation that includes the graph cuts, random walker, and shortest path optimization algorithms. Viewing an image as a weighted graph, these algorithms can be expressed by means of a common energy function with differing choices of a parameter q acting as an exponent on the differences between neighboring nodes. Introducing a new parameter p that fixes a power for the edge weights allows us to also include the optimal spanning forest algorithm for watersheds in this same framework. We then propose a new family of segmentation algorithms that fixes p to produce an optimal spanning forest but varies the power q beyond the usual watershed algorithm, which we term power watersheds. Placing the watershed algorithm in this energy minimization framework also opens new possibilities for using unary terms in traditional watershed segmentation and using watersheds to optimize more general models of use in application beyond image segmentation. <s> BIB009 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> Accurate skin lesion segmentation is critical for automated early skin cancer detection and diagnosis. In this paper, we present a novel multi-modal skin lesion segmentation method based on region fusion and narrow band energy graph partitioning. The proposed method can handle challenging characteristics of skin lesions, such as topological changes, weak or false edges, and asymmetry. Extensive testing demonstrated that in this method complex contours are detected correctly while topological changes of evolving curves are managed naturally. The accuracy of the method was quantified using a lesion similarity measure and lesion segmentation error ratio, Our results were validated using a large set of epiluminescence microscopy (ELM) images acquired using cross-polarization ELM and side-transillumination ELM. Our findings demonstrate that the new method can achieve improved robustness and better overall performance compared to other state-of-the-art segmentation methods. <s> BIB010 </s> A Review on Graph Based Segmentation <s> VI. OTHER METHODS <s> We propose a framework of graph-based tools for the segmentation of microscopic cellular images. This framework is based on an object oriented analysis of imaging problems in pathology. Our graph tools rely on a general formulation of discrete functional regularization on weighted graphs of arbitrary topology. It leads to a set of useful tools which can be combined together to address various image segmentation problems in pathology. To provide fast image segmentation algorithms, we also propose an image simplification based on graphs as a pre processing step. The abilities of this set of image processing discrete tools are illustrated through automatic and interactive segmentation schemes for color cytological and histological images segmentation problems. <s> BIB011
There are many other methods which do not belong to any of the above categories of the graph based methods. Methods based on graph-searching principles BIB001 BIB002 BIB003  are notable of this kind. A few methods were proposed for image segmentation based on graph shortest path algorithms BIB004 BIB005 BIB006 . It was shown that shortest paths, random walker, and watershed were all actually the same algorithm with different norms BIB009 . The work of Gomez et al. BIB007 utilized an iterative binary coloring technique, which considers the changing behavior of adjacent pixels, for image segmentation. Granularity of the output of this method mainly depends on number of iterations: a few iterations might develop a wrong segmentation, while too much iteration might yield useless results. Corso et al. BIB008 proposed an extended graph-shift algorithm, which is a hierarchical energy minimization algorithm, for segmenting brain tumors and multiple sclerosis lesions in MRI. Yuan et al. BIB010 proposed a multi-modal segmentation method based on region fusion and narrow band energy graph partitioning. Ta et al. BIB011 utilized a framework of graph-based tools for microscopic image segmentation.