=Paper=
{{Paper
|id=None
|storemode=property
|title=Spatial Relations for Positioning Objects in a Cabinet
|pdfUrl=https://ceur-ws.org/Vol-620/paper9.pdf
|volume=Vol-620
}}
==Spatial Relations for Positioning Objects in a Cabinet==
https://ceur-ws.org/Vol-620/paper9.pdf
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, Japan
ykurata@tmu.ac.jp
2
SFB-TR/8 Spatial Cognition SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
shi@informatik.uni-bremen.de
Abstract. This paper proposes a set of qualitative spatial relations designed for
supporting 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-topological
relations, directional relations, RCC-5, Allen’s interval relations
1 Introduction
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 order
that 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 application
of 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] and
that 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 with
each other). The resulting relations, called cabinet relations, are smoothly mapped to
natural language expressions for positioning objects (Section 3).
2 Formalization of Cabinet Relations
Allen [7] distinguished 13 relations between two intervals. Considering projections of
2D objects onto x- and y-axes and the interval relations between these projections on
each axis, Guesgen [8] distinguished 1313 relations between two 2D objects. His
theory, called Rectangular Algebra (RA), is used typically for capturing north-south-
east-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 xy-
plane. 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 1313 relations and
the new 66 relations are called RA relations and simplified RA relations,
respectively. For instance, the arrangement of two objects in Fig. 1a is represented by
a 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 xy-
plane, whose inner spaces (i.e., empty spaces enclosed by the projection), if they
exist, 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 is
represented as [separate, (proceeds, within)]. Since we have 3 enclosure relations and
66 simplified RA relations, there are 366 = 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, we
can 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 and
are difficult to characterize with simple expressions.
Allen’s Simplified RCC-5 Enclosure
Interval Interval Relations Relations
Relations Relations
y before proceeds
meets DR separate
metBy
after
succeeds
PO
starts
during within
finishes
PP enclosed
finishedBy
contains includes
startedBy
x PPI encloses
equal equal
overlaps
overlappedBy
overlap
EQ
(a) (b) (c)
Fig. 1. (a) Projection of two 2D objects in Rectangular Algebra, (b) simplification of Allen’s
interval relations, and (c) correspondences between RCC-5 relations and enclosure relation
[enclosed, [encloses, [separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate,
(within, (includes, (proceeds, (proceeds, (proceeds, (proceeds, (proceeds, (proceeds, (succeeds, (succeeds,
within)] includes)] proceeds)] succeeds] within)] includes)] equal)] overlap)] proceeds)] succeeds]
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)
[separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate,
(succeeds, (succeeds, (succeeds, (succeeds, (within, (within, (within, (within, (includes, (includes,
within)] includes)] equal)] overlap] proceeds)] succeeds] within)] overlaps)] proceeds)] succeeds]
(k) (l) (m) (n) (o) (p) (q) (r) (s) (t)
[separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate, [separate,
(includes, (includes, (equal, (equal, (overlap, (overlap, (overlap, (overlap, (overlap,
includes)] overlap)] proceeds)] succeeds] proceed)] succeed)] within)] includes)] overlap]
(u) (v) (w) (x) (y) (z) () () ()
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 can
assign [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 a
similar work, Shi and Kurata [9] mapped path-landmark relations to ontological
concepts in GUM [10]. Such generalization in our model is left for future work.
4 Conclusions and Future Work
This paper introduced a set of qualitative spatial relations designed for the positioning
of physical objects in a cabinet. These cabinet relations will work powerfully for
supporting human-machine communication in smart environments. At this moment,
the mapping between the cabinet relations and language expressions is empirical and
thus, we need certain justification of this mapping in future work. We may also need
certain fine-tuning of the model, considering the use of additional information such as
adjacency/distance between two objects. Lastly, another issue in our future agenda is
to 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. 165-
176. Morgan Kaufmann, San Francisco, CA, USA (1992)
4. Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships between
Regions, 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 Pairwise-
Consistency 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-Based
Spatial Models. In: Gottfried, B., Aghajan , H. (eds.): Behavioral Monitoring and
Interpretation, 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)