Go to Paper
Return to GeoComputation 99 Index

Error-Constrained Change Detection

WARE, J. Mark (jmware@glam.ac.uk), and JONES, Christopher B., University of Glamorgan, School of Computing, Pontypridd CF37 1DL, Wales, U.K.

Key Words: equivalence testing, data uncertainty, Bayesian classification, locational error

We consider the problem of detecting real-world changes that occur over a period of time. This is achieved by comparing a pair of vector-defined polygon coverages, A and B; A represents a given theme for a particular region at the start of the time-period (t₁), and B represents the same theme and region at the end of the time-period (t₂). The standard technique for detecting change is to intersect A and B so as to produce a third coverage C. Each intersection-polygon in C is associated with two theme classification codes; one describing theme class at t₁, the other describing theme class at t₂. If these classification codes differ, then the polygon is labeled as corresponding to an area that has undergone change. A problem with adopting this approach is that it assumes the source coverages are free of error. This will not usually be the case; it is likely that A and B are subject to both classification error (i.e., some polygons are assigned to a wrong class) and positional error (i.e., some polygon boundaries are in the wrong location).

In this paper we hope to improve on the standard change detection procedure. To date, we concern ourselves with positional error only. We try to achieve improvement by matching and aligning boundaries (or parts of boundaries) in A with equivalent boundaries (or parts of boundaries) in B. The term equivalent boundaries is used here to describe a pair of boundaries that are intended to be representing the same real-world phenomena. It is most probable that, because of locational error, equivalent boundaries will not match exactly with regards to their geometry. Boundary matching is achieved using Bayesian multivariate classification, in which candidate matching pairs are classed as being actual matches or not. To begin, conditional a priori probability is calculated using geometric signatures obtained from a training set of manually classified boundary pairs. The signatures used include comparisons based on length, sinuosity, bandwidth, anchor length, and angle. Next, candidate matching boundary pairs are found using a crude feature matching procedure based on buffering. In essence, this procedure deems two boundaries (or parts of boundaries), bA and bB, to be a candidate match if all of bA lies within a pre-defined distance of bB and all of bB lies within a pre-defined distance of bA. Each candidate matching pair (bA, bB) is then assigned a posteriori probability of it being an actual match. This probability is calculated using signatures derived from (bA, bB) and the previously derived a priori probability. Having been calculated, the a posteriori probabilities of all candidate matching boundary pairs are examined and compared against a pre-defined probability threshold value, and a list of matching boundary pairs is produced. Each matching boundary pair is then aligned using a boundary merging procedure. This procedure makes use of weighted interpolation, thus, allowing for a range of results (i.e., bA replaces bB in B, or bB replaces bA in A, or bA and bB are both replaced by a weighted average). Having updated A and B, we can produce a modified intersection coverage CM. The assumption is that when compared to C, the change statistics derived from CM will more accurately represent change that has taken place in reality.

The above method has been implemented as a collection of C functions. These functions are callable from within an ArcView Script and can be applied to ArcView Shapefiles. Testing is being carried out on land-cover data supplied by the Macaulay Land Use Research Institute. Three data sets are available, each representing the same region of the Cairngorms (Scotland) at different times (1946, 1964 and 1988). These data have been manually processed, and all matching boundary pairs were recorded. A subset of the data was set aside for training purposes. The full paper will report on a comparison of the results of automatic change detection, based on the training set, with the independent data produced by expert manual interpretation.