Noname manuscript No. (will be inserted by the editor)Elastic Shape Models for Face Analysis Using CurvilinearCoordinatesA. Srivastava1, C. Samir2, S. H. Joshi3, M. Daoudi21 Department of Statistics, Florida State University, Tallahassee, FL 32306, USA2 GET/Telecom Lille1, LIFL (UMR USTL/CNRS 8022), France3 Department of Electrical Engineering, Florida State University, Tallahassee, FL 32306, USAThe date of receipt and acceptance will be inserted by the editorAbstract We study the problem of analyzing variability in shapes of facial surfaces. The main diﬃculty inthis problem comes from the lack of a canonical coordinate system to compare faces. Our idea is to imposea speciﬁc, yet natural, coordinate system, called a Darcyan curvilinear coordinate system, on facial surfaces.This system is intrinsic to the surfaces and it deforms with them. Here, one coordinate ξ1 measures thedistance from the tip of the nose and the other coordinate ξ2 measures distances along level curves of ξ1.Using the Darcyan system, we develop tools for matching, comparing and deforming surfaces under an elasticmetric. The central idea is to ﬁnd optimal matches between level curves of ξ1 across faces, and to use anelastic (Riemannian) metric on the space of closed curves to deﬁne and compute geodesic paths betweenmatched curves. Together these geodesics provide optimal elastic deformations between faces and an elasticmetric for comparing facial shapes. We demonstrate this idea using examples from FSU face database.1 IntroductionThere is an increasing interest in analyzing shapes of facial surfaces with many applications including bio-metrics, facial surgery, video communications, and 3D animation. This interest is fueled by the advent ofdiﬀerent types of scanners that can provide (high-resolution) measurements, of both geometry and texture,of human facial surfaces, and a common goal in these areas is to develop computational tools for analyzing3D face data. In particular, one is interested in comparing the shapes of facia surfaces. Such a tool can beused to recognize human beings according to their facial shapes, to measure changes in a facial shape due toa surgery, or to study/capture the variations in facial shapes during conversations and expressions of emo-tions. Additionally, the goal may be to ﬁnd an optimal deformation of one surface into another, under somechosen criterion. These deformations can be useful in deﬁning summary statistics of a collection of faces.For example, one can compute an average face of a set of people, or for one person under diﬀerent facialexpressions. Eﬃcient tools for understanding and studying variability in facial shapes are of great importancein our biometric-oriented society. Accordingly, the main theme of this paper is to develop a computationalframework for analyzing shapes of facial surfaces.1.1 Major Issues in Surface AnalysisWhat are the diﬃculties in performing standard pattern recognition on the face data? The main issue is thatthere is no canonical coordinate system to represent and study the geometry of a nonlinear surface, such asa face. To highlight this issue, contrast the geometry of a surface with that of a curve. The points along acurve are ordered in a particular way, and this allows us to impose a coordinate system for studying shapesof curves. A parametrization for a curve is not unique but the task of analyzing shapes of curves moduloall possible parameterizations is still tractable. More speciﬁcally, the space of all possible parameterizations

2 A. Srivastava et al.of a curve is the set of all one-dimensional diﬀeomorphisms, and there exist eﬃcient algorithms (such asthe dynamic programming algorithm) for ﬁnding an optimal diﬀeomorphism under a certain class of costfunctions. For a surface, there is no natural ordering of points and, thus, no natural way of parameterizing asurface. The goal of analyzing shapes of surfaces, modulo all possible re-parameterizations, is quite ambitiousand leads to enormous computational diﬃculties.1.2 Past WorkPast literature has tackled this fundamental issue with a varying degree of success, depending on the ultimateapplication. If we divide the main tasks in facial shape analysis into matching, comparing, and deforming,there are a number of past papers that have addressed these individual tasks.1. Comparing Facial Features: For comparing faces, a common theme in this literature has been to represent facial surfaces by certain feature sets that are geometrical, such as the height function [9], convex regions, areas with high curvatures, saddle points, etc. These methods provide reasonable results in classiﬁcation and clustering of faces, but they do not study deformations nor develop statistical analysis of shapes. Additionally, although some of these features are intuitively meaningful, the computation of some of them (e.g. curvatures) involves numerical approximation of second derivatives which is very susceptible to observation noise. Other approaches, such as those based on shape distribution [22] and conformal geometry [27], have also been proposed. Beumier and Acheroy [2] have used shapes of facial proﬁles to compare faces.2. Matching Facial Surfaces: There are two types of matching algorithms: rigid and non-rigid. Rigid surface matching, often viewed as a matching of two point clouds in R3, is performed using the Iterative Closest Point (ICP) algorithm (see for example [1]) or its modiﬁcations. For non-rigid matching, several ideas have been proposed. Lu et al. [17,18] have used thin plate splines to perform non-rigid matching of faces. Chang et al. researchers have suggested restricting to some prominent parts of faces, such as the nose region, for performing the matching [3]. One idea that is often used in medical image analysis is the use of mutual information to register points across high-dimensional images. This idea has been applied to matching of facial surfaces by Wang et al. [28]. However, this approach is often applied to matching using statistics of pixel values in images rather than geometric properties of a surface.3. Deforming Facial Surfaces: In recent years there has been focus on not only comparing and matching facial surfaces, but also on deforming them from one to another under a chosen criterion. This idea is more general as one can study the templates and the deformations separately to model their variability. As an example, this is central in Grenander’s deformable template theory [6] that has been successfully applied to studying shapes of anatomical parts using medical images [20,7]. The set of non-rigid deformations can be subdivided into linear and nonlinear deformations. Nonlinear deformations imply local stretching, compression, and bending of surfaces to match each other, and are also referred to as elastic deformations. Earlier attempts at elastic matching utilized graphs based on texture images of faces [29,16]. Kakadiaris et al. [12] utilize an annotated face model to study geometrical variability across faces. A recent work in shape analysis is by Glaunes et al. [4] where the authors have studied diﬀeomorphic matching of a given pair of distributions (of points) in a general setting, with applications to various matching problems including curves, surfaces, and unlabeled points-sets.1.3 Our ApproachWe present a uniﬁed framework that provides optimal matching, comparisons and deformations of facesusing elastic metric. Conceptually, there are two main contributions of this paper that lead to eﬃcientcomputational tools for 3D face analysis.1. Darcyan Curvilinear Coordinate System: Rather than choosing a ﬁxed predetermined system, such as a Cartesian or a polar system, we present a coordinate system that is natural for analyzing shapes of facial surfaces. This system is deﬁned on the surface itself and it evolves with the surface (in case the surface is changing). Being intrinsic to the surface, it is invariant to rigid motions (rotations

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 3 and translations). The fact that it deforms with the changes in facial expressions provides a possibility of countering variability in facial shapes induced by changes in facial expressions. We will denote the coordinate system by Ξ and points in Ξ by ξ. The level sets of coordinates ξ = (ξ1, ξ2) in this system are curves that diﬀerent shapes, depending upon the geometry of the face involved. This coordinate system is centered at the tip of the nose; typically, it is the easiest point to ﬁnd automatically on an observed facial surface. The level curves of ξ1 denote points equidistant from the noise tip and the level curves of ξ2 will be radial curves going away from the noise tip. We will use this coordinate system to match, compare and deform facial surfaces. Such a curvilinear coordinate system has been proposed earlier for use in medical image analysis by Grenander et al. [8] who referred to it as the Darcyan coordinate system, after the famous shape analyst D’Arcy Thompson. Variations of this system have also been used in our earlier papers. For instance, the paper [23] uses a similar system using planar curves obtained as the level curves of the height function on a facial surface. Another paper [24] uses the level curves of ξ1 for shape analysis without formally deﬁning a coordinate system.2. Elastic Matching: An important requirement of a face analysis system is the non-rigid or elastic match- ing of points across faces. As described later, the task of elastic matching becomes relatively simpler in a Darcyan coordinate system. Let Ξ be the Darcyan coordinate system associated with one face and Ξ with another. The main task in shape matching is to decide which point in Ξ is matched to the point ξ ∈ Ξ, and to answer this for all ξ ∈ Ξ. In other words, a matching can be represented by a map φ : Ξ → Ξ that is a diﬀeomorphism (smooth and invertible, with a smooth inverse). If φs are considered random, then shapes should be compared by integrating over all possible φs. d(S1, S2) = dκ(κ1(ξ), κ2(φ(ξ)))P (φ)dφ , φ where – κ is some geometric descriptor being used to compare the surfaces, – dκ is a distance on the space of that descriptor, and – P (φ) is the probability density on φ. However, in practice one uses an optimal φ under a pre-determined criterion, to match shapes. This requires solving an optimization problem over the set of all mapping φs. d(S1, S2) ≈ dκ(κ1(ξ), κ2(φ∗(ξ))), where φ∗ = argmin dκ(κ1(ξ), κ2(φ(ξ))) . φ The advantage of a Darcyan coordinate system is that the search for this optimal φ is constrained to be in a smaller space. In our representation, φ(ξ1, ξ2) decomposes into the form φ1(ξ1)φ2(ξ2; ξ1). The ﬁrst function simply matches the level curves of ξ1 on S1 with the level curves of ξ1 on S2. Then, given any pair of matched curves, the points on them are matched using the function φ2. This function can be diﬀerent for diﬀerent values of ξ1 and, hence, our notation shows an explicit dependence of φ2 on ξ1. The search for optimal φ1 and φ2 is performed using an elastic energy function that allows for these functions to be nonlinear. The actual matching is performed using ideas from elastic matching of curves and the dynamic programming algorithm. This paper diﬀers from [24] in the use of an elastic metric; in the earlier paper φ is ﬁxed to be the identity function, φ(ξ) = ξ. The rest of this paper is organized as follows. We introduce the Darcyan coordinate system on facialsurfaces in Section 2. In Section 3, we summarize ideas from a past paper on elastic matching of points onclosed curves in R3 and the resulting deformations of level curves of ξ1, while in Section 4, we use ideasfrom dynamic programming to match curves on facial surfaces and to deform facial surfaces. In Section5, we present some examples on elastic deformation facial surfaces and point to their applications in faceclassiﬁcation. We ﬁnish the paper with a summary in Section 6.2 Curvilinear Coordinate SystemOne of the main contributions of this paper is in deﬁning an intrinsic coordinate system on each facial surfacethat is natural for studying shape variability. In fact, as described later, this coordinate system is essentialto decomposing the elastic deformations of these surfaces into simpler, more elementary components.

4 A. Srivastava et al.Fig. 1 Top row: Level curves of ξ1 and middle row: level curves of ξ2 for three diﬀerent facial surfaces. Bottom row:the two level curves together to construct a Darcyan coordinate system. Instead of using a pre-deﬁned coordinate system, such as the Cartesian system or the polar system,we deﬁne an intrinsic coordinate system on surfaces that simpliﬁes the analysis of their shapes. FollowingGrenander et al. [8], we will call it the Darcyan coordinate system. The level curves of these coordinatesare neither straight lines nor circles; these are curves that lie completely on the surface and locally matchthe geometry of the surface. We will establish this coordinate system using a number of propositions. LetS be a facial surface. We will assume that S is a two-dimensional diﬀerentiable manifold that contains itsboundaries. This is obtained in practice by ﬁlling the holes in the data obtained from 3D scanners, andby smoothly interpolating the resulting mesh to ensure two-dimensionality of any patch on the surface.Furthermore, S is endowed with a Riemannian structure using the usual Euclidean metric in R2, the tangentspace at any interior point of S. Let r ∈ S denote the tip of the nose on S.Proposition 1 For any point p, there exists a shortest geodesic, connecting r and p, that lies completely inS. The shortest geodesic may not be unique, but there exists at least one.The proof comes from the fact that S is a complete, diﬀerentiable manifold. Based on this proposition, onecan deﬁne a smooth function on S using geodesic distances as follows:Deﬁnition 1 For any point p ∈ S, deﬁne a function f : S → R such that f (p) is the length of the shortestgeodesic from r to p.Since there exists a shortest geodesic from r to every point p, the function f is well deﬁned. Also, since S isa diﬀerentiable manifold, the function f is a continuous function.

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 5Fig. 2 Darcyan coordinate system: Shown here are level curves of Darcyan coordinates ξ1 and ξ2 on several facialsurfaces. With this deﬁnition of f , we can impose a coordinate system on S. Since S is two-dimensional, we willdeﬁne two sets of coordinate axes, each axis will be orthogonal to all axes from the other set at all points ofintersection.Proposition 2 For any ξ1 ∈ f (S), the set {p ∈ S|f (p) = ξ1} is a one-dimensional diﬀerentiable manifold.The proof is a direct application of the inverse function theorem. Since the level sets of f are one-dimensional,they can be treated as parameterized curves. In our system, the level curves of f form one set of coordinateaxes. Let u = sup{f (p) : p ∈ S} and for 0 ≤ ξ1 ≤ u deﬁne the set Cξ1 = {p ∈ S|f (p) = ξ1}. For a ﬁxed ξ1,the set Cξ1 is a coordinate axis in the Darcyan system. Shown in the top row of Figure 1 are examples ofthese curves for three diﬀerent faces. Deﬁne grad(f ) to be the gradient of f on S. At any point p ∈ S, grad(f ) is a vector that is tangentialto S at p, i.e. grad(f ) ∈ Tp(S), and generates a vector ﬁeld on S. The ﬂow lines of this vector ﬁeld form thesecond set of coordinate axes. The tangent space Tr(S) at the nose is a two-dimensional vector space, andwe can denote a direction in this space by a parameter ξ2 ∈ [0, 2π]. For each ξ2, we can construct a ﬂow lineof grad(f ) starting from r as follows: dX (t) = grad(f )(X(t)), X(0) = r, dtand dX (t) |t=0 corresponds to ξ2. The middle row in Figure 1 shows examples of level curves of ξ2, and the dtbottom row shows the merging of two coordinates to form a full Darcyan coordinate system. In this system,the deﬁnition of ξ2 = 0 is somewhat arbitrary. To keep the choice standard across faces, we determine theplane of symmetry of a face and use the intersection of this plane with S at r as the direction for ξ2 = 0. Oneach level curve Cξ1 , the point corresponding to the ﬂow line ξ2 = 0 will be the origin for parametrization. Thus, we have established the following result.Lemma 1 For a given surface S with desired smoothness properties, the Darcyan coordinate system is welldeﬁned for all of S. It has the property that the level curves of each coordinate always, or the coordinate axes,intersect at right angles.Figure 2 shows several examples of the Darcyan coordinate system drawn on facial surfaces. Note that inpractice the measurement errors associated with computation of ﬂow lines on S may result in the coordinateaxes that are not orthogonal.

6 A. Srivastava et al.3 Elastic Matching/Deformation of Darcyan Level CurvesOnce the Darcyan coordinate system is established, the task of elastically matching two surfaces can bedecomposed into simpler components. There are two ways of decomposing φ(ξ1, ξ2): (i) into φ2(ξ2)φ1(ξ1; ξ2)and (ii) into φ2(ξ2)φ1(ξ1; ξ2). In the former decomposition, we ﬁrst match the level curves of ξ1, to ﬁnd φ1,and then for each pair of matched curves we ﬁnd φ2. This procedure is reversed for the latter decomposition.Similar to [24], we choose the former in this paper since the level curves of ξ1 are more interesting andintuitively look more useful in shape analysis. We remark that the level curves of ξ2 form facial proﬁles andwere used in [2] for face recognition. We start by describing the estimation of φ2: for a matched pair of curves Cξ11 and Cξ2 , each generated as alevel curve from a diﬀerent facial surface, our goal is to ﬁnd a mapping φ2 : ξ2 → ξ2 that is a diﬀeomorphismand it minimizes the elastic distance (to be deﬁned) between the two curves. We treat the two curves asclosed, parameterized curves in R3 with ﬁxed origins for parameterizations. Furthermore, we rescale themto be of the same length, say 2π. This viewpoint allows us to use one of many methods already availablefor an elastic analysis of closed curves. The key idea in elastic analysis is that the mapping φ2 is nonlinear,i.e. points that are matched together are at nonlinear distances from their origins. Such a matching canbe considered as an elastic matching, as one curve has to (locally) stretch, compress and bend to matchthe other. Several authors, starting with Younes [30], followed by Michor & Mumford [19], Mio et al. [21],and more recently Joshi et al. [11,10] have studied elastic analysis of curves. The main diﬀerence in theseapproaches is the choice of the representation of a curve. Here we adopt the approach presented in Joshiet al. [11,10] because it greatly simpliﬁes the elastic shape analysis. As stated earlier, we will provide notonly a matching of points across curves but also obtain an optimal deformation of one curve into the otherunder the elastic metric. Mathematically, this is accomplished by deﬁning a space of closed curves of interest,imposing a Riemannian structure on it using the elastic metric, and computing geodesic paths under thismetric. These geodesic paths can then be interpreted as optimal elastic deformations of curves. We brieﬂy summarize the approach taken in [11, 10] for elastic comparison of closed curves in R3. For theinterval I ≡ [0, 2π], let β : I → R3 be a parameterized curve with a non-vanishing derivative everywhere. Werepresent its shape by the function q : I → R3 deﬁned as: q(s) = √ β˙ (s) ∈ R3. Here, || · || ≡ (·, ·)R3 , and ||β˙ (s)||(·, ·)R3 is taken to be the standard Euclidean inner product in R3. The quantity ||q(s)|| is the square-root of q(s)the instantaneous speed of the curve β, whereas the ratio ||q(s)|| is the direction for each s ∈ [0, 2π) along thecurve. Let Q ≡ {q = (q1, q2, q3)|q(s) : I → R3, q(s) = 0, ∀s} be the space of all square integrable functionsin R3. This is an open subset of the inﬁnite-dimensional vector space of all functions in L2(I). The closurecondition for a →curRve4,βwrietqhuciorems ptohnaetnt0s2:π β˙ (s)ds = 0, which translates to 2π ||q(s)||q(s) ds = 0. We deﬁne amapping G : Q 0 G1 = q1(s) ||q(s)||ds, G2 = q2(s) ||q(s)||ds, G3 = q3(s) ||q(s)||ds, G4 = q(s) 2ds = 1 . IIIIThe space obtained by the inverse image C = G−1(0) is the space of all closed curves of a unit length, andthis representation is invariant to translation and scaling. C is endowed with a Riemannian structure usingthe metric: for any two tangent vectors v1, v2 ∈ Tq(C), we deﬁne v1, v2 = (v1(s), v2(s))R3 ds . (1) IIt is shown in [10] that this metric is equivalent to the elastic metric described in [21]. With this Riemannian strucutre, we want a tool to compute geodesic paths between arbitrary elementsof C. There have been two prominent numerical approaches for computing geodesic paths on nonlinearmanifolds. One approach uses the shooting method ([15,21]) where, given a pair of shapes, one ﬁnds atangent direction at the ﬁrst shape such that its image under the exponential map reaches as close to thesecond shape as possible. The search for the tangent direction uses an iterative technique that iterativelyreﬁnes the tangent vector (shooting direction) using the gradient of a shooting error. We will use another,more stable approach that uses path-straightening ﬂows to ﬁnd a geodesic between two shapes. In thisapproach, the given pair of shapes is connected by an initial arbitrary path that is iteratively “straightened”so as to minimize its length. The path-straightening method, proposed by Klassen et al [14], overcomes

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 7(a) 6 (c) 5 4 3 2 1 0 0123456 6 5 4 3 2 1 0 0123456 7 6 5 4 3 2 1 0 0123456 6 5 4 3 2 1 0 0123456 (b)Fig. 3 Elastic matching/deformation of closed, planar curves to demonstrate our matching algorithm. (a) the match-ing points across the curves, (b) optimal matching functions γ, and (c) the optimal elastic deformation.some of the practical limitations in the shooting method. Other authors, including Schmidt et al. [25] andGlaunes et al [5], have also presented variational techniques for ﬁnding optimal matches. Given two curves,represented by q0 and q1, our goal is to ﬁnd a geodesic between them in C. Let α : [0, 1] → C be any pathconnecting q0, q1 in C, i.e. α(0) = q0 and α(1) = q1. Then, the critical points of the energy E[α] = 1 1 dt (2) 2 α˙ (t), α˙ (t) 0are geodesics in C (this result is true on a general manifold [26]). The inner product is deﬁned in Eqn. 1.As described by Klassen et al. [14] for general shape manifolds, and by Joshi et al. [11] for this particularrepresentation of curves, one can use a gradient approach to ﬁnd a critical point of E and reach a geodesic.The distance between the two curves q0 and q0 is given by the length of the geodesic α: 1 dc(q1, q2) = ( α (t), α (t) )1/2dt . 0We call this the elastic distance in deforming the curve represented by q0 to the curve represented by q1. Similar to Kendall’s shape formulation [13], we would like to study shapes of curves as equivalences underrigid motions, uniform scaling and other such “shape-preserving” transformations. Since translation, scaling,and location of origin are already accounted for, we need to remove the variability associated with rotationsand origin-preserving (positive) diﬀeomorphisms on I. In other words, the shape space for analyzing shapesof closed curves in R3 is given by S = C/(SO(3) × D), where SO(3) is the three-dimensional rotation groupand D is the set of origin-preserving positive diﬀeomorphisms on I. The task of ﬁnding a geodesic in S isthat of ﬁnding a geodesic in C that achieves the distance: ds(q1, q2) = min dc(q1, γ · (Oq2)) , (3) γ∈D,O∈SO(3)

8 A. Srivastava et al. 6 5 4 3 2 1 0 0123456 6 5 4 3 2 1 0 0123456 6 5 4 3 2 1 0 0123456Fig. 4 Elastic matching of facial curves. The left and middle panels show two views of the matching points acrossthe curves, while the right panels show optimal matching functions γ.where γ · q2 is the re-parametrization of q2 according to the formula: √γ˙ q2(γ). As described in [10], one cansolve for this minimization on D × SO(3) using a gradient iteration. We refer the reader to that paper forfurther details.We illustrate these ideas through some experimental results. Firstly, we present some examples of elasticmatching between points across planar shapes in Figure 3. Shown in the left column are four pairs of shapesand the optimal matching of points across each pair. The optimal matching function for each pair is shownin the middle column of this ﬁgure. Nonlinearity of this matching function emphasizes the elastic nature ofthis matching. The rightmost column shows the geodesic paths between the shapes in each pair. One canalso view these paths as optimal elastic deformations of one curve into another. Figure 4 shows similar matching examples for facial curves Cξ11 and SCinξ21c.e Each row shows an examplefrom two diﬀerent viewing angles and the optimal matching function γ. facial curves, in general, aremore similar to each other, than the examples in Figure 3, the matching function is relatively closer to astraight line. Finally, Figure 5 presents the corresponding geodesic paths between facial curves in S under theelastic metric. In each case, the ﬁrst and the last curve are the examples of Cξ11 and Cpξ2r1ovainddesthoepitnimtearml eeldaisatticecurves are points along the geodesic path connecting them. These geodesic pathdeformations of one facial curve into another.4 Elastic Matching of Curves Across Facial SurfacesNow that we have tools for elastically deforming arbitrary closed curves into each other, we consider theproblem of matching curves across two indexed collections, {inCitξ11ia|ξll1y∈fo[r0m, uu1la]}teatnhde{pCrξo21b|lξe1m∈in[0,thue1]c}o. nHteinreuuCmξi1,is the level curve at ξ1 for the facial surface Si, i = 1, 2. Webut later discretize the domain for a computational solution. Let φ1 : [0, u1] → [0, u1] be a diﬀeomorphicmapping that minimizes the cost function: u1 ds(Cξ11 , Cφ21(ξ1))2dξ1 , Es[φ1; 0, u1] = (4) 0where ds is as described in Eqn. 3. The solution requires a search over the inﬁnite-dimensional space of alldiﬀeomorphisms from [0, u1] to [0, u1]. There exists a computational approach to solving this type of problem

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 9Fig. 5 Examples of optimal elastic deformations between facial curves extracted as level curves of ξ1.Fig. 6 Left: An example of a φ1 function restricted to a ﬁnite graph. Right: An illustration of some nodes that areallowed to go to (i/n, j/n) point on the graph.in situations where the domains [0, u1] and [0, u1] are sampled uniformly to generate a ﬁnite number of points.This solution is described next. For the notational convenience we will scale ξ1 → ξ1/u1, ξ2 → ξ2/u2 so thatthey both take values in [0, 1], and we seek an optimal φ1 on D[0,1], the set of all diﬀeomophisms from [0, 1]to itself. Let each surface be sampled uniformly in ξ1 at n points, each giving rise to a discrete (indexed) collectionof n curves in C. This results in an n × n graph, of the type shown in Figure 6, whose nodes denotepossible matchings of corresponding curves from the two surfaces. The goal is now to ﬁnd a piecewise linearφ1 ∈ D[0,1], i.e. a curve that passes through the nodes on the graph, that minimizes the energy function givenin Eqn. 4, and we do so using dynamic programming (DP). DP is useful in ﬁnding optimal paths betweenany two points on a ﬁnite graph when the cost associated with the path is additive over its segments. Thepiecewise-linear path between the points (0, 0) to (1, 1) is constrained to be such that: (i) the slope is alwayspositive along the path, and (ii) it minimizes the elastic energy. To evaluate the elastic energy we will needthe term ds(C(1i/n), C(2j/n)) for all i, j. These are calculated using the tools described in the last section. Consider a uniform, n × n grid in R2 such that the bottom left maps to (0, 0) and the top right mapsto indices (1, 1) on this grid, as shown in Figure 6. For any point (i/n, j/n), for 0 < i, j ≤ n, let Nij be the

10 A. Srivastava et al. 70 70 60 60 50 51 40 41 30 31 20 21 10 11Fig. 7 Left: Elastic matching of curves across two collections of curves. Each collection represents a facial surfacesampled using 70 level curves of ξ1. The middle and the right panel show a sub-sampled set of matched curves acrossthe two collections.set of indices that are allowed to go to (i/n, j/n). In principle, all the points (k/n, l/n) such that k < i andl < j are valid, but one may restrict to a smaller set to seek a computationally eﬃcient approximation. LetL(k, l; i, j) denote a straight line joining the pairs (k/n, l/n) and (i/n, j/n). Then, the iterative optimizationproblem is: (kˆ, ˆl) = argmin Es[L(k, l; i, j); k/n, i/n] , (k,l)∈Nij (5)with Es as deﬁned in Eqn. 4. Deﬁne the minimum energy of reaching the point (i/n, j/n), in an iterativefashion as: Hs(i/n, j/n) = E[L(kˆ, ˆl; , j), kˆ/n, i/n] + Hs(kˆ/n, ˆl/n) , with H(0, 0) = 0 .The optimization problem in Eqn. 5 is solved sequentially for each point (i/n, j/n), starting from (0, 0) andincreasing i/n, j/n until the last point (1, 1). Tracing the path that results in the optimal elastic energyHs(1, 1) provides a discrete version of the optimal φ1. The set of nodes on the graph, contained in optimalφ1, provide the matching pairs in the two collections. Shown in Figure 7 is an example of this idea forn = 70. The left panel shows pictorial view of the function H with darker shade corresponding to lowerenergy. Overlaid on this picture is the plot of optimal φ1 for this case. Shown in the two panels on the rightare the corresponding pairs of curves Cξ11 and Cξ22 . Only the matching curves, associated with the nodes thatlie on optimal φ1, are shown for clarity. According to this ﬁgure, the 69th curve in the ﬁrst surface matchesthe 70th curve in the second, the 65th curve in the ﬁrst surface matches the 66th curve in the second, and soon.5 Elastic Deformation of Facial SurfacesThe previous two sections provide the solutions for solving optimal mappings φ2 (Section 3) and φ1 (Section4). Together they provide an elastic matching of points across the two facial surfaces according to φ∗(ξ1, ξ2) =φ1(ξ1), φ2(ξ2; ξ1). With this matching we can accomplish a number of tasks.– Comparing Matched Faces: In case we are interested in simply comparing the two shapes, i.e. quan-tifying the diﬀerences between the shapes of faces, we can do that as follows. Deﬁne a set of (local)geometric properties of a facial surface by κ. For instance, κ may include curvature tensor, velocity, tor-sion, or position along facial curves. Then, one can quantify diﬀerences between any two matched surfacesusing: 1/2 S1 − S2 ≡ dκ(κ1(ξ), κ (φ(ξ)))2dξ . (6) Ξ– Deforming Facial Surfaces: However, if the goal is to ﬁnd an optimal elastic deformation from one facial surface to another. The construction of geodesic paths between Darcyan curves in Section 3, using

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 11Fig. 8 Example 1: Optimal deformations of facial surfaces into each other, both belonging to the same person, underthe elastic energy.Fig. 9 Example 2: Optimal deformations of a facial surface into another, belonging to a diﬀerent person, under theelastic energy.an elastic metric, allows us to achieve this goal. This construction not only provides an optimal matchingof points across two curves, but also it provides an optimal deformation of one Darcyan curve into another.Applying this idea repeatedly to each pair of registered curves gives us a full elastic deformation fromone face to another. If we view each facial surface as an indexed collection of curves, indexed by ξ1, thisidea provides a path on the space of such collections, in going from one face to another. We will denotethis path by Ω, where Ω(t), for any t ∈ [0, 1] is an indexed collection of points in S. This path is optimalin the sense that it minimizes the total energy: u1 ds(Cξ11 , Cφ21∗(ξ1))2dξ1 .d(S1, S2) ≡ (7) 0Shown in Figures 8 - 9 are examples of these deformations. Figure 8 shows two examples of deformingfacial surfaces, one into another, when they both belong to the same person. These deformations show someartifacts of using a small n; a larger value improves the approximation of the underlying optimal deformationbut also increases the computational cost. Similarly, Figure 9 shows two examples of elastic deformationswhen the faces belong to diﬀerent persons.

12 A. Srivastava et al. 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0Fig. 10 Matrix of pairwise distances between 12 facial surfaces using the distance given in Eqn. 7. The ﬁrst six facesbelong to the same person while the remaining six are all diﬀerent individuals. This solution also provides an elastic distance (eqn. 7) between individual facial surfaces. To illustratethe usefulness of this distance, we show a matrix of pairwise distances between 12 faces in Figure 10, sixof which belong to the same person while the remaining six belong to diﬀerent persons. In this display, thedistances have been scaled to take value between 0 and 1. As expected, the distances between faces of sameperson are much smaller compared to the distances between faces of diﬀerent persons.6 SummaryWe have presented a framework for analyzing shapes of facial surfaces for the purposes of matching, com-paring, and deforming them. The main contribution is the introduction of a Darcyan coordinate system,a system that is intrinsic to a facial surface. This system is centered at the tip of the nose and its twocoordinates ξ1 and ξ2 specify distances from this tip and the plane of symmetry, respectively. In this co-ordinate system, the task of elastic matching and deforming is broken into two distinct components. Onecomponent matches level curves of each surfaces, and the other component matches points along each pair ofmatched curves. These tasks are performed using geodesics on appropriate manifolds of curves and surfaces,with Riemannian metrics that measure elastic deformation. In other words, geodesics provide the optimaldeformations of curves and surfaces across faces.AcknowledgementsThe authors would like to thank CNRS, France, for a visiting Professorship to Anuj Srivastava, and Groupedes Ecole de Telecommunications for their support. This research was also supported in part by the grantsARO W911NF-04-1-0268, ARO W911NF-04-1-0113, and AFOSR FA9550-06- 10324.References 1. P.J. Besl and N.D. McKay. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239–256, February 1992. 2. C. Beumier and M. Acheroy. Automatic 3D face authentication. Journal of Image and Vision Computing, 18(4):315–321, 2000. 3. K. I. Chang, K. W. Bowyer, and P. J. Flynn. Multiple nose region matching for 3D face recognition under varying facial expression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10):1695–1700, 2006. 4. J. Glaunes, A. Trouv´e, and L. Younes. Diﬀeomorphic matching of distributions: A new approach for unlabelled point-sets and sub-manifolds matching. In CVPR (2), pages 712–718, 2004. 5. J. Glaunes, A. Trouve, and L. Younes. Modeling planar shape variation via hamiltonian ﬂows of curves. In H. Krim and A. Yezzi, editors, Statistics and Analysis of Shapes. Birkhauser, 2006.

Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 13 6. U. Grenander. General Pattern Theory. Oxford University Press, 1993. 7. U. Grenander and M. I. Miller. Computational anatomy: An emerging discipline. Quarterly of Applied Mathe- matics, LVI(4):617–694, 1998. 8. U. Grenander, A. Srivastava, and S. Saini. A pattern-theoretic characterization of biological growth. IEEE Transactions on Medical Imaging, 26(5):648–659, 2007. 9. C. Hesher, A. Srivastava, and G. Erlebacher. A novel technique for recognizing faces using range images. In Proceedings of ISSPA, 2003, Paris, France, 2003.10. S. H. Joshi, E. Klassen, and A. Srivastava. An eﬃcient representation for computing geodesics between shapes of n-dimensional curves. Technical report, Department of Statistics, Florida State University, 2007.11. S. H. Joshi, E. Klassen, A. Srivastava, and I. H. Jermyn. An eﬃcient representation for computing geodesics between n-dimensional elastic shapes. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2007.12. I. A. Kakadiaris, G. Passalis, G. Toderici, M. N. Murtuza, N. Karampatziakis, and T. Theoharis. Three- dimensional face recognition in the presence of facial expressions: An annotated deformable model approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(4):1–10, 2007.13. David G. Kendall. Shape manifolds, procrustean metrics and complex projective spaces. Bulletin of London Mathematical Society, 16:81–121, 1984.14. E. Klassen and A. Srivastava. Geodesics between 3D closed curves using path straightening. In European Conference on Computer Vision, vol. I, pages 95–106, 2006.15. E. Klassen, A. Srivastava, W. Mio, and S. H. Joshi. Analysis of planar shapes using geodesic paths on shape spaces. IEEE Trans. Pattern Analysis and Machine Intelligence, 26(3):372–383, 2004.16. C. Kotropoulos, A. Tefas, and I. Pitas. Frontal face authentication using morphological elastic graph matching. IEEE Transactions on Image Processing, 9(4):555–560, April 2000.17. X. Lu and A. K. Jain. Deformation analysis for 3D face matching. In Proc. 7th IEEE Workshop on Applications of Computer Vision, pages 99–104. Breckenridge, CO, 2005.18. X. Lu, A. K. Jain, and D. Colbry. Matching 2.5d face scans to 3d models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(1):31–43, Jan. 2006.19. P. W. Michor and D. Mumford. Riemannian geometries on spaces of plane curves. J. Eur. Math. Soc., 8:1–48, 2006.20. M. I. Miller and L. Younes. Group actions, homeomorphisms, and matching: A general framework. Intl. Journal of Computer Vision, 41(1/2):61–84, 2001.21. W. Mio, A. Srivastava, and S. H. Joshi. On shape of plane elastic curves. International Journal of Computer Vision, 73(3):307–324, 2007.22. R. Osada, T. Funkhouser, B. Chazells, and D. Dobkin. Matching 3D models with shape distributions. In IEEE Shape Modeling International, May 2001.23. C. Samir, A. Srivastava, and M. Daoudi. Three-dimensional face recognition using shapes of facial curves. IEEE Transactions on Pattern Analysis and Pattern Recognition, 28(11):1858–1863, 2006.24. C. Samir, A. Srivastava, M. Daoudi, and E. Klassen. An intrinsic framework for analysis of facial surfaces. International Journal of Computer Vision, in review, 2007.25. F. R. Schmidt, M. Clausen, and D. Cremers. Shape matching by variational computation of geodesics on a man- ifold. In Pattern Recognition (Proc. DAGM), volume 4174 of LNCS, pages 142–151, Berlin, Germany, September 2006. Springer.26. Michael Spivak. A Comprehensive Introduction to Diﬀerential Geometry, Vol I & II. Publish or Perish, Inc., Berkeley, 1979.27. S. Wang, Y. Wang, M. Jin, Xianfeng Gu, and Dimitris Samaras. 3D surface matching and recognition using conformal geometry. In CVPR (2), pages 2453–2460, 2006.28. Y. Wang, M.-C. Chiang, and P. Thompson. Mutual information-based 3d surface matching with applications to face recognition and brain mapping. In International Conference on Computer Vision, 2005.29. L. Wiskott, J.-M. Fellous, N. Kru¨ger, and C. von der Malsburg. Face recognition by elastic bunch graph matching. In L. C. Jain, U. Halici, I. Hayashi, and S. B. Lee, editors, Intelligent Biometric Techniques in Fingerprint and Face Recognition, chapter 11, pages 355–396. CRC Press, 1999.30. L. Younes. Computable elastic distance between shapes. SIAM Journal of Applied Mathematics, 58(2):565–586, 1998.

# Elastic Shape Models for Face Analysis Using Curvilinear ...

##
**Description: ** Elastic Shape Models for Face Analysis Using Curvilinear Coordinates 3 and translations). The fact that it deforms with the changes in facial expressions provides a ...

### Read the Text Version

No Text Content!

- 1 - 13

Pages: