# Cubic map algebra functions for spatio-temporal analysis.

 Author: Mennis, Jeremy

FREE EXCERPT

Introduction

The term "map algebra" was first introduced in the late 1970s (Tomlin and Berry 1979) and has since been used in loose reference to a set of conventions, capabilities, and analytical techniques that have been widely adopted for raster-based geographic information systems (GIS) (Tomlin 1990; 1991). Map algebra attempts to accommodate a wide variety of GIS applications in a clear and consistent manner by decomposing data, data processing capabilities, and data processing control techniques into elemental components that can then be recomposed with both ease and flexibility. The resulting algebra-like language is one in which single-factor map layers are treated as variables that can be transformed or combined into new variables by way of primitive operations invoked through expressions conforming to a well defined syntax. Map algebra has been incorporated in many GIS and remote sensing image processing packages, and it has been extended in areas ranging from cellular automata (Takeyama and Couclelis 1997) to environmental modeling (van Deursen 1995; Hofierka and Neteler 2001; Pullar 2001) to topographic analysis (Caldwell 2000). It is widely recognized as one of the most influential analytical frameworks for GIS-based raster data handling (Longley et al. 2001; DeMers 2003).

Like most of the analytical frameworks embodied in current GIS packages, map algebra is primarily oriented toward data that are static. Each layer is associated with a particular moment or period of time, and analytical capabilities are intended to deal with spatial relationships. In its original form, map algebra was never intended to handle spatial data with a temporal component. However, as the availability of spatio-temporal data has increased dramatically in recent years due to the growth of satellite remote sensing and other technologies, and as the sophistication of things such as video games and animation in the motion picture industry has raised popular expectations for spatio-temporal processing capabilities there has also been an increasing demand for the spatio-temporal extension of GIS.

One of the reasons for the widespread adoption of conventional map algebra for raster processing in GIS is its simple syntax and the ability to string together multiple functions to create more complex models. These features provide a simple yet powerful toolbox for raster data manipulation analysis. The inclusion of a library of temporal map algebra functions in GIS packages would be just as useful and facile for analyzing the multitude of spatio-temporal raster data now being generated. We note that despite the growing volume of research on spatio-temporal data models over the past dozen or so years (e.g., Langran 1992; Peuquet 2001), the extension of map algebra to the temporal dimension has been largely ignored by the spatio-temporal GIS research community. The present research is intended as a first step toward the development of such a temporal map algebra library by providing a conceptual foundation for temporal map algebra and the implementation of a select set of map algebra functions that may be applied to spatio-temporal data.

In the following section a framework for the extension of map algebra to the temporal dimension is described. This design is then demonstrated through a prototype implementation of certain temporal map algebra functions which we call "cube functions." Whereas conventional map algebra functions operate on data layers representing two-dimensional space, cube functions operate on data cubes representing two-dimensional space over a third-dimensional period of time. A case study is used to demonstrate how cube functions can be utilized. This case study analyzes the spatio-temporal variability of remotely sensed, southeastern U.S. vegetation character over various land covers and during different El Nino/ Southern Oscillation (ENSO) phases.

Motivation

A variety of approaches for storing and analyzing spatio-temporal data in GIS have been proposed and implemented (cf. Abraham and Roddick 1999; Peuquet 2001). Most of these approaches have focused on the representation and analysis of spatial phenomena that have a temporal beginning and end, and which may change in their spatial extent, location, or non-spatial properties over their lifetime (Worboys 1994; Wachowicz 1999; Hornsby and Egenhofer 2000). Additionally, conventional metric and topological spatial operators have been extended for spatio-temporal analysis (Breunig 2003). This research has been heavily oriented toward spatial phenomena that are modeled as discrete objects, such as countries or cars, rather than qualities of space that are modeled as continuous fields, such as temperature or population density. Such approaches have generally involved temporal extensions to structured query language (SQL) processing of vector-encoded data (Erwig et al. 1999; Griffiths et al. 2001).

In contrast there have been fewer efforts at developing representation and analysis strategies for spatio-temporal field-like data stored in raster format. The most straightforward approach for storing spatio-temporal raster data is the "snapshot" model in which change through time is represented using a series of spatially registered grids, each corresponding to a particular moment in time (Langran 1992). Another approach employs a form of spatio-temporal "run length encoding" in which temporal events that mark changes in the value of individual grid cells are stored (Peuquet and Duan 1995). Other approaches have used object-oriented techniques to store spatio-temporal arrays of environmental measurements encoded in a spatio-temporal "data cube" in which two cube dimensions are spatial and the third is temporal (Raper and Livingstone 1995; Mennis 2003).

The statistical analysis of spatio-temporal raster data has been undertaken for interpolation (Mitasova et al. 1995), geostatistics (Kyriakidis and Journel 1999; Christakos 2000), and Bayesian approaches (Christakos et al. 2002). Researchers in remote sensing have also applied spectral analysis and principle components analysis to extract temporal signals from time series of imagery (Eastman and Fulk 1993; Jakabauskus et al. 2001). Other researchers focusing on spatio-temporal raster processing have addressed feature extraction, for instance in the recognition of meteorological phenomena from time series of observational meteorological data, remotely sensed imagery, or general circulation model (GCM) output (Stolorz et al. 1995; Yuan 2001; Mennis and Peuquet 2003). Van Deursen (1995) and Wesseling et al. (1996) describe a language for extending the spatial capabilities of map algebra to support dynamic modeling, implemented in the GIS PCRaster.

Also of relevance to the present research is three-dimensional raster GIS in which space is exhaustively partitioned into a regular tessellation of three-dimensional cubic volume elements (voxels) instead of two-dimensional square grid cells (Raper 1989; 2002). This approach has been used for a variety of geologic and atmospheric science modeling and visualization applications (Hibbard et al. 1994; Marschallinger 1996; Masumoto et al. 2004). Of note is the Geographic Resources Analysis Support System (GRASS) GIS, originally developed by the U.S. Army Construction Engineering Research Laboratories, which supports three-dimensional raster encoding for which a limited set of map algebra functions are available (Brown et al. 1997; Neteler 2004). Other GIS software packages that handle raster data, such as ArcGIS (Environmental Systems Research Institute, Inc.), provide the ability to link multiple grids in a "stack" to mimic a three-dimensional representation, though the analysis capabilities associated with these stacks are typically limited. Raper (2002) provides a taxonomy of three-dimensional spatial query and analysis functions.

Research in image processing has also described algorithms similar in nature to those used in three-dimensional GIS. These algorithms have focused on the extension of filters, image arithmetic, and segmentation to three and four dimensions (Nikolaidis and Pitas 2000). This research has been applied primarily to medical imaging (Wan and Higgins 2003) as well as to motion detection in video sequencing (Rajagopalan et al. 1997) and time series of satellite imagery (Yamomoto et al. 2001).

Despite this breadth of research in spatio-temporal and three-dimensional GIS there is a notable lack of attention given to extending map algebra beyond two spatial dimensions, and particularly to the temporal dimension. In fact, none of the research cited above explicitly addresses the extension of map algebra algorithms to the temporal dimension. Because of the lack of general-purpose, spatio-temporal raster data manipulation capabilities in current commercial GIS, researchers working with spatio-temporal raster data have been forced to develop customized algorithms (e.g., Yuan 2001; Mennis and Peuquet 2003). Consequently, these algorithms are specific to the application domain under investigation and cannot be readily reused in other application contexts.

In the present research we demonstrate how the original map algebra construct can be extended to support spatio-temporal raster data analysis in a manner that transcends any one particular application domain. For this purpose we draw from previous research in spatio-temporal GIS in the use of the spatio-temporal cube metaphor for data encoding and manipulation. The cube function algorithms are adapted from conventional map algebra and its extension to three spatial dimensions, as well as from related functions associated with three-dimensional image processing.

Extending Map Algebra for Spatio-Temporal Processing

Two-Dimensional Map Algebra

In the original map algebra, each variable or "layer" is a bounded plane surface on which position is expressed in terms of Cartesian (X,Y) coordinates. The portion of...