ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 Vrije Universiteit
Amsterdam Amsterdam The Netherlands Vrije Universiteit Amsterdam Amsterdam The
Netherlands Vrije Universiteit Amsterdam Amsterdam The Netherlands

# Establishing Shared Query Understanding in an Open Multi-Agent System

Nikolaos Kondylidis<EMAIL_ADDRESS>,  Ilaria Tiddi<EMAIL_ADDRESS>and
Annette ten Teije<EMAIL_ADDRESS>
###### Abstract.

We propose a method that allows to develop shared understanding between two
agents for the purpose of performing a task that requires cooperation. Our
method focuses on efficiently establishing successful task-oriented
communication in an open multi-agent system, where the agents do not know
anything about each other and can only communicate via grounded interaction.
The method aims to assist researchers that work on human-machine interaction
or scenarios that require a human-in-the-loop, by defining interaction
restrictions and efficiency metrics. To that end, we point out the challenges
and limitations of such a (diverse) setup, while also restrictions and
requirements which aim to ensure that high task performance truthfully
reflects the extent to which the agents correctly understand each other.
Furthermore, we demonstrate a use-case where our method can be applied for the
task of cooperative query answering. We design the experiments by modifying an
established ontology alignment benchmark. In this example, the agents want to
query each other, while representing different databases, defined in their own
ontologies that contain different and incomplete knowledge. Grounded
interaction here has the form of examples that consists of common instances,
for which the agents are expected to have similar knowledge. Our experiments
demonstrate successful communication establishment under the required
restrictions, and compare different agent policies that aim to solve the task
in an efficient manner.

###### Key words and phrases:

Open Multi-Agent Systems; Task-oriented Communication Establishment;
Collaborative Query Answering

##  1\. Introduction

Establishing successful communication between a human and a machine is
challenging. It requires an a priori definition of all the potential scenarios
under which these agents will have to communicate. This is not always
possible, especially when designing autonomous systems. Another solution would
be for the human to understand the system’s operation and communicate
accordingly. This is also non trivial, as it is very challenging “to
understand, comprehend, and work with very large conceptual schemas” Villegas
Niño (2013).

The adaptive ability of a system to establishing successful communication with
humans in non-foreseen cases can substantially extend its (re-)usability. This
would allow for the system to learn new concepts or tasks with ad-hoc user
interaction. This is possible while not requiring the user to be familiar with
the particular system, or even be a domain expert. Communicating that via
natural language is not always possible, as it would require high levels of
natural language understanding and preferably in several languages. Instead,
we suggest that such an understanding can be approximated using only a few
examples of correct and wrong query results, provided by the user. Such an
ability would be particularly useful in the case where a person needs to query
multiple databases, without having to familiarize with their respective
schemas. For example, a new Ph.D. student wants to reach out to senior
researchers, i.e. people that have been members of a Program Committee of a
conference. The student knows which of the people in her group have been
members of such a committee and can use them to form examples to query
conference organisation databases, without having to familiarise with the
schema of each database. This study aims to put together a framework with
guidelines for designing communication experiments with a human-hybrid
application focus.

Different fields have studied how successful communication can be established
between agents. Studies from Ontology Alignment (OA) Euzenat et al. (2007),
attempt to establish translations between ontologies, allowing for the systems
to communicate their own concepts with each other. These approaches require
both systems to operate under formally defined ontologies and are too
inefficient to be applied in real time Besana et al. (2005). The problem has
also an overlap with the Open Multi-Agent Systems (OMAS) field, where agents
from a diverse population, that do not have an established communication
protocol, need to learn how to communicate, only via grounded interaction.
Similarly, language games Steels (2001) also study the establishment of
correct communication. Nevertheless, in these fields, the agents do not
actively attempt to communicate or explain a particular concept in an
efficient manner, but instead the context of each interaction is randomly
provided by the environment. Therefore, applications of such methods are not
able to represent restrictions that humans bring in the problem, i.e. not
having a formal ontology for each agent, nor aim to educate or be educated by
a human about a particular topic in an efficient manner.

Our research question is whether we can put together such restrictions and
efficiency aspects in a framework. This would allow the development and
evaluation of intelligent systems that can learn to communicate with humans in
an ad-hoc setting. Furthermore, to minimize hardly acquired human input, this
framework should allow researchers to indirectly estimate their method’s
efficiency, according to application-specific metrics that they can define,
before running experiments with humans.

The framework describes how two agents and an environment interact in a cycle.
The agents need to cooperate in order to perform a task on the environment.
Since at least one of the agents does not operate under a formally defined
ontology, we cannot simply compare its interpretation with the intended
interpretation and evaluate communication, but can only indirectly evaluate it
based on the performance of a downstream task. Neither agent can perform the
task alone, so that cooperation is required and task performance reliably
reflects correct understanding among the agents. In more detail, one agent
called “Teacher” can understand the task that needs to be performed but cannot
act towards it. Instead, it can only provide grounded examples to the other
agent, the “Student”, who needs to understand the task and perform it. The
environment is able to evaluate the Student’s action, which indirectly
evaluates the Student’s understanding of the Teacher. It is nevertheless
important that the environment’s evaluation is only presented to the Teacher,
so that the Student alone cannot figure out the task over time without the
Teacher’s input. This framework allows to test and compare different Teacher
and Student policies, namely how they should teach or learn a new concept in
terms of both task performance and efficiency (e.g. number of interaction
cycles, cognitive load, or memory demands).

We applied this framework on the scenario where the two agents need to
collectively answer a query. Specifically, we utilize an OA dataset that
provides common instances that can be used for grounded communication and
concept alignments that allow the Environment to evaluate whether the two
agents are talking about the same thing and correctly understand each other.
Additionally, the different ontologies contain overlapping and incomplete
data, so neither agent can alone correctly answer the query successfully, and
task performance is measured in terms of traditional information retrieval.
Efficiency is principally measured in terms of number of interactions or
examples that the agents exchange. Furthermore, we consider cognitive
limitations and ask the Teacher to only provide one relevant and one
irrelevant instance within each example. Last but not least, we also attempt
to represent the memory demands of the agent policies that we put forward, by
defining episodic memory and working memory sizes in number of memorized
episodes and variables used respectively. Please note that the cognitive load
metrics used are only intended as an example of how one could define its own
case-specific metrics to evaluate shared understanding using our framework and
are not meant as a main reference to measure cognitive load. Our experiments
display a use-case application of our framework that allows us to evaluate
teaching and learning policies that can be applied in an OMAS. The applied
communication restrictions and efficiency metrics aim to represent that these
policies can also be applied when the other agent is a human, while taking
into account their estimated cognitive demand. The experiments show that it is
possible for the agents to be well understood in the described setting, using
only a very limited number of interactions. In addition, the results suggest
that a robust query understanding method can be expected to perform better in
a scenario where the agents have incomplete knowledge of their environment.
Finally, the experiments on the applied use-case suggest that the examples
which seem to be more informative are more probable to be interpreted
differently by the two agents.

In this work, and specifically in Section 3, we put together i) the challenges
that need to be considered when developing human-machine communication and ii)
suggest guidelines on how to computationally evaluate understanding
performance but also efficiency metrics into a framework that can foster
research around on-the-fly human-machine communication. Additionally, Section
4 presents a use-case of applying this framework on the task of cooperative
query answering, where we suggest and evaluate policy agents that aim to
either teach or learn query-concepts to each other in an efficient manner. The
queries are about roles of conference participants, i.e. authors, reviewers,
program committee members, etc. Our experiments indicate that successful
communication in such a setting is possible using only a small number of
interactions.

##  2\. Related Work

Several research fields are dealing with different aspects of communication
establishment among agents.

###  2.1. Ontology Alignment

The field of Ontology Alignment studies how systems with different formal
representations of their knowledge can communicate successfully. An OA method
traditionally takes as input a pair of ontologies and suggests concept or
instance alignments Euzenat et al. (2007, 2011) among them. These alignments
are used as a basis for the two systems to translate knowledge between them,
allowing for successful communication. Most OA studies are very hard to be
applied in our scenario. Firstly, most OA methods require complete access to
both ontologies, which might not be possible to extract from humans. Secondly,
the evaluation of suggested OA methods is usually performed by comparing the
produced alignments with a set of gold reference alignments, which can be very
expensive to get. Instead, we suggest the evaluation to be indirectly
reflected on the performance of a task that requires agent collaboration. Last
but not least, the complexity of existing methods makes their real time
application almost impossible Besana et al. (2005); Mcneill and Bundy (2007);
Atencia and Schorlemmer (2012). The hybrid aim of our framework requires the
communication establishment methods to be evaluated in the form of trade-off
between efficiency and task achievement, i.e. precision and recall), instead
of only focusing on the latter.

#### Incremental OA Through Interaction

Other studies do not take a holistic approach that suggests all possible
alignments in one go. Instead, the ontologies are used by agents that aim to
establish or to refine existing alignments through agent interaction Laera et
al. (2007); Payne and Tamma (2015); Euzenat (2017b, a); Aberer et al. (2003);
Anslow and Rovatsos (2015); Besana et al. (2005). In some studies, the agents
engage in formal negotiation procedures, the content of which is concept
alignments Laera et al. (2007); Payne and Tamma (2015). The agents have
(limited) access to each other’s ontologies as to subjectively propose, reject
or rebut about them, until they converge to a set of commonly agreed
alignments. Contrary to our framework, the agents do not strategically decide
their interactions as to efficiently achieve a concrete communication outcome,
while also they evaluate communication according to reference alignments
instead of some downstream task performance. In other studies Euzenat (2017b,
a) the agents use properties from their ontology to describe objects to one
another. Eventually, they form several property alignments. In contrast, in
our study, the same agent keeps on providing examples to efficiently explain
one particular property to another agent. Furthermore, the examples consist of
both relevant and non-relevant objects to narrow down the possible property
interpretation more efficiently. In Aberer et al. (2003), a population of
agents that are grouped to represent databases in different ontologies are
asked to collectively answer queries. The agents spread the queries and their
answers around the rest of the population using provided concept alignments in
a gossip-like way. When an agent receives again a query that it had forwarded
in the past, it evaluates its translations or even replaces them, based on the
translations or answers of agents that have meanwhile propagated that query.
Such an approach evaluates communication according to provided alignments and
not using a task, while requiring very large communication volumes that humans
could not support. In Anslow and Rovatsos (2015), a population of agents that
exist in a shared environment need to exchange information regarding
environmental observations. Similar to our study, their evaluation is taking
place with respect to a downstream task, while they also measure communication
efficiency in terms of communicated data volume. However, their work focuses
on performing instance matching provided a shared schema and therefore cannot
be applied when some agents are humans, as they are not expected to use the
same schema. Last but not least, research has also been performed on agents
that focus on aligning only what is necessary for the current interaction,
aiming to allow an efficient real time application Besana et al. (2005).
Additionally, the agents store “interaction contexts”, in order to reduce the
interpretation space of future interactions based on its context. In contrast
to us,  the authors do not account for minimizing communication volume
restrictions when some agents are humans. Alignments are generated following
traditional structural/lexical OA metrics by comparing parts of the
ontologies.

###  2.2. Agent Communication Establishment

Here, we present studies on communication establishment that can be applied on
different agents, regardless of the (in-)formal system each agent operates
under.

#### Communication Establishment in Open Multi-Agent Systems

O-MAS focuses on agent interaction in dynamic populations of agents.
Computationally this means that neither the agents’ system, nor the task that
they will need to perform, can be decided a priori. Therefore, the agents need
to learn how to communicate while making the least amount of assumptions
regarding other agents. To that end, communication or symbol alignments is
established according to environment observations, that is grounded
communication.

In Atencia and Schorlemmer (2012), the agents engage in a conversation, which
both interpret according to their own automaton. Some of the communication
language is shared, and the rest of the symbols are aligned after enough
interactions. The communication is considered to be successful if the agents
end the conversation at the same time, which is an observable act and inline
with our approach, but ignores the actual outcome. Our framework requires the
agents to perform an action, i.e. answer a query, to better estimate the
levels of correct communication. Experiments of that study were performed on
synthetically generated automata.

In Rovatsos et al. (2003), a set of agents learn how to interact with each
other in order to achieve potentially conflicting goals. The communicated
symbols are interpreted in terms of the agent’s observable actions that
follow. Agents decide what to communicate aiming to decrease interpretation
entropy, but can also misuse a word as an attempt to take advantage of other
agents. In this approach, agent communication is not explicitly interpreted,
but indirectly affects the agent behavior, via training a Markov Decision
Process that translates communication events into actions, based on
environmental rewards. While this study does not focus on communication
establishment, it follows our framework idea that agent learning should be
based on indirect environmental rewards.

#### Language Games

Language games Steels (2001) are an approach to establish successful
communication in an OMAS only via grounded communication. In this setup, a
population of agents engage in pairs to play grounded referential games. In
these games, the agents develop their own vocabulary, that is interpreted in
terms of object characteristics and is used to refer to a particular object in
a context. After enough games, the population of agents converges to having
shared symbol interpretations, allowing them to always communicate
successfully. This work has been extended to scenarios where one agent teaches
the other one how to interpret natural language questions regarding a commonly
perceived scene of objects Nevens et al. (2022). Additionally, there has also
been a demonstration on how a human can engage with a computer to teach it a
concept, by constructing examples using physical world objects Nevens et al.
(2019). These studies have a different focus compared to our work. They aim to
replicate the humane ability of developing a language through de-centralized
peer-to-peer interactions. The main aim of these studies is to study the
evolution of natural languages, by replicating the process. In more detail,
the agents interact in multiple random scenarios of having to refer to an
object in their surrounding using invented words. Eventually they converge to
a commonly interpreted vocabulary that allows them to successfully communicate
in any scenario. On the other hand, our framework is designed for learning to
communicate one specific concept, as efficiently as possible, by designing
interaction contexts, i.e. the teaching examples, accordingly.

#### Interactive Reinforcement Learning

There have also been some studies that do not aim to establish human-computer
communication, but use a human in the loop to create more efficient
Reinforcement Learning (RL) methods. RL studies categories of problems where
the reward signal is sparse and is only provided to the agent after multiple
decisions. Such algorithms are very computationally expensive as they usually
require a lot of action-reward exploration. Interactive RL aims to incorporate
human input in that process, in order to make the convergence of such
approaches faster Cruz and Igarashi (2021). This way, interactive RL studies
focus on the downstream task, and use human input as a way to improve their
performance.

##  3\. A Framework for Developing and Evaluating Human-Hybrid Understanding

This section presents our framework which provides guidelines on designing and
evaluating communication establishment policies in an OMAS setting, including
human-computer scenarios. Guidelines are either in the form of restrictions,
or by defining efficiency goals that should be optimized.  Our framework is
designed in an abstract and modular way, allowing the experiment designer to
easily define different humane aspects that best fit their scenario. We define
understanding as the product of the interpretation process. For example, two
agents have a shared understanding of a query when they interpret it using
equivalent classes in their own ontologies.

Figure 1.  The task-oriented information flow cycle for shared understanding.
One agent, i.e. the Teacher, understands the task that has to be performed,
while the other agent i.e. the Student, does not, while the latter is the only
one who can perform the task. The agents engage in an iterative loop: 1.
Grounded Example: the Teacher attempts to explain the task at hand to the
Student providing an example; 2. Action: the Student follows by attempting to
perform the task; 3. Understanding Evaluation: the Teacher is informed by the
Environment regarding the Student’s performance on the task, which reflects
its understanding of the task.

#### The Process of Defining the Problem Computationally

Our framework proposes a way of establishing successful understanding between
two agents that is indirectly evaluated with respect to a downstream task. The
application of our framework follows a process of three steps so that it can
be computationally studied.

First, one needs to define what consists a grounded interaction in their
scenario. These are objects that both agents know and can refer to during an
interaction, while each of them has their own way of perceiving them.
Therefore, a set of common objects must be identified among the agents. In our
example, these are the researchers of the student’s group.

Second, it is important that the downstream task cannot be solved by either
agent independently and that there is no conflict of interests. To that end,
the agents cannot have complete information about the environment, requiring
input from both of them to successfully solve the downstream task. As a
consequence, the agents can either be designed to not be aware of all the
objects of the environment or at least not to know all their properties. In
our example, while the student can find all researchers, she does not know who
are senior researchers. At the same time, the database agent does not know
what the student is looking for.

Third, the cognitive load of the involved agents should be somehow
computationally approximated so that it can then be minimized. This should be
defined by the researcher, having in mind the target group of the end user
that will use their application. It can be in the form of number of
interactions, or additionally Episodic or Working memory demands, depending on
how we assume the human to behave when interacting with the computer.

Once we have these, we suggest that the agents interact in a task-oriented
loop that allows for incremental shared understanding development and its
evaluation. Figure 1 illustrates the abstract share understanding
establishment cycle as described by our framework, while Figure 2 instantiates
it for our specific example use-case, as described in Section 4. Initially,
one agent, i.e. the Ph.D. student, is provided with a task from the
environment, i.e. find senior researchers. The task can also come from the
Teacher, but only the environment can fully evaluate its completion. Then, the
agents engage in a 3-step cycle. In the first step, the Teacher, i.e. the
Ph.D. student, provides some objects as examples using people from her group.
In the second step, the Student, i.e. agent database, provides what it
currently interprets as relevant objects from its complete set of objects,
i.e. researchers. In the third step, the Teacher observes the Student’s object
selection, i.e. list of assumed senior researchers, and the Environment, i.e.
the supervisors, acts as an object selection evaluation. By repeating this
cycle, the evaluation, i.e. query performance, should improve over time.

###  3.1. The Process of Defining the Problem Computationally

Establishing successful communication between agents can be challenging
because they are designed to have different goals or beliefs. These aspects
shape how the agent perceives the world and give them a potentially unique
perspective. A simple way to computationally define different perspectives is
by assuming that the agents are operating using different ontologies. Provided
that these agents exist in a similar or the same environment, we expect their
ontologies to have some overlap both in terms of concepts and knowledge, while
also their ontologies are expected to be incomplete. Following, we will
present how we apply the three steps of defining our problem computationally
for a scenario that agents operate under different ontologies.

#### Step 1: Defining Communication Restrictions.

Following traditional OMAS restrictions, the agents share limited to none
common language and can only communicate via grounded interaction, which for
example can have the form of referring to common world objects of their shared
surrounding. Besides being a good fit for an OMAS setting, it is inspired by
the Language Games studies Steels (2001), which are an attempt to mimic how a
population of humans learn to interpret a vocabulary similarly. Nevertheless,
they have in mind the task that needs to be performed and are aware of
possible communication action interpretations. Additionally, given the
participation of human agents, the communicated examples should be concise so
that their comprehension is not very laborsome.

####  Step 2: Defining Cooperation Restrictions.

It is very challenging to evaluate communication in an OMAS setup when some of
the agents are humans. One cannot simply compare the interpretation of the
receiver and the intended interpretation of the sender, since there is no
agent that understands both system representations. Therefore, we suggest that
the agents need to perform a task on the observable environment, that requires
their cooperation. This way the environment can act as a communication
evaluator, since task performance depends on cooperation which requires
successful communication. In order to make sure that this is the case, it is
important that neither agent can perform the task by independently interacting
with the environment. Finally, we assume that there is no conflict of interest
among the agents, so that they have no reason to misuse communication signals
for their own interest.

####  Step 3: Defining Efficiency Aspects

Since some involved agents are humans, it is important to have efficient
interactions. To that end, efficiency must be somehow defined, so that its
evaluation can at least be approximated. While these definitions depend on the
specific application, we suggest two type of efficiency evaluations to be
taken into account. First, it is important to minimize interaction time, which
can be approximated by the number of interactions needed. Second, the agents’
effort during the complete sequence of interactions should also be taken into
account, until they quit or perform the task successfully. This can for
example be represented roughly in terms of episodic and working memory
demands, as this can be approximated by the number of examples that the agents
had to memorize or by the number of variables that they need to keep track of,
respectively.

##  4\. An Applied Use Case on Artificial Agents

In this section, we present an example application of our Framework in a
scenario where two agents query each other about conference participants and
their roles. Although we apply it on artificial agents, they behave as if they
interact with humans, respecting all communication and efficiency
restrictions.

#### An Example Use-Case

We consider a human and an artificial agent (representing a database) querying
each other. Whether the human wants to query the database, or the database
agent aims to extend its knowledge, the aim is to allow knowledge exchange
without the human having to learn the schema of the database. Let us assume a
new Ph.D. student who want to reach out to a broader circle of senior
researchers. She knows some researchers from her group, and is able to
distinguish who is senior and who is not. While there are several conference
organisation databases she can query, it is hard for her to define what a
senior researcher is, let alone to form such a concept under the different
schemas of all the databases. Instead, she can use the people of her group to
form examples of senior and junior researchers. She provides such examples to
the artificial agent, who tries to understand the query and returns results
based on its knowledge. Since the student does not know who are the senior
researchers, she is unable to evaluate the results herself. She can still ask
her supervisors to evaluate the results, as this takes less of their time
compared to coming up with the list themselves. In this case, the student acts
as a Teacher, the database agent as a Student and the supervisors as the
Environment.

###  4.1. Applying Our Framework

In this section, we will go through the three steps of defining our framework
computationally, as described in Section 3.1.

####  Step 1: Defining Communication Restrictions

Communicating over common objects is achieved by referring to researchers that
both agents, i.e. the Ph.D. student and the database agent, are aware of.
Furthermore, concise interaction is achieved by asking the Ph.D. student to
only provide examples that consist of one junior and one senior researcher at
a time.

####  Step 2: Defining Cooperation Restrictions

Successful communication and cooperation is required in our example. The
student cannot find senior researchers alone, as she would have to waste a lot
of her supervisors’ time. At the same time, the database agent alone cannot
automatically be updated about new roles of researchers in conferences. It is
also clear why there is no conflict of interest, as neither agent has any
incentive to mislead the other.

#### Step 3: Defining Efficiency Aspects

Interaction time is measured by the number of examples exchanged between the
agents and cognitive load is measured based on the estimated memory volume
needs of the participating agents (cf. Section 5.2 for details).

Figure 2.  The shared understanding cycle instantiated for our example. Step
(1) Provide example: the Ph.D. student (acting as Teacher) wants to query the
agent database (acting as Student) about senior researchers
(“cmt:ProgramCommitteeMember”). Examples (URIs for senior and junior
researcher) both the Ph.D. student and the database agent are aware of those
common objects. Step (2) Forward Query: the agent database needs to interpret
the example and apply its Student policy to update its current estimated query
representation, and forward the query results from its database to the
supervisors (Environment). Step (3) Return Query Performance: evaluation in
terms of Precision and Recall, and inform their student how well the agent
database understands her query. Figure 3.  Example of how two agents can
perceive the same grounded example (URIs) differently according to their
ontologies. The URIs are grounded: both ontologies refer to the same
“entities”.

###  4.2. Task Definition

The agent interaction and the task they need to solve are presented in Figure
2. The Teacher needs to explain the query to the Student who can then answer
it. The Teacher’s knowledge is artificially represented by another database,
i.e. the cmt ontology in our example. The Student’s database includes
knowledge of the confOf ontology. Communication has the form of examples of
world objects, i.e. researchers, that both ontologies are aware of. The
queries are always about world objects that share some properties.
Furthermore, the agents are not aware of all the objects, nor of all the
properties of the objects that they know. Thus, only the Environment, i.e. the
supervisors, is up to date and knows the complete answer set of the query. Our
task focuses on evaluating the answers of the Student. The evaluation of the
Student’s answers is not provided to the Student, as this could allow the
Student to understand the query alone and make the agent communication
dispensable.

#### Subjective Example Interpretation

While the examples consist of objects that both agents are aware of and the
identity of the relevant object is known, the examples are perceived
differently by each agent, as presented in Figure 3. The agents independently
use their own databases to perceive the objects, i.e. retrieve their
properties. Then, they interpret the examples by forming three property sets.
The Positive and Negative property sets ($P_{ex}$ and $N_{ex}$) of an example
($ex$) are the ones that consist of properties only owned by the relevant and
irrelevant object respectively. Additionally, the agents can also calculate
the set of Common properties ($C_{ex}$) of the two objects. The Teacher, i.e.
Ph.D. student, communicates examples that contain the property it wants to
explain in their Positive property set. In case they example interpretation of
the Student, i.e. database agent, has an empty Positive property set, then
this example is unclear for the Student. A clear example, according to the
Student, does not necessarily mean that it was understood as the Teacher
intended. This would be the case if the same communicated example presented in
Figure 3 was used to explain the concept “cmt:Chairman”, or “cmt:Reviewer”.
Therefore, due to different databases, the Teacher might need to provide
several examples until the Student can fairly approximate the query at hand.

###  4.3. Teacher Policies

Provided the property of the query, the Teacher creates an example pool, with
all examples i.e. object pairs, where the query property is contained in their
Positive property set. The Teacher has to decide which example to provide
next. This is performed by the Teacher’s policy which scores the examples in
that pool, based on the history of examples and the Student’s feedback. The
Student’s feedback is used to communicate when an example was unclear, i.e.
has an empty Positive property set according to the Student. The Teacher
cannot foresee these cases, but can instead memorize these examples and not
present them again by removing them from the example pool.

#### Random Teacher Policy (Euzenat (2017a))

One option is for the agent to follow a random teaching policy, where examples
are randomly sampled from the pool, with replacement. This agent policy is an
adaptation of the proposed method in Euzenat (2017a), for our task, where the
objects that the agents describe is chosen randomly.

#### Property-Based Teacher Policy

This policy increases the score of an example according to the properties that
it aims to exclude from query interpretation candidates. We define the weight
($w_{p}$) of each property $p$ as the number of objects that have this
property, compared to the total number of objects in the database (its
normalized frequency). Then, we define the score of each example
($score_{e}x$) as:

$score_{ex}=\sum^{\forall p\in(N_{ex}\cup C_{ex})}w_{p}-\sum^{\forall p\in
P_{ex}}w_{p}$

###  4.4. Student Policies

The Student’s policy provides instructions on how to translate the incoming
stream of examples to an estimated query representation, which is then used to
provide results to the Environment. It is common knowledge that the query is
about a set of objects that share some property. Thus, the estimated query
representation consists of a set of property-score pairs. The Student policies
only make use of the Positive and Common property sets of an example. We will
now present the two policies that we are comparing.

#### Logic-Based Student Policy

This policy requires the Student to memorize the provided examples, and then
apply Formal Concept Analysis (FCA) Ganter and Wille (2012) to deduce which
properties are implied by the query. FCA can be used to derive property
relations, provided a set of objects and their relations. Therefore, we treat
each example as an individual object, and the Positive property set of that
episode ($P_{ex}$), as the properties of this object. The Student memorizes a
set of unique Positive property sets of examples. The query is also
represented as a pseudo property of these example objects. This way, FCA
provides us with relations between the query and the properties of the agent’s
ontology. Only the properties that can be induced from the query pseudo
property are found on the estimated query representation set, and they all
have the same score, so that they affect the produced results in the same way.

#### Frequency-Based Student Policy

The Frequency-based policy does not require the student to memorize any
example, but only to maintain and update scores per observed property.
Specifically, the agent starts with an empty set of property-score pairs, as
its estimated query representation. For every new example, the Student makes
use of its Positive and Common property sets. In case any of these properties
is not in the estimated query representation, they are added with an initial
score of 0. Then, the score of each property on the Positive or Common
property sets of the example is increased or decreased by 1, respectively.

#### Providing Query Results

When asked, the Student uses its estimated query representation to rank all
objects in its database and provides them to the Environment. The score of
each object is equal to the summation of the scores of its properties, as they
are calculated in the estimated query representation. The agent only returns
objects with positive scores.

##  5\. Experiments

In this section, we present the experiments that we performed. Our code is
publicly
available111https://github.com/kondilidisn/shared_query_understanding,
ensuring reproducibility of our work.

###  5.1. Dataset

For our experiments, we used the dataset of the Ontology Alignment for Query
Answering (OA4QA) track Solimando et al. (2014). The dataset contains 7
populated ontologies, that have on average 817 instances belonging to 17
classes. The ontologies describe an overlapping set of conference venues, with
information such as people’s role, types of submitted papers, etc. About 259
class alignments are present over the 21 ontology pairs. This dataset is a
populated version of the popular dataset used on the Conference track of the
well established Ontology Alignment Evaluation
Initiative222http://oaei.ontologymatching.org/2022/conference/index.html,
although we only use the instances and their classes.

#### Utilizing the Dataset

We only focus on the instances and their classes from each ontology, that we
use as world objects and their properties respectively. This dataset is a very
good fit for our scenario, as it contains several class alignments. These can
be used as equivalent object properties across agent databases, over which we
can perform query understanding experiments. Furthermore, since the ontologies
describe a set of overlapping venues, they contain different and incomplete
knowledge about their environment. This way, we ensure that cooperation is
required, since no agent can alone provide all answers in any query
understanding experiments, as the complete answer set is always distributed
among both agents.

#### Crafting Query Understanding Experiments

Every provided class alignment between two ontologies can be turned into a
query understanding experiment. Specifically, each alignment can generate two
experiments, since the agent that represents one of the two ontologies can
either participate as a Teacher or as a Student. In order for the alignment to
be put to use, both ontologies need to have at least one instance of their
corresponding aligned class in the set of common instances between the two
ontologies.

#### The Simple Dataset

As previously described, the number of common instances across ontology pairs
has a direct effect of how many of the provided class alignments can be used
as query understanding experiments. Instance alignment across ontologies is
not a problem that we aim to address in this paper. Instead, we aim to
identify common instances across ontologies, and create two different datasets
accordingly. In the first dataset, denoted as Simple, two instances are the
same only if they have exactly the same Unique Resource Identifier (URI). This
dataset has on average 303 common instances across pairs of ontologies, and
can be used for running 126 experiments.

#### The Extended Dataset

The second dataset, denoted as Extended, extends the first dataset by making
three more assumptions on whether two instances are the same across
ontologies. The first extra assumption suggests that two instances with the
same name but different namespace are the same. The second extra assumption
suggests that two instances are the same, if the are related in the same way,
i.e. equivalent relation, to another instance that is known to be the same.
This would be formalized as o1:x == o2:y if (common_entity, common_relation,
o1:x) AND (common_entity, common_relation, o2:y). Last but not least, we also
mined some instance alignments by executing complex queries. For example, in
one ontology, the relation o1:writes can connect a o1:Person with either a
o1:Paper, or with a o1:Review. In the other ontology, o2:has_written only
relates o2:Person with o2:Paper. In this case, we first retrieved all
o1:Person that were related with instance o1:X, with the relation o1:writes.
Then, we filtered out all o1:X that were not o1:Paper, and finally applied our
second assumption as described before. This dataset has 482 common instances
across ontology pairs on average, and allowed the execution of 226 different
experiments.

#### Aggregating Evaluations Over Multiple Queries and Experiments

Each experiment represents the behavior of the combination of Teacher’s and
Student’s policy for a specific dataset. This is calculated by averaging the
recorded evaluation metric values over all the query understanding experiments
that can be performed on that dataset. Additionally, some agent policies are
non-deterministic, which can be the case because scoring ties are resolved
randomly. For this reason, we repeat every experiment of a specific query 10
times, and report average values of the evaluation metrics.

###  5.2. Evaluation Metrics

Our evaluation focuses both on how well the agents understand each other, i.e.
reflected by the task performance, while also the efficiency costs of each
approach.

#### Task Performance

The task that the agents are trying to collectively solve is query answering.
Therefore, their performance is measured in terms of traditional information
retrieval terms, i.e. Precision and Recall.

#### Efficiency Costs

The interaction time is measured as the number of examples that were
communicated between the agents, i.e. #examples. Furthermore, we use the
notions of Episodic Memory, and Working Memory, to approximate the agents’
cognitive effort throughout the complete sequence of interactions. The
Episodic memory is defined as the number of episodes that the agent has
memorized. These are the unclear examples for the Teacher and the clear
examples for the Logic-based Student. The Working memory is equal to the
number of variables that the agent policy is using in order to operate, i.e.
the property scores. The terms Episodic and Working memory here are used as an
example of how one can measure cognitive effort.

###  5.3. Experiment Results and Discussion

Figure 4 depicts how the suggested agent policies behave in terms of task
performance, with respect to the number of examples exchanged. Recall that the
evaluation takes place on the query results of the Student to the environment,
as a way of indirectly measuring how well the Student understands the
Teacher’s query. An important takeaway is that in any combination of selected
policies, the agents achieve more than 80% Precision and around 90% Recall,
within only a handful of provided examples. Nevertheless, it is interesting to
note that when the Student is following the Logic-based policy, Recall starts
to decline after only a few examples. This suggests that the Logic-based
policy is not robust enough for scenarios with ontologies that contain
incomplete and partial knowledge. Similar behavior is also observed on the
Precision of the Logic-based Student policies, but only on the small dataset.
Furthermore, when comparing the applications of Frequency-based Student
policies, we can see that a Teacher that applies the Property-based policy
helps achieving a good agent understanding in fewer examples. Moreover, it is
also interesting to note that only in the large dataset, a Student following a
Frequency-based policy and taught by a Teacher with Random policy, is under-
performing in terms of Precision compared to all other policy combinations.
Besides, all policy combinations achieve higher Precision on the extended
dataset. Additionally, the Frequency-based Student policies show a drop of
Recall on the Extended dataset.

Figure 4.  Performance evaluation of the proposed agent policies on the two
datasets. The legends denote the Teacher and Student applied policy
respectively, separated by ‘-’.

#### Efficiency Metrics Performance

When the Student applies the Frequency-based policy, its working memory is
around 5,5 and 4,6 on the small and the extended dataset respectively, and
equal to 0 for the Logic-based policy. This number reflects the average number
of properties on the estimated query representation. It seems that on average,
there are less potential candidate properties over which the examples are
interpreted on the Extended dataset, which also explains the higher average
performance of all experiments there. Complementary, the Student only uses its
Episodic memory when following the Logic-based policy, in which case the agent
memorizes around 1.6% examples on average in all experiments. This suggests
that there are equally few distinct useful examples to memorize their
properties, across all experiments. Last but not least, the Episodic memory of
the Teacher, which reflects the number of unclear examples found, is much
smaller on the extended dataset, ranging from 2% to 4%, compared to the Simple
dataset where it ranges from 9% to 12%. This suggests that maybe the knowledge
overlap across the ontologies is bigger on the extended dataset on average.
Moreover, this shows that the examples which are expected to be more
informative are more probable to be perceived differently by the two agents in
our use-case. Additionally, when the Teacher is following the Property-based
policy, it ends up memorizing on average around 2% to 3% more unclear
examples. One can therefore say that the Teacher is more likely to select an
example that contains instances with different information across ontologies,
when attempting to find more informative examples.

#### Discussion

The experiments exhibit that our framework can be applied for incrementally
establishing a shared understanding between the agents. In more detail, it is
shown that a few concise examples are enough for the agents to develop a
sufficiently good enough understanding of each other. Moreover, it seems that
the cognitive load, i.e. Episodic and Working memory demands, were not too
high, according to our example estimations.

##  6\. Conclusion and Future Work

We have described a framework that can assist researchers in developing agent
policies that establish successful communication in an OMAS setting, like in a
human-hybrid scenario. Additionally, we provide an application example the
framework on a collaborative query answering task. Our experiments display
satisfactory levels of communication for the task at hand, while doing so in a
very small number of interactions.

There are several ways to extend the presented study.  First, we are already
working on demonstrating the generalizability of the framework by applying it
in different studies of communication establishment including most studies
presented in our related work. Second, we will apply the framework on more
challenging tasks, which will require improving the presented agent policies
with particular focus on using both the Student’s feedback signal and its
current level of understanding. Such tasks can either be done by focusing on
collaborative query answering using larger ontologies with complex alignments,
or use tasks that include actual interaction with an environment besides
information exchange. Third, we aim to focus on the human participant aspect
of our framework. We can for example use relevant literature to apply more
sophisticated methods to estimate cognitive load, or involve human
participants and ask them to self-report the overall effort required for one
interaction or the complete experiment. Besides improving the estimation of
human participants’ effort, we plan designing artificial agents that take into
account the behavior of a target group of end-users, requiring for example the
design of robust agent policies that can interact with irrational human input.

### Acknowledgments

This work was supported by “MUHAI - Meaning and Understanding in Human-centric
Artificial Intelligence” project, funded by the European Union’s Horizon 2020
research and innovation program under grant agreement No 951846. We also want
to heartily thank prof. Frank van Harmelen for his support, guidance and for
being a continuous source of inspiration.

## References

  * (1)
  * Aberer et al. (2003) Karl Aberer, Philippe Cudré-Mauroux, and Manfred Hauswirth. 2003\.  Start making sense: The Chatty Web approach for global semantic agreements.  _Journal of Web Semantics_ 1, 1 (Dec. 2003), 89–114.  https://doi.org/10.1016/j.websem.2003.09.001
  * Anslow and Rovatsos (2015) Michael Anslow and Michael Rovatsos. 2015.  Aligning Experientially Grounded Ontologies Using Language Games. 15–31.  https://doi.org/10.1007/978-3-319-28702-7_2
  * Atencia and Schorlemmer (2012) Manuel Atencia and Marco Schorlemmer. 2012.  An interaction-based approach to semantic alignment.  _Journal of Web Semantics_ 12-13 (April 2012), 131–147.  https://doi.org/10.1016/j.websem.2011.12.001
  * Besana et al. (2005) Paolo Besana, Dave Robertson, and Michael Rovatsos. 2005\.  Exploiting interaction contexts in P2P ontology mapping.. In _P2PKM_.
  * Cruz and Igarashi (2021) Christian Arzate Cruz and Takeo Igarashi. 2021.  A Survey on Interactive Reinforcement Learning: Design Principles and Open Challenges.  _CoRR_ abs/2105.12949 (2021).  arXiv:2105.12949 https://arxiv.org/abs/2105.12949
  * Euzenat (2017a) Jérôme Euzenat. 2017a.  Crafting Ontology Alignments from Scratch Through Agent Communication.  In _PRIMA 2017: Principles and Practice of Multi-Agent Systems_ , Bo An, Ana Bazzan, João Leite, Serena Villata, and Leendert van der Torre (Eds.). Vol. 10621. Springer International Publishing, 245–262.  Series Title: Lecture Notes in Computer Science.
  * Euzenat (2017b) Jérôme Euzenat. 2017b.  Interaction-based ontology alignment repair with expansion and relaxation. In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence_. International Joint Conferences on Artificial Intelligence Organization, 185–191.
  * Euzenat et al. (2011) Jérôme Euzenat, Christian Meilicke, Heiner Stuckenschmidt, Pavel Shvaiko, and Cássia Trojahn. 2011.  Ontology alignment evaluation initiative: six years of experience.  In _Journal on data semantics XV_. Springer, 158–192.
  * Euzenat et al. (2007) Jérôme Euzenat, Pavel Shvaiko, et al. 2007\.  _Ontology matching_. Vol. 18.  Springer.
  * Ganter and Wille (2012) Bernhard Ganter and Rudolf Wille. 2012.  _Formal concept analysis: mathematical foundations_.  Springer Science & Business Media.
  * Laera et al. (2007) Loredana Laera, Ian Blacoe, Valentina Tamma, Terry Payne, Jerôme Euzenat, and Trevor Bench-Capon. 2007.  Argumentation over ontology correspondences in MAS. In _Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems - AAMAS ’07_. ACM Press, Honolulu, Hawaii, 1\.
  * Mcneill and Bundy (2007) Fiona Mcneill and Alan Bundy. 2007.  Dynamic, Automatic, First-Order Ontology repair by Diagnosis of Failed Plan Execution.  _Int. J. Semantic Web Inf. Syst._ 3 (July 2007), 1–35.  https://doi.org/10.4018/jswis.2007070101
  * Nevens et al. (2022) Jens Nevens, Jonas Doumen, Paul Van Eecke, and Katrien Beuls. 2022.  Language Acquisition through Intention Reading and Pattern Finding. In _Proceedings of the 29th International Conference on Computational Linguistics_. International Committee on Computational Linguistics, Gyeongju, Republic of Korea, 15–25.
  * Nevens et al. (2019) Jens Nevens, Paul Van Eecke, and Katrien Beuls. 2019\.  Interactive Learning of Grounded Concepts.. In _BNAIC/BENELEARN_.
  * Payne and Tamma (2015) Terry R. Payne and Valentina Tamma. 2015.  Using Preferences in Negotiations over Ontological Correspondences.  In _PRIMA 2015: Principles and Practice of Multi-Agent Systems_ , Qingliang Chen, Paolo Torroni, Serena Villata, Jane Hsu, and Andrea Omicini (Eds.). Vol. 9387. Springer International Publishing, 319–334.
  * Rovatsos et al. (2003) Michael Rovatsos, Matthias Nickles, and Gerhard Weiss. 2003\.  Interaction is Meaning: A New Model for Communication in Open Systems.  _Proceedings of the Interantional Conference on Autonomous Agents_ 2 (July 2003).  https://doi.org/10.1145/860575.860661
  * Solimando et al. (2014) Alessandro Solimando, Ernesto Jiménez-Ruiz, and Christoph Pinkel. 2014.  Evaluating Ontology Alignment Systems in Query Answering Tasks.. In _ISWC (Posters & Demos)_. 301–304.
  * Steels (2001) L. Steels. 2001\.  Language games for autonomous robots.  _IEEE Intelligent Systems_ 16, 5 (Sept. 2001), 16–22.  https://doi.org/10.1109/MIS.2001.956077 Conference Name: IEEE Intelligent Systems.
  * Villegas Niño (2013) Antonio Villegas Niño. 2013\.  A filtering engine for large conceptual schemas.  (2013).


capbtabboxtable[][]

# Towards Rotation Invariance in Object Detection

Agastya Kalra1, Guy Stoppi1, Bradley Brown1, Rishav Agarwal1 and Achuta
Kadambi1,2
1Akasha Imaging, Palo Alto CA
2UCLA, Los Angeles CA
{agastya, guy.stoppi, bradley.brown<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Rotation augmentations generally improve a model’s invariance/equivariance to
rotation - except in object detection. In object detection the shape is not
known, therefore rotation creates a label ambiguity. We show that the de-facto
method for bounding box label rotation, the Largest Box Method, creates very
large labels, leading to poor performance and in many cases worse performance
than using no rotation at all. We propose a new method of rotation
augmentation that can be implemented in a few lines of code. First, we create
a differentiable approximation of label accuracy and show that axis-aligning
the bounding box around an ellipse is optimal. We then introduce Rotation
Uncertainty (RU) Loss, allowing the model to adapt to the uncertainty of the
labels. On five different datasets (including COCO, PascalVOC, and Transparent
Object Bin Picking), this approach improves the rotational invariance of both
one-stage and two-stage architectures when measured with AP, AP50, and AP75.
The code is available at https://github.com/akasha-imaging/ICCV2021.

##  1 Introduction

It is desirable for object detectors to work when scenes are rotated. But
there is a problem: methods like Convolutional Neural Networks (CNNs) may be
scale and translation invariant but CNNs are not rotation invariant [15]. To
overcome this problem, the training dataset can be expanded to include data at
new rotation angles. This is known as _rotation augmentation_. In object
detection, rotation augmentation can be abstracted as follows: given an
original bounding box and any desired angle of rotation, how should we
determine the axis-aligned rotated bounding box label? If the shape of the
object is known, this is quite simple: we rotate the object shape and re-
compute the bounding box. However in the case of object detection, the shape
is unknown.

The prevailing folk wisdom in the community is to select a label large enough
to completely overlap the rotated box [45]. In studying this problem, we find
that this method may hurt performance, and on COCO [22], we find that _every
other prior we tried is better_. Yet somehow this “Largest Box” method is very
prevalent both in academia and in large scale object detection codebases [43,
4, 45, 37, 28, 26, 5, 7, 1, 17, 6, 40]. Indeed, recent analysis has found that
largest box is only robust to about $<3^{\circ}$ [16] of rotation.

Figure 1: A method is proposed to properly rotate a bounding box for rotation
augmentation. The previous solution of largest box is an overestimate of the
perfect bounding box for a rotated scene. See table for how choice of rotation
augmentation affects object detection performance.

In this paper, we propose an advance on the largest box solution that achieves
significantly better performance on five object detection datasets; while
retaining the simplicity of a few lines of code implementation.

###  1.1 Contributions

In a nutshell, our solution has two aspects. First, we derive an elliptical
shape prior from first principles to determine the rotated box label. We
compare it to many other novel priors and show this is optimal. Second, we
introduce a novel Rotation Uncertainty (RU) Loss function, which allows the
network to adapt the labels at higher rotations using priors from lower
rotations based on label certainty. We demonstrate the effectiveness of this
solution by both improving performance datasets where rotation is important
such as Pascal VOC [14] and Transparent Object Bin Picking [18] and
generalizing to novel test time rotations on MS COCO [22] (Figure 1).

###  1.2 Scope

Rotation data augmentation in object detection is not new. This paper is not
about finding the best overall way to use a rotation data augmentation. For
that - a brute force search or papers like AutoAugment [45] might be better
examples. This paper focuses solely on methods to perform a rotation
augmentation on axis-aligned bounding boxes. When implemented, these proposed
modifications boil down to a few lines of code and leave little reason to use
the current Largest Box method.

##  2 Related Work

Data Augmentations are an effective technique to boost the performance of
object detection. Data augmentation increases the quantity and improves the
diversity of data. Data augmentations are of two types. Photo-metric
transforms modify the color channels such that the detector becomes invariant
to change in lighting and color. Classical photometric techniques include
adding Gaussian blur or adding colour jitters. Modern photo-metric
augmentations like Cutout [11] and CutMix [44], randomly remove patches of the
image. On the other hand, geometric transforms modify the image’s geometry,
making the detector invariant to position and orientation. Geometric
modifications require corresponding changes to the labels as well. Geometric
transforms are difficult to implement [5] and contribute more towards accuracy
improvements [38]. We focus specifically on rotation augmentations and object
detection.

Figure 2: Comparison between our method and other methods. We show example
predictions from models trained with each rotation augmentation above. Our
method has comparable performance to using perfect segmentation labels without
requiring the extra shape information.

Rotation Method | AP50 (Coarse) | AP75 (Fine) | Shape Label
---|---|---|---
No Rotation |  orange!25Med |  orange!25Med |  green!25No
Largest Box (e.g. [1, 17, 5]) |  orange!25Med |  red!25Low |  green!25No
Ellipse + RU Loss (Ours) |  green!25Very High |  green!25High |  green!25No
Perfect Box (Gold Std) |  green!25Very High |  green!25Very High |  red!25Yes

Rotation Augmentation in Object Detection is currently done by the largest box
method for major repositories (e.g. [5, 7, 1, 17, 6, 40]) and publications
(e.g. [43, 4, 45, 37, 28, 26]) that do bounding box rotation for deep learning
object detection. The largest box method does a great job guaranteeing
containment, but at large angles, it severely overestimates the bounding box’s
size. Figure 2 shows an example of these over-sized bounding boxes. For that
reason, FastAI [16] recommends rotation of no more than 3 degrees. Some recent
work, such as AutoAugment [45, 37], use rotation as part of a complex learned
data augmentation scheme. While learning rotation augmentation directly is
interesting, it requires extensive computing resources. We seek to achieve the
simplicity of the largest box, with performance improvements for larger
angles.

Oriented Bounding Boxes, a sister of object detection, is the task of
predicting non-axis aligned bounding boxes, also known as oriented bounding
boxes. Several methods like [12, 8, 25], aim to achieve rotation invariance
when predicting rotated bounding boxes. However, these methods already have
labelled rotated boxes as input and do not end up with loose boxes when the
input image is rotated. As this is a different task, it is out of the scope of
this paper. Our paper focuses on axis-aligned bounding boxes only.

Rotational Invariance is an important problem to solve in object detection.
Classical computer vision methods achieved rotational invariance by extracting
features from images [41, 23, 24, 34]. With the rise of neural networks, newer
methods attempt to modify the architecture to achieve rotation invariance [10,
9, 43]. These methods rotate the input images and add special layers that
learn the object’s orientation in the image. Our general-purpose method can
again aid these methods as well.

##  3 Background

###  3.1 Rotation Augmentation for Object Detection

An image is parameterized by $x$ and $y$ coordinates. Suppose the image
contains an object with shape $S$. Let $S$ denote the shape set that describes
all points in an object:

$S=\\{(x,y)\,\,|\,\,\forall\,\,(x,y)\in\textrm{object}\\}.$ (1)

In object detection, a bounding box is defined to be the tightest fitting
axis-aligned box around a shape. Therefore a shape determines the coordinates
of a bounding box, $\mathbf{b}=[x_{min},y_{min},x_{max},y_{max}]^{T}$. Each of
the four edges of the bounding box intersects at least one element of the
shape set. Let the operator $\mathcal{B}$ represent the perfect conversion of
a shape to a bounding box:

$\mathbf{b}\triangleq\mathcal{B}(S).$ (2)

Figure 3: Our Ellipse method leads to good initial training labels while the
Largest Box overestimates the labels. From left to right: (1) The original
bounding box prior to rotation. (2) The oversized Largest Box estimate of the
ground truth label post rotation. (3) The tighter Ellipse estimate (Section
4.1). (4) The actual ground truth which we get from segmentation shape labels.
(5) The set of all possible ground truth boxes given a rotation and an initial
box.

The operator $\mathcal{B}$ extracts the bounding box $\mathbf{b}$ (tightest
fitting axis aligned box) for $S$ by taking the minimum/maximum $(x,y)$
coordinates of the shape. As $S$ is not unique, the same bounding box can be
generated by many shapes. For example, a square of side length $d$ and a
circle of diameter $d$ are just two of many unique shapes that generate the
same bounding box. More formally, let $V_{\mathbf{b}}$ denote the set of
shapes that could possibly generate a bounding box $\mathbf{b}$, such that

$V_{\mathbf{b}}=\\{S_{i}\,\,|\,\,\mathcal{B}(S_{i})=\mathbf{b},\,\forall\,\,S_{i}\in\mathcal{P}\\}.$
(3)

Where $\mathcal{P}$ is the dataset specific distribution of shapes. Let us
consider the problem of rotation augmentation where an image and corresponding
box label $\mathbf{b}$ is rotated by angle $\theta$. If the shape of the
object is known, then we can rotate the original shape by angle $\theta$ using
a rotation operator: $\mathcal{R}^{\theta}(S)$. In analogy to Equation 2, we
can then use the perfect method to obtain an axis-aligned bounding box for the
rotated image as:

$\mathbf{b}^{\theta}_{\textrm{perfect}}\triangleq\mathcal{B}(\mathcal{R}^{\theta}({S}_{\textrm{perfect}})),$
(4)

We call this method perfect labels, where ${S}_{\textrm{perfect}}$ is the
actual shape of the object for a given bounding box $\mathbf{b}$. However,
this requires shape labels, which are not available for object detection. In
object detection, humans label boxes by implicitly segmenting the shape.
Without knowing the shape labels, any shape $S\in V_{\textbf{b}}$ could be
${S}_{\textrm{perfect}}$, leading to many possible boxes
$\mathbf{b^{\theta}}$. This paper seeks a method to estimate the rotated
bounding box when we do not know the shape. We are only provided with the
original bounding box $\mathbf{b}$, which we will hereafter write as
$\mathbf{b}^{0}$ by making explicit that $\theta=0$. The problem statement
follows.

##### Problem Statement:

Given only an input bounding box $\mathbf{b}^{0}$ and an angle $\theta$ by
which the image should be rotated, find the axis aligned bounding box
$\widehat{\mathbf{b}}^{\theta}$ that: (1) has high IoU with
$\mathbf{b}^{\theta}_{\textrm{perfect}}$; and (2) improves model performance
on rotated versions of vision datasets.

###  3.2 Largest Valid Box Method

Rotation augmentation without shape knowledge is not a new problem statement.
The _de facto_ method in the object detection community for determining the
bounding box post-rotation with no shape priors is the largest box method. The
largest box method is _extremely_ prevalent (e.g. [28, 26, 5, 7, 1, 17, 6, 40,
20, 19, 27, 33, 36, 39]). Just like our proposed method, the largest box takes
only the original bounding box $\mathbf{b}^{0}$ and $\theta$ as input. From
Equation 3 it is clear that several shapes could define $\mathbf{b}^{0}$. This
creates an _ambiguity problem_. The largest box method chooses the single
largest of these possible shapes in area, $S_{\textrm{largest}}$. This shape
is simply the box itself (Table 1). Treating this as the object shape,
Equation 4 can be adapted to obtain

$\mathbf{b}^{\theta}_{\textrm{largest}}\triangleq\mathcal{B}(\mathcal{R}^{\theta}(S_{\textrm{largest}})).$
(5)

The benefit of this method is that it produces a box that is _guaranteed_ to
contain the original object [45], and it is easy to implement. The downside is
that the method produces oversized boxes [16, 45, 35, 2, 29, 3], and if used
generously, hurts performance more than it helps (Table 11). Surprisingly, to
our best knowledge, including personal communication with practitioners and
posts on internet forums, no alternatives have been adopted. We hope our
method will change that.

##  4 Proposed Solution

We now describe our solution to the problem: given $\mathbf{b^{0}}$ and
desired rotation angle $\theta$, find $\widehat{\mathbf{b}}^{\theta}$. In a
nutshell, our solution estimates a rotated bounded box by assuming the
original shape is an ellipse (Table 1, Figure 3) and rotating accordingly
(Section 4.1). We then adapt the loss function to account for error in the
labels (Section 4.3).

###  4.1 Ellipse Method

In this section, we first derive the ellipse assumption from first principles
by trying to find the shape that is most likely to have high overlap with
potential ground truth boxes. Then we discuss the implementation and intuition
of the ellipse method. Finally, we mention other novel methods we developed.

####  4.1.1 Ellipse from Maximizing Expect IoU

We start with a simple assumption: the optimal method for determining a
bounding box post-rotation augmentation should maximize label accuracy, which
in the case of object detection is measured in IoU.

We define $\widehat{\mathbf{b}}^{\theta}$ as the optimal rotated bounding box.
We are provided the input angle $\theta$ and box $\mathbf{b}^{0}$. From
Equation 3, this box could have been generated from any number of shapes:
$V_{\mathbf{b}^{0}}=\\{S_{i}\\}_{i=1,2,\ldots,N}$. For each shape we can use
the “perfect method” from Equation 4 to obtain a potential rotated bounding
box. Since multiple shapes can lead to the same rotated box, we obtain $M\leq
N$ possible bounding boxes, which we write as the set:

$\displaystyle Q^{\theta}_{\mathbf{b}^{0}}$
$\displaystyle=\textrm{unique}\\{\mathbf{b}^{\theta}_{j}=\mathcal{B}(\mathcal{R}^{\theta}(S_{i})),\forall
S_{i}\in V_{\mathbf{b}^{0}}\\}$ (6)
$\displaystyle=\\{\mathbf{b}^{\theta}_{j}\\}_{j=1,\ldots,M}.$ (7)

Hereafter, and without loss of generality, the paper will assume that
$\mathbf{b}^{0}$ is the input allowing notation to be simplified:

$Q^{\theta}\triangleq Q^{\theta}_{\mathbf{b}^{0}}.$ (8)

Now the task becomes to pick the “best” of the $M$ possible bounding boxes in
$Q^{\theta}$. Recall that the de facto solution is to choose the largest box
in $Q^{\theta}$. This largest box is guaranteed to contain the object.
However, optimizing for containment does not seem like a good choice to
directly address the metric of AP because AP uses IoU to determine true
positives, not containment. A more relevant goal for object detection is to
select a box that maximizes:

$\widehat{\mathbf{b}}^{\theta}=\underset{\widehat{\mathbf{b}}^{\theta}\in
Q^{\theta}}{\textrm{argmax}}\,\,IoU(\widehat{\mathbf{b}}^{\theta},\mathbf{b}^{\theta}_{\textrm{perfect}}).$
(9)

In which case
$\widehat{\mathbf{b}}^{\theta}=\mathbf{b}^{\theta}_{\textrm{perfect}}$. Of
course, we are not given $\mathbf{b}^{\theta}_{\textrm{perfect}}$. So for the
moment, let us assume any of the bounding boxes in $Q^{\theta}$ has an equal
chance of being the perfect box. Then, it would make sense to optimize over:

$\widehat{\mathbf{b}}^{\theta}=\underset{\widehat{\mathbf{b}}^{\theta}\in
Q^{\theta}}{\textrm{argmax}}\,\,Avg\\{IoU(\widehat{\mathbf{b}}^{\theta},\mathbf{b}^{\theta}_{j})\,\,|\,\,\forall\,\,\mathbf{b}^{\theta}_{j}\in
Q^{\theta}\\}.$ (10)

Now, let us break the assumption that each candidate box in $Q^{\theta}$ is
equally likely to be the perfect box. Indeed, we know that many shapes can
produce the same box (since $M\leq N$), so certain boxes are more likely than
others. For example, the only shape that can produce the largest box is the
original box itself, whereas other rotated boxes can be generated by multiple
object shapes in the dataset. Denote $p(\mathbf{b}^{\theta}_{j})$ as the
probability that box
$\mathbf{b}^{\theta}_{j}=\mathbf{b}^{\theta}_{\textrm{perfect}}$. Then
Equation 10 can be reformulated as:

$\widehat{\mathbf{b}}^{\theta}=\underset{\widehat{\mathbf{b}}^{\theta}\in
Q^{\theta}}{\textrm{argmax}}\sum_{i=1}^{M}p(\mathbf{b}^{\theta}_{j})IoU(\widehat{\mathbf{b}}^{\theta},\mathbf{b}^{\theta}_{j}).$
(11)

Readers may recognize this equation as being analogous to an expectation. We
refer to this in the paper as the Expected IoU. The expected IoU is not
directly tractable: we do not know $p(\mathbf{b}^{\theta}_{j})$ _a priori_.
However, if we can sample $K$ random shapes from a dataset distribution over
shapes $S_{k}\sim\mathcal{P}$ where
$\mathbf{b}^{\theta}_{k}=\mathcal{B}(\mathcal{R}^{\theta}(S_{k}))$ we get the
following optimization objective:

$\widehat{\mathbf{b}}^{\theta}=\underset{\widehat{\mathbf{b}}^{\theta}\in
Q^{\theta}}{\textrm{argmax}}\frac{1}{K}\sum^{K}_{k=1}IoU(\widehat{\mathbf{b}}^{\theta},\mathbf{b}^{\theta}_{k}).$
(12)

Method | Shape Definition
---|---
$S_{\textrm{largest}}$ | $\\{(x_{1},y_{1}),(x_{2},y_{1}),(x_{2},y_{2}),(x_{1},y_{2})\\}$
$S_{\textrm{ellipse}}$ (Ours) | $\Big{\\{}(x,y)\,\Big{|}\,\dfrac{(x-x_{c})^{2}}{(\nicefrac{{b^{0}_{W}}}{{2}})^{2}}+\dfrac{(y-y_{c})^{2}}{(\nicefrac{{b^{0}_{H}}}{{2}})^{2}}=1\Big{\\}}$

Table 1: Our method can be compared with the Largest Box in the shape domain.
The implementation difference is one line of code.

Since all object detection datasets do not have shape labels, we sample
$\mathcal{P}$ by generating random shapes that touch each side of $b^{0}$
once. This way we are not dataset-specific. We analyze using COCO shapes in
the supplement and show the performance is extremely similar. The above
equation is fully differentiable, and so we can solve with gradient ascent.
The problem here is that we would then have to solve this equation for every
$\theta$ and every box $b$, and this is not practical. Therefore we generalize
this further to a canonical shape.

Label Method | $S_{\textrm{largest}}$ |  $S_{\textrm{ellipse}}$ (Ours) |  $\widehat{S}$ (Ours)
---|---|---|---
Expected IoU | 60.8 | 72.9 | 72.9

Figure 4: The optimal shape to maximize expected IoU with potential ground
truth boxes converges to an ellipse. Curve showing the progression of gradient
ascent starting from the largest box and converging to an elliptical shape.
The final converged expected IoU for $\widehat{S}$ matches that of the largest
inscribed ellipse $S_{\textrm{ellipse}}$.

##### Optimizing Equation 12 via a canonical shape:

Instead of solving Equation 12 for every possible combination of $b^{0}$ and
$\theta$, we attempt to find a shape that is optimal across different input
bounding boxes. This way, we could solve for some best shape $\widehat{S}\in
V_{\mathbf{b^{0}}}$, and solve for $\widehat{\mathbf{b}}^{\theta}$ as follows:

$\widehat{\mathbf{b}}^{\theta}\triangleq\mathcal{B}(\mathcal{R}^{\theta}(\widehat{S})),$
(13)

To obtain the likely shape, we combine Equations 12 and 13 to optimize the
quantity:

$\widehat{S}=\underset{S\in\mathcal{V}_{\mathbf{b^{0}}}}{\textrm{argmax}}\,\sum_{\theta}\frac{1}{K}\sum_{k=1}^{K}\left[IoU(\mathcal{B}(\mathcal{R}^{\theta}(S)),\mathbf{b}^{\theta}_{k})\right].$
(14)

| AP50 | AP75
---|---|---
| $10^{\circ}$ | $20^{\circ}$ | $30^{\circ}$ | $40^{\circ}$ | $10^{\circ}$ | $20^{\circ}$ | $30^{\circ}$ | $40^{\circ}$
Largest Box | 98.2 | 93.79 | 86.31 | 82.9 | 59.2 | 25.6 | 19.9 | 17.3
Ellipse (Ours) | 99.6 | 98.6 | 97.0 | 96.5 | 86.8 | 56.2 | 47.2 | 46.5

Figure 5: Comparing Label AP (assuming uniform confidence) at different IOU
thresholds for both methods at a $15^{o}-30^{o}$ rotation augmentation. Ours
is significantly better at AP50 and AP75.

Note that we now optimize over all rotation angles and aspect ratios
simultaneously. This adds enough constraints to find a unique shape. The goal
is to find _the shape $\widehat{S}$ that produces an augmented bounding box
that has high IoU with likely ground truth boxes_. Since $\mathcal{R}$ and
$\mathcal{B}$ are differentiable operators, Equation 14 can be optimized
through gradient ascent to solve for $\widehat{S}$. We provide details and
pseudo-code and some analysis in the supplement. The stable solution found by
gradient ascent is that of an elliptical shape. We show the progression of
gradient ascent in Figure 4 from the largest box shape to a circle. If we
change the aspect ratio, it simply converges to the largest inscribed ellipse.
Also in Figure 4, we show the Expected IoU for the Largest Box shape is much
lower than the Ellipse, and in Figure 5 we show that the resulting AP of the
Ellipse labels is much better. The elliptical solution is similar to the
optimized shape for various tested distributions of $\mathcal{P}$, including
the random model described in the previous paragraph.

####  4.1.2 The Ellipse Method

When we model the shape as an ellipse, we can find the estimated bounding box
as:

$\widehat{\mathbf{b}}^{\theta}=\mathcal{B}(\mathcal{R}^{\theta}(S_{\textrm{ellipse}})),$
(15)

where $S_{\textrm{ellipse}}$ is the largest inscribed ellipse inside
$\mathbf{b}^{0}$, expressed as:

$S_{\textrm{ellipse}}=\Big{\\{}(x,y)\,\Big{|}\,\dfrac{(x-x_{c})^{2}}{(\nicefrac{{b^{0}_{W}}}{{2}})^{2}}+\dfrac{(y-y_{c})^{2}}{(\nicefrac{{b^{0}_{H}}}{{2}})^{2}}=1\Big{\\}},$
(16)

where $(x_{c},y_{c})$ is the location of the center of $b^{0}$ and
$b^{0}_{W},b^{0}_{H}$ are the width and height of $b^{0}$ respectively.

This equation is fast, simple to implement, and high-performing on modern
vision datasets. The elliptical approximation can be implemented in the same
line of code as the largest box method (cf. Appendix A), yet it greatly
improves performance. We see in Figure 5 the ellipse labels are far more
accurate than the largest box labels. However, one disadvantage with the
proposed elliptical box method is that the elliptical box can underestimate
the object size or aspect ratio. This still causes some noise in the labels,
especially at large rotations. We mitigate this by allowing the model to adapt
labels at higher rotations based on priors from lower rotations in Section
4.3.

###  4.2 Other Methods

We do not limit our analysis to the ellipse method. To perform a complete
study we came up with an additional 4 methods. To conserve space, full details
and results of these novel methods are available in the supplement Appendix B,
we provide a quick summary for these methods here.

  * •

_Scaled Octagon:_ We use an octagon with a scaling factor ($s$) to interpolate
between the largest box shape and a diamond shape.

  * •

_Random Boxes:_ We sample random valid boxes and use those as ground truth
labels.

  * •

_RotIoU:_ We select the label that has the maximum IoU with the rotated ground
truth box rather than the expected axis-aligned ground truth box.

  * •

_COCO Shape:_ Rather than using random shapes for the optimization, we use the
shapes from the COCO dataset. We keep results from this to the supplement
since the performance between this and the ellipse method is negligible and we
want this paper to be dataset independent and easy to implement.

###  4.3 Rotation Uncertainty Loss

$C(\theta)=\max\left(0.5,1+\frac{1-\cos(4\theta)}{2\cos(4\delta)-2}\right)$

Figure 6: Rotational certainty used by RU Loss as a function of theta plotted
for different hyper-parameters $\delta$ where $\delta$ is the angle at which
$C(\theta)=0.5$.

Figure 7: The Expected IoU of a rotation method is heavily correlated with
performance. Our final Ellipse is optimal for both.

COCO val2017 Ablations | $0^{\circ}$ | $10^{\circ}$ | $20^{\circ}$ | $30^{\circ}$
---|---|---|---|---
(a) Previous method
Largest Box(e.g. [4, 45, 37]) | 35.20 | 28.37 | 22.34 | 18.47
(b) Our Rotation Label Methods (Section 4.2)
Random | 37.39 | 35.59 | 32.22 | 28.33
Octagon $s=0.1$ | 35.82 | 31.64 | 27.16 | 23.54
Octagon $s=0.2$ | 36.52 | 34.57 | 31.65 | 28.15
Octagon $s=0.5$ (Diamond) | 38.36 | 35.39 | 28.76 | 22.92
RotIoU | 38.32 | 36.48 | 32.68 | 28.94
gray!30 Ellipse (Section 4.1.2) | 38.21 | 36.83 | 33.59 | 29.95
(c) With Our Loss (Section 4.3)
Ellipse + RU Loss $\delta=45^{\circ}$ | 38.54 | 37.45 | 34.56 | 31.26
Ellipse + RU Loss $\delta=30^{\circ}$ | 39.09 | 37.99 | 35.45 | 32.25
Ellipse + RU Loss $\delta=15^{\circ}$ | 39.14 | 38.19 | 35.78 | 32.50
gray!30 Ellipse + RU Loss $\mathbf{\delta=10^{\circ}}$ (Final) | 39.33 | 38.31 | 36.00 | 32.72

Figure 8: The AP at different test rotations on the COCO val2017 set for
different methods. (a) The previous method of largest box leads to the worst
performance - every other idea we had was better. (b) The Ellipse is the best
of all the label generation methods. (c) Our RU Loss with $\delta=10^{\circ}$
leads to the best AP across all rotations and therefore we use this as our
final method. _Note: We bold within 0.2 of best result._

Figure 9: Example bounding box predictions for Largest Box model (top row) and
Ellipse model (bottom row) for all 5 datasets. We can see that ours produces
tighter bounding boxes overall.

Datasets (At $0^{\circ}$ Test Rotation) | Pascal VOC [14] | Transparent Bin Picking [18] | Synthetic Fruit Dataset [13] |  Oxford Pets [30]
---|---|---|---|---
Methods | AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75 | AP | AP50 | AP75
No Rotation | 51.94 | 80.91 | 56.54 | 48.53 | 79.14 | 54.3 | 84.3 | 95.07 | 92.6 | 80.70 | 92.80 | 88.76
Largest Box(e.g. [4, 45, 37]) | 50.23 | 81.31 | 54.3 | 37.49 | 79.09 | 28.45 | 83.47 | 95.05 | 92.24 | 79.54 | 94.20 | 90.03
(relative improvement) | -3.29% | 0.49% | -3.96% | -22.7% | -0.06% | -47.6% | -0.98% | -0.02% | -0.39% | -1.43% | 1.56% | 1.43%
gray!30 Ellipse + RU Loss (Ours) | 52.89 | 81.57 | 57.97 | 50.36 | 81.78 | 56.76 | 84.83 | 95.83 | 93.17 | 81.28 | 94.37 | 91.09
gray!30(relative improvement) | 1.84% | 0.82% | 2.53% | 3.78% | 3.35% | 4.53% | 1.05% | 0.80% | 0.62% | 0.72% | 1.69% | 2.63%

Figure 10: Across four separate datasets we show that our method of rotation
augmentation leads to an improved performance where the previous method hurts
performance. Especially in the case of transparent object bin picking where
the largest box is almost 50% worse and ours is 4.5% better AP75.

As shown in Figure 4 the expected IoU with random shapes is 72.9. This means
attaining good performance at the higher APs, like AP75, will be very
difficult using just these labels. To tackle this problem, we create a custom
loss function that adapts the regression loss to account for the uncertainty
of the rotation. The idea is simple - if we are uncertain of the label, we
turn off the regression loss if the model is _close enough_. The labels are
more uncertain as the rotation approaches
$45^{\circ},135^{\circ},225^{\circ},315^{\circ}$. and perfectly certain at
$0^{\circ},90^{\circ},180^{\circ}\text{ and }270^{\circ}.$ We formalize on the
concept of certainty (Figure 6) as a function of $\theta$:

$\alpha=2\cos(4\delta),$ (17)
$C(\theta)=1+\frac{1}{\alpha-2}(1-\cos(4\theta)).$ (18)

This function maps a rotation $\theta$ to an IoU threshold $C(\theta)$. We use
this IoU threshold to serve as an indicator for applying regression loss. If
the predicted box is greater than $max(0.5,C(\theta))$, it uses the regression
loss, otherwise, it does not and assumes the model’s prediction is correct. We
parameterize $C$ with $\delta$. $\delta$ is the angle at which
$C(\theta)=0.5$. We visualize $C$ in Figure 6. We bound it by 0.5 since that
is the threshold for anchor-matching in standard object detection
architectures [21].

This function allows the model to take the priors it learns at the confident
rotations and apply them to the higher rotations, preventing it from
overfitting to poor labels. We show in Table 8.

##  5 Results

###  5.1 Setup

Our hardware setup contains only a single P100 GPU for training, and all our
code is implemented in Detectron2 [42] with Pytorch [31]. We use the default
training pipeline for both Faster-RCNN [32] and RetinaNet [21]. We conduct
most of our experiments on the standard COCO benchmark since it contains a
variety of objects with many different shapes - making it a challenging test
set.

Training Since we have only a single GPU, we can only fit a batch size of 3.
To account for this, we increase the training time by around 5x from the
default configurations. This allows us to match online available pre-trained
baselines for RetinaNet [21] and Faster-RCNN [32]. Since most datasets are
right-side-up images, we train with a normal distribution with a mean of 0 and
a standard deviation of 15 degrees for all experiments. Since this paper aims
to find the optimal rotation augmentation method, not the strategy for
applying rotation augmentation, we do not try other combinations. This may be
left for future work.

COCO val2017 Results | AP | AP50 | AP75
---|---|---|---
$\boldsymbol{0^{\circ}}$ | $\boldsymbol{{10}^{\circ}}$ | $\boldsymbol{{20}^{\circ}}$ | $\boldsymbol{{30}^{\circ}}$ | $\boldsymbol{0^{\circ}}$ | $\boldsymbol{{10}^{\circ}}$ | $\boldsymbol{{20}^{\circ}}$ | $\boldsymbol{{30}^{\circ}}$ | $\boldsymbol{0^{\circ}}$ | $\boldsymbol{{10}^{\circ}}$ | $\boldsymbol{{20}^{\circ}}$ | $\boldsymbol{{30}^{\circ}}$
No Rotation | 39.26 | 37.54 | 33.68 | 29.19 | 59.68 | 56.88 | 51.35 | 45.37 | 41.69 | 40.14 | 35.63 | 30.39
Largest Box (e.g. [4, 45, 37]) | 35.20 | 28.37 | 22.34 | 18.47 | 58.79 | 56.31 | 51.49 | 46.30 | 36.00 | 25.37 | 14.95 | 10.91
(relative improvement) | -10.3% | -24.4% | -33.7% | -36.7% | -1.48% | -1.01% | 0.27% | 2.04% | -13.6% | -36.8% | -58.1% | -64.1%
gray!30 Ellipse + RU Loss (Ours) | 39.33 | 38.31 | 36.00 | 32.72 | 60.08 | 58.66 | 55.73 | 51.60 | 41.74 | 40.71 | 38.05 | 33.97
gray!30 (relative improvement) | 0.17% | 2.05% | 6.88% | 12.1% | 0.67% | 3.12% | 8.54% | 13.7% | 0.13% | 1.42% | 6.79% | 11.8%
Perfect Labels | 39.66 | 39.17 | 37.24 | 34.08 | 60.28 | 58.89 | 55.91 | 51.83 | 42.05 | 41.73 | 39.61 | 36.02
(relative improvement) | 1.02% | 4.36% | 10.6% | 16.7% | 1.00% | 3.53% | 8.88% | 14.2% | 0.88% | 3.94% | 11.2% | 18.5%

Figure 11: Our method of Ellipse + RU Loss performs close to perfect labels
for AP50 and performs better than No Rotation and Largest Box for AP and AP75
- demonstrating the first reliable rotation augmentation without shape labels.

Testing: For all datasets except COCO we do not have complete segmentation
labels, so we only test on the standard test set ($0^{\circ}$). For COCO we
generate our test set by taking the COCO val2017 set and rotating it from
$0^{\circ}$-$40^{\circ}$ to simulate out-of-distribution rotations. We then
bucket these rotations in intervals of 10 and evaluate using segmentation
labels to generate ground truth. We leave COCO results for Faster-RCNN to
supplement because they are similar to the results for RetinaNet shown below.

###  5.2 Ablation Studies

In Figure 8 and the accompanying table, we conduct a thorough ablation study
on both the method for choosing the label and the impact of the RU Loss
function.

##### Justifying EIoU Optimization:

In Section 4.1.1 we assumed that the optimal method for label rotation should
maximize label accuracy, which we approximated as Expected IoU (Eq. 14). In
Figure 8 we demonstrate a strong correlation between Expected IoU and
performance on COCO at $10^{\circ}$ across all methods, proving the
effectiveness of our first principles derivation. We see similar correlations
at other angles as well.

##### Justifying the Ellipse:

In Section 4.1 we introduced many potential methods for rotating a box label.
In the ablation Table 8b we show that the Ellipse leads to the best
performance across all rotations except $0^{\circ}$ where it is within a small
noise tolerance. It is also important to note that all methods we tried
perform significantly better than the Largest Box - showing the importance of
fixing this issue.

##### RU Loss Ablation:

In Section 4.3 we introduce a hyper-parameter $\delta$ in our final method. We
ablate over that in Table 8 and demonstrate that $10^{\circ}$ is optimal. We
found this to be true on COCO, however, on simpler datasets we use larger
values of $\delta$ for optimal performance.

###  5.3 Overall Performance

Our best performing method consists of using both Ellipse-based label rotation
and RU Loss. In this section, we show it leads to much better performance
across multiple datasets and approximates segmentation-based rotation
augmentations on COCO.

####  5.3.1 Object Detection Datasets

In Table 10, we provide four datasets where our method of rotation
augmentation improves performance while the previous one (Largest Box) hurts
performance. We notice this to be especially bad at higher APs, such as AP75.
The gap is also larger in complex datasets such as transparent object bin
picking where the largest box reduces performance by almost 50% and ours
increases it by 4.5%.

####  5.3.2 Generalizing to new Rotation Angles

Our method significantly outperforms the original largest box method and also
outperforms not using rotation for AP, AP50, and AP75 across all new angles
from $[0^{o}-30^{o}]$ on COCO in Figure 1 and Figure 11. In the case of AP50,
we show very similar improvements compared to using segmentation-based labels.
This is a huge improvement since the largest box method hurts rotation
performance.

##  6 Conclusion

The widespread Largest Box method (e.g. [43, 4, 45, 37, 28, 26]) is based on
the folk wisdom of maximizing overlap. Instead, we show that by maximizing
Expected IoU and accounting for label certainty in the loss, we can completely
match the performance of perfect “segmentation-based” labels at AP50 while
also achieving significant gains for AP and AP75. These results represent a
step toward achieving rotation invariance for object detection models, while
adding only a few lines of complexity to object detection codebases.

##### Acknowledgements:

We thank Yuri Boykov, Tomas Gerlich, Abhijit Ghosh, Olga Veksler and Kartik
Venkataraman for their helpful discussions and edits to improve the paper.

## References

  * [1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al.  Tensorflow: A system for large-scale machine learning.  In 12th $\\{$USENIX$\\}$ symposium on operating systems design and implementation ($\\{$OSDI$\\}$ 16), pages 265–283, 2016.
  * [2] Albumentations-Team.  Why does the bounding box become so loose after rotation data aug? is there a better way? · issue 746 · albumentations-team/albumentations.  https://github.com/albumentations-team/albumentations/issues/746.
  * [3] Aleju.  Make the bounding box more tighten for the object after image rotation · issue 90 · aleju/imgaug.  https://github.com/aleju/imgaug/issues/90.
  * [4] Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao.  Yolov4: Optimal speed and accuracy of object detection.  arXiv preprint arXiv:2004.10934, 2020.
  * [5] Alexander Buslaev, Vladimir I Iglovikov, Eugene Khvedchenya, Alex Parinov, Mikhail Druzhinin, and Alexandr A Kalinin.  Albumentations: fast and flexible image augmentations.  Information, 11(2):125, 2020.
  * [6] Ángela Casado-García, César Domínguez, Manuel García-Domínguez, Jónathan Heras, Adrián Inés, Eloy Mata, and Vico Pascual.  Clodsa: a tool for augmentation in classification, localization, detection, semantic segmentation and instance segmentation tasks.  BMC bioinformatics, 20(1):323, 2019.
  * [7] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, et al.  Mmdetection: Open mmlab detection toolbox and benchmark.  arXiv preprint arXiv:1906.07155, 2019.
  * [8] Gong Cheng, Junwei Han, Peicheng Zhou, and Dong Xu.  Learning rotation-invariant and fisher discriminative convolutional neural networks for object detection.  IEEE Transactions on Image Processing, 28(1):265–278, 2018.
  * [9] Gong Cheng, Peicheng Zhou, and Junwei Han.  Learning rotation-invariant convolutional neural networks for object detection in vhr optical remote sensing images.  IEEE Transactions on Geoscience and Remote Sensing, 54(12):7405–7415, 2016.
  * [10] Gong Cheng, Peicheng Zhou, and Junwei Han.  Rifd-cnn: Rotation-invariant and fisher discriminative convolutional neural networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2884–2893, 2016.
  * [11] Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552, 2017.
  * [12] Jian Ding, Nan Xue, Yang Long, Gui-Song Xia, and Qikai Lu.  Learning roi transformer for oriented object detection in aerial images.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [13] Brad Dwyer.  How to create a synthetic dataset for computer vision.  https://blog.roboflow.com/how-to-create-a-synthetic-dataset-for-computer-vision/, Aug 2020.
  * [14] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International journal of computer vision, 88(2):303–338, 2010.
  * [15] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep Learning.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * [16] Jeremy Howard.  Lesson 9: Deep learning part 2 2018 - multi-object detection - fast ai.  https://youtu.be/0frKXR-2PBY?t=554.
  * [17] Alexander B Jung, K Wada, J Crall, S Tanaka, J Graving, S Yadav, J Banerjee, G Vecsei, A Kraft, J Borovec, et al.  imgaug, 2018.
  * [18] Agastya Kalra, Vage Taamazyan1, Supreeth Krishna Raol, Kartik Venkataraman, Ramesh Raskar, and Achuta Kadambi.  Deep polarization cues for transparent object segmentation.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [19] Ayoosh Kathuria.  Data augmentation for bounding boxes: Rethinking image transforms for object detection.  https://www.kdnuggets.com/2018/09/data-augmentation-bounding-boxes-image-transforms.html.
  * [20] Ayoosh Kathuria.  Data augmentation for object detection: How to rotate bounding boxes.  https://blog.paperspace.com/data-augmentation-for-object-detection-rotation-and-shearing/, Sep 2018.
  * [21] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [22] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [23] Baozhen Liu, Hang Wu, Weihua Su, Wenchang Zhang, and Jinggong Sun.  Rotation-invariant object detection using sector-ring hog and boosted random ferns.  The Visual Computer, 34(5):707–719, 2018.
  * [24] Kun Liu, Henrik Skibbe, Thorsten Schmidt, Thomas Blein, Klaus Palme, Thomas Brox, and Olaf Ronneberger.  Rotation-invariant hog descriptors using fourier analysis in polar and spherical coordinates.  International Journal of Computer Vision, 106(3):342–364, 2014\.
  * [25] Lei Liu, Zongxu Pan, and Bin Lei.  Learning a rotation invariant detector with rotatable bounding box.  arXiv preprint arXiv:1711.09405, 2017.
  * [26] Yang Liu, Lei Huang, Xianglong Liu, and Bo Lang.  A novel rotation adaptive object detection method based on pair hough model.  Neurocomputing, 194:246–259, 2016.
  * [27] Rodrigo Lozuwa.  lozuwa/impy.  https://github.com/lozuwa/impy, Mar 2019.
  * [28] Daniel Mas Montserrat, Qian Lin, Jan Allebach, and Edward J Delp.  Training object detection and recognition cnn models using data augmentation.  Electronic Imaging, 2017(10):27–36, 2017.
  * [29] Open-Mmlab.  Why does the bounding box become so loose after rotation data aug? is there a better way · issue 4070 · open-mmlab/mmdetection.  https://github.com/open-mmlab/mmdetection/issues/4070.
  * [30] Omkar M. Parkhi, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar.  Cats and dogs.  In IEEE Conference on Computer Vision and Pattern Recognition, 2012\.
  * [31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  In Advances in neural information processing systems, pages 8026–8037, 2019.
  * [32] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [33] Pranjal Saxena.  Data augmentation for custom object detection: Yolo.  https://medium.com/predict/data-augmentation-for-custom-object-detection-15674966e0c8, Sep 2020.
  * [34] Uwe Schmidt and Stefan Roth.  Learning rotation-aware features: From invariant priors to equivariant descriptors.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2050–2057. IEEE, 2012.
  * [35] Dennis Soemers.  How data augmentation like rotation affects the quality of detection?  https://ai.stackexchange.com/questions/9935/how-data-augmentation-like-rotation-affects-the-quality-of-detection, Mar 2018.
  * [36] Jacob Solawetz.  Why and how to implement random rotate data augmentation.  https://blog.roboflow.com/why-and-how-to-implement-random-rotate-data-augmentation/, Aug 2020.
  * [37] Mingxing Tan and Quoc V Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  arXiv preprint arXiv:1905.11946, 2019.
  * [38] Luke Taylor and Geoff Nitschke.  Improving deep learning with generic data augmentation.  In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1542–1547. IEEE, 2018.
  * [39] Matlab Team.  Augment bounding boxes for object detection.  https://www.mathworks.com/help/deeplearning/ug/bounding-box-augmentation-using-computer-vision-toolbox.html.
  * [40] Aleksei Tiulpin.  Solt: Streaming over lightweight transformations, July 2019.
  * [41] Guoli Wang, Bin Fan, and Chunhong Pan.  Ordinal pyramid pooling for rotation invariant object recognition.  In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1349–1353. IEEE, 2015.
  * [42] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2, 2019.
  * [43] Yue Xi, Jiangbin Zheng, Xiuxiu Li, Xinying Xu, Jinchang Ren, and Gang Xie.  Sr-pod: sample rotation based on principal-axis orientation distribution for data augmentation in deep object detection.  Cognitive Systems Research, 52:144–154, 2018.
  * [44] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In Proceedings of the IEEE International Conference on Computer Vision, pages 6023–6032, 2019.
  * [45] Barret Zoph, Ekin D Cubuk, Golnaz Ghiasi, Tsung-Yi Lin, Jonathon Shlens, and Quoc V Le.  Learning data augmentation strategies for object detection.  arXiv preprint arXiv:1906.11172, 2019.