| GISdevelopment.net ---> Technology---> Image Processing |
Back Propagation Algorithm for DEM Generation based on Quad tree Structure
M. Saati, A.Hashemi, J. Amini a
Department of Geomatics Engineering, Faculty of Engineering,
University of Tehran, Tehran, Iran,
P.O.Box:11365-4563, Tel: +98218008841,
E mail:- Saati@geomatics.ut.ac.ir Ar_m_hashemi@yahoo.com jamini@ut.ac.ir
S. Sadeghian
Research Institute of National Cartographic Center (NCC),
Tehran, Iran, P.O.Box:13185-1684
E mail:- Sadeghian@ncc.neda.net.ir
J. Noori
Faculty of Civil Engineering, IAU of Estahban, Estahban, Iran,
P.O.Box:74515-111, Tel: +987324225001,
E mail:- jam_1350@yahoo.com
ABSTRACT:
In this paper, we developed an approach for DEM generation from topographic maps and height points. The method used a neural network with back propagation algorithm to determine heights for grid points based on the quad tree structure.
The height points were extracted randomly from topographic maps 1:2000. These points structured under the quad tree structure and for each constructed region used a trained network to determine a height for each point on a regular grid. About 80% of points in each region are used for training the network. Results of the method were compared with the approaches in the PCI Geomatica software.
1. INTRODUCTION
DEM Definition: Digital elevation model (DEM) data consist of a sampled array of regularly spaced elevation values referenced horizontally either to a Universal Transverse Mercator (UTM) projection or to a geographic coordinate system (USGS definition). The grid cells are spaced at regular intervals along south to north profiles that are ordered from west to east.
DEM provides the basis in modeling and analysis of spatio-topographic information, therefore DEM reconstruction is the important task for 3D data users. Geo-spatial Information Systems (GIS) are becoming increasingly popular for visualizing spatial data. Most systems layer patterns or colors, which depict data such as soil type, roads, and the like, over a two-dimensional map. As technology continues to improve, users increasingly expect to view such data in three dimensional systems.
DEM Applications: there are many applications from DEM in different science.
- Civil Engineering: cut and fill in road design, site planning, volumetric calculations in dams and reservoirs etc.
- Earth Sciences: for modeling, analysis and interpretation of terrain morphology e.g. drainage basin delineation, hydrological run-off modeling, geomorphologic simulation and classification, geological mapping etc.
- Planning and resource management: site location, support of image classification in RS, geometric and radiometric correction in RS images, erosion potential models, crop suitability studies, pollution dispersion modeling etc.
- Surveying and Photogrammetry: in building high quality contours, used in survey or photogrammetric data capture and subsequent editing, orthophoto production, data quality assessment and topographic mapping.
- Military Applications: intervisibility analysis for battlefield management, 3-D display for weapons guidance systems and flight simulation, and radar line of sight analyses
A (Triangulation Irregular Network) TIN can also get converted to a grid by the interpolation of points on the TIN. An advantage over the TIN is that it is easier to find the height at a given location. Only a simple calculation is required to locate the nearest grid points and interpolate between them.
In this paper, we used some of conventional methods and the proposed method based on Artificial Neural Network (ANN) for preparing DEM.
2. INTERPOLATION
During height points assessment, the interpolation technique used to grid DEM generation. There are two approaches for this purpose that illustrated as following sections.
2.1 Conventional interpolation
In many science specially earth's science, spatial interpolation used for evaluation of physical data in continuity surface.
Each used method is suitable for a type of dataset.in other hand maybe a method for a dataset can be present good result but it is no suitable for other dataset [2]. Numbers of conventional interpolation have been shown in table 1.
In this paper the PCI Geomatica V8.1 software is supported any conventional method; we used this software for data point interpolation for DEM generation.
For this purpose we need to height data that we used the digital topographic map consist of height data points and major and minor contours. Figure 1. Shows the part of a topographic map and Figure 2 shows all of DEM generated with conventional methods .
Fig.1- the part of topographic map
(a)
(b)
(c)
(d)
Fig.2- reconstructed DEM with:
a. nearest neighbor method,
b. PCI Geomatica,
c. weighted inverse distance and
d. simple inverse distance
2.2 Neural Network interpolation
The potential of neural networks in multidimensional interpolation explore using a multilayer perceptron for fitting surfaces to a synthetic topographic dataset [1]. For data interpolating, the network uses two input units, corresponding to the spatial Cartesian coordinates (x,y), and a single output unit representing the computed height of grid points. The network is trained using the irregular dataset. The trained network is subsequently used to compute the height of any node location (x,y) [3,4].
During our dataset is very large, we used quad tree structure for partitioning data into smaller dataset. This is performing twice that in first every region consists of maximum 2000 points and another dataset which consist of maximum 1000 points in any region. In figure 3. Results of applying this structure on our dataset are illustrated. Each region that does not have any point is not contributed in DEM generation process and those are shown as background in output results.
Fig. 3- Quad tree structure applied on all of data
For training of network we used multilayer perceptron (MLP) with one hidden layer that numbers of neuron in hidden layer is changed from 1 to 30. During as illustrated in figure 4, the optimum number of neuron is 19 but we select 10 neurons for decrease processing calculation.
Fig.4 - optimum neuron extraction
Every one of above parts is trained by following parameter:
- The number of neuron in hidden layer=10;
- Number of epoch=2000(in most cases, the network convergences in about 90 epoch.)
- The value of goal function=1e-006;
- The time of training=INF.
Figure 5 shows all of DEM generated based on neural network.
(a)
(b)
Fig.5- DEM reconstructed with neural network:
a. max data of any region are 2000 points and
b. max data of any region are 1000 points
2.3 DEM accuracy
The accuracy of DEM data depends on the source and resolution of the data samples. DEM data accuracy is derived by comparing linear interpolation elevations in the DEM with corresponding map location elevations and computing the statistical standard deviation or root mean-square error (RMSE). The RMSE is used to describe the DEM accuracy. RMSE results of 20 check point's witch interpolated with conventional and MLP approaches have been shown in table 2 and table 3.
3. CONCLUSIONS
An advantage of DEM over the TIN is that it is easier to find the height at a given location. Only a simple calculation is required to locate the nearest grid points and interpolate between them.
Compared with the conventional approaches, the neural network approach was found to better represent the nonlinearity in the synthetic dataset.
ACKNOWLEDJMENTS
The authors would like to thanks from University of Tehran for support this project and national cartographic center (NCC) for the IKONOS image and 1:2000 digital maps.
REFERENCES
- Atkinson, P.M., and Tatnal, A.R.L., 1997, "Introduction Neural Networks in Remote Sensing", International Journal of Remote Sensing, 18, pp 699-709.
- Caruso, C.; Quarta, F., "Interpolation Methods Comparison", Computers Math. Applic. 35(12):109-126, 1998.
- Menhaj M.B. and Hagan M., 1994, "Training Feed forward Networks with the Marquardt Algorithm", IEEE Transactions on Neural Networks, Vol. 5, No. 6, November 1994, pp. 989-993.
- Sarzeaud, O. and Stephan, Y., 2000, "Fast Interpolation Using Kohonen Self-Organizing Neural Networks", IFIP TCS 2000, Sendai, Japan, pp.126-139.