Abstract

The goal of this work is to develop techniques that can be used for comprehensive shape analysis of 3D objects (as continuous, parameterized surfaces) under a Riemannian framework. This requires a Riemannian metric that allows: (1) re-parameterizations of surfaces by isometries, and (2) efficient computations of geodesic paths between surfaces. These tools allow for computing Karcher means and covariances (using tangent PCA) for shape classes, and a probabilistic classification of surfaces. The process of computing geodesics requires optimal re- parameterizations (deformations of grids) of surfaces. This results in a superior alignment of geometric features. The resulting means and covariances are better representatives of the original data and lead to parsimonious shape models.

Geodesic with Fixed Parameterization
Geodesic in Shape Space

Problem Introduction

Shape is an important feature of objects and can be immensely useful in characterizing objects for the purpose of detection, tracking, classification, and recognition. As an example, it is central in medical image analysis where advances in non-invasive imaging technology have enabled researchers to study biological variations of anatomical structures. Studying shapes of 3D anatomical structures in the brain is of particular interest because many diseases can potentially be linked to alterations of these shapes. Shape analysis of surfaces has also become important in biometrics, graphics, 3D TV, computer vision, etc. There has been a significant amount of research and activity in the general area of shape analysis. By shape analysis we mean a set of tools for comparing, matching, deforming, and modeling shapes. The main differences amongst different tools proposed so far lie in the mathematical representations and metrics used in the analysis.

There have been several analogous representations of surfaces. Several groups have proposed methods for studying the shapes of surfaces by embedding them in volumes and deforming these volumes (1). While these methods are both prominent and pioneering in medical image analysis, they are typically computationally expensive since they try to match not only the objects of interest but also some background space containing them. An alternative approach is based on manually-generated landmarks under the Kendall shape (2). Others study 3D shape variabilities using various other methods such as level sets (3) or curvature flows (4). Also, there has been remarkable success in the use of medial representations for shape analysis, especially in medical image analysis, see e.g. (5). However, the most natural representation for studying shapes of 3D objects seems to be parameterized surfaces. In case of parameterized surfaces, there is an additional issue of handling the parameterization variability. Some papers, e.g. using SPHARM (6), tackle this problem by choosing a fixed parameterization. Kilian et al. (7) presented a technique for computing geodesics between triangulated meshes (discretized surfaces) but at their given parameterizations. Similar to elastic representations of curves, we would like to include the parameterization variable in the analysis. This inclusion results in an improved registration of features across surfaces. Of course, the question is: How can we include the parameterization variable in our shape analysis? A large set of papers in the literature treat parameterization (or registration) as a pre-processing step. In other words, they take a set of surfaces and use some energy function, such as the entropy (8) or the minimum description length (9), to register points across surfaces. Once the surfaces are registered, they are compared using standard procedures. There are several fundamental problems with this approach. Firstly, due to a registration procedure based on ensembles, the distance between any two shapes ends up being dependent on the other shapes in the ensemble. Secondly, the registration and the comparisons of surfaces end up being disjoint procedures and under different metrics.

Our Approach

To discuss our approach (10) (11) (12) (13), let f1 and f2 denote two surfaces; f1 and f2 are elements of an appropriate space F, and let ‹‹∙,∙›› be the chosen Riemannian metric on F. Then, under certain conditions, the geodesic distance between shapes of f1 and f2 will be given by quantities of type:

(This assumes that translation and scaling variability has already been removed.) Here G(t) is a parameterized path in F, and the quantity

denotes the length of G. The minimization inside the brackets, thus, denotes the problem of finding a geodesic path (locally the shortest path) between the surfaces f1 and O(f2 ◦ γ), where O and γ stand for an arbitrary rotation and re-parameterization of f2, respectively. The minimization outside the bracket seeks the optimal rotation and re-parameterization of the second surface so as to best match it with the first surface. In simple words, the outside optimization solves the registration or matching problem while the inside optimization solves for both an optimal deformation (geodesic) and a formal distance (geodesic distance) between shapes. An important strength of this approach is, thus, that the registration and comparison are solved jointly rather than sequentially. Another strength is that this framework can be easily extended to different types of surfaces. In order to solve the outside optimization problem over SO(3) and Γ we utilize Procrustes analysis (for rotation) and a gradient descent algorithm (for parameterization). This provides the optimal registration of the two surfaces. An example of this procedure is given in Figure 1.

Figure 1: Optimal re-parameterization of surfaces.

In order to solve the inside optimization problem, which deals with finding geodesics in the space of parameterized surfaces, we utilize a gradient method called path-straightening. The basic idea is to initialize the path in the space of parameterized surfaces and update it iteratively according to the gradient of a certain energy. A few examples of geodesic paths between optimally registered surfaces are given in Figure 2.

Figure 2: Geodesics in shape space of parameterized surfaces.

References

  1. Computational Anatomy: An Emerging Discipline. U. Grenander, M.I. Miller. 1998, Quarterly of Applied Mathematics, pp. 617-694.
  2. I.L. Dryden, K.V. Mardia. Statistical Shape Analysis. s.l. : John Wiley & Son, 1998.
  3. A Fast Level Set Based Algorithm for Topology Independent Shape Modeling. R. Malladi, J.A. Sethian, B.C. Vemuri. 1996, Journal of Math Imaging and Vision, pp. 269-290.
  4. Ricci Flow for 3D Shape Analysis. X. Gu, S. Wang, J. Kim, Y. Zeng, Y. Wang, H. Qin, D. Samaras. 2007. IEEE International Conference on Computer Vision.
  5. Multi-Object Analysis of Volume, Pose, and Shape Using Statistical Discrimination. K. Gorczowski, M. Styner, J.Y. Jeong, J.S. Marron, J. Piven, H.C. Hazlett, S. M. Pizer, G. Gerig. 2010, IEEE Pattern Analysis and Machine Intelligence, pp. 652-666.
  6. Parameterization of Closed Surfaces for 3D Shape Description. C. Brechbuler, G. Gerig, O. Kubler. 1995, Compter Vision and Image Understanding, pp. 154-170.
  7. Geometric Modeling in Shape Space. M. Kilian, N.J. Mitra, H. Pottmann. s.l. : SIGGRAPH, 2006.
  8. Entropy-Based Particle Systems for Shape Correspondence. J. Cates, M. Meyer, P.T. Fletcher, R. Whitaker,. 2006. MICCAI Workshop on Mathematical Foundations of Computational Anatomy. pp. 90- 99.
  9. Building 3-D Statistical Shape Models by Direct Optimization. R.H. Davies, C.J. Twining, T.F. Cootes, C.J. Taylor. 2010, IEEE Medical Imaging, pp. 961-981.
  10. A Novel Riemannian Framework for Shape Analysis of 3D Objects. S. Kurtek, E. Klassen, Z. Ding, A. Srivastava. San Francisco, CA : s.n., 2010. IEEE Computer Vision and Pattern Recognition.
  11. Parameterization-Invariant Shape Comparisons of Anatomical Surfaces. S. Kurtek, E. Klassen, Z. Ding, S.W. Jacobson, J.L. Jacobson, M.J. Avison, A. Srivastava. 2010, IEEE Medical Imaging, pp. 849-858.
  12. Elastic Geodesic Paths in Shape Space of Parameterized Surfaces. S. Kurtek, E. Klassen, J.C. Gore, Z. Ding, A. Srivastava. In Review, IEEE Pattern Analysis and Machine Intelligence.
  13. Parameterization-Invariant Shape Statistics and Probabilistic Classification of Anatomical Surfaces . S. Kurtek, E. Klassen, Z. Ding, M.J. Avison, A. Srivastava. Irsee, Germany : s.n., 2011. Information Processing in Medical Imaging.