We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.
Exact medial axis computation is possible only for simple or special shapes, such as polyhedra @cite_25 @cite_17 . For free-form shapes, medial axis approximations are widely used in practice. There are several main approaches to computing the medial axis approximation: pixel or voxel-based methods that compute the medial axis using a thinning operation @cite_26 ; methods based on distance transform @cite_21 @cite_13 @cite_8 @cite_28 , often performed on a regular or adaptive grid; the divide-and-conquer methods @cite_5 , performed on spline curve boundaries; the tracing approaches @cite_3 , by tracing along the shape boundary or the seam curves; and the Voronoi diagram (VD) based methods @cite_0 @cite_23 @cite_9 @cite_29 @cite_15 .
@cite_26 @cite_8 @cite_28 @cite_9 @cite_21 @cite_29 @cite_3 @cite_0 @cite_23 @cite_5 @cite_15 @cite_13 @cite_25 @cite_17
2158008371 2024335283 2020065037 2013991211 2071657752 2116251909 2660405673 2029041800 2008425943 2141835663 1967930428 1977276706 1974675819
A comprehensive survey of thinning methodologies is presented. A wide range of thinning algorithms, including iterative deletion of pixels and nonpixel-based methods, is covered. Skeletonization algorithms based on medial axis and other distance transforms are not considered. An overview of the iterative thinning process and the pixel-deletion criteria needed to preserve the connectivity of the image pattern is given first. Thinning algorithms are then considered in terms of these criteria and their modes of operation. Nonpixel-based methods that usually produce a center line of the pattern directly in one pass without examining all the individual pixels are discussed. The algorithms are considered in great detail and scope, and the relationships among them are explored. > The medial axis transform (MAT) of a shape, better known as its skeleton, is frequently used in shape analysis and related areas. In this paper a new approach for determining the skeleton of an object is presented. The boundary is segmented at points of maximal positive curvature and a distance map from each of the segments is calculated. The skeleton is then located by applying simple rules to the zero sets of distance map differences. A framework is proposed for numerical approximation of distance maps that is consistent with the continuous case and hence does not suffer from digitization bias due to metrication errors of the implementation on the grid. Subpixel accuracy in distance map calculation is obtained by using gray-level information along the boundary of the shape in the numerical scheme. The accuracy of the resulting efficient skeletonization algorithm is demonstrated by several examples. The power crust is a construction which takes a sample of points from the surface of a three-dimensional object and produces a surface mesh and an approximate medial axis. The approach is to first approximate the medial axis transform (MAT) of the object. We then use an inverse transform to produce the surface representation from the MAT. This idea leads to a simple algorithm with theoretical guarantees comparable to those of other surface reconstruction and medial axis approximation algorithms. It also comes with a guarantee that does not depend in any way on the quality of the input point sample. Any input gives an output surface which is the watertight' boundary of a three-dimensional polyhedral solid: the solid described by the approximate MAT. This unconditional guarantee makes the algorithm quite robust and eliminates the polygonalization, hole-filling or manifold extraction post-processing steps required in previous surface reconstruction algorithms. In this paper, we use the theory to develop a power crust implementation which is indeed robust for realistic and even difficult samples. We describe the careful design of a key subroutine which labels parts of the MAT as inside or outside of the object, easy in theory but non-trivial in practice. We find that we can handle areas in which the input sampling is scanty or noisy by simply discarding the unreliable parts of the MAT approximation. We demonstrate good empirical results on inputs including models with sharp corners, sparse and unevenly distributed point samples, holes, and noise, both natural and synthetic. We also demonstrate some simple extensions: intentionally leaving holes where there is no data, producing approximate offset surfaces, and simplifying the approximate MAT in a principled way to preserve stable features. Skeletons provide a synthetic and thin representation of objects. Therefore, they are useful for shape description. Recent papers have proposed to approximate the skeleton of continuous shapes using the Voronoi graph of boundary points. An original formulation is presented here, using the notion of polyballs (we call polyball any finite union of balls). A preliminary work shows that their skeletons consist of simple components (line segments in 2D and polygons in 3D). An efficient method for simplifying 3D continuous skeletons is also presented. The originality of our approach consists in simplifying the shape without modifying its topology and in including these modifications on the skeleton. Depending on the desired result, we propose two strategies which lead to either surfacical skeletons or wireframe skeletons. Two angular criteria are proposed that allow us to build a size-invariant hierarchy of simplified skeletons. The paper describes an algorithm for generating an approximation of the medial axis transform (MAT) for planar objects with free form boundaries. The algorithm generates the MAT by a tracing technique that marches along the object boundary rather than the bisectors of the boundary entities. The level of approximation is controlled by the choice of the step size in the tracing procedure. Criteria based on distance and local curvature of boundary entities are used to identify the junction or branch points and the search for these branch points is more efficient than while tracing the bisectors. The algorithm works for multiply connected objects as well. Results of implementation are provided. We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on a local feature size function, the output is topologically valid and convergent (both pointwise and in surface normals) to the original surface. We briefly describe an implementation of the algorithm and show example outputs. We present a simple, efficient, and stable method for computing-with any desired precision-the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm. We present a new algorithm for simplifying the shape of 3D objects by manipulating their medial axis transform (MAT). From an unorganized set of boundary points, our algorithm computes the MAT, decomposes the axis into parts, then selectively removes a subset of these parts in order to reduce the complexity of the overall shape. The result is simplified MAT that can be used for a variety of shape operations. In addition, a polygonal surface of the resulting shape can be directly generated from the filtered MAT using a robust surface reconstruction method. The algorithm presented is shown to have a number of advantages over other existing approaches. Abstract We present a fast algorithm for preserving the total volume of a solid undergoing free-form deformation using level-of-detail representations. Given the boundary representation of a solid and user-specified deformation, the algorithm computes the new node positions of the deformation lattice, while minimizing the elastic energy subject to the volume-preserving criterion. During each iteration, a non-linear optimizer computes the volume deviation and its derivatives based on a triangular approximation, which requires a finely tessellated mesh to achieve the desired accuracy. To reduce the computational cost, we exploit the multi-resolution representations of the boundary surfaces to greatly accelerate the performance of the non-linear optimizer. This technique also provides interactive response by progressively refining the solution. Furthermore, it is generally applicable to lattice-based free-form deformation and its variants. Our implementation has been applied to several complex solids. We have been able to achieve an order of magnitude performance improvement over the conventional methods. We present an accurate algorithm to compute the internal Voronoi diagram and medial axis of a 3-D polyhedron. It uses exact arithmetic and exact representations for accurate computation of the medial axis. The algorithm works by recursively finding neighboring junctions along the seam curves. To speed up the computation, we have designed specialized algorithms for fast computation with algebraic curves and surfaces. These algorithms include lazy evaluation based on multivariate Sturm sequences, fast resultant computation, culling operations, and floating-point filters. The algorithm has been implemented and we highlight its performance on a number of examples.