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.     

2D finite element mesh generation by medial axis subdivision

An algorithm for the automatic generation of two-dimensional finite element meshes using quadrilateral elements has been demonstrated. The technique uses information derived from the medial axis of a 2D region, the locus of the centre of an inscribed disc of maximal diameter as it rolls around the region interior. Using this information, an arbitrarily complex object can be subdivided into a series of meshable subregions. Within these subregions relatively conventional meshing patterns are then generated. The resulting meshes are well structured and flow smoothly round the object boundary with minimum mesh irregularity.     

Triangle rendering using adaptive subdivision

Based on the error analysis of line segment rendering, we propose a new approach to piecewise linear approximation that proves significantly more efficient than previous solutions and allows the maintenance of any degree of accuracy. The major idea uses triangle subdivision versus scanline subdivision, computing the number of subtriangles based on the ratio of homogeneous coordinates. We show that it is possible to reduce the number of divisions by several orders of magnitude and still maintain high-quality rendering     

Serial and parallel algorithms for the medial axis transform

An O(n²) time serial algorithm is developed for obtaining the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log² n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n²) processors. Two problems associated with the MAT, the area and perimeter reporting problem, are studied. An O(log n) time hypercube algorithm is developed for both of them, where n is the number of squares in the MAT, and the algorithms use O(n²) processors     

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.     

3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

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.     

Parallel computation of geometric properties from the medial axis transform

The medial axis transform (MAT) represents a region of a digital image as the union of maximal upright squares contained in the region. This paper presents algorithm to compute the contour, perimeter, and area of the region covered by a set of n upright rectangles in O(n) time using O(n) processors for the shared memory model, and using O(n²) processors for mesh-connected computers.     

Computing the medial axis transform in parallel with eight scanoperations

The main result of this paper shows that the block-based digital medial axis transform can be computed in parallel by a constant number of calls to scan (parallel prefix) operations. This gives time- and/or work-optimal parallel implementations for the distance-based and the block-based medial axis transform in a wide variety of parallel architectures. Since only eight scan operations plus a dozen local operations are performed, the algorithm is very easy to program and use. The originality of our approach is the use of the notion of a derived grid and the oversampling of the image in order to reduce the computation of the block-based medial axis transform in the original grid to the much easier task of computing the distance based medial axis transform of the oversampling of the image on the derived grid     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Modeling smooth shape using subdivision on differential coordinates

Traditional subdivision schemes are applied on Euclidean coordinates (the spatial geometry of the control mesh). Although the subdivision limit surfaces are almost everywhere C² continuous, their mean-curvature normals are only C⁰. In order to generate higher quality surfaces with better-distributed mean-curvature normals, we propose a novel framework to apply subdivision for shape modeling, which combines subdivision with differential shape processing. Our framework contains two parts: subdivision on differential coordinates (a kind of differential geometry of the control mesh), and mutual conversions between Euclidean coordinates and differential coordinates. Further discussions about various strategies in both parts include a special subdivision method for mean-curvature normals, additional surface editing options, and a version of our framework for curve design. Finally, we demonstrate the improvement on surface quality by comparing the results between our framework and traditional subdivision methods.     

MATHSM: medial axis transform toward high speed machining of pockets

The pocketing operation is a fundamental procedure in NC machining. Typical pocketing schemes compute uniform successive offsets or parallel cuts of the outline of the pocket, resulting in a toolpath with C¹ discontinuities. These discontinuities render the toolpath quite impractical in the context of high speed machining (HSM).This work addresses and fully resolves the need for a C¹ continuous toolpath in HSM and offers MATHSM, a C¹ continuous toolpath for arbitrary C¹ continuous pockets. MATHSM automatically generates a C¹ continuous toolpath that consists of primarily circular arcs while maximizing the radii of the generated arcs and, therefore, minimizing the exerted radial acceleration. MATHSM is especially suited for machining of elongated narrow pockets.     

基于双法线跟踪的形状中轴并行提取算法

为准确而高效地提取出形状的中轴,提出一种利用双法线跟踪算法来并行计算形状中轴的方法。通过离散化将形状的边界离散为由若干样本点连接成的多边形,分别对样本点以及样本点连接成的边界边进行两次的法线跟踪,通过多次的迭代与并行计算后,得到所有样本点对应的中轴点,根据样本点的拓扑联通性连接相应中轴点,生成形状的中轴。通过多次实验,该方法可以快速准确得到形状的中轴,验证了其精确性和高效性。     

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     

Relation between the medial axis of the foot outline and 3-D foot shape

Posterior flexion angle (PFA) of the medial axis of foot outline is a useful tool for analysing the morphological variation of the human foot. In order to clarify the relation between PFA and the three-dimensional foot shape, the right foot was measured three-dimensionally for 20 male and 39 female subjects. The foot was taken to consist of a series of cross-sections, and morphological characteristics of these sections as well as PFA and the intensity of medial bulge were used to analyse the foot shape. These morphological characteristics were independent of the foot size and correlated with each other. The results of a principal component analysis indicate that the most important variation in the human foot shape is that contrasting a pronated flat foot and a foot of ‘standard’ type. A ‘standard’ type of foot has well-developed plantar arch and straight medial axis, and actually the majority of people do not have this type of foot. The strategies for improving the fit of the shoe in a general population were discussed.     

Analysis of foot shape variation based on the medial axis of foot outline

The variations in foot outline forms are analyzed by using flexion angles of the medial axis of foot outline. Foot outline and 12 conventional measurements taken on the right foot of 443 male and 297 female subjects with no visible pathological deformation of the foot were used for analyses. The results indicate that the foot is outflared in most of the subjects. Medial bulge and lateral concavity of foot outline are responsible for the foot outflare, and they are not correlated with each other. Medial bulge is due to the overhang of navicular bone that is caused by the pronation of the foot. Its intensity is negatively correlated with dorsal arch height. Lateral concavity is partly due to the abduction of talus and calcaneus relative to the tarsometatarsal bones anterior to them. These three-dimensional morphological characteristics of outflared feet intimately relate to the fit and comfort of the shoe. The flexion angles of medial axis of foot outline provide a useful tool in morphological analysis of the foot for the following reasons; (1) they carry the information on the three-dimensional foot shape that cannot be represented by conventional measurements; and (2) the data is easily obtained and calculations are easily made with minimum expense.     

Perceptually adaptive spread transform image watermarking scheme using Hadamard transform

The present paper proposes a digital image watermarking scheme using the characteristics of the human visual system (HVS), spread transform technique and statistical information measure. Spread transform (ST) scheme is implemented using the transform coefficients of both the host and the watermark signal. Watermark embedding strength is adaptively adjusted using frequency sensitivity, luminance, contrast and entropy masking of HVS model. The choice of Hadamard transform as watermark embedding domain offers several advantages, such as low loss in image information (higher image fidelity), greater reliability of watermark detection and higher data hiding capacity at high degree of compression. Performance of the proposed method is compared with a number of recently reported watermarking schemes based on spread spectrum (SS) and quantization index modulation (QIM).