# LiteTrack: Layer Pruning with Asynchronous Feature Extraction
for Lightweight and Efficient Visual Tracking

Qingmao Wei1,, Bi Zeng1, Jianqi Liu1*, Li He2, Guotian Zeng1 *Corresponding
author1Q. Wei, B. Zeng, J. Liu, and G. Zeng are with the School of Computer,
Guangdong University of Technology, Guangzhou 510006, China.
<EMAIL_ADDRESS>He is with the Department of Electronic and Electrical
Engineering, Southern University of Science and Technology, Shenzhen 518055,
China.

###### Abstract

The recent advancements in transformer-based visual trackers have led to
significant progress, attributed to their strong modeling capabilities.
However, as performance improves, running latency correspondingly increases,
presenting a challenge for real-time robotics applications, especially on edge
devices with computational constraints. In response to this, we introduce
LiteTrack, an efficient transformer-based tracking model optimized for high-
speed operations across various devices. It achieves a more favorable trade-
off between accuracy and efficiency than the other lightweight trackers. The
main innovations of LiteTrack encompass: 1) asynchronous feature extraction
and interaction between the template and search region for better feature
fushion and cutting redundant computation, and 2) pruning encoder layers from
a heavy tracker to refine the balnace between performance and speed. As an
example, our fastest variant, LiteTrack-B4, achieves 65.2% AO on the GOT-10k
benchmark, surpassing all preceding efficient trackers, while running over 100
_fps_ with ONNX on the Jetson Orin NX edge device. Moreover, our LiteTrack-B9
reaches competitive 72.2% AO on GOT-10k and 82.4% AUC on TrackingNet, and
operates at 171 _fps_ on an NVIDIA 2080Ti GPU. The code and demo materials
will be available at https://github.com/TsingWei/LiteTrack.

##  I Introduction

Visual object tracking is a fundamental task in computer vision, which aims to
track an arbitrary object given its initial state in a video sequence. In
recent years, with the development of deep neural networks [1, 2, 3, 4],
tracking has made significant progress. In particular, the utilization of
transformers [4] has played a pivotal role in the development of several high-
performance trackers [5, 6, 7, 8, 9, 10, 11]. Unfortunately, a majority of
recent research efforts [12, 13, 5] has concentrated solely on achieving high
performance without considering tracking speed.

While these state-of-the-art trackers might deliver real-time performance on
powerful GPUs, their efficiency diminishes on devices with limited
computational resources. For instance, ARTrack [14], considered as a top-tier
tracker, reaches a tracking speed of 37 frames per second (_fps_) on the
NVIDIA RTX 2080Ti GPU but drops to 5 _fps_ on the Nvidia Jetson Orin NX, a
common edge device. This underscores the pressing need for trackers that
effectively strike a balance between performance and speed.

Figure 1:  Performance comparison of LiteTrack against state-of-the-art
trackers on GOT-10k in terms of Average Overlap and RTX 2080Ti Speed.  and
reperesent for non-real-time and real-time trackers respectively, based on
Nvidia Jetson Orin NX speed (see Tab.II). Our LiteTrack () family offers
comparable accuracy to all other trackers, significantly outpacing them in
inference speed. Notably, LiteTrack-B4 achieves over 300 _fps_ on 2080Ti and
100 _fps_ (ONNX) on edge device. Notice that our LiteTrack delivering the best
real-time accuracy trained without extra data, unlike the other efficient
trackers.  Figure 2:  Comparison of the popular architectures for visual
tracking. Our method (c) is able to cache the template features like two-stage
(b) in testing and also enjoy the powerful pretrain technique like one-stage
method (a).  Figure 3:  Visualization of attention map (average attention
value over all template features attending to the search features) of 2nd ,
6th and 8th layer in the twelve-layer enoder of JNTrack [15]. The model
focuses nearly precisely on the target even in the early stage of the encoder.

The one-stage structure has gained popularity in tracking applications [10,
16, 17, 9]. This structure combines feature extraction and fusion as a joint
process as pictured in Fig. 2 (a), leveraging the capabilities of the
transformer network, especially the ViT [18] that has been pre-trained by
mask-image-modeling(MIM) [19, 20]. Conversely, two-stage trackers [6, 5, 21],
operating by sequentially extracting features and then fusing them, benefit
from caching template features during the testing phase, as shown in Fig. 2
(b). However, the two-stage trackers who extract feature first then perform
feature fusion, can cache the template feature during testing, while the one-
stage trackers can not. Even though most of one-stage trackers are running
faster than the two-stage, we can further accelerate the former by the similar
caching technique. Inspired by ViTDet [22], we find that only the last layer
of template feature is sufficient and better for fusion with the search
feature of various earlier layer, which can be cached in the testing like two-
stage trackers. Therefore, this naturally decides our overall design: the
feature extraction of template is performed first and individually, then the
extracted last-layer template features interact with the feature extraction of
the search region, as shown in Fig. 2(c).

Traditional efficient trackers have primarily sought to achieve faster
runtimes by directly incorporating an initially lightweight-designed network
as their backbone. These lightweight networks are designed for efficiency,
which results in relatively mediocre performance in their upstream tasks like
image classification. Consequently, when such networks are utilized in visual
tracking, their performance leaves much to be desired. In contrast, our
approach derive efficient model by scaling down a high-performing heavy
tracker, instead of starting with a lightweight architecture. This strategy is
inspired by our observation, as depicted in Fig.3, that early layers pay
sufficient attention to the target. By pruning network layers and integrating
our novel asynchronous feature extraction technique, we ensure only a marginal
drop in performance even when multiple layers are excised. Consequently,
LiteTrack not only rivals the performance of its heavyweight peers but also
competes in runtime with lightweight models, presenting an optimal trade-off.
Fig.1 reinforces this assertion, showcasing LiteTrack’s commendable
performance on the challenging GOT-10k[23] benchmark, standing shoulder-to-
shoulder with state-of-the-art (SOTA) trackers.

Our contributions are summarized as follows:

  * •

A efficient tracking achitechture which feature extractions of template and
search region are asynchronous is proposed for reducing redundant computation.

  * •

A novel scaling principle of tracking model is introduced by adjusting encoder
layers for trade-off between accuracy and speed.

  * •

Comprehensive evaluations on authoritative generic visual tracking benchmarks
have validated the excellent performance of LiteTrack compared with other SOTA
trackers. Edge device deployment are tested with promising performance,
demonstrating the superior effectiveness of LiteTrack on robotics
applicability.

Figure 4: Overview of the proposed LiteTrack-B6 tracker, consist of 3 layers
in feature extraction (FE) stage and 3 layers in asynchronous interaction (AI)
stage. For simplicity, we omit the position enocding, skip connetion and MLP
in the figure. Two branchs of network for template and search region share the
same weights.

##  II Related Works

###  II-A Visual Tracking with Transformers.

Visual tracking has seen the rise of Siamese-based methods [24, 25, 12, 21,
26, 27, 28, 29, 30] that typically employ dual-backbone networks with shared
parameters. They have been instrumental in the field due to their efficiency
in feature extraction of the template and search region images. Further
advancements introduced transformers [4] into the tracking communaty [5, 7, 6,
31, 32, 33, 34], leveraging them for feature interaction training from
scratch. The emergence of the one-stream framework [9, 17, 16, 10, 35]
showcased improved performance by integrating feature extraction and fusion
within the backbone network, enjoying the powerful mask-image-modeling (MIM)
pretraining method [36, 20, 19]. Despite their effectiveness, these methods,
tailored for powerful GPUs, often falter in speed on edge devices. In
response, our research incorporates the last layer feature of the template
directly into the search region’s feature extraction, provide a simliar cache-
in-testing ability like two-stage tracker while also enjoying the powerful
pretraining.

###  II-B Lightweight Trackers.

Efficiency in tracking is crucial for practical robotics applications,
especially on edge devices. Early methods such as ECO [37] and ATOM [38]
focused on real-time operation but didn’t achieve the accuracy levels of newer
trackers. Recent advancements [39, 40, 41] have employed lightweight-designed
backbones for efficient real-time tracking. However, these solutions still
show a performance gap when compared to SOTA heavyweight trackers [10, 6, 9].
There have been efforts to refine these advanced trackers: OSTrack [10]
considered pruning non-essential features unrelated to the foreground, while
SimTrack [16] suggested removing the last four layers to cut computational
costs. Despite these modifications, there remains a lack of deep exploration
into true real-time lightweight tracking architectures. Our proposed LiteTrack
fills this gap, combining efficiency and performance for effective tracking on
edge devices.

##  III Proposed Method

This section presents the LiteTrack method in detail. First, we briefly
overview our LiteTrack framework. Then, we depict the asynchronous featrue
extraction process, layer pruning of our model, and the head network plus with
the training obejctive.

###  III-A Overview

As shown in Fig. 4, LiteTrack is a combination of one-stage and two-stage
tracking framework consisting of two components: the lightweight transformer
encoder and the head network. The template of target to be tracked is fed into
the lightweight transformer encoder first for feature extraction individually.
Then the image of search region is also fed into the same encoder but only the
first n layers. We call these first n layers as Featrure Extraction Stage
(FE). Next, the extracted template features of last layer together with the
intermediate search features after the featrure extraction stage, are fed as a
concatenated sequence into the remaining encoder layers. We call these final
layers as Asynchronous Interaction Stage (AI). Finally, only the part belongs
to the search of the final sequence are selected and flatten to 2D feature
map, and fed into the head network for the tracking result.

###  III-B Asynchronous Featrure Extraction

The so-called asynchronous means that we extract the template feature first
and then the search feature. The feature extraction is done by the transformer
encoder, in which each layer mainly constists of multi-head attention.
Specifically, for a template image
$\mathbf{Z}\in{\mathbb{R}}^{3\times{H_{z}}\times{W_{z}}}$, the pacth embedding
layer transform the image into sequence of tokens
$\mathbf{Z_{p}}\in{\mathbb{R}}^{C\times{\frac{H_{z}}{16}}\times{\frac{W_{z}}{16}}}$.
In each layer of the transofmer encoder, the main operation is multi-head self
attention:

$\displaystyle{\rm{Attn}_{z}}=$
$\displaystyle{\rm{softmax}}(\frac{\mathbf{Q}_{z}\mathbf{K}_{z}^{\top}}{\sqrt{d_{k}}})\mathbf{V}_{z}.$
(1)

The featrue extraction of template is performed by a serially stacked encoder
layers. For a search image
$\mathbf{X}\in{\mathbb{R}}^{3\times{H_{x}}\times{W_{x}}}$, the same pacth
embedding layer also transform the image into sequence of tokens
$\mathbf{X_{p}}\in{\mathbb{R}}^{C\times{\frac{H_{x}}{16}}\times{\frac{W_{x}}{16}}}$.
In the feature extraction stage, the search tokens only attent to itself in
the multi-head attention operation:

$\displaystyle{\rm{Attn}_{x}}=$
$\displaystyle{\rm{softmax}}(\frac{\mathbf{Q}_{x}\mathbf{K}_{x}^{\top}}{\sqrt{d_{k}}})\mathbf{V}_{x}.$
(2)

In the asynchronous interaction stage, the tokens of extracted template
features of last layer concatenated together with the intermediate search
features after the feature extraction stage are concatenated, as the input of
the encoder layer. Inspired by MixFormer [9], the attention in the layers
within the interaction stage is a little different from the standard self-
attention: we generate queris $\mathbf{Q}$ only by the search features. Thus
the attention process can be written as:

$\displaystyle{\rm{Attn}_{xz}}=$
$\displaystyle{\rm{softmax}}(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d_{k}}})\mathbf{V}$
(3) $\displaystyle=$
$\displaystyle{\rm{softmax}}(\frac{[\mathbf{Q}_{x}][\mathbf{K}_{x}^{\top};\mathbf{K}_{z}^{\top}]}{\sqrt{d_{k}}})\mathbf{[}{V}_{x};{V}_{z}].$

Though the attention computation are different between two stages, the
parameters of the networks are still in the same structure. Therefore the
template branch and search branch of the network can share the weight.

Analysis: Our method works depending on one critical development of recent
trackers: the application of homogeneous structure backbone such as the ViT
[18] encoder. The chanel of the features, or the dimension of the tokens in
context of the transformer, remains unchange during the layers of encoder,
therefore the template features can interact with the search features from any
intermediate encoder layer.

Figure 5:  Comparative architectures of recent one-stage one-stream trackers
versus our proposed method. (a) Symmetric interaction: both template and
search region features engage layer by layer. (b) Template-only updates:
features of the template update without search region interactions. (c) Last-
layer interaction: only the final-layer template feature engages with the
search region.

This introduce our first model scaling principle: adjusting the layers for the
feature extraction stage and the asynchronous stage for the accuracy-speed
trade-off as discussed in Sec. 7. During testing, synchronous and symmetric
feature extraction methods, such as OSTrack [10] shown in Fig.5(a), often
result in redundant computations for the template. Given that the template,
typically the initial frame of a video sequence, remains unchanged, its
feature also remains constant. By caching these template features, we
eliminate unnecessary computations during testing. In contrast to MixFormer,
which caches every layer of template features as depicted in Fig.5(b), our
method conserves memory by only storing the last layer of template features,
as shown in Fig. 5(c).

###  III-C Layer Pruning

Figure 6:  Performance (left) and speed (right) vs. number of pruning layers
on GOT-10k benchmark. The baseline without asynchronous feature extraction is
bulit upon OSTrack [10].

In the pursuit of enhancing object tracking performance, deep neural networks
have grown increasingly complex, often at the expense of computational
efficiency. Layer pruning offers an avenue to mitigate this by systematically
reducing the number of layers in the network. Starting with a 12-layer ViT
encoder, we adopted a top-down pruning strategy, progressively eliminating
layers and assessing performance against a baseline. As illustrated in Fig.6,
the performance dropped with the layers pruned while the speed rise up
significantly. However, when paired with asynchronous feature extraction, the
decreasing of performance by the layer pruning is moderated. For example, our
9-layer variant combined with asynchronous as outperformed its 12-layer
counterpart as shown in Fig.6.

###  III-D Head and Training Objective

We employ the center head [10] for prediction, which consists of three
convolutional branches for center classification, offset regression and size
regression, respectively. The center classification branch outputs a
centerness score map, where each score represents the confidence of the target
center locating at the corresponding position. The prediction of offset
regression branch is for the discretization error of the center. The size
regression branch predicts the height and width of the target. The position
with the highest confidence in the center score map is selected as the target
position and the corresponding regressed coordinates are used to compute a
bounding box as the final prediction.

We apply the weighted focal loss [42] for classification. For localization, we
combine $\ell_{1}$ loss and the generalized GIoU loss [43] as the training
objective. The overall loss function can be formulated as

$\displaystyle\mathcal{L}=\mathcal{L}_{\operatorname{focal}}+\lambda_{G}\mathcal{L}_{\operatorname{GIoU}}+\lambda_{l}\mathcal{L}_{l},$
(4)

where $\lambda_{G}=2$ and $\lambda_{l}=5$ are trade-off weights following [10]
to balance optimization.

##  IV Experiments

###  IV-A Implementation Details

Model | LiteT-B9 | LiteT-B8 | LiteT-B6 | LiteT-B4
---|---|---|---|---
# FE Layers | 6 | 6 | 3 | 2
# AI Layers | 3 | 2 | 3 | 2
_fps_ | 2080Ti (PyTorch) | 171 | 190 | 237 | 315
OrinNX (PyTorch) | 21 | 25 | 31 | 44
OrinNX (ONNX fp16) | 64 | 70 | 82 | 102
MACs(G) | 14.17 | 12.77 | 10.09 | 6.78
Params(M) | 54.92 | 49.60 | 38.97 | 26.18

TABLE I: Details and variants of our LiteTrack model. FE and AI denote for
Feature Extraction and Asynchronous Interaction, respectively.

| Method | Source |  TrackingNet [44] |  |  LaSOT [45] |  |  GOT-10k∗ [23] |  |  Speed (_fps_)
---|---|---|---|---|---|---|---|---|---
| AUC |  PNorm | P |  | AUC |  PNorm | P |  | AO |  SR0.5 |  SR0.75 |  | 2080Ti | OrinNX
Real-time | LiteTrack-B9 | Ours | 82.4 | 87.3 | 80.4 |  | 67.0 | 77.0 | 72.7 |  | 72.2 | 82.3 | 69.3 |  | 171 | 21
LiteTrack-B8 | Ours | 81.4 | 86.4 | 79.4 |  | 66.4 | 76.4 | 71.4 |  | 70.4 | 80.1 | 66.4 |  | 190 | 25
LiteTrack-B6 | Ours | 80.8 | 85.7 | 78.2 |  | 64.6 | 73.9 | 68.9 |  | 68.7 | 78.2 | 64.2 |  | 237 | 31
LiteTrack-B4 | Ours | 79.9 | 84.9 | 76.6 |  | 62.5 | 72.1 | 65.7 |  | 65.2 | 74.7 | 57.7 |  | 315 | 44
HiT-Base111The _fps_ on GPU of HiT [41] is directly from their paper due to limitated access to their code. We consider HiT as a real-time tracker based on their reported results on the AGX Xavier, which has a performance near to our Orin NX. For a hardware comparison, see the benchmarks on https://developer.nvidia.com/embedded/jetson-benchmarks. [41] | ICCV’23 | 80.0 | 84.4 | 77.3 |  | 64.6 | 73.3 | 68.1 |  | 64.0 | 72.1 | 58.1 |  | 175 | -
E.T.Track [46] | WACV’23 | 75.0 | 80.3 | 70.6 |  | 59.1 | - | - |  | - | - | - |  | 67 | 21
FEAR-XS [40] | ECCV’22 | - | - | - |  | 53.5 | - | 54.5 |  | 61.9 | 72.2 | - |  | 182 | 50
HCAT [47] | ECCVW’22 | 76.6 | 82.6 | 72.9 |  | 59.3 | 68.7 | 61.0 |  | 65.1 | 76.5 | 56.7 |  | 235 | 34
LightTrack [39] | CVPR’21 | 72.5 | 77.8 | 69.5 |  | 53.8 | - | 53.7 |  | 61.1 | 71.0 | - |  | 107 | 38
|  HiFT [48, 49] | ICCV’21 | 66.7 | 73.8 | 60.9 |  | 45.1 | 52.7 | 42.1 |  | - | - | - |  | 230 | 50
|  ECO [37] | CVPR’17 | 55.4 | 61.8 | 49.2 |  | 32.4 | 33.8 | 30.1 |  | 39.5 | 40.7 | 17.0 |  | 113 | 22
Non-real-time |  ARTrack-256 [14] | CVPR’23 | _84.2_ | _88.7_ | 83.5 |  | _70.4_ | _79.5_ | _76.6_ |  | _73.5_ | 82.2 | _70.9_ |  | 37 | 6
GRM-256 [35] | CVPR’23 | 84.0 | _88.7_ | 83.3 |  | 69.9 | 79.3 | 75.8 |  | 73.4 | _82.9_ | 70.4 |  | 79 | 10
OSTrack-256 [10] | ECCV’22 | 83.1 | 87.8 | 82.0 |  | 69.1 | 78.7 | 75.2 |  | 71.0 | 80.4 | 68.2 |  | 140 | 18
MixFormer [9] | CVPR’22 | 83.1 | 88.1 | 81.6 |  | 69.2 | 78.7 | 74.7 |  | 70.7 | 80.0 | 67.8 |  | 48 | 12
Sim-B/16 [16] | ECCV’22 | 82.3 | 86.5 | - |  | 69.3 | 78.5 | - |  | 68.6 | 78.9 | 62.4 |  | 131 | 15
STARK-ST50 [6] | ICCV’21 | 81.3 | 86.1 | - |  | 66.6 | - | - |  | 68.0 | 77.7 | 62.3 |  | 61 | 13
TransT [5] | CVPR’21 | 81.4 | 86.7 | 80.3 |  | 64.9 | 73.8 | 69.0 |  | 67.1 | 76.8 | 60.9 |  | 84 | 13
TrDiMP [7] | CVPR’21 | 78.4 | 83.3 | 73.1 |  | 63.9 | - | 61.4 |  | 67.1 | 77.7 | 58.3 |  | 36 | 6
PrDiMP [50] | CVPR’20 | 75.8 | 81.6 | 70.4 |  | 59.8 | 68.8 | 60.8 |  | 63.4 | 73.8 | 54.3 |  | 47 | 12
DiMP [13] | ICCV’19 | 74.0 | 80.1 | 68.7 |  | 56.9 | 65.0 | 56.7 |  | 61.1 | 71.7 | 49.2 |  | 100 | 16
|  SiamRPN++ [26] | CVPR’19 | 73.3 | 80.0 | 69.4 |  | 49.6 | 56.9 | 49.1 |  | 51.7 | 61.6 | 32.5 |  | 83 | 16
|  ATOM [38] | CVPR’19 | 70.3 | 77.1 | 64.8 |  | 51.5 | 57.6 | 50.5 |  | 55.6 | 63.4 | 40.2 |  | 175 | 15

TABLE II: State-of-the-art comparison on TrackingNet [44], LaSOT [45], and
GOT-10k [23] benchmarks. The best three real-time results are shown in red,
blue and green fonts, and the best non-real-time results are shown in
_underline_ font. * denotes results on GOT-10k obtained following the official
one-shot protocol, with gray font indicating training using extra data.

Method |  NFS [51] |  UAV123 [52] |  VOT’21 [53]
---|---|---|---
AUC | AUC | EAO
LiteTrack-B9 | 65.4 | 67.7 | 0.269
LiteTrack-B8 | 64.6 | 67.1 | 0.261
LiteTrack-B6 | 64.4 | 66.2 | 0.254
LiteTrack-B4 | 63.4 | 66.4 | 0.251
HiT-Base [41] | 63.6 | 65.6 | 0.252
HCAT [47] | 63.5 | 62.7 | -
FEAR [40] | 61.4 | - | 0.250
E.T.Track [46] | 59.0 | 62.3 | 0.224
LightTrack [39] | 55.3 | 62.5 | 0.225
HiFT [48] | - | 58.9 | -
ECO [37] | 46.6 | 53.2 | -

TABLE III: Comparison with state-of-the-art real-time trackers on additional
benchmarks. We report the results on the NFS [51] and UAV123 [52] in AUC
score, and the EAO for VOT2021 [53] real-time benchmark.

Model Variants. We use ViT-B [18] pretrained by CAE [20] as our backbone. We
develop four variants of LiteTrack with using different layers of the
transformer, as elaborated in Tab. I. We adopt first 9, 8, 6 and 4 layers of
the 12-layer ViT-B model for LiteTrack-B9, LiteTrack-B8, LiteTrack-B6, and
LiteTrack-B4, respectively. FE layers and AI layers in the table denote for
the layers used in feature extraction stage and asynchronous interaction
stage, respectively. In addition, Tab. I reports model parameters, Multiply-
Accumulate operations (MACs), and inference speed on multiple environments.
The running setups are detailed decribed in Sec IV-B.

Training.  For the GOT-10k [23] benchmark, we only use the training split of
GOT-10k following the one-shot protocols and train the model for 100 epochs.
For the other benchmarks, the training splits of GOT-10k, COCO [54], LaSOT
[45] and TrackingNet [44] are used for training in 300 epochs. For video
datasets, we sample the image pair from a random video sequence. For the image
dataset COCO, we randomly select an image and apply data augmentations to
generate an image pair. Common data augmentations such as scaling,
translation, and jittering are applied on the image pair. The search region
and the template are obtained by expanding the target box by a factor of 4 and
2, respectively. The optimizer is the AdamW optimizer [55], with the weight
decay of 1e-4. The initial learning rate of the encoder and the decoder are
4e-5 and 4e-4, respectively. We reduce the learning rate to 10% in the last
20% epochs. Each GPU holds 64 image-pairs. Training of LiteTrack-B8 takes
about 9 hours for GOT-10k and 24 hours for the other benchmarks on one RTX
3090 GPU, and the lighter model trains faster.

Testing. During inference, the template is initialized in the first frame of a
video sequence. For each subsequent frame, the search region is cropped based
on the target’s bounding box of the previous frame. We adopt Hanning window
penalty to utilize positional prior like scale change and motion smoothness in
tracking, following the common practice [33, 10]. The output scores are simply
element-wise multiplied by the Hanning window with the same size, and we
choose the box with the highest multiplied score as the target box.

###  IV-B State-of-the-art Comparisons

LiteTrack is benchmarked against state-of-the-art trackers, both real-time and
non-real-time, across six tracking datasets. We evaluated the speed of these
trackers on two distinct platforms: an Nvidia GeForce RTX 2080Ti GPU (with an
Intel i5-11400F CPU) and an Nvidia Jetson Orin NX 16GB edge device. For these
tests, we utilized PyTorch 1.12.0 on the former and PyTorch 2.0.0 @ JetPack
5.1 on the latter. Trackers are categorized into real-time and non-real-time
based on their PyTorch speed on the Orin NX device, following the 20 _fps_
real-time setting of VOT [56]. Detailed comparative results are showcased in
Tables II and III. We also report our tracker’s speed accelerated with ONNX
fp16 in Tab. I.

GOT-10k. GOT-10k [23] is a large-scale and challenging dataset that contains
10k training sequences and 180 test sequences which are zero-overlapping in
classes. The official one-shot protocol reuqires the evaluated tracker
training without extra data, which encourages the model designed for
challenging scenes like unseen objects. We report the Average Overlap (AO),
Success Rate over a overlapping rate of 50% (SR0.5) and the same one over 75%
(SR0.75) obtained by submitting the result to the official evaluation server.
As shown in Table II, LiteTrack-B9 achieves the best real-time results of
72.2% AO score, which is also competitive to the best non-real-time tracker
ARTrack-256 [14] (73.5% AO score). Our LiteTrack-B4 surpassing all the real-
time trackers with AO score of 65.2%, even though our trackers are trained
without extra data.

TrackingNet. TrackingNet [44] is a large-scale dataset containing a variety of
situations in natural scenes and multiple categories, and its test set
includes 511 video sequences. We report the Area Under Curve (AUC), Normalized
Precision (PNorm) and Precision (P) obtained by submitting the tracking result
to the official evaluation server. As reported in Table II, LiteTrack series
achieve competitive results compared with the previous real-time trackers.
LiteTrack-B9 gets the best AUC of 82.4%, surpassing the previous best real-
time tracker HiT-Base [41] by 2.4%. Compared to non-real-time tracker ARTrack
[14], LiteTrack-B9 achieves comparable performance to it in AUC (82.4 $vs$.
84.2) while being $4.5\times$ faster on the GPU and $6\times$ faster on the
Jetson edge platform.

LaSOT. LaSOT [45] is a large-scale, long-term dataset containing 1400 video
sequences, with 1120 training videos and 280 test videos. We report the same
matrices as in TrackingNet evaluated by
PyTracking222https://github.com/visionml/pytracking tools. The results on
LaSOT are shown in Table II. LiteTrack-B9 achieves the best real-time results
of 67.0%, 77.0%, and 72.7% in AUC, PNorm, and P, respectively. LiteTrack-B8
and LiteTrack-B6 achieves the second-best and the third-best AUC score.
Compared with the recent efficient tracker HiT-Base [41], LiteTrack-B9
outperform it by 2.4% in AUC.

NFS, UAV123 and VOT2021. On the NFS dataset [51], known for its fast-moving
objects spanning 100 video sequences, our LiteTrack variants B9, B8, and B6
emerge as the top three in real-time performance as highlighted in Table III.
Meanwhile, on the UAV123 dataset [52], which features 123 video clips from
low-altitude UAVs, even our fastest LiteTrack-B4 takes the lead among real-
time trackers with an AUC score of 66.4%, surpassing competitors such as HiT
[41] and HCAT [47] by margins of 0.8% and 3.7%, respectively. Similarly, our
VOT-2021 real-time experiments on the VOT2021 benchmark [53] witnessed
LiteTrack-B9 achieving the highest EAO score of 26.9% among real-time
trackers, as tabulated in Table III.

###  IV-C Ablation Study and Visualization

# | Method | AO | _fps_
---|---|---|---
1 | OSTrack(w/o CE) | 71.0 | 121
2 | Strong baseline(1 + CAE [20] pretrained) | 71.7 | 120
3 | 2 + Last 3 layers pruned | 69.1 | 162
4 | 3 + Asynchronous Feature Extraction | 72.2 | 171

TABLE IV: Comparison of key components for object tracking performance. We use
gray color to denote for our final configuration.

# Total | # FE | # AI | AO | SR0.5 | fps
---|---|---|---|---|---
Layers |  Layers |  Layers
8 | 6 | 2 | 70.3 | 80.4 | 190
5 | 3 | 70.4 | 80.1 | 185
0 | 8 | 68.3 | 77.9 | 173
6 | 4 | 2 | 68.0 | 77.5 | 241
3 | 3 | 68.7 | 78.2 | 237
4 | 3 | 1 | 64.6 | 73.7 | 318
2 | 2 | 65.2 | 75.5 | 315

TABLE V: Performance comparison based on varying ratios of feature extraction
layers to asynchronous interaction layers. We use gray color to denote our
final configuration. Figure 7:  Prediction comparison from UAV123 [52]. We use
green lines to demonstrate the Groud Truth bounding box of the target. Blue
boxes represent our LiteTrack’s predictions, while yellow and red boxes denote
the predictions of trackers HCAT [47] and E.T.Track [46] respectively.

Component-wise Analysis. The significance of our proposed methods is
underscored through a comparative study built upon OSTrack [10]. For setting a
solid baseline, we enhanced OSTrack by substituting its MAE [19] pretrained
weights with those of CAE [20], the outcome of which is enumerated in Tab. IV,
Row 2. Direct layer pruning, as seen in Row 3, led to a marked decline in
performance. However, when integrated with our novel asynchronous feature
extraction (Row 4), not only was the deficit recovered, but the model also
achieved superior accuracy and efficiency, surpassing even the strong
baseline.

Layer Configuration Analysis. We explored various configurations concerning
the ratio of feature extraction (FE) layers to asynchronous interaction (AI)
layers, as depicted in Tab. V. For configurations with 8 total layers, peak
performance was achieved with a majority of the layers dedicated to FE. The
6-layer configuration showed comparable results, especially with an even FE-
to-AI ratio. Notably, in the 4-layer configurations, a balanced 2:2 FE-to-AI
setup still produced respectable results. The data highlights the model’s
adaptability across different layer configurations and offers insights into
achieving an optimal balance between FE and AI layers.

Qualitative Results. To better present the superiority of LiteTrack, we
highlight representative scenes in Fig. 7. In a challenging UAV tracking
scenario under a noisy and jittery UAV camera feed, LiteTrack consistently
maintains its track, outperforming other trackers. Similarly, when tracking a
moving car from a UAV’s perspective, LiteTrack demonstrates pinpoint
precision, ensuring more accurate alignment with the ground truth than
competing methods. These real-world tests underscore LiteTrack’s proficiency
in handling diverse tracking challenges.

##  V Conclusions

In this work, we’ve presented LiteTrack, a pioneering approach to object
tracking tailored for robotics applications and edge devices. By combining
layer pruning with asynchronous feature extraction, we’ve achieved significant
improvements in both accuracy and execution speed across diverse datasets. Our
results underscore LiteTrack’s potential, as it not only outperforms leading
real-time trackers but also addresses the constraints of computational
resources often found in robotics and edge deployments. With its efficient
design, LiteTrack promises to be a valuable basline for real-time robotics
applications.

## References

  * [1] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _NIPS_ , 2012, pp. 1106–1114.
  * [2] K. He, X. Zhang, S. Ren, and J. Sun, “Deep Residual Learning for Image Recognition,” in _CVPR_ , 2016, pp. 770–778.
  * [3] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _CVPR_ , 2015, pp. 1–9.
  * [4] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NIPS_ , 2017, pp. 5998–6008.
  * [5] X. Chen, B. Yan, J. Zhu, D. Wang, X. Yang, and H. Lu, “Transformer Tracking,” in _CVPR_ , 2021, pp. 8126–8135.
  * [6] B. Yan, H. Peng, J. Fu, D. Wang, and H. Lu, “Learning Spatio-Temporal Transformer for Visual Tracking,” in _ICCV_ , 2021, pp. 10 428–10 437.
  * [7] N. Wang, W. Zhou, J. Wang, and H. Li, “Transformer Meets Tracker: Exploiting Temporal Context for Robust Visual Tracking,” in _CVPR_ , 2021, pp. 1571–1580.
  * [8] B. Yu, M. Tang, L. Zheng, G. Zhu, J. Wang, H. Feng, X. Feng, and H. Lu, “High-Performance Discriminative Tracking with Transformers,” in _ICCV_ , 2021, pp. 9836–9845.
  * [9] Y. Cui, C. Jiang, L. Wang, and G. Wu, “Mixformer: End-to-End Tracking with Iterative Mixed Attention,” in _CVPR_ , 2022, pp. 13 598–13 608.
  * [10] B. Ye, H. Chang, B. Ma, S. Shan, and X. Chen, “Joint Feature Learning and Relation Modeling for Tracking: A One-Stream Framework,” in _ECCV_ , 2022, pp. 341–357.
  * [11] X. Chen, H. Peng, D. Wang, H. Lu, and H. Hu, “Seqtrack: Sequence to sequence learning for visual object tracking,” in _CVPR_ , 2023, pp. 14 572–14 581.
  * [12] B. Li, J. Yan, W. Wu, Z. Zhu, and X. Hu, “High Performance Visual Tracking With Siamese Region Proposal Network,” in _CVPR_ , 2018, pp. 8971–8980.
  * [13] G. Bhat, M. Danelljan, L. V. Gool, and R. Timofte, “Learning Discriminative Model Prediction for Tracking,” in _ICCV_ , 2019, pp. 6181–6190.
  * [14] X. Wei, Y. Bai, Y. Zheng, D. Shi, and Y. Gong, “Autoregressive visual tracking,” in _CVPR_ , June 2023, pp. 9697–9706.
  * [15] Q. Wei, B. Zeng, and G. Zeng, “Towards efficient training with negative samples in visual tracking,” _arXiv preprint arXiv:2309.02903_ , 2023.
  * [16] B. Chen, P. Li, L. Bai, L. Qiao, Q. Shen, B. Li, W. Gan, W. Wu, and W. Ouyang, “Backbone is All Your Need: A Simplified Architecture for Visual Object Tracking,” in _ECCV_ , 2022, pp. 375–392.
  * [17] F. Xie, C. Wang, G. Wang, Y. Cao, W. Yang, and W. Zeng, “Correlation-aware deep tracking,” in _CVPR_ , 2022, pp. 8751–8760.
  * [18] 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,” in _ICLR_ , 2021.
  * [19] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick, “Masked autoencoders are scalable vision learners,” in _Proc. of CVPR_ , 2022.
  * [20] X. Chen, M. Ding, X. Wang, Y. Xin, S. Mo, Y. Wang, S. Han, P. Luo, G. Zeng, and J. Wang, “Context autoencoder for self-supervised representation learning,” _International Journal of Computer Vision_ , pp. 1–16, 2023.
  * [21] Q. Wang, L. Zhang, L. Bertinetto, W. Hu, and P. H. S. Torr, “Fast Online Object Tracking and Segmentation: A Unifying Approach,” in _CVPR_ , 2019, pp. 1328–1338.
  * [22] Y. Li, H. Mao, R. Girshick, and K. He, “Exploring plain vision transformer backbones for object detection,” in _European Conference on Computer Vision_. Springer, 2022, pp. 280–296.
  * [23] L. Huang, X. Zhao, and K. Huang, “Got-10k: A Large High-Diversity Benchmark for Generic Object Tracking in the Wild,” _IEEE TPAMI_ , vol. 43, no. 5, pp. 1562–1577, 2021.
  * [24] L. Bertinetto, J. Valmadre, J. F. Henriques, A. Vedaldi, and P. H. S. Torr, “Fully-Convolutional Siamese Networks for Object Tracking,” in _ECCV_ , 2016, pp. 850–865.
  * [25] R. Tao, E. Gavves, and A. W. M. Smeulders, “Siamese Instance Search for Tracking,” in _CVPR_ , 2016, pp. 1420–1429.
  * [26] B. Li, W. Wu, Q. Wang, F. Zhang, J. Xing, and J. Yan, “SiamRPN++: Evolution of Siamese Visual Tracking with Very Deep Networks,” in _CVPR_ , 2019, pp. 4282–4291.
  * [27] Y. Xu, Z. Wang, Z. Li, Y. Yuan, and G. Yu, “SiamFC++: Towards Robust and Accurate Visual Tracking with Target Estimation Guidelines.” in _AAAI_ , 2020, pp. 12 549–12 556.
  * [28] D. Guo, J. Wang, Y. Cui, Z. Wang, and S. Chen, “SiamCAR: Siamese Fully Convolutional Classification and Regression for Visual Tracking,” in _CVPR_ , 2020, pp. 6268–6276.
  * [29] Z. Chen, B. Zhong, G. Li, S. Zhang, and R. Ji, “Siamese Box Adaptive Network for Visual Tracking,” in _CVPR_ , 2020, pp. 6667–6676.
  * [30] Z. Zhang and H. Peng, “Deeper and Wider Siamese Networks for Real-Time Visual Tracking,” in _CVPR_ , 2019, pp. 4591–4600.
  * [31] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin Transformer: Hierarchical Vision Transformer using Shifted Windows,” in _ICCV_ , 2021, pp. 9992–10 002.
  * [32] C. Mayer, M. Danelljan, G. Bhat, M. Paul, D. P. Paudel, F. Yu, and L. Van Gool, “Transforming model prediction for tracking,” in _CVPR_ , 2022, pp. 8731–8740.
  * [33] Z. Song, J. Yu, Y.-P. P. Chen, and W. Yang, “Transformer tracking with cyclic shifting window attention,” in _CVPR_ , 2022, pp. 8791–8800.
  * [34] S. Gao, C. Zhou, C. Ma, X. Wang, and J. Yuan, “AiATrack: Attention in attention for transformer visual tracking,” in _ECCV_ , 2022, pp. 146–164.
  * [35] S. Gao, C. Zhou, and J. Zhang, “Generalized relation modeling for transformer tracking,” in _CVPR_ , 2023, pp. 18 686–18 695.
  * [36] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning Transferable Visual Models From Natural Language Supervision,” in _ICML_ , 2021, pp. 8748–8763.
  * [37] M. Danelljan, G. Bhat, F. S. Khan, and M. Felsberg, “ECO: Efficient Convolution Operators for Tracking,” in _CVPR_ , 2017, pp. 6931–6939.
  * [38] ——, “ATOM: Accurate tracking by overlap maximization,” in _Proc. of CVPR_ , 2019.
  * [39] B. Yan, H. Peng, K. Wu, D. Wang, J. Fu, and H. Lu, “LightTrack: Finding Lightweight Neural Networks for Object Tracking via One-Shot Architecture Search,” in _CVPR_ , 2021, pp. 15 180–15 189.
  * [40] V. Borsuk, R. Vei, O. Kupyn, T. Martyniuk, I. Krashenyi, and J. Matas, “FEAR: Fast, Efficient, Accurate and Robust Visual Tracker,” in _ECCV_ , 2022, pp. 644–663.
  * [41] B. Kang, X. Chen, D. Wang, H. Peng, and H. Lu, “Exploring lightweight hierarchical vision transformers for efficient visual tracking,” in _ICCV_ , 2023.
  * [42] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár, “Focal loss for dense object detection,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 2980–2988.
  * [43] H. Rezatofighi, N. Tsoi, J. Gwak, A. Sadeghian, I. D. Reid, and S. Savarese, “Generalized Intersection Over Union: A Metric and a Loss for Bounding Box Regression,” in _CVPR_ , 2019, pp. 658–666.
  * [44] M. Muller, A. Bibi, S. Giancola, S. Alsubaihi, and B. Ghanem, “TrackingNet: A Large-Scale Dataset and Benchmark for Object Tracking in the Wild,” in _ECCV_ , 2018, pp. 310–327.
  * [45] H. Fan, L. Lin, F. Yang, P. Chu, G. Deng, S. Yu, H. Bai, Y. Xu, C. Liao, and H. Ling, “LaSOT: A High-Quality Benchmark for Large-Scale Single Object Tracking,” in _CVPR_ , 2019, pp. 5374–5383.
  * [46] P. Blatter, M. Kanakis, M. Danelljan, and L. Van Gool, “Efficient Visual Tracking with Exemplar Transformers,” in _WACV_ , 2023, pp. 1571–1581.
  * [47] X. Chen, B. Kang, D. Wang, D. Li, and H. Lu, “Efficient Visual Tracking via Hierarchical Cross-Attention Transformer,” in _ECCVW_ , 2022, pp. 461–477.
  * [48] Z. Cao, C. Fu, J. Ye, B. Li, and Y. Li, “Hift: Hierarchical feature transformer for aerial tracking,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 15 457–15 466.
  * [49] J. Thangavel, T. Kokul, A. Ramanan, and S. Fernando, “Transformers in single object tracking: An experimental survey,” _arXiv preprint arXiv:2302.11867_ , 2023.
  * [50] M. Danelljan, L. V. Gool, and R. Timofte, “Probabilistic Regression for Visual Tracking,” in _CVPR_ , 2020, pp. 7181–7190.
  * [51] H. Kiani Galoogahi, A. Fagg, C. Huang, D. Ramanan, and S. Lucey, “Need for Speed: A Benchmark for Higher Frame Rate Object Tracking,” in _ICCV_ , 2017, pp. 1134–1143.
  * [52] M. Mueller, N. Smith, and B. Ghanem, “A Benchmark and Simulator for UAV Tracking,” in _ECCV_ , 2016, pp. 445–461.
  * [53] M. Kristan, J. Matas, A. Leonardis, M. Felsberg, R. Pflugfelder, J.-K. Kämäräinen, H. J. Chang, M. Danelljan, L. Cehovin, A. Lukežič _et al._ , “The ninth visual object tracking vot2021 challenge results,” in _ICCV_ , 2021, pp. 2711–2738.
  * [54] T.-Y. Lin, M. Maire, S. J. Belongie, L. D. Bourdev, R. B. Girshick, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft COCO: Common Objects in Context,” in _ECCV_ , 2014, pp. 740–755.
  * [55] I. Loshchilov and F. Hutter, “Decoupled Weight Decay Regularization,” in _ICLR_ , 2019.
  * [56] M. Kristan, A. Leonardis, J. Matas, M. Felsberg, R. Pflugfelder, J.-K. Kämäräinen, M. Danelljan, L. Č. Zajc, A. Lukežič, O. Drbohlav _et al._ , “The eighth visual object tracking VOT2020 challenge results,” in _ECCV_ , 2020, pp. 547–601.


# Proposal-free Lidar Panoptic Segmentation with Pillar-level Affinity

Qi Chen
The Johns Hopkins University
<EMAIL_ADDRESS>work done while interning at Motional Sourabh Vora
Motional
<EMAIL_ADDRESS>
###### Abstract

We propose a simple yet effective proposal-free architecture for lidar
panoptic segmentation. We jointly optimize both semantic segmentation and
class-agnostic instance classification in a single network using a pillar-
based bird’s-eye view representation. The instance classification head learns
pairwise affinity between pillars to determine whether the pillars belong to
the same instance or not. We further propose a local clustering algorithm to
propagate instance ids by merging semantic segmentation and affinity
predictions. Our experiments on nuScenes dataset show that our approach
outperforms previous proposal-free methods and is comparable to proposal-based
methods which requires extra annotation from object detection.

##  1 Introduction

Panoptic Segmentation [11] unifies the two tasks of semantic segmentation
(assign a class label to each pixel) and instance segmentation (detect and
segment each object instance). In a similar vein, pointcloud panoptic
segmentation needs to provide the semantic label id for each point and further
assign a unique instance label to points that belong to the same object.

Inspired by image panoptic segmentation literature, lidar panoptic
segmentation algorithms can be categorized into two categories: proposal-based
and proposal-free. While proposal-based methods typically require complicated
and slower object detection heads, proposal-free methods usually adopt a
bottom-up approach and group semantic segmentation outputs efficiently.

EfficientLPS[16] and PolarStream[5] generate proposals and group points using
the bounding box centers as cluster centers. These proposal-based methods have
three issues: 1) the post-processing module needs to resolve conflicts between
different branches, such as the inconsistent class labels of semantic branch
and instance branch prediction; 2) the training and inference is not efficient
because object detection/instance segmentation and semantic segmentation are
coupled tasks and have redundant information; 3) overlapping boxes result in
over-segmentation.

To avoid these conflicts, proposal-free methods start with semantic
segmentation predictions and then generate instance masks through grouping or
clustering. Panoptic-PolarNet[8] uses a class-agnostic instance segmentation
branch to predict the centroid of points coming from same instances and
regresses the offset from each point in those instances to their centroid. The
predicted class-agnostic centroids serve as cluster centers. This centroid-
based approach is challenging, particularly for pointclouds of partially
occluded objects. As shown in Fig. 1, even a miss of a point may result in a
dramatic change in the centroid. Furthermore, since the predicted centroids
are shared and reused by multiple semantic classes, there is a risk of over-
segmentation. And finally the offset estimation sub-task has its own
limitations. It is harder to learn because of its large variance and is not
synergistic to the semantic segmentation task, thereby competing against it in
gradient distribution.

Figure 1: The issue of centroid-based proposal-free lidar panoptic
segmentation approach. Miss of a single observation (blue) by lidar scan can
cause significant change in centroid (red).

(a) Original image from COCO dataset

(b) Panoptic labels for (a)

(c) Lidar points (on BEV) and bounding box annotation for cars from NuScenes
dataset

(d) Panoptic labels for (c).

Figure 2: Long range dependency vs short range dependency for thing classes.
The green arrows show long range dependency on an image and short range
dependency on a lidar based bird’s-eye view representation.

In contrast to unreliable instance centroids, the affinity describing pairwise
semantic relations between pixels is invariant to the change of object
appearances. The affinity matrix is often used in semantic segmentation to
encourage the labeling consistency of local similar pixels. This motivates us
to learn affinities for the instance segmentation task as it will help group
pillars from the same instance and discriminate between different instances.
However, the dimensionality of the resulting affinity matrix will be very
high. Pairwise similarity between all pixels, i.e. pillars in the bird’s-eye
view grid, requires a holistic affinity matrix of size $(H\times
W)\times(H\times W)$ for the grid with spatial size $H\times W$. On images, a
holistic affinity matrix is needed due to long range dependency between
pixels. As shown in Fig. 2(b), objects in images have varying scales and can
be occluded by another instance of the same semantic class so pixels far apart
may share the same instance id. This is however not a problem with the lidar
bird’s-eye view representation. As shown in Fig. 2(d) objects appear in fixed
scales and objects with same semantic class usually do not overlap with each
other. This means that only the pillar-level affinity in a local neighborhood
is needed to group semantic predictions of the same class. We further observe
that if we scan the bird’s-eye view grid from left to right, as the green
arrow in Fig. 2(d), a pillar belonging to a thing class can either be the
start of an instance or share the same instance id as the pillars to its left.
Based on this observation, we narrow our focus on the affinity between a
pillar $pl_{i}$ and another pillar to the left of $pl_{i}$. This allows us to
reduce the affinity associated with $pl_{i}$ from a vector of length $HW$ to a
single value, and therefore reduce the affinity matrix of size $(H\times
W)\times(H\times W)$ into a matrix of size $H\times W$.

In this paper, we propose a panoptic segmentation model consisting of two
heads: a semantic segmentation head and a head which predicts pillar-level
affinities. The affinity head performs pillar-wise binary classification to
predict whether the pillar belongs to the same instance as one of its previous
pillars. We also propose a zig-zag traversal order for all pillars. The
learned affinities and the zig-zag traversal order enable us to propose a
local clustering algorithm to assign unique instance ids to pillars with zero
affinity predictions and propagate the instance ids to the similar pillars.

To summarize, our contributions are three-fold:

  * •

We simplify lidar panoptic segmentation training into purely classification
sub-tasks: a) semantic segmentation and b) pillar-wise affinity prediction
where we reduce the dimensionality of the affinity matrix

  * •

We propose a local clustering algorithm for instance id propagation

  * •

Our approach closes the gap between proposal-based and proposal-free methods
and outperforms previous proposal-free methods

Figure 3: Panoptic network overview. Figure inspired by PointPillars[12].

##  2 Related Works

###  2.1 Image-based Panoptic Segmentation

Since panoptic segmentation is a unified task of semantic segmentation and
instance segmentation, most panoptic segmentation models adopt a detection
followed by semantic segmentation approach, or semantic segmentation followed
by grouping approach. Thus panoptic segmentation methods can be generally
categorized as top-down (proposal-based) methods and bottom-up (proposal-free)
methods. Most proposal-based methods, such as Panoptic FPN[11], start from
instance segmentation, usually with a Mask R-CNN[9] and FPN[13]. The two
branches are coupled with redundant information. The post-processing module
needs to merge the output results of the semantic branch and the instance
branch. Sometimes it needs to resolve conflicts between different branches
such as the inconsistent class labels. UPSNet[19] developed a parameter-free
panoptic head for unified training and inference. A line of transformer-based
works[18, 10] directly generate masks as set prediction, eliminating the need
for merging operators. On the other hand, Axial-DeepLab[18], the state-of-the-
art bottom-up approach that predicts pixel-wise offsets to pre-defined
instance centers, suffers from highly deformable objects or near-by objects
with close centers.

###  2.2 Lidar Panoptic Segmentation

Similar to image-based approaches, lidar panoptic segmentation methods, though
less explored, can also be categorized into proposal-based and proposal-free
methods. Adapted from a 2D panoptic segmentation architecture,
EfficientLPS[16] generates region proposals from encoded features and then
detects the instances in parallel to perform semantic segmentation.
PolarStream[5] does semantic segmentation and object detection simultaneously
and then groups points according to bounding box centers. Proposal-free
methods generally infer semantic segmentation before detecting instances
through either keypoint detection tasks like center point estimation or
through voting/learnable clustering in the range view or bird’s-eye view
domain. In addition to semantic segmentation, Panoptic-PolarNet[8] trains an
instance head that predicts the centroid of the points in each instance and
offsets from each point to the centroid. The proposal-free architecture is
trained without any bounding box annotation.

###  2.3 Affinity Learning for Semantic Segmentation

Several works adopt graphical models with affinity as binary potentials to
refine the outputs of fully supervised semantic segmentation models. RWN[3]
learns pixelwise affinity and semantic segmentation jointly and employs a
convolutional random walk layer to combine both objectives. LS-DeconvNet[7]
leverages affinity to refine object boundaries in upsampling layers. Another
line of works incorporates affinity in a weakly supervised setting. Given only
image-level class annotation, Ahn _et al_. [1] predicts affinities by a deep
neural network and propagates labels to nearby areas which belong to the same
semantic entity.

##  3 Problem Statement

A lidar point cloud sample consists of a set of N points, each point
represented by a vector of point feature $f=(x,y,z,i,t)$, where $(x,y,z)$ is
its location in Cartesian coordinates relative to the sensor, $i$ is the
reflection intensity and $t$ is the timestamp when the LiDAR point is
captured. LiDAR point cloud semantic segmentation task aims to predict a set
of class labels $S=\\{s_{i}\in\\{1,2,...,K\\}\\}_{i=1,...,N}$ for the points.
Panoptic segmentation task extends this problem to requiring different
instance ids assigned to points belonging to countable instances in some
‘thing’ classes, e.g., car, bicycle, and pedestrian. The remaining classes are
‘stuff’ classes, which do not require detailed separation and share the same
label among all points.

(a) Zigzag traversal order for two-dimensional pillars (along a and b axes) on
BEV.

(b) Illustration of instance id propagation from semantic and affinity
prediction. Here shows an example of polar pillars with size $6\times 6$.
Wrap-around effect is considered because $\theta$ is periodic.

Figure 4: Pillar-level affinity Representation.

##### Zig-zag Traversal Order for Pillars

To facilitate our representation of affinity, we first define an order for the
two-dimensional pillars on BEV, as show in Fig. 4(a). We uniquely map pillars
along $a,b$ axes to one-dimensional order. For Cartesian pillars, $a,b$ axes
corresponds to $y,x$ axes respectively ($x,y$ axes are also feasible); for
Polar pillars, $a,b$ axes corresponds to r, $\theta$ axes respectively.

##  4 Approach

As shown in Fig. 3, our approach consists of the following four components:
(1) a small pillar feature encoder that encodes the raw point cloud data to 2D
pillar-based representation; (2) a shared 2D CNN backbone; (3) two heads for
semantic segmentation and affinity classification (4) a local clustering
scheme for instance id propagation.

###  4.1 Preliminary

####  4.1.1 Pillar-Based Point Clouds Representation

There are two alternative pillar partition schemes, cartesian pillars and
polar pillars, based on which coordinate system is chosen. The cartesian
pillars are rectangular-shaped on the bird’s-eye view while the polar pillars
are wedge-shaped. In this paper, we present the results of both pillar
partition schemes.

##### Cartesian Pillar Partition

The point cloud is discretized into an evenly spaced grid in the $x-y$ plane,
creating a set of pillars. Each pillar contains T points where T varies for
different pillars. A Pillar Feature Encoder consisting of a multi-layer
perceptron and a max pooling layer is applied to T point features in each
pillar to extract a single vector of dimensions $C$ as the pillar feature. The
encoded pillars form a bird’s-eye view pseudo-image of size $H\times W\times
C$.

##### Polar Pillar Partition

Each point is represented by a vector of point feature
$f=(r,\theta,z,x,y,i,t)$, where $(r,\theta)$ is the polar coordinates. The
points are grouped in $r-\delta$ plane, resulting in a BEV pseudo-image of
size $R\times\Theta\times C$.

####  4.1.2 2D CNN Backbone

We use a similar backbone as [5] and the structure is shown in Fig.3. The
backbone has a UNet-like [15] structure, with a top-down network that produces
features at increasingly small spatial resolution and a network that performs
deconvolution and concatenation of the top-down features. The final output
features are a concatenation of all upsampled features that originated from
different strides as well as the input pseudo-image.

####  4.1.3 Pillarwise Semantic Segmentation

The semantic segmentation head is doing pillarwise K-class classification,
with output size $H\times W\times K$, same spatial size as the input pillars.
The ground truth label for each pillar is decided by majority voting of points
within the same pillar. During inference, all points inside the same pillar
share the same predicted semantic class.

###  4.2 Pillar-level Affinity

##### Class-agonistic Pillar-level Affinity

We denote affinity between two pillars $pl_{i}$ and $pl_{j}$ as
$a_{pl_{i},pl_{j}}$. The holistic affinity vector associated with $pl_{i}$ is

$A_{i}=\\{a_{pl_{i},pl_{j}}\\},j=0,1,...,H\times W-1$ (1)

As discussed in Sec. 1, we only care about whether $pl_{i}$ shares the same
instance as any of its previous pillars in our zig-zag traversal order. Our
target for $pl_{i}$ can be reduced as

$a_{i}^{\prime}=max(\\{a_{pl_{i},pl_{j}}\\}),j=0,1,...,i-1$ (2)

which is a single value. The ground truth for $a_{i}^{\prime}$ is a binary
value. $a_{i}^{\prime}=0$ means $pl_{i}$ is not similar to any of its previous
pillars and $a_{i}^{\prime}=1$ means $pl_{i}$ shares the same instance with at
least one of its previous pillars. We can also see that if $a_{i}^{\prime}=0$,
$pl_{i}$ is the start (left-most pillar) of a new instance.

##### Generating Affinity Labels

First we gather pillarwise panoptic labels. We then traverse the pillars
belonging to the ’thing’ classes in the zig-zag order described earlier and if
the instance id has not been visited before, i.e., no similar pillars have
been visited, we set affinity label 0 to the current pillar. Otherwise we set
the label to 1.

##### Local Clustering for Instance Id Propagation

We need to recover the panoptic predictions from the direct outputs of our
network, i.e. semantic class predictions and pillar-wise affinity. We assign
unique instance ids to pillars with affinity zero and propagate the instance
ids to pillars with affinity one (pillars similar to their previous pillars).
The algorithm is described in Algorithm 1. We only do local clustering by
keeping a memory of instance ids and corresponding pillar locations for the
past k columns. As we traverse the pillars, if the pillar is predicted as a
‘thing’ class and has zero affinity, we assign a new instance id corresponding
to the semantic class. If the pillar is predicted as a ‘thing’ class and has
high affinity to previous pillars, we search the memory for the past k columns
and match the current pillar to the instance of the same semantic class and
within nearest Manhattan distance in pillar unit. Fig. 4(b) shows an
illustration of our binary affinity predictions and the resulting instance id
propagation.

Data: $\mathrm{sem\\_pred}\in\\{1,2...,K\\}^{H\times
W},\mathrm{affinity\\_pred}\in\\{0,1\\}^{H\times W}$

Result: $\mathrm{ins\\_pred}\in\mathbb{Z}^{H\times W}$

$\mathrm{ins\\_pred}\leftarrow 0$ ;

/* init with ignore class */

$\mathrm{counter}[1,...,L]\leftarrow 0$;

/* #instances for L ‘thing’ classes respectively */

init $\mathbb{M}$ ;

/* Memory to store instance id and corresponding pillar locations for past k
columns */

$\mathrm{offset}\leftarrow 1000$ ;

/* NuScenes panoptic label format, which sets max #instance per class to 1000
*/

for  _$a\leftarrow 0$ to $H-1$_ do

for  _$b\leftarrow 0$ to $W-1$_ do

$s\leftarrow\mathrm{sem\\_pred}[a,b]$;

if  _$s$ is stuff_ then

$\mathrm{ins\\_pred}[a,b]\leftarrow s\times\mathrm{offset}$;

else

if  _$\mathrm{affinity\\_pred}[a,b]$ is 0_ then

$\mathrm{ins\\_pred}[a,b]\leftarrow\mathrm{counter}[s]+1+s\times\mathrm{offset}$;

$\mathrm{counter}[s]\leftarrow\mathrm{counter}[s]+1$;

$update(\mathbb{M},ins\\_pred[a,b],a,b)$;

else

$\mathrm{ins\\_pred}[a,b]\leftarrow argmin\\_distance(\mathbb{M},s,a,b)$;

$update(\mathbb{M},\mathrm{ins\\_pred}[a,b],a,b)$;

end if

end if

end for

$drop\\_oldest\\_column(\mathbb{M},k)$ ;

/* keep k columns at maximum */

end for

Algorithm 1 Local Clustering for Instance Id Propagation

##  5 Experiments

###  5.1 Dataset and Metrics

NuScenes[4] is a large scale autonomous driving dataset. It contains 1,000
driving scenes from 4 locations in Singapore and Boston, with 850 scenes for
training and validation, and 150 scenes for testing. Points in 40,000
keyframes are manually annotated with 32 fine semantic classes, which can be
grouped into 16 coarse semantic classes.

We use mean intersection over union (mIoU) to evaluate the performance of
semantic segmentation. For panoptic segmentation, we use the Panoptic Quality
(PQ)[8], Semantic Quality (SQ) and Recognition Quality (RQ).

Method | $PQ\uparrow$ | $SQ\uparrow$ | $RQ\uparrow$ | $PQ^{Th}\uparrow$ | $SQ^{Th}\uparrow$ | $RQ^{Th}\uparrow$ | $PQ^{St}\uparrow$ | $SQ^{St}\uparrow$ | $RQ^{St}\uparrow$ | seg mIoU$\uparrow$
---|---|---|---|---|---|---|---|---|---|---
sem + box [5] | 77.7 | 87.2 | 88.7 | 80.3 | 88.9 | 90 | 73.3 | 84.2 | 86.4 | 73
sem + box$\circ$ [5] | 77.1 | 87.1 | 88 | 79.7 | 88.8 | 89.4 | 72.8 | 84.2 | 85.7 | 74.6
sem + centroid [8] | 76 | 87.4 | 86.4 | 79.2 | 90.4 | 87.6 | 70.5 | 82.5 | 84.6 | 70
sem + centroid$\circ$ [8] | 75 | 87.3 | 85.6 | 76.9 | 89.6 | 85.8 | 71.9 | 83.5 | 85.4 | 72.7
sem + affinity (Ours) | 76.7 | 87.5 | 87.3 | 78.5 | 89.3 | 87.7 | 73.6 | 84.3 | 86.6 | 73.6
sem + affinity$\circ$ (Ours) | 77.9 | 87.9 | 88.2 | 80 | 89.7 | 89 | 74.3 | 84.9 | 86.9 | 75.4
Table 1: Panoptic Segmentation results on the validation split of nuScenes.
$\circ$ denotes polar pillars and otherwise cartesian pillars. Table 2: Class-
wise Panoptic Segmentation results on the NuScenes val set. $\circ$ denotes
polar pillars and otherwise cartesian pillars.

Method |  barrier |  bike |  bus |  car |  cvehicle |  motorcycle |  pedestrian |  traffic cone |  trailer |  truck |  drivable |  other flat |  sidewalk |  terrain |  manmade |  vegetation | PQ
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
sem + box [5] | 72.5 | 73.1 | 81.8 | 92.1 | 72.3 | 87.3 | 91.6 | 90 | 65.4 | 76.5 | 94.9 | 56.4 | 67.9 | 51.3 | 86.9 | 82.6 | 77.7
sem + box$\circ$ [5] | 72.4 | 74.9 | 81.4 | 92.2 | 65.8 | 88.9 | 92.7 | 92 | 59.9 | 76.7 | 95.6 | 55.5 | 67.4 | 51 | 86.5 | 81.1 | 77.1
sem + centroid [8] | 74.4 | 71.6 | 80.5 | 91.5 | 67.2 | 82.9 | 86.7 | 86.7 | 73.1 | 77.4 | 94.4 | 54.2 | 62.0 | 47.7 | 85.1 | 79.8 | 76
sem + centroid$\circ$ [8] | 72.6 | 71.7 | 77.5 | 89.9 | 65.8 | 81.0 | 84.9 | 86.3 | 68.2 | 70.8 | 95.1 | 55.1 | 65.1 | 51.4 | 85.2 | 79.2 | 75
sem + affinity (Ours) | 60.3 | 73.3 | 74.9 | 90.1 | 73.1 | 87.2 | 91.3 | 90.7 | 69.1 | 75.1 | 95.1 | 55.8 | 68.5 | 52.6 | 86.8 | 82.7 | 76.7
sem + affinity$\circ$ (Ours) | 61.3 | 78.1 | 79.7 | 92 | 68.8 | 87.8 | 92.1 | 92 | 70.4 | 78 | 95.8 | 59.1 | 68.8 | 53.5 | 86.9 | 81.5 | 77.9

###  5.2 Baselines

Our baselines include both proposal-based and proposal-free methods.
PolarStream[5] is the first work for simultaneous lidar object detection and
semantic segmentation. The instance ids of points of ‘thing’ classes are
associated with the detection box ids whose box centers are the nearest and
share the same semantic predictions. Panoptic-PolarNet[8] is a proposal-free
lidar point cloud panoptic segmentation framework that regresses the point
centroid of each instance and group the points according to the predicted
centroids. For fair comparison, we implement both methods using the same
backbone as ours while following their original implementations for everything
else.

###  5.3 Implementation Details

Following the same configuration of PolarStream [5], we discretize the 3D
space within $[distance:0.3\sim 50.3m,z:-5\sim 3m]$ to $[512,512]$ Polar
pillars in NuScenes. For Cartesian pillars, the pillar size is $(0.2,0.2,8)m$
within 3D space $[x:-51.2\sim 51.2m,y:-51.2\sim 51.2m,,z:-5\sim 3m]$,
resulting in $[512,512]$ Cartesian pillars. We implement two sub-task heads,
i.e. semantic segmentation and affinity classification with one convolution
layer in total, each taking 16 and 2 channels respectively out of 18 channels.
We use cross-entropy loss and Lovasz softmax loss [2] to train semantic
segmentation as well as affinity classification. We set both semantic
segmentation and affinity classification loss weights to 2. We use adamW [14]
optimizer together with one-cycle policy [17] with LR max 0.00875, division
factor 10, momentum ranges from 0.95 to 0.85, fixed weight decay 0.01 to
achieve super convergence. With batch size 56, the model is trained for 20
epochs. We set $k=15$ in instance id propagation.

###  5.4 Quantative Results

Tab. 1 shows the comparison between our approach and the baselines on the val
split of NuScenes. Our method outperforms the centroid-based proposal-free
baseline, Panoptic-PolarNet[8] (sem + centroid) in both PQ and seg mIoU
regardless of the pillar shapes. We also find the offset estimation sub-task
in Panoptic-PolarNet diminishes the accuracy on semantic segmentation. It
validates the issues of centroid-based approaches as discussed in Sec. 1 and
shows that affinity is a more robust and transferable feature. Our affinity
classification head helps improve semantic segmentation and achieves best
semantic mIoU among all methods. Affinity classification focuses on structural
object information and the discrimination among different objects. Therefore,
it is beneficial to semantic segmentation. Our method is slightly better or
comparable to the proposal-based baseline PolarStream[5] (sem+box) in PQ even
though PolarStream uses extra 3D box annotations.

Tab. 2 shows per-class panoptic quality. Our model lags behind the baselines
in the PQ for barriers. We find the reason is that our method groups connected
barriers into fewer instances, resulting in more false negatives in
evaluation, as shown in Fig. 5. However, this under segmentation is completely
acceptable in practice for autonomous driving. Human drivers never try to
segment connected barriers.

(a) Original image

(b) Ground truth

(c) PolarStream[5] predictions

(d) Our predictions

Figure 5: Visualization of instance ids (color-coded) on barrier class. Our method tends to group connected barriers into fewer instances, resulting in lower PQ but is acceptable in practice. We do all experiments on lidar and project lidar on images here for better visualization. Method | $PQ\uparrow$ | $SQ\uparrow$ | $RQ\uparrow$ | $PQ^{Th}\uparrow$ | $SQ^{Th}\uparrow$ | $RQ^{Th}\uparrow$
---|---|---|---|---|---|---
global clustering | 73.3 | 85.7 | 84.8 | 72.7 | 86.2 | 83.5
global clustering + iterative | 77 | 87.7 | 87.4 | 78.7 | 89.4 | 87.8
local clustering | 77.9 | 87.9 | 88.2 | 80 | 89.7 | 89
Table 3: Ablation study on choices of clustering.

###  5.5 Ablation

To further analyze the influence of clustering for label propagation, we
conduct the ablation study on the validation split of NuScenes, as shown in
Tab. 3. The results are based on polar pillars. We find global clustering is
sub-optimal for our method because our cluster center is the left-most pillar
of the instance and grouping a pillar to a cluster center to its right is not
reasonable. But if we do global clustering iteratively to update cluster
centers by accumulating the points within an instance, the cluster centers are
moving towards the centroids, and then global clustering improves by 3.7. Our
local clustering matching current pillar to an instance only within past k
columns shows the best results.

###  5.6 Oracle Tests

To check what are the upper-bound performances for our model and the
baselines, we conduct an oracle test by replacing the predictions of our model
with the encoded (pre-processed) and then decoded (post-processed) ground
truth and obtain Tab. 4. We find that provided perfect predictions, all
approaches have close PQ for cartesian pillars. For polar pillars, the
proposal-free methods show close PQ upper-bound, while having higher upper-
bound compared to proposal-based method because it’s challenging to do object
detection with polar pillars.

Method | $PQ\uparrow$ | $SQ\uparrow$ | $RQ\uparrow$ | seg mIoU$\uparrow$
---|---|---|---|---
sem + box | 92.4 | 93.4 | 98.9 | 92.4
sem + box$\circ$ | 88.4 | 93 | 94.7 | 95.2
sem + centroid | 93.5 | 94.3 | 99.2 | 92.4
sem + centroid$\circ$ | 94.7 | 95.5 | 99.1 | 95.2
sem + affinity (ours) | 92.6 | 94 | 98.5 | 92.4
sem + affinity$\circ$ (ours) | 94.6 | 95.2 | 99.4 | 95.2
Table 4: The upper-bound performance of semantic segmentation and panoptic segmentation for the methods. The results are obtained by replacing the predictions of the network with ground truth (encoded and then decoded). PQ: panoptic quality; SQ: semantic quality; RQ: recognition quality; seg mIoU: semantic segmentation mIoU. $\circ$ denotes polar pillars. GT Semantic | GT Affinity | PQ
---|---|---
|  | 77.9
| ✓ | 78.9
✓ |  | 92.1
✓ | ✓ | 94.6
Table 5: Oracle test on the validation split of NuScenes.

Similar to Panoptic-PolarNet[8], we also conducted an oracle test to
investigate the room for improvement in our method, as shown in Tab. 5. We
replaced semantic and affinity predictions respectively with ground truth for
each experiment and generated the panoptic predictions using the same instance
id propagation scheme. It can be seen that our affinity prediction is very
close to the ground truth in our test setting and has only -1 difference in PQ
compared to given ground truth instance. Conversely, ground truth semantic
prediction greatly impacts the results and increases PQ to above 90. This
matches the finding in [6, 8] that the biggest bottleneck in proposal-free
panoptic segmentation is the quality of semantic segmentation predictions.

##  6 Conclusion

In this work, we have shown that lidar panoptic segmentation can be trained as
two purely classification sub-tasks, i.e. semantic segmentation and pillar-
level affinity prediction, removing the need for object detection heads and
their associated post-processing operations like NMS. We also show that
pillar-level affinities are a more robust feature to learn for the panoptic
segmentation task as compared to learning instance centroids as the former is
synergistic to the semantic segmentation task. We finally propose a simple and
efficient local clustering algorithm to propagate instance ids by merging
semantic segmentation and affinity predictions. Our model outperforms previous
proposal-free methods and completely closes the gap between proposal-based and
proposal-free methods.

## References

  * [1] Jiwoon Ahn and Suha Kwak.  Learning pixel-level semantic affinity with image-level supervision for weakly supervised semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4981–4990, 2018.
  * [2] Maxim Berman, Amal Rannen Triki, and Matthew B Blaschko.  The lovász-softmax loss: A tractable surrogate for the optimization of the intersection-over-union measure in neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4413–4421, 2018.
  * [3] Gedas Bertasius, Lorenzo Torresani, Stella X Yu, and Jianbo Shi.  Convolutional random walk networks for semantic image segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 858–866, 2017.
  * [4] Holger Caesar, Varun Bankiti, Alex H Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom.  nuscenes: A multimodal dataset for autonomous driving.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11621–11631, 2020.
  * [5] Qi Chen, Sourabh Vora, and Oscar Beijbom.  Polarstream: Streaming object detection and segmentation with polar pillars.  Advances in Neural Information Processing Systems, 34, 2021.
  * [6] Bowen Cheng, Maxwell D Collins, Yukun Zhu, Ting Liu, Thomas S Huang, Hartwig Adam, and Liang-Chieh Chen.  Panoptic-deeplab: A simple, strong, and fast baseline for bottom-up panoptic segmentation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12475–12485, 2020.
  * [7] Yanhua Cheng, Rui Cai, Zhiwei Li, Xin Zhao, and Kaiqi Huang.  Locality-sensitive deconvolution networks with gated fusion for rgb-d indoor semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3029–3037, 2017.
  * [8] Whye Kit Fong, Rohit Mohan, Juana Valeria Hurtado, Lubing Zhou, Holger Caesar, Oscar Beijbom, and Abhinav Valada.  Panoptic nuscenes: A large-scale benchmark for lidar panoptic segmentation and tracking.  arXiv preprint arXiv:2109.03805, 2021.
  * [9] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [10] Jie Hu, Liujuan Cao, Yao Lu, ShengChuan Zhang, Yan Wang, Ke Li, Feiyue Huang, Ling Shao, and Rongrong Ji.  Istr: End-to-end instance segmentation with transformers.  arXiv preprint arXiv:2105.00637, 2021.
  * [11] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollar.  Panoptic feature pyramid networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [12] Alex H Lang, Sourabh Vora, Holger Caesar, Lubing Zhou, Jiong Yang, and Oscar Beijbom.  Pointpillars: Fast encoders for object detection from point clouds.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12697–12705, 2019.
  * [13] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [14] Ilya Loshchilov and Frank Hutter.  Fixing weight decay regularization in adam.  2018\.
  * [15] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015.
  * [16] Kshitij Sirohi, Rohit Mohan, Daniel Büscher, Wolfram Burgard, and Abhinav Valada.  Efficientlps: Efficient lidar panoptic segmentation.  IEEE Transactions on Robotics, 2021.
  * [17] Leslie N Smith.  A disciplined approach to neural network hyper-parameters: Part 1–learning rate, batch size, momentum, and weight decay.  arXiv preprint arXiv:1803.09820, 2018.
  * [18] Huiyu Wang, Yukun Zhu, Bradley Green, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  Axial-deeplab: Stand-alone axial-attention for panoptic segmentation.  In European Conference on Computer Vision, pages 108–126. Springer, 2020.
  * [19] Yuwen Xiong, Renjie Liao, Hengshuang Zhao, Rui Hu, Min Bai, Ersin Yumer, and Raquel Urtasun.  Upsnet: A unified panoptic segmentation network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8818–8826, 2019.


#  $\cL$ is unequal $\NL$ under the Strong Exponential Time Hypothesis

Reiner Czerwinsk

###### Abstract

Due to Savitch’s theorem we know $\NL\subseteq{\mathbf{DSPACE}}(\log^{2}(n))$.
To show this upper bound, Savitch constructed an algorithm with
$O(\log^{2}(n))$ space on the working tape. We will show that Savitch’s
algorithm also described a lower bound under the Strong Exponential Time
Hypothesis. Every algorithm for the Connectivity Problem needs
$O(\log^{2}(n))$ space in this case.

##  1 Introduction

There are well-known upper bounds in the relation between nondeterministic and
deterministic complexity classes. It is obvious that
${\mathbf{NSPACE}}(t)\subseteq{\mathbf{DTIME}}(2^{O(t)})$, and, due to
Savitch’s theorem[4], ${\mathbf{NSPACE}}(s)\subseteq{\mathbf{DTIME}}(s^{2})$.
In this paper, we analyze, whether these bounds are also lower bounds under
the Strong Exponential Time Hypothesis (SETH).

The proof of Savitch’s theorem is constructive. There is an algorithm to find
a path between two vertices in a digraph, which needs $O(\log^{2}(n))$ space.
To show that Savitch’s algorithm is optimal, we use the following approach:
First, we will prove that for each algorithm there is a graph with $n$
vertices where the algorithm needs space to mark more than one vertex. With
this graph, we will construct a graph with $n^{l}$ vertices, where we have to
mark $l$ vertices.

In section 2 we introduce nondeterministic TMs (NTM). We need the NTM to
analyze the effect of SETH on -complete problems in section 3.

In section 4 , we will show that the algorithm described in Savitch’s theorem
has minimal space complexity when SETH is valid. So, SETH implies
$\cL\not=\NL$.

##  2 Nondeterministic Turing Machines

In this paper, we use a nondeterministic Turing machine (NTM) with an
additional certificate tape[1, p.84-86]. An NTM has a read-only input tape, a
read-once certificate tape, one working tape, and an output tape. W.l.o.g.,
the head of the certificate tape moves one cell to the right on each step of
the NTM. An input $x$ is accepted by the NTM $M$, i.e $x\in L(M)$, if there is
a certificate $c\in\\{0,1\\}^{*}$ with $M(x,c)=1$.

The configuration is the information one needs to continue the calculation of
an NTM from a specific moment. It is defined by the words on the input tape
and the working tape and the head position of the input and working tape and
the state of the NTM. The configuration does not depend on the content of the
certificate tape.

The configuration of an NTM is denoted by the content of the working and
output tape, and the position of the heads from the input, working, and output
tape.

The configuration graph is a digraph where the vertices are possible
configurations of the NTM. Two configurations are connected with a directed
edge if one configuration can be transformed into the other within one step of
the NTM. If the out-degree of a vertex of the configuration graph is more than
one, the possible edges are distinguished by the content of the current cell
on the certificate tape. So, the certificate describes a path in the
configuration graph but is not part of the configuration.

##  3  The Strong Exponential Time Hypothesis

The Exponential Time Hypothesis implies that a deterministic algorithm for
${\mathbf{SAT}}$ needs exponential run time. If the Strong Exponential Time
Hypothesis (SETH) is valid, then an algorithm for an $\mathbf{SAT}$-formula in
$k-{\mathbf{CNF}}$ form with $n$ variables needs $O(2^{n})$ run time in the
worst case when $k\to\infty$[3].

The SETH is related to NTMs via the Cook–Levin theorem[2]. We define

$U_{{\mathbf{NP}}}=\\{\langle N,x,1^{k}\rangle\mid\text{ NTM }N\text{ accepts
}x\text{ within }k\text{ steps}\\}$ (1) $U_{\NL}=\\{\langle
N,x,1^{k}\rangle\mid\text{ NTM }N\text{ accepts }x\text{ within }\log(k)\text{
working space}\\}\text{.}$ (2)

Obviously the set $U_{{\mathbf{NP}}}$ is $\mathbf{NP}$-complete, and the set
$U_{\NL}$ is -complete. The Cook–Levin theorem uses a p-many-one reduction
from $U_{{\mathbf{NP}}}$ to ${\mathbf{SAT}}$. With this proof technique we can
analyze $U_{\NL}$ under SETH.

######  Lemma 1.

Assume the Strong Exponential Time Hypothesis. Then we have to check every
possible path beginning with the start configuration of the configuration
graph.

###### Proof.

We use the reduction from the Cook-Levin theorem. The configuration at every
step during the run time of the NTM is described by Boolean variables. The
variable $T_{W}(t,p,s)$ is true if the symbol $s$ is on the working space tape
on $p$ at step $t$. The variable $H_{W}(t,p)$ is true if the head position of
the working space tape is on $p$ at step $t$. And there are similar variables
for the other heads.

Additionally, we get clauses from the space limitation. For this reason we
introduce the Boolean variables $S_{W}(t,p)$, which is true when the head of
the working space tape has passed the position $p$ before step $t$. It is
$S_{W}(t+1,p)=S_{W}(t,p)\lor H_{W}(t,p)$. If $k$ is the maximal tape space,
then we add the clauses$(\lnot S_{W}(t,p)\lor\lnot S_{W}(t,p+k))$ for all
$t$,$p$.

Assume SETH. If the NTM has not used the whole tape space, then an algorithm
has to check all paths. ∎

Although we have to check all paths, an algorithm for $U_{\NL}$ can be
accelerated by memorizing some configurations.

##  4 Savitch’s Algorithm is optimal

An -complete problem is ${\mathbf{st-CON}}$. Is there a path between two given
points of a digraph? This problem is in $\NL$ because an NTM needs only the
working space size for one point, i.e. $\log(n)$, where $n$ is the number of
vertices. The problem is -hard because there is a reduction from $U_{\NL}$ to
${\mathbf{st-CON}}$ by writing the configuration graph.

An $\mathbf{st-CON}$algorithm has to write some information about the digraph
on the working space. W.l.o.g., it can store information by marking some
vertices. The digraph consists of vertices and directed edges. Each edge is a
tuple of two vertices. If one marks a vertex by writing it on the working
tape, then one needs $O(\log(n))$ space.

######  Lemma 2.

Assume SETH. For each algorithm that solves ${\mathbf{st-CON}}$, there is a
digraph where at least two vertices are marked at one moment.

###### Proof.

The problem ${\mathbf{st-CON}}$ is $\NL$-complete. So, there is a reduction
from $U_{\NL}$ to ${\mathbf{st-CON}}$. We construct the configuration graph
with a logspace-transmuter. Due to theorem 1, a deterministic algorithm has to
test all possible paths from the start configuration to an accepted state in
the worst case. If the algorithm marks only one vertex each time, it has to
traverse every path. In this case, the run time is exponential. So, the
working space grows faster than logarithmic.

So, there is a graph where the algorithm has to mark more than one vertex to
shorten the computation time. ∎

######  Definition 1 (st-substitution).

There is a digraph $G$ with vertex $v$ and a digraph $H$ with vertices $s_{H}$
and $t_{H}$. The vertex $v$ will be substituted by $H$ when every vertex
adjacent to $v$ will be adjacent to $s_{H}$ and every vertex adjacent from $v$
will be adjacent from $s_{H}$.

When an algorithm for ${\mathbf{st-CON}}$ would mark the substituted vertex in
the origin digraph, then it would solve ${\mathbf{st-CON}}$ in the subgraph
that substituted the vertex. So, we can generalize lemma 2:

######  Lemma 3.

Assume SETH. For an arbitrary deterministic algorithm for ${\mathbf{st-CON}}$,
there is a digraph with the following property: If one st-substitutes each
vertex with a subdigraph, then there is a moment during the run time where the
algorithm solves ${\mathbf{st-CON}}$ on one of these subdigraphs and a vertex
outside this subdigraph is marked.

###### Proof.

As mentioned in lemma 2, the number of paths, that an algorithm has to check
can grow exponentially in relation to the number of vertices before the
substitutions. So, there is a moment during the run time when the algorithm
computes on a substituting subdigraph and has marked a vertex outside this
subdigraph. ∎

Now we use the st-substitution to construct a digraph, where more than two
vertices have to be marked at some moment.

Algorithm 1 Generation of the graph $G^{l}$

$K\leftarrow G$

if $l>1$ then

for $v\in V(K)$ do

substitute $v$ with $G^{l-1}$

$G^{l}\leftarrow K$

If the graph $G$ has $n$ vertices, then $G^{l}$ has $n^{l}$ vertices.

######  Lemma 4.

If SETH, then for an arbitrary algorithm to solve ${\mathbf{st-CON}}$ there is
a digraph $G$, where $A$ will mark at least $l+1$ vertices at one moment on
input $G^{l}$.

###### Proof.

We proof this lemma with induction over $l$. Due to lemma 2, there is a
digraph $G$ where the algorithm $A$ has to mark at least two vertices at one
moment. If $l=1$, then $G^{l}=G$. So, there is a moment at the run time of $A$
where it has marked at least two vertices.

For the graph $G^{l+1}$ there is a digraph $K$ isomorphic to $G$, where every
vertex will be substituted by $G^{l}$. If $v$ is a vertex of $K$, then
$G^{l}(v)$ is the subdigraph, that will substitute $v$. So, an $\mathbf{st-
CON}$ algorithm has to solve $\mathbf{st-CON}$ on the subdigraph $G^{l}(v)$
instead of marking $v$. By induction hypothesis one has to mark $l+1$ vertices
of this subdigraph. But $K$ is isomorphic to $G$. Due to theorem 3, there is a
vertex $v$, where one also has to mark a vertex outside of $G^{l}(v)$ when
calculating $\mathbf{st-CON}$ on this subdigraph. ∎

The graph $G^{l}$ has $N=n^{l}$ vertices, and the algorithm $A$ needs working
space to mark $l+1$ vertices. One vertex needs $\Theta(\log(N))$ space. So, we
need $\Theta(\log^{2}(N))$ working space. The SETH implies that Savitch’s
Algorithm is optimal.

## References

  * [1] Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009), https://books.google.de/books?id=nGvI7cOuOOQC
  * [2] Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. p. 151–158. STOC ’71, Association for Computing Machinery, New York, NY, USA (1971). https://doi.org/10.1145/800157.805047, https://doi.org/10.1145/800157.805047
  * [3] Impagliazzo, R., Paturi, R.: Complexity of k-sat. In: Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317). pp. 237–240 (1999). https://doi.org/10.1109/CCC.1999.766282
  * [4] Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4(2), 177 – 192 (1970). https://doi.org/https://doi.org/10.1016/S0022-0000(70)80006-X, http://www.sciencedirect.com/science/article/pii/S002200007080006X