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

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

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

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

Step3：GPU分配M×N個thread對柵格進行處理，當M×N大于所有的thread的總數(shù)時，可以將M×N個柵格分塊處理，即將其分成A行×B列×C塊，其中A×B小于thread的總數(shù)。對于分成了C塊的柵格來說，每個線程只需要處理C個柵格。

Step4：當生長目標數(shù)目不多時，每一個線程計算其對應的柵格到所有的生長目標點的距離，取距離最小的生長目標，為此線程對應的空白柵格的歸屬，轉(zhuǎn)Step6。當生長目標過多時，則轉(zhuǎn)Step5。

Step5：當生長目標較多時，為了減少遍歷生長目標的時間，通過借鑒王新生的算法，不計算柵格點到每一個生長目標的距離，通過對空白柵格不斷的進行鄰域擴張，直到遇到目標生長點的方法確定此柵格的歸屬。

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

3 實驗與總結(jié)

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

4 結(jié)語

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