In this work, a hierarchical graph partitioning based on optimum cuts in graphs is proposed for unsupervised image segmentation, that can be tailored to the target group of objects, according to their boundary polarity, by extending Oriented Image Foresting Transform (OIFT). The proposed method, named UOIFT, theoretically encompasses as a particular case the single-linkage algorithm by minimum spanning tree (MST) and gives superior segmentation results compared to other approaches commonly used in the literature, usually requiring a lower number of image partitions to accurately isolate the desired regions of interest with known polarity. The method is supported by new theoretical results involving the usage of non-monotonic-incremental cost functions in directed graphs and exploits the local contrast of image regions, being robust in relation to illumination variations and inhomogeneity effects. UOIFT is demonstrated using a region adjacency graph of superpixels in medical and natural images.

Evaluating medical imaging segmentation is a very complex problem. Several papers proposed methodologies and different metrics pursuing more reliable and unbiased procedures. In this paper, we propose a novel accuracy metric which is more balanced than the well known Dice and Jaccard coefficients. We also prove mathematically that the proposed metric generalizes Dice, Jaccard and the previously proposed Balanced Dice and Balanced Jaccard coefficients. Our experiments show that significant changes in brain tissue segmentation evaluation results are noticed as we applied our new metric.

In this work, we propose a hybrid method for seeded image segmentation, named Relaxed OIFT, which extends a method by Malmberg et al. to directed graphs, to properly incorporate the boundary polarity constraint. Relaxed OIFT, lies between the pure Oriented Image Foresting Transform (OIFT) at one end and the extension of Random Walks (RW) to directed graphs as proposed by Singaraju et al. Relaxed OIFT is evaluated in MR and CT medical images, producing more intuitively correct segmentation results than both OIFT and RW, and being easy to be extended to multi-dimensional images.

Superpixel segmentation has emerged as an important research problem in the areas of image processing and computer vision. In this paper, we propose a framework, namely Iterative Spanning Forest (ISF), in which improved sets of connected superpixels (supervoxels in 3D) can be generated by a sequence of image foresting transforms. In this framework, one can choose the most suitable combination of ISF components for a given application-i.e., 1) a seed sampling strategy; 2) a connectivity function; 3) an adjacency relation; and 4) a seed pixel recomputation procedure. The superpixels in ISF structurally correspond to spanning trees rooted at those seeds. We present five ISF-based methods to illustrate different choices for those components. These methods are compared with a number of state-of-the-art approaches with respect to effectiveness and efficiency. Experiments are carried out on several datasets containing 2D and 3D objects with distinct texture and shape properties, including a high-level application, named sky image segmentation. The theoretical properties of ISF are demonstrated in the supplementary material and the results show ISF-based methods rank consistently among the best for all datasets.

Many papers are published every year containing new methodologies for brain tissue segmentation in magnetic resonance images. The evaluation of these methods is fundamental to understand their behavior and to observe their weak and strong points. Even though improvements have been proposed, the analysis of the segmentation results can still lead to incorrect conclusions. This paper contains an investigation of the state-of-the-art in brain tissue segmentation evaluation, which includes tissue classification or segmentation, handling partial volume effect, and evaluation metrics. It uncovers previously unnoticed pitfalls and proposes standard procedures to avoid them. Experiments show that the proposed evaluation strategy gives a better insight about the method's strong and weak points.

A new algorithm, named Connected Oriented Image Foresting Transform (COIFT), is proposed, which provides global optimum solutions according to a graph-cut measure, subject to high-level boundary constraints. COIFT incorporates the connectivity constraint in the Oriented Image Foresting Transform (OIFT), ensuring the generation of connected objects, and can also handle simultaneously the boundary polarity. While the connectivity constraint usually leads to NP-hard problems in other frameworks, such as the min-cut/max-flow algorithm, COIFT conserves the low complexity of the OIFT algorithm. Experiments show that COIFT can improve the segmentation of thin and elongated objects, for the same amount of user interaction.

We propose two novel region-based descriptors for shape-based image retrieval and analysis, which are built upon an extended tensor scale based on the Euclidean Distance Transform (EDT). First the tensor scale algorithm is applied to extract local structure thickness, orientation, and anisotropy as represented by the largest ellipse within a homogeneous region centered at each image pixel. In this work, we extend the local orientation to 360°. Then, for the first proposed descriptor, named Tensor Scale Sector descriptor (TSS), the local distributions of relative orientations within circular sectors are used to compose a fixed-length feature vector for a region-based representation. For the second method, named Tensor Scale Band descriptor (TSB), we consider histograms of relative orientations for each circular concentric band to compose a fixed-length feature vector with linear time matching. Experimental results with MPEG-7 and MNIST datasets are presented to illustrate and validate the methods. TSS can achieve high retrieval values comparable to state-of-the-art methods, which usually rely on time-consuming correspondence optimization algorithms, but uses a simpler and faster distance function, while the even faster linear complexity of TSB leads to a suitable and better solution for very large shape collections.

In this work, we propose a novel boundary constraint, which we denote as the Geodesic Band Constraint (GBC), and we show how it can be efficiently incorporated into a subclass of the Generalized Graph Cut framework (GGC). We include a proof of the optimality of the new algorithm in terms of a global minimum of an energy function subject to the new boundary constraints. The Geodesic Band Constraint helps regularizing the boundary, and consequently, improves the segmentation of objects with more regular shape, while keeping the low computational cost of the Image Foresting Transform (IFT). It can also be combined with the Geodesic Star Convexity prior, and with polarity constraints, at no additional cost. The method is demonstrated in CT thoracic studies of the liver, and MR images of the breast.

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, regionbased 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.

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). Moreover, 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.

In this work, we discuss how to incorporate Gulshan's geodesic star convexity prior in a region-based approach for interactive image segmentation, called “IFT segmentation by Seed Competition”, which encompasses many popular methods, such as watersheds, and fuzzy connectedness. This convexity constraint eliminates undesirable intricate shapes, improving the segmentation of objects with more regular shape. We include a theoretical proof of the optimality of the new algorithm in terms of a global minimum of an energy function subject to the shape constraints. We also present an experimental evaluation that shows the obtained gains in accuracy for segmenting a variety of medical images, including MR images of the foot, CT thoracic studies of the liver, and MR images of the breast.

In this work, we propose a novel approach for improving center of gravity (COG) estimation of the brain in magnetic resonance (MR) images, that uses 3D Haar-like features. We hypothesize that better pose estimation will advance the posterior skull-stripping results of the popular Brain Extraction Tool (BET). The proposed methodology is quantitatively validated in 20 T1- and T2-weighted images of the brain. As compared to the native BET COG algorithm, our method produced COGs 87.3% closer to the expected coordinates for the T1-weighted dataset, and importantly this resulted in an average enhancement of 15.4% to the accuracy of skull-stripping masks. As far the authors know, we are first in analyzing the impact of COG estimation over skull-stripping of MR images.

We introduce an image segmentation algorithm GCsummax, which combines, in a novel manner, the strengths of two popular algorithms: Relative Fuzzy Connectedness (RFC) and (standard) Graph Cut (GC). We show, both theoretically and experimentally, that GCsummaxpreserves robustness of RFC with respect to the seed choice (thus, avoiding “shrinking problem” of GC), while keeping GC's bigger control over “leaking though the weak boundary.” The theoretical analysis of GCsummaxis greatly facilitated by our recent theoretical results that RFC belongs to the Generalized GC (GGC) segmentation algorithms framework. In our implementation of GCsummaxwe use, as a subroutine, a version of RFC algorithm (based on Image Foresting Transform) that runs (provably) in linear time with respect to the image size. This results in GCsummaxrunning in a time close to linear.

We have developed interactive tools for graph-based segmentation of natural images, in which the user guides object delineation by drawing strokes (markers) inside and outside the object. A suitable arc-weight estimation is paramount to minimize user time and maximize segmentation accuracy in these tools. However, it depends on discriminative image properties for object and background. These properties can be obtained from some marker pixels, but their identification is a hard problem during delineation. Careless arc-weight re-estimation reduces user control and drops performance, while interactive arc-weight estimation in a step before interactive object extraction is the best option so far, albeit it is not intuitive for nonexpert users. We present an effective solution using the unified framework of the image foresting transform (IFT) with three operators: clustering for interpreting user interaction and determining when and where arc weights need to be re-estimated; fuzzy classification for arc-weight estimation; and marker competition based on optimum connectivity for object extraction. For validation, we compared the proposed approach with another interactive IFT-based method, which computes arc weights before extraction. Evaluation involved multiple users (experts and nonexperts), a dataset with several natural images, and measurements to quantify accuracy, precision, efficiency (user time and computation time), and user control, being some of them novel measurements, proposed in this work.

This paper presents an optimum user-steered boundary tracking approach for image segmentation, which simulates the behavior of water flowing through a riverbed. The riverbed approach was devised using the image foresting transform with a never-exploited connectivity function. We analyze its properties in the derived image graphs and discuss its theoretical relation with other popular methods such as live wire and graph cuts. Several experiments show that riverbed can significantly reduce the number of user interactions (anchor points), as compared to live wire for objects with complex shapes. This paper also includes a discussion about how to combine different methods in order to take advantage of their complementary strengths.

This work presents an optimum user-steered boundary tracking approach for image segmentation, which simulates the behavior of water flowing through a riverbed. The riverbed approach was devised using the Image Foresting Transform with a never exploited connectivity function. We analyze its properties in the derived image graphs and discuss its theoretical relation with other popular methods, such as live wire and graph cuts. Riverbed can significantly reduce the number of user interactions (anchor points) as compared to live wire for objects with complex shapes.

Tensor Scale is a morphometric parameter that unifies the representation of local structure thickness, orientation, and anisotropy, which can be used in several image processing tasks. This paper introduces a new application for tensor scale, which is the detection of saliences on a given contour, based on the tensor scale orientations computed for the entire object and mapped to its contour. For validation purposes, we present a shape descriptor that uses the detected contour saliences. Experimental results are provided, comparing the proposed method with our previous Contour Salience Descriptor (CS). We show that the proposed method can be not only faster and more robust in the detection of salience points than the CS method, but also more effective as a shape descriptor.