Implications of Weighting Metrics for Line Generalization with Visvalingam's Algorithm

Visvalingam's algorithm was designed for caricatural line generalization. A distinction must be made between the algorithm and its operational definition, which includes the metric used to drive it. When the algorithm was first introduced, it was demonstrated using the concept of the effective area of triangles. It was noted that alternative metrics could be used and that the metrics could be weighted, for example to take account of shape.

Ordnance Survey (Great Britain) and others are using Visvalingam's algorithm for generalizing coastlines and other natural features, with complex parameter-driven functions to weight the original metric. This paper shows how free software and data were used to scrutinize the implications of one of Matthew Bloch's simple and transparent weighting functions. The results look promising, when compared with manually produced mid and small-scale maps; and encourage further research focussed on weighting functions and related topics, such as self-intersection of lines and model-based generalization. The paper discusses why weights were used in some projects. It comments on their range of applicability and reiterates the original guidance provided for the use of weights. It also demonstrates how weights can undermine the algorithm's capacity to draw caricatures with very few points. The paper provides sufficient background and links to the authors’ test data and to open source software for the benefit of others wishing to undertake research in line generalization using Visvalingam's algorithm.     

一种顾及空间关系约束的线化简算法

线要素化简在制图表达与综合领域一直是研究的热点和难点之一。然而,经典化简算法多针对单独线要素进行处理,缺乏对该线要素与周边线要素之间整体空间关系的考虑,并且,存在计算结果生硬(D-P算法)、局部极值点缺失,特别是在曲度较大之处出现相交异常(L-O算法)等问题。为此,本文提出一种顾及空间关系约束的线化简算法,建立线要素全局化简方法(LGSM)和矢量位移、面积位移等5类评价指标。采用等高线、河流和道路3类线要素实际数据进行了试验,充分检验了本文算法的优越性,其处理结果符合开方根模型规律,降低了曲线复杂度,在保证全局空间关系不变条件下,不仅更好地保持了曲线整体形状特征,而且光滑美观、精度高。     

A Computer Science Perspective on the Bendsimplification Algorithm

The primary aim of this study was to evaluate whether the use of bends provides a better basis than point elimination for research on line structuring. These investigations were undertaken using Arc/Info 7.1.1. Comparative experimental results suggest that the algorithm may not be as widely applicable as the much simpler geometric filters, such as the Douglas-Peucker or Visvalingam algorithms. The paper therefore provides a brief review of these three algorithms. A more detailed conceptual and empirical evaluation of the bendsimplification system follows, highlighting some problems with implementing the system in Arc/Info. The paper then questions the value of over-coupling model- and image-oriented generalization processes within the black-box bendsimplification system. It suggests the type of parameters which could enhance the utility and usability of the Bendsimplify option within the Arc/Info (and perhaps also within the ArcView) environment and provides some pointers for further research. With respect to the main aim of the research, the evidence suggests that bendsimplification is less useful for line segmentation than Visvalingam's algorithm. Further research is needed to assess the value of the iterative bend elimination operator within bendsimplification.     

Line generalisation by repeated elimination of points

Abstract

This paper presents a new approach to line generalisation which uses the concept of 'effective area' for progressive simplification of a line by point elimination. Two coastlines are used to compare the performance of this, with that of the widely used Douglas-Peucker, algorithm. The results from the area-based algorithm compare favourably with manual generalisation of the same lines. It is capable of achieving both imperceptible minimal simplifications and caricatural generalisations. By careful selection of cut-off values, it is possible to use the same algorithm for scale-dependent and scale-independent generalisations. More importantly, it offers scope for modelling cartographic lines as consisting of features within features so that their geometric manipulation may be modified by application- and/or user-defined rules and weights. The paper examines the merits and limitations of the algorithm and the opportunities it offers for further research and progress in the field of line generalisation.     

利用质心Voronoi图对地形自适应简化的算法

地形简化算法利用少量有效的地形信息表达整体地形,能很好地解决海量地形数据与计算机硬件之间的矛盾,同时满足多尺度地形应用需求。针对现有地形简化算法难以兼顾局部地形起伏与地形整体特征的问题,提出一种基于质心Voronoi图的地形自适应简化算法。首先,利用质心Voronoi图的特点,以地形起伏度作为密度函数生成质心Voronoi图;然后,利用分布在地形起伏较大区域的质心Voronoi图种子点及大多分布在地形特征线上的Voronoi区域顶点重构地形;最后,通过原始地形与重构地形的特征线验证地形简化的效果,并与三维道格拉斯-普克（3D DouglasPeucker,3D DP）算法进行精度对比。实验结果表明,从简化地形中提取的山脊线、山谷线、等高线等地形特征线与原始地形的重叠度均较高,算法能较好地保持地形整体特征;且在相同的简化级别下,算法的简化误差小于3D DP算法,具有较高的地形简化精度。     

Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation

A new method of cartographic line simplification is presented. Regular hexagonal tessellations are used to sample lines for simplification, where hexagon width, reflecting sampling fidelity, is varied in proportion to target scale and drawing resolution. Tesserae constitute loci at which new sets of vertices are defined by vertex clustering quantization, and these vertices are used to compose simplified lines retaining only visually resolvable detail at target scale. Hexagon scaling is informed by the Nyquist–Shannon sampling theorem. The hexagonal quantization algorithm is also compared to an implementation of the Li–Openshaw raster-vector algorithm, which undertakes a similar process using square raster cells. Lines produced by either algorithm using like tessera widths are compared for fidelity to the original line in two ways: Hausdorff distances to the original lines are statistically analyzed, and simplified lines are presented against input lines for visual inspection. Results show that hexagonal quantization offers advantages over square tessellations for vertex clustering line simplification in that simplified lines are significantly less displaced from input lines. Visual inspection suggests lines produced by hexagonal quantization retain informative geographical shapes for greater differences in scale than do those produced by quantization in square cells. This study yields a scale-specific cartographic line simplification algorithm, following Li and Openshaw's natural principle, which is readily applicable to cartographic linework. Open-source Java code implementing the hexagonal quantization algorithm is available online.     

建筑物形状特征分析表达与自适应化简方法EI北大核心CSCD

建筑物化简是地图制图领域关注的热点问题之一。集成不同算法构建形状特征自适应的化简模型是应对建筑物多样化形态的有效策略,但当前相关研究主要从局部结构模式或化简结果评价展开,缺乏对形状结构的整体分析视角和深层次认知。本文提出一种深度学习支持下的形状自适应建筑物化简方法。首先,利用图卷积自编码网络对建筑物形状进行深度认知,提取隐含在边界节点分布中的形状特征并进行编码表达;然后,通过监督学习方法建立形状编码与化简算法之间的映射关系,从而实现依据输入建筑物的形状特征选择适宜化简算法的自适应机制。试验表明,本文方法的化简结果在位置、方向、面积和形状保持指标上总体优于单一算法,具备较好的理论与应用价值。     

矢量地图数据简化研究进展

从传统矢量数据简化算法及基于并行技术的矢量数据简化算法两方面进行分析,将当前传统的矢量数据简化算法:Douglas-Peuker的简化算法及演化、Li-OpenShaw简化算法及演化、渐进式的简化算法及演化、基于小波理论的简化算法及演化和简化质量的评价,在基于并行技术简化算法研究的基础上,指出矢量数据并行简化和简化算法的智能化、感知化、自动化是矢量数据简化研究发展的趋势。     

基于交叉点的道路曲线化简算法研究

现有的曲线化简算法不能很好地化简具有交叉路口的道路曲线,针对这一问题提出一种基于交叉点的道路曲线化简算法。算法分为预化简和修正化简两个阶段:首先识别并得到曲线上的分段点,利用相邻的分段点作为道格拉斯-普克算法的首尾点对曲线进行化简,得到预化简的结果;然后对于交叉点引入偏差阈值ε,通过判断道路曲线交叉点与化简后交叉点的距离与偏差精度ε的大小关系来确定该交叉点的化简与保留,如果保留或者化简后的道路曲线没有交叉点那么将原交叉点作为分段点对此段曲线进行重新化简。理论分析与实验结果表明,文中算法能够有针对性地保留或化简道路交叉点以及保持曲线化简后的形态特征。     

基于点删除的TIN简化算法改进

摘要： 三角网格模型的简化在三维建模过程中占有很重要的地位。本文通过系统研究目前常用的三角网简化算法，归纳总结出了各主要算法的优缺点与适用范围。文中重点选择了一种适用性比较广的基于点删除的TIN简化算法，并将它应用于实际的三维地形模型简化当中，在实际工作中检验它的实用性。根据三维地形数据量大、精度要求具层次感的特点，对原算法做了一些修改，在保证简化模型细节损失在误差控制范围内的情况下，使得算法简化效率更高。     

小波分析在空间数据处理中的应用研究

在GIS中,海量数据的处理问题一直是个难题,如果解决了海量数据的网上传输,则在WebGIS中就可以实现大范围矢量影像叠加漫游及大范围地形三维浏览飞行展示。在研究基于小波系数的地形、DEM及影像简化方法的基础上,提出了一种基于小波变换的大规模地进行简化算法;其思路是先将大地形、影像分块管理并作小波变换,然后根据视野从中提取可见的一组子块,最后基于小波系数进行简化并绘制地形和影像。试验结果证实了小波分析方法对地形简化的有效性。在数据处理过程中,对小波变换处理过程进行了优化和改进。     

基于网格模型的导航道路图渐进式化简方法

针对将导航数据精度降低时的道路图形综合转换为基于网格模型的线图形化简问题,提出了一种基于网格模型的导航道路数据渐进式协同图形综合方法。该方法能保证综合后的单条道路和道路网都与原始高精度数据保持空间方向关系相似。在数据处理过程中,用导航需求来约束道路的渐进式图形简化,并对道路形状和道路交叉处的空间方向关系进行维护,顾及了导航中道路的可视化效果。已用实际生产中的导航数据进行了验证,证明了本文方法是有效且实用的。     

线要素化简算法的时间复杂度分析

线状要素是地图中数量最大、要素类型最多样的要素,其化简在地图自动综合中占据了重要的地位.目前对线状要素化简算法的改进、化简质量、化简精度等方面的研究较多,对线状要素化简算法的效率研究较少.此处是在兼顾化简质量的前提下研究算法效率,通过分析化简算法约束参数的特征,将线状要素化简算法分为6类,选取其中的几个典型算法,分析了其时间复杂度,并按照线状要素化简算法的时间复杂度将其分为线性算法和非线性算法两类,初步探讨了适合这两类算法的并行计算方法.     

基于层次信息量的线要素化简算法性能评价研究

化简算法是地图综合的一类基本算法,而算法性能评价是解决算法优化和算法选取的一个重要问题。现有评价指标更多地考虑要素化简前后的位置偏移,难以客观地评价算法性能。为此,本文以线要素为例,全面考虑线要素化简原则,从信息传递的角度,提出一种基于层次信息量的线要素化简算法性能评价方法。首先将线要素的信息划分为三个层次来描述,即：元素层次、邻域层次和整体层次,并发展相应的信息量计算方法。然后,从化简后各层次信息量的保持能力（或信息传递能力）来评价线要素化简算法的性能。其中,元素层次信息传递比评价关键点保持性能;邻域层次信息传递比评价弯曲保持性能;整体层次信息传递比评价整体形态保持性能。最后,以河网为例,采用层次信息量指标,对四种经典化简算法进行评价,分析验证了层次信息量评价指标的合理性,与经典评价指标的对比分析进一步验证了该指标的优越性。     

化简方法在线要素匹配中的应用及性能评估

多源同名线要素数据局部细节差异较大,但整体形态基本上是一致的,化简算法可以删除线要素的局部细节,提取其主要形态,从而有助于匹配算法提升匹配正确率。不同化简算法的化简效果存在差异,提升匹配正确率的效果也存在差异。本文提出了利用线要素匹配来评估化简算法性能的方法。首先,阐述了动态化简带动动态匹配的方法和过程;其次,采用3种不同的化简算法进行试验,验证了所提方法提高已有匹配算法匹配正确率的有效性,以及对化简算法的普遍适用性;最后,根据加入3种化简算法的不同匹配结果,从匹配的角度对化简算法适用性进行了比较评估。     

Morse理论支持下的建筑物点云特征提取

针对传统特征提取算法的结果存在交叉紊乱、不连续、缺少拓扑关系等问题,本文提出了基于Morse理论的建筑物点云特征提取算法。首先定义三维表面模型上顶点的Morse函数指标;然后采用邻点比较法自动提取特征点;最后针对Morse-Smale复形的对偶性在建筑物拓扑特征中已无实际意义的问题,提出了单复形拓扑模型的提取与简化算法。试验结果表明,该算法能够获得清晰、连续、完整的建筑物特征线,实现对建筑物模型表面的完全分割;简化算法在保证建筑物特征线拓扑一致性的前提下,可以获取不同层次的建筑物拓扑特征,为建筑物模型的重建与可视化提供了保障。     

图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用

为充分利用已有化简成果及其蕴含的化简知识,本文集成几种机器学习算法提出图形、图像融合利用的智能化简方法,实现顶点取舍决策的学习和优化。首先,分别利用全连接神经网络和卷积神经网络设计、构建基于图形的顶点取舍模型和基于图像的顶点取舍模型,通过样本训练各模型拟合从图形特征到顶点取舍和从栅格图像到顶点取舍的映射;然后,基于线性加权、朴素贝叶斯、支持向量机、人工神经网络构建多种融合决策模型,实现基于图形和基于图像的顶点取舍的融合利用;最后,通过试验用例对所有模型进行测试。试验结果表明：基于图形和基于图像的顶点取舍模型在一定程度上学习、掌握了化简算子,融合利用后还能进一步提高化简准确性、实现优势互补。     

基于正对投影距离的双线道路提取方法

大比例尺地图中双线道路的识别与提取是路网综合的重要组成部分。针对双线道路识别问题,根据双线道路的结构特点,结合国内外研究提出了一种可用于提取双线道路的距离度量方法——正对投影距离。首先通过缓冲区分析构建可能构成双线道路的候选线对集,然后利用正对投影距离构造约束参数从线对候选集中精确识别出双线道路线对。通过与其他距离度量方法的对比试验,表明正对投影距离能较准确表达双线道路线对的空间邻近性,可以准确识别出双线道路,符合人类空间认知特点。     

地理信息系统中动态分段技术的研究

动态分段是一种新的线性特征的动态分析、显示和绘图技术。本文结合ＧＩＳ在公路信息管理领域的应用，论述了动态分段技术产生的根源，动态分段数据库的特点及实现动态分段的算法。以空间数据库和属性数据库的双向查询为例，说明了动态分段技术的具体应用，它的有关算法及命令格式。     

规则格网DEM化简的一种改进方法

分析了从较高分辨率DEM化简到较低分辨率DEM的地形简化方法的优缺点,提出了考虑整体地形特征信息的一种改进方法,实现了改进后的方法具有较好的简化效果。