Superpixel segmentation has become an important research problem in image processing. In this paper, we propose an Iterative Spanning Forest (ISF) framework, based on sequences of Image Foresting Transforms, where one can choose i) a seed sampling strategy, ii) a connectivity function, iii) an adjacency relation, and iv) a seed pixel recomputation procedure to generate improved sets of connected superpixels (supervoxels in 3D) per iteration. The superpixels in ISF structurally correspond to spanning trees rooted at those seeds. We present five ISF methods to illustrate different choices of its components. These methods are compared with approaches from the state-of-the-art in effectiveness and efficiency. The experiments involve 2D and 3D datasets with distinct characteristics, and a high level application, named sky image segmentation. The theoretical properties of ISF are demonstrated in the supplementary material and the results show that some of its methods are competitive with or superior to the best baselines in effectiveness and efficiency.
ISF falls in the category of graph-based algorithms as a particular case of a more general framework @cite_23 --- the Image Foresting Transform (IFT). The IFT is a framework for the design of image operators based on connectivity, such as distance and geodesic transforms, morphological reconstructions, multiscale skeletonization, image description, region- and boundary-based image segmentation methods @cite_35 @cite_54 @cite_26 @cite_41 @cite_47 @cite_44 @cite_53 @cite_45 @cite_22 , with extensions to clustering and classification @cite_30 @cite_13 @cite_27 @cite_36 @cite_37 . As discussed in @cite_42 , by choice of the connectivity function, the IFT algorithm computes a watershed transform from a set of seeds that corresponds to a graph cut in which the minimum gradient value in the cut is maximized. From @cite_29 , it is known that the watershed transform from seeds is equivalent to a cut in a minimum-spanning tree (MST). That is, the removal of the arc with maximum weight from the single path in the MST that connects each pair of seeds results a minimum-spanning forest (i.e., a watershed cut). Such a graph cut tends to be better than the normalized cut in boundary adherence, but worse in superpixel regularity.
@cite_30 @cite_35 @cite_37 @cite_26 @cite_22 @cite_41 @cite_36 @cite_54 @cite_53 @cite_42 @cite_29 @cite_44 @cite_27 @cite_45 @cite_23 @cite_47 @cite_13
2160879691 2048593433 2605891472 2120078253 2398616336 2282030987 1968974811 2128000934 2028174169 2622333333 2115284428 1979548221 2512089339
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. In the framework of the Image Foresting Transform (IFT), there is a class of connectivity functions that were vaguely explored, which corresponds to the non-smooth connectivity functions (NSCF). These functions are more adaptive to cope with the problems of field in homogeneity, which are common in MR images of 3 Tesla. In this work, we investigate the NSCF from the standpoint of theoretical and experimental aspects. We formally classify several non-smooth functions according to a proposed diagram representation. Then, we investigate some theoretical properties for some specific regions of the diagram. Our analysis reveals that many NSCFs are, in fact, the result of a sequence of optimizations, each of them involving a maximal set of elements, in a well-structured way. Our experimental results indicate that substantial improvements can be obtained by NSCFs in the 3D segmentation of MR images of 3 Tesla, when compared to smooth connectivity functions. The foolproof segmentation of 3D anatomical structures in medical images is usually a challenging task, which makes automatic results often far from desirable and interactive repairs necessary. In the past, we introduced a first solution to resume segmentation from third-party software into an initial optimum-path forest for interactive correction by differential image foresting transforms (DIFTs). Here, we present a new method that estimates the initial forest (input segmentation) rooted at more regularly separated seed voxels to facilitate interactive editing. The forest is a supervoxel segmentation from seeds that result from a sequence of image foresting transforms to conform as much as possible the supervoxel boundaries to the boundaries of the object in the input segmentation. We demonstrate the advantages of the new method over the previous one by using a robot user, as an impartial way to correct brain segmentation in MR-T1 images. Abstract This paper presents two shape descriptors, multiscale fractal dimension and contour saliences, using a graph-based approach— the image foresting transform. It introduces a robust approach to locate contour saliences from the relation between contour and skeleton. The contour salience descriptor consists of a vector, with salience location and value along the contour, and a matching algorithm. We compare both descriptors with fractal dimension, Fourier descriptors, moment invariants, Curvature Scale Space and Beam Angle Statistics regarding to their invariance to object characteristics that belong to a same class (compact-ability) and to their ability to separate objects of distinct classes (separability). The annotation of large data sets by a classifier is a problem whose challenge increases as the number of labeled samples used to train the classifier reduces in comparison to the number of unlabeled samples. In this context, semi-supervised learning methods aim at discovering and labeling informative samples among the unlabeled ones, such that their addition to the correct class in the training set can improve classification performance. We present a semi-supervised learning approach that connects unlabeled and labeled samples as nodes of a minimum-spanning tree and partitions the tree into an optimum-path forest rooted at the labeled nodes. It is suitable when most samples from a same class are more closely connected through sequences of nearby samples than samples from distinct classes, which is usually the case in data sets with a reasonable relation between number of samples and feature space dimension. The proposed solution is validated by using several data sets and state-of-the-art methods as baselines. HighlightsA new algorithm for semi-supervised learning based on optimum-path forest.The algorithm provides significant improvements in accuracy and efficiency.Labels are propagated from labeled to unlabeled training samples with less errors.The novel classifier can be more accurate than other state-of-the-art methods.A fast and effective algorithm suitable for developing active learning methods. This work reviews the watershed in the graph framework of a shortest-path forest problem using a lexicographic path cost formulation. This formulation reflects the behavior of the ordered queue-based watershed algorithm. This algorithm is compared with our proposed shortest-path forest (IFT-Image Foresting Transform), concluding that the watershed is a special case of that. Recently many different watershed approaches are being used. We point out that in some cases the watershed algorithm does not keep the optimality of the shortest-path forest solution unless the IFT algorithm is used. The main difference between the algorithms is related to permanently labeling a pixel when inserting or removing it from the queue. The watershed based on the pixel dissimilarity using IFT can segment one-pixel width regions while keeping the optimality of the shortest-path forest solution. 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. We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: they can be equivalently defined by their "catchment basinsrdquo (through a steepest descent property) or by the "dividing linesrdquo separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations. Interactive image segmentation methods normally rely on cues about the foreground imposed by the user as region constraints (markers brush strokes) or boundary constraints (anchor points). These paradigms often have complementary strengths and weaknesses, which can be addressed to improve the interactive experience by reducing the user's effort. We propose a novel hybrid paradigm based on a new form of interaction called live markers, where optimum boundary-tracking segments are turned into internal and external markers for region-based delineation to effectively extract the object. We present four techniques within this paradigm: 1) LiveMarkers; 2) RiverCut; 3) LiveCut; and 4) RiverMarkers. The homonym LiveMarkers couples boundary-tracking via live-wire-on-the-fly (LWOF) with optimum seed competition by the image foresting transform (IFT-SC). The IFT-SC can cope with complex object silhouettes, but presents a leaking problem on weaker parts of the boundary that is solved by the effective live markers produced by LWOF. Conversely, in RiverCut, the long boundary segments computed by Riverbed around complex shapes provide markers for Graph Cuts by the Min-Cut Max-Flow algorithm (GCMF) to complete segmentation on poorly defined sections of the object's border. LiveCut and RiverMarkers further demonstrate that live markers can improve segmentation even when the combined approaches are not complementary (e.g., GCMFs shrinking bias is also dramatically prevented when using it with LWOF). More- over, since delineation is always region based, our methodology subsumes both paradigms, representing a new way of extending boundary tracking to the 3D image domain, while speeding up the addition of markers close to the object's boundary— a necessary but time consuming task when done manually. We justify our claims through an extensive experimental evaluation on natural and medical images data sets, using recently proposed robot users for boundary-tracking methods. Abstract Skeletons are simplified shape representations with many applications involving image processing, analysis, and visualization. A fundamental problem in shape skeletonization is the sensitivity of the skeletons to small perturbations of the input shape, which leads to the appearance of spurious branches. By assigning an importance metric to every skeleton point, one encodes the scale of the shape details. Subsequently, simplified skeletons can be obtained by simply thresholding at continuous values of that metric. Such a multiscale regularization procedure should ideally produce one-spel-wide skeletons in all scales. In this chapter, we present a new method based on the image foresting transform framework, which achieves this result for medial axes of 2D shapes and for surface skeletons of 3D shapes. Our approach relies on simple and efficient algorithms, faster than several methods based on the same importance metric, simpler than others, far less sensitive to numerical noise than a recent one, and attains similar quality of centeredness, smoothness, thinness, and ease to simplify the skeleton. Such a conclusion is substantiated with a comparative analysis on a wide set of 2D and 3D real-word shapes against its multiscale counterparts. 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. Seed-based methods for region-based image segmentation are known to provide satisfactory results for several applications, being usually easy to extend to multidimensional images. However, while boundary-based methods like live wire can easily incorporate a preferred boundary orientation, region-based methods are usually conceived for undirected graphs, and do not resolve well between boundaries with opposite orientations. This motivated researchers to investigate extensions for some region-based frameworks, seeking to better solve oriented transitions. In this same spirit, we discuss how to incorporate this orientation information in a region-based approach called “IFT segmentation by seed competition” by exploring digraphs. We give direct proof for the optimality of the proposed extensions in terms of energy functions associated with the cuts. To stress these theoretical results, we also present an experimental evaluation that shows the obtained gains in accuracy for some 2D and 3D data sets of medical images. A deeper theoretical background about the Optimum-Path Forest (OPF) classifier with k-neighborhood (OPFk) is presented.A new, faster and less prone to error training step is also proposed.A faster classification algorithm for the OPFk classifier is presented.An extensive experimental evaluation is conducted.New insights about future research concerning OPFk are also discussed. Display Omitted Graph-based pattern recognition techniques have been in the spotlight for many years, since there is a constant need for faster and more effective approaches. Among them, the Optimum-Path Forest (OPF) framework has gained considerable attention in the last years, mainly due to the promising results obtained by OPF-based classifiers, which range from unsupervised, semi-supervised and supervised learning. In this paper, we consider a deeper theoretical explanation concerning the supervised OPF classifier with k-neighborhood (OPFk), as well as we proposed two different training and classification algorithms that allow OPFk to work faster. The experimental validation against standard OPF and Support Vector Machines also validates the robustness of OPFk in real and synthetic datasets.