Computing a compact spline representation of the medial axis transform of a 2D shape

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.     

Total curvature variation fairing for medial axis regularization

We present a new fairing method for planar curves, which is particularly well suited for the regularization of the medial axis of a planar domain. It is based on the concept of total variation regularization. The original boundary (given as a closed B-spline curve or several such curves for multiply connected domains) is approximated by another curve that possesses a smaller number of curvature extrema. Consequently, the modified curve leads to a smaller number of branches of the medial axis. In order to compute the medial axis, we use the state-of-the-art algorithm from [1] which is based on arc spline approximation and a domain decomposition approach. We improve this algorithm by using a different decomposition strategy that allows to reduce the number of base cases from 13 to only 5. Moreover, the algorithm reduces the number of conic arcs in the output by approx. 50%.     

Computation of medial axis and offset curves of curved boundaries in planar domain

In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper.     

Transformation of a thin-walled solid model into a surface model via solid deflation

A simplified geometric model with lower dimensionality, such as a mid-surface model, is often preferred over a detailed solid model for the analysis process, if the analysis results are not seriously impacted. In order to derive a mid-surface model from a thin-walled solid model, in this paper, we propose a novel approach called the solid deflation method. In this method, a solid model is assumed to be created by using air to inflate a shell that comprises the surface of the solid model. First, the model is simplified by the removal of any detailed features whose absence would not alter its overall shape. Next, the solid model itself can be converted into a degenerate solid model with zero thickness. Finally, a surface model is generated by splitting large faces paired in the thinned solid model, selecting one face per pair for creating a sheet model, and sewing the selected faces. Using this method, a more practical and usable mid-surface model can be very efficiently generated from a solid model because it can circumvent not only the tedious trimming and extension processes of the medial axis transformation method but also the time-consuming patch joining process of the mid-surface abstraction approach.     

Distance functions and skeletal representations of rigid and non-rigid planar shapes

Shape skeletons are fundamental concepts for describing the shape of geometric objects, and have found a variety of applications in a number of areas where geometry plays an important role. Two types of skeletons commonly used in geometric computations are the straight skeleton of a (linear) polygon, and the medial axis of a bounded set of points in the k-dimensional Euclidean space. However, exact computation of these skeletons of even fairly simple planar shapes remains an open problem.In this paper we propose a novel approach to construct exact or approximate (continuous) distance functions and the associated skeletal representations (a skeleton and the corresponding radius function) for solid 2D semi-analytic sets that can be either rigid or undergoing topological deformations. Our approach relies on computing constructive representations of shapes with R-functions that operate on real-valued halfspaces as logic operations. We use our approximate distance functions to define a new type of skeleton, i.e, the C-skeleton, which is piecewise linear for polygonal domains, generalizes naturally to planar and spatial domains with curved boundaries, and has attractive properties. We also show that the exact distance functions allow us to compute the medial axis of any closed, bounded and regular planar domain. Importantly, our approach can generate the medial axis, the straight skeleton, and the C-skeleton of possibly deformable shapes within the same formulation, extends naturally to 3D, and can be used in a variety of applications such as skeleton-based shape editing and adaptive motion planning.     

Medial axis computation for planar free-form shapes

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.     

Robust skeletonization using the discrete λ-medial axis

Medial axes and skeletons are notoriously sensitive to contour irregularities. This lack of stability is a serious problem for applications in e.g. shape analysis and recognition. In 2005, Chazal and Lieutier introduced the λ-medial axis as a new concept for computing the medial axis of a shape subject to single parameter filtering. The λ-medial axis is stable under small shape perturbations, as proved by these authors. In this article, a discrete λ-medial axis (DLMA) is introduced and compared with the recently introduced integer medial axis (GIMA). We show that DLMA provides measurably better results than GIMA, with regard to stability and sensibility to rotations. We give efficient algorithms to compute the DLMA, and we also introduce a variant of the DLMA which may be computed in linear-time.     

基于模糊控制的自适应有限元网格自动剖分

本文采用模糊控制策略，对有限元网格划分过程中难以控制的因素－网格密度作出自适应控制。同时借鉴先验自适应的思想，在后验控制过程中综合考虑了边界属性的影响，避免了较多层次的网格局部细化与退化，采用此方法，不仅保证了计算精度，而且可以提高运算效率。     

New reduced discrete Euclidean nD medial axis with optimal algorithm

Skeletons have been playing an important role in shape analysis since the introduction of the medial axis in the sixties. The original medial axis definition is in the continuous Euclidean space. It is a skeleton with the following characteristics: centered, thin, homotopic (it has the same topology as the object), and reversible (sufficient for the reconstruction of the object). The discrete version of the Euclidean medial axis (MA) is also reversible and centered, but no longer homotopic nor thin. The combination of the MA with homotopic thinning algorithms can result in a topology preserving, reversible skeleton. However, such combination may generate thicker skeletons, and the choice of the thinning algorithm is not obvious. A robust and well defined framework for fast homotopic thinning available in the literature is defined in the domain of abstract complexes. Since the abstract complexes are represented in a doubled resolution grid, some authors have extended the MA to a doubled resolution grid and defined the discrete Euclidean medial axis in higher resolution (HMA). The HMA can be combined with the thinning framework defined on abstract complexes. Other authors have given an alternative definition of medial axis, which is a subset of the MA, called reduced discrete medial axis (RDMA). The RDMA is reversible, thinner than the MA, and it can be computed in optimal time. In this paper, we extend the RDMA to the doubled resolution grid and we define the high-resolution RDMA (HRDMA). We provide an optimal algorithm to compute the HRDMA. The HRDMA can be combined with the thinning framework defined on abstract complexes. The skeleton obtained by such combination is provided with strong characteristics, not found in the literature.     

Skeletonization based on error reduction

The accuracy of a non-pixel-based skeletonization method is largely dependent on the contour information chosen as input. When using a Constrained Delaunay Triangulation to construct an object's skeleton, a number of contour pixels must be chosen as a basis for triangulation. This paper presents a new method of selecting these contour pixels. A new method for measuring skeletonization error is proposed, which quantifies the deviation of a skeleton segment from the true medial axis of a stroke in an image. The goal of the proposed algorithm is to reduce this error to an acceptable level, whilst retaining the superior efficiencies of previous non-pixel-based techniques. Experimental results show that the proposed method is adept at following the medial axis of an image, and is capable of producing a skeleton that is confirmed by a human's perception of the image. It is also computationally efficient and robust against noise.