Project topics and materials
Get Complete Project Material File(s) Now! »
Geometric representation of deformable models
Many different geometric representations have been proposed in the deformable models literature. The interested reader may refer to [105] for a thorough review. Often, these representations are divided into two categories: “parametric” models and “geometric” models. However, we believe that these two terms are a source of confusion. First, we suggest to use “parameterized” instead of “parametric” to deal with geometric objects given by a parameterization, and to keep the term “parametric” for the families of objects indexed by a small number of parameters. Second, in the literature, “geometric” models often refer exclusively to the level set representation. As a result, some representations like unstructured surface meshes would be classified as “parametric”, whereas they are neither parametric nor parameterized. . .
In this thesis, we make a distinction between “explicit” and “implicit” representations. Explicit models are given through a set of coordinates while implicit models are defined as the zero set of a higher-dimensional scalar function. In parallel, we make a difference between “geometric” and “non-geometric” evolution laws. Geometric evolutions are not dependent on a particular parameterization. They find their origin in the theory of curve evolution [54]. In this type of evolution, the velocity field of the model typically depends on intrinsic geometric quantities such as normal, curvature, and on the input data.
Geometric evolutions can be implemented very naturally with a level set representation, but the use of other representations, including explicit models, is possible. Choosing an explicit or an implicit representation to implement a geometric evolution is closely related to choosing a Lagrangian or an Eulerian perspective.
Explicit models
Parameterization
Parameterized curves and surfaces are an important type of explicit models. This kind of representation is the one proposed in the original snake model of Kass, Witkin and Terzopoulos [77]. A variety of other parameterized representations are found in the litera-ture, either based on some basis functions (finite elements [32, 96], B-splines [132], Fourier harmonics [151], etc.), or on a parametric family (superquadrics [161, 9, 10]).
A typical problem of parameterized deformable models is that their evolution and the final reconstruction are dependent on the parameterization of the initial shape. To be more exact, this problem is related to the definition of the energy functional rather than to the geometric representation itself: in most cases, the metric distortions between the parameterization space and the model are disregarded. As a consequence, the energy is not intrinsic to the model.
Not all explicit models are parameterized. Oriented particle systems [159] and unstruc-tured meshes (triangulated surfaces [104], simplex meshes [39], polyhedrons [147]) do not have an underlying parameterization.
Topology
A serious limitation of most explicit models is that their topology cannot change during the evolution to fit the data topology. Several attempts have been made to overcome this problem. McInerney and Terzopoulos [98, 99] propose topology adaptative deformable curves and triangulations, called T-snakes and T-surfaces. During the evolution, the model is periodically resampled by computing its intersections with a simplicial decomposition of space. A labeling of the vertices of the simplicial grid as inside or outside of the model is maintained. Besides being computationally expensive, this procedure imposes a fixed uniform spatial resolution. Also, not all motions are admissible: this approach only works when the model inflates or deflates everywhere.
Lachaud and Montanvert [85] use the concept of δ-triangulation. A length parameter δ is used to control the sampling of the triangulation and to detect self-intersections, by monitoring the distance between pairs of neighbor and non-neighbor vertices. This approach is costly, even when optimizing the computations with an octree structure.
Delingette and Montagnat [39, 40] propose to modify the topology of an evolving sim-plex mesh with some elementary topological operators, but their approach needs manual interaction in 3D.
Thus, a fully automatic and efficient handling of topology changes with explicit models, in three dimensions and more, remains an open issue. This is one important reason why the level set representation has received much interest in the deformable models literature.
Implicit models
Implicit models are not limited to the level set method [112]. Algebraic polynomial surfaces [160] and implicit superquadrics/hyperquadrics [9, 30] also fall into this category. However, among implicit models, the level set method is by far the most powerful. It is applicable to a considerably wider range of applications, because it can handle complex geometries while the others are limited to a small family of shapes.
The level set method, introduced by Osher and Sethian in [112] (a similar work in the area of fluid mechanics [41, 42] has recently surfaced), is an established technique to represent moving interfaces in two or more dimensions. Basically, it consists in representing the interface implicitly as the zero level set of a higher-dimensional scalar function. The movement of the interface can be cast as an evolution of the embedding level set function by an Eulerian PDE (partial differential equation).
On the one hand, this approach has several advantages over an explicit Lagrangian rep-resentation of the interface: no parameterization is needed, topology changes are handled automatically, any number of dimensions is accommodated, intrinsic geometric properties such as normal or curvature can be computed easily from the level set function. Last but not least, the theory of viscosity solutions [34] provides robust numerical schemes and strong mathematical results to deal with the evolution PDE.
On the other hand, several serious shortcomings limit the applicability of the level set method. First, the higher dimensional embedding makes the level set method much more expensive computationally than explicit representations. Much effort has been done to alleviate this drawback, leading to the narrow band methodology [1] and more recently to the PDE-based fast local level set method [118].
Also, in its basic formulation, the level set method can only represent manifolds of codimension one without borders, such as closed curves in R2 and closed surfaces in R3. Several approaches have been proposed to handle a codimension strictly greater than one. Ambrosio and Soner [5] propose to evolve an hypersurface corresponding to an -neighborhood of the manifold. For instance, in the case of a curve in R3, it consists in evolving a tubular neighborhood of the curve which has a small radius . This idea was used in [90] to segment blood vessels from medical images. A drawback of this approach is that the manifold of interest cannot be accurately positioned. A more principled approach by Burchard, Cheng, Merriman and Osher [20] consists in representing the curve as the intersection of two hypersurfaces, and to express its motion as the evolution of two level set functions. In [59], the author investigates the extension of this idea to any codimension k by simultaneously evolving k level set functions, at the expense of facing increasing numerical difficulties. A similar idea is proposed by Solem and Heyden [149] to represent surfaces with borders with the level set method.
Some other shortcomings of the level set method have recently surfaced. One is inti-mately related to the implicit point of view and to the absence of parameterization: the point-wise correspondence is lost during the evolution. In other words, we do not know how each point and each part of the interface moves. This is not a surprise, since the level set function conveys a purely geometric description of the interface. More generally, it is not possible to handle some data associated with the moving interface, in other words some interfacial data, in the traditional level set framework. This considerably restricts the range of possible applications. In Chapter 3, we propose a method, based on a system of coupled Eulerian PDEs, to overcome this limitation.
The ability to automatically handle topology changes is a long claimed advantage of the level set method over explicit deformable models. But it may not be desirable in some applications where some prior knowledge of the target topology is available. This is typically the case in biomedical image segmentation, where the topology of the organs and their mutual topological relations is prescribed by anatomical knowledge. Chapter 4 deals with some methods, inspired by digital topology, to exert a control on the topology during a level set evolution.
Minimization of the energy functional
The design of the evolution equation driving the motion of deformable models follows two main approaches. In the variational formulation, the problem is cast as the minimization of an energy functional. The latter is defined so that low-energy configurations indicate a good fit with the input data and the prior information (typically some regularity assump-tions), and the solution is defined as a shape achieving a global minimum of the energy. In the dynamic force formulation, the motion is designed ad hoc, often as a combination of internal forces, defined from the model itself and dedicated to keep the model smooth during the deformation, and of external forces, defined from the input data. The solution is seen as an equilibrium of the forces.
In this thesis, we favor the variational formulation, because it has several advantages over the dynamic force formulation. First, it appears less empirical and often enables a better understanding of the model. This is particularly true when the energy func-tional derives from a statistical modeling, such as the maximum a posteriori (MAP) of a Bayesian formulation [157]. Second, in some cases, the existence of a global minimum of the energy and the well-posedness of the minimization procedure can be mathematically proven. Finally, once the variational problem is defined, it can be tackled with a variety of minimization procedures, depending on the available prior information and on the allo-cated computational time. In this section, we deal with the choice of such a minimization procedure.
In general, an exact minimization of the energy functional is computationally unfeasible due to the huge number of unknowns. Simulated annealing [152] and dynamic programming [6] have been proposed to compute a global minimum, but the former is very slow in practice and the latter only applies to a particular form of energy functionals. More recently, graph cuts have emerged as a powerful energy minimization method allowing to find a global minimum or a strong local minimum. In the last few years, this method has been successfully applied to several problems in computer vision, including multi-view stereovision [80] and image segmentation [18]. However, it has two severe limitations: it cannot be applied to any energy function [81], and, when applicable, is computationally expensive.
Hence, in most cases, a suboptimal strategy is adopted, based on the calculus of varia-tions. A necessary condition of optimality deduced from the energy functional, called the Euler-Lagrange equation, is solved instead. The Euler-Lagrange equation characterizes the local minima and the local maxima of the energy. Just like the original variational prob-lem, it cannot be solved exactly, so an evolutive method starting from an initial guess is necessary. As a result, an artificial notion of time is added to the problem. This is the core principle of the deformable models framework: the resolution of the problem translates into the time evolution of a geometric object.
When using parameterized deformable models, the resolution of the Euler-Lagrange equation is typically done by updating the model parameters with a gradient descent or with fast convergence numerical schemes such as the conjugate gradient method, the Newton method or the Levenberg-Marquardt method. These evolutions are non-geometric, i.e. they are dependent on a parameterization of the model, so they fall out of the scope of this thesis.
Another minization procedure was pioneered by Chan and Vese in [25]. It consists in using the level set method at the same time as a geometric representation and as an optimization framework. In other words, the energy functional is defined directly from the level function φ, and the minimization is also performed with respect to φ. In this approach, the integral of a quantity f along the boundary of the model or over the inside/outside region write with the Dirac distribution δ and the Heaviside function H:
Z Γ f (x) dx = ZRn δ(φ(x)) f (x) krφ(x)k dx , (2.1)
Z in f (x) dx = Z Rn [1 − H(φ(x))] f (x) dx , (2.2)
Z out f (x) dx = ZRn H(φ(x)) f (x) dx . (2.3)
This approach has become popular in image segmentation [25, 170, 114, 56, 130]. However, it raises several conceptual and practical problems. First, it is specific to a particular geometric representation. Second, the need for an -regularized version of δ and H in the implementation is quite inelegant. Last but not least, the resulting evolution is non-geometric. It depends on the initial values of φ off the zero level. Disconnected components of the model can appear, which is definitely not compatible with a curve evolution.
Moreover, a mistake commonly done with this approach is to assume the preservation of the signed distance property when computing the variation of the energy with respect to a variation of φ. For example, in [56], the authors propose to segment the cerebral cortex with two coupled deformable models, and with a prior on their mutual distance. This distance is taken as the absolute value of the signed distance function representing each interface. Because of the aforementioned abuse, the derivation of the energy functional in this work is not exact. A derivation along the space of signed distance functions is neither possible, because this space is not a well-behaved manifold.
In this thesis, we focus on a minimization procedure called geometric gradient flows. It is the geometric evolution obtained by following the direction of steepest descent of an intrinsic energy. Its mathematical meaning is detailed in Chapter 5. For instance, the minimization of the area of the model leads to the well-known motion by mean curvature [54]. Another important geometric gradient flow is obtained by minimizing the area of the model in a Riemannian space with an image-based metric: it is the geodesic active contours approach proposed by Caselles, Kimmel and Sapiro in [24] for the detection of image boundaries.
Due to the highly non-convex nature of most energy functionals, geometric gradient flows are very likely to be trapped in a local minimum. Also, this local minimum depends on the position of the initial shape. If the latter is far from the expected final configu-ration, the evolution may be trapped in a completely irrelevant state. This sensitivity to initial conditions seriously limits the applicability and efficiency of the deformable models framework.
There are essentially two ways of dealing with this problem: positioning the initial model very close to the expected final configuration, or using a multiresolution coarse-to-fine strategy, in other words running the optimization on a series of smoothed and subsampled models and input data. In Chapter 5, we pioneer a third way to tackle the problem of unwanted local minima: the careful design of new geometric minimizing flows.
Major trends in the design of the energy functional
Image segmentation
The many deformable models methods dedicated to image segmentation can be di-vided into two categories: boundary-based methods and region-based methods. Whereas boundary-based methods only rely on the gradient of the image at the current position of the model, region-based methods use global intensity information of the different image segments. We also review some important works on introducing prior shape information in the extraction process, in order to cope with the highly ambiguous nature of the image segmentation problem. Note that boundary-based information, region-based information and complex prior information can advantageously be combined in a same energy func-tional, as in [70]. Here, for sake of clarity, we present these components separately. The reader may also refer to [174, 97] for some specific surveys on deformable models in medical image segmentation.
Boundary-based methods
The original snake model of Kass, Witkin and Terzopoulos [77] falls into this category. This seminal work proposes to find the boundaries of an image I : Ω ⊂ R2 → R by moving a parameterized curve C : [0, 1] → Ω under the influence of some internal and external forces deriving from the minimization of the following energy functional:
E(C) = Z 0 1 α(p)|C0(p)|2dp + Z 0 1 β(p)|C00(p)|2dp + λ Z 0 1 P (C(p)) dp . (2.4)
| {z } | {z }
Eint(C) Eext(C)
The internal energy accounts for the elasticity and the rigidity of the curve, which can be locally modulated with the weighting parameters α(p) and β(p). The external energy is the integral along the curve of a potential function P which takes smaller values at locations of high image gradient. This approach yields a remarkable robustness to noise and missing data. However, it has important limitations. First, as we mentioned earlier, the evolution and the results are dependent on the parameterization, because the energy is not intrinsic to the curve. In (2.4), this dependency is visible in the derivatives of C and in the integrals with respect to the parameter of the curve. To make the formulation intrinsic, an arc-length param-eterization ought to be maintained throughout the evolution, which the above approach cannot achieve. Second, it is very sensitive to initialization. Due to the local relevance of gradient information, it may easily converge towards false edges if the initial shape is not very close to the desired configuration.
Several extensions have been proposed in the literature to overcome these limita-tions. The parameterization independence was achieved concurrently by several authors [23, 29, 94] with some geometric evolutions, deriving from the mean curvature flow, and implemented with the level set method. A balloon force that can either inflate or deflate the model was proposed by Cohen in [31] to remove the requirement to initialize the model near the desired object boundaries. When combining these two approaches, the evolution of the model Γ is of the form ∂Γ = g(−H + c) N . (2.5)
In the above equation, N is the outward normal vector, H is the mean curvature of the model, c is the amplitude of the balloon force, and g is a positive function which takes smaller values at features of interest. For instance, if the model should stop on the edges of the image, g is generally defined such that g → 0 if krIk → +∞, (2.6) g → 1 if krIk ≈ 0.
The flow (2.5) and the associated level set evolution equation apply to any number of dimensions. Γ may denote a curve in 2D, a surface in 3D, and so on. Below, let n be the number of dimensions. A problem with this approach is that the model may slow down but not completely stop on low contrast edges. This is often referred as the leakage problem. Also, (2.5) does not derive from a variational formulation.
A significant step was made with the geodesic active contours method proposed by Caselles, Kimmel and Sapiro in [24] and by Kichenassamy et al. in [78, 179]. It is based on the minimization of the following intrinsic energy functional: E(Γ) = g(x) dx , (2.7) where dx denotes the area element of the model (its length in 2D, its area in 3D, and so on). Interestingly, this energy can be interpreted as the geodesic area of the model in a Riemannian space with metric g. The associated geometric gradient flow, given by ∂Γ = [−rg • N − (n − 1)gH] N , (2.8) is more robust to low contrast edges than the previous approach, due to the stopping term rg • N that pulls back the model if it passes the boundary. However, the attraction range is still limited, due to the local relevance of gradient information. As a result, the model has difficulties to deform into large concavities.
To address this problem, Siddiqi et al. propose area and length minimizing flows [146]. Xu and Prince work out a new force called gradient vector flows [176]. Their approach consists in smoothing the gradient field of an edge map of the image with a non-linear PDE, thereby extending the attraction range of image boundaries to the whole image domain.
Despite significant improvements, boundary-based methods still require an accurate manual initialization. This limitation has motivated the emergence of region-based meth-ods.
Region-based methods
A popular work in this category is the active contours without edges method proposed by Chan and Vese in [25]. This approach derives from the minimization of the Mumford-Shah functional [108] with the level set based optimization procedure discussed in Section 2.2. A partitioning of the image in 2n regions assuming to have a constant intensity is performed by evolving n level set functions. The regions are tagged by the different sign combinations of the level set functions. In the simplest case of bi-partitioning, the energy functional writes:
E(φ, c1, c2) = |I(x) − c1|2 H(φ(x)) dx + |I(x) − c2|2 [1 − H(φ(x))] dx
Ω Ω Z + λ δ(φ(x)) krφ(x)k dx , (2.9) Ω
where H and δ denote the usual Heaviside and Dirac functions. c1 and c2 are the estimated intensity constants in the two regions. Their optimal value at constant φ are the empirical intensity means in the corresponding regions. In [170], the same authors propose an extension of this approach to piecewise smooth images.
Rousson, Paragios and Deriche [114, 130, 115] embed region-based segmentation in a Bayesian formulation. The energy functional originates from the maximization of the posterior probability of the model. This is known as a maximum a posteriori (MAP) tech-nique. The intensity statistics of the different regions are modeled by Gaussian densities or mixtures of Gaussian densities. These statistics are either learned offline or iteratively reestimated with an expectation-maximization (EM) algorithm.
In parallel to these approaches relying on a level set based optimization procedure, very similar approaches relying on geometric gradient flows have been proposed [190, 165, 71]. In Chapter 7, we combine such a region-based image segmentation method with the level set method under topology control of Chapter 4 to extract several head tissues from magnetic resonance imaging (MRI).
Table of contents :
1 Introduction (version francaise)
1.1 Representation geometrique des modeles deformables
1.1.1 Modeles explicites
1.1.2 Modeles implicites
1.2 Minimisation de la fonctionnelle d’energie
1.3 Tendances majeures dans l’elaboration de la fonctionnelle d’energie
1.3.1 Segmentation d’images
1.3.2 Stereovision multi-cameras
1.4 Contributions de cette these
1.4.1 Contributions methodologiques
1.4.2 Contributions appliquees
1.4.3 Contributions logicielles
2 Introduction
2.1 Geometric representation of deformable models
2.1.1 Explicit models
2.1.2 Implicit models
2.2 Minimization of the energy functional
2.3 Major trends in the design of the energy functional
2.3.1 Image segmentation
2.3.2 Multi-view stereovision
2.4 Contributions of this thesis
2.4.1 Methodological contributions
2.4.2 Applied contributions
2.4.3 Software contributions
3 Maintaining the Point Correspondence in the Level Set Framework
3.1 Motivation
3.2 Methods
3.2.1 Previous work on region tracking
3.2.2 Previous work on transport and diusion of a material quantity
3.2.3 LSID: Level sets with some interfacial data
3.2.4 LSPC: Level sets with a point correspondence
3.3 Numerical algorithms
3.3.1 Level set reinitialization and data extension
3.3.2 Keeping the point correspondence onto the initial interface
3.3.3 Finite-dierence schemes
3.3.4 Overview of the algorithm
3.4 Experimental results
3.4.1 Denition of the error measures
3.4.2 2D experiments
3.4.3 3D experiments
3.4.4 Comments on the errors
3.5 Contributions of this chapter
4 Controlling Topology Changes in the Level Set Framework
4.1 Background
4.1.1 Topology
4.1.2 Digital topology
4.1.3 The topology preserving level set method
4.2 The topology preserving nested level set method
4.2.1 Digital topology criterion
4.2.2 Description of the algorithm
4.3 The genus preserving level set method
4.3.1 From simple points to multisimple points
4.3.2 Description of the algorithm
4.4 Experimental results
4.4.1 Synthetic data
4.4.2 Real data
4.5 Contributions of this chapter
5 Improving the Robustness to Local Minima with Spatially Coherent Minimizing Flows
5.1 Motivation
5.2 Abstract study
5.2.1 Designing new inner products
5.2.2 Designing new minimizing
5.3 Spatially coherent minimizing
5.3.1 The H1 gradient
5.3.2 Motion decomposition
5.3.3 Intrinsic Gaussian smoothing
5.4 Experimental results
5.4.1 Shape warping
5.4.2 Tracking
5.5 Contributions of this chapter
II Applications
6 Area Preserving Cortex Unfolding
6.1 Motivation
6.2 Area preserving surface motion
6.2.1 The total, local and relative area preserving conditions
6.2.2 Designing a relative area preserving tangential motion
6.2.3 The area relaxation term
6.2.4 Numerical methods
6.3 Experimental results
6.3.1 Synthetic data
6.3.2 Real data
6.4 Contributions of this chapter
7 Head Segmentation from MRI under Topological Constraints
7.1 Motivation
7.1.1 Problem statement
7.1.2 Previous work
7.1.3 Goals of our approach
7.2 Methods
7.2.1 Hidden Markov random eld classication
7.2.2 Topology preserving nested level sets
7.2.3 Bayesian region-based deformable models evolution
7.3 Experimental results
7.4 Contributions of this chapter
8 Multi-View Stereo Reconstruction and Scene Flow Estimation with a Global Image-Based Matching Score
8.1 Introduction
8.1.1 Problem statement
8.1.2 Common photometric and geometric assumptions used for shape and motion estimation
8.1.3 Previous work on multi-view complete stereovision
8.1.4 Previous work on scene ow estimation
8.1.5 Motivations of our approach
8.2 Minimizing the prediction error
8.2.1 Stereovision
8.2.2 Scene
8.3 Some similarity measures
8.3.1 Cross correlation
8.3.2 Mutual information
8.4 Experimental results
8.4.1 Stereovision
8.4.2 Stereovision + scene
8.5 Contributions of this chapter
Conclusion
Conclusion (version francaise)
Appendices
A Formulas of Geometric and Dierential Calculus
A.1 Some useful identities of intrinsic dierential geometry
A.2 Some useful expressions for implicit interfaces
B Numerical Schemes
B.1 Evolution schemes
B.1.1 Normal propagation
B.1.2 Passive advection
B.1.3 Mean curvature motion
B.1.4 Reinitialization
B.1.5 Extension
B.2 High-order WENO nite-dierence schemes
B.2.1 Third-order WENO scheme
B.2.2 Fifth-order WENO scheme
B.3 Finite-dierence discretization of the Laplace-Beltrami operator
C Publications of the Author
Bibliography
