具有鲁棒性的图像骨架提取方法

基于最大正方形的中轴变换,提出了一种二值图像的骨架提取算法。首先通过计算目标像素邻域内最大正方形的所有像素的个数来进行中轴变换,判断骨架点,并提取骨架。如果通过设定一个阈值,再提取骨架,就可以滤除背景中的噪声。实验结果表明:该方法提取的骨架效果好,通过与基于传统中轴变换和形态学提取骨架方法进行比较,该方法抗干扰能力强。     

优化的离散λ-中轴骨架提取算法

离散λ-中轴(DLMA)是一种快速、健壮的中轴变换算法,选择合适的参数λ可以提取物体较为精准的单像素骨架.针对DLMA算法的缺点,提出一种融合欧氏距离变换局部极大值点思想和背景点空间思想的DLMA优化算法.该算法将DLMA算法分成2步,先使用一个小λ阈值获得骨架的粗提取结果,计算过程中将其N4邻域简化为N2邻域;然后在粗提取的结果下设计骨架生长阈值自动调整策略,使其对宽度变化具有足够的适应性.实验结果表明,与原DLMA算法相比,文中提出的优化算法不仅具有更快的计算速度,鲁棒性和自适应能力均有显著提高.     

基于距离变换的A*搜索骨架提取方法

针对部分传统骨架提取方法提取骨架位置偏离中轴的问题,提出了一种基于距离变换的A*搜索骨架的提取方法.根据距离变换和形态学分水岭算法获得包含物体骨架的骨架潜在图,通过主动轮廓线模型确定骨架关键点,通过A*算法对骨架线进行搜索,得到骨架.实验证明,该方法获得的骨架具有连通性、单像素性、多尺度性及位置准确等优点.     

基于中轴变换的骨架特征提取算法

针对中轴变换算法提取骨架特征时,其结果对边界噪声敏感且易产生毛刺的问题,提出一种基于中轴变换的改进算法。采用Voronoi图计算原始中轴,使用改进的二次误差度量方法去除毛刺。在二维及三维数据集上的实验结果表明,该算法能够提取简洁、准确的骨架,且对边界噪声具有鲁棒性。     

基于欧氏骨架的手势识别系统

引进最新骨架提取算法,设计并实现了一种以手势的欧氏骨架为基准的手势识别系统,系统由通用视频采集模块和ARM开发板硬件组成.利用动态前景检测算法结合YCbCr肤色识别模型,分割出手势区域;借助欧氏距离变换和Delta—中轴骨架提取算法获得手势区域的欧氏骨架,并提取骨架的关键点和欧氏距离等几何参数,以此建立手势识别的几何模型.实验测试正确识别率高达94%,每帧图片处理时间小于25 ms,表明该系统实时、有效.     

区域表示：二元数组转换成线性四元树

本文提出一种方法实现二值图象的二元数组表示转换成线性四元树描述。它包括两个算法:(1)二元数组转换成0-四分形集合,和(2)平移-合并0-四分形。对于二元数组,算法(1)需要O(2~(2n))时间。算法(2)以0-四分形数目的线性时间运行。     

基于三角剖分对偶图的结构表示模型及其算法

通过提取中轴骨架并对其进行跟踪而获得层次结构图是模式识别中最常用的一种方法。论文提出一种相对骨架的新型结构表示模型“三角剖分对偶图”。利用这种结构表示模型可以从二值图像中直接获得层次结构图,并表达为树的最基本的数据结构。此外,论文还给出了三角剖分对偶图的提取和优化算法,并与骨架表示模型的层次结构图作了比较。     

一个基于线性四元树的连通标记算法

图象的四元树表示提供了有效地节省图象存储空间及快速地实施图象处理的方法,而利用四元树实现图象的连通标记则是图象处理、图象分析及计算机图形学中最基本的操作之一。文献〔1〕和〔2〕分别给出了基于指针四元树和线性四元树的图象连通标记算法。本文提出了一个新的基于线性四元树(Linear Quadtree,简称 LQT)的连通标记算法 CCL(T,N)(Connected Component Labeling),其算法平均时间复杂度与前两个算法相同,均为 O(N.logN),但其实用效率及通用性均优于前两者。     

利用模板和邻域信息的静脉骨架提取新算法

为提高骨架提取的准确性和连通性,提出了一种利用模板和邻域信息的静脉骨架提取新算法,该算法首先对二值图像进行平滑,并通过自适应方法计算静脉纹路上所有像素点邻域之和,以快速区分出边缘点和中轴点,然后遍历图像找出所有符合中轴点模板的像素点,并删除其中的孤立中轴点之后,得到一些间断的中轴线段,最后从这些中轴线段的端点开始采用最大邻域点跟踪方法提取出静脉骨架。实验结果表明,该算法提取的静脉骨架与中轴线重合且平滑稳定,且具有尺度不变性,角度不变性和良好的抗噪性能,是一种有效的骨架提取算法。     

基于优化DRG的三维人体点云骨架提取方法

针对离散Reeb图（Discrete Reeb Graph,DRG）描述人体骨架时分支部位骨架线偏离中轴的问题,采用了能量函数最小化的方法对DRG曲线进行优化。将人体模型的DRG曲线作为初始骨架,定义其能量函数,在点云模型的距离场梯度的作用下,迭代地调整偏离中轴目标段的曲线位置使其逐渐逼近中轴,能量函数最小时得到优化的骨架。将该算法应用于同一模特四个不同姿势和四个不同模特同一姿势的人体点云模型,并与基于拉普拉斯算子的点云收缩的骨架提取方法进行了比较。结果表明,该算法能够很好地适应各种不同姿势和体型,模型分叉部位的特征得到更加完善的描述,得到的骨架曲线更接近模型的中轴。     

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

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

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.     

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.     

Dimensional Reduction of Surface Models for Analysis

This paper describes a set of procedures by which an analyst can idealise slender 2D shell structures for linear static analysis using reduced-dimensional beam finite elements. The first step is the development of the topological operations that are necessary to achieve the desired dimensionally reduced representation. Next, the automatic derivation of necessary geometric and physical properties of the reduced dimensional entities are described, together with the application of appropriate coupling constraints between dimensions. Dimensional reduction of shell models involves finding areas of the geometric model whose dimensions are such that this region may be represented in an analysis model with a 1D beam. Using the medial axis transform, geometric measures are defined for identifying such areas in the geometric model. However, topological features of the model and its medial axis were also identified as significant in the automation of dimensional reduction. The application of the medial axis transform to automatic dimensional reduction is described and example models given.     

Fast distance transformation on irregular two-dimensional grids

In this article, we propose a new fast algorithm to compute the squared Euclidean distance transform (E²DT) on every two-dimensional (2-D) irregular isothetic grids (regular square grids, quadtree based grids, etc.). Our new fast algorithm is an extension of the E²DT method proposed by Breu et al. [3]. It is based on the implicit order of the cells in the grid, and builds a partial Voronoi diagram of the centers of background cells thanks to a data structure of lists. We compare the execution time of our method with the ones of others approaches we developed in previous works. In those experiments, we consider various kinds of classical 2-D grids in imagery to show the interest of our methodology, and to point out its robustness. We also show that our method may be interesting regarding an application where we extract an adaptive medial axis construction based on a quadtree decomposition scheme.     

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.     

Shape representation using a generalized potential field model

This paper is concerned with efficient derivation of the medial axis transform of a 2D polygonal region. Instead of using the shortest distance to the region border, a potential field model is used for computational efficiency. The region border is assumed to be charged and the valleys of the resulting potential field are used to estimate the axes for the medial axis transform. The potential valleys are found by following the force field, thus, avoiding 2D search. The potential field is computed in closed form using equations of the border segments. The simple Newtonian potential is shown to be inadequate for this purpose. A higher order potential is defined which decays faster with distance than the inverse of distance. It is shown that as the potential order becomes arbitrarily large, the axes approach those computed using the shortest distance to the border. Algorithms are given for the computation of axes, which can run in linear parallel time for part of the axes having initial guesses. Experimental results are presented for a number of examples     

基于图象分层优化二元树结构表示的图象处理基本算法

在图象分层优化二元树结构表示的基础上,给出了图象分层优化二元树结构表示的图象处理基本算法:点搜索算法、邻域查找算法及同级灰度查找算法,试验结果表明,该结构表示比线性四元树结构表示及指针四元树结构表示相应算法查找速度要快.     

一种用于手写数字分割的滴水算法的改进

在分析传统滴水算法针对共用粘连字符分割存在不足的基础上,提出一种改进的渗漏过程.该方法首先对字符的笔划粘连部分利用距离变换提取出中心线,并通过计算字符笔划的倾斜角度来指导水滴在中心线上端和下端的渗漏方向,最终形成一条较长倾斜的分割路径,避免了因垂直分割而造成的字符断裂.实验结果中分割效果较好,表明该方法的有效性.