# Split and Connect: A Universal Tracklet Booster for Multi-Object Tracking

Gaoang Wang1, Yizhou Wang2, Renshu Gu∗,3, Weijie Hu∗,4, and Jenq-Neng Hwang2
1Zhejiang University, China
2University of Washington, USA
3Hangzhou Dianzi University, China
4Guangdong University of Petrochemical Technology, China
<EMAIL_ADDRESS>
###### Abstract

Multi-object tracking (MOT) is an essential task in the computer vision field.
With the fast development of deep learning technology in recent years, MOT has
achieved great improvement. However, some challenges still remain, such as
sensitiveness to occlusion, instability under different lighting conditions,
non-robustness to deformable objects, etc. To address such common challenges
in most of the existing trackers, in this paper, a tracklet booster algorithm
is proposed, which can be built upon any other tracker. The motivation is
simple and straightforward: split tracklets on potential ID-switch positions
and then connect multiple tracklets into one if they are from the same object.
In other words, the tracklet booster consists of two parts, i.e., Splitter and
Connector. First, an architecture with stacked temporal dilated convolution
blocks is employed for the splitting position prediction via label smoothing
strategy with adaptive Gaussian kernels. Then, a multi-head self-attention
based encoder is exploited for the tracklet embedding, which is further used
to connect tracklets into larger groups. We conduct sufficient experiments on
MOT17 and MOT20 benchmark datasets, which demonstrates promising results.
Combined with the proposed tracklet booster, existing trackers usually can
achieve large improvements on the IDF1 score, which shows the effectiveness of
the proposed method.

###### Index Terms:

multi-object tracking, embedding, attention

11footnotetext: Corresponding author.

##  I Introduction

Multi-object tracking (MOT) has drawn great attention in recent years. This
technique is critically needed in many tasks, such as traffic flow analysis
[1, 2, 3, 4], human behavior prediction and pose estimation [5, 6, 7, 8, 9],
autonomous driving assistance [10, 11, 12] and even for underwater animal
abundance estimation [13, 14, 15]. Recent years have seen the emergence of a
variety of tracking algorithms, from graph clustering methods [16, 17, 1, 18,
19] to graph neural networks [20, 21, 22, 23] that aggregate information
across frames and objects, from tracking-by-detection paradigm to joint
detection and tracking [24, 25, 20, 26, 27, 28] to improve the detection
performance with multiple frames, from Kalman filtering [29] to recurrent
neural networks (RNN) [30] and long-short term memory (LSTM) [31] to boost
association performance with the motion clue. However, due to the noisy visual
object detection and occlusion, tracking multiple objects over a long time is
yet very challenging.

Typically, the tracking error comes from two parts: object detection and
temporal association. To measure the performance of trackers, three main
evaluation metrics, i.e., multi-object tracking accuracy (MOTA) [32], IDF1
score [33] and higher order tracking accuracy (HOTA) [34], are widely used in
MOT field. As demonstrated in [34], MOTA emphasizes detection accuracy while
IDF1 focuses more on association measurement. As shown in Figure 1, generally,
the association errors can be concluded into two categories: 1) different
objects are associated to the same tracklet, 2) tracklets from the same object
are assigned to different IDs. A good tracker should reduce these two types of
errors as much as possible in the association task. Due to missing detection,
change of lighting condition, camera movement, occlusion and object
deformation, the association is one of the major challenges of almost all
existing trackers.

Figure 1: Demonstration of association errors. The first error type shows
multiple objects are associated to the same tracklet. The second error shows
the same object are assigned to different tracklets.

In this paper, we propose a novel method, tracklet booster, that directly
targets the two types of association error to boost the performance on IDF1
score, without tackling much for the detection error. Also, it can be
efficiently plugged into any existing trackers. The tracklet booster has two
main modules, Splitter and Connector. Splitter aims at finding potential ID-
switch positions of a tracklet and split the tracklet into small pieces at the
detected ID-switch positions. Splitter is designed with stacked dilated
temporal convolution blocks to measure the temporal consistency of a tracklet.
An adaptive label smoothing strategy with Gaussian kernels is proposed to
improve the stability of the model training. With Splitter, the first type of
error that multiple objects are assigned with the same ID can be largely
reduced. On the other hand, Connector is introduced to address the second type
of association error that the same identity is assigned to multiple tracklets.
Connector aims at distinguishing different objects and merging multiple
tracklets into one if they are from the same object. Specifically, Connector
is modeled as a tracklet embedding network. Tracklets with small embedding
distances are grouped and associated with the same tracking ID. Inspired by
the transformer [35], we use the multi-head self-attention mechanism to learn
the tracklet embedding. The framework of the tracklet booster is shown in
Figure 2.

We summarize our contributions as follows:

  * •

We propose a novel tracklet boosting model, consisting of a Splitter and a
Connector, to directly address the temporal association errors that exist in
almost all trackers in the MOT field. Besides, the proposed tracklet booster
can be integrated with any existing trackers to significantly improve their
tracking performance.

  * •

A novel adaptive label smoothing strategy with Gaussian kernels is proposed in
Splitter to predict the potential ID-switch positions within the given
tracklet.

  * •

Multi-head self-attention based encoder is employed for tracklet embedding,
which serves as the main module of the proposed Connector.

  * •

We conduct experiments on MOT17 and MOT20 benchmark datasets and prove the
generality, effectiveness and robustness of our tracklet boosting method.

##  II Related Work

Figure 2: The flowchart of the proposed tracklet booster. The top part and
bottom part show the process of Splitter and Connector, respectively. $f_{s}$
and $f_{c}$ represent the dilated temporal convolution model and multi-head
self-attention based encoder used in Splitter and Connector, respectively.
$\hat{\boldsymbol{\sigma}}$ is the predicted standard deviation for adaptive
smoothing; $\hat{\boldsymbol{m}}$ is the predicted splitting position mask;
$\boldsymbol{m^{*}}$ is the ground truth splitting mask; $\mathcal{L}_{s}$,
$\mathcal{L}_{xent}$ and $\mathcal{L}_{triplet}$ are mean squared error,
cross-entropy loss and triplet loss, respectively.

###  II-A Tracking with Graph Models

Graph models [16, 17, 1, 18, 19, 36, 37, 38, 39, 40, 41, 42, 43, 44] are
widely used in MOT for temporal association. The association is traditionally
solved by optimizing the total cost or energy function. For example, [17]
formulates MOT as a minimization of a continuous energy function. [16]
proposes a novel graph-based formulation that links and clusters person
hypotheses over time by solving an instance of a minimum cost lifted multi-cut
problem. [40] proposes an end-to-end framework for learning parameters of min-
cost flow MOT problem with quadratic trajectory interactions including
suppression of overlapping tracks and contextual cues about the co-occurrence
of different objects. [44] proposes an extension to the disjoint paths problem
in which additional lifted edges are introduced to provide path connectivity
priors. [41] proposes an efficient online min-cost flow tracking algorithm
with bounded memory and computation. In addition to the single-view tracking,
graph based methods are also explored in multi-view tracking tasks [45, 46,
47], where the multi-view tracking is formulated as a graph clustering
problem. Usually, detections or tracklets are adopted as graph nodes. Then,
the similarities among nodes are measured on the connected edges. For
detection-based graphs, the temporal information is not well utilized and
usually comes with a remarkably high dimensional affinity matrix with a heavy
computational cost. The tracklet-based graph, on the other hand, is much more
efficient and also incorporates global temporal information. However, the
conventional graph models, based on optimization, usually suffer from
empirically setting of hand-crafted features. Moreover, representative
embeddings are not well-explored for the temporal association.

Since the graph neural networks (GNN) show great power recently, many
approaches [20, 21, 22, 23, 48] adopt GNN for the association, rather than
using conventional graph models based on optimization. Specifically, [21]
exploits the classical network flow formulation of MOT to define a fully
differentiable framework based on message passing networks. [22] presents an
adaptive graph neural network to fuse locations, appearance, and historical
information for MOT. [23] proposes a novel feature interaction mechanism based
on the GNN to learn the interaction among objects. [48] presents a novel
learnable graph matching method to address association issues in MOT. [49]
proposes a novel proposal-based learnable framework, which models MOT as a
proposal generation, proposal scoring and trajectory inference paradigm on an
affinity graph. The existing methods show the effectiveness of employing GNN
to MOT. Moreover, GNN also shows power in other related vision tasks, such as
human action recognition [50], visual question answering [51] and single
object tracking [52].

###  II-B Joint Detection and Tracking

More recently, joint detection and tracking based methods have drawn great
attention [24, 25, 20, 26, 27, 28, 53]. Usually, such trackers take sequential
adjacent frames as input. Features are aggregated in different frames, and
bounding box regression is conducted with temporal information. For example,
Tracktor [27] applies bounding box regression to refine the box position in
the next frame to form the track; JDE [28] incorporates the appearance
embedding model into a single-shot detector that can simultaneously output
detections and the corresponding embeddings; while CenterTrack [24] applies a
detection model to a pair of images and detections from the prior frame.
Besides that, CTracker [25] constructs tracklets by chaining paired boxes in
every two frames. TubeTK [26] directly predicts a box tube as a tracklet in an
offline manner. [53] proposes a quasi-dense similarity learning approach that
densely samples hundreds of region proposals on a pair of images for
contrastive learning. However, due to the heavy computational cost, the
networks can only take a very limited number of frames as input. However, such
methods usually suffer long-time occlusions, which further results in temporal
association error.

###  II-C Tracking with Visual Transformers

Recently, due to the non-local attention mechanism, transformers [35] show
great success in many visual tasks, such as image classification [54], object
detection [55, 56], 3D human pose estimation [57] and low-level image
processing [58]. Moreover, several methods with visual transformers [59, 60,
61] are explored in the MOT field. For example, [59] proposes a baseline
tracker via transformer, which takes advantage of the query-key mechanism and
introduces a set of learned object queries into the pipeline to enable
detecting new-coming objects. [60] extends the DETR object detector [55] and
achieves a seamless data association between frames in a new tracking-by-
attention paradigm by encoder-decoder and self-attention mechanisms. [61]
leverages graph transformers to efficiently model the spatial and temporal
interactions among the objects. However, transformer-based trackers usually
require pre-training on large-scale datasets.

##  III Method

The motivation of the tracklet booster is simple yet effective. We take the
tracklets from any tracklet generators [13, 62, 39] or preliminary tracking
results as the input. Due to matching errors, a tracklet may contain multiple
object IDs. To clean the IDs within the tracklet, Splitter is proposed to
split tracklets into small pieces on the potential ID-switch positions to
ensure split tracklets have purer IDs as much as possible. Next, the split
tracklets are sent into Connector to learn representative embeddings. Finally,
the tracklets with the similar embeddings are grouped to form clusters, i.e.,
to generate the final entire track. The framework of the tracklet booster is
shown in Figure 2. The details of Splitter and Connector are demonstrated in
the following sub-sections.

###  III-A Splitter

In this sub-section, we demonstrate the proposed Splitter, which is designed
to predict the potential ID-switch positions and split the tracklets. Denote
the input tracklets as $\boldsymbol{x}$ with the dimension $K\times T$, where
$K$ is the feature dimension, and $T$ is the temporal length of tracklet.
Denote the ID-switch position mask as $\boldsymbol{m}$ with the dimension
$T-1$, where $\boldsymbol{m}$ is set as follows,

$\boldsymbol{m}_{t}=\begin{cases}1,\ \text{if}\
\text{ID}_{t}\neq\text{ID}_{t+1};\\\ 0,\ \text{otherwise}.\end{cases}$ (1)

The goal of Splitter is to estimate the ID-switch position mask given the
input tracklets $\boldsymbol{x}$, i.e.,

$\boldsymbol{\hat{m}}=f_{s}(\boldsymbol{x}),$ (2)

where $f_{s}(\cdot)$ is the proposed Splitter.

To learn Splitter, a loss function, i.e.,
$\mathcal{L}_{s}=l(\boldsymbol{\hat{m}},\boldsymbol{m}^{*})$, needs to be
defined between the predicted ID-switch position mask $\boldsymbol{\hat{m}}$
and the ground truth ID-switch position mask $\boldsymbol{m}^{*}$. As shown in
Figure 3, the object embeddings in adjacent frames usually change gradually
rather than change abruptly, even in the ID-switch positions. However, the
ground truth mask is hard labeled with zeros and ones. Such inconsistency
between labels and features will harm the stability of the model training with
the commonly used mean squared error, i.e.,
$\mathcal{L}_{s}=||\boldsymbol{\hat{m}}-\boldsymbol{m}^{*}||^{2}$. As a
result, it would be more appropriate to use soft labels rather than hard
labels in the loss function design.

To incorporate the soft label, we adopt Gaussian smoothing in the mean squared
error as the loss function as follows,

$\mathcal{L}_{s}=\sum_{t}\left(\boldsymbol{\hat{m}}_{t}-\min\left(\sum_{\tau}\boldsymbol{m}^{*}_{\tau}\exp\left(-{\frac{(\tau-t)^{2}}{\sigma^{2}}}\right),1\right)\right)^{2},$
(3)

where $t$ and $\tau$ are the frame index for the predicted mask
$\boldsymbol{\hat{m}}$ and ground truth mask $\boldsymbol{m}^{*}$,
respectively; $\sigma$ is the standard deviation that controls the smoothness
of the label. The ground truth mask $\boldsymbol{m}^{*}$ is used as an
indicator for the summation of Gaussian kernels. We also use $\min(\cdot,1)$
to constrain the smoothed mask labels in the range $[0,1]$.

In different scenarios, the gradual change of embeddings when the ID switch
happens can last from a few frames to tens of frames. In other words, $\sigma$
should be dependent on the duration of the ID-switch transition. Setting a
fixed $\sigma$ in the model would derive a sub-optimal solution. To deal with
such an issue, we propose an adaptive Gaussian smoothing strategy. Along with
the prediction of ID-switch position mask $\boldsymbol{\hat{m}}$, we also
predict a time and tracklet dependent $\boldsymbol{\hat{\sigma}}$
simultaneously via Splitter as follows,

$[\boldsymbol{\hat{m}},\boldsymbol{\hat{\sigma}}]=f_{s}(\boldsymbol{x}),$ (4)

where $\boldsymbol{\hat{\sigma}}$ has the same dimension as
$\boldsymbol{\hat{m}}$. Based on the time dependent
$\boldsymbol{\hat{\sigma}}$, we modify the loss function as follows,

$\mathcal{L}_{s}=\sum_{t}\left(\boldsymbol{\hat{m}}_{t}-\min\left(\sum_{\tau}\boldsymbol{m}^{*}_{\tau}\exp\left(-{\frac{(\tau-t)^{2}}{\boldsymbol{\tilde{\sigma}}_{\tau}^{2}}}\right),1\right)\right)^{2}.$
(5)

where we set
$\boldsymbol{\tilde{\sigma}}=\max(\min(\boldsymbol{\hat{\sigma}},10),\epsilon)$
to avoid irregular predictions. Typically, $\epsilon$ is set to be a small
positive scalar, e.g., 0.001. With adaptive soft labels, Splitter model can
predict ID-switch positions with different variant transitions of ID switches.

Figure 3: Example of the transition of an ID switch. Usually, the embeddings
around the ID switch positions change gradually. Thus, the hard label of the
ground truth splitting position mask $\boldsymbol{m}^{*}$ can cause
instability in the training. Figure 4: The architecture of the Splitter model.
The box with dashed lines represents each temporal dilated convolution block.
“k3d2” means the temporal convolution with kernel size 3 and dilation rate 2.
“$\oplus$” represents the summation operation.

The architecture of Splitter is designed as follows. Commonly used stacked
dilated temporal convolution and pointwise convolution blocks are employed as
the backbone for the feature extraction. Then two fully connected layers are
used for ID-switch position mask and standard deviation prediction,
respectively. We also add a skip connection for each intermediate block. In
total, we stack 24 blocks. As a result, the receptive field is large enough to
capture the long-term temporal patterns to detect the splitting positions. The
architecture of Splitter is shown in Figure 4.

###  III-B Connector

In this sub-section, we demonstrate the proposed Connector, which is designed
to connect multiple tracklets if they are from the same object. We formulate
the tracklet connection as a tracklet embedding problem as follows,

$\boldsymbol{h}=f_{c}(\boldsymbol{x}),$ (6)

where $f_{c}$ is the proposed Connector model, $\boldsymbol{h}$ is the
tracklet embedding with $\boldsymbol{h}\in\mathbb{R}^{D}$. After embedding is
learned, tracklets from the same object should have a smaller embedding
distance, while the tracklets from distinct objects should have a larger
distance.

Due to sensitivity in occlusion, the difference in lighting condition,
deformation in object pose, features from tracklets may have much difference
even though they are from the same object. To address such issues, self-
attention is an appropriate strategy for tracklet embedding. Inspired from the
transformer [35], a multi-head self-attention mechanism is employed for
tracklet embedding in the proposed Connector model. The embedding framework is
shown in Figure 5.

Specifically, given the tracklet appearance features
$\boldsymbol{x}\in\mathbb{R}^{K\times T}$, the self-attention (SA) is defined
as follows,

$\displaystyle[\boldsymbol{q},\boldsymbol{k},\boldsymbol{v}]=\boldsymbol{x}^{T}\boldsymbol{W},$
(7)
$\displaystyle\boldsymbol{A}=\text{softmax}\left(\boldsymbol{q}\boldsymbol{k}^{T}/\sqrt{D_{h}}\right),$
$\displaystyle\text{SA}(\boldsymbol{x})=\boldsymbol{A}\boldsymbol{v},$

where $\boldsymbol{W}\in\mathbb{R}^{D\times 3D_{h}}$ is the transformation
that converts the input tracklet to query, key and value;
$\boldsymbol{A}\in\mathbb{R}^{T\times T}$ stores the attention weights;
$\text{SA}(\boldsymbol{x})$ represents the self-attention given the input
$\boldsymbol{x}$. For the first input layer, we set $D=K$. Then we define the
multi-head self-attention with the concatenation of $k$ SA as follows,

$\text{MSA}(\boldsymbol{x})=[\text{SA}_{1}(\boldsymbol{x});\text{SA}_{2}(\boldsymbol{x});...;\text{SA}_{k}(\boldsymbol{x})]\boldsymbol{W}^{O},$
(8)

where $\boldsymbol{W}^{O}\in\mathbb{R}^{kD_{h}\times D}$ aggregates the
information from multi-heads and transforms it back to the original dimension
$D$. After the multi-head self-attention layer, a feed-forward layer is
further applied for encoding.

After the final layer of the encoder, we also stack a classification head for
learning the embedding. The classification head includes a global average
pooling (GAP) layer, $l_{2}$ normalization and one fully connected layer,
i.e.,

$\displaystyle\boldsymbol{h}=\text{norm}_{l_{2}}\left(\text{GAP}(\boldsymbol{z}_{L})\right),$
(9) $\displaystyle\boldsymbol{p}=\boldsymbol{W}_{c}\boldsymbol{h},$

where $\boldsymbol{z}_{L}$ is the output of the last encoding layer,
$\boldsymbol{h}$ is the final tracklet embedding,
$\boldsymbol{W}_{c}\in\mathbb{R}^{D\times C}$ is the weight of the fully
connected layer, $\boldsymbol{p}$ is the predicted logits for $C$ classes. The
purpose of GAP is to pool the features along the temporal dimension from
$D\times T$ to $D$. cross-entropy loss $\mathcal{L}_{xent}$ and triplet loss
$\mathcal{L}_{triplet}$ are used in the training as follows,

$\displaystyle\mathcal{L}_{xent}=\sum_{i=1}^{N}-\log\left(\frac{\exp\left(\boldsymbol{p}_{i}^{c}\right)}{\sum_{j=1}^{C}\exp\left(\boldsymbol{p}_{i}^{j}\right)}\right),$
(10)
$\displaystyle\mathcal{L}_{triplet}=\sum_{i=1}^{N}[||\boldsymbol{h}_{i}^{a}-\boldsymbol{h}_{i}^{p}||_{2}-||\boldsymbol{h}_{i}^{a}-\boldsymbol{h}_{i}^{n}||_{2}+\alpha]_{+},$
$\displaystyle\mathcal{L}_{total}=\mathcal{L}_{xent}+\lambda\mathcal{L}_{triplet},$

where $\boldsymbol{h}_{i}^{a}$, $\boldsymbol{h}_{i}^{p}$ and
$\boldsymbol{h}_{i}^{n}$ are embeddings of the anchor sample, the positive
sample and the negative sample in the mini-batch, $\alpha$ is a pre-defined
distance margin, and $\lambda$ is the trade-off between two loss terms.

Figure 5: Connector model. Input tracklets are first sent to a pre-trained CNN
for feature extraction. A multi-head self-attention based encoder is employed
with the combination of cross-entropy loss and contrastive loss for tracklet
embedding.

For the architecture of Connector, we stack 6 encoding layers. 4-head self-
attention is employed in each encoding layer. We set $D=512$ as the
intermediate channel dimension.

###  III-C Tracking

In the inference stage, each of the initial tracklets is first sent to the
Splitter model. Based on the predicted ID-switch position mask
$\boldsymbol{\hat{m}}$, local maximum peaks are picked and the peak values are
compared with a pre-defined splitting threshold $\delta_{s}$. The positions
with peak values greater than $\delta_{s}$ are treated as splitting positions.
Then tracklets are split at the predicted splitting positions.

To group tracklets into tracks with the trained Connector, a tracklet graph
$\mathcal{G}(V,E)$ is first built based on the split tracklets, where $V$ and
$E$ are the vertex set and edge set, respectively. Specifically, each tracklet
is treated as a vertex in set $V$, while $E$ is a finite set in which every
element $e\in E$ represents an edge between a pair of two tracklets $u,w\in V$
that are not far away in the time domain, yet no temporal overlap with each
other, i.e.,

$\min_{t_{u}\in T(u),t_{w}\in T(w)}\lvert
t_{u}-t_{w}\rvert\leq\delta_{t}\text{ and }T_{f}(u)\cap T_{f}(w)=\emptyset,$
(11)

where $T_{f}(u)$ is the set of frame indices of the tracklet $u$. Based on the
built tracklet graph, each tracklet is embedded via the encoder of the
proposed Connector. A pairwise Euclidean distance on each element $e\in E$ is
measured. With a sufficiently good embedding framework, a simple bottom-up
greedy matching algorithm is employed to group tracklets if two tracklets
satisfy

$||\boldsymbol{h}_{i}-\boldsymbol{h}_{j}||_{2}<\delta_{c},$ (12)

where $\delta_{c}$ is a pre-defined connection threshold. The setting of the
hyper-parameters is described in Section IV-C.

The time complexity for Splitter and Connector is as follows. Denote the
number of tracklets as $M$, and the video length as $L$. Since Splitter is
conducted in a temporal window manner, the time complexity in inference is
$O(ML)$. For Connector, the tracklet embedding takes about $O(ML)$, while the
graph clustering with the greedy method takes about $O(M^{2}L)$. As a result,
the complexity of the entire model is roughly $O(M^{2}L)$.

##  IV Experiments

TABLE I: Result on MOT17 testing set. For each pair of comparisons, the first row shows the original state-of-the-art (SOTA) method and the second row shows the corresponding method with the proposed TBooster (short for “tracklet booster”). The number in “()” besides the IDF1 score is the improvement after TBooster applied. Method (MOT17) | IDF1 (%) $\uparrow$ | MOTA (%) $\uparrow$ | MOTP (%) $\uparrow$ | MT (%) $\uparrow$ | ML (%) $\downarrow$ | IDS $\downarrow$ | FRAG $\downarrow$ | FPS $\uparrow$
---|---|---|---|---|---|---|---|---
IOU [63] | 39.4 | 45.5 | 76.9 | 369 | 953 | 5,988 | 7,404 | 1,522.9
TBooster+IOU |  45.1 (+5.7) | 45.8 | 76.8 | 369 | 953 | 4,189 | 7,430 | 7.7
Tracktor_v2 [27] | 55.1 | 56.3 | 78.8 | 498 | 831 | 1,987 | 3,763 | 1.5
TBooster+Tracktor_v2 |  59.2 (+4.1) | 56.4 | 78.9 | 498 | 831 | 1,785 | 3,750 | 1.3
MPNTrack [21] | 61.7 | 58.8 | 78.6 | 679 | 788 | 1,185 | 2,265 | 6.5
TBooster+MPNTrack |  62.3 (+0.6) | 58.9 | 78.7 | 682 | 790 | 1,198 | 2,209 | 4.2
CenterTrack [24] | 59.6 | 61.5 | 78.9 | 621 | 752 | 2,583 | 4,965 | 17.0
TBooster+CenterTrack |  63.3 (+3.7) | 61.5 | 78.8 | 622 | 754 | 2,470 | 5,079 | 6.9
TABLE II: Result on MOT20 testing set. For each pair of comparisons, the first row shows the original state-of-the-art (SOTA) method and the second row shows the corresponding method with the proposed TBooster (short for “tracklet booster”). The number in “()” besides the IDF1 score is the improvement after TBooster applied. Method (MOT20) | IDF1 (%) $\uparrow$ | MOTA (%) $\uparrow$ | MOTP (%) $\uparrow$ | MT (%) $\uparrow$ | ML (%) $\downarrow$ | IDS $\downarrow$ | FRAG $\downarrow$ | FPS $\uparrow$
---|---|---|---|---|---|---|---|---
Tracktor [27] | 52.7 | 52.6 | 79.9 | 365 | 331 | 1,648 | 4,374 | 1.2
TBooster+Tracktor |  53.3 (+0.6) | 52.6 | 79.8 | 365 | 329 | 1,734 | 4,389 | 0.6
UnsupTrack [64] | 50.6 | 53.6 | 80.1 | 376 | 311 | 2,178 | 4,335 | 1.3
TBooster+UnsupTrack |  54.3 (+3.7) | 53.7 | 80.1 | 374 | 313 | 1,771 | 4,322 | 0.6
MOT20_TBC [65] | 50.1 | 54.5 | 77.3 | 415 | 245 | 2,449 | 2,580 | 5.6
TBooster+MOT20_TBC |  54.3 (+4.2) | 54.6 | 77.3 | 416 | 247 | 1,771 | 2,679 | 0.8
GNNMatch [66] | 49.0 | 54.5 | 79.4 | 407 | 317 | 2,038 | 2,456 | 0.1
TBooster+GNNMatch |  53.4 (+4.4) | 54.6 | 79.4 | 407 | 317 | 1.674 | 2,455 | 0.1

###  IV-A Datasets

To evaluate the proposed tracklet booster, we conduct experiments on two
widely used pedestrian tracking benchmark datasets, i.e., MOT17 [32] and MOT20
[67]. The details of the datasets are described as follows.

#### MOT17 dataset

MOT17 is a widely used pedestrian tracking benchmark dataset. In total, there
are $7$ training video sequences and $7$ testing video sequences. The
benchmark also provides public deformable part models (DPM) [68], Faster-RCNN
[69] and scale dependent pooling (SDP) [70] detections for both training and
testing data. The number of tracks is 1,331 and the number of total frames is
11,235.

#### MOT20 dataset

MOT20 is a recently released pedestrian tracking dataset for crowded scenarios
with plenty of occlusions. The average density is over 150. In total, there
are $4$ training video sequences and $4$ testing video sequences. The dataset
also provides public Faster R-CNN detections with ResNet101 [71] as the
backbone. The number of trajectories in the training data is 3,833 and the
total number of frames is 13,410.

###  IV-B Training Details

The training details for the proposed tracklet booster are described as
follows.

#### Splitter

We apply the simple and fast IOU tracker [63] to the randomly jittered and
horizontally flipped ground truth bounding boxes with variant overlapping
thresholds to generate tracklets on the fly. Each tracklet may contain
multiple ground truth object IDs since there are association errors. We store
the ID-switch positions in the mask $\boldsymbol{m}^{*}$, which is treated as
the ground truth splitting positions. The temporal window $T$ is set to be 65
frames. For tracklets that last shorter than 65 frames, padding with the
starting and ending frames is used. A baseline re-id method [72] is adopted
for extracting the input appearance feature with dimension 2048. 4 Normalized
bounding box parameters are used as motion features. Thus, the input tracklet
has a size of $2052\times 65$. We use Adam optimizer with an initial learning
rate of 0.001. Cosine annealing learning rate scheduler is adopted with a
maximum iteration of 60,000.

#### Connector

For training Connector, we follow the similar data preparation as Splitter.
Slightly different from the tracklets generated for training Splitter, we
ensure that each tracklet only contains one object ID. Adam optimizer with
initial learning rate 0.0001 is adopted. We use cosine annealing learning rate
scheduler with maximum iteration 120,000. For hyper-parameters in the loss
function, we set $\lambda=0.5$ and $\alpha=0.2$ in Eq. (10).

###  IV-C Inference Details

In the inference stage, we use tracklets generated from existing trackers as
input. We process the tracklets with the temporal sliding window procedure
with 50% overlapping frames. Splitter is firstly conducted to predict the
potential splitting positions. As defined in Section III-C, we set the
splitting threshold $\delta_{s}=0.5$ for all experiments. Connector is also
conducted in the sliding window manner. We set $\delta_{t}=64$ and
$\delta_{c}=0.9$ for all following experiments. Currently, the proposed method
is conducted offline. Since it is processed in a temporal sliding window
manner, it can be modified to an online method, which will be implemented in
future work.

###  IV-D Evaluation Metrics

We employ ID F1 measure (IDF1) [33], multiple object tracking accuracy (MOTA),
mostly tracked targets (MT), mostly lost targets (ML), fragments (FM) and
identity switches (IDS) [32] as the evaluation metrics of the tracking
performance, which are widely used in MOT.

###  IV-E Main Results

We evaluate the performance of the proposed tracklet booster on MOT17 and
MOT20 with several state-of-the-art (SOTA) methods.

#### MOT17

We test four SOTA methods, i.e., IOU [63], Tracktor [27], MPNTrack [21] and
CenterTrack [24] on MOT17, combined with the proposed tracklet booster method.
Specifically, the IOU tracker uses intersection over union between bounding
boxes across frames as the main clue for data association; Tracktor exploits
the bounding box regression of an object detector to predict the position of
an object in the next frame, given sequential input frames; MPNTrack exploits
the classical network flow formulation of MOT to define a fully differentiable
framework based on message passing networks; while CenterTrack applies
detection to a pair of frames and associate the objects to the previous frame.
The results are reported in Table I. For each pair of comparisons, the
original method is shown in the first row, while the method with the proposed
TBooster (short for “tracklet booster”) is shown in the second row. As
expected, there are significant improvements on the IDF1 score, ranging from
+0.6% to +5.7%. Since we do not tackle detection algorithms, the MOTA metrics
roughly remain the same with TBooster added.

#### MOT20

We also test four SOTA methods, i.e., Tracktor [27], UnsupTrack [64],
MOT20_TBC [65] and GCNNMatch [66] on MOT20, combined with the proposed
tracklet booster method. Specifically, Tracktor is the same tracker as used in
MOT17, UnsupTrack trains a ReID network to predict the generated labels using
cross-entropy loss; MOT20_TBC jointly models detection, counting, and tracking
of multiple targets as a network flow program, which simultaneously finds the
global optimal detections and trajectories of multiple targets over the whole
video; GCNNMatch uses graph convolutional neural network based feature
extraction and end-to-end feature matching for object association. The results
are reported in Table II. Similarly, there are also large improvements on the
IDF1 compared with the original methods. This demonstrates the effectiveness
of the proposed method on the association task in MOT.

###  IV-F Qualitative Results

To better visualize the improvement with TBooster, we show some qualitative
comparison results between CenterTrack and TBooster in Figure 6. The frames
are sampled from the sequence MOT17-01. Each color of the bounding box
represents a distinct predicted object ID. The first row shows the result from
CenterTrack and the second row is from TBooster. As the result from
CenterTrack, the person with the pointed arrow changes ID after it reappears
from occlusion at frame 160. Thanks to Splitter and Connector modules, the
association error is fixed in TBooster, as shown in the second row of the
figure.

Figure 6: Qualitative comparison results between CenterTrack and TBooster. The frames are sampled from the sequence MOT17-01. Each color of the bounding box represents a distinct predicted object ID. The first row shows the result from CenterTrack and the second row is from TBooster. As the result from CenterTrack, the person with the pointed arrow changes ID after it reappears from occlusion at frame 160, while the association error is fixed in TBooster. TABLE III: Effectiveness of Splitter and Connector. Method | IDF1 (%) | MOTA (%)
---|---|---
Original | 48.5 | 55.1
w/. Connector | 52.2 (+3.7) | 55.4
w/. Splitter | 47.1 (-1.4) | 54.4
w/. Splitter & Connector |  54.6 (+6.1) | 55.2
TABLE IV: Effect of different combinations of thresholds for Splitter and Connector. Method | IDF1 (%) | MOTA (%)
---|---|---
Original | 48.5 | 55.1
$\delta_{s}=0.5$, $\delta_{c}=0.5$ | 52.9 (+4.4) | 54.9
$\delta_{s}=0.5$, $\delta_{c}=0.7$ | 53.8 (+5.3) | 55.1
$\delta_{s}=0.5$, $\delta_{c}=0.9$ |  54.6 (+6.1) | 55.2
$\delta_{s}=0.5$, $\delta_{c}=1.1$ | 53.2 (+4.7) | 55.2
$\delta_{s}=0.7$, $\delta_{c}=0.5$ | 51.6 (+3.1) | 55.2
$\delta_{s}=0.7$, $\delta_{c}=0.7$ | 52.3 (+3.8) | 55.3
$\delta_{s}=0.7$, $\delta_{c}=0.9$ | 52.2 (+3.7) | 55.3
$\delta_{s}=0.7$, $\delta_{c}=1.1$ | 52.1 (+3.6) | 55.3
$\delta_{s}=0.9$, $\delta_{c}=0.5$ | 51.8 (+3.3) | 55.3
$\delta_{s}=0.9$, $\delta_{c}=0.7$ | 52.4 (+3.9) | 55.4
$\delta_{s}=0.9$, $\delta_{c}=0.9$ | 52.2 (+3.7) | 55.4
$\delta_{s}=0.9$, $\delta_{c}=1.1$ | 52.1 (+3.6) | 55.4

###  IV-G Ablation Study

For the ablation study, we use the MOT17-09 sequence as the validation set and
the rest sequences as the training set. We adopt the IOU tracker as the
baseline original tracking method.

#### Study of the Effectiveness of the Splitter and Connector

To test the effectiveness of Splitter and Connector modules, we compare three
different settings, i.e., combining Connector without Splitter, combining
Splitter without Connector, and combining both Splitter and Connector. The
comparison results are shown in Table III. As shown in the second row of the
table, with a standalone Connector module, the IDF1 is boosted by 3.7%.
However, as shown in the third row, the IDF1 is decreased by 1.4% with the
standalone Splitter module. This means some tracks are divided into pieces,
which negatively affects the IDF1 score. This is a common phenomenon,
especially when occlusion happens. There is a high chance for tracklets to get
split since the appearance feature changes rapidly. As shown in the last row
of the table, with the combination of both Splitter and Connector, IDF1 is
boosted by 6.1%, which is a further boost of 2.4% compared with standalone
Connector module in the second row. This is because after the Splitter module,
tracklets can get much purer IDs, which further helps Connector to increase
the grouping accuracy. This demonstrates the effectiveness of both Splitter
and Connector modules.

#### Effect of Different Inference Thresholds

We also conduct experiments related to thresholds $\delta_{s}$ and
$\delta_{c}$ for Splitter and Connector in the inference stage, respectively.
We vary $\delta_{s}$ from 0.5 to 0.9 and $\delta_{c}$ from 0.5 to 1.1. We
report the results in Table IV. From the results, there is an over 3.0%
consistent improvement on the IDF1 score against the original tracking
performance. This demonstrates the robustness of both Splitter and Connector
modules.

#### Effect of Adaptive Smoothing Strategy

To validate the effectiveness of the adaptive smoothing strategy in Splitter,
we compare with the baseline method, where we use the ground truth splitting
position $\boldsymbol{m}^{*}$ to guide the prediction $\boldsymbol{\hat{m}}$
directly using mean squared error without adaptive Gaussian smoothing
strategy, i.e., the loss is set as
$\mathcal{L}_{s}=||\boldsymbol{\hat{m}}-\boldsymbol{m}^{*}||^{2}$. In the
evaluation, for both the baseline method and the proposed method, we select
the local peaks from the predicted mask $\boldsymbol{\hat{m}}$ as the detected
splitting positions and use corresponding peak values as the predicted
confidences. Average precision (AP) is adopted as the evaluation metric for
measure the splitting performance. We show the results in Table V. Compared
with the baseline method, there is a 9.4% improvement on AP for the proposed
approach, which shows the effectiveness of the adaptive Gaussian smoothing
strategy.

#### Effect of Multi-Head Self-Attention

To illustrate the influence of the multi-head self-attention mechanism, we
conduct experiments with a variant number of attention heads in Connector.
Specifically, we train Connector with four settings, i.e., with 1, 2, 4 and 8
heads, respectively. We assign $512/k$ channels to each head to ensure the
total number of channels is fixed for all settings. We adopt the same training
scheduler and keep other parts unchanged. The results are shown in Table VI.
The best result is achieved when 4-head attention is employed and no further
improvement with more attention heads used. Typically, more heads have the
capability to deal with more complex situations. Meanwhile, the dimension of
each head is reduced when we add more heads if the channel number is fixed. A
trade-off should be made for both of the effects. Thus, the result also
conforms to our expectations.

TABLE V: Comparison between adaptive smoothing and the baseline method in Splitter. Method | Baseline | Adaptive Smoothing
---|---|---
Average Precision (%) | 49.0 | 58.4
TABLE VI: Effect of varying number of heads in the self-attention. #Heads | IDF1 (%) | MOTA (%)
---|---|---
1 | 53.5 | 55.1
2 | 53.9 | 55.2
4 | 54.6 | 55.2
8 | 54.4 | 55.2

##  V Conclusion

In this paper, we propose a simple yet effective tracklet boosting approach,
that can be easily combined with the existing trackers and boost the
association performance. The tracklet booster has two main modules, i.e.,
Splitter and Connector. Splitter estimates the ID-switch positions and splits
tracklets into small parts, while Connector merges multiple tracklets into
clusters if they are from the same object. To stabilize the training of
Splitter, a novel adaptive Gaussian smoothing strategy is proposed. To learn
the discriminative tracklet embeddings, a multi-head self-attention mechanism
is employed in Connector. We validate the tracklet booster on two widely used
benchmark datasets, i.e., MOT17 and MOT20, and achieve significant improvement
against several SOTA methods. Moreover, we also conduct sufficient experiments
on several aspects of tracklet booster in the ablation study, which further
proves the effectiveness of each module in the proposed method. Currently, we
are still working on combining the graph neural networks with multi-head self-
attention encoder for tracklet embeddings. This would be our potential
direction for future work.

## References

  * [1] Z. Tang, G. Wang, H. Xiao, A. Zheng, and J.-N. Hwang, “Single-camera and inter-camera vehicle tracking and 3d speed estimation based on fusion of visual and semantic features,” in _CVPR Workshop (CVPRW) on the AI City Challenge_ , 2018.
  * [2] Z. Tang, M. Naphade, M.-Y. Liu, X. Yang, S. Birchfield, S. Wang, R. Kumar, D. Anastasiu, and J.-N. Hwang, “Cityflow: A city-scale benchmark for multi-target multi-camera vehicle tracking and re-identification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 8797–8806.
  * [3] G. Wang, X. Yuan, A. Zhang, H.-M. Hsu, and J.-N. Hwang, “Anomaly candidate identification and starting time estimation of vehicles from traffic videos,” in _AI City Challenge Workshop, IEEE/CVF Computer Vision and Pattern Recognition (CVPR) Conference, Long Beach, California_ , 2019.
  * [4] H.-M. Hsu, T.-W. Huang, G. Wang, J. Cai, Z. Lei, and J.-N. Hwang, “Multi-camera tracking of vehicles based on deep features re-id and trajectory-based camera link models,” in _AI City Challenge Workshop, IEEE/CVF Computer Vision and Pattern Recognition (CVPR) Conference, Long Beach, California_ , 2019.
  * [5] R. Gu, G. Wang, and J.-N. Hwang, “Efficient multi-person hierarchical 3d pose estimation for autonomous driving,” in _2019 IEEE Conference on Multimedia Information Processing and Retrieval (MIPR)_. IEEE, 2019, pp. 163–168.
  * [6] ——, “Exploring severe occlusion: Multi-person 3d pose estimation with gated convolution,” _arXiv preprint arXiv:2011.00184_ , 2020.
  * [7] R. Gu, G. Wang, Z. Jiang, and J.-N. Hwang, “Multi-person hierarchical 3d pose estimation in natural videos,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 30, no. 11, pp. 4245–4257, 2019.
  * [8] B. Jagadeesh and C. M. Patil, “Human motion tracking for human behavior analysis using gaussian mixture model and kalman filtering,” _International Journal of Pure and Applied Mathematics_ , vol. 118, no. 18, pp. 2637–2644, 2018.
  * [9] A. Jalal, M. Mahmood, and A. S. Hasan, “Multi-features descriptors for human activity tracking and recognition in indoor-outdoor environments,” in _2019 16th International Bhurban Conference on Applied Sciences and Technology (IBCAST)_. IEEE, 2019, pp. 371–376.
  * [10] A. Kim, A. Ošep, and L. Leal-Taixé, “Eagermot: Real-time 3d multi-object tracking and segmentation via sensor fusion.”
  * [11] M. Chaabane, P. Zhang, J. R. Beveridge, and S. O’Hara, “Deft: Detection embeddings for tracking,” _arXiv preprint arXiv:2102.02267_ , 2021.
  * [12] H.-N. Hu, Q.-Z. Cai, D. Wang, J. Lin, M. Sun, P. Krahenbuhl, T. Darrell, and F. Yu, “Joint monocular 3d vehicle detection and tracking,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 5390–5399.
  * [13] G. Wang, J.-N. Hwang, K. Williams, and G. Cutter, “Closed-loop tracking-by-detection for rov-based multiple fish tracking,” in _Computer Vision for Analysis of Underwater Imagery (CVAUI), 2016 ICPR 2nd Workshop on_. IEEE, 2016, pp. 7–12.
  * [14] M.-C. Chuang, J.-N. Hwang, J.-H. Ye, S.-C. Huang, and K. Williams, “Underwater fish tracking for moving cameras based on deformable multiple kernels,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 47, no. 9, pp. 2467–2477, 2016.
  * [15] M. Dawkins, L. Sherrill, K. Fieldhouse, A. Hoogs, B. Richards, D. Zhang, L. Prasad, K. Williams, N. Lauffenburger, and G. Wang, “An open-source platform for underwater image and video analytics,” in _2017 IEEE Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2017, pp. 898–906.
  * [16] S. Tang, M. Andriluka, B. Andres, and B. Schiele, “Multiple people tracking by lifted multicut and person reidentification,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 3539–3548.
  * [17] A. Milan, K. Schindler, and S. Roth, “Multi-target tracking by discrete-continuous energy minimization,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 38, no. 10, pp. 2054–2068, 2016.
  * [18] M. Keuper, S. Tang, Y. Zhongjie, B. Andres, T. Brox, and B. Schiele, “A multi-cut formulation for joint segmentation and tracking of multiple objects,” _arXiv preprint arXiv:1607.06317_ , 2016.
  * [19] R. Kumar, G. Charpiat, and M. Thonnat, “Multiple object tracking by efficient graph partitioning,” in _Asian Conference on Computer Vision_. Springer, 2014, pp. 445–460.
  * [20] Y. Wang, X. Weng, and K. Kitani, “Joint detection and multi-object tracking with graph neural networks,” _arXiv preprint arXiv:2006.13164_ , 2020.
  * [21] G. Brasó and L. Leal-Taixé, “Learning a neural solver for multiple object tracking,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 6247–6257.
  * [22] C. Shan, C. Wei, B. Deng, J. Huang, X.-S. Hua, X. Cheng, and K. Liang, “Fgagt: Flow-guided adaptive graph tracking,” _arXiv preprint arXiv:2010.09015_ , 2020.
  * [23] X. Weng, Y. Wang, Y. Man, and K. M. Kitani, “Gnn3dmot: Graph neural network for 3d multi-object tracking with 2d-3d multi-feature learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 6499–6508.
  * [24] X. Zhou, V. Koltun, and P. Krähenbühl, “Tracking objects as points,” _arXiv preprint arXiv:2004.01177_ , 2020.
  * [25] J. Peng, C. Wang, F. Wan, Y. Wu, Y. Wang, Y. Tai, C. Wang, J. Li, F. Huang, and Y. Fu, “Chained-tracker: Chaining paired attentive regression results for end-to-end joint multiple-object detection and tracking,” in _European Conference on Computer Vision_. Springer, 2020, pp. 145–161.
  * [26] B. Pang, Y. Li, Y. Zhang, M. Li, and C. Lu, “Tubetk: Adopting tubes to track multi-object in a one-step training model,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 6308–6318.
  * [27] P. Bergmann, T. Meinhardt, and L. Leal-Taixé, “Tracking without bells and whistles,” in _The IEEE International Conference on Computer Vision (ICCV)_ , October 2019.
  * [28] Z. Wang, L. Zheng, Y. Liu, and S. Wang, “Towards real-time multi-object tracking,” _arXiv preprint arXiv:1909.12605_ , 2019.
  * [29] D. Y. Kim and M. Jeon, “Data fusion of radar and image measurements for multi-object tracking via kalman filtering,” _Information Sciences_ , vol. 278, pp. 641–652, 2014.
  * [30] A. Milan, S. H. Rezatofighi, A. R. Dick, I. D. Reid, and K. Schindler, “Online multi-target tracking using recurrent neural networks.” in _AAAI_ , vol. 2, 2017, p. 4.
  * [31] Y. Lu, C. Lu, and C.-K. Tang, “Online video object detection using association lstm,” in _Proceedings of the IEEE International Conference on Computer Vision, Venice, Italy_ , 2017, pp. 22–29.
  * [32] A. Milan, L. Leal-Taixé, I. Reid, S. Roth, and K. Schindler, “Mot16: A benchmark for multi-object tracking,” _arXiv preprint arXiv:1603.00831_ , 2016.
  * [33] E. Ristani, F. Solera, R. Zou, R. Cucchiara, and C. Tomasi, “Performance measures and a data set for multi-target, multi-camera tracking,” in _European Conference on Computer Vision_. Springer, 2016, pp. 17–35.
  * [34] J. Luiten, A. Osep, P. Dendorfer, P. Torr, A. Geiger, L. Leal-Taixé, and B. Leibe, “Hota: A higher order metric for evaluating multi-object tracking,” _International Journal of Computer Vision_ , pp. 1–31, 2020.
  * [35] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” _arXiv preprint arXiv:1706.03762_ , 2017.
  * [36] W. Choi, “Near-online multi-target tracking with aggregated local flow descriptor,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 3029–3037.
  * [37] S. Tang, B. Andres, M. Andriluka, and B. Schiele, “Subgraph decomposition for multi-target tracking,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 5033–5041.
  * [38] L. Wen, W. Li, J. Yan, Z. Lei, D. Yi, and S. Z. Li, “Multiple target tracking based on undirected hierarchical relation hypergraph,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2014, pp. 1282–1289.
  * [39] G. Wang, Y. Wang, H. Zhang, R. Gu, and J.-N. Hwang, “Exploit the connectivity: Multi-object tracking with trackletnet,” in _Proceedings of the 27th ACM International Conference on Multimedia_ , 2019, pp. 482–490.
  * [40] S. Wang and C. C. Fowlkes, “Learning optimal parameters for multi-target tracking with contextual interactions,” _International journal of computer vision_ , vol. 122, no. 3, pp. 484–501, 2017.
  * [41] P. Lenz, A. Geiger, and R. Urtasun, “Followme: Efficient online min-cost flow tracking with bounded memory and computation,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2015, pp. 4364–4372.
  * [42] A. Milan, S. Roth, and K. Schindler, “Continuous energy minimization for multitarget tracking,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 36, no. 1, pp. 58–72, 2013.
  * [43] A. Andriyenko, K. Schindler, and S. Roth, “Discrete-continuous optimization for multi-target tracking,” in _2012 IEEE Conference on Computer Vision and Pattern Recognition_. IEEE, 2012, pp. 1926–1933.
  * [44] A. Hornakova, R. Henschel, B. Rosenhahn, and P. Swoboda, “Lifted disjoint paths with application in multiple object tracking,” _arXiv preprint arXiv:2006.14550_ , 2020.
  * [45] Y. Xu, X. Liu, Y. Liu, and S.-C. Zhu, “Multi-view people tracking via hierarchical trajectory composition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 4256–4265.
  * [46] Y. Xu, X. Liu, L. Qin, and S.-C. Zhu, “Cross-view people tracking by scene-centered spatio-temporal parsing.” in _AAAI_ , 2017, pp. 4299–4305.
  * [47] R. Han, W. Feng, J. Zhao, Z. Niu, Y. Zhang, L. Wan, and S. Wang, “Complementary-view multiple human tracking,” in _AAAI Conference on Artificial Intelligence_ , 2020.
  * [48] J. He, Z. Huang, N. Wang, and Z. Zhang, “Learnable graph matching: Incorporating graph partitioning with deep feature learning for multiple object tracking,” _arXiv preprint arXiv:2103.16178_ , 2021.
  * [49] P. Dai, R. Weng, W. Choi, C. Zhang, Z. He, and W. Ding, “Learning a proposal classifier for multiple object tracking,” _arXiv preprint arXiv:2103.07889_ , 2021.
  * [50] M. Guo, E. Chou, D.-A. Huang, S. Song, S. Yeung, and L. Fei-Fei, “Neural graph matching networks for fewshot 3d action recognition,” in _Proceedings of the European conference on computer vision (ECCV)_ , 2018, pp. 653–669.
  * [51] M. Narasimhan, S. Lazebnik, and A. G. Schwing, “Out of the box: Reasoning with graph convolution nets for factual visual question answering,” _arXiv preprint arXiv:1811.00538_ , 2018.
  * [52] J. Gao, T. Zhang, and C. Xu, “Graph convolutional tracking,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4649–4659.
  * [53] J. Pang, L. Qiu, X. Li, H. Chen, Q. Li, T. Darrell, and F. Yu, “Quasi-dense similarity learning for multiple object tracking,” _arXiv preprint arXiv:2006.06664_ , 2020.
  * [54] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [55] N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, “End-to-end object detection with transformers,” in _European Conference on Computer Vision_. Springer, 2020, pp. 213–229.
  * [56] X. Zhu, W. Su, L. Lu, B. Li, X. Wang, and J. Dai, “Deformable detr: Deformable transformers for end-to-end object detection,” _arXiv preprint arXiv:2010.04159_ , 2020.
  * [57] C. Zheng, S. Zhu, M. Mendieta, T. Yang, C. Chen, and Z. Ding, “3d human pose estimation with spatial and temporal transformers,” _arXiv preprint arXiv:2103.10455_ , 2021.
  * [58] H. Chen, Y. Wang, T. Guo, C. Xu, Y. Deng, Z. Liu, S. Ma, C. Xu, C. Xu, and W. Gao, “Pre-trained image processing transformer,” _arXiv preprint arXiv:2012.00364_ , 2020.
  * [59] P. Sun, Y. Jiang, R. Zhang, E. Xie, J. Cao, X. Hu, T. Kong, Z. Yuan, C. Wang, and P. Luo, “Transtrack: Multiple-object tracking with transformer,” _arXiv preprint arXiv:2012.15460_ , 2020.
  * [60] T. Meinhardt, A. Kirillov, L. Leal-Taixe, and C. Feichtenhofer, “Trackformer: Multi-object tracking with transformers,” _arXiv preprint arXiv:2101.02702_ , 2021.
  * [61] P. Chu, J. Wang, Q. You, H. Ling, and Z. Liu, “Spatial-temporal graph transformer for multiple object tracking,” _arXiv preprint arXiv:2104.00194_ , 2021.
  * [62] Z. Zhang, J. Wu, X. Zhang, and C. Zhang, “Multi-target, multi-camera tracking by hierarchical clustering: Recent progress on dukemtmc project,” _arXiv preprint arXiv:1712.09531_ , 2017.
  * [63] E. Bochinski, V. Eiselein, and T. Sikora, “High-speed tracking-by-detection without using image information,” in _International Workshop on Traffic and Street Surveillance for Safety and Security at IEEE AVSS 2017_ , Lecce, Italy, Aug. 2017. [Online]. Available: http://elvera.nue.tu-berlin.de/files/1517Bochinski2017.pdf
  * [64] S. Karthik, A. Prabhu, and V. Gandhi, “Simple unsupervised multi-object tracking,” _arXiv preprint arXiv:2006.02609_ , 2020.
  * [65] W. Ren, X. Wang, J. Tian, Y. Tang, and A. B. Chan, “Tracking-by-counting: Using network flows on crowd density maps for tracking multiple targets,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 1439–1452, 2020.
  * [66] I. Papakis, A. Sarkar, and A. Karpatne, “Gcnnmatch: Graph convolutional neural networks for multi-object tracking via sinkhorn normalization,” _arXiv preprint arXiv:2010.00067_ , 2020.
  * [67] P. Dendorfer, H. Rezatofighi, A. Milan, J. Shi, D. Cremers, I. Reid, S. Roth, K. Schindler, and L. Leal-Taixé, “Mot20: A benchmark for multi object tracking in crowded scenes,” _arXiv preprint arXiv:2003.09003_ , 2020.
  * [68] P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan, “Object detection with discriminatively trained part-based models,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 32, no. 9, pp. 1627–1645, 2010.
  * [69] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” in _Advances in neural information processing systems_ , 2015, pp. 91–99.
  * [70] F. Yang, W. Choi, and Y. Lin, “Exploit all the layers: Fast and accurate cnn object detector with scale dependent pooling and cascaded rejection classifiers,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2129–2137.
  * [71] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [72] H. Luo, Y. Gu, X. Liao, S. Lai, and W. Jiang, “Bag of tricks and a strong baseline for deep person re-identification,” in _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2019.


P. BAUDIŠ, COCOpf Algorithm Portfolios

# COCOpf: An Algorithm Portfolio Framework

Petr Baudiš  Dept. of Cybernetics, Czech Technical University, Technická 2,
166 27 Praha, Czech Republic<EMAIL_ADDRESS>
###### Abstract

Algorithm portfolios represent a strategy of composing multiple heuristic
algorithms, each suited to a different class of problems, within a single
general solver that will choose the best suited algorithm for each input. This
approach recently gained popularity especially for solving combinatoric
problems, but optimization applications are still emerging. The COCO platform
[6] [5] of the BBOB workshop series is the current standard way to measure
performance of continuous black-box optimization algorithms.

As an extension to the COCO platform, we present the Python-based COCOpf
framework that allows composing portfolios of optimization algorithms and
running experiments with different selection strategies. In our framework, we
focus on black-box algorithm portfolio and online adaptive selection. As a
demonstration, we measure the performance of stock SciPy [8] optimization
algorithms and the popular CMA algorithm [4] alone and in a portfolio with two
simple selection strategies. We confirm that even a naive selection strategy
can provide improved performance across problem classes.

###### keywords:

Algorithm portfolio, continuous black-box optimization, hyperheuristics,
software engineering.

##  1 Introduction

The problem of Algorithm Selection is not new [16], but has only recently
gained traction in particular in the field of combinatoric problem solvers.
[9] There are multiple ways to approach the issue, in our work we adopt the
abstraction of algorithm portfolios. [3] The basic idea is that we have a set
of heuristic algorithms at our disposal (each suitable for a different class
of problem instances), and for each problem instance on input, we apply a
selection strategy to pick an algorithm from this portfolio and apply it on
the problem. We can perform the selection once or along a fixed schedule
(offline selection) based on features of the problem instance, or in multiple
rounds first exploring the suitability of portfolio members, then allocating
time to them based on their previous performance. In successive rounds,
algorithms can be either resumed from their previous state or restarted; we
take the approach of resuming them, reserving the restart schedule to be an
internal matter of each algorithm.111That is, sometimes resumption will simply
continue the algorithm to a next iteration, on reaching a local optimum the
algorithm may attempt to escape it and failing that, a complete restart may
occur.

Applying algorithm portfolios on continuous black-box optimization is still a
fresh area of research.222Especially if we do not consider applying related
methods to individual operator selection within genetic algorithms used for
optimization. The main results so far lie either in population methods,
combining a variety of genetic algorithms together, e.g. the AMALGAM-SO
algorithm [17], or in offline methods based chiefly on exploratory landscape
analysis [11].

In our work, we aim to allow the more traditional optimization methods to
enter the mix as we regard the algorithms as black-box, i.e. we completely
avoid modifying their inner working and we simply call them to retrieve a
single result. This allows state-of-art methods to be combined in a single
portfolio easily and offers easy implementation of whatever selection strategy
desired as the existing algorithm modules can be simply reused without
modification. Furthermore, we focus on online adaptive selection that selects
algorithms based on their performance so far and does not require possibly
expensive feature extraction and training.

The currently accepted de-facto standard for benchmarking optimization methods
is the COmparing Continuous Optimisers COCO platform [6] [5] that was
originally developed for the BBOB workshop series. It provides the
infrastructure, glue code for both running experiments and preparing high
quality figures, a set of common reference results and the code for a set of
benchmark functions. Therefore, we chose to add algorithm portfolio support to
this platform. The glue code is available in multiple languages, we extended
the Python implementation. We are in part motivated by the convenient
availability of optimization algorithms distributed along the popular SciPy
library [8].

We have two options when testing algorithm selection methods in practice:
either using only previously published data on preformance of individual
algorithms, or re-running optimization algorithms from scratch under the guide
of a particular selection method. The former approach is certainly an easier
option while benchmarking, nevertheless we opted for the latter model so that
we can also readily apply all code on practical function optimization aside of
mere benchmarking. Apart of that, the available performance data does not
include information about algorithm iterations, listingonly individual
function evaluations. That makes it unclear when is a good time to switch.
Lastly, the re-running model allows migration of intermediate solutions
between algorithms as a simple extension.

In Section 2, we introduce the COCOpf software, explaining its architecture,
general API and a few interesting implementation points. In Section 3, we
establish a reference algorithm portfolio, benchmarking its individual members
and two algorithm selection methods implemented in the framework. We present
the benchmark results in Section 4 and conclude with a results summary and
outline of a few directions of future work in Section 5.

##  2 COCOpf Framework

Our framework has been implemented as a Python module that can be imported by
user applications. The framework provides the means to run the experiment on a
given set of benchmark scenarios, maintains a population of algorithm
instances and provides a complex wrapper to individual algorithms that uses an
existing per-iteration callback mechanism to suspend and resume execution of
the algorithm after a single iteration. Algorithm wrappers for the SciPy
optimization methods and the reference implementation of CMA are available
out-of-the box as well as two example algorithm selection strategies that are
benchmarked below. The framework is publicly available as free software under
the permissible MIT licence at https://github.com/pasky/cocopf.

In design of such a framework, a choice presents itself — to either build a
generic main program which allows an experiment to choose a certain
configuration and plug in custom callbacks, or to prepare a set of ”lego
bricks” that replace common parts of the main program but letting each
experiment provide a separate main program. We opted for the latter; it
reduces encapsulation and requires slightly more repetitive code, but it
allows a much greater degree of flexibility encouraging diverse experiments.

###  2.1 Experiment Wrapper

The Experiment class wraps up the common code that sets up the COCO benchmark,
initializing the logs, sets of dimensions and function instances etc. It also
provides an iterator that in turn returns individual function instances to be
minimized, and a pretty-printing progress report function. After an experiment
is finished, the standard BBOB postprocessing tools may be used to examine and
plot the performance data. An example of usage is shown in Fig. 1.

⬇

e = Experiment(maxfev=10000, shortname="EG50",

comments="Eps-greedy, eps=0.5")

for i in e.finstances():

minimization(i)

e.f.finalizerun()

e.freport(i)

Figure 1: A minimalistic main body of a Python script using the Experiment
class. Function minimization is to be provided by the user.

###  2.2 Minimization Wrappers

All algorithms are executed via the MinimizeMethod class. Its primary purpose
is to produce a callable Python object from a user-provided string name of
algorithm. By default, it calls the scipy.optimize.minimize API with unchanged
method name and wraps it in the scipy.optimize.basinhopping API. However, it
is expected the user will create a subclass adding custom optimizers; a demo
subclass adding the CMA optimization is included.333The custom optimizers may
also legitimately want to use the Basin Hopping algorithm (see Sec. 3.1), but
SciPy allows using custom minimization routines with the basinhopping API only
starting with version 0.14.

We were presented with a software engineering problem of how to suspend,
resume and cancel the algorithms between iterations without requiring any
modification to the algorithm code, while all we have is a callback executed
after each iteration. Our answer is the MinimizeStepping class which creates a
separate thread for each algorithm instance and uses the standard Python Queue
mechanism to pause execution of each thread within the callback code based on
instructions from the main thread. At any time, only a single thread is
running. To cancel execution (when time is up or a solution is found) we pass
a special message through the queue that raises an exception within the
callback, eventually cancelling the whole algorithm and thread orderly. An
“mlog” facility is provided to log function evaluation status at the end of
each algorithm iteration.

###  2.3 Portfolio Population

The Population class maintains a population of algorithms drawn from the
algorithm portfolio; each population member corresponds to a tuple of method,
solution coordinates, current value and number of iterations invested.
Usually, the size of population is static, but dynamically adding new members
is also supported.

In a typical case, the population size is the same as the portfolio size,
meaning that only a single solution is tracked for each algorithm. However, in
principle this may not be the case. In fact, we can also make a population
from solutions all using a single algorithm — this special case corresponds to
the problem of finding an efficient restart or resume schedule for a
particular algorithm.

##  3 Benchmarking Simple Portfolios

To showcase COCOpf, we composed a reference portfolio from readily available
open source Python optimizers and implemented two selection strategies.

###  3.1 Reference Algorithm Portfolio

As a testbed algorithm portfolio, we have chosen the six stock minimizers
provided by SciPy v0.13 [8] that are available for direct use:444Other
minimizers are also available in SciPy, but they are either unsuitable for
black-box minimization or do not provide a callback mechanism to allow pausing
execution between individual iterations.

  * •

Nelder-Mead uses the Simplex algorithm. [12] [19]

  * •

Powell implements a tweaked version of the Powell’s conjugate direction
method. [14]

  * •

CG is a nonlinear conjugate gradient method using the Fletcher-Reeves method.
[13, p. 120–122]

  * •

BFGS uses the quasi-Newton method of Broyden, Fletcher, Goldfarb and Shanno
[13, p.136] with numerically approximated derivations.

  * •

L-BFGS-B is a limited-memory variant of BFGS with box constraints. [1] [20]

  * •

SLSQP implements Sequential Least SQuares Programming [10] with inequalities
as the box constraints.

All of these SciPy minimizers perform local minimization; to achieve global
optimization, we wrap them in the “Basin Hopping” restart strategy [18] (also
provided by SciPy), which is conceptually similar to Simulated Annealing with
a fixed temperature. The strategy performs the hopping step 100 times (the
default) before restarting from scratch. On restart, the starting position is
determined uniformly randomly in the $[-5,5]^{k}$ space.

To improve the portfolio performance on more difficult functions, we also
included the popular CMA algorithm [4] (in the “production“ version of its
official reference Python implementation), i.e. a genetic algorithm that
follows the Covariance Matrix Adaptation evolution strategy.

In accordance with our black-box approach, we kept all the algorithms at their
default settings and did not tune any of their parameters. Where applicable,
we set the box constraints to $[-6,6]^{k}$ bounds.555The optimum is guaranteed
to be in $[-5,5]^{k}$, but some minimizers may behave erraticaly when the
optimum is near to or at the bounds.

Each algorithm provides a callback method that is invoked after a single
iteration of the algorithm; we suspend the algorithm after each callback
invocation.

The reference portfolio is not perfectly balanced and certainly would benefit
from algorithms with more diverse performance. Our motivation for going with
these is that the implementations are free software, trivial to obtain and
therefore representing a very low barrier of entry. Also, a SciPy-based
portfolio gives valuable feedback to SciPy users regarding the best algorithm
to use on a certain function, and provides a gateway to introduce an algorithm
portfolio selection strategy to SciPy itself in the future.

###  3.2 Algorithm Selection Strategies

While the core of our followup work involves researching various algorithm
selection strategies, in the context of presentation of the COCOpf framework,
we decided to demonstrate just the performance of two simple simplest methods
whose source code is also a part of the framework:

  * •

The UNIF strategy performs a number of rounds where in every round, a
uniformly randomly selected algorithm is run for a single iteration.

  * •

The EG50 strategy performs a number of rounds where in every round, an
epsilon-greedy policy with $\varepsilon=0.5$ selects the algorithm to run for
one iteration. That is, the algorithm with the currently best solution is run
with $p=0.5$ and a randomly chosen algorithm is run otherwise.

##  4 Results

Results from experiments according to [5] on the benchmark functions given in
[2, 7] are presented in Figures 2, 3 and 4.666The full results dataset is
available at http://pasky.or.cz/sci/cocopf-scipy. The expected running time
(ERT) used in the figures depends on a given target function value,
$f_{\mathrm{t}}=f_{\mathrm{opt}}+\Delta f$, and is computed over all relevant
trials as the number of function evaluations executed during each trial while
the best function value did not reach $f_{\mathrm{t}}$, summed over all trials
and divided by the number of trials that actually reached $f_{\mathrm{t}}$ [5,
15].

If we review the results in context of choosing a best (black-box function)
SciPy optimizer, we can see that there is no single right choice of a SciPy
optimizer that works on all function instances and computational budgets. We
can observe that Powell generally works best for separable functions while
BFGS and SLSQP are good choices for many functions, especially in high
dimensions. For non-separable functions, CMA sooner or later overtakes the
SciPy optimizers but often with a slow start (which is relevant in case a
function evaluation is very expensive) and is not competitive with the SciPy
optimizers on separable functions.

---

Expected running time divided by dimension versus dimension. Expected running
time ($\mathrm{ERT}$ in number of $f$-evaluations) divided by dimension for
target function value $10^{-8}$ as $\log_{10}$ values versus dimension. Light
symbols give the maximum number of function evaluations from the longest trial
divided by dimension. Horizontal lines give linear scaling, slanted dotted
lines give quadratic scaling. Black stars indicate statistically better result
compared to all other algorithms with $p<0.01$ and Bonferroni correction
number of dimensions (six). Legend: $\circ$:Nelder-Mead,
$\triangledown$:Powell, $\star$:CG, $\Box$:BFGS, $\triangle$:L-BFGS-B,
$\diamondsuit$:SLSQP, $\varhexagon$:CMA, $\pentagon$:UNIF, $\hexagon$:EG50

separable fcts | moderate fcts
---|---

& ill-conditioned fcts multi-modal fcts  weakly structured multi-modal fcts
all functions  Bootstrapped empirical cumulative distribution of the number of
objective function evaluations divided by dimension (FEvals/D) for 50 targets
in $10^{[-8..2]}$ for all functions and subgroups in 5-D. The “best 2009” line
corresponds to the best $\mathrm{ERT}$ observed during BBOB 2009 for each
single target.

& ill-conditioned fcts multi-modal fcts  weakly structured multi-modal fcts
all functions  Bootstrapped empirical cumulative distribution of the number of
objective function evaluations divided by dimension (FEvals/D) for 50 targets
in $10^{[-8..2]}$ for all functions and subgroups in 20-D. The “best 2009”
line corresponds to the best $\mathrm{ERT}$ observed during BBOB 2009 for each
single target.

##  5 Discussion and Conclusion

We described an easy-to-use framework that allows users to plug in and
experiment with custom algorithm selection strategies and then directly move
to use these strategies on practical problems instead of benchmarks. The
framework currently focuses on online black-box algorithm portfolios, being
careful not to require any modification to stock and third-party optimization
routines besides a simple callback mechanism that is commonly provided. The
framework could be easily modified to deal with off-line scenarios too.

Our insights may provide guidance for users of the SciPy optimizers. Regarding
algorithm portfolios, the results show that even a very naive algorithm
selection strategy can be beneficial; while it cannot beat the best algorithm
CMA in high-dimensional cases on average over all functions, it provides a
more consistent performance than CMA, translating to best-of-all performance
in low dimensions.

###  5.1 Future Work

The currently chosen reference portfolio is somewhat ad hoc, chosen in part to
contribute value to the SciPy project, but not optimal for further general
research into algorithm portfolios. In the long run, we hope to transition to
a better balanced portfolio.

A common scheme of online algorithm selection schemes is that a credit is
assigned to an algorithm in each round based on its performance (e.g. relative
improvement, absolute value) and accrued over the rounds (e.g. averaging it or
using an adaptation rule). Credit-based selection is so common that it should
be directly supported by the framework; diverse pluggable strategies would
then enable exploration of various interesting strategy combinations. A work-
in-progress preview implementation is already available.

Actually running the individual algorithms is appropriate for optimizing non-
benchmark functions and useful in the future when solutions may migrate within
the portfolio population. However, a useful feature would be to allow testing
selection strategies based on just the saved “mlog“ data (see Sec. 2.2) from
individual algorithm runs.

## Acknowledgements

Research described in the paper was supervised by Dr. Petr Pošík and supported
by the CTU grant SGS14/194/ OHK3/3T/13 “Automatic adaptation of search
algorithms”.

## References

  * [1] Byrd, R. H., Lu, P., Nocedal, J., and Zhu, C. A limited memory algorithm for bound constrained optimization.  SIAM Journal on Scientific Computing 16, 5 (1995), 1190–1208.
  * [2] Finck, S., Hansen, N., Ros, R., and Auger, A. Real-parameter black-box optimization benchmarking 2009: Presentation of the noiseless functions.  Tech. Rep. 2009/20, Research Center PPE, 2009.  Updated February 2010.
  * [3] Gomes, C. P., and Selman, B. Algorithm portfolios.  Artificial Intelligence 126, 1 (2001), 43–62.
  * [4] Hansen, N. The CMA evolution strategy: a comparing review.  In Towards a new evolutionary computation. Advances on estimation of distribution algorithms, J. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea, Eds. Springer, 2006, pp. 75–102.
  * [5] Hansen, N., Auger, A., Finck, S., and Ros, R. Real-parameter black-box optimization benchmarking 2012: Experimental setup.  Tech. rep., INRIA, 2012.
  * [6] Hansen, N., et al. Comparing continuous optimisers: Coco.  http://coco.gforge.inria.fr/.
  * [7] Hansen, N., Finck, S., Ros, R., and Auger, A. Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions.  Tech. Rep. RR-6829, INRIA, 2009.  Updated February 2010.
  * [8] Jones, E., Oliphant, T., Peterson, P., et al. SciPy: Open source scientific tools for Python, 2001–.
  * [9] Kotthoff, L. Algorithm selection for combinatorial search problems: A survey.  AI Magazine (2014).
  * [10] Kraft, D. A software package for sequential quadratic programming.  DFVLR Obersfaffeuhofen, Germany, 1988.
  * [11] Muñoz, M., Kirley, M., and Halgamuge, S. The algorithm selection problem on the continuous optimization domain.  In Computational Intelligence in Intelligent Data Analysis, C. Moewes and A. Nürnberger, Eds., vol. 445 of Studies in Computational Intelligence. Springer Berlin Heidelberg, 2013, pp. 75–89.
  * [12] Nelder, J. A., and Mead, R. A simplex method for function minimization.  The Computer Journal 7, 4 (1965), 308–313.
  * [13] Nocedal, J., and Wright, S. Numerical optimization.  Springer-Verlag, 2006.
  * [14] Powell, M. J. An efficient method for finding the minimum of a function of several variables without calculating derivatives.  The computer journal 7, 2 (1964), 155–162.
  * [15] Price, K. Differential evolution vs. the functions of the second ICEO.  In Proceedings of the IEEE International Congress on Evolutionary Computation (1997), pp. 153–157.
  * [16] Rice, J. R. The algorithm selection problem.  Advances in Computers 15 (1976), 65–118.
  * [17] Vrugt, J. A., Robinson, B. A., and Hyman, J. M. Self-adaptive multimethod search for global optimization in real-parameter spaces.  IEEE Trans. on Evolutionary Computation 13, 2 (2009), 243–259.
  * [18] Wales, D. J., and Doye, J. P. K. Global optimization by basin-hopping and the lowest energy structures of lennard-jones clusters containing up to 110 atoms.  The Journal of Physical Chemistry A 101, 28 (1997), 5111–5116.
  * [19] Wright, M. H. Direct search methods: Once scorned, now respectable.  Pitman Research Notes in Math. Series (1996), 191–208.
  * [20] Zhu, C., Byrd, R. H., Lu, P., and Nocedal, J. Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization.  ACM Transactions on Mathematical Software (TOMS) 23, 4 (1997), 550–560.

Petr Baudiš has received his Bachelors degree and Masters degree in
Theoretical Computer Science at the Charles University in Prague. His Master
thesis “MCTS with Information Sharing” presented a state-of-art Computer Go
program. Currently, he is a PhD student at the Czech Technical University with
principal research interest in Algorithm Portfolios and applications of Monte
Carlo Tree Search.


# Graph Neural Network as Computationally Efficient Emulator of Ice-sheet and
Sea-level System Model (ISSM)

###### Abstract

The Ice-sheet and Sea-level System Model (ISSM) provides solutions for Stokes
equations relevant to ice sheet dynamics by employing finite element and fine
mesh adaption. However, since its finite element method is compatible only
with Central Processing Units (CPU), the ISSM has limits on further
economizing computational time. Thus, by taking advantage of Graphics
Processing Units (GPUs), we design a graph convolutional network (GCN) as a
fast emulator for ISSM. The GCN is trained and tested using the 20-year
transient ISSM simulations in the Pine Island Glacier (PIG). The GCN
reproduces ice thickness and velocity with a correlation coefficient greater
than 0.998, outperforming the traditional convolutional neural network (CNN).
Additionally, GCN shows 34 times faster computational speed than the CPU-based
ISSM modeling. The GPU-based GCN emulator allows us to predict how the PIG
will change in the future under different melting rate scenarios with high
fidelity and much faster computational time.

Index Terms—  Pine Island Glacier, graph convolutional network (GCN), graphic
processing unit (GPU), Deep learning, Basal melting rate

##  1 Introduction

Recently, as the global climate has been warming, the Antarctic ice sheets
have lost around 2,720 billion tonnes of ice mass since 1992, which
corresponds to an increase in mean sea level of 7.6 mm [1]. In particular, the
Pine Island Glacier (PIG) has shown the most rapid mass loss and speedups,
contributing to more than 20 % of the total sea level rise in Antarctica [2].
Among various environmental factors, melt-driven thinning near the grounding
line and calving events have been blamed for driving such changes in the PIG
[3, 4, 5]. Therefore, in order to predict the future mass changes of the PIG
and its impact on the rise of global sea level, it is necessary to model the
thermodynamic and dynamic reaction of the PIG to external heat sources (e.g.,
ocean warming).

To explain the dynamics of ice sheets, scientists have assumed ice is viscous
and non-Newton fluid governed by the Stokes equation [6]. Based on the Stokes
equation, the flow of large ice sheets can be described by several simplified
approximations: e.g., Shallow Ice Approximation (SIA) [7], Shallow Shelf
Approximation (SSA) [8], Blatter-Pattyn approximation (BP) [9, 10], and a
full-Stokes model (FS) [11]. The Ice-sheet and Sea-level System Model (ISSM)
provides numerical solutions for these four different ice flow models using a
finite element approach [12]. The ISSM has significant advantages in fast and
accurate ice modeling for the following reasons: (1) finite element methods,
(2) fine mesh adaptation, and (3) parallel technologies. The unstructured
meshes and anisotropic mesh refinement allow ISSM to allocate its
computational resources to the fine-resolution area of fast ice and coarse-
resolution areas of stagnant ice. Additionally, state-of-the-art parallel
technologies reduce the running time of the ISSM model dramatically when
implemented in massive computer clusters [12].

Although the parallel technologies of the ISSM allow for saving computational
time, its computational performance is still limited because it is only
available through multi-core central processing units (CPUs). Recently,
graphic processing units (GPUs) have emerged as an attractive alternative
processor to CPUs due to their specialty in parallel processing. GPUs divide a
task into several small tasks and process them parallelly, which allows a
magnificent speed-up compared to serial processing by CPU. Nevertheless,
considering that every finite element has to be solved one at a time in ice
flow modeling, the parallel computation of GPUs cannot be directly used to
solve the governing equations of ice flow. Hence, instead of using GPU to
solve the ice flow equations directly, a GPU-based machine learning model can
be used as a statistical emulator (a.k.a. surrogate model) to accelerate the
computational time on ice sheet modeling [13, 14, 15, 16].

In this study, we develop a new deep-learning emulator of the ISSM by
selecting the PIG as the test site. To take full advantage of the finite
element and mesh adaption of the ISSM, we employ a graph neural network (GNN)
instead of the traditional convolutional neural network (CNN) that has been
used in most previous studies [13, 14, 15]. Although traditional CNNs succeed
in recognizing spatial patterns of Euclidean or grid-like structures (e.g.,
images) by using fixed-size trainable localized filters, CNNs cannot be used
for non-Euclidean or irregular structures where the connections to neighbors
are not fixed [17]. Hence, for irregular structures, including point clouds,
natural languages, molecular structures, and social networks, GNNs have been
more broadly used [17]. Since the meshes of the ISSM model resemble irregular
graph structures, GNN is more appropriate than other deep-learning
architectures in reproducing the ISSM model. In this study, by substituting
the mesh defined in ISSM with a graph structure, we focus on developing and
testing a graph convolutional network (GCN) that imitates the ability of the
ISSM to model ice flow and thickness. Furthermore, by using this fast GCN
emulator, we examine how the ice flow and thickness of the PIG will change by
ocean warming and ice melting.

##  2 Methods

###  2.1 ISSM simulation for the Pine Island Glacier

We simulate the 20-year evolution of ice thickness and ice velocity in the PIG
by following the previous studies of ISSM-based sensitivity experiments [18,
19]. For ice velocity, thickness, surface elevation, and bed topography data,
we use the NASA Making Earth System Data Records for Use in Research
Environments (MEaSUREs) data [20, 21] (Fig.1). SSA [8] is used as an ice flow
model with 10 km of initial mesh sizes ($M_{0}$). The final mesh consists of
2085 elements and 1112 nodes. To check the impact of basal melting rate on ice
thickness and ice velocity, we change annual basal melting rates from 0 to 70
m/year for every 2 m/year. This basal melting rate is only applied for the
floating ice; ground ice is assumed to have zero melting rate. Transient
simulations are run forward for 20 years with time steps of one month, and all
results for 240 months and 36 melting rates are collected.

Fig. 1: (a) Location of the Pine Island Glacier (PIG) in Antarctica; (b) Ice
velocity, (c) surface elevation, and (d) ice thickness of the PIG acquired
from NASA MEaSUREs data.

###  2.2 Graph Convolutional Network (GCN)

The GCN of this study is based on the graph convolutional layer, which is
inspired by a localized first-order approximation of spectral graph
convolutions on graph-structured data [22]. Let the $l$th graph convolutional
layer receives a set of node features
$\textbf{h}^{(l)}=\\{h_{1}^{(l)},h_{2}^{(l)},...,h_{N}^{(l)}\\}$,
$h_{i}^{(l)}\in{R}^{F_{l}}$ as the input and produces a new set of node
features,
$\textbf{h}^{(l+1)}=\\{h_{1}^{(l+1)},h_{2}^{(l+1)},...,h_{N}^{(l+1)}\\}$,
$h_{i}^{(l+1)}\in{R}^{F_{l+1}}$, for the next $l+1$th layer. $N$ is the number
of nodes; $F_{l}$ and $F_{l+1}$ is the number of features in each node at
$l$th layer and $l+1$ layer, respectively. Then, the layer-wise propagation
rule of the graph convolutional layer is defined by the following equation:

$\begin{split}&h_{i}^{(l+1)}=\sigma(\sum_{j\in\mathcal{N}(i)}\frac{e_{ij}}{c_{ij}}\textbf{W}^{(l)}h_{j}^{(l)})\\\
&e_{ij}=\text{exp}(-\frac{1}{\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}})\end{split}$
(1)

where $\mathcal{N}(i)$ is the set of neighbors of node $i$, $c_{ij}$ is the
product of the square root of node degrees (i.e.,
$c_{ij}=\sqrt{|\mathcal{N}(j|)}\sqrt{|\mathcal{N}(i)|}$), $e_{ij}$ is the
scalar weight determined by the spatial distance between node $i$ and node
$j$. The x, y coordinates and node $i$ and node $j$ are denoted by
$(x_{i},y_{i})$ and $(x_{j},y_{j})$, respectively. $\textbf{W}^{(l)}$ is a
layer-specific trainable weight matrix ($\textbf{W}^{(l)}\in{R}^{F_{l+1}\times
F_{l}}$), and $\sigma(\cdot)$ is an activation function; we use the Leaky ReLU
activation function of 0.01 negative slope in this study. The GCN takes four
input features (i.e., x and y coordinates on the Antarctic Polar Stereographic
projection, time, and basal melting rate) and produces three output features
(i.e., x-component and y-component ice velocity and ice thickness). We use
five graph convolutional layers with 128 feature sizes and add a fully
connected layer after the final graph convolutional layer to produce the
outputs (Fig. 2).

Fig. 2: Schematic illustration of the graph convolutional network (GCN)
emulator.

###  2.3 Fully Convolutional Network (FCN)

We also train and test a fully convolutional network (FCN) as a baseline
machine learning model to compare with GCN. FCN, a type of CNN, consists of
only convolutional layers. In this study, we use an FCN with six convolutional
layers; all the graph convolutional layers and fully connected layers in Fig.
2 are replaced with 2-D convolutional layers with a kernel size of 3 and
filter size of 128. The leaky ReLu activation function of 0.01 negative slope
is applied after each convolutional layer. Since the FCN should take regular
grids as the input and output, we interpolate all the irregular mesh
construction of the ISSM simulation into a 1 km grid, and these 1 km grid
datasets are used as the input and output of the FCN. The output of the FCN is
sampled again to the ISSM mesh to be compared with the GCN output.

##  3 Results

###  3.1 Experiment set-up

We collect a total of 8,640 graph structures ($240\text{ months}\times
36\text{ basal melting rates}$) from the ISSM transient simulations. All 8,640
graph structures are divided into train, validation, and test datasets based
on the melting rate values: melting rates of 10, 30, 50, and 70 m/year are
used for validation, melting rates of 0, 20, 40, and 60 m/year are used for
testing, and the remainders are for training. Consequently, the number of
train, validation, and test datasets is 6,720, 960, and 960, respectively. We
use the mean square error (MSE) as the loss function, and the model is
optimized by Adam stochastic gradient descent algorithm with 200 epochs and
0.01 learning rate. All deep learning models are trained on the Python
environment using the Deep Graph Library (DGL) and PyTorch modules. In
measuring the computational time, we record the time to generate the final
results of 20-year ice thickness and velocity for all 36 melting rates after
training. Two computational resources of the same desktop (Lenovo Legion T5
26IOB6) are compared: a CPU (Intel(R) Core(TM) i7-11700F) and a GPU (NVIDIA
RTX A5000).

###  3.2 Fidelity of the graph neural network emulators

The accuracy of GCN and FCN machine learning surrogate models are described in
Table 1. Both GCN and FCN show high correlation coefficients greater than
0.996 with the ISSM results for ice velocity and thickness modeling. However,
GCN generally shows better agreement with the ISSM results than the FCN. The
RMSE of ice velocity from GCN is less than that from FCN by 42.55 m/year, and
the RMSE of ice thickness from GCN is less than FCN by 9.64 m. This result
shows that the graph construction and GCN architecture can represent the mesh
structure of the ISSM better than the FCN (CNN). In other words, the fixed
kernel (window) size of FCN cannot efficiently reproduce different neighboring
impacts by different ice velocity fields. Indeed, as shown in Fig. 3, the
error of FCN concentrates on the fast-ice area in the southern center of the
PIG. Additionally, the ice thickness error of GCN is lower than FCN in this
fast-ice area (Fig. 4).

Fig. 3: Maps of the 20-year-averaged ice velocity for different basal melting rates Fig. 4: Maps of the 20-year-averaged ice thickness for different basal melting rates Table 1: Accuracy of ice velocity and thickness for machine learning emulators. Model | Ice velocity | Ice thickness
---|---|---
RMSE (m/year) | R | RMSE (m) | R
GCN | 55.31 | 0.999 | 42.95 | 0.998
FCN | 97.86 | 0.996 | 52.59 | 0.997

###  3.3 Computational performance of the graph neural network emulators

GCN also shows a better computational performance than FCN (Table 2). When
GPUs are used for machine learning models, GCN shows approximately 33.8 times
faster computation time than ISSM computational time, which is only compatible
with CPUs. On the other hand, FCN shows approximately 12.0 times faster
computation time than ISSM. This result shows that both GCN and FCN based on
GPUs can save significant time in obtaining transient simulation results, but
GCN is more efficient.

Table 2: Computational time (in seconds) for producing final ice sheet modeling results. The percentage in the parentheses represents the percentage ratio to the ISSM simulation time. | Model | Computational time (seconds)
---|---|---
CPU | GPU
Simulation | ISSM | 399.78 | -
Emulator | GCN | 60.37 | 11.83
FCN | 1859.65 | 33.27

###  3.4 Sensitivity to basal melting rate

Finally, by using the GCN and FCN emulators, we examine how ice velocity and
thickness of the PIG are sensitive to changes in basal melting rates. Fig. 5
shows the 20-year variations in the mean ice velocity and thickness modeled by
ISSM, GCN, and FCN under four different melting rates (0, 20, 40, and 60
m/year). In all modeling results, ice velocity and thickness vary dramatically
by different basal melting rates. Interestingly, no significant difference
between GCN and FCN is observed, even though GCN shows better accuracy in ice
velocity and thickness predictions. Under zero melting rate (i.e., no melting
on floating ice), ice velocity remains relatively consistent over 20 years
within 500-550 m/year of speed. However, under positive melting rates, ice
velocity increases with time; the slope becomes steeper with a higher melting
rate. If the melting rate is 60 m/year, the terminal ice velocity in year 20
reaches around 800 m/year, corresponding to almost 200 m/year of speed-up over
20 years. Such a dramatic increase in ice velocity can result in extreme
calving at the ice front and large mass loss. When it comes to ice thickness,
the mean ice thickness increases by 20-30 m over 20 years under zero melting
rate. If the melting rate is 20 m/year, the mean ice thickness remains static
over 20 years. However, if the melting rate exceeds 20 m/year, the mean ice
thickness decreases continuously over 20 years, and this decreasing trend is
accelerated at a higher melting rate. The decrease in mean ice thickness is
expected to reach 50 m under an extremely high melting rate of 60 m/year.
Under this 60 m/year ocean melting scenario, the PIG will lose approximately
1,800 Gt of ice for 20 years, equivalent to 2.57 mm of global sea level rise.

Fig. 5: Changes in mean ice velocity and ice thickness of the PIG under
different melting rates (0, 20, 40, and 60 m/year).

##  4 Conclusion

In this study, we assess the potential of graph convolutional network (GCN) as
a fast and efficient emulator (surrogate model) for the ISSM (Ice-sheet and
Sea-level System Model) numerical model. Compared to the traditional
convolutional neural network (CNN), GCN shows better accuracy and
computational efficiency in reproducing the ISSM modeling based on refined
finite element construction. This GCN emulator is used for detailed
sensitivity analysis about how the ice velocity and thickness in the PIG will
change under different basal melting rate scenarios. The sensitivity analysis
results exhibit that the mass loss and speed-up in the PIG will be
dramatically accelerated under $>$ 20 m/year of melting rates. As a fast and
high-fidelity emulator of the ISSM, GCN can be further used to investigate the
impact of climate change and ocean warming on Greenland and Antarctic ice
sheets.

## References

  * [1] The IMBIE team,  “Mass balance of the antarctic ice sheet from 1992 to 2017,”  Nature, vol. 558, pp. 219–222, 2018.
  * [2] Eric Rignot, Jérémie Mouginot, Bernd Scheuchl, Michiel van den Broeke, Melchior J. van Wessem, and Mathieu Morlighem,  “Four decades of antarctic ice sheet mass balance from 1979–2017,”  Proceedings of the National Academy of Sciences, vol. 116, no. 4, pp. 1095–1103, 2019.
  * [3] Ian Joughin, Daniel Shapero, Ben Smith, Pierre Dutrieux, and Mark Barham,  “Ice-shelf retreat drives recent pine island glacier speedup,”  Science Advances, vol. 7, no. 24, pp. eabg3080, 2021.
  * [4] Ian Joughin, Daniel Shapero, Pierre Dutrieux, and Ben Smith,  “Ocean-induced melt volume directly paces ice loss from pine island glacier,”  Science Advances, vol. 7, no. 43, pp. eabi5738, 2021.
  * [5] Stanley S Jacobs, Adrian Jenkins, Claudia F Giulivi, and Pierre Dutrieux,  “Stronger ocean circulation and increased melting under pine island glacier ice shelf,”  Nature Geoscience, vol. 4, no. 8, pp. 519–523, 2011.
  * [6] J. W. Glen and Max Ferdinand Perutz,  “The creep of polycrystalline ice,”  Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, vol. 228, no. 1175, pp. 519–538, 1955.
  * [7] K. Hutter,  Theoretical Glaciology: Material Science of Ice and the Mechanics of Glaciers and Ice Sheets,  Mathematical Approaches to Geophysics. Springer, 1983.
  * [8] Douglas R. MacAyeal,  “Large-scale ice flow over a viscous basal sediment: Theory and application to ice stream b, antarctica,”  Journal of Geophysical Research: Solid Earth, vol. 94, no. B4, pp. 4071–4087, 1989.
  * [9] Heinz Blatter,  “Velocity and stress fields in grounded glaciers: a simple algorithm for including deviatoric stress gradients,”  Journal of Glaciology, vol. 41, no. 138, pp. 333–344, 1995.
  * [10] Frank Pattyn,  “Numerical modelling of a fast-flowing outlet glacier: experiments with different basal conditions,”  Annals of Glaciology, vol. 23, pp. 237–246, 1996.
  * [11] M. Morlighem, E. Rignot, H. Seroussi, E. Larour, H. Ben Dhia, and D. Aubry,  “Spatial patterns of basal drag inferred using control methods from a full-stokes and simpler models for pine island glacier, west antarctica,”  Geophysical Research Letters, vol. 37, no. 14, 2010.
  * [12] E. Larour, H. Seroussi, M. Morlighem, and E. Rignot,  “Continental scale, high order, high spatial resolution, ice sheet modeling using the ice sheet system model (issm),”  Journal of Geophysical Research: Earth Surface, vol. 117, no. F1, 2012.
  * [13] Guillaume Jouvet, Guillaume Cordonnier, Byungsoo Kim, Martin Lüthi, Andreas Vieli, and Andy Aschwanden,  “Deep learning speeds up ice flow modelling by several orders of magnitude,”  Journal of Glaciology, vol. 68, no. 270, pp. 651–664, 2022.
  * [14] Guillaume Jouvet and Guillaume Cordonnier,  “Ice-flow model emulator based on physics-informed deep learning,”  Journal of Glaciology, p. 1–15, 2023.
  * [15] Guillaume Jouvet,  “Inversion of a stokes glacier flow model emulated by deep learning,”  Journal of Glaciology, vol. 69, no. 273, pp. 13–26, 2023.
  * [16] QiZhi He, Mauro Perego, Amanda A. Howard, George Em Karniadakis, and Panos Stinis,  “A hybrid deep neural operator/finite element method for ice-sheet modeling,”  Journal of Computational Physics, vol. 492, pp. 112428, 2023.
  * [17] Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski,  “Graph convolutional networks: a comprehensive review,”  Computational Social Networks, vol. 6, no. 1, pp. 1–23, 2019.
  * [18] H. Seroussi, M. Morlighem, E. Rignot, J. Mouginot, E. Larour, M. Schodlok, and A. Khazendar,  “Sensitivity of the dynamics of pine island glacier, west antarctica, to climate forcing for the next 50 years,”  The Cryosphere, vol. 8, no. 5, pp. 1699–1710, 2014.
  * [19] E. Larour, J. Schiermeier, E. Rignot, H. Seroussi, M. Morlighem, and J. Paden,  “Sensitivity analysis of pine island glacier ice flow using issm and dakota,”  Journal of Geophysical Research: Earth Surface, vol. 117, no. F2, 2012.
  * [20] M. Morlighem,  “Measures bedmachine antarctica, version 3,” 2022.
  * [21] J. Mouginot, B. Scheuchl, and E. Rignot,  “Measures annual antarctic ice velocity maps, version 1,” 2017.
  * [22] Thomas N. Kipf and Max Welling,  “Semi-supervised classification with graph convolutional networks,” 2017.