基于QTM的球面Voronoi圖生成算法與應(yīng)用

王 磊

1. 河南理工大學(xué)測繪與國土信息工程學(xué)院，河南 焦作 454000； 2. 中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京 100083

隨著全球生態(tài)環(huán)境、社會經(jīng)濟(jì)一體化的不斷深入，研究區(qū)域逐漸從局部區(qū)域擴(kuò)大到整個地球，而攝影測量、遙感、全球定位系統(tǒng)等現(xiàn)代對地觀測技術(shù)的快速發(fā)展，使得全球大范圍、多尺度、多時相數(shù)據(jù)的獲取成為可能。為了在全球范圍內(nèi)有效地管理和分析空間數(shù)據(jù)，需要構(gòu)建一個全球的、連續(xù)的、多尺度的動態(tài)數(shù)據(jù)模型。球面Voronoi圖(簡稱V圖)，具有自然鄰近、動態(tài)穩(wěn)定等優(yōu)良特性，已成為全球空間信息管理與分析最有潛力的解決方案之一。針對現(xiàn)有的球面V圖生成算法在精度和效率方面存在的諸多問題，本文從球面V圖的生成算法、動態(tài)維護(hù)及其應(yīng)用方面進(jìn)行了研究，主要內(nèi)容如下：

(1) 提出了基于QTM的球面V圖確定歸屬生成算法。本文將球面四元三角格網(wǎng)(quaternary triangular mesh, QTM)單元視作平面柵格算法中的像素(最小單元)，計(jì)算每個格網(wǎng)單元到所有種子點(diǎn)的距離，并通過比較得到最近的種子點(diǎn)作為相應(yīng)QTM格網(wǎng)單元的歸屬，從而生成基于QTM的球面V圖。試驗(yàn)結(jié)果表明，該算法能夠?qū)⑸汕蛎鎂圖的誤差控制在兩個格網(wǎng)以內(nèi)，初步解決了現(xiàn)有球面V圖柵格生成算法的精度問題。

(2) 利用GPU對確定歸屬算法進(jìn)行了優(yōu)化(硬件優(yōu)化)。確定歸屬算法具有計(jì)算密集性、指令一致性和相互獨(dú)立性的特點(diǎn)，非常適合于GPU單指令多數(shù)據(jù)流的計(jì)算模型。本文采用GPU統(tǒng)一計(jì)算設(shè)備架構(gòu)(CUDA)對算法進(jìn)行實(shí)現(xiàn)，并從GPU全局內(nèi)存、共享內(nèi)存、常量內(nèi)存、寄存器等內(nèi)存的使用及訪問方式等方面對確定歸屬算法進(jìn)行了優(yōu)化，以從整體上提高算法的效率。試驗(yàn)結(jié)果表明，利用GPU并行計(jì)算對算法進(jìn)行優(yōu)化后，效率可提高兩個數(shù)量級以上。

(3) 利用雙向掃描方法對確定歸屬算法進(jìn)行改進(jìn)(算法優(yōu)化)。將球面按QTM的方式剖分后，依次按從左到右、從上到下和從右到左、從下到上的順序?qū)η蛎嫒切螁卧M(jìn)行掃描，并在掃描過程中通過計(jì)算和比較格網(wǎng)到其鄰近格網(wǎng)的最近種子點(diǎn)的距離，得到當(dāng)前格網(wǎng)的最近種子點(diǎn)，進(jìn)而得到球面V圖。試驗(yàn)結(jié)果表明，該改進(jìn)算法大大減少了確定歸屬算法中不必要的計(jì)算，在同一層次下，球面V圖生成時間基本恒定(與種子點(diǎn)數(shù)無關(guān))。

(4) 利用QTM格網(wǎng)的層次性對確定歸屬算法進(jìn)行改進(jìn)(尺度優(yōu)化)。首先利用低層次的格網(wǎng)生成球面V圖，并根據(jù)QTM格網(wǎng)及其三鄰近格網(wǎng)的歸屬信息提取構(gòu)成Voronoi區(qū)域邊界的QTM格網(wǎng)；然后對邊界格網(wǎng)進(jìn)行再次剖分，利用確定歸屬算法確定邊界格網(wǎng)子格網(wǎng)的歸屬，以此得到更高層次的球面V圖，重復(fù)該步驟直至達(dá)到相應(yīng)層次。試驗(yàn)結(jié)果表明，算法效率相對于確定歸屬算法有較大提高，且能夠生成更高層次的球面V圖。

(5) 試驗(yàn)系統(tǒng)設(shè)計(jì)開發(fā)與應(yīng)用。設(shè)計(jì)開發(fā)了基于QTM的球面Voronoi圖算法與應(yīng)用試驗(yàn)系統(tǒng)，利用不同類型的數(shù)據(jù)，從效率、精度等方面對各算法進(jìn)行了驗(yàn)證；同時，還給出了球面Voronoi圖的動態(tài)維護(hù)操作方法和基于柵格Voronoi圖的球面自然鄰近插值方法，并對基于質(zhì)心Voronoi圖的全球地形自適應(yīng)建模方法進(jìn)行了初步的探索與試驗(yàn)。