Skeletonisation of three-dimensional object using generalized potential field

In this paper, the potential-based skeletonization approach for 2D medial axis transform (MAT), which identifies object skeleton as potential valleys using a Newtonian potential model in place of the distance function, is generalized to three dimensions. The generalized potential functions given by Chung (1998), which decay faster with distance than the Newtonian potential, is used for the 3D case. The efficiency of the proposed approach results from the fact that these functions and their gradients can be obtained in closed forms for polyhedral surfaces. According to the simulation results, the skeletons obtained with the proposed approach are closely related to the corresponding MAT skeletons. While the medial axis (surface) is 2D in general for a 3D object, the potential valleys, being one-dimensional, form a more realistic skeleton. Other desirable attributes of the algorithm include stability against perturbations of the object boundary, the flexibility to obtain partial skeleton directly, and low time complexity.     

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.     

An algorithm for the medial axis transform of 3D polyhedral solids

The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes     

Linear one-sided stability of MAT for weakly injective 3D domain

Despite its usefulness in many applications, the medial axis transform (MAT) is very sensitive to the change of the boundary in the sense that, even if a shape is perturbed only slightly, the Hausdorff distance between the MATs of the original shape and the perturbed one may be large. However, it is known that MATs of 2D domains are stable if we view this phenomenon with the one-sided Hausdorff distance. This result depends on the fact that MATs are stable if the differences between them are measured with the recently introduced hyperbolic Hausdorff distance. In this paper, we extend the result for the one-sided stability of the MAT to a class of 3D domains called weakly injective, which contains many important 3D shapes typically appearing in solid modeling. Especially, the weakly injective 3D domains can have sharp features like corners or edges. In fact, by using the stability of the MAT under the hyperbolic Hausdorff distance, we obtain an explicit bound for the one-sided Hausdorff distance of the MAT of a weakly injective 3D domain with respect to that of a perturbed domain, which is linear with respect to the domain perturbation. We discuss some consequences of this result concerning the computation and the approximation of the MAT of 3D objects.     

Domain connected graph: the skeleton of a closed 3D shape for animation

In previous research, three main approaches have been employed to solve the skeleton extraction problem: medial axis transform (MAT), generalized potential field and decomposition-based methods. These three approaches have been formulated using three different concepts, namely surface variation, inside energy distribution, and the connectivity of parts. By combining the above mentioned concepts, this paper creates a concise structure to represent the control skeleton of an arbitrary object. First, an algorithm is proposed to detect the end, connection and joint points of an arbitrary 3D object. These three points comprise the skeleton, and are the most important to consider when describing it. In order to maintain the stability of the point extraction algorithm, a prong-feature detection technique and a level iso-surfaces function-based on the repulsive force field was employed. A neighborhood relationship inherited from the surface able to describe the connection relationship of these positions was then defined. Based on this relationship, the skeleton was finally constructed and named domain connected graph (DCG). The DCG not only preserves the topology information of a 3D object, but is also less sensitive than MAT to the perturbation of shapes. Moreover, from the results of complicated 3D models, consisting of thousands of polygons, it is evident that the DCG conforms to human perception.     

Constructing medial axis transform of planar domains with curved boundaries

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.     

多视点识别三维运动目标新方法

本文讨论了从多视点识别三维运动目标问题．该方案基于对连续输入的二维图像聚类,构成 三维目标的特征视图和转移矩阵,利用极 对数坐标变换（LPM）和离散付立叶变换（DFT） 提取出与目标二维特征视图的位置、比例和旋转无关的特征向量．ART-2模型作为目标特征 信息的存储器和分类器．实验中对ART-2神经网络进行了改进,取得了满意的结果．     

Discrete shading of three-dimensional objects from medial axis transform

In this paper, we present a discrete shading technique using medial axis transform (MAT) of 3D binary image data based on digital generalized octagonal distances. Our method is computationally attractive as it does not require the explicit computation of surface normals. We have compared our results with images rendered from voxel and octree representations while using analytical surface rendered images as bench marks. The quality of rendering by our method is certainly superior to those obtained from voxel and octree representations.     

A medial axis transformation for grayscale pictures

Blum's medial axis transformation (MAT) for binary pictures yields medial axis points that lie midway between opposite borders of a region or along angle bisectors. This note discusses a generalization of the MAT in which a score is computed for each point P of a grayscale picture based on the gradient magnitudes at pairs of points that have P as their midpoint. These scores are high at points that lie midway between pairs of antiparallel edges or along angle bisectors, so that they define a MAT-like ``skeleton,' which we may call the GRADMAT. However, this skeleton is rather sensitive to the presence of noise edges or to irregularities in the region edges, and it also is subject to artifacts created by pairs of edges belonging to different objects.     

Computation of the medial axis of planar domains based on saddle point programming

This paper presents a saddle point programming approach to compute the medial axis (MA). After exploring the saddle point properties of the medial axis transform (MAT), the mathematical programming method is employed to establish the saddle point programming model of the MAT. By using the optimal conditions, i.e., the number and distribution of the tangent points between the boundary and medial axis disk, the one- and two-dimensional saddle point algorithms are developed. In order to determine the branch point, it is better to consider its generating mechanism. Here, we identify the branch point according to the sudden changes of the solutions to the one-dimensional saddle point algorithm. Hence, all the regular and irregular points of MA can be computed by a general algorithm, and it is proved to be efficient and accurate by the numerical examples.     

Geometric properties of the union of maximal neighborhoods

The problem of computing area and perimeter of a digital figure presented by its discrete medial axis transform (MAT) is addressed. The figure is seen as the union of the square-shaped maximal neighborhoods centered on the local maxima of the MAT. The contribution given by each maximal neighborhood to figure area and perimeter is computed while tracing the MAT. Multiple overlaps among the maximal neighborhoods are possible. However, due to the properties of the local maxima and their associated maximal neighborhoods a single tracing of the MAT is provided to be sufficient to obtain the desired result. Thus, the procedure requires O(N) time, where N is the number of MAT pixels     

A min-max medial axis transformation

Blum's medial axis transformation (MAT) of the set S of 1's in a binary picture can be defined by an iterative shrinking and reexpanding process which detects ``corners' on the contours of constant distance from S?, and thereby yields a ``skeleton' of S. For unsegmented (gray level) pictures, one can use an analogous definition, in which local MIN and MAX operations play the roles of shrinking and expanding, to compute a ``MMMAT value' at each point of the picture. The set of points having high values defines a good ``skeleton' for the set of high-gray level points in the given picture.     

一种插值与逼近运动物体活动标架的新方法

插值运动物体给定活动标架(原点位置和3个坐标轴朝向)是计算机图形学、机器人等领域的一个重要问题.该文提出一种采用B样条曲线插值与逼近运动物体活动标架的新方法.采用4个欧拉参数对正交活动标架的旋转变换矩阵进行参数化,得到了一个简单的优化方程.采用迭代法求解该优化方程来逼近运动轨迹任意处伪活动标架的旋转变换矩阵.还证明了插值和逼近所引起的误差是可控的.由于活动标架的计算只涉及2阶或3阶线性方程组,所以此方法具有很高的运行效率.     

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.     

基于整数中轴骨架的3维模型检索算法

针对3维模型检索算法性能较低的问题,提出了一种基于整数中轴骨架的3维模型检索算法。在对3维模型进行姿态调整和各向同向性预处理后,提取模型的整数中轴骨架,并记录每个骨架点相应的几何信息,对提取的骨架按不同的空间区域划分,形成模型骨架二叉树。为了能够描述骨架二叉树的不同节点对模型整体相似性匹配的影响程度,为每个节点定义一个特征权值,其大小由该节点对应的骨架区域大小所决定。最后,采用由粗到细逐步淘汰的策略计算不同模型的相似度。对一个标准3维模型测试数据库的检索实验结果表明,由于将模型的拓扑结构和统计特征相结合,该算法可以得到较好的检索性能。     

An automatic coarse and fine surface mesh generation scheme based on medial axis transform: Part i algorithms

We present an algorithm for the generation of coarse and fine finite element (FE) meshes on multiply connected surfaces, based on the medial axis transform (MAT). The MAT is employed to automatically decompose a complex shape into topologically simple subdomains, and to extract important shape characteristics and their length scales. Using this technique, we can create a coarse subdivision of a complex surface and select local element size to generate fine triangular meshes within those subregions in an automated manner. Therefore, this approach can lead to integration of fully automatic FE mesh generation functionality into FE preprocessing systems.     

LSMAT Least Squares Medial Axis Transform

The medial axis transform has applications in numerous fields including visualization, computer graphics, and computer vision. Unfortunately, traditional medial axis transformations are usually brittle in the presence of outliers, perturbations and/or noise along the boundary of objects. To overcome this limitation, we introduce a new formulation of the medial axis transform which is naturally robust in the presence of these artefacts. Unlike previous work which has approached the medial axis from a computational geometry angle, we consider it from a numerical optimization perspective. In this work, we follow the definition of the medial axis transform as ‘the set of maximally inscribed spheres’. We show how this definition can be formulated as a least squares relaxation where the transform is obtained by minimizing a continuous optimization problem. The proposed approach is inherently parallelizable by performing independent optimization of each sphere using Gauss–Newton, and its least‐squares form allows it to be significantly more robust compared to traditional computational geometry approaches. Extensive experiments on 2D and 3D objects demonstrate that our method provides superior results to the state of the art on both synthetic and real‐data.