Elsevier

Pattern Recognition

Volume 47, Issue 2, February 2014, Pages 659-671
Pattern Recognition

Continuous Generalized Procrustes analysis

https://doi.org/10.1016/j.patcog.2013.08.006Get rights and content

Highlights

  • Continuous formulation of the generalized Procrustes analysis.

  • CGPA avoids the need to generate 2D projections from all 3D rigid transformations.

  • CGPA builds an efficient non-biased 2D shape model from 3D objects.

  • CGPA uses the Haar measure to integrate over the space of 3D rotations.

  • Experimental results building 2D shape models for different public datasets.

Abstract

Two-dimensional shape models have been successfully applied to solve many problems in computer vision, such as object tracking, recognition, and segmentation. Typically, 2D shape models are learned from a discrete set of image landmarks (corresponding to projection of 3D points of an object), after applying Generalized Procustes Analysis (GPA) to remove 2D rigid transformations. However, the standard GPA process suffers from three main limitations. Firstly, the 2D training samples do not necessarily cover a uniform sampling of all the 3D transformations of an object. This can bias the estimate of the shape model. Secondly, it can be computationally expensive to learn the shape model by sampling 3D transformations. Thirdly, standard GPA methods use only one reference shape, which can might be insufficient to capture large structural variability of some objects.

To address these drawbacks, this paper proposes continuous generalized Procrustes analysis (CGPA). CGPA uses a continuous formulation that avoids the need to generate 2D projections from all the rigid 3D transformations. It builds an efficient (in space and time) non-biased 2D shape model from a set of 3D model of objects. A major challenge in CGPA is the need to integrate over the space of 3D rotations, especially when the rotations are parameterized with Euler angles. To address this problem, we introduce the use of the Haar measure. Finally, we extended CGPA to incorporate several reference shapes. Experimental results on synthetic and real experiments show the benefits of CGPA over GPA.

Introduction

Procrustes analysis (PA) [1], [2], [3] is a form of statistical shape analysis used to analyze the distribution of a set of shapes. Given two shapes PA “superimposes” both shapes by optimally translating, rotating and scaling one shape towards the other. If more than two shapes are registered, the problem is typically known as generalized Procrustes analysis (GPA). GPA has been typically used in computer vision as a first step to build 2D models of shape or appearance of objects. These 2D models have been applied to solve problems such as object recognition [4], [5], facial feature detection and tracking [6], [7] and image segmentation [8], [9]. In particular, Point distribution models (PDMs) and active shape models (ASMs) [11] are among the most popular techniques to learn 2D objects models. PDMs and ASMs build the shape models from a 2D training set of image landmarks. In PDMs and ASMs, first GPA is used to remove rigid transformations and, then principal component analysis (PCA) is applied to construct a subspace that models the variation of the normalized shapes [11].

Fig. 1 (left) illustrates the GPA process of building shape models for PDM or ASM: given a set of 2D views of one or several 3D rigid or non-rigid objects under several configurations, the shape of the object is represented by several landmarks that are consistently labeled across view-points. Observe that if the object is rigid and the projection is orthographic, all views can be represented using a three-dimensional subspace [10]. Given the set of shapes (2D projections across views, objects or non-rigid transformations of 3D objects), GPA aligns the shapes using a rigid transformation (e.g., Euclidean or affine) to a 2D reference shape such that it minimizes the least-squares error. Although GPA has been extensively used, it suffers from three main limitations when modeling non-rigid transformations of a 3D object or a class of 3D objects: (i) 2D training samples do not necessarily cover a uniform sampling of all 3D transformations of an object, thereby biasing the estimate of the 2D models towards some particular configuration; (ii) it is computationally expensive to compute a rich set of 2D projections from all possible 3D transformations of a set of objects; and (iii) the large variability of the object class cannot necessarily be well registered with only one reference shape.

In order to deal with these limitations, we propose continuous generalized Procrustes analysis (CGPA). CGPA generalizes GPA using a continuous formulation that avoids the need to generate 2D projections from 3D configurations and uniformly covers the space of 3D transformations. Fig. 1 (right) illustrates the main idea behind CGPA, CGPA integrates over the space of 3D rotations avoiding the need to compute 2D projections. The continuous approach proposed in this paper is efficient in space and time, and is not biased to non-uniform sampling of the input space. A requirement of CGPA is to have access to a 3D mesh of several configurations of one or more 3D object, which is a realistic assumption in several computer vision problems. It is important to notice that building 2D models from 3D samples is a problem that has been relatively unexplored in computer vision [13], [27].

A major challenge of the proposed work is to integrate 3D objects over the special orthogonal group in 3D: S0(3). While there are many possible parameterizations of S0(3), we have chosen Euler angles because it is easy to determine the relation between the rotation limits and the integration domain (unlike other parameterizations such as quaternions). However, Euler angles suffer from well-known problems such the lack of uniform integration over the space of rotations [12] or the gimbal lock effect. In this paper, to address these problems we use the Haar measure in the definition of the integral and uniformly integrate over the space of rotations. In addition, in some cases a simple mean in the case of GPA is not enough to model the variability of objects across view-points, and we propose a multi-reference CGPA by using several reference shapes. Experimental results in several synthetic and real experiments show the benefits of CGPA over GPA. A preliminary version of this work was presented in [13].

The rest of the document is organized as follows: Section 2 reviews previous work in GPA and functional data analysis (FDA), Section 3 gives the mathematical background necessary for CGPA formulation and Section 4 motivates and derives CGPA. Section 5 reports our experimental results and Section 6 presents the conclusions and outlines future lines of research. Finally, in Appendix A we review the GPA fitting algorithm.

Section snippets

Previous work

This section reviews previous work within the field of computer vision on Procrustes analysis and functional data analysis (FDA).

Mathematical background

This section describes the mathematical background to our work. We review basic statements from the calculus of variations and integral calculus, as well as details regarding SO(3), and measures defined on it.

Continuous generalized Procrustes analysis

In this section, we formulate the proposed continuous generalized Procrustes analysis (CGPA). CGPA extends GPA by adopting a continuous formulation that incorporates the information of all rigid 3D transformations.

Experimentation

This section describes the experimental validation that compares the performance of CGPA to standard discrete PA methods.

Conclusions

In this work, we have proposed continuous generalized Procrustes analysis, a continuous alternative to GPA, as a method for learning 2D shape models from 3D objects. CGPA has three main advantages over GPA: (i) it does not need to generate 2D samples, (ii) unbiased 2D models are constructed, and (iii) the memory requirements for CGPA are only those of the storage of the 3D objects and the reference shape(s). Moreover, we have reviewed the problems of the uniform sampling of 3D transformations

Conflict of interest

None declared.

Acknowledgments

This research was supported by the projects TIN2009-14404-C02, CONSOLIDER-INGENIO 354CSD2007-00018, TIN2012-38416-C03-01, FEDER funds, and the Comissionat per a Universitats i Recerca del Departament d'Innovació, Universitats i Empresa de la Generalitat de Catalunya.

Laura Igual received the degree in Mathematics from the University of Valencia in 2000. She obtained her Ph.D. Thesis in 2006 from the University Pompeu Fabra and since then she is a research member at the Computer Vision Center of Barcelona. Since 2009, she is a lecturer at University de Barcelona.

References (37)

  • M.J. Jones, T. Poggio, Multidimensional morphable models, in: ICCV,...
  • F. De la Torre, M. Nguyen, Parameterized kernel principal component analysis: theory and applications to supervised and...
  • T. Cootes et al.

    Active appearance models

    Transactions on Pattern Analysis and Machine Intelligence

    (2001)
  • S. Osher et al.

    Geometric Level Set Methods in Imaging, Vision, and Graphics

    (2003)
  • D. Mumford et al.

    Optimal approximations by piecewise smooth functions and associated variational problems

    Communications on Pure and Applied Mathematics

    (1989)
  • C. Tomasi et al.

    Shape and motion from image streams under orthographya factorization method

    International Journal of Computer Vision

    (1992)
  • T.F. Cootes, C.J. Taylor, Statistical Models of Appearance for Computer Vision, Technical Report, University of...
  • J. Kuffner, Effective sampling and distance metrics for 3d rigid body path planning, in: ICRA,...
  • Cited by (21)

    • Semi-supervised learning with dropouts

      2023, Expert Systems with Applications
    • Procrustes: A python library to find transformations that maximize the similarity between matrices

      2022, Computer Physics Communications
      Citation Excerpt :

      The algorithms implemented are detailed in the appendix emphasizing the more innovative aspects of the Procrustes library, most notably several valuable heuristics for two-sided permutation Procrustes problems. For future work, more flavors of Procrustes methods will be implemented, including an alternative way of solving orthogonal Procrustes problem without SVD [73], generalized Procrustes analysis (GPA) [74,3,75], projected Procrustes analysis [76,77], and continuous Procrustes methods [78,79]. Furthermore, improvements to the scalability of the implemented algorithms will help make the analysis of very large matrices more feasible.

    • Feature selection method based on support vector machine and shape analysis for high-throughput medical data

      2017, Computers in Biology and Medicine
      Citation Excerpt :

      Therefore, it is very suitable for the feature reduction of high dimensional data with small sample size. In this paper, a rigid shape analysis method, PA [37–41], is employed. It searches for the best approximation of two groups of geometric structures under isomorphic scaling, translation and rotation transformations.

    • Uncertainty characterization of the orthogonal Procrustes problem with arbitrary covariance matrices

      2017, Pattern Recognition
      Citation Excerpt :

      This is not the objective of the optimization problem (3). However, once a reference shape is chosen or found (for example using the classical alternation approach [1, Chapter 9] or the more evolved approaches proposed in [33,29], the problem of finding the Euclidean transformation is exactly expressed by (3) and therefore all the derivations in this and the following sections hold. Within the scope of perturbation theory, the error models of the known variables are defined as

    • Generalized correlation for shape alignment

      2016, Information Sciences
      Citation Excerpt :

      However, silhouette (a popular form for storing shapes) cannot be aligned by directly using these methods. Procrustes Analysis (PA) [10,15] is one of the state-of-the-art methods used in shape alignment. However, it requires manually selecting point-to-point correspondences.

    View all citing articles on Scopus

    Laura Igual received the degree in Mathematics from the University of Valencia in 2000. She obtained her Ph.D. Thesis in 2006 from the University Pompeu Fabra and since then she is a research member at the Computer Vision Center of Barcelona. Since 2009, she is a lecturer at University de Barcelona.

    Xavier Perez-Sala received the B.Sc. degree in Industrial Electronics (2008) and the M.Sc. degree in Artificial Intelligence (2010) from the Technical University of Catalonia. He is currently pursuing a Ph.D. degree in Artificial Intelligence at the same university and the Fundació Privada Sant Antoni Abat. Since 2012 he is member of the Computer Vision Center of Barcelona.

    Sergio Escalera received the B.S. and M.S. degrees from the Universitat Autònoma de Barcelona in 2003 and 2005, respectively. He obtained the Ph.D. degree on multi-class visual categorization systems at Computer Vision Center, UAB. Currently, Lecturer of Universitat de Barcelona. Partial time professor at the Universitat Oberta de Catalunya.

    Cecilio Angulo received the M.Sc. degree in Mathematics from the University of Barcelona (1993) and a Ph.D. in Sciences from the Technical University of Catalonia (2001).He is a associated professor at the same university from 2007. He is coordinator of the master's degree in Automatic Control and Robotics.

    Fernando De la Torre received his B.Sc. in Telecommunications (1994), M.Sc. (1996), and Ph.D. (2002) in Electronic Engineering from La Salle of Engineering in Ramon Llull University. He was an assistant and associate professor in La Salle (1997, 2000). Since 2005, he is a research assistant professor in the Robotics Institute at Carnegie Mellon University.

    View full text