3D Active Meshes

Short Description

3D Active Mesh plug-in for cell segmentation and tracking in 3D images and sequences.

Documentation

Introduction

This plug-in implements the algorithm published in the following article: “Dufour, A. et al. (2011) 3-D Active Meshes: Fast Discrete Deformable Models for Cell Tracking in 3-D Time-Lapse Microscopy, IEEE Transactions in Image Processing, 20, 1925-1937″ (reprint available upon request).

Background

The principle of deformable models is to define an initial curve (2D or 3D, opened or closed) in the vicinity of an object of interest, and let this curve deform until it reaches a steady-state when it fits the boundary of the target. The curve and its deformation can be expressed mathematically in many different ways, as described below.

Curve representations

Curve representations are presented here in (more or less) chronological order (rather than by group) to give a coherent view of the evolution in the field over the last decades. This review is however not exhaustive and only gives the main lines of research for the general reader, directed toward the purpose of the plug-in (cell segmentation and tracking).

• Explicit parametric representation The original scheme (originally developed by Kass & Terzopoulos in 1987) is to represent the curve by a parametric equation. The parameters of this curve are adjusted during the deformation, and the curve is regularly reparameterized to ensure global smoothness. This model is known as the “Snake” model, since the evolution of an opened curve may mimic the undulations of a snake. Such model is fast and computationally efficient, although usually criticized for two main reasons: 1) their lack of topological flexibility (a parametric curve cannot be split), therefore a single curve must be created for each object of interest to detect; 2) the extension to 3D is quite delicate in terms of curve manipulation and reparameterization.

• Implicit level set representation Almost coincidentally, other researchers from the field of fluid dynamics (namely S. Osher and J. Sethian in 1988) have derived an alternative representation of the curve, by defining it as the zero-level of a higher-dimensional Lipschitz function. One metaphor of this representation is a flame (the fluid) burning a hole through a piece of paper. The boundary (2D) of the hole is the zero-level of the flame function (3D), and the deformation of the hole’s boundary is implicitely controlled by the motion of the flame. For this reason this model is usually termed “implicit model”. This model has received extensive attention from the community, since it solved most of the drawbacks of the Snake model: 1) the model is topology-independent (the fluid function may evolve such that the zero-level actually appears as two distinct contours), hence a single level set function may be used to detect multiple non-touching objects in the image; 2) the formalism naturally works in any dimension. Yet, these advantages also come at a significant computational cost (notably in 3D, where the level set function is 4D). Moreover, for the purpose of cell segmentation and tracking, the topological flexibility can become a drawback: indeed, since topology is uncontrolled by nature, objects moving and eventually touching over time will see their zero-level merged together, such that their identity is lost. Many methods have therefore focused on re-inserting topology control in these approaches.

• Explicit discrete representation With the improvement in computer graphics technology and in the Computer Aided Design (CAD) industry, extensive development has been conducted on discrete curve representations. The goal of these representations is to take the best of both worlds with 3 key features: 1) inherit the speed and computational efficiency of the parametric representation; 2) incorporate the topological flexibility of implicit representation; 3) rely on a discrete data structure in order to benefit from the power of graphics processing units for computation and/or rendering purposes. As a result, the computational cost in both time and memory load can be decreased by up to several orders of magnitude as compared to an equivalent level set representation.

• Graph-cut representation Graph-cut representations rely on the theory of minimal path finding in a connected graph, and has only recently been applied in the context of deformable model-based segmentation. This representation is usually compared to the level-set approach, but considers the curve as the minimum cut of a flow that connects all image pixels to either an imaginary sink or target source. The major difference with the level set models lies in the mathematical description of the curve evolution, which is discussed later below.

Curve evolution

Once the contour representation is fixed, one must choose a mathematical framework to actually drive the deformation of the curve from its initial position toward the boundary of the object of interest. Here again, several solutions are available, the most popular ones cited below in arbitrary order.

• Dynamic mass-spring systems. Such systems consider the curve to be discretized into a set of physical nodes connected with springs, and that the entire evolution of this physical system follows the Newton laws of motion. By applying attracting and repulsing forces on the various nodes of the system (using the image data to guide them in the correct direction), the curve deforms until it reaches a physical steady-state, assumed to correspond to the solution, although there is no guarantee on its exactness.

• Energy-minimizing frameworks. These frameworks rely on the definition of an energy functional that combines terms related either to the image data (usually referred to as “data attachment” terms), to geometrical properties of the curve (usually termed “regularization” terms), or to prior estimates of the solution when available. The key idea is to define the functional such that the solution of the segmentation problem (i.e. the optimal position of the curve) is a minimizer of this functional. These frameworks are particularly popular thanks to their flexibility, while minimization per se can be conducted using a wide variety of numerical schemes, one of the most popular being the Euler-Lagrange steepest gradient descent, which guarantees convergence to at least a local minimum of the functional.

• Statistical frameworks. These frameworks are very similar to the energy-minimizing ones, however the the optimal solution is defined by maximizing the probability of a given gain function, which is formed of terms analogous to those of the previous case. The advantage here is that the incorporation of shape priors is facilitated by the statistical formulation of the problem. The notion of convergence to a local minimum is complemented by a statistical measure of the correctness of fit of the original terms.

• Energy-minimizing graph-cuts. The use of graph-cuts for deformable models has mostly been motivated by the high computational cost and convergence time of energy-minimizing (ot statistical) frameworks, based on the observation that steepest gradient descent approaches may take a very high number of iterations to converge, yielding substantial computational costs, notably in the case of level set approaches. The idea here is to minimize an energy functional defined on a graph constructed from the image grid, such that each image pixel (or voxel in 3D) is connected to its neighbors by an edge with a cost, while one set of nodes are connected to an additional imaginary “source” node, and the remaining nodes to a “target” node. This graph is then cut with minimal cost using a principle of maximal flow algortithm. The advantage is a substantial gain in convergence time (the number of iterations is up to several order of magnitude lower than in Euler-Lagrange minimization), at the cost of a more complex incorporation of energy terms, which need to be expressed in terms of graph edge costs.

Plug-in description

This plug-in implements a method for cell segmentation and tracking based on an energy-minimizing framework and a discrete explicit representation of the contours via triangular meshes (see above for a theoretical background on these terms).

The energy that is minimized is based on the popular Chan-Vese-Mumford-Shah segementation model, which aims to segment the regions of an image assumed two-phase piecewise constant (constant intensity for the bacground and the object of interest). In this plug-in, the original model has been extended with the following features:

• 3D implementation using discrete triangular meshes with self-parameterization and topology control
• Multi-phase extension: the image is considered multi-phase piecewise constant, where each object of interest exhibits a constant average intensity (not necessarily equal across objects).
• Localized background estimation: the average intensity of each object of interest is assumed to be locally different from the background, which allows to cope for global background illumination artifacts.
• Additional edge term that attracts the contour along intensity gradients (i.e. edge information) whenever available.
• Time-lapse tracking: the objects are initially detected and segmented in the first frame, then for each subsequent frame, the obtained meshes are locally adapted to fit the new position and shape of each object of interest.
• Objects in contact: by segmenting each object with a dedicated mesh, objects of similar intensity coming into close vicinity remain separated, via the incorporation of a non-overlapping constraint in the evolution of the meshes.

Parameters

Coming soon.