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

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

【摘要】：隨著全球生態(tài)環(huán)境、社會(huì)經(jīng)濟(jì)一體化的不斷深入,人們的研究區(qū)域逐漸從局部區(qū)域擴(kuò)大到整個(gè)地球。而攝影測(cè)量、遙感、全球定位系統(tǒng)等現(xiàn)代對(duì)地觀測(cè)技術(shù)的快速發(fā)展,使得全球大范圍、多尺度、多時(shí)相數(shù)據(jù)的獲取成為可能。為了在全球范圍內(nèi)有效地管理和分析空間數(shù)據(jù),需要構(gòu)建一個(gè)全球的、連續(xù)的、多尺度的動(dòng)態(tài)數(shù)據(jù)模型。球面Voronoi圖(簡(jiǎn)稱(chēng)V圖),具有自然鄰近、動(dòng)態(tài)穩(wěn)定等優(yōu)良特性,已成為全球空間信息管理與分析的最有潛力的解決方案之一。針對(duì)現(xiàn)有的球面V圖生成算法,在生成V圖的精度和效率方面存在的諸多問(wèn)題,本文從球面V圖的生成算法、動(dòng)態(tài)維護(hù)及其應(yīng)用方面進(jìn)行了研究,主要工作總結(jié)如下:(1)提出基于QTM的球面V圖確定歸屬生成算法球面四元三角網(wǎng)(Quaternary Triangular Mesh,QTM)相對(duì)于傳統(tǒng)的經(jīng)緯度格網(wǎng)較為均勻。本文將QTM格網(wǎng)單元視作平面柵格算法中的像素(最小單元),計(jì)算每個(gè)格網(wǎng)單元到所有種子點(diǎn)格網(wǎng)的距離,并通過(guò)比較得到最近的種子點(diǎn)作為相應(yīng)QTM格網(wǎng)單元的歸屬,從而生成基于QTM的球面V圖。實(shí)驗(yàn)結(jié)果表明,該算法能夠?qū)⑸傻那蛎鎂圖的誤差控制在兩個(gè)格網(wǎng)以?xún)?nèi),初步解決了現(xiàn)有球面V圖柵格生成算法的精度問(wèn)題。(2)利用GPU對(duì)確定歸屬算法進(jìn)行優(yōu)化(硬件優(yōu)化)確定歸屬算法需要計(jì)算并比較球面上每一個(gè)QTM格網(wǎng)單元到所有種子點(diǎn)的距離,算法計(jì)算量較大,具有計(jì)算密集型的特點(diǎn);同時(shí),對(duì)于每一個(gè)格網(wǎng)單元所進(jìn)行的處理是基本一致的,且不同格網(wǎng)單元之間的處理相互獨(dú)立,互不影響,算法具有指令一致性和相互獨(dú)立性的特點(diǎn),這非常適合于GPU單指令多數(shù)據(jù)流(Single Instruction Multiple Data,SIMD)的計(jì)算模型。本文采用GPU統(tǒng)一計(jì)算設(shè)備架構(gòu)(Compute Unified Device Architecture,CUDA)對(duì)算法進(jìn)行實(shí)現(xiàn),并從GPU全局內(nèi)存、共享內(nèi)存、常量?jī)?nèi)存、寄存器等內(nèi)存的使用及訪問(wèn)方式等方面對(duì)確定歸屬算法進(jìn)行優(yōu)化,以從整體上提高算法的效率。實(shí)驗(yàn)結(jié)果表明,利用GPU并行計(jì)算對(duì)算法進(jìn)行優(yōu)化后,效率可提高兩個(gè)數(shù)量級(jí)以上。(3)利用雙向掃描方法對(duì)確定歸屬算法進(jìn)行改進(jìn)(算法優(yōu)化)QTM格網(wǎng)單元往往與其鄰近格網(wǎng)具有相同的最近種子點(diǎn),因此可利用QTM格網(wǎng)的鄰近特性,通過(guò)鄰近格網(wǎng)傳遞最近種子點(diǎn)。將球面按QTM的方式剖分后,依次按從左到右、從上到下和從右到左、從下到上的順序?qū)η蛎嫒切螁卧M(jìn)行掃描,并在掃描過(guò)程中通過(guò)計(jì)算和比較格網(wǎng)到其鄰近格網(wǎng)最近種子點(diǎn)的距離,得到當(dāng)前格網(wǎng)的最近種子點(diǎn),進(jìn)而得到球面V圖。實(shí)驗(yàn)結(jié)果表明,該改進(jìn)算法大大減少了確定歸屬算法中不必要的計(jì)算,在同一層次下,球面V圖生成時(shí)間基本恒定(與種子點(diǎn)數(shù)無(wú)關(guān))。(4)利用QTM格網(wǎng)的層次性對(duì)確定歸屬算法進(jìn)行改進(jìn)(尺度優(yōu)化)相同種子點(diǎn)在不同層次QTM格網(wǎng)上生成的V圖僅在Voronoi邊界處有所不同。因此,可首先利用低層次的格網(wǎng)生成球面V圖,并根據(jù)QTM格網(wǎng)及其三鄰近格網(wǎng)的歸屬信息提取構(gòu)成Voronoi區(qū)域邊界的QTM格網(wǎng);然后對(duì)邊界格網(wǎng)進(jìn)行再次剖分,利用確定歸屬算法確定邊界格網(wǎng)子格網(wǎng)的歸屬,以此得到更高層次的球面V圖,重復(fù)該步驟直至達(dá)到相應(yīng)層次。實(shí)驗(yàn)結(jié)果表明,算法效率較確定歸屬算法有較大提高,且能夠生成更高層次的球面V圖。(5)實(shí)驗(yàn)系統(tǒng)設(shè)計(jì)開(kāi)發(fā)與應(yīng)用以.Net框架為基礎(chǔ),利用C#、C++語(yǔ)言及GPU并行編程架構(gòu)——CUDA開(kāi)發(fā)了基于QTM的球面Voronoi圖算法與應(yīng)用實(shí)驗(yàn)系統(tǒng)。在該系統(tǒng)中,利用全球各國(guó)的首都、主要河流、主要湖泊等數(shù)據(jù)對(duì)本文提出的各球面Voronoi圖生成算法進(jìn)行了實(shí)驗(yàn),并從效率、精度等方面對(duì)各算法及應(yīng)用進(jìn)行了分析;同時(shí),在系統(tǒng)中還給出了球面Voronoi圖的動(dòng)態(tài)維護(hù)操作方法和基于柵格Voronoi圖的球面自然鄰近插值方法,并對(duì)基于質(zhì)心Voronoi圖的全球地形自適應(yīng)建模方法進(jìn)行了初步的探索與實(shí)驗(yàn)。
[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é)位授予單位】：中國(guó)礦業(yè)大學(xué)(北京)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：P208

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1956529