Procrustes analysis普氏分析

Procrustes Analysis Amy Ross Department of Computer Science and Engineering University of South Carolina, SC 29208 arossam2@cse.sc.edu Abstract. Shape correspondence is an important aspect of imaging. Understanding shape is the basis of any correspondence. The correspondence and analysis of shapes plays a vital role, not only in determining correspondence, but also determining the validity of the algorithms used to place the landmarks in accurate locations. The analysis should be well defined so that it is unbiased and thorough in its evaluation. Procrustes analysis is a rigid shape analysis that uses isomorphic scaling, translation, and rotation to find the “best” fit between two or more landmarked shapes. This paper is an in-depth study of Procrustes analysis. 1 Introduction Procrustes analysis has many variations and forms. Of these forms, the generalized orthogonal Procrustes analysis (GPA) is the most useful in shape correspondence, because of the orthogonal nature of the rotation matrix. Gower played an important role in the introduction and derivation of the generalized orthogonal Procrustes analysis in 1971-75. Though Hurley and Cattell first used the term Procrustes analysis in 1962 with a method that did not limit the transformation to an orthogonal matrix [2]. This paper will explore what shape is, how to maintain shape, landmarks, and how these all work together to correspond shapes using the technique of generalized orthogonal Procrustes analysis. 2 Shape and Landmarks Shape and landmarks are two important concepts involved with generalized orthogonal Procrustes analysis. Both shape and landmarks have their own role in the process of aligning shapes. The following is an overview of shape and landmarks to give a foundation for the generalized orthogonal Procrustes analysis. 2.1 Shape The definition of shape must be known in order to understand how to correspond shapes. Shape: “all the geometrical information that remains when location, scale and rotational effects are filtered out from an object” [3] By this definition of shape, there exists transforms that allow the shape to move so that the differences may be removed between two shapes while preserving the angles and parallel lines, and therefore preserving the shape itself. Isomorphic scaling, translation, and rotation are the three transforms used to align shapes. These shape-preserving transforms are called Euclidean similarity transforms. Fig. 1. The same shape represented in four ways by different Euclidean similarity transforms [3] 2.2 Landmarks Shape can be described as a finite number of points along the outline of the shape. These points are called landmarks. Landmark: a finite set of points on a shapes surface that accurately describe a shape Fig. 2. Example of how landmarks are used to represent a shape There consists of three types of landmarks: Anatomical landmarks: expert (i.e. Doctor) assigned points that represent a biological object or objects. Mathematical landmarks: points assigned by some mathematical property (i.e. high curvature).  Pseudo-landmarks: point located between the other two types of landmarks or points around the outline [1]. 3 Generalized Orthogonal Procrustes Analysis Procrustes analysis is the comparison of two sets of configurations (shapes). Therefore, Procrustes analysis is limited in its application. Generalized orthogonal Procrustes analysis (GPA) is the evaluation of k sets of configurations. With GPA the k sets can be aligned to one target shape or aligned to each other. This paper will discuss the latter, since it is easily adapted to one target shape. Algorithm for generalized orthogonal Procrustes analysis: 1. Select one shape to be the approximate mean shape (i.e. the first shape in the set). 2. Align the shapes to the approximate mean shape. a. Calculate the centroid of each shape (or set of landmarks). b. Align all shapes centroid to the origin. c. Normalize each shapes centroid size. d. Rotate each shape to align with the newest approximate mean. 3. Calculate the new approximate mean from the aligned shapes. 4. If the approximate mean from steps 2 and 3 are different the return to step 2, otherwise you have found the true mean shape of the set. 3.1 Translation The translation step essentially moves all the shapes to a common center. The origin (0,0) is the most likely candidate to become that common center, yet not exclusively so. For this example the origin will be the common center. (1) X: kxm matrix of coordinates of the k landmarks in m dimensions (m = 2 or 3) Xc: the new coordinates of X centered at the origin The centroid is calculated from the column sums of the matrix X divided by the number of landmark (number of rows). Once the centroid is calculated then subtracting the centroid from each element in the matrix will center it at the origin. 3.2 Isomorphic Scaling Isomorphic scaling is a manipulation technique that transforms a shape smaller or larger while maintaining the ratio of the shapes proportions. Normalization is a type of isomorphic transformation that is useful to scale the shapes to a similar size. (2) X: the coordinates of X centered at the origin Xn: the coordinates of X centered and normalized 3.3 Rotation When the matrices are aligned and scaled it is time for the rotation step. Rotation involves aligning all of the shapes to one target shape. The average is the target shape used for this process. X: the coordinates of X centered and normalized Q: the orthogonal rotation matrix to align X to the average : the average matrix Rotation uses the Eucidean/Frobenius norm where ||A|| = trace(A’A), which is the sum-of-squares of the elements A [2]. So, we will minimize the difference between the average and the rotated shape matrix using the sum-of-squares. ||XQ - || min (3) Since, ||A|| = trace(A’A), we have ||XQ - || = trace(X’X+ ’ ) –2trace( ’XQ) (4) Since the first part of the rhs doesn’t contain Q, we have trace( ’XQ) max (5) Using singular value decomposition of ’X=USV’ and the cyclic property of trace we have trace( ’XQ) = trace(USV’Q) = trace(SV’QU) = trace(SH) (6) H = V’QU is an orthogonal (pxp) matrix because it is the product of orthogonal matrices. Thus, we have trace(SH) = si hii (7) Therefore, since si is non-negative numbers and trace(SH) is maximum when hii=1 for i=1, 2…p (the maximal value of an orthogonal matrix), we have H = I = V’QU (8) Thus the Q that minimizes ||XQ - || is Q = VU’ (9) Therefore the rotation is completed by multiplying VU’ to the X matrix in order to align it with the matrix. The following figure is an example of the Procrustes process. Fig. 3. Left: 40 unaligned shapes. Right: 40 aligned shapes with the mean given in red [1] 4 Conclusion General orthogonal Procrustes analysis has several advantages. GPA is a fairly straightforward approach to shape correspondence. The algorithms low complexity allows for easy implementation. Also, GPA is a practical solution for very similar object alignment. These advantages give merit to the Procrustes process. General orthogonal Procrustes analysis does however have some disadvantages as well. GPA is a rigid evaluation and requires a one to one landmark correspondence both of which limit it correspondence capabilities. Also, the convergence of means is not guaranteed and therefore convergence is then signified when there is not a significant change in the mean. This lack of convergence leaves room for a more accurate aligning algorithm. The disadvantages exist, but general orthogonal Procrustes analysis is an effective way to correspond shapes. But just because it is effective does not mean that it is the best algorithm for the job. Even Hurley and Cattell wrote that Procrustes analysis “lends itself to the brutal feat of making almost any data fit almost any hypothesis!” [2] In the end we are still just like Procrustes1, stretching and chopping to find the right fit. 1 In the Greek myths of Theseus, Procrustes was an inn owner with a unique “one-size-fits- all” bed. In order for this magical bed to work, Procrustes would chop off the legs of any guests who were too tall and stretch, on the rack, any guest who was too short. References 1. Cairns, Matthew James Francis: An Investigation into the use of 3D Computer Graphics for Forensic Facial Reconstruction, Glasgow University, 2000. 2. Gower, John C. and Dijksterhuis, Garmt B.: Procrustes Problems, Oxford University Press, 2004. 3. Stegmann, Mikkel B., Gomez , David Delgado: A Brief Introduction to Statistical Shape Analysis, Technical University of Denmark, Lyngby, 2002.