一种保形的快速图象形态细化算法

骨架是一种重要的图象目标几何特征,对不同形状的图象目标,如何快速地获得其非畸变骨架,是进行图象目标的形状分析、特征提取、模式识别等应用的前提。基于数字形态学的形态细化是获取图象目标骨架的有效细化方法之一。它采用具有一定形状的预定义结构元素,对图象进行形态薄化运算,仅需进行移位和逻辑运算就能完成。但是形态细化一般使用序贯细化算法,在每次细化迭代过程中,只能采用单一的结构元素对目标进行薄化,因此存在关     

On the generation of skeletons from discrete Euclidean distancemaps

The skeleton is an important representation for shape analysis. A common approach for generating discrete skeletons takes three steps: 1) computing the distance map, 2) detecting maximal disks from the distance map, and 3) linking the centers of maximal disks (CMDs) into a connected skeleton. Algorithms using approximate distance metrics are abundant and their theory has been well established. However, the resulting skeletons may be inaccurate and sensitive to rotation. In this paper, we study methods for generating skeletons based on the exact Euclidean metric. We first show that no previous algorithms identify the exact set of discrete maximal disks under the Euclidean metric. We then propose new algorithms and show that they are correct. To link CMDs into connected skeletons, we examine two prevalent approaches: connected thinning and steepest ascent. We point out that the connected thinning approach does not work properly for Euclidean distance maps. Only the steepest ascent algorithm produces skeletons that are truly medially placed. The resulting skeletons have all the desirable properties: they have the same simple connectivity as the figure, they are well-centered, they are insensitive to rotation, and they allow exact reconstruction. The effectiveness of our algorithms is demonstrated with numerous examples     

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.     

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.     

Hidden Deletable Pixel Detection Using Vector Analysis in Parallel Thinning to Obtain Bias-Reduced Skeletons

The improvement of producing skeletons that preserve the significant geometric features of patterns is of great importance. One of feasible approaches is to develop a method embedded in a known parallel algorithm to produce bias-reduced skeletons since a bias skeleton usually degrades the preservation of significant geometric features of patterns. From our observations, bias skeletons always appear in the junction of lines which form an angle less than or near equal to 90°. In this paper, thehidden deletable pixel(HDP) which influences the speed of deleting the boundary pixels on a concave side is newly defined. Based on the comparable performance of our pseudo 1-subcycle parallel thinning algorithm (CH), a reduced form of larger support (twoL-pixel vectors, which is not the form ofk×ksupport) operated by an intermediate vector analysis about the deleted pixels in each thinning iteration is developed for HDP detection to obtain bias-reduced skeletons, which can be purchased by a reasonable computation cost. HDP restoration and parallel implementation are further considered to formulate an improved algorithm (CYS), where the connectivity preservation is guaranteed by the use ofCH's operators and HDP restoration. A set of synthetic images are used to quantify the skeleton from the geometry viewpoint and investigate the skeleton variations of using different (L)s. Based on the analyzing results, 3 ≤L≤ 9 are suggested for the current algorithm ofCYS.CYSis evaluated in comparison with two small support algorithms (AFP3andCH) and one larger support algorithm (VRCT) using the same patterns. Performances are reported by the number of iterations (NI), CPU time (TC), and number of unmatched pixels (N_unmatchfor bias-reduced measure). Results show that on the measure ofTC,CYSis approximately 2 to 3 times slower than the others, while on the measure ofNI, the four algorithms have approximately identical performance. On the measure ofN_unmatch,CYSis approximately 2 to 3 times less than the others. One-pixel boundary noise is also considered for exploring the noise immunity. The results suggest that the noise immunity ofCYSandCHis identical and is better than that ofAFP3. As a result, the better bias-reduced skeletons produced byCYSmay be purchased by a reasonable computation cost.     

Skeleton growing and pruning with bending potential ratio

We propose a novel significance measure for skeleton pruning, called bending potential ratio (BPR), in which the decision regarding whether a skeletal branch should be pruned or not is based on the context of the boundary segment that corresponds to the branch. By considering this contextual information, we can better evaluate the contribution of the boundary segment to the overall shape, which generally depends on its particular location within the whole contour (i.e., a segment may be considered to be insignificant in one place while it may be considered as a feature elsewhere). The BPR is a measure of the significance of contour segments in such context, and depicts the bending potential of a contour segment. Unlike other significance measures that only contain local shape information, the BPR evaluates both local and global shape information. Thus, it is insensitive to local boundary deformation. In addition, we also present a scheme for skeleton growing, which integrates pruning based on the BPR measurement. Our experiments demonstrate that the skeletons obtained by the proposed algorithm are medially placed and connected. We also demonstrate that shapes reconstructed from these skeletons are very close to the original shapes. Moreover, the BPR measure yields a natural multi-scale skeletal representation.     

A knowledge-based thinning algorithm

One common defect of thinning algorithms is deformation at crossing points. To solve this problem, a new thinning method, called the knowledge-based thinning algorithm (KBTA), is proposed. It first represents a binary pattern by coded run lengths of the horizontal line segments. Then the relationship between line segments is described quantitatively by another new algorithm which makes use of both forward and backward derivatives. It afterwards identifies the regions where branches of the pattern meet, then extracts their shape features and thins all of them. Knowing the identities of these regions, perfect skeletons can be obtained. Other regions are thinned by an existing algorithm which is based on contour generation. Experiments with a wide variety of binary patterns show that this new technique generates better skeletons than several other well-known algorithms.     

Implementation of parallel thinning algorithms using recurrentneural networks

The use of recurrent neural networks for skeletonization and thinning of binary images is investigated. The networks are trained to learn a deletion rule and they iteratively delete object pixels until only the skeleton remains. Recurrent neural network architectures that implement a variety of thinning algorithms, such as the Rosenfeld-Kak algorithm and the Wang-Zhang (WZ) algorithm, are presented. A modified WZ algorithm which produces skeletons that are intuitively more pleasing is introduced.     

动态骨架算法

骨架是表示物体形状的一种有效形式.基于距离变换的骨架求解算法得到的骨架尽管准确光滑,但必须仔细地检查其连续性;而当骨架的结构较为复杂时,这种连续性检查会变得非常困难.结合Thinning技术和Snake模型,提出了一个平面二值图的动态骨架算法.首先利用Thinning技术生成连续且拓扑保持的初始骨架,然后根据Snake模型的思想,将初始骨架引导到正确的位置上.动态骨架算法提取的骨架不仅保持了位置的准确和外形的光滑,同时也解决了骨架的连续性问题.     

Thinning and segmenting handwritten characters by line following

This article presents a new thinning algorithm particularly well suited to handwriting characters or engineering drawing images. The line following scheme is used with major improvements to reduce the distortion at intersections. The new algorithm uses a thinning window to detect the shape and type of each intersection it is about to thin. This added information allows for a much more accurate thinning process. The algorithm also segments the skeleton into line segments as it is generated. These lines correlate partly with the strokes that produced the image. To analyze the performance of the new algorithm, a comparative study of the skeletons is performed over speed and quality criteria. This study shows that the algorithm reduces the distortion at the line intersections while remaining fast.     

Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform

A general algorithm for computing Euclidean skeletons of 2D and 3D data sets in linear time is presented. These skeletons are defined in terms of a new concept, called the integer medial axis (IMA) transform. We prove a number of fundamental properties of the IMA skeleton, and compare these with properties of the CMD (centers of maximal disks) skeleton. Several pruning methods for IMA skeletons are introduced (constant, linear and square-root pruning) and their properties studied. The algorithm for computing the IMA skeleton is based upon the feature transform, using a modification of a linear-time algorithm for Euclidean distance transforms. The skeletonization algorithm has a time complexity which is linear in the number of input points, and can be easily parallelized. We present experimental results for several data sets, looking at skeleton quality, memory usage and computation time, both for 2D images and 3D volumes.     

一种适于串行机实现的图像并行细化算法

为解决现有的图像并行细化算法在串行机上的高效实现问题 ,首先提出了一种 4× 4邻域二值图像的双字节图像编码方案 ,由于在该方案中将每个 4× 4邻域的像素用一个双字节的整数来表示 ,从而将基于整个邻域 16个像素的细化处理转化为一个双字节整数的读、写和比较运算的问题 ;然后在此基础上提出了一种可在串行机上实现的并行细化算法。实验证明 ,该算法适用于当前通用的各种基于模板匹配的并行细化算法 ,其不仅可以取得完全相同的细化结果 ,而且可以大幅度提高图像细化过程在串行机上的执行速度 ;最后简要讨论了该算法利用 PC机中的 MMX技术来进一步提高并行粒度和运算效率方面所具有的潜力     

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.     

Thinning algorithms: A critique and a new methodology

This paper surveys the applications of thinning in image processing, and examines the difficulties that confront existing thinning algorithms. A fundamental problem is that an algorithm may not be guaranteed to operate successfully on all possible images: in particular, it may not discriminate properly between ‘noise spurs’ and valid limbs, and the skeleton produced may not accurately reflect the shape of the object under scrutiny. Analysis of the situation results in a new, systematic approach to thinning, leading to a family of algorithms able to achieve guaranteed standards of skeleton precision. One algorithm of this family is described in detail.

“There is still no definitely good method for thinning” - Nagao⁽²⁸⁾     

One-pass parallel thinning: analysis, properties, and quantitativeevaluation

A one-pass parallel thinning algorithm based on a number of criteria, including connectivity, unit-width convergence, medial axis approximation, noise immunity, and efficiency, is proposed. A pipeline processing model is assumed for the development. Precise analysis of the thinning process is presented to show its properties, and proofs of skeletal connectivity and convergence are provided. The proposed algorithm is further extended to the derived-grid to attain an isotropic medial axis representation. A set of measures based on the desired properties of thinning is used for quantitative evaluation of various algorithms. Image reconstruction from connected skeletons is also discussed. Evaluation shows that the procedures compare favorably to others     

Parallel Thinning Algorithms on 3D (18, 6) Binary Images

Thinning algorithms on binary images are used to generate skeletons that preserve the same connectivity structures as the objects in the original images. Two kinds of skeletons may be appropriate for 3D thinning algorithms: digital curves and digital surfaces. We propose two thinning algorithms on 3D (18, 6) binary images. One algorithm generates skeletons as digital curves and the other algorithm generates skeletons as digital surfaces. Both algorithms are 6-subiteration algorithms—in each iteration, they are applied alternatively to delete border voxels from each of the six directions, upper, lower, north, south, east, and west.     

Image Thinning by Neural Networks

An image thinning technique using a neural network is proposed. Using different activation functions at different layers, the proposed neural network removes the boundary pixels from four directions in such a manner that the general configuration of the input pattern is unaltered and the connectivity is preserved. The resulting object, called a skeleton, provides an abstraction of the global shape of the object. The skeleton is often useful for geometrical and structural analysis of the object. The output skeleton here satisfies the basic properties of a skeleton, namely connectivity and unit thickness. The proposed method is experimentally found to be more efficient in terms of better medial axis representation and robustness to boundary noise over a few existing algorithms. ID="A1" Correspondence and offprint requests to: Dr A. Datta, Indian Statistical Institute, 203 B. T. Road, Calcutta – 700 108, India. Email: amitava@isical.ac.in     

A Pruning Algorithm for Stable Voronoi Skeletons

We present a skeleton computation algorithm for binary image shape which is stable and efficient. The algorithm follows these steps: first the shape boundary curves are subsampled, then the Voronoi Skeleton is computed from the resulting reduced boundary set of points, and finally, a?novel two stage pruning procedure is applied to obtain a?simplified skeleton. The first stage removes skeleton edges non fully included in the shape. The second stage applies an enhanced variation of the Discrete Curve Evolution (DCE) for Voronoi skeletons. We obtain improved skeleton stability, complexity reduction and noise robustness. Pruning computing time efficiency is improved thanks to some properties of Voronoi skeletons. Entire skeleton edges can be removed or retained on the basis of conditions tested on the edge endpoints. Pattern recognition experiments and skeleton stability experiments of the algorithm outperform previous approaches in the literature.     

Detection of the non-topology preservation of Ma and Sonka’s algorithm,by the use of P-simple points

In 1996, Ma and Sonka proposed a thinning algorithm which yields curve skeletons for 3D binary images [C. Ma, M. Sonka, A fully parallel 3D thinning algorithm and its applications, Comput. Vis. Image Underst. 64 (3) (1996) 420–433]. This algorithm is one of the most referred thinning algorithms in the context of digital topology: either by its use in medical applications or for comparisons with other thinning algorithms.In 2007, Wang and Basu [T. Wang, A. Basu, A note on ‘a fully parallel 3D thinning algorithm and its applications’, Pattern Recognit. Lett. 28 (4) (2007) 501–506] wrote a paper in which they claim that Ma and Sonka’s 3D thinning algorithm does not preserve topology. As they highlight in their paper, a counter-example was given in 2001, in Lohou’s thesis [C. Lohou, Contribution à l’analyse topologique des images: étude d’algorithmes de squelettisation pour images 2D et 3D selon une approche topologie digitale ou topologie discrète. Ph.D. thesis, University of Marne-la-Vallée, France, 2001].In this paper, it is shown how P-simple points have guided the author towards a proof that Ma and Sonka’s algorithm does not always preserve topology. Moreover, the reasoning being very general, it could be reused for such a purpose, i.e., to simplify the proof on the non-topology preservation.