# A Bayesian Generative Model for Surface Template Estimation

Authors: Jun Ma; Michael I. Miller; Laurent Younes
Journal: International Journal of Biomedical Imaging
 (2010)

---

## Abstract

3D surfaces are important geometric models for many objects of interest in image analysis and Computational Anatomy. In this paper, we describe a Bayesian inference scheme for estimating a template surface from a set of observed surface data. In order to achieve this, we use the geodesic shooting approach to construct a statistical model for the generation and the observations of random surfaces. We develop a mode approximation EM algorithm to infer the maximum a posteriori estimation of initial momentumμ, which determines the template surface. Experimental results of caudate, thalamus, and hippocampus data are presented.


---

## Body

## 1. Introduction

3D surfaces are important geometric models for many objects of interest in image analysis and Computational Anatomy. For example, they are often used to represent the shape of 3D objects, the surface of human faces, and the boundaries of brain structures or of other human organs. Most data analysis methods in this domain are template-centered, and a proper estimation of a template plays an important role to obtain high quality results. This paper is devoted to the description of statistically supported template estimation method which is adapted to surface data sets.Our approach will be to build a generative statistical shape model in which the template is a parameter. We will then estimate it using maximum likelihood. This model relies on the very natural setting for which an observed surface is a noisy version of a random deformation of the template. This is the most generic and most basic approach of the deformable template paradigm, even if we add a small refinement by including a prior distribution on the template, based on what we will call ahypertemplate. Even with this global scheme which is fairly simple, we will see that implementing it in the context of surfaces will constitute a significant theoretical and numerical challenge.At the exception of the recent work of [1], this approach significantly differs from what has been mostly proposed in the literature, in which most of the methods compute templates as averages over specific common parametrizations of the surfaces (using, for example, the sphere as a parameter space [2]). Parametric representations, however, are limited by the fact that, because they are defined a priori and independently for each object, they cannot be assumed to suitably align important features in a given data set of surfaces (i.e., give similar coordinates to similar features in the surfaces). This usually results in oversmoothed template surfaces (which is the equivalent of getting blurry template images in the case of image averaging). In [1], a similar diffeomorphic transformation model is used, but, as we will see, our Bayesian construction will provide a well-specified template whereas [1] needs to rely to topologically unconstrained approximations to end up with a manageable template.In addition to the references above, there have been several publications addressing the issue of shape averaging over a dataset, although most of them work with 3D volume data or landmark points set. In several cases, the average is based on metric properties of the space of shapes [3–7], and the template is computed as an intrinsic average, minimizing the sum of square distances to each element of the set (Fréchet mean). Such methods have been implemented in the context of diffeomorphic deformation models (which are also models of interest in the present paper) for landmark matching [8], for 3D average digital atlas construction [9], and to quantify variability in heart geometry [10]. Other definitions of the average, adapted to situations in which the data is corrupted by noise, have been proposed [11–13], based on variational approaches (but not relying on a generative statistical model).Our approach to build a generative statistical shape model is reminiscent of the construction developed in [14] for linear models of deformations, and in [15] for large diffeomorphic deformations in 3D volume image averaging. Adapting these ideas to surfaces will however require new algorithms and numerical developments.In order to present our model, we need to first provide some background materials and notation, describing in particular the geodesic shooting equations that we will use to generate deformed surfaces. We will then introduce a random statistical model describing the generation and the observations of random surfaces. We then develop a Mode Approximation EM algorithm for surface averaging, to estimate the template from observations. In the optimization part, we derive and implement a new variational scheme, which is also applicable to surface matching, providing an alternative approach to the one originally proposed in [16, 17]. Finally, we present and discuss experimental results on caudate, thalamus, and hippocampus data.


## 2. EPDiff for Surface Evolution

We will base our random shape model on the so-called EPDiff equation, which describes the evolution of deformable structures (like images, surfaces, or landmarks) under the action of groups of diffeomorphisms. It is a geodesic equation for a Riemannian metric on diffeomorphisms, and describes a momentum conservation law in the associated Hamiltonian system. The reader interested by the theory behind this equation can refer to [18–20], but most of this background will not be needed for the present paper, in which we will only use the specific form of the equations for surface evolution. The term EPDiff comes from its determination as an Euler-Poincaré equation in the group of diffeomorphisms, as introduced in [21]. One of its main interests here is that it provides a numerically stable, easily described, Hamiltonian evolution over diffeomorphisms, which will constitute an ideal support for our shape models.The EPDiff equations describe the combined time evolution of a diffeomorphism, denotedϕ(t,·) and of what can be interpreted as a momentum, denoted p(t,·). The initial conditions are always ϕ(0,x)=x for ϕ, and some initial value, p0, for p. This initial  momentum will be a key component of the statistical model that will be built later on.Let us start with the simplest form of the equation, which assumes thatp0 is a vector-valued function over ℝd, that is, p0:ℝd→ℝd. It involves a smoothing kernel, K, defined on ℝ3×ℝ3, a typical choice being(1)K(x,y)=cstexp(-∥x-y∥22τ2).
Letting ∇1K denote the gradient of K with respect to its first variable, the corresponding EPDiff equation is(2)dϕdt(t,x)=∫ℝ3K(ϕ(t,x),ϕ(t,y))p(t,y)dy,dpdt(t,x)=-∫ℝ3∇1K(ϕ(t,x),ϕ(t,y))(p(t,x)·p(t,y))dy.
Here, the notation a·b refers to the usual dot product between vectors in ℝ3. If K is smooth enough, this system has solutions for arbitrary large t, and the mapping x↦ϕ(t,x) is a diffeomorphism at all times.The interesting fact about these equations is that they can have singular variants that are described in a similar way and have the same existence properties. The simplest way to relate the variants to the previous equation is to replace the Lebesgue's measure in the integrals by another, possibly singular, measure. For example, taking a surfaceS0 in ℝ3, we can use the volume form on S0 as a reference measure and obtain the equations (in which p0 and p(t,·) need only to be defined on S0)(3)dϕdt(t,x)=∫S0K(ϕ(t,x),ϕ(t,y))p(t,y)dωS0(y),dpdt(t,x)=-∫S0∇1K(ϕ(t,x),ϕ(t,y))×(p(t,y)·p(t,y))dωS0(y),
where dωS0 is the volume form on S0. Note that the first equation is defined for x∈ℝ3, but it suffices to use it for x∈S0 to obtain an equation for the evolving surface (4)St=ϕ(t,S0)={y=ϕ(t,x),x∈S0}.We can write a discrete form of the equations by replacingdy by a sum of Dirac measures (at points x1,…,xL in ℝ3), which gives, letting al(t)=p(t,xl),(5)dϕdt(t,x)=∑l=1LK(ϕ(t,x),ϕ(t,xl))al,dakdt=-∑l=1L(al·ak)∇1K(ϕ(t,xk),ϕ(t,xl)).
Similarly to (3), the first equation is valid for all x∈ℝ3, but it suffices to solve it for x=xl, l=1,…,L to obtain the evolution of the point set (6)xl(t)=ϕ(t,xl).
Also, (5) can be seen as a discretization of (3) in which x1,…,xL are the vertices of a triangulation of S0, and al(t)=p(t,xl)δσS0(xl), where δσS0(xl) is the area of a surface element around xl.The evolution of point sets is the most important from a practical point of view, since it is an ODE that can be easily implemented. Assuming a radial kernelK(x,y)=γ(∥x-y∥2) like in (1), and denoting γkl=γ(∥xk-xl∥2), and γkl′=γ′(∥xk-xl∥2), (5) can be rewritten as(7)dxkdt=∑l=1Lγklal,dakdt=-2∑l=1Lγkl′(al·ak)(xk-xl).
Once the initial position of the vertices, x(0)=(x1(0),…,xL(0)), and the initial momentum, a(0)=(a1(0),…,aL(0)), are provided, the evolution of the point set is uniquely determined.


## 3. Generative Model for Surface Observation

### 3.1. Random Triangulated Surfaces

If a triangulated template surfaceT with vertices x(T) is given, and we solve, until time t=1, (5) initialized with x(0)=x(T) and a random initial momentum a(0)=α, the displaced vertices provide a random perturbation of the initial surface that will be denoted by Tα. This is stated in the following definition.Definition 1.
LetT be a triangulated surface with vertices x(T)=(x1(T),…,xL(T)). Let α∈(ℝ3)L be a collection of L vectors in ℝ3. Let (x(t),a(t)) be the solution of (5) with initial condition x(0)=x(T) and a(0)=α. One defines Tα to be the triangulated surface with vertices x(Tα)=x(1) and the same topology as T.By lettingα be random, we build Tα as a random deformation of T. This will form the “ideal”, unobserved, surface, of which only a noisy version is observable (the noise process will be described in the next section).Following [15], we will use a Bayesian formulation in which T is itself represented as a random deformation T0,μ:=(T0)μ, where T0 is a fixed surface that we will call the hypertemplate, and μ is a prior initial momentum shooting from T0 to T (same notation as in Definition 1). One of the main interests of using a hypertemplate is to fix the topology of T so that it belongs, by construction, to the same class of objects as T0.So, ifN surfaces are observed, we need to model the probability distribution of the prior momentum, μ (starting at T0), which specifies T=T0,μ and of N deformation momenta α(1),…,α(N) which specify the surfaces Tα(1),…,Tα(N). We now provide a statistical model for the joint probability distribution of μ,α(1),…,α(N).We first introduce some notation. LettingK be the kernel introduced in the previous section to define the geodesic shooting equations, we let ΓT be the 3L by 3L matrix formed with the 3 by 3 blocks K(xk(T),xl(T))Idℝ3. We define, for a triangulated surface T with L vertices x(T), and α∈ℝ3L, (8)∥α∥T2=α*ΓTα=∑k,l=1LK(xk(T),xl(T))(αk·αl).We define the joint distribution ofμ,α(1),…,α(N) on ℝ3L×(ℝ3L)N by(9)p(μ,α(1),…,α(N))=1Zexp(-12λ∥μ∥T02-12∑n=1N∥α(n)∥T0,μ2),
where λ is a fixed parameter regulating the weight on the hypertemplate.There is a technical difficulty here, which is that one must make sure that this probability can be normalized (Z exists), which requires that the exponential is integrable. That this is true is not straightforward, and we have not been able to find a proof that works with any choice of the kernel K. One way to deal with this is to introduce a constant Aμ (which can be chosen arbitrarily large so that it does not interfere with the algorithms that will follow), and add to the model the constraint that ∥μ∥T0 is smaller than Aμ. Under such an assumption, one obtains (after integrating out the α's) (10)Z=(2π)3NL/2∫∥μ∥T0≤Aμexp(-12∥μ∥T02-N2logdetΓT0,μ)dμ.
This is finite, since, for any given μ, the transformation x(T0)→x(T0,μ) is the restriction of a diffeomorphism to the vertices of T0 (as seen from (5)). This implies that ΓT0,μ is nonsingular, and its determinant is bounded away from 0 when μ is restricted to a compact space.In fact, the choiceAμ=∞ can be proved to be acceptable for a large class of kernels. Those are kernels for which the smallest eigenvalue of  ΓT decreases at a speed which is at most polynomial in the minimal distance, hT, between the vertices. A list of kernels satisfying this property can be found in [22]. For such kernels, we find that (L being fixed) logdetΓT=O(loghT). Just sketching the argument here, one can prove, using elementary properties of dynamical systems, that hT=O(exp(-C∥μ∥T0,μ) for some constant C, so that the log determinant in (9) is linear in ∥μ∥T0,μ and Z is well defined, even with AT0,μ=∞. For very smooth kernels, including the Gaussian, bounds on the smallest eigenvalue of ΓT are much worse (with a decay which is exponential in (-1/hT2)), and the previous argument does not work. Since the bounds in [22] hold uniformly with respect to the number of points, a polynomial bound may still be valid for a fixed L, although we were unable to discover it.Notice that, conditionally to the template, the momentaα are independent and follow a Gaussian distribution with inverse covariance matrix given by ΓT. An example of simulated random deformations obtained using such a model is provided in Figure 1.Random deformation of a template caudate surface (left). The six surfaces following the template are independent realization of the model described in (9).
(a)(b)


### 3.2. Observation and Noise

The second part of our generative model is to describe the observation process, which takes an ideal surfaceTα generated according to the model above, and returns the noisy observable.Modeling such a noise process is a tricky issue. Obvious choices (like adding noise to the vertices ofTα) do not work because one cannot assume that the observed surfaces are discretized consistently with the template. In this paper, we will work around this issue by assimilating the observation of a surface that of a singular Gaussian process.For this, we consider that surfaces inℝ3 are not observable directly, but only via their action on test functions, that we will call sensors. We define a sensor to be a smooth vector field w over ℝ3 (typically with small support). Given an oriented surface S, define (11)(S,w)=∫Sw(s)·NS(s)dωS(s),
where NS is the normal to S. The real number, (S,w) is the measurement of S through the sensor w.Now, modeling noisy surfaces will result in assuming that, given anyw, the measurement (S,w) is a random variable. We will assume that it is Gaussian, and more generally, that, given m sensors, w1,…,wm, the random vector ((S,wj),j=1,…,m) is Gaussian.S, via its action on sensors, is therefore modeled as a Gaussian random field. Given an ideal surface Tα, we will assume that its mean is given by(12)E((S,w))=(Tα,w)
and the process is thereafter uniquely characterized by its covariance operator(13)G(w,w̃)=cov((S,w),(S,w̃)).
We will assume that this covariance is associated to a symmetric operator Lobs so that(14)G(w,w̃)=σ2∫ℝd(Lobsw(x)·w̃(x̃))dxdx̃.
(The apparently redundant parameter σ2, which could have been included in Lobs, appears here because it can be easily estimated by the algorithm, with the operator Lobs remaining constant.)To finalize our model, it remains to describe howS is discretized, that is, to make explicit a finite family of sensors through which S is measured. Let (zj,j∈J) form a regular grid of points in Ω. Let γs be a radial basis function (a Gaussian, e.g.,) and define, for j∈J and d=1,2,3(15)wj,d=γs(x-zj)ed
where ed is the dth vector of the standard basis of ℝ3 (this therefore specifies 3|J| sensors). The resulting observed variables are(16)yj,d=(S,wj,d)=∫Sγs(s-zj)NS(d)(s)dωS(s),
where NS(d)=NS·ed is the dth coordinate of NS. These variables are, by assumption, jointly Gaussian, with means mj,d=(Tα,wj,d) and covariance matrix(17)gi,d,i′,d′=G(wi,d,wi′,d′)=σ2δd,d′∫ℝdLobsγs(x-zi)γs(x̃-zi′)dxdx̃.
Assuming that Lobs is translation invariant, the resulting expression is a function of zi-zi′ that we will denote(18)gi,d,i′,d′=σ2δdd′γobs(zi-zi′).LetRobs=(rij(obs)) be the inverse matrix of the one with coefficients (γobs(zj-zj′),j,j′∈J). The log likelihood of the process will include error terms taking the form (19)ℰobs=1σ2∑j,j′∈J∑d=13rj,j′(obs)(yj,d-(Tα,wj,d))(yj′,d-(Tα,wj′,d)).
Replacing yj,d by its expression in (16), we have (20)σ2ℰobs=∑j,j′∈J‍∑d=13rj,j′(obs)∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Sγs(x-zj′)NS(d)(x)dωS(x)-2∑j,j′∈Jrj,j′(obs)∑d=13∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Tαγs(x-zj′)NTα(d)(x)dωTα(x)×∑j,j′∈Jrjj′(obs)∑d=13∫Tαγs(x-zj)NTα(d)(x)dωTα(x)×∫Tαγs(x-zj′)NTα(d)(x)dωTα(x).
Let us analyze the first term. We have (21)∑j,j′∈Jrj,j′(obs)∑d=13∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Sγs(x-zj′)NS(d)(x)dωS(x)=∑j,j′∈Jrj,j′(obs)∑d=13∫S×Sγs(x-zj)NS(d)(x)γs×(y-zj′)NS(d)(y)dωS(x)dωS(y)=∫S×S∑j,j′∈Jrj,j′(obs)γs(x-zj)γs(y-zj′)×(NS(x)·NS(y))dωS(x)dωS(y)=∫S×SKobs(x,y)(NS(x)·NS(y))dωS(x)dωS(y),
with the notation(22)Kobs(x,y)=∑j,j′∈Jrj,j′(obs)γs(x-zj)γs(y-zj′).Treating the other terms similarly, we can rewrite the error term in the form(23)ℰobs=1σ2∫S×SKobs(x,y)(NS(x)·NS(y))dωS(x)dωS(y)-2σ2∫S×TαKobs(x,y)×(NS(x)·NTα(y))dωS(x)dωTα(y)+1σ2∫Tα×TαKobs(x,y)×(NTα(x)·NTα(y))dωTα(x)dωTα(y)
and we will abbreviate this (introducing a notation for the right-hand side) as ℰobs=(1/σ2)∥S-Tα∥obs2. Thus, we can write (24)p(y∣Tα,σ)=cstexp(-12σ2∥S-Tα∥obs2).We have the following important proposition.Proposition 1.
Assume thatγs is taken equal to the Green function of Lobs. Then, when the grid J becomes finer and Kobs is given by (22), one has
(25)Kobs(x,y)→γobs(x-y).See the appendix for a proof of this proposition (which requires some background on the theory of Hilbert spaces with a reproducing kernel) and possible extensions. For practical purposes, we will useγobs instead of Kobs in ∥·∥obs, therefore assuming that the sensors are chosen according to the proposition. It is interesting to notice that the resulting norm in this case is precisely the norm that has been introduced in [16] to compare surfaces, when they are considered as elements of a reproducing kernel Hilbert space of currents. We refer to [16] for details on the mathematical construction.In the rest of the paper, we develop a parametric procedure to estimate the templateT from the observation of i.i.d. surfaces S(1),S(2),…,S(N) generated as described above. This includes in particular N hidden deformation momenta α(1),α(2),…,α(N), such that the complete distribution of observed and unobserved variables is(26)p(μ,α(1),S(1),…,α(N),S(N))=cstexp(-λ2∥μ∥T02-12∑n=1N(∥α(n)∥T2+1σ2∥S(n)-Tα(n)∥obs2)),
where we have written for short T=T0,μ.We now discuss the estimation of the parameterμ, and of the associated template T0,μ, which is the main purpose of this paper. This will be implemented with a mode approximation of the EM algorithm, as described in the next section.


## 3.1. Random Triangulated Surfaces

If a triangulated template surfaceT with vertices x(T) is given, and we solve, until time t=1, (5) initialized with x(0)=x(T) and a random initial momentum a(0)=α, the displaced vertices provide a random perturbation of the initial surface that will be denoted by Tα. This is stated in the following definition.Definition 1.
LetT be a triangulated surface with vertices x(T)=(x1(T),…,xL(T)). Let α∈(ℝ3)L be a collection of L vectors in ℝ3. Let (x(t),a(t)) be the solution of (5) with initial condition x(0)=x(T) and a(0)=α. One defines Tα to be the triangulated surface with vertices x(Tα)=x(1) and the same topology as T.By lettingα be random, we build Tα as a random deformation of T. This will form the “ideal”, unobserved, surface, of which only a noisy version is observable (the noise process will be described in the next section).Following [15], we will use a Bayesian formulation in which T is itself represented as a random deformation T0,μ:=(T0)μ, where T0 is a fixed surface that we will call the hypertemplate, and μ is a prior initial momentum shooting from T0 to T (same notation as in Definition 1). One of the main interests of using a hypertemplate is to fix the topology of T so that it belongs, by construction, to the same class of objects as T0.So, ifN surfaces are observed, we need to model the probability distribution of the prior momentum, μ (starting at T0), which specifies T=T0,μ and of N deformation momenta α(1),…,α(N) which specify the surfaces Tα(1),…,Tα(N). We now provide a statistical model for the joint probability distribution of μ,α(1),…,α(N).We first introduce some notation. LettingK be the kernel introduced in the previous section to define the geodesic shooting equations, we let ΓT be the 3L by 3L matrix formed with the 3 by 3 blocks K(xk(T),xl(T))Idℝ3. We define, for a triangulated surface T with L vertices x(T), and α∈ℝ3L, (8)∥α∥T2=α*ΓTα=∑k,l=1LK(xk(T),xl(T))(αk·αl).We define the joint distribution ofμ,α(1),…,α(N) on ℝ3L×(ℝ3L)N by(9)p(μ,α(1),…,α(N))=1Zexp(-12λ∥μ∥T02-12∑n=1N∥α(n)∥T0,μ2),
where λ is a fixed parameter regulating the weight on the hypertemplate.There is a technical difficulty here, which is that one must make sure that this probability can be normalized (Z exists), which requires that the exponential is integrable. That this is true is not straightforward, and we have not been able to find a proof that works with any choice of the kernel K. One way to deal with this is to introduce a constant Aμ (which can be chosen arbitrarily large so that it does not interfere with the algorithms that will follow), and add to the model the constraint that ∥μ∥T0 is smaller than Aμ. Under such an assumption, one obtains (after integrating out the α's) (10)Z=(2π)3NL/2∫∥μ∥T0≤Aμexp(-12∥μ∥T02-N2logdetΓT0,μ)dμ.
This is finite, since, for any given μ, the transformation x(T0)→x(T0,μ) is the restriction of a diffeomorphism to the vertices of T0 (as seen from (5)). This implies that ΓT0,μ is nonsingular, and its determinant is bounded away from 0 when μ is restricted to a compact space.In fact, the choiceAμ=∞ can be proved to be acceptable for a large class of kernels. Those are kernels for which the smallest eigenvalue of  ΓT decreases at a speed which is at most polynomial in the minimal distance, hT, between the vertices. A list of kernels satisfying this property can be found in [22]. For such kernels, we find that (L being fixed) logdetΓT=O(loghT). Just sketching the argument here, one can prove, using elementary properties of dynamical systems, that hT=O(exp(-C∥μ∥T0,μ) for some constant C, so that the log determinant in (9) is linear in ∥μ∥T0,μ and Z is well defined, even with AT0,μ=∞. For very smooth kernels, including the Gaussian, bounds on the smallest eigenvalue of ΓT are much worse (with a decay which is exponential in (-1/hT2)), and the previous argument does not work. Since the bounds in [22] hold uniformly with respect to the number of points, a polynomial bound may still be valid for a fixed L, although we were unable to discover it.Notice that, conditionally to the template, the momentaα are independent and follow a Gaussian distribution with inverse covariance matrix given by ΓT. An example of simulated random deformations obtained using such a model is provided in Figure 1.Random deformation of a template caudate surface (left). The six surfaces following the template are independent realization of the model described in (9).
(a)(b)


## 3.2. Observation and Noise

The second part of our generative model is to describe the observation process, which takes an ideal surfaceTα generated according to the model above, and returns the noisy observable.Modeling such a noise process is a tricky issue. Obvious choices (like adding noise to the vertices ofTα) do not work because one cannot assume that the observed surfaces are discretized consistently with the template. In this paper, we will work around this issue by assimilating the observation of a surface that of a singular Gaussian process.For this, we consider that surfaces inℝ3 are not observable directly, but only via their action on test functions, that we will call sensors. We define a sensor to be a smooth vector field w over ℝ3 (typically with small support). Given an oriented surface S, define (11)(S,w)=∫Sw(s)·NS(s)dωS(s),
where NS is the normal to S. The real number, (S,w) is the measurement of S through the sensor w.Now, modeling noisy surfaces will result in assuming that, given anyw, the measurement (S,w) is a random variable. We will assume that it is Gaussian, and more generally, that, given m sensors, w1,…,wm, the random vector ((S,wj),j=1,…,m) is Gaussian.S, via its action on sensors, is therefore modeled as a Gaussian random field. Given an ideal surface Tα, we will assume that its mean is given by(12)E((S,w))=(Tα,w)
and the process is thereafter uniquely characterized by its covariance operator(13)G(w,w̃)=cov((S,w),(S,w̃)).
We will assume that this covariance is associated to a symmetric operator Lobs so that(14)G(w,w̃)=σ2∫ℝd(Lobsw(x)·w̃(x̃))dxdx̃.
(The apparently redundant parameter σ2, which could have been included in Lobs, appears here because it can be easily estimated by the algorithm, with the operator Lobs remaining constant.)To finalize our model, it remains to describe howS is discretized, that is, to make explicit a finite family of sensors through which S is measured. Let (zj,j∈J) form a regular grid of points in Ω. Let γs be a radial basis function (a Gaussian, e.g.,) and define, for j∈J and d=1,2,3(15)wj,d=γs(x-zj)ed
where ed is the dth vector of the standard basis of ℝ3 (this therefore specifies 3|J| sensors). The resulting observed variables are(16)yj,d=(S,wj,d)=∫Sγs(s-zj)NS(d)(s)dωS(s),
where NS(d)=NS·ed is the dth coordinate of NS. These variables are, by assumption, jointly Gaussian, with means mj,d=(Tα,wj,d) and covariance matrix(17)gi,d,i′,d′=G(wi,d,wi′,d′)=σ2δd,d′∫ℝdLobsγs(x-zi)γs(x̃-zi′)dxdx̃.
Assuming that Lobs is translation invariant, the resulting expression is a function of zi-zi′ that we will denote(18)gi,d,i′,d′=σ2δdd′γobs(zi-zi′).LetRobs=(rij(obs)) be the inverse matrix of the one with coefficients (γobs(zj-zj′),j,j′∈J). The log likelihood of the process will include error terms taking the form (19)ℰobs=1σ2∑j,j′∈J∑d=13rj,j′(obs)(yj,d-(Tα,wj,d))(yj′,d-(Tα,wj′,d)).
Replacing yj,d by its expression in (16), we have (20)σ2ℰobs=∑j,j′∈J‍∑d=13rj,j′(obs)∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Sγs(x-zj′)NS(d)(x)dωS(x)-2∑j,j′∈Jrj,j′(obs)∑d=13∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Tαγs(x-zj′)NTα(d)(x)dωTα(x)×∑j,j′∈Jrjj′(obs)∑d=13∫Tαγs(x-zj)NTα(d)(x)dωTα(x)×∫Tαγs(x-zj′)NTα(d)(x)dωTα(x).
Let us analyze the first term. We have (21)∑j,j′∈Jrj,j′(obs)∑d=13∫Sγs(x-zj)NS(d)(x)dωS(x)×∫Sγs(x-zj′)NS(d)(x)dωS(x)=∑j,j′∈Jrj,j′(obs)∑d=13∫S×Sγs(x-zj)NS(d)(x)γs×(y-zj′)NS(d)(y)dωS(x)dωS(y)=∫S×S∑j,j′∈Jrj,j′(obs)γs(x-zj)γs(y-zj′)×(NS(x)·NS(y))dωS(x)dωS(y)=∫S×SKobs(x,y)(NS(x)·NS(y))dωS(x)dωS(y),
with the notation(22)Kobs(x,y)=∑j,j′∈Jrj,j′(obs)γs(x-zj)γs(y-zj′).Treating the other terms similarly, we can rewrite the error term in the form(23)ℰobs=1σ2∫S×SKobs(x,y)(NS(x)·NS(y))dωS(x)dωS(y)-2σ2∫S×TαKobs(x,y)×(NS(x)·NTα(y))dωS(x)dωTα(y)+1σ2∫Tα×TαKobs(x,y)×(NTα(x)·NTα(y))dωTα(x)dωTα(y)
and we will abbreviate this (introducing a notation for the right-hand side) as ℰobs=(1/σ2)∥S-Tα∥obs2. Thus, we can write (24)p(y∣Tα,σ)=cstexp(-12σ2∥S-Tα∥obs2).We have the following important proposition.Proposition 1.
Assume thatγs is taken equal to the Green function of Lobs. Then, when the grid J becomes finer and Kobs is given by (22), one has
(25)Kobs(x,y)→γobs(x-y).See the appendix for a proof of this proposition (which requires some background on the theory of Hilbert spaces with a reproducing kernel) and possible extensions. For practical purposes, we will useγobs instead of Kobs in ∥·∥obs, therefore assuming that the sensors are chosen according to the proposition. It is interesting to notice that the resulting norm in this case is precisely the norm that has been introduced in [16] to compare surfaces, when they are considered as elements of a reproducing kernel Hilbert space of currents. We refer to [16] for details on the mathematical construction.In the rest of the paper, we develop a parametric procedure to estimate the templateT from the observation of i.i.d. surfaces S(1),S(2),…,S(N) generated as described above. This includes in particular N hidden deformation momenta α(1),α(2),…,α(N), such that the complete distribution of observed and unobserved variables is(26)p(μ,α(1),S(1),…,α(N),S(N))=cstexp(-λ2∥μ∥T02-12∑n=1N(∥α(n)∥T2+1σ2∥S(n)-Tα(n)∥obs2)),
where we have written for short T=T0,μ.We now discuss the estimation of the parameterμ, and of the associated template T0,μ, which is the main purpose of this paper. This will be implemented with a mode approximation of the EM algorithm, as described in the next section.


## 4. Algorithms for Surface Template Estimation

### 4.1. Mode Approximation EM

LetΘ=(α(1),α(2),…,α(N)) be the hidden part of the process, representing the collection of initial momenta, and let S=(S(1),S(2),…,S(N)) be the collection of observed surfaces. The complete distribution for the process, including the prior is given by (26).The EM algorithm is an iterative method that updates a current estimation ofμ using the following two E- and M-steps.E-step: determine the conditional expectation μ̃↦Eμ{logπ(μ̃,Θ,S)∣S)}.M-step: maximize this expression with respect to μ̃ and replace the current estimation of μ by the obtained maximizer.The conditional expectation can be expanded as(27)Eμ{logπ(μ̃,Θ,S)∣S)}=-λ2∥μ̃∥T02-12∑n=1NEμ(∥α(n)∥T2+1σ2∥S(n)-Tα(n)∥obs2∣S(n)).Considering the highly nonlinear relation betweenα(n) and the deformed surface Tα(n), an explicit computation in (27) is impossible. We will therefore rely on the classic mode approximation in the EM which replaces the conditional distribution by a Dirac measure taken at the conditional mode, yielding(28)Eμ{logπ(μ̃,Θ,S)∣S)}≈λ2∥μ̃∥T02+12∑n=1N∥α̂(n)∥T2+1σ2∥S(n)-Tα̂(n)∥obs2},
where (29)α̂(n)=argminα{∥α∥T2+1σ2∥S(n)-Tα∥obs2}.This results in a maximum a posteriori procedure that maximizes alternatively inμ and in the α(n)'s. Like in [15], we will refer to it as a mode approximation to the EM (MAEM) rather than a MAP algorithm, in order to strengthen the fact that it is an approximation of the maximum a posteriori procedure relying on the likelihood of the observed data only. As illustrated in [14], the MAEM can be biased (leading to inexact estimation of the template, even with a very large number of samples), especially when the noise is important, but it is obviously more feasible than the exact EM. Notice that the MAEM method is a special form of EM algorithm, and as such optimizes a lower bound of the log likelihood of the observed data.We summarize the two steps of theith iteration of the MAEM in our case. Suppose μ and the α(n)'s are the current variables to be updated. Then the next iteration is as follows.MAE step: withμ (and therefore T) fixed, find, for n=1,…,N, α̂(n) to minimize(30)∥α∥T2+1σ2∥S(n)-Tα∥obs2
and replace α(n) by α̂(n).M step: with α(n) fixed, update μ with the minimizer of(31)λ∥μ̃∥T02+∑n=1N(∥α(n)∥T0,μ̃2+1σ2∥S(n)-(T0μ̃)α(n)∥obs2).We now discuss how each of these steps can be implemented.


### 4.2. MAE Step

Our goal in this section is to optimize (30). We work with fixed n and drop it from the notation to simplify the expressions. The objective function is(32)E(α)=∥α∥T2+1σ2∥S-Tα∥obs2.
This problem is equivalent to the surface matching algorithm considered in [16], with a slightly different formulation since [16] optimize an energy with respect to a time-dependent momentum instead of just the initial momentum (i.e., they solved simultaneously the geodesic estimation and the matching problems). These two formulations are equivalent when using continuous time (they produce the same minima), but they yield different results when discretized. In our setting, formulating the problem as in (32) is natural, and focuses on the modeled random variable, α.We need to compute the variation ofE with respect to α. This computation will be useful for the M-step also. We first discuss the discretization of the error term, which follows [16]. Let S be a triangulated surfaces, with vertices x(S)=(x1(S),…,xL(S)) and faces F(S)=(f1(S),…,fM(S)). Each face is represented by an ordered triple of vertices: f=(x1f,x2f,x3f), and we define the face centers and area-weighted normals by (33)cf=13(x1f+x2f+x3f),Nf=12(x2f-x1f)×(x3f-x1f).
Then a discrete approximation of ∥S-S′∥obs2 is (34)U(xS′)=∑f,f′∈F(S)γobs(cf-cf′)(Nf·Nf′)+∑f,f′∈F(S′)γobs(cf-cf′)(Nf·Nf′)-2∑f∈F(S),f′∈F(S′)γobs(cf-cf′)(Nf·Nf′),
where S is considered as fixed and U is therefore considered as a function of the vertices, x(S′), of S′.With this notation, we can write(35)E(α)=∥α∥T2+1σ2U(x(Tα)).
We want to compute the gradient of E and for this, apply the chain rule to the transformations α→Tα→U(x(Tα)), yielding(36)∂αU=(dx(Tα)dα)*∂xU,
where A* is the transpose matrix of A.The gradient ofU with respect to x(S′) has been computed in [16], and is given as follows. We denote by Fl(S) the set of faces (triangles) that contain a vertex xl in a triangulated surface S. For f∈Fl(S), we let el(f) denote the edge opposed to xl in f, positively oriented in f. With S′=Tα, we have(37)∂U∂xl(S′)(x(S′))=∑f∈Fl(S′)∑g∈F(S)∪F(S′)ag(23∇γobs(cf-cg)(Nf·Ng)+γobs(cf-cg)el(f)×Ng23),
where ag=1 if g∈F(S′) and a(g)=-1 if g∈F(S).Now let us derive the variation ofx(Tα) with respect to the initial momentum, α. We know that x(Tα)=x(1), where x and a evolve according to the system (7) (38)dxkdt=∑l=1Lγklal,dakdt=-2∑l=1Lγkl′(al·ak)(xk-xl)
with x(0)=x(T) and a(0)=α (and γkl,γkl′ are short for γ(∥xk-xl∥2) and γ′(∥xk-xl∥2)). Now an infinitesimal variation α→α+δα in the initial condition induces infinitesimal variations a+δa and x+δx over time, and the pair (δx,δa) obeys the following differential system, that can be obtained from a formal differentiation of (7):(39)dδxk(t)dt=∑l=1Lγklδal+2∑l=1Lγkl′al(xk-xl)·(δxk-δxl),(40)dδak(t)dt=-2∑l=1Lγkl′(al·δak+δal·ak)(xk-xl)-2∑l=1Lγkl′(al·ak)(δxk-δxl)-4∑l=1Lγkl′′(al·ak)(xk-xl)((xk-xl)·(δxk-δxl))
with γkl′′=γ′′(∥xk-xl∥2).One can rewrite it in the matrix form:(41)ddt(δxδα)=J(t)(δxδα),
where J(t)=(JxxJxaJaxJaa) with(42)Jxx(k,l)=(2∑q=1Lγkq′aq(xl-xq)*)δkl-2γkl′al(xk-xl)*Jxa(k,l)=γklIdℝ3.Jax(k,l)=-(2∑q=1L(aq·al)×(γkq′Idℝ3+2γkq′′(xl-xq)(xl-xq)*)δkl∑q=1L)+2(al·ak)(γkl′Idℝ3+2γkl′′(xk-xl)(xk-xl)*).Jaa(k,l)=-(2(∑q=1Lγkq′(xl-xq)aq*))δkl-2γkl′(xk-xl)ak*.
Solving this system with initial condition δx(0)=0 and δa(0)=δα provides what we have denoted (43)(dx(Tα)dα)δα.
One does not need to compute all the coefficients of the matrix dx(Tα)/dα using this equation in order to apply the transpose in (36). This is fortunate because this would constitute a computationally demanding effort given that this matrix is 3L by 3L with L large. The right hand side of (36) can be in fact computed directly using a single dynamical system, given by(44)ddt(ηxηα)=-J(t)*(ηxηα),
where J(t) is defined in (39). If (44) is solved from time t=1 to time t=0 with ηx(1)=∂xU and ηα(1)=0, then (45)∂αU=ηα(0).
This is a simple consequence of the theory of linear differential systems (a proof is provided in the Appendix for completeness). Note that the matrix J(t) depends on the solution of (7) computed with initial conditions x(0)=x(T) and a(0)=α. To emphasize this dependency, we will denote it J(t)=J(T,α)(t) in the following.Given this, we see that a variationα→α+δα induces a first-order variation δE of the energy given by(46)δE=2〈δα,α〉T+1σ2δα·ηα(0),
where the T-dot product is 〈δα,α〉T=δα·(ΓTα) and ΓT is the matrix formed with 3 by 3 blocs γklIdℝ3.We choose to operate the gradient descent with respect to this dot product and therefore choose a variation proportional toδα=-(2α+ΓT-1ηα(0)). So, the algorithm to compute an optimal α is the following.Algorithm 1 (MAE Step for Surface Template Estimation).
(1)
Compute the variation∂x(Tα)U using (37).(2)
Solve backward in time (44) initialized with ηx(1)=∂x(Tα)U and ηα=0.(3)
Replaceα by α-ϵ(2α+(1/σ2)ΓT-1ηα(0)) (using a line-search to optimize ϵ).This algorithm has to be appliedN times (for all αk, k=1,…,N) in the MAE step.Remark 1.
The matrixΓT being typically very badly conditioned, we numerically compute ΓT-1ηα after adding a small positive number to the diagonal of ΓT. The inversion itself is computed using conjugate gradient.


### 4.3. M Step

There are many similarities between theM-step and the E-step variational problems, so that we will be able to only sketch the detail of the computation here. We need to minimize (47)Ẽ(μ)=∥μ∥T02+1λ∑n=1NŨ(n)(x(T0,μ))
with(48)Ũ(n)(x(T))=∥α(n)∥T2+1σ2∥S-Tα(n)∥obs2.Let us consider the variation of each term in the sum (fixingn, that we temporarily drop from the notation). Since (49)∥α∥T2=∑k,l=1Lγ(∥xk(T)-xl(T)∥2)(αk·αl),
we can write(50)∂∥α∥T2∂xk(T)=2∑l=1Lγ′(∥xk(T)-xl(T)∥2)(αk·αl)(xk(T)-xl(T)).The functionU being defined as before, we see that the derivative of the second term is given by applying the chain rule again, this time in the form (51)(dx(Tα)dx(T))*∂x(Tα)U.Like in the previous section, the transpose of the differential applied to the gradient ofU can be computed by solving a dynamical system backward in time. In fact, it is the same system as with the variation in α, namely, (52)ddt(ηxηα)=-J(T,α)(t)*(ηxηα)
still initialized with ηx(1)=∂x(Tα)U and ηα(1)=0, but the relevant result now is ηx(0). The gradient of Ũ is then(53)∂x(T)U=∂x(T)∥α∥T2+1σ2ηx(0).Once this is computed, the next step is to compute (reintroducingn in the notation) (54)(dx(T0μ)dμ)*(∑n=1N∂x(T)U(n)).
This follows a similar procedure, using (44), with T0 instead of T and μ instead of α. This requires solving(55)ddt(ηxημ)=-J(T0,μ)(t)*(ηxημ),
initialized with ηx(1)=∂x(T)Ũ and ημ(1)=0. The variation of Ẽ associated to an infinitesimal variation of μ is then (56)δE=〈δμ,2μ〉T0+1λ(δμ·ημ(0))=〈δμ,2μ+1λΓT0-1ημ(0)〉.We summarize the M step in the following algorithm.Algorithm 2 (M-Step Algorithm for Surface Template Estimation).
(1)
Forn=1,…,N:
(1.1)
Compute∂x(Tα(n))U using (37).(1.2)
Solve system (44) backward in time with initial condition ηx(n)(1)=∂x(Tα(n))U and ηα(n)(1)=0.(1.3)
Compute(57)∂x(T)Ũ(n)=∂x(T)∥α(n)∥T2+1σ2ηx(n)(0)
using (50).(2)
Solve system (55) backward in time with
(58)ηx(1)=∑n=1N∂x(T)Ũ(n)
and ημ(1)=0.(3)
Replaceμ by μ-ϵ(μ+ΓT0-1ημ(0)/λ), ϵ being optimized with a line search.


### 4.4. Surface Template Estimation Algorithm

We finally summarize the surface template estimation algorithm:Algorithm 3 (Surface Template Estimation).
Having the hypertemplateT0 and observed surfaces S(1),…,S(N), the goal is to estimate the template T. Let T,μ,α(1),…,α(N) denote the current estimation with initial guess T=T0,μ=0, α(n)=0. Then, in the next iteration, update with the following steps: (i)
WithT fixed, apply Algorithm 1 to update each α(n), n=1,…,N.(ii)
Withα(n)'s fixed, apply Algorithm 2 to obtain a new value for μ.(iii)
Solve (7) initialized with the hypertemplate T0 and the newly obtained μ to update the estimated template, T.


## 4.1. Mode Approximation EM

LetΘ=(α(1),α(2),…,α(N)) be the hidden part of the process, representing the collection of initial momenta, and let S=(S(1),S(2),…,S(N)) be the collection of observed surfaces. The complete distribution for the process, including the prior is given by (26).The EM algorithm is an iterative method that updates a current estimation ofμ using the following two E- and M-steps.E-step: determine the conditional expectation μ̃↦Eμ{logπ(μ̃,Θ,S)∣S)}.M-step: maximize this expression with respect to μ̃ and replace the current estimation of μ by the obtained maximizer.The conditional expectation can be expanded as(27)Eμ{logπ(μ̃,Θ,S)∣S)}=-λ2∥μ̃∥T02-12∑n=1NEμ(∥α(n)∥T2+1σ2∥S(n)-Tα(n)∥obs2∣S(n)).Considering the highly nonlinear relation betweenα(n) and the deformed surface Tα(n), an explicit computation in (27) is impossible. We will therefore rely on the classic mode approximation in the EM which replaces the conditional distribution by a Dirac measure taken at the conditional mode, yielding(28)Eμ{logπ(μ̃,Θ,S)∣S)}≈λ2∥μ̃∥T02+12∑n=1N∥α̂(n)∥T2+1σ2∥S(n)-Tα̂(n)∥obs2},
where (29)α̂(n)=argminα{∥α∥T2+1σ2∥S(n)-Tα∥obs2}.This results in a maximum a posteriori procedure that maximizes alternatively inμ and in the α(n)'s. Like in [15], we will refer to it as a mode approximation to the EM (MAEM) rather than a MAP algorithm, in order to strengthen the fact that it is an approximation of the maximum a posteriori procedure relying on the likelihood of the observed data only. As illustrated in [14], the MAEM can be biased (leading to inexact estimation of the template, even with a very large number of samples), especially when the noise is important, but it is obviously more feasible than the exact EM. Notice that the MAEM method is a special form of EM algorithm, and as such optimizes a lower bound of the log likelihood of the observed data.We summarize the two steps of theith iteration of the MAEM in our case. Suppose μ and the α(n)'s are the current variables to be updated. Then the next iteration is as follows.MAE step: withμ (and therefore T) fixed, find, for n=1,…,N, α̂(n) to minimize(30)∥α∥T2+1σ2∥S(n)-Tα∥obs2
and replace α(n) by α̂(n).M step: with α(n) fixed, update μ with the minimizer of(31)λ∥μ̃∥T02+∑n=1N(∥α(n)∥T0,μ̃2+1σ2∥S(n)-(T0μ̃)α(n)∥obs2).We now discuss how each of these steps can be implemented.


## 4.2. MAE Step

Our goal in this section is to optimize (30). We work with fixed n and drop it from the notation to simplify the expressions. The objective function is(32)E(α)=∥α∥T2+1σ2∥S-Tα∥obs2.
This problem is equivalent to the surface matching algorithm considered in [16], with a slightly different formulation since [16] optimize an energy with respect to a time-dependent momentum instead of just the initial momentum (i.e., they solved simultaneously the geodesic estimation and the matching problems). These two formulations are equivalent when using continuous time (they produce the same minima), but they yield different results when discretized. In our setting, formulating the problem as in (32) is natural, and focuses on the modeled random variable, α.We need to compute the variation ofE with respect to α. This computation will be useful for the M-step also. We first discuss the discretization of the error term, which follows [16]. Let S be a triangulated surfaces, with vertices x(S)=(x1(S),…,xL(S)) and faces F(S)=(f1(S),…,fM(S)). Each face is represented by an ordered triple of vertices: f=(x1f,x2f,x3f), and we define the face centers and area-weighted normals by (33)cf=13(x1f+x2f+x3f),Nf=12(x2f-x1f)×(x3f-x1f).
Then a discrete approximation of ∥S-S′∥obs2 is (34)U(xS′)=∑f,f′∈F(S)γobs(cf-cf′)(Nf·Nf′)+∑f,f′∈F(S′)γobs(cf-cf′)(Nf·Nf′)-2∑f∈F(S),f′∈F(S′)γobs(cf-cf′)(Nf·Nf′),
where S is considered as fixed and U is therefore considered as a function of the vertices, x(S′), of S′.With this notation, we can write(35)E(α)=∥α∥T2+1σ2U(x(Tα)).
We want to compute the gradient of E and for this, apply the chain rule to the transformations α→Tα→U(x(Tα)), yielding(36)∂αU=(dx(Tα)dα)*∂xU,
where A* is the transpose matrix of A.The gradient ofU with respect to x(S′) has been computed in [16], and is given as follows. We denote by Fl(S) the set of faces (triangles) that contain a vertex xl in a triangulated surface S. For f∈Fl(S), we let el(f) denote the edge opposed to xl in f, positively oriented in f. With S′=Tα, we have(37)∂U∂xl(S′)(x(S′))=∑f∈Fl(S′)∑g∈F(S)∪F(S′)ag(23∇γobs(cf-cg)(Nf·Ng)+γobs(cf-cg)el(f)×Ng23),
where ag=1 if g∈F(S′) and a(g)=-1 if g∈F(S).Now let us derive the variation ofx(Tα) with respect to the initial momentum, α. We know that x(Tα)=x(1), where x and a evolve according to the system (7) (38)dxkdt=∑l=1Lγklal,dakdt=-2∑l=1Lγkl′(al·ak)(xk-xl)
with x(0)=x(T) and a(0)=α (and γkl,γkl′ are short for γ(∥xk-xl∥2) and γ′(∥xk-xl∥2)). Now an infinitesimal variation α→α+δα in the initial condition induces infinitesimal variations a+δa and x+δx over time, and the pair (δx,δa) obeys the following differential system, that can be obtained from a formal differentiation of (7):(39)dδxk(t)dt=∑l=1Lγklδal+2∑l=1Lγkl′al(xk-xl)·(δxk-δxl),(40)dδak(t)dt=-2∑l=1Lγkl′(al·δak+δal·ak)(xk-xl)-2∑l=1Lγkl′(al·ak)(δxk-δxl)-4∑l=1Lγkl′′(al·ak)(xk-xl)((xk-xl)·(δxk-δxl))
with γkl′′=γ′′(∥xk-xl∥2).One can rewrite it in the matrix form:(41)ddt(δxδα)=J(t)(δxδα),
where J(t)=(JxxJxaJaxJaa) with(42)Jxx(k,l)=(2∑q=1Lγkq′aq(xl-xq)*)δkl-2γkl′al(xk-xl)*Jxa(k,l)=γklIdℝ3.Jax(k,l)=-(2∑q=1L(aq·al)×(γkq′Idℝ3+2γkq′′(xl-xq)(xl-xq)*)δkl∑q=1L)+2(al·ak)(γkl′Idℝ3+2γkl′′(xk-xl)(xk-xl)*).Jaa(k,l)=-(2(∑q=1Lγkq′(xl-xq)aq*))δkl-2γkl′(xk-xl)ak*.
Solving this system with initial condition δx(0)=0 and δa(0)=δα provides what we have denoted (43)(dx(Tα)dα)δα.
One does not need to compute all the coefficients of the matrix dx(Tα)/dα using this equation in order to apply the transpose in (36). This is fortunate because this would constitute a computationally demanding effort given that this matrix is 3L by 3L with L large. The right hand side of (36) can be in fact computed directly using a single dynamical system, given by(44)ddt(ηxηα)=-J(t)*(ηxηα),
where J(t) is defined in (39). If (44) is solved from time t=1 to time t=0 with ηx(1)=∂xU and ηα(1)=0, then (45)∂αU=ηα(0).
This is a simple consequence of the theory of linear differential systems (a proof is provided in the Appendix for completeness). Note that the matrix J(t) depends on the solution of (7) computed with initial conditions x(0)=x(T) and a(0)=α. To emphasize this dependency, we will denote it J(t)=J(T,α)(t) in the following.Given this, we see that a variationα→α+δα induces a first-order variation δE of the energy given by(46)δE=2〈δα,α〉T+1σ2δα·ηα(0),
where the T-dot product is 〈δα,α〉T=δα·(ΓTα) and ΓT is the matrix formed with 3 by 3 blocs γklIdℝ3.We choose to operate the gradient descent with respect to this dot product and therefore choose a variation proportional toδα=-(2α+ΓT-1ηα(0)). So, the algorithm to compute an optimal α is the following.Algorithm 1 (MAE Step for Surface Template Estimation).
(1)
Compute the variation∂x(Tα)U using (37).(2)
Solve backward in time (44) initialized with ηx(1)=∂x(Tα)U and ηα=0.(3)
Replaceα by α-ϵ(2α+(1/σ2)ΓT-1ηα(0)) (using a line-search to optimize ϵ).This algorithm has to be appliedN times (for all αk, k=1,…,N) in the MAE step.Remark 1.
The matrixΓT being typically very badly conditioned, we numerically compute ΓT-1ηα after adding a small positive number to the diagonal of ΓT. The inversion itself is computed using conjugate gradient.


## 4.3. M Step

There are many similarities between theM-step and the E-step variational problems, so that we will be able to only sketch the detail of the computation here. We need to minimize (47)Ẽ(μ)=∥μ∥T02+1λ∑n=1NŨ(n)(x(T0,μ))
with(48)Ũ(n)(x(T))=∥α(n)∥T2+1σ2∥S-Tα(n)∥obs2.Let us consider the variation of each term in the sum (fixingn, that we temporarily drop from the notation). Since (49)∥α∥T2=∑k,l=1Lγ(∥xk(T)-xl(T)∥2)(αk·αl),
we can write(50)∂∥α∥T2∂xk(T)=2∑l=1Lγ′(∥xk(T)-xl(T)∥2)(αk·αl)(xk(T)-xl(T)).The functionU being defined as before, we see that the derivative of the second term is given by applying the chain rule again, this time in the form (51)(dx(Tα)dx(T))*∂x(Tα)U.Like in the previous section, the transpose of the differential applied to the gradient ofU can be computed by solving a dynamical system backward in time. In fact, it is the same system as with the variation in α, namely, (52)ddt(ηxηα)=-J(T,α)(t)*(ηxηα)
still initialized with ηx(1)=∂x(Tα)U and ηα(1)=0, but the relevant result now is ηx(0). The gradient of Ũ is then(53)∂x(T)U=∂x(T)∥α∥T2+1σ2ηx(0).Once this is computed, the next step is to compute (reintroducingn in the notation) (54)(dx(T0μ)dμ)*(∑n=1N∂x(T)U(n)).
This follows a similar procedure, using (44), with T0 instead of T and μ instead of α. This requires solving(55)ddt(ηxημ)=-J(T0,μ)(t)*(ηxημ),
initialized with ηx(1)=∂x(T)Ũ and ημ(1)=0. The variation of Ẽ associated to an infinitesimal variation of μ is then (56)δE=〈δμ,2μ〉T0+1λ(δμ·ημ(0))=〈δμ,2μ+1λΓT0-1ημ(0)〉.We summarize the M step in the following algorithm.Algorithm 2 (M-Step Algorithm for Surface Template Estimation).
(1)
Forn=1,…,N:
(1.1)
Compute∂x(Tα(n))U using (37).(1.2)
Solve system (44) backward in time with initial condition ηx(n)(1)=∂x(Tα(n))U and ηα(n)(1)=0.(1.3)
Compute(57)∂x(T)Ũ(n)=∂x(T)∥α(n)∥T2+1σ2ηx(n)(0)
using (50).(2)
Solve system (55) backward in time with
(58)ηx(1)=∑n=1N∂x(T)Ũ(n)
and ημ(1)=0.(3)
Replaceμ by μ-ϵ(μ+ΓT0-1ημ(0)/λ), ϵ being optimized with a line search.


## 4.4. Surface Template Estimation Algorithm

We finally summarize the surface template estimation algorithm:Algorithm 3 (Surface Template Estimation).
Having the hypertemplateT0 and observed surfaces S(1),…,S(N), the goal is to estimate the template T. Let T,μ,α(1),…,α(N) denote the current estimation with initial guess T=T0,μ=0, α(n)=0. Then, in the next iteration, update with the following steps: (i)
WithT fixed, apply Algorithm 1 to update each α(n), n=1,…,N.(ii)
Withα(n)'s fixed, apply Algorithm 2 to obtain a new value for μ.(iii)
Solve (7) initialized with the hypertemplate T0 and the newly obtained μ to update the estimated template, T.


## 5. Result and Discussion

We applied the algorithm to surface data of human brain's caudate, thalamus, and hippocampus. All data are courtesy of Center for Imaging Science at Johns Hopkins University. Each surface has around 5–10 thousand triangle cells. We randomly chose one as the hypertemplate and the others as observed surfaces. In these experiments, we setλ=1.0 and σ2=1.0.Figures2 and 3 are the template estimation result for caudate and thalamus, respectively.Estimating the surface template from 9 caudate data. (a)–(i) observed surfaces. (j) is the hypertemplate. (k) is the result.
(a)
S1(b)
S2(c)
S3(d)
S4(e)
S5(f)
S6(g)
S7(h)
S8(i)
S9(j)
HypertemplateT0(k)
Estimated templateTEstimating the surface template from 9 thalamus data. (a)–(i) observed surfaces. (j) is the hypertemplate. (k) is the result.
(a)
S1(b)
S2(c)
S3(d)
S4(e)
S5(f)
S6(g)
S7(h)
S8(i)
S9(j)
HypertemplateT0(k)
Estimated templateTWe also applied the algorithm to 101 hippocampus surface data in the BIRN Project (Biomedical Informatics Research Network). In Figure4, Panels (a)–(h) are 8 examples of the 101 observations. Panel (i) is the hypertemplate and Panel (j) is the estimated template.Estimating the surface template from 101 data. (a)–(h) are 8 examples out of 101 observed surfaces. (i) is the hypertemplate. (j) is the result.
(a)
S1(b)
S2(c)
S3(d)
S4(e)
S5(f)
S6(g)
S7(h)
S8(i)
HypertemplateT0(j)
Estimated templateTThe result is visually satisfying in the sense that the estimated template is found to agree with a qualitative representation of the population. For example, in the caudate experiment, the estimated template has an obviously narrower upper tip than the hypertemplate. This captures the population characteristic since most observed data have narrower upper tips. Notice that the obtained template does not look smoother than the rest of the population, as would typically yield template estimation methods that average over fixed parametrizations.Figure5 shows how the energy in (31) changes with the iteration in the caudate experiment. This confirms the effectiveness and convergence of the algorithm. One can see the energy drops quickly in the first twenty iterations, then gradually slows down. After the 35th iteration, the energy changes little and the estimated template remains stable.Figure 5
Energy change with the iteration.In our model, the hypertemplate can be provided by an atlas obtained from other studies, although we here simply choose one of the surfaces in the population. Actually, as Figure6 shows, different choices for the hypertemplate yield very similar results.For the same observed population, we choose different surfaces as hypertemplate. The results only have minor differences.
(a)
Hypertemplate 1(b)
Result 1(c)
Hypertemplate 2(d)
Result 2(e)
Hypertemplate 3(f)
Result 3


## 6. Conclusion

In this paper, we have presented a Bayesian approach for surface template estimation. We have built, for this purpose, a generative statistical model for surfaces: the construction first applies a random initial momentum to the template surface, then assumes an observation process using test functions and noise. The template is assumed to be generated as a random deformation of ahypertemplate, completing the Bayesian model. We used a mode approximation EM scheme to estimate the surface template, and introduced for this purpose a novel surface matching algorithm optimizing with respect to the initial momentum. The procedure has been tested with caudate, thalamus, and hippocampus surface data, showing its effectiveness and convergence, and also experimentally proved to be robust to variations in the choice of the hypertemplate.



---

*Source: 974957-2010-09-20.xml*