11.1 Introduction

The problem of shape analysis of objects is very important with applications across all areas. Specifically, the shape analysis of curves in Euclidean spaces is important with widespread applications in biology, computer vision, and medical image analysis. For instance, the functionality of biological objects, such as proteins, RNAs, and chromosomes, is often closely related to their shapes, and we would like statistical tools for analyzing such shapes to understand their functionalities. These tools include metrics for quantifying shape differences, geodesics to study deformations between shapes, shape summaries (including means, covariances, and principals components) to characterize shape population, and statistical shape models to capture shape variability. Consequently, a large number of mathematical representations and approaches have been developed to analyze shapes of interest. Depending on their goals, these representations can differ vastly in their complexities and capabilities.

Shape analysis naturally involves elements of differential geometry of curves and surfaces. In the appendix we summarize some concepts and notions from differential geometry that are useful in any approach to shape analysis. Specifically, we introduce the concepts of a Riemannian metric, geodesics, group actions on manifolds, quotient spaces, and equivalence relations using orbits. We also provide some simple examples to illustrate them to a reader not familiar with these concepts. Given these items, we can layout a typical approach to shape analysis. A typical framework for shape analysis takes the following form. We start with a mathematical representation of objects—as vectors, matrices, or functions—and remove certain shape-preserving transformations termed as preprocessing. The remaining transformations, the ones that cannot be removed as preprocessing, as removing by forming group actions and quotient spaces.

David Kendall [10] provided one of the earliest formal mathematical frameworks for quantifying shapes. In this framework we start with a finite set of points, termed landmarks, that represent an object and removes the effects of certain transformation groups, namely rigid motions and global scaling, to reach final shape representations. As depicted in Fig. 11.1, the key idea is to remove two groups via preprocessing—remove translation group by centering landmarks and remove size group by rescaling landmark vector—and reach a constrained space called the preshape space. The remaining transformation, the rotation in this case, is removed by forming orbits under this group action, or equivalence classes, and imposing a metric on this quotient space of orbits. We introduce the concepts of equivalence relations, group actions, orbits, and quotient spaces in the Appendix. A number of prominent researchers have subsequently developed this framework into a rich set of statistical tools for practical data analysis [3,17,11,6].

One of the most important challenges in shape analysis is registration. Registration stands for densely matching points across objects and using this registration for comparing shapes and developing shape models. Historically, some approaches presume that objects are already perfectly registered, whereas some other approaches use off-the-shelf methods to preregister before applying their own shape analysis. Whereas a presumption of perfect registration is severely restrictive, the use of registration as a preprocessing step is also questionable, especially when the metrics for registration have no bearing on the metrics used in ensuing shape analysis and modeling. A better solution, one that has gained recognition over the last few years, is an approach called elastic shape analysis. Here we incorporate a solution for performing registration along with the process of shape comparisons, thus resulting in a unified framework for registration, shape comparisons, and analysis. The key idea here is to endow the shape space with an elastic Riemannian metric that has an appropriate invariance under the action of the registration group (and other nuisance groups). Whereas such elastic metrics are somewhat complicated to be of use directly, especially for analyzing large datasets, there is often a square-root transformation that simplifies them into the standard Euclidean metric. This point of view is the main theme of this chapter.

In this chapter we focus on the problem of shape analysis of curves in Euclidean spaces and provide an overview of this problem area. This setup includes, for example, shape analysis of planar curves that form silhouettes of objects in images or shape analysis of space curves representing complex biomolecular structures, such as proteins and chromosomes. A particular case of this problem is when we restrict to curves in $\mathbb{R}$, that is, we analyze shapes of real-valued functions on a fixed interval. This fast growing area in statistics, called functional data analysis [16], deals with modeling and analyzing data, where observations are functions over intervals. The use of elastic Riemannian metrics and square-root transformations for curves was first proposed by [22,23] although this treatment used complex arithmetic and was restricted to planar curves. Later on, [15] presented a family of elastic metrics that allowed for different levels of elasticity in shape comparisons. Joshi et al. [9] and Srivastava et al. [19] introduced a square-root representation, slightly different from that of Younes, which was applicable to curves in any Euclidean space. Subsequently, several other elastic metrics and square-root representations, each representing a different strength and limitation, have been discussed in the literature [25,1,2,12,24]. In this chapter we focus on the framework of [9] and [19] and demonstrate that approach using a number of examples involving functional and curve data.

We mention in passing that such elastic frameworks have also been developed for curves taking values on nonlinear domains also, including unit spheres [26], hyperbolic spaces [5,4], the space of symmetric positive definite matrices [27], and some other manifolds. Additionally, elastic metrics and square-root representations have also been used to analyze shapes of surfaces in ${\mathbb{R}}^3$. These methods provide techniques for registration of points across objects, as well as comparisons of their shapes, in a unified metric-based framework. For details, we refer the reader to a text book by [8] and some related papers [7,21,13].

11.2 Registration problem and elastic approach

Using a formulation similar to Kendall's approach, we provide a comprehensive framework for comparing shapes of curves in Euclidean spaces. The key idea here is to study curves as (continuous) parameterized objects and to use parameterization as a tool for registration of points across curves. Consequently, this introduces an additional group, namely the re-parameterization group, which is added in the representation and needs to be removed using the notion of equivalence class and quotient spaces.

11.2.1 The ${\mathbb{L}}^2$ norm and associated problems

As mentioned earlier, the problem of registration of points across curves is important in comparisons of shapes of curves. To formalize this problem, let Γ represent all boundary-preserving diffeomorphisms of $[0,1]$ to itself. Elements of Γ play the role of re-parameterization (and registration) functions. Let $\mathcal{F}$ be the set of all absolutely continuous parameterized curves of the type $f:[0,1]\to {\mathbb{R}}^n$. For any $f\in \mathcal{F}$ and $\gamma \in \mathrm{\Gamma }$, the composition $f\circ \gamma$ denotes a reparameterization of f. Note that both f and $f\circ \gamma$ go through the same set of points in ${\mathbb{R}}^n$ and thus have exactly the same shape. Fig. 11.2 shows an example of reparameterization of a semicircular curve f. The top row shows three γ's, and the bottom row shows the corresponding parameterizations of f. For any $t\in [0,1]$ and any two curves $f_1,f_2\in \mathcal{F}$, the points $f_1(t)$ and $f_2(t)$ are said to be registered to each other. If we re-parameterize $f_2$ by γ, then the registration of $f_1(t)$ changes to $f_2(\gamma (t))$ for all t. In this way the reparameterization γ controls registration of points between $f_1$ and $f_2$. On one hand, reparameterization is a nuisance variable since it preserves the shape of a curve but, and on the other hand, it is an important tool in controlling registration between curves.

To register two curves, we need an objective function that evaluates and quantifies the level of registration between them. A natural choice will use the ${\mathbb{L}}^2$ norm, but it has some unexpected pitfalls as described next. Let $\Vert f\Vert$ represent the ${\mathbb{L}}^2$ norm, that is, $\Vert f\Vert =\sqrt{{\int }_0^1|f(t){|}^{2}dt}$, of a curve f, where $|\cdot |$ inside the integral denotes the ${\ell }^2$ norm of a vector. The ${\mathbb{L}}^2$ norm provides the most commonly used Hilbert structure in functional data analysis. Despite its popularity, there are problems with this metric. The main problem is that as an objective function for registration, it leads to a degeneracy, called the pinching effect. In other words, if we try to minimize $\Vert f_1-f_2\circ \gamma \Vert$ over γ, this quantity can be made infinitesimally small despite $f_1$ and $f_2$ being very different functions. Fig. 11.3 shows a simple example to illustrate this idea using scalar functions on $[0,1]$. The top left panel of the figure shows to functions $f_1$, $f_2$ that agree at only one point $t=0.5$ in the domain. We design a sequence of piecewise-linear time-warping functions γs (shown in the bottom row) that increasingly spend time at $t=0.5$ from left to right, resulting in the steady decrease in the ${\mathbb{L}}^2$ norm $\Vert f_1\circ \gamma -f_2\circ \gamma \Vert$. Continuing this process, we can arbitrarily decrease the ${\mathbb{L}}^2$ norm between two functions, irrespective of the other values of these functions. Thus an optimization problem of the type ${\inf }_{\gamma \in \mathrm{\Gamma }}\Vert f_1-f_2\circ \gamma \Vert$ has degenerate solutions. This problem is well recognized in the literature [16,14], and the most common solution used to avoid pinching is to penalize large warpings using roughness penalties. More precisely, we solve an optimization problem of the type

$\underset{\gamma \in \mathrm{\Gamma }}{\inf }({\Vert f_1-f_2\circ \gamma \Vert }^2+\lambda \mathcal{R}(\gamma )),$

(11.1)

where $\mathcal{R}(\gamma )$ measures the roughness of γ. Examples of $\mathcal{R}$ include $\int \dot{\gamma }{(t)}^{2}dt$, $\int \ddot{\gamma }{(t)}^{2}dt$, and so on. The role of $\mathcal{R}$ is to discourage large time warpings. By large we mean γs whose first or second derivatives have high norms.

Whereas this solution helps avoid the pinching effect, it often also restricts alignment of functions. Since it reduces the solution space for warping functions, it can also inhibit solutions that correctly require large deformations. Fig. 11.4 shows an example of this problem using two functions $f_1$ and $f_2$ shown in the top left panel. In this example we use the first order penalty ($\int \dot{\gamma }{(t)}^{2}dt$) in Eq. (11.1) and study several properties of the resulting solution—does to align the functions well, is the solution symmetric in the functions $f_1$ and $f_2$, does it have pinching effect, and how sensitive is the solution to the choice of λ? In each row, for a certain value of λ, we first obtain an optimal value of γ in Eq. (11.1). Then, to study the symmetry of the solution, we swap $f_1$ and $f_2$ and solve this optimization again. Finally, we compose the two resulting optimal warping functions. If the composition is a perfect identity function ${\gamma }_{id}(t)=t$, then the solution is called inverse consistent (and symmetric), otherwise not. In the first row, where $\lambda =0$, we see that the solution is inverse consistent, but there is substantial pinching, as expected. As we increase λ (shown in the second row), the level of pinching is reduced, but the solution also shows a small inconsistency in the forward and backward solutions. In the last row, where λ is large, the pinching effect is gone, but inverse inconsistency has increased. Also, due to increased penalty, the quality of alignment has gone down too. This discussion also points an obvious limitation of methods involving penalty terms. We need to decide which type of penalty and how large λ should be used in real situations. In contrast to the penalized ${\mathbb{L}}^2$ approach, the elastic approach described in this chapter results in the solution shown in the bottom row. This solution is inverse consistent, rules out the pinching effect (and does not need any penalty or choice of λ), and achieves an excellent registration between the functions. Additionally, the computational cost is very similar to the penalized ${\mathbb{L}}^2$ approach.

Lack of invariance under ${\mathbb{L}}^2$ norm  To study the shape of curves, we need representations and metrics that are invariant to rigid motions, global scale, and reparameterization of curves. The biggest challenge comes from the last group since it is an infinite-dimensional group and requires closer inspection. To understand this issue, take an analogous task of removing the rotation group in Kendall's shape analysis, where each object is represented by a set of landmarks. Let $X_1,X_2\in {\mathbb{R}}^{n\times k}$ represent two sets of landmarks (k landmarks in ${\mathbb{R}}^n$), and let $SO(n)$ be the set of all rotations in ${\mathbb{R}}^n$. To (rotationally) align $X_2$ to $X_1$, we solve for a Procrustes rotation according to ${\mathrm{argmin}}_{O\in SO(n)}{\Vert X_1-O{X}_2\Vert }_F$, where ${\Vert \cdot \Vert }_F$ denotes the Frobenius norm of matrices. In other words, we keep $X_1$ fixed and rotate $X_2$ into a configuration that minimizes the Frobenius norm between them. The choice of Frobenius norm is important because it satisfies the following property:

$\Vert X_1-X_2\Vert =\Vert O{X}_1-O{X}_2\Vert \text{for all}{X}_1,X_2\in {\mathbb{R}}^{n\times k},O\in SO(n).$

(11.2)

If this property was not satisfied, we would not be able to perform Procrustes rotation. In mathematical terms we say that the action of $SO(n)$ on ${\mathbb{R}}^{n\times k}$ is by isometries under the Frobenius norm or that the metric is invariant under the rotation group action. (Please refer to the Appendix for a proper definition of isometry under group actions.) A similar approach is needed for performing registration and removing the reparameterization group in the case of functions and curves. However, it is easy to see that $\Vert f_1-f_2\Vert \ne \Vert f_1\circ \gamma -f_2\circ \gamma \Vert$ in general. In fact, Fig. 11.3 already provides an example of this inequality. Since ${\mathbb{L}}^2$ norm is not preserved under identical reparameterizations of curves, it is not suitable for use in registration and shape analysis. Thus we seek a new metric to accomplish registration and shape analysis of curves.

11.2.2 SRVFs and curve registration

Now we describe an elastic approach that addresses these issues and provides a fundamental tool for registration and shape analysis of curves.

As earlier, let $\mathcal{F}$ be the set of all absolutely continuous parameterized curves in ${\mathbb{R}}^n$, and let Γ be the same of all reparameterization functions. Define the square-root velocity function (SRVF) [19,18] of f as a mathematical representation of f given by

$q(t)=\{\begin{array}{cc}\hfill \frac{\dot{f}(t)}{\sqrt{|\dot{f}(t)|}},\hfill & \hfill |\dot{f}(t)|\ne 0,\hfill \\ \hfill 0,\hfill & \hfill |\dot{f}(t)|=0.\hfill \end{array}$

(11.3)

In case of $n=1$ this expression simply reduces to $q(t)=\text{sign}(\dot{f}(t))\times \sqrt{|\dot{f}(t)|}$. Here are some important properties associated with this definition.

• •  If f is absolutely continuous, as assumed, then q is square integrable, that is, $\Vert q\Vert <\infty$.
• •  This transformation from f to q is invertible up to a constant, with the inverse given by $f(t)=f(0)+{\int }_0^{t}q(s)|q(s)|ds$. In fact the mapping $f\mapsto (f(0),q)$ is a bijection between $\mathcal{F}$ and $\mathbb{R}\times {\mathbb{L}}^2([0,1],{\mathbb{R}}^n)$.
• •  If f is reparameterized by $\gamma \in \mathrm{\Gamma }$ to result in $f\circ \gamma$, the SRVF change from q to $(q\circ \gamma )\sqrt{\dot{\gamma }}\stackrel{\mathrm{\Delta }}{=}(q\star \gamma )$. In other words, the action of Γ on ${\mathbb{L}}^2$ is given by $q\star \gamma$. Also, if a curve is rotated by a matrix $O\in SO(n)$, then its SRVF gets rotated by the same matrix O, that is, the SRVF of a curve Of is given by Oq.
• •  The length of the curve f, given by $L[f]={\int }_0^1|\dot{f}(t)|dt$, is equal to the ${\mathbb{L}}^2$ norm of its SRVF q, that is, $L[f]=\Vert q\Vert$.
• •  The most important property of this representation is preservation of the ${\mathbb{L}}^2$ norm under time warping or reparameterization, that is,

$\Vert q_1-q_2\Vert =\Vert (q_1\star \gamma )-(q_2\star \gamma )\Vert ,\forall q_1,q_2\in {\mathbb{L}}^2([0,1],{\mathbb{R}}^n),\gamma \in \mathrm{\Gamma }.$

(11.4)

• We already know that ${\mathbb{L}}^2$ norm is preserved under identical rotation, that is, $\Vert q_1-q_2\Vert =\Vert O{q}_1-O{q}_2\Vert$.

In view of the invariant property, this representation provides a proper setup for registration of functional and curve data.

Definition 11.1

Pairwise registration

Given two curves $f_1,f_2\in \mathcal{F}$ and their SRVFs $q_1,q_2\in {\mathbb{L}}^2([0,1],{\mathbb{R}}^n)$, we define their registration to be the optimization problem

$\underset{\gamma \in \mathrm{\Gamma },O\in SO(n)}{\inf }\Vert q_1-O(q_2\star \gamma )\Vert =\underset{\gamma \in \mathrm{\Gamma },O\in SO(n)}{\inf }\Vert q_2-O(q_1\star \gamma )\Vert .$

(11.5)

We make a few remarks about this registration formulation.

1. 1.  No Pinching: Firstly, this setup does not have any pinching problem. A special case of the isometry condition is that $\Vert q\star \gamma \Vert =\Vert q\Vert$ for all q and γ. In other words, the action of Γ on ${\mathbb{L}}^2$ is norm preserving. Thus pinching is not possible in this setup.
2. 2.  No Need for a Penalty Term: Since there is no pinching, we do not have to include any penalty term in this setup. Therefore there is no inherent problem about choosing the relative weight between the data term and the penalty term. However, if we need to control the time warping or registration, beyond the basic formulation, we can still add an additional penalty term as desired.
3. 3.  Inverse Symmetry: As stated in Eq. (11.5), the registration of $f_1$ to $f_2$ results in the same solution as the registration of $f_2$ to $f_1$. The equality between the two terms in that equation comes from fact that $SO(n)$ and Γ are groups, and the isometry condition is satisfied (Eq. (11.4)).
4. 4.  Invariance to Scale and Translation: We can show that the optimizer in Eq. (11.5) does not change if either function is changed using positive scaling or translation, that is, we can replace any $f_i(t)$ with $a{f}_i(t)+c$ for any $a\in {\mathbb{R}}_{+}$ and $c\in {\mathbb{R}}^n$, and the solution does not change. This is an important requirement for shape analysis since shape is invariant to these transformations. The solution is invariant to translation because the SRVF $q_i$ is based on the of the curve $f_i$ and because

$\underset{\gamma \in \mathrm{\Gamma }}{\mathrm{arginf}}\Vert q_1-(q_2\star \gamma )\Vert =\underset{\gamma \in \mathrm{\Gamma }}{\mathrm{arginf}}\Vert a_1{q}_1-a_2(q_2\star \gamma )\Vert$

1. for any $a_1,a_2\in {\mathbb{R}}_{+}$.
2. 5.  Proper Metric: As described in the next section, the infimum in Eq. (11.5) is a proper metric itself in a quotient space and hence can be used for ensuing statistical analysis. (Please refer to the definition of a metric on the quotient space $M/G$ using an invariant metric on parent space M).

In Eq. (11.5) the optimization over $SO(n)$ is performed using the Procrustes solution:

$\begin{array}{c}{O}^{⁎}=\{\begin{array}{c}UV\text{if }\det (A)>0,\hfill \\ U\left[\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill \end{array}\right]V^T\text{otherwise,}\hfill \end{array}\hfill \end{array}$

where $A={\int }_0^1{q}_1(t)q_2^T(t)dt\in {\mathbb{R}}^{n\times n}$, and $\text{svd}(A)=U\mathrm{\Sigma }{V}^T$. The optimization over Γ is accomplished using the dynamic programming algorithm [20]. The optimization over $SO(n)\times \mathrm{\Gamma }$ is performed by iterating between the two individual solutions until convergence.

We present some examples of registration of functions and curves to illustrate this approach. In the case $n=1$ we do not have any rotation in Eq. (11.5), and one minimizes only over Γ using the dynamic programming algorithm. The last row of Fig. 11.4 shows alignment of two functions studied in that example. It shows alignments of the two functions to each other and the composition of the two γ functions resulting in a perfect identity function (confirming inverse consistency). Note that even though the optimization is performed using SRVFs in ${\mathbb{L}}^2$ space, the results are displayed in the original function space for convenience. Fig. 11.5 shows another example of registering functions using this approach.

Fig. 11.6 shows a few examples of registration of points along planar curves. In each panel we show the two curves in red (light gray in print version) and blue (dark gray in print version), and optimal correspondences across these curves using black lines, obtained using Eq. (11.5). We can see that the algorithm is successful in matching points with similar geometric features (local orientation, curvature, etc.) despite different locations of matched points along the two curves. This success in registering curves translates into a superior performance in ensuing shape analysis.

11.3 Shape space and geodesic paths

So far we have focused on an important problem of registering curves and functions. Our larger goal, of course, is the shape analysis of these objects, and registration plays an important role in that analysis. Returning to the problem of analyzing shapes, we describe the framework for an elastic shape analysis of Euclidean curves. It is called elastic because it incorporates the registration of curves as a part of their shape comparisons.

This framework follows the approach laid out in Fig. 11.1. We will use the SRVF representation of curves, reach a preshape space by removing some nuisance transformations, and form quotient space of that preshape space under the remaining nuisance transformations. Once again, let $\mathcal{F}$ be the set of all absolutely continuous curves in ${\mathbb{R}}^n$, and let ${\mathbb{L}}^2$ denote the set of square-integrable curves in ${\mathbb{R}}^n$. For any $f\in \mathcal{F}$, its length $L[f]=\Vert q\Vert$, where q is the SRVF of f. So, if we rescale f to be of unit length, then its SRVF satisfies $\Vert q\Vert =1$. Let $\mathcal{C}$ denote the unit Hilbert sphere inside ${\mathbb{L}}^2$. $\mathcal{C}$ is called the preshape space and is the set of SRVFs representing all unit length curves in $\mathcal{F}$. The geometry of $\mathcal{C}$ is simple, and we can compute distances/geodesics on $\mathcal{C}$ relatively easily. For any two points $q_1,q_2\in \mathcal{C}$, the distance between them on $\mathcal{C}$ is given by the arc length $d_c(q_1,q_2)={\cos }^{-1}(\langle q_1,q_2\rangle )$. The geodesic path between them is the shorter arc on a great circle given by

$\alpha :[0,1]\to \mathcal{C},\alpha (\tau )=\frac{1}{\sin \theta }(\sin ((1-\tau )\theta )q_1+\sin (\tau \theta )q_2),$

where $\theta =d_c(q_1,q_2)$.

In representing a unit-length $f\in \mathcal{F}$ by its $q\in \mathcal{C}$ we have removed its translation (since q depends only on the derivatives of f) and its scale. However, the rotation and re-parameterization variabilities are still left in this representation, that is, we can have two curves with exactly the same shape but at different rotations and reparameterizations and thus with nonzero distance between them in $\mathcal{C}$. These transformations are removed using groups actions and equivalence relations, as described next. For any $O\in SO(n)$ and $\gamma \in \mathrm{\Gamma }$, $O(f\circ \gamma )$ has the same shape as f. In the SRVF representation we characterize these transformations as actions of product group $SO(n)\times \mathrm{\Gamma }$ on $\mathcal{C}$ according to

$(SO(n)\times \mathrm{\Gamma })\times {\mathbb{L}}^2\to {\mathbb{L}}^2,(O,\gamma )⁎q=O(q\star \gamma ).$

This leads to the definition of orbits or equivalent classes:

$[q]=\{O(q\star \gamma )|O\in SO(n),\gamma \in \mathrm{\Gamma }\}.$

Each orbit $[q]$ represents a unique shape of curves. The set of all such orbits forms the shape space of curves

$\mathcal{S}=\mathcal{C}/(SO(n)\times \mathrm{\Gamma })=\{[q]|q\in \mathcal{C}\}.$

(Once again, we advise the reader not familiar with these ideas to follow the definitions given in the Appendix.)

The interesting part of this definition is that the process of registration of points across shapes is incorporated in the definition of shape metric. The two computations, registration of curves and comparisons of their shapes, have been unified under the same metric. The optimal deformation from one shape to the other is mathematically realized as a geodesic in the shape space. We can evaluate the geodesic between the shapes $[q_1]$ and $[q_2]$ in $\mathcal{S}$ by constructing the shortest geodesic between the two orbits in $\mathcal{C}$. If $(\hat{O},\hat{\gamma })$ denote the optimal arguments in Eq. (11.8), then this geodesic is given by

$\alpha (\tau )=\frac{1}{\sin \theta }(\sin ((1-\tau )\theta )q_1+\sin (\tau \theta ){\hat{q}}_2),{\hat{q}}_2=\hat{O}(q_2⁎\hat{\gamma }).$

We present some examples of this framework. Fig. 11.7 shows three examples of geodesic paths between given 2D curves. It is clear from these examples that the elastic registration of points across the two curves result in a very natural deformation between them. Similar geometric parts are matched to each other despite different relative sizes across the objects, a clear depiction of stretching and compression needed for optimal matching. Fig. 11.8 shows an example of elastic geodesic between two very simple proteins viewed as curves in ${\mathbb{R}}^3$.

Shape spaces of closed curves  In case we are interested in shapes of closed curves, we need to restrict to the curves satisfying the condition $f(0)=f(1)$. In this case it is often more natural to choose the domain of parameterization to be ${\mathbb{S}}^1$, instead of $[0,1]$. Thus Γ now represents all orientation-preserving diffeomorphisms of ${\mathbb{S}}^1$ to itself. Under the SRVF representation of f, the closure condition is given by ${\int }_{{\mathbb{S}}^1}q(t)|q(t)|dt=0$. The preshape space for unit-length closed curves is

${\mathcal{C}}^c=\{q\in {\mathbb{L}}^2({\mathbb{S}}^1,{\mathbb{R}}^n)|{\int }_{{\mathbb{S}}^1}|q(t)|dt=1,{\int }_{{\mathbb{S}}^1}q(t)|q(t)|dt=0\}\subset \mathcal{C}.$

An orbit or an equivalence class is defined to be: for $q\in {\mathcal{C}}^c$, $[q]=\{O(q\star \gamma )|O\in SO(n),\gamma \in \mathrm{\Gamma }\}$, and the resulting shape space is ${\mathcal{S}}^c={\mathcal{C}}^c/(SO(n)\times \mathrm{\Gamma })=\{[q]|q\in {\mathcal{C}}^c\}$. The computation of geodesic paths in ${\mathcal{C}}^c$ is more complicated as there is no analytical expression similar to Eq. (11.6) is available for ${\mathcal{C}}^c$. In this case we use a numerical approximation, called path straightening [19], for computing geodesics and geodesic distances. Let $d_c(q_1,q_2)$ denote the length of a geodesic path in ${\mathcal{C}}^c$ between any two curves $q_1,q_2\in {\mathcal{C}}^c$. Then the distance between their shapes is given by

$d_s([q_1],[q_2])=\underset{O\in SO(n),\gamma \in \mathrm{\Gamma }}{\inf }{d}_c(q_1,O(q_2\star \gamma )).$

Fig. 11.9 shows some examples of geodesic between curves taken from the MPEG7 shape dataset.

11.4 Statistical summaries and principal modes of shape variability

Using the mathematical platform developed so far, we can define and compute several quantities that are useful in statistical shape analysis. For example, we can use the shape metric to define and compute a mean or a median shape, as a representative of shapes denoting a population. Furthermore, using the tangent structure of the shape space, we can compute principal modes for variability in a given sample of data. Given mean and covariance estimates, we can characterize underlying shape populations using Gaussian-type distributions on shape spaces.

In other words, the mean is defined to be the shape that achieves minimum of the sum of squared distances to the given shapes. There is a well-known gradient-based algorithm for estimating this mean from given data.

In case of real-valued functions, we can simplify the setup and use it to register and align multiple functions. The basic idea is to use a template to register all the given curves using previous pairwise alignment. A good candidate of the template is a mean function defined previously. In the case of unscaled functions the definition of the mean simplifies to

$[\mu ]=\underset{q\in {\mathbb{L}}^2}{\mathrm{argmin}}\sum _{i=1}^n(\underset{{\gamma }_i\in \mathrm{\Gamma }}{\inf }{\Vert q-(q_i\star {\gamma }_i)\Vert }^2).$

If we fix the optimal warpings to be $\{{\gamma }_i\}$s, then the solution for the mean reduces to $\mu =\frac{1}{n}\sum _{i=1}^n(q_i\star {\gamma }_i)$. Using this idea, we can write an iterative algorithm for registration of multiple functions or curves.

Multiple alignment algorithm 

Fig. 11.10 shows an example of registration of multiple functions using this algorithm. The left panel shows a set of simulated functions $\{f_i\}$ that all are bimodal, but their modes differ in the locations and heights. This set forms the input to the algorithm, and the next two panels show the outputs. The middle panel shows the functions $\{{\tilde{f}}_i\}$ associated with the aligned SRVFs $\{{\tilde{q}}_i\}$, and the right panel shows the optimal time warping functions $\{{\gamma }_i\}$. We can see the high quality of registration in matching of peaks and valleys across functions.

Fig. 11.11 shows some more examples of multiple function registration, this time using real data. The two rows of this figure correspond to female (top) and male (bottom) growth curves taken from the famous Berkeley growth dataset. Each curve shows the rate at which the height of an individual changes from the age of one to twelve. Each row shows the original growth rate functions $\{f_i\}$ (left), their registrations $\{{\tilde{f}}_i\}$ (middle), and the optimal warpings $\{{\gamma }_i\}$. The peaks in rate functions, denoting growth spurts, are better matched after registrations and are easier to interpret in the resulting data.

Fig. 11.12 shows some examples of mean shapes computed for a set of given shapes. We can see that the mean shapes are able to preserve main distinguishing features of the shape class while smoothing out the intraclass variabilities.

We can use the shape metric and the flatness of the tangent space to discover principal modes of variability in the given set of shapes. Let $T_{[\mu ]}\mathcal{S}$ denote the tangent space to $\mathcal{S}$ at the mean shape $[\mu ]$, and let ${\exp }_{[\mu ]}^{-1}([q])$ denote the mapping from the shape space $\mathcal{S}$ to this tangent space using the inverse exponential map. We evaluate this mapping by finding the geodesic α from $[\mu ]$ to a shape $[q]$ and then computing the initial velocity of the geodesic, that is, ${\exp }_{[\mu ]}^{-1}([q])=\dot{\alpha }(0)$. We also call these initial velocities the shooting vectors. Let $v_i={\exp }_{[\mu ]}^{-1}([q_i])$, $i=1,2,\dots ,n$, be the shooting vectors from the mean shape to the given shapes. Then performing PCA of $\{v_i\}$ provides the directions of maximum variability in the given shapes and can be used to visualize the main variability in that set. Fig. 11.13 shows three examples of this idea using some leaf shapes. In each panel of the top row we show the set of given leafs and their mean shapes. The bottom row shows the shape variability along the two dominant modes of variability, obtained using PCA in the tangent space. In the bottom plots the two axes represent the two dominant directions, and we can see the variation in shapes as one moves along these coordinates.

11.5 Summary and conclusion

This chapter describes an elastic approach to shape analysis of curves in Euclidean spaces. It focuses on the problem of registration of points across curves and shows that the standard ${\mathbb{L}}^2$ norm, or its penalized version, has inferior mathematical properties and practical performances. Instead, it uses a combination of SRVFs and ${\mathbb{L}}^2$ norm to derive a framework for a unified shape analysis framework. Here we register curves and compare their shape in a single optimization framework. We compute geodesic paths, geodesic distances, and shape summarizes using the geometries of shape spaces. These tools can then be used in statistical modeling and analysis of shapes of curves.

Appendix Mathematical background

We summarize here some background knowledge of algebra and differential geometry with the example of planar shapes represented by k ordered points in ${\mathbb{R}}^2$, denoted by $X\in {\mathbb{R}}^{2\times k}$. Clearly, X and $OX,O\in SO(2)$ have the same shape. That can be defined strictly through the following concepts.

Thus the space of planar shapes in the form of discrete points is the quotient space of ${\mathbb{R}}^{2\times k}/SO(2)$. To measure the difference between two shapes, we need a proper metric. For ${\mathbb{R}}^{2\times k}$, a natural choice is the Euclidean metric, but for a nonlinear manifold, the difference is measured by the length of the shortest path connecting the two shapes, which requires the following definitions.

For $X\in {\mathbb{R}}^{2\times k}$, the fact $\Vert X\Vert =\Vert OX\Vert$, $O\in SO(2)$, induces two important concepts, group action and isometry.

The groups appearing in this chapter are all Lie groups.

For a planar shape denoted by a $2\times k$ matrix X, the shape can be identified by an orbit $[X]=\{OX|O\in SO(2)\}$.

We illustrate this idea by an example. Let ${\mathbb{R}}^{2\times k}$ be the space of planar shapes of k points with Euclidean metric. Consider the action of rotation group $SO(2)$ on ${\mathbb{R}}^{2\times k}$. The metric on the quotient space ${\mathbb{R}}^{2\times k}/SO(2)$ is

$d_{{\mathbb{R}}^{2\times k}/SO(2)}([X_1],[X_2])=\underset{O\in SO(2)}{\min }\Vert X_1-O{X}_2\Vert .$

The geodesic between two shapes $[X_1]$ and $[X_2]$ is $\alpha (\tau )=(1-\tau )X_1+\tau O^{⁎}{X}_2$, where $O^{⁎}=\underset{O\in SO(2)}{\arg \min }\Vert X_1-O{X}_2\Vert$, $\tau \in [0,1]$. If the two shapes are rescaled to be unit length, that is, $\Vert X_1\Vert =\Vert X_2\Vert =1$, then the geodesic is the arc on a great circle of the unit sphere $\alpha (\tau )=\frac{1}{\sin (\theta )}[\sin ((1-\tau )\theta )X_1+\sin (\tau \theta )O^{⁎}{X}_2]$, where $\theta =\mathrm{arc}\cos (\langle X_1,O^{⁎}{X}_2\rangle )$, $O^{⁎}=\underset{O\in SO(2)}{\arg \min }\mathrm{arc}\cos (\langle X_1,O{X}_2\rangle )$.