CONTOUR TRACING TECHNIQUE USING INTERPOLATION METHOD

PAWAN KUMAR MISHRA¹*
¹Department of Computer Science & Engineering, Faculty of Science and Technology, ICFAI University Dehradun, India
* Corresponding Author : pawantechno@rediffmail.com

Received : 12-12-2011     Accepted : 15-01-2012     Published : 28-02-2012
Volume : 3     Issue : 1       Pages : 111 - 113
J Inform Oper Manag 3.1 (2012):111-113

This paper presents a method for the interpolation of contour lines to terrain surfaces using desktop type computers. Applications of Analytical Cartography include terrain visibility, Map overlay, Interpolation and approximation etc. A method was developed to solve Laplacian approximation algorithm which is based on the LSQR iterative solver provided with a very good initial estimate. The initial estimate is computed from the input elevation grid using a fast solver producing a lower quality interpolation. The fast solver uses a four-nearest-neighbor second order central difference approximation of the Laplacian heat equation. The result is a high quality interpolation of the Laplacian approximation. It takes less time and much less storage than either a direct solution (using factorization or row reduction) or a solution computed by the LSQR solver without a good initial estimate.

LSQR, analytical cartography, algorithm, solver, grid.

Interpolating information from known data to unknown data points is one of the classical problems of computational cartography. This technique is used widely in many diverse GIS (Geographical Information Systems) applications. One example is the derivation of DEMs from topographical contour maps for areas where DEMs are not available.
In this multi step process, contour maps are scanned into digital format (if they are not already archived that way). Then the contour line elevation data layer is separated from the other information on the map. The contour line data is then conditioned (to the highest degree possible) to correct bleeding, breaks, spurs bridges and other anomalies [1] . The contours must then be tagged with their elevation values in a machine-readable format. This is typically done by vector zing the contour lines using a line following method [2] and tagging the vectors with their elevations either automatically, or more commonly using a semi-automated labor-intensive process. The tagged vector data is then rasterized and transferred to a grid using an Interpolation algorithm. Finally, the gridded elevation values are written to some type of GIS format that can be used by other applications, such as the USGS ASCII DEM format.
One algorithm known to be an improvement over commonly used algorithms for the interpolation (or rather the approximation) of known elevations to a regular grid is described by Franklin. Viewshed determination for a specific observer, and selection of the most visible observers, can be combined to site a set of observers that, jointly, will cover the whole terrain. The process of selecting a set S of observers goes as follows.
• Initially S = {}
• Find a set, P, of very visible potential observers.
• Calculate all their visibility indices.
• Pick the most visible one, insert it into S, and determine its viewshed, ν.
• Delete any observers in P that are also in ν.
• Pick the most visible remaining observer.
• Add it to the set of observers, and find the union of its viewshed = with the other observers in S.
• Repeat until this union viewshed is the entire terrain.

The main objectives of the proposed work are as follows:
• To develop a computational technique that would allow the algorithm to be used for realistic data sets using small computers. The target size is 1201 by 1201 Digital Elevation Model.
• To compare the quality of the grids produced by the algorithm (once a computational technique was developed) with a commercially implemented algorithm. The hope is thus to apply Laplacian approximation algorithm to large data sets and to further demonstrate its utility to the cartographic community.

Application of Analytical Cartography includes terrain visibility Interpolation and approximation etc [3] . Interpolation and approximation includes a discussion of theory, mentioning some counterin- tuitive results. It also discusses terrain elevation interpolation, including using the solution of an over determined system of equations, with Matlab, to cause greater smoothness and to infer local peaks inside topmost contours. It also summarizes drainage determination.

This section samples applications in analytical cartography that have benefitted, in computer science.

Consider a terrain elevation database, and an observer, O. The viewshed is the terrain visible from O within some distance R of O. The observer might be situated at a certain height above ground evel, and might also be looking for targets at a certain height. Figure 1 on the following page hows a viewshed with error bars for a region in northeastern New York State. figure was produced by a program that classifies the grid cells [4] according to how likely they are to be visible.

In this section, we will first see some interpolation theory, then some practice from the CAD/CAM community, and finally some issues in terrain reconstruction.

The mathematics of interpolation is counterintuitive [5] , and the desired properties often mutually contradictory. Consider the Lagrangian interpolation of an N-1 degree polynomial to fit N points in 2D. Even though the generated curve passes through the data points, between them it will tra-verse far from the line joining adjacent pairs of points.

Despite the limitations of interpolation, used intelligently, it can do a very good job of increasing the size of images. Of course, discerning photographers want the best prints possible -- thus, the best interpolation possible is required.

It simply takes the color of a pixel and assigns it to the new pixels that are created from that pixel.

Bilinear interpolation uses the information from a pixel (let's call it the original pixel) and four of the pixels that touch it to determine the color of the new pixels that are created from the original pixel.

Bicubic interpolation uses the information from an original pixel and sixteen of the surrounding pixels to determine the color of the new pixels that are created from the original pixel.

Bicubic Smoother interpolation is a relatively new addition to the Photoshop interpolation methods. It also uses a Bicubic calculation.

With Stairstep interpolation, the interpolation is done in small increments using Bicubic interpolation. In other words, the interpolation is done in several small steps rather than one step as in traditional Bicubic interpolation.

Genuine Fractals samples from a larger number of pixels than Bicubic interpolation and uses its own algorithm to determine the value of the new pixels.

Implementation of a conjugate-gradient type method for solving sparse linear equations [6] and sparse least-squares problems:
Solve Ax = b
or minimize || Ax - b ||2
or minimize || Ax - b ||2 + d2 ||x||2.

The LSQR algorithm [7] was originally introduced by Paige and Saunders in the early eighties (Paige and Saunders, 1982a, b). Basically, such as the conjugate gradients (CG) methods, it is a subspace based iterative procedure to solve sys-tems of equations by means of successive approximations.

It is considered that the main objective of this paper, the development of a method to compute the Franklin approximation for DEMs as large as 1201 by 1201 elevation nodes, using an unsophisticated desktop computer, was technically accomplished. The method [8] developed as a result of this paper, the two-level iterative computation, has been demonstrated to compute input files of 800 by 800, 900 by 900, and 1201 by 1201 elevation nodes to completion. The test hardware platform with 256MB RAM was only marginally adequate for the 1201 by 1201 input file. target input file size is not unreasonable considering the ever decreasing cost of RAM.
Follow up studies have demonstrated that the quality of the solution vector for small problems is identical to that produced by direct solution of the system of equations.
A final study demonstrated that the Franklin algorithm is markedly superior to an interpolative algorithm offered by a commercial DEM extraction software package that is considered a leading product in its field.

The development of better methods to estimate the degree of convergence, as discussed above. These would ideally take into account the localized nature of errors and other convergence characteristics unique or common to iteratively interpolating terrains.

[1] Arrighi P., Soille P. (1999) Geovision, International Symposium on Imaging Applications in Geology (ICA) University of Liege, Belgium, Page1.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Powers D.L. (2000) Springer-Verlag.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Franklin W.R. (2000) Applications of Analytical Cartography’ Cartography and Geographic Information Systems 27(3), pp. 225-237.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Gousie M.K. and Franklin W.R. (1998) Eighth International Symposium on Spatial Data Handling (SDH), Vancouver BC Canada. Dept of Geography, Simon Fraser University, Burnaby, BC, Canada.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Matthews J.H. (1992) Science and Engineering Prentice-Hall.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Lay D.C. (2000) Linear Algebra and its Applications Addison Wesley.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Paige C.C. and Saunders M.A. (1982) ACM TOMS 8(1), 43-71.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Gousie M.K., Franklin W.R. (1998) ‘Contour to DEM’, Presentation Notes.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1- Viewshed with Uncertainty
	Fig.2- Interpolating 12 Points
	Fig. 3- Moving one point