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

具體步驟如下：(這里假設(shè)柵格的規(guī)模為M×N)：

Step1：根據(jù)柵格圖像的規(guī)模，確定GPU端線程塊和線程的分配方式和分配數(shù)量，初始化GPU端的參數(shù)。

Step2：程序調(diào)用GPU端內(nèi)核函數(shù)，同時(shí)將待處理柵格圖像數(shù)據(jù)傳入GPU中。數(shù)據(jù)主要是圖像的柵格距離，一般是二維數(shù)組，0表示空白柵格，其他各生長(zhǎng)目標(biāo)可由1，2等不同的數(shù)字定義。

Step3：GPU分配M×N個(gè)thread對(duì)柵格進(jìn)行處理，當(dāng)M×N大于所有的thread的總數(shù)時(shí)，可以將M×N個(gè)柵格分塊處理，即將其分成A行×B列×C塊，其中A×B小于thread的總數(shù)。對(duì)于分成了C塊的柵格來(lái)說(shuō)，每個(gè)線程只需要處理C個(gè)柵格。

Step4：當(dāng)生長(zhǎng)目標(biāo)數(shù)目不多時(shí)，每一個(gè)線程計(jì)算其對(duì)應(yīng)的柵格到所有的生長(zhǎng)目標(biāo)點(diǎn)的距離，取距離最小的生長(zhǎng)目標(biāo)，為此線程對(duì)應(yīng)的空白柵格的歸屬，轉(zhuǎn)Step6。當(dāng)生長(zhǎng)目標(biāo)過(guò)多時(shí)，則轉(zhuǎn)Step5。

Step5：當(dāng)生長(zhǎng)目標(biāo)較多時(shí)，為了減少遍歷生長(zhǎng)目標(biāo)的時(shí)間，通過(guò)借鑒王新生的算法，不計(jì)算柵格點(diǎn)到每一個(gè)生長(zhǎng)目標(biāo)的距離，通過(guò)對(duì)空白柵格不斷的進(jìn)行鄰域擴(kuò)張，直到遇到目標(biāo)生長(zhǎng)點(diǎn)的方法確定此柵格的歸屬。

Step6將生成后的數(shù)據(jù)返回CPU端，CPU端完成柵格圖像的顯示與后處理。

3 實(shí)驗(yàn)與總結(jié)

在CPU參數(shù)為IntelXeonCPUE5-2609，2.4GHz，2處理器8核心，GPU參數(shù)為T(mén)eslaC2075，448CUDA核心，顯存 5.25GB的試驗(yàn)平臺(tái)下，做了不同方法在不同柵格規(guī)模下生成Voronoi圖的對(duì)比試驗(yàn)，試驗(yàn)中生長(zhǎng)目標(biāo)的個(gè)數(shù)定義為100個(gè)。由于不同的方法都采用了相同的距離定義，因此各種方法的Voronoi圖生成結(jié)果都是相同的，即他們之間的生成精度是相同的，所以這里重點(diǎn)比較了不同方法的生成耗時(shí)。表1列出了不同方法生成Voronoi圖的用時(shí)，圖2為表1的折線圖，從圖2中可以明顯看出，當(dāng)柵格數(shù)量較少時(shí)，GPU并行技術(shù)的使用并不能提升生成速度，但是當(dāng)柵格點(diǎn)數(shù)量增加時(shí)，逐點(diǎn)法和距離變換法用時(shí)明顯增加，但GPU并行算法用時(shí)幾乎不變。

4 結(jié)語(yǔ)

通過(guò)實(shí)驗(yàn)結(jié)果可以看出，采用GPU對(duì)Voronoi圖的生成進(jìn)行并行加速，能夠很好的提高生成速度。其生成Voronoi圖所需時(shí)間與只與生長(zhǎng)目標(biāo)的數(shù)量有關(guān)，而與柵格規(guī)模沒(méi)有關(guān)系，當(dāng)生長(zhǎng)目標(biāo)數(shù)量為n時(shí)，其時(shí)間復(fù)雜度近似于O(n)，為線性的生成時(shí)間。相對(duì)于前面的幾種CPU下串行算法，尤其是在柵格規(guī)模過(guò)大的情況下，能夠很好的提高Voronoi圖的生成速度。