DOC PREVIEW
Symmetry Restoration by Stretching

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CCCG 2009, Vancouver, BC, August 17–19, 2009Symmetry Restoration by StretchingMisha Kazhdan∗Nina Amenta†Shengyin Gu†David F. Wiley†Bernd Hamann†AbstractWe consider restoring the bilateral symmetry of an ob-ject which has been deformed by compression. Thisproblem arises in paleontology, where symmetric bonesare compressed in the process of fossilization. Our inputis a user-selected set P of point-pairs on the deformedobject, which are assumed to be mirror-images in someundeformed set AP , with some added noise. We care-fully formulate the problem, and give a closed-form so-lution.1 IntroductionMuch of what we know about evolution comes from thestudy of fossils. From the shapes of the b ones of extinctanimals we form hypotheses about how they moved,what they ate, how they are related to each other, andso on. Yet these shapes are usually deformed by the ge-ological pro c es se s which occur during fossilization, forexample the skull in Figure 1. For some fossils, for ex-ample skulls and vertebrae, we can assume that the orig-inal shape was roughly bilaterally symmetric. We canuse this assumption to reverse the deformation, or atleast limit the family of possible reconstructions. Thisprocess is sometimes called retrodeformation.Usually the input for retrodeformation is a set ofpoint-pairs, chosen by the paleontologist on the de-formed specimen. We assume the point-pairs are storedin a 3 × 2n matrix P with the assumption that pointp2iwas the mirror image of p2i+1, on the original objectbefore deformation. The point-pairs are chosen usingthe expert’s understanding of the biological shape. De-veloping automatic methods for finding point-pairs orother useful descriptions of the input data is a different,also well-studied, research question (see below).Under the ass umption that the objec t was com-pressed, we assume that the inverse deformation shouldbe what we call a single axis stretch. A single axisstretch is pro duced by choosing a direction vector andscaling only in that direction; it is represented by a sym-metric matrix A for which two of its eigenvalues are oneand the third is greater than one. Single-axis stretchesare important, since the simplest hypothesis for how a∗Department of Computer Science, Johns Hopkins University†Department of Computer Science, University of Cal ifornia atDavisFigure 1: A deformed dinosaur skull in the CarnegieMuseum of Science, Pittsburgh.fossil is deformed is that it is compressed in a single di-rection. We want to find a single-axis stretch A suchthat AP is as symmetric as possible.Problem 1 Let P be a set of point-pairs. Find thesingle-axis stretch A, a translation vector t, and a planeof reflection, such that the mean-squared errorE(A, w, t) =nXi=1||A(p2i+t)−Reflw(A(p2i+1+t)||2(1)is minimized. Here Reflwis the affine transformationreflecting space across the plane with normal w passingthrough the origin.The choice of mean-squared error is natural, and con-sistent with usual practice in paleontology.But there is a problem with this formulation: there isnot a unique solution in the absence of noise. Instead, aswe shall see, there is a one-dimensional set of single-axis21st Canadian Conference on Computational Geometry, 2009stretches that produce differe nt, but equally optimallysymmetric, shapes. As an analogy, think of fitting aplane to set of points that lie on a line; there is nounique solution. If noise is added, there is a unique so-lution, but it provides information only about the noise,not about the unknown plane that contains the points.Similarly, when P is noisy the unique minimum errorsolution selects one of the possible symmetrizing single-axis stretches, but based on the noise rather than onany information about the original shape.In the absence of any other information, the best ofthese possible solutions would be the one requiring min-imum deformation from the input shape: the smalleststretch (alternatives such as maintaining the volume orminimizing the squared distance from the input data arenot reasonable choices assuming compression). Whenother information is available - comparison with otherfossils, or perhaps similarity to extant species - it canbe used to select a solution [6, 11].wv-mFigure 2: Two ideas for retrodeformation. On the left,a perfectly symmetric set of point-pairs, deformed bycompression along a single axis. Center, it seems intu-itively clear that stretching in direction v is the mostefficient way to make w and −m perpendicular. Right,making the entire point set isotropic also makes it sym-metric.Our approach: In this paper we combine two ideas forrestoring symmetry, illustrated in Figure 2. The first isa “well known” idea in the area of symmetry detection:if there is any linear transformation which makes P per-fectly symmetric, then any linear transformation whichtakes P to an isotropic set˜P (that is, the principal com-ponents of˜P are all vectors of length one), also makesP pe rfectly symmetric. This means that the set of allperfectly symmetric solutions are exactly the transfor-mations of˜P which preserve symmetry. We apply thisidea to a any approximately symmetric s et P by firsttransforming P into an isotropic set˜P and then findingthe best of plane of symmetry of˜P .We then consider the single-axis stretches as a subsetof this family, and describe how to find the minimal sin-gle axis stretch. This method is e sse ntially the same as aprocedure for retrodeformation suggested by the phys-ical anthropolgists Zollikofer and Ponce de Le´on [13](Appendix E): given a vector w estimating the averagedirection of the vectors p2i− p2i+1, and an estimate mof the projection of that vector on the sagittal plane ofreflection, stretch in the direction v bisecting ∠w, −muntil w and −m become perpendicular. This methodwas presented without a proof of optimality. We usethe first idea to select v and m, and prove that the so-lution is indeed optimal in 3D.Other related work: In paleontology, this problemhas been approached in different ways. An article byMotatni [6] gave a closed-form solution in two dimen-sions, using a somewhat different set-up. Other 2Dmethods which have been used to study, for example,trilobites and turtles, are compared experimentally byAngielczyk and Sheets [1]. More free-form non-lineardeformations have also been considered [7]. In morpho-metrics, the problem of measuring symmetry has beenstudied [4, 3].Research in computer science has focused on detect-ing


Symmetry Restoration by Stretching

Download Symmetry Restoration by Stretching
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Symmetry Restoration by Stretching and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Symmetry Restoration by Stretching 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?