# GAMMA: Generative Augmentation for Attentive Marine Debris Detection

Vaishnavi Khindkar
<EMAIL_ADDRESS>
Janhavi Khindkar
<EMAIL_ADDRESS>

###### Abstract

We propose an efficient and generative augmentation approach to solve the
inadequacy concern of underwater debris data for visual detection. We use
cycleGAN as a data augmentation technique to convert openly available,
abundant data of terrestrial plastic to underwater-style images. Prior works
just focus on augmenting or enhancing existing data, which moreover adds bias
to the dataset. Compared to our technique, which devises variation,
transforming additional in-air plastic data to the marine background. We also
propose a novel architecture for underwater debris detection using an
attention mechanism. Our method helps to focus only on relevant instances of
the image, thereby enhancing the detector performance, which is highly obliged
while detecting the marine debris using Autonomous Underwater Vehicle (AUV).
We perform extensive experiments for marine debris detection using our
approach. Quantitative and qualitative results demonstrate the potential of
our framework that significantly outperforms the state-of-the-art methods.

##  1 Introduction

Object detection has shown tremendous improvements in recent years especially
after the invention of convolution neural networks which led to numerous
innovations in the fields like robotics, medical imaging, autonomous driving.
Although, a hurdle in training the object detection models is that they
usually rely on a vast amount of training data. This becomes daunting
especially while dealing with the marine domain, where collecting data is not
just time-consuming but also requires huge planning and a lot of manual
intervention. Prior work [1, 2, 3] shows that object detectors trained on such
underwater datasets show poor generalization as compared to their terrestrial
counterparts due to the data scarcity concern of the marine domain. Moreover,
the domain-specific issues which add up to the challenge of underwater object
detection and especially marine debris detections are as stated - i. The shape
of the object gets changed due to biological degradation and water pressure.
ii. Improper light conditions and turbidity add bias and difficulty in
detection. iii. Similar looking classes like suspended debris like plastic
bags and some of the marine life. iv. Color absorption differs as per depth.
Motivated by these challenges, we aim to solve the problem of marine debris
detection, by proposing a generative variational approach to solve the data
scarcity issue and by designing a novel and efficient attention-based
detection strategy.

The data scarcity problem can’t be solved using simple augmentations like
rotation or translation as it doesn’t add much variance and is merely the same
image from a different angle. To solve this problem we can make use of easily
available rich terrestrial data. The terrestrial data can be mapped to the
underwater domain using a mapping function $G:X\rightarrow Y$. G maps the
terrestrial data to domain Y such that the generated image is of the
underwater domain. This can be achieved with the help of Generative
Adversarial Networks (GANs) [4]. Over years GANs are used for various image
applications like image generation [5, 6], image editing [7], and image-to-
image translations [8, 9, 10]. Image to Image translation can be used to map
one domain image to another domain. Most of the image translation models
require paired data of different domains for translation and mapping. But this
is not possible in our case, as we cannot have simultaneous paired images for
underwater and terrestrial domains of marine debris. The recent architecture
of GAN, cycleGAN [10] can solve this problem, without the need for paired
images. It works with unpaired images of different domains, wherein one image
can be terrestrial plastic and the second one can be of underwater style.
Moreover cycleGAN use cycle consistency loss which ensures that for any input
image $x$, the learned mapping should be able to bring $x$ back to the
original image, i.e., $x\rightarrow G(x)\rightarrow F(G(x))=x$. This ensures
that the learned function generates the desired mapping and produces stable
results. As shown in figure 1, where we map two different domain images of (a)
Marine background and (b) Terrestrial plastic, to generate (c) Efficient
underwater plastic data. Image augmentation in this way not only helps us in
adding variation to the dataset but is also able to solve the problem of
degradation of marine debris and lighting conditions of images.

Figure 1: Efficient data augmentation using cycleGAN to convert (in-air)
terrestrial plastic images to underwater marine domain, generating variational
underwater plastic data.

The object detector fails in conditions where the light visibility is very low
and the detector performance completely depends upon the camera conditions.
Also, prior work [3] shows that the detector fails to classify similar-looking
species like jellyfish and a plastic bag due to similar appearances and low
visibility. So to identify and detect the instances in such a domain, we
require added attention such that the model will be able to enhance and
identify the objects irrespective of the background noise and lighting
conditions. Considering the issues in the existing methods as discussed above
we propose a novel object detection method based on the successful mechanism
of self-attention [11] to be able to classify similar looking classes and to
detect objects irrespective of the aforementioned conditions. The motivation
to use self-attention is based on the structural importance of the objects to
enhance the detector performance. The main contributions of this work are
three-fold:

  * •

We propose a novel Marine Debris dataset using a Generative approach by using
cycleGAN.

  * •

We believe we are the first to incorporate self-attention in marine debris
detection. We propose a novel Generative Augmentation for Attentive MArine
debris detection (GAAMA) method which is used for dataset creation and that
comprises a novel Self-Attentive Marine Debris Detector (SEA) module. SEA
generates self-attention feature maps which help improve marine debris
detection by enhancing the structural importance of objects.

  * •

We conduct extensive experiments on the benchmark J-EDI dataset annotated by
the University of Minnesota robotics lab [1]. The framework significantly
boosts the performance of existing Marine debris Faster R-CNN [12] ,yolo [13],
ssd [14] detectors, achieving 9.3%, and 11% improvements in the mAP scores
using our dataset w/o SEA and with sea module as compared to the state-of-the-
art.

##  2 Background

Our approach lies at the intersection of multiple fields. In the following, we
review related work.

Underwater Debris Detection: Increasing plastic pollution has been one of the
biggest problems in this century. This has resulted in a surge of research for
identifying and removing plastic from the world’s waterways using computer
vision and AUV solutions. Japan Agency for Marine-Earth Science and Technology
(JAMSTEC) has made a dataset of deep-sea debris available online as part of
the larger J-EDI (JAMSTEC E-library of Deep-sea Images) dataset containing
images and videos dating 1982. A team of researchers at the University of
Minnesota robotics lab [1] experimented and compared the performance of the
various state-of-the-art models for object detection like Faster R-CNN, SSD,
YOLO using metrics of mAP, IOU, and frame rate with Faster R-CNN performing
the best. They also released the annotated dataset of images collected by the
Japan Agency for Marine-Earth Science and Technology (JAMSTEC). Deeplastic [3]
conducted a similar kind of research using the above-mentioned annotated
dataset along with dataset from 3 sites across California thus generating a
total of 3200 training images on which they trained Yolov4 [15] and Yolov5
[16] models.

Image Data Synthesis: Over recent years Generative Adversarial Networks [4]
based image synthesis has gained a lot of popularity. Generative models based
augmentation has been used for various non-water domain work to improve object
detection and classification tasks. Prior works show the use of GANs for an
underwater domain such as WaterGAN [17], UGAN [18], and Multi-style GAN
(UMGAN) [19] for image enhancement purposes to improve detection accuracy.
WaterGAN uses pairs of non-underwater images and depth maps to generate
underwater images. UGAN uses CycleGAN [10] to generate distorted images with
the Wasserstein GAN [20] used to ensure the stability of output. UMGAN is a
combination of CycleGAN and Conditional GAN [21] to generate multi-style
underwater images. With all these methods, it is challenging to realistically
simulate color and shape distortions. To solve the generalization problems of
the above-mentioned techniques researcher at the University of Minnesota
robotics lab [2] uses 2 staged VAE [22] to generate underwater images and a
binary classifier to check whether the image is good or bad. Although this can
avoid distortions or using complex architectures as mentioned in the above
approaches it results in the generation of blur images which affects the
performance of the model. To handle problems of blur and distorted images, we
propose a simple CycleGAN based approach to generate underwater domain debris
data, translating terrestrial debris to the underwater background. Our
approach generates non-distorted and sharpened images which help in improving
the detection accuracy.

Self Attention Attention [23] was first introduced for the encoder-decoder in
a neural sequence transduction model to allow for content-based summarization
of information from a variable-length source sentence. Since its introduction,
the ability of attention to learning to focus on important regions within a
context has made it an important component in natural language models [24, 25,
26]. Since then using Self-attention in models has been the primary focus in
these models. The ability of self-attention to capture global dependencies and
handle parallelization, which leverages the strengths of modern hardware, has
led to state-of-the-art models for various tasks. Attention has been popular
in computer vision networks as well. It has been used in various tasks like
SAGAN [27], semantic segmentation and object detection etc [28, 29]. We try to
leverage this advantage of self-attention in the marine domain to focus on
important structures and objects and diminishing the role of background and
the lighting conditions.

Figure 2: Proposed architecture of GAMMA. It comprises of a variational
dataset generator used for augmentation of in-air terrestrial debris to
underwater style and novel SEA module that uses self-attention mechanism to
efficiently improve the marine debris detection performance.

##  3 Generative Augmentation for Attentive Marine Debris Detection

In this paper we pose the question: can we effectively solve the problem of
marine debris detection by solving the data scarcity issue and improving the
detector to effectively detect marine debris irrespective of the background
conditions? In doing so, we propose a novel approach for solving the problem:
Generative Augmentation for Attentive MArine debris detection (GAAMA). As
shown in figure 2, GAAMA is a two-fold method. The left part of the figure
depicts the process of generative dataset creation which is the mapping
function used to map the abundant terrestrial debris images to the underwater
domain using CycleGAN. Irrespective of the prior works which produce the
blurred or distorted images our method produces stable sharpened images
without the need for any extra combination with GAN or any need of paired
images. This helps to solve the problem of data scarcity and issues with
blurred and turbid images.

Prior work in the field uses state-of-the-art object detection models like
Faster R-CNN, SSD, and YOLO models without any modification. These models
usually fail due to incompatibility to handle varying light conditions and the
blurriness induced due to the turbidity of the underwater domain as they
process the information in a local neighborhood and are mostly suited for the
terrestrial domain. To tackle this problem we propose the novel architecture
of SElf Attentive marine debris detector (SEA) as shown in the figure. We make
use of self-attention which focuses on the structural importance of the
objects thus helping in the detection and classification of the debris
irrespective of any conditions induced by the domain.

###  3.1 Generative Dataset Creation

Our key idea is to generate a mapping function $\phi$ that maps $X$ to $Y$
such that $\phi:X\rightarrow Y$ where $x_{i}\in X$ is the set of terrestrial
debris given training samples $X_{i}^{n}$ and $y_{i}\in Y$ is the set
underwater styles given the samples ${Y_{j}^{m}}$, where $n$ and $m$ are the
numbers of images for terrestrial and underwater styles respectively. The data
distribution of terrestrial debris as $x$ ~$p_{data}(x)$ and underwater styles
as $y$ ~$p_{data}(y)$. The mapping should be such that it does not require
paired images as it is really difficult in the underwater domain to have them.
So we use cycleGAN to achieve the mapping due to its success with the unpaired
images. As a workaround for paired images, cycleGAN uses two mappings
$G:X\rightarrow Y$ and $F:Y\rightarrow X$ where $G$ maps terrestrial debris to
$X$ to water styles and $F$ maps the output of $G$ back to $X$. To make this
happen it uses two discriminators and two generators for each mapping. The
adversarial loss is applied on both the mappings. For mapping $G:X\rightarrow
Y$ and discriminator $D_{Y}$ the adversarial loss is defined as,

$L_{M_{GAN}}(G,D_{Y},X,Y)=\mathbb{E}_{y\in
p_{data}(y)}[logD_{Y}(y)]+\mathbb{E}_{x\in p_{data}(x)}[log(1-D_{Y}(G(x))]$
(1)

To ensure the generated underwater images from mapping $G$ does not completely
erode the debris in $X$ and the output of $F$ does not contradict input $X$
i.e $y\rightarrow F(y)\rightarrow G(F(y))=y$ we use cycle consistency loss
which is defined as,

$L_{cyc}(G,F)=\mathbb{E}_{x\in p_{data}(x)}[F(G(x))-x]+\mathbb{E}_{y\in
p_{data}(y)}[G(F(y))-y]$ (2)

Thus the complete objective by combining the adversarial and cycle consistency
loss is given by,

$L(G,F,D_{X},D_{Y})=L_{M_{GAN}}(G,D_{Y},X,Y)+L_{M_{GAN}}(F,D_{X},Y,X)+\lambda
L_{cyc}(G,F)$ (3)

####  3.1.1 Experiment Setting

The training set $C={(X_{i}^{m},Y_{j}^{n})}$ where $X_{i},Y\in R^{(H\times
W\times 3)}$. To generate these we collected both the terrestrial debris and
marine style data by web scraping of images and videos. We collected a total
of $N=1500$ images of terrestrial debris and $M=500$ of underwater styles.
Since gans are subjected to non-stability we ensured the stability of the
generated data by conducting various experiments to tune the hyperparameters.

To evaluate the quality and stability of generated images we use Frechet
Inception Distance (FID) score. The lower the score the higher is the quality
of generated images. To perform the evaluation it extracts features from both
the real images and output of the gans. The data distribution of the extracted
features modeled separately using a multivariate gaussian distribution. Then
the FID score is calculated by
${FID(x,g})=||\mu_{x}-\mu_{g}||_{2}^{2}+T_{r}(\sigma_{x}+\sigma_{g}-2(\sigma_{x}\sigma_{g})^{1/2})$
where $\mu$ is mean, and $\sigma$ is covariance.

###  3.2 SEA : Self Attentive Marine Debris Detector

In the case of marine domains, it is very difficult even for humans to detect
and then classify the objects into the correct category due to the various
problems of light conditions, color similarity, and objects similarity with
each other. The water adds more to the problem than the image or video. To
solve this problem we can make the object detector focus on the structure of
objects instead of the background, which is similar to how we normally detect
the objects. Inspired by the structural importance of objects in the scene to
improve object detection we proposed a novel architecture of SElf Attentive
marine debris detector (SEA). Thus to pay more attention to important
structures and to highlight these points in the input image we use the
technique of self-attention. Attention is a simple mechanism that makes use of
key, query, and value. The key and query decide how much value is important
for a particular operation. This value is the attention given to each region
in the input.

Initially, the features are extracted from a batch of training data,
consisting of images from training data. These features are then fed to the
SElf Attentive marine debris detector module. SEA generates the self-attention
maps representing important structures/regions in the feature vector. The map
is then concatenated with the feature vector to highlight the important
regions which should be focussed by the detector. This output is then passed
to the RPN layer to train the Faster R-CNN.

####  3.2.1 Experiment Setting

Input to the detector is labeled source data $D_{s}=(X_{i},Y_{i})$ where $X$
represents the marine debris images and $Y\in R^{(m\times 5)}$ represents the
list of bounding boxes and corresponding class labels for that particular
image. Our proposed method combines self-attention with the Faster R-CNN
framework. Initially the image $x_{i}\in X$ is passed to the feature extractor
$F_{1}$ as $f_{1}=F_{1}(x_{i})$. $F_{1}$ extracts image-level features
$f_{1}$, which are then passed to the SEA module to get the attention map. The
self-attentive feature maps are generated using the self-attention module
where we use key, query, and value vectors as discussed above. The $Q$ (query)
and $K$ (key) undergoes a matrix multiplication,

$QK_{1}=Q_{1}\times K_{1}$ (4)

The output passes through a softmax which converts the resultant vector into a
probability distribution, and then it finally gets multiplied by V (value),
where $K,Q,V\in R^{(H\times W\times C)}$.

$AT_{map}=softmax(QK)\times V$ (5)

To get the final self-attention map the $AT_{map}$ is concatenated with the
extracted feature $f_{1}$ to highlight the structurally important regions in
the feature vector.

$SA_{map}=AT_{map}\times\gamma+f_{1}$ (6)

This finally is fed to RPN to learn the attentive object detector and generate
the final output.

###  3.3 Algorithm

The novel algorithm GAMMA is explained in Algorithm 1. It explains the two
main functions of the proposed algorithm namely SEA and GAMMA. The function
SEA depicts the steps to calculate self-attention maps of the feature vectors.
Function GAMMA is the main backbone network. It first creates the new dataset
using Generative Variational mapping of $\phi$. It uses cycleGAN as the
mapping. The generated data is then passed to the training phase where the
features are extracted and then are fed to the SEA function which generates
the self-attention feature maps. And this final self-attention output is fed
to the RPN to learn the attentive marine debris detector.

Algorithm 1 GAMMA : Generative Augmentation for Attentive Marine Debris
Detection

1:function SEA($f_{1}$, Q, K, V)

2: $QK\leftarrow softmax(Q\times K)$ $\triangleright$ Converts the resultant
vector into probability distribution

3: $ATmap\leftarrow QK\times V$ $\triangleright$ Generates attention maps

4: $SAmap\leftarrow ATmap\times\gamma+f_{1}$$\triangleright$ Concatenates
attention maps with base feature map.

5: $\textbf{return }SAmap$

6:function GAMMA($\phi,F_{1},Q,K,V$)

7: $T\leftarrow loadTerrestrialData()$

8: $W\leftarrow loadMarineStyleData()$

9: $Data\leftarrow\phi(T,W)$ $\triangleright$ Marine debris dataset generator
using $\phi$ (cycleGAN)

10: for $x_{i}$, $y_{i}$ $\in$ $Data$ do$\triangleright$ Training Attentive
Object Detector

11: $f_{1}\leftarrow F_{1}(x_{i})$

12: $SAmap\leftarrow SEA(f1,Q,K,V)$ $\triangleright$ Generate Self-attention
map

13: $Ldet\leftarrow RPN(SAmap,y_{i})$ $\triangleright$ Generate ROIs and
detection loss

14: return  Ldet

##  4 Experiments

###  4.1 Implementation Details

We use the PyTorch framework for all the training tasks. Our proposed dataset
consists of a total of $7,930$ images of which $6,786$ images are used for
training and $1,144$ images are used for evaluation. We use a $60-40\%$ split
for existing (J-EDI) and augmented training data using our dataset generator
framework, which is only used in training, evaluation is done only on non-
augmented test images.

Variational dataset generator using cycleGAN. Following the practices in [10],
we train our network from scratch, with a learning rate of $0.0002$.
Similarly, we divide the objective by two while optimizing the discriminator,
which slows down the rate at which it learns, relative to the rate of the
generator. We keep the same learning rate for the first $100$ epochs and
linearly decay the rate to zero over the next $100$ epochs. Weights are
initialized from a gaussian distribution $N(0,0.02)$. For all the experiments,
we set $\lambda=10$ in equation 3. We use the Adam solver [30] with a batch
size of $1$. We train the model for over $200$ epochs.

Attentive Object Detection. We employ VGG-16 [31] as backbone network for
detection, where their weights are pre-trained on the Imagenet Dataset [32].
In all our experiments the shorter side of all the training and testing images
is resized to 600. Each batch in our training data is composed of four images.
We fine-tune the detection network with a learning rate of $1\times 10^{-3}$
for $1600$ iterations and then reduce the learning rate to $1\times 10^{-4}$
for the other $2000$ iterations. The momentum of $0.9$ and the weight decay of
$5\times 10^{-4}$ is used for VGG-16 [31] based detectors. In all experiments,
we use RoI-Align [33] for RoI feature extraction. For all the experiments, we
use mean average precision (mAP) metrics to evaluate the detection
performance.

###  4.2 Memory Usage

All the models are trained using a Linux Machine, using an NVIDIA GTX $1060$
GPU. Training of the presented models takes on the order of 2 days for
variational data generator and around a day for the attentive object detector.
A single forward pass takes around 6 GB of GPU memory per batch item for an
attentive object detector.

###  4.3 Results

Table 1 shows our experimental results for the task of marine debris detection
compared to the state-of-the-art as well as w or w/o using the SEA module. We
can see that our model beats the state-of-the-art [1] detection results, with
an improved performance gap of over $11\%$ using the SEA module and over
$9.3\%$ w/o using our SEA module. Also, we can see significant improvement in
per class detection APs, as over $12.3\%,17.1\%$ and $21.8\%$ of the plastic,
Rov, and bio classes respectively, compared to the state-of-the-art [1]. The
per-class APs of GAMMA w/o using the SEA module are also significantly
increased, which shows the potential of our variational dataset generator. We
get over $3\%$ improvement in the overall mAP of marine debris detection using
our SEA module, which proves the efficiency of our proposed architecture using
the self-attention mechanism. Also, it can be seen that we get significant
improvement in the mAP of the plastic class compared to [3], although being
trained on 3 different marine debris classes, as compared to [3] that only
trains on plastic class for marine debris detection. Notably, it’s also
because of the improved and efficient augmentation in our dataset as compared
to [2].

Table 1: Comparative results for marine debris detection Method | Dataset | Plastic | Rov | Bio | mAP
---|---|---|---|---|---
Trash Detector [1] | JAMSTEC JEDI | 83.3 | 73.2 | 71.3 | 81.0
Deep Plastic [3] | Deep Trash (Custom) | 85.0 | - | - | 85.0
GAMMA w/o SEA | GAMMA | 90.8 | 89.8 | 90.6 | 90.3
GAMMA (Ours) | GAMMA | 95.6 | 90.3 | 93.1 | 93.0
Figure 3: Attention map visualisation using SEA module

Figure 4: Marine Debris Detection results using GAMMA (left) and the state-of-
the-art (right).

Qualitative Visualisation and Analysis of Marine Debris Detection Results. We
perform qualitative visualizations and analysis on the marine debris detection
results. As seen in figure 4, the comparative detection results of our
proposed method GAMMA (left) and the state-of-the-art (right) are shown. We
can see that our method performs significantly improved detection as compared
to the state-of-the-art [1] and most importantly all the issues that we
discussed regarding the marine debris detection regarding turbidity or
similar-looking classes etc are all resolved using our method. As shown in the
figure, the first two rows show the cases where our model, GAMMA detects and
classifies the Bio class with high accuracy as compared to the state-of-the-
art method that detects it as a plastic class. This signifies the importance
and potential of our method to be able to classify the similar-looking classes
correctly without any confusion. The third and fourth rows show the
qualitative detection results where our model correctly detects the plastic in
the conditions of turbidity as well as the suspended plastic as compared to
the state-of-the-art which fails in such cases. Also, the last row shows the
detection results where our model detects the hardly observable plastic
efficiently where the state-of-the-art method fails as well. All these results
simply signify the importance of our proposed method GAMMA and also the SEA
module which helps in enhancing the important object instances using attention
mechanism, which helps the model successfully detect and classify the marine
debris efficiently even in the cases of turbidity, suspension, improper
lighting or even similar-looking classes detection.

Visualisation of Attention maps using SEA module. As shown in figure 3, we
visualize the generated self-attention feature maps using the SEA module in
our proposed design. These are the output features, $SA_{map}$ as given in the
equation 6 which are obtained using self-attention mechanism and are further
fed to RPN to learn attentive object detector. We can see in figure 3, the
attention map visualizations correctly enhance the significant instances of
the image, as both the plastic bags in the first row. This further helps in
improving detection results as can be seen comparatively in figure 4 (last
row) as discussed above. Failure cases. Also we show the failure cases, as can
be seen in the second row of the figure, where the attention map also tries to
attend regions of the image where non-debris objects like rocks come into the
picture along with the plastic debris. These are failure cases and we would
consider such cases as a part of future work where we work on improving the
design using multi-headed attention or additional improvements as required.

##  5 Motivation

According to the 5 Gyres organization, nearly 270,000 metric tons and 5.25
trillion items of plastic are on the surface of the world’s oceans. The
quantification of the buoyant marine plastic debris is important in
understanding the concentrations of trash across the world and identifying
high concentration garbage hotspots for its smooth removal. Marine plastic
debris affects at least 267 species worldwide including 87 percent of all sea
turtles and 44 percent of all seabird species and is also a cause of various
marine animal deaths. It also has a huge impact on wildlife causing ingestion,
entanglement, starvation, suffocation, infection, and drowning. Plastics also
routinely explode into the water, degrading the water quality with toxic
compounds and ends up harming human and animal health. Thus plastic pollution
not only poses an imminent threat to the marine environment but to human
health as well. It also has a huge impact on climate change. This makes it one
of the biggest problems of this generation and thus requires an efficient and
effective solution to tackle it.

Current methods of marine debris cleaning are confined to the surface debris
and don’t focus much on the suspended and settled plastic at the bed.
Currently, the technique to quantify floating plastic requires the use of a
manta trawl with manual intervention. This adds difficulty and requires a lot
of planning and incurs high cost. To solve this problem we propose a solution
using the power of computer vision and deep learning which can be incorporated
with autonomous underwater vehicles and help in the detection and collection
of marine debris.

##  6 Conclusion and Future Work

We presented GAMMA, a novel variational augmentation and attention-based
approach for marine debris detection. The relatively strong performance
demonstrates the efficiency of our method SEA to detect the debris
irrespective of the blurred background and lighting conditions. We also solve
the problem of hard-to-detect as well as similar-looking classes and improve
the detection performance using an attention mechanism as compared to the
state-of-the-art model. We also propose a new marine debris dataset using
variational augmentation which beats the state-of-the-art without even the SEA
module, highlighting the importance of our variational augmented dataset.
Extensive results and visualization prove the potential of the proposed method
to perform efficient marine debris detection, which can be also extended for
other domains.

In the future, we will try to optimize and quantize the algorithm to deploy it
on the edge devices as a part of AUV and test the proposed algorithm in real-
time. We will also try to improvise the dataset as well as the SEA (attention)
module to handle the failure cases.

##  7 Acknowledgments

The images in the dataset were a combination of the newly created dataset and
images sourced from the TrashCan dataset, which was hand-annotated by
researchers of the University of Minnesota from the JAMSTEC-JEDI dataset and
open-sourced. The authors would like to thank the researchers and would also
like to thank the Japan Agency for Marine-Earth Science and Technology for
open sourcing this data.

## References

  * [1] Michael Fulton, Jungseok Hong, Md Jahidul Islam, and Junaed Sattar.  Robotic detection of marine litter using deep visual detection models.  In 2019 International Conference on Robotics and Automation (ICRA), pages 5752–5758. IEEE, 2019.
  * [2] Jungseok Hong, Michael Fulton, and Junaed Sattar.  A generative approach towards improved robotic detection of marine litter.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 10525–10531. IEEE, 2020.
  * [3] Gautam Tata, Sarah-Jeanne Royer, Olivier Poirion, and Jay Lowe.  Deepplastic: A novel approach to detecting epipelagic bound plastic using deep visual models.  arXiv preprint arXiv:2105.01882, 2021.
  * [4] Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  NIPS, 2014.
  * [5] Emily L Denton, Soumith Chintala, Arthur Szlam, and Rob Fergus.  Deep generative image models using a laplacian pyramid of adversarial networks.  In NIPS, 2015.
  * [6] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  In ICLR, 2016.
  * [7] Jun-Yan Zhu, Philipp Krähenbühl, Eli Shechtman, and Alexei A Efros.  Generative visual manipulation on the natural image manifold.  In European conference on computer vision, pages 597–613. Springer, 2016.
  * [8] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1125–1134, 2017.
  * [9] Hajar Emami, Majid Moradi Aliabadi, Ming Dong, and Ratna Babu Chinnam.  Spa-gan: Spatial attention gan for image-to-image translation.  IEEE Transactions on Multimedia, 23:391–401, 2020.
  * [10] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2223–2232, 2017.
  * [11] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794–7803, 2018.
  * [12] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  NIPS, 2015.
  * [13] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [14] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In European conference on computer vision, pages 21–37. Springer, 2016.
  * [15] Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao.  Yolov4: Optimal speed and accuracy of object detection.  arXiv preprint arXiv:2004.10934, 2020.
  * [16] Glenn Jocher, Alex Stoken, Jirka Borovec, NanoCode012, Ayush Chaurasia, TaoXie, Liu Changyu, Abhiram V, Laughing, tkianai, yxNONG, Adam Hogan, lorenzomammana, AlexWang1900, Jan Hajek, Laurentiu Diaconu, Marc, Yonghye Kwon, oleg, wanghaoyang0106, Yann Defretin, Aditya Lohia, ml5ah, Ben Milanko, Benjamin Fineran, Daniel Khromov, Ding Yiwei, Doug, Durgesh, and Francisco Ingham.  ultralytics/yolov5: v5.0 - YOLOv5-P6 1280 models, AWS, Supervise.ly and YouTube integrations, April 2021.
  * [17] Jie Li, Katherine A Skinner, Ryan M Eustice, and Matthew Johnson-Roberson.  Watergan: Unsupervised generative network to enable real-time color correction of monocular underwater images.  IEEE Robotics and Automation letters, 3(1):387–394, 2017.
  * [18] Cameron Fabbri, Md Jahidul Islam, and Junaed Sattar.  Enhancing underwater imagery using generative adversarial networks.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7159–7165. IEEE, 2018.
  * [19] Yang-Jie Cao, Li-Li Jia, Yong-Xia Chen, Nan Lin, Cong Yang, Bo Zhang, Zhi Liu, Xue-Xiang Li, and Hong-Hua Dai.  Recent advances of generative adversarial networks in computer vision.  IEEE Access, 7:14985–15006, 2018.
  * [20] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein gan, Proceedings of the 34th International Conference on Machine Learning 2017.
  * [21] Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets, arXiv preprint arXiv:1411.1784 2014.
  * [22] Bin Dai and David Wipf.  Diagnosing and enhancing vae models.  arXiv preprint arXiv:1903.05789, 2019.
  * [23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NIPS, 2017.
  * [24] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  arXiv preprint arXiv:1609.08144, 2016.
  * [25] Jan Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio.  Attention-based models for speech recognition.  Advances in Neural Information Processing Systems, 2015.
  * [26] William Chan, Navdeep Jaitly, Quoc Le, and Oriol Vinyals.  Listen, attend and spell: A neural network for large vocabulary conversational speech recognition.  In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4960–4964. IEEE, 2016.
  * [27] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena.  Self-attention generative adversarial networks.  In International conference on machine learning, pages 7354–7363. PMLR, 2019.
  * [28] Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jonathon Shlens.  Stand-alone self-attention in vision models.  NIPS, 2019.
  * [29] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  arXiv preprint arXiv:2104.14294, 2021.
  * [30] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [31] Karen Simonyan and Andrew Zisserman.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  In 3rd International Conference on Learning Representations, ICLR 2015, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [32] J. Deng, W. Dong, R. Socher, L. Li, Kai Li, and Li Fei-Fei.  Imagenet: A Large-Scale Hierarchical Image Database.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [33] Kaiming He, Georgia Gkioxari, Piotr Dollar, and Ross Girshick.  Mask R-CNN.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.


§ ORBIT OF A BOX

In this section, we study the set of all boxes that can be generated given many copies of a starting box $\P$ and a wiring $\W$.
After introducing the orbit of a box, we provide some consequences to communication complexity. Subsequently, we study a particular example, $\Wbs$, with which we find collapsing boxes in [Subsection]subsection:analytical-results, and then we give some general remarks about other orbits.
Finally, we conclude this section by giving the technical proof of the theorem stating that the “best" parenthetization is the multiplication on the right.

§.§ Definition

Given multiple copies of a non-signalling box $\P\in\NS$ and of a (mixed) wiring $\W$, Alice and Bob can produce many other boxes, $(\P\boxtimes_\W\P)\boxtimes_\W\P$ or $\P\boxtimes_\W(\P\boxtimes_\W\P)$. All of these new boxes are again non-signalling because $\NS$ is closed under wirings, see [Lemma]lemma: NS closed under mixed wirings. We call orbit of the box $\P$ (induced by the wiring $\W$) the set of all of these possible new boxes:

\begin{align*}
\Orbit_\W(\P)
\,:=\,&
\Big\{
\text{\footnotesize boxes $\Q\in\NS$ that can be produced by using finitely many times the box $\P$ and the wiring $\W$}
\Big\} \\
\,=\,&
\bigcup_{k\geq1} \Orbit_\W^{(k)}(\P) \subseteq\NS
\,,
\end{align*}

where $\Orbit^{(k)}(\P)$ is called the orbit of depth $k$ of $\P$ (or simply $k$-orbit), defined as:

\[
\Orbit_\W^{(k)}(\P)
\,:=\,
\Big\{
\text{all possible products with $k$ times the term $\P$, using the multiplication $\boxtimes_\W$}
\Big\}
\,.
\]

When the context is clear, we overload the notation and write $\Orbit$ and $\Orbit^{(k)}$ respectively.
In general, these $k$-orbits are not singletons for $k\geq 3$ since
the algebra $\B_\W$ induced by $\W$ is not necessarily associative and commutative (see [Figure]fig: commutativity and associativity of the induced algebras). Actually, up to multiplicity, the cardinal $\#\Orbit^{(k)}$ is exactly the number of parenthesizations with $k$ terms, which is the Catalan number $\frac{1}{k}\tiny\begin{pmatrix} 2k-2 \\k-1 \end{pmatrix}$, which grows exponentially fast.
Here are the $3$- and $4$- orbits:

\begin{align*}
\Orbit^{(3)}(\P)
\,=\,
\Big\{
\P\boxtimes(\P\boxtimes\P)
\Big\}\,,
\\
\Orbit^{(4)}(\P)
\,=\,
\Big\{
\text{\footnotesize$
\big((\P\boxtimes\P)\boxtimes\P\big)\boxtimes\P,\,
\big(\P\boxtimes(\P\boxtimes\P)\big)\boxtimes\P,\,
\P\boxtimes\big((\P\boxtimes\P)\boxtimes\P\big),\,
\P\boxtimes\big(\P\boxtimes(\P\boxtimes\P)\big)
\Big\}\,.
\end{align*}

Note that a $k$-orbit ($k\geq2$) can be inductively computed using orbits with lower depth:

\[
\Orbit^{(k)}
\,=\,
\bigcup_{1\leq\ell\leq k-1}
\Orbit^{(\ell)} \boxtimes \Orbit^{(k-\ell)}
\,,
\]

which is the same recurrence relation as that of Catalan numbers.

§.§ Consequences to Communication Complexity

Assume Alice and Bob are given infinitely many copies of a nonlocal box $\P$, and assume they want to distantly compute (in finite time) the value of a Boolean function $f(X,Y)$, where $X,Y\in\{0,1\}^n$ are strings that are known by Alice and Bob respectively.
Among all the possible protocols they can try to do in order to succeed, they can wire their copies of $\P$ in order to produce a “better" box. For example, starting from a noisy box $\P$, Alice and Bob can try to produce a box that is closer to the “perfect box" $\PR$ which satisfies $a\oplus b = xy$ without noise.
Such a protocol is called a distillation protocol <cit.>.

Find Collapsing Boxes Using the Orbit.
Imagine Alice and Bob are able to produce a collapsing box $\Q$ after applying wirings to copies of a starting box $\P$. Then they can use that new box $\Q$ to distantly compute the value $f(X,Y)$, which means that they have a protocol to collapse communication complexity and therefore that $\P$ is collapsing.
This point of view is particularly interesting since it implies that it is sufficient to find a single collapsing box in the union $\bigcup_\W \Orbit_\W(\P)$ to deduce that $\P$ is collapsing as well.
See an illustration in [Figure]fig: collapsing orbits (a).

Find Collapsing Boxes Using a Cone.
Once we find a collapsing box $\P$, we can deduce many other collapsing boxes: there is a convex cone taking origin at $\P$ that is collapsing as well. More precisely, given a box $\P$, denote $\C_\P$ the convex cone of boxes $\Rbox$ for which there exists a local correlation $\L\in \LL$ such that $\P=\lambda\,\Rbox + (1-\lambda)\,\L$, with $\lambda\in[0,1]$.
We claim that if $\P$ is collapsing, then any $\Rbox\in\C_\P$ is collapsing as well.
Indeed, assume Alice and Bob are given copies of a box $\Rbox$.
Then, they can use shared randomness to produce the wanted box $\L$ and the wanted convex coefficient $\lambda$, so that they can generate the box $\P$ with the relation $\P=\lambda\,\Rbox + (1-\lambda)\,\L$. Now, as $\P$ is collapsing, they have a protocol that collapses communication complexity, hence $\Rbox$ is collapsing as well.
See an illustration in [Figure]fig: collapsing orbits (b).
In the study of collapsing boxes, notice that it is standard to assume that shared randomness is a “free" resource; for instance Brassard et. al. made that choice in <cit.> in their collapsing protocol.

Combining arguments from these last two paragraphs and by the fact that Alice and Bob can make a convex combination of boxes using shared randomness, we deduce a sufficient criterion for a box to collapse communication complexity:

Let $\P$ be a box in $\NS$. If there exists a box $\Q\in \Conv\big(\LL\cup \bigcup_\W\Orbit_\W(\P) \big)$ that collapses communication complexity, then $\P$ is collapsing as well.  See

Orbits that collapse communication complexity.

§.§ Case Study: Orbit of $\Wbs$

In this subsection, we focus our attention on the wiring $\Wbs$ inspired by Brunner and Skrzypczyk <cit.>. Denote $\boxtimes$ the corresponding box multiplication. Define the shared randomness box as $\SR:=(\P_0+\P_1)/2$; it is designed to output a couple $(a,b)$ such that $a=b$ uniformly and independently of the inputs. From the multiplication table in [Figure]fig: multiplication table, one can see that the $2$-dimensional affine space $\A:=\Aff\{\PR, \SR, \I\}$ is stable under $\boxtimes$.
As a consequence, the orbit $\Orbit(\P)$ of any box $\P$ in $\A$ is itself included in $\A$, and as $\A$ is two-dimensional, it is particularly easy to draw the orbit of a box in that case.
We represent an orbit in [Figure]figure: orbit of a box.

Example of a box orbit, drawn for depth up to $k=12$.
The quantum area $\QQ$ (in pink) is drawn using formulas from <cit.>.
Dark green represents the collapsing area that was found by Brassard et. al. in <cit.>, which consists of all the boxes with $\CHSH$-value higher than $\frac{3+\sqrt{6}}{6}\approx0.91$.
The orbit is drawn in yellow and orange dots — observe that it intersects the collapsing area in dark green, so [Propostion]prop: collapsing orbit tells us that the starting box $\P$ is collapsing.
The black circles represent the boxes that were studied in <cit.>, doing “pairwise" multiplications: $\P$, $\P\boxtimes\P$, $(\P\boxtimes\P)\boxtimes(\P\boxtimes\P)$, etc... Each iteration is the wiring of two copies of the previous iteration, it gives a subset of our orbit. As displayed in the drawing and detailed in the proof of [Proposition]theo: new known collapsing boxes, our method allows us to find a larger set of boxes $\P$ that are collapsing.

By definition of the affine space $\A$, any box $\Abox\in\A$ can be uniquely written as $\Abox=c_1(\Abox)\,\PR + c_2(\Abox)\,\SR + c_3(\Abox)\,\I$ for some real coefficients $c_i(\Abox)$ that sum to $1$, called convex coordinates of $\Abox$ in the affine basis $\{\PR, \SR, \I\}$. An interesting aspect of considering convex coordinates is that it gives a simple characterization of the parallelism property of lines:

\begin{equation}   \label{eq:equivalent-condition-of-being-parallel}
\forall \Abox,\Bbox\in\A,\quad\quad
\Aff\{\Abox, \Bbox\}\, ||\, \Aff\{\PR, \SR\}
\quad\Longleftrightarrow\quad
c_3(\Abox) = c_3(\Bbox)\,.~~\footnote{Indeed, for $\Abox\neq\Bbox\in\A$ whose convex coefficients are respectively $a_1, a_2, a_3$ and $b_1, b_2, b_3$, saying that the line $\Aff\{\Abox, \Bbox\}$ is parallel to the line $\Aff\{\PR, \SR\}$ is equivalent to knowing that there exists a scalar $\lambda\in\R^*$ such that $\Abox-\Bbox = \lambda\,(\PR-\SR)$, \ie we have three equations: $a_1-b_1=\lambda$ and $a_2-b_2 = -\lambda$ and $a_3-b_3=0$. Now, using the normalization condition $\sum_i a_i = \sum_j b_j = 1$ and after removing redundant equations, this condition simplifies $a_3 = b_3$, as claimed.}
\end{equation}

Moreover, in our case, we have an additional interesting property of the third convex coordinate:

The function $1-c_3(\cdot)$ is multiplicative:

\[
\forall \Abox,\Bbox\in\A,\quad\quad
1-c_3(\Abox\boxtimes\Bbox) = \big(1-c_3(\Abox)\big)\,\big(1-c_3(\Bbox)\big)\,.
\]

The multiplication table induced by the wiring $\Wbs$ <cit.> is:

\begin{equation}   \label{eq:multiplication-table-PR-SR-I}
\text{
\setlength{\length}{0.6cm}
\small
\renewcommand{\arraystretch}{1.5}
\newcommand{\mycommand}{\normalsize}
\begin{tabular}{| c ||c|c|c|c|c|c|c|c|}
\hline
{\small\diagbox{$\P$}{$\Q$}} & \hspace{\length}{\mycommand$\PR$}\hspace{\length} & \hspace{\length}{\mycommand$\SR$}\hspace{\length} & \hspace{\length}{\mycommand$\I$}\hspace{\length} \\
\hline\hline
{\mycommand$\PR$} &  $\PR$ & $\PR$& $\I$  \\ \hline
{\mycommand$\SR$} & $\textstyle\frac{1}{2}\PR + \frac12\SR$  & $\SR$ & $\I$  \\ \hline
{\mycommand$\I$}  & $\textstyle\frac14\PR - \frac14\SR + \I$ &  $\I$ & $\I$  \\ \hline
\end{tabular}
\renewcommand{\arraystretch}{1}
\end{equation}

where each cell displays the result of $\P\boxtimes\Q$.
For $\Abox, \Bbox\in\A$ whose coefficients $c_i$ are denoted $a_1, a_2, a_3$ and $b_1, b_2, b_3$ for the sake of readability,
we use the bilinearity of the product $\boxtimes$ and we get:

\begin{align*}
\Abox\boxtimes\Bbox
\,=\,
\Big[ \textstyle a_1b_1 + a_1b_2 + \frac12 a_2 b_1 + \frac14 a_3 b_1 \Big]\,\PR
\,+
\Big[ \textstyle\frac12 a_2 b_1 + a_2 b_2 - \frac14 a_3 b_1 \Big]\,\SR
\\
& \quad +
\Big[ a_1b_3 + a_2 b_3 + a_3 b_1 + a_3 b_2 + a_3 b_3 \Big]\,\I\,.
\end{align*}

Hence, using the normalization property of coefficients $\sum_i a_i = \sum_j b_j = 1$, the third coefficient simplifies as $b_3 + a_3(1-b_3)$, which is equal to $1-(1-a_3)(1-b_3)$ as wanted.

Now, interestingly, we observe that the points of a given $k$-orbit are all aligned, and we even know the equation of the line:

For any $k\geq1$ and $\P\in\mathcal \mathcal \A$, the points of $\Orbit^{(k)}(\P)$ are all aligned on a line $\line_k$ whose expression in convex coordinates is given by:

\[
\line_k
\,:=\,
\Big\{ \Abox\in\A\,:\, c_3(\Abox) = 1 - \big(1-c_3(\P)\big)^k \Big\}\,.
\]

We prove by induction on $k\geq1$ that $\Orbit^{(k)}\subseteq\line_k$.
For $k=1$, the $1$-orbit contains only one element, namely $\P$, which obviously satisfies $c_3(\P) = 1 - \big(1-c_3(\P)\big)$, so $\P$ indeed belongs to $\line_1$.
Now, assume the result holds until some integer $k\geq1$, and let $\Q\in\Orbit^{(k)}$. By definition, the box $\Q$ decomposes as $\Q=\Q_1\boxtimes\Q_2$, for some $\Q_1\in\Orbit^{(\ell)}$ and $\Q_2\in\Orbit^{(k-\ell)}$ for some $1\leq \ell \leq k-1$. By the induction hypothesis, we know that
c_3(\Q_1) = 1 - \big( 1-c_3(\P) \big)^\ell$ and
$c_3(\Q_2) = 1 - \big( 1-c_3(\P) \big)^{k-\ell}\,.
Then using [Lemma]lem:multiplicativity-of-the-third-coef, we obtain:

\begin{align*}
\,=\, &
1 - \big( 1-c_3(\Q_1) \big)\,\big( 1-c_3(\Q_2) \big)
\\
\,=\, &
1 - \big( 1-c_3(\P) \big)^\ell\,\big( 1-c_3(\P) \big)^{k-\ell}
\\
\,=\, &
1 - \big( 1-c_3(\P) \big)^k\,,
\end{align*}

which means that $\Q$ belongs to the line $\line_k$.

As a consequence, we see that all the points of the $k$-orbit have the same third convex coefficient, so using the equivalence given in [Equation]eq:equivalent-condition-of-being-parallel, we obtain:

The supporting line $\line_k$ of all the orbits $\Orbit^{(k)}$ are parallel to the diagonal line $\line_D:=\Aff\{\PR, \SR\}$:

\[
\forall k\geq1, \quad\quad \Orbit^{(k)}||\,\line_D\,.
\]

In particular, all the orbits are parallel to each other:

\begin{equation*}
\forall k,\ell\geq1,\quad \Orbit^{(k)}||\Orbit^{(\ell)}\,.
\tag*{\qed}
\end{equation*}

Moreover, looking closely at the sequence of coefficients $1 - \big(1-c_3(\P)\big)^k$ and noticing that the diagonal line $\line_D$ is defined by the equation $c_3(\Abox) = 0$, we see that:

Assume $\P\notin\line_D$.
Then the orbits are more and more distant from the diagonal line as $k$ grows.
Moreover, the sequence of lines $(\line_k)_k$ tends to the line $\line_\infty$ defined by the equation $c_3(\Abox)=1$, which is exactly the line passing through $\I$ and parallel to the diagonal $\line_D$.

It takes a lot of computational time to draw $k$-orbits of a box $\P$ as $k$ grows, since it requires to compute $\frac{1}{k}\tiny\begin{pmatrix} 2k-2 \\k-1 \end{pmatrix}$ elements (Catalan number), which grows exponentially.
However, our goal is not to compute the whole orbit, but simply to determine whether or not the orbit intersects the known collapsing area (dark green). To that end, one may notice that it is enough to compute the “highest" box of each $k$-orbit in the $y$-coordinate (see [Figure]figure: orbit of a box) and to check whether those “highest" boxes intersect the collapsing area (dark green area).
This is the purpose of the following proposition, which displays a simple expression of the “highest" box of each $k$-orbit, and which allows much faster tests of a box $\P$ being collapsing or not without computing all the points of the orbit.
We prove this result only in a subset of the orbit, that we call tilted orbit, which is easier to manipulate in inductions, and which is defined by $\Orbittilde{}^{(1)}(\P)
\,:=\,
\{\P\}$ and for $k\geq2$:

\[
\Orbittilde{}^{(k)}
\,:=\,
\Big(\P \boxtimes \Orbittilde{}^{(k-1)}  \Big) \cup \Big( \Orbittilde{}^{(k-1)} \boxtimes \P  \Big)
\,=\,
\bigcup_{\ell\in\{1, k-1\}}
\Orbittilde{}^{(\ell)} \boxtimes \Orbittilde{}^{(k-\ell)}
\subseteq
\Orbit^{(k)}
\,.
\]

Note that the cardinality of that set is $\#\Orbittilde{}^{(k+1)}=2^k$, up to multiplicity.
We call $\CHSH$-value the $y$-coordinate, indicating how “high" is a box:

\CHSH(\P)
\,:=\,
\mathbb P\big( \text{win at $\CHSH$} \big)
\,=\,
\frac14 \sum_{a\oplus b=xy} \P(a,b\,|\,x,y)\,.

We say that a tilted orbit distills the $\CHSH$-value if it contains a box $\Q$ such that $\CHSH(\Q)\geq\CHSH(\P)$. In the following theorem, we present the expression of the best parenthetization in terms of $\CHSH$-value, which confirms the numerical intuition reported in <cit.>:

Let $\P\in\Atilde$ be a box, and let $k\geq2$ an integer such that the tilted $(k-1)$-orbit distills the $\CHSH$-value.
Then the highest $\CHSH$-value of $\Orbittilde{}^{(k)}(\P)$ is achieved at a box whose expression is the product of $k$ times $\P$ on the right:

\[
\P^{\boxtimes k}
\,:=\,
\Big(\big(\text{\small$(\P\boxtimes\P)$}\boxtimes \P\big)\cdots\Big)\boxtimes\P
\,\,\in
\underset{\Q\in\Orbittilde{}^{(k)}(\P)}{\argmax} \,\,\,\CHSH(\Q)
\,.
\]

See [Subsection]appendix: proof of Highest Box proposition.

We conjecture that the same result actually holds without the tilde, the right multiplication $\P^{\boxtimes k}$ gives the highest $\CHSH$-value of $\Orbit^{(k)}(\P)$, as observed numerically.
An idea of the proof could be to use Dyck paths. Each time we open/close a parenthesis, the path goes up/down respectively, which produces a certain Dyck path.
The statement to be proved is that each time we convert a $\vee$ into a $\wedge$, the $\CHSH$-value is non-decreasing. Then, we would have that the best Dyck path is necessarily the one that always goes up first and then always goes down, which corresponds to the multiplication of boxes on the right.

As previously mentioned, the next theorem is concurrent and independent of the work of <cit.>:

The techniques described in [Subsection]subseq:ConsequencestoCommunicationComplexity allow the discovery of new collapsing boxes.
See new collapsing areas in [Figure]fig:numerical-new-collapsing-regions.

See [Figure]figure: orbit of a box for an intuition of the proof.
Take the starting box $\P$ with coordinates $(0.627, 0.862)$ in the affine plane $\A=\Aff\{\PR, \SR, \I\}$, where the coordinate system is given by the $\CHSH'$- and $\CHSH$- values of $\P$.
On the one hand, the tilted orbit of $\P$ intersects the collapsing area that was found in <cit.> (in dark green), since for instance $\CHSH(\P^{\boxtimes5}) \approx 0.913 > 0.908 \approx \frac{3+\sqrt{6}}{6}$, so $\P$ is collapsing by [Proposition]prop: collapsing orbit.
On the other hand, this box $\P$ does not lie in any of the previously-known collapsing areas from <cit.> (to the best of our knowledge, these five references are the only previous results showing a collapse of communication complexity, in addition to <cit.> which concurrently and independently found a similar result to ours as mentioned before).
Indeed, it is not in the collapsing areas from <cit.> since $\CHSH(\P)=0.862<0.908$, nor is it in the collapsing area from <cit.> since $A+B \approx 14.13 < 16$ (using the authors' notation).
The box $\P$ neither is in any of the collapsing regions found in <cit.> since it does not belong to the boundary $\partial\NS$ of the non-signalling set.
The last area to check is the one from <cit.>, which was numerically found. From a box $\P$, they define a sequence of boxes using “pairwise" multiplications: $\Q_1 := \P$ and $\Q_{n+1}:=\Q_n\boxtimes\Q_n$ for $n\geq1$, and they check whether or not there exists an integer $n$ such that $\CHSH(\Q_n)>\frac{3+\sqrt{6}}{6}$. But, for our starting box $\P$, none of the $\Q_n$ satisfy this inequality: indeed, for $1\leq n\leq 5$, it possible to check it by hand, for $n=6$ we have $\Q_6\in \LL$, and for $n\geq7$ we also have $\Q_n\in\LL$ since $\LL$ is closed under wirings <cit.>.
Hence our example $\P$ is a new collapsing box.

§.§ Some Other Orbits

In the previous subsection, we studied specifically the orbit of the wiring $\Wbs$ in the slice of $\NS$ passing through the boxes $\PR$, $\SR$, $\I$.
Here we comment on some examples of other orbits in three different ways:
(i) it is possible to study the same wiring $\Wbs$ but in different slices of $\NS$;
(ii) it is possible to study another wiring than $\Wbs$ but to keep the same slice as in the previous subsection;
(iii) it is possible to change both the wiring and the slice.
See [Appendix]sec:drawing-of-some-orbits for many drawings.

(i) We keep the wiring $\Wbs$ and we consider the slice of $\NS$ passing through $\PR$, $\P_0$, $\P_1$.
Notice that we prove in [Proposition]prop:PR-P0-P1-is-a-face-of-NS that this slice is actually precisely the convex combination of the three points.
We draw two examples of such an orbit in [Figure]figure:orbit-of-Wbs-in-a-different-slice, with two different starting boxes. We observe that both of them seem to recover the alignment and parallelism properties that we showed in [Theorem]theo: alignment and parallelism and its corollary. Again, these lines seem all parallel to what we called previously the diagonal line $\line_D$, which is defined as the line passing through $\PR$ and $\SR=\frac12(\P_0+\P_1)$.
Notice that we show in [Theorem]thm: the triangle PR-P0-P1 is collapsing that all the boxes of this triangle are actually collapsing, except the ones in the segment $\Conv\{\P_0, \P_1\}$, drawn in pink.

Orbit of $\Wbs$ in a different slice than in [Subsection]subsec:case-study: here we consider the slice of $\NS$ passing through $\PR$, $\P_0$, and $\P_1$. We represent the orbit with two different starting boxes.
Each orbit is drawn with depth going until $k=12$.
The game $\G$ is defined by the winning rule $a=0$ and $b=y$.

(ii) Among the “typical" wirings defined in [Subsection]subsec:typical-examples-of-wirings, the only ones that stabilize the plane $\Aff\{\PR, \SR, \I\}$ are $\Woplus$ and $\Wbs$, see [Appendix]ap:the-multiplication-tables.
This is why, for these two wirings, we can conveniently draw the orbits in a plane.
The orbit of $\Woplus$ is drawn in [Appendix]sec:drawing-of-some-orbits (a). We observe that each $k$-orbit contains only one element, which is not surprising since we know from [Figure]fig: commutativity and associativity of the induced algebras that its induced algebra is associative, meaning that the choice of parenthetization does not lead to a different result.
In the same appendix, we also draw the orbit for three other wirings. Surprisingly, we observe that the three new orbits look the same as the orbit of $\Wbs$.

(iii) We add the slice $\PR$, $\P_0$, $\P_1$ for each wiring of [Appendix]sec:drawing-of-some-orbits. We observe that the alignment and parallelism properties seem to still hold in those cases, as before. Moreover, we see that the example (d) distills the $\CHSH$-value better than the other examples in that slice.

§.§ Proof of [Theorem]theo: highest box

Recall that $\SR := (\P_0+\P_1)/2$ is the shared randomness box.
Given a non-signalling box $\P\in\NS$, its $\CHSH$- and $\CHSH'$- values are defined as follows:

\[
\CHSH(\P)
\,:=\,
\frac14
\sum_{a\oplus b=xy} \P(a,b\,|\,x,y)\,,
\quad\quad \text{and} \quad\quad
\CHSH'(\P)
\,:=\,
\frac14
\hspace{-0.4cm}
\sum_{\tiny\begin{array}{c}a\oplus b\\=(x\oplus1)(y\oplus1)\end{array}}\hspace{-0.4cm} \P(a,b\,|\,x,y)\,.
\]

For example, we have $\CHSH(\PR) = 1$ and $\CHSH(\SR)=\frac34$ and $\CHSH(\I) = \frac12$.
Denote $\A$ the affine space $\A:=\Aff\{\PR, \SR, \I\}$, and denote $\Atilde\subseteq \A$ the set of boxes $\P$ in the convex hull $\Conv\{\PR, \SR, \I\}$ whose $\CHSH$-value is $\geq3/4$.
We will prove our results in $\Atilde$; by symmetry of the problem, similar results also hold in other areas, such as $2\I-\Atilde$ the symmetric of $\Atilde$ by $\I$.

Let $\P\in\Atilde$, and let $\Q\neq\Rbox\in\A$ such that the line $\Aff\{ \Q, \Rbox\}$ is parallel to the diagonal line $\line_D:=\Aff\{\PR, \SR\}$.
We have:

\[
\CHSH(\Q)\geq\CHSH(\Rbox)
\quad\quad \Longrightarrow \quad\quad
\left\{
\begin{array}{c}
\CHSH(\Q\boxtimes \P)\geq\CHSH(\Rbox\boxtimes \P)\,,\\
\CHSH(\P\boxtimes \Q)\geq\CHSH(\P\boxtimes \Rbox)\,.
\end{array}
\right.
\]

As the box $\P$ lies in $\Atilde$, it is of the form $\P=p_1\PR + p_2\SR + (1-p_1-p_2)\I$ for some coefficients $p_1,p_2\geq0$ such that $p_1+p_2\leq1$.
Rewrite it as $\P = \tiny \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}$, and similarly denote $\Q = \tiny \begin{pmatrix} q_1 \\ q_2 \end{pmatrix}$ and $\Rbox = \tiny \begin{pmatrix} r_1 \\ r_2 \end{pmatrix}$ for some coefficients $q_i, r_j\in\R$.
By the parallelism assumption, vectors $\Q-\Rbox$ and $\PR-\SR$ have to be colinear,  there must exist some $\lambda\in\R^*$ such that $\Q-\Rbox = \lambda(\PR-\SR) = \lambda \tiny \begin{pmatrix} 1 \\ -1 \end{pmatrix}$, so we may rewrite the second coefficient of $\Rbox$ as $r_2 = q_1 + q_2 - r_1$.
With this notation, we can use the linearity of the function $\CHSH(\cdot)$ to see that condition $\CHSH(\Q)\geq\CHSH(\Rbox)$ simplifies to $(q_1-r_1)\geq0$:

\begin{align*}
\small
\CHSH(\Q)\!-\!\CHSH(\Rbox)
\small
(q_1\!-\!r_1) \!\times\! \CHSH(\PR)
+ (q_2\!-\!r_2)\!\times\! \CHSH(\SR)
+ \Big(\!(1\!-\!q_1\!-\!q_2) \!-\! (1\!-\!r_1\!-\!r_2)\!\Big)\!\times\! \CHSH(\I)
\\
(q_1-r_1) \times 1
- \textstyle (q_1-r_1)\times\frac34
+ 0 \times \frac12
\\
\textstyle
\frac14(q_1-r_1)\,.
\end{align*}

Now, using the multiplication table from [Figure]fig: multiplication table and bilinearity of $\boxtimes$, we may compute the following expressions:

\begin{align*}
\CHSH(\Q\boxtimes \P)-\CHSH(\Rbox\boxtimes \P)
\textstyle\frac{1}{8} (p_1+2 p_2) (q_1-r_1)\geq0\,,
\\
\CHSH(\P\boxtimes \Q)-\CHSH(\P\boxtimes \Rbox)
\textstyle\frac{1}{16} (1-p_1+p_2) (q_1-r_1)\geq0\,,
\end{align*}

which gives the desired result.

For any $\P\in\Atilde$ and $\Q\in\Orbittilde(\P)$, we have:

\[
\CHSH(\Q)\geq\CHSH(\P)
\quad \Longrightarrow \quad
\CHSH\Big( \Q\boxtimes\P \Big)
\,\geq\,
\CHSH\Big( \P\boxtimes\Q \Big).
\]

Use the coordinate system $(x,y)$ given by the $\CHSH'$- and $\CHSH$- values respectively in order to write $\P$ and $\Q$ as taking coordinates $(x_\P, y_\P)$ and $(x_\Q, y_\Q)$.
For instance we have $\PR:(\frac12,1)$ and $\SR:(\frac34,\frac34)$ and $\I:(\frac12, \frac12)$.
Use the multiplication table from [Equation]eq:multiplication-table-PR-SR-I and apply the bilinearity of $\boxtimes$ in order to obtain the following expression:

\[
\CHSH\big( \Q\boxtimes\P \big)
\CHSH\big( \P\boxtimes\Q \big)
\,=\,
\textstyle \frac{1}{8} (12 x_\P y_\Q-12 y_\P x_\Q-7 x_\P+7 y_\P+7 x_\Q-7 y_\Q)
\,=:\,
f_\P(x_\Q, y_\Q)\,.
\]

For any fixed $\P\in\Atilde$, we want to show that $f_\P(x_\Q, y_\Q)\geq0$.
By construction, we know that $\P\in\line_1$ and $\Q\in\line_k$ for some $k\geq1$, so by [Corollary]coro:orbits-move-to-the-left we have $x_\Q + y_\Q \leq x_\P + y_\P$, which we may rewrite as $x_\Q \leq x_\P + y_\P - y_\Q$.
As $\P$ lies in $\Atilde$, we have $y_\P\geq \frac34$, so
the first partial derivative is non-positive:
$\frac{\partial}{\partial x_\Q} f_\P(x_\Q, y_\Q) = \frac18(7 - 12 y_\P) \leq -1/4\leq0$, which means that the function $f_\P(\cdot, y_\Q)$ is decreasing over $\R$ for any fixed $y_\Q$.
It yields the following inequalities:

\[
f_\P(x_\Q, y_\Q)
\,\geq\,
f_\P(x_\P + y_\P - y_\Q, y_\Q)
\,=\,
\textstyle\frac{3}{2}\big(y_\Q - y_\P\big) \big(x_\P + y_\P - \frac76\big)
\,\geq\,
\]

since both factors are non-negative:
the first one is non-negative using the hypothesis $\CHSH(\Q)\geq\CHSH(\P)$,
and the second one is non-negative using $x_\P\geq1/2$ and $y_\P\geq3/4$ since $\P\in\Atilde$. Hence $f_\P$ is non-negative and we obtain the wanted result.

Recall that the set $\Orbittilde{}^{(k)}(\P)$ is called the tilted $k$-orbit of the box $\P$ and contains some boxes $\Q$ that are generated by applying a wiring to copies of $\P$. We say that this tilted $k$-orbit distills the $\CHSH$-value if it contains a box $\Q$ such that $\CHSH(\Q)\geq\CHSH(\P)$. In that distilling scenario, we can compute the expression of a box achieving the best $\CHSH$-value:

[Theorem <ref>]
Let $\P\in\Atilde$ be a box, and let $k\geq2$ be an integer such that the tilted $(k-1)$-orbit distills the $\CHSH$-value.
Then the highest $\CHSH$-value of $\Orbittilde{}^{(k)}(\P)$ is achieved at a box whose expression is the product of $k$ times $\P$ on the right:

\[
\P^{\boxtimes k}
\,:=\,
\Big(\big(\text{\small$(\P\boxtimes\P)$}\boxtimes \P\big)\cdots\Big)\boxtimes\P
\,\,\in
\underset{\Q\in\Orbittilde{}^{(k)}(\P)}{\argmax} \,\,\,\CHSH(\Q)
\,.
\]

We prove the result by induction on $k\geq2$.
It is obviously true for $k=2$ since $\Orbittilde{}^{(2)}(\P)$ only contains $\P\boxtimes\P$.
Now, fix $k\geq2$ and assume $\CHSH(\P^{\boxtimes k})\geq\CHSH(\Q)$ for any $\Q$ in the tilted $k$-orbit (induction hypothesis). Assume as well that $\CHSH(\P^{\boxtimes k})\geq\CHSH(\P)$ (distillation hypothesis).
We want to show that:

\[
\CHSH(\P^{\boxtimes k+1}) \geq \CHSH(\Q\boxtimes\P)
\quad\quad\text{and}\quad\quad
\CHSH(\P^{\boxtimes k+1}) \geq \CHSH(\P\boxtimes\Q)\,,
\]

for all $\Q$ in the tilted $k$-orbit.
The first inequality follows from [Lemma]lem: Multiplication by P preserves the CHSH order using the relation $\P^{\boxtimes k+1} = \P^{\boxtimes k} \boxtimes \P$ and the induction assumption.
For the other inequality, start from $\CHSH(\P^{\boxtimes k+1}) = \CHSH(\P^{\boxtimes k}\boxtimes\P)$ and apply [Lemma]lem: Multiplication to the right is higher
in order to get $\geq \CHSH(\P\boxtimes \P^{\boxtimes k})$.
Then conclude using [Lemma]lem: Multiplication by P preserves the CHSH order and the induction hypothesis in order to obtain $\geq \CHSH(\P\boxtimes \Q)$
for any $\Q$ in the tilted $k$-orbit.