> > Variational Methods in Shape Analysis
Cite | History | Comment | Print | References | Image Gallery | Hide Links
FREE ARTICLE

Variational Methods in Shape Analysis

Abstract

The concept of a shape space is linked both to concepts from geometry and from physics. On one hand, a path-based viscous flow approach leads to Riemannian distances between shapes, where shapes are boundaries of objects that mainly behave like fluids. On the other hand, a state-based elasticity approach induces a (by construction) non-Riemannian dissimilarity measure between shapes, which is given by the stored elastic energy of deformations matching the corresponding objects. The two approaches are both based on variational principles. They are analyzed with regard to different applications, and a detailed comparison is given.

Introduction

The analysis of shapes as elements in a frequently infinite-dimensional space of shapes has attracted increasing attention over the last decade. There are pioneering contributions in the theoretical foundation of shape space as a Riemannian manifold as well as path-breaking applications to quantitative shape comparison, shape recognition, and shape statistics. The aim of this chapter is to adopt a primarily physical perspective on the space of shapes and to relate this to the prevailing geometric perspective. Indeed, we here consider shapes given as boundary contours of volumetric objects, which consist either of a viscous fluid or an elastic solid.

In the first case, shapes are transformed into each other via viscous transport of fluid material, and the flow naturally generates a connecting pathin the space of shapes. The viscous dissipation rate - the rate at which energy is converted into heat due to friction - can be defined as a metric on an associated Riemannian manifold. Hence, via the computation of shortest transport paths one defines a distance measure between shapes.

In the second case, shapes are transformed via elastic deformations, where the associated elastic energy only depends on the final stateof the deformation and not on the path along which the deformation is generated. The minimal elastic energy required to deform an object into another one can be considered as a dissimilarity measure between the corresponding shapes.

In what follows we discuss and extensively compare the path-based and the state-based approach. As applications of the elastic shape model, we consider shape averages and a principal component analysis of shapes. The viscous flow model is used to exemplarily cluster 2D and 3D shapes and to construct a flow type nonlinear interpolation scheme. Furthermore, we show how to approximate the viscous, path-based approach with a time-discrete sequence of state-based variational problems.

Background A review of different shape space concepts

The structure of shape spaces and statistical analyses of shapes have been examined in various settings, and applications range from the computation of priors for segmentation [16, 43, 17] and shape classification [25, 50, 48, 44] to the construction of standardized anatomical atlases [37, 66, 14]. Among all existing approaches, a number of different concepts of a shape are employed, including landmark vectors [16, 39], planar curves [41, 84, 52], surfaces in R3 [25, 40, 24], boundary contours of objects [44, 31, 67], multiphase objects [83] as well as the morphologies of images [22].

The analysis of a shape space is typically based on a notion of a distance or dissimilarity measure d( ⋅, ⋅) between shapes [50, 31, 67, 10, 54, 51], whose definition frequently takes a variational form. This distance can be used to define an average [27, 67] or a median [28, 4] of given shapes according to for p = 1 and p = 2, respectively (cf. Sect. 4.1.1). Likewise, shape variations can be obtained by a principal component analysis (PCA, cf. Sect. 4.1.2) or a more general covariance analysis in a way which is consistent with the dissimilarity measure between shapes [11, 16, 27, 68]. From the conceptional point of view, one can distinguish two types of these dissimilarity or distance measures which may be characterized as rather state based or path based, respectively. While the first approach is independent of the notion of paths of shapes, the latter distance definition requires the computation of an optimal, connecting path in shape space. In some cases, both concepts coincide: The Euclidean distance between two points, e.g., can equivalently be interpreted in a state-based manner as the norm of the difference vector or as the length of the shortest connecting path (we shall provide a physical interpretation for each case in Sect. 3.1).

The notion of a shape space was already introduced by Kendall in 1984 [39], who considers shapes as k-tuples of points in Rd , endowed with the quotient metric of Rkd with respect to similarity transforms. Often, however, a shape space is just modeled as a linear vector space which is not invariant with respect to shift or rotation a priori. In the simplest case, such a shape space is made up of vectors of landmark positions, and distances between shapes can be evaluated in a state-based manner as the Euclidean norm of their difference. Chen and Parent [12] investigated averages of 2D contours already in 1989. Cootes et al. perform a PCA on training shapes with consistently placed landmarks to obtain priors for edge-based image segmentation [16]. Hafner et al. use a PCA of position vectors covering the proximal tibia to reconstruct the tibia surface just from six dominant modes [35]. Perperidis et al. automatically assign consistent landmarks to training shapes by a non-rigid registration as a preprocessing step for a PCA of the cardiac anatomy [63]. Söhn et al. compute dominant eigenmodes of landmark displacement on human organs, also using registration for preprocessing [73].

As an infinite-dimensional vector space, the Lebesgue-space L 2has served as shape space, where again shape alignment is a necessary preprocessing step. Leventon et al. identify shapes with their signed distance functions and impose the Hilbert space structure of L 2on them to compute an average and dominant modes of variation [43]. Tsai et al. apply the same technique to 3D prostate images [79]. Dambreville et al. also compute shape priors, but using characteristic instead of signed distance functions [19].

A more sophisticated state-based shape space is obtained by considering shapes as subsets of an ambient space with a metric d( ⋅, ⋅) and endowing them with the Hausdorff distance

between any two shapes . Charpiat et al. employ smooth approximations of the Hausdorff distance based on a comparison of the signed distance functions of shapes [10]. For a given set of shapes, the gradient of the shape distance functional at the average shape is regarded as shape variation of the average and used to analyze its dominant modes of variation [11]. Frame indifference is mimicked by an inner product that weights rotations, shifts, scalings, and the orthogonal complement to these transformations differently. Charpiat et al. also consider gradient flow morphing from one shape onto another one which can be regarded as a means to obtain meaningful paths even in shape spaces with state-based distance measures.

An isometrically invariant distance measure between shapes (or more general metric spaces) that is also not based on connecting paths is provided by the Gromov-Hausdorff distance, which can be defined variationally as
where is a distance measure between points in . The Gromov-Hausdorff distance represents a global, supremum-type measure of the lack of isometry between two shapes. Memoli and Sapiro use this distance for clustering shapes described by point clouds, and they discuss efficient numerical algorithms to compute Gromov-Hausdorff distances based on a robust notion of intrinsic distances on the shapes [50]. Bronstein et al. incorporate the Gromov-Hausdorff distance concept in various classification and modeling approaches in geometry processing [6]. Memoli investigates the relation between the Gromov-Hausdorff distance and the Hausdorff distance under the action of Euclidean isometries as well as L p -type variants of the Gromov-Hausdorff distance [49].

In [46], Manay et al. define shape distances via integral invariants of shapes and demonstrate the robustness of this approach with respect to noise.

Another distance or dissimilarity measure which also measures the lack of isometry between shapes can be obtained by interpreting shapes as boundaries of physical objects and measuring the (possibly nonlinear) deformation energy of an elastic matching deformation ϕ between two objects [67, 36]. Since, by the axiom of elasticity, this energy solely depends on the original and the final configuration of the deformed object but not on the deformation path, the elastic dissimilarity measure can clearly be classified as state based (as will be detailed in Sect. 3.2.2). This physical approach comes along with a natural linearization of shapes via boundary stresses to perform a covariance analysis [68] and will be presented in Sect. 4.1. Pennec et al. define a nonlinear elastic energy as the integral over the ambient space of an energy density that depends on the logarithm of the Cauchy-Green strain tensor [62, 61], which induces a symmetric state-based distance.

Typical path-based shape spaces have the structure of a Riemannian manifold. Here, the strength of a shape variation is measured by a Riemannian metric, and the square root of the Riemannian metric evaluated on the temporal shape variation is integrated along a path of shapes to yield the path length. The length of the shortest path between two shapes represents their geodesic distance d( ⋅, ⋅). Averages are obtained via the Fréchet mean [30], which was further analyzed by Karcher [38]. There is also a natural linear representation of shapes in the tangent space at the Fréchet mean via the logarithmic map, which enables a PCA.

A Riemannian shape space which might still be regarded as rather state- than path-oriented is given by the space of polygonal medial axis representations, where each shape is described by a polygonal lattice and spheres around each vertex [87]: Here, the Lie group structure of the medial representation space can be exploited to approximate the Fréchet mean as exponential map of the average of the logarithmic maps of the input. Fletcher et al. perform a PCA on these log-maps to obtain the dominant geometric variations of kidney shapes [27] and brain ventricles [26]. Fuchs and Scherzer use the PCA on log-maps to obtain the covariance of medial representations, and they use a covariance-based Mahalanobis distance to impose a new metric on the shape manifold. This metric is employed to obtain priors for edge-based image segmentation [32, 33].

Kilian et al. compute and extrapolate geodesics between triangulated surfaces of fixed mesh topology, using isometry invariant Riemannian metrics that measure the local distortion of the grid [40]. Eckstein et al. employ different metrics in combination with a smooth approximation to the Hausdorff distance to perform gradient flows for shape matching [24]. Liu et al. use a discrete exterior calculus approach on simplicial complexes to compute geodesics and geodesic distances in the space of triangulated shapes, in particular taking care of higher genus surfaces [45].

An infinite-dimensional Riemannian shape space has been developed for planar curves. Klassen et al. propose to use as a Riemannian metric, the L 2-metric on variations of the direction or curvature functions of arclength-parameterized curves. They implement a shooting method to find geodesics [41], while Schmidt and Cremers present an alternative variational approach [70]. Srivastava et al. assign different weights to the L 2-metric on stretching and on bending variations and obtain an elastic model of curves [75]. Michor and Mumford examine Riemannian metrics on the manifold of smooth regular curves [51]. They show the standard L 2-metric in tangent space, leading to arbitrarily short geodesics and hence employ a curvature-weighted L 2-metric instead. Yezzi and Mennucci resolved the problem taking into account the conformal factor in the metric [84]. Sundaramoorthi et al. use Sobolev metrics in the tangent space of planar curves to perform gradient flows for image segmentation via active contours [76]. Michor et al. discuss a specific metric on planar curves, for which geodesics can be described explicitly [52]. In particular, they demonstrate that the sectional curvature on the underlying shape space is bounded from below by zero, which points out a close relation to conjugate points in shape space and thus to only locally shortest geodesics. Finally, Younes considers a left-invariant Riemannian distance between planar curves by identifying shapes with elements of a Lie group acting on one reference shape [85].

When warping objects bounded by shapes in Rd , a shape tube in Rd + 1 is formed. Delfour and Zolésio [20] rigorously develop the notion of a Courant metric in this context. A further generalization to classes of non-smooth shapes and the derivation of the Euler-Lagrange equations for a geodesic in terms of a shortest shape tube is investigated by Zolésio in [88].

Dupuis et al. [23] and Miller et al. [54, 53] define the distance between shapes based on a flow formulation in the embedding space. They exploit the fact that in case of sufficient Sobelev regularity for the motion field von the whole surrounding domain Ω, the induced flow consists of a family of diffeomorphisms. This regularity is ensured by a functional ∫0 1∫ Ω Lv⋅v dx dt, where Lis a higher-order elliptic operator [76, 85]. Geometrically, ∫ Ω Lv⋅v dxis the underlying Riemannian metric, and we will discuss related, path-based concepts in Sect. 3.2.1. Under sufficient smoothness assumptions, Beg et al. derive the Euler-Lagrange equations for the diffeomorphic flow field [3]. To compute geodesics between hypersurfaces in the flow of diffeomorphism framework, a penalty functional measures the distance between the transported initial shape and the given end shape. Vaillant and Glaunès [80] identify hypersurfaces with naturally associated two forms and used the Hilbert space structures on the space of these forms to define a mismatch functional. The case of planar curves is investigated under the same perspective by Glaunès et al. in [34]. To enable the statistical analysis of shape structures, parallel transport along geodesics is proposed by Younes et al. [86] as the suitable tool to transfer structural information from subject-dependent shape representations to a single template shape.

In most applications, shapes represent boundary contours of physical objects. Fletcher and Whitaker adopt this viewpoint to develop a model for geodesics in shape space which avoids overfolding [29]. Fuchs et al. [31] propose a Riemannian metric on a space of shape contours, motivated by linearized elasticity. This metric can be interpreted as the rate of physical dissipation during the deformation of a viscous liquid object [83, 82] and will be elaborated in Sect. 4.2.

Finally, a shape space is sometimes understood as a manifold, learnt from training shapes and embedded in a higher-dimensional (often linear) space. Many related approaches are based on kernel density estimation in feature space. Here, the manifold is described by a probability distribution in the embedding space, which is computed by mapping points of the embedding space into a higher-dimensional feature space and assuming a Gaussian distribution there. In general, points in feature space have no exact preimage in shape space, so that approximate preimages have to be obtained via a variational formulation [64]. Cremers et al. use this technique to obtain 2D silhouettes of 3D objects as priors for image segmentation [17]. Rathi et al. provide a comparison between kernel PCA, local linear embedding (LLE), and kernel LLE (kernel PCA only on the nearest neighbors) [65]. Thorstensen et al. approximate the shape manifold using weighted Karcher means of nearest neighbor shapes obtained by diffusion maps [77].

Mathematical Modeling and Analysis

Recalling the Finite-Dimensional Case

At first, let us investigate distances and their relation to concepts from physics in the simple case of Euclidian space. In Euclidean space, shortest paths are straight lines, and they are unique, so that the distance computation involves only the states of the two end points: The geodesic distance between any two points x1,x2∈Rd is given by the norm of the difference, ∥ x 2 − x 1 ∥ 2, which implies the equivalence of the state-based and the path-based perspective. A corresponding physical view might be the following. Considering that - by Hooke's law - the stored elastic energy of an elastic spring extended from x 1to x 2is given by for the spring constant C, the distance can be interpreted in a state-based manner as the square root of the elastic spring energy (Fig. 1). Likewise, from a path-based point of view, the minimum dissipated energy of a dashpot which is extended from x 1to x 2at constant speed within the fixed time interval [0, 1] reads Diss = ∫0 12μv 2 2 dt = 2μx 2 − x 1 2 2, where 2μ is the dashpot parameter and the velocity is given by v = x 2 − x 1. Using this physical interpretation, we can express for instance the arithmetic mean of a given set of points x1,...,xn∈Rd either as the minimizer of the total elastic deformation energy in a system, where the average xis connected to each x i by elastic springs or as the minimizer of the total viscous dissipation when extending dashpots from x i to x.
Fig. 1 The force Fof an elastic spring between x 1and x 2is proportional to (x 2 − x 1), as well as the force Fof a dashpot which is extended from x 1to x 2within time 1 at constant velocity v. The spring energy reads and the dashpot dissipation Diss = ∫ \nolimits \nolimits F⋅v dt = 2μx 2 − x 1 2 2

Before we investigate the same concepts on more general Riemannian manifolds, let us briefly recall some basic notation. A Riemannian manifold is a set ℳthat is locally diffeomorphic to Euclidean space. Given a smooth path x(t) ∈ ℳ, t ∈ [0, 1], we can define its derivative at time tas a tangent vector to ℳat x(t). The vector space of all such tangent vectors makes up the tangent space T x(t) ℳ, and it is equipped with the metric g x(t)( ⋅, ⋅) as the inner product. The length of a path x(t) ∈ ℳ, t ∈ [0, 1], is defined as , and locally shortest paths are denoted geodesics. They can be shown to minimize [21, Lemma 2.3]. Let us emphasize that a general geodesic is only locally the shortest curve. In particular, there might be multiple geodesics of different length connecting the same end points. The geodesic distance between two points is the length of the shortest connecting path. Finally, for a given x ∈ ℳthere is a bijection exp x : T x ℳ → ℳof a neighborhood of 0 ∈ T x ℳinto a neighborhood of x ∈ ℳthat assigns to each tangent vector v ∈ T x ℳthe end point of the geodesic emanating from xwith initial velocity vand running over the time interval [0, 1] [42, Theorem 1.6.12] or [74, Chap. 9, Theorem 14].

We can now define the (possibly non-unique, cf. Sect. 5) mean xof a number of npoints x 1, …, x n ∈ ℳin analogy to the Euclidian case as , where d( ⋅, ⋅) is the Riemannian distance on ℳ. This average is uniquely defined as long as the geodesics involved in the distance computation are unique, and it has been investigated in differential geometry by Karcher [38]. Furthermore, on a Riemannian manifold ℳ, the inverse exponential map log x = exp x − 1provides a method to obtain representatives log x (x i ) ∈ T x ℳof given input points x i ∈ ℳin the (linear) vector space T x ℳ(Fig. 2). On these, we can perform a PCA, which is by definition a linear statistical tool.
Fig. 2 The logarithmic map assigns each point x i on the manifold ℳa vector in the tangent space T x ℳ, which may be seen as a linear representative

In a Riemannian space ℳ, the path-based approach can immediately be applied by exploiting the Riemannian structure, and can be considered as the energy dissipation spent to move a point from x(0) to x(1) along a geodesic. The logarithms log x (x i ) in this model correspond to the initial velocities of the transport process leading from xto x i . When applying the state-based elastic model in ℳ, however, there is no mechanically motivated notion of paths and thus also no logarithmic map. Only if we suppose that the Riemannian structure of the space ℳis not induced by changes in the inner structure of our objects, the physical model based on elastic springs still coincides with the viscous model: We consider elastic springs stretched on the surface ℳand connecting the points xand x i with a stored energy . Then, as before in the Euclidian case, a state-based average xof input points x 1, …, x n can be defined. Furthermore, interpreting spring forces acting on xand pointing toward x i as linear representatives of the input points x i , one can run a PCA on these forces as well. However, for any reasonable (even finite-dimensional) model of shape space, objects are not rigid, and the inner relation between points as subunits (such as the vertex points of polygonal shapes) essentially defines the Riemannian (and thus the path-based) structure of the space ℳ: The rate of dissipation along a path in shape space depends on the interaction of object points. Physically, the corresponding point interaction energy is converted into thermal energy via friction. This dissipation depends significantly on the path in shape space traversed from one shape to the other. In contrast, when applying the state-based approach to the same shape space, we directly compare the inner relations between the subunits, i.e., we have no history of these relations. This comparison can be quantified based on a stored (elastic) interaction energy which is then a quantitative measure of the dissimilarity of the two objects but in general no metric distance.

Path-Based Viscous Dissipation Versus State-Based Elastic Deformation for Non-rigid Objects

In the following, we will especially consider two different physically motivated perspectives on a shape space of non-rigid volumetric objects in more detail. In the first case, we will adopt a path-based view, motivated by the theory of viscous fluids, while the second, state-based approach will be motivated by elasticity.

We will regard shapes as boundaries of domains which will be interpreted as physical objects. The resulting shape space structure depends on the particular type of physical objects : An interpretation of as a blob of a viscous fluid will yield an actually Riemannian, path-based shape space, while the interpretation as an elastic solid results in a state-based perspective, which will turn out to be non-Riemannian by construction.

Path-Based, Viscous Riemannian Setup

Shapes will be modeled as the boundary contour of a physical object that is made of a viscous fluid. The object might be surrounded by a different fluid (e.g., with much lower viscosity and compression modulus), nevertheless, without any restriction we will assume void outside the object in the derivation of our model. Here, viscositydescribes the internal resistance in a fluid and is a macroscopic measure of the friction between fluid particles, e.g., the viscosity of honey is significantly larger than that of water. The friction is described in terms of the stress tensor σ = (σ ij ) ij = 1, …d , whose entries describe a force per area element. By definition, σ ij is the force component along the ith coordinate direction acting on the area element with a normal pointing in the jth coordinate direction. Hence, the diagonal entries of the stress tensor σ refer to normal stresses, e.g., due to compression, and the off-diagonal entries represent tangential (shear) stresses. The Cauchy stress law states that due to the preservation of angular momentum, the stress tensor σ is symmetric [13].

In a Newtonian fluid, the stress tensor is assumed to depend linearly on the gradient : = of the velocity v. In case of a rigid body motion the stress vanishes. A rotational component of the local motion is generated by the antisymmetric part of the velocity gradient, and it has the local rotation axis ∇ ×vand local angular velocity | ∇ ×v | [78]. Thus, as rotations are rigid body motions, the stress only depends on the symmetric part of the velocity gradient. For an isotropic Newtonian fluid we get σ ij = λδ ij ∑ k (ε[v]) kk + 2με[v] ij , or in matrix notation σ = λtrε[v]1 + 2με[v], where 1 is the identity matrix. The parameter λ is denoted Lamé's first coefficient. The local rate of viscous dissipation - the rate at which mechanical energy is locally converted into heat due to friction - can now be computed as
This is in direct correspondence to the mechanical definition of the stress tensor σ as the first variation of the local dissipation rate with respect to the velocity gradient, i.e., σ = δ Dv diss. Indeed, by a straightforward computation we obtain Here, trε[v]2measures the averaged local change of length and trε[v]2the local change of volume induced by the transport. Obviously divv = tr(ε[v]) = 0 characterizes an incompressible fluid.
Now, let us consider a path of objects connecting with and generated by a time-continuous deformation. If each point of the object at time t ∈ [0, 1] moves in an Eulerian framework at the velocity v(t, x) ( ), so that the total deformation of into can be obtained by integrating the velocity field vin time, then the accumulated global dissipation of the motion field vin the time interval [0, 1] takes the form
This is the same concept as employed by Dupuis et al. [23] and Miller et al. [53] in their pioneering diffeomorphism approach. They minimize a dissipation functional under the simplifying assumption that the material behaves equally viscous inside and outside the object. Also, is replaced by a higher-order quadratic form Lv⋅vwhich plays the role of the local rate of dissipation in a multipolar fluid model [57]. Multipolar fluids are characterized by the fact that the stresses depend on higher spatial derivatives of the velocity. If the quadratic form associated with Lacts only on ε[v] and is symmetric, then rigid body motion invariance is incorporated in the multipolar fluid model (cf. Sect. 4.2). In contrast to this approach, we here measure the rate of dissipation differently inside and outside the object and rely on classical (monopolar) material laws from fluid mechanics.
On this physical background we will now derive a Riemannian structure on the space of shapes in an admissible class of shapes S. The associated metric on the (infinite-dimensional) manifold Sis in abstract terms a bilinear mapping that assigns each element an inner product on variations of (cf. Sect. 3.1above). The associated length of a tangent vector is given by . Furthermore, as we have already seen above the length of a differentiable curve is then defined by , where is the temporal variation of at time t. The Riemannian distance between two shapes and on Sis given as the minimal length taken over all curves with and or equivalently (cf. Sect. 3.1above) as the length of a minimizer of the functional . For shapes an infinitesimal variation of a shape is associated with a transport field . This transport field is obviously not unique. Indeed, given any vector field won with for all (where denotes the (d − 1)-dimensional tangent space to at x), the transport field v + wis another possible representation of the shape variation . Let us denote by the affine space of all these representations. As a geometric condition for we obtain for all , where denotes the outer normal to in . Given all possible representations we are interested in the optimal transport, i.e., the transport leading to the least dissipation. Thus, using definition (1) of the local dissipation rate we finally define the metric as the minimal dissipation rate on motion fields vwhich are consistent with the variation of the shape δS,
Let us remark that we distinguish explicitly between the metric on motion fields and the metric on shape variations. Finally, integration in time leads to the total dissipation (2) to be invested in the transport along a path in the shape space S. This implies the following definition of a time-continuous geodesic path in shape shape: