Procrustes analysis
Encyclopedia
In statistics
, Procrustes analysis is a form of statistical shape analysis
used to analyse the distribution of a set of shape
s. The name Procrustes
refers to a bandit from Greek mythology who made his victims fit his bed either by stretching their limbs or cutting them off.
To compare the shape of two or more objects, the objects must be first optimally "superimposed". Procrustes superimposition (PS) is performed by optimally translating
, rotating
and uniformly scaling
the objects. In other words, both the placement in space
and the size of the objects are freely adjusted. The aim is to obtain a similar placement and size, by minimizing a measure of shape difference called the Procrustes distance between the objects. Notice that, after PS, the objects will exactly coincide if their shape is identical. This is sometimes called full, as opposed to partial PS, in which scaling is not performed (i.e. the size of the objects is preserved).
In some cases, both full and partial PS may also include reflection
. Reflection allows, for instance, a successful (possibly perfect) superimposition of a right hand to a left hand. Thus, partial PS with reflection enabled preserves size but allows translation, rotation and reflection, while full PS with reflection enabled allows translation, rotation, scaling and reflection.
In mathematics:
Optimal translation and scaling are determined with much simpler operations (see below).
When a shape is compared to another, or a set of shapes is compared to an arbitrarily selected reference shape, Procrustes analysis is sometimes further qualified as classical or ordinary, as opposed to Generalized
Procrustes analysis (GPA), which compares three or more shapes to an optimally determined "mean shape".
s.
The shape of an object can be considered as a member of an equivalence class formed by removing the translational
, rotational
and uniform scaling
components.
of all the object's points (i.e. its centroid
) lies at the origin.
Mathematically: take
points in two dimensions, say
.
The mean of these points is
where
Now translate these points so that their mean is translated to the origin
, giving the point 
.
distance (RMSD) from the points to the translated origin is 1. This RMSD is a statistical measure of the object's scale or size:
The scale becomes 1 when the point coordinates are divided by the object's initial scale:
.
Notice that other methods for defining and removing the scale are sometimes used in the literature.
, 
. One of these objects can be used to provide a reference orientation. Fix the reference object and rotate the other around the origin, until you find an optimum angle of rotation 
such that the sum of the squared distances (SSD) between the corresponding points is minimised (an example of least squares
technique).
A rotation by angle
gives
where (u,v) are the coordinates of a rotated point. Taking the derivative of
with respect to 
and solving for 
when the derivative is zero gives
When the object is three-dimensional, the optimum rotation is represented by a 3-by-3 rotation matrix R, rather than a simple angle, and in this case singular value decomposition
can be used to find the optimum value for R (see the solution for the constrained orthogonal Procrustes problem
, subject to det
(R) = 1).
This measure is often called Procrustes distance. Notice that other more complex definitions of Procrustes distance, and other measures of "shape difference" are sometimes used in the literature.
method to optimally superimpose a set of objects, instead of superimposing them to an arbitrarily selected shape.
Generalized and ordinary Procrustes analysis differ only in their determination of a reference orientation
for the objects, which in the former technique is optimally determined, and in the latter one is arbitrarily selected. Scaling and translation are performed the same way by both techniques. When only two shapes are compared, GPA is equivalent to ordinary Procrustes analysis.
The algorithm outline is the following:
The shape of an object can be considered as a member of an equivalence class formed by taking the set of all sets of k points in n dimensions, that is Rkn and factoring out the set of all translations, rotations and scalings. A particular representation of shape is found by choosing a particular representation of the equivalence class. This will give a manifold
of dimension kn-4. Procrustes is one method of doing this with particular statistical justification.
Bookstein obtains a representation of shape by fixing the position of two points
called the bases line. One point will be fixed at the origin and the other at (1,0)
the remaining points form the Bookstein coordinates.
It is also common to consider shape and scale that is with translational and rotational components removed.
is used in biological data
to identify the variations of anatomical features characterised by landmark data, for example in considering the shape of jaw bones.
One study by David George Kendall
examined the triangles formed by standing stones to deduce if these were often arranged in straight lines. The shape of a triangle can be represented as a point on the sphere, and the distribution of all shapes can be thought of a distribution over the sphere.
The sample distribution from the standing stones was compared with the theoretical distribution to show that the occurrence of straight lines was no more than average.
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, Procrustes analysis is a form of statistical shape analysis
Statistical shape analysis
Statistical shape analysis is a geometrical analysis from a set of shapes in which statistics are measured to describe geometrical properties from similar shapes or different groups, for instance, the difference between male and female Gorilla skull shapes, normal and pathological bone shapes, etc...
used to analyse the distribution of a set of shape
Shape
The shape of an object located in some space is a geometrical description of the part of that space occupied by the object, as determined by its external boundary – abstracting from location and orientation in space, size, and other properties such as colour, content, and material...
s. The name Procrustes
Procrustes
In Greek mythology Procrustes or "the stretcher [who hammers out the metal]", also known as Prokoptas or Damastes "subduer", was a rogue smith and bandit from Attica who physically attacked people by stretching them or cutting off their legs, so as to force them to fit the size of an iron bed...
refers to a bandit from Greek mythology who made his victims fit his bed either by stretching their limbs or cutting them off.
To compare the shape of two or more objects, the objects must be first optimally "superimposed". Procrustes superimposition (PS) is performed by optimally translating
Translation (geometry)
In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
, rotating
Rotation (mathematics)
In geometry and linear algebra, a rotation is a transformation in a plane or in space that describes the motion of a rigid body around a fixed point. A rotation is different from a translation, which has no fixed points, and from a reflection, which "flips" the bodies it is transforming...
and uniformly scaling
Scaling (geometry)
In Euclidean geometry, uniform scaling is a linear transformation that enlarges or shrinks objects by a scale factor that is the same in all directions. The result of uniform scaling is similar to the original...
the objects. In other words, both the placement in space
Orientation (geometry)
In geometry the orientation, angular position, or attitude of an object such as a line, plane or rigid body is part of the description of how it is placed in the space it is in....
and the size of the objects are freely adjusted. The aim is to obtain a similar placement and size, by minimizing a measure of shape difference called the Procrustes distance between the objects. Notice that, after PS, the objects will exactly coincide if their shape is identical. This is sometimes called full, as opposed to partial PS, in which scaling is not performed (i.e. the size of the objects is preserved).
In some cases, both full and partial PS may also include reflection
Reflection (mathematics)
In mathematics, a reflection is a mapping from a Euclidean space to itself that is an isometry with a hyperplane as set of fixed points; this set is called the axis or plane of reflection. The image of a figure by a reflection is its mirror image in the axis or plane of reflection...
. Reflection allows, for instance, a successful (possibly perfect) superimposition of a right hand to a left hand. Thus, partial PS with reflection enabled preserves size but allows translation, rotation and reflection, while full PS with reflection enabled allows translation, rotation, scaling and reflection.
In mathematics:
- an orthogonal Procrustes problemOrthogonal Procrustes problemThe orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B...
is a method which can be used to find out the optimal rotation and/or reflection (i.e., the optimal orthogonal linear transformation) for the PS of an object with respect to another. - a constrained orthogonal Procrustes problemOrthogonal Procrustes problemThe orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B...
, subject to detDeterminantIn linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
(R) = 1 (where R is a rotation matrix), is a method which can be used to determine the optimal rotation for the PS of an object with respect to another (reflection is not allowed). In some contexts, this method is called the Kabsch algorithmKabsch algorithmThe Kabsch algorithm, named after Wolfgang Kabsch, is a method for calculating the optimal rotation matrix that minimizes the RMSD between two paired sets of points...
.
Optimal translation and scaling are determined with much simpler operations (see below).
When a shape is compared to another, or a set of shapes is compared to an arbitrarily selected reference shape, Procrustes analysis is sometimes further qualified as classical or ordinary, as opposed to Generalized
Generalized Procrustes analysis
Generalized Procrustes analysis is a method of statistical analysis that can be used to compare the shapes of objects, or the results of surveys, interviews, panels. It was developed for analyising the results of free-choice profiling, a survey technique which allows respondents to describe a...
Procrustes analysis (GPA), which compares three or more shapes to an optimally determined "mean shape".
Ordinary Procrustes analysis
Here we just consider objects made up from a finite number k of points in n dimensions. Often, these points are selected on the continuous surface of complex objects, such as a human bone, and in this case they are called landmark pointLandmark point
In morphometrics, landmark point or shortly landmark is a point in a shape object in which correspondences between and within the populations of the object are preserved. In other disciplines, landmarks may be known as vertices, anchor points, control points, sites, profile points, 'sampling'...
s.
The shape of an object can be considered as a member of an equivalence class formed by removing the translational
Translation (geometry)
In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
, rotational
Rotation (mathematics)
In geometry and linear algebra, a rotation is a transformation in a plane or in space that describes the motion of a rigid body around a fixed point. A rotation is different from a translation, which has no fixed points, and from a reflection, which "flips" the bodies it is transforming...
and uniform scaling
Scaling (geometry)
In Euclidean geometry, uniform scaling is a linear transformation that enlarges or shrinks objects by a scale factor that is the same in all directions. The result of uniform scaling is similar to the original...
components.
Translation
For example, translational components can be removed from an object by translating the object so that the meanMean
In statistics, mean has two related meanings:* the arithmetic mean .* the expected value of a random variable, which is also called the population mean....
of all the object's points (i.e. its centroid
Centroid
In geometry, the centroid, geometric center, or barycenter of a plane figure or two-dimensional shape X is the intersection of all straight lines that divide X into two parts of equal moment about the line. Informally, it is the "average" of all points of X...
) lies at the origin.
Mathematically: take
points in two dimensions, say.The mean of these points is
whereNow translate these points so that their mean is translated to the origin
, giving the point .Uniform scaling
Likewise, the scale component can be removed by scaling the object so that the root mean squareRoot mean square
In mathematics, the root mean square , also known as the quadratic mean, is a statistical measure of the magnitude of a varying quantity. It is especially useful when variates are positive and negative, e.g., sinusoids...
distance (RMSD) from the points to the translated origin is 1. This RMSD is a statistical measure of the object's scale or size:
The scale becomes 1 when the point coordinates are divided by the object's initial scale:
.Notice that other methods for defining and removing the scale are sometimes used in the literature.
Rotation
Removing the rotational component is more complex, as a standard reference orientation is not always available. Consider two objects composed of the same number of points with scale and translation removed. Let the points of these be, . One of these objects can be used to provide a reference orientation. Fix the reference object and rotate the other around the origin, until you find an optimum angle of rotation such that the sum of the squared distances (SSD) between the corresponding points is minimised (an example of least squaresLeast squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
technique).
A rotation by angle
gives-
.
where (u,v) are the coordinates of a rotated point. Taking the derivative of
with respect to and solving for when the derivative is zero givesWhen the object is three-dimensional, the optimum rotation is represented by a 3-by-3 rotation matrix R, rather than a simple angle, and in this case singular value decomposition
Singular value decomposition
In linear algebra, the singular value decomposition is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics....
can be used to find the optimum value for R (see the solution for the constrained orthogonal Procrustes problem
Orthogonal Procrustes problem
The orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B...
, subject to det
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
(R) = 1).
Shape comparison
The difference between the shape of two objects can be evaluated only after "superimposing" the two objects by translating, scaling and optimally rotating them as explained above. The square root of the above mentioned SSD between corresponding points can be used as a statistical measure of this difference in shape:This measure is often called Procrustes distance. Notice that other more complex definitions of Procrustes distance, and other measures of "shape difference" are sometimes used in the literature.
Superimposing a set of shapes
We showed how to superimpose two shapes. The same method can be applied to superimpose a set of three or more shapes, as far as the above mentioned reference orientation is used for all of them. However, Generalized Procrustes analysis provides a better method to achieve this goal.Generalized Procrustes analysis (GPA)
GPA applies the Procrustes analysisProcrustes analysis
In statistics, Procrustes analysis is a form of statistical shape analysis used to analyse the distribution of a set of shapes. The name Procrustes refers to a bandit from Greek mythology who made his victims fit his bed either by stretching their limbs or cutting them off.To compare the shape of...
method to optimally superimpose a set of objects, instead of superimposing them to an arbitrarily selected shape.
Generalized and ordinary Procrustes analysis differ only in their determination of a reference orientation
Orientation (geometry)
In geometry the orientation, angular position, or attitude of an object such as a line, plane or rigid body is part of the description of how it is placed in the space it is in....
for the objects, which in the former technique is optimally determined, and in the latter one is arbitrarily selected. Scaling and translation are performed the same way by both techniques. When only two shapes are compared, GPA is equivalent to ordinary Procrustes analysis.
The algorithm outline is the following:
- arbitrarily choose a reference shape (typically by selecting it among the available instances)
- superimpose all instances to current reference shape
- compute the mean shape of the current set of superimposed shapes
- if the Procrustes distance between mean and reference shape is above a threshold, set reference to mean shape and continue to step 2.
Variations
There are many ways of representing the shape of an object.The shape of an object can be considered as a member of an equivalence class formed by taking the set of all sets of k points in n dimensions, that is Rkn and factoring out the set of all translations, rotations and scalings. A particular representation of shape is found by choosing a particular representation of the equivalence class. This will give a manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
of dimension kn-4. Procrustes is one method of doing this with particular statistical justification.
Bookstein obtains a representation of shape by fixing the position of two points
called the bases line. One point will be fixed at the origin and the other at (1,0)
the remaining points form the Bookstein coordinates.
It is also common to consider shape and scale that is with translational and rotational components removed.
Examples
Shape analysisShape analysis
This article describes shape analysis to analyze and process geometric shapes.The shape analysis described here is related to the statistical analysis of geometric shapes, to shape matching and shape recognition...
is used in biological data
Biological data
Biological data are data or measurements collected from biological sources, which are often stored or exchanged in a digital form. Biological data are commonly stored in files or databases...
to identify the variations of anatomical features characterised by landmark data, for example in considering the shape of jaw bones.
One study by David George Kendall
David George Kendall
David George Kendall FRS was an English statistician, who spent much of his academic life in the University of Oxford and the University of Cambridge. He worked with M. S...
examined the triangles formed by standing stones to deduce if these were often arranged in straight lines. The shape of a triangle can be represented as a point on the sphere, and the distribution of all shapes can be thought of a distribution over the sphere.
The sample distribution from the standing stones was compared with the theoretical distribution to show that the occurrence of straight lines was no more than average.
See also
- Active shape modelActive shape modelActive shape models are statistical models of the shape of objects which iteratively deform to fit to an example of the object in a new image, developed by Tim Cootes and Chris Taylor in 1995...
- Alignments of random pointsAlignments of random pointsAlignments of random points, as shown by statistics, can be found when a large number of random points are marked on a bounded flat surface. This might be used to show that ley lines exist due to chance alone .One precise definition which expresses the generally accepted meaning of "alignment"...
- BiometricsBiometricsBiometrics As Jain & Ross point out, "the term biometric authentication is perhaps more appropriate than biometrics since the latter has been historically used in the field of statistics to refer to the analysis of biological data [36]" . consists of methods...
- Generalized Procrustes analysisGeneralized Procrustes analysisGeneralized Procrustes analysis is a method of statistical analysis that can be used to compare the shapes of objects, or the results of surveys, interviews, panels. It was developed for analyising the results of free-choice profiling, a survey technique which allows respondents to describe a...
- Image registrationImage registrationImage registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, from different times, or from different viewpoints. It is used in computer vision, medical imaging, military automatic target...
- Kent distribution
- MorphometricsMorphometricsMorphometrics refers to the quantitative analysis of form, a concept that encompasses size and shape. Morphometric analyses are commonly performed on organisms, and are useful in analyzing their fossil record, the impact of mutations on shape, developmental changes in form, covariances between...
- Orthogonal Procrustes problemOrthogonal Procrustes problemThe orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B...
- ProcrustesProcrustesIn Greek mythology Procrustes or "the stretcher [who hammers out the metal]", also known as Prokoptas or Damastes "subduer", was a rogue smith and bandit from Attica who physically attacked people by stretching them or cutting off their legs, so as to force them to fit the size of an iron bed...
External links
- Extensions to continuum of points and distributions Procrustes Methods, Shape Recognition, Similarity and Docking, by Michel Petitjean.