Research On Topographic Factor Extraction Method Based On Octree And Its Distributed Computation

In recent years,the acquisition technology of DEM(Digital Elevation Model)is developing rapidly.The accuracy and amount of data are increasing continuously.How to handle and use these data has become a big challenge for users of geographic information system.But the traditional topographic factor extraction methods are mostly serial processing.On the one hand these methods take a long time to calculate the large amounts of data(hours or days),on the other hand few topographic factor extraction softwares can calculate more than GB data directly.These two aspects restrict the extraction of topographic factor for large amount of data,so the study of how fast and efficient to extract the topographic factor becomes inevitable.This method combine the octree model or the MapReduce model with the revised universal soil loss equation(RUSLE),solve the efficiency of the flat areas,flow accumulation and slope length calculation in topographic factor calculation and the memory limit problem when dealing with massive data.The following part are the main research achievements and contents of this paper.(1)The method of topographic factor extraction based on octree structure is proposed.The Deterministic 8 method is used to develop flow-direction octrees and flat matrice to show the relationship of terrain.The property that the points of flats are the cutoff points in the slope length calculation is used to simplify the search of flat directions.The flow-direction octrees and first-in-first-out queues are used to calculate the flow accumulation and slope length instead of the traditional forward and backward traversal algorithm,and solve the efficiency in topographic factor calculation.This method and traditional topographic factor calculation method DWSEL(Distributed Watershed Erosion Slope Length)were compared.This method required about 15-25% of the time that the DWSEL method needed to calculate the topographic factor,and improved the calculation efficiency.The calculation error was in the range of the allowable accuracy.But this method calculate with single machine,and processing ability is limited for big data.(2)Aiming at the single machine processing capacity constraints of(1),the method of the topographic factor extraction based on MapReduce is proposed.In order to search grid fast,the method use the principle of steep slope and the B+ tree to establishe the flow relationship search tree.The method use the MapReduce model to solve the efficiency of the slope length and flow accumulation calculation,and change the traditional traversal algorithm by search flow path and converge grid.The script of load balancing is used to solve the problem of disk utilization imbalance in the cluster.This MapReduce method ran on big data platform Hadoop and Spark.The MapReduce method was compared with the DWSEL method using the same evaluation criterion.The results showed that when the calculation of the number of nodes is 4,This method that ran on Hadoop platform required about 40% of the time that the DWSEL method needed to calculate the topographic factoron,and this method that ran on Spark platform required about 16.8% of the time of DWSEL method,so this method improved the calculation efficiency.When the number of machines in the cluster was less than 16,the extraction efficiency increased by a close linear proportion with the cluster number of machines.