带特征线约束的Delaunay三角剖分最优算法的研究及实现

为了提高特征线约束的Delaunay三角剖分的速度和功率,从两个方面进行改进;一是生成无约束的Delaunay三角网时,采用进行剖分算法;二是在约束线上插入点时,应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能;“交点”插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件,在满足全局Delaunay三角剖分的前提下,使插入的点最少,对原有的网格影响最小。     

Clothing segmentation using foreground and background estimation based on the constrained Delaunay triangulation

This paper proposes a new clothing segmentation method using foreground (clothing) and background (non-clothing) estimation based on the constrained Delaunay triangulation (CDT), without any pre-defined clothing model. In our method, the clothing is extracted by graph cuts, where the foreground seeds and background seeds are determined automatically. The foreground seeds are found by torso detection based on dominant colors determination, and the background seeds are estimated based on CDT. With the determined seeds, the color distributions of the foreground and background are modeled by Gaussian mixture models and filtered by a CDT-based noise suppression algorithm for more robust and accurate segmentation. Experimental results show that our clothing segmentation method is able to extract different clothing from static images with variations in backgrounds and lighting conditions.     

图像和视频的低多边形渲染

低多边形是近来艺术设计界的热门风格。为了提高图像和视频低多边形风格化的质量,提出一种基于边缘特征和超像素分割的图像和视频低多边形渲染方法。首先提取相邻超像素的交点以及对特征边和超像素边界的差集的均匀采样点作为三角网格顶点,并执行Delaunay三角剖分来生成初始三角网格;然后采用带约束的二次误差度量方法对生成的网格进行简化,以生成最终三角网格;最后对三角网格填充颜色,得到了具有低多边形风格的图像。对于视频低多边形渲染,使用时间一致性超像素跨帧跟踪同一对象的相同部分,以建立视频帧之间的关联,降低视频渲染后的抖动。此外,采用视频分割方法分割视频中的移动对象,获得移动对象与背景之间不同密度的采样点,对移动对象进行渲染获从而得到视频的局部风格化效果。实验结果表明,所提方法能够生成具有较好视觉效果的低多边形渲染结果。     

Text region extraction in a document image based on the Delaunay tessellation

In this paper, Delaunay triangulation is applied for the extraction of text areas in a document image. By representing the location of connected components in a document image with their centroids, the page structure is described as a set of points in two-dimensional space. When imposing Delaunay triangulation on these points, the text regions in the Delaunay triangulation will have distinguishing triangular features from image and drawing regions. For analysis, the Delaunay triangles are divided into four classes. The study reveals that specific triangles in text areas can be clustered together and identified as text body. Using this method, text regions in a document image containing fragments can also be recognized accurately. Experiments show the method is also very efficient.     

一种提花织物图像的有限元分割算法

提花织物图像分割是提花图案设计的关键,曲线演化模型是一种流行的图像分割方法,但是该方法无法检测含噪环境下的图像特征.由于Mumford-Shah(MS)模型能够在噪声环境下对不连续边集进行检测,因此它比曲线演化模型更适于对含噪提花织物图像的分割.提出一种结合有限元法和拟牛顿法的MS模型数值求解算法,并有效用于含噪提花织物图像的分割.首先定义了自适应三角剖分空间上的离散MS模型,并在每次迭代前对有限元网格进行自适应调整,以提高迭代的性能.接着采用拟牛顿最小化方法,通过收敛意义上的离散有限元逼近得到离散MS模型的最小值.该算法被用到含噪提花织物图像的分割中,取得了良好的效果.     

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究，提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分，然后再根据对偶特性构建Voronoi图．该算法健壮性很高，适用于处理各种非完全共面三维点集．     

Skeletonization based on error reduction

The accuracy of a non-pixel-based skeletonization method is largely dependent on the contour information chosen as input. When using a Constrained Delaunay Triangulation to construct an object's skeleton, a number of contour pixels must be chosen as a basis for triangulation. This paper presents a new method of selecting these contour pixels. A new method for measuring skeletonization error is proposed, which quantifies the deviation of a skeleton segment from the true medial axis of a stroke in an image. The goal of the proposed algorithm is to reduce this error to an acceptable level, whilst retaining the superior efficiencies of previous non-pixel-based techniques. Experimental results show that the proposed method is adept at following the medial axis of an image, and is capable of producing a skeleton that is confirmed by a human's perception of the image. It is also computationally efficient and robust against noise.     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

Anisotropic surface meshing with conformal embedding

This paper introduces a parameterization-based approach for anisotropic surface meshing. Given an input surface equipped with an arbitrary Riemannian metric, this method generates a metric-adapted mesh with user-specified number of vertices. In the proposed method, the edge length of the input surface is directly adjusted according to the given Riemannian metric at first. Then the adjusted surface is conformally embedded into a parametric 2D domain and a weighted Centroidal Voronoi Tessellation and its dual Delaunay triangulation are computed on the parametric domain. Finally the generated Delaunay triangulation can be mapped from the parametric domain to the original space, and the triangulation exhibits the desired anisotropic property. We compute the high-quality remeshing results for surfaces with different types of topologies and compare our method with several state-of-the-art approaches in anisotropic surface meshing by using the standard measurement criteria.     

边缘优化算法在地质模型可视化系统中的应用

边缘优化算法是一种利用曲率自适应方法来解决曲面三角网格化的方法。此种方法应用于可变的约束Dlaunay三角网中，使用曲率区域来决定三角网络化的边是否具有可容性。深入研究了此种算法，并将此算法运用到地质模型可视化软件系统的设计中，取得很好的效果。     

基于Delaunay四面体剖分的网格分割算法

为了构建有意义曲面分片,提出一种基于Delaunay四面体剖分的网格分割算法.首先根据Delaunay四面体剖分得到多边形网格内部的四面体,求出每个面上反映网格内部信息的Delaunay体距离;然后对Delaunay体距离进行平滑处理,再对网格上面的Delaunay体距离进行聚类,用高斯混合模型对Delaunay体距离作柱状图的拟合,利用期望最大化算法来快速求得拟合结果;最后结合图切分技术,同时考虑聚类的结果、分割区域的边界平滑和视觉认知中的最小规则,得到最终的网格分割结果.实验结果表明,采用文中算法可以有效地实现有意义的网格分割.     

Robust segmentation and analysis of DNA microarray spots using an adaptative split and merge algorithm

Microarray images push to their limits classical analysis methods, since gene spots are often poorly contrasted, ill defined and of irregular shapes. These characteristics hinder a robust quantification of corresponding values for red and green intensities as well as their R/G ratio. New approaches are thus needed to ensure accurate data extraction from these images. Herein we present an automatic non-supervised algorithm for a fast and accurate spot data extraction from DNA microarrays. The method is based on a split and merge algorithm, relying on a Delaunay triangulation process, allowing an incremental partition of the image into homogeneous polygons. Geometric properties of triangles as well as homogeneity criteria are defined according to the specificities of microarray image signals. The method is first assessed on simulated data, and then compared with GenePix and Jaguar Softwares. Results in segmentation and quantification are superior to those obtained from a number of standard techniques for spot extraction.     

三维物体表面重建的分支处理算法研究

根据平面点集Delaunay三角剖分的特性,将Delaunay三角剖分应用到分支问题上,改进和实现了一种分支问题处理算法。将相邻层轮廓线投影到同一个剖面上形成一个带约束边的平面点集,并将它们Delaunay三角化,根据这些三角形组来生成新的轮廓线,使轮廓线一一对应。实验结果表明该算法实现的效果较符合实际情况,能有效地处理各种不同情况。     

An adaptive spatial clustering algorithm based on delaunay triangulation

In this paper, an adaptive spatial clustering algorithm based on Delaunay triangulation (ASCDT for short) is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases (i.e. an earthquake dataset in China) are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm.     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

Two Triangulation Methods Based on Edge Refinement

In this paper two curvature adaptive methods of surface triangulation are presented. Both methods are based on edge refinement to obtain a triangulation compatible with the curvature requirements. The first method applies an incremental and constrained Delaunay triangulation and uses curvature bounds to determine if an edge of the triangulation is admissible. The second method uses this function also in the edge refinement process, i.e. in the computation of the location of a refining point, and in the re-triangulation needed after the insertion of this refining point. Results are presented, comparing both approaches.     

基于面结构的三角化新方法

提出了一种三角剖分的新方法,该方法以面结构为基本数据结构,利用作者提出的广义交换算子,并且采用可控制三角形态的点插入策略,形成任意 域的三角剖分,该方法具有如下特点：算法的实现仅需单一的基于面的三角形数据结构,实现简单,数值稳定性好,可对包孤边的任意复非流平面域进行三角化,最后给出了实验结果。     

基于简化Mumford-Shah模型的水平集红外图像分割算法

由于红外图像大多具有目标模糊,对比度低的特点,传统的分割方法容易受到噪声和边界轮廓的影响而导致分割效果不佳,提出了一种基于简化Mumford-Shah模型的水平集红外图像分割算法.该算法能够通过将初始闭合曲线嵌入水平集函数,利用函数的求解从而达到图像分割的目的.仿真实验结果表明,该分割算法与初始轮廓线位置无关,受边界轮廓线和图像噪声的影响较小,具有较强的鲁棒性,在目标与背景灰度级差别较小的红外图像的分割中取得了较好的效果.