Recent Advances In Shape Correspondence
The Visual Computer (2020) 1760-0SURVEYRecent advances in shape correspondenceYusuf Sahillioğlu1Published online: 28 September 2019 Springer-Verlag GmbH Germany, part of Springer Nature 2019AbstractImportant new developments have appeared since the most recent direct survey on shape correspondence published almost adecade ago. Our survey covers the period from 2011, their stopping point, to 2019, inclusive. The goal is to present the recentupdates on correspondence computation between surfaces or point clouds embedded in 3D. Two tables summarizing andclassifying the prominent, to our knowledge, papers of this period, and a large section devoted to their discussion lay downthe foundation of our survey. The discussion is carried out in chronological order to reveal the distribution of various typesof correspondence methods per year. We also explain our classification criteria along with the most basic solution examples.We finish with conclusions and future research directions.Keywords Shape correspondence · Shape matching · Survey1 IntroductionShape correspondence problem is stated as finding a set ofcorresponding points between given shapes. In our scope, theshapes are deformable and they are discretizations embeddedin 3D in the form of (i) surface mesh structures consistingof vertices, edges, and polygonal faces, or (ii) point clouds.While the common scenario dictates operation on two shapesin isolation, it is also possible to process multiple shapes atonce.This problem is interesting because finding correspondences between shapes is a fundamental operation in manycomputer graphics and digital geometry processing algorithms such as shape interpolation, shape reconstruction,shape retrieval, texture transfer, segmentation transfer, deformation transfer, symmetry detection, change detection, andstatistical shape modeling.This problem is difficult because it involves understanding the structure of the shapes at both the local and globallevels. The understanding requires a search in a huge solution space for the deformable scenario that we address inthis survey. Unlike the rigid shape correspondence scenariowhich deals with a space with low degree-of-freedom consisting only of rotation and translation, the deformable, akaB1Yusuf etu.edu.tr/ ysComputer Engineering Department, METU, Ankara, Turkeynon-rigid, scenario searches over the entire second shape tomatch a given point in the first shape. The second shapeexhibits bending and possible stretching. The space is therefore huge and nonlinear in that we have O(N !) possibilitiesof matching N points spread on both shapes. As in the caseof all difficult problems, one needs to learn from experienceby being aware of the existing solutions before developinghis own, hence this survey.Motivation The main motivation of this survey is to wrapup all the interesting and brand new correspondence methods since 2011, which is the endpoint of the closest work[104]. It is exciting to list all these new techniques based onwell-established frameworks as well as fundamentally different approaches such as functional maps and deep neuralnetworks. Collectionwise correspondence problem has alsobeen introduced and extensively studied within the 2011–2019 scope of our survey.2 Comparison with other surveysAlmost a decade later after the most recent shape correspondence survey by van Kaick et al. [104,105], we now present asurvey that compactly lists and discusses the new work. Weindeed pay special attention to cite shape correspondenceworks published on or after 2011, and refer the reader toSTAR—State of The Art Report [104], or its journal version[105], for the older ones.123
1706We also note a survey on mapping from 2014 [53]that deals mostly with parameterization and registrationtechniques, which constitute a subset of correspondencecomputation methods. Moreover, 87% of their referencesare published before 2011. The remaining ones also haveno overlap with our references at all.There is also a 2013 survey [98] that is devoted entirelyto 3D surface registration, which is one of the many possible ways to compute correspondences as we will see inSect. 3.5.1.Surveys on shape retrieval [54,61] also relate to our surveyas the evaluation of shape similarity, a requirement for theretrieval problem, can also be performed through correspondences. In fact, retrieval and correspondence problems areso related that the term shape matching is used interchangeably in the literature for these tasks. STAR [12], or its journalversion [11], explores shape similarity assessment problemby analyzing and describing shapes using geometrical andtopological properties of real functions.In summary, our survey, similar to the closest work [105],overviews shape correspondence methods directly. In addition to presenting new discoveries since 2011, we also discussmore on parameterization-based and learning-based methodswhich are lacking in [105].3 Classification criteriaIn the sequel, we categorize shape correspondence methodsbased on several criteria. Tables 1 and 2 summarize the entiresurvey by positioning the methods of interest with respect tothese criteria. We then elaborate on the criteria in the following subsections. Methods are discussed thoroughly in theguidance of these criteria in Sect. 4.3.1 Similarity levelTwo shapes between which correspondence is sought maybe either fully similar or partially similar. For the former,although additional deformations may be (and are likely tobe) admitted, it is certainly forbidden for one shape to possessa part that has no semantically meaningful counterpart on theother shape. If such a possession occurs, then we have thelatter case to deal with, which is more challenging (Fig. 1).The level of challenge increases further for the latter underarbitrary scaling of shapes. The former is not affected fromthis issue since scale can always be normalized prior to thematching process by using a global intrinsic property, suchas maximum geodesic distance, that is certainly compatiblebetween fully similar shapes.123Y. Sahillioğlu3.2 Deformation typeTwo shapes to be matched may differ by deformationsmost common of which is isometry. Under isometric deformations pairwise geodesic distances over the surface arepreserved (Fig. 1a), a constraint simplifies the correspondence searching process. Isometry is an important clue forshape correspondence; not only since most real-world deformations are isometric, but also because semantically similarshapes have similar metric structures. Articulation/bendingand rigid transformations are isometries.As soon as we have stretching and/or squeezing involved,we have a non-isometric deformation, a mild example ofwhich is depicted in Fig. 1b. Some severely non-isometricpairs are human versus gorilla and cat versus giraffe, wheresemantic similarity is preserved but pairwise geodesics arenot.3.3 Shape processingThe default setting in shape correspondence is matching twoshapes in isolation, which we call pairwise processing. Whenshapes come as part of a collection, one may want to processall shapes at the same time, which is likely to bring more consistency and accuracy to the results (Fig. 2). We refer to thissetting as collectionwise processing and list the alias termsas groupwise correspondence and multiple shape correspondence.3.4 Output densityShape correspondence methods aim to produce a mappingbetween some or all of the surface points of the two givenshapes. Points can be continuous or discretized to meshvertices. Continuous case, also referred to as sub-vertex resolution, uses barycentric coordinates of the enclosing triangleto define the match. If the output involves only some featured surface points, then we have a sparse correspondence,otherwise we have a dense one (Fig. 3). While sparse correspondence is quick and useful for initializing dense pipelinessuch as real-world scan registrations, dense correspondenceis required for globally smooth attribute transfer and shapemorphing applications.3.5 Solution approachShape correspondence solutions can be investigated underthree groups as follows.3.5.1 Registration-based solutionGiven two shapes, the registration-based scheme aligns themby either registering one shape to the other or registering both
Recent advances in shape correspondence1707Table 1 Shape correspondence methods classified according to the criteria of our workMethodCriteriaSimilarity levelDeformation typeShape processingOutput tric CollectionwiseDense[46,60] [70,87] [23] [101] [75] [102] [67] [66,96] [79,88] [89,103][41,45] [43,90] [99,112] [72] [57,74] [27,73] [39] [48] [59] [18,80] [4,5] [91,100] [15,58] [7,114][92] [40] [93] [47] [2,3] [6] [17,26] [86,113] [49,82] [10,19] [16,56] [95] [13] [31] [22,32] [8,116][97] [1,110] [36,50] [63] 123
1708Y. SahillioğluTable 1 continuedMethodCriteriaSimilarity levelDeformation typeShape processingOutput densityFullIsometricPairwiseSparse[55,109] [28,107] [33,62] [64] [30,111] Dense [21]Collectionwise [106]Non-isometric [81][69,76]Partial [84] [34,35] [77,78] [68,108] [9,65] [29] [20,24] [52] [94] [42] [37] in the Sparse column means that the method produces a sparse correspondence from parts to parts instead of points to points. Please see Table 2for continuationshapes to a common intermediate domain. One can see theformer operation as deformation and the latter as parameterization. Once registered, correspondence is derived from theproximity of the aligned shape elements.The alternative approach is to keep each shape as is andderive the correspondence directly from the pointwise and/orpairwise similarity of elements (Sect. 3.5.2). One can arguethat this approach is more popular than the registration-basedone because it avoids extra deformation and parameterizationprocessing power and errors. The argument is verified by thehigher number of checkmarks in the corresponding columnof Table 2.Deformation We give a generic framework to deform oneshape toward a data set, which would be the other shape inour case, while preserving its original geometric features.This demand is achieved by minimizing a combination ofdata and regularization energy terms:δi for vertex vi encapsulates local geometric informationaround vi by approximating mean curvature times the normal direction (Fig. 4a). This model tries the preserve originalgeometric features by minimizing the difference between theoriginal and the deformed Laplacian coordinates as the shapeis pulled toward the data points (Fig. 4b):E data (v) v c 2where c Rn 3 stores the data points to get close to, andE regularization (v) Lv Lv0 2(1)where v Rn 3 stores 3 elements per row for each of the nvertices, namely the x-, y-, and z-coordinates. In the mostbasic Laplacian deformation model, Laplacian coordinate123(3)where v0 Rn 3 stores the original cooridantes and L Rn n is the cotangent Laplacian matrix filled usingLi j E def (v) E data (v) γ E regularization (v)(2) wij j N (i) wi j 1 0vi and v j are neighbors,i j,(4)otherwise.Discussing the shortcomings of this basic model is beyondthe scope of this survey. We refer the reader to [85] for derivation and usage of more sophisticated deformation models,
Recent advances in shape correspondence1709Table 2 Complementing Table 1 with the remaining criteria for the same methodsMethodCriteria Cont’DSolution approachBased AutomaticYesNoFully FastSurf topologyMedSlowArbitrary [70,87] [23] [101] [75] [102] [67] [66,96] [79,88] [89,103] [41,45] [43,90] [99,112] [72] [57,74] [27,73] [39] [48] [18,80] [4,5] [15,58] [7,114] [92] [40] [47] [91,100][93] [59] [2,3] [6] [17,26] [86,113] [49,82] [10,19] [16,56] [95] [8,116] [97] [31] [1,110] [36,50][63] [13][22,32] SphereSemi 123
1710Y. SahillioğluTable 2 continuedMethodCriteria Cont’DSolution approachBased 5,109] [28,107] [81] [69,76] [106] Registration [33,62][64] [30,111] [21] [34,35] Surf topologyMed Sphere Arbitrary SlowSemi [84]NoFast [77,78] [68,108] [9,65] [29] [20,24] [52] [94] [42] [37] In order to save space, two methods are merged into one row if they share the same answers to both question here and in Table 1Fig. 2 Applying independent pairwise processings (a) lead to a worsetotal distortion than collectionwise processing does (b). If the distortionsof the black and red maps are .061 and .063, respectively, then theimplied green map at bottom becomes .069, hence a total distortionof .193 (a). If all shapes are considered at once, the red map slightlyincreases to .65, but the saving on the green map is larger, .060, hencea better total of .186 is achieved (b)and to the survey [44] for a thorough overview on the subject.Fig. 1 Fully (a, b) and partially (c, d) similar shape pairs. b, d Involvemild non-isometric deformations between the shapes due to somestretching, whereas the others have purely isometric deformations123Parameterization We give a generic framework to parameterize a shape embedded in 3D to a flat domain in 2D. Notethat a shape correspondence method performs this processfor two shapes and use a common intermediate domain thatis not necessarily flat (Sect. 4.5).
Recent advances in shape correspondence1711Wx bx and Wy by(5)where bx Rn 1 stores the x-coordinates of the boundarypositions at its top k rows when there are k boundary vertices. Remaining n k rows, which are set to 0, move theinterior vertices accordingly based on the multiplication ofthe bottom n k rows of W Rn n with x (Fig. 5d). They-coordinates are computed similarly.Fig. 3 Sparse (a, b) and dense (c) correspondences computed bySahillioğlu and Yemez [87] wi j wk i ikWi j 1 0vi , v j neighbs, vi interior,i j, vi interior,i j, vi boundary,otherwise.(6)Discussing the shortcomings of this basic model andextending it to non-disk topologies are beyond the scope ofthis survey. We refer to [53] for a comprehensive reading onthe subject.3.5.2 Similarity-based solutionFig. 4 Deformation in its most basic form using Laplacian coordinates(a). Data terms on two points at fingers under the Laplacian regularization perform the deformation (b)We now investigate the alternative scheme to the registrationbased solution, which we call the similarity-based solution.Here, the geometry of the input shapes is not altered inany manner. Instead, we compute geometric invariants, ordescriptors, under the appropriate deformation model. Suchdescriptors can be defined on vertices or between a pair ofvertices, the latter being more distinctive and effective. Acombination of both pointwise and pairwise terms leads toan energy function whose minimum gives the desired correspondence, or map, φ : S T :E(φ) w1 d S (vi ) d T (φ(vi )) vi w2 e S (vi , v j ) e T (φ(vi ), φ(v j )) (7)vi ,v jFig. 5 Parameterization in its most basic form using uniform (b) andcotangent (c) weights to flatten the 3D surface (a) to a disk. In d, thetoy 2D example at left is parameterized using the solution to the linearsystem at rightIn the most basic disk parameterization scheme, boundaryvertices of the surface (green ones in Fig. 5a) are first mappedto the boundary of a disk. Then, the remaining interior vertices are positioned in such a way that each one lands in thecenter (uniform—Fig. 5b) or weighted average (harmonic—Fig. 5c) of its immediate neighbors, the latter being morerespectful to the input geometry. We can solve two linearsystems for two coordinates separately to achieve this placement:where d S (.) and e S (., .) denote the descriptor values on avertex and between two vertices of the shape S, respectively.Descriptor choice depends on the deformation type, e.g., forisometric deformations a common choice for e is the geodesicdistance (Fig. 6a). Once Eq. 7 or a similar energy functionis ready, similarity-based solutions strive to minimize it viaefficient optimization tools. Similarity of real-valued functions over surfaces (Fig. 6b) has also been a trending topicsince 2012 (Sect. 4.2).3.5.3 Learning-based solutionRecent popularization of deep learning techniques hasaffected the shape correspondence field significantly. Wereport a work as learning-based if it learns some sort of prior123
1712Y. Sahillioğlu4 The methodsWe overview the methods in Tables 1 and 2 in the following subsections that go in chronological order from 2011 to2019. The prominent papers of each year, in our opinion, arediscussed with our criteria (Sect. 3) in mind.4.1 Year 2011Fig. 6 A bad correspondence composed of three blue matches generatesa high energy in Eq. 7 due to incompatible geodesics drawn as blackpaths (a). Matrix representation C of a functional map φ F (middle) withcolors proportional to matrix values. Colors on surfaces are based onfunction values (b)knowledge from a training set. The speed of such methods isdecided based on training and testing times. The corresponding value in Table 2 for a learning-based method is eithermedium or slow as the training time is naturally longer thanthe processing time of a non-learning-based method.3.6 AutomaticA method requiring user interaction, such as manual landmark matches, is labeled as semi-automatic, whereas allothers are considered as fully automatic.3.7 SpeedWe tag the methods as fast, medium, or slow according totheir reported worst-case time complexities. If this information is missing, then we approximately normalize theirreported execution times with a tagged method to make ourdecision. We also note that dense and sparse methods aretreated within their classes, i.e., a dense method is consideredfast even if it executes much slower than a sparse method.3.8 Surface topologySometimes correspondence methods require the input surfaces to be at particular topologies, most common of whichis genus-zero sphere topology. All other surfaces as well aspoint cloud inputs fall into the arbitrary topology category inTable 2.123Kim et al. [46] blend maps obtained by registering shapesto the extended complex plane by means of conformalMöbius transformations. Other than the topology restrictionand geodesic centroid approximations that degrade their performance for particular cases, the method produces reliablenon-isometric dense maps that are not necessarily onto, i.e.,some vertices are left unmatched. Other methods address theisometric correspondence problem by minimizing differentvariants of Eq. 7 in coarse-to-fine fashion [87] (Fig. 3) orwith an integer quadratic programming solver [23]. A coarsecorrespondence based on entropy-driven planned samples ismade dense in one shot using a propagation strategy thatrespects a geodesic consistency criterion [101]. It is, however, unclear how to connect the decrease in entropy with thestability of shape correspondence. Ovsjanikov et al. [71], onthe other hand, identify the samples that make the isometricshape correspondence problem easiest if their matches areknown.In the partial similarity setting, the correspondence-lessapproach in [75] optimizes the segment-wise similarityover the integration domains by relying on diffusion-basedlocal shape descriptors. It produces part correspondencesinstead of point correspondences. Knowledge-driven [102]also computes part correspondences where, unlike [75], theinput to their system is pre-segmented.Given a collection of shapes and maps between al
Important new developments have appeared since the most recent direct survey on shape correspondence published almost a . shape reconstruction, r,defor- . terize a shape em
advances in agronomy adv anat em advances in anatomy embryology and cell biology adv anat pa advances in anatomic pathology . advances in organometallic chemistry adv parasit advances in parasitology adv physics advances in physics adv physl e advances in physiology education adv poly t advances in polymer technology
records of to whom correspondence has been referred. Correspondence records (including originating correspondence and responses) are stored in NSW Treasury's information systems in accordance with NSW Treasury's Record Management Framework. Certain correspondence records (for example, correspondence received by the Minister or Members of
Advances in Aquatic Microbiology: 1·3, 1 g77.95 ··Look under DR 1 D5.A3 Advances in Carbohydrate Chemistry and Biochemistry: 24-37, 1g5g.ao ··Continues Advances in Carbohydrate Chemistry·· Look under DD321.A3 Advances in Carbohydrate Chemistry: 15·23, 1g60·6B ··Continued by Advances in Carbohydrate Chemistry and
advances in clinical cancer research, and identifies those that will have the greatest impact on patient care. This report, Clinical Cancer Advances 2008: Major Research Advances in Cancer Treatment, Screening, and Prevention, highlights 31 of the most significant advances over the past
: Show 3D Text.: Show 2D Text with a back shape.: Show 3D Text with a back shape.: Show a text hole in shape.: Show 3D Text in the border of shape. One Click add a object: Click the item to add a object quickly. Change Shape or Text Style: Double click the style icon can change node's shape or
Step 7 - Adding Shape # 2 Duplicate the shape from previous step by first selecting the arrow (A). While holding down the alt key click on the shape and drag it below the yellow rectangle. This will duplicate the shape. Now hold down the command key (apple) and drag the four points to transform your shape properly. Step 8 - Duplicating Shape #2
Folder 7. Correspondence: Greeting/Holiday/Thank You/Post Cards Folder 8. Correspondence: Kayo Cards Ltd., circa 1991-1992 Folder 9. Correspondence: Nickerson Research for Adidas commercial, 2004 Folder 10. Correspondence: Various Foreign Language Letters/cards Folder 11. Corresponde
QUALITY IN EDUCATION AND TRAINING AWARDS Trainee/Student Leader of the Year Aisha Gaido Adult Nursing BSc (Hons) Student, Anglia Ruskin University Nominated by Joe Laryea, Clinical Learning Environment Lead, Health Education East of England Aisha is a very keen and enthusiastic student nurse who goes out of her way to assist students both in practice and in the university. She has a very kind .
