Part‐type Segmentation of Articulated Voxel‐Shapes using the Junction Rule

We present a part‐type segmentation method for articulated voxel‐shapes based on curve skeletons. Shapes are considered to consist of several simpler, intersecting shapes. Our method is based on the junction rule: the observation that two intersecting shapes generate an additional junction in their joined curve‐skeleton near the place of intersection. For each curve‐skeleton point, we construct a piecewise‐geodesic loop on the shape surface. Starting from the junctions, we search along the curve skeleton for points whose associated loops make for suitable part cuts. The segmentations are robust to noise and discretization artifacts, because the curve skeletonization incorporates a single user‐parameter to filter spurious curve‐skeleton branches. Furthermore, segment borders are smooth and minimally twisting by construction. We demonstrate our method on several real‐world examples and compare it to existing part‐type segmentation methods.     

3D Skeletons: A State‐of‐the‐Art Report

Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.     

Hierarchical part-type segmentation using voxel-based curve skeletons

We present an effective framework for segmenting 3D shapes into meaningful components using the curve skeleton. Our algorithm identifies a number of critical points on the efficiently computed curve skeleton, either fully automatically as the junctions of the curve skeleton, or based on user input. We use these points to construct a partitioning of the object surface using geodesics. Because the segmentation is based on the curve skeleton, it intrinsically reflects the shape symmetry and articulation, and can handle shapes with tunnels. We describe a voxel-based implementation of our method which is robust and noise resistant, able to handle shapes of complex articulation and topology, produces smooth segment borders, and delivers hierarchical level-of-detail segmentations. We demonstrate the framework on various real-world 3D shapes. Additionally, we discuss the use of both curve and surface skeletons to produce part-type and patch-type, respectively, segmentations of 3D shapes.     

A level-set approach for the metamorphosis of solid models

We present a new approach to 3D shape metamorphosis. We express the interpolation of two shapes as a process where one shape deforms to maximize its similarity with another shape. The process incrementally optimizes an objective function while deforming an implicit surface model. We represent the deformable surface as a level set (iso-surface) of a densely sampled scalar function of three dimensions. Such level-set models have been shown to mimic conventional parametric deformable surface models by encoding surface movements as changes in the grayscale values of a volume data set. Thus, a well-founded mathematical structure leads to a set of procedures that describes how voxel values can be manipulated to create deformations that are represented as a sequence of volumes. The result is a 3D morphing method that offers several advantages over previous methods, including minimal need for user input, no model parameterization, flexible topology, and subvoxel accuracy     

Multiview human pose estimation with unconstrained motions

We present a system for human pose estimation by using a single frame and without making assumptions on temporal coherence. The system uses 3D voxel data reconstructed from multiple synchronized video streams as input, and computes, for each frame, a skeleton model which best fits the body pose. This system adopts a hierarchical approach where the head and torso locations are found first based on template fitting with their specific shapes and dimensions. It is followed by a limb detection procedure that estimates the pose parameters of four limbs. However, a problem generally faced with skeleton models is the means to find adequate measurements to fit the model. In this paper, voxel data, together with two novel local shape features, are used for this purpose. Experiments show that this system is robust to several perturbations associated with the input data, such as voxel reconstruction errors and complex poses with self-contact, and also allows unconstrained motions, such as fast or unpredictable movements.     

Convolution surfaces based on polygons for infinite and compact support kernels

We provide formulae to create 3D smooth shapes fleshing out a skeleton made of line segments and planar polygons. The boundary of the shape is a level set of the convolution function obtained by integration along the skeleton. The convolution function for a complex skeleton is thus the sum of the convolution functions for the basic elements of the skeleton. Providing formulae for the convolution of a polygon is the main contribution of the present paper. We improve on previous results in several ways. First we do not require the prior triangulation of the polygon. Then, we obtain formulae for families of kernels, either with infinite or compact supports. Last, but not least, in the case of compact support kernels, the geometric computations needed are restricted to intersections of spheres with line segments.     

Robust Structure‐Based Shape Correspondence

We present a robust method to find region‐level correspondences between shapes, which are invariant to changes in geometry and applicable across multiple shape representations. We generate simplified shape graphs by jointly decomposing the shapes, and devise an adapted graph‐matching technique, from which we infer correspondences between shape regions. The simplified shape graphs are designed to primarily capture the overall structure of the shapes, without reflecting precise information about the geometry of each region, which enables us to find correspondences between shapes that might have significant geometric differences. Moreover, due to the special care we take to ensure the robustness of each part of our pipeline, our method can find correspondences between shapes with different representations, such as triangular meshes and point clouds. We demonstrate that the region‐wise matching that we obtain can be used to find correspondences between feature points, reveal the intrinsic self‐similarities of each shape and even construct point‐to‐point maps across shapes. Our method is both time and space efficient, leading to a pipeline that is significantly faster than comparable approaches. We demonstrate the performance of our approach through an extensive quantitative and qualitative evaluation on several benchmarks where we achieve comparable or superior performance to existing methods.     

Snake terrestrial locomotion synthesis in 3D virtual environments

We present a method for a 3D snake model construction and terrestrial snake locomotion synthesis in 3D virtual environments using image sequences. The snake skeleton is extracted and partitioned into equal segments using a new iterative algorithm for solving the equipartition problem. This method is applied to 3D model construction and at the motion analysis stage. Concerning the snake motion, the snake orientation is controlled by a path planning method. An animation synthesis algorithm, based on a physical motion model and tracking data from image sequences, describes the snake’s velocity and skeleton shape transitions. Moreover, the proposed motion planning algorithm allows a large number of skeleton shapes, providing a general method for aperiodic motion sequences synthesis in any motion graph. Finally, the snake locomotion is adapted to the 3D local ground, while its behavior can be easily controlled by the model parameters yielding the appropriate realistic animations.     

Computing multiscale curve and surface skeletons of genus 0 shapes using a global importance measure

We present a practical algorithm for computing robust, multiscale curve and surface skeletons of 3D objects. Based on a model which follows an advection principle, we assign to each point on the skeleton a part of the object surface, called the collapse. The size of the collapse is used as a uniform importance measure for the curve and surface skeleton, so that both can be simplified by imposing a single threshold on this intuitive measure. The simplified skeletons are connected by default, without special precautions, due to the monotonicity of the importance measure. The skeletons possess additional desirable properties: They are centered, robust to noise, hierarchical, and provide a natural skeleton-to-boundary mapping. We present a voxel-based algorithm that is straightforward to implement and simple to use. We illustrate our method on several realistic 3D objects.     

Skeleton‐Intrinsic Symmetrization of Shapes

Enhancing the self‐symmetry of a shape is of fundamental aesthetic virtue. In this paper, we are interested in recovering the aesthetics of intrinsic reflection symmetries, where an asymmetric shape is symmetrized while keeping its general pose and perceived dynamics. The key challenge to intrinsic symmetrization is that the input shape has only approximate reflection symmetries, possibly far from perfect. The main premise of our work is that curve skeletons provide a concise and effective shape abstraction for analyzing approximate intrinsic symmetries as well as symmetrization. By measuring intrinsic distances over a curve skeleton for symmetry analysis, symmetrizing the skeleton, and then propagating the symmetrization from skeleton to shape, our approach to shape symmetrization is skeleton‐intrinsic. Specifically, given an input shape and an extracted curve skeleton, we introduce the notion of a backbone as the path in the skeleton graph about which a self‐matching of the input shape is optimal. We define an objective function for the reflective self‐matching and develop an algorithm based on genetic programming to solve the global search problem for the backbone. The extracted backbone then guides the symmetrization of the skeleton, which in turn, guides the symmetrization of the whole shape. We show numerous intrinsic symmetrization results of hand drawn sketches and artist‐modeled or reconstructed 3D shapes, as well as several applications of skeleton‐intrinsic symmetrization of shapes.     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

Skeleton‐driven Adaptive Hexahedral Meshing of Tubular Shapes

We propose a novel method for the automatic generation of structured hexahedral meshes of articulated 3D shapes. We recast the complex problem of generating the connectivity of a hexahedral mesh of a general shape into the simpler problem of generating the connectivity of a tubular structure derived from its curve‐skeleton. We also provide volumetric subdivision schemes to nicely adapt the topology of the mesh to the local thickness of tubes, while regularizing per‐element size. Our method is fast, one‐click, easy to reproduce, and it generates structured meshes that better align to the branching structure of the input shape if compared to previous methods for hexa mesh generation.     

B‐Mesh: A Modeling System for Base Meshes of 3D Articulated Shapes

This paper presents a novel modeling system, called B‐Mesh, for generating base meshes of 3D articulated shapes. The user only needs to draw a one‐dimensional skeleton and to specify key balls at the skeletal nodes. The system then automatically generates a quad dominant initial mesh. Further subdivision and evolution are performed to refine the initial mesh and generate a quad mesh which has good edge flow along the skeleton directions. The user can also modify and manipulate the shape by editing the skeleton and the key balls and can easily compose new shapes by cutting and pasting existing models in our system. The mesh models generated in our system greatly benefit the sculpting operators for sculpting modeling and skeleton‐based animation.     

Data‐Driven Sparse Priors of 3D Shapes

We present a sparse optimization framework for extracting sparse shape priors from a collection of 3D models. Shape priors are defined as point‐set neighborhoods sampled from shape surfaces which convey important information encompassing normals and local shape characterization. A 3D shape model can be considered to be formed with a set of 3D local shape priors, while most of them are likely to have similar geometry. Our key observation is that the local priors extracted from a family of 3D shapes lie in a very low‐dimensional manifold. Consequently, a compact and informative subset of priors can be learned to efficiently encode all shapes of the same family. A comprehensive library of local shape priors is first built with the given collection of 3D models of the same family. We then formulate a global, sparse optimization problem which enforces selecting representative priors while minimizing the reconstruction error. To solve the optimization problem, we design an efficient solver based on the Augmented Lagrangian Multipliers method (ALM). Extensive experiments exhibit the power of our data‐driven sparse priors in elegantly solving several high‐level shape analysis applications and geometry processing tasks, such as shape retrieval, style analysis and symmetry detection.     

A Pruning Algorithm for Stable Voronoi Skeletons

We present a skeleton computation algorithm for binary image shape which is stable and efficient. The algorithm follows these steps: first the shape boundary curves are subsampled, then the Voronoi Skeleton is computed from the resulting reduced boundary set of points, and finally, a?novel two stage pruning procedure is applied to obtain a?simplified skeleton. The first stage removes skeleton edges non fully included in the shape. The second stage applies an enhanced variation of the Discrete Curve Evolution (DCE) for Voronoi skeletons. We obtain improved skeleton stability, complexity reduction and noise robustness. Pruning computing time efficiency is improved thanks to some properties of Voronoi skeletons. Entire skeleton edges can be removed or retained on the basis of conditions tested on the edge endpoints. Pattern recognition experiments and skeleton stability experiments of the algorithm outperform previous approaches in the literature.     

Prototype Modeling from Sketched Silhouettes based on Convolution Surfaces

This paper presents a hybrid method for creating three‐dimensional shapes by sketching silhouette curves. Given a silhouette curve, we approximate its medial axis as a set of line segments, and convolve a linearly weighted kernel along each segment. By summing the fields of all segments, an analytical convolution surface is obtained. The resulting generic shape has circular cross‐section, but can be conveniently modified via sketched profile or shape parameters of a spatial transform. New components can be similarly designed by sketching on different projection planes. The convolution surface model lends itself to smooth merging between the overlapping components. Our method overcomes several limitations of previous sketched‐based systems, including designing objects of arbitrary genus, objects with semi‐sharp features, and the ability to easily generate variants of shapes.     

Projective Feature Learning for 3D Shapes with Multi‐View Depth Images

Feature learning for 3D shapes is challenging due to the lack of natural paramterization for 3D surface models. We adopt the multi‐view depth image representation and propose Multi‐View Deep Extreme Learning Machine (MVD‐ELM) to achieve fast and quality projective feature learning for 3D shapes. In contrast to existing multi‐view learning approaches, our method ensures the feature maps learned for different views are mutually dependent via shared weights and in each layer, their unprojections together form a valid 3D reconstruction of the input 3D shape through using normalized convolution kernels. These lead to a more accurate 3D feature learning as shown by the encouraging results in several applications. Moreover, the 3D reconstruction property enables clear visualization of the learned features, which further demonstrates the meaningfulness of our feature learning.