# On the ternary spatial relation "Between"

Isabelle Bloch, Olivier Colliot, Roberto M. Cesar

► To cite this version:

Isabelle Bloch, Olivier Colliot, Roberto M. Cesar. On the ternary spatial relation "Between". IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2006, 36 (2), pp.312-327. 10.1109/TSMCB.2005.857095. hal-01251251

HAL Id: hal-01251251

https://inria.hal.science/hal-01251251

Submitted on 5 Jan 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the ternary spatial relation “between”

Isabelle Bloch, Olivier Colliot, Roberto M. Cesar Jr.

## Abstract

The spatial relation “between” is a notion which is intrinsically both fuzzy and contextual, and depends in particular on the shape of the objects. The literature is quite poor on this relation and the few existing definitions do not take into account these aspects. In particular an object B that is in a concavity of an object $A_1$ not visible from an object $A_2$ is considered as between $A_1$ and $A_2$ for most definitions, which is counter-intuitive. Also none of the definitions deals with cases where one object is much more elongated than the other. We propose here definitions which are based on convexity, morphological operators and separation tools, and a fuzzy notion of visibility. They correspond to the main intuitive acceptions of the relation. We distinguish between cases where objects have similar spatial extensions and cases where one object is much more extended than the other. Extensions to cases where objects themselves are fuzzy and to 3D space are proposed as well. The original work proposed in this paper covers the main classes of situations and overcomes the limits of existing approaches, in particular concerning non visible concavities and extended objects. Moreover the definitions capture the intrinsic imprecision attached to this relation. The main proposed definitions are illustrated on real data from medical images.

## Index Terms

Relationship “between”, spatial reasoning, convex hull, mathematical morphology, visibility, fuzzy and 3D objects, structural pattern recognition.

I. Bloch is with Ecole Nationale Supérieure des Télécommunications, Département TSI, CNRS UMR 5141, 46 rue Barrault, 75634 Paris Cedex 13, France - Isabelle.Bloch@enst.fr. O. Colliot is with McConnell Brain Imaging Center, MNI, McGill University, 3801 University, Montréal, Québec, H3A2B4, Canada - colliot@bic.mni.mcgill.ca. R. Cesar is with Department of Computer Science, Institute of Mathematics and Statistics - IME, University of São Paulo - USP Rua do Matão, 1010, São Paulo, SP CEP 05508-090 - Brazil - cesar@ime.usp.br. R. Cesar and I. Bloch were partially supported for this work by a CAPES / COFECUB grant (number 369/01).
# On the ternary spatial relation “between”

## I. INTRODUCTION

Spatial reasoning and structural object recognition in images rely on characteristics or features of objects, but also on spatial relations between these objects, which are often more stable and less prone to variability. We have shown in our previous work how these relations could be modeled and used in recognition methods based on graph matching or deformable models [1], [2], [3], [4], [5]. However, as soon as relations which are more complex and less objective than distance or adjacency are concerned, their modeling is more difficult since they have several meanings and may vary depending on shape. Moreover, they are often intrinsically vague and imprecise, even if objects are precise. This is typically the case for the “between” relation. For instance, in Figure 1, we would like to consider that *B* is not completely between $A_1$ and $A_2$ but that it is between them to some degree. Furthermore, a second type of imprecision may occur if the boundaries of objects are imprecise too. Fuzzy objects are then considered, and the between relation for such objects is obviously fuzzy, and carries both types of fuzziness.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Is the object *B* between $A_1$ and $A_2$ and to which degree?</figcaption></figure>

Another important point is that it is hopeless to try to define such a relation in an absolute way. The definitions should rather be contextual, i.e. depending on the relative spatial extension of the objects, on the type of problem at hand, on the application domain. For instance, the between relation cannot be defined in the same way whether the objects have similar spatial extensions or not. The semantics of “between” changes depending on whether we consider a person between two buildings, a fountain between a house and a road, or a road passing between two houses. These differences have been exhibited in cognitive and linguistic studies [6]. Similar examples can be found for other relations, such as “surround”, “along”, etc. It follows that it is impossible to propose a single definition that would apply to all possible contexts. We will therefore deal with a few typical situations, and discuss for each definition to which cases they are adapted and which cases are not taken into account. Finally, the choice of a particular definition for a specific application will involve human decision. The models proposed in this paper constitute an help towards this aim.

The primary aim of this paper is to propose some definitions of the relation “between”. More precisely, we try to answer two types of questions:
1) Which is the region of space located between two objects $A_1$ and $A_2$? (these objects can be crisp or fuzzy, 2D or 3D, have similar spatial extents or very different ones);

2) Is object B between $A_1$ and $A_2$?, or better, since we underlined the intrinsic fuzziness of such a relation: To which degree is B between $A_1$ and $A_2$?

The first question is interesting for many problems in pattern recognition, scene interpretation and spatial reasoning, in cases one object is a reference and the relations of many other objects to this reference have to be assessed. This question is rarely addressed in the literature on spatial relations though.

As for the second question, the general scheme we propose is to answer the first question by defining the (fuzzy) region between $A_1$ and $A_2$, denoted by $\beta(A_1, A_2)$, and then to find an appropriate measure of comparison between $\beta(A_1, A_2)$ and B. Both questions may receive answers which depend on the context.

Looking at definitions in dictionaries, the one that corresponds to the spatial meaning involves the notion of separation, e.g. in the Merriam-Webster Dictionary: in the time, space, or interval that separates. This suggests to try to “separate” objects. Linear separation is clearly not always possible. But separation in the sense of the minimum distance line or surface between objects is more relevant. More difficult is to extend this line to the “space” that separates the objects. However, this will inspire one of the definitions we propose.

When proposing persons to draw the area which is between two objects, for different situations, they all provide the same answers, and when asking them about the idea behind their answers, two factors appear to play a role: the convex hull of the union of both objects and the notion of visibility. In all cases, they perceive an object as a whole and not as a set of points. Again, these two notions suggest some of the definitions proposed hereafter.

In this paper, we assume that, in continuous space, typically $\mathbb{R}^n$, the considered objects are compact sets (enabling an easy link with the digital case), and that they have only one connected component (we assume here the standard topology on $\mathbb{R}^n$). Extensions to objects having several connected components will be proposed based on a distributivity property.

The paper is organized as follows. In Section II, we present the few definitions existing in the literature. Interestingly enough, although this problem received very little attention, it was addressed by different communities. The following Sections are dedicated to our original definitions<fnref n="1" />: in Section III, the simplest idea, based on the convex hull of the union of both objects, is presented, along with its limits; definitions based on morphological operators, in particular dilations and skeleton by influence zones or watersheds, are presented in Section IV; definitions based on the notion of visibility are then proposed, in Section V. These definitions allow us to answer the first question, for different types of objects and contexts. Then, some ways to answer the second question, i.e. defining the degree to which an object is between two other objects, are proposed in Section VI. We discuss some properties and extensions in Section VII. In order to illustrate our work, in Section VIII, we apply some of the proposed definitions on real objects, namely anatomical structures in medical images, and show that the results

<footnote n="1">¹Preliminary versions of some of them can be found in [7], [8].</footnote>
correspond to what would be intuitively expected.

## II. RELATED WORK

In this Section, we briefly present the few definitions we have found in the literature.

### A. Artificial intelligence and qualitative spatial reasoning

In the domain of spatial logics and qualitative spatial reasoning, a few approaches can be found, which are generally crisp and do not take the fuzziness into account. They rely on collinearity between points, and do not consider objects globally, which contradicts the usual perception.

Logical approaches [9] usually rely on a predicate expressing betweenness between points in terms of collinearity[10]. A point is said to be between two objects (modeled as logical formulas), if it belongs to a segment with endpoints in each of the objects. The main limit of this approach is that it relies basically on relations between points. A typical problem is illustrated in Figure 2, where points in the concavity of object $A_2$ actually belong to segments with end points in each of the objects. Object $B$ is then between $A_1$ and $A_2$ although it can hardly be considered in the between region from a more global point of view (as the one used in human perception). This shows also that the notion of visibility is not taken into account in these approaches.

<figure><img src="image_3.png" /><figcaption>Fig. 2. An example where $B$ is considered to be between $A_1$ and $A_2$ according to the definition of [9].</figcaption></figure>

Despite the aforementioned drawbacks, this approach has the advantages related to logical expressions, in terms of compactness and reasoning power. This approach has also interesting links with convexity, which reinforce the idea of convex hull based definitions.

Another approach was proposed in [11], based on the notion of sphere system. The definition is also based on collinearity, but applied on the centers of the spheres (Figure 3).

<figure><img src="image_4.png" /><figcaption>Fig. 3. Sphere $B$ is between spheres $A_1$ and $A_2$ [11].</figcaption></figure>

This implies that the sphere centers should be aligned. For instance in Figure 1, the relation does not hold, according to [11]. Moreover, working on spheres is rather restrictive with respect to the variety of shapes that
can be found in the real world (this is a restriction with respect to mereotopology, introduced in order to add a
geometric and metric dimension to the topological one). The use of this definition would require to decompose
objects of interest as sets of spheres and extend the processing to a union of spheres.

B. Fuzzy set literature

To our knowledge, only three approaches take the fuzziness into account.

Two of them are close to our aim [12], [13]. In the definition of [12], the degree to which an object B is between
two objects A₁ and A₂ in the 2D space is computed based on a relation between points. For all a₁ ∈ A₁, a₂ ∈
A₂, b ∈ B, the angle θ at b between the segments [b, a₁] and [b, a₂] is computed. Then a function μ之間(b) is
defined as illustrated in Figure 4, and is used to measure the degree to which b is between a₁ and a₂.

<figure><img src="image_5.png" /><figcaption>Fig. 4. Illustration of the function $\mu_{between}(\theta)$ proposed in [12] ($\alpha$ is a parameter expressing the tolerance in the idea of between).</figcaption></figure>

For extended objects, the angle θ is averaged over all triplets of points (a₁, a₂, b) and the degree to which B is
between A₁ and A₂ is defined as μ之間(Θ), where Θ is this average angle.

This approach is extended to fuzzy objects by integrating the results obtained on all α-cuts.

Beside the fact that the extension to the fuzzy case is computationally heavy, this approach has a major drawback,
even in quite simple situations. Let us consider the example in Figure 5. Intuitively, we would expect B to be
completely between A₁ and A₂ since it lies in the convex hull of A₁ ∪ A₂ (which is the expected between area in
simple convex cases like this one). But this is not the case when applying the above formula, since the average θ
value is not close to π.

<figure><img src="image_6.png" /><figcaption>Fig. 5. An example where the definition of [12] hardly corresponds to intuition (Θ corresponds to the average angle and is significantly smaller than π, while B would be intuitively considered as completely between A₁ and A₂).</figcaption></figure>

The definition proposed in [13] also relies on computation of angles, but in a different spirit. In this work, what
is actually computed is the degree to which a set B is between different connected components of a set A. This is
based on the normalized angle or force histogram of A and B. Each α-cut $H_\alpha$ of this histogram is computed and some angles are defined to represent the intervals between connected components of $H_\alpha$ and the length of these connected components. The degree of the relation is then 0 if A is connected, and depends on the number of its connected components and on a function of these angles otherwise. Then the result is integrated over all α-cuts of the histogram. This approach has some major drawbacks: it is computationally heavy if a fine quantification of $\alpha$ is chosen; parts of the objects which are opposite to the between area have an influence (while they should not be involved) and induce a bias in the results; the examples shown in [13] are sometime counter-intuitive in case A has three connected components or more (a degree smaller than what would be expected is obtained), the problem being that the relation is then ambiguously defined and depends on which connected components build $A_1$ and which ones build $A_2$ (see Figure 6 (a)); finally, this approach does not deal appropriately with the non visible concavities of components of A (see Figure 6 (b)).

<figure><img src="image_7.png" /><figcaption>Fig. 6. Illustration of the definition of [13]. (a) A case of ambiguity: $A = A_1 \cup A_2 \cup A_3$ and B are considered to satisfy the relation according to this definition, while B is between $A_2$ and $A_3$ but not between $A_1$ and $A_2$. (b) A case with a non visible concavity, where again the relation is satisfied according to this definition with a non zero degree.</figcaption></figure>

The third existing fuzzy definition [14] applies on one-dimensional fuzzy sets. It relies on the definition of fuzzy ordering based on a T-equivalence, from which unary ordering-based modifiers are defined. Without going into details, these modifiers correspond to left and right relations (or before and after if the space is the temporal axis) and are idempotent. The fuzzy region between two 1D fuzzy sets $A_1$ and $A_2$ is then defined as conjunctions and disjunctions of these modifiers applied to both fuzzy sets. The main difficulty in these definitions is that they rely on an ordering, which makes their extension to higher dimensions an uneasy task. However the interpretation of these equations can provide some hints on possible extensions, that will be exploited later in definitions based on dilations. Indeed, as illustrated in Figure 7, one definition, denoted as $BTW(A_1, A_2)$, corresponds to the area which is to the left of one of the initial fuzzy sets and to the right of the other. A more strict definition, denoted as $SBT(A_1, A_2)$, removes parts that are to the left of both sets or to the right of both.

### C. Linguistics and cognition

It is also interesting and useful to look at some linguistic and cognitive aspects to understand the meaning of the relation. As stated in [15], the area between two objects is cognitively understood as “the minimal space bounded by the pair of reference objects”. This clearly refers in mathematical terms to the convex hull of the union of both
<figure><img src="image_8.png" /><figcaption>Fig. 7. An example illustrating the definitions of [14]. The plain line shows the result of the first definition and the dashed one the strict definition (note that in this case, only the part outside the supports of $A_1$ and $A_2$ can belong completely to the between region).</figcaption></figure>

objects.

This is confirmed by the work of [6], where a simple definition of the common understanding is provided: the region between $A_1$ and $A_2$ is defined as the strict interior of the convex hull of $A_1 \cup A_2$ to which $A_1$ and $A_2$ are then suppressed. Obviously this applies only in simple situations, as will be seen in Section III, but it confirms the interest of the notion of convex hull.

An interesting idea is briefly mentioned in this work [6]: in cases where the objects have different spatial extensions, in particular if one of them can be considered as infinite with respect to the other, then the proposed definition is not meaningful and more contextual definitions can be proposed, such as the area issued from the projection of the small object on the large one (Figure 8). But, as already mentioned, no general criteria can be exhibited that cover all possible situations.

<figure><img src="image_9.png" /><figcaption>Fig. 8. An example of objects with different spatial extension where a contextual definition is the most appropriate one [6].</figcaption></figure>

It should be noted that, to our knowledge, no definition deals appropriately with cases such as the one in Figure 8. We will propose a definition based on visibility that applies in such situations.

### III. CONVEX HULL

#### A. *Crisp case*

The intuitive answer given by most people when defining the region between two objects involves the convex hull of their union. This notion also appears in some work in the domain of linguistic and cognition [6]. Furthermore,
links between logical operators for defining the between relation and convexity have been also exhibited [9]. These observations led us to propose the following simple definition.

For any set X (closed and bounded), that we first assume to be binary (crisp), we denote by $X^C$ its complement, and $CH(X)$ its convex hull. We define the region of space between two objects $A_1$ and $A_2$, denoted by $\beta(A_1, A_2)$, as:

$$ \beta_{CH}(A_1, A_2) = CH(A_1 \cup A_2) \cap A_1^C \cap A_2^C. \qquad (1) $$

This definition is well adapted to convex objects or having concavities “facing each other”, as illustrated in Figure 9.

<figure><img src="image_10.png" /><figcaption>Fig. 9. Definition from convex hull: the dashed area corresponds to $\beta(A_1, A_2)$.</figcaption></figure>

For more complex objects, the connected components of $CH(A_1 \cup A_2) \setminus (A_1 \cup A_2)$ which are not adjacent to both $A_1$ and $A_2$ should be suppressed, as illustrated in Figure 10 (a). We have asked about this situation to more than twenty persons, who all drew the dashed area. Unfortunately, a drawback of this approach is its lack of continuity, as shown in Figure 10: $A_2$ in situation (a) can be deformed continuously towards $A_2$ in situation (b), while this is not the case for the dashed area $\beta(A_1, A_2)$.

<figure><img src="image_11.png" /><figcaption>Fig. 10. Continuity problem: $A_2$ can be deformed continuously from situation (a) to situation (b) but the region between $A_1$ and $A_2$ does not vary continuously.</figcaption></figure>

## B. Fuzzy case

The extension of this definition to fuzzy objects requires to define the convex hull of a fuzzy object. Since the $\alpha$-cuts of a fuzzy set $\mu^2$ are nested, so are their convex hulls. This property allows us to define the convex hull $CH(\mu)$ through its $\alpha$-cuts as:

$$ (CH(\mu))_{\alpha} = CH(\mu_{\alpha}). \qquad (2) $$

<footnote n="2">²The symbol $\mu$ denotes indifferently a fuzzy set or its membership function.</footnote>
The drawback of using α-cuts is the potential computational burden, in particular if the quantization step of α is fine. Another method can be used, by exploiting the fact that a morphological closing by a ball of infinite radius applied on an object provides exactly the convex hull of that object [16]. In practice the radius of the ball should only be larger than the largest diameter of the object. This method can be directly applied to fuzzy objects.

Now we can extend Equation 1 to fuzzy objects with membership functions $\mu_{A_1}$ and $\mu_{A_2}$:

$$ \beta_{CH}(A_1, A_2) = CH(\mu_{A_1} \cup \mu_{A_2}) \cap c(\mu_{A_1}) \cap c(\mu_{A_2}) \quad (3) $$

where c is a complementation, the intersection is implemented as a t-norm and the union as a t-conorm. In order to avoid undesirable regions, it is recommended to choose a t-norm that satisfies the law of excluded middle, such as Lukasiewicz' t-norm<fnref n="3" /> for instance (Figure 11). This definition reduces to Equation 1 if the objects are crisp, which therefore appears as a particular case of Equation 3. This is why we keep the same notation $\beta_{CH}$.

<figure><img src="image_12.png" /><figcaption>Fig. 11. Computing $\beta(A_1, A_2)$ from the convex hull of the union of fuzzy objects $A_1$ and $A_2$ with the minimum t-norm (thick blue line on the left) and with Lukasiewicz' t-norm (thick green line on the right). When using the min, triangles appear on the left and on the right which are unwanted since they can hardly be considered as being between $A_1$ and $A_2$. This phenomenon does not occur with Lukasiewicz' t-norm.</figcaption></figure>

### C. Non-connected objects

Let us now consider the case where one object has several connected components, and assume that $A_1$ can be decomposed into connected components as: $\cup_i A_1^i$. The region between $A_1$ and $A_2$ can be defined by using a distributivity property:

$$ \beta(A_1, A_2) = \beta(\cup_i A_1^i, A_2) = \cup_i \beta(A_1^i, A_2) \quad (4) $$

where each $\beta(A_1^i, A_2)$ is computed as presented above (or using another of the methods proposed in this paper). This principle is inspired by one of the properties satisfied in the logical definition of [9]. It applies similarly to the case where both objects are non-connected.

In particular in the case of convexity based definition, this approach is better than the one which would consist in using directly the convex hull of $A_1 \cup A_2$ (see Figure 12), and provides more satisfactory results.

Note that, in practice, if one object is composed of very distant connected components, it will probably not be considered globally to evaluate the between relation.

<footnote n="3">³The Lukasiewicz' t-norm is defined as $\forall (a, b) \in [0, 1], t(a, b) = \max(0, a + b - 1)$ (see e.g. [17] for the definitions of various t-norms).</footnote>
<figure><img src="image_13.png" /><figcaption>Fig. 12. Region C belongs to CH($A_1 \cup A_2$) but not to CH($A_1^1 \cup A_2$) $\cup$ CH($A_1^2 \cup A_2$), while an object in C would not be considered as between $A_1 = A_1^1 \cup A_1^2$ and $A_2$.</figcaption></figure>

IV. MORPHOLOGICAL DILATIONS

A. *Definition based on dilation and separation*

We now try to implement the notion of separation that is found in standard dictionary definitions. Morphological dilation provides a good basis to this aim. If both objects are dilated until they meet, the ultimate intersection can often be considered as being between both objects, and therefore constitutes a “seed” for constructing $\beta(A_1, A_2)$. The size of the dilation required to achieve intersection is directly related to the minimum distance between both sets.

Formally, we define:

$$ \beta_{Dil}(A_1, A_2) = D^n[D^n(A_1) \cap D^n(A_2)] \cap A_1^C \cap A_2^C \quad (5) $$

where $D^n$ denotes the dilation by a disk of radius $n$, and where $n$ is defined as:

$$ n = \inf\{k/D^k(A_1) \cap D^k(A_2) \neq \emptyset\} $$

i.e. $n$ is the half of the minimum distance between both sets. Since the sets are compact, $D^n(A_1) \cap D^n(A_2)$ is non-empty, and the definition is thus consistent.

This definition applies for convex sets, but is clearly not appropriate for non convex sets. Even for convex sets, this definition can be considered as too restricted, since it excludes some parts of the convex hull of the union of both sets, as illustrated in Figure 13 (a). This effect can be even stronger in case of non convex sets, as shown in Figure 14.

But the result can also be too extended, typically if the distance between objects is much larger than their size, as illustrated in Figure 13 (b).

A line that “best” separates the two sets can also be considered as a seed of $\beta(A_1, A_2)$. This line should stay as far as possible of both sets, hence another interpretation in terms of distance. From an algorithmic point of view, a possibility (that applies to non convex sets as well) is to compute the watersheds (denoted by WS) of the distance function to $A_1 \cup A_2$ (see Figure 14). With the assumptions made on the objects, this is equivalent to the SKIZ
<figure><img src="image_14.png" /><figcaption>Fig. 13. Dilation of the intersection of the dilations of $A_1$ and $A_2$ by a size equal to their half minimum distance. The obtained region for $\beta$ may exclude some parts belonging to the convex hull of $A_1 \cup A_2$ (dashed straight lines) in some cases (a), or may be too extended (b).</figcaption></figure>

(skeleton by influence zones), which is more set oriented. From this seed, the space that separates both sets can be defined as:

$$ \beta_{sep}(A_1, A_2) = D_{CH'(A_1 \cup A_2)}^{\infty}(WS) = D_{CH'(A_1 \cup A_2)}^{\infty}(SKIZ) \quad (6) $$

i.e. the geodesic dilation until convergence (reconstruction) of the watershed lines or the SKIZ in $CH'(A_1 \cup A_2)$, where $CH'(A_1 \cup A_2)$ denotes $CH(A_1 \cup A_2) \setminus (A_1 \cup A_2)$ from which the connected components of the convex hull not adjacent to both sets are suppressed too (as in the definition based on the convex hull).

<figure><img src="image_15.png" /><figcaption>Fig. 14. Definition based on watershed or SKIZ (thick line), in a case where the definition based on simple dilation leads only to the disk limited by the dashed line.</figcaption></figure>

Actually, in the cases we consider ($A_1$ and $A_2$ compact sets, and each having only one connected component), the reconstruction provides $CH'(A_1 \cup A_2)$. Indeed, $A_1^C \cap A_2^C$ has one connected component corresponding to the background (if $A_1$ and $A_2$ are not connected to each other) and possibly some components corresponding to holes of $A_1$ or $A_2$, which are not adjacent to both objects and therefore suppressed to yield $CH'$. When computing the convex hull, only new connected components corresponding to concavities and not adjacent to both sets can appear. Therefore $CH'$ has only one connected component, which is necessarily marked by the watersheds or the SKIZ, and is therefore completely reconstructed. Another example is given in Figure 15. One drawback of this approach, as can be observed in this Figure, is that non visible concavities belong to the between area.
<figure><img src="image_16.png" /><figcaption>Fig. 15. Definition based on watershed (red line), applied on the white objects and providing the grey area.</figcaption></figure>

Such cases could be handled in a satisfactory way by considering $CH(A_1 \cup A_2) \setminus (CH(A_1) \cup CH(A_2))$, i.e. by reasoning on the convex hulls of the objects, but this approach is not general enough and cannot deal with imbricated objects for instance. An example is displayed in Figure 16.

<figure><img src="image_17.png" /><figcaption>Fig. 16. Working on the convex hulls of the objects does not provide a satisfactory result in case of imbricated objects: the between area is very reduced (two small parts in red on the left only).</figcaption></figure>

Another way to implement the notion of separation is to use the definition of [18], where a compact set is said to separate two compact sets $A_1$ and $A_2$ if any segment with extremities in $A_1$ and $A_2$ respectively hits this set. Unfortunately this definition does not yield a unique definition of $\beta(A_1, A_2)$, does not solve the problem of non visible concavities and does not prevent the separating set to intersect $A_1$ or $A_2$.

## B. *Definition based on directional dilation*

In order to improve the dilation based approach, we develop an idea similar to the one proposed in 1D in [14]. Instead of looking right of an object and left of the other, we use the directional relative position of both objects. This avoids defining an order in spaces of dimension higher than 1. Directional dilation is then performed, using directional fuzzy structuring elements, with a similar approach as in [19]. For fuzzy dilation, we use the following
definition (see [20] for more details and other possible definitions):

$$D_{\nu}(\mu)(x) = \sup_{y} t[\mu(y), \nu(x-y)], \qquad (7)$$

where $\mu$ denotes the (fuzzy) set to be dilated, $\nu$ the structuring element, and $x$ and $y$ points of space.

The main direction between two objects can be determined from the angle histogram [21]. Given an axis of reference, say the $x$ axis denoted by $\vec{u}_x$, for each pair of points $(a_1, a_2)$ with $a_1 \in A_1$ and $a_2 \in A_2$, the angle between the axis and the segment joining these two points is computed. The histogram of the obtained angles $h_{(A_1, A_2)}$ for all possible pairs of points can then be derived:

$$h_{(A_1, A_2)}(\theta) = |\{(a_1, a_2), a_1 \in A_1, a_2 \in A_2, \angle(a_1\vec{a}_2, \vec{u}_x) = \theta\}|. \qquad (8)$$

It is then normalized as:

$$H_{(A_1, A_2)}(\theta) = \frac{h_{(A_1, A_2)}(\theta)}{\max_{\theta'} h_{(A_1, A_2)}(\theta')} \qquad (9)$$

in order to be interpreted as a fuzzy set. The maximum or the average value $\alpha$ of this histogram can be chosen as the main direction between $A_1$ and $A_2$.

Let $D_\alpha$ denote the dilation in direction $\alpha$. The structuring element can be either a crisp segment in the direction $\alpha$, or a fuzzy structuring element where the membership function at a point $(r, \theta)$ (in polar coordinates) is a decreasing function of $|\theta - \alpha|$ [19]. An example is shown in Figure 17, where $\alpha$ is equal to 0 (corresponding to the horizontal axis).

<figure><img src="image_18.png" /><figcaption>Fig. 17. An example of fuzzy structuring element defined around the horizontal axis.</figcaption></figure>

From this dilation, we define:

$$\beta_{\alpha}(A_1, A_2) = D_{\alpha}(A_1) \cap D_{\pi+\alpha}(A_2) \cap A_1^C \cap A_2^2, \qquad (10)$$

which is a fuzzy set if the structuring element is fuzzy (in the fuzzy case, complementation is replaced by a fuzzy complementation and intersection by a t-norm).

Since it can be difficult to find only one main direction (from histogram of angles for instance) we can use several values for $\alpha$ and define $\beta$ as:

$$\beta(A_1, A_2) = \cup_{\alpha} \beta_{\alpha}(A_1, A_2) \qquad (11)$$

or

$$\beta(A_1, A_2) = \cup_{\alpha} (\beta_{\alpha} \cup \beta_{\alpha+\pi}). \qquad (12)$$
We can also use the histogram of angles directly as a fuzzy structuring element. Let us define two fuzzy structuring elements $\nu_1$ and $\nu_2$ from the normalized angle histogram $H_{(A_1, A_2)}(\theta)$ as:

$$ \nu_1(r, \theta) = H_{(A_1, A_2)}(\theta), \qquad (13) $$

$$ \nu_2(r, \theta) = H_{(A_1, A_2)}(\theta + \pi) = \nu_1(r, \theta + \pi). \qquad (14) $$

Several definitions of the between region can be envisaged. The simplest one is:

$$ \beta_{FDil1}(A_1, A_2) = D_{\nu_2}(A_1) \cap D_{\nu_1}(A_2) \cap A_1^C \cap A_2^C, \qquad (15) $$

which is illustrated in Figure 18.

<figure><img src="image_19.png" /><figcaption>Fig. 18. Definition based on dilation by a structuring element derived from the angle histogram (Equation 15). Objects $A_1$ and $A_2$ are displayed in red, and the membership values to $\beta(A_1, A_2)$ vary from 0 (white) to 1 (black). The angle histogram is shown on the right.</figcaption></figure>

Another definition is inspired by [14]:

$$ \beta_{FDil2}(A_1, A_2) = [D_{\nu_1}(A_1) \cup D_{\nu_1}(A_2)] \cap [D_{\nu_2}(A_1) \cup D_{\nu_2}(A_2)], \qquad (16) $$

and, by removing the concavities which are not “facing each other”, we obtain:

$$ \beta_{FDil3}(A_1, A_2) = D_{\nu_2}(A_1) \cap D_{\nu_1}(A_2) \cap A_1^C \cap A_2^C \cap [D_{\nu_1}(A_1) \cap D_{\nu_1}(A_2)]^C \cap [D_{\nu_2}(A_1) \cap D_{\nu_2}(A_2)]^C, \qquad (17) $$

which is illustrated in Figure 19.

A potential problem with these definitions is that the result may be spatially too extended. Possible solutions are to threshold the angle histogram, or to take the intersection of the result with $CH(A_1 \cup A_2)$. Since these solutions require some parameters that may seem to be chosen in an ad hoc way, a formalization of these ideas will be achieved with the visibility approach, presented next.

The extension of this approach to the case of fuzzy objects $A_1$ and $A_2$ is straightforward, by computing a weighted histogram of angles.
<figure><img src="image_20.png" /><figcaption>Fig. 19. Definition based on dilation by a structuring element derived from the angle histogram, with Equation 17.</figcaption></figure>

## V. VISIBILITY

### A. Visibility and admissible segments

Let us consider again the situation in Figure 10. If we assume that the two objects are buildings and that someone is supposed to meet another person between these buildings, then he would probably expect the person not to wait in the dashed area (concavity), but to wait in an area where he can surely see this person. This example suggests that the notion of visibility has to play an important role in the definition of between. This becomes particular clear in the example of Figure 20. Although $CH(A_1 \cup A_2) \setminus (A_1 \cup A_2)$ has only one connected component, which is adjacent to both $A_1$ and $A_2$, object $A_2$ has a concavity which is not visible from $A_1$ and should probably not be included in the between area.

<figure><img src="image_21.png" /><figcaption>Fig. 20. An example with a non visible concavity (dashed area).</figcaption></figure>

To take such situations into account, we propose to base the notion of visibility on admissible segments as introduced in [22]. A segment $[x_1, x_2]$, with $x_1$ in $A_1$ and $x_2$ in $A_2$, is said to be admissible if it is included in $A_1^C \cap A_2^C$. Note that $x_1$ and $x_2$ then necessarily belong to the boundary of $A_1$ and $A_2$, respectively ($A_1$ and $A_2$ are still supposed to be compact sets). This has interesting consequences from an algorithmic point of view, since it considerably reduces the number of points to be explored. The visible points are those which belong to admissible segments. The region $\beta_{Adm}(A_1, A_2)$ between $A_1$ and $A_2$ can then be defined as the union of admissible segments.
It corresponds to the set $CH(A_1 \cup A_2) \setminus (A_1 \cup A_2)$ from which all points not belonging to admissible segments are suppressed. The dashed area in Figure 20 would then be adequately suppressed with this definition.

## B. Fuzzy visibility

However, the definition of admissible segments may be too strict in some cases. In order to get more flexibility, we introduce the notion of approximate (or fuzzy) visibility. It extends both the crisp definition of visibility and the definition proposed in [12] in the sense that the information is not reduced to an average angle.

This is achieved by relaxing the admissibility to semi-admissibility through the introduction of an intermediary point $P$ on the segments. A segment $]a_1, P]$ with $a_1 \in A_1$ (respectively $[P, a_2]$ with $a_2 \in A_2$) is said semi-admissible if it is included in $A_1^C \cap A_2^C$. At each point $P$ of space, we compute the angle the closest to $\pi$ between two semi-admissible segments from $P$ to $A_1$ and $A_2$ respectively. This is formally defined as:

$$ \theta_{min}(P) = \min\{|\pi - \theta|, \theta = \angle([a_1, P], [P, a_2]), ]a_1, P] \text{ and } [P, a_2[ \text{ semi-admissible}\}. \quad (18) $$

The region between $A_1$ and $A_2$ is then defined as the fuzzy region of space with membership function:

$$ \beta_{FVisib}(A_1, A_2)(P) = f(\theta_{min}(P)) \quad (19) $$

where $f$ is a function from $[0, \pi]$ to $[0, 1]$ such that $f(0) = 1$, $f$ is decreasing, and becomes 0 at the largest acceptable distance to $\pi$ (this value can be tuned according to the context). This idea is illustrated in Figure 21.

<figure><img src="image_22.png" /><figcaption>Fig. 21. Illustration of the fuzzy visibility concept. For point $P_1$ (and any point in the area bounded by the dashed lines), we have $\theta_{min}(P_1) = 0$ and therefore $\beta(P_1) = 1$, while for point $P_2$, it is not possible to find two collinear semi-admissible segments from $A_1$ (respectively $A_2$) to $P_2$, thus $\theta_{min}(P_2) > 0$ and $\beta(P_2) < 1$, expressing that $P_2$ is not completely between $A_1$ and $A_2$.</figcaption></figure>

In cases of non-connected objects, the distributivity principle can be used in a similar way as what we proposed for the convexity based definition.

## C. Extension to fuzzy objects

If the objects are fuzzy, with membership functions $\mu_{A_1}$ and $\mu_{A_2}$, the notion of admissible segments has to be changed by replacing the inclusion by a fuzzy inclusion. This concerns both the membership of the extremities of the segments $a_1$ and $a_2$, and the inclusion of $]a_1, a_2[$ in $A_1^C \cap A_2^C$, which can be expressed as a usual degree of inclusion:

$$ \mu_{incl}([a_1, a_2[) = \inf_{y \in [a_1, a_2[} \min[1 - \mu_{A_1}(y), 1 - \mu_{A_2}(y)], \quad (20) $$
if the segment is kept crisp. This equation defines a degree of visibility of a segment. The area between $A_1$ and $A_2$ is then a fuzzy set, defined as:

$$ \beta_{Adm}(A_1, A_2)(P) = \sup\{\mu_{incl}([a_1, a_2]); P \in [a_1, a_2[, a_1 \in \text{Supp}(A_1), a_2 \in \text{Supp}(A_2)\}, \quad (21) $$

where $\text{Supp}(A_i)$ denotes the support of the fuzzy set $A_i$, i.e. the set of points having non-zero membership values. The only constraint on $a_1$ and $a_2$ in this expression is that they belong to the supports of each fuzzy set. This guarantees that a point $P$ in the complement of the union of the supports can have a degree of being between equal to 1. A more strict definition could also involve $\mu_{A_1}(a_1)$ and $\mu_{A_2}(a_2)$, combined conjunctively with $\mu_{incl}([a_1, a_2])$, but this would strongly reduce the membership values to $\beta$. We keep the same notation $\beta_{Adm}$ as in the crisp case, since this Equation reduces to the crisp one if the objects are crisp. The degree of visibility of a segment can be interpreted as a degree of transparency. If it is equal to 1, then the segment is completely visible, if it is equal to 0, at least one point is not visible at all. Since this may appear as quite severe, the infimum in Equation 20 can be replaced by an average operator for instance, leading to a compensation between points of the segments which are visible and others that are less.

More interesting is the extension of the fuzzy visibility method to the case of fuzzy objects. Let us consider again Equations 18 and 19. Since the function $f$ is supposed to be decreasing, we can write:

$$ \begin{aligned} \beta_{FVisib}(A_1, A_2)(P) &= f(\min\{|\pi - \theta|, \theta = \angle([a_1, P], [P, a_2]),]a_1, P\} \text{ and } [P, a_2[ \text{ semi-admissible}]) \\ &= \max\{f(|\pi - \theta|), \theta = \angle([a_1, P], [P, a_2]),]a_1, P\} \text{ and } [P, a_2[ \text{ semi-admissible}]\}. \end{aligned} \quad (22) $$

Now if $A_1$ and $A_2$ are fuzzy, as above we replace the inclusion by a fuzzy inclusion (Equation 20), leading to the fuzzy visibility area between two fuzzy sets:

$$ \begin{aligned} \beta_{FVisib}(A_1, A_2)(P) &= \max\{t[f(|\pi - \theta|), a_1 \in \text{Supp}(A_1), a_2 \in \text{Supp}(A_2), \mu_{incl}([a_1, P]), \mu_{incl}([P, a_2])], \\ & \theta = \angle([a_1, P], [P, a_2])\} \end{aligned} \quad (23) $$

where $t$ is a t-norm (min for instance). This expresses, for each pair of segments issued from $P$ and with end point in $A_1$ (respectively $A_2$), a conjunction between the degree of semi-admissibility of the segments ($\mu_{incl}$) and $f(|\pi - \theta|)$. Then the best value over all segments is kept. If the segments are completely visible (semi-admissible), then the inclusion degrees are equal to 1 and are not involved in the computation of the t-norm. If the segments are not visible at all, the inclusion degrees are equal to 0, leading to 0 in the computation of the t-norm. This means that such segments are not involved in the computation of the maximum, which is satisfactory too. Again, this definition reduces to Equation 19 in case of crisp objects.

### D. Objects with very different spatial extensions: myopic vision

In this Section, we assume that one of the objects, say $A_2$, can be considered to have infinite size with respect to the other (we assume this to be known in advance). This is the case for instance when one says that a fountain
is between the house and the road, or that the sport area is between the city hall and the beach. None of the previous definitions applies in such cases, since they consider objects globally. Intuitively, the between area should be considered between $A_1$ and the only part of $A_2$ which is the closest to $A_1$, instead of considering $A_2$ globally. Hence the idea of projecting $A_1$ onto $A_2$ in some sense, and to consider the “umbra” of $A_1$. Here we make an additional assumption, largely verified in most situations, by approximating the part closest to $A_1$ by a segment<fnref n="4" />. Let us denote the segment direction by $\vec{u}$. The between region can then be defined by dilating $A_1$ by a structuring element defined as a segment orthogonal to $\vec{u}$ and limiting this dilation to the half plane defined by the segment of direction $\vec{u}$ and containing $A_1$. However this may appear as too restrictive and a fuzzy dilation [20] by a structuring element having decreasing membership degrees when going apart of the direction orthogonal to $\vec{u}$ is more flexible and matches better the intuitive idea. Figure 17 shows an example of fuzzy structuring element in case $\vec{u}$ is the vertical direction [19].

The projection segment can be defined by dilating the part of $A_2$ closest to $A_1$ (obtained by a distance map computation) conditionally to $A_2$ and computing the axis of inertia of the result.

This approach is illustrated in Figure 22. In terms of visibility, it corresponds to a “myopic” vision, in which the parts of $A_2$ which are too far from $A_1$ are not seen.

<figure><img src="image_23.png" /><figcaption>Fig. 22. Illustration of the definition of region $\beta$ in case of an extended object (myopic vision). In the areas indicated by $\beta > 0$, the relation is satisfied to some degree between 0 and 1. They can be more or less spread depending on the structuring element, i.e. on the semantics of the relation.</figcaption></figure>

## E. Adding a visibility constraint

In case the objects have concavities, this method should be combined with the visibility method in order to avoid counter-intuitive results. For instance in Figure 23, the concavity of object $A_1$ will be included in $\beta$ using the myopic approach. A simple solution to avoid this is to combine in a conjunctive way (e.g. using a minimum) this definition of $\beta$ with the region provided by the visibility method (based on admissible segments) computed in

<footnote n="4">⁴If this appears to be too restrictive, the part closest to $A_1$ can be approximated by several segments, of different directions, and the orthogonal direction is then locally defined.</footnote>
the support of $\beta$. The admissible segments can be further restricted to those in the projection direction (orthogonal to $\vec{u}$).

<figure><img src="image_24.png" /><figcaption>Fig. 23. An example with a concavity in $A_1$ not visible from $A_2$ (region X) and an extended object $A_2$ having concavities not visible from $A_1$ (Y).</figcaption></figure>

While the problem for concavities of $A_1$ can be easily solved, the question is less trivial for possible concavities of $A_2$. Figure 23 shows an example where $A_2$ has indeed a concavity not visible from $A_1$. This concavity should also be eliminated if we consider that both objects play a symmetrical role. Actually this is not exactly true in this case, since projecting $A_1$ onto $A_2$ or onto a part of it is not a symmetrical operation. Moreover, the approximation of $A_2$ by a segment cannot be done globally, but only the elongated part of $A_2$ facing $A_1$ should be considered for this approximation, as shown in Figure 23. Then the non visible concavity is on the side of the approximation line that is not concerned by the projection and therefore not included in $\beta$ anyway. These arguments advocate for ignoring the concavities of $A_2$ and concentrating on the ones of $A_1$ only.

This approach is illustrated on synthetic objects in Figure 24. The result of dilation was conditioned by the visibility region defined by the admissible segments in order to account for the concavities.

<figure><img src="image_25.png" /><figcaption>Fig. 24. Region $\beta_{Adm}$ between the two objects on the left, computed by directional fuzzy dilatation, and restricted to the union of admissible segments. The main direction $\vec{u}$ of the extended object is computed locally in a the region close to the other object. This is achieved by thresholding a distance map between both objects. The fuzzy structuring element has membership values equal to 1 in the direction orthogonal to $\vec{u}$, and decreasing degrees when going away of this direction. Region $\beta$ can be more or less spread depending on the structuring element.</figcaption></figure>
VI. SATISFACTION DEGREE OF THE RELATION “BETWEEN”

Once $\beta(A_1, A_2)$ is determined, using one of the proposed methods, the degree to which $B$ is between $A_1$ and $A_2$ can be defined and computed, by comparing $B$ and $\beta(A_1, A_2)$. The aim of this Section is to specify this comparison and to propose measures in different situations.

We propose to base the comparison on a degree of overlapping between $B$ and $\beta(A_1, A_2)$. Considering a degree instead of a all-or-nothing answer allows us to account for the fuzziness of the between relation, for instance in cases such as in Figure 1. Several ways can be explored to define this overlap degree, again with a strong dependence on the context, in particular concerning the spatial extension of the objects. For instance a simple measure such as the ratio between the surface of $B \cap \beta$ and the surface of $B$ is not always appropriate.

A required property is that the degree of overlapping should be 1 if $B \subseteq \beta$ and 0 if $B \subset \beta^C$. Although this sets some limits, it is far from being constraining and is not very helpful in intermediary situations. Fuzzy pattern matching can be a useful tool [23], by providing a pair of necessity/possibility measures, representing both a degree of inclusion and a degree of intersection. Other comparison measures can be investigated as well, such as satisfiability measures [24]. Let us now detail these solutions in two different situations ($B$ and $\beta$ can be either crisp or fuzzy in what follows).

A. Object $B$ with limited spatial extension.

We first assume that $B$ has typically a size of the same order of magnitude as $A_1$, $A_2$, or $\beta(A_1, A_2)$. Then an appropriate comparison measure is the normalized intersection:

$$S_1(B, \beta) = \frac{|B \cap \beta|}{|B|} \qquad (24)$$

This measure belongs to the more general class of satisfiability measures (i.e. which are increasing with respect to the two sets to be compared and decreasing with respect to their difference). Other possible measures in this class are for instance [24], [25]:

$$S_2(B, \beta) = 1 - \sup\{\mu_B(x)/\beta(x) = 0\}, \qquad (25)$$

$$S_3(B, \beta) = \inf_x \min(1 - \mu_B(x) + \beta(x), 1). \qquad (26)$$

In these equations, $x$ denotes any point of space, and $\mu_B$ the membership function to $B$.

A measure defined as an interval $[N, \Pi]$ [23], where $N$ is a degree of inclusion defined from a t-conorm $T$ as:

$$N(B, \beta) = \inf_x T[\beta(x), 1 - \mu_B(x)] \qquad (27)$$

and $\Pi$ is a degree of intersection defined from a t-norm $t$ as:

$$\Pi(B, \beta) = \sup_x t[\beta(x), \mu_B(x)] \qquad (28)$$

is also interesting since the length of this interval provides information on the ambiguity of the relation.

These measures will be illustrated on real objects in Section VIII. In our experiments, they have been computed using the minimum for $t$ and the maximum for $T$.
## B. Extended B.

We now move to the case of an object $B$ with a large spatial extent (which can be considered as infinite with respect to $A_1$, $A_2$, or $\beta$). If $B$ has a spatial extent which is similar to $\beta(A_1, A_2)$, then the computation of $S_1(B, \beta)$ is still meaningful.

Otherwise, typically if $B$ is itself elongated, the previous measures are not appropriate since the fact that $B$ extends outside $\beta$ should not be penalized. Thus the normalization by $|B|$ in the overlap degree does not make much sense. Inclusion is generally not satisfied and the pattern matching approach will always provide $[N, \Pi] = [0, 1]$ in case $B$ is actually between $A_1$ and $A_2$. Such a result is not discriminating enough since it can also be obtained in other situations, for instance in cases where $B$ has only one point in $\beta$. Other measures should then be defined, representing the notion “$B$ passes through $\beta$”. We develop here two methods for modeling this notion.

The first one relies on the assumption that $\text{Supp}(\beta) \setminus \text{Core}(\beta)$ has two connected components ($\text{Core}(\beta)$ denotes the core of $\beta$, i.e. the set of points having a membership value equal to 1, and $\text{Supp}(\beta)$ its support). This assumption generally holds and is reasonable for both crisp and fuzzy methods. It relies on the fact that $A_1$ and $A_2$ are not connected to each other, and on the following considerations. In the crisp case, $\beta$ has three types of boundaries: (i) common boundaries with $A_1$ and $A_2$, (ii) boundary inside $CH(A_1 \cup A_2)$ limiting non-visible concavities (if any), and (iii) two straight segments included in the boundary of $CH(A_1 \cup A_2)$. Now if we consider the set $R$ of points of the complement of $CH(A_1 \cup A_2)$ which are neighbors of the straight boundaries, it can be partitioned into two connected components $R_1$ and $R_2$ (see e.g. Figure 20). Now in the fuzzy case, $\text{Core}(\beta)$ has the same types of boundaries as $\beta$ in the crisp case. Let $R = \text{Supp}(\beta) \setminus \text{Core}(\beta)$. For the method of semi-admissible segments (fuzzy visibility), this region corresponds to points $P$ belonging to semi-admissible segments with an angle at $P$ less than $\pi$, but higher than some threshold value. Therefore, this region cannot extend much and the two parts adjacent to each straight boundary cannot join together. Therefore $R$ has again two connected components. The same holds for definitions based on dilation, either based on angle histogram or on projection, since the structuring element has an angular support of limited aperture (see Figure 22 for instance). Let us denote by $R_1$ and $R_2$ these components. The degree to which $B$ passes through $\beta$ will be high if $B$ goes at least from a point in $R_1$ to a point in $R_2$. This could be formalized for instance by computing the maximum of membership degrees of points of $B$ to $\beta$ along paths included in $B$, with extremities $x_1$ and $x_2$ in $R_1$ and $R_2$ respectively. Particular cases where $x_1$ or $x_2$ do not exist should be considered:

* if neither $x_1$ nor $x_2$ exist, then either $B$ is included in the core of $\beta$ and then the measure $S_1(B, \beta)$ is still meaningful, or $B \cap \beta = \emptyset$ and the degree should be simply equal to 0;

* if $x_1$ does not exist in $B$, but $x_2$ does (or the contrary), then a strict version could be to set the degree of being between to 0; a less severe approach could be to compute the normalized intersection, but restricted to the points of $B$ having a non-zero membership to $\beta$.

Another criterion along the same line is to check whether $B \setminus \beta$ has two components, on each side of $\beta$ (or of
Core(β)). A good measure is then:

$$M_1(B, \beta) = \min[\sup_{x \in R_1}(B \cap \beta^C)(x), \sup_{x \in R_2}(B \cap \beta^C)(x)], \quad (29)$$

which directly applies to the fuzzy case as well. In this Equation, $\beta$ can be replaced by its core, leading to a less pessimistic evaluation;

$$M_2(B, \beta) = \min[\sup_{x \in R_1}(B \cap \text{Core}(\beta)^C)(x), \sup_{x \in R_2}(B \cap \text{Core}(\beta)^C)(x)]. \quad (30)$$

Of course these measures make sense only if $B \cap \text{Core}(\beta) \neq \emptyset$, otherwise the degree of satisfaction of the relation should be set to 0. An illustration of both equations is provided in Figure 25 in 1D, for a crisp $B$ and fuzzy $\beta$.

<figure><img src="image_26.png" /><figcaption>Fig. 25. Example of computation of the degree of satisfaction of the relation in the case of an extended object $B$ (in a one dimensional space). Using Equation 29, the obtained value is $\mu_1$, which can be considered as a pessimistic evaluation. Using Equation 30, the obtained value is equal to 1, which may better fit the intuitive expectation.</figcaption></figure>

The second method we propose considers the coordinates of a sequence of points included in $B$ along the direction orthogonal to the projection direction. For increasing values of these coordinates along the sequence, the membership to $\beta$ should first increase and then decrease (not strictly). The maximum of $\beta$ along such sequences is then taken as the degree of betweenness.

Actually this type of measure could be used in more general cases, if the size of $B$ should not play an important role for the considered application. Let us for instance consider the examples in Figure 26. In the first example, we surely want $B$ to be between $A_1$ and $A_2$ with a degree 1. For the two other examples, the degree will depend on the definition and on the context. With the normalized intersection, the degree will decrease from the first example to the third one. With the proposed measure for elongated $B$, it would be 1 for all three examples. The question is to know what we want, in particular in the third case. If this instance of $B$ is a road passing between two houses, then it is consistent to obtain a degree equal to 1. If $B$ represents the area in which a person is supposed to wait, then it would be probably less convenient. We would expect the person to wait in a more restricted sense between the two houses, i.e. in the convex hull of the union of $A_1$ and $A_2$ (dashed lines). These examples show that the processing of cases where $B$ is extended also highly depends on the context of the application.
<figure><img src="image_27.png" /><figcaption>Fig. 26. Three cases where the degree to which *B* is between *A*₁ and *A*₂ may vary depending on the context and on the definition.</figcaption></figure>

# VII. PROPERTIES AND EXTENSIONS

## A. Properties of the main definitions

Several definitions have been proposed in the previous Sections. As explained all through the text, they are not applying adequately to all types of situations. Table I provides a summary of the cases where each of them applies. We distinguish cases where both objects are convex (denoted by “convex” in the Table), where they are not necessarily convex, but have concavities facing each other (“facing concavities”), such as in the example in Figure 9, where they have complex shapes, with any type of concavity (“complex shape”), where they are fuzzy sets (“fuzzy”), and where one object is much more extended than the other (“extended”).

<table><caption>TABLE I</caption><thead><tr><th>Types of objects →<br>Definitions ↓</th><th>Convex</th><th>Facing concavities</th><th>Complex shape</th><th>Fuzzy</th><th>Extended</th></tr></thead><tbody><tr><td>Convex hull β<sub>CH</sub></td><td>Y</td><td>Y</td><td>N</td><td>Y</td><td>N</td></tr><tr><td>Dilation β<sub>Dil</sub></td><td>N</td><td>N</td><td>N</td><td>N</td><td>N</td></tr><tr><td>Separation by watersheds or SKIZ β<sub>sep</sub></td><td>Y</td><td>Y</td><td>N</td><td>N</td><td>N</td></tr><tr><td>Fuzzy directional dilation β<sub>Fdil1</sub></td><td>Y</td><td>Y</td><td>N</td><td>Y</td><td>N</td></tr><tr><td>Fuzzy directional dilation β<sub>Fdil2</sub></td><td>Y</td><td>Y</td><td>N</td><td>Y</td><td>N</td></tr><tr><td>Fuzzy directional dilation β<sub>Fdil3</sub></td><td>Y</td><td>Y</td><td>Y</td><td>Y</td><td>N</td></tr><tr><td>Admissible segments β<sub>Adm</sub></td><td>Y</td><td>Y</td><td>Y</td><td>Y</td><td>N</td></tr><tr><td>Fuzzy visibility β<sub>Adm</sub></td><td>Y</td><td>Y</td><td>Y</td><td>Y</td><td>N</td></tr><tr><td>Myopic vision</td><td>Y</td><td>Y</td><td>N</td><td>Y</td><td>Y</td></tr><tr><td>Myopic vision + visibility</td><td>Y</td><td>Y</td><td>Y</td><td>Y</td><td>Y</td></tr></tbody></table>

SUMMARY OF THE PROPOSED DEFINITIONS AND THE CASES WHERE THEY APPLY IN A SATISFACTORY WAY.

The proposed definitions of $β(A_1, A_2)$ have the following properties:

* symmetry (by construction), except for the case of objects with very different spatial extensions;

* invariance with respect to geometrical operations (translation, rotation);
* invariance under affine transformations for convex hull and visibility methods;

* distributivity for non-connected objects (by construction); note that if $A_1$ and $A_2$ are connected, the property does not hold in general;

* for the convex hull method and for admissible segments, the following equality holds: $\beta(A, A) = CH(A) \cap A^C$;

* since convex hull and dilation operations used in the construction of some definitions of $\beta$ are continuous when applied on compact sets, the mapping $\beta(A_1, A_2)$ is continuous for $A_1$ and $A_2$ being compact sets (in a continuous space) for the definitions based on convex hull (Equation 1) and dilations; it is not continuous if the connected components not adjacent to both objects are removed from the convex hull, as already mentioned, nor for the visibility methods;

* in terms of complexity, the computation of $\beta(A_1, A_2)$ for the admissible segment methods is of the order of $N_1 N_2 \sqrt{N}$, where $N_i$ denotes the cardinality of $A_i$ and $N$ denotes the cardinality of the bounded space in which the computation is performed (image)<fnref n="5" />; for the methods based on fuzzy dilations (morphological approach and myopic vision for extended objects), the complexity is $O(NN_\nu)$ where $N_\nu$ is the cardinality of the support of the structuring element used in the fuzzy dilations; the morphological approach additionally requires the computation of the angle histogram which has a complexity of $O(N_1N_2)$; finally, the fuzzy visibility approach has a complexity of $O(NN_1N_2)$.

The properties of the degree of satisfaction of the relation are given below for some extreme cases:

* $S_1(B, \beta)$ is equal to 0 iff $B \cap \beta = \emptyset$ (i.e. $B$ is completely outside the between area) and equal to 1 iff $B \subseteq \beta$;

* $S_2(B, \beta)$ is equal to 0 iff $B \cap \beta^C \neq \emptyset$, which is stronger than the condition for the previous measure, and equal to 1 iff $B \subseteq \beta$;

* $S_3(B, \beta)$ is equal to 0 iff $B \cap \beta^C \neq \emptyset$, and equal to 1 iff $B \subseteq \beta$;

* $N(B, \beta) = 0$ as soon as $B$ intersects $\beta^C$; $N(B, \beta) = 1$ iff $B \subseteq \text{Core}(\beta)$ for $T$ being the maximum of the algebraic sum, iff $B = \beta$ for the Lukasiewicz t-conorm;

* $\Pi(B, \beta) = 0$ iff $\text{Supp}(B) \cap \text{Supp}(\beta) = \emptyset$ for $t$ being the minimum or the product, iff $B = \beta^C$ for the Lukasiewicz t-norm; $\Pi(B, \beta) = 1$ iff $\text{Core}(B) \cap \text{Core}(\beta) \neq \emptyset$;

* given that $B \cap \text{Core}(\beta) \neq \emptyset$, $M_1(B, \beta)$ (Equation 29) provides 0 iff $B \cap R_1 = \emptyset$ or $B \cap R_2 = \emptyset$, and 1 iff $B \cap \beta^C \cap R_1 \neq \emptyset$ and $B \cap \beta^c \cap R_2 \neq \emptyset$ (i.e. $B$ should extend further than the support of $\beta$ on both sides), which is indeed severe; on the other hand, $M_2(B, \beta)$ (Equation 30) provides 1 as soon as $B$ intersects $R_1$ and $R_2$, and 0 iff $B \cap R_1 = \emptyset$ or $B \cap R_2 = \emptyset$.

<footnote n="5">⁵Indeed checking that the segment is admissible has a complexity equal to the length of the segment. In the worst case, assuming a square image of size $\sqrt{N} \times \sqrt{N}$, the segment can have the length of the diagonal of the image, i.e. $\sqrt{2N}$. Therefore the worst-case complexity for this method is $N_1 N_2 \sqrt{N}$. In practice it is less since segments are shorter and only the points on the boundary of $A_1$ and $A_2$ are used as end points of the segments.</footnote>
## B. Extensions

Although all illustrations in this paper are given in 2D, mainly for sake of easiness of representation, most approaches apply directly in 3D. This is the case for the convex hull method, for approaches based on mathematical morphology, as well as for the visibility methods (actually, there is no assumption about the space dimension in these methods). The only case that requires some more discussion is the one of extended objects. Let us assume that object $A_2$ is extended. For 3D objects, two types of spatial extension have to be considered:

1) $A_2$ is almost a surface, and can be approximated by a 2D manifold (in the medical example used as illustration in Section VIII, it could be the interhemispheric plane for instance). Then the methods can be directly extended: the object is (at least locally, near $A_1$) approximated by a plane, and the orthogonal direction is chosen as projection direction. The structuring element has a maximal value along this axis, and decreasing membership values when going further from this direction (with a conic shape for instance).

2) $A_2$ is a “linear” object<fnref n="6" /> (in the medical example, it could be a blood vessel for instance). In this case, two methods can be envisaged:

* the first one consists in considering the principal axis of $A_2$ in order to define a structuring element with maximal membership values on a plane orthogonal to this axis and decreasing on both parts of it, and apply the same approach as in 2D;

* the second one consists in defining admissible segments in planes orthogonal to $A_2$ at each point (then the main direction of $A_2$ is defined locally at each point).

Another point that is worth discussing here is the case where both objects are extended. If one is still much more extended than the other, then the myopic vision approach can still be used. More interesting is the case where both objects can be considered as infinite, with respect to $B$ in particular. One of the previous method could be applied to the whole objects, but there are a lot of situations where this is not really meaningful. For instance, when saying “the house is between the river and the road”, we implicitly consider a region of interest around the house, and ignore the spatial arrangement of the objects at higher distance of $B$. This idea of region of interest is easy to implement, since any of the proposed approaches can be applied conditionally to such a region. It is interesting to note that what is proposed here consists of a spatial contextualization of the relation with respect to $B$. In the case of one extended object, the proposed method used a spatial contextualization of the relation with respect to $A_1$. Actually, defining a region of interest with respect to $B$ could be used in the other cases as well, but this might be debatable. Indeed, $\beta(A_1, A_2)$ would then not only depend on $A_1$ and $A_2$, but also on $B$, which is in contradiction with the approach we propose (i.e. defining first the area between two objects and then assess the adequation between this area and $B$). However, this could be interesting in some particular situations. We leave this for future work.

<footnote n="6">⁶i.e. having at each point a principal direction which is much stronger than the two other ones</footnote>
VIII. ILLUSTRATIVE EXAMPLES

In this Section, we illustrate some of the proposed definitions on anatomical objects. The first example concerns brain structures.

Figure 27 presents a few brain structures, on a 2D slice. Usual anatomical descriptions make intensive use of spatial relations to describe such objects<sup>7</sup> [26] and such descriptions are very useful for recognizing these structures in medical images [3], [4]. The between relation is involved in many of these descriptions. Let us provide three examples of such descriptions:

* the internal capsule (IC) is *between* the caudate nucleus (CN) and the lenticular nucleus (LN);

* the corpus callosum (CC) is *between* the lateral ventricles (LV) and the cingulate gyrus (CG);

* the medial frontal gyrus (MFG) is *between* the inferior frontal gyrus (IFG) and the superior frontal gyrus (SFG).

<figure><img src="image_28.png" /><figcaption>Fig. 27. A few brain structures (a 2D slice extracted from a 3D atlas).</figcaption></figure>

Our definitions were applied to define the region between the aforementioned brain structures. Figure 28 illustrates the third example and shows the region “between” IFG and SFG using the directional dilation (a-d), the convex hull approach (e), the admissible segments (f) and the fuzzy visibility (g). It is clear that the convex hull definition does not deal appropriately with concavities. This problem is solved by the directional dilation and visibility approaches. In (c) and (e), non visible concavities are included in the result, while they have been adequately suppressed in (d), (f) and (g). Also, it should be noted that fuzzy methods (directional dilation and fuzzy visibility) are more appropriate than crisp ones (convex hull and admissible segments): the median frontal gyrus is partly outside the $β$ region defined by crisp approaches while remaining in areas with high membership degrees when using the fuzzy ones. This last result better fits the intuition, and is confirmed by the high values obtained for the overlap measure. Note that the region where $β = 1$ is the same in (f) and (g) and almost the same in (d), therefore these approaches are equivalent for objects completely included in this region. Visibility methods and fuzzy dilations are better in handling concavities than the convex hull approach since the only concavities which are visible from the other

<footnote n="7"><sup>7</sup>http://www.chups.jussieu.fr/ext/neuranat</footnote>
object are kept in $\beta$. The fact that parts of object *B* which are outside the convex hull of $A_1 \cup A_2$ have a non zero membership degree to the area $\beta$ is consistent with the way of speaking about the relation in many situations. For instance, it is often said that “the nose is between the eyes”, which is understood by anybody, but does not mean that the nose is in the convex hull of the union of both eyes (generally it is not!).

<figure><img src="image_29.png" /><figcaption>Fig. 28. (a) Angle histogram of objects $A_1$ and $A_2$ (superior and inferior frontal gyri, displayed in red and blue in (c)). (b) Corresponding structuring element $\nu_1$ ($\nu_2$ is its symmetric with respect to the origin). (c) Definition based on fuzzy dilation (Equation 15). Membership values to $\beta(A_1, A_2)$ vary from 0 (white) to 1 (black). The contours of the median frontal gyrus are superimposed in green. (d) Definition based on fuzzy dilation, with Equation 17. (e) Convex hull approach. (f) Definition using the admissible segments. (g) Fuzzy visibility approach.</figcaption></figure>

To evaluate the relation “*B* is between $A_1$ and $A_2$”, we computed the normalized intersection of *B* and $\beta$: $\frac{|\beta \cap B|}{|B|}$. A few results are shown in Table II. They correspond to what is intuitively expected. Higher degrees are obtained with fuzzy methods which again indicates that they deal more appropriately with objects that would not be completely included in the crisp $\beta$ region. The measures are however quite similar for all approaches, since none of the objects *B* is located in a concavity. The fifth line corresponds to a case where only a part of *B* is between $A_1$ and $A_2$, the relation being thus satisfied with a lower degree than in the previous cases. This case can be compared to the ones obtained in the fourth line. Indeed the corpus callosum (CC) is more between the caudate nucleus (CN) and the cingulate gyrus (CG) than the lateral ventricules (LV), which have their lower part outside the between area. All methods preserve the order intuitively expected between the different situations. However,
ratios cannot be directly compared. The last two lines correspond to cases where the relation is not satisfied. Low but non-zero values are obtained with the fuzzy approaches, because of the tolerance on the angles. Fuzzy methods provide higher degrees than non fuzzy ones (after suppressing the non visible concavities), since they are more tolerant, as seen in Figure 28, and do not restrict the between area to the convex hull of the union of both objects (or a subset of it). We also provide results on the interval [N, Π]. For the convex hull and admissible methods, this measure is not really significant (the results for both methods are exactly the same). On the contrary, the overlap measure corresponds to what is intuitively expected. The intervals obtained for the fuzzy visibility method are more interesting since they better discriminate different types of situations. These intervals are similar for the fuzzy dilations, and are therefore not displayed.

<table><caption>TABLE II</caption><thead><tr><th>A<sub>1</sub></th><th>A<sub>2</sub></th><th>B</th><th>|β∩B| / |B| (1)</th><th>|β∩B| / |B| (2)</th><th>|β∩B| / |B| (3)</th><th>|β∩B| / |B| (4)</th><th>[N, Π] (1)</th><th>[N, Π] (4)</th></tr></thead><tbody><tr><td>CN</td><td>LN</td><td>IC</td><td>0.85</td><td>0.84</td><td>0.84</td><td>0.94</td><td>[0, 1]</td><td>[0.2, 1]</td></tr><tr><td>LV</td><td>CG</td><td>CC</td><td>1.00</td><td>0.93</td><td>1.00</td><td>1.00</td><td>[1, 1]</td><td>[1, 1]</td></tr><tr><td>IFG</td><td>SFG</td><td>MFG</td><td>0.78</td><td>0.92</td><td>0.76</td><td>0.95</td><td>[0, 1]</td><td>[0.7, 1]</td></tr><tr><td>CG</td><td>CN</td><td>CC</td><td>0.88</td><td>0.90</td><td>0.88</td><td>0.97</td><td>[0, 1]</td><td>[0.6, 1]</td></tr><tr><td>CG</td><td>CN</td><td>LV</td><td>0.47</td><td>0.63</td><td>0.47</td><td>0.79</td><td>[0, 1]</td><td>[0, 1]</td></tr><tr><td>IFG</td><td>SFG</td><td>IC</td><td>0.00</td><td>0.02</td><td>0.00</td><td>0.16</td><td>[0, 0]</td><td>[0, 0.6]</td></tr><tr><td>IFG</td><td>SFG</td><td>LN</td><td>0.00</td><td>0.00</td><td>0.00</td><td>0.04</td><td>[0, 0]</td><td>[0, 0.3]</td></tr></tbody></table>

A FEW RESULTS OBTAINED WITH THE METHOD OF CONVEX HULL (1), FUZZY DIRECTIONAL DILATION (USING EQUATION 17) (2), ADMISSIBLE SEGMENTS (3) AND WITH THE FUZZY VISIBILITY APPROACH (4).

Let us consider another example to illustrate the usefulness of the fuzzy approaches. It is still medical imaging, but now in the thoracic area. A useful way to segment the heart in computerized tomography (CT) images consists in reducing the search area in order to avoid confusion with other soft tissues such as the liver. This search area can be intuitively defined as the area between the lungs, as can be seen in Figure 29.

<figure><img src="image_30.png" /><figcaption>Fig. 29. A coronal slice of a CT image in the thoracic area.</figcaption></figure>
The method based on crisp admissible segments provides an interesting result, but somewhat restricted since a part of the heart is outside of the resulting region. This is illustrated in Figure 30.

<figure><img src="image_31.png" /><figcaption>Fig. 30. Contours of $\beta_{Adm}$ representing the region between the lungs, superimposed on an axial slice and on a coronal slice.</figcaption></figure>

Figure 31 illustrates the results obtained by fuzzy dilation based on angle histograms. The fuzzy region includes, with decreasing degrees, parts outside the convex hull of the union of the lungs. This constitutes a better region of interest for the heart for instance, compared to the crisp version. The contours of the heart have been added to this Figure in order to illustrate this feature of the proposed approach.

<figure><img src="image_32.png" /><figcaption>Fig. 31. Fuzzy region $\beta_{FDil3}$ between the lungs, superimposed on an axial slice and on a coronal slice of the segmented lungs. The contours of the heart and aorta are superimposed too.</figcaption></figure>

Figure 32 illustrates the results obtained on the same objects with the fuzzy visibility method (i.e. semi-admissible segments). Similar conclusions as for the fuzzy dilation can be drawn.

The satisfaction degree of the relation “the heart is between the lungs”, computed with measure $S_1$, is equal to 0.87 for the crisp method (admissible segments), and to 0.99 for both fuzzy methods (fuzzy dilation and fuzzy visibility). The higher degree obtained for the fuzzy methods confirms the usefulness of such approaches for modeling this type of anatomical information.
<figure><img src="image_33.png" /><figcaption>Fig. 32. Fuzzy region $\beta_{FAdm}$ between the lungs, obtained with the method of semi-admissible segments (fuzzy visibility), superimposed on an axial slice and on a coronal slice of the segmented lungs.</figcaption></figure>

## IX. CONCLUSION

We have shown in this paper how a complex spatial relation, “between”, can be modeled using simple tools of mathematical morphology and fuzzy mathematical morphology, and using notions of visibility. We addressed the modeling of this relation in cases where objects have similar spatial extensions or very different ones. Methods based on convex hull or crisp visibility (admissible segments) provide good results only for quite simple objects. On the contrary, methods based on mathematical morphology and fuzzy visibility apply on more general cases and provide results which correspond to what is intuitively expected, even in complex situations. These original approaches overcome the limits of existing methods.

Based on the definition of the area between two objects $A_1$ and $A_2$, we proposed several measures to assess the degree to which an object $B$ is between $A_1$ and $A_2$, in different types of contexts. These measures provide quantitative evaluations of the degree of satisfaction of the relation, either as a number, or as an interval expressing the possible ambiguity of the relation.

Properties of these definitions could be further studied, as well as possible links or transitions from one definition to the other, so as to achieve a continuity from the case where the objects have similar spatial extensions to the one where one becomes much more elongated. Future work aims also at introducing the between relation in structural pattern recognition and spatial reasoning schemes, as done previously for other relations [2], [4], [5]. Since the acceptance of the relation is largely depending on the context, another direction of research would be to learn typical classes of the relation (related to different contexts). This could be based on psycholinguistics and human perception experiments, or on the degrees of satisfaction of the relation in different cases.

The representation of the relation “between” has potential fruitful applications in different domains of computer science. In image processing, it could be used for the structural recognition of objects or as source of prior knowledge for image segmentation. This is particularly true in medical applications since the “between” relationship plays an important role in the description of anatomy (some first examples of brain and thoracic anatomy were given in Section VIII). Our representations, based on the definition of a “between” region, could be easily combined with
other spatial relations [27] and integrated in segmentation and recognition procedures that we previously proposed based on graph matching [28], [29] or deformable models [4]. Moreover it could be used, along with other relations, to construct descriptions of images for content-based image indexing and retrieval. This field received recently a growing attention and could benefit of such structural models. Potential applications are not restricted to imaging. In geographic information systems (GIS), this relation could be introduced to formalize queries about the arrangement of spatial landmarks (for example roads and buildings) [30]. In autonomous robotics, it could allow extracting complex structural information about the environment [31].

REFERENCES

[1] I. Bloch, T. Géraud, and H. Maître, "Representation and Fusion of Heterogeneous Fuzzy Information in the 3D Space for Model-Based Structural Recognition - Application to 3D Brain Imaging," *Artificial Intelligence*, vol. 148, pp. 141–175, 2003.

[2] R. Cesar, E. Bengoetxea, and I. Bloch, "Inexact Graph Matching using Stochastic Optimization Techniques for Facial Feature Recognition," in *International Conference on Pattern Recognition ICPR 2002*, vol. 2, Québec, aug 2002, pp. 465–468.

[3] O. Colliot, O. Camara, and I. Bloch, "Integration of Fuzzy Structural Information in Deformable Models," in *Information Processing and Management of Uncertainty IPMU 2004*, vol. 2, Perugia, Italy, jul 2004, pp. 1533–1540.

[4] O. Colliot, O. Camara, R. Dewynter, and I. Bloch, "Description of Brain Internal Structures by Means of Spatial Relations for MR Image Segmentation," in *SPIE Medical Imaging*, vol. 5370, no. 1, San Diego, CA, USA, 2004, pp. 444–455.

[5] O. Colliot, A. Tuzikov, R. Cesar, and I. Bloch, "Approximate Reflectional Symmetries of Fuzzy Objects with an Application in Model-Based Object Recognition," *Fuzzy Sets and Systems*, vol. 147, pp. 141–163, 2004.

[6] Y. Mathet, "Etude de l'expression en langue de l'espace et du déplacement : analyse linguistique, modélisation cognitive, et leur expérimentation informatique," Ph.D. dissertation, Université de Caen, France, Dec. 2000.

[7] I. Bloch, O. Colliot, and R. Cesar, "Modélisation de la relation spatiale entre à partir de notions de convexité et de visibilité floue," in *Rencontres francophones sur la Logique Floue et ses Applications LFA'04*, Nantes, France, nov 2004, pp. 149–156.

[8] I. Bloch, O. Colliot, and R. M. Cesar, "Mathematical Modeling of the Relationship "Between" Based on Morphological Operators," in *ISMM 2005*, Paris, France, apr 2005, pp. 299–308.

[9] M. Aiello and J. van Benthem, "A Modal Walk Through Space," *Journal of Applied Non Classical Logics*, vol. 12, no. 3-4, pp. 319–364, 2002.

[10] A. Tarski, "What is Elementary Geometry?" in *The Axiomatic Method, with Special Reference to Geometry and Physics*, L. Henkin, P. Suppes, and A. Tarski, Eds. North-Holland, 1959, pp. 16–29.

[11] Y. Larvor, "Notion de méréogéométrie : description qualitative de propriétés géométriques, du mouvement et de la forme d'objets tridimensionnels," Ph.D. dissertation, Université Paul Sabatier, Toulouse, 2004.

[12] R. Krishnapuram, J. M. Keller, and Y. Ma, "Quantitative Analysis of Properties and Spatial Relations of Fuzzy Image Regions," *IEEE Transactions on Fuzzy Systems*, vol. 1, no. 3, pp. 222–233, 1993.

[13] P. Matsakis and S. Andréfouët, "The Fuzzy Line Between Among and Surround," in *FUZZ'IEEE 2002*, 2002, pp. 1596–1601.

[14] U. Bodenhofer, "Fuzzy "Between" Operators in the Framework of Fuzzy Orderings," in *Intelligent Systems for Information Processing: From Representation to Applications*, B. Bouchon-Meunier, L. Foulloy, and R. R. Yager, Eds. Elsevier, 2003, pp. 59–70.

[15] B. Landau and R. Jackendorff, ""What" and "Where" in Spatial Language and Spatial Cognition," *Behavioral and Brain Sciences*, vol. 16, pp. 217–265, 1993.

[16] J. Serra, *Image Analysis and Mathematical Morphology*. London: Academic Press, 1982.

[17] D. Dubois and H. Prade, *Fuzzy Sets and Systems: Theory and Applications*. New-York: Academic Press, 1980.

[18] G. Matheron, *Random Sets and Integral Geometry*. New-York: Wiley, 1975.
[19] I. Bloch, "Fuzzy Relative Position between Objects in Image Processing: a Morphological Approach," *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 21, no. 7, pp. 657-664, 1999.

[20] I. Bloch and H. Maître, "Fuzzy Mathematical Morphologies: A Comparative Study," *Pattern Recognition*, vol. 28, no. 9, pp. 1341-1387, 1995.

[21] K. Miyajima and A. Ralescu, "Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations," *Fuzzy Sets and Systems*, vol. 65, pp. 225-236, 1994.

[22] A. Rosenfeld and R. Klette, "Degree of Adjacency or Surroundness," *Pattern Recognition*, vol. 18, no. 2, pp. 169-177, 1985.

[23] D. Dubois, H. Prade, and C. Testemale, "Weighted Fuzzy Pattern Matching," *Fuzzy Sets and Systems*, vol. 28, pp. 313-331, 1988.

[24] B. Bouchon-Meunier, M. Rifqi, and S. Bothorel, "Towards General Measures of Comparison of Objects," *Fuzzy Sets and Systems*, vol. 84, no. 2, pp. 143-153, Sept. 1996.

[25] M. Rifqi, V. Berger, and B. Bouchon-Meunier, "Discrimination Power of Measures of Comparison," *Fuzzy Sets and Systems*, vol. 110, pp. 189-196, 2000.

[26] S. G. Waxman, *Correlative Neuroanatomy*, 24th ed. New York: McGraw-Hill, 2000.

[27] I. Bloch, "Fuzzy Spatial Relationships for Image Processing and Interpretation: A Review," *Image and Vision Computing*, vol. 23, no. 2, pp. 89-110, 2005.

[28] E. Bengoetxea, P. Larranaga, I. Bloch, and A. Perchant, "Solving Graph Matching with EDAs Using a Permutation-Based Representation," in *Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation*, P. Larranaga and J. A. Lozano, Eds. Boston, Dordrecht, London: Kluwer Academic Publisher, 2001, ch. 12, pp. 239-261.

[29] R. Cesar, E. Bengoetxea, I. Bloch, and P. Larranaga, "Inexact Graph Matching for Model-Based Recognition: Evaluation and Comparison of Optimization Algorithmss," *Pattern Recognition*, 2005.

[30] A. R. Shariff, M. Egenhofer, and D. Mark, "Natural-Language Spatial Relations Between Linear and Areal Objects: The Topology and Metric of English-Language Terms," *International Journal of Geographical Information Science*, vol. 12, no. 3, pp. 215-246, 1998.

[31] I. Bloch and A. Saffiotti, "On the Representation of Fuzzy Spatial Relations in Robot Maps," in *Intelligent Systems for Information Processing: From Representation to Applications*, B. Bouchon-Meunier, L. Foulloy, and R. R. Yager, Eds. Amsterdam: Elsevier, 2003, pp. 47-57.