BIOEN6500:
Project 3
Name:
James Fishbaugh
Email:
jfishbau@cs.utah.edu
Exploration of Procrustes Analysis,
Frechet Mean, PCA and PGA
Frechet Mean, PCA and PGA
Introduction
Shape analysis is an increasingly powerful tool in many research areas in computational science.
The major goal of any shape analysis technique is to accurately capture only the geometric differences between
shapes. That is, those differences that are present when translation, scale, and rotation are factored out. In this
document, we explore traditional Procrustes analysis as well as principle geodesic analysis, a non-linear method which is a generalization of PCA
to manifold spaces.
Linear Shape Analysis
We model shape by a dense set of landmark points on the contour of an object. The x and y coordinates of the points are
concatenated into a vector. For example, we can represent a square by placing landmarks at the four corners, which results
in an eight dimensional vector. We represent a family of similar shapes by establishing corresponding landmarks for each
shape. In our square example, we might enforce the ordering of the landmarks starting at the top left corner and
continuing clockwise. In this way, we can compare shapes in a meaningful way.
Each shape is then represented as a vector, where the ith shape is written as
Each shape is then represented as a vector, where the ith shape is written as
where the shape is defined by n landmark points.
.
.
.
.
.
The log map is a function that computes a geodesic from two points on the manifold. The geodesic represents the shortest path on the manifold between two points. A geodesic is the generalization of a line to curved spaces. The log map returns a vector in the tangent space of the base point in the direction of the other point on the manifold. The magnitude of the vector represents the time it takes to traverse the geodesic. The log map, given points x and y on the manifold, for
is defined as
, 
,
.
, 
.
Average Shape
In order to perform meaningful statistical analysis, we require the concept of an average shape. If we consider our shapes
as points in 2n Euclidean space, we can compute the average shape as arithmetic mean, defined as
where N is the total number of shapes.
Principle Component Analysis
If we consider a set of shapes from the same class, but with slight variation,
we would expect high correlation in the distribution of landmark points.
In order to analyze the differences between the shapes in our set, we can investigate the modes of variation. We
begin by constructing a covariance matrix from the data, defined as
where every element in S represents the variation from the mean of a given landmark coordinate.
We obtain the modes of variation by performing a principle component analysis (PCA) on the data covariance matrix. The eigenvectors represent basis vectors in the new space, while the eigenvalues are a measurement of the amount of variance in that dimension. Typically, the majority of the variance is well captured by only a few dimensions of the transformed space. We can account for the majority of the variance by keeping only the eigenvectors corresponding to the largest eigenvalues. A good heuristic is to compute the cumulative sum of the eigenvalues, and only keep the eigenvectors for eigenvalues that account for 90% of variability.
Let us define a matrix
We obtain the modes of variation by performing a principle component analysis (PCA) on the data covariance matrix. The eigenvectors represent basis vectors in the new space, while the eigenvalues are a measurement of the amount of variance in that dimension. Typically, the majority of the variance is well captured by only a few dimensions of the transformed space. We can account for the majority of the variance by keeping only the eigenvectors corresponding to the largest eigenvalues. A good heuristic is to compute the cumulative sum of the eigenvalues, and only keep the eigenvectors for eigenvalues that account for 90% of variability.
Let us define a matrix
of the first k eigenvectors ordered by their corresponding eigenvalues from greatest to least. We can then construct
a statistically meaningful shape by deviating from the average shape, given by
where b is a vector of weights where bi represents the relative influence of the ith
mode of variation.
We can use this framework to explore the modes of variation by computing
We can use this framework to explore the modes of variation by computing
where 
represents the ith eigenvalue and we vary s from -3 to 3. In doing so,
we construct a range of shapes described by the ith mode of variation.
represents the ith eigenvalue and we vary s from -3 to 3. In doing so,
we construct a range of shapes described by the ith mode of variation.
Procrustes Alignment
In shape analysis, we wish to obtain meaningful information about shape differences that are invariant to translation, rotation,
and scale. We see immediately that our framework is not invariant under such rigid transformations. For example, the arithmetic
mean is sensitive to translation, rotation, and scale. Furthermore, the modes of variation computed by PCA will include
translation, rotation, and scale.
In order to limit the contribution of rigid transformations, we perform an alignment of the shapes as a preprocessing step. We wish to minimize the sum-of-squared distance between data points with respect to translation, rotation, and scale.
Translation
Translation invariance can be achieved by setting the center of mass of all shapes to zero by
In order to limit the contribution of rigid transformations, we perform an alignment of the shapes as a preprocessing step. We wish to minimize the sum-of-squared distance between data points with respect to translation, rotation, and scale.
Translation
Translation invariance can be achieved by setting the center of mass of all shapes to zero by
.
Scale
To compute the optimal scale difference between a reference shape xR and another shape xi, we seek a scaling s that minimizes
To compute the optimal scale difference between a reference shape xR and another shape xi, we seek a scaling s that minimizes
.
Taking the derivative with respect to s, setting it equal to zero, and solving for s provides the update
rule for shape xi
.
Rotation
We approach rotational invariance in the same manner as we did with scale. We seek to find an angle θ which rotates a shape xi around the origin to minimize the squared distance between a reference shape xR. Consider a 2-dimensional rotation matrix
We approach rotational invariance in the same manner as we did with scale. We seek to find an angle θ which rotates a shape xi around the origin to minimize the squared distance between a reference shape xR. Consider a 2-dimensional rotation matrix
.
To compute the solution, we observe that the optimal rotation occurs when there is maximum correlation between sets
of landmark points. First, we arrange shapes xR and xi so that the
x and y coordinates are columns of an n x 2 matrix. We then compute a correlation matrix by
xRTxi. A singular value decomposition provides a decomposition
into UΣVT. Therefore, the final update rule for shape xi is
. Non-Linear Shape Analysis
Again we model a shape by a dense set of landmark points on the contour of an object. However, here we represent the shape
as a complex vector
where 
. The shape in this representation is an element of 
.
We represent shapes as points on a manifold, rather than as points in Euclidean space.
. The shape in this representation is an element of .
We represent shapes as points on a manifold, rather than as points in Euclidean space.
We can achieve translation invariance in a similar fashion as with our linear framework, by forcing the centroid of each shape to be zero.
This removes a degree of freedom from the system, resulting in a projection to the subspace .
We observe that shapes are equivalent under scale and rotation if there a scaling 
and rotation angle 
, represented by 
,
such that two shapes are equal. The set of equivalent classes under scale and rotation forms the complex projective space
.
.
We observe that shapes are equivalent under scale and rotation if there a scaling
and rotation angle , represented by ,
such that two shapes are equal. The set of equivalent classes under scale and rotation forms the complex projective space
.
Log Map
The log map is a function that computes a geodesic from two points on the manifold. The geodesic represents the shortest path on the manifold between two points. A geodesic is the generalization of a line to curved spaces. The log map returns a vector in the tangent space of the base point in the direction of the other point on the manifold. The magnitude of the vector represents the time it takes to traverse the geodesic. The log map, given points x and y on the manifold, for
is defined as
, ,
. Exponential Map
The exponential map is a function that computes points on the manifold from a base point and a vector in the tangent space.
The exponential map, given a point on the manifold x and a tangent vector v, for is defined as
is defined as
, . Average Shape
With our log and exponential maps defined, we can define an average shape in this space in a similar fashion to linear
shape analysis. However, here we desire the average shape to minimize the squared geodesic distance to all points on
the manifold. The major difference is the Frechet mean in this space has no closed form solution. However,
it has been shown that a simple gradient descent algorithm computes the mean shape in just a few iterations, choosing the
first shape in the set to be the initial mean.
|
choose an initial guess for
 for k=1 to number of iterations    end |
Algorithm for computing Frechet mean on the manifold.
The algorithm follows intuition. First we compute geodesics from the current mean to all shapes in the set.
Next, we compute an average geodesic, which represents the most common direction. Remember, we can compute this average
because the vector lives in the tangent space of the current mean, which is a Euclidean space. Finally, we update
the mean by walking along the average geodesic. It is not surprising that this process converges very quickly.
Principle Geodesic Analysis
Principle geodesic analysis (PGA) is the natural generalization of PCA to a manifold space. The major difference
between PCA is that the covariance matrix is constructed with the tangent vectors at the Frechet mean. These vectors
are the final values of vi at the end of the Frechet mean computation.
As with PCA, we can explore the major modes of variation by computing
As with PCA, we can explore the major modes of variation by computing
where pi is the ith eigenvector, represents the ith eigenvalue and we vary s from -3 to 3. In doing so,
we construct a range of shapes described by the ith mode of variation.
represents the ith eigenvalue and we vary s from -3 to 3. In doing so,
we construct a range of shapes described by the ith mode of variation.
Experiments
Comparison of Procrustes Mean and Frechet Mean
We begin our experiments by comparing the mean shape determined after Procrustes alignment and the Frechet mean
shape computed on the manifold. Figure 1 shows the Procrustes mean in black, the Frechet mean in red, and
the rigid alignment of the two in blue. We observe that the main difference between the two mean shapes
is described by scale. The Procrustes mean shape was computed by explictly controlling the scale of the training shapes.
The Frechet mean, however, had no such scale adjustments. In fact, we never project the shapes to the complex
projective space, so the scale of the Frechet mean is not informative.
Figure 1: Procrustes mean in black. Frechet mean in red.
Rigid alignment of the two in blue.
By rigidly aligning the two mean shapes, we can obtain a better understanding of the differences between the two.
We observe that the two mean shapes are very similar, once scale and rotation has been removed. Furthermore, the
amount of rotation between the two shapes was small, measured as 0.69 degrees.
It is not surprising that the two mean shapes are similar for the hands dataset as all the shapes in the set are valid hands. The Procrustes alignment does a relatively good job of eliminating translation, scale, and rotation, so we expect the mean shape to be quite meaningful. If there were several outliers amongst the hands, we would expect the Procrustes mean to be less robust than the Frechet mean.
It is not surprising that the two mean shapes are similar for the hands dataset as all the shapes in the set are valid hands. The Procrustes alignment does a relatively good job of eliminating translation, scale, and rotation, so we expect the mean shape to be quite meaningful. If there were several outliers amongst the hands, we would expect the Procrustes mean to be less robust than the Frechet mean.
PCA without Procrustes Alignment
We next investigate PCA for statistical shape analysis without Procrustes alignment. The distribution of shapes is shown
in figure 2, with the mean shape shown in bold red. We observe a significant amount of rotation present in distribution of hands.
The correlation matrix is also shown in figure 2. There is a grid structure in the correlation matrix, which implies there is
a strong correlation between sets of landmarks. Furthermore, there are five such blocks in each row and column, which correspond
to the five fingers on a human hand. The eigenvalue distribution after PCA is shown in figure 2. We observe that 90% of shape
variation is described by the first four modes.
Figure 2: Left) Shape family. Mean shape in red. Middle) Correlation matrix.
Right) Ordered eigenvalues.
Animations of the four major modes of shape variation are shown in figure 3. The first mode is almost entirely rotation, with
perhaps a small amount of scaling. This mode does not reveal any significant information about shape. The second mode is more
informative, as it depicts the fingers spreading in and out. However, there is also rotation present. The third mode of
shape variation is quite similar to the second. The final mode of variation mostly describes the placement of the middle
and little finger. However, we also observe rotation in this mode as well.
Figure 3: Major modes of shape variation. **Mouse over to see animation**.
PCA with Procrustes Alignment
We further experiment with PCA for statistical shape analysis with Procrustes alignment as a preprocessing step.
The distribution of shapes is shown
in figure 4, with the mean shape shown in bold red. We observe a significant decrease in the amount of rotation and scale after
Procrustes alignment. We again observe the grid structure in the correlation matrix, except the blocks representing
fingers are more pronounced. The eigenvalue distribution after PCA is shown in figure 4. We observe that 90% of shape
variation is described by the first three modes.
Figure 4: Left) Shape family. Mean shape in red. Middle) Correlation matrix.
Right) Ordered eigenvalues.
Animations of the three major modes of shape variation are shown in figure 5. The first mode depicts the fingers spreading
in and out. While there is no discernable rotation present, there appears to be some scaling captured in this mode. However,
this first mode of variation is what we would expect as the most prominent difference between the various hands. The second
mode of variation describes the placement of the middle and little finger. This mode appears to show no contribution from scale and
rotation. The final mode of variation appears to be a pinching between the index and thumb. Again, there is no
noticeable effect of scale and rotation in this mode.
Figure 5: Major modes of shape variation. **Mouse over to see animation**.
PGA
We now move from linear to non-linear shape analysis by experimenting with PGA to describe the major modes of
variation present in the hands dataset. The Frechet mean is shown in figure 6. Also shown in figure 6 is
the correlation matrix. We note that the block structure is even more noticeable here than in PCA with Procrustes
alignment, implying a stronger correlation between the fingers of the hand. The eigenvalue distribution after PGA is shown
in figure 6. We observe that 90% of shape variation is described by the first three modes.
Figure 6: Left) Frechet mean. Middle) Correlation matrix.
Right) Ordered eigenvalues.
Animations of the three major modes of shape variation are shown in figure 7. The first mode of variation depicts the fingers
spreading in and out. While it appears that some scaling is taking place, the PGA framework ensures that no scaling can
be introduced. The next section provides more discussion on this interesting observation. The second mode of variation, as
with PCA with Procrustes alignment, shows the position of the middle and little finger. Again, it appears that some scaling of
the fingers and the hand is present, but we do not observe any noticeable rotation. The final mode of variation again appears
to be a pinching of the index finger and thumb. We observe the appearance of a slight amount of scaling present in
the little finger.
Figure 7: Major modes of shape variation. **Mouse over to see animation**.
Comparison of PCA and PGA
We have considered the results from PCA with and without Procrustes alignment and PGA in a qualitative manner. However,
in order to understand the methods, we must quantify the differences. We do this by measuring the amount of scaling and
rotation necessary to rigidly align each new shape constructed with the mean shape. In doing so, we can directly
quantify the amount of scaling and rotation present in analyzing the modes of variation.
Figure 8 shows the amount of scaling and rotation present in the reconstructions of the four modes of variation found using PCA without Procrustes alignment. The columns of the figure represent the mode of variation. We can see that there is a small amount of scaling difference between every shape and the mean shape. Even more telling is the amount of rotation between every shape and the mean shape. The first mode, in particular, shows a large amount of rotation present. The second and third modes also show a significant amount of rotation. We observe that the final mode of shape variation has only a small amount of rotation present.
Figure 8 shows the amount of scaling and rotation present in the reconstructions of the four modes of variation found using PCA without Procrustes alignment. The columns of the figure represent the mode of variation. We can see that there is a small amount of scaling difference between every shape and the mean shape. Even more telling is the amount of rotation between every shape and the mean shape. The first mode, in particular, shows a large amount of rotation present. The second and third modes also show a significant amount of rotation. We observe that the final mode of shape variation has only a small amount of rotation present.
Figure 8: Amount of scale and rotation per mode of variation from PCA
without Procrustes alignment.
Figure 9 shows the amount of scaling and rotation present in the reconstructions of the three modes of variation
found using PCA with Procrustes alignment as a preprocessing step. The columns of the figure represent the mode of variation.
We first observe that nearly no rotation is described by the major modes of variation. It appears that Procrustes alignment
does a good job of eliminating the effect of rotation. We do observe a slight amount of scale differences between
shapes constructed along the various modes of variation. These scale differences, however, are quite small. Again,
we conclude that Procrustes alignment does a reasonable job of ensuring scale invariance.
Figure 9: Amount of scale and rotation per mode of variation from PCA
with Procrustes alignment.
Figure 10 shows the amount of scaling and rotation present in the reconstructions of the three modes of variation
found using PGA. The columns of the figure represent the mode of variation.
As expected, there is no measurable scaling and rotation described in the modes of variation. This is rather anticlimactic,
because the equivalence classes were constructed to guarantee rigid invariance. However, it is interesting in light of the
results in figure 7, where it appears scale differences are captured by the modes of variation. We know that every hand displayed
in figure 7 lives on the manifold. However, it is possible that some strange hands are also points on the manifold. We
propose that the absolute scale invariance leads to some strange hand shapes, as the scale of each contour is forced to be equal.
Figure 10: Amount of scale and rotation per mode of variation from PGA.
Conclusion
We have seen two different methods, PCA and PGA, used for shape analysis. PCA is a linear shape analysis tool
where shapes are modeled as points in a Euclidean space. Conversely, PGA is a non-linear framework, where
shapes are modeled as points on a Riemannian manifold, which appears Euclidean in small neighborhoods.
PCA is straightforward and intuitive, but requires a preprocessing step to rigidly align shapes. We have also seen that alignment does not guarantee that the modes of variation will be invariant to rigid transformation. In fact, it is likely a small amount of scale and rotation will be captured by the modes of variation. This is particularly true if there is are a large number of outlier shapes.
PGA is also rather straightforward and intuitive, as it is a generalization of PCA. However, we have a theoretical guarantee that the modes of variation are invariant to translation, scale, and rotation. We achieve this guarantee by constructing equivalence classes on the complex space of shape vectors. We have seen that the modes of shape variation do not show any measurable effect from translation, scale, and rotation. However, we observe the appearance of scale differences between the shapes constructed along a given mode of variation.
It appears from this work that there is not a major difference between Procrustes analysis and PGA. We should note that we base this conclusion on the hand data alone. As mentioned previously, PGA is likely more robust to outlier shapes. Furthermore, the modes of variation are likely more capable of describing non-linear shape changes. However, for data where all the shapes are quite similar, as is the case with the hands, Procrustes analysis performs well.
PCA is straightforward and intuitive, but requires a preprocessing step to rigidly align shapes. We have also seen that alignment does not guarantee that the modes of variation will be invariant to rigid transformation. In fact, it is likely a small amount of scale and rotation will be captured by the modes of variation. This is particularly true if there is are a large number of outlier shapes.
PGA is also rather straightforward and intuitive, as it is a generalization of PCA. However, we have a theoretical guarantee that the modes of variation are invariant to translation, scale, and rotation. We achieve this guarantee by constructing equivalence classes on the complex space of shape vectors. We have seen that the modes of shape variation do not show any measurable effect from translation, scale, and rotation. However, we observe the appearance of scale differences between the shapes constructed along a given mode of variation.
It appears from this work that there is not a major difference between Procrustes analysis and PGA. We should note that we base this conclusion on the hand data alone. As mentioned previously, PGA is likely more robust to outlier shapes. Furthermore, the modes of variation are likely more capable of describing non-linear shape changes. However, for data where all the shapes are quite similar, as is the case with the hands, Procrustes analysis performs well.
Last Updated: May 4, 2010