# Accelerating Spatio-Textual Queries with Learned Indices

Georgios Chatzigeorgakidis  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Kostas Patroumpas  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Dimitrios Skoutas  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>Spiros Athanasiou  IMSI, Athena R.C., Greece, email:
<EMAIL_ADDRESS>
###### Abstract

Efficiently computing spatio-textual queries has become increasingly important
in various applications that need to quickly retrieve geolocated entities
associated with textual information, such as in location-based services and
social networks. To accelerate such queries, several works have proposed
combining spatial and textual indices into hybrid index structures. Recently,
the novel idea of replacing traditional indices with ML models has attracted a
lot of attention. This includes works on learned spatial indices, where the
main challenge is to address the lack of a total ordering among objects in a
multidimensional space. In this work, we investigate how to extend this novel
type of index design to the case of spatio-textual data. We study different
design choices, based on either loose or tight coupling between the spatial
and textual part, as well as a hybrid index that combines a traditional and a
learned component. We also perform an experimental evaluation using several
real-world datasets to assess the potential benefits of using a learned index
for evaluating spatio-textual queries.

##  1 Introduction

The ubiquity of mobile devices, along with the proliferation of location-based
services and geosocial networks, has set off an unprecedented generation of
geotagged content. Efficiently querying and exploring spatio-textual data has
become increasingly important for various applications. Typically, query
execution must be very fast in order to enable interactive response times. To
address this need, several spatio-textual indices have been proposed over the
past decade. These are hybrid structures that combine a spatial index, such as
grid or R-tree, with a textual part, such as bitmap or inverted file, to allow
pruning the search space using both criteria.

Recently, the novel idea of thinking of indices as ML models has been proposed
[14]. According to it, an index can be formulated as a function $f$ that maps
an input key to a set of candidate objects (e.g., stored in a page on disk).
Naturally, this has attracted a lot of interest, as it opens up a
fundamentally new approach to the decades old problem of index design. Initial
works focused on designing learned indices for one-dimensional data,
leveraging the total ordering that exists among such objects.

Following this novel line of research, learned spatial indices have been
recently introduced [8, 18], extending the concept of learned indices from
1-dimensional data to two or more dimensions. Coping with more than one
dimension raises additional challenges, most importantly the lack of a total
ordering among objects. This is typically addressed by employing a space-
filling curve (SFC) to impose an ordering. However, the higher the
dimensionality, the less the accuracy of the resulting ordering, which also
means a higher error for the ML model that tries to learn the data
distribution based on it. Consequently, learned indices over multidimensional
data typically focus on a low number of dimensions.

Many spatial objects, such as Points of Interest or geotagged posts in social
media, are described by some textual information, which is or can be
represented as a set of keywords. Spatio-textual queries allow retrieving such
objects based on both spatial and textual criteria. Perhaps the two most
common types of such queries are _Boolean Window Queries_ (BWQ) and _Boolean
$k$-nearest neighbor Queries_ (B$k$Q). A BWQ retrieves objects located within
a rectangular spatial region that match all query keywords. A B$k$Q retrieves
the $k$ nearest objects to the query location that also match all given
keywords.

Figure 1 illustrates an example involving ten spatio-textual objects. Each
object $o_{i}$ is associated with a location and a set of keywords. Figure 1a
shows a BWQ $Q$ = ($\mathcal{W}$, $\langle pizza,bar\rangle$) to fetch all
objects inside a rectangular region $\mathcal{W}$ (shown in blue) that contain
the keywords _pizza_ and _bar_. Figure 1b shows a B$k$Q $Q$ = ($q$, $\langle
pizza,bar\rangle$, 1), which seeks the closest object to location $q$ tagged
with _pizza_ and _bar_. In both queries, the result is object $o_{2}$.

To accelerate such queries, several spatio-textual indices have been proposed
over the past decade. These are hybrid structures that combine a spatial
access method (e.g., grid, R-tree, quadtree, k-d tree) with a textual one
(e.g., bitmap, inverted file). Proposed variants differ on the type of spatial
and textual index they are based on, the type of coupling (i.e., loose vs
tight), and the type of queries they support. A typical example is the
IR2-Tree [11], which extends the widely used spatial index R∗-Tree [2] by
augmenting its nodes with textual information in the form of signatures [10].

A question that naturally arises is whether and how the evaluation of spatio-
textual queries can benefit from the use of ML models, as has been suggested
for one-dimensional or two-dimensional data. In this work, we investigate this
question by designing and evaluating hybrid spatio-textual indices that employ
a learned component. Although some suggestions for learned indices over
strings have been proposed, their benefits are not clear [14]. Thus, for the
learned part, we focus on the spatial component, in particular using the
current state-of-the-art learned spatial index RSMI [8]. RSMI has been shown
to be able to speed up spatial queries by an order of magnitude compared to
traditional query processing based on R-trees. Motivated by this, we
investigate how to extend RSMI towards a learned hybrid spatio-textual index,
and we study the implications of the learned part and the textual part to the
performance of the resulting index structure. To the best of our knowledge,
this is the first work to employ learned indices over spatio-textual data.

(a) A Boolean Window Query.

(b) A Boolean $k$NN Query.

Figure 1: Boolean spatio-textual queries.

The contributions of our work can be summarized as follows:

  * •

We derive a baseline learned spatio-textual index by loosely coupling RSMI
with an inverted index to enable textual pruning on the leaf nodes.

  * •

We suggest a tightly coupled index that augments RSMI by associating both
internal and leaf models with textual information in the form of bitmaps.

  * •

We design a hybrid index that combines both a learned part (RSMI) and a
traditional part (IR2-Tree).

  * •

We present an alternative partitioning strategy that takes into account the
textual information besides the spatial one.

  * •

We empirically evaluate the performance of proposed learned index variants
against real-world datasets and also compare them with traditional indices to
identify potential benefits.

The remainder of this paper is organized as follows: Section 2 reviews related
work. In Section 3 we formulate the problem. The methods under examination are
presented in Section 4, followed by an extensive experimental evaluation in
Section 5. Finally, Section 6 concludes the paper.

##  2 Background and Related Work

In this section, we briefly review related work on spatio-textual indices and
learned indices.

Spatio-Textual Indices. Spatio-textual indices are hybrid index structures
that combine a spatial and a textual component so that pruning on both
criteria can be performed during query processing. Several such indices have
been proposed in the literature (see surveys in [7, 4, 6]). The spatial
indexing part can be based on R-trees (e.g., IF-R∗-Tree and R∗-Tree-IF [27],
KR∗-Tree [12], IR2-Tree [11], IR-Tree [23], SKI [3], S2I [20], WIBR-Tree
[24]), Quad-tree (e.g., I3 [26], ILQ [25]), grid (e.g., ST and TS [21], SKIF
[13]) or Space-filling curve (e.g., SF2I [5], SFC-QUAD [7]). For the textual
part, typically a signature (e.g., a bitmap) or an inverted file is used to
indicate the presence of keywords in the objects being indexed. In our
approach, we employ the IR2-tree [11], which is a representative spatio-
textual index that can answer both Boolean window (BWQ) and $k$NN (B$k$Q)
queries. It is based on the R∗-Tree [2], where each node is enhanced with a
signature indicating which keywords exist in the objects corresponding to that
node.

Learned Indices. Recently, the novel idea of learned indices has been proposed
[14]. Such indices rely on ML models to predict the physical location of an
object in memory or on disk. The key idea is to use a machine learning model,
which may range from a deep neural network to a simple regression model, to
learn the cumulative distribution function (CDF) of object keys in a sorted
array. Thus, most of these indices are proposed for 1-dimensional data, where
a natural ordering of the objects exists [16].

Nevertheless, several multidimensional learned indices have also been proposed
to handle data of two or more dimensions, overcoming the lack of an inherent
total ordering [1, 17, 9]. These often rely on a space-filling curve to map
the data to a single dimension, so that a total ordering can be imposed. For
instance, the $z$-order model (ZM) index [22] combines the $z$-order space-
filling curve with a model to learn the distribution of the data. LISA [15] is
a learned index structure for spatial data, which consists of a function that
maps spatial keys into 1-D values, a function that partitions the mapped
space, and a series of local models that organize partitions into pages. In
this paper, we use the Recursive Spatial Model Index (RSMI) [18] as the basis
for designing a learned spatio-textual index, hence we describe RSMI in more
detail below.

RSMI [18] relies on a $z$-order space-filling curve to map the 2-D spatial
points to a single dimension, where the resulting CDF of the data is learned.
To avoid large gaps in this CDF, it first transforms the original point
coordinates to a rank space, following the same idea that has been proposed as
an R-Tree packing strategy [19]. Hence, the $z$-order curve is applied to the
rank space instead of the original one. Then, RSMI employs a feed forward
neural network to learn the resulting CDF. The maximum error $\epsilon$ of the
model is also calculated and is used at query time to define a search range
around the predicted location so that results are not missed.

When indexing a large collection of spatial objects, it is often not feasible
for a single model to learn the entire CDF with sufficient accuracy. To
overcome this, RSMI recursively partitions the space and creates a hierarchy
of models, so that each model only learns a fraction of the entire CDF. The
partitioning is a non-regular grid that follows the data distribution,
assuming a maximum allowed partition size $S$. At each level of the hierarchy,
the partitions are ordered based on a $z$-order curve calculated over their
centroids. For each partition, a separate model is trained. At query time,
each model predicts which of its children nodes should be visited next, thus
traversing the hierarchy from the root to the leaf nodes. At the bottom level,
each leaf model predicts a range of blocks to be searched, also taking into
account the model error $\epsilon$.

##  3 Problem Definition

In this section, we introduce the main definitions and notions used throughout
the paper. The basic notations are listed in Table 1.

Assume a collection $\mathcal{D}$ of spatio-textual objects, which are
formally defined as follows.

######  Definition 1 (Spatio-Textual Object)

A spatio-textual object $o$ is represented by a pair $(o.s,o.T)$, where $o.s$
is a point in a 2-dimensional Euclidean space and $o.T$ is a set of keywords.

We consider the following two basic types of spatio-textual queries, which are
commonly studied in the literature [7, 4, 6].

######  Definition 2 (Boolean Window Query (BWQ))

A boolean window spatio-textual query is defined as
$BWQ=(\mathcal{W},\mathcal{T})$, where $\mathcal{W}$ is a rectangular spatial
area (window), and $\mathcal{T}$ is a set of keywords. Given a collection
$\mathcal{D}$ of spatio-textual objects, the result set $R$ of $BWQ$ comprises
all objects that lie within $\mathcal{W}$ and contain all the keywords in
$\mathcal{T}$, i.e.,
$R=\\{o\in\mathcal{D}\,|\,within(o.s,\mathcal{W})\wedge\mathcal{T}\subseteq
o.T\\}$.

If the sequel, for purposes of presentation, we interchangeably denote a
spatial window $\mathcal{W}$ with the pair $(q_{l},q_{h})$ of its lower left
and upper right corners.

######  Definition 3 (Boolean $k$NN Query (B$k$Q))

A boolean $k$NN spatio-textual query is defined as $BkQ=(q,\mathcal{T},k)$,
where $q$ is a point location, $\mathcal{T}$ is a set of keywords, and $k$ is
the number of objects to be returned. Given a collection $\mathcal{D}$ of
spatio-textual objects, the result set $R$ of $BkQ$ comprises $k$ objects that
contain all the keywords in $\mathcal{T}$ and are most closely located to $q$,
i.e., (i) $R\subseteq\mathcal{D}$, (ii) $|R|=k$, (iii) $\forall o\in
R,\mathcal{T}\subseteq o.T$, (iv) $\forall o\not\in R,\exists o^{\prime}\in
R\,|\,d(q.o.s)\geq d(q,o^{\prime}.s)$, where $d$ refers to Euclidean distance.

Our goal in this paper is to design learned spatio-textual indices that can
accelerate the evaluation of $BWQ$ and $BkQ$ queries compared to traditional
indexing schemes.

Table 1: Basic notations $\mathcal{D}$ | dataset of spatio-textual objects
---|---
$o.s$ | location of spatio-textual object $o\in\mathcal{D}$
$o.T$ | set of keywords associated to spatio-textual object $o\in\mathcal{D}$
$\mathcal{T}$ | set of query keywords
$\mathcal{W}$ | spatial query rectangle (window) in BWQ
$q_{l},q_{h}$ | lower left and upper right corner of window $\mathcal{W}$ in BWQ
$mbr$ | Minimum Bounding Rectangle over the input location(s)
$k$ | number of nearest qualifying objects to retrieve in B$k$Q
$\ell$ | side length of window used in evaluating B$k$Q
$R$ | set of query results
$S$ | maximum size (number of contained objects) per partition
$B$ | block of data in a leaf node of RSMI
$\epsilon$ | maximum error of the model

##  4 Index Design

Inspired by traditional spatio-textual indices, which combine a spatial part
and a textual part, our approach is to enhance a learned spatial index with
keyword information. As a basis, we use RSMI [18] (see Section 2). We first
provide an overview of our approach, and then we describe three indices based
on different design choices, namely a loosely coupled, a tightly coupled, and
a hybrid scheme.

###  4.1 Overview

1

2 Procedure  _BWQTraversal $(N,Q,R)$_

3

4 $M\leftarrow N.model$

5 if  _$N$ is $leaf$_ then

6 foreach  _$B\in[M(Q.q_{l})-M.\epsilon_{l},M(Q.q_{h})+M.\epsilon_{h}]$_ do

7 if  _$intersects(B.mbr,Q.\mathcal{W})$_ then

8 $R\leftarrow CheckLeafNode(B,Q,R)$

9

10

11 else

12 foreach  _node $N^{\prime}\in[M(Q.q_{l}),M(Q.q_{h})]$_ do

13 if  _$CheckInnerNode(N^{\prime},Q)$_ then

14 BWQTraversal$(N^{\prime},Q,R)$

15

16

17

18 return $R$

19

Algorithm 1 Index Traversal

The backbone of our proposed indices is RSMI, which hierarchically partitions
the space and builds a respective hierarchy of ML models. At each level,
partitions are created. Each partition is assigned an id based on $z$-order,
and is associated with a model that directs the search to its children. An
illustrative example is depicted in Figure 2 (the bitmaps next to each model
$M_{i,j}$ are explained later). There are four partitions at the top level.
The root model is $M_{0,0}$, which points to the four models
$M_{1,0},...,M_{1,3}$ at the next level. Models $M_{2,0},...,M_{2,3}$ are leaf
models. Each model is also associated with the MBR of the respective
partition. This is used during query evaluation to avoid false positives that
may occur due to prediction errors by the models, i.e., to prune subtrees
whose MBR does not intersect with the specified query window.

To answer a Boolean Window Query $Q$, we traverse the index as in Algorithm 1.
Procedure _BWQTraversal_ is recursive, starting from the root node. Assume the
model $M$ of a visited node $N$. Given the lower left and upper right corners
($q_{l}$ , $q_{h}$) of the query window $\mathcal{W}$, model $M$ predicts the
range of the children nodes (or blocks, in the case of leaf models) across the
$z$-order curve that should be checked. For inner nodes (Lines 7-10), process
_CheckInnerNode_ takes into account any available information (MBR, bitmaps)
per node and determines whether to recursively descend its subtree, as
detailed later for each of the proposed schemes. To reduce the number of total
checks, note that RSMI does not consider the model errors at inner nodes. For
each block in a visited leaf node (Lines 3-6), if its MBR intersects the query
window, we proceed to check its contents according to the keyword indexing
scheme applied by each of our proposed methods. At the leaf level, the model
errors $\epsilon_{l},\epsilon_{h}$ are taken into account. The process
terminates once there are no more leaves to search and the set $R$ of results
is returned.

To answer a Boolean $k$NN Query (B$k$Q), we follow the same approach as in
RSMI. This involves executing a series of BWQ with increasingly larger window
size until at least $k$ objects are found. As a heuristic, the side length of
the initial window is set to $\ell=\sqrt{k/|\mathcal{D}|}$ (assuming that
original coordinates have been normalized to a unit space). Then, this length
is increased by a factor of 2 at each subsequent window query. In all proposed
indexing schemes, the applied query is a $BWQ$ query, i.e., only objects
containing the query keywords are qualifying for the top-$k$ results.

###  4.2 Loosely Coupled Scheme

This approach loosely combines a spatial and a textual indexing component. Its
advantage is simplicity and modularity, allowing existing implementations to
be reused. The downside is lower pruning capacity, since each component only
allows pruning with the respective criterion.

Index Structure. In this scheme, we combine RSMI with inverted files (IF)
attached to its leaf nodes. We refer to the resulting index as RSMI-IF. Given
a collection $\mathcal{D}$ of spatio-textual objects, RSMI is first built
based on their point locations. Recall that each leaf model points to a series
of blocks. RSMI-IF constructs an inverted index for each such block. Hence, at
query time, instead of checking all objects in each block, only those that
contain a query keyword can be accessed. Essentially, this is analogous to the
R∗-Tree-IF [27] spatio-textual index, where we use the learned spatial index
RSMI in place of the R∗-Tree.

Figure 2: The RSMI-BM spatio-textual index.

Query Processing. Following the loosely-coupled nature of the RSMI-IF index,
evaluation of a Boolean window query $BWQ=(\mathcal{W},\mathcal{T})$ comprises
two main stages. The first stage is essentially a spatial window query over
RSMI using the specified window $\mathcal{W}$. Inner nodes with MBRs not
intersecting $\mathcal{W}$ can be safely pruned (Algorithm 2, process
_CheckInnerNode_). However, instead of returning all objects within
$\mathcal{W}$, the process terminates a step earlier, specifically as soon as
the leaf models identify the candidate blocks where these points may be
contained. The second stage is handled by process _CheckLeafNode_ in Algorithm
2. For each such block in a leaf, its associated inverted file $IF$ is used to
retrieve the inverted lists of objects containing the query keywords. The
intersection of these lists produces a set of candidate objects that contain
all the query keywords. Finally, the location of each candidate object $o$ is
checked to verify that it is within $\mathcal{W}$. This processing method is
also employed to answer B$k$Q queries, as noted in Section 4.1.

1

2 Procedure  _CheckInnerNode $(N,Q)$_

3 if  _intersects( $N.mbr,Q.\mathcal{W}$)_ then return true

4 else return false

5

6

7

8 Procedure  _CheckLeafNode $(B,Q,R)$_

9 $cands\leftarrow search(B.IF,Q.\mathcal{T})$

10 foreach  _object $o\in cands$_ do

11 if  _within( $o.s,Q.\mathcal{W}$)_ then $R\leftarrow R\cup\\{o\\}$

12

13 return $R$

14

Algorithm 2 RSMI-IF query processing

###  4.3 Tightly Coupled Scheme

In this setting, the proposed index tightly combines a spatial and a textual
component, so that pruning with both criteria can be performed throughout all
levels of the hierarchy. Next, we introduce RSMI-BM, an index that augments
RSMI with the use of bitmaps to encode the presence of keywords in the
objects.

Index Structure. RSMI-BM follows the same base structure as RSMI, i.e., it
consists of a hierarchy of models. However, each model is now additionally
associated with a bitmap, where each bit corresponds to a keyword. The bit
corresponding to keyword $t$ is set to 1, if there exists an object in the
subtree of that model that contains $t$, or 0 otherwise. To construct the
index, the RSMI index is built first, based on the locations of the objects.
Then, its nodes are traversed bottom-up, keeping track of the encountered
keywords, which are used to set the respective bitmap for each model. An RSMI-
BM index with three levels is illustrated in Figure 2, corresponding to the
collection of spatio-textual objects depicted in Figure 1.

Query Processing. Evaluating a Boolean window query BWQ again follows the
paradigm shown in Algorithm 1. The model hierarchy of the RSMI component is
traversed from the root to the leaves, visiting the nodes indicated by each
model encountered at each level. Checking the given spatial window
$\mathcal{W}$ against node MBRs is also used for pruning, as in RSMI-IF. The
difference now is that before using a model to make a prediction, the
algorithm also checks whether the bitmap $bm$ associated to the corresponding
leaf or inner node $N$ (Algorithm 3) matches the bitmap of the query keywords.
If $bm$ has a bit set to 0 for any of the query keywords, then that model is
skipped, i.e., its corresponding subtree is pruned.

1

2 Procedure  _CheckInnerNode $(N,Q)$_

3 if  _intersects( $N.mbr,Q.\mathcal{W}$) $\wedge$
BitmapMatch($N.bm,bm(Q.\mathcal{T})$)_ then return true

4 else return false

5

6

7 Procedure  _CheckLeafNode $(B,Q,R)$_

8 foreach  _object $o\in B$_ do

9 if  _within( $o.s,Q.\mathcal{W}$) $\wedge$
BitmapMatch($bm(o.T),bm(Q.\mathcal{T})$)_ then $R\leftarrow R\cup\\{o\\}$

10

11 return $R$

12

Algorithm 3 RSMI-BM query processing

(a) Partitioning on $x$-axis.

(b) Partitioning on $y$-axis.

(c) Final partitioning.

Figure 3: The alternative partitioning method.

Alternative Partitioning. Recall that RSMI partitions the data based on a non-
regular grid adapted to the spatial distribution of the objects. This involves
interchangeably splitting the $x$ and $y$ axes into equi-sized partitions.
Having balanced partitions facilitates model training. Nevertheless, RSMI
completely disregards the presence of keywords in the objects. Next, we
describe a modified partitioning scheme that also takes the keywords into
consideration. The goal is to produce partitions with more diverse bitmaps,
which will increase the pruning capacity based on the textual information. We
use the Hamming distance $H$ to measure the difference between two bitmaps.
Let $bm_{q}$ denote the bitmap corresponding to the set of query keywords
$Q.\mathcal{T}$, and $bm_{i}$, $bm_{j}$ the bitmaps of two nodes $N_{i}$,
$N_{j}$, respectively, at a given level of the hierarchy. Intuitively, the
higher the distance $H(bm_{i},bm_{j})$, the less likely it is that both
$bm_{i}$ and $bm_{j}$ match with $bm_{q}$, i.e., that both subtrees rooted at
$N_{i}$ and $N_{j}$ need to be traversed.

Based on this, our modified partitioning scheme works as follows. At each
iteration, we perform two splits, one on the $x$ axis and another one on the
$y$ axis, each producing two equi-sized partitions. We choose the order of
these splits based on the above criterion. Let $bm^{x}_{1}$ and $bm^{x}_{2}$
(resp., $bm^{y}_{1}$ and $bm^{y}_{2}$) denote the bitmaps of the resulting
partitions by splitting on the $x$ (resp., $y$) axis. If
$H(bm^{x}_{1},bm^{x}_{2})>H(bm^{y}_{1},bm^{y}_{2})$, we first split on the $x$
axis, otherwise we first split on $y$. The process is repeated recursively
until no partition exceeds the maximum allowed size $S$.

Figure 3 illustrates an example. Performing a split on the $x$ axis (Figure
3a) yields two bitmaps with Hamming distance 2. Instead, a split on the $y$
axis (Figure 3b) yields two bitmaps with Hamming distance 5. Thus, we choose
to split on the $y$ axis first, resulting on the partitions shown in Figure
3c.

###  4.4 Hybrid Scheme

In the context of learned indices, hybrid index designs have been suggested,
which may employ different types of models, or even non-learned indices, at
different levels of the hierarchy [14]. Following this idea, we present the
RSMI-BM-IR2 index, which combines a learned and a non-learned part.

Index Structure. In RSMI-BM-IR2, the top levels in the hierarchy consist of an
RSMI-BM index, as described in the previous section. The difference is that
here we set a much larger maximum allowed partition size $S$, which reduces
the depth of the model hierarchy and increases the number of objects contained
in each leaf node. Then, for each leaf node of RSMI-BM, we index the set of
its objects using an IR2-tree, which is a traditional spatio-textual index
(see Section 2). The structure of RSMI-BM-IR2 is illustrated in Figure 4.
Starting from the root, there is first a hierarchy of models, with 3 levels in
this example. Then, each leaf model (e.g., $M_{2,3}$) points to a series of
IR2-trees (i.e., $IR_{2,2,0}$, $IR_{2,2,1}$, etc.). Each of these is again
associated with a respective bitmap, which is checked before starting a tree
traversal.

Figure 4: The hybrid RSMI-BM-IR2 spatio-textual index.

Query Processing. Processing a BWQ using RSMI-BM-IR2 proceeds similarly to the
RSMI-BM until a leaf is reached. Then, as shown in Algorithm 4, the same
search query is issued against the IR2-tree attached under each such leaf in
RSMI-BM. The union of these search results provides the final answer.

1

2 Procedure  _CheckLeafNode $(B,Q,R)$_

3 $R\leftarrow search(B.IR^{2},Q)$

4 return $R$

5

Algorithm 4 RSMI-BM-IR2 query processing

##  5 Experimental Evaluation

In this section, we present an experimental evaluation using four real-world
datasets. We compare the different index variants described in Section 4, as
well as two traditional spatio-textual indices.

###  5.1 Experimental Setup

####  5.1.1 Datasets

We use four real-world datasets with different characteristics, as shown in
Table 2. The datasets have been preprocessed to only keep frequent keywords.

Table 2: Dataset characteristics. Dataset | Objects | Area Size | Distinct kwds | Kwds per obj.
---|---|---|---|---
Foursquare | 94,158 | 5,053,518 $mi^{2}$ | 412 | 5.63
OSM USA | 1,228,616 | 3,975,720 $mi^{2}$ | 204 | 1.49
OSM Europe | 3,451,588 | 6,683,510 $mi^{2}$ | 255 | 1.71
Twitter | 10,000,000 | 6,301,967 $mi^{2}$ | 313 | 2.19

_Foursquare_. This contains 94,158 Points of Interest (POIs) extracted from
Foursquare in the United
States111https://star.cs.ucr.edu/?yin/foursquare#center=39.00,-98.00&zoom=4,
with a total of 412 distinct keywords and an average of 5.63 keywords per
object.

_OSM USA_. This contains 1,228,616 spatial entities extracted from
OpenStreetMap (OSM) across the United States222
http://download.slipo.eu/results/osm-to-csv/all/north-america/us/. Each entity
is represented by its centroid (lon/lat coordinates). There are 204 distinct
keywords, with an average of 1.49 keywords per object.

_OSM Europe_. This dataset contains 3,451,588 spatial entities extracted from
OSM across Europe333http://download.slipo.eu/results/osm-to-csv/all/europe/.
Each entity is again represented by its centroid (lon/lat coordinates). There
are 255 distinct keywords, with an average of 1.71 keywords per entity.

_Twitter_. This contains 10 million geo-tagged tweets in the United
States444https://star.cs.ucr.edu/?Tweets#center=39.00,-98.00&zoom=4. There are
313 distinct keywords, with an average of 2.19 keywords per tweet.

####  5.1.2 Competitors

We compare the indexing schemes listed below.

_R ∗-Tree-IF_. A traditional spatio-textual index [27] that loosely combines
the R∗-tree with inverted files.

_IR 2-tree_. A traditional spatio-textual index [11] that tightly combines the
R∗-tree with signatures encoding the textual information. As signatures, we
use bitmaps with length equal to the number of distinct keywords per dataset.

_RSMI-IF_. The index presented in Section 4.2, which loosely combines RSMI
with inverted files.

_RSMI-BM_. The index presented in Section 4.3, which tightly combines RSMI
with bitmaps.

_RSMI-BM ∗_. The variant of RSMI-BM using the modified partitioning strategy
in Section 4.3.

_RSMI-BM-IR 2_. The index presented in Section 4.4, which combines RSMI-BM
with the non-learned IR2-tree.

All methods were implemented in GNU C++. All indices are held in memory. The
experiments were executed using gcc version 9.4.0 on a server with AMD Ryzen
Threadripper 3960X 24-Core processor and 256 GB RAM running Ubuntu 20.04.1
LTS.

####  5.1.3 Index Parameters

We conducted some preliminary tuning tests, and we have set the parameters of
each index as described next. The block size for RSMI-BM and RSMI-BM∗ was set
to $|B|=100$. Similarly, for the IR2-Tree, we set the minimum and maximum node
capacity to $m=50$ and $M=100$, respectively. For both R∗-Tree-IF and RSMI-IF,
we set these values to $|B|=1000$, $m=500$, and $M=1000$, to benefit from the
inverted indices in the leaves. For RSMI-BM-IR2, the block size was set to
$|B|=1000$, while using $m=10$ and $M=20$ for the IR2-trees constructed in the
leaves in order to increase the tree height. For RSMI-IF, RSMI-BM, RSMI-BM∗
and RSMI-BM-IR2 the maximum partition size was set to
$S=0.1\cdot|\mathcal{D}|$ for each dataset.

The ML models used in the RSMI-based indices are multi-layer perceptrons (MLP)
and their configuration is the same as in the original RSMI paper [18].
Specifically, the hidden layer size is set to the sum of the number of
dimensions and the number of output classes divided by two. For the hidden
layer, we use the sigmoid activation function. The models are trained level by
level, starting from the root, with the learning rate set to 0.01 and the
number of epochs to 500.

Table 3: Query parameters and their ranges. Parameter | Value
---|---
Window side length $\ell$ in BWQ queries | 0.01, 0.05, 0.1, 0.15, 0.2
Count $k$ of results in B$k$Q queries | 5, 10, 20, 50, 100
Number of query keywords $\mathcal{T}$ | 1, 2, 3, 4, 5

####  5.1.4 Query Workload

The query parameters are listed in Table 3, with default values shown in bold.
Each experiment is performed using a randomly selected workload of 1,000
objects as queries from each dataset, reporting the average response time. For
BWQ, we construct the query windows as squares having as center the query
location and specifying a varying side length $\ell$ as listed in Table 3. The
window side length $\ell$ is expressed as a percentage of the whole dataset
area. For tests involving a varying number of keywords $\mathcal{T}$, we
isolate the spatio-textual objects containing at least $|\mathcal{T}|$
keywords in each case, and randomly select 1,000 objects as the respective
query workload. To assess the quality of query results, we measure the average
recall over the query workload. For B$k$Q queries, we also calculate the
distance of the returned $k$NN from the query point and we measure its
deviation (%) from the distance of the exact $k$NN.

###  5.2 Index Construction

(a)

(a) Index build time.

(b) Index size.

Figure 5: Index build time and size.

Figure 5 depicts the build time and memory footprint required by each index
per dataset. It is noticeable that traditional indices (i.e., IR2-Tree and
R*-Tree-IF) incur a significantly less construction cost, built almost an
order of magnitude faster compared to the RSMI-based indices (Figure 5a). This
is expected, since all proposed RSMI-based indices must undergo multiple
expensive multi-epoch training tasks during construction; the more the models
are trained, the more the construction cost.

Besides, traditional indices consume less memory (Figure 5b). The increased
memory footprint of the RSMI-based indices should be attributed to the ML
models that must also be kept in memory and the large number of bitmaps stored
per leaf node and block along with the raw data (point coordinates and
keywords). Furthermore, the RSMI-based indices by default must keep for each
point the mapped coordinates to the rank space and the space-filling curve
value, thus requiring extra memory.

###  5.3 BWQ Performance Results

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 6: BWQ response time with varying window size.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 7: Recall of BWQ results for varying window sizes.

##### Varying Window Size

Figure 6 illustrates performance of BWQ for various window sizes.
Unsurprisingly, RSMI-IF is significantly slow, an order of magnitude worse
than its competitors, as it does not take into account the query keywords
while traversing the RSMI. It also has to perform multiple additional searches
in inverted files of the leaves followed by expensive set intersection
operations. The fastest scheme in all cases is RSMI-BM-IR2, which manages to
cope well, taking advantage of RSMI’s quick node traversal. IR2-Tree comes in
a close second in most cases, while all other indices are less efficient.
Interestingly, though, the R*-Tree-IF manages to outperform IR2-Tree for
larger window sizes against the Twitter dataset, despite being the slowest in
all other cases. This is possibly due to the larger node capacities along with
efficient pruning on the spatial domain, requiring only few interactions with
the inverted files at the leaf level.

The corresponding recall results are shown in Figure 7. Noticeably, recall
values for the RSMI-based methods on OSM data are all close to 1. Performance
of RSMI-BM∗ against the Foursquare data is poor, especially for smaller window
sizes, possibly because the ML models are struggling to learn the calculated
partitions. Interestingly, for the Twitter dataset, RSMI-BM achieves the
highest recall (close to 1) for all window sizes, possibly due to a
partitioning that was easier to learn. In general, we noticed that RSMI-based
indices with multiple levels tend to have many false negatives, since inner
node traversal does not take into account the model errors.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 8: BWQ response time with varying number of query keywords
$\mathcal{T}$.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 9: Recall of BWQ results for varying number of query keywords
$\mathcal{T}$.

##### Varying Number of Query Keywords

Figure 8 plots BWQ response times for a varying number $|\mathcal{T}|$ of
keywords per query. As previously noted, RSMI-IF is the slowest scheme. Since
objects with many keywords are rather rare (see Table 2), increasing the
number of keywords decreases the selectivity in all methods and performance is
either improved, or remains stable. In general, RSMI-BM-IR2 is again the
fastest; however, it is outperformed by RSMI-BM and RSMI-BM∗ for
$|\mathcal{T}|>3$, except for the small Foursquare dataset.

Regarding accuracy, note that recall is almost equal to 1 in most cases
(Figure 9). The only exception is RSMI-BM∗, which offers less accurate results
in some settings over the Foursquare and Twitter datasets, possibly because it
is harder to learn the derived partitions. Nevertheless, for queries with
$|\mathcal{T}|>4$ keywords over the Twitter dataset, the RSMI-BM∗ approach is
both the fastest and achieves a very high recall close to 1.

###  5.4 B$k$Q Performance Results

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 10: B$k$Q response time for varying $k$.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 11: Distance deviation of $k$-th NN in B$k$Q results for varying $k$.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 12: Recall of B$k$Q results for varying $k$.

##### Varying $k$

Figure 10 illustrates B$k$Q performance for a varying number $k$ of returned
results. Note that R∗-Tree-IF does not support such queries, hence it is not
included in this experiment. In contrast to BWQ performance results, the RSMI-
BM-IR2 approach is now the fastest only over the Foursquare and Twitter
datasets. For the rather small Foursquare dataset, the IR2-Tree scales better
for larger $k$, overtaking RSMI-BM-IR2. However, this is not the case over the
OSM datasets, where RSMI-BM and RSMI-BM∗ are almost on par (RSMI-BM∗ is
slightly faster), and generally faster than their competitors. While RSMI-BM-
IR2 is faster than IR2-Tree over the OSM Europe data, it struggles over OSM
USA data. The most interesting observation, though, concerns the larger
Twitter dataset, where IR2-Tree is significantly slower than the RSMI-based
indices. In this case, these latter learned schemes manage to detect the
requested $k$ nearest neighbors without issuing many window queries.

Figure 11 depicts the distance deviation between exact and RSMI-based $k$-th
nearest neighbors from the query point. Intuitively, this indicates the
quality of the RSMI-based results by considering the distance difference from
the farthest result. The loosely coupled RSMI-IF has poor accuracy, with
distance deviations reaching 75% in some cases. RSMI-BM∗ and RSMI-BM manage to
cope reasonably well, with a deviation of 20-40% in most cases. The best
performance is achieved by RSMI-BM-IR2, which yields an almost zero deviation
in most cases. This observation is also confirmed by the corresponding recall
values (Figure 12), with RSMI-BM-IR2 achieving a recall close to 1 in all
cases. Now, the superiority of RSMI-BM-IR2 is more evident; by taking
advantage of the fast RSMI-based inner node traversal and the accurate query
results of IR2-Tree in the leaves, it manages to achieve very low response
times in all cases, while maintaining a recall approximately equal to 1.

##### Varying Number of Query Keywords

Figure 13 illustrates B$k$Q performance for a varying number $|\mathcal{T}|$
of keywords per query. Increasing the number of keywords does not improve the
response time, since queries with more keywords are rather rare and more
searches are needed to fetch all qualifying $k$ neighbors. RSMI-BM-IR2 is
again the fastest in most cases. Interestingly, IR2-Tree does not scale well;
it is the fastest approach for $|\mathcal{T}|=1$ (or |$\mathcal{T}|=2$ over
the Foursquare dataset), but it gets significantly slower with more query
keywords. RSMI-based indices in general seem to cope well for any number of
query keywords.

Figure 14 shows the corresponding distance deviation of the retrieved $k$-th
nearest neighbor from the exact one. As before, RSMI-BM-IR2 manages to achieve
a deviation close to 0%. RSMI-BM and RSMI-BM∗ have a similar behavior in most
cases, except for the Foursquare dataset, where RSMI-BM∗ yields slightly
better results. The most interesting findings concern the Twitter dataset, and
are also confirmed by the corresponding recall results in Figure 15. Observe
that, increasing the number of query keywords tends to improve the recall (and
reduce the deviation as shown in Figure 14d) in all RSMI-based indices over
Twitter data. This is possibly because fewer objects have many keywords, which
can result in less false positives. The only differentiation is RSMI-BM-IR2,
yielding recall values very close to 1 in all cases. Since RSMI-based
processing of B$k$Q employs windows (i.e., BWQ) of side length $\ell$ (instead
of circles of radius $\ell$), there is an interesting observation. The result
set may contain objects that may be at a distance up to
$\frac{\ell\sqrt{2}}{2}$ from the query point (close to a corner of the
window). However, there may still exist objects with a smaller distance that
may be outside of the applied window; these will be missed. This explains the
lower recall rates for B$k$Q queries using RSMI-based schemes.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 13: B$k$Q response time with varying number of query keywords
$\mathcal{T}$.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 14: Distance deviation of $k$-th NN in B$k$Q results for varying number
of query keywords $\mathcal{T}$.

(a)

(a) Foursquare Dataset

(b) OSM USA Dataset

(c) OSM Europe Dataset

(d) Twitter Dataset

Figure 15: Recall of B$k$Q results for varying number of query keywords
$\mathcal{T}$.

##  6 Conclusions

In this paper, we examined the case of answering Boolean spatio-textual
queries by extending RSMI, a state-of-the-art spatial learned index. We
presented three different indexing schemes: a loosely coupled RSMI with
inverted indices, a tightly coupled scheme that augments RSMI nodes with
keyword bitmaps, and a hybrid approach that attaches a traditional state-of-
the-art spatio-textual index under each leaf node of RSMI. We also examined an
alternative partitioning strategy that takes the textual part of the objects
under consideration. Our extensive experimental evaluation indicated that, in
general, the hybrid approach is faster and yields very accurate results. In
the future, we plan to investigate ways for integrating the textual
information in the learning process of the indices, to further improve query
response times, as well as to support index updates.

## Acknowledgments

This work was supported by the EU H2020 project SmartDataLake (825041) and the
EU H2020 project OpertusMundi (870228).

## References

  * [1] A. Al-Mamun, H. Wu, and W. G. Aref.  A tutorial on learned multi-dimensional indexes.  In SIGSPATIAL, pages 1–4, 2020.
  * [2] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger.  The R*-tree: An efficient and robust access method for points and rectangles.  In SIGMOD, pages 322–331, 1990.
  * [3] A. Cary, O. Wolfson, and N. Rishe.  Efficient and scalable method for processing top-k spatial boolean queries.  In SSDBM, pages 87–95, 2010.
  * [4] L. Chen, G. Cong, C. S. Jensen, and D. Wu.  Spatial keyword query processing: An experimental evaluation.  PVLDB, 6(3):217–228, 2013.
  * [5] Y. Chen, T. Suel, and A. Markowetz.  Efficient query processing in geographic web search engines.  In SIGMOD, pages 277–288, 2006.
  * [6] Z. Chen, L. Chen, G. Cong, and C. S. Jensen.  Location- and keyword-based querying of geo-textual data: a survey.  VLDB J., 30(4):603–640, 2021.
  * [7] M. Christoforaki, J. He, C. Dimopoulos, A. Markowetz, and T. Suel.  Text vs. space: efficient geo-search query processing.  In CIKM, pages 423–432, 2011.
  * [8] A. Davitkova, E. Milchevski, and S. Michel.  The ML-index: A multidimensional, learned index for point, range, and nearest-neighbor queries.  In EDBT, pages 407–410, 2020.
  * [9] J. Ding, V. Nathan, M. Alizadeh, and T. Kraska.  Tsunami: A learned multi-dimensional index for correlated data and skewed workloads.  PVLDB, 14(2):74–86, 2020.
  * [10] C. Faloutsos and S. Christodoulakis.  Signature files: An access method for documents and its analytical performance evaluation.  ACM Transactions on Information Systems (TOIS), 2(4):267–288, 1984\.
  * [11] I. D. Felipe, V. Hristidis, and N. Rishe.  Keyword search on spatial databases.  In ICDE, pages 656–665, 2008.
  * [12] R. Hariharan, B. Hore, C. Li, and S. Mehrotra.  Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems.  In SSDBM, page 16, 2007.
  * [13] A. Khodaei, C. Shahabi, and C. Li.  Hybrid indexing and seamless ranking of spatial and textual features of web documents.  In DEXA, volume 6261, pages 450–466, 2010.
  * [14] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis.  The case for learned index structures.  In SIGMOD, pages 489–504, 2018.
  * [15] P. Li, H. Lu, Q. Zheng, L. Yang, and G. Pan.  LISA: A learned index structure for spatial data.  In SIGMOD, pages 2119–2133, 2020.
  * [16] R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska.  Benchmarking learned indexes.  PVLDB, 14(1):1–13, 2020.
  * [17] V. Nathan, J. Ding, M. Alizadeh, and T. Kraska.  Learning multi-dimensional indexes.  In SIGMOD, pages 985–1000, 2020.
  * [18] J. Qi, G. Liu, C. S. Jensen, and L. Kulik.  Effectively learning spatial indices.  PVLDB, 13(12):2341–2354, 2020.
  * [19] J. Qi, Y. Tao, Y. Chang, and R. Zhang.  Theoretically optimal and empirically efficient r-trees with strong parallelizability.  PVLDB, 11(5):621–634, 2018.
  * [20] J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvåg.  Efficient processing of top-k spatial keyword queries.  In SSTD, pages 205–222, 2011.
  * [21] S. Vaid, C. B. Jones, H. Joho, and M. Sanderson.  Spatio-textual indexing for geographical search on the web.  In SSTD, volume 3633, pages 218–235, 2005.
  * [22] H. Wang, X. Fu, J. Xu, and H. Lu.  Learned index for spatial queries.  In MDM, pages 569–574, 2019.
  * [23] D. Wu, G. Cong, and C. S. Jensen.  A framework for efficient spatial web object retrieval.  VLDB J., 21(6):797–822, 2012.
  * [24] D. Wu, M. L. Yiu, G. Cong, and C. S. Jensen.  Joint top-k spatial keyword query processing.  IEEE Trans. Knowl. Data Eng., 24(10):1889–1903, 2012.
  * [25] C. Zhang, Y. Zhang, W. Zhang, and X. Lin.  Inverted linear quadtree: Efficient top k spatial keyword search.  IEEE Trans. Knowl. Data Eng., 28(7):1706–1721, 2016.
  * [26] D. Zhang, K. Tan, and A. K. H. Tung.  Scalable top-k spatial keyword search.  In EDBT, pages 359–370, 2013.
  * [27] Y. Zhou, X. Xie, C. Wang, Y. Gong, and W. Ma.  Hybrid index structures for location-based web search.  In CIKM, pages 155–162, 2005.


# Unseen Object Amodal Instance Segmentation
via Hierarchical Occlusion Modeling

Seunghyeok Back, Joosoon Lee, Taewon Kim, Sangjun Noh, Raeyoung Kang, Seongho
Bak, Kyoobin Lee All authors are with the School of Integrated Technology
(SIT), Gwangju Institute of Science and Technology (GIST), Cheomdan-gwagiro
123, Buk-gu, Gwangju 61005, Republic of Korea. † Corresponding author: Kyoobin
Lee<EMAIL_ADDRESS>
###### Abstract

Instance-aware segmentation of unseen objects is essential for a robotic
system in an unstructured environment. Although previous works achieved
encouraging results, they were limited to segmenting the only visible regions
of unseen objects. For robotic manipulation in a cluttered scene, amodal
perception is required to handle the occluded objects behind others. This
paper addresses Unseen Object Amodal Instance Segmentation (UOAIS) to detect
1) visible masks, 2) amodal masks, and 3) occlusions on unseen object
instances. For this, we propose a Hierarchical Occlusion Modeling (HOM) scheme
designed to reason about the occlusion by assigning a hierarchy to a feature
fusion and prediction order. We evaluated our method on three benchmarks
(tabletop, indoors, and bin environments) and achieved state-of-the-art (SOTA)
performance. Robot demos for picking up occluded objects, codes, and datasets
are available at https://sites.google.com/view/uoais.

##  I INTRODUCTION

Segmentation of unseen objects is an essential skill for robotic manipulations
in an unstructured environment. Recently, unseen object instance segmentation
(UOIS) [1, 2, 3, 4, 5, 6] have been proposed to detect unseen objects via
category-agnostic instance segmentation by learning a concept of object-ness
from large-scale synthetic data. However, these methods focus on perceiving
only visible regions, while humans have the ability to infer the entire
structure of occluded objects based on the visible structure [7, 8]. This
capability, called amodal perception, can allow a robot to straightforwardly
manipulate the occlusions in a cluttered scene. Although recent works [9, 10,
11, 12, 13, 14, 15] have shown the usefulness of amodal perception in
robotics, they have been limited to perceiving bounded object sets, where
prior knowledge about the manipulating target is given (e.g., labeling a task-
specific dataset and training for specific objects and environments).

Figure 1: Comparison of UOAIS and existing tasks. While other segmentation
methods are limited to perceiving known object sets or detecting only visible
masks of unseen objects, UOAIS aims to segment both visible and amodal masks
of unseen object instances in unstructured clutter.

This work proposes unseen object amodal instance segmentation (UOAIS) to
detect visible masks, amodal masks, and occlusion of unseen object instances
(Fig. 1). Similar to UOIS, it performs category-agnostic instance segmentation
to distinguish the visible regions of unseen objects. Meanwhile, UOAIS jointly
performs two additional tasks: amodal segmentation and occlusion
classification of the detected object instances. For this, we propose UOAIS-
Net, which reasons the object’s occlusion via hierarchical occlusion modeling
(HOM). The hierarchical fusion (HF) module in our model combines the multiple
features of prediction heads according to their hierarchy, thereby allowing
the model to consider the relationship between the visible mask, amodal mask,
and occlusion. We trained the model on 50,000 photo-realistic RGB-D images to
learn various object geometry and occlusion scenes and evaluated its
performance in various environments. The experiments demonstrated that visible
masks, amodal masks, and the occlusion of unseen objects could be detected in
a single framework with state-of-the-art (SOTA) performance. The ablation
studies demonstrated the effectiveness of the proposed HOM for UOAIS.

The contributions of this work are summarized as follows:

  * •

We propose a new task, UOAIS, to detect category-agnostic visible masks,
amodal masks, and occlusion of arbitrary object instances in a cluttered
environment.

  * •

We propose a HOM scheme to reason about the occlusion of objects by assigning
the hierarchy to feature fusion and prediction order.

  * •

We introduce a large-scale photorealistic synthetic dataset named UOAIS-SIM
and amodal annotations for the existing UOIS benchmark, OSD [16].

  * •

We validated our UOAIS-Net on three benchmarks and showed the effectiveness of
HOM by achieving state-of-the-art performance in both UOAIS and UOIS tasks.

  * •

We demonstrated a robotic application of UOAIS. Using UOAIS-Net, the object
grasping order for retrieving the occluded objects in clutter can be easily
planned.

##  II Related Work

Unseen Object Instance Segmentation. UOIS aims to segment the visible regions
of arbitrary object instances in an image [2, 3], and is useful for robotic
tasks such as grasping [17] and manipulating unseen objects [18]. Many
segmentation methods [19, 20, 16, 21, 22, 23] have been proposed to
distinguish objects but segmentation in cluttered scenes is challenging,
especially for objects with complex textures or that are under occlusion [24,
23]. To generalize over unseen objects and clutter scenes, recent UOIS methods
[1, 2, 3, 4, 6, 5] have trained category-agnostic instance segmentation models
to learn the concept of object-ness from a large amount of domain-randomized
[25] synthetic data. Although these methods are promising, they focus on
segmenting only the visible part of objects. On the other hand, our method can
jointly perform visible segmentation, amodal segmentation, and occlusion
classification for unseen object instances.

Amodal Instance Segmentation. When humans perceive an occluded object, they
can guess the entire structure even though part of it is invisible [7, 8]. To
mimic this amodal perception ability, amodal instance segmentation [26] has
been proposed, in which the goal is to segment both the amodal and visible
masks of each object instance in an image. The SOTA approaches are mainly
built on visible instance segmentation [27, 28] and perform amodal
segmentation through the addition of an amodal module, such as amodal branch
and invisible mask loss [29], multi-level coding (MLC) [30], refinement layers
[31], and occluder segmentation [32]. They have demonstrated that it is
possible to segment the amodal masks of occluded objects on various datasets
[30, 29]. However, these methods can detect only a particular set of trained
objects and require additional training data to deal with unseen objects. In
contrast, UOAIS learns to segment the category-agnostic amodal mask, reducing
the need for task-specific datasets and model re-training.

Amodal Perception in Robotics. The amodal concept is useful for occlusion
handling and recent studies have utilized amodal instance segmentation for
robotic picking systems [10, 9, 11] to decide the proper picking order for
target object retrieval. Amodal perception has also been applied to various
robotics tasks including object search [12, 33], grasping [14, 10, 9, 11], and
active perception [34, 15], but it is often limited to perceiving the
amodality of specific object sets. The works most related to our method are
[12] and [35]. These studies trained a 3D shape completion network that infers
the occluded geometry of unseen objects based on visible observation for
robotics manipulation in a cluttered scene. Although the reconstruction of the
occluded 3D structure is valuable, their amodal reconstruction network
requires an additional object instance segmentation module [23, 2] and only a
single instance can be reconstructed on a single forward pass. Whereas their
methods require a high computational cost, our method can directly predict the
occluded regions of multiple object instances in a single forward pass; thus,
it can be easily extended to various amodal robotic manipulations in the real
world.

##  III Problem Statement

We formalize our problem using the following definitions.

  1. I.

Scene: Let
$\mathcal{S}=\\{\mathcal{F}_{1},...,\mathcal{F}_{K},\mathcal{G}_{1},...,\mathcal{G}_{L},\mathcal{E}\\}$
be a simulated or real scene containing $K$ foreground object instances
$\mathcal{F}$, $L$ background object instances $\mathcal{G}$, and a camera
$\mathcal{E}$.

  2. II.

State: Let
$\mathbf{y}=\\{\mathcal{B}_{i},\mathcal{V}_{i},\mathcal{A}_{i},\mathcal{O}_{i},\mathcal{C}_{i}\\}^{K}_{1}$
be a ground truth state of foreground object instances in the scene $S$, which
is the set of the bounding box $\mathcal{B}\in\mathbb{R}^{4}$, visible mask
$\mathcal{V}\in\\{0,1\\}^{W\times H}$, amodal mask
$\mathcal{A}\in\\{0,1\\}^{W\times H}$, occlusion $\mathcal{O}\in\\{0,1\\}$,
and class $\mathcal{C}\in\\{0,1\\}$ captured by the camera $\mathcal{E}$. $W$
and $H$ are the width and height of the image. The occlusion $\mathcal{O}$ and
class $\mathcal{C}$ denote whether the instance is occluded and whether the
instance is a foreground objects or not, respectively.

  3. III.

Observation: An RGB-D image $\mathcal{I}=\\{\mathcal{R},\mathcal{U}\\}$
captured the scene $\mathcal{S}$ with the camera $\mathcal{E}$ at the pose
$\mathcal{T}$. $\mathcal{R}\in\mathbb{R}^{W\times H\times 3}$ is the RGB
image, and $\mathcal{U}\in\mathbb{R}^{W\times H}$ is the depth image.

  4. IV.

Dataset and Object Models: Let
$\mathcal{D}=\\{(\mathbf{y}_{i},\mathcal{I}_{i})\\}_{1}^{N}$ be a dataset. Let
$\mathcal{M_{\mathcal{D}}}$ be a set of object models used for $\mathcal{F}$
and $\mathcal{G}$ in the dataset $\mathcal{D}$.

  5. V.

Known and Unseen Object: Let the train and test set be $\mathcal{D}_{train}$
and $\mathcal{D}_{test}$. Let $f$ be a function trained on
$\mathcal{D}_{train}$ and then tested on $\mathcal{D}_{test}$. If the
$\mathcal{M}_{\mathcal{D}_{train}}\cap\mathcal{M}_{\mathcal{D}_{test}}=\emptyset$,
the object in $\mathcal{M}_{\mathcal{D}_{test}}$ is the unseen object, and the
object in $\mathcal{M}_{\mathcal{D}_{train}}$ is the known object for $f$.

The objective of UOAIS is to detect a category-agnostic visible mask, an
amodal mask and the occlusion of arbitrary objects. Thus, our paper aims to
find a function $f:\mathcal{I}\rightarrow\mathbf{y}$ for $\mathcal{D}_{test}$
given $\mathcal{D}_{train}$, where
$\mathcal{M}_{\mathcal{D}_{train}}\cap\mathcal{M}_{\mathcal{D}_{test}}=\emptyset$.

Figure 2: Architecture of our proposed UOAIS-Net. UOAIS-Net consists of (1) an
RGB-D fusion backbone for RoI RGB-D feature extraction and (2) an HOM Head for
hierarchical prediction of the bounding box, visible mask, amodal mask, and
occlusion. It was trained on synthetic RGB-D images and then tested on real
clutter scenes. Through occlusion modeling with a HF module, segmentation and
occlusion prediction of unseen objects can be significantly enhanced.

##  IV Unseen Object Amodal Instance Segmentation

###  IV-A Motivation

To design an architecture for UOAIS, we first made the following observations
based on the relationship of bounding box $\mathcal{B}$, visible mask
$\mathcal{V}$, amodal mask $\mathcal{A}$, and occlusion $\mathcal{O}$.

  1. 1.

$\mathcal{B}\rightarrow\mathcal{V,A,O}$: Most SOTA instance segmentation
methods [36, 27, 37, 30, 38, 28] have detect-then-segment approaches; They
detect the object region of interest (RoI) bounding box first, then segment
the instance mask in a given RoI bounding box. We followed this paradigm by
adopting a Mask R-CNN [27] for UOAIS, and thus visible, amodal, and occlusion
predictions strongly depend on the bounding box prediction.

  2. 2.

$\mathcal{V}\rightarrow\mathcal{A}$: The amodal mask is the union of the
visible mask $\mathcal{V}$ and the invisible mask $\mathcal{IV}$
($\mathcal{A}=\mathcal{V}\cup\mathcal{IV}$). The visible mask is more obvious
than amodal and invisible masks; thus, segment the visible mask, and then
infer the amodal mask based on the segmented visible mask.

  3. 3.

$\mathcal{A,V}\rightarrow\mathcal{O}$: The occlusion is defined by the ratio
of the visible mask to the amodal mask, i.e., if the visible mask equals to
the amodal mask ($\mathcal{V}/\mathcal{A}=1$), the object is not occluded
($\mathcal{O}=0$); segment the visible and amodal masks, and then classify the
occlusion.

Based on these observations, we propose an HOM scheme for UOAIS; (1) detect
the RoI bounding box $\mathcal{B}$ (2) segment the visible mask $\mathcal{V}$
(3) segment the amodal mask $\mathcal{A}$, and (4) classify the occlusion
$\mathcal{O}$
($\mathcal{B}\rightarrow\mathcal{V}\rightarrow\mathcal{A}\rightarrow\mathcal{O}$).
For this, we propose a UOAIS-Net, which employs an HOM scheme on the top of
Mask R-CNN [27] with an HF module. The HF module explicitly assigns a
hierarchy to feature fusion and prediction order and improves the overall
performance.

###  IV-B UOAIS-Net

Overview. UOAIS-Net consists of (1) an RGB-D fusion backbone and (2) an HOM
Head (Fig. 2). From an input RGB-D image $\mathcal{I}$, the RGB-D fusion
backbone with a feature pyramid network (FPN) [39] extracts an RGB-D FPN
feature. Next, the region proposal network (RPN) [36] proposes possible object
regions and the RoIAlign layer crops an RoI RGB-D FPN feature ($F_{RoI}^{S}$)
size of $7\times 7\times Q$. Then, the bounding box branch in the HOM Head
performs a box regression and foreground classification. For positive RoIs,
the HOM Head extracts an RoI feature ($F_{RoI}^{L}$) with dimensions of
$14\times 14\times Q$ from the RGB-D FPN feature and predicts a visible mask
$\mathcal{V}$, amodal mask $\mathcal{A}$, and occlusion $\mathcal{O}$
hierarchically for each RoI via the HF module. $Q$ is the number of channels.

Sim2Real Transfer. To generalize over unseen objects of various shapes and
textures, our model is trained via Sim2Real transfer; trains a model on large
synthetic data and then applies it to real clutter scenes. In this scheme, the
domain gap between simulation and real scenes greatly affects the performance
of the model [40, 3]. While depth shows a reasonable performance against the
Sim2Real transfer [41, 1, 6], training with only the non-photorealistic RGB is
often insufficient to segment the real object instances [2, 3]. To address
this issue, we trained a UOAIS-Net using photo-realistic synthetic images
(UOAIS-Sim in Section IV-D) so the Sim2Real gap could be significantly
reduced.

RGB-D Fusion. Depth provides useful 3D geometric information for recognizing
the object [2, 3, 6], but the joint use of the RGB with depth is required to
produce a precise segmentation boundary [42, 43, 2], as depth is noisy
especially for transparent and reflective surfaces. To effectively learn
discriminative RGB-D features, the RGB-D fusion backbone extracts RGB and
depth features with a separate ResNet-50 [44] for each modality. Then, the RGB
and depth features are fused into RGB-D features in a multiple level (C3, C4,
C5) through concatenation and $1\times 1$ convolution, thereby reducing the
number of the channel $2Q$ to $Q$. Finally, RGB-D features are fed into the
FPN [39] and the RoIAlign layer [27] and form an RGB-D FPN feature.

###  IV-C Hierarchical Occlusion Modeling

The HOM Head is designed to reason about the occlusion in an RoI by predicting
the output in the order of
$\mathcal{B}\rightarrow\mathcal{V}\rightarrow\mathcal{A}\rightarrow\mathcal{O}$.
The HOM Head consists of (1) a bounding box branch (2) a visible mask branch
(3) an amodal mask branch, and (4) an occlusion prediction branch. The HF
module $h$ for each branch fuses all prior features into that branch.

Bounding Box Branch ($\mathcal{B}$, $\mathcal{C}$). The HOM Head first
predicts the bounding box $\mathcal{B}$ and the class $\mathcal{C}$ from
$F_{RoI}^{S}$ given by RPN. The structure of the bounding box branch follows a
standard localization layer in [27]. $F_{RoI}^{S}$ is fed into two fully
connected (FC) layers, then the $\mathcal{B}$ and $\mathcal{C}$ are predicted
by the following FC layer. For the category-agnostic segmentation, we set
$\mathcal{C}\in\\{0,1\\}$ to detect all the foreground instances.

HF module. ($\mathcal{V},\mathcal{A},\mathcal{O}$) For the positive RoI, the
HOM Head performs visible segmentation, amodal segmentation, and occlusion
classification sequentially with the HF module. Following motivation $1)$, we
first provided a box feature $F_{\mathcal{B}}$ to all other subsequent
branches for the prediction conditioned on $\mathcal{B}$. It is similar to the
MLC [30] that provides a box feature in mask predictions, which allows the
mask layers to exploit global information and enhances the segmentation.
$F_{RoI}^{S}$ is fed into a $3\times 3$ deconvolution layer, and then an
upsampled RoI feature with a size of $14\times 14\times Q$ is forwarded to
three $3\times 3$ convolutional layers. The output of this operation is used
as the box feature $F_{\mathcal{B}}$.

Following the hierarchy of the HOM scheme, the HF module $h$ for each branch
fuses an $F_{RoI}^{L}$ with $F_{\mathcal{B}}$ and features from a prior branch
as follows:

$F_{\mathcal{V}}=h_{\mathcal{V}}(F_{\mathcal{B}},F_{RoI}^{L})$ (1)
$F_{\mathcal{A}}=h_{\mathcal{A}}(F_{\mathcal{B}},F_{RoI}^{L},F_{\mathcal{V}})$
(2)
$F_{\mathcal{O}}=h_{\mathcal{O}}(F_{\mathcal{B}},F_{RoI}^{L},F_{\mathcal{V}},F_{\mathcal{A}})$
(3)

where $F_{\mathcal{V}}$, $F_{\mathcal{A}}$, and $F_{\mathcal{O}}$ are the
visible, amodal, and occlusion features, respectively, and $h_{\mathcal{V}}$,
$h_{\mathcal{A}}$, $h_{\mathcal{O}}$ are the HF modules for the visible,
amodal, occlusion branches. Specifically, the HF module fuses all inputs by
concatenating them to be the channel dimension as $P$ and passing it to three
3x3 convolutional layers to reduce the number of channels into $Q$. Then it is
forwarded to three $3\times 3$ convolutional layers to extract the task-
relevant feature in each branch. Finally, each branch of the HOM outputs the
final predictions with the prediction layer $g$. The loss for HOM Head
$\mathcal{L}_{HOM}$ is

$\mathcal{L}(g_{\mathcal{V}}(F_{\mathcal{V}}),\mathcal{V})+\mathcal{L}(g_{\mathcal{A}}(F_{\mathcal{A}}),\mathcal{A})+\mathcal{L}(g_{\mathcal{O}}(F_{\mathcal{O}}),\mathcal{O})$
(4)

where $g_{\mathcal{V}}$, $g_{\mathcal{A}}$, and $g_{\mathcal{O}}$ are the
prediction layers for the visible mask, amodal mask, and occlusion,
respectively. We used a $2\times 2$ deconvolutional layer for
$g_{\mathcal{V}},g_{\mathcal{A}}$, and FC layer for $g_{\mathcal{O}}$. The
total loss for UOAIS-Net is
$\mathcal{L}_{reg}+\mathcal{L}_{class}+\mathcal{L}_{HOM}$, where the
regression and classification loss are from [27].

Architecture Comparison. We compare the prediction heads of amodal instance
segmentation methods in Fig. 3. From the cropped RoI feature $F_{RoI}$, Amodal
MRCNN [29] outputs all the predictions with separate branches, without
considering the relationship between them. ORCNN [29] regulates the invisible
mask to be an amodal minus the visible mask, but their features are not inter-
weaved. ASN [30] fuses the features from $F_{RoI}^{S}$ into mask branches via
multi-level-coding, but the visible and amodal features are extracted
parallelly. In contrast, all the branches in UOAIS-Net are hierarchically
connected via the HF module for the hierarchical prediction via occlusion
reasoning.

Figure 3: Prediction head comparison. a) Amodal MRCNN [29], b) ORCNN [29], c)
ASN [30], d) Ours. UOAIS-Net hierarchically fuses the box, visible, amodal and
occlusion features
($\mathcal{B}\rightarrow\mathcal{V}\rightarrow\mathcal{A}\rightarrow\mathcal{O}$),
while the visible and amodal features in other methods [29, 30] are indirectly
related to each other. $F_{RoI}$ denotes an RoI feature after the RoIAlign.

Implementation Details. The model was trained on UOAIS-Sim dataset following
the standard schedule in [45] for $90,000$ iterations with SGD [46] using the
learning rate of $0.00125$. We applied color [47], depth [48], and crop
augmentation. Training took about $8$h on a single Tesla A100, and the
inference took $0.13$ s per image (1,000 iterations) on a Titan XP. For it to
serve as a general object instance detector, only the plane and bin were set
to background objects $\mathcal{G}$ and all other objects are set to
foreground objects $\mathcal{F}$; thus, it detected all instances in the image
except for the plane and bin. For the cases requiring the task-specific
foreground object selection [16], we trained a binary segmentation model [49]
on the TOD dataset [2], thereby enabling real-time foreground segmentation
($14$ ms for single forward pass) with less than 0.5 M parameters.

Figure 4: Photo-realistic synthetic RGB images of UOAIS-Sim in plane surfaces
(top row) and bin (bottom row). TABLE I: UOAIS ($\mathcal{A}$, $\mathcal{IV}$,
$\mathcal{O}$, $\mathcal{V}$) performances on OSD[16]-Amodal. All methods are
trained with RGB-D UOAIS-Sim. $\\{\\}$ denotes that they are predicted
parallelly. $\rightarrow$ refers the hierarchy in prediction heads. OV:
Overlap $F$, BO: Boundary $F$

Method | Hierarchy Order | Amodal Mask ($\mathcal{A}$) | Invisible Mask ($\mathcal{IV}$) | Occlusion ($\mathcal{O}$) | Visible Mask ($\mathcal{V}$)
---|---|---|---|---|---
OV | BO |<EMAIL_ADDRESS>| OV | BO |<EMAIL_ADDRESS>| $F_{\mathcal{O}}$ | $ACC_{\mathcal{O}}$ | OV | BO |<EMAIL_ADDRESS>
Amodal MRCNN [29] | { $\mathcal{B},\ \mathcal{V},\ \mathcal{A}$ } | 82.5 | 66.7 | 82.7 | 51.1 | 28.2 | 35.5 | 72.3 | 75.9 | 83.3 | 69.7 | 75.1
ORCNN [29] | { $\mathcal{B},\ \mathcal{V},\ \mathcal{A}$ } $\rightarrow\mathcal{IV}$ | 83.1 | 67.2 | 84.2 | 48.7 | 23.7 | 29.1 | 63.6 | 70.0 | 83.1 | 70.0 | 75.9
ASN [30] | { $\mathcal{B},\ \mathcal{O}$ } $\rightarrow$ { $\mathcal{V},\ \mathcal{A}$ } | 80.6 | 66.9 | 84.6 | 41.9 | 20.8 | 30.5 | 59.6 | 66.3 | 85.0 | 72.8 | 78.9
UOAIS-Net (Ours) | $\mathcal{B}\rightarrow\mathcal{V}\rightarrow\mathcal{A}\rightarrow\mathcal{O}$ | 82.2 | 68.7 | 84.1 | 55.3 | 32.3 | 42.9 | 82.1 | 90.8 | 85.2 | 73.1 | 79.1

TABLE II: UOIS ($\mathcal{V}$) performances of UOAIS-Net and SOTA UOIS methods
on OSD [16] and OCID [24].

Method | Input |  Amodal Perception |  Refine -ment | OSD [16] | OCID [24]
---|---|---|---|---|---
Overlap | Boundary |<EMAIL_ADDRESS>| Overlap | Boundary |<EMAIL_ADDRESS>
P | R | F | P | R | F | P | R | F | P | R | F
UOIS-Net-2D [2] | RGB-D |  |  | 80.7 | 80.5 | 79.9 | 66.0 | 67.1 | 65.6 | 71.9 | 88.3 | 78.9 | 81.7 | 82.0 | 65.9 | 71.4 | 69.1
UOIS-Net-3D [3] | RGB-D |  |  | 85.7 | 82.5 | 83.3 | 75.7 | 68.9 | 71.2 | 73.8 | 86.5 | 86.6 | 86.4 | 80.0 | 73.4 | 76.2 | 77.2
UCN [4] | RGB-D |  |  | 84.3 | 88.3 | 86.2 | 67.5 | 67.5 | 67.1 | 79.3 | 86.0 | 92.3 | 88.5 | 80.4 | 78.3 | 78.8 | 82.2
Mask R-CNN [27] | RGB-D |  |  | 83.8 | 84.3 | 83.9 | 70.3 | 72.7 | 71.0 | 77.8 | 67.6 | 83.7 | 69.0 | 63.3 | 72.6 | 64.1 | 72.7
UOAIS-Net (Ours) | RGB | ✓ |  | 84.2 | 83.7 | 83.8 | 72.2 | 72.8 | 72.1 | 76.7 | 66.5 | 83.1 | 67.9 | 62.1 | 70.2 | 62.3 | 73.1
UOAIS-Net (Ours) | Depth | ✓ |  | 85.0 | 86.6 | 85.6 | 68.2 | 66.0 | 66.8 | 81.3 | 89.8 | 90.8 | 89.7 | 86.7 | 84.0 | 84.6 | 87.0
UOAIS-Net (Ours) | RGB-D | ✓ |  | 85.3 | 85.4 | 85.2 | 72.7 | 74.3 | 73.1 | 79.1 | 70.7 | 86.7 | 71.9 | 68.2 | 78.5 | 68.8 | 78.7
UCN + Zoom-in [4] | RGB-D |  | ✓ | 87.4 | 87.4 | 87.4 | 69.1 | 70.8 | 69.4 | 83.2 | 91.6 | 92.5 | 91.6 | 86.5 | 87.1 | 86.1 | 89.3

###  IV-D Amodal Datasets

UOAIS-Sim. We generated 50,000 RGB-D images of 1,000 cluttered scenes with
amodal annotations (Fig. 4.). We used the BlenderProc [50] for photo-realistic
rendering. A total of 375 3D textured object models from [51, 52, 53] were
used, including household (e.g., cereal box, bottle) and industrial objects
(e.g., bracket, screw) of various geometries. One to 40 objects were randomly
dropped on randomly textured bin or plane surfaces. Images were captured at a
random camera pose. We split the images and object models with a 9:1 and 4:1
ratio for the training and validation sets. The YCB object models [54] in BOP
[53] were excluded from the simulation so that they could be utilized as test
objects in the real world.

OSD-Amodal. We introduced amodal annotations for the OSD [16] dataset to
benchmark the UOAIS performance. Several amodal instance datasets have been
proposed, but [8] and [30] consist of mainly outdoor scenes, and [29] does not
contain depth. OSD is a UOIS benchmark consisting of RGB-D tabletop clutter
scenes, but it does not provide amodal annotations. We manually annotated the
amodal instance masks. To ensure consistent and precise annotation, three
annotators cross-checked each annotation. We also annotated object’s relative
occlusion orders for future research.

##  V Experiments

Datasets. We compared our methods and SOTA on the three benchmarks. OSD[16],
consisting of 111 tabletop clutter images, was used to evaluate the UOAIS
($\mathcal{V}$, $\mathcal{A}$, $\mathcal{IV}$, $\mathcal{O}$) and UOIS
($\mathcal{V}$) performances. Further, OCID and WISDOM were used to compare
the UOIS performance. OCID provides 2,346 indoor images and WISDOM includes
300 top-view test images in bin picking. The image size of input was set to
$640\times 480$ in OSD and OCID, and $512\times 384$ in WISDOM.

Metrics. In OSD and OCID, we measured the Overlap $P/R/F$, Boundary $P/R/F$,
and<EMAIL_ADDRESS>for the amodal, visible, and invisible masks [55, 2]. Overlap
$P/R/F$ and Boundary $P/R/F$ evaluate the whole area and the sharpness of the
prediction, respectively, where $P$, $R$, and $F$ are the precision, recall,
and F-measure of instance masks after the Hungarian matching, respectively.
<EMAIL_ADDRESS>is the percentage of segmented objects with an Overlap F-measure
greater than 0.75. For details, refer to [2] and [55]. We also reported the
accuracy ($ACC_{o}$) and F-measure ($F_{o}$) of occlusion classification,
where $ACC_{o}=\frac{\delta}{\alpha}$,
$F_{o}=\frac{2P_{o}R_{o}}{P_{o}+R_{o}}$, $P_{o}=\frac{\delta}{\beta}$,
$R_{o}=\frac{\delta}{\gamma}$. $\alpha$ is the number of the matched instances
after the Hungarian matching. $\beta$, $\gamma$, and $\delta$ are the numbers
of occlusion prediction, ground truth, and correct prediction, respectively.
In WISDOM, we measured the mask AP, AP50, and AR [56]. All the metrics of the
model trained on UOAIS-Sim are the average scores of three different random
seeds. We used a light-weight network [49] on the OSD to filter the out-of-
the-table instances as described in Section IV-C.

Figure 5: Comparison of UOAIS-Net and SOTA methods (left) and predictions of
our methods on various environments (right). Red region: pixel predicted as an
invisible mask ($\mathcal{IV}=\mathcal{A}-\mathcal{V}$), Red border: object
predicted as an occluded ($\mathcal{O}=1$)

Comparison with SOTA in UOAIS ($\mathcal{A}$, $\mathcal{IV}$, $\mathcal{O}$,
$\mathcal{V}$). Table I compares the UOAIS-Net and the SOTA amodal instance
segmentation methods [29, 30] in OSD-Amodal. SOTA methods are trained on
UOAIS-Sim RGB-D images with the same hyper-parameters of UOAIS-Net. The only
difference between the models is the prediction heads (Fig. 3). The occlusion
predictions for Amodal MRCNN and ASN are decided using the ratio of
$\mathcal{V}$ to $\mathcal{A}$ ($\mathcal{O}=1$ if
$\mathcal{V}/\mathcal{A}<0.95$). Our proposed UOAIS-Net outperforms the others
on $\mathcal{IV}$, $\mathcal{O}$, and $\mathcal{V}$ and achieves a similar
performance with the ASN on $\mathcal{A}$, which shows the effectiveness of
the HOM Head.

TABLE III: UOIS ($\mathcal{V}$) performances in WISDOM [1]

Method | Input | Train Dataset | Visible Mask ($\mathcal{V}$)
---|---|---|---
AP | AP50 | AR
Mask R-CNN [1] | RGB | WISDOM-Sim | 38.4 | - | 60.8
Mask R-CNN [1] | Depth | WISDOM-Sim | 51.6 | - | 64.7
Mask R-CNN [1] | RGB | WISDOM-Real | 40.1 | 76.4 | -
D-SOLO [57] | RGB | WISDOM-Real | 42.0 | 75.1 | -
PPIS [58] | RGB | WISDOM-Real | 52.3 | 82.8 | -
Mask R-CNN | RGB | UOAIS-Sim | 60.6 | 90.3 | 68.8
Mask R-CNN | Depth | UOAIS-Sim | 56.5 | 85.9 | 65.4
Mask R-CNN | RGB-D | UOAIS-Sim | 63.8 | 91.8 | 70.5
UOAIS-Net (Ours) | RGB-D | UOAIS-Sim | 65.9 | 93.3 | 72.2

Comparison with SOTA in UOIS ($\mathcal{V}$). Table II shows the visible
segmentation performances in OSD and OCID. The metrics of [2, 4, 3] are from
their paper where non-photorealistic images are used. The Mask R-CNN [27]
trained on UOAIS-Sim was also used as a baseline. UOAIS-Net achieved the
performance on par with the SOTA UOIS methods. Note that our methods can
detect the amodal masks and occlusions, while others are limited to segmenting
the visible masks only. UCN with Zoom-in refinement [4] achieved a better
performance than ours in OCID, but it requires more computation ($0.2+0.05K$ s
total, $K$: number of instances) than our methods ($0.13$ s total). Also, the
loss function of UCN considers only visible regions by pushing the pixels from
the same objects to be close in feature embedding space; thus, an extra
clustering network and loss function should be added for the amodal
perception. UOAIS-Net with depth performs better than the RGB-D model in OCID,
as it includes much more complex textured backgrounds than OSD. Table III
compares the visible segmentation performance in WISDOM, where the metrics of
the others are from [1, 58], and the backbone for [1] is ResNet-32 [44].
UOAIS-Net outperforms all other methods and shows that it can also generalize
well on the bin environment. The qualitative comparisons of the models trained
on RGB-D images are shown in Fig. 5.

TABLE IV: Ablation of hierarchy order on OSD-Amodal

Hierarchy |  Overall Score | Amodal Mask | Invisible Mask | Occlusion | Visible Mask
---|---|---|---|---|---
OV |<EMAIL_ADDRESS>| OV |<EMAIL_ADDRESS>| $ACC_{\mathcal{O}}$ | OV |<EMAIL_ADDRESS>
$\mathcal{O}\rightarrow\mathcal{A}\rightarrow\mathcal{V}$ | 0.41 | 80.8 | 84.9 | 54.1 | 43.3 | 89.0 | 85.2 | 79.8
$\mathcal{A}\rightarrow\mathcal{O}\rightarrow\mathcal{V}$ | 0.40 | 80.7 | 83.7 | 54.3 | 44.1 | 91.1 | 85.3 | 78.7
$\mathcal{A}\rightarrow\mathcal{V}\rightarrow\mathcal{O}$ | 0.49 | 81.4 | 83.2 | 54.6 | 42.0 | 90.8 | 85.6 | 79.7
$\mathcal{O}\rightarrow\mathcal{V}\rightarrow\mathcal{A}$ | 0.48 | 81.9 | 84.0 | 56.3 | 44.6 | 89.4 | 84.9 | 78.6
$\mathcal{V}\rightarrow\mathcal{O}\rightarrow\mathcal{A}$ | 0.49 | 82.4 | 84.0 | 55.5 | 42.1 | 90.4 | 85.2 | 78.8
$\mathbfcal{V}\rightarrow\mathbfcal{A}\rightarrow\mathbfcal{O}$ | 0.57 | 82.2 | 84.1 | 55.3 | 42.9 | 90.8 | 85.2 | 79.1

TABLE V: Ablation of feature fusion on OSD-Amodal

$F_{\mathcal{B}}$ | $F_{\mathcal{V}},F_{\mathcal{A}},F_{\mathcal{O}}$ |  Overall Score | Amodal Mask | Invisible Mask | Occlusion | Visible Mask
---|---|---|---|---|---|---
OV |<EMAIL_ADDRESS>| OV |<EMAIL_ADDRESS>| $ACC_{\mathcal{O}}$ | OV |<EMAIL_ADDRESS>
✓ |  | 0.17 | 81.9 | 84.3 | 51.3 | 38.1 | 87.5 | 83.6 | 76.2
| ✓ | 0.47 | 81.1 | 84.4 | 53.0 | 41.6 | 89.1 | 84.1 | 77.9
✓ |  | 0.61 | 80.5 | 84.7 | 53.1 | 40.0 | 90.2 | 84.6 | 79.1
✓ | ✓ | 0.85 | 82.2 | 84.1 | 55.3 | 42.9 | 90.8 | 85.2 | 79.1

Ablation of Hierarchy Order. Table IV shows the ablation of hierarchy orders
in UOAIS-Net on OSD-Amodal with RGB-D input. The overall score was computed by
averaging the normalized value of each column. Consistent with our motivation,
the model with the HOM scheme
($\mathcal{V}\rightarrow\mathcal{A}\rightarrow\mathcal{O}$) performed better
than the others, while the model with the reverse scheme
($\mathcal{O}\rightarrow\mathcal{A}\rightarrow\mathcal{V}$) showed the worst
performances. This indicates that the proposed HOM scheme is effective in
modeling the occlusion of objects.

Ablation of Feature Fusion. Table V shows the ablation of $F_{\mathcal{B}}$
and $F_{\mathcal{V}},F_{\mathcal{A}},F_{\mathcal{O}}$ in the HOM Head of
UOAIS-Net on OSD-Amodal, where the input is RGB-D. The model with both
$F_{\mathcal{B}}$ and $F_{\mathcal{V}},F_{\mathcal{A}},F_{\mathcal{O}}$ fusion
achieved the best performance, which highlights the importance of dense
feature fusion in the prediction heads.

Occluded Object Retrieval. We demonstrated an amodal robotic manipulation by
combining UOAIS-Net with the 6-DOF grasp generator [17] (Fig. 6). When the
target object is occluded, grasping it directly is often infeasible due to the
collision between the objects and the robot. Using UOAIS-Net, the grasping
order to retrieve the target object can be easily determined; If the target
object is occluded ($O=1$), remove the nearest unoccluded objects ($O=0$)
until the target becomes unoccluded ($O=0$). Then the target object can be
easily grasped. We simply used a ResNet-34 [44] trained on 25 images per
object to classify the objects.

Figure 6: Amodal robotic manipulation using UOAIS. To retrieve the target
object (cup in (a)) in a cluttered scene (b), grasp the unoccluded objects
sequentially (box in (c) and bowl in (d)), then the target object can be
easily retrieved (e). The demonstration video is available at our project
website: https://sites.google.com/view/uoais

##  VI Conclusion

This paper proposed a novel task, UOAIS, to jointly detect the visible masks,
amodal masks, and occlusions of unseen objects in a single framework. Under
the HOM scheme, UOAIS-Net could successfully detect and reason the occlusion
of unseen objects with SOTA performance on the three datasets. We also
demonstrated a useful demo for occluded object retrieval. We hope UOAIS can
serve as a simple and effective baseline for amodal robotic manipulation.

##  VII Acknowledgement

We give a special thanks to Sungho Shin and Yeonguk Yu for their helpful
comment and technical advice. This work was fully supported by the Korea
Institute for Advancement of Technology (KIAT) grant funded by the Korea
Government (MOTIE) (Project Name: Shared autonomy based on deep reinforcement
learning for responding intelligently to unfixed environments such as robotic
assembly tasks, Project Number: 20008613). This work was also partially
supported by the HPC Support project of the Korea Ministry of Science and ICT
and NIPA.

## References

  * [1] M. Danielczuk, M. Matl, S. Gupta, A. Li, A. Lee, J. Mahler, and K. Goldberg, “Segmenting unknown 3d objects from real depth images using mask r-cnn trained on synthetic data,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 7283–7290.
  * [2] C. Xie, Y. Xiang, A. Mousavian, and D. Fox, “The best of both modes: Separately leveraging rgb and depth for unseen object instance segmentation,” in _Conference on robot learning_. PMLR, 2020, pp. 1369–1378.
  * [3] ——, “Unseen object instance segmentation for robotic environments,” _IEEE Transactions on Robotics_ , 2021.
  * [4] Y. Xiang, C. Xie, A. Mousavian, and D. Fox, “Learning rgb-d feature embeddings for unseen object instance segmentation,” _arXiv preprint arXiv:2007.15157_ , 2020.
  * [5] M. Durner, W. Boerdijk, M. Sundermeyer, W. Friedl, Z.-C. Marton, and R. Triebel, “Unknown object segmentation from stereo images,” _arXiv preprint arXiv:2103.06796_ , 2021.
  * [6] S. Back, J. Kim, R. Kang, S. Choi, and K. Lee, “Segmenting unseen industrial components in a heavy clutter using rgb-d fusion and synthetic data,” in _2020 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2020, pp. 828–832.
  * [7] S. E. Palmer, _Vision science: Photons to phenomenology_. MIT press, 1999.
  * [8] Y. Zhu, Y. Tian, D. Metaxas, and P. Dollár, “Semantic amodal segmentation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1464–1472.
  * [9] K. Wada, K. Okada, and M. Inaba, “Joint learning of instance and semantic segmentation for robotic pick-and-place with heavy occlusions in clutter,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 9558–9564.
  * [10] K. Wada, S. Kitagawa, K. Okada, and M. Inaba, “Instance segmentation of visible and occluded regions for finding and picking target from a pile of objects,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 2048–2055.
  * [11] Y. Inagaki, R. Araki, T. Yamashita, and H. Fujiyoshi, “Detecting layered structures of partially occluded objects for bin picking,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 5786–5791.
  * [12] A. Price, L. Jin, and D. Berenson, “Inferring occluded geometry improves performance when retrieving an object from dense clutter,” _arXiv preprint arXiv:1907.08770_ , 2019.
  * [13] M. Narasimhan, E. Wijmans, X. Chen, T. Darrell, D. Batra, D. Parikh, and A. Singh, “Seeing the un-scene: Learning amodal semantic maps for room navigation,” in _European Conference on Computer Vision_. Springer, 2020, pp. 513–529.
  * [14] Y. Qin, R. Chen, H. Zhu, M. Song, J. Xu, and H. Su, “S4g: Amodal single-view single-shot se (3) grasp detection in cluttered scenes,” in _Conference on robot learning_. PMLR, 2020, pp. 53–65.
  * [15] M. Li, C. Weber, M. Kerzel, J. H. Lee, Z. Zeng, Z. Liu, and S. Wermter, “Robotic occlusion reasoning for efficient object existence prediction,” _arXiv preprint arXiv:2107.12095_ , 2021.
  * [16] A. Richtsfeld, T. Mörwald, J. Prankl, M. Zillich, and M. Vincze, “Segmentation of unknown objects in indoor environments,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2012, pp. 4791–4796.
  * [17] M. Sundermeyer, A. Mousavian, R. Triebel, and D. Fox, “Contact-graspnet: Efficient 6-dof grasp generation in cluttered scenes,” _arXiv preprint arXiv:2103.14127_ , 2021.
  * [18] A. Murali, A. Mousavian, C. Eppner, C. Paxton, and D. Fox, “6-dof grasping for target-driven object manipulation in clutter,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 6232–6238.
  * [19] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” _International journal of computer vision_ , vol. 59, no. 2, pp. 167–181, 2004.
  * [20] R. B. Rusu, “Semantic 3d object maps for everyday manipulation in human living environments,” _KI-Künstliche Intelligenz_ , vol. 24, no. 4, pp. 345–348, 2010.
  * [21] S. Koo, D. Lee, and D.-S. Kwon, “Unsupervised object individuation from rgb-d image sequences,” in _2014 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2014, pp. 4450–4457.
  * [22] E. Potapova, A. Richtsfeld, M. Zillich, and M. Vincze, “Incremental attention-driven object segmentation,” in _2014 IEEE-RAS International Conference on Humanoid Robots_. IEEE, 2014, pp. 252–258.
  * [23] T. T. Pham, T.-T. Do, N. Sünderhauf, and I. Reid, “Scenecut: Joint geometric and object segmentation for indoor scenes,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 3213–3220.
  * [24] M. Suchi, T. Patten, D. Fischinger, and M. Vincze, “Easylabel: a semi-automatic pixel-wise object annotation tool for creating robotic rgb-d datasets,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 6678–6684.
  * [25] J. Tobin, R. Fong, A. Ray, J. Schneider, W. Zaremba, and P. Abbeel, “Domain randomization for transferring deep neural networks from simulation to the real world,” in _2017 IEEE/RSJ international conference on intelligent robots and systems (IROS)_. IEEE, 2017, pp. 23–30.
  * [26] K. Li and J. Malik, “Amodal instance segmentation,” in _European Conference on Computer Vision_. Springer, 2016, pp. 677–693.
  * [27] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 2961–2969.
  * [28] Z. Tian, C. Shen, H. Chen, and T. He, “Fcos: Fully convolutional one-stage object detection,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 9627–9636.
  * [29] P. Follmann, R. König, P. Härtinger, M. Klostermann, and T. Böttger, “Learning to see the invisible: End-to-end trainable amodal instance segmentation,” in _2019 IEEE Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2019, pp. 1328–1336.
  * [30] L. Qi, L. Jiang, S. Liu, X. Shen, and J. Jia, “Amodal instance segmentation with kins dataset,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 3014–3023.
  * [31] Y. Xiao, Y. Xu, Z. Zhong, W. Luo, J. Li, and S. Gao, “Amodal segmentation based on visible region segmentation and shape prior,” _arXiv preprint arXiv:2012.05598_ , 2020.
  * [32] L. Ke, Y.-W. Tai, and C.-K. Tang, “Deep occlusion-aware instance segmentation with overlapping bilayers,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 4019–4028.
  * [33] M. Danielczuk, A. Angelova, V. Vanhoucke, and K. Goldberg, “X-ray: Mechanical search for an occluded object by minimizing support of learned occupancy distributions,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 9577–9584.
  * [34] J. Yang, Z. Ren, M. Xu, X. Chen, D. J. Crandall, D. Parikh, and D. Batra, “Embodied amodal recognition: Learning to move to perceive objects,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 2040–2050.
  * [35] W. Agnew, C. Xie, A. Walsman, O. Murad, C. Wang, P. Domingos, and S. Srinivasa, “Amodal 3d reconstruction for robotic manipulation via stability and connectivity,” _arXiv preprint arXiv:2009.13146_ , 2020.
  * [36] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” _arXiv preprint arXiv:1506.01497_ , 2015.
  * [37] Y. Lee and J. Park, “Centermask: Real-time anchor-free instance segmentation,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 13 906–13 915.
  * [38] K. Chen, J. Pang, J. Wang, Y. Xiong, X. Li, S. Sun, W. Feng, Z. Liu, J. Shi, W. Ouyang _et al._ , “Hybrid task cascade for instance segmentation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4974–4983.
  * [39] S. Seferbekov, V. Iglovikov, A. Buslaev, and A. Shvets, “Feature pyramid network for multi-class land segmentation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2018, pp. 272–275.
  * [40] T. Kim, Y. Park, Y. Park, and I. H. Suh, “Acceleration of actor-critic deep reinforcement learning for visual grasping in clutter by state representation learning based on disentanglement of a raw input image,” _arXiv preprint arXiv:2002.11903_ , 2020.
  * [41] J. Mahler, M. Matl, V. Satish, M. Danielczuk, B. DeRose, S. McKinley, and K. Goldberg, “Learning ambidextrous robot grasping policies,” _Science Robotics_ , vol. 4, no. 26, 2019.
  * [42] C. Hazirbas, L. Ma, C. Domokos, and D. Cremers, “Fusenet: Incorporating depth into semantic segmentation via fusion-based cnn architecture,” in _Asian conference on computer vision_. Springer, 2016, pp. 213–228.
  * [43] S.-J. Park, K.-S. Hong, and S. Lee, “Rdfnet: Rgb-d multi-level residual feature fusion for indoor semantic segmentation,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 4980–4989.
  * [44] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [45] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” https://github.com/facebookresearch/detectron2, 2019.
  * [46] M. Zinkevich, M. Weimer, A. J. Smola, and L. Li, “Parallelized stochastic gradient descent.” in _NIPS_ , vol. 4, no. 1. Citeseer, 2010, p. 4.
  * [47] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in _European conference on computer vision_. Springer, 2016, pp. 21–37.
  * [48] S. Zakharov, B. Planche, Z. Wu, A. Hutter, H. Kosch, and S. Ilic, “Keep it unreal: Bridging the realism gap for 2.5 d recognition with geometry priors only,” in _2018 International Conference on 3D Vision (3DV)_. IEEE, 2018, pp. 1–11.
  * [49] T. Wu, S. Tang, R. Zhang, J. Cao, and Y. Zhang, “Cgnet: A light-weight context guided network for semantic segmentation,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 1169–1179, 2020.
  * [50] M. Denninger, M. Sundermeyer, D. Winkelbauer, Y. Zidan, D. Olefir, M. Elbadrawy, A. Lodhi, and H. Katam, “Blenderproc,” _arXiv preprint arXiv:1911.01911_ , 2019.
  * [51] A. Kasper, Z. Xue, and R. Dillmann, “The kit object models database: An object model database for object recognition, localization and manipulation in service robotics,” _The International Journal of Robotics Research_ , vol. 31, no. 8, pp. 927–934, 2012.
  * [52] A. Singh, J. Sha, K. S. Narayan, T. Achim, and P. Abbeel, “Bigbird: A large-scale 3d database of object instances,” in _2014 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2014, pp. 509–516.
  * [53] T. Hodaň, M. Sundermeyer, B. Drost, Y. Labbé, E. Brachmann, F. Michel, C. Rother, and J. Matas, “Bop challenge 2020 on 6d object localization,” in _European Conference on Computer Vision_. Springer, 2020, pp. 577–594.
  * [54] B. Calli, A. Singh, A. Walsman, S. Srinivasa, P. Abbeel, and A. M. Dollar, “The ycb object and model set: Towards common benchmarks for manipulation research,” in _2015 international conference on advanced robotics (ICAR)_. IEEE, 2015, pp. 510–517.
  * [55] A. Dave, P. Tokmakov, and D. Ramanan, “Towards segmenting anything that moves,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops_ , 2019, pp. 0–0.
  * [56] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _European conference on computer vision_. Springer, 2014, pp. 740–755.
  * [57] X. Wang, T. Kong, C. Shen, Y. Jiang, and L. Li, “Solo: Segmenting objects by locations,” in _European Conference on Computer Vision_. Springer, 2020, pp. 649–665.
  * [58] S. Ito and S. Kubota, “Point proposal based instance segmentation with rectangular masks for robot picking task,” in _Proceedings of the Asian Conference on Computer Vision_ , 2020.