Communications of the ACM
Home/Magazine Archive/January 2003 (Vol. 46, No. 1)/Efficient Summarization of Spatiotemporal Events/Full Text
Digital government
Efficient Summarization of Spatiotemporal Events
Summarizing the content of collections of temporally varying raster datasets in order to communicate it efficiently to an ever increasing and diversifying user community is a substantial challenge. In our NSF- sponsored digital government project we are working toward this goal by modeling the variations of an object's location (movement) and outline (deformation) through spatiotemporal helixes. A spatiotemporal helix is a novel spatiotemporal generalization model suitable for deformable objects. It comprises a central spine and several protruding prongs. The spine describes the spatiotemporal trajectory of an object's center, while the prongs describe the deformation (expansion or collapse) of the object's outline at specific time instances.
To construct helixes we have developed two novel image analysis techniques for spatiotemporal monitoring. The first is an extension of deformable contour models (a.k.a. snakes) to function in a differential mode. This is a deviation from traditional image-based object extraction, and allows us to not only extract a curvilinear outline from a current image automatically, but also to compare this outline to the previous record of this object, and identify local and/or global changes. We treat information as stochastic in nature, taking into account its accuracy to determine whether an outline has expanded or shrank globally, or whether it was deformed in a particular direction [1]. The locations where change has been detected produce prongs for the spatiotemporal helix. By selecting deformation thresholds we can alter the level of abstraction, modeling only major outline variations (high threshold), or even minor variations (low threshold) if so desired.
Our second activity on spatiotemporal monitoring is the development of a novel approach based on a variation of self-organizing maps (SOM) that allows us to generalize spatiotemporal lifelines. A lifeline can be defined as the trajectory of an object in space and time during a time interval. Using a SOM technique we model this lifeline through a sequence of nodes. SOM nodes correspond to breakpoints along these lifelines, and therefore mark instances where the moving object accelerates/decelerates and/or changes its orientation [2]. We proceed by using few initial nodes to describe the general behavior of the object, and then introduce additional nodes in areas of high curvature. The overall number of nodes has a generalizing effect on our approach, producing more abstract representations of an object's path as the number of nodes is reduced.
Combined, these two techniques comprise a powerful abstraction mechanism to monitor and model an event as it is captured in a sequence of raster datasets, by identifying specific points and instances where this event changed its rate, extent, and/or orientation [3]. This information is used to produce spatiotemporal helixes. In the accompanying figure we can see on the left the outlines of an object as they vary over time. The vertical axis corresponds to time, while the two horizontal axes define the spatial coordinates. On the right-hand side we can see the corresponding helix, with a central spine outlined by the blue nodes, and the protruding prongs. Collapse nodes are marked by red, while expansion nodes are marked by green stars (for global expansion) or black prongs (for localized expansion).
Helixes can be viewed as an essential mechanism that allows us to map knowledge onto datasets, thus providing a powerful tool for the development of complex and efficient knowledge bases.
Spatiotemporal helixes can be used to both model and communicate spatiotemporal information. Accordingly, they can be exploited as content descriptors, to summarize the content of large multitemporal datasets. These summarizations may be viewed as annotations of datasets, conveying field-specific knowledge. Indeed, the same dataset can have different summaries for different disciplines, as they may focus on different events captured within this dataset. Helix-based summaries support fast browsing of the content of large datasets, while also being suitable for subsequent analysis, as helixes maintain metric quality information. Image and video analysis and general geospatial techniques can be applied to helixes to establish similarities between events, and to group events into complex phenomena.
Within this context helixes can be viewed as an essential mechanism that allows us to map knowledge (as it is expressed by the definition of a phenomenon) onto datasets, and can thus provide a powerful tool for the development of complex and efficient knowledge bases. For further details, project publications, and future developments please refer to our project Web site at www.spatial.maine.edu/~peggy/ dgi.html.
References
1. Agouris P., Stefanidis, A., and Gyftakis, S. Differential snakes for change detection in road segments. Photogrammetric Engineering & Remote Sensing 67, 12 (2001), 13911399.
2. Partsinevelos P., Stefanidis, A., and Agouris, P. Automated spatiotemporal scaling for video generalization. In Proceedings of the IEEE International Conference on Image Processing (Thessaloniki, Greece, 2001), 177180.
3. Stefanidis A., Agouris, P, and Partsinevelos, P. SpatioTemporal Helixes for Event Modeling. In Proceedings of the National Conference on Digital Government Research (Los Angeles, Calif., 2002), 219224.
©2003 ACM 0002-0782/03/0100 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2003 ACM, Inc.
No entries found