# Unbalanced Optimal Transport: A Unified Framework for Object Detection

Henri De Plaen1* Pierre-François De Plaen2* Johan A. K. Suykens1 Marc
Proesmans2
Tinne Tuytelaars2 Luc Van Gool2,3
1ESAT-STADIUS, KU Leuven, Belgium 2ESAT-PSI, KU Leuven, Belgium
3Computer Vision Lab, ETH Zürich, Switzerland

###### Abstract

During training, supervised object detection tries to correctly match the
predicted bounding boxes and associated classification scores to the ground
truth. This is essential to determine which predictions are to be pushed
towards which solutions, or to be discarded. Popular matching strategies
include matching to the closest ground truth box (mostly used in combination
with anchors), or matching via the Hungarian algorithm (mostly used in anchor-
free methods). Each of these strategies comes with its own properties,
underlying losses, and heuristics. We show how Unbalanced Optimal Transport
unifies these different approaches and opens a whole continuum of methods in
between. This allows for a finer selection of the desired properties.
Experimentally, we show that training an object detection model with
Unbalanced Optimal Transport is able to reach the state-of-the-art both in
terms of Average Precision and Average Recall as well as to provide a faster
initial convergence. The approach is well suited for GPU implementation, which
proves to be an advantage for large-scale models.

**footnotetext: These authors contributed equally.

|
---|---
|  |
|  |

A
---
B
---
1
---
2
---
3
---
4
---
5
---
(a) Image №163 from the VOC training dataset. The ground truth boxes are
colored, and the predictions are outlined in black.

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.61
---
0.96
---
0.8
---
1.34
---
0.88
---
0.8
---
0.88
---
0.89
---
0.8
---
0.4
---
0.65
---
0.8
---
1.11
---
0.73
---
0.8
---
(b) Costs between the predictions and the ground truth ($1-\mathrm{GIoU}$).
The background cost is $c_{\varnothing}=0.8$.

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(c) Prediction to best ground truth (Unbalanced OT with $\epsilon=0$,
$\tau_{1}\rightarrow+\infty$ and $\tau_{2}=0$).

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(d) Hungarian matching (OT with $\epsilon=0$, $\tau_{1}\rightarrow+\infty$ and
$\tau_{2}\rightarrow+\infty$).

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(e) Ground truth to best prediction (Unbalanced OT with $\epsilon=0$,
$\tau_{1}=0$ and $\tau_{2}\rightarrow+\infty$).

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(f) Unbalanced OT with $\epsilon=0.05$, $\tau_{1}=100$ and $\tau_{2}=0.01$.

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(g) OT with $\epsilon=0.05$ ($\tau_{1}\rightarrow+\infty$ and
$\tau_{2}\rightarrow+\infty$).

A
---
B
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
(h) Unbalanced OT with $\epsilon=0.05$, $\tau_{1}=0.01$ and $\tau_{2}=100$.

Figure 1: Different matching strategies. All are particular cases of
_Unbalanced Optimal Transport_. A match ($\hat{P}_{i,j}=1$) is denoted by a
black square and it is white if there is no match ($\hat{P}_{i,j}=0$).

##  1 Introduction

Object detection models are in essence multi-task models, having to both
localize objects in an image and classify them. In the context of supervised
learning, each of these tasks heavily depends on a matching strategy. Indeed,
determining which predicted object matches which ground truth object is a non-
trivial yet essential task during the training (Figure 1(a)). In particular,
the matching strategy must ensure that there is ideally exactly one prediction
per ground truth object, at least during inference. Various strategies have
emerged, often relying on hand-crafted components. They are proposed as
scattered approaches that seem to have nothing in common, at least at first
glance.

###  1.1 A Unifying Framework

To perform any match, a matching cost has to be determined. The example at
Fig. 1(b) uses the _Generalized Intersection over Union_ ($\mathrm{GIoU}$)
[giou]. Given such a cost matrix, matching strategies include:

  * •

Matching each prediction to the closest ground truth object. This often
requires that the cost lies under a certain threshold [liu2016ssd,
ren2015fasterrcnn, redmon2016yolo, lin2017focalloss], to avoid matching
predictions that may be totally irrelevant for the current image. The
disadvantage of this strategy is its redundancy: many predictions may point
towards the same ground truth object. In Fig. 1(c), both predictions 1 and 4
are matched towards ground truth object A. Furthermore, some ground truth
objects may be unmatched. A solution to this is to increase the number of
predicted boxes drastically. This is typically the case with anchors boxes and
region proposal methods.

  * •

The opposite strategy is to match each ground truth object to the best
prediction [he2015spatial, liu2016ssd]. This ensures that there is no
redundancy and every ground truth object is matched. This also comes with the
opposite problem: multiple ground truth objects may be matched to the same
prediction. In Fig. 1(e), both ground truth objects A and B are matched to
prediction 4. This can be mitigated by having more predictions, but then many
of those are left unmatched, slowing convergence [liu2016ssd].

  * •

A compromise is to perform a _Bipartite Matching_ (BM), using the _Hungarian
algorithm_ [kuhn1955hungarian, munkres1957algorithmstransportationhungarian],
for example [carion2020detr, zhu2020deformabledetr]. The matching is one-to-
one, minimizing the total cost (Definition 2). Every ground truth object is
matched to a unique prediction, thus reducing the number of predictions
needed, as shown in Fig. 1(d). A downside is that the one-to-one matches may
vary from one epoch to the next, again slowing down convergence
[li2022dndetr]. This strategy is difficult to parallelize, _i.e_. to take
advantage of GPU architectures.

All of these strategies have different properties and it seems that one must
choose either one or the other, optionally combining them using savant
heuristics [liu2016ssd]. There is a need for a unifying framework. As we show
in this paper, _Unbalanced Optimal Transport_[chizat2018unbalanced] offers a
good candidate for this (Figure 1). It not only unifies the different
strategies here above, but also allows to explore all cases in between. The
cases presented in Figures 1(c), 1(d) and 1(e) correspond to the limit cases.
This opens the door for all intermediate settings. Furthermore, we show how
regularizing the problem induces smoother matches, leading to faster
convergence of DETR, avoiding the problem described for the BM. In addition,
the particular choice of entropic regularization leads to a class of fast
parallelizable algorithms on GPU known as _scaling algorithms_
[cuturi2013sinkhorn, chizat2018scaling], of which we provide a compiled
implementation on GPU. Our code and additional resources are publicly
available111https://hdeplaen.github.io/uotod.

###  1.2 Related Work

Matching Strategies Most _two-stage_ models often rely on a huge number of
initial predictions, which is then progressively reduced in the region
proposal stage and refined in the classification stage. Many different
strategies have been proposed for the initial propositions and subsequent
reductions, ranging from training no deep learning networks
[girshick2014rcnn], to only train those for the propositions
[girshick2015fast, lin2017feature, he2015spatial], to training networks for
both propositions and reductions [ren2015fasterrcnn, pang2019libra,
he2017maskrcnn, cai2018cascade, dai2016r]. Whenever a deep learning network is
trained, each prediction is matched to the closest ground truth object
provided it lies beneath a certain threshold. Moreover, the final performance
of these models heavily depends on the hand-crafted anchors
[liu2020objectdetectionsurvey].

Many _one-stage_ models rely again on predicting a large number of initial
predictions or _anchor boxes_ , covering the entire image. As before, each
anchor box is matched towards the closest ground truth object with certain
threshold constraints [redmon2016yolo, lin2017focalloss]. In [liu2016ssd],
this is combined with matching each ground truth object to the closest anchor
box and a specific ratio heuristic between the matched and unmatched
predictions. The matching of the fixed anchors is justified to avoid a
collapse of the predictions towards the same ground truth objects.
Additionally, this only works if the number of initial predictions is
sufficiently large to ensure that every ground truth object is matched by at
least one prediction. Therefore, it requires further heuristics, such as _Non-
Maximal Suppression_ (NMS) to guarantee a unique prediction per ground truth
object, at least during the inference.

By using the _Hungarian algorithm_ , DETR [carion2020detr] removed the need
for a high number of initial predictions. The matched predictions are improved
with a multi-task loss, and the remaining predictions are trained to predict
the background class $\varnothing$. Yet, the model converges slowly due to the
instability of BM, causing inconsistent optimization goals at early training
stages [li2022dndetr]. Moreover, the sequential nature of the Hungarian
algorithm does not take full advantage of the GPU architecture. Several
subsequent works accelerate the convergence of DETR by improving the
architecture of the model [zhu2020deformabledetr, liu2021dabdetr] and by
adding auxiliary losses [li2022dndetr], but not by exploring the matching
procedure.

Optimal Transport The theory of _Optimal Transport_ (OT) emerges from an old
problem [monge1781memoire], relaxed by a newer formulation [kantorovich]. It
gained interest in the machine learning community since the re-discovery of
_Sinkhorn’s algorithm_ [cuturi2013sinkhorn] and opened the door for
improvements in a wide variety of applications ranging from graphical models
[montavon2016wasserstein], kernel methods [kolouri2016sliced,
de2020wasserstein], loss design [frogner2015learningwasserstein], auto-
encoders [tolstikhin2017wasserstein, kolouri2018sliced, rubenstein2018latent]
or generative adversarial networks [arjovsky2017wasserstein,
gulrajani2017improved].

More recent incursions in computer vision have been attempted, _e.g_. for the
matching of predicted classes [Han_2020_CVPR_Workshops], a loss for rotated
object boxes [pmlr-v139-yang21l] or a new metric for performance evaluation
[otani2022optimal]. Considering the matching of predictions to ground truth
objects, recent attempts using OT bare promising results [ge2021ota,
ge2021yolox]. However, when the _Hungarian algorithm_ is mentioned, it is
systematically presented in opposition to OT [ge2021ota, vo2022review]. We lay
a rigorous connection between those two approaches in computer vision.

_Unbalanced OT_ has seen a much more recent theoretical development
[chizat2018unbalanced, chizat-these]. The hard mass conservation constraints
in the objective function are replaced by soft penalization terms. Its
applications are scarcer, but we must mention here relatively recent machine
learning applications in motion tracking [9152115] and domain adaptation
[fatras2021unbalanced].

###  1.3 Contributions

  1. 1.

We propose a unifying matching framework based on _Unbalanced Optimal
Transport_. It encompasses both the _Hungarian algorithm_ , the matching of
the predictions to the closest ground truth boxes and the ground truth boxes
to the closest predictions;

  2. 2.

We show that these three strategies correspond to particular limit cases and
we subsequently present a much broader class of strategies with varying
properties;

  3. 3.

We demonstrate how entropic regularization can speed up the convergence during
training and additionally take advantage of GPU architectures;

  4. 4.

We justify the relevancy of our framework by exploring its interaction with
NMS and illustrate how it is on par with the state-of-the-art.

###  1.4 Notations and Definitions

Notations Throughout the paper, we use small bold letters to denote a vector
$\bm{a}\in\mathbb{R}^{N}$, with elements $a_{i}\in\mathbb{R}$. Similarly,
matrices are denoted by bold capital letters such as
$\bm{A}\in\mathbb{R}^{N\times M}$, with elements $A_{i,j}\in\mathbb{R}$. The
notation $\bm{1}_{N}$ represents a column-vector of ones, of size $N$, and
$\bm{1}_{N\times M}$ the matrix equivalent of size $N\times M$. The identity
matrix of size $N$ is $\bm{I}_{N,N}$. With $\llbracket
N\rrbracket=\\{1,2,\ldots,N\\}$, we denote the set of integers from $1$ to
$N$. The probability simplex uses the notation
$\Delta^{N}=\left.\left\\{\bm{u}\in\mathbb{R}_{\geq
0}^{N}\right|\sum_{i}u_{i}=1\right\\}$ and represents the set of discrete
probability distributions of dimension $N$. This extends to the set of
discrete joint probability distributions $\Delta^{N\times M}$.

Definitions For each image, the set $\\{\hat{\bm{y}}_{i}\\}_{i=1}^{N_{p}}$
denotes the predictions and $\\{\bm{y}_{j}\\}_{j=1}^{N_{g}}$ the ground truth
samples. Each ground truth sample combines a target class and a bounding box
position:
$\bm{y}_{j}=\left[\,\bm{c}_{j},\,\bm{b}_{j}\,\right]\in\mathbb{R}^{N_{c}+4}$
where $\bm{c}_{j}\in\\{0,1\\}^{N_{c}}$ is the target class in one-hot encoding
with $N_{c}$ the number of classes and $\bm{b}_{j}\in[0,1]^{4}$ defines the
relative bounding box center coordinates and dimensions. The predictions are
defined similarly
$\hat{\bm{y}}_{i}=[\,\hat{\bm{c}}_{i},\,\hat{\bm{b}}_{i}\,]\in\mathbb{R}^{N_{c}+4}$,
but the predicted classes may be non-binary
$\hat{\bm{c}}_{i}\in\left[0,1\right]^{N_{c}}$. Sometimes, predictions are
defined relatively to fixed anchor boxes $\tilde{\bm{b}}_{i}$.

(a) BM as a particular case of OT with no regularization ($\epsilon=0$). The
_Hungarian algorithm_ obtains the same solution.

(b) OT with regularization ($\epsilon\neq 0$). The regularization smoothens
the matching allowing for multiple connections.

(c) Unbalanced OT with regularization ($\epsilon\neq 0$ and
$\tau_{1}\ll\tau_{2}$). The smoothing is also visible.

(d) Matching each ground truth object to the closest prediction as Unbalanced
OT without regularization with $\epsilon=0$, $\tau_{1}=0$ and
$\tau_{2}\rightarrow\infty$.

Figure 2: Example of the influence of the parameters. The blue dots represent
predictions $\hat{\bm{y}}_{i}$. The red squares represent ground truth objects
$\bm{y}_{j}$. The distributions $\bm{\alpha}$ and $\bm{\beta}$ are defined as
in Prop. 1. The thickness of the lines is proportional to the amount
transported $P_{i,j}$. Only sufficiently thick lines are plotted. The dummy
_background_ ground truth $\bm{y}_{N_{g}+1}=\varnothing$ is not shown, nor are
the connections to it.

##  2 Optimal Transport

In this section, we show how _Optimal Transport_ and then its _Unbalanced_
extension unify both the _Hungarian algorithm_ used in DETR [carion2020detr],
and matching each prediction to the closest ground truth object used in both
Faster R-CNN [ren2015fasterrcnn] and SSD [liu2016ssd]. We furthermore stress
the advantages of entropic regularization, both computationally and
qualitatively. This allows us to explore a new continuum of matching methods,
with varying properties.

######  Definition 1 (Optimal Transport).

Given a distribution $\bm{\alpha}\in\Delta^{N_{p}}$ associated to the
predictions $\\{\hat{\bm{y}}_{i}\\}_{i=1}^{N_{p}}$, and another distribution
$\bm{\beta}\in\Delta^{N_{g}}$ associated with the ground truth objects
$\\{\bm{y}_{j}\\}_{j=1}^{N_{g}}$. Let us consider a pair-wise matching cost
$\mathcal{L}_{\text{match}}(\hat{\bm{y}}_{i},\bm{y}_{j})$ between a prediction
$\hat{\bm{y}}_{i}$ and a ground truth object $\bm{y}_{j}$. We now define
_Optimal Transport (OT)_ as finding the match $\bm{P}$ that minimizes the
following problem:

$\hat{\bm{P}}=\underset{\bm{P}\,\in\,\mathcal{U}(\bm{\alpha},\bm{\beta})}{\mathrm{arg\,min}}\left\\{\sum_{i,j=1}^{N_{p},N_{g}}P_{i,j}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right\\},$
(1)

with transport polytope (admissible solutions)
$\mathcal{U}(\bm{\alpha},\bm{\beta})=\left\\{\bm{P}\in\mathbb{R}_{\geq
0}^{N_{p}\times
N_{g}}:\sum_{j=1}^{N_{g}}P_{i,j}=\alpha_{i},\sum_{i=1}^{N_{p}}P_{i,j}=\beta_{j}\right\\}.$

Provided that certain conditions apply to the underlying cost
$\mathcal{L}_{\text{match}}$, the minimum defines a distance between
$\bm{\alpha}$ and $\bm{\beta}$, referred to as the Wasserstein distance
$\mathcal{W}(\bm{\alpha},\bm{\beta})$ (for more information, we refer to
monographs [villani2009optimal, santambrogio, peyre2019computational]; see
also Appendix A.2).

###  2.1 The Hungarian Algorithm

The Hungarian algorithm solves the _Bipartite Matching_ (BM). We will now show
how this is a particular case of Optimal Transport.

######  Definition 2 (Bipartite Matching).

Given the same objects as in Definition 1, the _Bipartite Matching (BM)_
minimizes the cost of the pairwise matches between the ground truth objects
with the predictions:

$\hat{\sigma}=\mathrm{arg\,min}\left\\{\sum_{j=1}^{N_{g}}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{\sigma(j)},\bm{y}_{j}\right):\sigma\in\mathcal{P}_{N_{g}}(\llbracket
N_{p}\rrbracket)\right\\},$ (2)

where $\mathcal{P}_{N_{g}}(\llbracket
N_{p}\rrbracket)=\left.\big{\\{}\sigma\in\mathcal{P}(\llbracket
N_{p}\rrbracket)\,\right||\sigma|=N_{g}\big{\\}}$ is the set of possible
combinations of $N_{g}$ in $N_{p}$, with $\mathcal{P}(\llbracket
N_{p}\rrbracket)$ the power set of $\llbracket N_{p}\rrbracket$ (the set of
all subsets).

BM tries to assign each ground truth $\bm{y}_{j}$ to a different prediction
$\hat{\bm{y}}_{i}$ in a way to minimize the total cost. In contrast to OT, BM
does not consider any underlying distributions $\bm{\alpha}$ and $\bm{\beta}$,
all ground truth objects and predictions are implicitly considered to be of
same mass. Furthermore, it only allows one ground truth to be matched to a
unique prediction, some of these predictions being left aside and matched to
nothing (which is then treated as a matching to the background $\varnothing$).
The OT must match all ground truth objects to all predictions, not allowing
any predictions to be left aside. However, the masses of the ground truth
objects are allowed to be split between different predictions and inversely,
as long as their masses correctly sum up
($\bm{P}\in\mathcal{U}(\bm{\alpha},\bm{\beta})$).

Particular Case of OT A solution for an imbalanced number of predictions
compared to the number of ground truth objects would be to add dummy ground
truth objects—the background $\varnothing$—to even the balance. Concretely,
one could add a new ground truth $\bm{y}_{N_{g}+1}=\varnothing$, with the mass
equal to the unmatched number of predictions. In fact, doing so directly
results in performing a BM.

######  Proposition 1.

The Hungarian algorithm with $N_{p}$ predictions and $N_{g}\leq N_{p}$ ground
truth objects is a particular case of OT with
$\bm{P}\in\mathcal{U}(\bm{\alpha},\bm{\beta})\subset\mathbb{R}^{N_{p}\times(N_{g}+1)}$,
consisting of the predictions and the ground truth objects, with the
background added
$\left\\{\bm{y}_{j}\right\\}_{j=1}^{N_{g}+1}=\left\\{\bm{y}_{j}\right\\}_{j=1}^{N_{g}}\cup\left(\bm{y}_{N_{g}+1}=\varnothing\right)$.
The chosen underlying distributions are

$\displaystyle\bm{\alpha}$ $\displaystyle=$
$\displaystyle\frac{1}{N_{p}}[\;\underbrace{1,\;1,\;1,\;\ldots,\;1}_{\text{$N_{p}$
predictions}}\;],$ (3) $\displaystyle\bm{\beta}$ $\displaystyle=$
$\displaystyle\frac{1}{N_{p}}[\;\underbrace{1,\;1,\;\ldots,\;1}_{\text{$N_{g}$
ground truth objects}},\;\underbrace{(N_{p}-N_{g})}_{\text{background
}\varnothing}\;],$ (4)

provided the background cost is constant:
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\varnothing\right)=c_{\varnothing}$.
In particular for $j\in\llbracket N_{g}\rrbracket$, we have
$\hat{\sigma}(j)=\left\\{i:P_{i,j}\neq 0\right\\}$, or equivalently
$\hat{\sigma}(j)=\left\\{i:P_{i,j}=1/N_{p}\right\\}$.

###### Proof.

We refer to Appendix B.1. ∎

In other words, we can read the matching to each ground truth in the columns
of $\hat{\bm{P}}$. The last columns represents all the predictions matched to
the background $\hat{\sigma}(N_{g}+1)$. Alternatively and equivalently, we can
read the matching of each prediction $i$ in the rows, the ones being matched
to the background have a $\hat{P}_{i,N_{g}+1}=1/N_{p}$.

Solving the Problem Both OT and BM are linear programs. Using generic
formulations would lead to a $\left(N_{p}+N_{g}+1\right)\times
N_{p}\left(N_{g}+1\right)$ equality constraint matrix. It is thus better to
exploit the particular bipartite structure of the problem. In particular, two
families of algorithms have emerged: _Dual Ascent Methods_ and _Auction
Algorithms_ [peyre2019computational]. The Hungarian algorithm is a particular
case of the former and classically runs with an
$\mathcal{O}\left(N_{p}^{4}\right)$ complexity
[munkres1957algorithmstransportationhungarian], further reduced to cubic by
[hungarian-cubic]. Although multiple GPU implementations of a BM solver have
been proposed [gpu-bipartite, gpu-hungarian, gpu-matching], the problem
remains poorly parallelizable because of its sequential nature. To allow for
efficient parallelization, we must consider a slightly amended problem.

###  2.2 Regularization

We show here how we can replace the _Hungarian algorithm_ by a class of
algorithms well-suited for parallelization, obtained by adding an entropy
regularization.

######  Definition 3 (OT with regularization).

We consider a regularization parameter $\epsilon\in\mathbb{R}_{\geq 0}$.
Extending Definition 1 (OT), we define the _Optimal Transport with
regularization_ as the following minimization problem:

$\hat{\bm{P}}=\underset{\bm{P}\,\in\,\mathcal{U}(\bm{\alpha},\bm{\beta})}{\mathrm{arg\,min}}\left\\{\sum_{i,j=1}^{N_{p},N_{g}}P_{i,j}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)-\epsilon\,\mathrm{H}(\bm{P})\right\\},$
(5)

with $\mathrm{H}:\Delta^{N\times M}\rightarrow\mathbb{R}_{\geq
0}:\bm{P}\mapsto-\sum_{i,j}P_{i,j}(\log(P_{i,j})-1)$ the entropy of the match
$\bm{P}$, with $0\ln(0)=0$ by definition.

Regularized OT
---

Matching cost
---

Matches $\bm{P}$
---
Bipartite
---
Matching
$\bm{P}\mathcal{L}_{\text{match}}$
---
$-\,\epsilon\,\mathrm{H}(\bm{P})$
$\bm{P}\mathcal{L}_{\text{match}}$
---
Machine
---
precision
Figure 3: Effect of the regularization on the minimization of the matching
cost. The red line corresponds to the regularized problem ($\epsilon\neq 0$)
and the blue to the unregularized one ($\epsilon=0$).

Sinkhorn’s Algorithm The entropic regularization used when finding the match
$\hat{\bm{P}}$ ensures that the problem is smooth for $\epsilon\neq 0$ (see
Figure 3). The advantage is that it can now be solved very efficiently using
_scaling algorithms_ and in this particular case the algorithm of _Sinkhorn_.
It is particularly suited for parallelization [cuturi2013sinkhorn], with some
later speed refinements [greenkorn, screenkorn]. Reducing the regularization
progressively renders the scaling algorithms numerically unstable, although
some approaches have been proposed to reduce the regularization further by
working in log-space [schmitzer2019stabilized, chizat2018scaling]. In the
limit of $\epsilon\rightarrow 0$, we recover the exact OT (Definition 1) and
the scaling algorithms cannot be used anymore. Parallelization is lost and we
must resolve to use the sequential algorithms developed in Section 1. In
brief, regularization allows to exploit GPU architectures efficiently, whereas
the Hungarian algorithm and similar cannot.

Smoother Matches When no regularization is used as in the Hungarian algorithm,
close predictions and ground truth objects can exchange their matches from one
epoch to the other, during the training. This causes a slow convergence of
DETR in the early stages of the training [li2022dndetr]. The advantage of the
regularization not only lies in the existence of efficient algorithms but also
allows for a reduction of sparsity. This results in a less drastic match than
the Hungarian algorithm obtains. A single ground truth could be matched to
multiple predictions and inversely. The proportion of these multiple matches
is controlled by the regularization parameter $\epsilon$. An illustration can
be found in Figures 2(a) and 2(b).

###  2.3 Unbalanced Optimal Transport

We will now show how considering soft constraints instead of hard leads to an
even greater generalization of the various matching techniques used in object
detection models. In particular, matching each prediction to the closest
ground truth is a limit case of the _Unbalanced OT_.

######  Definition 4 (Unbalanced OT).

We consider two constraint parameters $\tau_{1},\tau_{2}\in\mathbb{R}_{\geq
0}$. Extending Definition 3 (OT with regularization), we define the
_Unbalanced OT with regularization_ [chizat2018scaling] as the following
minimization problem:

$\displaystyle\hat{\bm{P}}=\underset{\bm{P}\in\mathbb{R}_{\geq 0}^{N_{p}\times
N_{g}}}{\mathrm{arg\,min}}\biggl{\\{}\epsilon\,\mathrm{KL}(\bm{P}\,\|\,\bm{K}_{\epsilon})\,+$
$\displaystyle\,\tau_{1}\mathrm{KL}(\bm{P}\bm{1}_{N_{g}}\,\|\,\bm{\alpha})$
(6) $\displaystyle+$
$\displaystyle\,\tau_{2}\mathrm{KL}(\bm{1}_{N_{p}}^{\top}\bm{P}\,\|\,\bm{\beta})\biggr{\\}},$

where $\mathrm{KL}:\mathbb{R}^{N\times M}_{\geq 0}\times\mathbb{R}^{N\times
M}_{>0}\rightarrow\mathbb{R}_{\geq
0}^{\phantom{N}}:(\bm{U},\bm{V})\mapsto\sum_{i,j=1}^{N\times
M}U_{i,j}\log(U_{i,j}/V_{i,j})-U_{i,j}+V_{i,j}$ is the _Kullback-Leibler
divergence_ – also called _relative entropy_ – between matrices or vectors
when $M=1$, with $0\ln(0)=0$ by definition. The Gibbs kernel
$\bm{K}_{\epsilon}$ is given by
$\left(K_{\epsilon}\right)_{i,j}=\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)/\epsilon\right)$.

We can see by development that the first term corresponds to the matching term
$\bm{P}\mathcal{L}_{\text{match}}$ and an extension of the entropic
regularization term $\mathrm{H}(\bm{P})$. The two additional terms replace the
transport polytope’s hard constraints $\mathcal{U}(\bm{\alpha},\bm{\beta})$
that required an exact equality of mass for both marginals. These new soft
constraints allow for a more subtle sensitivity to the mass constraints as it
allows to slightly diverge from them. It is clear that in the limit of
$\tau_{1},\tau_{2}\rightarrow+\infty$, we recover the “balanced” problem
(Definition 3). This definition naturally also defines Unbalanced OT without
regularization if $\epsilon=0$. The matching term would remain and the
entropic one disappear.

Matching to the Closest Another limit case is however particularly interesting
in the quest for a unifying framework of the matching strategies. If the mass
constraint is to be perfectly respected for the predictions
($\tau_{1}\rightarrow\infty$), but not at all for the ground truth objects
($\tau_{2}=0$), it suffices to assign the closest ground truth to each
prediction. The same ground truth object could be assigned to multiple
predictions and another could not be matched at all, not respecting the hard
constraint for the ground truth $\bm{\beta}$. Each prediction however is
exactly assigned once, perfectly respecting the mass constraint for the
predictions $\bm{\alpha}$. By assigning a low enough value to the background,
a prediction would be assigned to it provided all the other ground truth
objects are further. In other words, the background cost would play the role
of a _threshold_ value.

######  Proposition 2 (Matching to the closest).

We consider the same objects as Proposition 1. In the limit of
$\tau_{1}\rightarrow\infty$ and $\tau_{2}=0$, Unbalanced OT (Definition 4)
without regularization ($\epsilon=0$) admits as solution each prediction being
matched to the closest ground truth object unless that distance is greater
than a threshold value
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{N_{g}+1}=\varnothing\right)=c_{\varnothing}$.
It is then matched to the background $\varnothing$. In particular, we have

$\hat{P}_{i,j}=\left\\{\begin{array}[]{ll}\frac{1}{N_{p}}&\text{if
}j=\mathrm{\arg\,min}_{j\in\llbracket
N_{g}+1\rrbracket}\left\\{\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right\\},\\\
0&\text{otherwise}.\end{array}\right.$ (7)

###### Proof.

We refer to Appendix B.2. ∎

$\tau_{1}$
---
$\infty$
---
$0$
---
$\infty$
---
$\tau_{2}$
---
(degenerate)
---
Ground truth object
---
to best prediction
Prediction to best
---
ground truth object
Bipartite
---
Matching
Figure 4: Limit cases of Unbalanced OT without regularization ($\epsilon=0$).

The converse also holds. If the ground truth objects mass constraints were to
be perfectly respected ($\tau_{2}\rightarrow\infty$), but not the predictions
($\tau_{1}\rightarrow 0$), each ground truth would then be matched to the
closest prediction. The background would be matched to the remaining
predictions. Some predictions could not be matched and other ones multiple
times. The limits of Unbalanced OT are illustrated in Fig. 4. By setting the
threshold sufficiently high, we get an exact minimum, i.e., where every
prediction is matched to the closest ground truth. This can be observed in
Figure 2(d).

Scaling Algorithm Similarly as before, adding entropic regularization
($\epsilon\neq 0$) to the _Unbalanced OT_ allows it to be solved efficiently
on GPU with a scaling algorithm, as an extension of Sinkhorn’s algorithm
[chizat2018scaling, chizat-these]. The regularization still also allows for
smoother matches, as shown in Figure 2(c).

Softmax In the limit of $\tau_{1}\rightarrow+\infty$ and $\tau_{2}=0$, the
solution corresponds to a softmax over the ground truth objects for each
prediction. The regularization $\varepsilon$ controls then the “softness” of
the softmax, with $\varepsilon=1$ corresponding to the conventional softmax
and $\varepsilon\rightarrow 0$ the matching to the closest. We refer to
Appendix C.2 for more information.

##  3 Matching

Following previous work [carion2020detr, zhu2020deformabledetr,
ren2015fasterrcnn, redmon2016yolo, liu2016ssd], we define a multi-task
matching cost between a prediction $\hat{\bm{y}}_{i}$ and a ground truth
object $\bm{y}_{j}$ as the composition of a classification loss ensuring that
similar object classes are matched together and a localization loss ensuring
the correspondence of the positions and shapes of the matched boxes
$\mathcal{L}(\hat{\bm{y}}_{i},\bm{y}_{j})=\mathcal{L}_{\text{classification}}(\hat{\bm{c}}_{i},\bm{c}_{j})+\mathcal{L}_{\text{localization}}(\hat{\bm{b}}_{i},\bm{b}_{j})$.
Most models, however, do not use the same loss to determine the matches as the
one used to train the model. We therefore refer to these two losses as
$\mathcal{L}_{\text{match}}$ and $\mathcal{L}_{\text{train}}$. The training
procedure is the following: first find a match $\hat{\bm{P}}$ given a matching
strategy and matching cost $\mathcal{L}_{\text{match}}$, then compute the loss
$N_{p}\sum_{i=1}^{N_{p}}\sum_{j=1}^{N_{g}}\hat{P}_{ij}\mathcal{L}_{\text{train}}(\hat{\bm{y}}_{i},\bm{y}_{j})$
where the particular training loss for the background ground truth includes
only a classification term
$\mathcal{L}_{\text{train}}(\hat{\bm{y}}_{i},\varnothing)=\mathcal{L}_{\text{classification}}(\hat{\bm{c}}_{i},\varnothing)$.

###  3.1 Detection Transformer (DETR)

The object detection is performed by matching the predictions to the ground
truth boxes with the _Hungarian algorithm_ applied to the loss
$\mathcal{L}_{\text{match}}(\hat{\bm{y}}_{i},\bm{y}_{j})=\lambda_{\text{prob}}(1-\left<\hat{\bm{c}}_{i},\bm{c}_{j}\right>)+\lambda_{\ell^{1}}\lVert\hat{\bm{b}}_{i}-\bm{b}_{j}\rVert_{1}+\lambda_{\mathrm{GIoU}}(1-\mathrm{GIoU}(\hat{\bm{b}}_{i},\bm{b}_{j}))$
(Definition 2). To do so, the number of predictions and ground truth boxes
must be of the same size. This is achieved by padding the ground truths with
$(N_{p}-N_{g})$ dummy _background_ $\varnothing$ objects. Essentially, this is
the same as what is developed in Proposition 1. The obtained match is then
used to define an object-specific loss, where each matched prediction is
pushed toward its corresponding ground truth object. The predictions that are
not matched to a ground truth object are considered to be matched with the
background and are pushed to predict the background class. The training loss
uses the cross-entropy ($\mathrm{CE}$) for classification:
$\mathcal{L}_{\text{train}}(\hat{\bm{y}}_{i},\bm{y}_{j})=\lambda_{\mathrm{CE}}\mathcal{L}_{\mathrm{CE}}(\hat{\bm{c}}_{i},\bm{c}_{j})+\lambda_{\ell^{1}}\lVert\hat{\bm{b}}_{i}-\bm{b}_{j}\rVert_{1}+\lambda_{\mathrm{GIoU}}(1-\mathrm{GIoU}(\hat{\bm{b}}_{i},\bm{b}_{j}))$.
By directly applying Proposition 1 and adding entropic regularization
(Definition 3), we can use _Sinkhorn’s algorithm_ and push each prediction
$\hat{\bm{y}}_{i}$ to ground truth $\bm{y}_{j}$ according to weight
$\hat{P}_{i,j}$. In particular, for any non-zero $\hat{P}_{i,N_{g}+1}\neq 0$,
the prediction $\hat{\bm{y}}_{i}$ is pushed toward the background
$\bm{y}_{N_{g}+1}=\varnothing$ with weight $\hat{P}_{i,N_{g}+1}$.

###  3.2 Single Shot MultiBox Detector (SSD)

The Single Shot MultiBox Detector [liu2016ssd] uses a matching cost only
comprised of the $\mathrm{IoU}$ between the fixed anchor boxes
$\tilde{\bm{b}}_{i}$ and the ground truth boxes:
$\mathcal{L}_{\text{match}}(\hat{\bm{y}}_{i},\bm{y}_{j})=1-\mathrm{IoU}(\tilde{\bm{b}}_{i},\bm{b}_{j})$
(the $\mathrm{GIoU}$ was not published yet [giou]). Each ground truth is first
matched toward the closest anchor box. Anchor boxes are then matched to a
ground truth object if the matching cost is below a threshold of 0.5. In our
framework, this corresponds to applying $\tau_{1}=0$ and $\tau_{2}\to\infty$
for the first phase and then $\tau_{1}\to\infty$ and $\tau_{2}=0$ with
$c_{\varnothing}=0.5$ (see Proposition 2). Here again, by adding entropic
regularization (Definition 4), we can solve this using a _scaling algorithm_.
We furthermore can play with the parameters $\tau_{1}$ and $\tau_{2}$ to make
the matching tend slightly more towards a matching done with the _Hungarian
algorithm_ (Figure 2). Again, the training uses a different loss than the
matching, in particular
$\mathcal{L}_{\text{train}}(\hat{\bm{y}}_{i},\bm{y}_{j})=\lambda_{\mathrm{CE}}\mathcal{L}_{\mathrm{CE}}(\hat{\bm{c}}_{i},\bm{c}_{j})+\lambda_{\text{smooth
}\ell^{1}}\mathcal{L}_{\text{smooth }\ell^{1}}(\hat{\bm{b}}_{i},\bm{b}_{j})$.

Hard Negative Mining Instead of using all negative examples
$N_{\text{neg}}=(N_{p}-N_{g})$ (predictions matched to background), the method
sorts them using the highest confidence loss
$\mathcal{L}_{\mathrm{CE}}(\hat{\bm{c}}_{i},\varnothing)$ and picks the top
ones so that the ratio between the hard negatives and positives
$N_{\text{pos}}=N_{g}$ is at most 3 to 1. Since $\hat{\bm{P}}$ is non-binary,
we define the number of negatives and positives to be the sum of the matches
to the background
$N_{\text{neg}}=N_{p}\sum_{i=1}^{N_{p}}\hat{P}_{i,(N_{g}+1)}$ and to the
ground truth objects
$N_{\text{pos}}=N_{p}\sum_{j=1}^{N_{g}}\sum_{i=1}^{N_{p}}\hat{P}_{ij}$. We
verify that for any $\bm{P}\in\mathcal{U}(\bm{\alpha},\bm{\beta})$, we have
the same number of positives and negatives as the initial model:
$N_{\text{neg}}=(N_{p}-N_{g})$ and $N_{\text{pos}}=N_{g}$. Hence, hard
negatives are the $K$ predictions with the highest confidence loss
$\hat{P}_{k,(N_{g}+1)}\mathcal{L}_{\mathrm{CE}}(\hat{\bm{c}}_{k},\varnothing)$
such that the mass of kept negatives is at most triple the number of
positives: $N_{p}\sum_{k=1}^{K}\hat{P}_{k,(N_{g}+1)}^{s}\leq 3N_{\text{pos}}$,
where $\hat{\bm{P}}^{s}$ is a permutation of transport matrix $\hat{\bm{P}}$
with rows sorted by highest confidence loss.

##  4 Experimental Results & Discussion

We show that matching based on Unbalanced Optimal Transport generalizes many
different matching strategies and performs on par with methods that use either
Bipartite Matching or anchor boxes along with matching each prediction to the
closest ground truth box with a threshold. We then analyze the influence of
constraint parameter $\tau_{2}$ by training SSD with and without NMS for
multiple parameter values. Finally, we show that OT with entropic
regularization both improves the convergence and is faster to compute than the
Hungarian algorithm in case of many matches.

0
---
50
---
100
---
150
---
200
---
250
---
300
---
Epoch
---
0
---
10
---
20
---
30
---
40
---
50
---

AP
---

Hungarian
---
OT
---
Hungarian with finetuning
---
at epoch 200
Hungarian with finetuning
---
at epoch 100
OT with finetuning
---
at epoch 100
Figure 5: Convergence curves for DETR on the Color Boxes dataset. The model
converges faster with a regularized matching.

###  4.1 Setup

Datasets We perform experiments on a synthetic object detection dataset with
4.800 training and 960 validation images and on the large-scale COCO
[lin2014microsoft] dataset with 118,287 training and 5,000 validation test
images. We report on mean Average Precision (AP) and mean Average Recall (AR).
The two metrics are an average of the per-class metrics following COCO’s
official evaluation procedure. For the Color Boxes synthetic dataset, we
uniformly randomly draw between 0 and 30 rectangles of 20 different colors
from each image. Appendix I provides the detailed generation procedure and
sample images.

Training For a fair comparison, the classification and localization costs for
matching and training are identical to the ones used by the models. Unless
stated otherwise, we train the models with their default hyper-parameter sets.
DETR and Deformable DETR are trained with hyper-parameters
$\lambda_{\text{prob}}=\lambda_{\mathrm{CE}}=2$, $\lambda_{\ell^{1}}=5$ and
$\lambda_{\mathrm{GIoU}}=2$. For Deformable DETR, we found the classification
cost to be overwhelmed by the localization costs in the regularized
minimization problem (Definition 3). We therefore set
$\lambda_{\text{prob}}=5$. We, however keep $\lambda_{\mathrm{CE}}=2$ so that
the final loss value for a given matching remains unchanged. SSD is trained
with original hyper-parameters $\lambda_{\mathrm{CE}}=\lambda_{\text{smooth
}\ell^{1}}=1$. For OT, we set the entropic regularization to
$\epsilon=\epsilon_{0}/(\log{(2N_{p})}+1)$ where $\epsilon_{0}=0.12$ for all
models (App. D). In the following experiments, the Unbalanced OT is solved
with multiple values of $\tau_{2}$ whereas $\tau_{1}$ is fixed to a large
value $\tau_{1}=100$ to simulate a hard constraint. In practice, we limit the
number of iterations of the scaling algorithm. This provides a good enough
approximation [ge2021yolox].

| Model | Matching | $\bm{\tau_{2}}$ | Epochs | AP | AR
---|---|---|---|---|---|---
Color Boxes | DETR | Hungarian |  ($\infty$) | 300 | 50.9 | 65.7
DETR | Hungarian |  ($\infty$) | 150 | 45.3 | 60.7
DETR | OT |  ($\infty$) | 150 | 50.3 | 65.7
D. DETR | Hungarian |  ($\infty$) | 50 | 64.0 | 75.9
D. DETR | OT |  ($\infty$) | 50 | 63.5 | 76.5
COCO | D. DETR | Hungarian |  ($\infty$) | 50 | 44.5 | 63.0
D. DETR | OT |  ($\infty$) | 50 | 44.2 | 62.0
SSD300 | Two Stage | —- | 120 | 24.9 | 36.8
SSD300 | Unb. OT | $0.01$ | 120 | 24.7 | 36.4
Table 1: Object detection metrics for different models and loss functions on
the Color Boxes and COCO datasets.

###  4.2 Unified Matching Strategy

DETR and Deformable DETR Convergence curves for DETR on the Color Boxes
dataset are shown in Fig. 5 and associated metrics are presented in Table 1.
DETR converges in half the number of epochs with the regularized balanced OT
formulation. This confirms that one reason for slow DETR convergence is the
discrete nature of BM, which is unstable, especially in the early stages of
training. Training the model for more epochs with either BM or OT does not
improve metrics as the model starts to overfit. Appendix E provides
qualitative examples and a more detailed convergence analysis. We evaluate how
these results translate to faster converging DETR-like models by additionally
training Deformable DETR [zhu2020deformabledetr]. In addition to model
improvements, Deformable DETR makes three times more predictions than DETR and
uses a sigmoid focal loss [lin2017focalloss] instead of a softmax cross-
entropy loss for both classification costs. Table 1 gives results on Color
Boxes and COCO. We observe that the entropy term does not lead to faster
convergence. Indeed, Deformable DETR converges in $50$ epochs with both
matching strategies. Nevertheless, both OT and bipartite matching lead to
similar AP and AR.

Matching | $\bm{\tau_{2}}$ | with NMS | w/o NMS
---|---|---|---
AP | AR | AP | AR
Two Stage | —- | 51.6 | 67.0 | 23.2 | 77.8
Unb. OT | 0.01 | 51.1 | 66.3 | 25.3 | 76.5
Unb. OT | 0.1 | 50.9 | 66.8 | 35.9 | 75.4
Unb. OT | 1 | 48.3 | 64.4 | 44.3 | 73.4
Unb. OT | 10 | 48.0 | 64.1 | 44.9 | 72.9
OT |  ($\infty$) | 48.1 | 64.3 | 45.2 | 73.0
Table 2: Comparison of matching strategies on the Color Boxes dataset. SSD300
is evaluated both with and without NMS.

SSD and the Constraint Parameter To better understand how unbalanced OT
bridges the gap between DETR’s and SSD’s matching strategies, we analyze the
variation in performance of SSD for different values of $\tau_{2}$. Results
for an initial learning rate of 0.0005 are displayed in Table 2. In the second
row, the parameter value is close to zero. From Proposition 2 and when
$\epsilon\to 0$, each prediction is matched to the closest ground truth box
unless the matching cost exceeds 0.5. Thus, multiple predictions are matched
to each ground truth box, and NMS is needed to eliminate near duplicates. When
NMS is removed, AP drops by 25.8 points and AR increases by 10.2 points. We
observe similar results for the original SSD matching strategy (1st row),
which suggests matching each ground truth box to the closest anchor box does
not play a huge role in the two-stage matching procedure from SSD. The lower
part of Table 1 shows the same for COCO. When $\tau_{2}\to+\infty$, one
recovers the balanced formulation used in DETR (last row). Removing NMS leads
to a 2.9 points drop for AP and a 9.7 points increase for AR. Depending on the
field of application, it may be preferable to apply a matching strategy with a
low $\tau_{2}$ and with NMS when precision is more important or without NMS
when the recall is more important. Moreover, varying parameter $\tau_{2}$
offers more control on the matching strategy and therefore on the precision-
recall trade-off [buckland1994precisionrecall].

100
---
300
---
1000
---
8732
---
Number of predictions
---
10-3
---
10-2
---

Time [s]
---

Scaling alg. for OT (Sinkhorn)
---
Scaling alg. for Unb. OT
---
Hungarian alg.
---
DETR
---
Def. DETR
---
SSD
---
Model
---
Figure 6: Average and standard deviation of the computation time for different
matching strategies on COCO with batch size $16$. The Hungarian algorithm is
computed with SciPy and its time includes the transfer of the cost matrix from
GPU memory to RAM. We run $20$ Sinkhorn iterations. Computed with an Nvidia
TITAN X GPU and Intel Core i7-4770K CPU @ 3.50GHz.

Computation Time For a relatively small number of predictions, implementations
of Sinkhorn perform on par with the Hungarian algorithm (Fig. 6). The
“balanced” algorithm is on average 2.6ms slower than the Hungarian algorithm
for $100$ predictions (DETR) and 1.5ms faster for 300 predictions (Deformable
DETR). For more predictions, GPU parallelization of the Sinkhorn algorithm
makes a large difference (more than 50x speedup). As a reference point, SSD300
and SSD512 make $8,732$ and $24,564$ predictions.

##  5 Conclusion and Future Work

Throughout the paper, we showed both theoretically and experimentally how
_Unbalanced Optimal Transport_ unifies the _Hungarian algorithm_ , matching
each ground truth object to the best prediction and each prediction to the
best ground truth, with or without threshold.

Experimentally, using OT and Unbalanced OT with entropic regularization is on
par with the state-of-the-art for DETR, Deformable DETR and SSD. Moreover, we
showed that entropic regularization lets DETR converge faster on the Color
Boxes dataset and that parameter $\tau_{2}$ offers better control of the
precision-recall trade-off. Finally, we showed that the _scaling algorithms_
compute large numbers of matches faster than the Hungarian algorithm.

Limitations and Future Work The convergence improvement of the regularized OT
formulation compared to bipartite matching seems to hold only for DETR and on
small-scale datasets. Further investigations may include Wasserstein-based
matching costs for a further unification of the theory and the reduction of
the entropy with time, as it seems to boost convergence only in early phases,
but not in fine-tuning.

## Acknowledgements

EU: The research leading to these results has received funding from the
European Research Council under the European Union’s Horizon 2020 research and
innovation program / ERC Advanced Grant E-DUALITY (787960). This paper
reflects only the authors’ views and the Union is not liable for any use that
may be made of the contained information. Research Council KUL: Optimization
frameworks for deep kernel machines C14/18/068. Flemish Government: FWO:
projects: GOA4917N (Deep Restricted Kernel Machines: Methods and Foundations),
PhD/Postdoc grant; This research received funding from the Flemish Government
(AI Research Program). All the authors are also affiliated to Leuven.AI - KU
Leuven institute for AI, B-3000, Leuven, Belgium.

## References

  * [1] Mokhtar Z Alaya, Maxime Berar, Gilles Gasso, and Alain Rakotomamonjy.  Screening sinkhorn algorithm for regularized optimal transport.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [2] Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet.  Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [3] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International conference on machine learning, pages 214–223. PMLR, 2017.
  * [4] Richard A. Brualdi.  Combinatorial Matrix Classes.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2006.
  * [5] Michael Buckland and Fredric Gey.  The relationship between recall and precision.  Journal of the American society for information science, 45(1):12–19, 1994.
  * [6] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6154–6162, 2018.
  * [7] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European conference on computer vision, pages 213–229. Springer, 2020.
  * [8] Lenaic Chizat.  Unbalanced Optimal Transport : Models, Numerical Methods, Applications.  Theses, Université Paris sciences et lettres, Nov. 2017.
  * [9] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Scaling algorithms for unbalanced optimal transport problems.  Mathematics of Computation, 87(314):2563–2609, 2018.
  * [10] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard.  Unbalanced optimal transport: Dynamic and kantorovich formulations.  Journal of Functional Analysis, 274(11):3090–3123, 2018.
  * [11] Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré.  Faster wasserstein distance estimation with the sinkhorn divergence.  In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.
  * [12] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [13] Jifeng Dai, Yi Li, Kaiming He, and Jian Sun.  R-fcn: Object detection via region-based fully convolutional networks.  Advances in neural information processing systems, 29, 2016.
  * [14] Ketan Date and Rakesh Nagi.  Gpu-accelerated hungarian algorithms for the linear assignment problem.  Parallel Computing, 57:52–72, 2016.
  * [15] Henri De Plaen, Michaël Fanuel, and Johan AK Suykens.  Wasserstein exponential kernels.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–6. IEEE, 2020.
  * [16] Jack Edmonds and Richard M. Karp.  Theoretical improvements in algorithmic efficiency for network flow problems.  J. ACM, 19(2):248–264, apr 1972.
  * [17] Bas O Fagginger Auer and Rob H Bisseling.  A gpu algorithm for greedy graph matching.  In Facing the Multicore-Challenge II, pages 108–119. Springer, 2012\.
  * [18] Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty.  Unbalanced minibatch optimal transport; applications to domain adaptation.  In International Conference on Machine Learning, pages 3186–3197. PMLR, 2021.
  * [19] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio.  Learning with a wasserstein loss.  Advances in neural information processing systems, 28, 2015.
  * [20] Zheng Ge, Songtao Liu, Zeming Li, Osamu Yoshie, and Jian Sun.  Ota: Optimal transport assignment for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 303–312, 2021.
  * [21] Zheng Ge, Songtao Liu, Feng Wang, Zeming Li, and Jian Sun.  Yolox: Exceeding yolo series in 2021.  arXiv preprint arXiv:2107.08430, 2021.
  * [22] Aude Genevay.  Entropy-Regularized Optimal Transport for Machine Learning.  Theses, PSL University, Mar. 2019.
  * [23] Aude Genevay, Gabriel Peyre, and Marco Cuturi.  Learning generative models with sinkhorn divergences.  In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1608–1617. PMLR, 09–11 Apr 2018.
  * [24] Ross Girshick.  Fast r-cnn.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 1440–1448, December 2015.
  * [25] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580–587, 2014.
  * [26] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of wasserstein gans.  Advances in neural information processing systems, 30, 2017.
  * [27] Yuzhuo Han, Xiaofeng Liu, Zhenfei Sheng, Yutao Ren, Xu Han, Jane You, Risheng Liu, and Zhongxuan Luo.  Wasserstein loss-based deep object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2020.
  * [28] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Spatial pyramid pooling in deep convolutional networks for visual recognition.  IEEE transactions on pattern analysis and machine intelligence, 37(9):1904–1916, 2015.
  * [30] L. Kantorovitch.  On the translocation of masses.  Management Science, 5(1):1–4, 1958.
  * [31] Soheil Kolouri, Phillip E Pope, Charles E Martin, and Gustavo K Rohde.  Sliced wasserstein auto-encoders.  In International Conference on Learning Representations, 2018.
  * [32] Soheil Kolouri, Yang Zou, and Gustavo K Rohde.  Sliced wasserstein kernels for probability distributions.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5258–5267, 2016.
  * [33] Harold W Kuhn.  The hungarian method for the assignment problem.  Naval research logistics quarterly, 2(1-2):83–97, 1955.
  * [34] John Lee, Nicholas P. Bertrand, and Christopher J. Rozell.  Unbalanced optimal transport regularization for imaging problems.  IEEE Transactions on Computational Imaging, 6:1219–1232, 2020.
  * [35] Feng Li, Hao Zhang, Shilong Liu, Jian Guo, Lionel M Ni, and Lei Zhang.  Dn-detr: Accelerate detr training by introducing query denoising.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13619–13627, 2022.
  * [36] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [37] 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.
  * [38] 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.
  * [39] Li Liu, Wanli Ouyang, Xiaogang Wang, Paul Fieguth, Jie Chen, Xinwang Liu, and Matti Pietikäinen.  Deep learning for generic object detection: A survey.  International journal of computer vision, 128(2):261–318, 2020\.
  * [40] Shilong Liu, Feng Li, Hao Zhang, Xiao Yang, Xianbiao Qi, Hang Su, Jun Zhu, and Lei Zhang.  Dab-detr: Dynamic anchor boxes are better queries for detr.  In International Conference on Learning Representations, 2021.
  * [41] 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.
  * [42] Gaspard Monge.  Mémoire sur la théorie des déblais et des remblais.  Mem. Math. Phys. Acad. Royale Sci., pages 666–704, 1781.
  * [43] Grégoire Montavon, Klaus-Robert Müller, and Marco Cuturi.  Wasserstein training of restricted boltzmann machines.  Advances in Neural Information Processing Systems, 29, 2016.
  * [44] James Munkres.  Algorithms for the assignment and transportation problems.  Journal of the society for industrial and applied mathematics, 5(1):32–38, 1957.
  * [45] Mayu Otani, Riku Togashi, Yuta Nakashima, Esa Rahtu, Janne Heikkilä, and Shin’ichi Satoh.  Optimal correction cost for object detection evaluation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 21107–21115, 2022.
  * [46] Jiangmiao Pang, Kai Chen, Jianping Shi, Huajun Feng, Wanli Ouyang, and Dahua Lin.  Libra r-cnn: Towards balanced learning for object detection.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 821–830, 2019.
  * [47] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [48] 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.
  * [49] 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, volume 28. Curran Associates, Inc., 2015.
  * [50] H. Rezatofighi, N. Tsoi, J. Gwak, A. Sadeghian, I. Reid, and S. Savarese.  Generalized intersection over union: A metric and a loss for bounding box regression.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 658–666, Los Alamitos, CA, USA, jun 2019. IEEE Computer Society.
  * [51] Paul K Rubenstein, Bernhard Schoelkopf, and Ilya Tolstikhin.  On the latent space of wasserstein auto-encoders.  arXiv preprint arXiv:1802.03761, 2018.
  * [52] F. Santambrogio.  Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling.  Progress in Nonlinear Differential Equations and Their Applications. Springer International Publishing, 2015.
  * [53] Bernhard Schmitzer.  Stabilized sparse scaling algorithms for entropy regularized transport problems.  SIAM Journal on Scientific Computing, 41(3):A1443–A1481, 2019.
  * [54] Jiaming Sun, Zehong Shen, Yuang Wang, Hujun Bao, and Xiaowei Zhou.  Loftr: Detector-free local feature matching with transformers.  In CVPR, pages 8922–8931, 2021.
  * [55] Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf.  Wasserstein auto-encoders.  In International Conference on Learning Representations, 2018.
  * [56] Cristina Nader Vasconcelos and Bodo Rosenhahn.  Bipartite graph matching computation on gpu.  In International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pages 42–55. Springer, 2009.
  * [57] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * [58] Xuan-Thuy Vo and Kang-Hyun Jo.  A review on anchor assignment and sampling heuristics in deep learning-based object detection.  Neurocomputing, 2022.
  * [59] Xue Yang, Junchi Yan, Qi Ming, Wentao Wang, Xiaopeng Zhang, and Qi Tian.  Rethinking rotated object detection with gaussian wasserstein distance loss.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11830–11841. PMLR, 18–24 Jul 2021.
  * [60] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  In International Conference on Learning Representations, 2021.

Unbalanced Optimal Transport: A Unified Framework for Object Detection
Supplementary Material

##  Appendix A Optimal Transport Discussion

The _Otpimal Transport_ formulation presented throughout the paper is
formulated in discrete space. In this section, we present the more general
formulation of which the discrete one is a particular case of. We also discuss
the Wasserstein distance in the particular context of object detection and the
effect of regularization on the uniqueness of the solutions. Only the case of
the original OT formulation—or “balanced” case—is covered here.

###  A.1 Continuous Formulation

More generally, we define Optimal Transport in its continuous form.

######  Definition 5 (Continuous Optimal Transport).

Given two distributions $\alpha\in\mathscr{P}_{+}(X)$ and
$\beta\in\mathscr{P}_{+}(Y)$ of same mass
$\int\alpha\,\mathrm{d}x=\int\beta\,\mathrm{d}y$, and given an underlying cost
function $c:X\times Y\rightarrow[0,+\infty]$, we define _Continuous Optimal
Transport_ as the minimization of a transport cost

$\inf\left\\{\int_{X\times Y}c\,\mathrm{d}\gamma:\gamma\in
U(\alpha,\beta)\right\\},$ (8)

with admissible solutions, here called transport plans

$U(\alpha,\beta)=\bigg{\\{}\gamma\in\mathscr{P}_{+}(X\times
Y):\int_{Y}\mathrm{d}\gamma=\alpha\quad\text{and}\quad\int_{X}\mathrm{d}\gamma=\beta\bigg{\\}}.$
(9)

If a minimum exists, it is called the optimal transport plan $\hat{\gamma}$.

We replace the probability simplex $\Delta^{N}$ by the space on probability
distributions $\mathscr{P}_{+}(X)$ on $X$. The transport plans are the set of
joint probability distribution $\gamma\in\mathscr{P}_{+}(X\times Y)$, whose
marginal distributions are $\alpha$ and $\beta$. The discrete formulation
(Definition 1) is a particular case where
$\alpha=\sum_{i}\alpha_{i}\delta_{\hat{\bm{y}}_{i}}$,
$\beta=\sum_{j}\beta_{j}\delta_{\bm{y}_{j}}$ and the cost
$c=\mathcal{L}_{\text{match}}$. In this case, a minimum always exists.

###  A.2 Wasserstein Distance

This infimum defines a distance between $\alpha$ and $\beta$, called the
Wasserstein distance $\mathcal{W}_{p}(\alpha,\beta)$, provided that the
underlying cost function is also a distance $c=d^{p}$ up to some exponent
$p\in[1,+\infty[$. In our case, $\mathcal{L}_{\text{match}}$ is not a
distance. More formally, sum of distances are distances. The $\ell^{1}$ norm
is a distance, and $1-\mathrm{IoU}$, or $1-\mathrm{GIoU}$ also are [giou].
However, the cross entropy or the focal loss do not satisfy the triangular
inequality or the symmetry properties. In consequence, we cannot talk about a
Wasserstein distance here.

Furthermore, interpreting a Wasserstein distance
$\mathcal{W}_{p}(\alpha,\beta)$ would not make much sense even if the
underlying matching cost was to be a distance. Indeed, the distributions
$\alpha$ and $\beta$ would be the same at every iteration in our framework. In
other words, the distance would always be computed between the same points,
but the underlying cost would change and it would be different for each image.
Each iteration would be computing the distance of two same points in a
changing geometry and each image would have its own evolving geometry.

For completeness, we must mention that the regularized version does not define
a distance as
$\mathcal{W}_{p,\text{reg.}}(\bm{\alpha},\bm{\alpha})=-\epsilon\,\mathrm{H}(\bm{I}_{N_{p},N_{p}}/N_{p})>0$
with $\bm{I}_{N_{p},N_{p}}$ the identity matrix of size $N_{p}$ (we refer to
[genevay, genevay-these, sinkhorn-divergences] for a broader discussion on the
subject).

###  A.3 Uniqueness

We consider here the discrete formulation used throughout the paper. By
classical linear programming theory, the non-regularized problem admits a non-
unique solution if and only if multiple extreme points minimize the problem.
In that case, the set of minimizers is all the linear interpolations between
those extreme points. The regularization term however is $\epsilon$-strongly
convex; the regularized problem thus always has a unique solution
[peyre2019computational].

##  Appendix B Proofs of the Propositions

In this section, we provide the proofs of Propositions 1 and 2 and enrich them
with some insight through a few additional results.

###  B.1 Hungarian Algorithm

Before providing a proof of the particular equivalence between OT and BM, we
first consider a more general result.

######  Lemma 1.

We consider the rational probability simplex
$\Delta_{\mathbb{Q}}^{N}=\\{\bm{u}\in\mathbb{Q}^{N}_{\geq
0}|\sum_{i}u_{i}=1\\}$. Given an OT problem (Definition 1) with underlying
distributions $\bm{\alpha}\in\Delta^{N}_{\mathbb{Q}}$ and
$\bm{\beta}\in\Delta^{M}_{\mathbb{Q}}$. Each extreme point of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$ is comprised of elements, which are
multiples of the _common measure_ of $\bm{\alpha}$ and $\bm{\beta}$:

$\text{$\bm{P}$ is an extreme point of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$}\qquad\Longrightarrow\qquad\bm{P}\in\mathrm{CM}(\bm{\alpha},\bm{\beta})\cdot\mathbb{N}_{\geq
0}^{N\times M},$ (10)

where the _common measure_ is the greatest rational such that all non-zero
elements of both distributions are multiples of it:

$\mathrm{CM}(\bm{\alpha},\bm{\beta})=\frac{\mathrm{GCD}\left(\mathrm{LCM}\left(\left[\,\bm{\alpha},\,\bm{\beta}\,\right]\right)/\left[\,\bm{\alpha},\,\bm{\beta}\,\right]\right)}{\mathrm{LCM}\left(\left[\,\bm{\alpha},\,\bm{\beta}\,\right]\right)}\in\mathbb{Q}_{>0},$
(11)

with $\mathrm{GCD}:\mathbb{N}_{>0}^{N}\rightarrow\mathbb{N}_{>0}$ the greatest
common divisor and
$\mathrm{LCM}:\mathbb{N}_{>0}^{N}\rightarrow\mathbb{N}_{>0}$ the lowest common
multiple.

The _common measure_ extends the $\mathrm{GCD}$ to non-integers. As an example
$\mathrm{CM}(\left[\,\nicefrac{{2}}{{3}},\,\nicefrac{{4}}{{5}}\,\right])=\nicefrac{{2}}{{15}}$
and
$\mathrm{CM}(\left[\,\nicefrac{{2}}{{3}},\,\nicefrac{{5}}{{6}},\,\nicefrac{{4}}{{7}}\,\right])=\nicefrac{{1}}{{42}}$.

###### Proof.

In [brualdi_2006], Corollary 8.1.3, an algorithm is given to build the
exhaustive list of extreme points. It comprises only minimum and subtraction
operations, which leave the common measure unchanged. ∎

######  Corollary 1.

Given the underlying distributions as in Proposition 1, the extreme points of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$ are comprised only of zeros and
$1/N_{p}$:

$\text{$\bm{P}$ is an extreme point of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$}\qquad\Longrightarrow\qquad\bm{P}\in\left\\{0,1/N_{p}\right\\}^{N_{p}\times\left(N_{g}+1\right)}.$
(12)

This is a direct consequence of Lemma 1 and the mass constraints directly
implying that $P_{i}\leq 1/N_{p}$ for all $i$. In this particular case, there
is also an equivalence.

######  Lemma 2.

Given the underlying distributions as in Proposition 1, the extreme points of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$ are comprised only of zeros and
$1/N_{p}$:

$\text{$\bm{P}$ is an extreme point of
$\,\mathcal{U}(\bm{\alpha},\bm{\beta})$}\qquad\Longleftrightarrow\qquad\bm{P}\in\left\\{0,1/N_{p}\right\\}^{N_{p}\times\left(N_{g}+1\right)}\quad\text{and}\quad\bm{P}\in\,\mathcal{U}(\bm{\alpha},\bm{\beta}).$
(13)

###### Proof.

We consider Corollary 1 and add the fact that such a match
$\bm{P}\in\left\\{0,1/N_{p}\right\\}^{N_{p}\times\left(N_{g}+1\right)}$ only
has one element per row (or prediction if we prefer) to satisfy the mass
constraints. Therefore, it cannot be any interpolation of two other extreme
points. ∎

We however also give a more direct proof, based essentially on the same
arguments.

###### Proof.

We will first show that the elements of the match $\bm{P}$ corresponding to
any extreme point, can only be $1/N_{p}$ or $0$. Therefore we can consider the
associated bipartite graph of the problem: each prediction consists in a node
$i$ and each ground truth a node $j$. Each non-zero value entry of $\bm{P}$
connects nodes $i$ and $j$ with weight $P_{i,j}$. The solution is admissible
if and only if the weight of each node $i$ equals $\alpha_{i}$ and $j$ equals
$\beta_{j}$. A transport plan $\bm{P}$ is an extreme point if and only if the
corresponding bipartite graph only consists in trees, or equivalently, it has
no cycle (Theorem 8.1.2 of [brualdi_2006]).

Because the mass constraint must all sum up to one for the predictions, we
already know that $P_{i,j}\leq 1/N_{p}$. We will now proceed _ad absurdum_ and
suppose that there were to be an entry $0<P_{i,j}<1/N_{p}$ connecting a
prediction and a ground truth. In order to satisfy the mass constraints, they
would both also have to be connected to another prediction and another ground
truth. Similarly, these would also have to be connected to at least one
prediction and one ground truth, and so on. They would all form a same graph,
or be “linked” together in other words. By consequence, each new connection
must be done to yet “unlinked” prediction and ground truth to avoid the
formation of a cycle. Considering that there are $N_{p}$ predictions, there
would be at the end at least $2N_{p}$ edges within the graph. This is
incompatible with the fact that there cannot be any cycle (Corollary 8.1.3 of
[brualdi_2006]). By consequence, the entries of $\bm{P}$ must be either $0$ or
$1/N_{p}$. ∎

We can now proceed to prove the said proposition.

######  Proposition 1.

The Hungarian algorithm with $N_{p}$ predictions and $N_{g}\leq N_{p}$ ground
truth objects is a particular case of OT with
$\bm{P}\in\mathcal{U}(\bm{\alpha},\bm{\beta})\subset\mathbb{R}^{N_{p}\times(N_{g}+1)}$,
consisting of the predictions and the ground truth objects, with the
background added
$\left\\{\bm{y}_{j}\right\\}_{j=1}^{N_{g}+1}=\left\\{\bm{y}_{j}\right\\}_{j=1}^{N_{g}}\cup\left(\bm{y}_{N_{g}+1}=\varnothing\right)$.
The chosen underlying distributions are

$\displaystyle\bm{\alpha}$ $\displaystyle=$
$\displaystyle\frac{1}{N_{p}}[\;\underbrace{1,\;1,\;1,\;\ldots,\;1}_{\text{$N_{p}$
predictions}}\;],$ (14) $\displaystyle\bm{\beta}$ $\displaystyle=$
$\displaystyle\frac{1}{N_{p}}[\;\underbrace{1,\;1,\;\ldots,\;1}_{\text{$N_{g}$
ground truth objects}},\;\underbrace{(N_{p}-N_{g})}_{\text{background
}\varnothing}\;],$ (15)

provided the background cost is constant:
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\varnothing\right)=c_{\varnothing}$.
In particular for $j\in\llbracket N_{g}\rrbracket$, we have
$\hat{\sigma}(j)=\left\\{i:P_{i,j}\neq 0\right\\}$, or equivalently
$\hat{\sigma}(j)=\left\\{i:P_{i,j}=1/N_{p}\right\\}$.

###### Proof.

We will demonstrate that OT with
$\bm{\alpha}=\frac{1}{N_{p}}[\;1,\;1,\;1,\;\ldots,\;1\;]$ and
$\bm{\beta}=\frac{1}{N_{p}}[\;1,\;1,\;\ldots,\;1,\;(N_{p}-N_{g})\;]$ and
constant background cost necessarily has the BM as minimal solution. We first
observe that because of the linear nature of the problem, there is at least
one extreme point that minimizes the total cost. By directly applying Lemma 2,
there must be exactly one match per prediction and exactly one match for each
non-background ground truth to satisfy the mass constraints. The added
background ground truth has $N_{p}-N_{g}$ matches. This is equivalent to
saying that disregarding the background ground truth, we wave
$\sigma\in\mathcal{P}_{N_{g}}(\llbracket N_{p}\rrbracket)$ with
$\hat{\sigma}(j)=\left\\{i:P_{i,j}=1/N_{p}\right\\}$. The proof is concluded
by observing that the part of the background in the total transport cost is
equal to $\frac{1}{N_{p}}\left(N_{p}-N_{g}\right)c_{\varnothing}$ and is
constant, hence not influencing the minimum. ∎

###  B.2 Minimum Matching with Threshold

######  Proposition 2 (Matching to the closest).

We consider the same objects as Proposition 1. In the limit of
$\tau_{1}\rightarrow\infty$ and $\tau_{2}=0$, Unbalanced OT (Definition 4)
without regularization ($\epsilon=0$) admits as solution each prediction being
matched to the closest ground truth object unless that distance is greater
than a threshold value
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{N_{g}+1}=\varnothing\right)=c_{\varnothing}$.
It is then matched to the background $\varnothing$. In particular, we have

$\hat{P}_{i,j}=\left\\{\begin{array}[]{ll}\frac{1}{N_{p}}&\text{if
}j=\mathrm{\arg\,min}_{j\in\llbracket
N_{g}+1\rrbracket}\left\\{\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right\\},\\\
0&\text{otherwise}.\end{array}\right.$ (16)

###### Proof.

By taking the limit of $\tau_{1}\rightarrow+\infty$ and setting
$\epsilon,\tau_{2}=0$, the problem becomes

$\begin{array}[]{ll}\mathrm{arg\,min}&\left\\{\left.\sum_{i,j=1}^{N_{p},N_{g}+1}P_{i,j}\mathcal{L}_{\text{match}}\left(\bm{y}_{i},\hat{\bm{y}}_{j}\right)\right|\bm{P}\in\mathbb{R}_{\geq
0}^{N_{p}\times\left(N_{g}+1\right)}\right\\},\\\
\text{s.t.}&\sum_{j}P_{i,j}=1/N_{p}\qquad\forall i.\end{array}$ (17)

We can now see that the choice made in each row is independent from the other
rows. In other words, each ground truth object can be matched independently of
the others. The minimization is then obtained if, for each prediction (or
row), all the weight is put on the ground truth object with minimum cost,
including the background. This leads to Eq. 16. ∎

######  Corollary 2 (Matching to the closest without threshold).

Provided the background cost is more expensive than any other cost
$c_{\varnothing}>\max\left.\big{\\{}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right|i\in\llbracket
N_{p}\rrbracket\,\text{and}\,j\in\llbracket N_{g}\rrbracket\big{\\}}$, each
prediction will always be matched to the closest ground truth.

In theory, this a much too strong condition, the background cost can just be
greater than the minimum cost for each prediction
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\varnothing\right)>\min_{j}\left\\{\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right\\}$.
In practice, however, this does not change much. It suffices to set the
background cost high enough and we are assured to get a minimum. One could
also imagine a different background cost for each prediction in order to have
a more granular threshold.

##  Appendix C Scaling Algorithms

We present here the two scaling algorithms: Sinkhorn’s algorithm for
“‘balanced” _Optimal Transport_ and its variant for _Unbalanced Optimal
Transport_. We further show how it is connected to the softmax.

###  C.1 Sinkhorn and Variant

These two algorithms are taken from [peyre2019computational,
chizat2018scaling]. In particular we can see how taking
$\tau_{1}\rightarrow+\infty$ and $\tau_{2}\rightarrow+\infty$ in Algorithm 2
leads to Algorithm 1. Indeed, we have
$\lim_{\tau\rightarrow+\infty}\frac{\tau}{\tau+\epsilon}=1$. By $\oslash$, we
denote the element-wise (or Hadamard) division.

Data: Distributions $\bm{\alpha}\in\Delta^{N_{p}}$ and
$\bm{\beta}\in\Delta^{N_{g}+1}$, regularization parameter
$\epsilon\in\mathbb{R}_{>0}$ and cost matrix
$\bm{C}=\left[\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right]_{i,j=1}^{N_{p},N_{g}+1}\in\mathbb{R}_{\geq
0}^{N_{p}\times N_{g}+1}$ (including background
$\bm{y}_{N_{g}+1}=\varnothing$).

Result: Match $\hat{\bm{P}}\in\Delta^{N_{p},N_{g}+1}$.

1 begin

$\bm{K}_{\epsilon}\longleftarrow\exp\left(-\bm{C}/\epsilon\right)$

/* Gramm matrix (element-wise) */

$\bm{u}\longleftarrow\bm{1}_{N_{p}}/N_{p}$

/* Dual variable associated with $\bm{\alpha}$ */

$\bm{v}\longleftarrow\bm{1}_{N_{g}+1}/\left(N_{g}+1\right)$

/* Dual variable associated with $\bm{\beta}$ */

2 repeat

$\bm{u}\longleftarrow\bm{\alpha}\oslash\left(\bm{K}_{\epsilon}\bm{v}\right)$

/* Scaling iteration for $\bm{u}$ */

$\bm{v}\longleftarrow\bm{\beta}\oslash\left(\bm{K}_{\epsilon}^{\top}\bm{u}\right)$

/* Scaling iteration for $\bm{v}$ */

3

4 until  _convergence_

5 $\hat{\bm{P}}\longleftarrow\bm{u}\bm{K}_{\epsilon}\bm{v}$

6

Algorithm 1 Sinkhorn’s algorithm for “balanced” _Optimal Transport_ with
regularization.

1

Data: Distributions $\bm{\alpha}\in\Delta^{N_{p}}$ and
$\bm{\beta}\in\Delta^{N_{g}+1}$, regularization parameter
$\epsilon\in\mathbb{R}_{>0}$, constraint parameters
$\tau_{1},\tau_{2}\in\mathbb{R}_{\geq 0}$ and cost matrix
$\bm{C}=\left[\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right]_{i,j=1}^{N_{p},N_{g}+1}\in\mathbb{R}_{\geq
0}^{N_{p}\times N_{g}+1}$ (including background
$\bm{y}_{N_{g}+1}=\varnothing$).

Result: Match $\hat{\bm{P}}\in\mathbb{R}_{\geq 0}^{N_{p},N_{g}+1}$.

2 begin

$\bm{K}_{\epsilon}\longleftarrow\exp\left(-\bm{C}/\epsilon\right)$

/* Gramm matrix (element-wise) */

$\bm{u}\longleftarrow\bm{1}_{N_{p}}/N_{p}$

/* Dual variable associated with $\bm{\alpha}$ */

$\bm{v}\longleftarrow\bm{1}_{N_{g}+1}/\left(N_{g}+1\right)$

/* Dual variable associated with $\bm{\beta}$ */

3 repeat

$\bm{u}\longleftarrow\big{(}\bm{\alpha}\oslash(\bm{K}_{\epsilon}\bm{v})\big{)}^{\frac{\tau_{1}}{\tau_{1}+\epsilon}}$

/* Scaling iteration for $\bm{u}$ */

$\bm{v}\longleftarrow\big{(}\bm{\beta}\oslash(\bm{K}_{\epsilon}^{\top}\bm{u})\big{)}^{\frac{\tau_{2}}{\tau_{2}+\epsilon}}$

/* Scaling iteration for $\bm{v}$ */

4

5 until  _convergence_

6 $\hat{\bm{P}}\longleftarrow\bm{u}\bm{K}_{\epsilon}\bm{v}$

7

Algorithm 2 Scaling algorithm for _Unbalanced Optimal Transport_ with
regularization.

###  C.2 Connection with the Softmax

In this section, we lay a connection between the softmax and the solutions of
the scaling algorithms, in particular considering its first iterations. We
consider more precisely the softmin, which is the opposite of the softmax:
$\left(\mathrm{softmin}(\bm{v})\right)_{i}=\left(\mathrm{softmax}(-\bm{v})\right)_{i}=\exp(-v_{i})/\sum_{j=1}^{N}\exp(-v_{j})$,
for any vector $\bm{v}\in\mathbb{R}^{N}$. Considering a softmin over
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)$ is thus
the same as considering the softmax over
$-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)$, as in
[loftr]. By simplicity, we will only use the softmax terminology.

####  C.2.1 Without Background

We first consider the case without background, where the underlying
distributions are equal to $\bm{\alpha}=\bm{1}_{N_{p}}/N_{p}$ and
$\bm{\beta}=\bm{1}_{N_{g}}/N_{g}$. This does not correspond to the setup of
Prop. 1 and only approximates a one-to-one match if $N_{p}=N_{g}$.

######  Proposition 3.

Consider the two uniform distributions $\bm{\alpha}=\bm{1}_{N_{p}}/N_{p}$ and
$\bm{\beta}=\bm{1}_{N_{g}}/N_{g}$ with cost
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)$. The
solution of the Unbalanced OT scaling algorithm with regularization
$\varepsilon=1$, $\tau_{1}=0$ and $\tau_{2}\rightarrow+\infty$ is proportional
to performing a softmax over the predictions, for each ground truth object. In
particular, we have

$\hat{P}_{i,j}=\frac{\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{N_{g}\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(18)

###### Proof.

We consider the first scaling iteration from Alg. 2. We first observe that the
exponents lead to $\lim_{\tau_{1}\rightarrow
0}\frac{\tau_{1}}{\tau_{1}+\varepsilon}=0$ and
$\lim_{\tau_{2}\rightarrow+\infty}\frac{\tau_{2}}{\tau_{2}+\varepsilon}=1$.
Starting with $\bm{v}_{0}=\bm{1}_{N_{g}}/N_{g}$, we obtain the new

$\displaystyle\bm{u}_{1}=\left(\bm{\alpha}\oslash\left(\bm{K}_{\varepsilon}\bm{v}_{0}\right)\right)^{0}=\bm{1}_{N},$
$\displaystyle\qquad\text{or }\left(\bm{u}_{1}\right)_{i}=1,$ (19)
$\displaystyle\bm{v}_{1}=\left(\bm{\beta}\oslash\left(\bm{K}_{\varepsilon}^{\top}\bm{u}_{1}\right)\right)^{1}=\left(\bm{1}_{N_{g}}/N_{g}\right)\oslash\left(\bm{K}_{\varepsilon}^{\top}\bm{1}_{N}\right),$
$\displaystyle\qquad\text{or
}\left(\bm{v}_{1}\right)_{j}=\frac{1}{N_{g}\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(20)

We observe that $\bm{u}_{2}=\bm{u}_{1}$ and $\bm{v}_{2}=\bm{v}_{1}$ and
conclude that the algorithm converges after only one iteration. Computing the
match $\hat{\bm{P}}=\bm{u}\bm{K}_{\epsilon}\bm{v}$ leads to the softmax. ∎

The exact opposite happens if we consider $\tau_{1}\rightarrow+\infty$ and
$\tau_{2}=0$ instead: the softmax is taken over the ground truth objects for
each prediction. The proof is the same, just inverting $\bm{u}$ and $\bm{v}$
and obtaining factor $1/N_{p}$ instead. This can be observed at Fig. 7(b).

$\tau_{1}$
---
$\infty$
---
$0$
---
$\infty$
---
$\tau_{2}$
---
(degenerate)
---
Ground truth object
---
to best prediction
Prediction to best
---
ground truth object
Bipartite
---
Matching
(a) No regularization $\varepsilon=0$ (same as Fig. 4).

$\tau_{1}$
---
$\infty$
---
$0$
---
$\infty$
---
$\tau_{2}$
---
$\bm{P}=\hat{\bm{K}}_{\varepsilon}$
---
Softmax over
---
the predictions
Softmax over the
---
ground truth objects
Regularized OT
---
(b) With regularization $\varepsilon=1$.

Figure 7: Comparison of the different limit cases of _Unbalanced Optimal
Transport_ , with and without regularization.

If we would like to exactly obtain the softmax without the factor $1/N_{g}$
(or $1/N_{p}$), we could consider only one iteration starting with both
initial dual variables $\bm{u}_{0}$ and $\bm{v}_{0}$. It would however not be
the optimal match $\hat{\bm{P}}$ and will converge to the same solution as in
Prop. 3 after the second—and last—iteration. Nevertheless, starting from both
initial dual variables is more interesting in the “balanced” case.

######  Proposition 4.

Consider the two uniform distributions $\bm{\alpha}=\bm{1}_{N_{p}}/N_{p}$ and
$\bm{\beta}=\bm{1}_{N_{g}}/N_{g}$ with cost
$\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)$. Starting
from both initial dual variables, one iteration of the “balanced” OT scaling
algorithm with regularization $\varepsilon=1$ is equal to

$P_{i,j}=\frac{\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)\cdot\sum_{j=1}^{N_{g}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(21)

###### Proof.

We consider the first scaling iteration from Alg. 1 with
$\bm{\alpha}=\bm{1}_{N_{p}}/N_{p}$ and $\bm{\beta}=\bm{1}_{N_{g}}/N_{g}$.
Starting with $\bm{u}_{0}=\bm{1}_{N_{p}}/N_{p}$ and
$\bm{v}_{0}=\bm{1}_{N_{g}}/N_{g}$, we obtain the new

$\displaystyle\bm{u}_{1}=\bm{\alpha}\oslash\left(\bm{K}_{\varepsilon}\bm{v}_{0}\right)=\left(\bm{1}_{N_{p}}/N_{p}\right)\oslash\left(\bm{K}_{\varepsilon}\left(\bm{1}_{N_{g}}/N_{g}\right)\right),$
$\displaystyle\qquad\text{or
}\left(\bm{u}_{1}\right)_{i}=\frac{N_{g}}{N_{p}\sum_{j=1}^{N_{g}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)},$
(22)
$\displaystyle\bm{v}_{1}=\bm{\beta}\oslash\left(\bm{K}_{\varepsilon}^{\top}\bm{u}_{0}\right)=\left(\bm{1}_{N_{g}}/N_{g}\right)\oslash\left(\bm{K}_{\varepsilon}^{\top}\left(\bm{1}_{N_{p}}/N_{p}\right)\right),$
$\displaystyle\qquad\text{or
}\left(\bm{v}_{1}\right)_{j}=\frac{N_{p}}{N_{g}\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(23)

Computing the match $\bm{P}=\bm{u}\bm{K}_{\epsilon}\bm{v}$ leads to the Eq.
21. This is not the optimal match $\hat{\bm{P}}$ as the algorithm did not
converge yet. ∎

The _dual-softmax_ considered in [loftr] is essentially the same as Prop. 4,
with the difference of a factor $2$ in the numerator’s exponential:

$\displaystyle P_{i,j}$ $\displaystyle=$
$\displaystyle\mathrm{softmax}\left(\left[-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{k}\right)\right]_{k=1}^{N_{g}}\right)_{j}\cdot\,\mathrm{softmax}\left(\left[-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{l},\bm{y}_{j}\right)\right]_{j=1}^{N_{p}}\right)_{i},$
(24) $\displaystyle=$
$\displaystyle\frac{\exp\left(-2\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)\cdot\sum_{j=1}^{N_{g}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(25)

####  C.2.2 With Background

We now consider the underlying distributions as defined in Prop. 1.
Fundamentally, adding a background with a different weight than the other
ground truth objects does not change much. The unbalanced case with
$\tau_{1}\rightarrow+\infty$ and $\tau_{2}=0$ remains exactly the same. The
opposite case with $\tau_{1}=0$ and $\tau_{2}\rightarrow+\infty$ now becomes

$\hat{P}_{i,j}=\frac{1}{N_{p}}\frac{\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)},$
(26)

for all $1\leq j\leq N_{g}$, and

$\hat{P}_{i,j}=\frac{N_{p}-N_{g}}{N_{p}}\frac{\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)},$
(27)

for $j=N_{g}+1$ (the background). In essence, this ensures that the mass
constraints induced by $\tau_{2}$ are satisfied, as the background has a
higher weight.

Similarly, the “balanced” case is the same as Eq. 21 for all $1\leq j\leq
N_{g}$. For $j=N_{g}+1$, we have the same with an added factor:

$P_{i,j}=\left(N_{p}-N_{g}\right)\frac{\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}{\sum_{i=1}^{N_{p}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)\cdot\sum_{j=1}^{N_{g}}\exp\left(-\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)\right)}.$
(28)

####  C.2.3 Other Regularization

We can also consider other cases that having the regularization
$\varepsilon=1$. The regularization $\varepsilon$ controls the “softness” of
the softmax: the greater is $\varepsilon$, the softer is the minimum; the
smaller, the harder. In the case of no regularization at all
($\varepsilon\rightarrow 0$), the softmax is exactly a minimum as proven in
Prop. 2. This can be observed at Fig. 8.

|  |  |
---|---|---|---
|  |
|  |
|  |

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0
---
2
---
4
---
6
---
8
---
10
---
(a) Cost between the predictions and the ground truth objects.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(b) Unbalanced OT with $\varepsilon=0.2$, $\tau_{1}=0.001$ and
$\tau_{2}=1000$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(c) Unbalanced OT with $\varepsilon=1$, $\tau_{1}=0.001$ and $\tau_{2}=1000$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(d) Unbalanced OT with $\varepsilon=5$, $\tau_{1}=0.001$ and $\tau_{2}=1000$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(e) Unbalanced OT with $\varepsilon=0.2$, $\tau_{1}=1000$ and
$\tau_{2}=0.001$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(f) Unbalanced OT with $\varepsilon=1$, $\tau_{1}=1000$ and $\tau_{2}=0.001$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(g) Unbalanced OT with $\varepsilon=5$, $\tau_{1}=1000$ and $\tau_{2}=0.001$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(h) “Balanced” OT with only one iteration and $\varepsilon=0.2$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(i) “Balanced” OT with only one iteration and $\varepsilon=1$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(j) “Balanced” OT with only one iteration and $\varepsilon=5$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(k) “Balanced” OT until convergence with $\varepsilon=0.2$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(l) “Balanced” OT until convergence with $\varepsilon=1$.

A
---
B
---
C
---
$\varnothing$
---
1
---
2
---
3
---
4
---
5
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
(m) “Balanced” OT until convergence with $\varepsilon=5$.

Figure 8: Connection between scaling algorithms and the softmax. The pairwise
matching cost between the predictions (numbers) and the ground truth objects
(letters) is given in Fig. 8(a). The background cost is $c_{\varnothing}=2$.
The scaling algorithm for Unbalanced OT corresponds to performing the softmax
column-wise (Figs. 8(b), 8(c) and 8(d)), or row-wise (Figs. 8(e), 8(f) and
8(g)). Similarly, one iteration of the scaling algorithm for “balanced” OT is
almost equivalent to the dual-softmax (Figs. 8(h), 8(i) and 8(j)), but does
not satisfy the mass constraints unlike when it is run until convergence
(Figs. 8(k), 8(l) and 8(m)).

##  Appendix D Scaling the Entropic Parameter

In this section, we consider the particular choice of the entropic
regularization parameter. In particular, we study how it scales with the
problem size.

###  D.1 Uniform Matches

######  Definition 6 (Matches).

We define a _match_
$\bm{P}\in\mathbb{R}_{+}^{N_{p}\times\left(N_{g}+1\right)}$ as a positive
matrix of unity mass $\sum_{i,j}P_{i,j}=1$. The set of all matches of size
$N_{p}\times\left(N_{g}+1\right)$ is the joint probability simplex
$\Delta^{N_{p}\times\left(N_{g}+1\right)}$.

We now consider a particular subset of all these matches.

######  Definition 7 (Uniform Matches).

We define the set of _uniform matches_
$\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}\subsetneq\Delta^{N_{p}\times\left(N_{g}+1\right)}$
as the set of matrices
$\bm{P}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$,
containing only zero elements and all non-zero elements having the same value:

$P_{i,j}^{\mathrm{unif.}}=\left\\{\begin{array}[]{ll}0&\text{for some
values,}\\\
1/\left|\mathrm{spt}\left(\bm{P}^{\mathrm{unif.}}\right)\right|&\text{for the
other values,}\end{array}\right.$ (29)

with the support $\mathrm{spt}:\bm{P}\mapsto\left\\{(i,j):P_{i,j}\neq
0\right\\}$ and $\left|\,\cdot\,\right|$ the cardinality of a set.

We directly see from the definition that the matrices are well defined as they
have unity mass. They are uniquely defined by the carnality of their support.

######  Proposition 5 (Cardinality).

The cardinality of $\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
is given by

$\left|\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}\right|=2^{N_{p}\left(N_{g}+1\right)}.$
(30)

###### Proof.

We first notice that the different possible supports
$k=\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}\right)$ range from $1\leq
k\leq N_{p}\left(N_{g}+1\right)$. For any support of size $k$, we have to
consider a uniform match containing all combinations. The rest follows from
the binomial identity
$\sum_{k=1}^{N_{p}\left(N_{g}+1\right)}\binom{N_{p}\left(N_{g}+1\right)}{k}=2^{N_{p}\left(N_{g}+1\right)}$.
∎

We can also see that the uniform matches cover the set of all matches.

######  Proposition 6 (Diameter).

The diameter of the set of transport matrices
$\Delta^{N_{p}\times\left(N_{g}+1\right)}$ and uniform transport matrices
$\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$, equipped with the
Fröbenius norm $\|\cdot\|_{F}$, is given by

$\mathrm{diam}\left(\Delta^{N_{p}\times\left(N_{g}+1\right)}\right)=\mathrm{diam}\left(\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}\right)=\sqrt{2}$
(31)

###### Proof.

Maximizing the Fröbenius norm is equivalent to considering the maximization of
$\sum_{i}(u_{i}-v_{i})^{2}$ subject to $\sum_{i}u_{i}=1$ and
$\sum_{i}v_{i}=1$, with $\bm{u},\bm{v}\geq 0$. It takes its maximum value on
the boundary of the admissible solutions, for $u_{i}=1$ (the rest is zero) and
$v_{j}=1$ (the rest zero) for any $j\neq i$. These extreme points are also in
$\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$, in particular
those of unity support
$\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}\right)=1$. ∎

$\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)$
---
$\operatorname{spt}\left(\bm{P}_{2}^{\mathrm{unif.}}\right)$
---
$\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)$
$\setminus\operatorname{spt}\left(\bm{P}_{2}^{\mathrm{unif.}}\right)$
---
$\operatorname{spt}\left(\bm{P}_{2}^{\mathrm{unif.}}\right)$
$\setminus\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)$
---
$\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)$
$\cap\operatorname{spt}\left(\bm{P}_{2}^{\mathrm{unif.}}\right)$
---
Figure 9: Decomposition of the non-zero indices of two uniform transport
matrices
$\bm{P}_{1}^{\mathrm{unif.}},\bm{P}_{2}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$.

######  Proposition 7.

The Fröbenius norm square
$\lVert\bm{P}_{1}^{\mathrm{unif.}}-\bm{P}_{2}^{\mathrm{unif.}}\rVert_{F}^{2}$
between two uniform matches
$\bm{P}_{1}^{\mathrm{unif.}},\bm{P}_{2}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
is given by

$\frac{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|+\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|-2\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cap\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|}{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|}.$
(32)

###### Proof.

By decomposing the all indices as in Figure 9 in

$\displaystyle\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cup\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)$
$\displaystyle=$
$\displaystyle\left(\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\setminus\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right)$
$\displaystyle\cup\left(\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\setminus\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right)$
$\displaystyle\cup\left(\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cap\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right),$

and noticing that all other values are zero, we have for
$\lVert\bm{P}^{\mathrm{unif.}}_{1}-\bm{P}^{\mathrm{unif.}}_{2}\rVert_{F}^{2}$

$\displaystyle\left(\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|-\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cap\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|\right)\frac{1}{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|^{2}}$
$\displaystyle+$
$\displaystyle\left(\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|-\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cap\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|\right)\frac{1}{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|^{2}}$
$\displaystyle+$
$\displaystyle\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\cap\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|\left(\frac{1}{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|}-\frac{1}{\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|}\right)^{2}.$

The rest is just a simplification of the latter. ∎

######  Corollary 3.

Each uniform match
$\bm{P}_{1}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
has as closest neighbors all other uniform matches
$\bm{P}_{2}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
of support increased by one
$\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right|=\left|\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)\right|+1$
and differing in support for only one entry
$\left|\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\setminus\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)\right|=1$.
In particular, the square Fröbenius norm is then equal to

$\left\lVert\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{1}\right)-\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}_{2}\right)\right\rVert_{F}^{2}=\frac{1}{\left|\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)\right|\left(\left|\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)\right|+1\right)}.$
(33)

In in the particular limit case of
$\left|\operatorname{spt}\left(\bm{P}_{1}^{\mathrm{unif.}}\right)\right|=N_{p}\left(N_{g}+1\right)$,
its closest neighbors are all the $\bm{P}_{2}^{\mathrm{unif.}}$ such that
$\left|\operatorname{spt}\left(\bm{P}_{2}^{\mathrm{unif.}}\right)\right|=N_{p}\left(N_{g}+1\right)-1$.

######  Proposition 8.

We consider the projector
$\mathbb{P}:\Delta^{N_{p}\times\left(N_{g}+1\right)}\rightarrow\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$,
that minimizes the Fröbenius norm. For any
$\bm{P}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}$, we consider

$\mathbb{P}(\bm{P})=\underset{\bm{P}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}}{\mathrm{argmin}}\lVert\bm{P}-\bm{P}^{\mathrm{unif.}}\rVert_{F}.$
(34)

It is given by the matrix
$\bm{P}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
with the $k$ greatest elements of $\bm{P}$ as support and

$k=\underset{k\in\llbracket
N_{p}\left(N_{g}+1\right)\rrbracket}{\mathrm{arg\,max}}\,\frac{1}{k}\left(2\sum_{\begin{subarray}{c}\text{$k$
greatest}\\\ \text{elements}\end{subarray}}P_{ij}-1\right).$ (35)

###### Proof.

We consider the distance between any element
$\bm{P}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}$ and
$\bm{P}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$:
$\lVert\bm{P}-\bm{P}^{\mathrm{unif.}}\rVert_{F}^{2}=\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}\left(P_{i,j}-P^{\mathrm{unif.}}_{i,j}\right)^{2}=\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}P_{i,j}^{2}+\left(P^{\mathrm{unif.}}_{i,j}\right)^{2}-2P_{ij}P^{\mathrm{unif.}}_{i,j}$.
We notice that because of the uniform nature of $\bm{P}^{\mathrm{unif.}}$, it
only has $k$ non-zero elements, all equal to $1/k$. By consequence we have
$\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}\left(P^{\mathrm{unif.}}_{ij}\right)^{2}=\frac{1}{k}$
and
$\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}P_{ij}P^{\mathrm{unif.}}_{ij}=\frac{1}{k}\sum_{\mathrm{spt}(\bm{P}^{\mathrm{unif.}})}P_{ij}$.
The distance is now equal to
$\lVert\bm{P}-\bm{P}^{\mathrm{unif.}}\rVert_{F}^{2}=\lVert\bm{P}\rVert^{2}_{F}+\frac{1}{k}-\frac{2}{k}\sum_{\mathrm{spt}(\bm{P}^{\prime})}P_{ij}$,
and is minimal if
$\frac{2}{k}\sum_{\mathrm{spt}(\bm{P}^{\mathrm{unif.}})}P_{ij}-\frac{1}{k}$ is
maximal which is unique as it suffices to see that is it reached once

$\sum_{\begin{subarray}{c}\text{$k$ greatest}\\\
\text{elements}\end{subarray}}P_{ij}>P_{\begin{subarray}{c}\text{next}\\\
\text{greatest}\end{subarray}}+\frac{1}{2},$ (36)

is satisfied. ∎

The norm with the projector is therefore also given by
$\left\lVert\bm{P}-\mathbb{P}(\bm{P})\right\rVert^{2}_{F}=\lVert\bm{P}\rVert_{F}-2\sum_{\operatorname{spt}\left(\mathbb{P}(\bm{P})\right)}P_{ij}+\frac{1}{\left|\operatorname{spt}\left(\mathbb{P}(\bm{P})\right)\right|}$.
Equation 36 gives a direct algorithm to determine $k$ and thus the projected
value of any match $\bm{P}$.

###  D.2 Entropy

The study of uniform matches is relevant as they have an easy formulation for
their entropy.

######  Definition 8 (Entropy).

The entropy
$\mathrm{H}:\Delta^{N_{p}\times\left(N_{g}+1\right)}\rightarrow\mathbb{R}_{\geq
0}$ of a match $\bm{P}$ is given by

$\mathrm{H}(\bm{P})\stackrel{{\scriptstyle\text{def.}}}{{=}}-\sum_{i,j}P_{i,j}\left(\log\left(P_{i,j}\right)-1\right).$
(37)

If one of the elements would be zero, i.e., $P_{i,j}=0$, we consider
$P_{i,j}\log\left(P_{i,j}-1\right)=0$.

The latter condition ensures that the entropy is well defined. This choice is
justified as it remains consistent with the limit. Some authors prefer another
convention [peyre2019computational].

######  Lemma 3.

The entropy of a uniform match
$\bm{P}^{\mathrm{unif.}}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}_{\mathrm{unif.}}$
is given by

$\mathrm{H}(\bm{P}^{\mathrm{unif.}})=\log\left(\left|\mathrm{spt}(\bm{P}^{\mathrm{unif.}})\right|\right)+1.$
(38)

###### Proof.

The proof is a direct application of the definition of the entropy:

$\displaystyle\mathrm{H}(\bm{P}^{\mathrm{unif.}})$ $\displaystyle=$
$\displaystyle-\sum_{i,j}P_{i,j}^{\mathrm{unif.}}\left(\log\left(P^{\mathrm{unif.}}_{i,j}\right)-1\right),$
(39) $\displaystyle=$
$\displaystyle-\sum_{\operatorname{spt}\left(\bm{P}^{\mathrm{unif.}}\right)}P_{i,j}^{\mathrm{unif.}}\left(\log\left(P_{i,j}^{\mathrm{unif.}}\right)-1\right),$
(40) $\displaystyle=$
$\displaystyle-\frac{\left|\mathrm{spt}\left(\bm{P}^{\mathrm{unif.}}\right)\right|}{\left|\mathrm{spt}\left(\bm{P}^{\mathrm{unif.}}\right)\right|}\left(\log\left(\frac{1}{\left|\mathrm{spt}\left(\bm{P}^{\mathrm{unif.}}\right)\right|}\right)-1\right),$
(41) $\displaystyle=$
$\displaystyle\log\left(\left|\mathrm{spt}(\bm{P}^{\mathrm{unif.}})\right|\right)+1.$
(42)

∎

######  Proposition 9.

For any match $\bm{P}\in\Delta^{N_{p}\times\left(N_{g}+1\right)}$,

$1\leq H(\bm{P})\leq\log(N_{p}\left(N_{g}+1\right))+1.$ (43)

###### Proof.

For an arbitrary coupling matrix, the entropy is always minimal if $P_{i,j}=1$
for one element and all the others are zero. Similarly, the entropy is always
for the uniform match $P_{i,j}=1/\left|\mathrm{spt}\left(\bm{P}\right)\right|$
for all $i,j$, with
$\left|\mathrm{spt}\left(\bm{P}\right)\right|=N_{p}\times\left(N_{g}+1\right)$.
∎

###  D.3 Rule of Thumb

We first consider two different matches of different dimensions
$\bm{P}_{1}\in\Delta^{N_{p,1}\times\left(N_{g,1}+1\right)}$ and
$\bm{P}_{2}\in\Delta^{N_{p,2}\times\left(N_{g,2}+1\right)}$. In this case, the
OT with regularization cost (Definition 3) is given by
$\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}P_{i,j}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)-\epsilon\,\mathrm{H}(\bm{P})$.
The goal is to scale the regularization parameter $\epsilon$ in such a way
that the weight of the entropy is proportionally the same. Because of unit
mass of any match, we could assume that the first term
$\sum_{i,j=1}^{N_{p},\left(N_{g}+1\right)}P_{i,j}\mathcal{L}_{\text{match}}\left(\hat{\bm{y}}_{i},\bm{y}_{j}\right)$
is independent of $N_{p}$ and $N_{g}$ in magnitude. We therefore have to
guarantee that
$\epsilon_{1}\mathrm{H}\left(\bm{P}_{1}\right)=\epsilon_{2}\mathrm{H}\left(\bm{P}_{2}\right)$.
Given an already determined regularization value $\epsilon_{1}$ for one of the
two sizes, the other can be found with
$\epsilon_{2}=\epsilon_{1}\mathrm{H}\left(\bm{P}_{1}\right)/\mathrm{H}\left(\bm{P}_{2}\right)$.
In practice, however, the entropy is not trivial and we can rely on the
projection onto the uniform matches

$\epsilon_{1}=\epsilon_{2}\frac{\log\left(\left|\operatorname{spt}\left(\mathbb{P}\left(\bm{P}_{2}\right)\right)\right|\right)+1}{\log\left(\left|\operatorname{spt}\left(\mathbb{P}\left(\bm{P}_{1}\right)\right)\right|\right)+1}.$
(44)

In the particular case of Proposition 1, we can use the approximation
$\left|\operatorname{spt}\left(\mathbb{P}\left(\bm{P}\right)\right)\right|=N_{p}$,
which gives

$\epsilon_{1}=\epsilon_{2}\frac{\log\left(N_{p,2}\right)+1}{\log\left(N_{p,1}\right)+1}.$
(45)

The idea is to determine the optimal value $\epsilon_{1}$ on toy examples. By
setting $N_{p}=N_{p,2}$, $\epsilon=\epsilon_{2}$ and
$\epsilon_{0}=\epsilon_{1}\left(\log\left(N_{p,1}\right)+1\right)$, we can use
the simple scaling formula
$\epsilon=\epsilon_{0}/\left(\log\left(N_{p}\right)+1\right)$. From our
experiments, we determined $\epsilon_{0}=0.12$.

##  Appendix E Qualitative Analysis

This section provides qualitative examples (Figure 10 and Figure 11) of some
matches, as well as a convergence analysis for DETR and Deformable DETR. We
compare the losses and matches $\bm{P}$ of the two matching algorithms at
different training epochs.

Figure 10 shows some assignments of the two matching algorithms for DETR on
the Color Boxes dataset. We sample examples with few ground truth objects for
readability. We only show predictions that are matched at least once with a
background $\varnothing$ ground truth in three consecutive epochs. At the
beginning of the training, the _Bipartite Matching_ with the _Hungarian
algorithm_ assigns different predictions to the ground truth objects from one
epoch to the other. As an example, the algorithm for image №630 assigns
predictions $\\{4,49\\}$, $\\{8,1\\}$ and then $\\{99,1\\}$ to the ground-
truth objects $\\{A,B\\}$ at epoch 25 to 27 (Figure 10(a)). The regularized OT
match instead provides a smoother solution and is more consistent from one
epoch to the other. Later in training, Figure 10(a) illustrates that the
regularized OT matches are one-to-one and behave like the bipartite ones.

Figure 12 provides the loss curves for DETR on the Color Boxes dataset. The
curves suggest that the cross-entropy loss term mainly drives the convergence
speedup in the early training epochs. We don’t observe such speedups on COCO
or with Deformable DETR (Figure 13). An explanation could be that the
difference between DETR and Deformable DETR is due to the slower convergence
of transformers (we also tried DETR with the focal loss from Deformable DETR
without improvement). The difference between Color Boxes and COCO is difficult
to isolate, but probably due to the wider class diversity in the latter.

| A
---
B
---
$\varnothing$
---
9
---
41
---
43
---
63
---
90
---
epoch 25
---
A
---
B
---
$\varnothing$
---
epoch 26
---
A
---
B
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
$\varnothing$
---
9
---
67
---
69
---
90
---
epoch 75
---
A
---
B
---
$\varnothing$
---
epoch 76
---
A
---
B
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
$\varnothing$
---
67
---
69
---
epoch 125
---
A
---
B
---
$\varnothing$
---
epoch 126
---
A
---
B
---
$\varnothing$
---
epoch 127
---
| A
---
B
---
$\varnothing$
---
1
---
4
---
8
---
49
---
99
---
epoch 25
---
A
---
B
---
$\varnothing$
---
epoch 26
---
A
---
B
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
$\varnothing$
---
14
---
66
---
81
---
86
---
epoch 75
---
A
---
B
---
$\varnothing$
---
epoch 76
---
A
---
B
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
$\varnothing$
---
50
---
81
---
epoch 125
---
A
---
B
---
$\varnothing$
---
epoch 126
---
A
---
B
---
$\varnothing$
---
epoch 127
---
(a) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №630

| A
---
B
---
C
---
$\varnothing$
---
3
---
41
---
47
---
59
---
65
---
80
---
epoch 25
---
A
---
B
---
C
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
$\varnothing$
---
6
---
41
---
59
---
65
---
80
---
epoch 75
---
A
---
B
---
C
---
$\varnothing$
---
epoch 76
---
A
---
B
---
C
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
C
---
$\varnothing$
---
3
---
41
---
65
---
85
---
epoch 125
---
A
---
B
---
C
---
$\varnothing$
---
epoch 126
---
A
---
B
---
C
---
$\varnothing$
---
epoch 127
---
| A
---
B
---
C
---
$\varnothing$
---
4
---
11
---
28
---
39
---
55
---
59
---
67
---
81
---
90
---
epoch 25
---
A
---
B
---
C
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
$\varnothing$
---
11
---
14
---
31
---
34
---
63
---
69
---
epoch 75
---
A
---
B
---
C
---
$\varnothing$
---
epoch 76
---
A
---
B
---
C
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
C
---
$\varnothing$
---
6
---
31
---
70
---
epoch 125
---
A
---
B
---
C
---
$\varnothing$
---
epoch 126
---
A
---
B
---
C
---
$\varnothing$
---
epoch 127
---
(b) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №180

| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
7
---
9
---
14
---
22
---
32
---
41
---
47
---
48
---
50
---
54
---
65
---
epoch 25
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
3
---
22
---
50
---
54
---
63
---
69
---
99
---
epoch 75
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 76
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
22
---
48
---
50
---
54
---
63
---
69
---
epoch 125
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 126
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 127
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
14
---
21
---
33
---
36
---
37
---
57
---
62
---
63
---
65
---
66
---
81
---
83
---
92
---
99
---
epoch 25
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
6
---
14
---
26
---
36
---
55
---
81
---
82
---
epoch 75
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 76
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 77
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
6
---
17
---
42
---
52
---
56
---
81
---
82
---
epoch 125
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 126
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 127
---
(c) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №613

Figure 10: Output of the matching algorithms with DETR on the validation set
of the Color Boxes Dataset. The model is trained two times: once with an OT
match and once with a Hungarian matching. The rows indicate the predictions
and the columns indicate the ground truth objects (including the background
$\varnothing$). We sample examples with few ground truth objects for
readability and only show predictions that are matched at least once with a
non-background ground truth.

| A
---
B
---
$\varnothing$
---
17
---
28
---
80
---
111
---
epoch 5
---
A
---
B
---
$\varnothing$
---
epoch 6
---
A
---
B
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
$\varnothing$
---
17
---
28
---
147
---
epoch 25
---
A
---
B
---
$\varnothing$
---
epoch 26
---
A
---
B
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
$\varnothing$
---
28
---
147
---
epoch 45
---
A
---
B
---
$\varnothing$
---
epoch 46
---
A
---
B
---
$\varnothing$
---
epoch 47
---
| A
---
B
---
$\varnothing$
---
111
---
114
---
147
---
epoch 5
---
A
---
B
---
$\varnothing$
---
epoch 6
---
A
---
B
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
$\varnothing$
---
114
---
147
---
202
---
epoch 25
---
A
---
B
---
$\varnothing$
---
epoch 26
---
A
---
B
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
$\varnothing$
---
80
---
114
---
epoch 45
---
A
---
B
---
$\varnothing$
---
epoch 46
---
A
---
B
---
$\varnothing$
---
epoch 47
---
(a) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №630

| A
---
B
---
C
---
$\varnothing$
---
63
---
129
---
168
---
179
---
191
---
211
---
274
---
epoch 5
---
A
---
B
---
C
---
$\varnothing$
---
epoch 6
---
A
---
B
---
C
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
C
---
$\varnothing$
---
129
---
168
---
179
---
191
---
204
---
epoch 25
---
A
---
B
---
C
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
$\varnothing$
---
93
---
129
---
168
---
epoch 45
---
A
---
B
---
C
---
$\varnothing$
---
epoch 46
---
A
---
B
---
C
---
$\varnothing$
---
epoch 47
---
| A
---
B
---
C
---
$\varnothing$
---
105
---
191
---
211
---
272
---
274
---
epoch 5
---
A
---
B
---
C
---
$\varnothing$
---
epoch 6
---
A
---
B
---
C
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
C
---
$\varnothing$
---
93
---
191
---
274
---
287
---
epoch 25
---
A
---
B
---
C
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
$\varnothing$
---
129
---
191
---
287
---
epoch 45
---
A
---
B
---
C
---
$\varnothing$
---
epoch 46
---
A
---
B
---
C
---
$\varnothing$
---
epoch 47
---
(b) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №180

| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
54
---
61
---
80
---
145
---
180
---
181
---
245
---
254
---
epoch 5
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 6
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
54
---
61
---
80
---
145
---
180
---
238
---
245
---
254
---
epoch 25
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
54
---
61
---
80
---
180
---
254
---
epoch 45
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 46
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 47
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
54
---
61
---
62
---
66
---
80
---
145
---
180
---
245
---
265
---
epoch 5
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 6
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 7
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
61
---
163
---
179
---
180
---
245
---
254
---
epoch 25
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 26
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 27
---
| A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
61
---
179
---
180
---
214
---
245
---
epoch 45
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 46
---
A
---
B
---
C
---
D
---
E
---
$\varnothing$
---
epoch 47
---
(c) Result of the OT match (top row) and the Hungarian match (bottom row) on
image №613

Figure 11: Output of the matching algorithms with Deformable-DETR on the
validation set of the Color Boxes Dataset. The model is trained two times:
once with an OT match and once with a Hungarian matching. The rows indicate
the predictions and the columns indicate the ground truth objects (including
the background $\varnothing$). We sample examples with few ground truth
objects for readability and only show predictions that are matched at least
once with a non-background ground truth. 0
---
25
---
50
---
75
---
100
---
125
---
150
---
0.5
---
1.0
---
1.5
---
2.0
---
2.5
---

CE loss
---

Training
---
Hungarian
---
OT
---
0
---
25
---
50
---
75
---
100
---
125
---
150
---
0.5
---
1.0
---
1.5
---
2.0
---
2.5
---
Validation
---
Hungarian
---
OT
---
0
---
25
---
50
---
75
---
100
---
125
---
150
---
0.4
---
0.8
---
1.2
---
1.6
---

GIOU loss
---

Hungarian
---
OT
---
0
---
25
---
50
---
75
---
100
---
125
---
150
---
0.4
---
0.8
---
1.2
---
1.6
---
Hungarian
---
OT
---
0
---
25
---
50
---
75
---
100
---
125
---
150
---
Epoch
---
0.1
---
0.2
---
0.3
---
0.4
---
0.5
---

L1 loss
---

Hungarian
---
OT
---
0
---
25
---
50
---
75
---
100
---
125
---
150
---
Epoch
---
0.1
---
0.2
---
0.3
---
0.4
---
0.5
---
Hungarian
---
OT
---
Figure 12: Training and validation unscaled loss curves for DETR on the Color
Boxes dataset. The training loss is the average over the epoch. 0
---
10
---
20
---
30
---
40
---
50
---
0.10
---
0.20
---
0.30
---
0.40
---
0.50
---

Focal loss
---

Training
---
Hungarian
---
OT
---
0
---
10
---
20
---
30
---
40
---
50
---
0.10
---
0.20
---
0.30
---
0.40
---
0.50
---
Validation
---
Hungarian
---
OT
---
0
---
10
---
20
---
30
---
40
---
50
---
0.10
---
0.20
---
0.30
---
0.40
---
0.50
---

GIOU loss
---

Hungarian
---
OT
---
0
---
10
---
20
---
30
---
40
---
50
---
0.10
---
0.20
---
0.30
---
0.40
---
0.50
---
Hungarian
---
OT
---
0
---
10
---
20
---
30
---
40
---
50
---
Epoch
---
0.03
---
0.06
---
0.09
---
0.12
---

L1 loss
---

Hungarian
---
OT
---
0
---
10
---
20
---
30
---
40
---
50
---
Epoch
---
0.03
---
0.06
---
0.09
---
0.12
---
Hungarian
---
OT
---
Figure 13: Training and validation unscaled loss curves for Deformable DETR on
the Color Boxes dataset. The training loss is the average over the epoch.

##  Appendix F Number of Sinkhorn Iterations

Using a stopping criterion is not straightforward when solving a batch of
matching problems. The scaling algorithm is therefore set to a fixed number of
iterations. Figure 14 displays the results for different numbers of
iterations. For the balanced OT with 300 predictions (Figure 14(a)), the AP
increases only slightly when more than 10 iterations are performed.
Furthermore, it is sufficient to run 1 iteration in terms of the AR. For the
_Unbalanced OT_ with 8,732 predictions (Figure 14(b)), the metrics are
significantly lower when running for less than 5 iterations. Again, running
more than 10 iterations only slightly improves the final performance. This
fact is supported by Prop. 3, which shows that in the limit case where
$\tau_{1}=0$ and $\tau_{2}\rightarrow+\infty$, only one or two iterations are
required for convergence (depending on the implementation).

1
---
5
---
10
---
20
---
30
---
40
---
50
---
80
---
Number of iterations
---
60
---
64
---
68
---
72
---
76
---
80
---

Metric
---

AP
---
AR
---
(a) Deformable DETR with Balanced OT.

1
---
5
---
10
---
20
---
30
---
40
---
50
---
80
---
Number of iterations
---
32
---
38
---
44
---
50
---
56
---
62
---
68
---

Metric
---

AP
---
AR
---
(b) SSD300 with Unbalanced OT ($\tau_{2}=0.01$).

Figure 14: Influence of the number of Sinkhorn iterations on the final metrics
on the Color Boxes dataset.

##  Appendix G First Constraint Parameter

In this section, we analyze the effect of the prediction’s mass constraint
parameter $\tau_{1}$, while we fix parameter $\tau_{2}$ to a large value
$\tau_{2}=100$ to simulate a hard constraint. Parameter $\tau_{1}$ controls
the degree to which variations in the prediction masses are penalized. Each
ground-truth object can be matched to the best prediction in the limit case
$\tau_{2}\to+\infty$ and $\tau_{1}=0$. However, some predictions cannot be
matched, and others multiple times. The results for SSD on Color Boxes are
displayed in Table 3. Wa can therefore conclude that the first constraint
parameter $\tau_{1}$ has a small influence on the metrics, both with and
without NMS. Nevertheless, a higher performance is reached in the balanced
case, _i.e_., when $\tau_{1}\to+\infty$.

Matching | $\bm{\tau_{1}}$ | with NMS | w/o NMS
---|---|---|---
AP | AR | AP | AR
Unb. OT | 0.01 | 47.2 | 62.0 | 41.9 | 71.1
Unb. OT | 0.1 | 47.7 | 63.7 | 44.7 | 72.3
Unb. OT | 1 | 47.7 | 64.0 | 44.8 | 72.7
Unb. OT | 10 | 47.8 | 63.8 | 45.0 | 72.6
OT |  ($\infty$) | 48.1 | 64.3 | 45.2 | 73.0
Table 3: Comparison of matching strategies on the Color Boxes dataset. SSD300
is evaluated both with and without NMS.

##  Appendix H Timing Analysis for SSD

As can be seen in Table 4, OT-based matches improve the epoch time (forward
pass, compute the match cost, matching algorithm, and backward pass; in blue)
for SSD with the Hungarian algorithm by almost 50%. The difference is smaller
for DETR and variants as the models are proportionally heavier and the number
of predictions smaller.

Epoch step | OT | Unb. OT | Hung. | 2-step
---|---|---|---|---
Preprocessing | 6.3 ms | idem | idem | idem
Forward pass | 5.8 ms | idem | idem | idem
Anchor gen. | 54.2 ms | idem | idem | idem
Match cost | 4.2 ms | idem | idem | idem
Matching | 1.1 ms | 1.5 ms | 18.3 ms | 2.3 ms
Backward pass | 8.2 ms | idem | idem | idem
Final losses | 11.6 ms | 11.6 ms | 9.7 ms | 9.7 ms
Table 4: Timing for each step in SSD300 on Color Boxes and a batch size of 16,
computed with an Nvidia TITAN X GPU and Intel Core i7-4770K CPU @ 3.50GHz.
Likewise the models we built upon, we used Torchvision’s anchor generation
implementation, which extensively relies on heavy loops and could drastically
be improved (not the focus of our work). The final losses timings are
partially due to the expensive hard-negative mining.

##  Appendix I Color Boxes Dataset

This section provides a discussion of the Color Boxes synthetic dataset. It is
split into 4,800 training and 960 validation images of 500 $\times$ 400
pixels. Images have a gray background. We uniformly randomly draw between 0
and 30 rectangles of 20 different colors, which define the category of the
rectangle. The dimension of the rectangles vary from 12 to 80 pixels and are
uniformly randomly rotated. They are placed such that the $\mathrm{IoU}$
between their bounding boxes is at most $0.25$. A gaussian noise of mean 0 and
standard deviation 0.05 is added to each pixel value independently. Sample
images are drawn in Fig. 15.

|  |  |
---|---|---|---
|  |  |
|  |  |
Figure 15: Sample images from the Color Boxes Dataset.