JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN ELECTRONICS AND COMMUNICATION ENGINEERING
REVIEW ON IMAGE SEGMENTATION USING LEVEL SET METHOD
1 NAITIK KAPADIA, 2 RINKU SOLANKI
I. NAITIK KAPADIA(M.Tech in digital communication, R.K.D.F. college, Bhopal,india)
II. RINKU SOLANKI (M.Tech in digital communicaton, N.R.I.collge, Bhopal,india)
,
ABSTRACT: The level set method is a popular technique for tracking moving interfaces in several disciplines including computer vision and fluid dynamics. The level set method has been used in a rapidly growing number of areas, far too many to be represented here. These include epitaxial growth, optimal design, CAD, MEMS, optimal control, MRI image segmentation and others where the simulation of moving interfaces plays a key role in the problem to be solved. In this paper we give the overview of the recent development in the area of image segmentation using level set method.
Keywords— level set method, image segmentation, literature survey
ISSN: 0975 –6779| NOV 11 TO OCT 12 | VOLUME – 02, ISSUE - 01 Page 310
JOURNAL OF INFORMATION, KNOWLEDGE AND RESEARCH IN ELECTRONICS AND COMMUNICATION ENGINEERING
I: Introduction
In the last twenty years, the level set method (LSM) of Osher and Sethian [11] has become a popular numerical technique for tracking moving interfaces in computational geometry, fluid mechanics, computer graphics, computer vision and material sciences. The main reasons of its success are the high flexibility of this method to adapt to different problems, the ability to deal with changes of topology (contour breaking and merging) without any extra functions and the guarantee of the existence of solutions in the class of viscosity partial differential equations (PDEs). Moreover, extensive numerical algorithms based on Hamilton-Jacobi equations have been developed, accurately handling shocks and providing stable numerical schemas.
The key idea of the LSM is to implicitly represent a contour or interface as the zero level set of a higher dimensional function, called the level set function (LSF), and formulate the evolution of the contour through the evolution of the level set function. For closed contours, signed distance functions (SDFs) were originally adopted to represent level set functions because they directly provide stability and accuracy to the LSM.
The rest of the paper is organized as follows. Section 2 illustrate the different types of methods for image segmentation Section 3 presents Level Set Method. Section 4 literature review of LSM, and section-5 result of recent research on image segmentation using LSM Section 6 concludes the paper.
II: IMAGE SEGMENTATION
Segmentation is the process of partitioning an image into semantically interpretable regions. The purpose of segmentation is to decompose the image into parts that are meaningful with respect to a particular application. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. The result of image segmentation is a set of regions that collectively cover the entire image, or a set of contours extracted from the image. Each of the pixels in a region is similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristic.
IMAGE SEGMENTATION METHODS
Several general-purpose algorithms and techniques have been developed for image segmentation. These are listed below:
· Clustering methods
· Compression-based methods
· Histogram-based methods
· Edge detection methods
· Region growing methods
· Split-and-merge methods
· Partial differential equation-based methods
1. Parametric methods
2. Level set methods
3. Fast Marching methods
· Graph partitioning methods
· Watershed transformation
· Model based segmentation
· Semi-automatic segmentation
· Segmentation Benchmarking
· Neural networks segmentation
Several different segmentation techniques could be used to come up with similar results. The methods typically vary in speed, accuracy and robustness. In the following section various segmentation methods are studied:
1) Clustering methods
The K-means algorithm is an iterative technique that is used to partition an image into K clusters. The basic algorithm is:
(i) Pick K cluster centers, either randomly or based on some heuristic
(ii) Assign each pixel in the image to the cluster that minimizes the distance between the pixel and the cluster center
(iii) Re-compute the cluster centers by averaging all of the pixels in the cluster
(iv) Repeat steps 2 and 3 until convergence is attained (e.g. no pixels change clusters)
2) Compression based methods
Compression based methods postulate that the optimal segmentation is the one that minimizes, over all possible segmentations, the coding length of the data. The connection between these two concepts is that segmentation tries to find patterns in an image and any regularity in the image can be used to compress it. The method describes each segment by its texture and boundary shape. Each of these components is modeled by a probability distribution function and its coding length is computed as follows:
(i) The boundary encoding leverages the fact that regions in natural images tend to have a smooth contour. This prior is used by huffman coding to encode the difference chain code of the contours in an image. Thus, the smoother a boundary is the shorter coding length it attains.
(ii) Texture is encoded by lossy compression in a way similar to minimum description length (MDL) principle, but here the length of the data given the model is approximated by the number of samples times the entropy of the model. The texture in each region is modeled by a multivariate normal distribution whose entropy has closed form expression.
3) Histogram-based methods
Histogram-based methods are very efficient when compared to other image segmentation methods because they typically require only one pass through the pixels. In this technique, a histogram is computed from all of the pixels in the image, and the peaks and valleys in the histogram are used to locate the clusters in the image. Color or intensity can be used as the measure. A refinement of this technique is to recursively apply the histogram-seeking method to clusters in the image in order to divide them into smaller clusters. This is repeated with smaller and smaller clusters until no more clusters are formed. One disadvantage of the histogram-seeking method is that it may be difficult to identify significant peaks and valleys in the image. In this technique of image classification distance metric and integrated region matching are familiar. Histogram-based approaches can also be quickly adapted to occur over multiple frames, while maintaining their single pass efficiency. The histogram can be done in multiple fashions when multiple frames are considered. The same approach that is taken with one frame can be applied to multiple, and after the results are merged, peaks and valleys that were previously difficult to identify are more likely to be distinguishable.
4) Edge detection
Edge detection is a well-developed field on its own within image processing. Region boundaries and edges are closely related, since there is often a sharp adjustment in intensity at the region boundaries. Edge detection techniques have therefore been used as the base of another segmentation technique.
The edges identified by edge detection are often disconnected. To segment an object from an image however, one needs closed region boundaries. The desired edges are the boundaries between such objects.
5) Partial Differential Equation-based methods
Using a partial differential equation (PDE)-based method and solving the PDE equation by a numerical scheme, one can segment the image. Curve propagation is a popular technique in this category, with numerous applications to object extraction, object tracking, stereo reconstruction, etc. The central idea is to evolve an initial curve towards the lowest potential of a cost function, where its definition reflects the task to be addressed. As for most inverse problems, the minimization of the cost functional is non-trivial and imposes certain smoothness constraints on the solution, which in the present case can be expressed as geometrical constraints on the evolving curve.
5.1) Parametric methods
Lagrangian techniques are based on parameterizing the contour according to some sampling strategy and then evolve each element according to image and internal terms. Such techniques are fast and efficient, however the original "purely parametric" formulation (due to Kass and Terzopoulos in 1987 and known as "snakes")[9], is generally criticized for its limitations regarding the choice of sampling strategy, the internal geometric properties of the curve, topology changes (curve splitting and merging), addressing problems in higher dimensions, etc.. Nowadays, efficient "discretized" formulations have been developed to address these limitations while maintaining high efficiency. In both cases, energy minimization is generally conducted using a steepest-gradient descent, whereby derivatives are computed.
5.2) Level Set segmentation
Segmenting images with level set methods was introduced at the end of the 1980’s and was based on previous work on moving curvatures. Since then several variants and improvements have come up. Some of the improvements are aimed at speeding up the processing. Other methods have strength related to specific challenges like noise and broken edges. In the level set method, the curve is represented implicitly as a level set of a 2D scalar function referred to as the level set function which is usually defined on the same domain as the image. The level set is defined as the set of points that have the same function value. Fig1.1 shows an example of embedding a curve as a zero level set. It is worth noting that the level set function is different from the level sets of images, which are sometimes used for image enhancement. The sole purpose of the level set function is to provide an implicit representation of the evolving curve. Instead of tracking a curve through time, the level set method evolves a curve by updating the level set function at fixed coordinates through time. This perspective is similar to that of an Eulerian formulation of motion as opposed to a Lagrangian formulation, which is analogous to the parametric deformable model. A useful property of this approach is that the level set function remains a valid function while the embedded curve can change its topology.
5.3) Fast Marching methods
Fast marching method has been introduced by James A. Sethian. It has been used in image segmentation in 2006, and this model has been improved (permitting a both positive and negative speed propagation speed) in an approach called Generalized Fast Marching method
6) Watershed segmentation
Watershed segmentation uses the analogy from topography. By interpreting the gradient map of an intensity image as height values we get lines which appear to be ridges. If the contours were a terrain, falling rain would find the way from the dividing lines towards the connected catchments basin. These dividing lines are called watersheds.
III. LEVEL SET METHOD
The level set method is a numerical technique used for tracking interfaces and shapes. Level set is optimization method to extract or segment the object by its shape from an image. These interface can have sharp corners .The technique can find a wide range of application including problems in image processing, computer graphics, shape of snowflakes. Consider an image f with background and foreground. Boundaries can be detected using curve evolution. The boundary of an open domain can be represented using a curve C as the isoline of a Lipschitz continuous function:
We have to operate on the family of curves C(t) over the time t≥0 to perform curve evolution.
The positive sign indicates that the point lie inside the curve and the negative sign indicates that the point is outside the closed curve and Figure.1 shows a pictorial representation. The curve evolves in time; the value of the function at each grid point also evolves. The level set method updates the value of the function at each point over small increments of time.
In effect Φ divides the image into 3 regions, inside of the level set with positive Φ, boundary with Φ=0 and outside of the levelset with negative Φ. Then, an iterative procedure is followed, which uses an edge stopping function to decide the rate at which, the curve evolves. The evolution of curve happens in a direction normal to itself and the evolution stops when the curve meets an object or boundary. Broadly there are two approaches- Edge based and Region based
Figure 2 Level set visualization
Figure 3: flow chart of image segmentation using level set method
IV LITERATURE REVIEW
In the past two decades, active contour models (ACMs, also called snakes or deformable models) [1] have been widely used in image processing and computer vision applications, especially for image segmentation [5][9][12-13][17-18][30][34][41-42][52-53][59].
The original ACM proposed by Kass et al. [1] moves the explicit parametric curves to extract objects in images. However, the parametric ACM has some intrinsic drawbacks, such as its difficulty in handling topological changes and its dependency of parameterization [2].
The level set method later proposed by Osher and Sethian [2] implicitly represents the curve by the zero level of a high dimensional function, and it significantly improves ACM by being free of these drawbacks [2-5].
The level set methods (LSM) can be categorized into partial differential equation (PDE) based ones [8]
and variational ones [9].
The level set evolution (LSE) of PDE-based LSM is directly derived from the geometric consideration of the motion equations [6], which can be used to implement most of the parametric ACMs, such as Kass et al.’s snakes [1], region competition snakes [12], and geodesic active contours [5], etc.
The LSE of variational LSM is derived via minimizing a certain energy functional defined on the level set [9], such as Chan-Vese ACM [18], Vese and Chan’s piecewise smoothing ACM [42], local binary fitting ACM [30][41], etc.
Moreover, the variational LSM can be easily converted into PDE-based LSM by changing slightly the LSE equation while keeping the final steady state solution unchanged [7].