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
2282030987 2048593433 2115284428 2472480899
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. 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 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. In this paper, we present a real-time salient object detection system based on the minimum spanning tree. Due to the fact that background regions are typically connected to the image boundaries, salient objects can be extracted by computing the distances to the boundaries. However, measuring the image boundary connectivity efficiently is a challenging problem. Existing methods either rely on superpixel representation to reduce the processing units or approximate the distance transform. Instead, we propose an exact and iteration free solution on a minimum spanning tree. The minimum spanning tree representation of an image inherently reveals the object geometry information in a scene. Meanwhile, it largely reduces the search space of shortest paths, resulting an efficient and high quality distance transform algorithm. We further introduce a boundary dissimilarity measure to compliment the shortage of distance transform for salient object detection. Extensive evaluations show that the proposed algorithm achieves the leading performance compared to the state-of-the-art methods in terms of efficiency and accuracy.