Research On The Observation Point Setting And Its Parallelization Method Based On The Terrain Visual Domain

Terrain visibility analysis is to solve the visibility problem between the set of observation points and target points on the terrain by using computer geometric principles and computer graphics technology.It is an important part of geospatial analysis.The multiple viewshed problem is an important issue in terrain visibility analysis.It has a wide range of applications in military,urban planning and endangered animal protection.The observation point setting problem is one of multiple viewshed problems.This problem is generally abstracted as selecting the least number of viewpoints on a given terrain to maximize the joint viewshed area covered by the viewpoints.It is a combinatorial optimization problem,and the solving process for it is also an NP problem.However,with the rapid development of computer technology and remote sensing technology,the accuracy of the terrain data obtained is getting higher and higher and the number of terrain feature points is naturally increasing.The number of viewpoints is great even if selecting terrain feature points as the candidate viewpoints.Therefore,how to efficiently and quickly solve the observation point setting is a difficult and hot issue.Based on this,the following research work is carried out.1.A method of terrain feature point extraction for peaks,ridges and planes is proposed.Because terrain feature points are to be extracted as candidate viewpoints,the quality of terrain feature point directly affects the coverage ration of the observers last retained.This thesis proposes feature point extraction methods for peaks,ridges and planes respectively.For the peaks,they are extracted in anti-terrain data using hydrological flow modeling method.The points with the most accumulated water or the lowest elevation in the anti-terrain data are the peaks in the original terrain.For the ridges,the hydrological flow modeling method is used to obtain the water collection lines on the anti-terrain data,and then the water divide lines on the original terrain can be obtained.The topographic point on the water divide lines is the ridges.For the flat spots,the area judged as plane region is divided into multiple small areas,and then the centered point is selected as a candidate point in each of the divided small areas.Experiments show that if the terrain points extracted by the method are used as candidate viewpoints,the viewshed coverage ratio of the last remained observers is higher.2.A fast candidate viewpoints filtering method for multiple viewshed based on clustering is proposed.Firstly,terrain feature points are selected as candidate viewpoints.Then,these candidate viewpoints are clustered and those belonging to each cluster are sorted according to the index of viewshed contribution(IVC).Finally,the candidate viewpoints with relatively low viewshed contribution rate are removed gradually using our CVF algorithm.Through the CVF algorithm proposed in this article,the viewpoints with high viewshed contribution are preserved and the number of viewpoints to be preserved can be controlled by the number of clusters.To evaluate the performance and effectiveness of our CVF algorithm,we compare it with Region Partitioning for Filtering(RPF)and Simulated Annealing(SA)algorithm.Experimental results show that our CVF algorithm has a great improvement in both computational efficiency and total viewshed coverage rate.3.A parallel method of viewpoint filtering algorithm is proposed.In the viewpoint filtering algorithm,it is necessary to perform k-means clustering on the terrain points and sort the viewpoints according to their viewshed contribution rate in each cluster before filtering,which takes more time.Therefore,this paper uses the MPI and Open MP to parallelize k-means and the sorting of terrain points.Finally,when a viewpoint is moved to another cluster,the viewpoint contribution rate of the viewpoint needs to be recalculated and the amount of calculation is relatively large.It is considered that the viewshed of each viewpoint is calculated in parallel with Open MP,which can improve the calculation efficiency.Experiment results show that the parallelized viewpoint filtering method can reduce the calculation time greatly.