#  S-Graphs+: Real-time Localization and Mapping leveraging Hierarchical
Representations

Hriday Bavle1, Jose Luis Sanchez-Lopez1, Muhammad Shaheer1,
Javier Civera2 and Holger Voos1 *This work was partially funded by the Fonds
National de la Recherche of Luxembourg (FNR), under the projects
C19/IS/13713801/5G-Sky, by a partnership between the Interdisciplinary Center
for Security Reliability and Trust (SnT) of the University of Luxembourg and
Stugalux Construction S.A., by the Spanish Government under Grant
PID2021-127685NB-I00 and by the Aragón Government under Grant DGA T45 17R/FSE.
For the purpose of Open Access, the author has applied a CC BY public
copyright license to any Author Accepted Manuscript version arising from this
submission.1Authors are with the Automation and Robotics Research Group,
Interdisciplinary Centre for Security, Reliability and Trust, University of
Luxembourg. Holger Voos is also associated with the Faculty of Science,
Technology and Medicine, University of Luxembourg, Luxembourg. {hriday.bavle,
joseluis.sanchezlopez, muhammad.shaheer<EMAIL_ADDRESS>is with
I3A, Universidad de Zaragoza, Spain<EMAIL_ADDRESS>
###### Abstract

In this paper, we present an evolved version of the Situational Graphs, which
jointly models in a single optimizable factor graph, a SLAM graph, as a set of
robot keyframes, containing its associated measurements and robot poses, and a
3D scene graph, as a high-level representation of the environment that encodes
its different geometric elements with semantic attributes and the relational
information between those elements.

Our proposed S-Graphs+ is a novel four-layered factor graph that includes: (1)
a keyframes layer with robot pose estimates, (2) a walls layer representing
wall surfaces, (3) a rooms layer encompassing sets of wall planes, and (4) a
floors layer gathering the rooms within a given floor level. The above graph
is optimized in real-time to obtain a robust and accurate estimate of the
robot’s pose and its map, simultaneously constructing and leveraging the high-
level information of the environment. To extract such high-level information,
we present novel room and floor segmentation algorithms utilizing the mapped
wall planes and free-space clusters.

We tested S-Graphs+ on multiple datasets including, simulations of distinct
indoor environments, on real datasets captured over several construction sites
and office environments, and on a real public dataset of indoor office
environments. S-Graphs+ outperforms relevant baselines in the majority of the
datasets while extending the robot situational awareness by a four-layered
scene model. Moreover, we make the algorithm available as a docker file.

Project web: https://snt-arg.github.io/s_graphs_docker/

##  I Introduction

Robots require a deep understanding of the situation for their autonomous and
intelligent operations. Works like [1], [2], [3], [4] generate 3D scene graphs
modeling the environment with high-level semantic abstractions (such as
chairs, tables, or walls) and their relationships (such as a set of walls
forming a room or a corridor). While providing a rich understanding of the
scene, they rely on separate SLAM methods, such as [5], [6], [7], that
previously estimate the robot’s pose and its map using metric/semantic
representations without exploiting this hierarchical high-level information of
the environment. Thus in general, there exists a loose coupling between 3D
scene graphs and the underlying SLAM graphs.

Our previous work S-Graphs [8] bridges this gap proposing for the first time a
tightly coupled geometric LiDAR SLAM with 3D scene graphs, demonstrating
state-of-the-art metrics. However, the performance of S-Graphs is limited in
complex environments, due to its loosely-coupled factors of walls and rooms,
the influence of its multiple hand-tuned parameters for room extraction, and
the lack of higher-level abstractions other than rooms.

Figure 1: S-Graph+ built using a legged robot (circled in black) as it
navigates a real construction site consisting of four adjacent houses. (a) 3D
view of the four-layered hierarchical optimizable graph. The zoomed-in image
shows a partial view of the free-space clusters utilized for room
segmentation. (b) Top view of the graph.

To overcome these limitations, we present S-Graphs+, with updated front-end
and back-ends relying on 3D LiDAR measurements. The new front-end includes (1)
a novel room segmentation algorithm using free-space clusters and wall planes.
We define two- and four-walled rooms, corresponding to corridors and squarish
rooms respectively. (2) a floor segmentation algorithm extracting the floor
centers using all the currently extracted wall planes.

Its back-end consists of a real-time optimizable factor graph composed of four
layers. A keyframes layer constraining a sub-set of robot poses at specific
distance-time intervals. A walls layer constraining of the wall plane
parameters and linked to the keyframes using pose-plane constraints. A rooms
layer modeling detected rooms to its corresponding wall planes. The highest-
level layer of the graph, the floors layer, denotes the current floor level in
the graph and constrains the rooms at that level. See Fig. 1 for an
illustrative example of an S-Graph+ of a real building.

Our main contributions are, therefore, summarized as:

  * •

A novel real-time factor graph organized in four hierarchical layers.

  * •

A real-time extraction of high-level information using the novel room and
floor segmentation algorithms.

  * •

A thorough experimental evaluation in different simulated and real
construction/office environments as well as software release for the research
community.

##  II Related Works

###  II-A SLAM and Scene Graphs

The literature on LiDAR SLAM is huge, and there are several well known
geometric approaches like LOAM [5] and its variants [6], [9], [10], and also
semantic ones like LeGO-LOAM [7], SegMap [11], SUMA++ [12] that provide robust
and accurate localization and 3D maps of the environments. However, geometric
SLAM lacks meaning in the representation of the environments, which causes
failures in aliased environments and limitations for high-level tasks or
human-robot interation. And its semantic SLAM counterpart lacks in most
occasions geometric accuracy and robustness, due among other to wrong matches
between the semantic elements and the absence of relational constraints
between them.

Scene graphs, on the other hand, model scenes as structured representations,
specifically in the form of a graph comprising objects, their attributes, and
the inter-relationships among them. This high-level representation has the
potential to boost several aspects in mapping, as for example the map
compacity or the robot understanding. Focusing on 3D scene graphs for
understanding, the pioneering work [1] creates an offline semi-autonomous
framework using object detections from RGB images, generating a multi-layered
hierarchical representation of the environment and its components, divided
mainly into layers of camera, objects, rooms, and building. [13] presents a
framework for generating a 3D scene graph using a sequence of images to verify
its applicability to visual questioning and answering and to task planning. 3D
SSG (Semantic Scene Graph) presents a learning method based on PointNet and
Graph Convolutions Networks (GCN) to semi-automatically generate graphs for 3D
scenes, while SceneGraphFusion [3] on the other hand, generate a real-time
incremental 3D scene graph using RGB-D sequences, accurately handling partial
and missed semantic data. 3D DSG (Dynamic Scene Graph) [14] extend the 3D
scene graph concept to environments with static parts and dynamic agents in an
offline manner, while Hydra [4], presents research in the direction of real-
time 3D scene graph generation as well as its optimization using loop closure
constraints. Approaches have also been presented such as [15] exploiting scene
graphs to efficiently generate a 3D scene. Though promising in terms of scene
representation and higher-level understanding, a major drawback of these
models is that they do not tightly couple the estimate of the scene graph with
the SLAM state, in order to simultaneously optimize them. They thus generate a
scene graph and a SLAM graph in an independent manner. Our previous work
S-Graphs [8] bridged this gap showcasing the potential of tightly coupling
SLAM graphs and scene graphs. However, for several reasons, it was limited to
simple structured environments. Our current work S-Graphs+ overcomes these
limitations generating a four-layered hierarchical optimizable graph while
simultaneously representing the environment as a 3D scene graph, able to
provide an excellent performance even in complex environments.

###  II-B Room Segmentation

For a robot to understand structured indoor environments, it is necessary to
first understand their basic components, such as walls, and their composition
into higher-level structures such as rooms. Hence, room identification and
segmentation is one of the critical tasks in S-Graphs+. In the literature,
different room segmentation techniques are presented over pre-generated maps
using 2D LiDARs [16, 17, 18]. Their performance is, however, degraded in
presence of clutter. While [19] presents a room segmentation approach based on
pre-generated 2D occupancy maps in cluttered indoor environments, it still
lacks real-time capabilities. Methods such as [20, 21, 22] perform
segmentation of indoor spaces into meaningful rooms, although they require a
pre-generated 3D map of the environment and cannot segment it in real-time.
Given the current state-of-the-art for room segmentation, there was a need to
develop a room segmentation algorithm capable of running in real-time as the
robot explores its environment, to simultaneously incorporate this high-level
information into the optimizable S-Graphs+.

##  III Overview

Figure 2: S-Graphs+ overview. Our inputs are the 3D LiDAR measurements and
robot odometry, which are pre-filtered and processed in the front-end to
extract wall planes, rooms, floor, and loop closures. Note the four-layered
S-Graph+, whose parameters are jointly optimized in the back-end.

The architecture of S-Graphs+ is illustrated in Fig. 2. Its pipeline can be
divided into six modules, and its estimates are referred to four frames: the
LiDAR frame $L_{t}$, the robot frame $R_{t}$, the odometry frame $O$, and the
map frame $M$. $L_{t}$ and $R_{t}$ are rigidly attached to the robot and then
depend on the time instant $t$, while $O$ and $M$ are fixed. The first module
receives the 3D LiDAR point cloud in frame $L_{t}$, which is pre-filtered and
downsampled. The second module estimates the robot odometry in frame $O$
either from LiDAR measurements or the robot encoders. Four additional font-end
modules generate the four-layered topological graph modelling the
understanding of the environment, namely: 1) The plane segmentation module,
segmenting and initializing wall planes in the map frame $M$ using the point
clouds at each keyframe. 2) The room segmentation module, generating first
free-space clusters from the robot poses and 3D LiDAR measurements, and then
using such clusters along with the mapped planes to detect room centers in
frame $M$. 3) The floor segmentation module, utilizes the information of all
the currently mapped walls to extract the center of the current floor level in
frame $M$. 4) Finally, the loop closure module, which utilizes a scan-matching
algorithm to recognize revisited places and correct the drift. We define the
global state as:

$\mathbf{s}=[\leftidx{{}^{M}}{\mathbf{x}}_{R_{1}},\ \ldots,\
\leftidx{{}^{M}}{\mathbf{x}}_{R_{T}},\
\leftidx{{}^{M}}{\boldsymbol{\pi}}_{1},\ \ldots,\
\leftidx{{}^{M}}{\boldsymbol{\pi}}_{P},\\\
\leftidx{{}^{M}}{\boldsymbol{\rho}}_{1},\ \ldots,\
\leftidx{{}^{M}}{\boldsymbol{\rho}}_{S},\
\leftidx{{}^{M}}{\boldsymbol{\kappa}}_{1},\ \ldots,\
\leftidx{{}^{M}}{\boldsymbol{\kappa}}_{K},\ \\\
\leftidx{{}^{M}}{\boldsymbol{\xi}}_{1},\ \ldots,\
\leftidx{{}^{M}}{\boldsymbol{\xi}}_{F},\
\leftidx{{}^{M}}{\mathbf{x}}_{O}]^{\top},$ (1)

where $\leftidx{{}^{M}}{\mathbf{x}}_{R_{t}}\in SE(3),\ t\in\\{1,\ldots,T\\}$
are the robot poses at $T$ selected keyframes,
$\leftidx{{}^{M}}{\boldsymbol{\pi}}_{i}\in\mathbb{P}^{3},\
i\in\\{1,\ldots,P\\}$ are the plane parameters of the $P$ wall planes in the
scene, $\leftidx{{}^{M}}{\boldsymbol{\rho}}_{j}\in\mathbb{R}^{2},\
j\in\\{1,\ldots,S\\}$ contains the parameters of the $S$ four-wall rooms and
$\leftidx{{}^{M}}{\boldsymbol{\kappa}}_{k}\in\mathbb{R}^{2},\
k\in\\{1,\ldots,K\\}$ the parameters of the $K$ two-wall rooms,
$\leftidx{{}^{M}}{\boldsymbol{\xi}}_{f}\in\mathbb{R}^{2},f\in\\{1,\ldots\,F\\}$
are the $F$ floors levels, and $\leftidx{{}^{M}}{\mathbf{x}}_{O}$ models the
drift between the odometry frame $O$ and the map frame $M$.

##  IV Front-End

###  IV-A Robot Odometry

S-Graphs+ is agnostic to the source of odometry, thus it can utilize odometry
from different sources. It can utilize odometry estimated either from 3D LiDAR
measurements or directly generated from encoders of the robotic platforms.

###  IV-B Wall Extraction

We use sequential RANSAC to detect and initialize wall planes. Compared to our
previous work [8], in which wall detection was done on a different thread
leading to missed planar detections, in S-Graphs+ we extract the wall planes
every time a new keyframe is registered. This results in efficient detection
and mapping of all the wall planes at a given time instant. Each wall plane
extracted at time $t$, $\leftidx{{}^{L_{t}}}{\boldsymbol{\pi}}$, is referred
to the LiDAR frame $L_{t}$, we need to convert it to its Closest Point (CP)
representation [8], and then to the map frame
$\leftidx{{}^{M}}{\boldsymbol{\pi}}$ using the estimated robot pose at time
$t$. The wall plane normals with their $\leftidx{{}^{M}}{{n}_{x}}$ or
$\leftidx{{}^{M}}{{n}_{y}}$ components greater than the
$\leftidx{{}^{M}}{{n}_{z}}$ component are classified as vertical planes.
Furthermore, normals where $\leftidx{{}^{M}}{{n}_{x}}$ is greater than
$\leftidx{{}^{M}}{{n}_{y}}$ are classified as $x$-plane normals, and otherwise
they are classified as $y$-plane normals. Finally, planes whose normals’
bigger component is $\leftidx{{}^{M}}{{n}_{z}}$ are classified as horizontal
planes or ground surfaces. After initializing each plane in the global map,
correspondences are searched for every subsequent plane observation. Data
association is performed using the Mahalanobis distance between each mapped
plane and the newly extracted ones.

###  IV-C Room Segmentation

Input: Free-space graph $\mathcal{G}$, generated using [23]

Output: Clustered sub-graphs $\mathcal{G}_{f_{i}},i\in\\{1,\ldots,N\\}$

1: Filter nodes far from obstacles: $\mathcal{G}_{f}\leftarrow\mathcal{G}$

for  _$v_{i}\in\boldsymbol{v}$ $\&$ $\boldsymbol{v}$ $\in$ $\mathcal{G}$_ do

if  _$v_{i}.distance >t_{\lambda}$_ then

$\boldsymbol{v}_{d}\leftarrow v_{i}$ $\&$ $\boldsymbol{e}_{d}\leftarrow
v_{i}.edges$

else

$\boldsymbol{v}_{f}\leftarrow v_{i}$ $\&$ $\boldsymbol{e}_{f}\leftarrow
v_{i}.edges$

end if

end for

$\mathcal{G}_{f}\leftarrow(\boldsymbol{v}_{f},\boldsymbol{e}_{f})$

2: Graph clustering by connectivity:
$\mathcal{G}_{f_{1}}\ldots\mathcal{G}_{f_{n}}\leftarrow\mathcal{G}_{f}$

$c\leftarrow 0$

for  _$v_{f_{i}}\in\boldsymbol{v}_{f}$_ do

$v_{f_{i}}.visited\leftarrow False$ $\&$ $v_{f_{i}}.cluster\leftarrow 0$

end for

Function  _visit( $v_{f}$)_:

if  _$v_{f_{i}}.visited=False$_ then

$v_{f_{i}}.visited\leftarrow True$

if  _$v_{f_{i}}.cluster=0$_ then

$c\leftarrow c+1$

$v_{f_{i}}.cluster\leftarrow c$ $\&$ $\mathcal{G}_{c}\leftarrow v_{f_{i}}$

end if

for  _$v_{f_{n}}\in v_{f_{i}}.neighbours$_ do

$v_{f_{n}}.cluster\leftarrow c$ $\&$ $visit(v_{f_{n}})$

end for

end if

return

for  _$v_{f_{i}}\in\boldsymbol{v}_{f}$_ do

$visit(v_{f_{i}})$

end for

3: Inclusion of deleted vertices and edges in the cluster:
$\mathcal{G}_{f_{i}}\leftarrow(\boldsymbol{v}_{d},\boldsymbol{e}_{d}$)

for  _$v_{d_{i}}\in\boldsymbol{v}_{d}$_ do

for  _$v_{n}\in v_{d_{i}}.neighbours$_ do

if  _$v_{n}\in\mathcal{G}_{f_{i}}$_ then

$c\leftarrow v_{n}.cluster$ $\&$
$\mathcal{G}_{f_{i}}\leftarrow(v_{d_{i}},e_{d_{i}})$

end if

end for

end for

Algorithm 1 Free-Space Clustering

In this work, we present a novel room segmentation strategy capable of
segmenting different room configurations in a structured indoor environment.
It consists on two steps, Free-Space Clustering and Room Extraction, and the
output are the parameters of four-wall and two-wall rooms. All this is
explained in the next paragraphs.

Free-Space Clustering. Our free-space clustering algorithm divides the Free-
Space Graph of a scene into several clusters that should correspond to the
rooms of that scene. We first generate a complete sparse connected graph of
free spaces using [23], given the robot poses and a Euclidean Signed Distance
Field (ESDF) representation [24]. We then cluster this free-space graph into
different free-space regions as follows. Given the graph $\mathcal{G}$, we
create a filtered graph $\mathcal{G}_{f}$ removing the vertices
$\boldsymbol{v}_{d}$ whose distance to obstacles is greater than a given
threshold $t_{\lambda}$. We also remove from $\mathcal{G}_{f}$ all the edges
$\boldsymbol{e}_{d}$ that are connected to the node set $\boldsymbol{v}_{d}$.
We then run the connected components method [25] on $\mathcal{G}_{f}$ to
divide it into several connected sub-graphs
$\mathcal{G}_{f_{i}},i\in\\{1,\ldots,N\\}$. In order to re-connect the deleted
vertices $\boldsymbol{v}_{d}$ and their edges $\boldsymbol{e}_{d}$ to the
filtered sub-graphs $\mathcal{G}_{f_{i}}$, we check within the entire graph
$\mathcal{G}$, each edge $e_{d_{i}}$ that connects vertex $v_{f_{i}}$ of a
filtered sub-graph $\mathcal{G}_{f_{i}}$ to the deleted vertex $v_{d_{i}}$,
thus inserting vertex $v_{d_{i}}$ within $\mathcal{G}_{f_{i}}$. Using this
technique we can obtain disconnected free-space clusters belonging to
different rooms as vertices close to room openings have distances closer to
walls (obstacles) and thus vote for disconnecting the graph. Algorithm. 1 and
Fig. 3 give further details on this free-space clustering.

Room Extraction. Room extraction uses the free-space clusters
$\mathcal{G}_{f_{i}}$ and the wall planes from a keyframe at time $t$ to
detect different room configurations. Wall planes are represented in the map
frame as
$\leftidx{{}^{M}}{\boldsymbol{\Pi}}=[\leftidx{{}^{M}}{\boldsymbol{\pi}_{i}},\ldots,\leftidx{{}^{M}}{\boldsymbol{\pi}_{j}}]$,
where each plane
$\leftidx{{}^{M}}{\boldsymbol{\pi}_{i}}=[\leftidx{{}^{M}}{\boldsymbol{n}},\leftidx{{}^{M}}{d}]$
is defined by its normal
$\leftidx{{}^{M}}{\boldsymbol{n}}=[\leftidx{{}^{M}}{n_{x}},\leftidx{{}^{M}}{n_{y}},\leftidx{{}^{M}}{n_{z}}]$
and distance $\leftidx{{}^{M}}{d}$ to the origin. All extracted wall planes
are first categorized as $x$-direction planes
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{x}}$, for which their highest normal
component is $n_{x}$, and $y$-direction planes
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{y}}$ for which the highest normal
dimension is $n_{y}$. $\leftidx{{}^{M}}{\boldsymbol{\Pi}_{x}}$ plane are
further classified as $\leftidx{{}^{M}}{\boldsymbol{\Pi}_{x_{a}}}$, with
$n_{x}>0$, and $\leftidx{{}^{M}}{\boldsymbol{\Pi}_{x_{b}}}$ with $n_{x}<0$.
Analogously $\leftidx{{}^{M}}{\boldsymbol{\Pi}_{y_{a}}}$ and
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{y_{b}}}$ represent $y$-planes with
positive and negative $n_{y}$ respectively.

Given each sub-category of the wall planes, our room extraction method first
checks the $L2$ norm between the 3D points of each plane and the vertices of
each cluster $\mathcal{G}_{f_{i}}$, to find the set of walls lying closer to
each specific cluster.

Four-Wall Rooms. For a given cluster $\mathcal{G}_{f_{i}}$, if the room
extraction module finds a set of four wall planes
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{s}}=[\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{b_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{b_{2}}}}]$
close to the cluster vertices, it is considered as a four-wall room candidate
and further tests are carried out. First, the widths $w_{x}$ and $w_{y}$ of
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{x}}=\\{\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{b_{1}}}}\\}$
and
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{y}}=\\{\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{b_{1}}}}\\}$
should be greater than a given threshold $t_{w}$, where

$\displaystyle
w_{x}=\big{[}\lvert{\leftidx{{}^{M}}{d}_{x_{a_{1}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}}_{x_{a_{1}}}-{\lvert\leftidx{{}^{M}}{d}_{x_{b_{1}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}}_{x_{b_{1}}}\big{]}$
$\displaystyle
w_{y}=\big{[}\lvert{\leftidx{{}^{M}}{d}_{y_{a_{1}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}}_{y_{a_{1}}}-{\lvert\leftidx{{}^{M}}{d}_{y_{b_{1}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}}_{y_{b_{1}}}\big{]}$
(2)

$\leftidx{{}^{M}}d_{x_{a_{1}}}$ and $\leftidx{{}^{M}}d_{x_{b_{1}}}$ are the
plane distances to the origin and $\leftidx{{}^{M}}{\mathbf{n}_{x_{a_{1}}}}$
and $\leftidx{{}^{M}}{\mathbf{n}_{x_{b_{1}}}}$ are the normals of $x$-planes.
Similarly, $\leftidx{{}^{M}}{d_{y_{a_{1}}}}$,
$\leftidx{{}^{M}}{d_{y{b_{1}}}}$, $\leftidx{{}^{M}}{\mathbf{n}_{y_{a_{1}}}}$
and $\leftidx{{}^{M}}{\mathbf{n}_{y_{b_{1}}}}$ are the distances and normals
for in $y$-planes. For Eq. 2 to hold true,
$\lvert{\leftidx{{}^{M}}{d}_{x_{a_{1}}}\rvert}>\lvert{\leftidx{{}^{M}}{d}_{x_{b_{1}}}\rvert}$
and
$\lvert{\leftidx{{}^{M}}{d}_{y_{a_{1}}}\rvert}>\lvert{\leftidx{{}^{M}}{d}_{y_{b_{1}}}\rvert}$.
All plane normals are converted to point away from the map $M$ frame as:

$\leftidx{{}^{M}}{\mathbf{n}}=\begin{cases}-1\cdot\leftidx{{}^{M}}{\mathbf{n}}&\text{if
$\leftidx{{}^{M}}{d}>0$}\\\
\leftidx{{}^{M}}{\mathbf{n}}&\text{otherwise}\end{cases}$ (3)

If the above test is successful, the 3D points in each wall are checked to be
enclosed within the two apposed walls. For example, in-plane points belonging
to $\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{1}}}}$ are checked to lie within
the points of $\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{a_{1}}}}$ and
$\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{b_{1}}}}$. Given a room candidate with
a planar set $\leftidx{{}^{M}}{\boldsymbol{\Pi}_{s}}$ consisting of four
walls, we first calculate the room center as follows:

$\leftidx{{}^{M}}{\mathbf{r}_{x_{i}}}=\frac{1}{2}\big{[}\lvert{\leftidx{{}^{M}}{d_{x_{a_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{a_{1}}}}-{\lvert\leftidx{{}^{M}}{d_{x_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{b_{1}}}}\big{]}+\lvert{\leftidx{{}^{M}}{d_{x_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{b_{1}}}}$

$\leftidx{{}^{M}}{\mathbf{r}_{y_{i}}}=\frac{1}{2}\big{[}\lvert{\leftidx{{}^{M}}{d_{y_{a_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{y_{a_{1}}}}-{\lvert\leftidx{{}^{M}}{d_{y_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{y_{b_{1}}}}\big{]}+\lvert{\leftidx{{}^{M}}{d_{y_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{y_{b_{1}}}}$

$\displaystyle\leftidx{{}^{M}}{\boldsymbol{\rho}_{i}}=\leftidx{{}^{M}}{\boldsymbol{r}_{x_{i}}}+\leftidx{{}^{M}}{\boldsymbol{r}_{y_{i}}}$
(4)

Figure 3: Free space clustering and rooms segmentation, obtained from the
estimated wall planes surrounding each cluster. Pink colored squares represent
a four-wall room, while yellow and green colored squares represent two-wall
rooms in $x$ and $y$ directions respectively. Nodes colored in black are those
that are closest to walls and vote for splitting the graph.

Eq. 4 holds true when $\lvert d_{x_{1}}\rvert>\lvert d_{x_{2}}\rvert$. Again,
all planes are converted to point away from the origin $M$ using Eq. 3.

Data association for the room node follows two steps. First, the $L2$ norm
between the positions of the mapped rooms with the newly detected ones is
calculated. Second, the shortlisted rooms using the first step undergo further
checks at each wall plane. The $id$ of each wall plane comprised by the newly
detected room is checked with the wall planes of the mapped room. In case of
$id$ mismatch, Mahalanobis distance between wall planes constituting the wall
planes is checked. If all wall planes are matched a detected room is matched.
This process allows for the identification and merging of duplicate wall
planes ($id$ mismatch) for a given room, arising from inaccuracies in the wall
plane matching step (Section. IV-B) as the room and its respective wall plane
matching thresholds can be safely tuned to be larger than the single wall
plane matching threshold.

Two-Wall Rooms. The room extraction method is sometimes able to find only two
walls that surround a free-space cluster $\mathcal{G}_{f_{i}}$. These two-wall
rooms can be rooms with some undetected walls or corridor-like structures. If
a wall plane set
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{s}}=[\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{b_{1}}}}]$
contains two $x$-planes then it is a two-wall room in $x$ direction.
Analogously, two-wall rooms in the $y$ direction are composed of opposed
$y$-planes. Walls forming two-wall rooms undergo the same checks as four-wall
rooms, shown in equations 3 and 2. Given the missing information, in addition
to the wall planes, the corresponding center
$\leftidx{{}^{M}}{\boldsymbol{c}_{i}}$ of the cluster $\mathcal{G}_{f_{i}}$ is
utilized to compute the two-wall room center as follows:

$\leftidx{{}^{M}}{\mathbf{r}_{x_{i}}}=\frac{1}{2}\big{[}\lvert{\leftidx{{}^{M}}{d_{x_{a_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{a_{1}}}}-{\lvert\leftidx{{}^{M}}{d_{x_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{b_{1}}}}\big{]}+\lvert\leftidx{{}^{M}}{{d_{x_{b_{1}}}}\rvert}\cdot\leftidx{{}^{M}}{\mathbf{n}_{x_{b_{1}}}}$

$\displaystyle\leftidx{{}^{M}}{\boldsymbol{\kappa}_{x_{i}}}=\leftidx{{}^{M}}{\mathbf{r}_{x_{i}}}+\big{[}\leftidx{{}^{M}}{\mathbf{c}_{i}}-[\
\leftidx{{}^{M}}{\mathbf{c}_{i}}\cdot\leftidx{{}^{M}}{\hat{\mathbf{r}}_{x_{i}}}]\
\cdot\hat{\leftidx{{}^{M}}{\mathbf{r}}_{x_{i}}}\big{]}$ (5)

where $\leftidx{{}^{M}}{\boldsymbol{\kappa}_{x_{i}}}$ is the two-wall room
center in $x$ direction,
$\leftidx{{}^{M}}{\hat{\mathbf{r}}_{x_{i}}}=\leftidx{{}^{M}}{\mathbf{r}_{x_{i}}}/\|\leftidx{{}^{M}}{\mathbf{r}_{x_{i}}}\|$,
and $\leftidx{{}^{M}}{\boldsymbol{c}_{i}}$ is the cluster center obtained from
the endpoints of the cluster $\mathcal{G}_{f_{i}}$ as:

$\displaystyle\leftidx{{}^{M}}{{c}}_{x_{i}}=\frac{1}{2}\big{[}\leftidx{{}^{M}}{p}_{x_{1}}-\leftidx{{}^{M}}{p}_{x_{2}}\big{]}+\leftidx{{}^{M}}{p}_{x_{2}}$
$\displaystyle\leftidx{{}^{M}}{{c}_{y_{i}}}=\frac{1}{2}\big{[}\leftidx{{}^{M}}{p}_{y_{1}}-\leftidx{{}^{M}}{p}_{y_{2}}\big{]}+\leftidx{{}^{M}}{p}_{y_{2}}$
$\displaystyle\leftidx{{}^{M}}{\mathbf{c}_{i}}=\big{[}\leftidx{{}^{M}}{c_{x_{i}}},\leftidx{{}^{M}}{c_{y_{i}}}\big{]}$
(6)

where $\leftidx{{}^{M}}{p}_{x_{1}}$ to $\leftidx{{}^{M}}{p}_{y_{2}}$ are the
cluster endpoints. Two-wall room center in $y$ direction can be calculated
analogously.

Data association of two-wall rooms follows a similar concept as four-wall
rooms. In the case of a two-wall room in the $x$ direction, we first compute
the $L2$ norm along the $x$-axis of the two-wall room center followed by the
$id$ check of individual wall planes comprising the two-wall room. In case of
$id$ mismatch, $L2$ norm of the planar points between the detected and the
mapped wall planes is computed. A new two-wall room is created in case either
of the matching distances is greater than the threshold and as in the case of
four-wall rooms, this procedure allows for the identification of duplication
wall planes. Both the detected four and two-wall rooms are optimized along
with their corresponding wall planes in the back-end explained in Section. V.

###  IV-D Floor Segmentation

The floor segmentation module extracts the widest wall planes within the
current explored floor level by the robot which can then be used to calculate
the center of the current floor level. Our floor segmentation utilizes the
information from all mapped walls to create a sub-category of wall planes as
described in the room segmentation (Section. IV-C) as,
$\leftidx{{}^{M}}{\boldsymbol{\Pi}_{s_{t}}}$ where $t=\\{1,\ldots,T\\}$. After
receiving a complete plane set it computes the widths $\boldsymbol{w}_{x}$
between all $x$-direction planes and similarly $\boldsymbol{w}_{y}$ for
$y$-direction planes using Eq. 2. The wall plane set with the largest $w_{x}$
and $w_{y}$ is the chosen candidate for the current floor level. These planar
pairs in both $x$ and $y$ direction undergo an additional dot product check
between their corresponding normal orientations,
$|\mathbf{n}_{x_{a_{1}}}\cdot\mathbf{n}_{x_{b_{1}}}|<t_{n}$ and
$|\mathbf{n}_{y_{a_{1}}}\cdot\mathbf{n}_{y_{b_{1}}}|<t_{n}$, to remove wall
planes originating outside the building structure. The floor segmentation
computes the floor center node using the obtained wall plane candidates
following Eq. 4. Whenever the robot ascends or descends to a different floor
level, the newly mapped wall planes are incorporated with the new floor, and
the current floor level is computed only using the wall planes with the same
floor.

###  IV-E Loop Closure

As in [8], room detections provide “soft” loop closure constraints when the
robot revisits previously mapped rooms, while a scan matching-based “hard”
loop closure method add constraints on the relative pose of neighboring
keyframes.

##  V Back-End

The back-end is responsible for creating and optimizing the four layered
S-Graph+, which is explained in detail as follows.

Keyframes. This layer creates a factor node
$\leftidx{{}^{M}}{\boldsymbol{x}}_{R_{t}}\in SE(3)$ with the robot keyframe
pose at time $t$ in the map frame $M$. The pose nodes are constrained by
pairwise odometry readings between consecutive poses as in [8].

Walls. This layer creates the planar factor nodes for the wall planes
extracted by the wall segmentation (Section. IV-B). The planar nodes are
factored as
$\leftidx{{}^{M}}{\boldsymbol{\pi}}=[\leftidx{{}^{M}}\phi,\leftidx{{}^{M}}\theta,\leftidx{{}^{M}}d]$,
where $\leftidx{{}^{M}}\phi$ and $\leftidx{{}^{M}}\theta$ stand for the
azimuth and elevation of the plane in frame $M$. The planar nodes are
constrained with their corresponding keyframes using pose-plane constraints as
in [8]. The room segmentation module utilizes mapped walls at current keyframe
$k_{t}$ (Section. IV-C) to identify different room candidates, whereas mapped
walls from all the mapped keyframes $\boldsymbol{k}=\\{k_{1},\ldots,k_{T}\\}$
are utilized by the floor segmentation module (Section. IV-D) to identify the
center of the floor level.

Rooms. The rooms layer receives the extracted room candidates and their
corresponding wall planes from the room segmentation module (Section IV-C) to
create appropriate constraints between them.

Four-Wall Rooms: We propose a novel edge formulation between the detected room
node (generated from its center) and its four mapped wall planes, where the
total cost function to minimize the room node and its plane set can be given
as:

$c_{\boldsymbol{\rho}}(\leftidx{{}^{M}}{\boldsymbol{\rho}},\big{[}\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{i}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{b_{i}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{a_{i}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{b_{i}}}}\big{]})\\\
=\sum_{t=1,i=1}^{T,S}\|\leftidx{{}^{M}}{\hat{\boldsymbol{\rho}}_{i}}-{{f(\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{a_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{b_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{y_{a_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{y_{b_{i}}}})}}\|^{2}_{\mathbf{\Lambda}_{\boldsymbol{\tilde{\boldsymbol{\rho}}}_{i,t}}}$
(7)

Where $\leftidx{{}^{M}}{\hat{\boldsymbol{\rho}}_{i}}$ is the estimated four-
wall room center obtained from Section. IV-C and
$f(\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{a_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{b_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{y_{a_{i}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{y_{b_{i}}}})$
is the function mapping the four wall planes estimated to a four-wall room
center using Eq. 4. The goal of this cost function is to maintain the
structural consistency between the four planes forming the room.

Two-Wall Rooms: We propose a similar cost function to minimize room nodes and
their two corresponding wall planes as follows:

$c_{\boldsymbol{\kappa}}(\leftidx{{}^{M}}{\boldsymbol{\kappa}_{i}},\big{[}\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{a_{1}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{x_{b_{1}}}},\leftidx{{}^{M}}{\textbf{c}_{i}}\big{]})\\\
=\sum_{t=1,i=1}^{T,K}\|\leftidx{{}^{M}}{\hat{\boldsymbol{\kappa}}_{i}}-f(\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{a_{1}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{b_{1}}}},\leftidx{{}^{M}}{\textbf{c}_{i}})\|^{2}_{\mathbf{\Lambda}_{\boldsymbol{\tilde{\boldsymbol{\kappa}}}_{i,t}}}$
(8)

$\leftidx{{}^{M}}{\textbf{c}_{i}}$ is the cluster center, which is kept
constant during the optimization, and
$\leftidx{{}^{M}}{\hat{\boldsymbol{\kappa}}_{i}}$ is the estimated two-wall
room center in $x$ direction obtained from Section. IV-C.
$f(\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{a_{1}}}},\leftidx{{}^{M}}{\tilde{\boldsymbol{\pi}}_{x_{b_{1}}}},\leftidx{{}^{M}}{\textbf{c}_{i}})$
maps the two wall planes and its cluster center to a room center using Eq. 5.
The cost function to minimize two-wall rooms in $y$ direction follows Eq. 8
for wall planes
$(\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{a_{j}}}},\leftidx{{}^{M}}{\boldsymbol{\pi}_{y_{b_{j}}}})$
and cluster center $\leftidx{{}^{M}}{\textbf{c}_{j}}$. Duplicate wall plane
nodes identified during the four-wall or two-wall room segmentation are
constrained by a factor minimizing the difference between their respective
parameters.

Floors. The floor node consists of the center of the current floor level
calculated from the floor segmentation (Section. IV-D). We add a cost function
between the floor node and all the mapped four-wall rooms at that floor level
as follows:

$c_{\xi}(\leftidx{{}^{M}}{\boldsymbol{\xi_{i}}},\leftidx{{}^{M}}{\boldsymbol{\rho}_{i}})=\sum_{t=1,i=1,j=1}^{T,F,S}\|\leftidx{{}^{M}}{\hat{\boldsymbol{\delta}}_{{\xi_{i}},{\rho_{j}}}}-f(\leftidx{{}^{M}}{\boldsymbol{\xi_{i}}},\leftidx{{}^{M}}{\boldsymbol{\rho}_{j}})\|^{2}_{\mathbf{\Lambda}_{\boldsymbol{\tilde{\boldsymbol{\xi}}}_{i,t}}}$
(9)

where $\leftidx{{}^{M}}{\hat{\boldsymbol{\delta}}_{{\xi_{i}},{\rho_{j}}}}$
stands for the relative distance between the floor $i$ with center
${\boldsymbol{\xi_{i}}}$ and the four-wall room $j$ with center
$\boldsymbol{\rho}_{j}$, and
$f(\leftidx{{}^{M}}{\boldsymbol{\xi_{i}}},\leftidx{{}^{M}}{\boldsymbol{\rho}_{j}})$
maps the relative distance between the centers of floor node and four-wall
room node. Two-wall room nodes are constrained with the floor node using the
same Eq. 9. While the robot navigates in the surroundings and discovers new
wall planes, the estimate of the floor node might change due to the insertion
of such planes into the map. If the current floor center calculated from the
new wall planes gets updated beyond a threshold $t_{f}$, the estimate of the
floor node is updated in the graph accordingly along with the relative
distances between the floors and all the rooms.

##  VI Experimental Results

(a) S-Graphs+

(b) HDL-SLAM

(c) ALOAM

(d) FLOAM

Figure 4: Maps by S-Graphs+ and baselines, in-house seq. C4F0.

###  VI-A Methodology

We validate S-Graphs+ on simulated and real-world scenarios, comparing it
against several state-of-the-art LiDAR SLAM frameworks and the baseline
S-Graphs. The experiments cover a wide array of scenes, from construction
sites to office spaces, and use data recorded in-house and from the public
TIERS dataset. We report standard error metrics for the map and trajectory
estimations (RMSE and ATE) as well as qualitative results. For comparing the
room detection of S-Graphs+ against the heuristics in S-Graphs, we report the
precision and recall of the four-walled and two-walled room detections in the
simulated environments, for which we have the ground truth number of rooms
defined in the architectural plans.

Simulated Data. We conduct a total of five simulated experiments. Two of them,
CF1 and CF2, are generated from the 3D meshes of two floors of actual
architectural plans. The other three, SE1, SE2, and SE3, are performed in
additional simulated environments resembling typical indoor environments with
different room configurations. Due to absence of odometry from robot encoders,
in all simulated experiments the odometry is estimated only from LiDAR
measurements. For a fair validation, S-Graphs+ is run using two different
odometry inputs, specifically VGICP [26] and FLOAM [6].

TABLE I: Absolute Trajectory Error (ATE) [m], of S-Graph+ and relevant baselines on simulated data. Best results are boldfaced, second best are underlined. Method | Dataset |
---|---|---
Mapping | Odometry | C1F0 | C1F2 | SE1 | SE2 | SE3
HDL-SLAM [10] |  VGICP [26] | 0.15 | 0.02 | 0.04 | 0.15 | 0.14
ALOAM [5] | ALOAM | 0.10 | 0.09 | 0.16 | 0.32 | 0.20
MLOAM [9] | MLOAM | 1.14 | 0.52 | 0.65 | 2.82 | 0.17
FLOAM [6] | FLOAM | 0.11 | 0.15 | 0.15 | 0.24 | 0.76
LeGO-LOAM [7] | LeGO-LOAM | - | - | - | - | 0.73
S-Graphs [8] | VGICP | 0.07 | 0.02 | 0.03 | 0.17 | 0.33
S-Graphs+ (ours) | VGICP | 0.08 | 0.01 | 0.02 | 0.12 | 0.05
S-Graphs+ (ours) | FLOAM | 0.05 | 0.03 | 0.15 | 0.14 | 0.12

In-House Dataset. In all our in-house data we utilize the robot encoders for
estimating the odometry. The first two experiments, denoted as C1F1 and C1F2,
are performed on two floors of a construction site consisting of a single
house. Additionally, experiments are performed over larger construction sites
combining several houses. C2F0, C2F1, and C2F2 consist of three floors of an
ongoing construction site combining four individual houses. C3F1, and C3F2 are
two combined houses, while C4F0 is a basement area with different storage
rooms. LC1 consists of an office environment in which the robot traverses back
and forth a long corridor. To validate the accuracy of each method in all the
real experiments we report the RMSE of the estimated 3D maps against the
actual 3D map generated from the architectural plan except for experiment
C4F0, for which we provide qualitative results due to the absence of a ground
truth plan.

TABLE II: Point cloud RMSE [m] for our in-house real sequences. All methods use odometry from robot encoders. Best results are boldfaced, second best underlined. | Dataset |  |  |  |  |  |
---|---|---|---|---|---|---|---
Method | Point Cloud RMSE |  |  |  |  |
Mapping | C1F1 | C1F2 | C2F0 | C2F1 | C2F2 | C3F1 | C3F2 | LC1
HDL-SLAM [10] | 1.34 | 0.37 | 0.26 | 0.46 | 0.26 | 1.41 | 1.08 | 1.45
ALOAM [5] | 8.03 | 1.20 | 0.31 | 0.43 | 0.57 | 0.57 | 0.58 | 3.14
MLOAM [9] | 3.73 | 1.93 | 0.34 | 0.61 | 0.51 | - | 0.37 | 1.68
FLOAM [6] | 7.63 | 1.15 | 0.46 | 0.74 | 0.35 | 1.66 | 0.41 | 2.90
LeGO-LOAM [7] | 4.08 | 0.70 | 0.46 | 0.48 | 0.53 | 0.32 | 0.52 | 3.40
S-Graphs [8] | 0.33 | 0.37 | 0.30 | 0.48 | 0.50 | 0.41 | 0.29 | 1.24
S-Graphs+ (ours) | 0.31 | 0.33 | 0.17 | 0.46 | 0.13 | 0.39 | 0.32 | 1.27
TABLE III: Absolute Trajectory Error (ATE) [m], of S-Graph+ and relevant baselines on the TIERS dataset [27]. Best results boldfaced, second best underlined. Method |  | Dataset |
---|---|---|---
Mapping | Odometry | T6 | T7 | T8 | T10 | T11
HDL-SLAM [10] |  VGICP [26] | 0.26 | 0.29 | 0.34 | 1.42 | 2.98
ALOAM |  ALOAM [5] | 0.26 | 0.27 | 0.34 | 0.76 | 2.29
MLOAM |  MLOAM [9] | 0.26 | 0.26 | 0.35 | 3.27 | 0.92
FLOAM |  FLOAM[6] | 0.25 | 0.26 | 0.33 | 0.65 | 2.05
LeGO-LOAM |  LeGO-LOAM [7] | 0.27 | 0.33 | 0.38 | 1.49 | 0.80
S-Graphs [8] | VGICP | 0.26 | 0.28 | 0.37 | 1.41 | 1.41
S-Graphs+ (ours) | VGICP | 0.25 | 0.27 | 0.34 | 1.27 | 0.95
S-Graphs+ (ours) | FLOAM | 0.25 | 0.26 | 0.32 | 0.54 | 0.55

TIERS LiDARs dataset. We also validate S-Graphs+ on the public TIERS dataset
[27], recorded by a moving platform in a variety of scenarios. We show results
in the five indoor sequences of the dataset. Experiments T6 to T8 are done in
a single small room in which the platform does several passes at increasing
speeds. Experiments T10 and T11 are performed in a larger indoor hallway with
longer trajectories of the moving platform. We use the VLP-16 LiDAR data and
report the ATE against the provided ground truth. Due to the absence of
encoder readings in this dataset, each baseline method uses its own LiDAR-
based odometry. As in the simulated datasets, we validate S-Graphs+ with VGICP
and FLOAM odometry.

(a) S-Graphs+

(b) S-Graphs

Figure 5: S-Graphs+ and S-Graphs maps, in-house seq. C2F0.

###  VI-B Results and Discussion

Simulated Data. Table. I showcases the ATE for the simulated experiments. We
outperform S-Graphs [8] thanks to the new plane segmentation module, new rooms
factors and the new room segmentation algorithm. Experiments are sorted by
scene size, from left to right the scene size being larger. Note how the
baseline errors tend to grow for larger scenes, and how our S-Graphs+ achieves
bigger error reductions for larger scenes due to its better representation. It
can also be seen in Table. I how S-Graphs+ has been run using two odometry
methods, VGICP and FLOAM, and how it is able to improve the results of the two
odometries.

In-House Dataset. Table II presents the point cloud RMSE obtained by comparing
the generated 3D maps against the 3D maps from the building plans. As it can
be observed in the table, S-Graphs+ is more accurate than the baseline in most
of the cases. For experiment C4F0, Fig. 4 shows a top view of the final maps
estimated by S-Graphs+ and three other baselines. Observe the higher degree of
accuracy and cleaner map elements in the S-Graphs+ case, the latest indicating
a better alignment for different robot passes. Similarly, observe the precise
map generated by S-Graphs+ in Fig. 5 for experiment C2F0 when comparing with
S-Graphs, mainly due to the improved wall plane segmentation and improved
rooms-wall planes constraints. Fig. 1, shows the entire four-layered S-Graphs+
for C2F2 along with its map accuracy. In all the above experiments, no fine-
tuning of parameters of S-Graphs+ was required for room detection and the same
prior tuned parameters sufficed for all.

Figure 6: Map estimated by S-Graphs+ on TIERS sequence T11.

Figure 7: Precision and recall for S-Graphs+ (blue) and S-Graphs (red) on six
different scenes of our in-house dataset.

Fig. 7 presents the precision/recall of the room detection in S-Graphs+ (the
method described in Section IV-C) and the one in S-Graphs. Note how the
precision is slightly higher for S-Graphs+. More importantly, the recall is
clearly higher for S-Graphs, in particular for scenarios with complex layouts
such as C2F1. The latest is one of the main strengths of S-Graphs, extracting
a higher number of rooms adds a higher number of constraints leading to more
accurate estimates and a better representation.

TIERS LiDARs dataset. Table. III presents the ATE for all baseline methods and
our S-Graphs+ in the indoor sequences of the public TIERS dataset [27].
S-Graphs+ with FLOAM odometry gives the best results in all the experiments.
Again, the sequences are sorted from left to right by increasing size. Note
that all methods perform similarly for small scenes, but differ as scenes
become larger, S-Graphs+ presenting significant error reductions for large
environments. The strength of our hierarchical representation is particularly
evident in scenarios like T11, in which S-Graphs+ keeps the errors small even
if the FLOAM odometry error grows substantially. The accuracy of our method in
such sequence can be observed qualitatively in the top view of the estimated
map in Fig. 6.

##  VII Conclusion

In this work we present S-Graphs+, a novel four-layered hierarchical factor
graph composed of A keyframes layer constraining a sub-set of robot poses at
specific distance-time intervals. A walls layer constraining the wall plane
parameters and linking it to the keyframes. A rooms layer modeling detected
rooms to their corresponding wall planes and a floors layer, denoting the
current floor level in the graph and constraining the rooms at that level. To
extract this high-level information we also propose a novel room segmentation
algorithm using free-space clusters and wall planes and a floor segmentation
algorithm extracting the floor centers using all the currently extracted wall
planes. We demonstrate state-of-the-art results against several baselines on
simulated and real experiments covering different office and construction
indoor environments. In future work, we plan to exploit the hierarchical
structure of the graph for efficient and faster optimization as well as
enhance the reasoning over the graph for improving the detection of different
relationship constraints between its semantic elements.

## References

  * [1] I. Armeni, Z.-Y. He, J. Gwak, A. R. Zamir, M. Fischer, J. Malik, and S. Savarese, “3D Scene Graph: A structure for unified semantics, 3D space, and camera,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 5664–5673.
  * [2] A. Rosinol, A. Gupta, M. Abate, J. Shi, and L. Carlone, “3D dynamic scene graphs: Actionable spatial perception with places, objects, and humans,” _arXiv preprint arXiv:2002.06289_ , 2020.
  * [3] S.-C. Wu, J. Wald, K. Tateno, N. Navab, and F. Tombari, “SceneGraphFusion: Incremental 3D Scene Graph Prediction from RGB-D Sequences,” 2021. [Online]. Available: https://arxiv.org/abs/2103.14898
  * [4] N. Hughes, Y. Chang, and L. Carlone, “Hydra: A Real-time Spatial Perception Engine for 3D Scene Graph Construction and Optimization,” _arXiv preprint arXiv:2201.13360_ , 2022.
  * [5] J. Zhang and S. Singh, “LOAM: Lidar Odometry and Mapping in Real-time,” in _Robotics: Science and Systems_ , 2014.
  * [6] H. Wang, C. Wang, C. Chen, and L. Xie, “F-LOAM : Fast LiDAR Odometry and Mapping,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020.
  * [7] T. Shan and B. Englot, “LeGO-LOAM: Lightweight and Ground-Optimized Lidar Odometry and Mapping on Variable Terrain,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 4758–4765.
  * [8] H. Bavle, J. L. Sanchez-Lopez, M. Shaheer, J. Civera, and H. Voos, “Situational graphs for robot navigation in structured indoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9107–9114, 2022.
  * [9] J. Jiao, H. Ye, Y. Zhu, and M. Liu, “Robust Odometry and Mapping for Multi-LiDAR Systems With Online Extrinsic Calibration,” _IEEE Transactions on Robotics_ , pp. 1–10, 2021.
  * [10] K. Koide, J. Miura, and E. Menegatti, “A portable three-dimensional LIDAR-based system for long-term and wide-area people behavior measurement,” _International Journal of Advanced Robotic Systems_ , vol. 16, no. 2, Mar. 2019.
  * [11] R. Dubé , A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “SegMap: Segment-based mapping and localization using data-driven descriptors,” _The International Journal of Robotics Research_ , vol. 39, no. 2-3, pp. 339–355, jul 2019. [Online]. Available: https://doi.org/10.1177%2F0278364919863090
  * [12] X. Chen, A. Milioto, E. Palazzolo, P. Giguère, J. Behley, and C. Stachniss, “SuMa++: Efficient LiDAR-based Semantic SLAM,” in _Proceedings of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , 2019.
  * [13] U.-H. Kim, J.-M. Park, T. jin Song, and J.-H. Kim, “3-D Scene Graph: A Sparse and Semantic Representation of Physical Environments for Intelligent Agents,” _IEEE Transactions on Cybernetics_ , vol. 50, no. 12, pp. 4921–4933, dec 2020. [Online]. Available: https://doi.org/10.1109%2Ftcyb.2019.2931042
  * [14] A. Rosinol, A. Violette, M. Abate, N. Hughes, Y. Chang, J. Shi, A. Gupta, and L. Carlone, “Kimera: From SLAM to spatial perception with 3D dynamic scene graphs,” _The International Journal of Robotics Research_ , vol. 40, no. 12-14, pp. 1510–1546, 2021.
  * [15] H. Dhamo, F. Manhardt, N. Navab, and F. Tombari, “Graph-to-3D: End-to-End Generation and Manipulation of 3D Scenes Using Scene Graphs,” 2021. [Online]. Available: https://arxiv.org/abs/2108.08841
  * [16] R. Bormann, F. Jordan, W. Li, J. Hampp, and M. Hägele, “Room segmentation: Survey, implementation, and analysis,” _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 1019–1026, 2016.
  * [17] M. Mielle, M. Magnusson, and A. J. Lilienthal, “A method to segment maps from different modalities using free space layout maoris: Map of ripples segmentation,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 4993–4999.
  * [18] F. Foroughi, J. Wang, A. Nemati, Z. Chen, and H. Pei, “MapSegNet: A Fully Automated Model Based on the Encoder-Decoder Architecture for Indoor Map Segmentation,” _IEEE Access_ , vol. 9, pp. 101 530–101 542, 2021.
  * [19] M. Luperto, T. P. Kucner, A. Tassi, M. Magnusson, and F. Amigoni, “Robust structure identification and room segmentation of cluttered indoor environments from occupancy grid maps,” 2022. [Online]. Available: https://arxiv.org/abs/2203.03519
  * [20] I. Armeni, O. Sener, A. R. Zamir, H. Jiang, I. Brilakis, M. Fischer, and S. Savarese, “3D Semantic Parsing of Large-Scale Indoor Spaces,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 1534–1543.
  * [21] R. Ambruş, S. Claici, and A. Wendt, “Automatic Room Segmentation From Unstructured 3-D Data of Indoor Environments,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 749–756, 2017.
  * [22] S. Ochmann, R. Vock, and R. Klein, “Automatic reconstruction of fully volumetric 3D building models from oriented point clouds,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , vol. 151, pp. 251–262, 2019.
  * [23] H. Oleynikova, Z. Taylor, R. Siegwart, and J. Nieto, “Sparse 3D Topological Graphs for Micro-Aerial Vehicle Planning,” 2018. [Online]. Available: https://arxiv.org/abs/1803.04345
  * [24] H. Oleynikova, Z. Taylor, M. Fehr, R. Siegwart, and J. Nieto, “Voxblox: Incremental 3D Euclidean Signed Distance Fields for on-board MAV planning,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, sep 2017. [Online]. Available: https://doi.org/10.1109%2Firos.2017.8202315
  * [25] J. Clark and D. A. Holton, _A first look at graph theory_. World Scientific, 1991.
  * [26] K. Koide, M. Yokozuka, S. Oishi, and A. Banno, “Voxelized GICP for Fast and Accurate 3D Point Cloud Registration,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 11 054–11 059.
  * [27] Q. Li, X. Yu, J. P. Queralta, and T. Westerlund, “Multi-Modal LiDAR Dataset for Benchmarking General-Purpose Localization and Mapping Algorithms,” 2022\. [Online]. Available: https://arxiv.org/abs/2203.03454


1      & 1     & \cdot & \cdot & 1     & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
2      & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot \\
3      & \cdot & 1     & \cdot & \cdot & 1     & \cdot & 1     & \cdot & 1     & \cdot & \cdot & \cdot & \cdot \\
4      & \cdot & \cdot & 1     & \cdot & \cdot & 1     & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot
\CodeAfter
\begin{tikzpicture}
\node () [fit=(5-3) (5-3), draw=magenta!80!black, rounded corners] {};
\node () [fit=(5-6) (5-6), draw=magenta!80!black, rounded corners] {};
\node () [fit=(5-8) (5-11), draw=magenta!80!black, rounded corners] {};
\end{tikzpicture}
\end{pNiceArray}
\]

The injective resolution of $k_\Gamma$ and the derived pushforward $Rl_\ast k_\Gamma$. Here we provide the labeled matrices describing the injective resolution of $k_\Gamma$, and its pushforward $Rl_\ast k_\Gamma$. Note that no rows labeled by the simplices on the boundary – $45$, $46$, $56$, $4$, $5$, $6$ – appear in the injective resolution of $k_\Gamma$.

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{ccccccccc}
\lambda^0   & 013   & {\color{blue!80!black} 015}   & 034   & {\color{blue!80!black} 046}   & {\color{blue!80!black} 056}   & 123   & 124   & {\color{blue!80!black} 145}   & 234   \\
01          & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
03          & 1     & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
04          & \cdot & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot \\
{\color{blue!80!black} 05}          & \cdot & 1     & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & \cdot \\
{\color{blue!80!black} 06}          & \cdot & \cdot & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot \\
12          & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & 1     & \cdot & \cdot \\
13          & 1     & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & \cdot \\
14          & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & 1     & \cdot \\
{\color{blue!80!black} 15}          & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot \\
23          & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     \\
24          & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & 1     \\
34          & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & 1
\end{pNiceArray}
\]

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccccccccccc}
\lambda^1 & 01    & 03    & 04    & {\color{blue!80!black} 05}    & {\color{blue!80!black} 06}    & 12    & 13    & 14    & {\color{blue!80!black} 15}    & 23    & 24    & 34    \\
0         & 1     & 1     & 1     & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
1         & 1     & \cdot & \cdot & \cdot & \cdot & 1     & 1     & 1     & 1     & \cdot & \cdot & \cdot \\
2         & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & 1     & 1     & \cdot \\
3         & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     & \cdot & 1
\CodeAfter
\end{pNiceArray}
\]

To get the pushforward $Rl_\ast k_\Gamma$, we need to relabel the matrices according to $l$, and minimize. We highlighted in blue the labels that change. Recall that the map $l$ is defined on vertices by mapping $5,6\mapsto 4$ and other vertices identically.

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{ccccccccc}
\tilde\lambda^0   & 013   & {\color{blue!80!black} 014}   & 034   & {\color{blue!80!black} 04\phantom{0}}   & {\color{blue!80!black} 04\phantom{0}}   & 123   & 124   & {\color{blue!80!black} 14\phantom{0}}   & 234   \\
01          & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
03          & 1     & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
04          & \cdot & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot \\
{\color{blue!80!black} 04}          & \cdot & 1     & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & \cdot \\
{\color{blue!80!black} 04}          & \cdot & \cdot & \cdot & 1     & 1     & \cdot & \cdot & \cdot & \cdot \\
12          & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & 1     & \cdot & \cdot \\
13          & 1     & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & \cdot \\
14          & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & 1     & \cdot \\
{\color{blue!80!black} 14}          & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot \\
23          & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     \\
24          & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & 1     \\
34          & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & 1
\CodeAfter
\begin{tikzpicture}
\node () [fit=(3-4) (5-5), draw=blue!80!black, rounded corners] {};
\node () [fit=(8-8) (9-8), draw=red!80!black, rounded corners] {};
\end{tikzpicture}
\end{pNiceArray}
\]

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccccccccccc}
\tilde\lambda^1 & 01    & 03    & 04    & {\color{blue!80!black} 04}    & {\color{blue!80!black} 04}    & 12    & 13    & 14    & {\color{blue!80!black} 14}    & 23    & 24    & 34    \\
0         & 1     & 1     & 1     & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
1         & 1     & \cdot & \cdot & \cdot & \cdot & 1     & 1     & 1     & 1     & \cdot & \cdot & \cdot \\
2         & \cdot & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & \cdot & 1     & 1     & \cdot \\
3         & \cdot & 1     & \cdot & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     & \cdot & 1
\CodeAfter
\end{pNiceArray}
\]

We highlight the non-trivial 04- and 14-block in blue and red, respectively. Due to their ranks, we see we need to remove 2 columns and 2 rows from the blue 04-block, and 1 column and 1 row from the red 14-block. After the Gaussian elimination and deletion as described in Algorithm <ref>, we get the following matrices.

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccccc}
Rl_\ast\lambda^0   & 013   & 014   & 034   & 123   & 124   & 234   \\
01                 & 1     & 1     & \cdot & \cdot & \cdot & \cdot \\
03                 & 1     & \cdot & 1     & \cdot & \cdot & \cdot \\
04                 & \cdot & 1     & 1     & \cdot & \cdot & \cdot \\
12                 & \cdot & \cdot & \cdot & 1     & 1     & \cdot \\
13                 & 1     & \cdot & \cdot & 1     & \cdot & \cdot \\
14                 & \cdot & 1     & \cdot & \cdot & 1     & \cdot \\
23                 & \cdot & \cdot & \cdot & 1     & \cdot & 1     \\
24                 & \cdot & \cdot & \cdot & \cdot & 1     & 1     \\
34                 & \cdot & \cdot & 1     & \cdot & \cdot & 1
\CodeAfter
\end{pNiceArray}
\]

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{ccccccccc}
Rl_\ast\lambda^1 & 01    & 03    & 04    & 12    & 13    & 14    & 23    & 24    & 34    \\
0                & 1     & 1     & 1     & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
1                & 1     & \cdot & \cdot & 1     & 1     & 1     & \cdot & \cdot & \cdot \\
2                & \cdot & \cdot & \cdot & 1     & \cdot & \cdot & 1     & 1     & \cdot \\
3                & \cdot & 1     & \cdot & \cdot & 1     & \cdot & 1     & \cdot & 1
\end{pNiceArray}
\]

Now that we computed the derived push-forward of several maps, we have three examples of (complexes of) sheaves on the triangulation of the sphere. We will now use microlocal Morse theory to analyze these examples. First, we choose our analogue of a discrete Morse function: an order preserving map, $f$ (see Figure <ref>), from the face-relation poset of the triangulation of the sphere to the real line (or, more precisely, to a totally ordered set). We then compute which fibers lie in the discrete microsupport of each sheaf. For this example we choose $f$ to be an honest discrete Morse function in the sense of [14, 15] (see Figure <ref>). However, Theorem <ref> and Theorem <ref> make no assumptions on $f$ other than the requirement that it is order preserving.

Intervals in the discrete microsupport.
Giving a full list of all of the locally closed subsets of $\Lambda$ in the microsupport of $Rg_\ast k_\Sigma$ (or $Rh_\ast k_\Sigma$) is cumbersome and mostly unnecessary. In practice, we are mostly interested in the locally closed subsets which arise as fibers of a discrete Morse function (for example, the fibers of $f$). Below we will compute and visualize the intersection of $\mu\supp^! Rh_\ast k_\Sigma$ with several intervals of interest.

Entries in the tables mark (an incomplete list of) intervals in the microsupport. The rows correspond to three chosen simplicies, $\sigma$, and the columns correspond to each of the simplicies, $\tau$, in $\Lambda$. Each entry of the first table is given $\checkmark$ if $[\sigma,\tau]\in\mu\supp^! Rh_\ast k_\Sigma$, 55 if $[\sigma,\tau]\not\in\mu\supp^! Rh_\ast k_\Sigma$, and are left empty if $\sigma\not\le \tau$. Similarly, the second table gives the corresponding intervals for $\mu\supp^\ast Rh_\ast k_\Sigma$. Below the tables we visualize the intervals contained in the discrete microsupport. In the first row ((a), (b), and (c)) red arrows correspond to intervals $[\sigma,\tau]\coloneqq \{\gamma\in\Lambda:\sigma\le\gamma\le\tau\}$ (where $\sigma$ is the base of the arrow and $\tau$ is the head) contained in $\mu\supp^!Rh_\ast k_\Sigma$. In the second row ((d), (e), and (f)) red arrows correspond to intervals contained in $\mu\supp^\ast Rh_\ast k_\Sigma$. The first column ((a) and (d)) visualize intervals in the star of $0$, in the second column ((b) and (e)) the star of $1$, and in the third column ((c) and (f)) the star of $4$.

Critical elements.
Here we give a table of $(Rg_\ast k_\Sigma,f,\ast)$, $(Rg_\ast k_\Sigma,f,!)$, $(Rh_\ast k_\Sigma,f,\ast)$, $(Rh_\ast k_\Sigma,f,!)$, $(Rl_\ast k_\Gamma,f,\ast)$, and $(Rl_\ast k_\Gamma,f,!)$-critical elements of $\Pi$. Below we give more details of the four computations for the pair $B=\{4,24\}$. We fix $j:B \hookrightarrow \Lambda$ to be the inclusion map.

Entries in the table mark critical elements of the quotient poset $\Pi$, for various notions of critical corresponding to row labels.

Computing critical elements: $(Rg_\ast k_\Sigma,f,\ast)$. We check whether $B=\{4,24\}$ is in $\mu\supp^\ast Rg_\ast k_\Sigma$. By definition, this happens iff $\mathbb{H}^d \left(Rj_!R j^\ast Rg_\ast k_\Sigma\right)\neq 0$.

We first need to compute the pullback $Rj^\ast (Rg_\ast k_\Sigma)$ using Algorithm <ref> as described in Section <ref>. According to the algorithm, we copy $Rg_\ast\eta^0$ and $Rg_\ast\eta^1$ as $\gamma^{-1}$ and $\gamma^0$, viewing them as matrices labeled by the poset cylinder $\Lambda\sqcup_j B$, and then run the updating step from Algorithm <ref> for elements in $B$. It is, however, enough to only copy the parts above $B$ in $\Lambda\sqcup_j B$, i.e., the submatrices labeled by $\St 4$, which we highlighted in the matrices above. Altogether we get the following matrices $\gamma^d$, where one row was added to each of them in the updating step:

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccc}
\gamma^{-1} & 014_\Lambda & 034_\Lambda & 124_\Lambda & 234_\Lambda \\
04_\Lambda  & 1           & 1           & \cdot       & \cdot       \\
14_\Lambda  & 1           & \cdot       & 1           & \cdot       \\
24_\Lambda  & \cdot       & \cdot       & 1           & 1           \\
34_\Lambda  & \cdot       & 1           & \cdot       & 1           \\
4_\Lambda  & \cdot       & \cdot       & \cdot       & \cdot       \\ \hline
24_B        & \cdot       & \cdot       & 1           & \cdot
\end{pNiceArray}
\]

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{ccccc|c}
\gamma^0   & 04_\Lambda    & 14_\Lambda    & 24_\Lambda    & 34_\Lambda    & 4_\Lambda     & 24_B    \\
4_\Lambda  & 1             & 1             & 1             & 1             & \cdot         & \cdot   \\ \hline
4_B        & \cdot         & \cdot         & \cdot         & \cdot         & 1             & \,\cdot\,
\CodeAfter
\begin{tikzpicture}
\node () [fit=(2-6) (2-6), draw=blue!80!black] {};
\end{tikzpicture}
\end{pNiceArray}
\]

We only keep the highlighted submatrix $\gamma^0[B, B]$. It already represents a minimal complex of injective sheaves, and no further minimization is needed. Altogether, we have
\[
Rj^\ast (Rg_\ast k_\Sigma) = \cdots \rightarrow 0 \rightarrow [24] \xrightarrow{0} [4] \rightarrow 0 \rightarrow \cdots.
\]

Next, we need to compute proper pushforward $Rj_!(R j^\ast Rg_\ast k_\Sigma)$. The general construction is described by Algorithm <ref> in Section <ref>. We first copy the $1\times 1$ matrix from above, and then run the updating step for all elements in $\bar B\setminus B = \{2\}$. This forces us to add one row in the first matrix, but nothing else in the following. We get
\[
Rj_!(R j^\ast Rg_\ast k_\Sigma) = \cdots \rightarrow 0 \rightarrow [24] \xrightarrow{\footnotesize \begin{pmatrix}
0 \\
\end{pmatrix}} [4]\oplus [2] \rightarrow 0 \rightarrow \cdots.
\]

\[
\mathbb{H}^d \left(Rj_!R j^\ast Rg_\ast k_\Sigma\right) = \begin{cases}
k \text{, if $d=1$} \\
0 \text{ otherwise.}
\end{cases}
\]

The hypercohomology is non-trivial, which means that $B \in \mu\supp^\ast Rg_\ast k_\Sigma$.

Computing critical elements: $(Rg_\ast k_\Sigma,f,!)$. Next, we check whether $B=\{4,24\}$ is in $\mu\supp^! R g_\ast k_\Sigma$, i.e., whether $\mathbb{H}^d \left(Rj^! Rg_\ast k_\Sigma\right)\neq 0$. As discussed in Section <ref>, computing the proper pullback is easy – we only need to consider the submatrices $Rg_\ast\eta^d[B,B]$. We get
\[
Rj^! Rg_\ast k_\Sigma = \cdots \rightarrow 0 \rightarrow 0 \rightarrow [24]\oplus[4]\xrightarrow{\footnotesize \begin{pmatrix}
1 & 0
\end{pmatrix}} [4] \rightarrow 0 \rightarrow \cdots,\]

the hypercohomology of which is
\[
\mathbb{H}^d \left(Rj^! Rg_\ast k_\Sigma\right) = \begin{cases}
k \text{, if $d=1$} \\
0 \text{ otherwise.}
\end{cases}
\]

Therefore, $B\in \mu\supp^! Rg_\ast k_\Sigma$.

Computing critical elements: $(Rh_\ast k_\Sigma,f,\ast)$. We follow the same computation as above, but for $h$. For the pullback, we get matrices

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccccc}
\gamma^{-1} & 014_\Lambda & 034_\Lambda & 124_\Lambda & 234_\Lambda & 14_\Lambda  & 34_\Lambda  \\
04_\Lambda  & 1           & 1           & \cdot       & \cdot       & \cdot       & \cdot       \\
14_\Lambda  & 1           & \cdot       & 1           & \cdot       & \cdot       & \cdot       \\
24_\Lambda  & \cdot       & \cdot       & 1           & 1           & \cdot       & \cdot       \\
34_\Lambda  & \cdot       & 1           & \cdot       & 1           & \cdot       & \cdot       \\
4_\Lambda  & 1           & \cdot       & \cdot       & \cdot       & 1           & \cdot       \\
4_\Lambda  & 1           & \cdot       & \cdot       & \cdot       & \cdot       & 1           \\ \hline
24_B        & \cdot       & \cdot       & 1           & \cdot       & \cdot       & \cdot
\end{pNiceArray}
\]

\[
\begin{pNiceArray}[first-row,first-col, margin=.5em]{cccccc|c}
\gamma^0   & 04_\Lambda    & 14_\Lambda    & 24_\Lambda    & 34_\Lambda    & 4_\Lambda     & 4_\Lambda     & 24_B    \\
4_\Lambda  & 1             & 1             & 1             & 1             & \cdot         & \cdot         & \cdot
\end{pNiceArray}
\]

The submatrices $\gamma^d[B,B]$ are all empty with one label in degree $0$, which yields
\[
Rj^\ast (Rh_\ast k_\Sigma) = \cdots \rightarrow 0 \rightarrow [24] \rightarrow 0 \rightarrow 0 \rightarrow \cdots.
\]

As above, to compute the proper pushforward, we start with the matrices we just computed, and perform the update step for $2$. We need to add a row in the matrix going from degree $0$, which had one column labeled by $24$ and no rows. Hence,
\[
Rj_! (Rj^\ast Rh_\ast k_\Sigma) = \cdots \rightarrow 0 \rightarrow [24] \xrightarrow{(1)} [2] \rightarrow 0 \rightarrow \cdots.
\]

The hypercohomology of this complex is trivial, so $B\notin \mu\supp^\ast Rh_\ast k_\Sigma$.

Computing critical elements: $(Rh_\ast k_\Sigma,f,!)$. The matrices $Rh_\ast\eta_0[B,B]$ and $Rh_\ast\eta_1[B,B]$ give
\[
Rj^! Rh_\ast k_\Sigma = \cdots \rightarrow 0 \rightarrow 0 \rightarrow [24]\oplus[4]\oplus[4]\xrightarrow{\footnotesize \begin{pmatrix}
1 & 0 & 0
\end{pmatrix}} [4] \rightarrow 0 \rightarrow \cdots,
\]

with hypercohomology
\[
\mathbb{H}^d \left(Rj^! Rg_\ast k_\Sigma\right) = \begin{cases}
k^2 \text{, if $d=1$} \\
0 \text{ otherwise,}
\end{cases}
\]

and hence $B\in \mu\supp^! Rh_\ast k_\Sigma$.

Filtrations and hypercohomology. In Figure <ref> we list Betti numbers for hypercohomology groups associated to the filtration of $\Lambda$ by sublevel-sets of $f$. As Theorem <ref> implies, the value in column $X$ for the sublevel filtration differs from the value in its left neighbor only if $X$ is a critical element for the corresponding notion of microlocal support as shown in the table above. Similarly, for the superlevel filtration, non-critical columns $X$ have the same value as their right neighbors.

Each entry in the table lists the dimension of hypercohomology groups in degree 0, 1, and 2 (empty entries have trivial hypercohomology). Here, $Z=f^{-1}(x)$ and $i_{\preceq x}$ ($i_{\succeq x}$) is the inclusion map of sublevel-sets (superlevel-sets) of $f$ (relative to the total order $\preceq$ on $\Pi$) into $\Lambda$, for $x$ an element of $\Pi$ corresponding to the column labels.

[1]
Jeffrey Adams, Dan Barbasch, and David A. Vogan, Jr.
The Langlands classification and irreducible characters for
real reductive groups, volume 104 of Progress in Mathematics.
Birkhäuser Boston, Inc., Boston, MA, 1992.

[2]
Adam Brown and Ondřej Draganov.
DESC: Derived Sheaf Calculator.
<https://github.com/OnDraganov/desc>, 2022.

[3]
Kai Behrend.
Donaldson-Thomas type invariants via microlocal geometry.
Ann. of Math. (2), 170(3):1307–1338, 2009.

[4]
Nicolas Berkouk and Grégory Ginot.
A derived isometry theorem for sheaves.
Adv. Math., 394:108033, 2022.

[5]
Nicolas Berkouk, Grégory Ginot, and Steve Oudot.
Level-sets persistence and sheaf theory.
arXiv, 2019.

[6]
Nicolas Berkouk and François Petit.
Ephemeral persistence modules and distance comparison.
Algebr. Geom. Topol., 21(1):247–277, 2021.

[7]
Glen E. Bredon.
Sheaf theory, volume 170 of Graduate Texts in
Springer-Verlag, New York, second edition, 1997.

[8]
Justin Curry, Robert Ghrist, and Vidit Nanda.
Discrete Morse theory for computing cellular sheaf cohomology.
Found. Comput. Math., 16(4):875–897, 2016.

[9]
Justin Curry, Sayan Mukherjee, and Katharine Turner.
How many directions determine a shape and other sufficiency results
for two topological transforms.
arXiv, 2018.

[10]
Justin Curry and Amit Patel.
Classification of constructible cosheaves.
Theory Appl. Categ., 35:Paper No. 27, 1012–1047, 2020.

[11]
Justin Michael Curry.
Sheaves, cosheaves and applications.
ProQuest LLC, Ann Arbor, MI, 2014.
Thesis (Ph.D.)–University of Pennsylvania.

[12]
Justin Michael Curry.
Dualities between cellular sheaves and cosheaves.
J. Pure Appl. Algebra, 222(4):966–993, 2018.

[13]
Paweł Dłotko and Hubert Wagner.
Simplification of complexes for persistent homology computations.
Homology Homotopy Appl., 16(1):49–63, 2014.

[14]
Robin Forman.
Morse theory for cell complexes.
Adv. Math., 134(1):90–145, 1998.

[15]
Robin Forman.
A user's guide to discrete Morse theory.
Sém. Lothar. Combin., 48:Art. B48c, 35, 2002.

[16]
Mark Goresky and Robert MacPherson.
Morse theory and intersection homology theory.
In Analysis and topology on singular spaces, II, III
(Luminy, 1981), volume 101 of Astérisque, pages 135–192. Soc.
Math. France, Paris, 1983.

[17]
Mark Goresky and Robert MacPherson.
Stratified Morse theory, volume 14 of Ergebnisse der
Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related
Areas (3)].
Springer-Verlag, Berlin, 1988.

[18]
Mark Goresky.
Morse theory, stratifications and sheaves.
In Handbook of Geometry and Topology of Singularities I, pages
275–319. Springer, 2020.

[19]
Mark Goresky.
Lecture notes on sheaves and perverse sheaves, 2021.

[20]
E. L. Green, Ø. Solberg, and D. Zacharia.
Minimal projective resolutions.
Trans. Amer. Math. Soc., 353(7):2915–2939, 2001.

[21]
Shaun Harker, Konstantin Mischaikow, Marian Mrozek, and Vidit Nanda.
Discrete Morse theoretic algorithms for computing homology of
complexes and maps.
Found. Comput. Math., 14(1):151–184, 2014.

[22]
Birger Iversen.
Cohomology of sheaves.
Universitext. Springer-Verlag, Berlin, 1986.

[23]
Masaki Kashiwara.
Index theorem for constructible sheaves.
Number 130, pages 193–209. 1985.
Differential systems and singularities (Luminy, 1983).

[24]
Masaki Kashiwara and Pierre Schapira.
Micro-support des faisceaux: application aux modules
C. R. Acad. Sci. Paris Sér. I Math., 295(8):487–490, 1982.

[25]
Masaki Kashiwara and Pierre Schapira.
Microlocal study of sheaves.
Astérisque, (128):235, 1985.
Corrections to this article can be found in Astérisque No. 130,
p. 209.

[26]
Masaki Kashiwara and Pierre Schapira.
Sheaves on manifolds, volume 292 of Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Springer-Verlag, Berlin, 1994.
With a chapter in French by Christian Houzel, Corrected reprint of
the 1990 original.

[27]
Masaki Kashiwara and Pierre Schapira.
Persistent homology and microlocal sheaf theory.
J. Appl. Comput. Topol., 2(1-2):83–113, 2018.

[28]
Masaki Kashiwara and Pierre Schapira.
Piecewise linear sheaves.
Int. Math. Res. Not. IMRN, (15):11565–11584, 2021.

[29]
Sefi Ladkani.
Homological properties of finite partially ordered sets.
Thesis (Ph.D.)–Hebrew University.

[30]
Sefi Ladkani.
On derived equivalences of categories of sheaves over finite posets.
J. Pure Appl. Algebra, 212(2):435–451, 2008.

[31]
Jean Leray.
Sur la forme des espaces topologiques et sur les points fixes des
J. Math. Pures Appl. (9), 24:95–167, 1945.

[32]
John Milnor.
Morse theory.
Annals of Mathematics Studies, No. 51. Princeton University Press,
Princeton, N.J., 1963.
Based on lecture notes by M. Spivak and R. Wells.

[33]
Konstantin Mischaikow and Vidit Nanda.
Morse theory for filtrations and efficient computation of persistent
Discrete Comput. Geom., 50(2):330–353, 2013.

[34]
Marston Morse.
Relations between the critical points of a real function of $n$
independent variables.
Trans. Amer. Math. Soc., 27(3):345–396, 1925.

[35]
Robert MacPherson and Amit Patel.
Persistent local systems.
Adv. Math., 386:Paper No. 107795, 39, 2021.

[36]
Vidit Nanda.
Discrete Morse theory and localization.
J. Pure Appl. Algebra, 223(2):459–488, 2019.

[37]
Vidit Nanda.
Local cohomology and stratification.
Found. Comput. Math., 20(2):195–222, 2020.

[38]
Vidit Nanda, Dai Tamaki, and Kohei Tanaka.
Discrete Morse theory and classifying spaces.
Adv. Math., 340:723–790, 2018.

[39]
David Nadler and Eric Zaslow.
Constructible sheaves and the Fukaya category.
J. Amer. Math. Soc., 22(1):233–286, 2009.

[40]
Mikio Sato.
Regularity of hyperfunctions solutions of partial differential
In Actes du Congrès International des Mathématiciens
(Nice, 1970), Tome 2, pages 785–794. 1971.

[41]
Pierre Schapira.
Propagation-set for sheaves and microsupport.

[42]
Allen Shepard.
A Cellular Description of the Derived Category of a Stratified
Thesis (Ph.D.)–Brown University.

[43]
Mikio Sato, Takahiro Kawai, and Masaki Kashiwara.
Microfunctions and pseudo-differential equations.
In Hyperfunctions and pseudo-differential equations (Proc.
Conf., Katata, 1971; dedicated to the memory of André
Martineau), Lecture Notes in Math., Vol. 287, pages 265–529. Springer,
Berlin, 1973.

[44]
Emil Sköldberg.
Morse theory from an algebraic viewpoint.
Trans. Amer. Math. Soc., 358(1):115–129, 2006.

[45]
Pierre Schapira and Nobuyuki Tose.
Morse inequalities for ${\bf R}$-constructible sheaves.
Adv. Math., 93(1):1–8, 1992.

[46]
Edward Witten.
Supersymmetry and Morse theory.
J. Differential Geometry, 17(4):661–692 (1983), 1982.

§ REMAINING PROOFS

Let $I^\bullet$ be an injective resolution of the constant sheaf on $\Sigma$. By Corollary <ref>,

\[
m_{ k_\Sigma}^d(\sigma) = \dim H^d Ri_\sigma^! I^\bullet.\]

For $\sigma\in\Sigma$, let $C(\sigma)\coloneqq \sigma^0\ast \left\{ \tau\setminus\sigma \,\middle|\, \tau\in\St\sigma\setminus\{\sigma\} \right\}$ be the cone of the link $\left\{ \tau\setminus\sigma \,\middle|\, \tau\in\St\sigma\setminus\{\sigma\} \right\}$ (where $\tau\setminus\sigma$ denotes set difference when $\tau$ and $\sigma$ are viewed as sets of vertices in $\Sigma$), with cone point given by the vertex $\sigma^0$. Then $\St_{C(\sigma)}\sigma^0 \cong \St_\Sigma\sigma$ as posets. Therefore, $I^\bullet\vert_{\St_\Sigma\sigma}$, viewed as a complex of sheaves over $\St_{C(\sigma)}\sigma^0$, is an injective resolution of the constant sheaf on $\St_{C(\sigma)}\sigma^0$. Let $J^\bullet$ be the injecive resolution of the constant sheaf on the simplicial complex $C(\sigma)$, defined (non-inductively) in Section <ref>. Then $I^\bullet\vert_{\St_\Sigma\sigma}$ is quasi-isomorphic to $J^\bullet\vert_{\St_{C(\sigma)}\sigma^0}$.
By definition, $i^!_{\sigma^0}(J^\bullet)$ is exactly the complex of vector spaces used to compute compactly supported cohomology of the constant sheaf on $\St_{K(C(\sigma))}(\sigma^0)$, the star of $\sigma^0$ in the barycentric subdivision $ K(C(\sigma))$ of $C(\sigma)$ (see <cit.> and [42]). Because the geometric realisation $|\St_{K(C(\sigma))}(\sigma^0)|$ is homeomorphic to $|\St_{C(\sigma)}\sigma^0|$, the cohomology groups of this complex are isomorphic to $H_c^{d}(|\St_{C(\sigma)}(\sigma^0)|;k)$. Finally, because $|\St_\Sigma \sigma|$ is homeomorphic to $\mathbb{R}^{\dim\sigma}\times |\St_{C(\sigma)}\sigma^0|$,

\[
m^d_{k_\Sigma}(\sigma) = \dim H_c^{d}(|\St_{C(\sigma)}(\sigma^0)|;k) = \dim H_c^{d+\dim\sigma}(|\St_\Sigma (\sigma)|;k).
\]

When $\Pi$ is a cell complex, the theorem follows, for example, from <cit.>. We include a more general proof for arbitrary finite posets below. Let $I^\bullet$ be an injective resolution of $F$. Because $t^\ast$ defines an exact functor from the category of sheaves on $\Pi$ to the category of sheaves on $K(\Pi)$, we have that

\[
0\rightarrow t^\ast F\rightarrow t^\ast I^0\rightarrow t^\ast I^1\rightarrow \cdots\rightarrow t^\ast I^n\rightarrow 0
\]

is an exact sequence. We claim that each $t^\ast I^d$ is acyclic:

\[
H^j(R(p\circ t)_\ast \left( t^\ast I^d\right))=0, \text{ for }j>0.
\]

Indeed, it is enough to prove that for each indecomposable injective sheaf $[\pi]$ on $\Pi$, the sheaf $t^\ast [\pi]$ is acyclic. Because $t^\ast[\pi]$ is the constant sheaf on the order complex of the downward closure, $\Cl\pi\coloneqq  \{\tau\in\Pi:\tau\le\pi\}$, of $\pi$ in $\Pi$, we have

\[
H^j(R(p\circ t)_\ast \left(t^\ast[\pi]\right))\cong H^j(|K(\Cl\pi)|;k).
\]

Notice that $K(\Cl\pi)$, as a simplicial complex, is equal to the cone of the simplicial complex $K(\Cl\pi-\pi)$. Therefore, $|K(\Cl\pi)|$ is contractible, $H^j(|K(\Cl\pi)|;k)=0$ for $j>0$, and $t^\ast[\pi]$ is acyclic. The complex $t^\ast I^\bullet$ is therefore an acyclic resolution of $t^\ast F$, and by standard results of homological algebra (for example, <cit.>), we have

\[
H^j(K(\Pi); t^\ast F)\cong H^j\big( (p \circ t)_\ast (t^\ast I^\bullet)\big) \cong H^j(\Pi;F).
\]