Granular Description of Qualitative Change

Abstract

Qualitative representations of spatial knowledge have been widely studied and a variety of frameworks are used to express relationships between static regions. Dynamic regions present a much greater challenge, but are important in practical applications such as describing crowds of people moving over time. Previous work has analysed changes as regions merge and split and as new regions are created and existing ones disappear. We present a novel framework for the qualitative description of spatial regions based on two levels of granularity. Introducing granularity yields significantly more informative qualitative descriptions than are available from a single level of detail. The formal model represents a region, which may have multiple components, as a bipartite graph where the nodes are the components of the region at a fine level of detail and at a coarse level. The edges of the graph model the way that a component in the coarse view can be made up of parts of components at the more detailed level. We show that all graphs of this form (except for some degenerate cases) can be realized as regions in a discrete space of pixels, and we develop a theory of relations between these graphs to model the dynamic behaviour of regions.