Riverbed: A Novel User-Steered Image Segmentation Method Based on Optimum Boundary Tracking

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.

Classical segmentation methods on novel MR imaging: a study of brain tissue segmentation of MP2RAGE vs MPRAGE

MP2RAGE has proven to be a bias-free MR acquisition with excellent contrast between grey and white matter. We investigated the ability of three state-of-the-art algorithms to automatically extract white matter (WM), grey matter (GM) and cerebrospinal fluid (CSF) from MPRAGE and MP2RAGE images: unified Segmentation (S) in SPM82 , its extension New Segment (NS), and an in-house Expectation-Maximization Markov Random Field tissue classification3 (EM-MRF) with Graph Cut (GC) optimization4 . Our goal is to quantify the differences between MPRAGE and MP2RAGE-based brain tissue probability maps.

Segmentação de imagens pela transformada imagem-floresta com faixa de restrição geodésica

Vários métodos tradicionais de segmentação de imagens, como a transformada de watershed de marcado- res e métodos de conexidade fuzzy (Relative Fuzzy Connectedness- RFC, Iterative Relative Fuzzy Connected- ness - IRFC), podem ser implementados de modo eficiente utilizando o método em grafos da Transformada Imagem-Floresta (Image Foresting Transform - IFT). No entanto, a carência de termos de regularização de fronteira em sua formulação fazem com que a borda do objeto segmentado possa ser altamente irregular. Um modo de contornar isto é por meio do uso de restrições de forma do objeto, que favoreçam formas mais regulares, como na recente restrição de convexidade geodésica em estrela (Geodesic Star Convexity - GSC). Neste trabalho, apresentamos uma nova restrição de forma, chamada de Faixa de Restrição Geodésica (Geodesic Band Constraint - GBC), que pode ser incorporada eficientemente em uma sub-classe do fra- mework de corte em grafos generalizado (Generalized Graph Cut - GGC), que inclui métodos pela IFT. É apresentada uma prova da otimalidade do novo algoritmo em termos de um mínimo global de uma função de energia sujeita às novas restrições de borda. A faixa de restrição geodésica nos ajuda a regularizar a borda dos objetos, consequentemente melhorando a segmentação de objetos com formas mais regulares, mantendo o baixo custo computacional da IFT. A GBC pode também ser usada conjuntamente com um mapa de custos pré estabelecido, baseado em um modelo de forma, de modo a direcionar a segmentação a seguir uma dada forma desejada, com grau de liberdade de escala e demais deformações controladas por um parâmetro único. Essa nova restrição também pode ser combinada com a GSC e com as restrições de polaridade de borda sem custo adicional. O método é demonstrado em imagens naturais, sintéticas e médicas, sendo estas provenientes de tomografias computadorizadas e de ressonância magnética.

Automatic Abdominal Aortic Aneurysm segmentation in MR images

Abdominal Aortic Aneurism is a disease related to a weakening in the aortic wall that can cause a break in the aorta and the death. The detection of an unusual dilatation of a section of the aorta is an indicative of this disease. However, it is difficult to diagnose because it is necessary image diagnosis using computed tomography or magnetic resonance. An automatic diagnosis system would allow to analyze abdominal magnetic resonance images and to warn doctors if any anomaly is detected. We focus our research in magnetic resonance images because of the absence of ionizing radiation. Although there are proposals to identify this disease in magnetic resonance images, they need an intervention from clinicians to be precise and some of them are computationally hard. In this paper we develop a novel approach to analyze magnetic resonance abdominal images and detect the lumen and the aortic wall. The method combines different algorithms in two stages to improve the detection and the segmentation so it can be applied to similar problems with other type of images or structures. In a first stage, we use a spatial fuzzy C-means algorithm with morphological image analysis to detect and segment the lumen; and subsequently, in a second stage, we apply a graph cut algorithm to segment the aortic wall. The obtained results in the analyzed images are pretty successful obtaining an average of 79% of overlapping between the automatic segmentation provided by our method and the aortic wall identified by a medical specialist. The main impact of the proposed method is that it works in a completely automatic way with a low computational cost, which is of great significance for any expert and intelligent system.

Automatic object segmentation from calibrated images

This paper addresses the problem of automatically obtaining the object/background segmentation of a rigid 3D object observed in a set of images that have been calibrated for camera pose and intrinsics. Such segmentations can be used to obtain a shape representation of a potentially texture-less object by computing a visual hull. We propose an automatic approach where the object to be segmented is identified by the pose of the cameras instead of user input such as 2D bounding rectangles or brush-strokes. The key behind our method is a pairwise MRF framework that combines (a) foreground/background appearance models, (b) epipolar constraints and (c) weak stereo correspondence into a single segmentation cost function that can be efficiently solved by Graph-cuts. The segmentation thus obtained is further improved using silhouette coherency and then used to update the foreground/background appearance models which are fed into the next Graph-cut computation. These two steps are iterated until segmentation convergences. Our method can automatically provide a 3D surface representation even in texture-less scenes where MVS methods might fail. Furthermore, it confers improved performance in images where the object is not readily separable from the background in colour space, an area that previous segmentation approaches have found challenging. © 2011 IEEE.

A hybrid genetic algorithm for the minimum interconnection cut problem

In the real world there are many problems in network of networks (NoNs) that can be abstracted to a so-called minimum interconnection cut problem, which is fundamentally different from those classical minimum cut problems in graph theory. Thus, it is desirable to propose an efficient and effective algorithm for the minimum interconnection cut problem. In this paper we formulate the problem in graph theory, transform it into a multi-objective and multi-constraint combinatorial optimization problem, and propose a hybrid genetic algorithm (HGA) for the problem. The HGA is a penalty-based genetic algorithm (GA) that incorporates an effective heuristic procedure to locally optimize the individuals in the population of the GA. The HGA has been implemented and evaluated by experiments. Experimental results have shown that the HGA is effective and efficient.

Automatic Road Extraction using High Resolution Satellite Image Based on Texture Progressive Analysis and Normalized Cut Method

In this paper the approach for automatic road extraction for an urban region using structural, spectral and geometric characteristics of roads has been presented. Roads have been extracted based on two levels: Pre-processing and road extraction methods. Initially, the image is pre-processed to improve the tolerance by reducing the clutter (that mostly represents the buildings, parking lots, vegetation regions and other open spaces). The road segments are then extracted using Texture Progressive Analysis (TPA) and Normalized cut algorithm. The TPA technique uses binary segmentation based on three levels of texture statistical evaluation to extract road segments where as, Normalizedcut method for road extraction is a graph based method that generates optimal partition of road segments. The performance evaluation (quality measures) for road extraction using TPA and normalized cut method is compared. Thus the experimental result show that normalized cut method is efficient in extracting road segments in urban region from high resolution satellite image.

Multiview stereo via volumetric Graph-Cuts and occlusion robust photo-consistency.

This paper presents a volumetric formulation for the multi-view stereo problem which is amenable to a computationally tractable global optimisation using Graph-cuts. Our approach is to seek the optimal partitioning of 3D space into two regions labelled as "object" and "empty" under a cost functional consisting of the following two terms: (1) A term that forces the boundary between the two regions to pass through photo-consistent locations and (2) a ballooning term that inflates the "object" region. To take account of the effect of occlusion on the first term we use an occlusion robust photo-consistency metric based on Normalised Cross Correlation, which does not assume any geometric knowledge about the reconstructed object. The globally optimal 3D partitioning can be obtained as the minimum cut solution of a weighted graph.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Evaluation of serological tests for the diagnosis of Neospora caninum infection in dogs: Optimization of cut off titers and inhibition studies of cross-reactivity with Toxoplasma gondii

Diagnosis of Neospora caninum infection in dogs is based on serological assays such as the indirect fluorescent antibody test (IFAT) and enzyme-linked immunosorbent assays (ELISA). This study evaluated two serological tests (IFAT and ELISA) for the detection of IgG antibodies to N. caninum in 300 serum samples of dogs through the optimization of cut off titers by using the two-graph receiveroperating characteristic (TG-ROC) curve. In addition, the identification of major cross-reactive antigens with Toxoplasma gondii was investigated by inhibition ELISA and immunoblotting (IB) assays. IFAT and ELISA results showed 74% agreement, with a good negative concordance (P-neg=0.83), but a poor positive concordance (P-pos=0.42). The great majority (86%) of sera with positive concordant results (IFAT+/ELISA+) recognized at least two out of three N. caninum immunodominant antigens, particularly the 29-32 and 35-37 kDa bands. Optimization of cut off titers in IFAT and ELISA was performed considering the reactivity to at least two out of three N. caninum immunodominant antigens as infection markers, obtaining a titer of 50 for IFAT and 200 for ELISA. Seropositivity to N. caninuin was significantly associated with T gondii-seropositive samples, particularly in ELISA (55.4%). Inhibition ELISA curves for N. caninum showed a partial heterologous inhibition, indicating some degree of cross-reactivity between N. caninum and T gondii antigens. Inhibition IB assays showed a moderate heterologous inhibition for N. caninum antigens above 45-50 kDa. These results indicate that ELISA should be used critically when crude tachyzoite antigen preparations are employed, due to possible cross-reactivity with other related parasites as T gondii. Also, the cut off dilution of 1:50 in IFAT showed to be the most appropriated for N. caninum serology in dogs. Therefore, we suggest that N. caninum immunodominant antigens, specially the 17 and 29-32 kDa proteins, should be selected markers in serological assays for canine neosporosis. (c) 2006 Elsevier B.V. All rights reserved.

Image segmentation through combined methods: watershed transform, unsupervised distance learning and normalized cut

Research on image processing has shown that combining segmentation methods may lead to a solid approach to extract semantic information from different sort of images. Within this context, the Normalized Cut (NCut) is usually used as a final partitioning tool for graphs modeled in some chosen method. This work explores the Watershed Transform as a modeling tool, using different criteria of the hierarchical Watershed to convert an image into an adjacency graph. The Watershed is combined with an unsupervised distance learning step that redistributes the graph weights and redefines the Similarity matrix, before the final segmentation step using NCut. Adopting the Berkeley Segmentation Data Set and Benchmark as a background, our goal is to compare the results obtained for this method with previous work to validate its performance.

A genetic algorithm for the multi-source and multi-sink minimum vertex cut problem and its applications

We present a new penalty-based genetic algorithm for the multi-source and multi-sink minimum vertex cut problem, and illustrate the algorithm’s usefulness with two real-world applications. It is proved in this paper that the genetic algorithm always produces a feasible solution by exploiting some domain-specific knowledge. The genetic algorithm has been implemented on the example applications and evaluated to show how well it scales as the problem size increases.

Multi-vehicles interaction graph model for cooperative collision warning system

Cooperative collision warning system for road vehicles, enabled by recent advances in positioning systems and wireless communication technologies, can potentially reduce traffic accident significantly. To improve the system, we propose a graph model to represent interactions between multiple road vehicles in a specific region and at a specific time. Given a list of vehicles in vicinity, we can generate the interaction graph using several rules that consider vehicle's properties such as position, speed, heading, etc. Safety applications can use the model to improve emergency warning accuracy and optimize wireless channel usage. The model allows us to develop some congestion control strategies for an efficient multi-hop broadcast protocol.

Accurate silhouette segmentation using motion detection and graph cuts

Acquiring accurate silhouettes has many applications in computer vision. This is usually done through motion detection, or a simple background subtraction under highly controlled environments (i.e. chroma-key backgrounds). Lighting and contrast issues in typical outdoor or office environments make accurate segmentation very difficult in these scenes. In this paper, gradients are used in conjunction with intensity and colour to provide a robust segmentation of motion, after which graph cuts are utilised to refine the segmentation. The results presented using the ETISEO database demonstrate that an improved segmentation is achieved through the combined use of motion detection and graph cuts, particularly in complex scenes.