本文選題：柵格數(shù)據(jù)矢量化 + 數(shù)據(jù)劃分��； 參考：《南京大學(xué)》2013年碩士論文

【摘要】：遙感柵格數(shù)據(jù)是地理信息系統(tǒng)中最常用的數(shù)據(jù)源之一,由于其數(shù)據(jù)量大、定位精度低、難以表達(dá)空間拓?fù)潢P(guān)系等缺點(diǎn),在現(xiàn)實(shí)應(yīng)用中往往需要將其轉(zhuǎn)換為矢量數(shù)據(jù),因此柵格數(shù)據(jù)矢量化操作成為空間數(shù)據(jù)轉(zhuǎn)換的重要內(nèi)容之一。隨著航空航天遙感朝著多傳感器、多平臺(tái)、多角度和高空間分辨率、高光譜分辨率、高時(shí)相分辨率、高輻射分辨率的方向發(fā)展,柵格數(shù)據(jù)量呈現(xiàn)爆炸式增長,傳統(tǒng)的柵格矢量化算法已經(jīng)不能滿足矢量信息提取的需要,因此探索新型硬件架構(gòu)下的柵格數(shù)據(jù)矢量化并行算法具有重大理論意義和實(shí)用價(jià)值。然而長期以來對(duì)柵格數(shù)據(jù)矢量化的研究還多數(shù)停留在通過改進(jìn)現(xiàn)有算法以提高效率的階段,僅有的涉及柵格數(shù)據(jù)矢量化并行算法的研究,多采用均等的數(shù)據(jù)按行劃分方法,轉(zhuǎn)換結(jié)果為拓?fù)鋽?shù)據(jù)結(jié)構(gòu),不能滿足實(shí)際應(yīng)用中對(duì)簡單矢量實(shí)體結(jié)構(gòu)的需求。本文以傳統(tǒng)的基于拓?fù)潢P(guān)系的柵格數(shù)據(jù)矢量化算法為基礎(chǔ),研究數(shù)據(jù)并行模式下的柵格數(shù)據(jù)矢量化并行方法,重點(diǎn)探索柵格數(shù)據(jù)劃分、數(shù)據(jù)塊內(nèi)部拓?fù)錁?gòu)建以及數(shù)據(jù)塊拼接方法,探討柵格數(shù)據(jù)矢量化的任務(wù)調(diào)度策略和任務(wù)映射方法等并行關(guān)鍵技術(shù),設(shè)計(jì)并實(shí)現(xiàn)基于拓?fù)潢P(guān)系的柵格數(shù)據(jù)矢量化并行算法,并對(duì)該算法的時(shí)間性能和可擴(kuò)展性進(jìn)行評(píng)估。論文的主要研究內(nèi)容包括：(1)柵格數(shù)據(jù)劃分方法分析�？偨Y(jié)常見的柵格數(shù)據(jù)劃分方法、分析影響柵格數(shù)據(jù)劃分的兩個(gè)重要因素——柵格數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和柵格處理算法類型,針對(duì)柵格數(shù)據(jù)矢量化對(duì)數(shù)據(jù)劃分的要求,提出基于游程統(tǒng)計(jì)的柵格數(shù)據(jù)劃分方法,使得每個(gè)進(jìn)程所處理的柵格區(qū)域內(nèi)的數(shù)據(jù)復(fù)雜度相接近,進(jìn)而平衡各數(shù)據(jù)塊的內(nèi)部拓?fù)錁?gòu)建時(shí)間,減少進(jìn)程間等待。(2)并行拓?fù)錁?gòu)建方法研究。在分析基于拓?fù)潢P(guān)系的柵格數(shù)據(jù)矢量化串行算法中各要素之間拓?fù)潢P(guān)系構(gòu)建過程的基礎(chǔ)上,通過提取數(shù)據(jù)塊邊界處的特征點(diǎn),分別記錄其在上下數(shù)據(jù)塊中的連接信息,研究數(shù)據(jù)行劃分下的數(shù)據(jù)塊內(nèi)部拓?fù)錁?gòu)建和數(shù)據(jù)塊拼接等關(guān)鍵問題。(3)柵格數(shù)據(jù)矢量化并行算法設(shè)計(jì)。結(jié)合并行算法設(shè)計(jì)中的PCAM模型,按照任務(wù)分解、任務(wù)調(diào)度以及任務(wù)映射的研究思路,完成柵格數(shù)據(jù)矢量化的并行算法詳細(xì)設(shè)計(jì),重點(diǎn)探索主從模式下的數(shù)據(jù)塊動(dòng)態(tài)分配策略和數(shù)據(jù)拼接策略。(4)柵格數(shù)據(jù)矢量化并行算法實(shí)現(xiàn)與測(cè)試。在并行軟硬件環(huán)境支持下編程實(shí)現(xiàn)柵格數(shù)據(jù)矢量化并行算法,并選擇不同規(guī)模的數(shù)據(jù)對(duì)算法進(jìn)行測(cè)試,評(píng)估該并行算法的運(yùn)行時(shí)間、加速比等時(shí)間性能和可擴(kuò)展性。綜上所述,本文提出了考慮柵格數(shù)據(jù)復(fù)雜度的基于游程統(tǒng)計(jì)的柵格數(shù)據(jù)劃分方法；突破了并行拓?fù)錁?gòu)建這一柵格數(shù)據(jù)并行矢量化的關(guān)鍵問題；設(shè)計(jì)了主從模式的柵格數(shù)據(jù)矢量化并行算法,并在并行環(huán)境下編程實(shí)現(xiàn)。研究結(jié)果表明：基于游程統(tǒng)計(jì)的柵格數(shù)據(jù)劃分方法能夠獲得更加穩(wěn)定的并行加速比,并行拓?fù)錁?gòu)建是提高柵格數(shù)據(jù)矢量化效率的關(guān)鍵,主從模式可以有效實(shí)現(xiàn)數(shù)據(jù)塊的動(dòng)態(tài)分配和數(shù)據(jù)塊拼接。
[Abstract]:Remote sensing raster data is one of the most commonly used data sources in geographic information system. Because of its large amount of data, low positioning precision and difficult to express spatial topology, it is often needed to convert it into vector data in practical applications, so the raster data vectorization operation becomes one of the important contents of spatial data conversion. Space remote sensing has developed towards multi-sensor, multi platform, multi angle and high spatial resolution, high spectral resolution, high phase resolution and high radiative resolution, and the grid data amount presents an explosive growth. The traditional grid vectorization algorithm can not meet the need of vector information extraction. Therefore, the grid grid under the new hardware architecture is explored. The parallel algorithm of data vectorization has great theoretical significance and practical value. However, for a long time, the research of grid data vectorization is still mostly in the stage of improving the efficiency by improving the existing algorithms. Only the parallel algorithm of grid data vectorization is studied. For the topology data structure, the requirement of the simple vector entity structure can not be met. Based on the traditional raster data vectorization algorithm based on the topology relation, the grid data vectorization and parallel method under the data parallel mode is studied, and the grid number is divided, the topology of the data block is built and the data block is built. The parallel key technologies such as task scheduling strategy and task mapping method of grid data vectorization are discussed. The parallel algorithm of grid data Vectorization Based on topology is designed and implemented. The time performance and extensibility of the algorithm are evaluated. The main contents of this paper are as follows: (1) grid data partition method The common grid data partition method is summarized, and the grid data storage structure and grid processing algorithm type are analyzed, which affect grid data partition. In view of the requirement of grid data vectorization to data division, the raster data classification method based on travel statistics is proposed, which makes the grid area processed by each process. The internal data complexity is close, then the internal topology construction time of each data block is balanced, and the inter process waiting is reduced. (2) the study of the parallel topology construction method. On the basis of the analysis of the topology relationship between the elements in the grid data vectorization serial algorithm based on the topology relation, the feature points at the boundary of the data block are extracted. To record the connection information in the up and down data blocks respectively, study the key problems of the topology construction and data block splicing of the data block under the data division. (3) the grid data vectorization parallel algorithm design, combined with the PCAM model in the parallel algorithm design, according to the task decomposition, task scheduling and task mapping research ideas, complete the grid. The parallel algorithm of lattice data vectorization is designed in detail, focusing on the dynamic allocation strategy and data splicing strategy of the data block in the master-slave mode. (4) the implementation and testing of the grid data vectorization parallel algorithm. The running time of the parallel algorithm and the time performance and extensibility of the acceleration ratio are evaluated. In summary, this paper presents a method of grid data partition based on run statistics, which considers the complexity of grid data, and breaks through the key problem of constructing the parallel vector quantization of the grid data in parallel topology, and designs the grid of the master-slave mode. The parallel algorithm of lattice data vectorization is implemented in parallel environment. The results show that the raster data partition method based on travel statistics can obtain a more stable parallel acceleration ratio. Parallel topology construction is the key to improve the efficiency of grid data vectorization. The master slave mode can effectively realize the dynamic distribution and number of data blocks. According to the block splicing.

【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：P208

【參考文獻(xiàn)】

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

1 程果;陳犖;吳秋云;景寧;;一種面向復(fù)雜地理空間柵格數(shù)據(jù)處理算法并行化的任務(wù)調(diào)度方法[J];國防科技大學(xué)學(xué)報(bào);2012年06期

2 歐陽柳;熊偉;程果;陳宏盛;陳犖;;地理柵格數(shù)據(jù)的并行訪問方法研究[J];計(jì)算機(jī)科學(xué);2012年11期

3 徐立;孫群;楊帥;徐振;;地圖矢量數(shù)據(jù)拓?fù)潢P(guān)系生成算法[J];地理與地理信息科學(xué);2012年04期

4 黎心靈;盧剛;;并行GIS研究綜述[J];測(cè)繪標(biāo)準(zhǔn)化;2012年02期

5 陳占龍;張丁文;吳亮;;基于圖模型的多邊形自動(dòng)并行構(gòu)建算法[J];計(jì)算機(jī)應(yīng)用研究;2012年05期

6 齊琳;沈婕;郭立帥;周侗;;面向D-TIN并行構(gòu)建的動(dòng)態(tài)條帶數(shù)據(jù)劃分方法與實(shí)驗(yàn)分析[J];地球信息科學(xué)學(xué)報(bào);2012年01期

7 蘇程;周祖煜;倪廣翼;俞偉斌;黃智才;章孝燦;;基于像元有向邊的柵格數(shù)據(jù)掃描線矢量化方法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2011年07期

8 張明;張研霞;廖祥春;;攝影測(cè)量與遙感學(xué)[J];測(cè)繪文摘;2010年03期

9 張燦峰;周海芳;;像素級(jí)遙感圖像融合并行算法研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與科學(xué);2010年09期

10 蔡少華;;柵格索引的結(jié)點(diǎn)匹配算法[J];測(cè)繪科學(xué)技術(shù)學(xué)報(bào);2010年03期

相關(guān)博士學(xué)位論文 前3條

1 曾聯(lián)明;基于網(wǎng)格和智能算法的遙感巖性分類方法研究[D];中南大學(xué);2009年

2 趙春宇;高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究[D];武漢大學(xué);2006年

3 周海芳;遙感圖像并行處理算法的研究與應(yīng)用[D];國防科學(xué)技術(shù)大學(xué);2003年

，

本文編號(hào)：1797874