Shape analysis is a much wider topic than just landmark analysis. We have concentrated most of our work on point set configurations, but the extension to more general objects is widespread.
Some simple measures for describing the shapes of sets include shape factors and other moment-based measures. These shape factors are dimensionless and are often used in microscopy (Exner and Hougardy 1988) and image analysis (Glasbey and Horgan 1995). Commonly used measures include the area–perimeter ratio
which has maximum value 1 for a circle and minimum value 0, with A the area and P the perimeter. The elongation shape factor is:
where B is the breadth of the object measured orthogonally to the maximum length L between the two most extreme points. See Stoyan and Stoyan (1994, Chapter 8) for further examples of simple shape measures.
Stoyan and Molchanov (1995) have developed theory for the shapes of set-valued data, and include methodology for the calculation of set-valued means. Distance measures between sets, such as the Hausdorff distance, can be used to develop estimated mean sets in a manner analogous to Fréchet means for shapes discussed in Chapter 6. The distance between a point x and a set C is:
and the Hausdorff distance between two sets A and B is:
Stoyan and Molchanov (1995) develop algorithms for estimating mean sets (Aumann and Vorob’ev means) from a random sample of random sets, where invariances such as rotation and translation are taken into account. They provide an algorithm in the spirit of GPA. Applications to random sets of particles are considered in Stoyan and Molchanov (1995), and a further application of interest is that of describing the shape variability of sand particles in Stoyan and Stoyan (1994) and Stoyan (1997), as described in Section 1.4.10. Charpiat et al. (2005) use the Hausdorff metric for averaging set objects in computer vision. Also motivated by image analysis applications, Dubuisson and Jain (1994) develop various modifications of Hausdorff distances. Note only the Hausdorff distance in the variants considered by Dubuisson and Jain (1994) is actually a metric.
Several approaches have been suggested for use on objects that do not have landmarks. The shape of outlines in a plane can be considered using Fourier series representations (Zahn and Roskies 1972). A Fourier series decomposition of a polar representation or a tangent angle representation of the x–y coordinates around the outline leads to a new set of variables (the Fourier coefficients). In particular, for a 2D outline a polar representation of the radius r(θ) as a function of angle θ with the horizontal axis is given by:
where aj, bj are the Fourier coefficients. If the object has been translated and rotated into a standard reference frame, and normalized to unit size in some way, then the Fourier coefficients represent the shape of the object. The Fourier coefficients can be estimated for each outline using least squares techniques, and an important consideration is to choose p. Standard multivariate analysis on the Fourier coefficients provides a suitable way of analysing such data. There are numerous applications of this technique in the literature including in engineering and biology – for some examples see Zahn and Roskies (1972); Rohlf and Archie (1984); Johnson et al. (1985); Rohlf (1990); Stoyan and Stoyan (1994); Renaud (1995); and Lestrel (1997). This Fourier approach is most often used when there is some approximate underlying correspondence between parts of the outlines. The technique can be extended to three dimensions using spherical harmonics (Chung et al. 2007; Dette and Wiens 2009). If the outlines have discontinuities or sharp edges then a wavelet representation is more appropriate. Other techniques include that of Parui and Majumder (1983) who consider shape similarity measures for open curves. Note that open curves (with distinct start and end points) are a little simpler to describe than closed curves (where the start point is an unknown parameter that needs to be factored out).
In modelling the outline of an object, Grenander and co-workers (Grenander 1994; Grenander and Miller 2007) specify a series of points around the outline connected by straight line segments. In their method, variability in the template is introduced by pre-multiplying the line segment by random scale-rotation matrices. Let us assume that the outline is described by the parameters θT = {θT1, θ2T}, where θ1 denotes a vector of similarity parameters (i.e. location, size and rotation) whereas θ2 denotes say k landmarks of the outlines. For θ1, we can construct a prior with centre of gravity parameters, a scale parameter and a rotation by an angle α. Conditional on θ1, we can construct a prior distribution of θ2 as follows. Let ηj and ej be the template edge and object edge, respectively, in complex coordinates, j = 1, …, k, where the edges are formed from the vertices (landmark points) by taking differences ej = vj − vj − 1, with v0 = vk and the edges satisfy the constraint ∑kj = 1ej = 0. A simple model is the Gaussian Markov Random Field (MRF) of order 1
where {tj} are random Gaussian rotations and
The process {θ2} is an improper Gaussian MRF of second order. The prior on {θ2} is invariant under location but not scale or rotation. Kent et al. (1996b) and Mardia (1996a) give full details and also provide a link with the snake (see Section 17.3.5).
Grenander and Manbeck (1993) use edge models in an application involving automatic testing of defective potatoes. Using real notation consider a template with edges g01, …, gk0 with ∑kj = 1gj0 = 0. Define the random edges gj by
where r is global size, ψ is global rotation and ψj are individual rotations. We can take the distribution of r to be log normal, ψ to be uniform on (0, 2π), the joint distribution of ψ1, …, ψk, to be multivariate von Mises such as (Mardia 1975):
where 0 < ψj < 2π, j = 1, …, k; ψk + 1 = ψ1, and β1, β2 > 0. Thus β1 and β2 are deformation parameters, β1 allows similar neighbouring rotations whereas β2 maintains fidelity to the template. Since ∑gj = 0, there are constraints on {ψj}. Let us take r = 1 and ψ = 0. The constraints ∑gj = 0 and ∑g0j = 0 imply the following constraints on ψ1, …, ψk:
where ∑g0jx = ∑g0jy = 0. These can be simplified further for small values of {ψj} leading to linear constraints on ψj. The field of view encloses a single position and therefore location parameters do not matter. Grenander and Manbeck (1993) also use information from a colour model in the defective potato testing application.
Consider star-shaped objects in which can be represented by a radial function R(u), where R(u) > 0 and u ∈ Sd − 1 are suitable spherical coordinates. An example of a star-shaped object suitable for such analysis is the leaf outline of Figure 16.1, which was modelled by Mardia and Qian (1995).
In general the radial function R(u) contains size, shape, location and rotation information of the surface. However, location and rotation information is not present if the object can be regarded as being in a fixed location and orientation, for example from preliminary registration. In some applications, it is of interest to restrict u to part of the sphere . The size of object the could be taken as the geometric mean
and, assuming the registration is fixed, the shape of surface is taken as X(u) = R(u)/S. A possible model for log R(u) is a Gaussian process with mean log μ(u) and covariance function .
An alternative procedure is to take the size as with shape XA(u) = R(u)/A. A suitable model here could be a Gaussian process for R(u) (Mancham and Molchanov 1996). The two procedures will be similar for small variations about the mean μ(u).
In practice a discrete set of points will be available, and we assume that the points are identified on the surface for k values of (e.g. on regularly spaced rays from the origin). Assuming an initial registration has been determined, the collection of radii R = (R1, …, Rk)T measures the size and shape of the surface. Let X* = (log R1, …, log Rk)T be the vector of log-radii. The size of the surface is measured by:
and the shape of the surface is measured by the vector
A possible model for log-shape is a (singular) multivariate normal distribution, and PCA can be used to reduce the dimensionality for inference.
Example 16.1 Dryden (2005b) and Brignell et al. (2010) consider the brain surface data of Section 1.4.15. Estimates of the mean surface shape were obtained using (16.3), and shape variability was investigated using PCA. In addition surface symmetry measures were calculated, and the schizophrenia patients were found to be more symmetrical than the controls – an effect known as brain torque. □
In some situations there is no sensible correspondence between outlines, for example in the sand particles of Section 1.4.10. Miller et al. (1994) develop an approach where the complex edge transformations {ti} are assumed to have a circulant Toeplitz covariance matrix in constructing a complex multivariate normal model. The model has been applied successfully to images of mitochondria (Grenander and Miller 1994). This model with circulant symmetry has also been studied by Kent et al. (2000), who consider additional constraints to make {θ2} invariant under the similarity transformations. Kent et al. (2000) also explore the eigenstructure of the circulant covariance matrix. Kent et al. (2000) and Hobolth et al. (2002) apply their circulant models to the sand particles of Section 1.4.10, where the mean is a circle and the variability about the mean is of particular interest. In this application the shape variability of the river particles is significantly higher than the sea particles. The circulant models build on those developed by Grenander and Miller (1994), and Hobolth et al. (2002) make an explicit connection between edge-based and vertex-based models, with a focus on Markov random field models around the outline. Studies where the objects under study are featureless (i.e. no obvious correspondence in parts of the outline) are common, for example Grenander and Manbeck (1993); Grenander and Miller (1994); Mardia et al. (1996f); Stoyan (1997); Rue and Syversveen (1998); Hobolth and Vedel Jensen (2000); Kent et al. (2000); Hobolth et al. (2003) and Gardner et al. (2005) study potatoes, mitochondria, sand grains and ceramic particles, mushrooms, cells, cell nuclei, and tumour classification. Several of the models have continuous representations using stochastic processes, and these models are not dependent on the particular discretization of the curves. Parameter estimation is often carried out using likelihood-based methods (e.g., Kent et al. 2000; Hurn et al. 2001; Hobolth et al. 2002).
Bookstein (1996a,c) has introduced the shape analysis of outlines based on semi-landmarks, which are allowed to slip around an outline. This approach is appropriate when there is some approximate notion of correspondence, which can be indicated by pseudo-landmarks that are allowed to slide along the outline.
First of all some landmarks are chosen and these are free to slide along the tangent direction of a curve. Let Xi = (Xix, Xiy)T be the ‘source’ or old landmarks and let Yi = (Yix, Yiy)T be the ‘target’ or new landmarks (i = 1, …, k). Let us write Y = (Yx, Yy)T where Yx = (Y1x, …, Ykx)T and Yy = (Y1y, …, Yky)T. Now suppose that Yj, j = 1, …, q < k, are free to slide away from their old position Xj, j = 1, …, q, along the directions uj = (ujx, ujy)T with ||uj|| = 1. Thus the new position of Yj is:
Note that Yq + 1, …, Yk are fixed in advance. We know that the bending energy is given by:
where Be depends only on the old configuration Xi, i = 1, …, k. Now we can write:
where
and
is a 2k × q matrix and t = (t1, …, tq)T. We need to minimize the bending energy
with respect to t. The problem is similar to generalized least squares linear regression, with solution
Bookstein (1996a,c) advocates an iterative procedure where the initial value of uj = (Xj + 1 − Xj − 1)/||Xj + 1 − Xj − 1|| (or an alternative procedure which iterates through uj = (uj + 1 − uj − 1)/||uj + 1 − uj − 1||). So, one obtains U then calculates t, then iterates. Once the semi-landmarks have been obtained we can consider Procrustes and other shape analysis techniques, to obtain a suitable shape prior distribution for object recognition. Alternatively, one may be interested in shape analysis of the outlines, and for example differences in average shape between groups. Bookstein (1996c) has investigated the shape of the corpus callosum in the midsagittal sections of MR scans of the brain in control subjects and schizophrenia patients, as in Figure 1.14. An important practical aspect of the work is how to sample the points: one needs to achieve a balance between coarse sampling of landmarks where information might be lost and over-fine sampling of landmarks where power can be lost. For an alternative but related approach, see Green (1996).
Srivastava et al. (2011a) have introduced a very promising method for the size-and-shape analysis of elastic curves, building on earlier work that started with Klassen et al. (2003). The method involves the analysis of curve outlines or functions and is invariant under re-parameterization of the curve.
Let f be a real valued differentiable curve function in the original space, . From Srivastava et al. (2011a) the square root velocity function (SRVF) or normalized tangent vector of f is defined as , where
and ||f(t)|| denotes the standard Euclidean norm. After taking the derivative, the q function is now invariant under translation of the original function. In the 1D functional case the domain t ∈ [0, 1] often represents ‘time’ rescaled to unit length, whereas in two and higher dimensional cases t represents the proportion of arc length along the curve.
Let f be warped by a re-parameterization γ ∈ G, that is f○γ, where γ ∈ G : [0, 1] → [0, 1] is a strictly increasing differentiable warping function. Note that γ is a diffeomorphism. The SRVF of f○γ is then given as:
using the chain rule. We would like to consider a metric that is invariant under re-parameterization transformation G. If we define the group G to be domain re-parameterization and we consider an equivalence class for q functions under G, which is denoted as [q], then we have the equivalence class [q] ∈ Q, where Q is a quotient space after removing arbitrary domain warping. Inference can be carried out directly in the quotient space Q.
An elastic distance (Srivastava et al. 2011a) defined in Q is given as:
where ||q||2 = {∫10q(t)2dt}1/2 denotes the L2 norm of q.
There are several reasons for using the q representation instead of directly working with the original curve function f. One of the key reasons is that we would like to consider a metric that is invariant under re-parameterization transformation G. The elastic metric of Srivastava et al. (2011a) satisfies this desired property,
although it is quite complicated to work with directly on the functions f1 and f2. However, the use of the SRVF representation simplifies the calculation of the elastic metric to an easy-to-use L2 metric between the SRVFs, which is attractive both theoretically and computationally. In practice q is discretized using p points.
If q1 can be expressed as some warped version of q2, that is they are in the same equivalence class, then d([q1], [q2]) = 0 in quotient space. This elastic distance is a proper distance satisfying symmetry, non-negativity and the triangle inequality. Note that we sometimes wish to remove scale from the function or curve, and hence we can standardize so that
and then the SRVF measures shape difference.
In the m ≥ 2 dimensional case it is common to also require invariance under rotation of the original curve. Hence we may also wish to consider an elastic distance (Joshi et al. 2007; Srivastava et al. 2011a) defined in Q given as:
The m = 2 dimensional elastic metric for curves was first given by Younes (1998).
Inference can be carried out directly in the quotient space Q, and in this case the population mean is most naturally the Fréchet/Karcher mean μQ. Given a random sample [q1], …, [qn] we obtain the sample Fréchet mean by optimizing over the warps for the 1D function case (Srivastava et al. 2011b):
In addition for the m ≥ 2 dimensional case (Srivastava et al. 2011a) we also need to optimize over the rotation matrices Γi where
This approach can be carried out using dynamic programming for pairwise matching, then ordinary Procrustes matching for the rotation, and the sample mean is given by:
Each of the parameters is then updated in an iterative algorithm until convergence.
Cheng et al. (2016) introduce a Bayesian approach for analysing SRVFs, where the prior re-parameterization for γ is a Dirichlet distribution. This prior distribution is uniform when the parameters in the Dirichlet are all a = 1, and a larger value of a leads to a transformation more concentrated on (i.e. translations). In the m ≥ 2 dimensional case, we consider a Gaussian process for the difference of two vectorized q functions in a relative orientation Γ, that is {vec(q1 − q*2)|γ, Γ} ∼ GP, where . The matrix Γ ∈ SO(m) is a rotation matrix with parameter vector θ. If we assign a prior for rotation parameters (Eulerian angles) θ corresponding to rotation matrix Γ, then the joint posterior distribution of (γ([t]), θ), given (q1([t]), q2([t])) is:
where γ, θ, κ are independent a priori. Cheng et al. (2016) carried out inference by simulating from the posterior using MCMC methods. For large samples estimation is consistent, which can be shown using the Bernstein–von Mises theorem (van der Vaart 1998, p. 141). Cheng et al. (2016) provide a joint model for the SVRF and the warping function, and hence it is in the ambient space.
Example 16.2 Consider a pairwise comparison of two mouse vertebrae from the dataset in Section 1.4.1, where there are 60 landmarks/pseudo-landmarks on each outline. We use Cheng et al. (2016)’s MCMC algorithm for pairwise matching with 50 000 iterations. The q-functions are obtained by initial smoothing, and then normalized so that ||q||2 = 1. The registration is carried out using rotation through an angle θ about the origin, and a warping function γ. The original and registered pair (using a posterior mean) are shown in Figure 16.2 and the point-wise correspondence between the curves and a point-wise 95% credibility interval for γ(t) are shown in Figure 16.3. The start point of the curve is fixed and is given by the left-most point on the curve in Figure 16.3 that has lines connecting the two bones. The narrower regions in the credibility interval correspond well with high curvature regions in the shapes. We also applied the multiple curve registration, as shown in Figure 16.4. □
There are many applications where the SRVF methods can be used, for example Srivastava et al. (2012) develop techniques for 2D and 3D shape analyses in gait-based biometrics, action recognition, and video summarization and indexing. The shape of curves that are invariant to re-parameterization has been the subject of deep mathematical work on different types of quotient spaces, with connections to elastic metrics (Michor and Mumford 2006, 2007; Younes et al. 2008a).
The choice as to whether to use quotient space inference or ambient space inference was discussed by Cheng et al. (2016), and in practice the two methods are often similar due to a Laplace approximation to the posterior density. This situation is similar to that of Chapter 14 in the analysis of unlabelled shape, where the choice between optimization (quotient space model) or marginalization (ambient space model) needs to be considered (see Section 14.2.2).
Mardia et al. (1999) have approached the problem of analysing curves in three dimensions through the Frenet–Serret framework, in particular to estimate curvature and torsion. Recall from differential geometry that curvature measures the rate of change of the angle of tangents and it is zero for straight lines. Torsion measures the twisting of a curve, and it is zero for the curves lying in two dimensions. For a helix, curvature and torsion are constant. Curvature and torsion are invariant under a rigid transformation and thus useful for studying the size-and-shape of curves. Given a curve {x(t), y(t), z(t)} the torsion function is given by τ(t) = τ1(t)/τ2(t), where
and the curvature function is . Note that the amount of smoothing required to estimate torsion can be large given that third derivatives need to be estimated, which in turn may bias the estimation. Recently, by using splines, Kim et al. (2013) have provided consistent estimators of curves in three dimensions which in particular lead to consistent estimators of curvature and torsion. One of the applications is to infer if torsion is zero or not, for example, in spinal deformity (Mardia et al. 1999). Cheng et al. (2014) use curvature and torsion to study the size-and-shapes of carotid arteries. Another application related to change in curvature, for example, is finding a kink in helices related to drug discovery (Deane et al. 2013).
Comparing surfaces is more complicated than comparing curves, as the natural ordering around an outline is not present for a surface. Extensions of the SRVF method to surfaces have been presented by Kurtek et al. (2010) and Jermyn et al. (2012). In particular, the SRVF is replaced by a square root normal field by Jermyn et al. (2012) and then distances between the shapes of surfaces need to be invariant to parameterization (common diffeomorphic transformations) of the surfaces. The methodology is applied to a wide variety of examples, including the comparisons of organs from medical images and 3D surface images from computer vision.
The ‘landmark-free’ matching procedure called the iterative closest point (ICP) algorithm uses a procedure where a set of points is located on one object and the corresponding closest points on the second object are used to update the registration (Besl and McKay 1992). A new set of closest corresponding points is then chosen and the registration is updated again, and so on.
In image analysis a method of representing shapes is via distance functions between points on the surface, which are isometrically embedded into Euclidean space. Biasotti et al. (2014) provide a review of 3D shape similarity using maps; Rosman et al. (2010) consider nonlinear dimension reduction by using a topologically constrained isometric embedding; Bronstein et al. (2010) consider metrics within a shape object for shape matching, and the methods are invariant under inelastic matching. Elad and Kimmel (2003) also use Euclidean embedding, and shape is regarded as a metric space. Further matching procedures have been proposed by minimizing pixel-based measures (e.g. Glasbey and Mardia 2001).
Other methods for surface shape comparison include using conformal Wasserstein distances (Lipman and Daubechies 2010; Lipman et al. 2013) with an emphasis on practical computation. Finally, in order to deal with continuous (infinite dimensional) surface shapes it can be useful to employ kernel methods in Hilbert spaces (Czogiel et al. 2011; Jayasumana et al. 2013b; 2015, Awate et al. 2014).
It is often of great interest to study curvature and boundary information, especially when landmarks are not available, but also in addition to landmarks. Curvature-based methods can be used for describing shape or for comparing object shapes for two dimensions or three dimensions. Other related topics of interest include the use of ridge curves (Kent et al. 1996a) and crest lines (Subsol et al. 1996) which could be used for object matching. Methods for describing solid shape, that is shapes of whole object volumes, have been summarized by Koenderink (). Also, Koenderink and van Doorn (1992) consider surface shape and curvature at different scales. A typical 3D application is the following from a study of human faces before and after operations.
Example 16.3 Range images are obtained of human faces before and after plastic surgery and the data are acquired using a laser scanner and charge-coupled device (CCD) camera (Coombes et al. 1991). A laser beam is fanned into a line and directed at a person sitting in a chair. Two mirrors reflect the image of the resulting profile into a CCD camera. The scan lines are recorded for the profiles and the chair is rotated under computer control. The result is that approximately 24 000 (3D) coordinates are obtained on the surface of the face, see Figure 16.5.
Consider a patient who has a cleft palate and therefore requires surgery to improve comfort and appearance. It is of interest to describe the differences in the shape of the face before and after surgery, for the benefit of the patient and surgical planning.
Mardia et al. (1995) provide maps on a patient scan, coloured according to different surface types, which are evaluated by curvature (e.g. saddle point, pit, valley, etc.). These maps are helpful for describing surface shape and can highlight abnormalities or differences in shape.
Note that in all examples of this chapter there is a large step from the object in the real world and the data that are obtained for analysis. How the data are acquired will feed in strongly to the type of statistical analysis carried out. Koenderink (1990) discusses apertures for instruments that lie between a natural phenomenon and the measured data. It is important that apertures, e.g. image pixels or sampling points, should not become a feature of the analysis. This is highly relevant for the study of discrete differential properties of curves, surfaces and volumes.
3.139.104.23