# CPSeg: Cluster-free Panoptic Segmentation of
3D LiDAR Point Clouds

Enxu Li , Ryan Razani 11footnotemark: 1 , Yixuan Xu, Bingbing Liu
Huawei Noah’s Ark Lab
Toronto, Canada
{thomas.enxu.li, ryan.razani, richard.xu2<EMAIL_ADDRESS>
Indicates equal contribution.

###### Abstract

A fast and accurate panoptic segmentation system for LiDAR point clouds is
crucial for autonomous driving vehicles to understand the surrounding objects
and scenes. Existing approaches usually rely on proposals or clustering to
segment foreground instances. As a result, they struggle to achieve real-time
performance. In this paper, we propose a novel real-time end-to-end panoptic
segmentation network for LiDAR point clouds, called CPSeg. In particular,
CPSeg comprises a shared encoder, a dual decoder, a task-aware attention
module (TAM) and a cluster-free instance segmentation head. TAM is designed to
enforce these two decoders to learn rich task-aware features for semantic and
instance embedding. Moreover, CPSeg incorporates a new cluster-free instance
segmentation head to dynamically pillarize foreground points according to the
learned embedding. Then, it acquires instance labels by finding connected
pillars with a pairwise embedding comparison. Thus, the conventional proposal-
based or clustering-based instance segmentation is transformed into a binary
segmentation problem on the pairwise embedding comparison matrix. To help the
network regress instance embedding, a fast and deterministic depth completion
algorithm is proposed to calculate surface normal of each point cloud in real-
time. The proposed method is benchmarked on two large-scale autonomous driving
datasets, namely, SemanticKITTI and nuScenes. Notably, extensive experimental
results show that CPSeg achieves the state-of-the-art results among real-time
approaches on both datasets.

Figure 1: PQ vs runtime on SemanticKITTI [1] test set. Methods that run in 100
ms or less are considered to be real-time (green area). Our proposed CPSeg
outperforms all other available real-time approaches.

##  1 Introduction

A panoptic segmentation system that is able to predict both semantic tags and
instance-level segmentation begins to draw the attention of the autonomous
driving community, because both foreground dynamic objects (i.e. the thing)
and background static scenes (i.e. the stuff) can be perceived and outputted
simultaneously. Compared with image-based approaches, a panoptic segmentation
system using LiDAR point cloud lacks sufficient research yet, despite the fact
that LiDAR is a well-concurred primary perception sensor for autonomous
driving for its active sensing nature with high resolution of sensor readings.
The recently published GP-S3Net [2] is the current state-of-the-art in LiDAR
panoptic segmentation task. The authors proposed using a 3D sparse
convolution-based UNet as a semantic backbone and a combination of HDBSCAN and
GCNN to segment instances. However, GP-S3Net is computationally intensive and
is thus not a real-time method. Among all published works for LiDAR panoptic
segmentation, only few of them [3, 4, 5] are capable of operating in real-time
(see Figure 1). There still exists a performance gap when comparing the real-
time methods with the current state-of-the-art. A natural question to ask: is
it possible to fill this gap and build a panoptic segmentation method with a
competitive PQ yet still with a fast running time?

Given the runtime constraint for real-time systems, proposal-free methods are
favorable as they are more computationally efficient. Current proposal-free
approaches in the literature usually rely on clustering or graph to segment
foreground objects. These methods are mainly adopted from 2D image processing
tasks. Designing an effective 3D panoptic segmentation system based on unique
characteristics of LiDAR point clouds is still an open research problem. This
motivates us to find a more suitable and unique design targeting the panoptic
segmentation task in the LiDAR domain. In this work, we take advantage of
strong geometric patterns in LiDAR point clouds and present a new proposal-
free and cluster-free approach to segment foreground objects with capabilities
of running in real-time. In particular, we propose a network to predict object
centroid as embedding of each point and dynamically group points with similar
embedding as pillars in the sparse 2D space. Then, objects are formed by
building connections of pillars.

Our main contributions can be summarized as,

  1. 1.

A real-time panoptic segmentation network that is end-to-end (i.e., not
relying on clustering or proposals to segment instances) and achieves state-
of-the-art results without extensive post-processing

  2. 2.

A novel Task-aware Attention Module (TAM) that enforces the dual decoder
network to learn task-specific features

  3. 3.

A fast surface normal calculation module to aid the process of regressing
foreground instance embedding with a novel deterministic depth completion
algorithm

  4. 4.

A comprehensive qualitative and quantitative comparison demonstrating the
proposed method as opposed to existing methods on both large-scale datasets of
SemanticKITTI and nuScenes

  5. 5.

A thorough ablation analysis of how each proposed component contributes to the
overall performance

##  2 Related Work

The panoptic segmentation task jointly optimizes semantic and instance
segmentation. LiDAR-based semantic segmentation can be categorized into either
a projection-based, a voxel-based, or a point-based method depending on the
format of data being processed. Projection-based methods project a 3D point
cloud into a 2D image plane either in spherical Range-View (RV) [6, 7], top-
down Bird-Eye-View (BEV) [8, 9], or multi-view format [10]. Voxel-based
methods transform a point cloud into 3D volumetric grids to be processed using
3D convolutions. Processing these 3D grids using 3D convolution is
computationally expensive. Therefore, some methods leverage sparse
convolutions to alleviate this limitation and to fully exploit sparsity of
point clouds [11, 12, 13]. Point-based methods [14, 15], however, process the
unordered point cloud directly. Despite the high accuracy of the latter
approaches, they are inefficient and require large memory consumption. Similar
to instance segmentation, panoptic segmentation can be divided into top-down
(proposal-based) or bottom-up (proposal-free) methods, as elaborated below.

###  2.1 Proposal-based panoptic segmentation

Top-down panoptic segmentation is a two-stage approach. First, foreground
object proposals are generated, and subsequently, they are further processed
to extract instance information that is fused with background semantic
information. Mask R-CNN [16] is commonly used for instance segmentation with a
light-weight stuff branch segmentation. To resolve the overlapping instance
predictions by Mask R-CNN and the conflict between instance and semantic
predictions, several methods are introduced. UPSnet [17] presents a panoptic
head with the addition of an unknown class label. EfficientPS [18] proposes to
fuse the instance and semantic heads according to their confidence. Inspired
by image-based methods, MOPT [19] and EfficientLPS [18] attach a semantic head
to Mask R-CNN to generate panoptic segmentation on the range image. However,
these top-down methods are a result of the multiple sequential processes in
the pipeline and are usually slow in speed.

###  2.2 Proposal-free panoptic segmentation

In contrast to the proposal-based methods, bottom-up panoptic segmentation
predicts semantic segmentation and groups the “thing" points into clusters to
achieve instance segmentation. DeeperLab [20] introduces the instance
segmentation by regressing the bounding box corners and object center. Later,
Panoptic-DeepLab [21] proposes to predict the instance center locations and
group pixels to their closest predicted centers. The pioneering panoptic
method in the LiDAR domain, LPSAD [3], presents a shared encoder with a dual
decoder, followed by a clustering algorithm to segment instances based on the
predicted semantic embedding and the predicted object centroids in the 3D
space. Panoster [22] proposes a learnable clustering module to assign instance
class labels to every point. It requires extensive post-processing steps (e.g.
using DBSCAN to merge nearby object predictions) to refine the predictions in
order to have comparable results with the other state-of-the-art methods. DS-
Net [23], however, offers a learnable dynamic shifting module to shift points
in 3D space towards the object centroids. Recently, GP-S3Net [2] proposes a
graph-based instance segmentation network for LiDAR-based panoptic
segmentation, which achieves state-of-the-art performance on nuScenes and
SemanticKITTI panoptic segmentation benchmarks. Moreover, SMAC-Seg [5]
introduces a Sparse Multi-directional Attention Clustering module with a novel
repel loss to better supervise the network separating the instances. They
reach the state-of-the-art among existing real-time LiDAR-based methods.

###  2.3 Normal surface calculation

Numerous point cloud processing algorithms, such as surface reconstruction,
segmentation, shape modeling, and feature extraction, benefit from accurate
normal vectors associated with each point. Existing methods for computing
normal vectors for LiDAR point clouds could be divided into learning-based and
traditional deterministic approaches. For instance, [24, 25, 26] use a neural
network to estimate the normal of point cloud directly. Using learning-based
approaches would require extensive training data in order to achieve good
performance and might need additional fine-tuning when using different types
of LiDAR setups. On the other hand, deterministic geometry-based approaches
like [27] usually require a nearest neighbour search to obtain the
neighbourhood for each point and then estimate the surface by fitting a plane
to the neighbourhood point cloud using the least square method. These
approaches usually struggle to achieve real-time performance as the
neighbourhood search in 3D space is computationally heavy. [28] uses a range-
based deterministic approach to compute surface normal where the 3D normal is
transformed from derivatives of the surface from a sparse spherical depth map.
This approach operates in real-time; however, the surface normal is
incorrectly affected by the empty entries in the projected depth map,
resulting in false sharp gradients. To overcome this limitation, we propose to
use a novel depth completion algorithm to adaptively complete the
neighbourhood around the valid points in the sparse depth map and then compute
its normal from the 2D gradient.

##  3 Proposed Method

###  3.1 Problem Formulation

Let $(\textbf{P},\textbf{L})=\\{\textbf{p}_{i},(c_{i},o_{i})\\}^{N}_{i=1}$ be
N unordered points of a point cloud where $\textbf{p}_{i}\in\mathbb{R}^{D}$ is
the input feature for point $i$, tuple
$(c_{i},o_{i})\in\mathbb{C}\times\mathbb{O}$ is the semantic class label and
instance ID label for point $i$. $\mathbb{C}$ is a set of semantic class
labels and $\mathbb{O}$ is a set of instance IDs. $\mathbb{C}$ can be further
divided into $\mathbb{C}_{thing}$ and $\mathbb{C}_{stuff}$ representing a set
of countable foreground thing classes and a set of background stuff classes,
respectively. Note that instance label $o_{i}$ is only valid if
$c_{i}\in\mathbb{C}_{thing}$. The goal is to learn a function
$\mathcal{F}(.,\Theta)$, parameterized by $\Theta$, that takes input feature
$\textbf{p}_{i}$ and assigns a semantic label for each point and an instance
label if it is part of the foreground.

To solve this problem, we propose CPSeg, an end-to-end network to generate
predictions for panoptic segmentation without proposals or clustering
algorithms.

###  3.2 Network Architecture

Figure 2: Overview of our panoptic segmentation system.

Figure 3: Illustration of CPSeg. The network consists of a dual decoder U-net
which processes the input point cloud in RV to obtain semantic segmentation
and instance embedding. Then, the Cluster-free Instance Segmentation Module
separates the foreground into pillars and builds connections which leads to
instances. Both semantic and instance predictions are then gathered and sent
back to 3D view for post-processing.

The overview of our panoptic segmentation framework is depicted in Figure 2.
We first transform the LiDAR point cloud $\textbf{P}\in\mathbb{R}^{N\times
C_{0}}$ with $C_{0}$ as input features (Cartesian coordinates, remission and
depth) into a 2D range image with spatial dimension $H\times W$ using
spherical projection similar to [3]. At the same time, we build a dense depth
map, which will be utilized as a guidance for the depth completion algorithm
to extract surface normal features in the following stage. Then, CPSeg takes
both inputs and predicts semantic and instance segmentation results in the
range view (RV). When re-projecting the results to the 3D point cloud, KNN-
based post-processing is utilized to refine the output, as introduced in [6].
Lastly, we fuse the results to obtain panoptic labels and use majority voting
to refine the semantic segmentation results where different semantics are
predicted in the same instance.

Our proposed model is summarized in Figure 3. It consists of three main
components: (A) a dual-decoder U-Net with Task-aware Attention Module (TAM),
(B) a surface normal calculation module, which takes the depth maps and
computes normal vectors to benefit instance embedding regression, (C) a
cluster-free instance segmentation head, which segments the foreground
instance embedding into objects.

A 2D range view representation of a LiDAR point cloud is fed into CPSeg. The
output $\hat{\mathcal{G}}_{1}$, $\hat{\mathcal{G}_{2}}$ of the dual-decoder
U-Net are the semantic prediction and instance embedding of the projected
point cloud, respectively. In particular, the semantic decoder generates
$\hat{\mathcal{G}}_{1}\in\mathbb{R}^{H\times W\times C_{class}}$, where
$C_{class}$ is the number of semantic class labels. With the Cartesian xy
coordinates added as a prior, the instance decoder outputs
$\hat{\mathcal{G}}_{2}\in\mathbb{R}^{H\times W\times 2}=P_{xy}+O_{xy}$ where
$P_{xy}$ is the xy coordinates of the point cloud in RV, and $O_{xy}$ is the
output from the last block of the instance decoder. Essentially,
$\hat{\mathcal{G}}_{2}$ is the instance embedding in 2D space, which could
also be interpreted as the predicted 2D location of the object centroids.
Then, a binary mask $\mathcal{M}$ is used to filter foreground points and can
be expressed as,

$\mathcal{M}=\mathbb{I}(\mathcal{C}\in\mathbb{C}_{thing})=\begin{cases}1&\text{if
}\mathcal{C}\in\mathbb{C}_{thing}\\\ 0&\text{otherwise}\end{cases}$ (1)

where $\mathbb{I}$ is the binary conditional function, $\mathcal{C}$ is the
ground truth semantic label during training and will be replaced by
$argmax(\hat{\mathcal{G}}_{1})$ during test stage. We use $\mathcal{M}$ to
obtain corresponding embedding of the foreground thing from the instance
decoder, denoted as $\hat{\mathcal{G}}_{2,th}\in\mathbb{R}^{N\times 2}$ where
$N$ is the number of foreground points and 2 refers to the embedding in 2D
space. The foreground embedding is then used by the cluster-free instance
segmentation head to segment objects.

Basic architecture We adopt CLSA module from [5] to extract contextual
features. CLSA block learns to recover local geometry in the neighbourhood
which is beneficial for RV-based methods to learn contextual information. The
output of the CLSA module is then fed to a shared encoder with five residual
blocks, similarly to [29], where we obtain multi-scale feature maps,
$J_{1},J_{2},J_{4},J_{8}$ (subscript indicates the stride with respect to the
full resolution downsampled by AvgPool layer at the end of each encoder
block). We provide the detailed architecture, such as, number of in/out
channels, number of layers, and dimension of feature maps at each stage of the
encoder and decoder blocks in the Supplementary Material.

Figure 4: TAM: Task-aware Attention Module.

Task-aware Attention Module (TAM) Given feature maps in multiple resolutions,
we upsample them to the full resolution in a hierarchical manner, as shown in
Figure 4. Then a convolution layer with a residual skip connection is used to
refine the boundary for each feature map. Next, we obtain channel-wise
attention weights, $\pi_{sem}$ and $\pi_{ins}$ with two MLPs targetting the
semantic and instance segmentation tasks, respectively, using the following
equation.

$\pi=\sigma(MLP(\\\ AvgPool(J_{1\rightarrow 1}\mathbin{\|}J_{2\rightarrow
1}\mathbin{\|}J_{4\rightarrow 1}\mathbin{\|}J_{8\rightarrow 1})))$ (2)

where $J_{m\rightarrow 1}$ is the upsampled and refined feature map from
stride $m$ to the full resolution, $\mathbin{\|}$ is the concatenation
operation, and $\sigma$ denotes the sigmoid operation. Lastly, each feature
channel of the refined feature maps is multiplied with $\pi_{sem}$ and
$\pi_{ins}$ to get $J_{sem}$ and $J_{ins}$, which are then sent to the two
decoders to be fused with a residual block and obtain semantic segmentation
and instance embedding.

###  3.3 Surface Normal

The instance decoder learns to regress the instance embedding, which is the
shifted location in 2D space starting from the original xy coordinates towards
the object centroids. Surface normal vectors provide additional geometric
features to aid the network in this process. Thus, we use a Diamond Inception
Module, adopted from [10], to extract geometric features from surface normals
and directly fuse them with the features in the instance decoder using
concatenation operation followed by convolutional layers to obtain instance
embedding. We provide the final results with and without this module in the
Ablation Studies to further demonstrate its impact to the overall performance.

Figure 5: Proposed Depth Completion Algorithm.

In this section, we describe a deterministic way of calculating surface normal
features of the point cloud with a novel depth completion algorithm, as
depicted in Figure 5. The inputs to this module are (A) $\textbf{r}_{s}$,
sparse 2D depth map with a scale of $H\times W$, and (B) $\textbf{r}_{d}$,
dense 2D depth map with a scale of $H/2\times W/2$. The depth map is obtained
by projecting the LiDAR point cloud onto a 2D map with a specified size using
discretized indices from spherical transformation, as introduced by [30].

First, obtain $\textbf{r}_{row}$, a completed depth map with a weighted row
fill using $k$ row neighbours for every entry, as given by,

$r_{row}[i,j]=\frac{1}{n_{row}[i,j]}\sum_{v=-\lfloor k/2\rfloor}^{\lfloor
k/2\rfloor}r_{s}[i,j+v]\cdot o[i,j+v]\cdot w(v)$ (3)
$n_{row}[i,j]=\sum_{v=-\lfloor k/2\rfloor}^{\lfloor k/2\rfloor}o[i,j+v]\cdot
w(v)$ (4)

where $r_{s}[i,j]$ and $o[i,j]$ are the depth value and binary occupancy at
$i^{th}$ row and $j^{th}$ columnm respectively. The operation
$\lfloor.\rfloor$ denotes the floor function. The weights
$w(v)=ae^{-\frac{v^{2}}{2b^{2}}}$ are sampled from a Gaussian distribution
where the center point receives the largest attention and the neighboring
points are weighted less as they deviate away from the center. Here, $a$ and
$b$ are hyperparameters which are set to 1 in our method. Then equations 3 and
4 are re-used to obtain $\textbf{r}_{col}$ using $k$ column neighbours to
fill. Next, bilinear upsample $\textbf{r}_{d}$ to $H\times W$ is applied to
obtain a coarse but dense depth map, denoting as $\textbf{r}_{u}$. From
$\textbf{r}_{u}$, we calculate
$\frac{\partial{\textbf{r}_{u}}}{\partial{\theta}}$ and
$\frac{\partial{\textbf{r}_{u}}}{\partial{\phi}}$ using finite difference
approximation along horizontal and vertical directions where $\theta$ and
$\phi$ are the azimuth and elevation angles for each entry. Local geometry
could be interpreted from the two signals. Hence, they serve as the guidance
signal to adaptively select a horizontal or vertical fill for each empty
entry. For instance, when the magnitude of
$\frac{\partial{r_{u}}}{\partial{\phi}}$ is small (i.e.
$\lVert\frac{\partial{r_{u}}}{\partial{\phi}}\rVert\rightarrow 0$), it
indicates the point is on a pole-like or wall-like object. Therefore, a
completion using weighted average of the valid column neighbours is more
desired since the change in depth in the vertical direction is relatively
small. In summary, each entry in the completed depth map can be expressed as,

$r=\begin{cases}r_{s}&\text{if }o=1\\\ r_{row}&\text{if }\text{if
}o=0\And\lVert\frac{\partial{r_{u}}}{\partial{\theta}}\rVert<=\lVert\frac{\partial{r_{u}}}{\partial{\phi}}\rVert\\\
r_{col}&\text{if }\text{if
}o=0\And\lVert\frac{\partial{r_{u}}}{\partial{\theta}}\rVert>\lVert\frac{\partial{r_{u}}}{\partial{\phi}}\rVert\end{cases}$
(5)

where that index [$i,j$] is omitted for brevity and $o$ denotes occupancy.
From the completed depth map, r, we follow [31] to calculate the gradients
$\frac{\partial{\textbf{r}}}{\partial{\theta}}$ and
$\frac{\partial{\textbf{r}}}{\partial{\phi}}$ and transform them into 3D
Cartesian frame centered at the LiDAR sensor to obtain
($\hat{\textbf{n}}_{x}$, $\hat{\textbf{n}}_{y}$, $\hat{\textbf{n}}_{z}$). Note
that the purpose of the depth completion algorithm above is to ensure the
neighbourhood of the valid pixels is smooth such that the gradients are not
influenced by the noise.

###  3.4 Cluster-free Instance Segmentation

Given the 2D embedding of the foreground $\hat{\mathcal{G}}_{2,th}$ from the
instance decoder , the goal of the cluster-free instance segmentation module
is to segment them into instances. First, we dynamically group the foreground
points into pillars according to $\hat{\mathcal{G}}_{2,th}$, their location in
the 2D embedding space, such that points within grid size $d$ are inside the
same pillar (see bottom right of Figure 3). The embedding of each resulting
pillar is the average embedding of the points being grouped together.
Pillarized foreground embedding is denoted as
$\hat{\mathcal{G}}_{p}\in\mathbb{R}^{M\times 2}$, where M is the number of
pillars. Next, we construct a pairwise comparison matrix
$\hat{\mathcal{G}}_{m}\in\mathbb{R}^{M\times M}$ to find connected pillars
with each entry as,

$\hat{\mathcal{G}}_{m,ij}=f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})$
(6)

Each entry represents the connectivity probability of pillar $i$ and $j$. A
large probability indicates the network is confident that the points in the
two pillars belong to the same object. In order for $\hat{\mathcal{G}}_{m}$ to
provide meaningful connectivity indications, we need the function, $f$, to
follow several constraints: 1).
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,i})=1$, a pillar must be
connected to itself with 100% confidence. 2).
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})=f(\hat{\mathcal{G}}_{p,j},\hat{\mathcal{G}}_{p,i})$,
the connectivity is symmetric; in other words, the network should output the
same confidence when comparing pillar $i$ to $j$ and pillar $j$ to $i$. 3).
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})>=0$ and
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})<=1$, with
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})\rightarrow 1$ indicating
the two pillars belong to the same object.

We define
$f(\hat{\mathcal{G}}_{p,i},\hat{\mathcal{G}}_{p,j})=exp(-\alpha\lVert\hat{\mathcal{G}}_{p,i}-\hat{\mathcal{G}}_{p,j}\rVert_{2})$
which satisfies all the constraints listed above. Note that $\alpha$ could be
either learned from the pillar features or fixed as a hyperparameter constant.
We discuss in detail and compare the results in the Ablation Studies. Then, we
use a threshold $T$ to obtain a binary connectivity matrix,
$\hat{\mathcal{G}}_{f}$, formally,
$\hat{\mathcal{G}}_{f}=\mathbb{I}(\hat{\mathcal{G}}_{m}>T)$. Note that
$\hat{\mathcal{G}}_{f}$ could be interpreted as an adjacency matrix as for the
graph structure where each pillar is a node of the graph and a true entry in
the matrix represents the two nodes are connected. Then a simple algorithm is
used to find the connected disjoint sets in $\hat{\mathcal{G}}_{f}$ and assign
them separate instance IDs. Lastly, we map the pillar instance ID back to the
range view using point index matching process. Both semantic and instance
segmentation results are now ready to be re-projected back to the point cloud
and post-process.

###  3.5 Loss Functions

Semantic Segmentation Loss We follow [10] to supervise the semantic
segmentation output, $\hat{\mathcal{G}}_{1}$, with a weighted combination of
cross entropy (WCE), Lovász softmax, and Total Variation loss (TV).

$L_{sem}=\text{WCE}(\hat{\mathcal{G}}_{1},\mathcal{G}_{1})+1.5J(e(\hat{\mathcal{G}}_{1},\mathcal{G}_{1}))+7.5\text{TV}(\hat{\mathcal{G}}_{1},\mathcal{G}_{1})$
(7)

where $\mathcal{G}_{1}$ is the ground truth (GT) semantic label, $J$ is the
Lovász extension of IoU introduced in [32],
$e(\hat{\mathcal{G}_{1}},\mathcal{G}_{1})$ is the absolute error between the
predicted probability and the GT.

Instance Embedding Loss We use L2 regression loss to supervise the learning of
instance embedding by taking the difference in predicted instance embedding
with the GT. Note that the instance embedding here can be interpreted as the
mass centroid of an object in 2D BEV.

$L_{ins\\_emb}=\sum_{ij}\mathcal{M}_{ij}\cdot\lVert\mathcal{G}_{2,ij}-\hat{\mathcal{G}}_{2,ij}\rVert_{2}$
(8)

where $ij$ denotes the 2D index on the range image, $\mathcal{M}$ is the GT
foreground binary mask to eliminate the background points when calculating
loss, $\mathcal{G}_{2}$ is the GT instance embedding, which is the mass
centroid of each instance calculated by taking the average of the xy
coordinates in the object.

Instance Segmentation Loss Essentially, the task here is to supervise binary
segmentation on the pairwise matrix $\hat{\mathcal{G}}_{m}$ and optimize the
IoUs for positive and negative predictions. Assume points within the same
pillar are from the same object, we construct the GT instance label of each
pillar by taking the mode label of the points inside, denoted as
$\mathcal{G}_{p}\in\mathbb{O}^{M}$ where $\mathbb{O}$ is the set of GT
instance labels. The GT binary label for the pairwise comparison matrix,
$\mathcal{G}_{m}\in\mathbb{B}^{M\times M}$ is obtained with entries
$\mathcal{G}_{m,ij}=\mathbb{I}(\mathcal{G}_{p,i}=\mathcal{G}_{p,j})$.

$L_{ins\\_seg}=BCE(\hat{\mathcal{G}}_{m},\mathcal{G}_{m})+J(e(\hat{\mathcal{G}}_{m},\mathcal{G}_{m}))$
(9)

where $BCE$ is the binary cross entropy loss, $J$ is the Lovász extension of
IoU, $e(\hat{\mathcal{G}_{m}},\mathcal{G}_{m})$ is the absolute error between
the predicted probability and GT. The Lovász loss introduced by [32] has been
shown to be effective in optimizing the IoU metrics. Further experimental
results in the Ablation Studies show adding this loss achieve better overall
accuracy.

The total loss that is used to train the network is a weighted combination of
the loss terms described above.

$L_{total}=\beta_{1}L_{sem}+\beta_{2}L_{ins\\_emb}+\beta_{3}L_{ins\\_seg}$
(10)

where $\beta_{1},\beta_{2},\beta_{3}$ are the weights for the semantic,
instance embedding, and instance segmentation loss terms.

##  4 Experiments

In this section, we describe the experimental settings and evaluate the
performance of CPSeg on SemanticKITTI [1] and nuScenes dataset [33] for
panoptic segmentation. We compared our results with state-of-the-art
approaches. We refer the readers to the Ablation Studies on the design choices
and various components of the network.

Datasets SemanticKITTI [1] is the first available dataset on LiDAR-based
panoptic segmentation for driving scenes. It contains 19,130 training frames,
4,071 validation frames, and 20,351 test frames. We provided ablation analysis
and validation results on sequence 08, as well as test results on sequence
11-21. Each point in the dataset is provided with a semantic label of 28
classes, which are mapped to 19 classes for the task of panoptic segmentation.
Among these 19 classes, 11 belong to stuff classes and the rest of them are
considered thing, where instance IDs are available.

nuScenes [33] is another popular large-scale driving-scene dataset, with 700
scenes for training, 150 for validation, and 150 for testing. At the time of
writing, the authors have not provided point-level panoptic segmentation
labels for LiDAR scans. Thus, we generated the labels using the provided 3D
bounding box annotations from the detection dataset and the semantic labels
from the lidarseg dataset. In particular, we assign the same instance ID for
points within the bounding box with same semantic labels. Out of 16 labeled
classes in lidarseg datset, 8 human and vehicle classes are considered things,
and 8 other classes are considered stuff. We follow [4] to discard instances
with fewer than 20 points during evaluation. We train our model on the 700
training scenes and report the results on the validation set of 150 scenes.

Baselines We use a dual-decoder U-Net based on SalsaNext [29] as the baseline.
In particular, the two decoders generate semantic segmentation and instance
embedding respectively. Then a clustering algorithm (e.g. BFS, HDBSCAN) is
added after the instance decoder to segment the objects based on the predicted
embedding. To be fair in comparison, we add the CLSA Feature Extractor Module
in front of the encoder to match our network design. Moreover, we implement
LPSAD based on [3] as an additional baseline. Quantitative and qualitative
results are compared against the proposed methods on the SemanticKITTI and
nuScenes validation set.

Evaluation Metric We follow [34] to use the mean Panoptic Quality (PQ) as our
main metric to evaluate and compare the results with others. In addition, we
also report Recognition Quality (RQ), and Segmentation Quality (SQ). They are
calculated separately on stuff and thing classes, providing PQSt, SQSt, RQSt
and PQTh, SQTh, RQTh.

###  4.1 Experimental Setup

For both datasets, we trained CPSeg end-to-end for 150 epochs using SGD
optimizer and exponential-decay learning rate scheduler with initial learning
rate starting at 0.01 and a decay rate of 0.99 every epoch. A weight decay of
$10^{-4}$ was used. The model was trained on 4 NVIDIA V100 GPUs with a batch
size of 4 per GPU. The weights for the losses were set to $\beta_{1}=1.0$,
$\beta_{2}=0.1$, $\beta_{3}=0.2$. We used a range image with resolution of
($H=64$, $W=2048$) for SemanticKITTI, and ($H=32$, $W=1024$) for nuScenes.
Additionally, we provided CPSeg HR (high-resolution) using input size of
($H=64$, $W=2048$) for nuScenes. The pillar grid size, $d$ of the final models
was set to $0.15$ with pillar pairwise matrix threshold, $T$ to be $0.5$. The
mapping parameter, $\alpha$ was set to be $2.5$ for the final model.

Method | PQ | PQ$\dagger$ | RQ | SQ | PQTh | RQTh | SQTh | PQSt | RQSt | SQSt | mIoU | FPS
---|---|---|---|---|---|---|---|---|---|---|---|---
RangeNet++ [6] \+ PointPillars [35] | $37.1$ | $45.9$ | $47.0$ | $75.9$ | $20.2$ | $25.2$ | $75.2$ | $49.3$ | $62.8$ | $76.5$ | $52.4$ | $2.4$
PanopticTrackNet [19] | $43.1$ | $50.7$ | $53.9$ | $78.8$ | $28.6$ | $35.5$ | $80.4$ | $53.6$ | $67.3$ | $77.7$ | $52.6$ | $6.8$
KPConv [15] \+ PointPillars [35] | $44.5$ | $52.5$ | $54.4$ | $80.0$ | $32.7$ | $38.7$ | $81.5$ | $53.1$ | $65.9$ | $79.0$ | $58.8$ | $1.9$
Panoster [22] | $52.7$ | $59.9$ | $64.1$ | $80.7$ | $49.4$ | $58.5$ | $83.3$ | $55.1$ | $68.2$ | $78.8$ | $59.9$ | $-$
DS-Net [23] | $55.9$ | $62.5$ | $66.7$ | $82.3$ | $55.1$ | $62.8$ | $87.2$ | $56.5$ | $69.5$ | $78.7$ | $61.6$ | $3.4^{*}$
EfficientLPS [18] | $57.4$ | $63.2$ | $68.7$ | 83.0 | $53.1$ | $60.5$ | 87.8 | 60.5 | 74.6 | 79.5 | $61.4$ | $-$
GP-S3Net [2] | 60.0 | 69.0 | 72.1 | $82.0$ | 65.0 | 74.5 | $86.6$ | $56.4$ | $70.4$ | $78.7$ | 70.8 | $3.7^{*}$
LPSAD [3] | $38.0$ | $47.0$ | $48.2$ | $76.5$ | $25.6$ | $31.8$ | $76.8$ | $47.1$ | $60.1$ | $76.2$ | $50.9$ | 11.8
Panoptic-PolarNet [4] | $54.1$ | $60.7$ | $65.0$ | $81.4$ | $53.3$ | $60.6$ | 87.2 | $54.8$ | $68.1$ | $77.2$ | $59.5$ | $11.6$
SMAC-Seg [5] | $56.1$ | $62.5$ | $67.9$ | $82.0$ | $53.0$ | $61.8$ | $85.6$ | 58.4 | 72.3 | 79.3 | 63.3 | $10.1$
CPSeg [Ours] | 57.0 | 63.5 | 68.8 | 82.2 | 55.1 | 64.1 | $86.1$ | 58.4 | 72.3 | 79.3 | $62.7$ | $10.6$

Table 1: Comparison of LiDAR panoptic segmentation performance on
SemanticKITTI [1] test dataset. Metrics are provided in [%] and FPS is in
[Hz].(*: source from [5])

Method | PQ | PQ$\dagger$ | RQ | SQ | PQTh | RQTh | SQTh | PQSt | RQSt | SQSt | mIoU | FPS
---|---|---|---|---|---|---|---|---|---|---|---|---
DS-Net [23] | $42.5$ | $51.0$ | $50.3$ | $83.6$ | $32.5$ | $38.3$ | $83.1$ | $59.2$ | $70.3$ | 84.4 | $70.7$ | $-$
PanopticTrackNet [19] | $50.0$ | $57.3$ | $60.6$ | $80.9$ | $45.1$ | $52.4$ | $80.3$ | $58.3$ | $74.3$ | $81.9$ | $63.1$ | $-$
EfficientLPS [18] | $59.2$ | $62.8$ | $70.7$ | $82.9$ | $51.8$ | $62.7$ | $80.6$ | 71.5 | 84.1 | $84.3$ | $69.4$ | $-$
GP-S3Net [2] | $61.0$ | $67.5$ | $72.0$ | $84.1$ | $56.0$ | $65.2$ | $85.3$ | $66.0$ | $78.7$ | $82.9$ | 75.8 | $-$
SMAC-Seg HiRes [5] | 68.4 | 73.4 | 79.7 | 85.2 | 68.0 | 77.2 | 87.3 | $68.8$ | $82.1$ | $83.0$ | $71.2$ | $6.2$
LPSAD [3] | $50.4$ | $57.7$ | $62.4$ | $79.4$ | $43.2$ | $53.2$ | $80.2$ | $57.5$ | $71.7$ | $78.5$ | $62.5$ | 22.3
SMAC-Seg [5] | $67.0$ | 71.8 | 78.2 | $85.0$ | 65.2 | 74.2 | $87.1$ | $68.8$ | $82.2$ | $82.9$ | 72.2 | $14.5$
Panoptic-PolarNet [4] | 67.7 | $71.0$ | $78.1$ | 86.0 | 65.2 | $74.0$ | 87.2 | 71.9 | 84.9 | 83.9 | $69.3$ | $10.1$
Dual-Dec UNet w/ BFS [Our Baseline] | $52.6$ | $58.0$ | $64.3$ | $79.7$ | $39.2$ | $49.0$ | $77.5$ | $66.0$ | $79.5$ | $81.9$ | $71.1$ | $20.1$
Dual-Dec UNet w/ HDBSCAN [Our Baseline] | $63.3$ | $68.8$ | $75.2$ | $83.5$ | $60.8$ | $70.9$ | $85.0$ | $66.0$ | $79.5$ | $81.9$ | $71.1$ | $18.8$
CPSeg [Ours] | $68.9$ | $73.6$ | $80.4$ | $84.9$ | $68.7$ | $78.4$ | $86.8$ | $69.2$ | $82.5$ | $83.1$ | $72.7$ | 21.3
CPSeg HR [Ours] | 71.1 | 75.6 | 82.5 | 85.5 | 71.5 | 81.3 | 87.3 | 70.6 | 83.7 | 83.6 | 73.2 | $7.0$

Table 2: Comparison of LiDAR panoptic segmentation performance on nuScenes
[33] validation dataset. Metrics are provided in [%] and FPS is in [Hz].

###  4.2 Quantitative Evaluation

In Table 1 and Table 2, we compile the results of CPSeg compared to other
models. For evaluations on SemanticKITTI test dataset (Table 1), we separate
the models into two groups based on their inference speed. Only the models in
row 8-11 are known to have real-time performance, with FPS’s above 10Hz. With
a PQ of $57.0\%$ and an FPS of 10.6Hz, CPSeg (row 11) achieves performances
that match state-of-the-art models. More importantly, it establishes a new
benchmark in PQ for real-time models, surpassing the next best real-time
model, SMAC-Seg, by $0.9\%$. Specifically, with a $2.3\%$ increase in RQTh and
0.5Hz improvement in FPS over SMAC-Seg, we demonstrate that CPSeg is better in
recognizing foreground objects while requiring less computation. These
improvements can be mainly attributed to the use of cluster-free instance
segmentation module and the incorporation of surface normal as a helpful part
of the instance embedding.

For results on nuScenes validation dataset (Table 2), since the methods for
creating the instance labels are not standardized across publications, we
separated the models into three groups for better comparison. The models in
rows 1-8 are previously published models, grouped by inference speed similar
to Table 1. The baseline and proposed models listed in row 9-12 use results
from our experiments. Using $64\times 2048$ range images as input, CPSeg HR
(row 12) obtains the highest PQ out of all models, outperforming the baseline
models Dual Decoder (BFS) and Dual Decoder (HDBSCAN) by $18.5\%$ and $7.8\%$,
respectively. However, because the setting in nuScenes dataset is more crowded
compared to semanticKITTI dataset with more instances in each scene, the
performance of CPSeg HR is no longer real-time. By reducing the resolution
from $64\times 2048$ to $32\times 1024$, CPSeg (row 11) again achieves a
competitive real-time performance with only a small trade-off in PQ.

###  4.3 Qualitative Evaluation

Figure 6: Qualitative comparison of CPSeg with other methods on both
SemanticKITTI and nuSenes validation set.

The panoptic segmentation performance of CPSeg can also be seen in Figure 6,
where we compare its inference results to LPSAD, our implementation based on
[3], and our baseline models. For a closedup view of a scene from
SemanticKITTI dataset (row 1) where three cars are lined up closely, only
CPSeg segments the instance points without errors. LPSAD identifies the car in
the middle as two separate instances, whereas the baseline model produce even
worse over-segmentation errors.

In a complex scene from nuScenes (row 2), with variations in instance classes
and few sparse points describing each instance, correctly recognizing and
distinguishing each instance is proved to be more difficult. For areas where
pedestrians are walking closely to each other or where cars are positioned
further away, the baseline model using HDBSCAN and LPSAD are prone to making
under-segmentation errors. In such a complex scene, only CPSeg is able to
segment each instance accurately. Additional examples and an explanation of
the models’ behaviours are provided in the Supplementary Material.

##  5 Ablation Studies

In this section, we present an extensive ablation analysis on the proposed
components in CPSeg. Note that all results are compared on SemanticKITTI
validation set (Seq 08). First, we investigate the individual contribution of
each component in the network and show the results in Table 3. The cluster-
free instance segmentation module is the key component, introducing $9.6\%$
increase on the PQ (compare to the baseline with BFS) while eliminating the
computation of clustering at the same time. Adding TAM also leads to a further
improvement as the two decoders receive more meaningful task-specific
features. Moreover, extracting surface normal brings another jump in PQ since
the network receives guidance on regressing the embedding for each foreground
object. Lastly, the model achieves the best result by incorporating binary
Lovász loss in supervising the segmentation on the pariwise matrix.

Architecture |  Cluster-free |  TAM |  3D Normal |  Lovász | mPQ
---|---|---|---|---|---
Baseline w/ BFS |  |  |  |  | 44.9
Baseline w/ HDBSCAN |  |  |  |  | 52.7
Proposed | ✓ |  |  |  |  $54.5$
✓ | ✓ |  |  |  $54.8$
✓ | ✓ | ✓ |  |  $55.6$
✓ | ✓ |  | ✓ |  $55.3$
✓ |  | ✓ | ✓ |  $55.1$
✓ | ✓ | ✓ | ✓ |  56.2

Table 3: Ablation study of the proposed model with individual components vs
baseline. Metrics are provided in [%].

We experiment with changing $\alpha$, the parameter used to map the pillar
embedding to the connectivity probability. We set the threshold $T$ to be 0.5,
and pillar grid size $d$ to be 0.15 for the experiments on $\alpha$. In the
first setting, $\alpha$ is learned from the corresponding pillar feature from
the instance decoder. In particular,
$\alpha=MLP(J_{ins,i}\mathbin{\|}J_{ins,j})$, where $J_{ins,i}$ and
$J_{ins,j}$ are the corresponding features of pillar $i$ and $j$ from the
instance decoder, and $\mathbin{\|}$ denotes the concatenation operation. In
the second setting, we set $\alpha$ to be various fixed values. From the
results in Table 4, constant $\alpha=2.5$ yields the best results. A fixed
value works relatively better than learning from the feature; for panoptic
segmentation tasks on outdoor autonomous driving dataset, the difference in
the regressed 2D embedding is enough to determine the connectivity of the
pillars. However, we think that a learned $\alpha$ could potentially work
better if the scene is dense and crowded (indoor scenes) such that the network
requires more information in making connections. Also note that
$\alpha=2.5\approx-ln(T)/(2\times d)$. We draw conclusions that $\alpha$ can
be regarded as a function of the threshold, $T$, and pillar grid size, $d$.
Hence, we choose $\alpha$ to be $\frac{-ln(T)}{2d}$ for the rest of the
experiments. This design choice ensures that adjacent pillars are considered
to be connected.

| $\alpha$ | PQ | PQTh | RQTh | SQTh
---|---|---|---|---|---
Fixed | $0.1$ | $44.7$ | $31.5$ | $38.7$ |  $71.9$
$1.0$ | $56.0$ | $58.4$ | $66.2$ |  76.7
$2.5$ | 56.2 | 58.7 | 66.8 |  $76.4$
$5.0$ | $48.7$ | $41.0$ | $51.2$ |  $68.0$
Learned | $-$ | $55.3$ | $56.2$ | $64.9$ |  $75.5$

Table 4: Ablation study of using different $\alpha$. Metrics are provided in
[%].

One may concern about the complexity of the model as it grows quadratically
with $M$, the number of pillars. Note that we provide the average number of
pillars resulted from using different grid sizes in Table 5. Typically, a
SemanticKITTI LiDAR scan contains an average number of 12 instances and 6.8k
number of foreground points. We find that $M$ is proportional to the number of
instances in the scan but significantly less than the number of points. As the
point embedding is learned to shift together in the network, dynamically
grouping the foreground points together using pillars according to their
embedding significantly reduces the computation the network needs to carry.

Grid Size (m) | $M$ | PQ | PQTh | RQTh | SQTh | Runtime (ms)
---|---|---|---|---|---|---
$0.05$ | $430$ | $55.1$ | $56.7$ | $65.6$ | $75.0$ |  $104$
$0.15$ | $141$ | 56.2 | 58.7 | 66.8 | $76.4$ |  $94$
$0.30$ | $103$ | $56.0$ | $57.6$ | $65.7$ | $76.2$ |  $91$
$0.50$ | $91$ | $55.8$ | $57.6$ | $65.4$ | 76.6 |  90

Table 5: Ablation study of using different grid sizes in pillarizing
foreground points by their embedding. Metrics are provided in [%].

##  6 Conclusion

In this work, we propose a novel real-time proposal-free and cluster-free
panoptic segmentation network for 3D point cloud, called CPSeg. Our method
builds upon an efficient semantic segmentation network and addresses the
instance segmentation by incorporating a unique cluster-free instance head
where the foreground point cloud is dynamically pillarized in the sparse space
according to the learned embedding and object instances are formed by building
connection of pillars. Moreover, a novel task-aware attention module is
designed to enforce two decoders to learn task-specific features. CPSeg
outperforms existing real-time LiDAR-based panoptic segmentation methods on
both datasets of SemanticKITTI and nucSenes. The thorough analysis illustrates
the robustness and effectiveness of the proposed method, which could inspire
the field and push the panoptic segmentation research towards a proposal-free
and cluster-free direction.

## References

  * [1] Jens Behley, Martin Garbade, Andres Milioto, Jan Quenzel, Sven Behnke, Cyrill Stachniss, and Jürgen Gall.  Semantickitti: A dataset for semantic scene understanding of lidar sequences.  In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019, pages 9296–9306. IEEE, 2019.
  * [2] Ryan Razani, Ran Cheng, Enxu Li, Ehsan Taghavi, Yuan Ren, and Liu Bingbing.  Gp-s3net: Graph-based panoptic sparse semantic segmentation network.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 16076–16085, October 2021.
  * [3] A. Milioto, J. Behley, C. McCool, and C. Stachniss.  Lidar panoptic segmentation for autonomous driving.  In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 8505–8512, 2020.
  * [4] Zixiang Zhou, Yang Zhang, and Hassan Foroosh.  Panoptic-polarnet: Proposal-free lidar point cloud panoptic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
  * [5] Enxu Li, Ryan Razani, Yixuan Xu, and Liu Bingbing.  Smac-seg: Lidar panoptic segmentation via sparse multi-directional attention clustering, 2021.
  * [6] Andres Milioto, Ignacio Vizzo, Jens Behley, and Cyrill Stachniss.  Rangenet++: Fast and accurate lidar semantic segmentation.  In Proc. of the IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2019.
  * [7] Ryan Razani, Ran Cheng, Ehsan Taghavi, and Liu Bingbing.  Lite-hdseg: Lidar semantic segmentation using lite harmonic dense convolutions.  In 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021.
  * [8] Y. Zeng, Y. Hu, S. Liu, J. Ye, Y. Han, X. Li, and N. Sun.  Rt3d: Real-time 3-d vehicle detection in lidar point cloud for autonomous driving.  IEEE Robotics and Automation Letters, 3(4):3434–3440, 2018.
  * [9] Martin Simon, Stefan Milz, Karl Amende, and Horst-Michael Gross.  Complex-yolo: An euler-region-proposal for real-time 3d object detection on point clouds.  In Laura Leal-Taixé and Stefan Roth, editors, Computer Vision – ECCV 2018 Workshops, pages 197–209, Cham, 2019. Springer International Publishing.
  * [10] Martin Gerdzhev, Ryan Razani, Ehsan Taghavi, and Bingbing Liu.  Tornado-net: multiview total variation semantic segmentation with diamond inception module.  In 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021.
  * [11] Ran Cheng, Ryan Razani, Yuan Ren, and Bingbing Liu.  S3net: 3d lidar sparse semantic segmentation network.  In 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021.
  * [12] Hui Zhou, Xinge Zhu, Xiao Song, Yuexin Ma, Zhe Wang, Hongsheng Li, and Dahua Lin.  Cylinder3d: An effective 3d framework for driving-scene lidar semantic segmentation.  arXiv preprint arXiv:2008.01550, 2020.
  * [13] Ran Cheng, Ryan Razani, Ehsan Taghavi, Enxu Li, and Bingbing Liu.  (af)2-s3net: Attentive feature fusion with adaptive feature selection for sparse semantic segmentation network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.
  * [14] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652–660, 2017.
  * [15] Hugues Thomas, Charles R Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, François Goulette, and Leonidas J Guibas.  Kpconv: Flexible and deformable convolution for point clouds.  In Proceedings of the IEEE International Conference on Computer Vision, pages 6411–6420, 2019.
  * [16] Kaiming He, Georgia Gkioxari, Piotr Dollar, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
  * [17] 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.
  * [18] Kshitij Sirohi, Rohit Mohan, Daniel Büscher, Wolfram Burgard, and Abhinav Valada.  Efficientlps: Efficient lidar panoptic segmentation, 2021.
  * [19] Juana Valeria Hurtado, Rohit Mohan, Wolfram Burgard, and Abhinav Valada.  Mopt: Multi-object panoptic tracking.  The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshop on Scalability in Autonomous Driving, 2020.
  * [20] Tien-Ju Yang, Maxwell D Collins, Yukun Zhu, Jyh-Jing Hwang, Ting Liu, Xiao Zhang, Vivienne Sze, George Papandreou, and Liang-Chieh Chen.  Deeperlab: Single-shot image parser.  arXiv preprint arXiv:1902.05093, 2019.
  * [21] 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.
  * [22] Stefano Gasperini, Mohammad-Ali Mahani, Alvaro Marcos-Ramiro, Nassir Navab, and Federico Tombari.  Panoster: End-to-end panoptic segmentation of lidar point clouds.  IEEE Robotics and Automation Letters, PP:1–1, 02 2021.
  * [23] Fangzhou Hong, Hui Zhou, Xinge Zhu, Hongsheng Li, and Ziwei Liu.  Lidar-based panoptic segmentation via dynamic shifting network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.
  * [24] Alexandre Boulch and Renaud Marlet.  Deep learning for robust normal estimation in unstructured point clouds.  Computer Graphics Forum, 35(5):281–290, 2016.
  * [25] Paul Guerrero, Yanir Kleiman, Maks Ovsjanikov, and Niloy J. Mitra.  Pcpnet learning local shape properties from raw point clouds.  Computer Graphics Forum, 37(2):75–85, 2018.
  * [26] Jun Zhou, Hua Huang, Bin Liu, and Xiuping Liu.  Normal estimation for 3d point clouds via local plane constraint and multi-scale selection.  Computer-Aided Design, 129:102916, 2020.
  * [27] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun.  Open3d: A modern library for 3d data processing, 2018.
  * [28] H. Badino, D. Huber, Y. Park, and T. Kanade.  Fast and accurate computation of surface normals from range images.  In 2011 IEEE International Conference on Robotics and Automation, pages 3084–3091, 2011.
  * [29] Tiago Cortinhal, George Tzelepis, and Eren Erdal Aksoy.  Salsanext: Fast semantic segmentation of lidar point clouds for autonomous driving.  In 2020 IEEE Intelligent Vehicles Symposium (IV), pages 655–661, 2020.
  * [30] Bichen Wu, Alvin Wan, Xiangyu Yue, and Kurt Keutzer.  Squeezeseg: Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 1887–1893. IEEE, 2018.
  * [31] H. Badino, D. D. Huber, Y. Park, and T. Kanade.  Fast and accurate computation of surface normals from range images.  In 2011 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2011.
  * [32] 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.
  * [33] 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.
  * [34] Alexander Kirillov, Kaiming He, Ross Girshick, Carsten Rother, and Piotr Dollar.  Panoptic segmentation.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [35] 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 (CVPR), June 2019.


# Spanning caterpillar in biconvex bipartite graphs

Dhanyamol Antony Department of Computer Science and Automation, Indian
Institute of Science, Bengaluru, India
Email: {dhanyamola, shirishgp, dalujacob<EMAIL_ADDRESS>Anita Das
Department of Mathematics, Manipal Institute of Technology Bengaluru, Manipal
Academy of Higher Education, Manipal, India
Email<EMAIL_ADDRESS>Shirish Gosavi Department of Computer Science and
Automation, Indian Institute of Science, Bengaluru, India
Email: {dhanyamola, shirishgp, dalujacob<EMAIL_ADDRESS>Dalu Jacob
Department of Computer Science and Automation, Indian Institute of Science,
Bengaluru, India
Email: {dhanyamola, shirishgp, dalujacob<EMAIL_ADDRESS>Shashanka
Kulamarva Department of Computer Science and Automation, Indian Institute of
Science, Bengaluru, India
Email: {dhanyamola, shirishgp, dalujacob<EMAIL_ADDRESS>
###### Abstract

A bipartite graph $G=(A,B,E)$ is said to be a biconvex bipartite graph if
there exist orderings $<_{A}$ in $A$ and $<_{B}$ in $B$ such that the
neighbors of every vertex in $A$ are consecutive with respect to $<_{B}$ and
the neighbors of every vertex in $B$ are consecutive with respect to $<_{A}$.
A _caterpillar_ is a tree that will result in a path upon deletion of all the
leaves. In this note, we prove that _there exists a spanning caterpillar in
any connected biconvex bipartite graph_. Besides being interesting on its own,
this structural result has other consequences. For instance, this directly
resolves the _burning number conjecture_ for biconvex bipartite graphs.

Keywords: Biconvex bipartite graphs; Caterpillar; Bipartite permutation
graphs; Chain graphs; Graph burning; Burning number

Mathematics Subject Classification: 05C75, 05C05

##  1 Introduction

We consider finite, simple, and undirected graphs throughout the paper. Let
$G=(V,E)$ be a graph with the set of vertices $V$ and the set of edges $E$.
For basic graph theoretic notations and definitions, we refer to [7].

A graph is _connected_ if, for any pair of vertices, there exists a path
between them. A graph is _acyclic_ if it does not contain a cycle. A _tree_ is
a connected acyclic graph. A _star_ on $n$ vertices, denoted as $K_{1,n-1}$,
is a tree with exactly $n-1$ leaves. A _caterpillar_ is a tree that will
result in a path upon deletion of all the leaves. Henceforth, we refer to this
path as _residual path_. In other words, a _caterpillar_ is a tree having a
residual path $P$ such that every vertex that is not in $P$ is adjacent to a
vertex in $P$. A graph is said to be a _permutation graph_ if its vertices
correspond to the elements of a permutation, and its edges denote the pairs of
elements that are reversed by this permutation. A subgraph $H$ of a graph $G$
is said to be a _spanning subgraph_ if $V(H)=V(G)$. The following lemma on
trees was given by Driscoll et al. [4].

######  Lemma 1.1 ([4]).

Every tree on at most six vertices is a caterpillar.

A graph $G=(V,E)$ is said to be _bipartite_ if the vertex set $V$ can be
partitioned into two partite sets $A$ and $B$ such that every edge in $E$ has
its one end-point in $A$ and the other end-point in $B$. A bipartite graph
$G=(A,B,E)$ is said to be a _convex bipartite_ graph if there exists an
ordering of vertices, say, $<_{B}$ of $B$ such that the neighbors of every
vertex in $A$ are consecutive with respect to $<_{B}$. A bipartite graph
$G=(A,B,E)$ is said to be a _biconvex bipartite graph_ if there exist
orderings $<_{A}$ of $A$ and $<_{B}$ of $B$ such that the neighbors of every
vertex in $A$ are consecutive with respect to $<_{B}$ and the neighbors of
every vertex in $B$ are consecutive with respect to $<_{A}$.

For any two distinct vertices $a_{i},a_{j}\in A$, by $a_{i}<_{A}a_{j}$, we
mean $a_{i}$ appears before $a_{j}$ in the ordering $<_{A}$. Similarly, for
any two distinct vertices $b_{i},b_{j}\in B$, by $b_{i}<_{B}b_{j}$, we mean
$b_{i}$ appears before $b_{j}$ in the ordering $<_{B}$. The set of all
neighbors of a vertex $v$ in $G$ is denoted as $N_{G}(v)$ or simply $N(v)$. A
bipartite graph $G=(A,B,E)$ is said to be a _chain graph_ if there exist
orderings $<_{A}$ of $A$ and $<_{B}$ of $B$ such that $N(u)\subseteq N(v)$
whenever $u<_{A}v$ and $N(a)\supseteq N(b)$ whenever $a<_{B}b$.

By a result of Spinrad et al. [6], the class of bipartite permutation graphs
is a subclass of the class of biconvex bipartite graphs. Further, it is easy
to see that the class of chain graphs is a subclass of the class of biconvex
bipartite graphs. The following observation follows from the definition of a
biconvex bipartite graph.

######  Observation 1.2.

Let $G=(A,B,E)$ be a biconvex bipartite graph, $x,y\in A$ (respectively,
$x,y\in B$), and $z\in N(x)\cap N(y)$. If $w\in A$ (respectively, $w\in B$)
such that $x<_{A}w<_{A}y$ (respectively, $x<_{B}w<_{B}y$), then by consecutive
property of the neighbors of $z$, we have that $z$ is adjacent to $w$, i.e.,
$z\in N(w)$.

Let $G=(A,B,E)$ be a biconvex bipartite graph. Two edges $a_{i}b_{s}$ and
$a_{j}b_{r}$ in $G$ are said to be _cross edges_ if either $a_{i}<_{A}a_{j}$
and $b_{r}<_{B}b_{s}$, or $a_{j}<_{A}a_{i}$ and $b_{s}<_{B}b_{r}$. A biconvex
ordering of $G$ (pair $<_{A}$ and $<_{B}$) is said to be a _straight ordering_
(in short, an $S$-ordering) if, whenever a pair of cross edges $a_{i}b_{s}$
and $a_{j}b_{r}$ exist in $G$, then at least one of the edges $a_{i}b_{r}$ and
$a_{j}b_{s}$ also exists. A biconvex ordering of $G$ that is also an
$S$-ordering is said to be a _biconvex $S$-ordering_ of $G$. Abbas and Stewart
[1] studied the structure of biconvex bipartite graphs and gave the following
theorem.

######  Theorem 1.3 ([1]).

Every connected biconvex bipartite graph has a biconvex $S$-ordering.

A path between a pair of vertices $u$ and $v$ in $G$ is said to be a _straight
path_ (in short, an $S$-path) if it does not contain any cross edges. Abbas
and Stewart [1] also proved the following theorem on the existence of
$S$-paths.

######  Theorem 1.4 ([1]).

Let $G$ be a connected biconvex bipartite graph with a biconvex $S$-ordering
and let $u$ and $v$ be any two vertices in $G$. Then there exists a shortest
$(u,v)$-path in $G$ that is an $S$-path.

An _asteroidal triple_ in a graph $G$ is an independent set (a set of vertices
with no edge between any pair) of three vertices in $G$ if every two of them
have a path between them avoiding the neighborhood of the third one. If there
is no asteroidal triple in a graph, then the graph is said to be _asteroidal
triple-free_ (_AT-free_ , for short). By a result of Corneil et al. [3], we
have that there exists a spanning caterpillar in every AT-free graph. One can
see that biconvex bipartite graphs can have an asteroidal triple, i.e.,
biconvex bipartite graphs need not be AT-free. Here, we present a similar
structural existential result on connected biconvex bipartite graphs. In
particular, we prove the following theorem.

######  Theorem 1.5.

If $G$ is a connected biconvex bipartite graph, then there exists a spanning
caterpillar in $G$.

Note that a similar statement of Theorem 1.5 may not hold for convex bipartite
graphs that are not biconvex. For instance, Figure 1 illustrates an example of
a connected convex bipartite graph that does not have a spanning caterpillar.
One can verify that the graph in Figure 1 is not a biconvex bipartite graph.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b_{1}$$b_{2}$$b_{3}$ Figure 1: A convex bipartite
graph having no spanning caterpillar

##  2 Proof of Theorem 1.5

This section is all about proving our main result, i.e., Theorem 1.5.

###### Proof.

Let $G$ be the given biconvex bipartite graph of order $n$, with $A$ and $B$
as the partite sets of cardinalities $n_{1}$ and $n_{2}$. Let
$<_{A}=(a_{1},a_{2},\dots,a_{n_{1}})$ and
$<_{B}=(b_{1},b_{2},\dots,b_{n_{2}})$ be the biconvex $S$-ordering of $G$
(existence of such a pair $<_{A}$ and $<_{B}$ follows from Theorem 1.3).
Suppose $n\leq 6$. Since graph $G$ is connected, it has a spanning tree $T$.
By Lemma 1.1, we have that $T$ is a caterpillar, as desired. Thus we can
assume that $n\geq 7$. Depending on the cardinalities of $n_{1}$ and $n_{2}$,
we have the following cases.

######  Case 1.

$n_{1}=1$ or $n_{2}=1$.

Without loss of generality, say $n_{1}=1$, i.e., $A=\\{a_{1}\\}$. Then since
$n\geq 7$, we have $n_{2}\geq 6$. Since $G$ is connected, $a_{1}$ is adjacent
to every vertex in $B$. Since $G$ is bipartite, there is no edge between two
vertices in $B$, implying that $G$ is a star, i.e., $G=K_{1,n_{2}}$. Hence, if
we delete all the leaves in $G$ (which itself is a tree), we get $P_{1}$,
i.e., a path on one vertex, which implies that $G$ is a caterpillar, as
desired.

######  Case 2.

$n_{1}\geq 2$ and $n_{2}\geq 2$

Let $a_{f}$ be the first neighbor of $b_{1}$ and let $a_{l}$ be the last
neighbor of $b_{n_{2}}$ with respect to $<_{A}$. Note that as $n_{1}\geq 2$
and $n_{2}\geq 2$, we have $a_{1}\neq a_{n_{1}}$ and $b_{1}\neq b_{n_{2}}$.
Depending on $N(a_{1})\cap N(a_{n_{1}})$ and $N(b_{1})\cap N(b_{n_{2}})$, we
have the following cases.

######  Case 2.1.

$N(a_{1})\cap N(a_{n_{1}})\neq\emptyset$ or $N(b_{1})\cap
N(b_{n_{2}})\neq\emptyset$.

Without loss of generality, let $N(a_{1})\cap N(a_{n_{1}})\neq\emptyset$. Let
$b_{c}$ be a common neighbor of $a_{1}$ and $a_{n_{1}}$. Then by Observation
1.2, we have that every vertex in $A$ is adjacent to $b_{c}$. Now, depending
on $N(b_{1})\cap N(b_{n_{2}})$, we have the following cases.

######  Case 2.1.1.

$N(b_{1})\cap N(b_{n_{2}})\neq\emptyset$.

Let $a_{c}$ be a common neighbor of $b_{1}$ and $b_{n_{2}}$. Then by
Observation 1.2, we have that every vertex in $B$ is adjacent to $a_{c}$. Now,
we consider $P=a_{c}b_{c}$. Then every vertex of $G$ that is not in $P$ is
adjacent to either $a_{c}$ or $b_{c}$ implying that $G$ has a spanning
caterpillar with $P$ being the residual path.

######  Case 2.1.2.

$N(b_{1})\cap N(b_{n_{2}})=\emptyset$.

Since $b_{c}$ is adjacent to every vertex in $A$, the fact that $N(b_{1})\cap
N(b_{n_{2}})=\emptyset$ will imply that $b_{1}$, $b_{c}$ and $b_{n_{2}}$ are
three distinct vertices in $B$ and $a_{f}\neq a_{l}$. Now, we consider
$P=b_{1}a_{f}b_{c}a_{l}b_{n_{2}}$. Let $v$ be a vertex of $G$ that is not in
$P$. If $v\in A$, then $v$ is adjacent to $b_{c}$. Otherwise, $v\in B$ and by
Observation 1.2, $v$ is adjacent to $a_{f}$ or $a_{l}$ implying that $G$ has a
spanning caterpillar with $P$ being the residual path.

######  Case 2.2.

$N(a_{1})\cap N(a_{n_{1}})=\emptyset$ and $N(b_{1})\cap
N(b_{n_{2}})=\emptyset$.

Let $Q$ be a shortest path from $b_{1}$ to $b_{n_{2}}$ in $G$ which is also an
$S$-path (recall that an $S$-path is a path without cross edges). Since $G$ is
connected, the existence of $Q$ follows from Theorem 1.4. Let
$Q=b^{\prime}_{1}a^{\prime}_{1}b^{\prime}_{2}\dots
b^{\prime}_{k-1}a^{\prime}_{k-1}b^{\prime}_{k}$ for some positive integer $k$.
Here we have $b^{\prime}_{1}=b_{1}$ and $b^{\prime}_{k}=b_{n_{2}}$. Moreover,
every vertex of the form $a^{\prime}_{i}$ is in $A$ and every vertex of the
form $b^{\prime}_{i}$ is in $B$. Further, since $N(b_{1})\cap
N(b_{n_{2}})=\emptyset$, we have $a^{\prime}_{1}\neq a^{\prime}_{k-1}$,
implying that $k\geq 3$. Since $Q$ is an $S$-path, we have:

$a^{\prime}_{1}<_{A}a^{\prime}_{2}<_{A}\dots<_{A}a^{\prime}_{k}\text{\enskip
and
\enskip}b_{1}=b^{\prime}_{1}<_{B}b^{\prime}_{2}<_{B}\dots<_{B}b^{\prime}_{k}=b_{n_{2}}$

Recall that $a_{f}$ is the first neighbor of $b_{1}$ and $a_{l}$ is the last
neighbor of $b_{n_{2}}$. If $a_{f}<_{A}a^{\prime}_{1}$, then add the edge
$a_{f}b_{1}$ (same as $a_{f}b^{\prime}_{1}$) to the path $Q$ and label
$a^{\prime}_{0}=a_{f}$. Note that otherwise, we have $a_{f}=a^{\prime}_{1}$.
If $a^{\prime}_{k-1}<_{A}a_{l}$, then add the edge $a_{l}b_{n_{2}}$ (same as
$a_{l}b^{\prime}_{k}$) to the path $Q$ and label $a^{\prime}_{k}=a_{l}$. Note
that otherwise, we have $a_{l}=a^{\prime}_{k-1}$. Let this modified path be
$P$. In other words, the path $P$ is defined as follows:

$P=\begin{aligned}
\begin{cases}a^{\prime}_{0}b^{\prime}_{1}a^{\prime}_{1}b^{\prime}_{2}\dots
b^{\prime}_{k-1}a^{\prime}_{k-1}b^{\prime}_{k}a^{\prime}_{k},\text{ if
}a^{\prime}_{0}=a_{f}<_{A}a^{\prime}_{1}\text{ and
}a^{\prime}_{k-1}<_{A}a_{l}=a^{\prime}_{k}\vskip 6.0pt plus 2.0pt minus
2.0pt\\\ a^{\prime}_{0}b^{\prime}_{1}a^{\prime}_{1}b^{\prime}_{2}\dots
b^{\prime}_{k-1}a^{\prime}_{k-1}b^{\prime}_{k},\text{ if
}a^{\prime}_{0}=a_{f}<_{A}a^{\prime}_{1}\text{ and
}a^{\prime}_{k-1}=a_{l}\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
b^{\prime}_{1}a^{\prime}_{1}b^{\prime}_{2}\dots
b^{\prime}_{k-1}a^{\prime}_{k-1}b^{\prime}_{k}a^{\prime}_{k},\text{ if
}a_{f}=a^{\prime}_{1}\text{ and
}a^{\prime}_{k-1}<_{A}a_{l}=a^{\prime}_{k}\vskip 6.0pt plus 2.0pt minus
2.0pt\\\ b^{\prime}_{1}a^{\prime}_{1}b^{\prime}_{2}\dots
b^{\prime}_{k-1}a^{\prime}_{k-1}b^{\prime}_{k},\text{
otherwise}\end{cases}\end{aligned}$

Let $b_{r}$ be a vertex in $B$ but not in $P$. Then $b_{r}$ is sandwiched
between two vertices $b^{\prime}_{i}$ and $b^{\prime}_{i+1}$ for some $i$ with
$1\leq i\leq k-1$ (i.e., $b^{\prime}_{i}<_{B}b_{r}<_{B}b^{\prime}_{i+1}$) such
that $b^{\prime}_{i},b^{\prime}_{i+1}\in V(P)$. Since the vertex
$a^{\prime}_{i}$ in $P$ is adjacent to both $b^{\prime}_{i}$ and
$b^{\prime}_{i+1}$, by Observation 1.2, $a^{\prime}_{i}$ is also adjacent to
$b_{r}$. Since $b_{r}$ was chosen arbitrarily, we can infer that every vertex
of $B$ that is not in $P$ is adjacent to a vertex in $P$. Let $a_{s}$ be a
vertex in $A$ but not in $P$ such that $a_{f}<_{A}a_{s}<_{A}a_{l}$. Then
$a_{s}$ is sandwiched between two vertices $a^{\prime}_{i}$ and
$a^{\prime}_{i+1}$, for some $i$ with $0\leq i\leq k-1$ (i.e.,
$a^{\prime}_{i}<_{A}a_{s}<_{A}a^{\prime}_{i+1}$) such that
$a^{\prime}_{i},a^{\prime}_{i+1}\in V(P)$. Since the vertex $b^{\prime}_{i+1}$
in $P$ is adjacent to both $a^{\prime}_{i}$ and $a^{\prime}_{i+1}$, by
Observation 1.2, $b^{\prime}_{i+1}$ is also adjacent to $a_{s}$. Since $a_{s}$
was chosen arbitrarily, we can infer that every vertex of $A$ that is not in
$P$, appearing in between $a_{f}$ and $a_{l}$ is adjacent to a vertex of $P$.

Let $A_{0}$ be the set of all vertices in $A$ that appear before $a_{f}$ in
the ordering $<_{A}$. Let $A_{1}$ be the set of all vertices in $A$ that
appear after $a_{l}$ in the ordering $<_{A}$. Note that every vertex in $G$
that is not in $A_{0}\cup A_{1}$ is either in $P$ or is adjacent to a vertex
in $P$. Hence, if $A_{0}=A_{1}=\emptyset$, then $P$ itself is the residual
path leading to the caterpillar. Therefore, we can assume that
$A_{0}\neq\emptyset$ or $A_{1}\neq\emptyset$. Further, we have the following
cases.

######  Case 2.2.1.

Exactly one among $A_{0}$ and $A_{1}$ is non-empty.

Without loss of generality, assume that $A_{1}\neq\emptyset$. Thus we have
$A_{0}=\emptyset$. Then clearly, $a_{n_{1}}\in A_{1}$ and is the last vertex
in $A_{1}$. Suppose $a_{n_{1}}$ is adjacent to some vertex $b^{\prime}_{i}$ in
$P$. Since $b^{\prime}_{i}$ is adjacent to both $a^{\prime}_{i-1}$ and
$a_{n_{1}}$, by Observation 1.2, $b^{\prime}_{i}$ is also adjacent to every
vertex in between $a^{\prime}_{i-1}$ and $a_{n_{1}}$. In particular,
$b^{\prime}_{i}$ is adjacent to every vertex in $A_{1}$. Therefore, since
$A_{0}=\emptyset$, we are sure that $P$ is the residual path which yields the
required caterpillar. Hence, we can assume that $a_{n_{1}}$ is not adjacent to
any vertex in $P$.

Let $\tilde{b}$ be the last neighbor of $a_{n_{1}}$ (for the case
$A_{0}\neq\emptyset$ and $A_{1}=\emptyset$, we consider $\tilde{b}$ to be the
first neighbor of $a_{1}$). Since $a_{n_{1}}$ is not adjacent to any vertex of
$P$, we have $\tilde{b}\notin V(P)$. In particular, $\tilde{b}\neq b_{1}$ and
$\tilde{b}\neq b_{n_{2}}$. Therefore, $\tilde{b}$ is sandwiched between two
vertices $b^{\prime}_{i}$ and $b^{\prime}_{i+1}$ for some $i$ with $1\leq
i\leq k-1$ (i.e., $b^{\prime}_{i}<_{B}\tilde{b}<_{B}b^{\prime}_{i+1}$) such
that $b^{\prime}_{i},b^{\prime}_{i+1}\in V(P)$. Since the vertex
$a^{\prime}_{i}$ in $P$ is adjacent to both $b^{\prime}_{i}$ and
$b^{\prime}_{i+1}$, by Observation 1.2, $a^{\prime}_{i}$ is also adjacent to
$\tilde{b}$.

Now, obtain a path $P_{1}$ from $P$ by replacing the vertex $b^{\prime}_{i+1}$
by $\tilde{b}$. We call this a _vertex replacement operation_ and denote it as
$R(b^{\prime}_{i+1},\tilde{b})$. Observe that any vertex in $G-V(P)$ which has
$b^{\prime}_{i+1}$ as the only neighbor in $P$ is either in between
$a^{\prime}_{i}$ and $a^{\prime}_{i+1}$, or in $A_{1}$. Since the vertex
$\tilde{b}$ in $P_{1}$ is adjacent to both $a^{\prime}_{i}$ and
$a^{\prime}_{n_{1}}$, by Observation 1.2, $\tilde{b}$ is also adjacent to
every vertex in between $a^{\prime}_{i}$ and $a^{\prime}_{n_{1}}$. This also
includes all the vertices in $A_{1}$ and all the vertices in between
$a^{\prime}_{i}$ and $a^{\prime}_{i+1}$. Further, every vertex in $B$ is
either in $P_{1}$ or is adjacent to some vertex in $P_{1}$, since
$V(P_{1})\cap A=V(P)\cap A$. Therefore, we have that every vertex of $G$ which
is not in $P_{1}$ is adjacent to a vertex of $P_{1}$, implying that $G$ has a
spanning caterpillar with $P_{1}$ being the residual path.

######  Case 2.2.2.

Both $A_{0}$ and $A_{1}$ are non-empty.

Recall that $A_{0}$ is the set of all vertices in $A$ that appear before
$a_{f}$ in the ordering $<_{A}$ and $A_{1}$ is the set of all vertices in $A$
that appear after $a_{l}$ in the ordering $<_{A}$. Let $G_{0}=G-A_{1}$ and let
$G_{1}=G-A_{0}$. Notice that in graph $G_{0}$, we have $A_{1}=\emptyset$ and
in graph $G_{1}$, we have $A_{0}=\emptyset$. Observe that in order to obtain
$G_{0}$ and $G_{1}$ from $G$, we are deleting some consecutive vertices with
respect to $<_{A}$. Hence, one can see that the graphs $G_{0}$ and $G_{1}$
remain biconvex bipartite. From the choice of $A_{0}$ and $A_{1}$, it is clear
that the graphs $G_{0}$ and $G_{1}$ are connected. Therefore, by using the
arguments in Case 2.2.1 individually, we obtain paths $P_{0}$ in $G_{0}$ and
$P_{1}$ in $G_{1}$ of the corresponding caterpillars. Let $R(x_{0},y_{0})$ be
the vertex replacement operation (refer Case 2.2.1 for the definition)
performed to obtain $P_{0}$ from $P$ and let $R(x_{1},y_{1})$ be the vertex
replacement operation performed to obtain $P_{1}$ from $P$. By the steps in
Case 2.2.1, we clearly have that $y_{0}$ is the first neighbor of $a_{1}$,
$y_{1}$ is the last neighbor of $a_{n_{1}}$, $x_{0}<_{B}y_{0}$, and
$y_{1}<_{B}x_{1}$.

Now, we obtain a new path $\tilde{P}$ by performing both the replacements
$R(x_{0},y_{0})$ and let $R(x_{1},y_{1})$ in the path $P$. Observe that if
$y_{0}<_{B}y_{1}$, then the replacements $R_{0}$ and $R_{1}$ are independent
of each other. In that case, one can see that every vertex in $G-V(\tilde{P})$
is adjacent to a vertex of $\tilde{P}$. This will in turn imply that $G$ has a
spanning caterpillar with $\tilde{P}$ being the residual path. So, the rest of
the proof boils down to proving that $y_{0}<_{B}y_{1}$.

######  Claim 1.

The vertex $y_{0}$ appears before the vertex $y_{1}$ in the ordering $<_{B}$.

###### Proof.

Since $N(a_{1})\cap N(a_{n_{1}})=\emptyset$, we have $y_{0}\neq y_{1}$. By way
of contradiction, assume that $y_{1}<_{B}y_{0}$. Then since
$a_{1}<_{A}a_{n_{1}}$ and $y_{1}<_{B}y_{0}$, we have a pair of cross edges
$a_{1}y_{0}$ and $a_{n_{1}}y_{1}$. Since the ordering considered for $G$ is an
$S$-ordering, we have $a_{1}y_{1}\in E(G)$ or $a_{n_{1}}y_{0}\in E(G)$. In the
former case, $y_{1}$ is a common neighbor of $a_{1}$ and $a_{n_{1}}$, and in
the latter case, $y_{0}$ is a common neighbor of $a_{1}$ and $a_{n_{1}}$. In
either case, we have a contradiction to the fact that $N(a_{1})\cap
N(a_{n_{1}})=\emptyset$. Hence, the claim. ∎

This also completes the proof of Theorem 1.5. ∎

##  3 Impact on Graph Burning

Apart from the structural significance, Theorem 1.5 would be useful in several
aspects. Here, we provide an implication of the result on a well-known
conjecture, called the _burning number conjecture_.

For a graph $G$, the _burning number_ , $b(G)$, is the minimum number of
iterations required to inflame (or burn) the whole graph while in each
iteration the fire spreads from all burned vertices to their neighbors and one
additional vertex can be burned. A sequence of vertices
$B=(b_{1},b_{2},\dots,b_{k})$ is said to be a _burning sequence_ of $G$ if the
whole graph can be burned in $k$ steps by burning the vertices in $B$
sequentially.

The concept of burning number was coined by Bonato et al. [2]. They
conjectured as follows:

######  Conjecture 3.1 ([2]).

For any connected graph $G$ of order $n$, $b(G)\leq\lceil\sqrt{n}\rceil$.

This is called the _burning number conjecture_ in the literature and is widely
worked upon from thereon. Hiller et al. [5] proved the conjecture for
caterpillars.

######  Theorem 3.2 ([5]).

If $G$ is a caterpillar of order $n$, then $b(G)\leq\lceil\sqrt{n}\rceil$.

It is clear that burning a spanning tree of a graph is sufficient to burn the
entire graph. Therefore, we have the following corollary of Theorem 1.5 and
Theorem 3.2.

######  Corollary 3.3.

If $G$ is a connected biconvex bipartite graph of order $n$, then
$b(G)\leq\lceil\sqrt{n}\rceil$.

Hence, we can conclude that Conjecture 3.1 is true for the class of biconvex
bipartite graphs. Consequently, the conjecture is true for any subclass of
biconvex bipartite graphs. In particular, we can also conclude that Conjecture
3.1 is true for the bipartite permutation graphs and the chain graphs.

##  4 Conclusion

In this paper, we proved the existence of a spanning caterpillar in connected
biconvex bipartite graphs. This structural existence is useful in studying
several problems on biconvex bipartite graphs. One such instance is provided
in the paper by applying this result in proving the burning number conjecture
for biconvex bipartite graphs. It would be interesting to see whether some
other problems can be addressed by using this result.

## References

  * Abbas and Stewart [2000] Nesrine Abbas and Lorna K. Stewart, “Biconvex Graphs: Ordering and Algorithms.” _Discrete Applied Mathematics_ , 103, (2000), 1–19.
  * Bonato et al. [2016] Anthony Bonato, Jeannette Janssen and Elham Roshanbin, “How To Burn A Graph.” _Internet Mathematics_ , 12, (2016), 85–100.
  * Corneil et al. [1997] Derek G. Corneil, Stephan Olariu and Lorna Stewart, “Asteroidal Triple-Free Graphs.” _SIAM Journal on Discrete Mathematics_ , 10, (1997), 399–430.
  * Driscoll et al. [2017] Keith Driscoll, Elliot Krop and Michelle Nguyen, “All Trees are Six-Cordial.” _Electronic Journal of Graph Theory and Applications_ , 5, (2017), 21–35.
  * Hiller et al. [2021] Michaela Hiller, Arie M. C. A. Koster and Eberhard Triesch, _On the Burning Number of p-Caterpillars_ , vol. 5, chap. Graphs and Combinatorial Optimization: from Theory to Applications: CTW2020 Proceedings. Springer, Cham (2021), pp. 145–156.
  * Spinrad et al. [1987] Jeremy Spinrad, Andreas Brandstädt and Lorna Stewart, “Bipartite permutation graphs.” _Discrete Applied Mathematics_ , 18, (1987), 279–292.
  * West [2001] Douglas B. West, _Introduction to Graph Theory_. $2^{nd}$ edn., Prentice Hall, Upper Saddle River, NJ (2001).