Energy Minimization in Graph Cut Based Image Segmentation Using Active Contour Model

Energy Minimization in Graph Cut Based Image Segmentation Using Active Contour Model

Amandeep Chhabra

Assistant Professor,CSE Dept,GIMT,Kurukshetra

Divya Garg

1. ech (CSE),GIMT,Kurukshetra

   Abstract

   In this paper we give a brief overview how to solve the energy minimization problems in computer vision which is applicable in many fields like image segmentation ,image restoration that involve a large number of labels.By combining and using existing previous techniques the work is to optimize the graph cut using different techniques such as min-cut/max flow or s-t cut etc.The concept of optimality of such cuts is usually done by associating an energy to each cut.This paper provides a brief overview of the graph cuts and active contours used for the optimization.In this paper the labeling of the graph cut is done through active contour model.The main work is done to get better segmentation and less exectution time.

   1. Introduction.

      One of the major challenges for modern Computer Vision is the abundance of high-resolution image data. This gives an urgent requirement of algorithms with fast and predictable runtimes. Many of the computational challenges including image segmentation, stereo reconstruction or shape matching have recently been addressed by graph cut approaches, because these allow to efficiently solve the underlying labeling or correspondence problems in a globally optimal manner.In fact, in applications of interactive segmentation its runtime typically depends on the initialization i.e. on the user-specified choice of pixels that belong to the object. In contrast to currently used methods in Computer Vision the presented approach provides an upper bound for its runtime behavior that is almost linear. In particular, we are able to match two different planar shapes of N points in O(N2logN) and segment a given image of N pixels in O(N logN).On planar shape matching and image segmentation the speed-up is observed of an order of magnitude, depending on resolution and presented a graph cut approach for planar graphs which

      solves the problem in O(N logN) which is in contrast to the currently used algorithm of Boykov and Kolmogorov which provides a known upper bound on the worst case complexity. This algorithm reduces substantially the amount of required data structures and is therefore faster. They also gave the advantages of this compressed version of a maximum flow method in two benchmark tests, one on planar shape matching with increasing shape resolution and one on image segmentation with increasing image resolution.

      1. Image Segmentation

         Image segmentation can be defined as the task of distinguishing objects from background in unseen images.This divison is based on low level cues such as intensity,homogeneity or contours.The main goal in terms of the image segmentation problem is to solve: Given an image and we seek to detect the shape of the objects in it. This problem like many other image processing problems has vast applications in the industry especially in the area of pattern recognition and motion capturing. The solution of the image segmentation problem is best described by a generally closed curve in the 2-D domain representing the boundary of the objects. This naturally led one to consider the problem to be solved by curve evolution or active contours: Starting with an initial curve and evolving it to the correct steady state, i.e. the object boundaries.This has led to various ideas such as marker-points, volume of fluid method, cell method and the level set method.

         Image segmentation methods can be broadly categorized into Variational and Combinatorial methods.These two categories can be further subdivided based on how the boundary is represented. Variational methods like snakes, active contours etc. and Combinatorial approaches like path-based graph methods which uses explicit boundary representation.On the other hand Level-set method which is Variational method and Interactive Graph Cuts[1] uses implicit boundary representation.

         There is a fast and generic technique for performing binary segmentation.The approach first models the problem using Markov Random Field where an energy function representing the optimal segmentation is formulated. The different terms of the function is determined based on the user input (likelihood model) and a prior model.In this approach, the user marks certain pixels as either background or object.The likelihood is then calculated using this data.Finally, the energy function is minimized using Graph Cuts based technique.

      2. Overview of Graph Cut

         A graph cut is the process of portioning a directed or undirected graph into disjoint sets. Graph cut has been a very popular optimization tool in computer vision for a decade because of their suitability to many problems defined on images and because of their ability to find in small polynomial time, global optima of energies which were mistakenly thought to be NP-hard to minimize before.The graph cut method consists in rewriting the energy minimization as a search for a minimal cut in a graph.The new problem obtained is known in graph theory as min-cut or maximum flow and there exist efficient algorithms to solve it [5, 1] provided all weights in the graph are non-negative.

         Fig 1 : Image segmentation via graph cut

         In order to use s-t min cut techniques such as max-flow[5], we introduce in the graph two special nodes, the sink and the source of the flow.It is possible to consider several sources or/and several sinks, but such a problem can be easily rewritten as a classical graph with only one source and one sink. The minimal cut obtained can be seen as a partition of the nodes of the graph : those which are connected to the source, and those which are connected to the sink. Thus considering a cut is equivalent to picking a state s(Ni) for each node of the graph amongst the two

         possibilities mentioned.Nodes can then be seen as binary variables and graph cuts as states of all these binary variables together.

      3. Concept of Energy Optimization

      Greiget al. were first to discover that powerful min- cut/max-flow algorithms from combinatorial optimization can be used to minimize certain important energy functions in vision.

      The energies addressed by Greig et al. and by most later graph-based methods can be represented as :

      E(L)=Dp(Lp)+Vp,q(Lp,Lq) (1)

      pP (p,q)N

      where L = {Lp |p P} is a labeling of image P, Dp(·) is a data penalty function,Vp,q is an interaction potential and N is a set of all pairs of neighboring pixels. Data penalties Dp(·) indicate individual label-preferences of pixels based on observed intensities and pre-specified likelihood function.Interaction potentials Vp,q encourage spatial coherence by penalizing discontinuities between neighboring pixels.All edges in the graph are assigned some weight or cost.A cost of a directed edge (p, q) may differ from the cost of the reverse edge (q, p).In fact, ability to assign different edge weights for (p, q) and (q, p) is important for many graph-based applications in vision.

      Normally there are two types of edges in the graph:N-links and T-links.N-links connect pairs of neighboring pixels or voxels.Thus they represent a neighborhood system in the image.Cost of n-links corresponds to a penalty for discontinuity between the pixels.These costs are usually derived from the pixel interaction term Vp,q in energy (1).T- links connect pixels with terminals (labels).The cost of a t- link connecting a pixel and a terminal corresponds to a penalty for assining the corresponding label to the pixel.This cost is normally derived from the data term Dp in the energy (1).

      An s/t cut C on a graph with two terminals is a partitioning of the nodes in the graph into two disjoint subsets S and T such that the source s is in S and the sink t is in T .In combinatorial optimization the cost of a cut C = {S, T } is defined as the sum of the costs of boundary edges (p, q) where p S and q T . The minimum cut problem on a graph is to find a cut that has the minimum cost among all cuts and this minimum s/t cut problem can be solved by finding a maximum flow from the source s to the sink t.Thus min-cut and max-flow problems are equivalent.In fact, the maximum flow value is equal to the cost of the minimum cut.

      The basic technique is to construct a specialized graph for the energy function to be minimized such that the minimum cut on the graph also minimizes the energy (either globally or locally). The minimum cut in turn can be computed very efficiently by max flow algorithms.The output of these algorithms is generally a solution with some interesting theoretical quality guarantee.In some cases it is the global minimum and in other cases a local minimum in a strong sense that is within a known factor of the global minimum.

   2. Related Work.

      David Mumford, Jayant Shah [6] introduced the most basic properties of three new variational problems which are suggested by applications to computer vision.In computer vision, a fundamental problem is to appropriately decompose the domain R of a function g(x, y) of two variables.The segmentation problem in computer vision consists in computing a decomposition R = R, U UR, of the domain of the image g such that:

      1. the image g varies smoothly and/or slowly within each R.

      2. the image g varies discontinuously and/or rapidly across most of the boundary r between different R .

      CAT scans are estimates of the density of the body at points (x , y, z) in three-space, segmentation is needed to identify the various organs of the body.

      Noha El-Zehiry and Adel Elmaghraby described a graph cut based active contour without edges segmentation model to track pedestrian in thermal images.The deformable model is based on the Mumford- Shah piecewise constant energy formulation.A discrete energy formulation is presented and the optimization is performed using graph cuts.The major advantages of the approach were:(1)The optimization using graph cuts makes the segmentation process much faster than solving it using level sets.2) Relaxing the global homogeneity assumption makes the model more practical.

      The paper presented an active contour model for image segmentation.The model has two major advantages: First, the model is very fast because of the polynomial time complexity associated with min cut/max flow algorithms.

      Second, it assumes only local homogeneity within the single object which makes it more practical and applicable. The segmentation model is general and can be used for any segmentation problem.

      2.1 Active Contour model.

      Chan and Vese introduced a method for segmenting images which is a powerful, flexible method that can successfully segment many types of images, including some that would be difficult or impossible to segment with classical thresholding or gradient-based methods. The Chan-Vese algorithm is an example of a geometric active contour model. Such models begin with a contour in the image plane defining an initial segmentation and then we evolve this contour according to some evolution equation. The goal is to evolve the contour in such a way that it stops on the boundaries of the foreground region. The Chan-Vese algorithm evolves this contour via a level set method .We define some function (i, j ,t),the level-set function where (i, j) are coordinates in the image plane and t is an artificial time. At any given time, the level set function simultaneously defines an edge contour and a segmentation of the image. The edge contour is taken to be the zero level set {(i,j)s.t.(i, j , t)= 0}, and the segmentation is given by the two regions {> 0} and { < 0}. The level set function will be evolved according to some partial differential equation, and hopefully will reach a steady state lim t that gives a useful segmentation of the image.

      As a simple illustration of this concept, suppose we have a 100 × 100 image and by some means we determine a level- set function to be (i,j)=(x50)2+(y 50)2600.If we define the foreground to be the region where < 0, then the foreground found by this segmentation would be the region inside the circle.

      The most important and difficult step is to actually determine a level set function that segments the image in a meaningful way.The most useful example would be to define the level set function to be the value of a gray level image at each pixel minus some threshold i.e set (i, j)=I(i,

      j) -t.

      Then the level set function is positive in regions where the gray level is above the threshold and negative in regions where the gray level is below the threshold.

   3. Conclusion .

      Fig 2: Surface plot of an example level set function f(x, y)

      Fig 3: Its zero level contour in the image plane.

      Image segmentation aims at extracting meaningful objects lying in images either by dividing images into contiguous semantic regions or by extracting one or more specific objects in images such as medical structures.The image segmentation task is in general very difficult to achieve since natural images are diverse,complex and the way we perceive them vary according to individuals.So a mathematical framework based on variational models and partial differential equations have been found to solve the image segmentation problem.The active contours or snakes model is more and more used in image segmentation because it relies on solid mathematical properties and its numerical implementation uses the efficient level set method to track evolving contours. In this paper labeling is described through level set methods.Level set methods are especially useful because they can easily handle topological changes in the edge contour that would be difficult to handle with a model that directly evolves the contour .In this paper labeling is described through level set methods.

   4. References:

1. Yuri Boykov and Vladimir Kolmogorov presented An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision in International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), number 2134 in LNCS, pages 359 374, Sophia Antipolis, France, September 2001.

2. Frank R. Schmidt, Eno Toppe and Daniel Cremers presented Efficient Planar Graph Cuts with Applications in Computer Vision in IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2009, Miami, Florida.

3. Vladimir Kolmogorov,Member, IEEE and Ramin Zabih, Member, IEEE.presented What Energy Functions Can Be Minimized via Graph Cuts in IEEE transcations on pattern analysis and machine intelligence,Vol 26,No.2,February 2004.

4. Anders P.eriksson,Olof Barr and Kalle Astrom ,Centre for mathematical Sciences presented Image Segmentation Using Minimal Graph Cuts.

5. Guillaume Charpiat ,Pulsar team,INRIA presented Exhaustive Family of Energies Minimizable Exactly by a graph cut.

6. David Mumford,Harvard University And Jayant Shah,Northeastern University presented Optimal Approxmiations

   by piecewise smooth functions and associated Variational Problems.

7. Robert Crandall presented image segmentation using the Chan Vese Algorithm in Project fall ,2009

8. Tony F.Chan,Member ,IEEE and Luminita A.Vese presented Active Contours without edges in IEEE Transcations on Image Processing ,Vol.10,No 2,February 2001

9. Yuri Boykov,Olga Veksler and Ramin Zabih presented Fast approximate energy minimizaton via Graph cuts.

10. Noha El-Zehiry and Adel Elmaghraby in Computer Engineering and Computer Science Department – University of Louisville presented A Graph Cut Based Active Contour without Edges with Relaxed Homogeneity Constraint.