Granular Description of Qualitative Change

1 Introduction

There are various formal systems of qualitative relations between static spatial regions. For example, the RegionConnection Calculus [Randell et al., 1992] can represent situations such as regions overlapping, touching or one being contained within another. Change in this setting is modelled by conceptual neighbourhood graphs [Freksa, 1991] which describe transitions between relations. If we imagine a set of regions moving against a background space, there are applications for which other kinds of qualitative change may be significant. Crowds of people provide one example. One crowd may divide and re-form later with fragments of other crowds. In a surveillance application it may be more important to monitor how a crowd is constituted from parts of earlier crowds than to monitor the spatial relationships between the regions occupied by different crowds at different times.

At the most basic level we can observe four kinds of change to regions: a region may split into two, two regions may merge into one, a region may disappear or a new region may form. These changes have been applied to geographical regions in [Hornsby and Egenhofer, 2000]. Jiang and Worboys [2009] have analysed topological changes in regions determined by wireless sensor networks. Besides the four kinds of change they also identify self-merges and self-splits, as in the diagram below, which can be regarded as splits and merges respectively to the background region.

Classifications of change arise in other application domains. For land-ownership, [Sp´ery et al., 1999, p469] describes five elementary changes: division, merge, extraction, passage, and rectification, which includes the redrawing of a shared boundary between two land parcels without affecting their overall extent.

More complex scenarios of change, many of which involve some metric aspect, can readily be found. Examples include a region growing or contracting, two regions moving relatively closer or further apart, or a number of regions moving relatively closer to each other to form an identifiable agglomerate. In the present paper we show how a wide range of qualitative changes, including regions growing and shrinking, moving closer and more distant, and different kinds of splitting and merging can all be derived by observing which of the four basic changes occurs at two different levels of detail, as well as observing features of the change of level of detail itself.

Granularity has interdisciplinary literature which can only be very briefly surveyed. A classification of different kinds of granularity is presented by Keet [2006]. From an AI perspective Hobbs [1985] used a notion of indistinguishable terms based on their behaviour under substitution in certain predicates. Temporal granularity is examined by Euzenat [1995; 2001], who also suggests how this might be applied to spatial reasoning. Stell and Worboys [1998] developed an abstract framework for spatial data (as for example in geographical information systems) at multiple levels of detail. Studies of connections between different formulations of granularity include [Zhang and Shen, 2006; Dubois and Prade, 2011].

Galton [2003] analysed how granulation, that is changing the level of detail, can affect qualitative descriptions. For example, separate regions which are relatively close may become connected under granulation. The notion of granulation used in [Galton, 2003] differs significantly from that in the present paper. Galton takes the detailed view to be continuous space and obtains a less-detailed view by dividing up the detailed view into a grid, the cells of which contribute to the coarser view if they are at least 50% covered. Although we use a discrete space at both levels of detail, the most significant difference between our notion of granulation and that in [Galton, 2003] is that instead of placing a coarser grid over the detailed view we use a notion of granulation based on mathematical morphology [Serra, 1982; Bloch et al., 2007]. Several of the effects noted in [Galton, 2003], for example change in relative size, depend critically on the placement of the grid. Our approach is translation invariant which rules out some of these effects.

The theory of rough sets [Pawlak, 1982] provides one formal model of granularity, and mathematical morphology has close connections with rough sets [Stell, 2007]. Mathematical morphology has also been used [Aiello and Ottens, 2007] to provide an implemented hybrid modal logic for spatial reasoning. The approach in the present paper is quite different as we are concerned with types of change that can occur instead of reasoning about topological relations in a static setting.

2 Motivating Scenario

Consider the following simple example of four stages in change undergone by a region viewed at two levels of detail. The images were obtained from an implementation in Matlab of the method described in Section 3.1. In the example time proceeds horizontally, left to right, and granularity changes vertically from more detail at the lower level to less detail at the upper level.

Moving from the lower to the upper level can cause narrow gaps to close up and thin parts of regions to vanish. Assume that at each level we can detect only the four basic qualitative changes (merge, split, creation, destruction). At the lower level we see that a single region divides into two. At the coarse level we see a single region divides into two and that each of the two parts then divides into two.

Using both descriptions together at each stage we obtain a more detailed account. Between the first and second times the single region remains a single region at the fine level but divides at the coarse. This tells us that the shape must have changed so as to appear to divide when seen coarsely. We deduce a change in shape so that the region now consists of two more substantial parts connected by pieces which are too slight to be seen at the higher level. Between the second and third times, the low-level narrative is that the region splits, but there is no qualitative change at the upper level. This tells us that the split is too small to be coarsely evident, hence we deduce a crack or narrow fissure has opened up. Finally, between the third and fourth times, the detailed view says no change, but the coarse detects two splits. The explanation will be that the previous crack has widened substantially - we can discount the possibility that another split different from the crack but larger has appeared as this would have produced a split at the lower level.

The idea that we can derive qualitative information with metric features (e.g. regions moving further apart) just by combining two non-metric qualitative descriptions is exactly what the use of granularity would be expected to provide. In combining the two descriptions, it is the granularity that encodes the metric aspect, and in this informal example we have essentially assumed that there are non-zero distances which are indistinguishable from zero at the coarser level.

3 2-Graphs

3.1 Structures defined

In our formal model we reduce a region to an abstract set of its connected components which form nodes in a graph. There are two sets of nodes for the two levels.

Definition 1. A 2-graph G consists of an ordered pair (N0,N1) of sets (the nodes) together with a set of edges E ⊆ N0 × N1.

An example of a 2-graph is N0 = {1, 2, 3, 4}, N1 = {1, 2, 3, 4, 5}, and E = {(4, 2), (1, 1), (2, 1), (2, 3), (2, 4)}. This example can be drawn as in the diagram below.

A realization of a 2-graph provides a region [[N0]], assigns the connected components of this region to the elements of N0, and assigns the connected components of a less-detailed view of [[N0]] to elements of N1, so that the intersection of high-level components with approximations of individual low-level ones corresponds to the existence of edges in the 2graph. Unrelated upper level nodes (e.g. 5 in the above example) are realizable by sets of small regions which are visible collectively but not individually at the upper level.

We choose here to use realizations in a discrete space, which we take to be Z2 . The elements of Z2 are often called pixels in this context. We approximate subsets of Z2 by using the operations of closing and opening from mathematical morphology [Serra, 1982]. These depend on a particular structuring element, T , which in a simple case can be a 2 × 2 block of pixels. Given a region X ⊆ Z2 the closing of X is the complement of Y , where Y is the largest region in the complement of X that can be expressed as a union of copies of T. Visually such a union covers Y by (possibly overlapping) copies of T . The opening of X is the largest region inside X that can be covered by copies of T . We approximate a region X by first closing X and then opening the result by the same structuring element. The following examples illustrate this showing four regions in the lower row with their approximations by a 2 × 2 square structuring element above them. In the second example the approximation is the empty set.

Definition 2. A realization of a 2-graph G = ((N0, N1), E) consists of the following data:

1. A structuring element inducing an approximation function α : PZ2 →PZ2 .
2. A subset [[N0]] ⊆ Z2 and a bijection β : N0 → C ([[N0]])
3. A bijection γ : N1 →C(α[[N0]]).

These data must satisfy: (m, n) ∈ E iff αβm ∩ γn ̸= ∅. A 2-graph is realizable if it has a realization.

3.2 Realization theorem

Theorem 1. Every 2-graph,G, is realizable except when

1. N1 is non-empty and N0 is empty, or
2. N0 has exactly one element and some element of N1 lies on no edge.

Proof. We show first that 2-graphs not of these forms are realizable, by constructing realizations using a 2 × 2 square structuring element. Let G have v0 low-level nodes and v1 high-level nodes, where v0 > 1. We assume that N0 = {1, 2, . . . , v0} and N1 = {1, 2, . . . , v1}.

The required subset of Z2 is described by an array of zeros and ones. This specifies the subset containing (i, j) iff the entry in the ith row and jth column of the matrix is 1. The matrix has 3v0 rows and 3(2v1 - 1) columns and consists of v0(2v1 -1) blocks, Bi j , each of which is a 3×3 matrix. The blocks take two forms depending on whether j is even or odd. In the case that j = 2q - 1 the block contains an entry which depends on the presence of an edge. Letting eqi be 1 if (i, q) is an edge and eqi = 0 otherwise, the blocks are defined as

where 1 ⩽ i ⩽ v0 and 1 ⩽ q ⩽ v1.

The construction is illustrated in the following diagram which shows the case of v0 = 3 = v1. The pixel corresponding to (1, 1) is in the second row and second column, and (0, 0) is at the top left corner in the diagram.

In the diagram the solid grey pixels correspond to the 1s in the matrix. The entries shown with thick horizontal lines are the eqi ; for a specific 2-graph these will either be solid grey (included) or white (excluded) depending on the presence or absence of each potential edge. There are three low-level components, each of which is a set of pixels in three consecutive rows, and these three groups of rows are indicated by the numbers on the left hand side.

The upper level view for the case of no edges is shown by the overlay consisting of small dots. The pixels indicated in this way belong to the upper level view whether there are any edges or not. Including an edge adds some pixels to the upper view which are specified below.

Returning to the formal description of the general case, we identify the data for the realization. The subset [[N0]] ⊆ Z2 consists of the non-zero elements in the matrix. The bijection β : N0 → C([[N0]]) takes i ∈ N0 to the component consisting of non-zero pixels in the i-th row of the block matrix, that is those belonging to Bi j for some j where 1 ⩽ j ⩽ 2v1 -1.

The pixels in α[[N0]] can be described in the same fashion as those in [[N0]] by giving a set of v0(2v1 - 1) blocks each of which is a 3 × 3 matrix. For 1 ⩽ i ⩽ v0 and 1 ⩽ q ⩽ v1, the block Ai 2q is a zero matrix. The other blocks are

The bijection γ takes q ∈ N1 to the component made up of all the elements which are 1 in some Ai 2q-1.

To complete the proof of Theorem 1, note that if N0 = ∅ then in any realization [[N0]] = ∅ = α[[N0]] so that the existence of γ implies N1 = ∅. If N0 = {m} and n ∈ N1 lies in no edge then αβm ∩ γn = ∅. Which is impossible as γn is a component of αβm.

4 2-Relations

4.1 Definition

A 2-graph provides an qualitative description of a static region at two levels of detail. We now extend this to dynamic regions. A change from an initial situation to a later one is represented abstractly as a relation between the two 2-graphs representing the two situations. These relations record not only how the components at each level are related, but also whether the connections between the two levels are maintained throughout the change. The relations we need consist of ordered pairs of nodes at each level and also ordered pairs of edges.

Definition 3. Given 2-graphs G = ((N0, N1), E) and G′ = ((N ′0 ,N ′1 ),E′ ), a 2-relation, R, from G to G′ consists of three relations (R0, R1, R2) where Ri ⊆ Ni×N ′ i for i = 0, 1 and R2 ⊆ E × E′ . These relations satisfy the condition that for any edges (m, n) ∈ E and (m′ , n′ ) ∈ E′ , if (m, n) R2 (m′ , n′ ) then m R0 m′ and n R1 n′ .

An example of a 2-relation between 2-graphs appears in the next diagram. In the diagram the relations between nodes are indicated by dashed lines, and the relation between edges is indicated by a solid line with transverse bars.

These relations generalize the bipartite relations between trees studied by Stell and Worboys [2011] by allowing arbitrary bipartite graphs (possibly with cycles or not being connected), and also by relating edges as well as nodes. However, the spatial interpretation of the edges in the 2-graphs here is quite different since it represents a connection across levels of detail whereas in [Stell and Worboys, 2011] it represents containment.

When R is a 2-relation from G to G′ we write R : G → G′ , and given a relation S : G′ → G′′ the composite R ; S : G → G′′ is defined by composing the components in the usual way, so that R;S = ((R0;S0), (R1;S1), (R2;S2)). It is immediate that this composition is associative and that we can define an identity 2-relation 1G on each 2-graph G.

4.2 Realization for 2-relations

A realization of a 2-relation consists of a realization of the source and target 2-graphs of the relation together with a dynamic region (a sequence of successively overlapping regions) which exhibit the structure of the relation as in Definition 4 below. Arbitrary 2-relations can be very complex, so it is important to understand how such relations can be built up out of primitive components. We analyse these primitive components shortly, and how they combine through composition to yield arbitrary 2-relations, but the following diagram is useful at this point. It shows a region (detailed level as grey pixels, higher level as dotted overlay) which changes from an initial situation to a final one with two intermediate times. The sequence of four static regions realizes the relation obtained by composing the three relations shown below. Each of these individual relations is realized by a sequence of just two regions. In this example the change from one stage to the next consists of the addition of a single pixel, but this is not an essential feature and more substantial changes may occur between successive times.

A dynamic region is given by specifying a set of instants k = {0, 1, . . . , k} and a function F : k → PZ2 , so that for each i ∈ k, there is a region F(i). A component of F is a function f : k → PZ2 with f(i) ∩ f(i + 1) ̸= ∅ and f(i) ∈ C(F(i)). This allows us to define a relation ΠF ⊆ C(F(0)) ×C(F(k)) where (a, b) ∈ ΠF iff there is a component f of F where f(0) = a and f(k) = b. When this happens, we say that f joins a to b. Note that there may be several distinct components joining a to b. When F : k →PZ2 is a dynamic region, αF denotes the function (αF)(i) = α(F(i)) where α is the approximation function as used in the realization of 2-graphs.

Definition 4. A realization of a 2-relation R : G → G′ where R = (R0,R1,R2), G = ((N0,N1),E), and G′ = ((N ′0 ,N ′1 ),E′ ) consists of the following data:

1. A set k = {0, 1, . . . , k} of times, where k ⩾ 1,
2. a dynamic region F : k →PZ2 ,
3. bijections β : N0 → C(F(0)), β′ : N ′0 → C(F(k)), γ : N1 →C(αF(0)), and γ ′ : N ′1 →C(αF(k)).

These data are subject to the conditions:

1. (m, n) ∈ E iff αβm∩ γn ̸= ∅,
2. (m′ , n′ ) ∈ E′ iff αβ′m′ ∩ γ ′n′ ̸= ∅,
3. (m,m′ ) ∈ R0 iff (βm, β′m′ ) ∈ ΠF ,
4. (n, n′ ) ∈ R1 iff (γn, γ ′n′ ) ∈ ΠαF ,
5. ((m, n), (m′ , n′ )) ∈ R2 iff there are components f0 joining βm to β′m′ and f1 joining γn to γ ′n′ such that αf0(i) ∩ f1(i) ̸= ∅ for every i ∈ k.

This notion of realization applies to arbitrary 2-relations, but our main aim here is to determine an appropriate set of atomic 2-relations that generalize the merge, split, insert and delete which are well-known in the single-level analysis of change. In the next section we introduce a set of atomic 2relations and justify it by showing that all 2-relations can be obtained from these atomic 2-relations and then that all the atomic 2-relations can themselves be realized.

5 Atomic 2-Relations

For regions at two levels of detail, where we only observe the number of components at each level, we can expect each of the four single-level changes (merge / split, create / delete) to occur in two variants (upper and lower). However there are additional cases because of our use of 2-relations where edges as well as nodes can split or merge.

5.1 Types of atomic 2-relation

There are five basic patterns of atomic 2-relation: meet, merge, create, link and the isomorphisms. Three of the patterns come in two variants depending on whether they involve the upper or lower nodes, and four of the five (apart from the isomorphisms) have converse versions. This makes 15 types of atomic relation in total, and the following table lists the 14 types other than isomorphisms.

The seven cases in the left hand column of the table are illustrated by the following diagrams. In each case examples of an initial and a final configuration are given to the left and right of a simple example of the atomic relation. Formal definitions are given below, but it is important that an upper meet, for example, is an archetype which includes not only the illustrated example but any 2-relation in which two upper nodes become identified while linked to a single common lower node and where apart from these edges and nodes the relation acts as the identity.

To describe the atomic relations formally, observe how an equivalence relation, ∼, on the set of upper nodes of a 2graph G induces a 2-graph G/∼ and a 2-relation η : G → G/∼ where η = (η0, η1, η2). The 2-graph G′ has the same set, N0, of lower nodes as G, and the upper nodes, N ′1 , are the equivalence classes of N1. The edges of G/∼ are E′ = {(m, [n]) ∈ N0 × N ′1 | (m, n) ∈ E}, where [n] denotes the equivalence class of n. The relation η0 is the identity on N0, and η1 pairs each n ∈ N1 with [n], and η2 pairs each (m, n) ∈ E with (m, [n]) ∈ E′ .

Definitions of Meet and of Merge

Let G be a 2-graph including distinct upper nodes n1, n2 ∈ N1, and let ∼ be the least equivalence relation on N1 which identifies n1 and n2.

If there is exactly one lower node m such that (m, n1) and (m, n2) are both edges then the relation η : G → G/∼ is an upper meet. In an upper meet there is exactly one less node and one less edge in the source than in the target. If there is no lower node m such that (m, n1) and (m, n2) are both edges then η is an upper merge. In this case the target has one less upper node than the source, but the same number of lower nodes and edges.

The definitions of lower meet and lower merge are similar and depend on the analogous construction of a relation induced by an equivalence relation on the lower nodes.

Definitions of Create and of Link

Let G be a 2-graph and let {n} be disjoint from N1. Letting G′ be the 2-graph with the same lower nodes and edges as G and with upper nodes N ′1 = N1 ∪ {n}, define the 2-relation θ = (θ0, θ1, θ2) by θ0 and θ2 being the identity on N0 and E, and θ1 = {(m, m) ∈ N1 ×(N1 ∪{n}) | m ∈ N1}. Then θ is an upper create, and the notion of lower create where a single new node appears at the lower level should be evident.

In a link, exactly one new edge appears. As this depends on one upper and one lower node the notion of link does not have upper and lower variants.

5.2 Decomposition theorem

We now show that these atomic 2-relations are sufficient to generate all 2-relations by composition. This is Theorem 5, to prove which we need some preliminary results and the following definition.

Definition 5. A 2-relation R : G→G′ is full if for all edges e = (m, n) in G and e′ = (m′ , n′ ) in G′ such that (m,m′ ) ∈ R0 and (n, n′ ) ∈ R1 we have (e, e′ ) ∈ R2.

Any 2-graph can be regarded as an undirected graph where the set of nodes is the disjoint union of the sets of upper and lower nodes of the 2-graph. Recall that a tree is an undirected graph with exactly one path between any two distinct nodes. When we have a 2-relation between 2-graphs each of which (regarded as a graph) is a tree, we will talk of having a "2relation between trees".

Theorem 2. Every full 2-relation between trees is expressible as a composite of atomic 2-relations.

Proof. Given any pair of ordinary relations on nodes, P ⊆ N0 ×N ′0 and Q ⊆ N1 ×N ′1 there is a unique full 2-relation R : G → G′ where R0 = P and R1 = Q. In particular, when G and G′ are both trees, the 'Atomic Relations' used in [Stell and Worboys, 2011] lead to full 2-relations between G and G′ . The 2-relations of this type will be called Basic Tree Relations (BTRs). Since the composition of full 2-relations is again full, it follows from Theorem 13 in [Stell and Worboys, 2011] that every full 2-relation between trees is obtainable as a composite of BTRs. But, the BTRs are themselves either atomic 2-relations (in the case of the 'merge', 'split' and 'isomorphisms' defined in [Stell and Worboys, 2011]) or expressible as composites of atomic 2-relations (in the case of the 'insert' and 'delete' in the same paper).

An important type of 2-relation from a graph to itself is the identity on all nodes and on every edge apart from exactly one edge. These are called erasers because, given a 2-relation, R : G → G′ , with (e, e′ ) ∈ R2, the 2-relation (R0, R1, R2 - {(e, e′ )}), that is R with (e, e′ ) removed, is expressible as R ; S with S an eraser on G′ . Erasers are not atomic but are composites of a separate followed by a link.

Corollary 3. Every 2-relation, R, between trees is expressible as a composite of atomic 2-relations.

Proof. By composing a full 2-relation with suitable erasers, we can remove any of the edge pairings not present in R and hence express R in the required form.

In the next Lemma, the converse of a 2-relation S is denoted ˘ S (obtained by taking the ordinary converse of each component relation) and 1G is the identity 2-relation on G.

Lemma 4. For any 2-graph, G, there is a 2-graph, T , which is a tree, and a 2-relation S : G → T where S ; ˘ S = 1G and S is a composite of atomic relations.

Proof. The construction is in two stages via a connected 2graph C and relations P : G → C and Q : C → T where P ; ˘ P = 1G and Q; ˘Q = 1C. The 2-graph C is constructed by adding edges and possibly nodes to G to make it connected. The relation P is a composite of relations each of which is a create (when adding a node) or a link (when adding an edge). From C we construct T by successively removing cycles by splitting a node in each cycle. The relation Q is then the composite of these splits. Finally S = P ; Q.

Theorem 5. Every 2-relation R : G → G′ between 2-graphs can be obtained as a composite of atomic 2-relations.

Proof. By Lemma 4 we can construct S : G → T and S′ : G′ → T ′ where T and T ′ are both trees, and S ; ˘ S = 1G and S′ ; ˘ S′ = 1G′ . The relation ˘ S ; R ; S′ : T → T ′ is expressible in atomic steps by Theorem 2, and R = S ; ˘ S ;R;S′ ; ˘ S′ .

5.3 Realization theorem

The earlier diagrams give specific examples, but we need to justify that arbitrary atomic relations can be realized.

Theorem 6. Every atomic 2-relation can be realized.

Proof. It is sufficient to show how to realize meets, merges, creates and links since a realization of any relation easily yields a realization of the converse relation. We suppose in each case that we are given an atomic 2-relation R : G → G′ . By choosing a suitable realization of the 2-graph G, we can achieve a realization of the 2-relation in just one step so there are just two times and the set k in Definition 4 has just two elements.

Suppose R : G → G′ is an upper meet. We can assume that the edges that are identified are (1, 1) and (1, 2) where the upper and lower nodes are taken to be sets of natural numbers as in the proof of Theorem 1. We can realize G by the set of pixels specified there by the matrices. To construct a realization of G′ it is sufficient to change the entries at positions (4, 1) and (5, 1) from 0 to 1. It is then straightforward to verify the required conditions.

In the case of a lower meet in which edges (1, 1) and (2, 1) are identified, we can realize G as before using the construction in Theorem 1. We can then realize G′ by changing the entry at position (2, 3) from 0 to 1.

The upper and lower merges are very similar, so we omit a detailed description.

For an upper create, there must be at least one lower level node in G which we realize, as in the other examples, in the first three rows of the area of pixels. To obtain a realization of G′ we add to the subset of Z2 thus described, the six elements (-5, 2), (-4, 2), . . . , (0, 2) and the two elements (-5, 1) and (-3, 1). For a lower create, it is sufficient to add the single element (0, 3) to the set of pixels which realize G in order to obtain the realization of G′ .

For a link, we can assume that the upper node 1 becomes linked to the lower node 1. We can realize G′ from G by adding a single pixel at (1, 1).

6 Conclusions and FurtherWork

We have demonstrated the value of introducing granularity into qualitative descriptions of change undergone by spatial regions. Granularity enables more informative qualitative descriptions to be obtained. For example an upper merge is a kind of change in which two regions which remain different appear to become one when viewed in a less detailed way. This can be due to the two regions moving closer together. Conversely an upper split can occur when two distinct regions move further apart.

We have used mathematical morphology to give a precise notion of 'less detailed' and we have introduced 2-graphs and 2-relations to give an abstract model of the qualitative structure of regions and changes to them. We have identified a set of atomic kinds of change, formalized by the 15 types of atomic 2-relation. We have proved that the atomic 2-relations are sufficient to generate all possible 2-relations and that all the atomic ones can arise as changes undergone by sets of pixels in a discrete space.

We propose to continue the work reported by considering the extension to more than two levels of granularity, and by investigating more elaborate spatial descriptions at each level. In particular we expect to be able to describe changes to the nesting of regions through time over multiple levels of detail.