Representing Uncertainty of Qualitative Thematic Maps with an Inter-Map Cell Swapping Heuristic

Introduction

Abstract

Key words: uncertainty, thematic maps, conflation, conditional simulation, unconditional simulation, geostatistics, and Monte Carlo simulation.

Probability modeling

• Conceptual errors in a map are either:
• unmapped inclusions (probably smaller than the minimum mapping unit of a well-formed map) or
• a misclassification of a class polygon (of a less than perfect map).
• Qualitative thematic map errors are usually represented as a probability vector for each cell in the study area.
• Probability vectors can be used to represent the transition between two classes if there are cartographic errors.

(1)

• The greater the spatial dependence, the larger the inclusions are.

Modeling spatial dependence

• The fields of geostatistics and landscape pattern metrics have both provided useful spatial statistic measures for qualitative thematic maps.
• Correlograms are one method to help define spatial dependence and spatial distribution in geostatistics. While variograms are popular in conditional simulation applications, correlograms provide advantages for modeling spatial uncertainty, normally a stochastic simulation application.
• Landscape pattern metrics, a set of measures defining land-cover map structure, can be used to describe many, if not all, qualitative thematic map patterns. Different landscape pattern metrics measure connectedness, diversity, shape complexity, and size.
• Choosing the appropriate landscape pattern metric or geostatistical measure is a difficult choice. Monte Carlo simulation requires a set of application input maps in which each input map consists of a possible representation of reality.
• There are two conceptual methods for constructing spatial dependence models: random field models and cell swapping heuristics.
• Random field models use a set of parameters to define the random field function.
• Intra-map cell swapping heuristic swaps two random cells in a realization map if the potential realization map more closely matches the goal spatial statistic.
• A cell swapping heuristic's significant advantage over random field models is that swapping cells can create random fields mimicking any spatial statistic.

• A generalized map, for the purpose of this paper, is a map containing qualitative thematic information at a resolution too coarse and/or attribute information too inaccurate to be useful for a particular application.
• Application quality data is qualitative thematic information accurate enough and with a resolution fine enough to achieve useful application results.
• The requirement that a generalized map and samples of higher quality data be available is both a potential solution to a classic uncertainty issue as well as a practical way to understand the impact of higher quality data.
• Maps are, by definition, generalized. Imprecise or nonexistent map error statements as well as the lack of consensus on how to precisely describe map uncertainty makes maps suspect as to whether they are accurate enough for a particular spatial application.
• Decision makers can only be certain of application results with well known applications using standardized maps.
• A probability vector is a set of values representing the likelihood each class is located in that particular cell.
• The generalized map is re-sampled to the resolution of the application quality data.
• A densogram measures the proportion of each application quality cell’s class at various distances from cells of the same class.

Figure One, Geology Densogram

• The inter-map cell swapping heuristic begins with a set of random thematic maps.
• Each cell within each random thematic map is given a class value based on the probability vector defined by the location of class polygons in the surrounding generalized map.
• Cells are swapped at the same location from different maps if the resulting maps’ densograms provide a better overall fit to the application quality data’s densogram.
• This heuristic is continued until no more possible cell swaps are possible.

Probability Model

• The choice of probability model should be dependent on the types of errors most prevalent in the study.
• When the generalized map's minimum mapping unit (MMU) is many magnitudes larger than the MMU of the application quality data, thematic errors will be much more prevalent than positional errors.
• Because cartographic errors are the bulk of errors in this case study, the likelihood a cell contains a specific class is based on how far from the more generalized polygon edge the cell is.
• Conceptually, this probability model creates buffers around as well as within class polygons and determines the density for that class for each buffer. Class density within a distance buffer, or lag, determines the potential the class exists at that distance.
• Each realization cell determines its probability vector by normalizing all class potentials based on the cell's distance to the generalized map class polygon.

(2)

(3)

In the equations above, A_j is a sampled point of application quality data, M_i is a point on the study area map, d_i,j is the distance between points i and j, L is the lag interval, c is a class represented in the samples of application quality data, and l is the lag.

The cell probability equation, equation (4), determines its probability vector by normalizing all class potentials based on the cell's distance to the generalized map class polygon. In the equation above, M_i and M_i are points on the study area map, d_i,j is the distance between points i and j, L is the lag interval, b is a class in the study area map, C_m are all classes in the study area map, and c is a class represented in the samples of application quality data, and l is the lag.

Densogram Spatial Statistic

In the equation above, A_i and A_j are sampled points of application quality data, d_i,j is the distance between points i and j, L is the lag interval, c is a class represented in the samples of application quality data, and l is the lag.

Spatial Dependence Model

Random field models can create reasonably precise representations of goal surfaces in a comparatively short period of time. However, random field models require multiple parameters to be determined in order to provide a good fit. Variogram models have sill, range, and nugget parameters, and the random field model used in this case study (from Ehlschlaeger & Goodchild, 1994a) has three parameters to make a decent fit. Cell swapping heuristics, on the other hand, require no parameters. However, they consume many computer CPU cycles to complete, and the resulting solutions can fit poorly. The following figures illustrate this behavior.
 

Figure Two, Densograms of Several Classes

Figure Three, Errors of Uncorrelated Realization before Inter-map Swapping	Figure Five, Errors of Correlated Realization before Inter-map Swapping
Figure Four, Errors of Uncorrelated Realization after Inter-map Swapping	Figure Six, Errors of Correlated Realization after Inter-map Swapping

All tests were done on a 200mhz Pentium computer. The probability distribution required 15 minutes to complete. The random field estimator and generator took 9.5 hours to construct correlated random fields with less error than the results of the cell swapping heuristic with uncorrelated random fields as its inputs. The cell swapping heuristic with uncorrelated random fields required 47 hours of swapping time to complete. Thus, the uncorrelated cell swapping heuristic was slower and less accurate than the random field model (even without manual fitting). The correlated cell swapping heuristic was the slowest of all tests. To find the optimal solution, 547.5 hours of processing time was used even though only 41.5% of the cells were swapped, compared to the number swapped by the uncorrelated cell swapping heuristic.
 

Figure Seven, Class Errors of Initial Noise

Figure Eight, Class Errors after Swapping fitted to 1600m.

 

Figure Nine, Class Errors after Swapping fitted to 160m.