Search

Object grasp planning is a challenging task. Recently, methods based on deep learning have made great progress in this area, but they are highly dependent on datasets, which means that they may encounter some difficulties when facing novel objects that are not available in the datasets. In this paper, a novel method is proposed to generate grasping candidate rectangles for object based on shape approximation, without datasets or shape priori of objects. Specifically, combining K-means and the minimum oriented bounding box algorithm for point sets, an adaptive K-means algorithm is applied for decomposing objects into multiple rectangles. The algorithm can independently select the number of K-means cores and automatically select the number of rectangles used to approximate the shape of the object. According to the parameters of each rectangle, a candidate grasping rectangle of the object is generated. In addition, using the Cornell grasping dataset, a LightGBM classifier is trained for the classification and evaluation of object candidate grasping rectangles. Experimental results show that our classification accuracy rate has reached 94.5% and the detection time is only 0.0003s. Among the candidate rectangles, the one with the highest score in the LightGBM model would be selected for real robot grasping. Finally, a multi-object grasping experiment conducted on a real robot platform shows that our algorithm can help the robot grasp new objects with an average success rate of 91.81%. [ABSTRACT FROM AUTHOR]

A new type of optical element that can focus a cylindrical wave to a point focus (or vice versa) is analytically described. Such waves are, for example, produced in a beamline where light is collimated in one direction and then doubly focused by a single optic. A classical example in X-ray optics is the collimated two-crystal monochromator, with toroidal mirror refocusing. The element here replaces the toroid, and in such a system provides completely aberration free, point-to-point imaging of rays from the on-axis source point. We present an analytic solution for the mirror shape in its laboratory coordinate system with zero slope at the centre, and approximate solutions, based on bending an oblique circular cone and a bent right circular cylinder, that may facilitate fabrication and metrology.

The structural design of 3D auxetic linkages is a burgeoning field in digital manufacturing. This article presents a novel algorithm for designing 3D auxetic linkage structures based on Kirigami principles to address existing limitations. The 3D input model is initially mapped to a 2D space using conformal mapping based on the BFF method. This is followed by 2D re-meshing using an equilateral triangle mesh. Subsequently, a 3D topological mesh of the auxetic linkage is calculated through inverse mapping based on directed area. We then introduce new basic rotating and non-rotating units, employing them as the initial structure of the 3D auxetic linkage in accordance with Kirigami techniques. Lastly, a deformation energy function is defined to optimize the shape of the rotating units. The vertex coordinates of the non-rotating units are updated according to the optimized positions of the rotating units, thereby generating an optimal 3D auxetic linkage structure. Experimental results validate the effectiveness and accuracy of our algorithm. Quantitative analyses of structural porosity and optimization accuracy, as well as comparisons with related works, indicate that our algorithm yields structures with smaller shape errors. • Extending Kirigami from 2D to 3D models with boundaries. • Designing of 3D auxetic linkage structures basing on rotating units and non-rotating units. • More complex 3D models with their 3D shapes preserved better. • Refining the shapes of rotating units to reduce the errors with deformation energy optimization. [ABSTRACT FROM AUTHOR]

• Shape of a rice particle can be simplified as an axi-symmetric ellipsoid. • The angularity factor can quantify the shape approximation of the MS models. • Accurate shape approximation does not always guarantee quality of the results. • Selection of the shape approximation scheme depends on the application. In this study experimental and numerical investigations on the mechanical and flow behavior of the multi-sphere (MS) rice particles with different degrees of shape approximation are conducted. This work aims to provide a better understanding of the adaptability of the degree of the shape approximation. The results indicated that rice particles can be approximated using the MS models with axi-symmetric ellipsoid shape. Furthermore, the angularity factor, AF , can be used to quantify the degree of shape approximation. As AF decreases, the degree of shape approximation increases. Finally, selection of the shape approximation scheme depends on the application of granular materials. Specifically, for the static and dynamic mechanical behavior of the single particle, the degree of shape approximation should not be strictly accurate, but should be appropriately rough. However, for the static and dynamic flow behavior of the particle assembly, the degree of shape approximation should be accurate. [ABSTRACT FROM AUTHOR]

Robotic grasping has always been a challenging task for both service and industrial robots. The ability of grasp planning for novel objects is necessary for a robot to autonomously perform grasps under unknown environments. In this work, we consider the task of grasp planning for a parallel gripper to grasp a novel object, given an RGB image and its corresponding depth image taken from a single view. In this paper, we show that this problem can be simplified by modeling a novel object as a set of simple shape primitives, such as ellipses. We adopt fuzzy Gaussian mixture models (GMMs) for novel objects' shape approximation. With the obtained GMM, we decompose the object into several ellipses, while each ellipse is corresponding to a grasping rectangle. After comparing the grasp quality among these rectangles, we will obtain the most proper part for a gripper to grasp. Extensive experiments on a real robotic platform demonstrate that our algorithm assists the robot to grasp a variety of novel objects with good grasp quality and computational efficiency. [ABSTRACT FROM AUTHOR]

Given a set S in Rn, a (δ,ε)-ball approximation of S is defined as a collection of balls that covers the morphological erosion of S (by a ball of radius ε) and remains inside the morphological dilation of S (by a ball of radius δ). We study the problem of computing a (δ,ε)-ball approximation when S is itself defined as a finite union of balls. This problem relates to geometric set cover problems but is however different in nature. It offers a new framework for reducing the size of a collection of balls while controlling both the inner and outer distance to the shape. We prove that computing a (δ,ε)-ball approximation of minimum cardinality is NP-complete for n=2. Along the way, we study the boundary of unions of disks and their erosion, for which we derive a computational description. [ABSTRACT FROM AUTHOR]

A depth image provides partial geometric information of a 3D scene, namely the shapes of physical objects as observed from a particular viewpoint. This information is important when synthesizing images of different virtual camera viewpoints via depth-image-based rendering (DIBR). It has been shown that depth images can be efficiently coded using contour-adaptive codecs that preserve edge sharpness, resulting in visually pleasing DIBR-synthesized images. However, contours are typically losslessly coded as side information, which is expensive if the object shapes are complex. In this paper, we pursue a new paradigm in depth image coding for color-plus-depth representation of a 3D scene: in a pre-processing step, we pro-actively simplify object shapes in a depth and color image pair to reduce depth coding cost, at a penalty of a slight increase in synthesized view distortion. Specifically, we first mathematically derive a distortion upper-bound proxy for 3DSwIM—a quality metric tailored for DIBR-synthesized images. This proxy reduces inter-dependency among pixel rows in a block to ease optimization. We then approximate object contours via a dynamic programming algorithm to optimally tradeoff coding the cost of contours using arithmetic edge coding with our proposed view synthesis distortion proxy. We modify the depth and color images according to the approximated object contours in an inter-view consistent manner. These are then coded, respectively, using a contour-adaptive image codec based on graph Fourier transform for edge preservation and High Efficiency Video Coding (HEVC) intra. Experimental results show that by maintaining sharp but simplified object contours during contour-adaptive coding, for the same visual quality of DIBR-synthesized virtual views, our proposal can reduce depth image coding rate by up to 22% in 3DSwIM and 42% in peak signal-to-noise ratio compared with alternative coding strategies, such as HEVC intra. [ABSTRACT FROM AUTHOR]

We present a method to produce a hierarchy of triangle meshes that can be used to blend different levels of detail in a smooth fashion. The algorithm produces a sequence of meshes 00, 01, 02, ..., 0n, where each mesh 0i can be transformed to mesh 0i+1 through a set of triangle-collapse operations. For each triangle, a function is generated that approximates the underlying surface in the area of the triangle, and this function serves as a basis for assigning a weight to the triangle in the ordering operation and for supplying the points to which the triangles are collapsed. The algorithm produces a limited number of intermediate meshes by selecting, at each step, a number of triangles that can be collapsed simultaneously. This technique allows us to view a triangulated surface model at varying levels of detail while insuring that the simplified mesh approximates the original surface well.

Approximation of free-form shape is essential in numerous engineering applications, particularly in automotive and aircraft industries. Commercial CAD software for the approximation of free-form shape is based almost exclusively on parametric polynomial and rational parametric polynomial. The parametric curve is defined by vector function of one independent variable R(u) = (x(u), y(u), z(u)), where 0≤u≤1. Bézier representation is one of the parametric functions, which is widely used in the approximating of free-form shape. Given a string of points with the assumption of sufficiently dense to characterise airfoil shape, it is desirable to approximate the shape with Bézier representation. The expectation is that the representation function is close to the shape within an acceptable working tolerance. In this paper, the aim is to explore the use of manual and automated methods for approximating section curve of airfoil with Bézier representation.

Many computer graphics applications use simpler yet faithful approximations of complex shapes to conduct reliably part of their computations. Some tasks, such as physical simulation, collision detection, occlusion queries or free-form deformation, require the simpler proxy to strictly enclose the input shape. While there are algorithms that can output such bounding proxies on simple input shapes, most of them fail at generating a proper coarse approximant on real-world complex shapes, which may contain multiple components and have a high genus. We advocate that, before reducing the number of primitives to describe a shape, one needs to regularize it while maintaining the strict enclosing property, to avoid any geometric aliasing that makes the decimation unreliable. Depending on the scale of the desired approximation, the topology of the shape itself may indeed have to be first simplified, to let the subsequent geometric optimization be free from topological locks. We propose a new bounding shape approximation algorithm which takes as input an arbitrary surface mesh, with potentially complex multi-component structures, and generates automatically a bounding proxy which is tightened on the input and can match even the coarsest levels of approximation. To sustain the nonlinear approximation process that may eventually abstract both geometry and topology, we propose to use an intermediate regularized representation in the form of a shape closing, computed in real time using a new fast morphological framework designed for efficient parallel execution. Once the desired level of approximation is reached in the shape closing, a coarse, tight and bounding polygonization of the proxy geometry is extracted using an adaptive meshing scheme. Our underlying representation is both geometry- and topology-adaptive and can be optionally controlled accurately by a user, through sizing and orientation fields, yielding an intuitive brush metaphor within an interactive proxy design environment. We provide extensive experiments on various kinds of input meshes and illustrate the potential applications of our method in scenarios that benefit greatly from coarse, tight bounding substitutes to the actual high resolution geometry of the original 3D model, including freeform deformation, physical simulation and level of detail generation for rendering. [ABSTRACT FROM AUTHOR]

Shape approximation algorithms aim at computing simple geometric descriptions of dense surface meshes. Many such algorithms are based on mesh decimation techniques, generating coarse triangulations while optimizing for a particular metric which models the distance to the original shape. This approximation scheme is very efficient when enough polygons are allowed for the simplified model. However, as coarser approximations are reached, the intrinsic piecewise linear point interpolation which defines the decimated geometry fails at capturing even simple structures. We claim that when reaching such extreme simplification levels, highly instrumental in shape analysis, the approximating representation should explicitly and progressively model the volumetric extent of the original shape. In this paper, we propose Sphere-Meshes, a new shape representation designed for extreme approximations and substituting a sphere interpolation for the classic point interpolation of surface meshes. From a technical point-of-view, we propose a new shape approximation algorithm, generating a sphere-mesh at a prescribed level of detail from a classical polygon mesh. We also introduce a new metric to guide this approximation, the Spherical Quadric Error Metric in R4, whose minimizer finds the sphere that best approximates a set of tangent planes in the input and which is sensitive to surface orientation, thus distinguishing naturally between the inside and the outside of an object. We evaluate the performance of our algorithm on a collection of models covering a wide range of topological and geometric structures and compare it against alternate methods. Lastly, we propose an application to deformation control where a sphere-mesh hierarchy is used as a convenient rig for altering the input shape interactively. [ABSTRACT FROM AUTHOR]

The profile-based features of a mechanical Computer aided design (CAD) system commonly have complicated shapes because of the guide curve, which is of free-form type. However, while considering interoperability between heterogeneous CAD systems, this kind of free-form guide curve makes it difficult to represent the corresponding feature shape in other CAD systems; for example, ship CAD systems usually use relatively simple shape primitives to represent objects. Thus, we propose a straightforward algorithm to represent profile-based features that is based on guide curve approximation using line and arcs segments. In addition, the solid alignment and filling operations are also provided to complete the entire process of solid model reconstruction. Furthermore, we apply this technique to a data exchange from a mechanical CAD system to a ship CAD system. Lastly, we use several test cases to demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Decomposing a 3D model into approximately convex components has gained more attention recently due to its ability to efficiently generate small decompositions with controllable concavity bounds. However, current methods are computationally expensive and require many user parameters. These parameters are usually unintuitive thus adding unnecessary obstacles in processing a large number of meshes with various types and shapes or meshes that are generated online within applications such as video games. In this paper, we investigate an approach that decomposes a mesh P based on the identification of convex ridges . Intuitively, convex ridges are the protruding parts of the mesh P . Our method, called CoRiSe , extracts nearly convex components of P by separating each convex ridge from all the other convex ridges through the new concept of residual concavity . CoRiSe takes a single user parameter: concavity tolerance which controls the maximum concavity of the final components, as input, along with other two fixed parameters for encoding the smoothness term of graph cut. We show that our method can generate comparable (sometimes noticeably better) segmentations in significant shorter time than the current state-of-art methods. Finally, we demonstrate applications of CoRiSe , including physically-based simulation, cage generation, model repair and mesh unfolding. [ABSTRACT FROM AUTHOR]

To take into account the variability of the medium through which the groundwater flow takes place, we presented the groundwater flow equation within a confined aquifer with prolate coordinates. The new equation is a perturbed singular equation. The perturbed parameters is introduced and can be used as accurately replicate the variability of the aquifer from one point to another. When the perturbed parameter tends to zero, we recover the Theis equation. We solved analytically and iteratively the new equation. We compared the obtained solution with experimental observed data together with existing solutions. The comparison shows that the modified equation predicts more accurately the physical problem than the existing model. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: The morphological skeleton transform (MST) is a leading morphological shape representation scheme. In the MST, a given shape is represented as the union of all the maximal disks contained in the shape. The concept of external skeleton points and external maximal disks has been used for shape description and characterization purposes. In this paper, we develop a generalized morphological skeleton transform that combines the concepts of internal and external maximal disks into a unified framework. In this framework, a shape is described in terms of disk components that need to be added as well as disk components that need to be removed. The procedures and formulae describing the extraction of the disk components and the reconstruction of the original shape from these components are developed. The correctness of the procedures and formulae is established. This new framework seems to provide a more powerful and more natural way of modeling the approximation and reconstruction of binary shapes using primitive shape components. [Copyright &y& Elsevier]

ABSTRACT Simulating a crowded scene like a busy shopping street requires tight packing of virtual characters. In such cases, collisions are likely to occur, and the choice in collision detection shape will influence how characters are allowed to intermingle. Full collision detection is too expensive for crowds, so simplifications are needed. The most common simplification, the fixed-width, pose-independent cylinder, does not allow intermingling of characters, as it will either cause too much empty space between characters or undetected penetrations. As a possible solution to this problem, we introduce the bounding cylinder hierarchy (BCH), a bounding volume hierarchy that uses vertical cylinders as bounding shapes. Because the BCH is a generalization of the single cylinder, we expect that this representation can be easily integrated with existing crowd simulation systems. We compare our BCH with commonly used collision shapes, namely the single cylinder and oriented bounding box tree, in terms of query time, construction time, and represented volume. To get an indication of possible crowd densities, we investigate how close characters can be before collision is detected and finally propose a critical maximum depth for the BCH. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Shape approximation algorithms aim at computing simple geometric descriptions of dense surface meshes. Many such algorithms are based on mesh decimation techniques, generating coarse triangulations while optimizing for a particular metric which models the distance to the original shape. This approximation scheme is very efficient when enough polygons are allowed for the simplified model. However, as coarser approximations are reached, the intrinsic piecewise linear point interpolation which defines the decimated geometry fails at capturing even simple structures. We claim that when reaching such extreme simplification levels, highly instrumental in shape analysis, the approximating representation should explicitly and progressively model the volumetric extent of the original shape. In this paper, we propose Sphere-Meshes, a new shape representation designed for extreme approximations and substituting a sphere interpolation for the classic point interpolation of surface meshes. From a technical point-of-view, we propose a new shape approximation algorithm, generating a sphere-mesh at a prescribed level of detail from a classical polygon mesh. We also introduce a new metric to guide this approximation, the Spherical Quadric Error Metric in R4, whose minimizer finds the sphere that best approximates a set of tangent planes in the input and which is sensitive to surface orientation, thus distinguishing naturally between the inside and the outside of an object. We evaluate the performance of our algorithm on a collection of models covering a wide range of topological and geometric structures and compare it against alternate methods. Lastly, we propose an application to deformation control where a sphere-mesh hierarchy is used as a convenient rig for altering the input shape interactively. [ABSTRACT FROM AUTHOR]

In this paper, we present a theoretical study of several shape approximation problems, called shape rectangularization ( SR), which arise in intensity-modulated radiation therapy (IMRT). Given a piecewise linear function f such that f( x)≥0 for any x∈ℝ, the SR problems seek an optimal set of constant window functions to approximate f under a certain error criterion, such that the sum of the resulting constant window functions equals (or well approximates) f. A constant window function W(⋅) is defined on an interval I such that W( x) is a fixed value h>0 for any x∈ I and is 0 otherwise. A constant window function can be viewed as a rectangle (or a block) geometrically, or as a vector with the consecutive a's property combinatorially. The SR problems find applications in setup time and beam-on time minimization and dose simplification of the IMRT treatment planning process. We show that the SR problems are APX-Hard, and thus we aim to develop theoretically efficient and provably good quality approximation SR algorithms. Our main contribution is to present algorithms for a key SR problem that achieve approximation ratios better than 2. For the general case, we give a $\frac{24}{13}$-approximation algorithm. For unimodal input curves, we give a $\frac{9}{7}$-approximation algorithm. We also consider other variants for which better approximation ratios are possible. We show that an important SR case that has been studied in medical literature can be formulated as a k-MST( k-minimum-spanning-tree) problem on a certain geometric graph G; based on a set of geometric observations and a non-trivial dynamic programming scheme, we are able to compute an optimal k-MST in G efficiently. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a method of shape chartification suitable for surface approximation. The innovation of this approach lies on the definition of an iterative refinement of the shape into a set of patches that are automatically tiled and used to approximate the original shape up to a prescribed error. The coding of the patches is supported by the Reeb graph and contains the rules to properly tile, stitch them, and reconstruct the original shape while preserving its topology, using a technique which is also exploited for reconstructing an object from non-planar contours. The method is geometry-aware by definition, as the nodes of the Reeb graph are representative of the main shape features, which belong to the approximated shape already at the initial iteration steps. The points of the reconstructed shape belong to the original surface, their total number is highly reduced, and the original connectivity is replaced by a set of patches that preserves the global topology of the input shape. [Copyright &y& Elsevier]

Abstract: Clothing computer design systems include three integrated parts: garment pattern design in 2D/3D, virtual try-on and realistic clothing simulation. Some important results have been obtained in pattern design and clothing simulation since the 1980s. However, in the area of virtual try-on, only limited methods have been proposed which are applicable to some defined garment styles or under restrictive sewing assumptions. This paper presents a series of new techniques from virtually sewing up complex garment patterns on human models to visualizing design effects through physical-based real-time simulation. We first employ an hierarchy of ellipsoids to approximate human models in which the bounding ellipsoids are optimized recursively. We also present a new scheme for including contact friction and resolving collisions. Four types of user interactive operation are introduced to manipulate cloth patterns for pre-positioning, virtual sewing and later obtaining cloth simulation. In the cloth simulation, we propose a simplified cloth dynamic model and an integration scheme to realize a high quality real-time cloth simulation. We demonstrate the robustness of our proposed systems by complex garment style virtual try-on and cloth simulation. [Copyright &y& Elsevier]

Abstract: The topological complexity of polygonal meshes has a large impact on the performance of various geometric processing algorithms, such as rendering and collision detection algorithms. Several approaches for simplifying topology have been discussed in the literature. These methods operate locally on models, which makes their effect on the topology hard to predict and analyze. Most existing methods tend to exhibit several disturbing artifacts, such as shrinking of the input and splitting of its components. We propose a novel top-down approach for topology simplification that avoids most problems that are common in existing methods. We start with a simple, genus-zero mesh that bounds the input and gradually introduce topologic features by a series of carving operations. This process yields a multiresolution stream of meshes with increasing topologic level of detail. We further present a carving algorithm that is based on constrained Delaunay tetrahedralization. The algorithm first constructs the tetrahedral mesh of the complement of the input with respect to its convex hull. It then proceeds to eliminate tetrahedra in a prioritized manner. We present quality results for two families of meshes that are difficult to simplify by all existing methods known to us: topologically complex meshes and highly clustered meshes. [Copyright &y& Elsevier]

• Mathematical formalization of 2D shape approximation by discrete assembly systems. • Computational complexity analysis of associated shape approximation problems. • Algorithmic framework combining shape sampling and mixed-integer linear programming. • Practical application: freeform contour approximation with the Zometool system. • Numerical experiments show: high-quality solutions can be obtained in reasonable time. We consider the problem of approximating a two-dimensional shape contour (or curve segment) using discrete assembly systems, which allow to build geometric structures based on limited sets of node and edge types subject to edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP -hard, and remains intractable even for very simple setups. We then devise an algorithmic framework that combines shape sampling with exact cardinality minimization to obtain good approximations using few components. As a particular application and showcase example, we discuss approximating shape contours using the classical Zometool construction kit and provide promising computational results, demonstrating that our algorithm is capable of obtaining good shape representations within reasonable time, in spite of the problem's general intractability. We conclude the paper with an outlook on possible extensions of the developed methodology, in particular regarding 3D shape approximation tasks. [ABSTRACT FROM AUTHOR]

Abstract: Given a smooth compact codimension one submanifold S of and a compact approximation K of S, we prove that it is possible to reconstruct S and to approximate the medial axis of S with topological guarantees using unions of balls centered on K. We consider two notions of noisy-approximation that generalize sampling conditions introduced by Amenta et al. and Dey et al. The first one generalizes uniform sampling based on the minimum value of the local feature size. The second one generalizes non-uniform sampling based on the local feature size function of S. The density and noise of the approximation are bounded by a constant times the local feature size function. This constant does not depend on the surface S. Our results are based upon critical point theory for distance functions. For the two approximation conditions, we prove that the connected components of the boundary of unions of balls centered on K are isotopic to S. We consider using both balls of uniform radius and also balls whose radii vary with the local level of detail of the manifold. For the first approximation condition, we prove that a subset (known as the λ-medial axis) of the medial axis of is homotopy equivalent to the medial axis of S. Our results generalize to smooth compact submanifolds S of of any codimension. [Copyright &y& Elsevier]

Abstract: When designing curves on surfaces the need arises to approximate a given noisy target shape by a smooth fitting shape. We discuss the problem of fitting a -spline curve to a point cloud by squared distance minimization in the case that both the point cloud and the fitting curve are constrained to lie on a smooth manifold. The on-manifold constraint is included by using the first fundamental form of the surface for squared distance computations between the point cloud and the fitting curve. For the solution we employ a constrained optimization algorithm that allows us to include further constraints such as one-sided fitting or surface regions that have to be avoided by the fitting curve. We illustrate the effectiveness of our algorithm by means of several examples showing different applications. [Copyright &y& Elsevier]

One problem with several leading morphological shape representation algorithms is the heavy overlapping among the representative disks of the same size. A shape component formed by grouping connected disk centers may use many heavily overlapping disks to represent a simple shape part. Sometimes, these representative disks form complicated structures. A generalized skeleton transform was recently introduced which allows a shape to be represented as a collection of modestly overlapped octagonal shape parts. However, the generalized skeleton transform needs to be applied many times. Furthermore, an octagonal component is not easily matched up with another octagonal component. In this paper, we describe a octagon-fitting algorithm which identifies a special maximal octagon for each image point in a given shape. This transform leads to the development of two new shape decomposition algorithms. These algorithms are more efficient to implement; the octagon-fitting algorithm only needs to be applied once. The components generated are better characterized mathematically. The disk components used in the second decomposition algorithm are more primitive than octagons and easily matched up with other disk components from another shape. The experiments show that the new decomposition algorithms produce as efficient representations as the old algorithm for both exact and approximate cases. A simple shape-matching algorithm using disk components is also demonstrated. [ABSTRACT FROM AUTHOR]

Abstract: We discuss how to map simply connected digital surfaces to the unit sphere using discrete harmonic functions. This technique is well known for constructing parametrizations of surfaces onto simpler domains. A common problem is the creation of dense clusters of vertices, which leads to numerical instability of methods operating on this mapping. By an explicit calculation, we quantify the cluster density for a simple model example. This example shows that distances between mapped vertices can decrease exponentially in regions on the sphere. By numerical examples, we show that severe clustering often occurs for natural objects. A computationally inexpensive algorithm, based on a bijective transformation of the unit sphere, is suggested for post-processing of clusters. Experiments indicate that this algorithm often improves the mapping such that convergence of a non-linear optimization program is achieved. The program aims at optimizing the parameterization, making it useful for global shape analysis. Examples of approximations in terms of spherical harmonics functions are presented. [Copyright &y& Elsevier]

Rationale and objectives: Surgical planning now routinely uses both two-dimensional (2D) and three-dimensional (3D) models that integrate data from multiple imaging modalities, each highlighting one or more aspects of morphology or function. We performed a preliminary evaluation of the use of spherical harmonics (SH) in approximating the 3D shape and estimating the volume of brain tumors of varying characteristics. Materials and methods: Magnetic resonance (MR) images from five patients with brain tumors were selected randomly from our MR-guided neurosurgical practice. Standardized mean square reconstruction errors (SMSRE) by tumor volume were measured. Validation metrics for comparing performances of the SH method against segmented contours (SC) were the dice similarity coefficient (DSC) and standardized Euclidean distance (SED) measure. Results: Tumor volume range was 22413–85189 mm3, and range of number of vertices in triangulated models was 3674–6544. At SH approximations with degree of at least 30, SMSRE were within 1.66 × 10–5 mm−1. Summary measures yielded a DSC range of 0.89–0.99 (pooled median, 0.97 and significantly >0.7; P < .001) and an SED range of 0.0002–0.0028 (pooled median, 0.0005). Conclusion: 3D shapes of tumors may be approximated by using SH for neurosurgical applications. [Copyright &y& Elsevier]

We introduce a new class of shape approximation techniques for irregular triangular meshes. Our method approximates the geometry of the mesh using a linear combination of a small number of basis vectors. The basis vectors are functions of the mesh connectivity and of the mesh indices of a number of anchor vertices. There is a fundamental difference between the bases generated by our method and those generated by geometry-oblivious methods, such as Laplacian-based spectral methods. In the latter methods, the basis vectors are functions of the connectivity alone. The basis vectors of our method, in contrast, are geometry-aware since they depend on both the connectivity and on a binary tagging of vertices that are "geometrically important" in the given mesh (e.g., extrema). We show that, by defining the basis vectors to be the solutions of certain least-squares problems, the reconstruction problem reduces to solving a single sparse linear least-squares problem. We also show that this problem can be solved quickly using a state-of- the-art sparse-matrix factorization algorithm. We show how to select the anchor vertices to define a compact effective basis from which an approximated shape can be reconstructed. Furthermore, we develop an incremental update of the factorization of the least-squares system. This allows a progressive scheme where an initial approximation is incrementally refined by a stream of anchor points. We show that the incremental update and solving the factored system are fast enough to allow an online refinement of the mesh geometry. [ABSTRACT FROM AUTHOR]

Pottmann et al. propose an iterative optimization scheme for approximating a target curve with a B-spline curve based on square distance minimization, or SDM. The main advantage of SDM is that it does not need a parameterization of data points on the target curve. Starting with an initial B-spline curve, this scheme makes an active B-spline curve converge faster towards the target curve and produces a better approximating B-spline curve than existing methods relying on data point parameterization. However, SDM is sensitive to the initial B-spline curve due to its local nature of optimization. To address this, we integrate SDM with procedures for automatically adjusting both the number and locations of the control points of the active spline curve. This leads to a method that is more robust and applicable than SDM used alone. Furthermore, it is observed that the most time consuming part of SDM is the repeated computation of the foot-point on the target curve of a sample point on the active B-spline curve. In our implementation, we speed up the foot-point computation by pre-computing the distance field of the target curve using the Fast Marching Method. Experimental examples are presented to demonstrate the effectiveness of our method. Problems for further research are discussed. [Copyright &y& Elsevier]

A common problem shared by several leading morphological shape representation algorithms is that there is much overlapping among the representative disks of the same size. A shape component represented by a group of connected disk centers sometimes uses many heavily overlapping representative disks to represent a relatively simple shape part. A shape component may also contain a large number of representative disks that form a complicated structure. In this paper, we introduce a generalized discrete morphological skeleton transform that uses eight structuring elements to generate skeleton subsets so that no two skeletal points from the same skeleton subset will be adjacent to each other. Each skeletal point will represent a shape part that is in general an octagon with four pairs of parallel opposing sides. The number of representative points needed to represent a given shape is significantly lower than that in the standard skeleton transform. A collection of shape components needed to build a structural representation is easily derived from the generalized skeleton transform. Each shape component covers a significant area of the given shape and severe overlapping is avoided. The given shape can also be accurately approximated using a small number of shape components. [ABSTRACT FROM AUTHOR]