Voronoi图的栅格生成方法研究与分析.doc
《Voronoi图的栅格生成方法研究与分析.doc》由会员分享,可在线阅读,更多相关《Voronoi图的栅格生成方法研究与分析.doc(5页珍藏版)》请在三一文库上搜索。
1、Voronoi图的栅格生成方法研究与分析Voronoi图是一种空间分割算法。其是对空间中的n个离散点而言的,它将平面分割为n个区域,每个区域包括一个点,此区域是到该点距离最近的点的集合。由于Voronoi图具有最邻近性,邻接性等众多性质和完善的理论体系,其被广泛的应用在地理学、气象学、结晶学、航天、机器人等领域。Voronoi图的生成主要有矢量方法和栅格方法。矢量法中,典型的方法有增量法、分治法和间接法。分治法是一种递归方法,算法思路简单,但是很难在应用过程中实现动态更新。间接法则是根据其对偶图Delaunay三角网来构造Voronoi图,因此其性能的高低由所采用的Delaunay三角网的构造
2、算法所决定。增量法通过不断向已生成的Voronoi图中增加点来动态构建Voronoi图。相对于前两种方法,增量法构造简单并且容易实现动态化,所以被广泛应用。矢量方法的优势是生成Voronoi图精度高,但是存在存储复杂,生长元只能是点和线,以及难以向三维及高维空间扩展等问题。因此本文重点研究了Voronoi图的栅格生成方法,首先比较了常见的栅格方法生成Voronoi图的优缺点,然后结合CUDA的出现,提出一种基于GPU的 Voronoi图并行栅格生成算法。1 栅格法简介栅格方法生成Voronoi 图主要是将二值图像转化为栅格图像,然后确定各个空白栅格归属。主要方法有两类,一类以空白栅格为中心,计
3、算每个空白栅格到生长目标的距离,以确定其归属,常见的方法有代数距离变换法,逐个空白栅格确定法等;另一类以生长目标为中心,不断扩张生长目标的距离半径,填充其中的空白栅格,直到将整个图像填充完成,主要有圆扩张法,数学形态学距离变换法等。代数距离变换法对距离图像进行上行扫描(从上到下,从左到右)和下行扫描(从下向上,从右到左)两次扫描,计算出每个空白栅格最邻近的生长目标,以此生长目标作为其归属。此方法中栅格距离的定义直接影响了空白栅格的归属和Voronoi图的生成精度,通常使用的栅格距离定义有街区距离、八角形距离、棋盘距离等。距离变换的栅格生成方法精度低、耗时长,所需要花费的时间和栅格的数量成正比,
4、当栅格为nn大小时,其时间复杂度为O(nn)。圆检测法以生长目标为圆心,以一定的步长为初始半径,所有生长目标同时对其构成的圆内的空白栅格进行覆盖。通过不断扩大生长目标的半径,将会有越来越多的空白栅格被各个圆所覆盖,直到最终覆盖完整个图像。数学形态学距离变换法与圆检测法类似,其思想来源于数学形态学中膨胀操作,膨胀操作起到了扩大图像的效果,通过不断的对生长目标进行膨胀操作,最终扩张到所有的空白栅格。这两种方法有个共同的缺点,在每次扩张后,都需要判断整个栅格图像是否已完成扩张,而这需要遍历栅格图像,十分耗时。2 GPU下的栅格生成方法2.1 CUDA编程模型与GPUCUDA是一个并行编程模型和一个软
5、件编程环境,其采用了C语言作为编程语言,提供了大量的高性能计算指令开发能力,使开发者能够在GPU的强大计算能力上建立起一种更加高效的密集数据计算解决方案。CUDA将CPU作为主机端,GPU作为设备端,一个主机端可以有多个设备端。其采用CPU和GPU协同工作的方式,CPU主要负责程序中的串行计算的部分,GPU主要负责程序中的并行计算的部分。GPU上运行的代码被称为内核函数,其能够被GPU上内置的多个线程并行执行。一个完整的任务处理程序由 CPU端串行处理代码和GPU端并行内核函数共同构成。当CPU中执行到GPU代码时,其首先将相关数据复制到GPU中,然后调用GPU的内核函数,GPU中多个线程并行
6、执行此内核函数,当完成计算后,GPU端再把计算的结果返回给CPU,程序继续执行。通过将程序中耗时的且便于并行处理的计算转移到GPU中使用GPU并行处理,以提高整个程序的运行速度。CUDA是以线程网格(Grid),线程块(Block),线程(Thread)为三层的组织架构,每一个网格由多个线程块构成,而一个线程块又由多个线程构成,如图1所示。在GPU中,线程是并行运行的最小单元,由此可见,当存在大量的线程时,程序的并行程度将会十分高。目前的GPU上一个网格最多包含6553565535个线程块,而一个线程块通常有512个或1024个线程,所以理论上可以对6553565535512个栅格同时进行计算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Voronoi 栅格 生成 方法 研究 分析
链接地址:https://www.31doc.com/p-3274909.html