EDN China > 设计实例 > 微处理器与DSP > CPU/GPU > 正文
? 2016博客大赛-不限主题,寻找电子导师,大奖升级??

基于GPU的并行Voronoi图栅格生成算法

屠文森?? 汪佳佳?? 南京理工大学 现代电子技术?? 2015年07月10日 ?? 收藏0
Voronoi图是一种空间分割算法。其是对空间中的n 个离散点而言的,它将平面分割为n 个区域,每个区域包括一个点,此区域是到该点距离最近的点的集合。由于Voronoi图具有最邻近性,邻接性等众多性质和完善的理论体系,其被广泛的应用在地理学、气象学、结晶学、航天、机器人等领域。

Voronoi图的生成主要有矢量方法和栅格方法。矢量法中,典型的方法有增量法、分治法和间接法。分治法是一种递归方法,算法思路简单,但是很难在应用过程中实现动态更新。间接法则是根据其对偶图Delaunay三角网来构造Voronoi图,因此其性能的高低由所采用的Delaunay三角网的构造算法所决定。增量法通过不断向已生成的Voronoi图中增加点来动态构建Voronoi图。相对于前两种方法,增量法构造简单并且容易实现动态化,所以被广泛应用。矢量方法的优势是生成Voronoi图精度高,但是存在存储复杂,生长元只能是点和线,以及难以向三维及高维空间扩展等问题。因此本文重点研究了Voronoi图的栅格生成方法,首先比较了常见的栅格方法生成Voronoi图的优缺点,然后结合CUDA的出现,提出一种基于GPU的Voronoi图并行栅格生成算法。

1 栅格法简介

栅格方法生成Voronoi图主要是将二值图像转化为栅格图像,然后确定各个空白栅格归属。主要方法有两类,一类以空白栅格为中心,计算每个空白栅格到生长目标的距离,以确定其归属,常见的方法有代数距离变换法,逐个空白栅格确定法等;另一类以生长目标为中心,不断扩张生长目标的距离半径,填充其中的空白栅格,直到将整个图像填充完成,主要有圆扩张法,数学形态学距离变换法等。代数距离变换法对距离图像进行上行扫描(从上到下,从左到右)和下行扫描(从下向上,从右到左)两次扫描,计算出每个空白栅格最邻近的生长目标,以此生长目标作为其归属。此方法中栅格距离的定义直接影响了空白栅格的归属和Voronoi图的生成精度,通常使用的栅格距离定义有街区距离、八角形距离、棋盘距离等。距离变换的栅格生成方法精度低、耗时长,所需要花费的时间和栅格的数量成正比,当栅格为n×n 大小时,其时间复杂度为O(n×n)。圆检测法以生长目标为圆心,以一定的步长为初始半径,所有生长目标同时对其构成的圆内的空白栅格进行覆盖。通过不断扩大生长目标的半径,将会有越来越多的空白栅格被各个圆所覆盖,直到最终覆盖完整个图像。数学形态学距离变换法与圆检测法类似,其思想来源于数学形态学中膨胀操作,膨胀操作起到了扩大图像的效果,通过不断的对生长目标进行膨胀操作,最终扩张到所有的空白栅格。这两种方法有个共同的缺点,在每次扩张后,都需要判断整个栅格图像是否已完成扩张,而这需要遍历栅格图像,十分耗时。

2 GPU下的栅格生成方法

2.1 CUDA编程模型与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上一个网格最多包含65535×65535 个线程块,而一个线程块通常有512 个或1024 个线程,所以理论上可以对65535×65535×512个栅格同时进行计算。

【分页导航】


上一页123下一页
?? ?? ??


打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

1.扫描左侧二维码
2.点击右上角的分享按钮
3.选择分享给朋友
?? ??

Voronoi图? 栅格法? GPU? CUDA?

相关文章

我来评论
美国的游客
美国的游客 ??? (您将以游客身份发表,请登录 | 注册)
?
有问题请反馈