IntroductionContributionsRelated workOverviewVerificationCompound TransformsResults and ApplicationsTheoretical AnalysisPartial and Approximate Symmetry Detection for 3D GeometryNiloy J. MitraStanford UniversityLeonidas J. GuibasStanford UniversityMark PaulyETH Z¨urich0.02-0.02Figure 1: Symmetry detection on a sculpted model. From left to right: Original model, detected partial and approximate symmetries,color-coded deviations from perfect symmetry as a fraction of the bounding box diagonal.Abstract“Symmetry is a complexity-reducing concept [...]; seek it every-where.” - Alan J. PerlisMany natural and man-made objects exhibit significant symmetriesor contain repeated substructures. This paper presents a new al-gorithm that processes geometric models and efficiently discoversand extracts a compact representation of their Euclidean symme-tries. These symmetries can be partial, approximate, or both. Themethod is based on matching simple local shape signatures in pairsand using these matches to accumulate evidence for symmetries inan appropriate transformation space. A clustering stage extractspotential significant symmetries of the object, followed by a veri-fication step. Based on a statistical sampling analysis, we providetheoretical guarantees on the success rate of our algorithm. Theextracted symmetry graph representation captures important high-level information about the structure of a geometric model which inturn enables a large set of further processing operations, includingshape compression, segmentation, consistent editing, symmetriza-tion, indexing for retrieval, etc.CR Categories: I.3.5 [Computer Graphics]: Computational Ge-ometry and Object Modeling.Keywords: geometric modeling, shape analysis, symmetry detec-tion, shape descriptor, sampling guarantees.1 IntroductionSymmetry is an essential and ubiquitous concept in nature, science,and art. For example, in geometry, the Erlanger program of FelixKlein [1893] has fueled for over a century mathematicians’ inter-est in invariance under certain group actions as a key principle forunderstanding geometric spaces. Numerous biological, physical, orman-made structures exhibit symmetries as a fundamental designprinciple or as an essential aspect of their function. Whether byevolution or design, symmetry implies certain economies and effi-ciencies of structure that make it universally appealing. Symmetryalso plays an important role in human visual perception and aes-thetics. Arguably much of the understanding of the world aroundus is based on the perception and recognition of shared or repeatedstructures, and so is our sense of beauty [Thompson 1961].In this paper we present a novel method for detecting meaningfulsymmetries in digital 3D shapes. We understand symmetry as theinvariance under a set of transformations — in our case translation,rotation, reflection, and uniform scaling, the common generatorsof the Euclidean group. The figure below shows a 2D illustration.As can be seen in this example, symmetries or congruences thatare quite apparent to us can be approximate and occur at differ-ent scales. Our goal is to define an algorithm that extracts (partial)symmetries at all scales, including approximate or imperfect sym-metries of varying degree. This allows the user to select the subsetof symmetries that are most meaningful for a specific application.Examples include scan registration and alignment, shape matching,segmentation and skeleton extraction, compression, advanced mod-eling and editing, and shape database retrieval.reflection reflection + rotation + translation scale + rotation + translationTo achieve this goal, we separate the symmetry computation intotwo phases: In the first step, we compute simple local shape de-scriptors at a selected set of points on the shape. These descriptorsare chosen so that they are invariant under the group actions of in-terest. We use these local descriptors to pair up points that could bemapped to each other under a candidate symmetry action. We thinkof each such pair as depositing mass, or voting, for a specific sym-metry in the transformation space of interest. In this space, pairswith similar transformations form clusters that provide evidence forthe corresponding symmetry relation.In the second step we use a stochastic clustering algorithm to ex-tract the significant modes of this mass distribution. Since the map-ping to transformation space does not preserve the spatial coher-ence or structure of samples on the input shape, we verify whether ameaningful symmetry has been found by checking the spatial con-sistency of the extracted subparts of the surface. Our clusteringmethod provides the necessary surface correspondences, since ev-ery point mass in transformation space corresponds to a candidatepair of points in the spatial domain. Thus only a small set of can-didates samples needs to be considered when detecting and extract-ing symmetric surface patches, avoiding a costly quadratic spatialsearch over the whole input data set.This separation into two stages is crucial for the effectiveness ofour algorithm. The underlying observation is the following: givena proposed symmetry relation, it is simple and efficient to verifywhether this specific symmetry is present in the model; we just needto apply the symmetry transform and check whether the model ismapped onto itself, or a sub-part of the model is mapped to a corre-sponding sub-part. However, the number of all potential mappingsis by far too large to do an exhaustive search. Therefore, we firstaccumulate statistical evidence for which symmetries are presentvia our clustering in transformation space. Only if this evidenceis sufficient do we perform spatial verification to check whether aspecific symmetry is actually valid. Thus the complexity of symme-try extraction depends primarily on the number and size of relevantsymmetries present in the model and not on the complexity of themodel itself or that of the underlying symmetry group. As part ofour approach, we can provide a quantitative measure on the “exact-ness”, or saliency, of a symmetry relation, which allows the userto control the degree of perfection in the extracted symmetries. Inaddition, by specifying the size of the set of local shape descriptors,the user can trade accuracy for computational efficiency. Whilefewer samples are sufficient for detecting large global symmetries,small partial symmetries require a significantly denser sampling.The final output of
View Full Document
Unlocking...