本文摘要：Voronoi图是一种空间拆分算法。其是对空间中的n个线性点而言的，它将平面拆分为n个区域，每个区域还包括一个点，此区域是到该点距离最近的点的子集。由于Voronoi图具备最附近性，相邻性等众多性质和完备的理论体系，其被普遍的应用于在地理学、气象学、结晶学、航天、机器人等领域。 Voronoi图的分解主要有矢量方法和栅格方法。矢量法中，典型的方法有增量法、共管法和间接法。 共管法是一种迭代方法，算法思路非常简单，但是很难在应用于过程中构建动态改版。

Voronoi图是一种空间拆分算法。其是对空间中的n个线性点而言的，它将平面拆分为n个区域，每个区域还包括一个点，此区域是到该点距离最近的点的子集。由于Voronoi图具备最附近性，相邻性等众多性质和完备的理论体系，其被普遍的应用于在地理学、气象学、结晶学、航天、机器人等领域。

　　Voronoi图的分解主要有矢量方法和栅格方法。矢量法中，典型的方法有增量法、共管法和间接法。

共管法是一种迭代方法，算法思路非常简单，但是很难在应用于过程中构建动态改版。间接法则是根据其对偶图Delaunay三角网来结构Voronoi图，因此其性能的强弱由所使用的Delaunay三角网的结构算法所要求。增量法通过大大向已分解的Voronoi图中减少点来动态建构Voronoi图。

相对于前两种方法，增量法结构非常简单并且更容易构建动态化，所以被广泛应用。矢量方法的优势是分解Voronoi图精度高，但是不存在存储简单，生长元不能是点和线，以及无法向三维及低维空间拓展等问题。

因此本文重点研究了Voronoi图的栅格分解方法，首先较为了少见的栅格方法分解Voronoi图的优缺点，然后融合CUDA的经常出现，明确提出一种基于GPU的Voronoi图分段栅格分解算法。　　1栅格法概述　　栅格方法分解Voronoi图主要是将二值图像转化成为栅格图像，然后确认各个空白栅格归属于。主要方法有两类，一类以空白栅格为中心，计算出来每个空白栅格到生长目标的距离，以确认其归属于，少见的方法有代数距离转换法，逐一空白栅格确认法等；另一类以生长目标为中心，大大扩展生长目标的距离半径，填满其中的空白栅格，直到将整个图像填满已完成，主要有圆扩展法，数学形态学距离转换法等。

代数距离转换法对距离图像展开下行扫瞄（从上到下，从左到右）和上行扫瞄（从下向上，从右到左）两次扫瞄，计算出来出有每个空白栅格最附近的生长目标，以此生长目标作为其归属于。此方法中栅格距离的定义直接影响了空白栅格的归属于和Voronoi图的分解精度，一般来说用于的栅格距离定义有街区距离、八角形距离、棋盘距离等。

距离转换的栅格分解方法精度较低、耗时宽，所必须花费的时间和栅格的数量成正比，当栅格为nn大小时，其时间复杂度为O（nn）。圆检测法以生长目标为圆心，以一定的步长为初始半径，所有生长目标同时对其包含的圆内的空白栅格展开覆盖面积。通过不断扩大生长目标的半径，将不会有更加多的空白栅格被各个圆所覆盖面积，直到最后覆盖面积原始个图像。

数学形态学距离转换法与圆检测法类似于，其思想源于数学形态学中收缩操作者，收缩操作者起着了不断扩大图像的效果，通过大大的对生长目标展开收缩操作者，最后扩展到所有的空白栅格。这两种方法有个联合的缺点，在每次扩展后，都必须辨别整个栅格图像否已完成扩展，而这必须迭代栅格图像，十分耗时。

　　2GPU下的栅格分解方法　　2.1CUDA编程模型与GPU　　CUDA是一个分段编程模型和一个软件编程环境，其使用了C语言作为编程语言，获取了大量的高性能计算出来指令研发能力，使开发者需要在GPU的强劲计算能力上创建起一种更为高效的密集数据计算出来解决方案。　　CUDA将CPU作为主机末端，GPU作为设备末端，一个主机末端可以有多个设备末端。其使用CPU和GPU协同工作的方式，CPU主要负责管理程序中的串行计算出来的部分，GPU主要负责管理程序中的并行计算的部分。GPU上运营的代码被称作内核函数，其需要被GPU上内置的多个线程并行执行。

一个原始的任务处理程序由CPU末端串行处置代码和GPU末端分段内核函数联合包含。当CPU中继续执行到GPU代码时，其首先将涉及数据读取GPU中，然后调用GPU的内核函数，GPU中多个线程并行执行此内核函数，当已完成计算出来后，GPU末端再行把计算出来的结果回到给CPU，程序继续执行。通过将程序中耗时的且便于并行处理的计算出来移往到GPU中用于GPU并行处理，以提升整个程序的运营速度。CUDA是以线程网格（Grid），线程块（Block），线程（Thread）为三层的的组织架构，每一个网格由多个线程块包含，而一个线程块又由多个线程包含，如图1右图。

在GPU中，线程是分段运营的大于单元，由此可见，当不存在大量的线程时，程序的分段程度将不会十分低。

本文关键词：基于,GPU,的,并行,Voronoi,图,栅格,生成,算法,开云体育全站app下载

本文来源：开云体育全站app下载-www.jinliyuanstone.com