Interpolation and DEM Accuracy

The accuracy of continuous raster surfaces relies on the ability of the interpolation method to calculate values for areas between sample points that are as close as possible to the actual measurements.  This is, of course, determined by taking a measure of the difference between a value taken directly from the field and one produced by an interpolation method- the less difference between these two measures, the more accurate the interpolation.  Vertical (elevation) accuracy in DEM data can be influenced by a number of factors, most notably the features of the ground cover, as these can influence and obscure remotely sensed images and data.  Bias and uncertainty can be introduced rather easily into a data set, and can lead to systematic over or underestimation.  Looking at the summary statistics of the differences between measured and interpolated values for different methods may look something like this:

	IDW elevation	Spline elevation	Kriging elevation
mean (m)	-1.544	-2.365	-1.967
standard deviation (m)	11.695	10.196	12.024
median (m)	-1.759	-1.838	-2.144

The interpolation methods across the top- Inverse Distance Weighting (IDW), spline and kriging- produced elevation values for 63 different points that were then compared to the actual elevations, and the differences between the values are summarized in the table above.  The method with the lowest mean difference- IDW- could be argued as superior to the others, as it produces values that are, on average, closer to the actual measure.    

Estimating Values for Unsampled Areas: Surface Interpolation

Many different phenomena are represented on maps as being continuous across a large surface area, despite the fact that the measurement for whatever is being depicted is necessarily taken from a set of discrete, measured point locations.  A news station weather map of north America, for example, might show areas with more precipitation or higher temperature in different colors across the map.  The methods used to estimate the values of some variable(s) in locations where samples are not directly taken from, based upon the values of sampled points in the proximity, is called spatial interpolation.  There are a plethora of different interpolation methods, differing in complexity and difficulty to execute, and each has its own strengths and weaknesses.  Thiessen polygons and Inverse Distance Weighting (IDW), for example, are relatively simple interpolation methods, and are somewhat easier to perform.  More sophisticated methods, like splining or kriging, which use spatial statistics in their calculations, may be preferable if a higher degree of accuracy is required.

The above map depicts concentrations of biochemical oxygen demand (BOD) in Tampa Bay, and is generated from sample data that goes with each of the point locations.  IDW is the interpolation method used to generate the above raster surface, which shows the estimation of concentrations across the bay based on the measurements at the sample points.  IDW is a relatively simple and common measure, but it is valuable in a number of spatial analysis scenarios.  This, and most other interpolation methods, rely on the assumption of autocorrelation- that what is nearer is more alike than what is further away.  Although IDW is an adequate and appropriate method of interpolation in this application, it may not be appropriate for every situation- the choice of method is based upon the characteristics of the application.

Elevation data: TIN vs. DEM (the vector/raster dichotomy epitomised)

In the world of geographic information science there exists two primary kinds of data- vector and raster.  The differences between the two could be discussed to no end, and everyone has their preference, but for some applications one can be simply superior to the other.  A  rather perfect example of this dyad is the comparison of elevation depicted with a vector TIN data set vs. that which is displayed with a raster DEM.  The triangular irregular network (TIN) is created from a series of elevation measurements called 'mass points,' which are connected with 'breaklines,' and elevations are interpolated from these.  The digital elevation model (DEM) is a digital representation of topography, which is displayed with a grid of spot heights, and is a widely used type of raster image.  Contour lines are a standard 2D representation of elevation, and can be created in ArcGIS from either a TIN or a DEM data set.

Above is an image with contour lines created from the same area, one set created from a TIN, and one from a DEM.  The most immediately notable difference between the two sets of lines is that the TIN contours are more angular, and don't curve in the same way as those created from the DEM.  This is somewhat logical, given that the TIN consists of discrete triangles, whereas the DEM represents a more continuous surface of values.  Because elevation is a more continuous phenomena- it's not delineated in nature with discrete lines- one might contend that the DEM provides the superior representation.  The TIN data lacks the more nuanced variations in values, which allow for the curved contour lines.  Thus it could be concluded that though vector data is invaluable in many situations, a raster image is somewhat preferable in the examination of phenomena like elevation.   

Location-Allocation Modeling

Anyone who has ever wondered how, exactly, it is decided just where things like new schools, new stores or other facilities will be located has considered a problem of location-allocation.  In making these decisions, which mainly involve analysis of things like travel cost, distance, and customer locations, a multitude of factors must be considered, and locations are decided upon based on their suitability.

Above is a comparison of market area assignment to distribution centers- both before and after the location-allocation model.  Each of the 22 distribution center points serves the market areas, based upon customer locations.  After the location analysis, the market area assignments are improved, as the number of customers within each and the distribution centers they use have been optimized according to our specified criteria.

Vehicle Routing, Round 2

Road networks are complicated bastions of all manner of spatial quandaries, most notably, for our purposes, those involving vehicle routing.  There is no end to the permutations of various circumstances these kinds of problems can involve, and knowledge of some of their more common manifestations is invaluable.  When these problems involve ordered pairs of pick ups and drop offs, there are a multitude of parameters we can specify to maintain various characteristics of our intended route- time windows, driver breaks, wheelchair access (if required), distance, etc.  According to the specifications we input the actual resulting route can vary widely.

Above is one solution (series of routes) to a routing problem involving pick ups and drop offs of people at locations in south Florida. The parameters used to create these routes include drop off and pick up time windows, maximum working hours and breaks for drivers, and route zones, which constrain where certain routes can travel.  The initial routing solution created for the above had constraints which produced an output with five "unassigned" locations, which were not assigned to any of the routes.  The second solution, shown above, modified the parameters such that two additional vehicles/routes were included, which eliminated the unassigned locations.  The customer service aspect of this modification is notable with regards to this routing problem- the ability to include all of the desired stops, which the second set of routes (above) does, increases the number of customers served, which is obviously beneficial.  Additionally, the extra routes may relieve some of the burden on the rest of the vehicles, allowing more flexibility in service times, which also benefits the customer.  

Road Networks and Vehicle Routing

Road networks are a feature of the landscape that is rife with potential for spatial analysis, and one of the more common problems involving these networks is the challenge of creating an appropriate vehicle route.  The time it takes a vehicle to get from point A to B varies according to a plethora of factors, including speed limit, road size, traffic patterns, etc., and the route chosen for the vehicle may need to take any number of these factors into consideration.

The above route maps are similar to one another, but the two do actually vary slightly.  The map on the left is identical to the one on the right, except that its route was created using rules involving traffic data, which changed the route, and actually added about an hour onto its travel time.  This kind of route optimization is invaluable to those who plan these kinds of routes- the more factors one can take into account when creating something like this, generally the better.     

Road Networks and the Spectre of Exhaustive Data Completeness

Spatial data is, ideally, completely representative of the real-world entities it is portraying.  In reality there is necessarily some amount of generalization inherent to any spatial data, a result of translating and scaling it for its practical use.  The perfectly complete data set is a very rare entity, and road networks like TIGER, TeleAtlas, and locally sourced street centerlines more often than not exclude some amount of road segments that are actually present.  This exclusion results from things like conscious decisions to leave smaller, privately-owned roads out of the data set, and errors of omission in data digitizing/collection procedures.  

The above represents a county and two different road network data sets- one from the census bureau's TIGER database, and another with locally collected street centerline locations.  A 1 km by 1 km grid is overlaid, in order to systematically derive a spatially comparable measure of each data set's relative completeness.  The total length of road segments within each grid cell can be compared between the two, and a measure of the magnitude of difference between the two is depicted with the choropleth map above.  Thus we can conclude that the TIGER data set is more complete than the street centerlines, as it contains a larger amount of total road segments- which is our sole qualifier for data comprehensiveness.  The caveat to that is, of course, that we may wish to consider other factors in gauging the data's relative "completeness."  If the TIGER data contains more driveways and non-navigable road segments, for example, we may wish to reevaluate our definition of "complete," as the superior accuracy of the other street centerline data renders it somewhat more "complete" than the TIGER, so to speak.     

Adventures in Metadata

This week's exercise in Data Quality includes examination of various data standards, namely the National Standard for Spatial Data Accuracy (NSSDA) and the older National Map Accuracy Standards (NMAS), which indicate the data set's accuracy, and are typically found in its metadata.  The actual procedure described in the NSSDA involves taking sample points from a test data set and a known, highly accurate reference value, and produces a value that indicates the tested data's horizontal or vertical accuracy at a 95% confidence level.

Above is a map, which includes 20 sample points, taken to be compared with a reference data set, which was created using aerial imagery.  The sample location distances from the reference points are used to calculate an error statistic, which is typically included in a data set's metadata.  The statistical and testing method prescribed in the NSSDA allows for a statement on the likely amount of error in the data, like the one for the map above-
tested 2492.12642 feet horizontal accuracy at 95% confidence level.  This indicates that a horizontal position taken on the map will generally be within about 2,492 feet of its actual location on the ground, as accurate as true location is, 95% of the time.

Spatial Accuracy and Precision

After a brief respite, I return to the GIS academic gauntlet with a look at the many facets of error in spatial analysis- primarily those involved in measurement precision and accuracy.  

  

Horizontal Accuracy - 3.8 meters
Horizontal Precision - 4.3 meters

The above map and measurements are based on a set of 50 point locations, recorded with a GPS unit in the same location at different times.  The precision of the measurements is a measure of how close each measurement is to the others taken in the same place, as there is some inherent error in commercially available GPS unit readings, and each of the 50 above seem to have given a relatively different location.  The average of the 50 is the larger yellow point in the center, and the blue bands around it correspond to the areas containing 50%, 68% and 95% of the points, respectively.  Because 68% of values in a normal distribution fall within one standard deviation of the mean, we can say that the average of the values within the 68% band gives a measure of horizontal precision- 4.3 meters.  The horizontal accuracy is a measure of the point distances from the true, or accurate location, which is obtained from a benchmark located where the measurements were actually taken on the ground.  The distance from that benchmark's known coordinates to the average point location is 3.8 meters, and so the horizontal accuracy of the GPS readings is determined to be 3.8 meters.  

Mapping the Fourth Dimension

Our 3-dimensional world is the usual subject of 2-dimensional maps; their purpose is to accurately depict geographic extent on a readable/publishable surface, with or without thematic content.  The purpose of adding the 4th dimension of time is somewhat intuitive- maps of the same area through time can give a viewer an understanding of change in some feature.  The problem in depicting the 4th, temporal, dimension on a 2-dimensional surface is remedied by the use of various spatiotemporal visualization techniques, the most effective of which, it could be argued, is the map animation.  The simplest form of this variety of cartographic visualization is the display of two or more maps, adjacent to one another, showing the same geographic area at different times.  The change in the area depicted is evident in the difference(s) between the various maps.  While this method is effective, actual animation on a map is an even more salient method of displaying areal change through time.  

       
The above graphics represent two years- 1790 and 2000- and contain proportional symbols indicating the most populous cities in the U.S. at those times.  The two maps are actually the beginning and ending frames of an animation, which shows the same map for each 10 year period between 1790 and 2000, and thus gives the viewer an idea of where the major centers of population in the U.S. were for each decade.  The ease of doing so with a simple animation, cycling through each decade, is fairly large in comparison to creating and displaying something singular including separate maps, one for each decade.