發(fā)布時間：2018-05-30 19:39

  本文選題：球面Voronoi圖 + 確定歸屬算法�。� 參考：《中國礦業(yè)大學(xué)(北京)》2016年博士論文

【摘要】：隨著全球生態(tài)環(huán)境、社會經(jīng)濟一體化的不斷深入,人們的研究區(qū)域逐漸從局部區(qū)域擴大到整個地球。而攝影測量、遙感、全球定位系統(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圖的精度和效率方面存在的諸多問題,本文從球面V圖的生成算法、動態(tài)維護及其應(yīng)用方面進行了研究,主要工作總結(jié)如下:(1)提出基于QTM的球面V圖確定歸屬生成算法球面四元三角網(wǎng)(Quaternary Triangular Mesh,QTM)相對于傳統(tǒng)的經(jīng)緯度格網(wǎng)較為均勻。本文將QTM格網(wǎng)單元視作平面柵格算法中的像素(最小單元),計算每個格網(wǎng)單元到所有種子點格網(wǎng)的距離,并通過比較得到最近的種子點作為相應(yīng)QTM格網(wǎng)單元的歸屬,從而生成基于QTM的球面V圖。實驗結(jié)果表明,該算法能夠?qū)⑸傻那蛎鎂圖的誤差控制在兩個格網(wǎng)以內(nèi),初步解決了現(xiàn)有球面V圖柵格生成算法的精度問題。(2)利用GPU對確定歸屬算法進行優(yōu)化(硬件優(yōu)化)確定歸屬算法需要計算并比較球面上每一個QTM格網(wǎng)單元到所有種子點的距離,算法計算量較大,具有計算密集型的特點;同時,對于每一個格網(wǎng)單元所進行的處理是基本一致的,且不同格網(wǎng)單元之間的處理相互獨立,互不影響,算法具有指令一致性和相互獨立性的特點,這非常適合于GPU單指令多數(shù)據(jù)流(Single Instruction Multiple Data,SIMD)的計算模型。本文采用GPU統(tǒng)一計算設(shè)備架構(gòu)(Compute Unified Device Architecture,CUDA)對算法進行實現(xiàn),并從GPU全局內(nèi)存、共享內(nèi)存、常量內(nèi)存、寄存器等內(nèi)存的使用及訪問方式等方面對確定歸屬算法進行優(yōu)化,以從整體上提高算法的效率。實驗結(jié)果表明,利用GPU并行計算對算法進行優(yōu)化后,效率可提高兩個數(shù)量級以上。(3)利用雙向掃描方法對確定歸屬算法進行改進(算法優(yōu)化)QTM格網(wǎng)單元往往與其鄰近格網(wǎng)具有相同的最近種子點,因此可利用QTM格網(wǎng)的鄰近特性,通過鄰近格網(wǎng)傳遞最近種子點。將球面按QTM的方式剖分后,依次按從左到右、從上到下和從右到左、從下到上的順序?qū)η蛎嫒切螁卧M行掃描,并在掃描過程中通過計算和比較格網(wǎng)到其鄰近格網(wǎng)最近種子點的距離,得到當(dāng)前格網(wǎng)的最近種子點,進而得到球面V圖。實驗結(jié)果表明,該改進算法大大減少了確定歸屬算法中不必要的計算,在同一層次下,球面V圖生成時間基本恒定(與種子點數(shù)無關(guān))。(4)利用QTM格網(wǎng)的層次性對確定歸屬算法進行改進(尺度優(yōu)化)相同種子點在不同層次QTM格網(wǎng)上生成的V圖僅在Voronoi邊界處有所不同。因此,可首先利用低層次的格網(wǎng)生成球面V圖,并根據(jù)QTM格網(wǎng)及其三鄰近格網(wǎng)的歸屬信息提取構(gòu)成Voronoi區(qū)域邊界的QTM格網(wǎng);然后對邊界格網(wǎng)進行再次剖分,利用確定歸屬算法確定邊界格網(wǎng)子格網(wǎng)的歸屬,以此得到更高層次的球面V圖,重復(fù)該步驟直至達到相應(yīng)層次。實驗結(jié)果表明,算法效率較確定歸屬算法有較大提高,且能夠生成更高層次的球面V圖。(5)實驗系統(tǒng)設(shè)計開發(fā)與應(yīng)用以.Net框架為基礎(chǔ),利用C#、C++語言及GPU并行編程架構(gòu)——CUDA開發(fā)了基于QTM的球面Voronoi圖算法與應(yīng)用實驗系統(tǒng)。在該系統(tǒng)中,利用全球各國的首都、主要河流、主要湖泊等數(shù)據(jù)對本文提出的各球面Voronoi圖生成算法進行了實驗,并從效率、精度等方面對各算法及應(yīng)用進行了分析;同時,在系統(tǒng)中還給出了球面Voronoi圖的動態(tài)維護操作方法和基于柵格Voronoi圖的球面自然鄰近插值方法,并對基于質(zhì)心Voronoi圖的全球地形自適應(yīng)建模方法進行了初步的探索與實驗。
[Abstract]:With the global ecological environment and the deepening of social and economic integration, people's research areas have gradually expanded from local areas to the whole earth. The rapid development of modern earth observation technology, such as photogrammetry, remote sensing and global positioning system, makes it possible to obtain large scale, multi-scale and multi phase data in the world. The effective management and analysis of spatial data in the surrounding area requires the construction of a global, continuous, multi-scale dynamic data model. The spherical Voronoi graph (V map), with natural proximity and dynamic stability, has become one of the most potential solutions for the global spatial information management and analysis. The existing spherical V maps are generated. The algorithm, in order to generate the precision and efficiency of V graph, this paper studies the generation algorithm, dynamic maintenance and application of the spherical V graph. The main work is summarized as follows: (1) a spherical V graph based on QTM is proposed to determine the ascription generation algorithm spherical four element triangle net (Quaternary Triangular Mesh, QTM) relative to the traditional one. The latitude and longitude grid is more uniform. This paper treats the QTM grid unit as the pixel (minimum element) in the plane grid algorithm, calculates the distance from each grid unit to the grid of all seed points, and obtains the nearest seed point as the corresponding QTM grid unit by comparison, thus generating the spherical V map based on the QTM. The experimental results show that this calculation is used. The method can control the error of the generated spherical V graph within two grid. The precision problem of the grid generation algorithm of the existing spherical V graph is solved preliminarily. (2) using GPU to optimize the ascription algorithm (hardware optimization) to determine the ascription algorithm and compare the distance of every QTM grid unit on the spherical surface to all the seed points. At the same time, the processing of each grid unit is basically the same, and the processing between the different grid units is independent and does not affect each other. The algorithm has the characteristics of instruction consistency and mutual independence, which is not often suitable for the GPU single instruction multiple data flow (Single Instruction Mu). The calculation model of ltiple Data, SIMD). This paper uses GPU unified computing device architecture (Compute Unified Device Architecture, CUDA) to implement the algorithm, and optimizes the ascription algorithm from the aspects of GPU global memory, shared memory, constant memory, register and other memory usage and access methods to improve the algorithm from the whole. Efficiency. The experimental results show that the efficiency can be increased by two orders of magnitude above the algorithm by using GPU parallel computing. (3) using bidirectional scanning method to improve the ascription algorithm (algorithm optimization), the QTM grid unit often has the same nearest seed point as its adjacent grid, so it can make use of the adjacent characteristics of the QTM grid. The nearest seed is passed by the adjacent grid. After dividing the sphere by QTM, the spherical triangular element is scanned in order from left to right, from upper to bottom and from right to left, from bottom to upper, and the nearest species of current grid is obtained by calculating and comparing the distance between the grid and the nearest seed point of its adjacent grid. The experimental results show that the improved algorithm greatly reduces the unnecessary calculation in the ascription algorithm. At the same level, the generation time of the spherical V graph is basically constant (independent of the number of seed points) at the same level. (4) using the hierarchy of the QTM grid to improve the classification algorithm (scale optimization) the same seed points are different. The V graph generated in the hierarchical QTM grid is only different at the boundary of the Voronoi. Therefore, we can first use the low-level grid to generate the spherical V map, and extract the QTM grid that constitutes the boundary of the Voronoi region according to the QTM grid and its three adjacent grid. Then the boundary grid is re divided and the ascription algorithm is used to determine the boundary. In order to get a higher level of spherical V map and repeat the step up to the corresponding level, the experimental results show that the algorithm efficiency is better than the ascription algorithm and can generate a higher level of spherical V graph. (5) the design and development of the experimental system are based on the.Net framework, using C#, C++ language and GPU, and Line programming architecture - CUDA has developed a QTM based spherical Voronoi map algorithm and an application experiment system. In this system, experiments are carried out using the data of the capital, main rivers and main lakes of all countries in this paper, and the algorithms and applications are analyzed in terms of efficiency, accuracy and so on. At the same time, the dynamic maintenance operation method of the spherical Voronoi graph and the spherical natural neighborhood interpolation method based on the grid Voronoi graph are also given in the system, and the global terrain adaptive modeling method based on the centroid Voronoi diagram is preliminarily explored and experimentation.
【學(xué)位授予單位】：中國礦業(yè)大學(xué)(北京)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：P208

【參考文獻】

相關(guān)期刊論文 前10條

1 陳金業(yè);李毅;孫青云;;基于Voronoi圖的移動空劃分[J];計算機技術(shù)與發(fā)展;2014年02期

2 閆浩文;王邦松;;地圖點群綜合的加權(quán)Voronoi算法[J];武漢大學(xué)學(xué)報(信息科學(xué)版);2013年09期

3 王豹;胡瑋;蒲英霞;王結(jié)臣;;Voronoi圖在地圖制圖中的應(yīng)用[J];海洋測繪;2012年06期

4 賀毅輝;葉晨;劉志忠;彭偉;;基于CUDA的大規(guī)模群體行為實時仿真并行實現(xiàn)及優(yōu)化[J];計算機應(yīng)用;2012年09期

5 陳朋;;基于Voronoi圖的傳感數(shù)據(jù)自然鄰點插值算法研究[J];湖南第一師范學(xué)院學(xué)報;2012年04期

6 趙學(xué)勝;王磊;王洪彬;李穎;;全球離散格網(wǎng)的建模方法及基本問題[J];地理與地理信息科學(xué);2012年01期

7 張偉;覃慶炎;簡興祥;;自然鄰點插值算法及其在二維不規(guī)則數(shù)據(jù)網(wǎng)格化中的應(yīng)用[J];物探化探計算技術(shù);2011年03期

8 徐賽花;張二華;;基于CUDA的三維數(shù)據(jù)并行可視化[J];CT理論與應(yīng)用研究;2011年01期

9 陳偉鋒;王銳;潘明皓;華煒;;基于GPU的快速球面距離變換[J];計算機學(xué)報;2011年03期

10 孫文彬;趙學(xué)勝;;基于QTM格網(wǎng)的空間數(shù)據(jù)無縫層次建模[J];中國礦業(yè)大學(xué)學(xué)報;2008年05期

，

本文編號：1956529