GISdevelopment.net --> Application --> Miscellaneous
1 Ali Shirzadi Babakan
M.Sc. Student, Dept. of GIS Eng.
Email:shirzadi_ali@yahoo.com
2 Mohammad S. Mesgari
Assistant Professor, Dept. of GIS Eng.
Email: mesgari@kntu.ac.ir
1,2 Faculty of Geodesy and Geomatics Eng.
K.N. Toosi University of Technology Vali Asr St., Vanak Sq., Tehran, Iran
Firoozeh Karimi
M.Sc. Student, Dept. of GIS Eng.
Faculty of Geomatics and Surveying Eng.
Tehran University Kargar St., Tehran, Iran
Email: firoozeh_1363@yahoo.com
ABSTRACT
Gridding methods produce a regularly spaced, rectangular array of Z values from irregularly spaced XYZ data. Gridding generates a Z value at each grid node by interpolating or extrapolating the data values. Different gridding methods provide different interpretations of data because each method calculates grid node values by using a different algorithm. In this paper, we apply and compare different gridding methods including Inverse Distance Weighting, Kriging, Minimum Curvature, Modified Shepard's Method, Natural Neighbor, Nearest Neighbor, Polynomial Regression, Radial Basis Function, Triangulation with Linear Interpolation, Moving Average and Local Polynomial for various pilot regions with varied elevations. Grid method parameters which are able to set when producing a grid file, control the interpolation procedures.
We also change these parameters to evaluate the effect of them on the resulted precision. We use a set of check points to compare the precision of these methods. To implement these methods, data points with equal precision is used so the results are affected only by interpolation method, and the effect of other parameters of grid and data points are reduced by using them equally in all gridding methods. Eventually, RMSE is computed by check points for each method with its special parameters for each region. The results of these methods and the evaluation of their advantages and disadvantages for the pilot regions are represented in this paper. Key Words: gridding, gridding methods, interpolation, DTM.
Introduction
In this paper we applied different gridding methods to four data files with equal precision for flat, hilly, mountainous and complex regions with surfer8 software. Then the precision of gridding methods for various regions is comparable. To investigate the precision of different gridding methods for each region some check points are used, as we know check points are not used in the interpolation and so they can be used to compute the absolute precision.
Data file of flat region includes 630 sample points, and 20 check points which are distributed in the region. Also, data files of hilly, mountainous and complex regions with 5451, 2884 and 4277 sample points, and 60, 55, 80 check points are used to compute absolute precision of different gridding methods. To examine the precision of each gridding method, RMSE is computed with the following equation: (The precision is high when the result of this equation is low.)
In the following, different gridding methods and the main characteristics of them are studied then absolute precision of each method for various regions is computed. Finally obtained results are represented in a table.
Gridding Overview
Gridding generates a Z value at each grid node by interpolating or extrapolating the data values. Gridding methods produce a regularly spaced, rectangular array of Z values from irregularly spaced XYZ data. The difference between gridding methods is how the weighting factors are computed and applied to data points during grid node interpolation. Grid method parameters control the interpolation procedures. Different gridding methods provide different interpretations of the data because each method calculates grid node values using a different algorithm .
1- Inverse Distance Weighting
The Inverse Distance Weighting gridding method is a weighted average interpolator, and can be either an exact or a smoothing interpolator. This method behaves as an exact interpolator when a zero Smoothing parameter is assigned. It is a very fast method for gridding but has the tendency to generate "bull's-eye" patterns of concentric contours around the data points .
This method is used for each region with various powers and RMSE is computed by means of check points. The results are represented in below table. Then the diagrams of power at RMSE for each region are drawn and by means of them, the optimum power of the method for each region (power with minimum RMSE) is obtained. As it is illustrated from the diagrams and table, optimum power for flat region is 4 and for other regions is 5. This method with optimum power has good precision.
2- Kriging
Kriging is a geostatistical gridding method that has proven useful and popular in many fields. This method produces visually appealing maps from irregularly spaced data. Kriging attempts to express trends suggested in the data. Within Surfer, Kriging can be either an exact or a smoothing interpolator depending on the user-specified parameters. With most data sets, Kriging with the linear variogram is quite effective. Surfer includes two Kriging types: Point Kriging and Block Kriging. Point Kriging estimates the values of the points at the grid nodes. Block Kriging estimates the average value of the rectangular blocks centered on the grid nodes [2], [4].
For this method both type of Kriging; point Kriging and block Kriging are used for each region with linear variogram and by following parameters:Slope = 1 Drift Type = none As it was predicted this method has very good precision for each region and the precision of point Kriging is better than the precision of block Kriging. One of the main disadvantages of this method is that, processing is rather slow and it takes long time for large amount of data.
3- Minimum Curvature
Minimum Curvature is widely used in the earth sciences. This method generates the smoothest possible surface while attempting to honor the data as closely as possible but it is not an exact interpolator, however. It is fast for most data sets but it can create high magnitude artifacts in areas of no data. Minimum Curvature produces a grid by repeatedly applying an equation over the grid in an attempt to smooth the grid. The grid node values are recalculated until successive changes in the values are less than the Maximum Residuals value, or the maximum number of iterations is reached [1], [2]. This method is used with various Maximum iterations and these parameters:
Maximum Residual = 0.05 Relaxation Factor = 1
Internal Tension = 0 Boundary Tension = 0.
The internal tension and boundary tension control the amount of smoothing and in general, the default value of Relaxation Factor (1.0) is a good generic value. The obtained results in below table show that it is a rather suitable method to produce a grid.
4- Modified Shepard's Method
Modified Shepard's Method uses an inverse distance weighted least squares method. As such, it is similar to the Inverse Distance Weighting interpolator, but the use of local least squares eliminates or reduces the "bull's-eye" appearance of the generated contours. This method can be either an exact or a smoothing interpolator depending on using of smoothing factor [2].
We apply this method to sample data sets with various values for Quadratic Neighbors and Weighting Neighbors, and by Smoothing Factor (RČ) equal to zero. The obtained results show that, the default values of Quadratic Neighbors and Weighting Neighbors (Quadratic Neighbors=13 and Weighting Neighbors=19) result the best precision for all regions.
5- Natural Neighbor
The Natural Neighbor gridding method is quite popular in some fields. This method does not extrapolate contours beyond the convex hull of the data locations and it is an exact interpolator. It generates good contours from data sets containing dense data in some areas and sparse data in other areas and does not generate data in areas without data [2], [6].
Although the obtained results of applying this method shown in blew table, present that it is very good and quick, but it can not produce a complete grid for whole region, because it can not assign a value to many grid nodes. Therefore there is no result for some check points and so RMSE is computed with less check points than other gridding methods.
6- Nearest Neighbor
The Nearest Neighbor gridding method assigns the value of the nearest point to each grid node. Alternatively, in cases where the data are nearly on a grid with only a few missing values, this method is effective for filling in the holes, or creating a grid file with the blanking value assigned to those locations where no data are present. It is an exact interpolator under all circumstances [2]. This method is very fast and the precision of its results is rather good. The obtained results are shown in below table.
7- Polynomial Regression
Polynomial Regression is used to define large-scale trends and patterns in the data. It is not really an interpolator because it does not attempt to predict unknown Z values. It is very fast for any amount of data, but local details in the data are lost in the generated grid [2]. As below table shows, the resulted grid has very low precision and the Simple Planar surface results the better precision than other surfaces and the Quadratic and Cubic surfaces results the rather equal precision for all regions.
8- Radial Basis Function
All of the Radial Basis Function methods are exact interpolators. A smoothing factor can be introduced to all the methods to produce a smoother surface. This method is quite flexible and compares to Kriging since it generates the best overall interpretations of most data sets and produces a result quite similar to Kriging. Experience indicates that the multiquadric basis function works quite well in most cases. Successful use of the Thin Plate Spline basis function is also reported regularly in the technical literature [2], [3].
By applying this method to all regions with default smoothing factor (R2), the results in below table are obtained and is exhibited that the precision of this method is very good but it is very slow and it is not recommended for very large data sets.
9- Triangulation with Linear Interpolation
The Triangulation with Linear Interpolation method in Surfer uses the optimal Delaunay triangulation. This method is an exact interpolator and works best when the data are evenly distributed over the grid area. All grid nodes within a given triangle are defined by the triangular surface. Because the original data are used to define the triangles, the data are honored very closely [2], [5].
The results of applying this method are similar to results of Natural Neighbor method. Although the obtained results shown in blew table present that it is very good and quick, but it can not produce a complete grid for whole region, because it can not assign a value to many grid nodes. Therefore there is no result for some check points and so RMSE is computed with less check points than other gridding methods.
10- Moving Average
The Moving Average gridding method assigns values to grid nodes by averaging the data within the grid node's search ellipse. To use Moving Average, a search ellipse can be defined and the minimum number of data can be specified to use. The output
grid node value is set equal to the arithmetic average of the identified neighboring data, thus this method is smoothing interpolator. Moving Average extracts intermediate-scale trends and variations from large, noisy data sets, and it is fast even for very large data sets [2]. As shown in blew table precision of this method is very low and it is not recommended to produce a grid.
11- Local polynomial
The Local Polynomial gridding method assigns values to grid nodes by using a weighted least squares fit with data within the grid node's search ellipse. This method is most applicable to data sets that are locally smooth. It is a smoothing interpolator and the computational speed of the method is not significantly affected by the size of the data set [2]. In this method, polynomials with degree of 1, 2 and 3 by distance weighting power equal to 2 are used. As shown in the blow table, the precision of polynomial with degree of 3 is higher than others.
Conclusion
In this paper we examined different methods of gridding and their resulted precisions. At first, 4 Sample data files that surveyed with the same surveying instrument from various regions with different elevations were chosen. Then different methods of gridding with various parameters were applied to each sample region by means of surfer 8 software and RMSE was computed by check points. All other affecting factors such as precision of sample points, type and number of check points, grid parameters and so on were equal in all methods so the results are just affected by parameters of gridding methods and therefore gridding methods can be comparable.
Finally it should be mentioned that all results of each gridding method are obtained upon of algorithms of surfer 8 for these sample regions and if algorithms are changed or sample data are very different from the these sample points, the obtained results may become a bit different. At the end, all results are represented in below table.
References
Evaluation of gridding methods for various regions with different elevations
1 Ali Shirzadi Babakan
M.Sc. Student, Dept. of GIS Eng.
Email:shirzadi_ali@yahoo.com
2 Mohammad S. Mesgari
Assistant Professor, Dept. of GIS Eng.
Email: mesgari@kntu.ac.ir
1,2 Faculty of Geodesy and Geomatics Eng.
K.N. Toosi University of Technology Vali Asr St., Vanak Sq., Tehran, Iran
Firoozeh Karimi
M.Sc. Student, Dept. of GIS Eng.
Faculty of Geomatics and Surveying Eng.
Tehran University Kargar St., Tehran, Iran
Email: firoozeh_1363@yahoo.com
ABSTRACT
Gridding methods produce a regularly spaced, rectangular array of Z values from irregularly spaced XYZ data. Gridding generates a Z value at each grid node by interpolating or extrapolating the data values. Different gridding methods provide different interpretations of data because each method calculates grid node values by using a different algorithm. In this paper, we apply and compare different gridding methods including Inverse Distance Weighting, Kriging, Minimum Curvature, Modified Shepard's Method, Natural Neighbor, Nearest Neighbor, Polynomial Regression, Radial Basis Function, Triangulation with Linear Interpolation, Moving Average and Local Polynomial for various pilot regions with varied elevations. Grid method parameters which are able to set when producing a grid file, control the interpolation procedures.
We also change these parameters to evaluate the effect of them on the resulted precision. We use a set of check points to compare the precision of these methods. To implement these methods, data points with equal precision is used so the results are affected only by interpolation method, and the effect of other parameters of grid and data points are reduced by using them equally in all gridding methods. Eventually, RMSE is computed by check points for each method with its special parameters for each region. The results of these methods and the evaluation of their advantages and disadvantages for the pilot regions are represented in this paper. Key Words: gridding, gridding methods, interpolation, DTM.
Introduction
In this paper we applied different gridding methods to four data files with equal precision for flat, hilly, mountainous and complex regions with surfer8 software. Then the precision of gridding methods for various regions is comparable. To investigate the precision of different gridding methods for each region some check points are used, as we know check points are not used in the interpolation and so they can be used to compute the absolute precision.
Data file of flat region includes 630 sample points, and 20 check points which are distributed in the region. Also, data files of hilly, mountainous and complex regions with 5451, 2884 and 4277 sample points, and 60, 55, 80 check points are used to compute absolute precision of different gridding methods. To examine the precision of each gridding method, RMSE is computed with the following equation: (The precision is high when the result of this equation is low.)
In the following, different gridding methods and the main characteristics of them are studied then absolute precision of each method for various regions is computed. Finally obtained results are represented in a table.
Gridding Overview
Gridding generates a Z value at each grid node by interpolating or extrapolating the data values. Gridding methods produce a regularly spaced, rectangular array of Z values from irregularly spaced XYZ data. The difference between gridding methods is how the weighting factors are computed and applied to data points during grid node interpolation. Grid method parameters control the interpolation procedures. Different gridding methods provide different interpretations of the data because each method calculates grid node values using a different algorithm .
1- Inverse Distance Weighting
The Inverse Distance Weighting gridding method is a weighted average interpolator, and can be either an exact or a smoothing interpolator. This method behaves as an exact interpolator when a zero Smoothing parameter is assigned. It is a very fast method for gridding but has the tendency to generate "bull's-eye" patterns of concentric contours around the data points .
This method is used for each region with various powers and RMSE is computed by means of check points. The results are represented in below table. Then the diagrams of power at RMSE for each region are drawn and by means of them, the optimum power of the method for each region (power with minimum RMSE) is obtained. As it is illustrated from the diagrams and table, optimum power for flat region is 4 and for other regions is 5. This method with optimum power has good precision.
2- Kriging
Kriging is a geostatistical gridding method that has proven useful and popular in many fields. This method produces visually appealing maps from irregularly spaced data. Kriging attempts to express trends suggested in the data. Within Surfer, Kriging can be either an exact or a smoothing interpolator depending on the user-specified parameters. With most data sets, Kriging with the linear variogram is quite effective. Surfer includes two Kriging types: Point Kriging and Block Kriging. Point Kriging estimates the values of the points at the grid nodes. Block Kriging estimates the average value of the rectangular blocks centered on the grid nodes [2], [4].
For this method both type of Kriging; point Kriging and block Kriging are used for each region with linear variogram and by following parameters:Slope = 1 Drift Type = none As it was predicted this method has very good precision for each region and the precision of point Kriging is better than the precision of block Kriging. One of the main disadvantages of this method is that, processing is rather slow and it takes long time for large amount of data.
3- Minimum Curvature
Minimum Curvature is widely used in the earth sciences. This method generates the smoothest possible surface while attempting to honor the data as closely as possible but it is not an exact interpolator, however. It is fast for most data sets but it can create high magnitude artifacts in areas of no data. Minimum Curvature produces a grid by repeatedly applying an equation over the grid in an attempt to smooth the grid. The grid node values are recalculated until successive changes in the values are less than the Maximum Residuals value, or the maximum number of iterations is reached [1], [2]. This method is used with various Maximum iterations and these parameters:
Maximum Residual = 0.05 Relaxation Factor = 1
Internal Tension = 0 Boundary Tension = 0.
The internal tension and boundary tension control the amount of smoothing and in general, the default value of Relaxation Factor (1.0) is a good generic value. The obtained results in below table show that it is a rather suitable method to produce a grid.
4- Modified Shepard's Method
Modified Shepard's Method uses an inverse distance weighted least squares method. As such, it is similar to the Inverse Distance Weighting interpolator, but the use of local least squares eliminates or reduces the "bull's-eye" appearance of the generated contours. This method can be either an exact or a smoothing interpolator depending on using of smoothing factor [2].
We apply this method to sample data sets with various values for Quadratic Neighbors and Weighting Neighbors, and by Smoothing Factor (RČ) equal to zero. The obtained results show that, the default values of Quadratic Neighbors and Weighting Neighbors (Quadratic Neighbors=13 and Weighting Neighbors=19) result the best precision for all regions.
5- Natural Neighbor
The Natural Neighbor gridding method is quite popular in some fields. This method does not extrapolate contours beyond the convex hull of the data locations and it is an exact interpolator. It generates good contours from data sets containing dense data in some areas and sparse data in other areas and does not generate data in areas without data [2], [6].
Although the obtained results of applying this method shown in blew table, present that it is very good and quick, but it can not produce a complete grid for whole region, because it can not assign a value to many grid nodes. Therefore there is no result for some check points and so RMSE is computed with less check points than other gridding methods.
6- Nearest Neighbor
The Nearest Neighbor gridding method assigns the value of the nearest point to each grid node. Alternatively, in cases where the data are nearly on a grid with only a few missing values, this method is effective for filling in the holes, or creating a grid file with the blanking value assigned to those locations where no data are present. It is an exact interpolator under all circumstances [2]. This method is very fast and the precision of its results is rather good. The obtained results are shown in below table.
7- Polynomial Regression
Polynomial Regression is used to define large-scale trends and patterns in the data. It is not really an interpolator because it does not attempt to predict unknown Z values. It is very fast for any amount of data, but local details in the data are lost in the generated grid [2]. As below table shows, the resulted grid has very low precision and the Simple Planar surface results the better precision than other surfaces and the Quadratic and Cubic surfaces results the rather equal precision for all regions.
8- Radial Basis Function
All of the Radial Basis Function methods are exact interpolators. A smoothing factor can be introduced to all the methods to produce a smoother surface. This method is quite flexible and compares to Kriging since it generates the best overall interpretations of most data sets and produces a result quite similar to Kriging. Experience indicates that the multiquadric basis function works quite well in most cases. Successful use of the Thin Plate Spline basis function is also reported regularly in the technical literature [2], [3].
By applying this method to all regions with default smoothing factor (R2), the results in below table are obtained and is exhibited that the precision of this method is very good but it is very slow and it is not recommended for very large data sets.
9- Triangulation with Linear Interpolation
The Triangulation with Linear Interpolation method in Surfer uses the optimal Delaunay triangulation. This method is an exact interpolator and works best when the data are evenly distributed over the grid area. All grid nodes within a given triangle are defined by the triangular surface. Because the original data are used to define the triangles, the data are honored very closely [2], [5].
The results of applying this method are similar to results of Natural Neighbor method. Although the obtained results shown in blew table present that it is very good and quick, but it can not produce a complete grid for whole region, because it can not assign a value to many grid nodes. Therefore there is no result for some check points and so RMSE is computed with less check points than other gridding methods.
10- Moving Average
The Moving Average gridding method assigns values to grid nodes by averaging the data within the grid node's search ellipse. To use Moving Average, a search ellipse can be defined and the minimum number of data can be specified to use. The output
grid node value is set equal to the arithmetic average of the identified neighboring data, thus this method is smoothing interpolator. Moving Average extracts intermediate-scale trends and variations from large, noisy data sets, and it is fast even for very large data sets [2]. As shown in blew table precision of this method is very low and it is not recommended to produce a grid.
11- Local polynomial
The Local Polynomial gridding method assigns values to grid nodes by using a weighted least squares fit with data within the grid node's search ellipse. This method is most applicable to data sets that are locally smooth. It is a smoothing interpolator and the computational speed of the method is not significantly affected by the size of the data set [2]. In this method, polynomials with degree of 1, 2 and 3 by distance weighting power equal to 2 are used. As shown in the blow table, the precision of polynomial with degree of 3 is higher than others.
Conclusion
In this paper we examined different methods of gridding and their resulted precisions. At first, 4 Sample data files that surveyed with the same surveying instrument from various regions with different elevations were chosen. Then different methods of gridding with various parameters were applied to each sample region by means of surfer 8 software and RMSE was computed by check points. All other affecting factors such as precision of sample points, type and number of check points, grid parameters and so on were equal in all methods so the results are just affected by parameters of gridding methods and therefore gridding methods can be comparable.
Finally it should be mentioned that all results of each gridding method are obtained upon of algorithms of surfer 8 for these sample regions and if algorithms are changed or sample data are very different from the these sample points, the obtained results may become a bit different. At the end, all results are represented in below table.
References
- Briggs, I. C. (1974), Machine Contouring Using Minimum Curvature, Geophysics, v. 39, n. 1, p. 39-48.
- Goldensoftware, Surfer8 Help, www.goldensoftware.com
- Hardy, R. L. (1990), Theory and Applications of the Multiquadric-BiHarmonic Method, Computers Math. Applic, v. 19, n. 8/9, p. 163-208.
- Isaaks, E. H., and Srivastava, R. M. (1989), An Introduction to Applied Geostatistics, Oxford University Press, New York, 561 pp.
- Lee, D. T., and Schachter, B. J. (1980), Two Algorithms for Constructing a Delaunay Triangulation, International Journal of Computer and Information Sciences, v. 9, n. 3, p. 219-242.
- Sibson, R. (1981), A Brief Description of Natural Neighbor Interpolation, Interpreting Multivariate Data, V. Barnett editor, John Wiley and Sons, New York, p. 21-36.