A Survey on Non-rigid 3D Shape Analysis <s> SUMMARY AND PERSPECTIVES <s> We address the problem of automatic recognition of functional parts of man-made 3D shapes in the presence of significant geometric and topological variations. We observe that under such challenging circumstances, the context of a part within a 3D shape provides important cues for learning the semantics of shapes. We propose to model the context as structural relationships between shape parts and use them, in addition to part geometry, as cues for functionality recognition. We represent a 3D shape as a graph interconnecting parts that share some spatial relationships. We model the context of a shape part as walks in the graph. Similarity between shape parts can then be defined as the similarity between their contexts, which in turn can be efficiently computed using graph kernels. This formulation enables us to: (1) find part-wise semantic correspondences between 3D shapes in a nonsupervised manner and without relying on user-specified textual tags, and (2) design classifiers that learn in a supervised manner the functionality of the shape components. We specifically show that the performance of the proposed context-aware similarity measure in finding part-wise correspondences outperforms geometry-only-based techniques and that contextual analysis is effective in dealing with shapes exhibiting large geometric and topological variations. <s> BIB001 </s> A Survey on Non-rigid 3D Shape Analysis <s> SUMMARY AND PERSPECTIVES <s> As collections of 3D models continue to grow, reusing model parts allows generation of novel model variations. Naively swapping parts across models, however, leads to implausible results, especially when mixing parts across different model families. Hence, the user has to manually ensure that the final model remains functionally valid. We claim that certain symmetric functional arrangements (sFarr-s), which are special arrangements among symmetrically related substructures, bear close relation to object functions. Hence, we propose a purely geometric approach based on such substructures to match, replace, and position triplets of parts to create non-trivial, yet functionally plausible, model variations. We demonstrate that starting even from a small set of models such a simple geometric approach can produce a diverse set of non-trivial and plausible model variations. <s> BIB002 </s> A Survey on Non-rigid 3D Shape Analysis <s> SUMMARY AND PERSPECTIVES <s> In order to develop statistical methods for shapes with a tree-structure, we construct a shape space framework for tree-like shapes and study metrics on the shape space. This shape space has singularities, corresponding to topological transitions in the represented trees. We study two closely related metrics on the shape space, TED and QED. QED is a quotient Euclidean distance arising naturally from the shape space formulation, while TED is the classical tree edit distance. Using Gromov's metric geometry we gain new insight into the geometries defined by TED and QED. We show that the new metric QED has nice geometric properties which facilitate statistical analysis, such as existence and local uniqueness of geodesics and averages. TED, on the other hand, does not share the geometric advantages of QED, but has nice algorithmic properties. We provide a theoretical framework and experimental results on synthetic data trees as well as airway trees from pulmonary CT scans. This way, we effectively illustrate that our framework has both the theoretical and qualitative properties necessary to build a theory of statistical tree-shape analysis. <s> BIB003
We have reviewed in this chapter the fundamentals as well as the state-of-the-art methods for nonrigid 3D shape analysis. We have seen that there are three fundamentally inter-related problems, which are correspondence (registration), geodesic deformation, and statistical summarization of shapes that undergo elastic deformations. Thus, these problems are better solved jointly using the same metric that captures (and quantifies) physical deformations, which are bending and stretching. We have particularly seen three types of metrics, mainly (1) the Euclidean distance or L 2 metric in the space of shapes C f , (2) the pullback of elastic metrics, including the elastic metric in the space of shells, and (3) the L 2 metric in the space of Square-Root Normal Fields (SRNF). While metrics in the first class are easy to use and have lead to some of the major developments in statistical shape analysis including the active shape models as well as the morphable models, they are limited to 3D objects that do not undergo large bending and stretching. Moreover, they are not reparameterization invariant and thus the correspondence problem should be solved in a pre-processing step using a different approach and a different optimality criteria. The second class of methods capture the true deformations of shapes and thus can generate natural geodesics and shape summaries. They are, however, computationally very expensive; computing one geodesic may take hours in some cases since they require solving a complex optimization problem. In fact, only a few methods (e.g. M-reps and Lie bodies) have closed-form formulas for computing geodesics and geodesic distances. Other methods, compute them by solving expensive optimization problems. Square Root representations, on the other hand, are particularly promising since they map 3D shapes onto an Euclidean space where the L 2 metric is equivalent to the partial elastic metric in the preshape and shape spaces C f and S f . Thus geodesics become straight lines. One can then perform all the computations in the space of SRNFs using standard vector calculus and only map the results back to the space of surfaces for visualization purposes. Moreover, diffeomorphisms act by isometries on the elements of the SRNF space under the L 2 metric. Thus, one can solve jointly the elastic registration problem under the same metric. The main limitations of these methods is that the L 2 metric on the space of SRNFs is only equivalent to the partial elastic metric with fixed weights for the bending and stretching terms. The existence of such nice representation for arbitrary weights is in fact unknown and can be a promising direction for future research. Finally, despite the rich literature in this field, there are several fundamental problems and challenges that require further research. Below we summarize some of the open challenges that we believe require further investigation. Topological and structural variabilities. While a significant progress has been made in studying geometric variability (driven by the computer vision and medical imaging communities), analyzing structural variability of man-made 3D shapes, which is receiving a growing interest by the graphics community, is still at its infant stage. Structural variability is highly related to the semantics and functionality of shapes BIB001 . Methods that studied it (driven by the computer graphics community and motivated by the need to easily create 3D models and enrich collections), do not come with a concept of structure space and a metric for performing true statistics on structure. On the other hand, discrete and continuous representations (driven by the computer vision, medical and biological imaging communities) lead to well defined shape spaces and metrics. These methods, however, perform poorly on 3D shapes that are composed of multiply interacting components, e.g. subcortical structures in the brain. Multiply-interacting shapes. Objects are not isolated in nature. Their shape is often influenced by their surroundings and by objects with which they interact. Examples include anatomical surfaces, e.g. subcortical structures in human brains, or man-made objects whose shape is influenced by their surroundings and by the actions to which they are subject to. Graphics papers that explored structural variability in manmade 3D shapes capture some of these interactions. Extending these techniques to natural objects (e.g. subcortical structures) is an interesting direction of research to explore. We believe that developing a mathematical representation of the space of structures and capturing and modeling the way shapes of multiple objects co-vary are open challenges that require further investigation. Solving them will open perspectives for new applications in medical image analysis, biology and 3D modeling in computer graphics. Correspondence. Despite the large amount of research on this particular topic, correspondence between 3D shapes still remains an open challenging problem, particularly in the presence of large elastic, topological and structural variations. Methods where correspondence and analysis are solved jointly under the same metric provide promising results, but still fail when analyzing 3D shapes that are semantically or functionally similar but significantly differ in their geometry or structure. This problem will be simplified if semantics and functionality of shapes and their parts can be incorporated into the analysis. Recent works that relate structure to functionality BIB001 , BIB002 provide a step forward in this direction. However, the main challenge when dealing with man-made 3D objects comes from the fact that correspondences are not one-to-one and thus cannot be represented with diffeomorphisms or other nice mappings. Recent works on graph and tree-graph statistics BIB003 may provide part of the solution, although having a joint model that captures both geometric and structural variabilities remains an open problem.