关于k(1≤k＜n)阶Voronoi图生成算法的研究

k( 1≤k 相似文献   

基于Voronoi k阶邻近的目标预警预报方法

利用Voronoi图实现对气象服务区域的划分,提出基于Voronoi k阶邻近的目标预警预报方法,以某目标为中心构造Voronoi k阶邻近,监视k阶邻近区域内的天气实况,发生危险天气立即发出警报,并报告危险天气的影响权重、危险等级和到达中心目标的时间。给出具体的算法实现以及时间和空间性能分析,实验结果验证了该方法的可行性和适用性。     

基于MapReduce的加权Voronoi图并行算法设计及应用

针对大规模数据的加权Voronoi图实现的复杂性和计算精度低问题, 采用欧氏距离法, 设计和实现了一种基于MapReduce编程模型的并行栅格加权Voronoi图的生成算法, 并将其成功应用于石家庄桥东区超市的推荐服务。该算法计算精度高, 同时可适用于任意点、线、面及复合发生元的加权Voronoi图的计算。实验结果表明, 算法在处理大规模栅格数据时能明显提高栅格Voronoi图的生成速度, 并能为用户推荐综合因素优选的超市。     

基于动态创建局部Voronoi图的连续近邻查询

在充分认识到k阶Voronoi图在解决连续k个近邻查询优越性和现实不可行性的基础上,用分支限界的思想去界定预创建Voronoi图生成点范围的上界,提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。该方法只是在给定查询段上所有点的k个近邻范围上界内创建一个局部的k阶Voronoi图,这样大大降低了基于Voronoi图的连续k近邻查询的代价。     

基于Voronoi K阶邻近图的半监督学习自动图像标注

在为自动图像标注构建相似图的过程中,针对传统的方法是基于图像间的视觉相似性,其没有考虑到数据集中某个子数据集内的结构信息这一问题,提出一种基于Voronoi k阶邻近图的半监督学习自动图像标注方法。该方法充分考虑Voronoi k阶邻近图能很好地表达空间目标的影响区域以及可以方便地进行空间邻近的描述与推理的特性,将特征空间内的图像数据点分布信息融合到点对间的相似度量表示中,利用未标注样本挖掘图像特征的内在规律,然后把半监督学习的方法和多标记学习有效结合起来,从而达到对图像进行自动标注。实验结果表明,提出的标注方法可行,同时标注结果与传统的标注方法相比得到了明显改善。     

小型移动机器人自主返航路径规划方法

针对遥控小型移动机器人在自主返航实际应用中定位精度低等问题,提出一种小型移动机器人自主返航路径规划方法.介绍小型移动机器人的任务流程及硬件系统,利用膨胀算子对栅格地图中的障碍物进行运算得到栅格Voronoi图.使用双边界路径矢量化方法从栅格Voronoi图中提取出矢量路径,并对该路径进行拓扑优化.通过Dijkstra算法对拓扑路径进行路径规划并进行算法验证.实验结果表明,该方法所得路径可使环境中的机器人与障碍物之间的距离最大化,并使移动机器人的运动轨迹具有较高的可执行性,提高了小型移动机器人自主返航的成功率.     

连续近邻查询方法的研究

连续近邻查询(CNN)要检索一给定查询线段上每一点的近邻。它是时空数据库中一种重要的查询类型,在智能交通系统中有着广泛的应用。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文从文献得到启示:用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

用户频繁通信关系的并行挖掘算法研究

随着移动通信技术和互联网的飞速发展,移动通信设备已经成为大多数人随身携带的工具,这些设备之间因互相通信而产生的数据构成了通信网络。文中提出了一种针对海量通信数据的频繁通信子图并行挖掘算法PMFCS。该算法 在频繁项目集挖掘思想和子图连接规则的基础上, 利用并行计算框架Spark 将所有的图以边为单位分布到各个计算节点,在各个节点统计1阶候选频繁子图,再通过汇总候选子图得到1阶频繁子图。PMFCS算法通过迭代地连接k－1阶子图和1阶子图生成k阶候选子图,再计算k阶候选子图的频繁度,直至k阶频繁子图集合为空集。实验结果表明,该算法可以快速、有效地解决频繁通信关系的挖掘问题。     

一种大规模矢量地图数据实时简化的方法

提出利用帧缓存和Voronoi图实现大规模矢量地图的快速简化以及用模板缓存剔除Voronoi图中因自相交而重叠的区域,避免了简化后要素间错误相交、自相交,点线位置改变和多边形邻接关系改变的拓扑错误,有效保持了简化前后拓扑关系的一致性。该方法的简化时间复杂度始终控制在一定范围内。该研究有助于提高多尺度、大尺度矢量数据融合的精度和效率。     

一种平面点集Voronoi 图的细分算法

Voronoi 图是计算几何中的重要概念之一,在计算机图形学、计算几何、 计算机辅助几何设计、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究 中得到广泛应用。借助于四叉树和区间算术,提出了一种新的构造平面点集Voronoi 图的细 分算法, 并且和经典的增量算法、栅格扩张法进行了比较, 结果显示新细分算法更为有效。 最重要的是细分算法原理简单,很容易编程实现。     

Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS

A Voronoi diagram is an interdisciplinary concept that has been applied to many fields. In geographic information systems (GIS), existing capabilities for generating Voronoi diagrams normally focus on ordinary (not weighted) point (not linear or area) features. For better integration of Voronoi diagram models and GIS, a raster-based approach is developed, and implemented seamlessly as an ArcGIS extension using ArcObjects. In this paper, the methodology and implementation of the extension are described, and examples are provided for ordinary or weighted point, line, and polygon features. Advantages and limitations of the extensions are also discussed. The extension has the following features: (1) it works for point, line, and polygon vector features; (2) it can generate both ordinary and multiplicatively weighted Voronoi diagrams in vector format; (3) it can assign non-spatial attributes of input features to Voronoi cells through spatial joining; and (4) it can produce an ordinary or a weighted Euclidean distance raster dataset for spatial modeling applications. The results can be conveniently combined with other GIS datasets to support both vector-based spatial analysis and raster-based spatial modeling.     

Voronoi tessellation of points with integer coordinates: Time-efficient implementation and online edge-list generation

The Voronoi tessellation in the plane can be computed in a particularly time-efficient manner for generators with integer coordinates, such as typically acquired from a raster image. The Voronoi tessellation is constructed line by line during a single scan of the input image, simultaneously generating an edge-list data structure (DCEL) suitable for postprocessing by graph traversal algorithms. In contrast to the generic case, it can be shown that the topology of the grid permits the algorithm to run faster on complex scenes. Consequently, in Computer Vision applications, the computation of the Voronoi tessellation represents an attractive alternative to raster-based techniques in terms of both computational complexity and quality of data structures.     

MapReduce模型下Voronoi图栅格生成算法

针对"海量"点组成的平面点集Voronoi图栅格生成算法的效率问题,对其进行易并行性抽象,提出了一种MapReduce模型下基于欧氏距离的Voronoi图栅格生成算法,该算法采用三个MapReduce Job来实现。在第一个MapReduce Job中,将栅格按照隶属代码进行归属分类。在第二个MapReduce Job中,将新数据按照其对应的行号进行归类。在第三个MapReduce Job中,并行生成全局有序的Voronoi图部分文件,并连接各个部分文件,生成最终的Voronoi图。在多个不同大小数据集上的实验结果表明,这种MapReduce模型下的算法部署在Hadoop集群上运行具有较好的加速比和扩展性。     

IStar: a raster representation for scalable image and volume data

Topology has been an important tool for analyzing scalar data and flow fields in visualization. In this work, we analyze the topology of multivariate image and volume data sets with discontinuities in order to create an efficient, raster-based representation we call IStar. Specifically, the topology information is used to create a dual structure that contains nodes and connectivity information for every segmentable region in the original data set. This graph structure, along with a sampled representation of the segmented data set, is embedded into a standard raster image which can then be substantially downsampled and compressed. During rendering, the raster image is upsampled and the dual graph is used to reconstruct the original function. Unlike traditional raster approaches, our representation can preserve sharp discontinuities at any level of magnification, much like scalable vector graphics. However, because our representation is raster-based, it is well suited to the real-time rendering pipeline. We demonstrate this by reconstructing our data sets on graphics hardware at real-time rates.     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

改进的MKM算法及其在语音识别中的应用

提出了一种用于矢量量化的改进的聚类算法,该算法在MKM(Modified K-Means)算法的框架的基础上,对初始码本的生成、失真测度的选择、非典型胞腔的处理等方面进行了改进,从而减少了原算法在能量和增益上对聚类结果的影响。并将该算法应用于波形编辑孤立字识别器,这种识别器直接对语音样本的时域波形进行训练和聚类,不需要提取语音参数,算法复杂度较低,加上提出的聚类算法失真测度简单易实现,对芯片的运算能力要求不高,非常适用于有低成本要求的语音识别器场合。通过中文元音字识别的实验证明,在相同码本尺寸下,运用改进后的聚类算法的识别器的识别率有所提高。     

基于Voronoi图的有障碍物空间聚类

Voronoi图具有侧向临近特性，可以方便表达空间临近关系。根据这一性质，解决在空间数据聚类分析中的有实体障碍物所面临的问题。通过生成考虑实体障碍物的Voronoi图，建立Voronol图的距离度量方法，提出采用循障碍物求距离法，可以方便地完成有障碍物的空间聚类分析。该方法使得有实体障碍物情况下空间聚类更加准确，并通过实验进行验证。