线性四元树中轴变换

骨架和中轴变换概念运用于线性四元树,定义线性四元树中轴变换为具有一组棋盘距离值的线性四元树骨架.线性四元树中轴变换提供一种非常紧凑的区域表示法,它导致区域分割成边长为2的幂之和的最大正方形集合.提出两种算法计算一给定线性四元树的线性四元树中轴变换.最坏情况下它们的时间复杂性是O(n~2),其中n为线性四元树中四分形的数目.     

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

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

基于数学形态学的中轴变换算法

对二值图像处理中中轴变换的算法进行了研究,介绍了基于形态学的中轴变换算法,同时,对数学形态学的相关理论做了介绍。并利用该算法对地图图像进行了中轴变换的处理,取得了良好的实验效果。通过实验研究可以看出,该算法设计灵活,便于实现,具有一定的实用性。     

基于围线分层扫描的完全欧氏距离变换算法

围线扫描欧氏距离变换算法是一种快速的完全欧氏距离变换算法,其时间复杂度达到最优,但需在围线区域进行全局搜索,计算时间并未优化。针对此问题,提出了一种基 于围线分层扫描的完全欧氏距离算法。该算法首先根据中心像素的围线性质对二值图像像素点进行重新分类,然后按照围线区域像素与中心像素的空间关系,对中心像素的围线区 域进行分层搜索,并给出了搜索的终止条件。该算法保持了最优的时间复杂度,可通过定量分析单个像素的计算时间来证明其计算时间已得到优化。实验结果表明,该算法能够得到 准确的欧氏距离图像,且运行速度快。     

一种使用水平集的中轴提取算法

在岩心三维模型中,中轴是描述孔隙结构特征的一种重要表示方法。针对现有的拓扑细化和距离变换方法存在的中轴提取不准确和不连续的问题,提出了一种使用快速行进水平集方法进行距离变换的三维中轴提取算法。对比实验结果表明,该算法中提取的中轴在准确性和连续性上有着较好的保证,实际应用中效果良好。     

基于中轴表达的三维模型轮廓提取方法

三维网格模型的轮廓信息在网格检索、网格简化、网格重建中有着广泛应用。现有的轮廓提取方法较为复杂,需要分析和过滤网格模型的几何特征,计算量大且有时无法生成完整的轮廓信息。近年来,三维模型的中轴表达研究趋于成熟,在表达模型几何拓扑关系上有独特的优势。因此,提出了一种基于中轴表达的三维模型轮廓提取方法：首先提取三维模型的中轴表达信息,将中轴角点投影到三维模型表面;然后根据每个区域的拓扑关系选择适合的角点连接关系,将投影点连接形成模型区域轮廓;再针对投影过程中产生的误差进行分析和纠正;最后合并区域轮廓得到三维模型的完整轮廓。通过对多个模型数据库中代表性的三维网格模型进行实验和重建误差比较,该方法的平均重建质量较现有方法约有10%的提升,在重建质量和轮廓信息完整度方面优于现有方法。     

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

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

基于中轴变换的参数化图形构造方法

图形构造是工程领域中设计图形的重要手段,针对其在效率、交互性和复用性存在的不足,提出一种基于中轴变换的参数化图形构造方法.通过控制点生成中轴段,通过中轴半径确定图形边界信息.基于上一条中轴段的端点迭代生成中轴段及其边界;基于这些边界信息,构造出图形.利用中轴的控制点进行交互,确保了构造时的交互性;只需对参数值进行改变,即可构造相似的图形,保证了方法的复用性;复杂的图形仅需要通过简单的中轴变换即可得出,确保了构造方法的效率.通过实例,证明了该方法在效率、交互性和复用性上的优越性.     

深宽比对铜互连线残余应力的影响

采用ANSYS有限元软件模拟了不同深宽比铜互连线的残余应力分布情况。结果表明,铜互连线表面和侧壁区域的应力随深宽比升高而增加;底部区域的应力在深宽比接近1时达到最小值。     

基于改进边界距离变换的路径提取算法研究*

针对虚拟内窥镜中心路径提取算法时间效率不高的问题,通过改进边界距离变换,提出了中心路径的快速提取算法。首先建立最小距离场,在边界内推过程,仅扫描并处理与边界点面连接的点并对其设标记属性,每次向里剥离一层体素标记属性随之增加,直到对内部点集都置到边界的最小边界距离值（DFB）;然后找到DFB值不小于其所有面邻接点DFB值的体素点,即3D局部最大值;最后用最短路径相连3D局部最大值,形成中心线。实验结果表明,改进的中心路径提取算法的时间效率较传统距离变换算法有很大提高。     

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.     

基于递归的二值图像连通域像素标记算法

在研究以前二值图像连通算法的基础上，提出了一种基于递归方法的二值图像连通域像素标记算法。通过对二值图像的扫描和分析可得到二值图像中的连通域划分和连通域的数目。算法主要包括两个步骤：对输入的二值图像进行一次扫描，得到所有目标像素的连通域划分和标记的等价对表；利用递归对等价对表进行分析，得到正确的连通标记划分和连通区域数目。实验结果表明，该算法对于任意复杂形状、任意数目(小于1 000)的连通区域都能正确检测。     

实体模型的三轴数控粗加工刀轨生成算法

提出一种适合实体模型的三轴数控粗加工刀位轨迹生成算法。首先根据加工行距作一组平行于刀轴的平面，与模型的待加工表面求交，得到一系列交线；再根据精度规划一组垂直于刀轴的分层平面，与上述交线求交，在每一分层平面上判断加工区域，规划出加工刀位轨迹，将每一分层平面上的刀位轨迹较适当的方式连接起来，就构成零件的整体加工轨迹。该算法避免了轮廓环等距、自交处理和布尔运算等复杂的计算过程；同时，对生成开型腔的加工刀位轨迹也是有效的。     

熔焊快速成型的截面填充与扫描算法研究

本文针对熔焊快速成型技术的特点,在对其截面填充的过程与轨迹规划详细研究的基础上,提出了一整套适合熔焊快速成型的截面填充算法。该算法首先用双向循环链表表示模型截面轮廓的边界,然后对这些截面轮廓进行内外轮廓的判定、复连通区域和单连通区域的判定、以及复连通区域剖分和单连通区域的单调划分,最终生成有限个单调区域。最后对这些单调区域进行填充扫描,并生成可用于熔焊快速成型的数控指令。     

Optimal separable algorithms to compute the reverse euclidean distance transformation and discrete medial axis in arbitrary dimension

In binary images, the distance transformation (DT) and the geometrical skeleton extraction are classic tools for shape analysis. In this paper, we present time optimal algorithms to solve the reverse Euclidean distance transformation and the reversible medial axis extraction problems for d-dimensional images. We also present a d-dimensional medial axis filtering process that allows us to control the quality of the reconstructed shape     

基于蚁群融合D*Lite的动态改航路径规划

危险天气下的改航与受限区划设和路径规划算法密切相关, 本文针对改航环境构建中Graham扫描结果存在较大无效区域, 提出分块后并行扫描. 针对危险天气的突发性, 为了适用于复杂环境, 提出在增量式的D*Lite全局规划路径基础上智能分割、蚁群算法局部搜索的复合结构动态规划方法. 通过改进信息素更新策略解决收敛速度慢、耗时长且易陷入局部最优的缺点. 实验结果表明, 分块并行Graham扫描划设的飞行受限区形状更接近实际, 面积缩至原先的48.1%. 改进蚁群融合D*Lite的复合结构动态路径规划算法D*Lite-ACO兼顾全局与局部, 将重规划范围控制到当前位置与目标点间, 在路径长度、规划时间和迭代范围上的评价指标分别提升1.2%、40.7%、66.7%.     

On the intrinsic reconstruction of shape from its symmetries

The main question we address is: What is the minimal information required to generate closed, nonintersecting planar boundaries? For this paper, we restrict "shape" to this meaning. More precisely, we examine whether the medial axis, together with dynamics, can serve as a language to design shapes and to effect shape changes. We represent the medial axis together with a direction of flow along the axis as the shock graph and examine the reconstruction of shape along each of the three types of medial axis points, A/sub 1//sup 2/, A/sub 1//sup 3/, A/sub 3/, and the associated six types of shock points. First, we show that the tangent and curvature of the medial axis and the speed and acceleration of the shock with respect to time of propagation are sufficient to determine the boundary tangent and curvature at corresponding points of the boundary. This implies that a rather coarse sampling of the symmetry axis, its tangent, curvature, speed, and acceleration is sufficient to regenerate accurately a local neighborhood of shape at regular axis points (A/sub 1//sup 2/). Second, we examine the reconstruction of shape at branch points (A/sub 1//sup 3/) where three regular branches are joined. We show that the three pairs of geometry (that is, curvature) and dynamics (that is, acceleration) must satisfy certain constraints. Finally, we derive similar results for the end points of shock branches (A/sub 3/ points). These formulas completely specify the local reconstruction of a shape from its shock-graph or medial axis and the conditions required to form a coherent shape from the medial axis.     

A new method for analyzing local shape in three-dimensional images based on medial axis transformation

In this paper, we propose a new approach based on three-dimensional (3-D) medial axis transformation for describing geometrical shapes in three-dimensional images. For 3-D-images, the medial axis, which is composed of both curves and medial surfaces, provides a simplified and reversible representation of structures. The purpose of this new method is to classify each voxel of the three-dimensional images in four classes: boundary, branching, regular and arc points. The classification is first performed on the voxels of the medial axis. It relies on the topological properties of a local region of interest around each voxel. The size of this region of interest is chosen as a function of the local thickness of the structure. Then, the reversibility of the medial axis is used to deduce a labeling of the whole object. The proposed method is evaluated on simulated images. Finally, we present an application of the method to the identification of bone structures from 3-D very high-resolution tomographic images.