An Efficient Algorithm for Level Set Method Preserving Distance Function

Xavier Bresson, Virginia Estellers Casas, Jean-Philippe Thiran, Dominique Zosso
Institute of Electrical and Electronics Engineers, 2012
Journal paper

Abstract

The level set method is a popular technique for tracking moving interfaces in several disciplines including computer vision and fluid dynamics. However, despite its high flexibility, the original level set method is limited by two important numerical issues. Firstly, the level set method does not implicitly preserve the level set function as a distance function, which is necessary to estimate accurately geometric features s.a. the curvature or the contour normal. Secondly, the level set algorithm is slow because the time step is limited by the standard CFL condition, which is also essential to the numerical stability of the iterative scheme. Recent advances with graph cut methods and continuous convex relaxation methods provide powerful alternatives to the level set method for image processing problems because they are fast, accurate and guaranteed to find the global minimizer independently to the initialization. These recent techniques use binary functions to represent the contour rather than distance functions, which are usually considered for the level set method. However, the binary function cannot provide the distance information, which can be essential for some applications s.a. the surface reconstruction problem from scattered points and the cortex segmentation problem in medical imaging. In this paper, we propose a fast algorithm to preserve distance functions in level set methods. Our algorithm is inspired by recent efficient $\ell^1$ optimization techniques, which will provide an efficient and easy to implement algorithm. It is interesting to note that our algorithm is not limited by the CFL condition and it naturally preserves the level set function as a distance function during the evolution, which avoids the classical re-distancing problem in level set methods. We apply the proposed algorithm to carry out image segmentation, where our methods proves to be 5 to 6 times faster than standard distance preserving level set techniques. We also present two applications where preserving a distance function is essential. Nonetheless, our method stays generic and can be applied to any level set methods that require the distance information.

Official source

https://infoscience.epfl.ch/record/169593?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Xavier Bresson, Virginia Estellers Casas, Jean-Philippe Thiran, Dominique Zosso
Institute of Electrical and Electronics Engineers, 2012
Journal paper

Abstract

Official source

https://infoscience.epfl.ch/record/169593?ln=en

About this result

Related concepts (16)

Related concepts

Related publications (10)

Related publications

Image segmentation with variational active contours

Xavier Bresson

An important branch of computer vision is image segmentation. 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. For more than a decade, a promising mathematical framework, based on variational models and partial differential equations, have been investigated to solve the image segmentation problem. This new approach benefits from well-established mathematical theories that allow people to analyze, understand and extend segmentation methods. Moreover, this framework is defined in a continuous setting which makes the proposed models independent with respect to the grid of digital images. This thesis proposes four new image segmentation models based on variational models and the active contours method. 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. The first model defined in this dissertation proposes to determine global minimizers of the active contour/snake model. Despite of great theoretic properties, the active contours model suffers from the existence of local minima which makes the initial guess critical to get satisfactory results. We propose to couple the geodesic/geometric active contours model with the total variation functional and the Mumford-Shah functional to determine global minimizers of the snake model. It is interesting to notice that the merging of two well-known and "opposite" models of geodesic/geometric active contours, based on the detection of edges, and active contours without edges provides a global minimum to the image segmentation algorithm. The second model introduces a method that combines at the same time deterministic and statistical concepts. We define a non-parametric and non-supervised image classification model based on information theory and the shape gradient method. We show that this new segmentation model generalizes, in a conceptual way, many existing models based on active contours, statistical and information theoretic concepts such as mutual information. The third model defined in this thesis is a variational model that extracts in images objects of interest which geometric shape is given by the principal components analysis. The main interest of the proposed model is to combine the three families of active contours, based on the detection of edges, the segmentation of homogeneous regions and the integration of geometric shape prior, in order to use simultaneously the advantages of each family. Finally, the last model presents a generalization of the active contours model in scale spaces in order to extract structures at different scales of observation. The mathematical framework which allows us to define an evolution equation for active contours in scale spaces comes from string theory. This theory introduces a mathematical setting to process a manifold such as an active contour embedded in higher dimensional Riemannian spaces such as scale spaces. We thus define the energy functional and the evolution equation of the multiscale active contours model which can evolve in the most well-known scale spaces such as the linear or the curvature scale space.

EPFL2005

Segmentation of diffusion weighted MRI using the level set framework

Lisa Jonasson

Medical imaging is a rapidly growing field in which diffusion imaging is a recently developed modality. This novel imaging contrast permits in-vivo measurement of the diffusion of water molecules. This is particularly interesting in brain imaging where the diffusion reveals an amazing insight into the neuronal organization and cerebral cytoarchitecture. Diffusion images contain from six up to hundreds of values in each voxel and are represented as tensor fields (Diffusion Tensor Imaging (DTI)) or as fields of functions (High Angular Resolution Diffusion (HARD) imaging). To fully extract the large amount of data contained within these images new processing and analysis tools are needed. The aim of this thesis is the development of such tools. The method we have been mainly focusing on for this purpose is the level set method. The level set method is a numerical and theoretical tool for propagating interfaces. In image processing it is used for propagating curves in 2D or surfaces in 3D for delineation of objects or for regularization purposes. In this thesis we have explored some of the numerous aspects of the level set frame work to see how the diffusion properties can be used for segmentation. For segmentation of tensor fields we have considered similarity measures for comparison of tensors. From these similarity measures several applications of the level set method have been developed for the segmentation of different structures. Different measures of similarity have been used dependent on the application. When segmenting white matter regions in DTI, the similarity measure emphasizes anisotropic regions. The segmentation algorithm itself has a very local dependence since white matter, in general fiber tracts, experiences different diffusion in different parts of the structure. The presented results show segmentations of the major fiber tracts in the brain. Other structures, such as the deep cerebral nuclei, that are mainly composed of gray matter, have more homogenous diffusion properties than white matter structures. Therefore, in these structures we maximize the internal coherence within the entire structure by using a region based approach to the segmentation problem. Segmentations of the thalamus and its nuclei as well as on tensor fields from fluid mechanics are presented. For High Angular Resolution Diffusion (HARD) images, two methods for fiber tract segmentation are presented based on different types of coherence. The coherence is either measured as the similarity between fibers obtained from a tractography algorithm, or the similarity of scalar values in a five-dimensional non-Euclidean space. The similarity between two fibers is determined by a counting strategy and is equal to the number of voxels they have in common. A spectral clustering algorithm is then used for grouping fibers with a high inter-resemblance. When segmenting white matter with the level set method, we propose to expand the space we are working in from a three-dimensional space of Orientation Distribution Functions (ODF) to a five-dimensional space of position and orientation. By a careful definition of this space and an adaptation of the level set to five dimensions the fibers tracts can be segmented as separated structures. We show some preliminary results from segmentations in this 5D space. The approaches proposed in this thesis permit a consideration of the fiber tracts and gray matter structures as an entity, allowing quantitative measures of the diffusion without losing information by simplifying the images to scalar representations.

EPFL2005

In the early stages of visual information processing one of the most fundamental and complex task is segmentation. This process is used to divide images or image sequences into meaningful regions or objects. Such a representation is definitely needed to go from the first rough description of the scene (i.e. light intensity) up to the semantic level, where one is able to discriminate shapes and other high-level visual primitives. The biological visual system performs this extremely difficult task with such ease that is still a major challenge for computer vision to reach this level of speed and accuracy. It is by now widely believed that a method inspired by biological vision has the best chances of accomplishing this goal. Therefore, our main goal in this thesis is to step on biologically inspired schemes to propose new and efficient techniques to solve the image segmentation problem. The starting point and key concept in this research, is the multiresolution paradigm. Indeed, the fact that the Human Visual System (HVS) processes the information in a multiresolution fashion is now well established. Several techniques have been introduced to model this behaviour. Scale-space is one of them and we will thus focus on such a formulation of the segmentation problem. Such a representation is composed by a stack of successive versions of the original data set at coarser scales. It is assumed that, the bigger the scale, the less information referred to local characteristics of the input data will appear. We also impose that general information applying to large scales will last through scale. Taking that into account, it is reasonable to think that local and high resolution scale information can be related to general and low resolution information. This will enable us to extract image structures. We thus propose to link the multiresolution approach to a computational model based on the analysis of the entire range of significant information across scales. The inherent multiscale image structure of the non-linear scale-space guides a coarse to fine segmentation using different strategies. The first one might be termed extrinsic because the non-linear scale-space is analyzed by an external process of linking information through scales. This leads to a completely adaptive scheme that can then be coupled to a labeling procedure in order to define a genuine segmentation. The second one could be labeled intrinsic because it adapts to the image through its inner properties and incorporate this in the labeling step of the main algorithm. These two approaches are particular examples of multiscale image segmentation. We also apply the same scale-space concept to define a segmentation variational formulation that leads to a region merging segmentation. In order to illustrate the proposed segmentation schemes, we apply our algorithms to gray-scale, noisy, color and texture images. Finally, it should be mentioned that the main problem addressed in this thesis, general image segmentation, plays an important role in the image understanding process, especially those that involve natural scenes rich in color and texture. The potential applications of the algorithms are thus numerous: medical image analysis, interactive multimedia developments, object based coding and compression, surveillance applications, image content based browsing and retrieval, etc.

EPFL2006

Image segmentation with variational active contours

Xavier Bresson

EPFL2005

Segmentation of diffusion weighted MRI using the level set framework

Lisa Jonasson

EPFL2005

EPFL2006