The Experts below are selected from a list of 11403 Experts worldwide ranked by ideXlab platform
Ramin Zabih - One of the best experts on this subject based on the ideXlab platform.
-
segmentation of liver tumor using efficient global optimal tree metrics Graph Cuts
Abdominal Imaging, 2011Co-Authors: Ruogu Fang, Ramin Zabih, Ashish Raj, Tsuhan ChenAbstract:We propose a novel approach that applies global optimal tree-metrics Graph Cuts algorithm on multi-phase contrast enhanced contrast enhanced MRI for liver tumor segmentation. To address the difficulties caused by low contrasted boundaries and high variability in liver tumor segmentation, we first extract a set of features in multi-phase contrast enhanced MRI data and use color-space mapping to reveal spatial-temporal information invisible in MRI intensity images. Then we apply efficient tree-metrics Graph cut algorithm on multi-phase contrast enhanced MRI data to obtain global optimal labeling in an unsupervised framework. Finally we use tree-pruning method to reduce the number of available labels for liver tumor segmentation. Experiments on real-world clinical data show encouraging results. This approach can be applied to various medical imaging modalities and organs.
-
spatially coherent clustering using Graph Cuts
Computer Vision and Pattern Recognition, 2004Co-Authors: Ramin Zabih, Vladimir KolmogorovAbstract:Feature space clustering is a popular approach to image segmentation, in which a feature vector of local properties (such as intensity, texture or motion) is computed at each pixel. The feature space is then clustered, and each pixel is labeled with the cluster that contains its feature vector. A major limitation of this approach is that feature space clusters generally lack spatial coherence (i.e., they do not correspond to a compact grouping of pixels). In this paper, we propose a segmentation algorithm that operates simultaneously in feature space and in image space. We define an energy function over both a set of clusters and a labeling of pixels with clusters. In our framework, a pixel is labeled with a single cluster (rather than, for example, a distribution over clusters). Our energy function penalizes clusters that are a poor fit to the data in feature space, and also penalizes clusters whose pixels lack spatial coherence. The energy function can be efficiently minimized using Graph Cuts. Our algorithm can incorporate both parametric and non-parametric clustering methods. It can be applied to many optimization-based clustering methods, including k-means and k-medians, and can handle models, which are very close in feature space. Preliminary results are presented on segmenting real and synthetic images, using both parametric and non-parametric clustering.
-
What Energy Functions Can Be Minimized via Graph Cuts?
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004Co-Authors: Vladimir Kolmogorov, Ramin ZabihAbstract:In the last few years, several new algorithms based on Graph Cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a Graph such that the minimum cut on the Graph also minimizes the energy. Yet, because these Graph constructions are complex and highly specific to a particular energy function, Graph Cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by Graph Cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using Graph Cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by Graph Cuts. Researchers who are considering the use of Graph Cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate Graph. A software implementation is freely available.
-
what energy functions can be minimized via Graph Cuts
European Conference on Computer Vision, 2002Co-Authors: Vladimir Kolmogorov, Ramin ZabihAbstract:In the last few years, several new algorithms based on Graph Cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a Graph such that the minimum cut on the Graph also minimizes the energy. Yet because these Graph constructions are complex and highly specific to a particular energy function, Graph Cuts have seen limited application to date. In this paper we characterize the energy functions that can be minimized by Graph Cuts. Our results are restricted to energy functions with binary variables. However, our work generalizes many previous constructions, and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration and scene reconstruction. We present three main results: a necessary condition for any energy function that can be minimized by Graph Cuts; a sufficient condition for energy functions that can be written as a sum of functions of up to three variables at a time; and a general-purpose construction to minimize such an energy function. Researchers who are considering the use of Graph Cuts to optimize a particular energy function can use our results to determine if this is possible, and then follow our construction to create the appropriate Graph.
-
Multi-camera Scene Reconstruction via Graph Cuts
European Conference on Computer Vision (ECCV), 2002Co-Authors: Vladimir Kolmogorov, Ramin ZabihAbstract:We address the problem of computing the 3-dimensional shape of an arbitrary scene from a set of images taken at known view- points. Multi-camera scene reconstruction is a natural generalization of the stereo matching problem. However, it is much more difficult than stereo, primarily due to the difficulty of reasoning about visibility. In this paper, we take an approach that has yielded excellent results for stereo, namely energy minimization via Graph Cuts. We first give an en- ergy minimization formulation of the multi-camera scene reconstruction problem. The energy that we minimize treats the input images symmet- rically, handles visibility properly, and imposes spatial smoothness while preserving discontinuities. As the energy function is NP-hard tominimize exactly, we give a Graph cut algorithm that computes a local minimum in a strong sense. We handle all camera configurations where voxel col- oring can be used, which is a large and natural class. Experimental data demonstrates the effectiveness of our approach.
Yuri Boykov - One of the best experts on this subject based on the ideXlab platform.
-
active Graph Cuts
Computer Vision and Pattern Recognition, 2006Co-Authors: O Juan, Yuri BoykovAbstract:This paper adds a number of novel concepts into global s/t cut methods improving their efficiency and making them relevant for a wider class of applications in vision where algorithms should ideally run in real-time. Our new Active Cuts (AC) method can effectively use a good approximate solution (initial cut) that is often available in dynamic, hierarchical, and multi-label optimization problems in vision. In many problems AC works faster than the state-of-the-art max-flow methods [2] even if initial cut is far from the optimal one. Moreover, empirical speed improves several folds when initial cut is spatially close to the optima. Before converging to a global minima, Active Cuts outputs a multitude of intermediate solutions (intermediate Cuts) that, for example, can be used be accelerate iterative learning-based methods or to improve visual perception of Graph Cuts realtime performance when large volumetric data is segmented. Finally, it can also be combined with many previous methods for accelerating Graph Cuts.
-
automatic heart isolation for ct coronary visualization using Graph Cuts
International Symposium on Biomedical Imaging, 2006Co-Authors: Gareth Funkalea, Yuri Boykov, Charles Florin, Mariepierre Jolly, Romain Moreaugobard, Ramamani Ramaraj, D RinckAbstract:We describe a means to automatically and efficiently isolate the outer surface of the entire heart in computer tomoGraphy (CT) cardiac scans. Isolating the entire heart allows the coronary vessels on the surface of the heart to be easily visualized despite the proximity of surrounding organs such as the ribs and pulmonary blood vessels. Numerous techniques have been described for segmenting the left ventricle of the heart in images from various types of medical scanners but rarely has the entire heart been segmented. We make use of Graph-Cuts to do the segmentation and introduce a novel means of initiating and constraining the Graph-cut technique for heart isolation. The technique has been tested on 70 patient data sets. Results are compares with hand labeled results.
-
Graph Cuts and efficient N-D image segmentation
International Journal of Computer Vision, 2006Co-Authors: Yuri Boykov, Gareth Funka-leaAbstract:Combinatorial Graph cut algorithms have been successfully applied to a wide range of problems in\nvision and Graphics. This paper focusses on possibly the simplest application of Graph-Cuts: segmentation of objects\nin image data. Despite its simplicity, this application epitomizes the best features of combinatorial Graph Cuts\nmethods in vision: global optima, practical efficiency, numerical robustness, ability to fuse a wide range of visual\ncues and constraints, unrestricted topological properties of segments, and applicability to N-D problems. Graph\nCuts based approaches to object extraction have also been shown to have interesting connections with earlier\nsegmentation methods such as snakes, geodesic active contours, and level-sets. The segmentation energies optimized\nby Graph Cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah\nstyle functionals. We present motivation and detailed technical description of the basic combinatorial optimization\nframework for image segmentation via s/t Graph Cuts. After the general concept of using binary Graph cut algorithms\nfor object segmentation was first proposed and tested in Boykov and Jolly (2001), this idea was widely studied\nin computer vision and Graphics communities. We provide links to a large number of known extensions based\non iterative parameter re-estimation and learning, multi-scale or hierarchical approaches, narrow bands, and other\ntechniques for demanding photo, video, and medical applications.
-
Graph Cuts in vision and Graphics theories and applications
Handbook of Mathematical Models in Computer Vision, 2006Co-Authors: Yuri Boykov, Olga VekslerAbstract:Combinatorial min-cut algorithms on Graphs have emerged as an increaseingly useful tool for problems in vision. Typically, the use of Graph-Cuts is motivated by one of the following two reasons. Firstly, Graph-Cuts allow geometric interpretation; under certain conditions a cut on a Graph can be seen as a hypersurface in N-D space embedding the corresponding Graph. Thus, many applications in vision and Graphics use min-cut algorithms as a tool for computing optimal hypersurfaces. Secondly, Graph-Cuts also work as a powerful energy minimization tool for a fairly wide class of binary and nonbinary energies that frequently occur in early vision. In some cases Graph Cuts produce globally optimal solutions. More generally, there are iterative techniques based on Graph-Cuts that produce provably good approximations which (were empirically shown to) correspond to high-quality solutions in practice. Thus, another large group of applications use Graph-Cuts as as an optimization technique for low-level vision problems based on global energy formulations.
-
interactive Graph Cuts for optimal boundary region segmentation of objects in n d images
International Conference on Computer Vision, 2001Co-Authors: Yuri Boykov, Mariepierre JollyAbstract:In this paper we describe a new technique for general purpose interactive segmentation of N-dimensional images. The user marks certain pixels as "object" or "background" to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and region information. Graph Cuts are used to find the globally optimal segmentation of the N-dimensional image. The obtained solution gives the best balance of boundary and region properties among all segmentations satisfying the constraints. The topology of our segmentation is unrestricted and both "object" and "background" segments may consist of several isolated parts. Some experimental results are presented in the context of photo/video editing and medical image segmentation. We also demonstrate an interesting Gestalt example. A fast implementation of our segmentation method is possible via a new max-flow algorithm.
Vladimir Kolmogorov - One of the best experts on this subject based on the ideXlab platform.
-
Kolmogorov and Zabih's Graph Cuts Stereo Matching Algorithm
Image Processing On Line, 2014Co-Authors: Vladimir Kolmogorov, Pascal Monasse, Pauline TanAbstract:Binocular stereovision estimates the three-dimensional shape of a scene from two photoGraphs taken from different points of view. In rectified epipolar geometry, this is equivalent to a matching problem. This article describes a method proposed by Kolmogorov and Zabih in 2001, which puts forward an energy-based formulation. The aim is to minimize a four-term-energy. This energy is not convex and cannot be minimized except among a class of perturbations called expansion moves, in which case an exact minimization can be done with Graph Cuts techniques. One noteworthy feature of this method is that it handles occlusion: The algorithm detects points that cannot be matched with any point in the other image. In this method displacements are pixel accurate (no subpixel refinement).
-
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007Co-Authors: Vladimir Kolmogorov, Carsten RotherAbstract:Optimization techniques based on Graph Cuts have become a standard tool for many vision applications. These techniques allow to minimize efficiently certain energy functions corresponding to pairwise Markov random fields (MRFs). Currently, there is an accepted view within the computer vision community that Graph Cuts can only be used for optimizing a limited class of MRF energies (e.g., submodular functions). In this survey, we review some results that show that Graph Cuts can be applied to a much larger class of energy functions (in particular, nonsubmodular functions). While these results are well-known in the optimization community, to our knowledge they were not used in the context of computer vision and MRF optimization. We demonstrate the relevance of these results to vision on the problem of binary texture restoration.
-
spatially coherent clustering using Graph Cuts
Computer Vision and Pattern Recognition, 2004Co-Authors: Ramin Zabih, Vladimir KolmogorovAbstract:Feature space clustering is a popular approach to image segmentation, in which a feature vector of local properties (such as intensity, texture or motion) is computed at each pixel. The feature space is then clustered, and each pixel is labeled with the cluster that contains its feature vector. A major limitation of this approach is that feature space clusters generally lack spatial coherence (i.e., they do not correspond to a compact grouping of pixels). In this paper, we propose a segmentation algorithm that operates simultaneously in feature space and in image space. We define an energy function over both a set of clusters and a labeling of pixels with clusters. In our framework, a pixel is labeled with a single cluster (rather than, for example, a distribution over clusters). Our energy function penalizes clusters that are a poor fit to the data in feature space, and also penalizes clusters whose pixels lack spatial coherence. The energy function can be efficiently minimized using Graph Cuts. Our algorithm can incorporate both parametric and non-parametric clustering methods. It can be applied to many optimization-based clustering methods, including k-means and k-medians, and can handle models, which are very close in feature space. Preliminary results are presented on segmenting real and synthetic images, using both parametric and non-parametric clustering.
-
What Energy Functions Can Be Minimized via Graph Cuts?
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004Co-Authors: Vladimir Kolmogorov, Ramin ZabihAbstract:In the last few years, several new algorithms based on Graph Cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a Graph such that the minimum cut on the Graph also minimizes the energy. Yet, because these Graph constructions are complex and highly specific to a particular energy function, Graph Cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by Graph Cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using Graph Cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by Graph Cuts. Researchers who are considering the use of Graph Cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate Graph. A software implementation is freely available.
-
what energy functions can be minimized via Graph Cuts
European Conference on Computer Vision, 2002Co-Authors: Vladimir Kolmogorov, Ramin ZabihAbstract:In the last few years, several new algorithms based on Graph Cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a Graph such that the minimum cut on the Graph also minimizes the energy. Yet because these Graph constructions are complex and highly specific to a particular energy function, Graph Cuts have seen limited application to date. In this paper we characterize the energy functions that can be minimized by Graph Cuts. Our results are restricted to energy functions with binary variables. However, our work generalizes many previous constructions, and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration and scene reconstruction. We present three main results: a necessary condition for any energy function that can be minimized by Graph Cuts; a sufficient condition for energy functions that can be written as a sum of functions of up to three variables at a time; and a general-purpose construction to minimize such an energy function. Researchers who are considering the use of Graph Cuts to optimize a particular energy function can use our results to determine if this is possible, and then follow our construction to create the appropriate Graph.
Philip H S Torr - One of the best experts on this subject based on the ideXlab platform.
-
simultaneous segmentation and pose estimation of humans using dynamic Graph Cuts
International Journal of Computer Vision, 2008Co-Authors: Pushmeet Kohli, Jonathan Rihan, Matthieu Bray, Philip H S TorrAbstract:This paper presents a novel algorithm for performing integrated segmentation and 3D pose estimation of a human body from multiple views. Unlike other state of the art methods which focus on either segmentation or pose estimation individually, our approach tackles these two tasks together. Our method works by optimizing a cost function based on a Conditional Random Field (CRF). This has the advantage that all information in the image (edges, background and foreground appearances), as well as the prior information on the shape and pose of the subject can be combined and used in a Bayesian framework. Optimizing such a cost function would have been computationally infeasible. However, our recent research in dynamic Graph Cuts allows this to be done much more efficiently than before. We demonstrate the efficacy of our approach on challenging motion sequences. Although we target the human pose inference problem in the paper, our method is completely generic and can be used to segment and infer the pose of any rigid, deformable or articulated object.
-
multiview stereo via volumetric Graph Cuts and occlusion robust photo consistency
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007Co-Authors: George Vogiatzis, Philip H S Torr, Carlos Hernandez, Roberto CipollaAbstract:This paper presents a volumetric formulation for the multiview stereo problem which is amenable to a computationally tractable global optimization using Graph-Cuts. Our approach is to seek the optimal partitioning of 3D space into two regions labeled 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 normalized 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.
-
measuring uncertainty in Graph cut solutions efficiently computing min marginal energies using dynamic Graph Cuts
Lecture Notes in Computer Science, 2006Co-Authors: Pushmeet Kohli, Philip H S TorrAbstract:In recent years the use of Graph-Cuts has become quite popular in computer vision. However, researchers have repeatedly asked the question whether it might be possible to compute a measure of uncertainty associated with the Graph-cut solutions. In this paper we answer this particular question by showing how the min-marginals associated with the label assignments in a MRF can be efficiently computed using a new algorithm based on dynamic Graph Cuts. We start by reporting the discovery of a novel relationship between the min-marginal energy corresponding to a latent variable label assignment, and the flow potentials of the node representing that variable in the Graph used in the energy minimization procedure. We then proceed to show how the min-marginal energy can be computed by minimizing a projection of the energy function defined by the MRF. We propose a fast and novel algorithm based on dynamic Graph Cuts to efficiently minimize these energy projections. The min-marginal energies obtained by our proposed algorithm are exact, as opposed to the ones obtained from other inference algorithms like loopy belief propagation and generalized belief propagation. We conclude by showing how min-marginals can be used to compute a confidence measure for label assignments in labelling problems such as image segmentation.
-
posecut simultaneous segmentation and 3d pose estimation of humans using dynamic Graph Cuts
Lecture Notes in Computer Science, 2006Co-Authors: Matthieu Bray, Pushmeet Kohli, Philip H S TorrAbstract:We present a novel algorithm for performing integrated segmentation and 3D pose estimation of a human body from multiple views. Unlike other related state of the art techniques which focus on either segmentation or pose estimation individually, our approach tackles these two tasks together. Normally, when optimizing for pose, it is traditional to use some fixed set of features, e.g. edges or chamfer maps. In contrast, our novel approach consists of optimizing a cost function based on a Markov Random Field (MRF). This has the advantage that we can use all the information in the image: edges, background and foreground appearances, as well as the prior information on the shape and pose of the subject and combine them in a Bayesian framework. Previously, optimizing such a cost function would have been computationally infeasible. However, our recent research in dynamic Graph Cuts allows this to be done much more efficiently than before. We demonstrate the efficacy of our approach on challenging motion sequences. Note that although we target the human pose inference problem in the paper, our method is completely generic and can be used to segment and infer the pose of any specified rigid, deformable or articulated object.
-
multi view stereo via volumetric Graph Cuts
Computer Vision and Pattern Recognition, 2005Co-Authors: George Vogiatzis, Philip H S Torr, Roberto CipollaAbstract:This paper presents a novel formulation for the multi-view scene reconstruction problem. While this formulation benefits from a volumetric scene representation, it is amenable to a computationally tractable global optimisation using Graph-Cuts. The algorithm proposed uses the visual hull of the scene to infer occlusions and as a constraint on the topology of the scene. A photo consistency-based surface cost functional is defined and discretised with a weighted Graph. The optimal surface under this discretised functional is obtained as the minimum cut solution of the weighted Graph. Our method provides a viewpoint independent surface regularisation, approximate handling of occlusions and a tractable optimisation scheme. Promising experimental results on real scenes as well as a quantitative evaluation on a synthetic scene are presented.
Xiahai Zhuang - One of the best experts on this subject based on the ideXlab platform.
-
atrial scar quantification via multi scale cnn in the Graph Cuts framework
Medical Image Analysis, 2020Co-Authors: Guang Yang, Tom Wong, Raad Mohiaddin, David N Firmin, Jennifer Keegan, Xiahai ZhuangAbstract:Abstract Late gadolinium enhancement magnetic resonance imaging (LGE MRI) appears to be a promising alternative for scar assessment in patients with atrial fibrillation (AF). Automating the quantification and analysis of atrial scars can be challenging due to the low image quality. In this work, we propose a fully automated method based on the Graph-Cuts framework, where the potentials of the Graph are learned on a surface mesh of the left atrium (LA) using a multi-scale convolutional neural network (MS-CNN). For validation, we have included fifty-eight images with manual delineations. MS-CNN, which can efficiently incorporate both the local and global texture information of the images, has been shown to evidently improve the segmentation accuracy of the proposed Graph-Cuts based method. The segmentation could be further improved when the contribution between the t-link and n-link weights of the Graph is balanced. The proposed method achieves a mean accuracy of 0.856 ± 0.033 and mean Dice score of 0.702 ± 0.071 for LA scar quantification. Compared to the conventional methods, which are based on the manual delineation of LA for initialization, our method is fully automatic and has demonstrated significantly better Dice score and accuracy (p
-
atrial scar quantification via multi scale cnn in the Graph Cuts framework
arXiv: Computer Vision and Pattern Recognition, 2019Co-Authors: Guang Yang, Tom Wong, Raad Mohiaddin, David N Firmin, Jennifer Keegan, Xiahai ZhuangAbstract:Late gadolinium enhancement magnetic resonance imaging (LGE MRI) appears to be a promising alternative for scar assessment in patients with atrial fibrillation (AF). Automating the quantification and analysis of atrial scars can be challenging due to the low image quality. In this work, we propose a fully automated method based on the Graph-Cuts framework, where the potentials of the Graph are learned on a surface mesh of the left atrium (LA) using a multi-scale convolutional neural network (MS-CNN). For validation, we have employed fifty-eight images with manual delineations. MS-CNN, which can efficiently incorporate both the local and global texture information of the images, has been shown to evidently improve the segmentation accuracy of the proposed Graph-Cuts based method. The segmentation could be further improved when the contribution between the t-link and n-link weights of the Graph is balanced. The proposed method achieves a mean accuracy of 0.856 +- 0.033 and mean Dice score of 0.702 +- 0.071 for LA scar quantification. Compared with the conventional methods, which are based on the manual delineation of LA for initialization, our method is fully automatic and has demonstrated significantly better Dice score and accuracy (p < 0.01). The method is promising and can be useful in diagnosis and prognosis of AF.
