基于GPU的并行Voronoi圖柵格生成算法

Voronoi圖是一種空間分割算法。其是對空間中的n個離散點而言的，它將平面分割為n個區(qū)域，每個區(qū)域包括一個點，此區(qū)域是到該點距離最近的點的集合。由于Voronoi圖具有最鄰近性，鄰接性等眾多性質(zhì)和完善的理論體系，其被廣泛的應(yīng)用在地理學(xué)、氣象學(xué)、結(jié)晶學(xué)、航天、機器人等領(lǐng)域。

Voronoi圖的生成主要有矢量方法和柵格方法。矢量法中，典型的方法有增量法、分治法和間接法。分治法是一種遞歸方法，算法思路簡單，但是很難在應(yīng)用過程中實現(xiàn)動態(tài)更新。間接法則是根據(jù)其對偶圖Delaunay三角網(wǎng)來構(gòu)造Voronoi圖，因此其性能的高低由所采用的Delaunay三角網(wǎng)的構(gòu)造算法所決定。增量法通過不斷向已生成的Voronoi圖中增加點來動態(tài)構(gòu)建Voronoi圖。相對于前兩種方法，增量法構(gòu)造簡單并且容易實現(xiàn)動態(tài)化，所以被廣泛應(yīng)用。矢量方法的優(yōu)勢是生成Voronoi圖精度高，但是存在存儲復(fù)雜，生長元只能是點和線，以及難以向三維及高維空間擴展等問題。因此本文重點研究了Voronoi圖的柵格生成方法，首先比較了常見的柵格方法生成Voronoi圖的優(yōu)缺點，然后結(jié)合CUDA的出現(xiàn)，提出一種基于GPU的 Voronoi圖并行柵格生成算法。

1 柵格法簡介

柵格方法生成Voronoi 圖主要是將二值圖像轉(zhuǎn)化為柵格圖像，然后確定各個空白柵格歸屬。主要方法有兩類，一類以空白柵格為中心，計算每個空白柵格到生長目標的距離，以確定其歸屬，常見的方法有代數(shù)距離變換法，逐個空白柵格確定法等;另一類以生長目標為中心，不斷擴張生長目標的距離半徑，填充其中的空白柵格，直到將整個圖像填充完成，主要有圓擴張法，數(shù)學(xué)形態(tài)學(xué)距離變換法等。代數(shù)距離變換法對距離圖像進行上行掃描(從上到下，從左到右)和下行掃描(從下向上，從右到左)兩次掃描，計算出每個空白柵格最鄰近的生長目標，以此生長目標作為其歸屬。此方法中柵格距離的定義直接影響了空白柵格的歸屬和Voronoi圖的生成精度，通常使用的柵格距離定義有街區(qū)距離、八角形距離、棋盤距離等。距離變換的柵格生成方法精度低、耗時長，所需要花費的時間和柵格的數(shù)量成正比，當柵格為n×n大小時，其時間復(fù)雜度為O(n×n)。圓檢測法以生長目標為圓心，以一定的步長為初始半徑，所有生長目標同時對其構(gòu)成的圓內(nèi)的空白柵格進行覆蓋。通過不斷擴大生長目標的半徑，將會有越來越多的空白柵格被各個圓所覆蓋，直到最終覆蓋完整個圖像。數(shù)學(xué)形態(tài)學(xué)距離變換法與圓檢測法類似，其思想來源于數(shù)學(xué)形態(tài)學(xué)中膨脹操作，膨脹操作起到了擴大圖像的效果，通過不斷的對生長目標進行膨脹操作，最終擴張到所有的空白柵格。這兩種方法有個共同的缺點，在每次擴張后，都需要判斷整個柵格圖像是否已完成擴張，而這需要遍歷柵格圖像，十分耗時。

2 GPU下的柵格生成方法

2.1 CUDA編程模型與GPU

CUDA是一個并行編程模型和一個軟件編程環(huán)境，其采用了C語言作為編程語言，提供了大量的高性能計算指令開發(fā)能力，使開發(fā)者能夠在GPU的強大計算能力上建立起一種更加高效的密集數(shù)據(jù)計算解決方案。

CUDA將CPU作為主機端，GPU作為設(shè)備端，一個主機端可以有多個設(shè)備端。其采用CPU和GPU協(xié)同工作的方式，CPU主要負責(zé)程序中的串行計算的部分，GPU主要負責(zé)程序中的并行計算的部分。GPU上運行的代碼被稱為內(nèi)核函數(shù)，其能夠被GPU上內(nèi)置的多個線程并行執(zhí)行。一個完整的任務(wù)處理程序由 CPU端串行處理代碼和GPU端并行內(nèi)核函數(shù)共同構(gòu)成。當CPU中執(zhí)行到GPU代碼時，其首先將相關(guān)數(shù)據(jù)復(fù)制到GPU中，然后調(diào)用GPU的內(nèi)核函數(shù)，GPU中多個線程并行執(zhí)行此內(nèi)核函數(shù)，當完成計算后，GPU端再把計算的結(jié)果返回給CPU，程序繼續(xù)執(zhí)行。通過將程序中耗時的且便于并行處理的計算轉(zhuǎn)移到GPU中使用GPU并行處理，以提高整個程序的運行速度。CUDA是以線程網(wǎng)格(Grid)，線程塊(Block)，線程(Thread)為三層的組織架構(gòu)，每一個網(wǎng)格由多個線程塊構(gòu)成，而一個線程塊又由多個線程構(gòu)成，如圖1所示。在GPU中，線程是并行運行的最小單元，由此可見，當存在大量的線程時，程序的并行程度將會十分高。目前的GPU上一個網(wǎng)格最多包含65535×65535個線程塊，而一個線程塊通常有512個或1024個線程，所以理論上可以對65535×65535×512個柵格同時進行計算。

2.2 并行Voronoi圖柵格生成算法

傳統(tǒng)的柵格生成算法中，不論是采用以空白柵格為中心確定其歸屬的方法，還是以生長目標為中心通過不斷增長生長目標半徑對空白柵格進行覆蓋的方法，他們在計算每個空白柵格距離時，只能通過遍歷柵格，逐一處理。而柵格處理過程中的一個重要特點是，各個柵格的計算并不依賴于其他柵格的計算結(jié)果。即各個柵格的計算是相互獨立的，而由于CPU的串行性，導(dǎo)致了各個柵格只能順序處理，降低了處理速度。

圖1GPU組織架構(gòu)

由于GPU下的多個線程都是硬件實現(xiàn)的，各個線程的處理都是并行的，因此將柵格距離的計算分散到GPU端各個線程，必然能夠提高其生成速度。為了并行處理柵格化圖像，可以采用如下的想法，將每一個柵格點對應(yīng)于一個線程，此線程計算此柵格到所有的生長目標的距離，取最小距離的生長目標作為其歸屬。即采用一個線程用來確定一個空白柵格歸屬的方法。

確定方法后，就需要對GPU端內(nèi)核函數(shù)進行設(shè)計，由于內(nèi)核函數(shù)是并行處理的執(zhí)行單元，其設(shè)計方式直接決定了GPU端的程序運行效率。因此如何設(shè)計良好的內(nèi)核函數(shù)是提高并行速度的關(guān)鍵。本文采用如下方式進行內(nèi)核函數(shù)的設(shè)計，假設(shè)共分配了K個并行處理線程，柵格規(guī)模為M×N，設(shè)A[i]為第i個線程處理的柵格編號。當K

由于顯卡上的內(nèi)存是動態(tài)隨機存儲(DRAM)，因此最有效率的存取方式，是以連續(xù)的方式存取。當采用第一種方式時，看似是一種連續(xù)的存取方式，實際上恰好是非連續(xù)的，當?shù)趇個線程處理第i個柵格時，由于處理需要一定的時間，此時GPU自動將下個一線程i+1需要的內(nèi)存數(shù)據(jù)取出給其使用，此時下一個線程的內(nèi)存數(shù)據(jù)卻是在i+C處，內(nèi)存變成了間斷存取。而在使用第二種方式進行處理時，恰好是一種連續(xù)的存取方式，由于第i個線程正在處理第i個柵格數(shù)據(jù)，此時 GPU為第i+1個線程準備數(shù)據(jù)，而此時的數(shù)據(jù)正好為第i+1內(nèi)存處。滿足了內(nèi)存的連續(xù)存取特性。因此本文采用第二種方式，內(nèi)核函數(shù)的設(shè)計偽代碼如下：