A New Continuous Max-flow Algorithm for Multiphase Image Segmentation using Super-level Set Functions

ArticleinJournal of Visual Communication and Image Representation 25(6) · August 2014with 60 Reads 
How we measure 'reads'
A 'read' is counted each time someone views a publication summary (such as the title, abstract, and list of authors), clicks on a figure, or views or downloads the full-text. Learn more
Cite this publication
Abstract
We propose a graph cut based global minimization method for image segmentation by representing the segmentation label function with a series of nested binary super-level set functions. This representation enables us to use K-1K-1 binary functions to partition any images into K phases. Both continuous and discretized formulations will be treated. For the discrete model, we propose a new graph cut algorithm which is faster than the existing graph cut methods to obtain the exact global solution. In the continuous case, we further improve the segmentation accuracy using a number of techniques that are unique to the continuous segmentation models. With the convex relaxation and the dual method, the related continuous dual model is convex and we can mathematically show that the global minimization can be achieved. The corresponding continuous max-flow algorithms are easy and stable. Experimental results show that our model is very competitive to some existing methods.

Do you want to read the rest of this article?

Request Full-text Paper PDF
  • Conference Paper
    Full-text available
    We propose a unified graph cut based global minimization method for multiphase image segmentation by convexifying the non-convex image segmentation cost functionals. As examples, we shall apply this method to the non-convex multiphase Chan-Vese (CV) model and piecewise constant level set method (PCLSM). Both continuous and discretized formulations will be treated. For the discrete models, we propose a unified graph cut algorithm to implement the CV and PCLSM models, which extends the result of Bae and Tai [1] to any phases CV model. Moreover, in the continuous case, we further improve the model to be convex without any conditions using a number of techniques that are unique to the continuous segmentation models. With the convex relaxation and the dual method, the related continuous dual model is convex and we can mathematically show that the global minimization can be achieved. The corresponding continuous max-flow algorithm is easy and stable. Experimental results show that our model is very efficient.
  • Article
    The basic idea of active contour model upon the image segmentation problem is evolved into a closed curve about the functional minimization problems. Active contour model based on edge information takes advantage of gradient information, and it has some shortcomings such as cannot separate weak boundary, fuzzy boundary, and discontinuous boundary object. Chan–Vese active contour model without edges can overcome the shortcomings of model based on gradient, but it cannot separate gray inhomogeneous target and evolves slowly, moreover, segmentation efficiency is low. The aim of this article is to overcome the shortage of the geodesic active contour model such as lower convergence rate and more easily trapped in local minimum .The article puts forward a new active contour model control system where the edge information is combined with regional one effectively, and it makes good use of the gradient information and the area information. A large amount of simulation results show that the proposed algorithm’s convergence speed is much faster than geodesic active contour model, and it can segment serious noisy image. It inherited the edge and the region information as well, so the new model performs well in resisting noise and has high segmentation efficiency.
  • Article
    This paper presents a convex variational model for multiphase image segmentation by incorporating a multiresolution approach. We extend our previous work to formulate the energy functional which is robust response to image variations. In contrast to our previous work, which can lead to local minima, a global solution is proposed to minimize the segmentation energy with some constraint conditions. By incorporating edge-based information, a non-convex energy functional is first introduced on the membership functions, which are used as indicators of different homogeneous regions. Then the non-convex problem is converted into a continuous convex formulation. An efficient dual minimization implementation of our binary partitioning function model accurately describes disjoint regions using stable segmentation. Experiments results show the proposed model is robust to noise, independent of initialization and unambiguous segmentation. Compared with the traditional variational models, the proposed model can get more accurate results and higher computational efficiency.
  • Conference Paper
    The study is to investigate a fast globally convex variational model for the multiphase image segmentation. Firstly, a nonconvex energy functional on the membership functions, which are used as indicators of different homogeneous regions, is introduced by incorporating edge-based information. Secondly, the nonconvex problem is converted into a continuous convex formulation. Finally, a dual minimization formulation of the binary partitioning function accurately describes disjoint regions using stable segmentations by avoiding local minima solutions and unambiguous segmentation. Experiments results show more accurate segmentation results on both medical and natural images compared with multi-region competition model.
  • We propose and study novel max-flow models in the continuous setting, which directly map the discrete graph-based max-flow problem to its continuous optimization formulation. We show such a continuous max-flow model leads to an equivalent min-cut problem in a natural way, as the corresponding dual model. In this regard, we revisit basic conceptions used in discrete max-flow / min-cut models and give their new explanations from a variational perspective. We also propose corresponding continuous max-flow and min-cut models constrained by priori supervised information and apply them to interactive image segmentation/labeling problems. We prove that the proposed continuous max-flow and min-cut models, with or without supervised constraints, give rise to a series of global binary solutions λ*(x) ϵ {0,1}, which globally solves the original nonconvex image partitioning problems. In addition, we propose novel and reliable multiplier-based max-flow algorithms. Their convergence is guaranteed by classical optimization theories. Experiments on image segmentation, unsupervised and supervised, validate the effectiveness of the discussed continuous max-flow and min-cut models and suggested max-flow based algorithms.
  • Conference Paper
    We propose an algorithm for minimizing the total variation of an image, and provide a proof of convergence. We show applications to image denoising, zooming, and the computation of the mean curvature motion of interfaces.
  • Article
    We propose an algorithm for minimizing the total variation of an image, and provide a proof of convergence. We show applications to image denoising, zooming, and the computation of the mean curvature motion of interfaces.
  • Article
    The Mumford-Shah model is one of the most important image segmentation models and has been studied extensively in the last twenty years. In this paper, we propose a two-stage segmentation method based on the Mumford-Shah model. The first stage of our method is to find a smooth solution g to a convex variant of the Mumford-Shah model. Once g is obtained, then in the second stage the segmentation is done by thresholding g into different phases. The thresholds can be given by the users or can be obtained automatically using any clustering methods. Because of the convexity of the model, g can be solved efficiently by techniques like the split-Bregman algorithm or the Chambolle-Pock method. We prove that our method is convergent and that the solution g is always unique. In our method, there is no need to specify the number of segments K (K≥2) before finding g. We can obtain any K-phase segmentations by choosing (K-1) thresholds after g is found in the first stage, and in the second stage there is no need to recompute g if the thresholds are changed to reveal different segmentation features in the image. Experimental results show that our two-stage method performs better than many standard two-phase or multiphase segmentation methods for very general images, including antimass, tubular, MRI, noisy, and blurry images.
  • Article
    This paper studies continuous image labeling problems with an arbitrary data term and a total variation regularizer, where the labels are constrained to a finite set of real numbers. Inspired by Ishikawa’s multi-layered graph construction for the same labeling problem over a discrete image domain, we propose a novel continuous max-flow model and build up its duality to a convex relaxed formulation of image labeling under a new variational perspective. Via such continuous max-flow formulations, we show that exact and global optimizers can be obtained to the original non-convex labeling problem. We also extend the studies to problems with continuous-valued labels and introduce a new theory to this problem. Finally, we show the proposed continuous max-flow models directly lead to new fast flow-maximization algorithmic schemes which outperform previous approaches in terms of efficiency. Such continuous max-flow based algorithms can be validated by convex optimization theories and accelerated by modern parallel computational hardware.
  • Article
    Full-text available
    We propose an exact global minimization framework for variational image segmentation models, such as the Chan-Vese model, involving four regions. A global solution is guaranteed if the data term satisfies a mild condition. It is shown theoretically and experi-mentally that such a condition holds in practice for the most commonly used type of data terms, such as the Chan-Vese model and Mumford Shah model. If the con-dition is violated, convex and submodular relaxations are proposed which are not guaranteed to produce ex-act solutions, but tends to do so in practice. We also build up a convex relaxation for Pott's model with four regions, which is at least as tight as the tightest ex-isting relaxation, but significantly simpler. Algorithms are proposed which are very efficient due to the simple formulations.
  • Article
    Full-text available
    We describe a convex relaxation for a family of problems of minimal perimeter partitions. The minimization of the relaxed problem can be tackled numerically, we describe an algorithm and show some results. In most cases, our relaxed problem finds a correct numerical approximation of the optimal solution: we give some arguments to explain why it should be so, and also discuss some situation where it fails. This preprint is a revised version of an technical paper of 2008 (see for instance the CMAP preprint #649, november 2008), which was rewritten in order to clarify, in particular, the relationship with the classical "paired calibration" approach for minimal surfaces.
  • Article
    We propose an algorithm for minimizing the total variation of an image, and provide a proof of convergence. We show applications to image denoising, zooming, and the computation of the mean curvature motion of interfaces.
  • Article
    We propose a new multiphase level set framework for image segmentation using the Mumford and Shah model, for piecewise constant and piecewise smooth optimal approximations. The proposed method is also a generalization of an active contour model without edges based 2-phase segmentation, developed by the authors earlier in T. Chan and L. Vese (1999. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141–151) and T. Chan and L. Vese (2001. IEEE-IP, 10(2):266–277). The multiphase level set formulation is new and of interest on its own: by construction, it automatically avoids the problems of vacuum and overlap; it needs only log n level set functions for n phases in the piecewise constant case; it can represent boundaries with complex topologies, including triple junctions; in the piecewise smooth case, only two level set functions formally suffice to represent any partition, based on The Four-Color Theorem. Finally, we validate the proposed models by numerical results for signal and image denoising and segmentation, implemented using the Osher and Sethian level set method.
  • Data
    In this paper, we propose a new, fast, and stable hybrid numerical method for multiphase image segmentation using a phase-field model. The proposed model is based on the Allen-Cahn equation with a multiple well potential and a data-fitting term. The model is computationally superior to the previous multiphase image segmentation via Modica-Mortola phase transition and a fitting term. We split its numerical solution algorithm into linear and a nonlinear equations. The linear equation is discretized using an implicit scheme and the resulting discrete system of equations is solved by a fast numerical method such as a multigrid method. The nonlinear equation is solved analytically due to the availability of a closed-form solution. We also propose an initialization algorithm based on the target objects for the fast image segmentation. Finally, various numerical experiments on real and synthetic images with noises are presented to demonstrate the efficiency and robustness of the proposed model and the numerical method.
  • Article
    Full-text available
    In this paper, we propose a new variational framework to solve the Gaussian mixture model (GMM) based methods for image segmentation by employing the convex relaxation approach. After relaxing the indicator function in GMM, flexible spatial regularization can be adopted and efficient segmentation can be achieved. To demonstrate the superiority of the proposed framework, the global, local intensity information and the spatial smoothness are integrated into a new model, and it can work well on images with inhomogeneous intensity and noise. Compared to classical GMM, numerical experiments have demonstrated that our algorithm can achieve promising segmentation performance for images degraded by intensity inhomogeneity and noise.
  • We integrate the total variation (TV) minimization into the expectation–maximization (EM) algorithm to perform the task of image segmentation for general vector-valued images. We first propose a unified variational method to bring together the EM and the TV regularization and to take advantages from both approaches. The idea is based on operator interchange and constraint optimization. In the second part of the paper we propose a simple two-phase approach by splitting the above functional into two steps. In the first phase, a typical EM method can classify pixels into different classes based on the similarity in their measurements. However, since no local geometric information of the image has yet been incorporated into the process, such classification in practice gives unsatisfactory segmentation results. In the second phase, the TV-step obtains the segmentation of the image by applying a TV regularization directly to the clustering result from EM.
  • Article
    p1 Present address: The University of Adelaide, South Australia.
  • Article
    Full-text available
    In this paper, for a degraded two‐colour or binary scene, we show how the image with maximum a posteriori (MAP) probability, the MAP estimate, can be evaluated exactly using efficient variants of the Ford–Fulkerson algorithm for finding the maximum flow in a certain capacitated network. Availability of exact estimates allows an assessment of the performance of simulated annealing and of MAP estimation itself in this restricted setting. Unfortunately, the simple network flow algorithm does not extend in any obvious way to multicolour scenes. However, the results of experiments on two‐colour images suggest that, in general, simulated annealing, according to practicable ‘temperature’ schedules, can produce poor approximations to the MAP estimate to which it converges.
  • Article
    Full-text available
    The active contour/snake model is one of the most successful variational models in image segmentation. It consists of evolving a contour in images toward the boundaries of objects. Its success is based on strong mathematical properties and efficient numerical schemes based on the level set method. The only drawback of this model is the existence of local minima in the active contour energy, which makes the initial guess critical to get satisfactory results. In this paper, we propose to solve this problem by determining a global minimum of the active contour model. Our approach is based on the unification of image segmentation and image denoising tasks into a global minimization framework. More precisely, we propose to unify three well-known image variational models, namely the snake model, the Rudin–Osher–Fatemi denoising model and the Mumford–Shah segmentation model. We will establish theorems with proofs to determine the existence of a global minimum of the active contour model. From a numerical point of view, we propose a new practical way to solve the active contour propagation problem toward object boundaries through a dual formulation of the minimization problem. The dual formulation, easy to implement, allows us a fast global minimization of the snake energy. It avoids the usual drawback in the level set approach that consists of initializing the active contour in a distance function and re-initializing it periodically during the evolution, which is time-consuming. We apply our segmentation algorithms on synthetic and real-world images, such as texture images and medical images, to emphasize the performances of our model compared with other segmentation models.
  • Article
    Stereo matching is one of the most active research areas in computer vision. While a large number of algorithms for stereo correspondence have been developed, relatively little work has been done on characterizing their performance. In this paper, we present a taxonomy of dense, two-frame stereo methods. Our taxonomy is designed to assess the different components and design decisions made in individual stereo algorithms. Using this taxonomy, we compare existing stereo methods and present experiments evaluating the performance of many different variants. In order to establish a common software platform and a collection of data sets for easy evaluation, we have designed a stand-alone, flexible C++ implementation that enables the evaluation of individual components and that can easily be extended to include new algorithms. We have also produced several new multi-frame stereo data sets with ground truth and are making both the code and data sets available on the Web. Finally, we include a comparative evaluation of a large set of today's best-performing stereo algorithms.
  • Conference Paper
    Full-text available
    In this work we propose a convex relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm which also allows a fast implementation on parallel hardware. Although our approach does not guarantee to find global minimizers of the Potts model we can give a tight bound on the energy between the computed solution and the true minimizer. Furthermore we show that our relaxation approach dominates recently proposed relaxations. As a consequence, our approach allows to compute solutions closer to the true minimizer. For many practical problems we even find the global minimizer. We demonstrate the excellent performance of our approach on several multi-label image segmentation and stereo problems.
  • Conference Paper
    We address the continuous problem of assigning multiple (unordered) labels with the minimum perimeter. The corresponding discrete Potts model is typically addressed with a-expansion which can generate metrication artifacts. Existing convex continuous formulations of the Potts model use TV-based functionals directly encoding perimeter costs. Such formulations are analogous to 'min-cut' problems on graphs. We propose a novel convex formulation with a continous 'max-flow' functional. This approach is dual to the standard TV-based formulations of the Potts model. Our continous max-flow approach has significant numerical advantages; it avoids extra computational load in enforcing the simplex constraints and naturally allows parallel computations over different labels. Numerical experiments show competitive performance in terms of quality and significantly reduced number of iterations compared to the previous state of the art convex methods for the continuous Potts model.
  • Conference Paper
    Full-text available
    We propose a spatially continuous formulation of Ishikawa's discrete multi-label problem. We show that the resulting non-convex vari- ational problem can be reformulated as a convex variational problem via embedding in a higher dimensional space. This variational problem can be interpreted as a minimal surface problem in an anisotropic Rie- mannian space. In several stereo experiments we show that the proposed continuous formulation is superior to its discrete counterpart in terms of computing time, memory efficiency and metrication errors.
  • Conference Paper
    Full-text available
    The piecewise constant level set method (PCLSM) has recently emerged as a variant of the level set method for variational interphase problems. Traditionally, the Euler-Lagrange equations are solved by some iterative numerical method for PDEs. Normally the speed is slow. In this work, we focus on the piecewise constant level set method (PCLSM) applied to the multiphase Mumford-Shah model for image segmentation. Instead of solving the Euler-Lagrange equations of the resulting minimization problem, we propose an efficient combinatorial optimization technique, based on graph cuts. Because of a simplification of the length term in the energy induced by the PCLSM, the minimization problem is not NP hard. Numerical experiments on image segmentation demonstrate that the new approach is very superior in terms of efficiency, while maintaining the same quality.
  • Conference Paper
    Full-text available
    In the recent decades the ROF model (total variation (TV) minimization) has made great successes in image restoration due to its good edge-preserving property. However, the non-differentiability of the minimization problem brings computational difficulties. Different techniques have been proposed to overcome this difficulty. Therein methods regarded to be particularly efficient include dual methods of CGM (Chan, Golub, and Mulet) [7] Chambolle [6] and split Bregman iteration [14], as well as splitting-and-penalty based method [28] [29]. In this paper, we show that most of these methods can be classified under the same framework. The dual methods and split Bregman iteration are just different iterative procedures to solve the same system resulted from a Lagrangian and penalty approach. We only show this relationship for the ROF model. However, it provides a uniform framework to understand these methods for other models. In addition, we provide some examples to illustrate the accuracy and efficiency of the proposed algorithm.
  • Multi-class labeling is one of the core problems in image analysis. We show how this combinatorial problem can be approximately solved using tools from convex optimization. We suggest a novel functional based on a multidimensional total variation formulation, allowing for a broad range of data terms. Optimization is carried out in the operator splitting framework using Douglas-Rachford Splitting. In this connection, we compare two methods to solve the Rudin-Osher-Fatemi type subproblems and demonstrate the performance of our approach on single- and multichannel images.
  • Conference Paper
    Full-text available
    This work presents a real-time, data-parallel approach for global label assignment on regular grids. The labels are selected according to a Markov random field energy with a Potts prior term for binary interactions. We apply the proposed method to accelerate the clean- up step of a real-time dense stereo method based on plane sweeping with multiple sweeping directions, where the label set directly corresponds to the employed directions. In this setting the Potts smoothness model is suitable, since the set of labels does not possess an intrinsic metric or total order. The observed run-times are approximately 30 times faster than the ones obtained by graph cut approaches.
  • Conference Paper
    Full-text available
    The Mumford-Shah model is an important variational image segmentation model. A popular multiphase level set approach, the Chan-Vese model, was developed for this model by representing the phases by several overlapping level set functions. Recently, exactly the same model was also formulated by using binary level set functions. In both approaches, the gradient descent equations had to be solved numerically, a procedure which is slow and has the potential of getting stuck in a local minima. In this work, we develop an efficient and global minimization method for the binary level set representation of the multiphase Chan-Vese model based on graph cuts. If the average intensity values of the different phases are sufficiently evenly distributed, the discretized energy function becomes submodular. Otherwise, a novel method for minimizing nonsubmodular functions is proposed with particular emphasis on this energy function.
  • Article
    Full-text available
    This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding duality-based approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality.
  • Article
    Full-text available
    In this paper we introduce novel regularization techniques for level set segmentation that target specifically the problem of multiphase segmentation. When the multiphase model is used to obtain a partitioning of the image in more than two regions, a new set of issues arise with respect to the single phase case in terms of regularization strategies. For example, if smoothing or shrinking each contour individually could be a good model in the single phase case, this is not necessarily true in the multiphase scenario. In this paper, we address these issues designing enhanced length and area regularization terms, whose minimization yields evolution equations in which each level set function involved in the multiphase segmentation can “sense” the presence of the other level set functions and evolve accordingly. In other words, the coupling of the level set function, which before was limited to the data term (i.e. the proper segmentation driving force), is extended in a mathematically principled way to the regularization terms as well. The resulting regularization technique is more suitable to eliminate spurious regions and other kind of artifacts. An extensive experimental evaluation supports the model we introduce in this paper, showing improved segmentation performance with respect to traditional regularization techniques.
  • Article
    In this paper, we propose a new, fast, and stable hybrid numerical method for multiphase image segmentation using a phase-field model. The proposed model is based on the Allen–Cahn equation with a multiple well potential and a data-fitting term. The model is computationally superior to the previous multiphase image segmentation via Modica-Mortola phase transition and a fitting term. We split its numerical solution algorithm into linear and a nonlinear equations. The linear equation is discretized using an implicit scheme and the resulting discrete system of equations is solved by a fast numerical method such as a multigrid method. The nonlinear equation is solved analytically due to the availability of a closed-form solution. We also propose an initialization algorithm based on the target objects for the fast image segmentation. Finally, various numerical experiments on real and synthetic images with noises are presented to demonstrate the efficiency and robustness of the proposed model and the numerical method.
  • Article
    In this paper, we propose a new model for active contours to detect objects in a given image, based on techniques of curve evolution, Mumford--Shah functional for segmentation and level sets. Our model can detect objects whose boundaries are not necessarily defined by gradient. We minimize an energy which can be seen as a particular case of the minimal partition problem. In the level set formulation, the problem becomes a "mean-curvature flow"-like evolving the active contour, which will stop on the desired boundary. However, the stopping term does not depend on the gradient of the image, as in the classical active contour models, but is instead related to a particular segmentation of the image. We will give a numerical algorithm using finite differences. Finally, we will present various experimental results and in particular some examples for which the classical snakes methods based on the gradient are not applicable. Also, the initial curve can be anywhere in the image, and interior contours are automatically detected.
  • Article
    Full-text available
    Variational models for image segmentation have many applications, but can be slow to compute. Recently, globally convex segmentation models have been introduced which are very reliable, but contain TV- regularizers, making them dicult to compute. The previously intro- duced Split Bregman method is a technique for fast minimization of L1 regularized functionals, and has been applied to denoising and compressed sensing problems. By applying the Split Bregman concept to image seg- mentation problems, we build fast solvers which can out-perform more conventional schemes, such as duality based methods and graph-cuts. We also consider the related problem of surface reconstruction from unorga- nized data points, which is used for constructing level set representations in 3 dimensions.
  • Article
    Full-text available
    We propose a novel multiphase segmentation model built upon the celebrated phase transition model of Modica and Mortola in material sciences and a properly synchronized tting term that complements it. The proposed sine-sinc model outputs a single multiphase distribution from which each individual segment or phase can be easily extracted. Theoretical analysis is developed for the -con vergence behavior of the proposed model and the existence of its minimizers. Since the model is not quadratic nor convex, for computation we adopted the convex-concave procedure (CCCP) that has been developed in the literatures of both computational nonlinear PDEs and neural computation. Numerical details and experiments on both synthetic and natural images are presented.
  • Article
    Full-text available
    TABLA DE CONTENIDO RESUMEN We<sup> </sup>show how certain nonconvex optimization problems that arise in image<sup> </sup>processing and computer vision can be restated as convex minimization<sup> </sup>problems. This allows, in particular, the finding of global minimizers <sup> </sup>via standard convex minimization schemes.
  • Article
    Full-text available
    In Part II of this paper we extend the results obtained in Part I for total variation minimization in image restoration towards the following directions: first we investigate the decomposability property of energies on levels, which leads us to introduce the concept of levelable regularization functions (which TV is the paradigm of). We show that convex levelable posterior energies can be minimized exactly using the level-independant cut optimization scheme seen in Part I. Next we extend this graph cut scheme to the case of non-convex levelable energies. We present convincing restoration results for images corrupted with impulsive noise. We also provide a minimum-cost based algorithm which computes a global minimizer for Markov Random Field with convex priors. Last we show that non-levelable models with convex local conditional posterior energies such as the class of generalized Gaussian models can be exactly minimized with a generalized coupled Simulated Annealing.
  • Article
    Full-text available
    In image processing, the Rudin-Osher-Fatemi (ROF) model [L. Rudin, S. Osher, and E. Fatemi, Physica D, 60(1992), pp. 259{268] based on total variation (TV) minimization has proven to be very useful. A lot of eorts have been devoted to obtain fast numerical schemes and overcome the non-dieren tiability of the model. Methods considered to be particularly ecien t for the ROF model include the dual methods of Chan-Golub-Mulet (CGM) [T.F. Chan, G.H. Golub, and P. Mulet, SIAM J. Sci. Comput., 20(1999), pp. 1964{1977] and Chambolle [A. Chambolle, J. Math. Imaging Vis., 20(2004), pp. 89{97], and splitting and penalty based method [Y. Wang, J. Yang, W. Yin, and Y. Zhang, SIAM J. Imaging Sciences, 1(2008), pp. 248{272], as well as split Bregman iteration [T. Goldstein, and S. Osher, SIAM J. Imaging Sciences, 2(2009), pp. 323{343]. In this paper, we propose to use augmented Lagrangian method to solve the model. Convergence analysis will be given for the method. In addition, we observe close connections between the method proposed here and some of the existing methods. We show that the augmented Lagrangian method, dual methods, and split Bregman iteration are dieren t iterative procedures to solve the same system. Moreover, the proposed method is extended to vectorial TV and high order models. Using the approach here, we can easily obtain the CGM dual method and split Bregman iteration for vectorial TV and high order models, which, to our best of knowledge, have not been presented in the literature. Numerical examples demonstrate the eciency,and accuracy of our method. Key words. augmented Lagrangian method, dual method, split Bregman iteration, ROF model,
  • Article
    Full-text available
    The class of ℓ 1 -regularized optimization problems has received much attention recently because of the introduction of “compressed sensing”, which allows images and signals to be reconstructed from small amounts of data. Despite this recent attention, many ℓ 1 -regularized problems still remain difficult to solve, or require techniques that are very problem-specific. In this paper, we show that Bregman iteration can be used to solve a wide variety of constrained optimization problems. Using this technique, we propose a “split Bregman” method, which can solve a very broad class of ℓ 1 -regularized problems. We apply this technique to the Rudin-Osher-Fatemi functional for image denoising and to a compressed sensing problem that arises in magnetic resonance imaging.
  • Article
    Full-text available
    In this paper we propose a variant of the level set formulation for identifying curves separating regions into different phases. In classical level set approaches, the sign of level set functions are utilized to identify up to 2n phases. The novelty in our approach is to introduce a piecewise constant level set function and use each constant value to represent a unique phase. If phases should be identified, the level set function must approach 2n predetermined constants. We just need one level set function to represent 2n unique phases, and this gains in storage capacity. Further, the reinitializing procedure requested in classical level set methods is superfluous using our approach. The minimization functional for our approach is locally convex and differentiable and thus avoids some of the problems with the nondifferentiability of the Delta and Heaviside functions. Numerical examples are given, and we also compare our method with related approaches. Published version
  • Article
    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.
  • Article
    After [15], [31], [19], [8], [25], [5], minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push-relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.