Spatial Relations for Positioning Objects in a Cabinet
Yohei Kurata1 and Hui Shi2
1

Department of Tourism Sciences, Tokyo Metropolitan University
1-1 Minami-Osawa, Hachioji, Tokyo 192-0397, Japanykurata@tmu.ac.jp
2SFB-TR/8 Spatial Cognition SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
shi@informatik.uni-bremen.deAbstract. This paper proposes a set of qualitative spatial relations designed forsupporting human-machine communication about objects’ locations in ‘planar’storage. Based on Allen’s interval relations and RCC-5 relations, our relations
are derived by combining directional and mereo-topological relations between
the projections of objects onto the 2D background. We identify 29 realizable
relations, which are then mapped to positioning expressions in English.
Keywords: spatial communication, relative locations, mereo-topologicalrelations, directional relations, RCC-5, Allen’s interval relations

1Introduction

When people describe the location of an object, they often use the relative position of
the object with respect to other objects which can be identified more easily. In orderthat people can communicate with smart environment via natural dialogue, computers
should be able to understand and generate such positioning expressions. To process
such positioning expressions, we may apply existing models of cardinal directional
relations (e.g., [1, 2]) or those of mereo-topological relations (e.g., [3, 4]). However,existing direction models distinguish too large number of relations—for instance,Papadias and Sellis [1], Cicerone and Felice [5], and Kurata and Shi [6] distinguish
169, 218, and 222 relations, respectively. In addition, we have to care the applicationof mereo-topological relations, because partonomy actually does not hold between
physical objects. This paper, therefore, proposes a task-oriented set of qualitative
spatial relations designed for supporting human-machine communication about object
locations in a cabinet, based on the model of cardinal directional relations in [1] andthat of mereo-topological relations in [3] (Section 2). Here a cabinet refers to any‘planar’ storage in which we can neglect the front-back arrangement of two different
objects. Moreover, objects are limited to physical objects in the real world (i.e., 3D
single-component spatial objects without cuts or spikes, which never intersect witheach other). The resulting relations, called cabinet relations, are smoothly mapped tonatural language expressions for positioning objects (Section 3).

2Formalization of Cabinet Relations

Allen [7] distinguished 13 relations between two intervals. Considering projections of2D objects onto x- and y-axes and the interval relations between these projections oneach axis, Guesgen [8] distinguished 1313 relations between two 2D objects. His
theory, called Rectangular Algebra (RA), is used typically for capturing north-southeast-west relationships, but here we use it for capturing above-below-left-right
relationships in a cabinet, setting x-, y-, and z-axes parallel to the cabinet’s width,height, and depth axes and considering the projections of 3D objects onto the xyplane. Moreover, we summarize the 13 interval relations into 6 relations (Fig. 1b),such that (i) each relation captures how the main bodies of two intervals overlap and(ii) converse of each relation is uniquely determined. The original 1313 relations andthe new 66 relations are called RA relations and simplified RA relations,respectively. For instance, the arrangement of two objects in Fig. 1a is represented bya RA relation (meets, starts) or by a simplified RA relation (proceeds, within).
RCC-5 relations [3] consist of five mereo-topological relations, namely DR(discrete), PO (partial overlap), PP (proper part), PPI (proper part inverse), and EQ(equal). In our cabinet scenario, we consider the projection of each object onto xyplane, whose inner spaces (i.e., empty spaces enclosed by the projection), if theyexist, are filled. Then, considering RCC-5 relations between the space-filled
projections, we distinguish three spatial relations between the original objects, namely
separate, enclosed, and encloses (Fig. 1c). These three relations capture whether one
object is enclosed by another object as seen from the front of the cabinet, thereby
called enclosure relations. Note that the projections never take PO and EQ relations,since in our scenario two objects never overlap nor have a front-back arrangement.
A cabinet relation between two objects is defined as a pair of their enclosure
relation and simplified RA relation. For instance, the cabinet relation in Fig. 1a isrepresented as [separate, (proceeds, within)]. Since we have 3 enclosure relations and66 simplified RA relations, there are 366 = 108 pairs of relations. However, only
29 pairs (Fig. 2) are realizable in the real world because (i) when the enclosure
relation is enclosed, the simplified RA relation must be (within, within) (note that(within, equal), (equal, within), and (equal, equal) are impossible because two objects
never overlap nor have a front-back arrangement), (ii) similarly, when the enclosure
relation is encloses, the simplified RA relation must be must be (includes, includes),and (iii) when the enclosure relation is separate, the simplified RA relation can be any
but neither (within, includes), (within, equal), (includes, within), (includes, equal),(equal, within), (equal, includes), (equal, equal), (equal, overlap), nor (overlap,equal), since these relations presume the overlap of two objects.

3

Mapping from Cabinet Relations to Positioning Expressions

When people explain the location of an object, they often rely on topological relations
between the object and other related object (especially if they intersect) or directional
relations between them (especially if they are located separately). Thus, the cabinet

relations, which capture both topological and directional characteristics of objects’arrangements, have certain correspondences to positioning expressions. Indeed, wecan map the cabinet relations to the following English expressions:
 [enclosed, (within, within)] A is in B (Fig. 2a) [encloses, (includes, includes)] A contains B (Fig. 2b)
 [separate, (proceeds, proceeds)]  A is at the lower left of B (Fig. 2c)
 [separate, (proceeds, within/includes/equal/overlap)]  A is at the left of B(Figs. 2e-h) [separate, (within/includes/equal/overlap, proceeds)]  A is below B (Figs. 2o, 2s,2w, and 2y) [separate, (within, within)]  A is surrounded by B (Fig. 2q)
 [separate, (includes, includes)]  A surrounds B (Fig. 2u)
Among 29 cabinet relations, 24 relations are assigned each to a certain expression.
Other 5 relations (Figs. 2r, 2v, 2-2) refer to rather complicated arrangements andare difficult to characterize with simple expressions.

yx(a)Allen’s
Interval
Relations

Simplified
IntervalRelations

before
meets
metBy
after

proceeds

RCC-5Relations

Enclosure
RelationsDRseparate

succeeds
PO

startsduringfinishes

withinfinishedBy
contains
startedBy

includes

equal

equal

overlaps
overlappedByoverlap

PP

enclosed

PPI

encloses



EQ

(b)

(c)

Fig. 1. (a) Projection of two 2D objects in Rectangular Algebra, (b) simplification of Allen’sinterval relations, and (c) correspondences between RCC-5 relations and enclosure relation[enclosed,(within,within)](a)[encloses,(includes,includes)](b)[separate,(proceeds,proceeds)](c)[separate,(proceeds,succeeds](d)[separate,(proceeds,within)](e)[separate,(proceeds,includes)](f)[separate,(proceeds,equal)](g)[separate,(proceeds,overlap)](h)[separate,(succeeds,proceeds)](i)[separate,(succeeds,succeeds](j)[separate,(succeeds,within)](k)[separate,(succeeds,includes)](l)[separate,(succeeds,equal)](m)[separate,(succeeds,overlap](n)[separate,(within,proceeds)](o)[separate,(within,succeeds](p)[separate,(within,within)](q)[separate,(within,overlaps)](r)[separate,(includes,proceeds)](s)[separate,(includes,succeeds](t)[separate,(includes,includes)](u)[separate,(includes,overlap)](v)[separate,(equal,proceeds)](w)[separate,(equal,succeeds](x)[separate,(overlap,proceed)](y)[separate,(overlap,succeed)](z)[separate,(overlap,within)]()[separate,(overlap,includes)]()[separate,(overlap,overlap]()Fig. 2. Twenty-nine cabinet relations

In actual dialogues, people use lots of expressions for describing locations. For
generality, we can consider an intermediate use of ontologies. For instance, we canassign [separate, (proceeds, within)] to an ontological concept, which is then mapped
to such expressions as “at the left of” in English and “-no hidari-ni” in Japanese. As asimilar work, Shi and Kurata [9] mapped path-landmark relations to ontologicalconcepts in GUM [10]. Such generalization in our model is left for future work.

4Conclusions and Future Work

This paper introduced a set of qualitative spatial relations designed for the positioningof physical objects in a cabinet. These cabinet relations will work powerfully forsupporting human-machine communication in smart environments. At this moment,
the mapping between the cabinet relations and language expressions is empirical andthus, we need certain justification of this mapping in future work. We may also needcertain fine-tuning of the model, considering the use of additional information such asadjacency/distance between two objects. Lastly, another issue in our future agenda isto implement the proposed idea and test its applicability in practical systems.

References
1. Papadias, D., Sellis, T.: Spatial Reasoning Using Symbolic Arrays. In: Frank, A., Campari,I., Formentini, U. (eds.): International Conference GIS (1992)
2. Goyal, R., Egenhofer, M.: Consistent Queries over Cardinal Directions across Different
Levels of Detail. In: Tjoa, A.M., Wagner, R., Al-Zobaidie, A. (eds.): 11th International
Workshop on Database and Expert Systems Applications, pp. 876-880 (2000)
3. Randell, D., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection. In:Nebel, B., Rich, C., Swarout, W. (eds.): Knowledge Representation and Reasoning, pp. 165176. Morgan Kaufmann, San Francisco, CA, USA (1992)
4. Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships betweenRegions, Lines and Points in Geographic Databases. In: Egenhofer, M., Herring, J., Smith,T., Park, K. (eds.): Ncgia Technical Reports 91-7. NCGIA, Santa Barbara, CA, USA (1991)
5. Cicerone, S., Felice, P.: Cardinal Directions between Spatial Objects: The PairwiseConsistency Problem. Information Science 164, 165-188 (2004)
6. Kurata, Y., Shi, H.: Toward Heterogeneous Cardinal Direction Calculus: . In: Mertsching,B., Hund, M., Aziz, M. (eds.): KI 2009, Lecture Notes in Computer Science, vol. 5803, pp.
452-459. Springer, Berlin/Heidelberg (2009)
7. Allen, J.: Maintaining Knowledge About Temporal Intervals. Communications of the ACM
26, 832-843 (1983)
8. Guesgen, H.: Spatial Reasoning Based on Allen's Temporal Logic. Technical report,
International Computer Science Institute (1989)
9. Shi, H., Kurata, Y.: Modeling Ontological Concepts of Motions with Two Projection-BasedSpatial Models. In: Gottfried, B., Aghajan , H. (eds.): Behavioral Monitoring andInterpretation, CEUR Workshop Proceedings, vol. 396, pp. 42-56. CEUR-WS.org (2008)10.Bateman, J., Hois, J., Ross, R., Farrar, S.: The Generalized Upper Model 3.0:
Documentation. Technical report, Collaborative Research Center for Spatial Cognition,
University of Bremen, Bremen, Germany (2006)