# ObVi-SLAM: Long-Term Object-Visual SLAM

Amanda Adkins  Taijing Chen  Joydeep Biswas The authors are with the
Department of Computer Science, The University of Texas at Austin, Austin, TX.
Email: {aaadkins, taijing<EMAIL_ADDRESS>This work is partially
supported by the National Science Foundation (GRFP DGE-2137420,
CAREER-2046955) and Amazon Lab126. Any opinions, findings, and conclusions
expressed in this material are those of the authors and do not necessarily
reflect the views of the sponsors.

###### Abstract

Robots responsible for tasks over long time scales must be able to localize
consistently and scalably amid geometric, viewpoint, and appearance changes.
Existing visual SLAM approaches rely on low-level feature descriptors that are
not robust to such environmental changes and result in large map sizes that
scale poorly over long-term deployments. In contrast, object detections are
robust to environmental variations and lead to more compact representations,
but most object-based SLAM systems target short-term indoor deployments with
close objects. In this paper, we introduce ObVi-SLAM to overcome these
challenges by leveraging the best of both approaches. ObVi-SLAM uses low-level
visual features for high-quality short-term visual odometry; and to ensure
global, long-term consistency, ObVi-SLAM builds an uncertainty-aware long-term
map of persistent objects and updates it after every deployment. By evaluating
ObVi-SLAM on data from 16 deployment sessions spanning different weather and
lighting conditions, we empirically show that ObVi-SLAM generates accurate
localization estimates consistent over long-time scales in spite of varying
appearance conditions.

##  I Introduction

Mobile service robots need to be able to operate autonomously over long time
periods. Existing visual SLAM approaches are susceptible to failures caused by
environmental changes that occur over such time scales, including geometric
changes from moving and movable objects, appearance changes from lighting and
seasonal variation, and viewpoint differences arising from different
perspectives of an environment. Further, visual SLAM systems generally use
maps composed of visual feature points, which results in large maps that do
not scale well with time.

Figure 1: ObVi-SLAM overview. In the factor graph, factors with solid lines
are present for all optimizations, whereas use of factors with dashed lines is
dependent on if the optimization is local or global.

Unlike classical visual feature extractors, object detectors are trained to be
invariant to appearance and large-scale viewpoint changes. Object-based SLAM
systems [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] can leverage object detections to
estimate landmarks that are similarly robust to such changes and provide a
low-dimensional representation of the environment. However, most existing
object-based SLAM systems target short-term, indoor trajectories in which
objects can be viewed from diverse perspectives, simplifying object
estimation.

In this work, we introduce ObVi-SLAM: an object-visual SLAM approach designed
for long-term deployments. ObVi-SLAM, shown in Fig. 1, aims to generate
accurate and consistent trajectory estimates for many deployment sessions over
long time scales. To accomplish this objective, ObVi-SLAM utilizes a long-term
map of the static objects in the target environment that reflects uncertainty
of the current estimates. Use of object detectors trained to be invariant to
different appearances enables ObVi-SLAM to be robust to appearance and
viewpoint variation, while focusing on static objects provides resilience to
movable entities. Forming the map with objects and their estimate uncertainty
enables scalability over time and continuous improvement using new
measurements from each deployment. Finally, use of low-level visual features
tracked within individual deployment sessions enables high short-term
accuracy. We summarize our contributions as follows:  (i) a joint object-
visual SLAM objective function for integrating long-term map information,
object detections, and visual feature observations,  (ii) a long-term scalable
object front-end for initializing objects and associating incoming bounding
boxes to existing objects, and  (iii) a method for extracting a long-term map
of the static objects in an environment with probabilistically-derived
uncertainty estimates.  We empirically show that ObVi-SLAM can accurately and
consistently estimate trajectories over long-term deployments using data
collected outdoors across 16 deployment sessions outdoors over two months.

##  II Related Work

###  II-A Object SLAM

Initial efforts in semantic object SLAM such as SLAM++ [11] used pre-existing
models. Many later works either estimate detailed geometry for each instance
[12, 13] or use coarse, generalized models. For computational efficiency,
ObVi-SLAM uses coarse models, thus we focus on the latter category. CubeSLAM
[1] introduces an object-based SLAM algorithm that represents objects as
cuboids and leverages relationships between low-level visual features,
objects, and camera poses for estimation. Ellipsoids are also an increasingly
popular representation for objects in SLAM. QuadricSLAM [2] is among the first
to use ellipsoids to represent objects, but requires known data associations.
Various extensions have enhanced object SLAM with ellipsoids, addressing
aspects such as fast object initialization and constraints to aid in cases of
limited viewpoint diversity in ROSHAN [3]; trajectory reinitialization using
objects in OA-SLAM [4]; constraints for object arrangement, symmetry, and
scale in SO-SLAM [5]; and providing scale to monocular SLAM using object prior
dimensions [6]. Others focused on data association or initialization of
ellipsoids, with ensemble data association [7]; initialization for straight
trajectory scenarios [8]; object initialization and association for outdoor
SLAM [9]; and few-frame, limited viewpoint association and initialization
[10]. In contrast to the proposed approach, consideration of long-term SLAM is
limited in these works: OA-SLAM is the only approach that addresses any
aspects of long-term localization and does so with a fixed map with no
uncertainty estimation.

###  II-B Long-Term Map Management

SLAM approaches used for long-term robot deployments need to be able to scale
over time. Many approaches have no support for multiple mapping sessions.
Others [14, 15] support multi-session mapping, but do not address scaling
concerns; another category fixes the map after initial data collection,
addressing scaling but leaving localization susceptible to initial errors and
environmental changes. Some approaches, such as POCD [16], maintain a fixed
map but leverage change detection to determine when map regions should be
updated. Other approaches prune or summarize the oldest data, retaining only
the most informative or recent data. Nashed and Biswas [17] generate an
uncertainty-aware vector-based map of long-term features using lidar data from
multiple deployments. A common technique for reducing map size used by ObVi-
SLAM and numerous prior works is marginalization and sparsification. Vallvé et
al. [18] proposed a method called factor descent for general SLAM
marginalization and sparsification. Hsiung et al. [19] and Wilbers et al. [20]
both addressed the problem of online marginalization and sparsification for
sliding window optimization; the former uses an information-theoretic approach
applied to visual-inertial odometry, whereas the latter generates a single
global prior to maintain optimal sparsity. Zhao et al. [21] focused on long-
term lidar localization, using marginalization and sparsification to remove
old submaps from a pose-graph.

###  II-C Long-term Robust SLAM

For a SLAM algorithm to be robust over long time scales, it must tolerate
geometric, appearance, and viewpoint changes. Most approaches that aim to be
robust to geometric changes arising from movable and moving entities aim to
identify observations that may correspond to such objects, either using
observed motion or semantic class. Some of these approaches, such as DOT [22],
discard observations arising from these features, whereas others like CubeSLAM
[1] and DynaSLAM II [23] use these objects for local corrections, estimating
and tracking moving objects.

Engineered feature representations, such as ORB features, can tolerate minor
viewpoint and appearance changes. Recently, deep-learning has been applied to
improve robustness to such changes. Gridseth et al. [24] developed and trained
a network to select sparse keypoints, with a differentiable pose estimation
framework. Chen and Barfoot [25] similarly aimed to generate lighting-
invariant keypoints in a self-supervised manner. Deja-Vu [26] generates dense
feature maps robust to seasonal changes using pairs of images captured in the
same location in different conditions. Learning-based methods like these,
however, are highly dependent on having training data, often requiring labels
or ground-truth, that matches the characteristics of the target environment.

##  III System Overview and Preliminaries

###  III-A Approach Overview

There are 2 phases in ObVi-SLAM: SLAM and long-term map extraction. SLAM runs
while the robot is deployed, estimating the robot’s trajectory and the map of
visual features and objects. Following this, estimates are refined and then
long-term map extraction uses the SLAM results to update the long-term map for
use in subsequent sessions. The full ObVi-SLAM system is illustrated in Fig.
1.

###  III-B Representation, Notation, and Assumptions

We first define notation and representations for variables and note key
assumptions. The following notation is used:

  * •

$i\in[1,L]$ \- deployment session index.

  * •

$x_{t}^{i}\in SE(3)$ \- pose at timestamp $t$ in session $i$; $t\in[1,T^{i}]$.

  * •

${x_{t}^{i}}{{}^{\prime}}\in SE(3)$ \- estimate for $x_{t}^{i}$ after the most
recent optimization; $t\in[1,T^{i}]$.

  * •

$v^{i}_{k}\in\mathbb{R}^{3}$ \- $k$th visual feature in session $i$;
$k\in[1,V^{i}]$.

  * •

$s_{m}^{i}\in\mathbb{R}^{2}$ \- $m$th visual feature observation in session
$i$: pixel at which feature was observed; $m\in[1,M^{i}]$.

  * •

$B_{n}^{i}\in\mathbb{R}^{4}$ \- $n$th object observation in session $i$
represented as a bounding box parameterized by the minimum and maximum x and y
pixels; $n\in[1,N^{i}]$.

  * •

$LTM^{i}$ \- Long-term map summarizing information gathered through session
$i$.

  * •

$Q^{i*}_{j}$ \- Object $j$ in session $i$, modeled as an ellipsoid;
$j\in[1,J^{i}]$.

  * •

$c^{i}_{j}$ \- Semantic class of object $Q^{i*}_{j}$.

Unless otherwise noted, variables correspond to deployment session $i$. Object
notation follows conventions in [3] and [2].

There are two supported parameterizations of the ellipsoid: upright and full-
DOF. In both cases, there are three position parameters and three dimension
parameters. The upright parameterization represents orientation with a single
parameter for yaw; the full-DOF parameterization uses three parameters for an
$SO(3)$ orientation. Parameterization choice depends on possible object
configurations in the target environment. We use the dual quadric form for
each ellipsoid, which defines the ellipsoid using the relationship to its
tangent planes. In the dual form, an ellipsoid $Q^{*}_{j}$ is represented by a
4x4 matrix. For details on this representation and how the parameters are
encoded in $Q^{*}_{j}$, refer to [2] and [3].

The only sensor data required for ObVi-SLAM are camera images; ObVi-SLAM
supports arbitrary camera configurations, including monocular and stereo,
given that relative camera poses are known. In our formulation, we assume that
the robot’s pose is combined with the appropriate relative camera pose when
assessing an observation likelihood. We also assume that the robot’s pose at
the beginning of each deployment session is known. Finally, the system should
be configured to use object detections of the static classes for the target
environment and approximate mean and variation for the dimensions of each
semantic class should be given.

##  IV Online SLAM Formulation

###  IV-A SLAM Factor Graph

During SLAM operation for deployment session $i$, we aim to find the optimal
estimates for the visual features, $v_{1:V}$; objects, $Q^{*}_{1:J}$; and
robot poses, $x_{1:T}$. Optimization inputs are the visual feature
observations, $s_{1:M}$; object detections, $B_{1:N}$; prior mean and
covariances for the dimensions of classes of interest; and, if it exists, the
long-term map from a previous session, $LTM^{i-1}$. We use two different
optimization modes: local adjustment and global adjustment. Local adjustment
optimizes the most recent poses and observations to generate high-quality
visual odometry estimates. For local adjustment, we use the following model
for belief:

$\displaystyle\mathrm{Bel}($ $\displaystyle
x_{1:T},v_{1:V},Q^{*}_{1:J})\propto\underbrace{p(s_{1:M}|x_{1:T},v_{1:V})}_{\begin{subarray}{c}\text{Reprojection
Error}\end{subarray}}$ (1)
$\displaystyle\underbrace{p(B_{1:N}|Q^{*}_{1:J},x_{1:T})}_{\begin{subarray}{c}\text{Bounding
Box
Error}\end{subarray}}\underbrace{p(Q^{*}_{1:J}|c_{1:J})}_{\begin{subarray}{c}\text{Semantic
Shape
Prior}\end{subarray}}\underbrace{p(Q^{*}_{1:J}|LTM^{i-1})}_{\begin{subarray}{c}\text{Long-
term Map Prior}\end{subarray}}.$

Global adjustment aims to shift the estimates generated by the local
optimization for improved global accuracy by using data from the entire
trajectory. For computational efficiency, we use a simplified form of the
belief, given by

$\displaystyle\mathrm{Bel}($ $\displaystyle
x_{1:T},v_{1:V},Q^{*}_{1:J})\propto\underbrace{p(x_{1:T})}_{\begin{subarray}{c}\text{Visual
Odometry Error}\end{subarray}}$ (2)
$\displaystyle\underbrace{p(B_{1:N}|Q^{*}_{1:J},x_{1:T})}_{\begin{subarray}{c}\text{Bounding
Box
Error}\end{subarray}}\underbrace{p(Q^{*}_{1:J}|c_{1:J})}_{\begin{subarray}{c}\text{Semantic
Shape
Prior}\end{subarray}}\underbrace{p(Q^{*}_{1:J}|LTM^{i-1})}_{\begin{subarray}{c}\text{Long-
term Map Prior}\end{subarray}}.$

A factor graph reflecting these models is shown in Fig. 1. Given the
appropriate form of the belief, ObVi-SLAM then uses a nonlinear least squares
optimizer to find the estimates that satisfy the following optimization
objective:

$\displaystyle x^{*}_{1:T},$ $\displaystyle
v^{*}_{1:V},Q^{*}_{1:J}={\underset{x_{1:T},v_{1:V},Q^{*}_{1:J}}{\mathrm{argmax}}\;\mathrm{Bel}(x_{1:T},v_{1:V},Q^{*}_{1:J})}$
(3)
$\displaystyle\equiv{\underset{x_{1:T},v_{1:V},Q^{*}_{1:J}}{\mathrm{argmin}}\;\left[-\log\mathrm{Bel}(x_{1:T},v_{1:V},Q^{*}_{1:J})\right]}.$
(4)

The factors in (1) and (2) are detailed in the next subsections.

####  IV-A1 Reprojection Factor

The reprojection factor uses low-level visual features to generate a smooth
trajectory estimate across local frames. Consistent with previous indirect
visual SLAM approaches, ObVi-SLAM estimates the 3D locations of features
detected in images by matching detections across temporally close frames. It
adjusts the robot’s trajectory and current visual feature position estimates
to minimize the distance between the detected feature locations and the
reprojections of the features onto the images. The reprojection factor term in
our optimization objective is the sum of terms for each feature detection:

$\displaystyle-\log p(s_{1:M}|$ $\displaystyle
x_{1:T},v_{1:V})=\sum_{m=1}^{M}-\log p(s_{m}|x_{s_{m}},v_{s_{m}})$ (5)
$\displaystyle=\frac{1}{2}\sum_{m=1}^{M}||\Pi(x_{s_{m}},v_{s_{m}})-s_{m}||^{2}_{\Sigma_{s_{m}}},$
(6)

where $x_{s_{m}}$ and $v_{s_{m}}$ are the robot’s pose and feature for the
detection, $\Pi(\cdot,\cdot)$ is the projection function giving the pixel
location of a 3D point, and $\Sigma_{{s_{m}}}$ is the detection covariance.

####  IV-A2 Visual Odometry Factor

In the global trajectory optimization, to improve computation time and reduce
the impact of local minima, we use visual odometry factors instead of
reprojection error factors. This term penalizes deviations from the result of
the local optimization in the relative poses between pairs of subsequent
poses. This has the form

$\displaystyle-\log p(x$ ${}_{1:T})=\sum_{t=2}^{T}-\log
p(x_{t}|x_{t-1},x^{\prime}_{t},x^{\prime}_{t-1})$ (7)
$\displaystyle=\sum_{t=2}^{T}\frac{1}{2}||\left(\left(x_{t}\ominus
x_{t-1}\right)\ominus\left(x^{\prime}_{t}\ominus
x^{\prime}_{t-1}\right)\right)||^{2}_{\Sigma_{t}},$ (8)

where $\Sigma_{t}$ is the covariance for the position deviation. $\Sigma_{t}$
is scaled with the magnitude of $x^{\prime}_{t}\ominus x^{\prime}_{t-1}$.

####  IV-A3 Bounding Box Factor

The bounding box factor aims to update object estimates such that edges of the
detected bounding boxes for an object are tangent to the ellipse generated by
projecting the ellipsoid onto the camera plane. This factor enables ObVi-SLAM
to relate the current trajectory to the long-term map and update object
estimates with new information. The bounding box factor contains a term for
each bounding box detection as follows:

$\displaystyle-\log p(B_{1:N}|$ $\displaystyle
Q^{*}_{1:J},x_{1:T})=\sum_{n=1}^{N}-\log p(B_{n}|Q^{*}_{B_{n}},x_{B_{n}})$
$\displaystyle=\frac{1}{2}\sum_{B_{n}\in
s_{O}}||\hat{B}_{n}-{B_{n}}||^{2}_{\Sigma_{B_{n}}},$ (9)

where $\hat{B}_{n}$ is the bounding box resulting from projecting the
ellipsoid onto the camera plane and $\Sigma_{B_{n}}$ gives the uncertainty of
the object detection. To handle occlusions resulting from the image boundary,
we inflate the entries of $\Sigma_{B_{n}}$ corresponding to the occluded edge
when a detected bounding box lies near the image boundary.

To find $\hat{B}_{n}$, we project the ellipsoid onto the camera and find the
horizontal and vertical tangent lines. As noted, the object’s dual quadric
representation in the world frame is a 4x4 matrix $Q^{*}_{j}$. The object’s
dual quadric representation with respect to the camera frame ${}^{C}Q^{*}_{j}$
is then given by

$\displaystyle{}^{C}Q^{*}_{j}=XQ^{*}_{j}X^{T},$ (10)

where $X$ is a homogeneous transformation giving the world frame pose with
respect to the camera, derived from $x_{B_{n}}$. This is projected to a dual
conic section $G^{*}_{j}\in\mathbb{R}^{3x3}$ with

$\displaystyle G^{*}_{j}=K{}^{C}Q^{*}_{j}K^{T}.$ (11)

All tangent lines $l$ to a dual conic must obey the property

$\displaystyle l^{T}G^{*}l=0.$ (12)

We can find the horizontal $l_{u}$ and vertical $l_{v}$ tangent lines to the
conic section, which take the forms $l_{u}=[1,0,-u]$ and $l_{v}=[0,1,-v]$. $u$
and $v$ are then obtained using (12), giving

$\displaystyle\hat{u}_{\min},\hat{u}_{\max}$
$\displaystyle=\left(G^{*}_{1,3}\pm\sqrt{{G^{*}_{1,3}}^{2}-G^{*}_{1,1}G^{*}_{3,3}}\right)/{G^{*}_{3,3}}$
(13) $\displaystyle\hat{v}_{\min},\hat{v}_{\max}$
$\displaystyle=\left(G^{*}_{2,3}\pm\sqrt{{G^{*}_{2,3}}^{2}-G^{*}_{2,2}G^{*}_{3,3}}\right)/{G^{*}_{3,3}}.$
(14)

These are stacked to create vector $\hat{B}_{n}$. It should be noted that when
either the x or y axes of the camera intersect an ellipsoid, the generated
conic is not a proper ellipse111If both the x and y axes intersect the
ellipsoid, the camera lies within the ellipsoid and the resulting conic is an
imaginary ellipse; otherwise, the projection is a hyperbola, with one branch
coming from behind the camera. Future work could improve handling of
hyperbolic projections., resulting in imaginary bounding box values. In these
cases, we set the error to a fixed value.

####  IV-A4 Semantic Shape Prior Factor

The semantic shape prior is important for constraining an object’s dimensions
in cases of limited viewpoint diversity where the object’s depth and dimension
along the camera ray are under-constrained. This factor penalizes deviations
from the mean dimension of an object’s semantic class. The semantic shape
prior is a sum of terms, each penalizing a single object, with the form

$\displaystyle-\log
p(Q^{*}_{1:J}|c_{1:J})=\sum_{j=1}^{J}||m_{\text{shape}}(c_{j})-d(Q^{*}_{j})||^{2}_{\Sigma_{c_{j}}},$
(15)

where $m_{\text{shape}}$ is a function giving the mean dimension for an object
of the given semantic class, $d(\cdot)$ gives the dimensions of an object, and
$\Sigma_{c_{j}}$ reflects the variance of the dimensions of an object of class
$c_{j}$. This term was introduced by Ok et al. [3] and additional details can
be found in their paper.

####  IV-A5 Long-Term Map Prior Factor

The long-term map prior factor incorporates information from previous sessions
in our object estimation. This serves as a prior for objects that have been
previously observed, so that their latest estimates appropriately balance
previous knowledge and uncertainty with new observations. The ObVi-SLAM
framework is generic to any factorization relating objects to each other and
to the map frame. The generic form for this factor is

$\displaystyle
p(Q^{*}_{1:J}|LTM^{i-1})=\prod_{S_{k}\in{LTM^{i-1}}}N(f_{S_{k}}(Q^{*}_{1:J^{i-1}})|\mu_{S_{k}},\Sigma_{S_{k}}),$
(16)

where $S_{k}$ is a component factor of the long-term map, $f_{S_{k}}(\cdot)$
is a function operating on a subset of the previously observed objects, and
$\mu_{S_{k}}$ and $\Sigma_{S_{k}}$ are the mean and covariance for factor
$S_{k}$. The current ObVi-SLAM formulation uses an independent normal
assumption for each previously observed object, so the long-term map prior
factor described generally in (16) has the form

$\displaystyle-\log
p(Q^{*}_{1:J}|LTM^{i-1})=\sum_{j=1}^{J^{i-1}}\frac{1}{2}||\text{v}(Q^{*}_{j})-\mu_{S_{j}}||^{2}_{\Sigma_{S_{j}}},$
(17)

where $\text{v}(\cdot)$ is a function that generates a vector of parameters
for object $Q^{*}_{j}$, and $\mu_{S_{j}}$ and $\Sigma_{S_{j}}$ are the object
estimate mean and uncertainty based on previous sessions.

###  IV-B Front-End

To use this optimization formulation, a front-end is needed to provide initial
estimates and associations relating observations over time. Visual feature
associations and initial estimates are obtained from the front-end of ORB-
SLAM2 [27], which generates feature tracks based on ORB descriptors.

Our object-front end maintains a set of pending objects, adding them to the
map after accumulating sufficient observations exceeding a minimum confidence.
This guards against false positive object detections and prevents poorly-
informed object estimates from influencing the trajectory estimates. Object
initialization uses identity for orientation and the mean dimensions for the
semantic class. The object’s initial position is along the ray through the
bounding box center and the depth is the distance at which the mean height
yields the detected bounding box height.

Associating incoming bounding boxes to past observations is a two-step
process. We first perform local appearance-based matching using ORB features
for the detected bounding boxes. If there are no matches for a bounding box, a
new pending object is created. ObVi-SLAM can thus generate high-quality local
estimates for objects using the same objective function as the main problem,
but optimizing only pending objects. After attaining a good local estimate,
ObVi-SLAM performs geometric matching to determine if the pending object
matches any older objects. If the objects’ centers are close, the pending
object’s detections are merged into the older object and the pending object is
removed. If there are no existing objects that match the pending estimate, a
new object is created. This method allows ObVi-SLAM’s object front-end to
scale with time, as only the features for the most recent bounding boxes are
kept, avoiding long-term aggregation of object appearance data.

##  V Long-Term Map Generation

After SLAM for a deployment session, ObVi-SLAM refines results before creating
a long-term map for subsequent sessions. A final optimization runs over the
full trajectory, first using the model in (2), and then further refining with
(1). This refinement is reserved for the post-processing stage due to
computational complexity.

ObVi-SLAM then checks if any of the objects should be merged into a single
object, as imperfect data association can yield multiple objects for the same
physical entity. To address this, ObVi-SLAM searches for pairs of objects that
have the same semantic class and are in close proximity, then merges the
observations. Global refinement and object merging are repeated until no pairs
of objects can be merged.

Following SLAM execution and refinement, ObVi-SLAM summarizes the information
obtained into a space-efficient long-term object map containing information
only for relationships between objects and the global coordinate frame. Inputs
to the long-term map extraction are the estimates
$\\{Q^{i*}_{1:J^{i}},x^{i}_{1:T^{i}},v^{i}_{1:V^{i}}\\}$ and associations
between observations and estimates. Long-term map extraction has two phases:
dense prior computation and map sparsification.

###  V-A Dense Prior Computation

The dense prior is a marginal distribution over the objects, with visual
features and robot poses marginalized out. As we model the full optimization
problem with a normal distribution, the dense long-term map thus takes the
form

$\displaystyle p($ $\displaystyle
Q^{*}_{1:J^{i}}|{LTM}^{i^{D}})=N(Q^{*}_{1:J^{i}}|\mu_{D},\Sigma_{D})$ (18)
$\displaystyle=N\left(\begin{bmatrix}Q_{1}\\\ \vdots\\\
Q_{J_{i}}\end{bmatrix}\middle|\begin{bmatrix}\mu_{1}\\\ \vdots\\\
\mu_{J_{i}}\end{bmatrix},\begin{bmatrix}\Sigma_{11}&\dots&\Sigma_{1J_{i}}\\\
\vdots&&\vdots\\\
\Sigma_{1J_{i}}^{T}&\dots&\Sigma_{J_{i}J_{i}}\end{bmatrix}\right).$

$\mu_{D}$ and $\Sigma_{D}$ are obtained with an optimization over the factors
to summarize in the long-term map and the Markov blanket of the states to
remove. In our case, we marginalize over the visual feature estimates,
$v_{1:V^{i}}$, and robot pose estimates, $x_{1:T^{i}}$, obtained in session
$i$. Shape priors are repeated across sessions, so these factors are omitted.
Using properties of marginals for a normal distribution, $\mu_{D}$ and
$\Sigma_{D}$ are formed from blocks corresponding to objects from the full
mean and covariance. Thus, $\mu_{D}$ is given by

$\displaystyle\mu_{D}=\underset{Q^{*}_{1:J}}{\mathrm{argmax}}\;$
$\displaystyle\underbrace{p(s_{1:M}|x_{1:T},v_{1:V})}_{\begin{subarray}{c}\text{Reprojection
Error}\end{subarray}}$ (19)
$\displaystyle\underbrace{p(B_{1:N}|Q^{*}_{1:N},x_{1:T})}_{\begin{subarray}{c}\text{Bounding
Box
Error}\end{subarray}}\underbrace{p(Q^{*}_{1:J}|LTM^{i-1})}_{\begin{subarray}{c}\text{Long-
term Map Prior}\end{subarray}}.$

For a least squares optimization problem given by
$y^{*}={\mathrm{argmin}}\;||f(y)-z||^{2},$ where $z$ is a measurement and
$f(y)$ is a predicted measurement given the state $y$, the covariance estimate
$\Sigma_{y}$ is given by $\Sigma_{y}=(J^{T}(y^{*})J(y^{*}))^{-1}$, where
$J(y^{*})$ is the Jacobian of $f$ evaluated at $y^{*}$. Thus, $\Sigma_{D}$ is
obtained using the Jacobian of the optimization expressed in (19), evaluated
at $\mu_{D}$, taking the blocks of the covariance matrix that correspond to
relationships between static objects.

###  V-B Map Sparsification

The dense prior above would increase the computational complexity of
optimization in a subsequent session, as modern optimization libraries rely on
sparsity. To address this, we aim to find a sparsified long-term map that
approximates the dense prior but has fewer correlations between objects in the
map. Sparsification first requires a design step to determine the factor
topology. The generic form for the sparsified long-term map is shown in (16).
Choosing the factor topology can be seen as selecting the functions
$f_{S_{k}}$ that comprise this long-term map representation. Once the factor
topology is determined, the parameters $\mu_{S_{k}}$ and $\Sigma_{S_{k}}$ need
to be found. To make the sparse long-term map prior as close as possible to
the dense prior, $\mu_{S_{k}}$ and $\Sigma_{S_{k}}$ are identified by finding
the values that minimize the KL divergence between the dense prior
$N(Q^{*}|\mu_{D},\Sigma_{D})$, and the sparse long-term map prior in (16).
After $\mu_{S_{k}}$ and $\Sigma_{S_{k}}$ are identified, the values for
$\Sigma_{S_{k}}$ may suggest that a component factor of the sparse long-term
map does not carry significant information, in which case minimally meaningful
components $f_{S_{k}}$ can be removed from the topology and the parameter
identification can be repeated, encouraging further sparsity in $LTM^{i}$.

As noted above, the current version of ObVi-SLAM uses the sparse prior form
with independently, normally-distributed ellipsoids. $LTM^{i}$ thus takes the
form

$\displaystyle p(Q^{*}_{1:J^{i}}|LTM^{i})$
$\displaystyle=N(Q^{*}_{1:J^{i}}|\mu_{S},\Sigma_{S})$ (20)
$\displaystyle=\prod_{j=1}^{J^{i}}N(Q^{*}_{j}|\mu_{S_{j}},\Sigma_{S_{j}}).$
(21)

Using this topology, the KL divergence between the dense long-term map and
sparse long-term map is

$\displaystyle
D_{KL}(p(Q^{*}_{1:J^{i}}|LTM^{i^{D}})||p(Q^{*}_{1:J^{i}}|LTM^{i}))=\frac{1}{2}\Bigl{(}\ln\frac{|\Sigma_{S}|}{|\Sigma_{D}|}$
$\displaystyle-d+(\mu_{S}-\mu_{D})^{T}\Sigma_{S}^{-1}(\mu_{S}-\mu_{D})+\operatorname{Tr}(\Sigma_{S}^{-1}\Sigma_{D})\Bigr{)},$
(22)

with $\Sigma_{S}$ constrained to be a block diagonal matrix with entries
$\Sigma_{S_{j}}$ and $d$ being the dimension of the normal distribution.
Differentiating gives the optimal $\mu_{S}$ equal to $\mu_{D}$ and the optimal
$\Sigma_{S}$ as a block diagonal matrix with the corresponding entries from in
$\Sigma_{D}$, as is consistent with independently distributed ellipsoids. More
specifically, this gives $\mu_{S_{j}}$ as the maximum likelihood estimate for
the $j$th ellipsoid for (19) and $\Sigma_{S_{j}}$ as the covariance
representing the uncertainty after optimization for the $j$th ellipsoid
estimate.

##  VI Experimental Results

We aim to answer the following questions in our evaluation:  (i) How globally
accurate are individual trajectory estimates generated by ObVi-SLAM?  (ii) How
consistent are ObVi-SLAM localization estimates with respect to a global frame
under diverse appearances?  (iii) How accurate are object estimates generated
by ObVi-SLAM?  (iv) How space efficient are ObVi-SLAM maps?  (v) What is the
impact of each component of the formulation for ObVi-SLAM on its performance?
Parameters and code for ObVi-SLAM and our evaluation pipeline can be found in
our github repository.222Code + website: https://github.com/ut-amrl/ObVi-SLAM;
Code uses Ceres Solver [28].

###  VI-A Experiment Setup and Implementation Details

To evaluate our approach, we collected 16 trajectories over two months in an
outdoor campus environment, shown in Fig. 2, with different lighting
conditions, covering varying paths to capture different viewpoints. In each
trajectory, the robot started and ended at the same location, visiting a
subset of six waypoints located consistently across the trajectories. We used
YOLOv5 [29] with a custom model for object detections of tree trunks,
lampposts, benches, and trash cans.

For our evaluations, we used the upright parameterization of objects for ObVi-
SLAM. We compared ObVi-SLAM to ORB-SLAM3 [14], a visual feature-based multi-
session SLAM approach; OA-SLAM [4], a joint object-visual SLAM approach that
uses objects only for relocalization; and DROID-SLAM [30], a learning-based
SLAM approach. For all algorithms, we used stereo image data from a Zed2i
mounted on a Clearpath Jackal. DROID-SLAM does not support map saving, so each
trajectory was evaluated individually. ORB-SLAM3 supports map saving, but
maximum capacity for a map data structure was reached after the seventh
trajectory, so the first seven trajectories were run in sequence and the
remaining nine were run individually starting with the map from the seventh
trajectory. This is denoted in Fig. 3 with a dashed line. OA-SLAM was run with
the same object detections as ObVi-SLAM and maps passed between sessions were
aggregated across the 16 trajectories. Ground truth was obtained by running
LeGO-LOAM [31] with an Ouster OS1 lidar and aligning the individual
trajectories using the waypoints.

Figure 2: Test environment: appearance change at waypoint A; satellite view
with waypoint labels; waypoint D from different perspectives.

###  VI-B Trajectory Accuracy

(a) Translation ATE.

(b) Orientation ATE.

Figure 3: Translation and orientation ATE for ObVi-SLAM and comparison
approaches for each trajectory.

(a) CDF of position deviation.

(b) CDF of orientation deviation.

Figure 4: Estimate consistency for ObVi-SLAM and comparison approaches. An
optimal algorithm would quickly rise to 1. (a) Reference (b) ObVi-SLAM (c)
ORB-SLAM3  (d) OA-SLAM  (e) DROID-SLAM  Figure 5: 16 trajectories through test
environment, shown in meters, as estimated by the approaches with highlighted
pink/purple waypoints. Performance of an approach is good when all estimates
for a given waypoint are colocated.

(a)

(b)

(c)

(d)

Figure 6: Object metrics for ObVi-SLAM and OA-SLAM. (6(a)) Lower quartile,
median, and upper quartile object center error. (6(b)) Lower quartile, median,
and upper quartile IoU between estimates and ground truth. (6(c)) Estimated
objects per ground truth object. (6(d)) Recall.

To understand individual trajectory accuracy, we computed the translational
and rotational absolute trajectory error (ATE) for each approach. We first
aligned each trajectory to the respective reference trajectory to mitigate
against early estimation error skewing results. These results are shown in
Fig. 3. ObVi-SLAM has competitive or lower rotational error compared to the
other approaches. Comparison approaches sometimes have lower error, but ObVi-
SLAM is the only approach with less than 8 degrees of average rotational error
for all trajectories. For translational error, ObVi-SLAM outperforms
comparision approaches on all trajectories.

###  VI-C Localization Consistency Under Varying Conditions

Long-term SLAM approaches must be able to generate estimates for key locations
that are consistent over time. We thus assess long-term robustness by
measuring consistency of estimates for the six waypoints over the 16
trajectories by measuring the deviation for each estimate from the average
estimate for the respective waypoint.

Fig. 4 shows the cumulative distribution functions (CDFs) for the position and
orientation estimate consistency. For rotation estimate consistency, ObVi-SLAM
and DROID-SLAM [30] have notably better performance than ORB-SLAM3 [14] and
OA-SLAM [4], with DROID-SLAM slightly outperforming ObVi-SLAM. However, ObVi-
SLAM notably outperforms all comparison approaches on position estimate
consistency, having no waypoint position estimates more than 4 meters from the
respective average waypoint position.

The trajectories and waypoints estimated by LeGO-LOAM [31] (reference), ObVi-
SLAM, ORB-SLAM3 [14], OA-SLAM [4], and DROID-SLAM [30] are shown in Fig. 5(a).
ORB-SLAM3 lost localization in one trajectory and the remaining trajectories
have rotational drift, caused by features not being recognizable under
viewpoint and lighting changes. OA-SLAM suffered relocalization failures that
present as jumps in the trajectories, resulting from noisy object estimation,
and DROID-SLAM has good orientation consistency, but suffers from scale
inconsistency, despite use of stereo data. ObVi-SLAM, by contrast, has
trajectories that match the reference well and waypoints are closely
colocated.

###  VI-D Object Accuracy

To understand ObVi-SLAM’s object estimation accuracy, we assess four different
metrics using the map result at the end of each evaluated trajectory:  1.
position accuracy: measures the distance between estimate and ground truth
object centers;  2. volume intersection over union (IoU): evaluates volumetric
accuracy by computing the intersection of estimated and ground truth objects,
divided by their union – an IoU of 1.0 indicates a perfect estimate;  3.
estimated objects per ground truth: ratio of number of estimated objects to
ground truth objects, providing insight into the generation of duplicate and
spurious objects; and  4. recall: measures how many ground truth objects were
estimated.  Ground truth data was generated by manually annotating 3D bounding
boxes for 72 objects in a lidar-SLAM point cloud. We aligned estimates with
ground truth frames and matched objects by finding the closest ground truth
object with the same semantic class, allowing for multiple matches per ground
truth object. Position deviation and volume IoU together assess geometric
accuracy, while the remaining metrics examine object instantiation false
positives and negatives.

Fig. 6 shows these metrics for ObVi-SLAM and OA-SLAM [4], as the other
approaches do not estimate objects. OA-SLAM initially exhibits competitive
median position deviation compared to ObVi-SLAM. However, as additional
trajectories are considered, OA-SLAM’s positional accuracy degrades. ObVi-SLAM
maintains position estimate accuracy over time and exhibits notably better IoU
for object estimates. This indicates that OA-SLAM’s object estimates are less
volumetrically accurate. It should be noted most estimated objects are tall
and thin, therefore a small amount of position error can lead to no overlap
between estimates and ground truth, explaining the relatively low IoU for both
approaches. In addition, ObVi-SLAM has better rates of object estimation than
OA-SLAM, producing less duplicate estimates and generating estimates for more
objects than OA-SLAM. The higher object recall also explains in part the
initial higher upper quartile position error: ObVi-SLAM is more aggressive in
generating estimates for objects, initially leading to some less accurate
estimates before sufficient data is obtained, but resulting in fewer missed
objects overall.

###  VI-E Map Space Efficiency

TABLE I: Size of compressed maps after specified trajectories. | Trajectory 1 | Trajectory 7 | Trajectory 16
---|---|---|---
ObVi-SLAM | 30 KB | 51 KB | 51 KB
ORB-SLAM3 | 165 MB | 1.3 GB | -
OA-SLAM | 1.4 MB | 8.6 MB | 17 MB

To assess the space efficiency of the maps, we evaluated the map files’
compressed size after trajectories 1, 7, and 16, shown in Table I. As noted,
DROID-SLAM [30] does not provide functionality for map saving, so it is
excluded. In addition, as ORB-SLAM3[14] could not run more than seven
trajectories sequentially, the map after trajectory 7 is the last attainable.
From these map sizes, it is clear that ObVi-SLAM’s object-only map affords a
much more compact and scalable representation, with orders of magnitude
smaller maps than ORB-SLAM3 and OA-SLAM [4].

###  VI-F Ablations

(a) CDF of position deviation.

(b) CDF of orientation deviation.

Figure 7: Position and orientation consistency for ObVi-SLAM and ablations. An
optimal algorithm would quickly rise to 1.

In addition to comparing against other approaches, we assess the performance
of ObVi-SLAM when individual factors are removed to understand their
importance. These are abbreviated as follows: ObVi-SLAM-S has the shape prior
removed; ObVi-SLAM-VF does not include the visual feature factors; and ObVi-
SLAM-LTM removes the long-term map, resulting in a sequence of individually-
evaluated trajectories. We did not assess ObVi-SLAM without objects, as this
is equivalent to a traditional visual SLAM approach.

The localization consistency results for ObVi-SLAM compared to the ablations
is shown in Fig. 7. ObVi-SLAM-VF is significantly worse than all other
variants, indicating the importance of visual features, with full ObVi-SLAM
outperforming the other variants. We provide ATE and object metrics for the
ablated versions in our github repositoryfootnote 2.

##  VII Conclusion and Future Work

This paper introduces ObVi-SLAM, a long-term SLAM approach that combines the
benefits of visual features and object detections to achieve scalable, long-
term consistent localization amid lighting and viewpoint changes. We
demonstrate that ObVi-SLAM achieves superior performance in single-trajectory
and multi-trajectory localization compared to existing SLAM approaches on 16
trajectories collected over two months with significant lighting variations.

There are several future directions that would build upon developments
introduced in ObVi-SLAM. Creation of a learning-based long-term appearance
descriptor for objects in the scene could improve robustness of inter-session
object association. Further, integrating an object-based change detection
method could aid in removing any stale data from objects incorrectly assumed
to be static. In addition, more complex factor toplogies for the long-term map
prior could be explored to better capture object estimate correlations.
Finally, ObVi-SLAM could be extended to allow loop closure or initial
localization based on the long-term object map.

## References

  * [1] S. Yang and S. Scherer, “CubeSLAM: Monocular 3-D Object SLAM,” _IEEE Transactions on Robotics_ , vol. 35, no. 4, pp. 925–938, aug 2019\. [Online]. Available: https://doi.org/10.1109%2Ftro.2019.2909168
  * [2] L. Nicholson, M. Milford, and N. Sünderhauf, “QuadricSLAM: Dual Quadrics From Object Detections as Landmarks in Object-Oriented SLAM,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 1, pp. 1–8, 2019.
  * [3] K. Ok, K. Liu, K. Frey, J. P. How, and N. Roy, “Robust Object-based SLAM for High-speed Autonomous Navigation,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 669–675.
  * [4] M. Zins, G. Simon, and M.-O. Berger, “OA-SLAM: Leveraging objects for camera relocalization in visual SLAM,” in _2022 IEEE International Symposium on Mixed and Augmented Reality (ISMAR)_. IEEE, 2022, pp. 720–728.
  * [5] Z. Liao, Y. Hu, J. Zhang, X. Qi, X. Zhang, and W. Wang, “SO-SLAM: Semantic Object SLAM With Scale Proportional and Symmetrical Texture Constraints,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 4008–4015, 2022\.
  * [6] S. Song, J. Zhao, T. Feng, C. Ye, and L. Xiong, “Scale Estimation with Dual Quadrics for Monocular Object SLAM,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 1374–1381.
  * [7] Y. Wu, Y. Zhang, D. Zhu, Y. Feng, S. Coleman, and D. Kerr, “EAO-SLAM: Monocular Semi-Dense Object SLAM Based on Ensemble Data Association,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020, pp. 4966–4973.
  * [8] S. Chen, S. Song, J. Zhao, T. Feng, C. Ye, L. Xiong, and D. Li, “Robust Dual Quadric Initialization for Forward-Translating Camera Movements,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4712–4719, 2021\.
  * [9] R. Tian, Y. Zhang, Z. Cao, J. Zhang, L. Yang, S. Coleman, D. Kerr, and K. Li, “Object SLAM With Robust Quadric Initialization and Mapping for Dynamic Outdoors,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–16, 2023.
  * [10] Z. Cao, Y. Zhang, R. Tian, R. Ma, X. Hu, S. Coleman, and D. Kerr, “Object-Aware SLAM Based on Efficient Quadric Initialization and Joint Data Association,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9802–9809, 2022.
  * [11] R. F. Salas-Moreno, R. A. Newcombe, H. Strasdat, P. H. Kelly, and A. J. Davison, “SLAM++: Simultaneous localisation and mapping at the level of objects,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2013, pp. 1352–1359.
  * [12] M. Grinvald, F. Furrer, T. Novkovic, J. J. Chung, C. Cadena, R. Siegwart, and J. Nieto, “Volumetric Instance-Aware Semantic Mapping and 3D Object Discovery,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 3, pp. 3037–3044, July 2019.
  * [13] L. Schmid, J. Delmerico, J. L. Schönberger, J. Nieto, M. Pollefeys, R. Siegwart, and C. Cadena, “Panoptic Multi-TSDFs: a Flexible Representation for Online Multi-resolution Volumetric Mapping and Long-term Dynamic Scene Consistency,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 8018–8024.
  * [14] C. Campos, R. Elvira, J. J. Gómez, J. M. M. Montiel, and J. D. Tardós, “ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual-Inertial and Multi-Map SLAM,” _IEEE Transactions on Robotics_ , vol. 37, no. 6, pp. 1874–1890, 2021.
  * [15] T. Schneider, M. T. Dymczyk, M. Fehr, K. Egger, S. Lynen, I. Gilitschenski, and R. Siegwart, “maplab: An Open Framework for Research in Visual-inertial Mapping and Localization,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1418–1425, 2018.
  * [16] J. Qian, V. Chatrath, J. Yang, J. Servos, A. Schoellig, and S. L. Waslander, “POCD: Probabilistic Object-Level Change Detection and Volumetric Mapping in Semi-Static Scenes,” in _2022 Robotics: Science and Systems (RSS)_ , 2022\.
  * [17] S. Nashed and J. Biswas, “Curating Long-Term Vector Maps,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 4643–4648.
  * [18] J. Vallvé, J. Solà, and J. Andrade-Cetto, “Graph SLAM Sparsification With Populated Topologies Using Factor Descent Optimization,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 1322–1329, 2018.
  * [19] J. Hsiung, M. Hsiao, E. Westman, R. Valencia, and M. Kaess, “Information Sparsification in Visual-Inertial Odometry,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 1146–1153.
  * [20] D. Wilbers, L. Rumberg, and C. Stachniss, “Approximating Marginalization with Sparse Global Priors for Sliding Window SLAM-Graphs,” in _2019 Third IEEE International Conference on Robotic Computing (IRC)_ , 2019, pp. 25–31.
  * [21] M. Zhao, X. Guo, L. Song, B. Qin, X. Shi, G. H. Lee, and G. Sun, “A General Framework for Lifelong Localization and Mapping in Changing Environment,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 3305–3312.
  * [22] I. Ballester, A. Fontán, J. Civera, K. H. Strobl, and R. Triebel, “DOT: Dynamic Object Tracking for Visual SLAM,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 11 705–11 711.
  * [23] B. Bescos, C. Campos, J. D. Tardós, and J. Neira, “DynaSLAM II: Tightly-coupled multi-object tracking and SLAM,” _IEEE robotics and automation letters_ , vol. 6, no. 3, pp. 5191–5198, 2021.
  * [24] M. Gridseth and T. D. Barfoot, “Keeping an Eye on Things: Deep Learned Features for Long-Term Visual Localization,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 1016–1023, 2022.
  * [25] Y. Chen and T. D. Barfoot, “Self-Supervised Feature Learning for Long-Term Metric Visual Localization,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 2, pp. 472–479, 2023.
  * [26] J. Spencer, R. Bowden, and S. Hadfield, “Same features, different day: Weakly supervised feature learning for seasonal invariance,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 6459–6468.
  * [27] R. Mur-Artal and J. D. Tardós, “ORB-SLAM2: an open-source SLAM system for monocular, stereo and RGB-D cameras,” _IEEE Transactions on Robotics_ , vol. 33, no. 5, pp. 1255–1262, 2017.
  * [28] S. Agarwal, K. Mierle, and T. C. S. Team, “Ceres Solver,” 3 2022. [Online]. Available: https://github.com/ceres-solver/ceres-solver
  * [29] G. J. et. al., “ultralytics/yolov5: v6.0 - YOLOv5n ’Nano’ models, Roboflow integration, TensorFlow export, OpenCV DNN support,” Oct. 2021. [Online]. Available: https://doi.org/10.5281/zenodo.5563715
  * [30] Z. Teed and J. Deng, “DROID-SLAM: Deep Visual SLAM for Monocular, Stereo, and RGB-D Cameras,” _Advances in neural information processing systems_ , 2021\.
  * [31] T. Shan and B. Englot, “LeGO-LOAM: Lightweight and Ground-Optimized Lidar Odometry and Mapping on Variable Terrain,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 4758–4765.

##  Appendix A Implementation

There are three notable aspects of implementation not detailed in the paper
body: visual feature pre-processing, two-phase optimization used for outlier
rejection, and modifications for sliding window observation stability.

###  A-A Visual Feature Pre-Processing

Distant and improperly matched features can cause problems for the
optimization. When detected features are far away and viewed from limited
perspectives, their depth is inadequately constrained due to insufficient
parallax and noise in the feature detection can cause the optimal feature
estimate to be very far away. More observations should fix this problem, but
if the feature is initially estimated to be extremely far away, local minima
in the optimization will often cause the estimate to be stuck far away, even
when a closer estimate fits the new observations better. Improper matches that
can occur under repetitive textures can also cause poor initial estimates.

To mitigate against these issues, we added a visual feature preprocessing
phases. For an incoming image, if robot observed a visual feature new to the
factor graph, we begin to maintain a recent observation record of this
feature. After accumulating an adequate number of observations of the same
feature, we compute pairwise epipolar errors between the current frame and all
other associated frames stored in the record. We consider the feature
observations only if their epipolar errors were small when computed against
the majority of frames to reduce outliers from the feature extractions.
Furthermore, we impose a minimum parallax requirement on the pending visual
features to guarantee that their depth estimates are well-constrained. This
requirement mandates that visual features exhibit sufficient disparities in
their pixel observations as well as the robot poses from which those visual
features are observed. If a visual feature meets both the epipolar error and
the minimum parallax criteria, we subsequently add it to the factor graph. On
the other hand, if the newly-detected visual feature has already appeared in
the factor graph, we repeat a similar process to calculate the epipolar errors
between the current frame and previous frames where the same feature had been
observed. If a substantial number of the computed errors are large, we discard
the current feature observation as an outlier.

###  A-B Two-Phase Optimization

One method we have for handling outliers is a two-phase optimization for each
added frame. In the first round of optimization, all factors are included and
the optimization is run with loose convergence parameters so that it finishes
quickly. Following this optimization, we identify the reprojection and
bounding box factors with the highest costs and consider them outliers.
Ignoring estimate adjustments made in the first round, we then rerun the
optimization without these outlier factors so that we can base the estimate on
only inlier observations. We only allow bounding box and visual feature
factors to be excluded in the second phase, as the outlier exclusion primarily
aims to handle incorrect data association; the long-term map prior, visual
odometry factor, and semantic shape prior are not considered for outlier
exclusion.

###  A-C Modifications for Sliding Window Optimization Stability

Without special handling, as the sliding window for local optimization moves
forward, features and objects can become under-constrained as they leave the
window, making their estimates and the estimates for robot poses from which
they are observed susceptible to dramatic changes from overfitting to the
remaining observations in the window. We apply a couple modifications to the
optimization to handle this. First, we set the first few poses in the sliding
window constant for local optimization, so observations that are included
cannot drift substantially due to the fixed observing pose. Second, we exclude
features and objects from the optimization that do not have a minimum number
of observations present in the sliding window. This prevents the optimization
from overfitting to a small number of observations.

##  Appendix B Numerical Stability

###  B-A Ellipsoid Projection

As noted above, if an object intersects the x or y axes of the camera, the
conic projection is not a proper ellipse. This manifests as negative values
under the square roots in (13) and/or (14). There are two possible resulting
projections: an imaginary ellipse and a hyperbola. In both cases, we currently
set the error to a static fixed threshold, but we believe there are possible
improvements to make in this handling. The imaginary ellipse results from the
camera being inside the object, and therefore is not a valid state given any
bounding box observation. An inverse barrier cost term could be added to the
bounding box factor cost, so that there is minimal cost when the camera is not
close to being inside the object estimate, but that the cost increases rapidly
as the camera approaches the object estimate surface. However, an object
estimate could be shifted in local optimization such that the camera could
start inside the object in a later global optimization, violating the boundary
condition while an observing pose is outside the local window. Thus, care must
be taken in inverse barrier function selection or optimization pre-processing
to prevent the estimates from being stuck in this bad state.

Figure 8: Simplified demonstration of problematic ellipsoid projection, shown from an angle, top down, and from the front. For an object with identity orientation and height, width, and length of 1 m and camera centered at the origin, projection will fail if the object’s center falls within either cylinder above. The dimensions of the object change the radii of the elliptic cylinders.  TABLE II: Absolute Trajectory Error for Translation and Orientation. Best results are bolded and second-best are italicized. | Translation (m) | Orientation (deg)
---|---|---
Traj Num | ObVi-SLAM | OA-SLAM | ORB-SLAM3 | DROID-SLAM | ObVi-SLAM | OA-SLAM | ORB-SLAM3 | DROID-SLAM
1 | 0.24 | 0.31 | 0.67 | 1.39 | 1.7 | 1.6 | 2.0 | 1.9
2 | 0.55 | 3.32 | 1.2 | 4.76 | 2.0 | 1.7 | 2.8 | 2.4
3 | 0.84 | 3.99 | 2.36 | 4.92 | 6.2 | 19.1 | 12.0 | 2.2
4 | 0.33 | 0.6 | 1.7 | 3.96 | 1.9 | 1.8 | 2.2 | 13.6
5 | 0.33 | 1.11 | 1.11 | 3.86 | 1.8 | 1.1 | 1.7 | 2.5
6 | 0.41 | 1.31 | 0.98 | 4.1 | 1.9 | 2.0 | 1.7 | 2.2
7 | 0.25 | 1.21 | 0.83 | 4.21 | 1.7 | 1.3 | 1.7 | 2.2
8 | 0.47 | 2.66 | 1.8 | 3.59 | 2.2 | 4.4 | 3.2 | 2.3
9 | 0.49 | 9.14 | 7.27 | 4.79 | 2.2 | 42.7 | 46.7 | 2.2
10 | 0.58 | 0.96 | 6.82 | 3.12 | 2.5 | 1.1 | 6.7 | 3.3
11 | 0.31 | 0.6 | 0.5 | 2.05 | 2.3 | 1.6 | 1.6 | 11.1
12 | 0.36 | 0.94 | 0.67 | 7.69 | 1.9 | 1.4 | 1.7 | 2.5
13 | 0.57 | 1.0 | 0.91 | 4.84 | 7.3 | 1.0 | 1.8 | 3.1
14 | 0.87 | 6.44 | 2.29 | 6.82 | 4.2 | 14.9 | 4.9 | 2.7
15 | 0.8 | 10.94 | 1.38 | 4.55 | 4.9 | 55.3 | 2.0 | 2.3
16 | 0.18 | 4.48 | 1.35 | 3.42 | 1.6 | 22.6 | 2.9 | 2.2
Overall | 0.51 | 4.21 | 2.91 | 4.49 | 3.3 | 18.4 | 12.3 | 4.9

The hyperbolic case results from either the x or y axes of the camera
intersecting the object, but not both. A simplified example is shown in Fig.
8. This case can occur for long objects observed at the edge of the frame for
which the object extends behind the camera. For example, we observed this when
the robot passed benches. In the hyperbolic case, recovery for either the x or
y limits of the projection bounding box fails and the other yields two real
values, only one of which is correct; the other results from projection of the
object’s extent behind the camera. Because this case corresponds to valid
relative object-camera estimates, a more appropriate method for handling this
case would not penalize such circumstances. An improved way to include this in
the cost is to identify the hyperbola branch corresponding to the portion of
the object in front of the camera, and then for the unrecoverable bounds, use
the intersection of that hyperbola branch with the image boundaries.

###  B-B Covariance Estimation

As noted above, covariance $\Sigma_{y}$ for a least squares problem is
computed from the Jacobian $J(y^{*})$ with
$\Sigma_{y}=(J^{T}(y^{*})J(y^{*}))^{-1}$. The presence of an inverse in this
operation means that the Jacobian must be full rank in order to compute the
covariance $\Sigma_{y}$. Floating point calculations and approximations for
matrix inverses used in optimization libraries exacerbate this problem,
requiring the condition number to be below some threshold. In some cases, we
observed that these requirements were not met, leading to failure to extract
the covariance estimates for the ellipsoids. One such cause of these failures
is objects that have the nearly same dimension in the x and y directions,
leading to an under-constrained orientation. Another example is very distant
features, for which changes to the distance from the camera do not notably
alter the reprojected feature location.

Singularities in matrix inversion can be addressed by adding to the diagonal
entries of the matrix. Using this concept to mitigate the covariance
extraction problem, we added a retry system to add small residuals to the
least constrained parameters if initial covariance recovery failed. When we
detect such a failure, we find the degree of rank deficiency $n$ and identify
the $n+1$th smallest column norm and use this as the minimum desired norm. For
columns with smaller norms than the target, we add an additional prior for the
individual parameter that increases the norm to match the target and then
retry covariance extraction. The adjustments applied were quite small, leading
to very minor differences in covariance estimation that will not meaningfully
alter the optimization result in a subsequent session.

##  Appendix C Experiment Setup

In order to assess localization consistency under varying conditions, we
needed to stop at a set of waypoints consistent across the trajectories. To
ensure that these locations were actually consistent, we marked the selected
locations with clear tape that the wheels should be aligned to when the robot
visited the waypoint. During data collection, when we stopped at a waypoint,
we marked the timestamp at which the waypoint was visited. The waypoint
locations were then computed using the pose for the image with the timestamp
closest to the recorded timestamp. Reference trajectories for absolute
trajectory error and Fig. 5(a) were obtained from LeGO-LOAM [31] using a
128-beam OS1 lidar. To verify that these results were of sufficient quality to
serve as ground-truth, we inspected the map consistency after each trajectory
evaluation as well as the consistency of the start and end position estimates,
as all trajectories started and ended at the same location. Owing to the
density of the sensor and high visibility through the whole evaluation area,
LeGO-LOAM was able to produce consistent maps and trajectories without
observable drift with the start and end pose estimates very well aligned. As
LeGO-LOAM trajectories were run independently without a global map, the LeGO-
LOAM trajectories were collectively aligned for Fig. 5(a) by minimizing the
spread of their waypoint estimates.

(a)

(b)

(c)

(d)

Figure 9: Object accuracy metrics by trajectory for ObVi-SLAM and
ablations.(9(a)) Lower quartile, median, and upper quartile object center
error. (9(b)) Lower quartile, median, and upper quartile IoU between estimates
and ground truth. (9(c)) Estimated objects per ground truth object. (9(d))
Recall.

(a) ObVi-SLAM

(b) OA-SLAM

Figure 10: Object estimates after trajectory 11. Estimated objects are shown
in red and ground truth objects are in cyan.

(a) Position ATE.

(b) Orientation ATE.

Figure 11: Position and orientation ATE for ObVi-SLAM and ablations for each
trajectory.

##  Appendix D Expanded Results

Table II shows the absolute trajectory errors depicted in Fig. 3, with the
best results for each trajectory bolded. Fig. 10 shows the object estimates
from ObVi-SLAM and OA-SLAM compared to the ground truth objects. These results
align with the quantitative results in Fig. 6, which show that OA-SLAM has
generally worse geometrically accurate object estimates and more duplicated
objects.

##  Appendix E Complete Ablation Results

In this section, we provide the ablation study metrics not included in the
main paper. Position and orientation ATE for ObVi-SLAM compared to the
ablations are shown in Fig. 11. ObVi-SLAM-VF is significantly worse than all
other variants, indicating the importance of visual-feature estimation for
trajectory accuracy, with full ObVi-SLAM generally slightly outperforming the
other variants. Object metrics for ObVi-SLAM and the ablated versions are
shown in Fig. 9. Object geometric accuracy in Figs. 9(a) and 9(b) is poor for
ObVi-SLAM-VF and ObVi-SLAM-S, demonstrating the importance of both visual
features and the semantic shape prior. ObVi-SLAM-LTM occasionally demonstrates
performance on par with or slightly superior to ObVi-SLAM, though it more
often performs worse. This indicates that carrying object information between
sessions is not always critical, but provides a floor for object geometry
estimate accuracy. ObVi-SLAM-VF and ObVi-SLAM-S also perform similarly poorly
on the erroneous object estimation rates shown in Figs. 9(c) and 9(d). ObVi-
SLAM-LTM does perform slightly better than ObVi-SLAM in the average number of
estimated objects per ground-truth object, but is substantially worse at
ensuring estimates exist for each ground truth object. This is not surprising,
as false positives generated in one session aren’t carried forward when the
long-term map is removed, but also means that objects must be sufficiently
viewed in every session to be included in the long-term map, which is often
not the case under varying paths.


# On edge-girth-regular graphs: lower bounds and new families

István Porupsánszki 111This research was supported in part by the Hungarian
National Research, Development and Innovation Office OTKA grant no. SNN
132625222Department of Geometry and MTA-ELTE Geometric and Algebraic
Combinatorics Research Group, Eötvös Loránd University, 1117 Budapest, Pázmány
s. 1/c, Hungary

## Abstract

An edge-girth-regular graph $egr(n,k,g,\lambda)$ is a $k-$regular graph of
order $n$, girth $g$ and with the property that each of its edges is contained
in exactly $\lambda$ distinct $g-$cycles. We present new families of edge-
girth regular graphs arising from generalized quadrangles and pencils of
elliptic quadrics.
An $egr(n,k,g,\lambda)$ is called extremal for the triple $(k,g,\lambda)$ if
$n$ is the smallest order of any $egr(n,k,g,\lambda)$. We give new lower
bounds for the order of extremal edge-girth-regular graphs using properties of
the eigenvalues of the adjacency matrix of a graph.

##  1 Introduction

This paper deals with simple, finite graphs, i.e., undirected graphs with no
loops and no multiple edges.A graph is $k-$regular if every vertex has exactly
$k$ distinct neighbours. It is of girth $g$ if its smallest cycle consists of
$g$ edges. A $g-$cycle or girth cycle is a cycle of length $g$. The number of
vertices is called the order of the graph.
In extremal graph theory, one often considers a problem with the following
type: we fix some graph parameters or some graph properties and want to deduce
the extremal number of another parameter (in many cases, the number of
vertices or edges). The problem considered in our paper is motivated by the
cage problem. Jajcay, Kiss, and Miklavič [6] defined a new type of regularity.

######  Definition 1.1.

An edge-girth-regular graph is a k-regular graph of order $n$, girth $g$, and
with the property that each of its edges is contained in exactly $\lambda$
distinct $g-$cycles. They are denoted by $egr(n,k,g,\lambda)$.
An $egr(n,k,g,\lambda)$ is called extremal for the triple $(k,g,\lambda)$ if
$n$ is the smallest order of any $egr(n,k,g,\lambda)$. We denote the order of
this extremal graph with $n(k,g,\lambda)$. If $G$ is an extremal bipartite
$egr(n,k,g,\lambda)$, then we denote its order with $n_{2}(k,g,\lambda)$.

The widely studied cage problem consists of finding $k-$regular graph of girth
$g$ and minimal order, which we call a $(k,g)-$cage. For $k=2$ the
$(k,g)-$cages are the $g-$cycles so without loss of generality, we assume that
$k>2$ throughout this paper.

######  Theorem 1.2 (Moore bound [2]).

Let $G$ be a $k-$regular graph of girth $g$ with $k>2$. Then the order of $G$
is at least $n_{0}(k,g)$, where

$n_{0}(k,g)=\begin{cases}\frac{k(k-1)^{\frac{g-1}{2}}-2}{k-2},\quad\text{if g
is odd;}\\\ \frac{2(k-1)^{\frac{g}{2}}-2}{k-2},\quad\text{~{}~{}if g is
even.}\end{cases}$

If a $G$ graph is a $(k,g)-$cage of order $n_{0}(k,g)$, then it is called a
Moore cage. The motivation behind the definition of edge-girth-regularity is
the fact that all of the Moore cages are also edge-girth-regular graphs.
Recently, Drglin, Filipovski, Jajcay, and Raiman in [5] improved the lower
bounds of the order of edge-girth-regular graphs.

######  Theorem 1.3 (Drglin, Filipovski, Jajcay, Raiman).

Let $k$ and $g$ be a fixed pair of integers greater than or equal to $3$, and
let $\lambda\leq(k-1)^{\frac{g-1}{2}}$, if $g$ is odd and
$\lambda\leq(k-1)^{\frac{g}{2}}$ if $g$ is even. Then

$n(k,g,\lambda)\geq
n_{0}(k,g)+\begin{cases}(k-1)^{\frac{g-1}{2}}-\lambda,\quad\text{if g is
odd;}\\\ \left\lceil
2\frac{(k-1)^{\frac{g}{2}}-\lambda}{k}\right\rceil,\quad\text{~{}~{}if g is
even.}\end{cases}$

Moreover,

$n_{2}(k,g,\lambda)\geq
n_{0}(k,g)+2\left\lceil\frac{(k-1)^{\frac{g}{2}}-\lambda}{k}\right\rceil.$

######  Remark 1.4.

This theorem gives us a $\Theta\left(k^{\left[\frac{g}{2}\right]-1}\right)$
lower bound for the order of extremal $egr(n,k,g,\lambda)$ graphs.

The paper is organized as follows. In Section 2, we introduce new families of
edge-girth-regular graphs arising from generalized quadrangles and pencils of
elliptic quadrics. In Section 3, we prove that the second family of edge-
girth-regular graphs constructed in Section 2 is extremal. Here we use the
properties of the eigenvalues of the adjacency matrix of a graph to give new
lower bounds for the order of extremal edge-girth regular graphs of even
girth. In Section 4, with a useful lemma, we extend the lower bounds to edge-
girth-regular graphs of odd girth.

##  2 New families of edge-girth regular graphs

This section introduces two infinite families of bipartite edge-girth-regular
graphs arising from generalized quadrangles and pencils of elliptic quadrics.
For a detailed introduction to generalized polygons, ovoids, spreads and
quadrics, we refer the reader to the books [8] and [9].

######  Definition 2.1.

Let $\Pi$ be a finite projective plane of order $q$. A biaffine plane is
obtained from $\Pi$ by choosing a point-line pair $(P,l)$ and deleting $P$,
$\ell$, all the lines incident with $P$ and all the points belonging to
$\ell$. If the point-line pair is incident in $\Pi$, then we call the biaffine
plane type 1, otherwise, type 2.

It was proved by Araujo-Pardo and Leemans [1] that the incidence graph of a
biaffine plane of type 1 is an extremal bipartite edge-girth-regular graph.

######  Theorem 2.2 (Araujo-Pardo, Leemans).

The incidence graph $\mathcal{B}_{q}$ of the biaffine plane of order $q$ of
type 1 is an extremal $egr(2q^{2},q,6,(q-1)^{2}(q-2))$ graph.

It was proved by Kiss, Miklavič, and Szőnyi [7] that the other type of
biaffine plane also gives us a new family of edge-girth-regular. We show that
this graph is also extremal.

######  Theorem 2.3.

The incidence graph $\mathcal{B}_{q}$ of a biaffine plane of order $q$ of type
2 is an extremal $egr(2q^{2}-2,q,6,(q-1)(q^{2}-3q+3))$ graph.

###### Proof.

The lower bound in Theorem 1.3 gives that

$n_{2}(q,6,(q-1)(q^{2}-3q+3))\geq
2(q^{2}-q+1)+2\left\lceil\frac{(q-1)^{3}-(q-1)(q^{2}-3q+3))}{q}\right\rceil=$
$=2(q^{2}-q+1)+2(q-2)=2q^{2}-2.$

The order of $\mathcal{B}_{q}$ is exactly $2q^{2}-2$. Hence it is an extremal
bipartite edge-girth-regular graph. ∎

The previous results can be extended to generalized quadrangles in the natural
way. However, only the case of type $1$ gives us a new family of edge-girth-
regular graphs.

######  Lemma 2.4.

Let $\mathcal{Q}_{q}$ be a generalized quadrangle of order $(q,q)$, $P$ a
point and $\\{e_{0},e_{1},\ldots,e_{q}\\}$ the set of lines incident with $P$.
Consider the incidence graph $\mathcal{C}_{q}$ that is obtained from the
generalized quadrangle by deleting $P$, all the points belonging to the set of
lines $\\{e_{0},e_{1},\ldots,e_{q}\\}$, and all the lines that are incident
with a point belonging to $e_{0}$. Then $\mathcal{Q}_{q}$ is a $q-$regular
graph of order $2q^{3}$ and girth $8$.

###### Proof.

By definition, $\mathcal{C}_{q}$ is obtained by deleting $1+(q+1)q$ points and
$q+1+q^{2}$ lines, hence $\mathcal{C}_{q}$ has
$2(q^{3}+q^{2}+q+1)-2(q^{2}+q+1)=2q^{3}$ vertices. We show now that
$\mathcal{C}_{q}$ is $q-$regular. Note that for every non-incident point-line
pair $(P,l)\in\mathcal{Q}_{q}$ there exists a unique point-line pair
$(P^{\prime},l^{\prime})$ such that
$P\mathrm{I}l^{\prime}\mathrm{I}P^{\prime}\mathrm{I}l$, where $\mathrm{I}$
denotes the incidence relation. We can use this fact for regularity. Every
deleted line has a point incident with $e_{0}$, hence every point has exactly
one deleted line because of the previous fact. On the other hand, every
deleted point has a line incident with $P$, hence every point has exactly one
deleted line. These induce that $\mathcal{C}_{q}$ is $q-$regular because the
incidence graph of $\mathcal{Q}_{q}$ is $(q+1)-$regular. The $\mathcal{C}_{q}$
graph is contained in the incidence graph of $\mathcal{Q}_{q}$, hence the
length of the minimal cycle of $\mathcal{C}_{q}$ is at least $8$.
∎

######  Theorem 2.5.

Suppose a generalized quadrangle of order $(q,q)$ exists. Then there exists an
$egr(2q^{3},q,8,(q-1)^{2}((q-2)^{2}+1)$ graph.

###### Proof.

We show that every edge of the graph $\mathcal{C}_{q}$ constructed in the
previous lemma is contained in exactly $(q-1)^{2}((q-2)^{2}+1)$ $8-$cycles.
Let $C=(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6},u_{7},u_{8})$ be a $8-$cycle. We
count how many unchanged $8-$cycles contain the edge $(u_{1},u_{2})$. Without
loss of generality, we may assume that $u_{1}$ is a line and $u_{2}$ is a
point. Then we have $(q-1)$ possible choices for the neighbours $u_{3}\neq
u_{1}$ and $u_{4}\neq u_{2}$.

There are two types of $u_{5}$: one intersects the same line $e_{i}$ that is
connected with $u_{1}$ and the other $q-1$ possible choices. Let us denote
that unique line by $u_{5}^{\prime}$ and any other neighbour of $u_{4}$ by
$u_{5}$. The intersection of $e_{i}$ and $u_{0}$ can be connected uniquely
with $u_{5}$, hence we have $q-2$ choices for $u_{6}$, but $u_{6}$ and $u_{1}$
uniquely define $u_{7}$ and $u_{8}$. Similarly, we have $q-1$ possible choices
for the neighbour of $u_{5}^{\prime}$ and $u_{6}^{\prime}$ and $u_{1}$
uniquely define $u_{7}$ and $u_{8}$. So far, we have
$(q-1)^{2}((q-2)^{2}+q-1)$ different $8-$cycles that contain the edge
$(u_{1},u_{2})$. Unfortunately, the line $u_{7}$ is sometimes deleted. We have
to count these cases and subtract the result to get the exact value.

We have $(q-1)$ possible choices for a neighbour $u_{3}\neq u_{1}$ and a
neighbour $u_{8}\neq u_{2}$. There is a unique deleted line through $u_{8}$,
we denote it by $u_{7}$. The intersection of $e_{j}$ and $u_{3}$ can be
connected uniquely with $u_{7}$, hence we have $q-2$ choices for $u_{6}$. Now,
$u_{4}$ and $u_{5}$ are uniquely defined by $u_{3}$ and $u_{6}$. So we have
$(q-1)^{2}(q-2)$ distinct $8-$cycles that contain the edge $(u_{1},u_{2})$
when $u_{7}$ is deleted. Therefore the number of $8-$cycles that contain a
certain edge in $C_{q}$ is

$(q-1)^{2}((q-2)^{2}+q-1)-(q-1)^{2}(q-2)=(q-1)^{2}((q-2)^{2}+1).$

∎

######  Corollary 2.6.

If $q$ is a prime power, then there exists a generalized quadrangle of order
$(q,q)$ therefore there exists an $egr(2q^{3},q,8,(q-1)^{2}((q-2)^{2}+1)$
graph.

######  Remark 2.7.

Theorem 1.3 gives the lower bound

$n_{2}\left(q,8,(q-1)^{2}((q-2)^{2}+1))\right)\geq 2(q^{3}-6q+10).$

The excess is $2(6q-10).$ We can get a slightly better result in a very
special case.

######  Theorem 2.8 (Kiss, Miklavič, Szőnyi [7]).

Let $\mathcal{G}=(\mathcal{P},\mathcal{L},\mathrm{I})$ be a generalized
quadrangle of order $q$ which admits both an ovoid $\mathcal{O}$ (a set of
$q^{2}+1$ points, no two of which are collinear) and a spread $\mathcal{S}$ (a
set of $q^{2}+1$ line, no two of which intersect). Delete the points of
$\mathcal{O}$ and the lines of $\mathcal{S}$. Then the Levi graph of
$(\mathcal{P}\setminus\mathcal{O},\mathcal{L}\setminus\mathcal{S},\mathrm{I})$
is an $egr(2q(q^{2}+1),q,8,(q-1)^{2}(q-2)^{2}).$

######  Remark 2.9.

Theorem 1.3 gives the lower bound

$n_{2}\left(q,8,(q-1)^{2}(q-2)^{2})\right)\geq 2(q^{3}-5q+8).$

The excess is $2(6q-8),$ and it is slightly better than the previous
construction. However, the only known generalized quadrangles admitting both
an ovoid and a spread are the generalized quadrangles $W(q)$ for $q$ even. The
construction in Lemma 2.4 works for any generalized quadrangle of order
$(q,q)$.

Our next construction is based on the following theorem whose proof can be
found for example in [4] or [10]. This is an extremal bipartite edge-girth-
regular graph and is special in that its parameter $\lambda$ is relatively
small compared to the previously seen graphs.

######  Theorem 2.10.

The points of $PG(3,q)$ can be covered by the union of $q+1$ pairwise disjoint
elliptic quadrics. The elements of the covering form a pencil of quadrics.

An important property of elliptic quadrics is that they are also ovoids, so
they do not have three collinear points.

######  Theorem 2.11.

Let $q$ be a prime power. Then there exists a bipartite
$egr(2(q^{3}+q^{2}+q+1),q^{2}+q+1,4,q^{3}+q^{2})$ graph.

###### Proof.

Let make two copies of the points of $PG(3,q)$ and denote the sets with
$\mathcal{P}$ and $\mathcal{P}$’, respectively. Similarly, $p\in\mathcal{P}$
and $p^{\prime}\in\mathcal{P}^{\prime}$ represent the same point.
By the previous theorem, we construct the edges of the graph in the following
way. Every point $P$ is contained in exactly one ovoid. In this ovoid, there
is a unique tangent plane $S_{p}$ through $p$. Let $(p,r^{\prime})\in E$ if
and only if $r\in S_{p}$. Now we show that this graph is a bipartite edge-
girth-regular graph.
First, we prove that every plane is a tangent plane for exactly one point,
therefore it is a bijection. Let $p$ be a point and $S_{p}$ its tangent plane.
The other $q$ ovoids intersect $S_{p}$ in at most $(q+1)$ points since an oval
of a plane contains $(q+1)$ points But if we use this upper bound, we get

$1+q(q+1)=q^{2}+q+1.$

It is the number of points of $S_{p}$, therefore it is indeed a bijection
between the points and planes. Now we focus on determining the parameters of
the graph. It is bipartite and has a valency of $(q^{2}+q+1).$ (For every
point $p$ $(p,p^{\prime})\in E$.)
Since it is a bipartite graph, its girth must be even so now it is enough to
show that every edge is contained in exactly $q^{3}+q^{2}$ distinct
$4-$cycles. Suppose that $p_{1}p_{2}^{\prime}\in E$, so equivalently $p_{2}\in
S_{p_{1}}$. We finish the $4-$cycle
$(p_{1},p_{2}^{\prime},p_{3},p_{4}^{\prime})$ and count the number of possible
ways it can be done. For $p_{4}^{\prime}\in S_{p_{1}}$ we $|S_{p}|-1=q^{2}+q$
possible choices since $p_{2}^{\prime}$ is already taken. $p_{2}$ and $p_{4}$
is contained in exactly $q+1$ planes. Each plane is a tangent plane for a
unique point, therefore for $p_{3}$ we have $q+1-1=q$ possible choices. Now we
have that each edge is contained in exactly $(q^{2}+q)q=q^{3}+q^{2}$ distinct
$4-$cycles. ∎

######  Remark 2.12.

Theorem 1.3 gives the lower bound

$n_{2}(q^{2}+q+1,4,q^{3}+q^{2})\geq 4q^{2}+2q+2.$

This is much lower than the orders of the previously constructed graphs. In
the next section, we prove that this graph is an extremal bipartite edge-girth
regular graph.

##  3 A new lower bound for the order of edge-girth regular graphs of even
girth

We recall the most important properties of eigenvalues of adjacency matrices.
The proofs of the following theorems can be found in [3].

######  Definition 3.1.

The adjacency matrix $A(G)$ of a simple graph $G=(V,E)$ is defined as follows:
it is a symmetric matrix of size $|V|\times|V|$ labeled by the vertices of
$G$, and

$A(G)_{u,v}=\begin{cases}1,~{}if~{}(u,v)\in E(G)\\\ 0,~{}if~{}(u,v)\not\in
E(G)\end{cases}$

######  Proposition 3.2.

If $G$ is a simple graph, then the eigenvalues of its adjacency matrix $A$
satisfies $\sum\lambda_{i}=0$ and $\sum\lambda_{i}^{2}=2e(G)$, where $e(G)$
denotes the number of edges of G.
In general, $\sum\lambda_{i}\ell$ counts the number of closed walks of length
$\ell$.

Let us now focus on the largest and the smallest eigenvalues denoted by
$\lambda_{1}$ and $\lambda_{n}$, respectively.

######  Theorem 3.3.

(a) We have $|\lambda_{n}|\leq\lambda_{1}$.
(b) Let $G$ be a connected graph and assume that $-\lambda_{n}$ =
$\lambda_{1}$. Then $G$ is bipartite.
(c) $G$ is a bipartite graph if and only if its spectrum is symmetric to $0$.

######  Theorem 3.4.

Let $G$ be a $k$-regular graph. Then $\lambda_{1}=k$ and its multiplicity is
the number of components. Every eigenvector belonging to $k$ is constant on
each component. In particular, the multiplicity of $\lambda_{1}$ is $1$ for
connected graphs.

First, we consider the case $g=4$. Later on, we generalize it for even girth.

######  Theorem 3.5.

Let $G$ be an extremal $egr(n,k,4,\lambda)$ graph. Then

$n=n(k,4,\lambda)\geq\frac{k^{3}-2k^{2}+2k-1+\lambda}{\lambda+k-1}.$

If $G$ is an extremal bipartite $egr(n,k,4,\lambda)$ graph, then

$n=n_{2}(k,4,\lambda)\geq\frac{2(k^{3}-2k^{2}+2k-1+\lambda)}{\lambda+k-1}.$

###### Proof.

By Theorem 3.4, $\lambda_{1}=k$ because $G$ is $k-$regular. The number of
closed walks of length $\ell$ equals $\sum\lambda_{i}^{\ell}$. The number of
closed walks of length two equals to twice the number of edges. If we count
the number of incident (point, edge) pairs in two ways, we get $2|e(G)|=nk.$
Now we have

$\sum_{i=1}^{n}\lambda_{i}^{2}=2|e(G)|=nk.$

Similarly, we calculate the number of closed walks of length four. We have two
cases depending on whether the closed walk is a circle or not. The number of
$4$-cycles is $nk\lambda$, because we can start at any vertex, every vertex is
incident with $k$ edges and every edge is contained in exactly $\lambda$
distinct $4-$cycles. If a closed walk of length four does not contain cycles,
then its undirected edges form a tree with two edges. Choose any vertex for
the first point of the closed walk. We have $k$ possible choices for the
second vertex. If the third vertex is the first one, then we again have $k$
possible choices for the fourth vertex. If the first and third vertices are
different, then the fourth vertex must be the same as the second one, thus the
number of closed walks of length four

$\sum_{i=1}^{n}\lambda_{i}^{4}=nk\lambda+nk^{2}+nk(k-1)=nk(\lambda+2k-1).$

$G$ is $k-$regular therefore $\lambda_{1}=k$. Now we have the following
equalities:

$\sum_{i=2}^{n}\lambda_{i}^{2}=nk-k^{2},$
$\sum_{i=2}^{n}\lambda_{i}^{4}=nk(\lambda+2k-1)-k^{4}.$

Using the inequality between the arithmetic and quadratic means for the set
$\\{\lambda_{2}^{2}\ldots\lambda_{n}^{2}\\}$ and some equivalent operations,
we get the first inequality:

$\left(\frac{\sum_{i=2}^{n}\lambda_{i}^{2}}{n-1}\right)^{2}\leq\frac{\sum_{i=2}^{n}\lambda_{i}^{4}}{n-1},$
$\left(\frac{nk-k^{2}}{n-1}\right)^{2}\leq\frac{nk(\lambda+2k-1)-k^{4}}{n-1},$
$(nk-k^{2})^{2}\leq(n-1)(nk(\lambda+2k-1)-k^{4}),$ $n^{2}k-2k^{2}n+k^{3}\leq
n^{2}(\lambda+2k-1)-n(\lambda+2k-1)-nk^{3}+k^{3},$
$n(k^{3}-2k^{2}+2k-1+\lambda)\leq n^{2}(\lambda+k-1),$
$\frac{k^{3}-2k^{2}+2k-1+\lambda}{\lambda+k-1}\leq n.$

If $G$ is $k-$regular and bipartite, then $\lambda_{1}=k=-\lambda_{n}$, hence
we have the following equalities:

$\sum_{i=2}^{n-1}\lambda_{i}^{2}=nk-2k^{2},$
$\sum_{i=2}^{n-1}\lambda_{i}^{4}=nk(\lambda+2k-1)-2k^{4}.$

In the same way, using the inequality between the arithmetic and quadratic
means for the set $\\{\lambda_{2}^{2}\ldots\lambda_{n-1}^{2}\\}$ and some
equivalent operations, we get the second inequality:

$\frac{2(k^{3}-2k^{2}+2k-1+\lambda)}{\lambda+k-1}\leq n.$

∎

######  Corollary 3.6.

The complete bipartite graph $K_{k,k}$ is an extremal bipartite
$egr(2k,k,4,(k-1)^{2})$ graph.

###### Proof.

The only property we have to check is that $K_{k,k}$ extremal. Theorem 3.5
gives the lower bound

$n_{2}(k,4,(k-1)^{2})\geq
2\frac{k^{3}-2k^{2}+2k-1+(k-1)^{2}}{(k-1)^{2}+k-1}=2\frac{k^{3}-k^{2}}{k^{2}-k}=2k.$

∎

######  Theorem 3.7.

The graph constructed in Theorem 2.11 is an extremal bipartite
$egr(2(q^{3}+q^{2}+q+1),q^{2}+q+1,4,q^{3}+q^{2})$ graph.

###### Proof.

The previous inequality gives a lower bound for
$n_{2}(q^{2}+q+1,4,q^{3}+q^{2})$ and it is exactly $2(q^{3}+q^{2}+q+1).$ ∎

######  Theorem 3.8.

áIf a bipartite $egr(n,k,4,\lambda)$ graph satisfies the inequality of Theorem
3.5 with equality, then its spectrum is

$\left\\{-k^{(1)};-\sqrt{\frac{nk-2k^{2}}{n-2}}^{\left(\frac{n-2}{2}\right)};\sqrt{\frac{nk-2k^{2}}{n-2}}^{\left(\frac{n-2}{2}\right)};k^{(1)}\right\\}.$

###### Proof.

The proof of Theorem 3.5 is based on the inequality between the arithmetic and
quadratic means. Thus equality holds if and only if
$\lambda_{2}^{2}=\ldots=\lambda_{n-1}^{2}$. We know the sum of these numbers:

$\sum_{i=2}^{n-1}\lambda_{i}^{2}=nk-2k^{2}.$

Hence

$(n-2)\lambda_{2}^{2}=nk-2k^{2},$ $\lambda_{2}^{2}=\frac{nk-2k^{2}}{n-2}.$

The spectrum of a bipartite graph is symmetric to $0$, therefore if $G$ is an
extremal bipartite $egr(n,k,4,\lambda)$ graph and its order satisfies the
inequality in Theorem 3.5, then the spectrum of $G$ is

$\left\\{-k^{(1)};-\sqrt{\frac{nk-2k^{2}}{n-2}}^{\left(\frac{n-2}{2}\right)};\sqrt{\frac{nk-2k^{2}}{n-2}}^{\left(\frac{n-2}{2}\right)};k^{(1)}\right\\}.$

∎

######  Corollary 3.9.

The spectrum of the graph constructed in Theorem 2.11 is

$\left\\{-(q^{2}+q+1)^{(1)};-q^{\left(q^{3}+q^{2}+q\right)};q^{\left(q^{3}+q^{2}+q\right)};(q^{2}+q+1)^{(1)}\right\\}.$

######  Remark 3.10.

This corollary also shows the strength of the inequality: if the spectrum of a
bipartite edge-girth-regular graph of girth $4$ consists of four distinct
eigenvalues, then the graph is an extremal bipartite edge-girth-regular graph.

Theorem 3.5 can be generalized for higher even girths, however, the results
and the formulas are less elegant.

######  Definition 3.11.

Let $G$ be an $egr(n,k,g,\lambda)$ graph. Let $c(\ell,k)$ denote the number of
closed walks of length $\ell$ starting of a vertex $v$ that do not contain
circles.

######  Proposition 3.12.

Let $\ell=2s$ be an even number. If $\ell\leq g+1$, then $c(\ell,k)$ is a
polynomial of $k$ of degree $\frac{\ell}{2}$ and its value does not depend on
the choice of the vertex $v$. In this case the main coefficient of $c(2s,k)$
is the $s$-th Catalan number

$C_{s}=\binom{2s}{s}-\binom{2s}{s+1}.$

Moreover,

$C_{s}k(k-1)^{s-1}\leq c(2s,k)\leq C_{s}k^{s}.$

###### Proof.

If we consider the fact that at each step, we either increase the distance
from $v$ by one or decrease it by one, then we get that in such a closed walk,
we increased this distance $s-$times. If we decrease the distance, then the
walk goes through the previous edge. If we increase the distance, we have $k$
possible choices when we are at the starting vertex, and $k-1$ possible
choices otherwise. If the main coefficient is $C$, then we proved that
$c(2s,k)$ is indeed a polynomial of $k$ of degree $s$ and

$Ck(k-1)^{s-1}\leq c(2s,k)\leq Ck^{s}.$

Now, we only need to show that the main coefficient is the $s-$th Catalan
number. We prove it with a combinatorial interpretation of the Catalan
numbers. It is a well-known folklore result that $C_{s}$ is the number of
monotonic lattice paths along the edges of a grid with $s\times s$ square
cells, which do not pass above the diagonal. A monotonic path starts in the
lower left corner, finishes in the upper right corner, and consists entirely
of edges pointing rightwards or upwards. Counting such paths is equivalent to
counting the type of closed walks of length $2s$: increasing the distance
stands for "move right" and decreasing the distance stands for "move up". ∎

######  Remark 3.13.

We present the list of the first few $c$ polynomials:

$\displaystyle c(2,k)=$ $\displaystyle k,$ $\displaystyle c(4,k)=$
$\displaystyle 2k^{2}-k,$ $\displaystyle c(6,k)=$ $\displaystyle
5k^{3}-6k^{2}+2k,$ $\displaystyle c(8,k)=$ $\displaystyle
14k^{4}-28k^{3}+20k^{2}-5k.$

Now, we ready to prove the main result of our paper.

######  Theorem 3.14.

Let $G$ be an $egr(n,k,g,\lambda)$ graph, where $g$ is even.
If $g\equiv 0$ (mod $4$), then

$n(k,g,\lambda)\geq\frac{c(g,k)+k\lambda+k^{g}-2c(\frac{g}{2},k)k^{\frac{g}{2}}}{c(g,k)-c^{2}(\frac{g}{2},k)+k\lambda},$
$n_{2}(k,g,\lambda)\geq
2\frac{c(g,k)+k\lambda+k^{g}-2c(\frac{g}{2},k)k^{\frac{g}{2}}}{c(g,k)-c^{2}(\frac{g}{2},k)+k\lambda}.$

If $g\equiv 2$ (mod $4$), then

$n(k,g,\lambda)\geq\frac{c(g,k)+k\lambda+k^{g}}{c(g,k)+k\lambda},$
$n_{2}(k,g,\lambda)\geq\frac{2k^{g}}{c(g,k)+k\lambda}.$

###### Proof.

$G$ is $k-$regular therefore $\lambda_{1}=k$. If $G$ is bipartite, then
$\lambda_{n}=-k$. Let $g=2s$. Similarly to the case of girth four, we use the
inequality between the arithmetic and quadratic means for the set
$\\{\lambda_{2}^{s}\ldots\lambda_{n}^{s}\\}$:

$\left(\frac{nc(s,k)-k^{s}}{n-1}\right)^{2}=\left(\frac{\sum_{i=2}^{n}\lambda_{i}^{s}}{n-1}\right)^{2}\leq\frac{\sum_{i=2}^{n}\lambda_{i}^{2s}}{n-1}=\frac{nc(2s,k)+nk\lambda-k^{2s}}{n-1}.$

First, if $s$ is even, then we have the following inequality

$(nc(s,k)-k^{s})^{2}\leq(n-1)(nc(2s,k)+nk\lambda-k^{2s}).$

After some calculations, we can give a lower bound for the order of the graph:

$n^{2}c^{2}(s,k)-2nc(s,k)k^{s}+k^{2s}\leq
n^{2}(c(2s,k)+k\lambda)-n(c(2s,k)+k\lambda+k^{2s})+k^{2s},$
$n(c(2s,k)+k\lambda+k^{2s}-2c(s,k)k^{s})\leq
n^{2}(c(2s,k)+k\lambda-c^{2}(s,k)),$
$\frac{c(2s,k)+k\lambda+k^{2s}-2c(s,k)k^{s}}{c(2s,k)+k\lambda-c^{2}(s,k)}\leq
n(k,g,\lambda).$

If $s$ is odd we can get the same result but we also know that in this case
$c(s,k)=c(\frac{g}{2})=0$.
Let $G$ be a bipartite edge-girth regular graph of girth $2s$. Then we apply
the inequality between the arithmetic and quadratic means for the set
$\\{\lambda_{2}^{s}\ldots\lambda_{n-1}^{s}\\}$:

$\left(\frac{nc(s,k)-k^{s}-(-k)^{s}}{n-2}\right)^{2}=\left(\frac{\sum_{i=2}^{n-1}\lambda_{i}^{s}}{n-2}\right)^{2}\leq\frac{\sum_{i=2}^{n-2}\lambda_{i}^{2s}}{n-2}=\frac{nc(2s,k)+nk\lambda-2k^{2s}}{n-2}.$

Begin with the case when $s$ is even, then we have the following inequality

$(nc(s,k)-2k^{s})^{2}\leq(n-2)(nc(2s,k)+nk\lambda-2k^{2s})$

With elementary calculations we get a lower bound for $n_{2}(k,2s,\lambda)$:

$n^{2}c^{2}(s,k)-4nc(s,k)k^{s}+4k^{2s}\leq
n^{2}(c(2s,k)+k\lambda)-2n(c(2s,k)+k\lambda+k^{2s})+4k^{2s},$
$2n(c(2s,k)+k\lambda+k^{2s}-2c(s,k)k^{s})\leq
n^{2}(c(2s,k)-c^{2}(s,k)+k\lambda),$
$2\frac{c(2s,k)+k\lambda+k^{2s}-2c(s,k)k^{s}}{c(2s,k)-c^{2}(s,k)+k\lambda}\leq
n_{2}(k,g,\lambda).$

If $s$ is odd, then $c(s,k)=0$ and $(-k)^{s}=-k^{s}$, hence left-hand side of
the inequality is $0$. This means that

$0\leq n(c(2s,k)+k\lambda)-2k^{2s},$ $\frac{2k^{2s}}{c(2s,k)+k\lambda}\leq
n_{2}(k,g,\lambda).$

∎

######  Remark 3.15.

Recall that Theorem 1.3 gives a
$\Theta\left(k^{\left[\frac{g}{2}\right]-1}\right)$ lower bound for the order
of extremal $egr(n,k,g,\lambda)$ graphs. The previous inequalities gives
$O\left(k^{\left[\frac{g}{2}\right]-1}\right)$ lower bounds for the order of
extremal $egr(n,k,g,\lambda)$ graphs of even girth.
On the other hand, if $\lambda=o(k^{\frac{g}{2}-1})$, then the inequalities
give $\Theta\left(k^{\left[\frac{g}{2}\right]}\right)$ lower bounds. It means
that if $\lambda$ is small, then we have a lower bound for the order of
extremal edge-girth-regular graphs of even girth that is around $k-$times
larger than the previously known lower bound.

##  4 A useful lemma and an inequality for edge-girth-regular graphs of odd
girth

We conclude our paper with an upper bound for the number of $(g+1)-$cycles
through a certain vertex of an $egr(n,k,g,\lambda)$ graph of odd girth and a
corollary of this result.
With another application of the Cauchy-Schwarcz inequality, we can give a new
lower bound of the order of edge-girth regular graphs of odd girth. First, we
need to prove the following lemma.

######  Lemma 4.1.

Let $G$ be an $egr(n,k,g,\lambda)$ graph, where $g=2h+1$ is an odd number.
Then every vertex is contained in at most
$\binom{k}{2}\left((k-1)^{h}-\frac{\lambda}{k-1}\right)$ distinct
$(g+1)-$cycles.

###### Proof.

Choose an arbitrary vertex $v$ and define the sets $D_{i}(v)$ of vertices as
follows: $u\in D_{i}(v)$ if the length of the shortest $uv-$path is $i$.
First, count the number of edges in $D_{h}(v)$. Suppose that there is an edge
$ab\in E$ in $D_{h}(v)$. Then $ab$, and the unique $h-$paths $av$ and $bv$
form a $g-$cycle. Since $G$ has girth $g$, this is a bijection between the
edges in $D_{h}(v)$ and the $g-$cycles through $v$. So it is enough to count
the number of $g-$cycles $v$. The graph is $k-$regular, hence $v$ lies on
exactly $k$ edges and every edge is contained in exactly $\lambda$ distinct
$g-$cycles, but in this way, every $g-$cycle through $v$ is counted twice.
Therefore the number of $g-$cycles through $v$ is $\frac{k\lambda}{2}$, hence
the number of edges in $D_{h}(v)$ is $\frac{k\lambda}{2}.$
Now count the number of edges between $D_{h}(v)$ and $D_{h+1}(v)$. There are
$k(k-1)^{h-1}$ vertices in $D_{h}(v)$. These vertices have $k^{2}(k-1)^{h-1}$
edges but every edge in $D_{h}(v)$ is counted twice. The number of edges
between $D_{h-1}(v)$ and $D_{h}(v)$ is $k(k-1)^{h-1}$, the number of edges in
$D_{h}(v)$ is $\frac{k\lambda}{2}$, hence the number of edges between
$D_{h}(v)$ and $D_{h+1}(v)$ is

$k^{2}(k-1)^{h-1}-k(k-1)^{h-1}-2\frac{k\lambda}{2}=k\left((k-1)^{h}-\lambda\right).$

There are two types of $(g+1)-$cycles through $v$: the ones that reach
$D_{h+1}(v)$ with two $(h+1)-$paths at the same vertex, and the ones that join
two $h-$paths in $D_{h}(v)$ with a $2-$path. We give upper bounds for the
number of $(g+1)-$cycles through $v.$
If a vertex $w\in D_{h+1}(v)$ has $m$ neighbours in $D_{h}(v)$, then $v$ and
$w$ can be with two distinct $(h+1)-$paths $\binom{m}{2}$ different ways,
therefore the number of $(g+1)-$cycles through $v$ and $w$ is $\binom{m}{2}$.
Thus there is a quadratic increase in the number of $(g+1)-$cycles through $v$
but $m\leq k$ because the graph is $k-$regular. If we would like to maximize
the number of $g+1-$cycles through $v$ that reaches $D_{h+1}(v)$, we have to
choose some vertices in $D_{h+1}(v)$ that cover all the edges between
$D_{h}(v)$ and $D_{h+1}(v)$ and have no other edges. Since the number of edges
between $D_{h}(v)$ and $D_{h+1}(v)$ is $k\left((k-1)^{h}-\lambda\right)$, the
number of $(g+1)-$cycles through $v$ that reach $D_{h+1}(v)$ is at most

$\frac{k\left((k-1)^{h}-\lambda\right)}{k}\binom{k}{2}=\binom{k}{2}\left((k-1)^{h}-\lambda\right).$

Similarly, if a vertex $w^{\prime}\in D_{h}(v)$ has $m$ neighbours in
$D_{h}(v)$, then $v$ and $w^{\prime}$ can be connected with two $(h+1)-$paths
in $\binom{m}{2}$ different ways. Therefore the number of $(g+1)-$cycles
through $v$ and $w^{\prime}$ is $\binom{m}{2}.$ Take the graph induced by the
vertices of $D_{h}(v).$ Every degree is at most $k-1$ and the number of edges
is $\frac{k\lambda}{2}$. Denote the set of degrees with
$\\{d_{1},d_{2},\ldots,d_{k(k-1)^{h}}\\}.$ Now we give an upper bound for

$\sum_{i=1}^{k(k-1)^{h}}\binom{d_{i}}{2}=\sum_{i=1}^{k(k-1)^{h}}\frac{d_{i}^{2}-d_{i}}{2}=\frac{1}{2}\sum_{i=1}^{k(k-1)^{h}}d_{i}^{2}-\frac{\lambda}{2}.$

To do that we need to maximize the sum of squares such that the sum of degrees
is constant, and $0\leq d_{i}\leq k-1$ for any $1\leq i\leq k(k-1)^{h}.$ Since
$x^{2}+y^{2}\leq(x+1)^{2}+(y-1)^{2}$ for any $x\leq y$ real numbers, we obtain
an upper bound if we set as many $d_{i}$ to $k-1$ as possible while the rest
is $0$. Hence

$\sum_{i=1}^{k(k-1)^{h}}d_{i}^{2}\leq\frac{k\lambda}{k-1}(k-1)^{2}=\lambda
k(k-1).$

Therefore

$\sum_{i=1}^{k(k-1)^{h}}\binom{d_{i}}{2}\leq\frac{\lambda
k(k-1)}{2}-\frac{\lambda
k}{2}=\binom{k}{2}\lambda\left(1-\frac{1}{k-1}\right).$

We gave upper bounds for each type of $(g+1)-$cycles through a certain vertex
and now we add them to prove the lemma:

$\binom{k}{2}\left((k-1)^{h}-\lambda\right)+\binom{k}{2}\lambda\left(1-\frac{1}{k-1}\right)=\binom{k}{2}\left((k-1)^{h}-\frac{\lambda}{k-1}\right).$

∎

######  Remark 4.2.

The upper bound of the previous lemma is sharp for the Petersen and Hoffmann-
Singleton graphs.

And now we conclude our paper with an application of Lemma 4.1.

######  Proposition 4.3.

Let $G$ be an $egr(n,k,g,\lambda)$ graph of odd girth. Then

$n(k,g,\lambda)\geq\frac{k^{g+1}c(g-1,k)+k^{g-1}\left(c(g+1,k)+k(k-1)^{\frac{g+1}{2}}-\lambda
k\right)-2k^{g+1}\lambda}{c(g-1,k)\left(c(g+1,k)+k(k-1)^{\frac{g+1}{2}}-\lambda
k\right)-k^{2}\lambda^{2}}.$

###### Proof.

Let $k=\lambda_{1}\geq\ldots\geq\lambda_{n}$ be the eigenvalues of the
adjacency matrix of $G$. Then

$\sum_{i=1}^{n}\lambda_{i}^{g-1}=nc(g-1,k),$
$\sum_{i=1}^{n}\lambda_{i}^{g}=nk\lambda,$
$\sum_{i=1}^{n}\lambda_{i}^{g+1}=nc(g+1,k)+\sum_{v\in G}\textrm{(the number of
directed (g+1)-cycles containing v)}.$

Using the fact the the largest eigenvalue is $k$ and the upper bound for the
number of $(g+1)-$cycles, we get

$\sum_{i=2}^{n}\lambda_{i}^{g-1}=nc(g-1,k)-k^{g-1},$
$\sum_{i=2}^{n}\lambda_{i}^{g}=nk\lambda-k^{g},$
$\sum_{i=2}^{n}\lambda_{i}^{g+1}=nc(g+1,k)+2n\binom{k}{2}\left((k-1)^{h}-\frac{\lambda}{k-1}\right)-k^{g+1}.$

Let $g=2h+1.$ Then the Cauchy-Schwarz inequality gives

$\left(\sum_{i=2}^{n}\lambda_{i}^{g}\right)^{2}=\left(\sum_{i=2}^{n}\lambda_{i}^{h}\lambda_{i}^{h+1}\right)^{2}\leq\left(\sum_{i=2}^{n}\lambda_{i}^{2h}\right)\left(\sum_{i=2}^{n}\lambda_{i}^{2h+2}\right)=\left(\sum_{i=2}^{n}\lambda_{i}^{g-1}\right)\left(\sum_{i=2}^{n}\lambda_{i}^{g+1}\right).$

Now we can give an upper bound for the right hand side and we get the
following inequality:

$\left(nk\lambda-k^{g}\right)^{2}\leq\left(nc(g-1,k)-k^{g-1}\right)\left(nc(g+1,k)+2n\binom{k}{2}\left((k-1)^{h}-\frac{\lambda}{k-1}\right)-k^{g+1}\right).$

We have a quadratic inequality in $n$. After simplifying the inequality we get
the lower bound for the order of $G$:

$n(k,g,\lambda)\geq\frac{k^{g+1}c(g-1,k)+k^{g-1}\left(c(g+1,k)+k(k-1)^{\frac{g+1}{2}}-\lambda
k\right)-2k^{g+1}\lambda}{c(g-1,k)\left(c(g+1,k)+k(k-1)^{\frac{g+1}{2}}-\lambda
k\right)-k^{2}\lambda^{2}}.$

∎

######  Corollary 4.4.

The Petersen graph is an extremal $egr(10,3,5,4)$ graph.

###### Proof.

The theorem states that

$n(k,5,\lambda)\geq\frac{3k^{6}+k^{5}-3k^{4}+k^{3}-2k^{4}\lambda-k^{3}\lambda}{2k^{4}+3k^{3}-8k^{2}+5k-1-\lambda^{2}-2k\lambda+\lambda}.$

Hence $n(3,5,4)\geq 9.78$ so the order of the Petersen graph is extremal. ∎

######  Remark 4.5.

Unfortunately, the lower bound presented in Proposition 4.3 is weaker than the
lower bound in Theorem 1.3. However, the inequality in Lemma 4.1 may be useful
for further improvements for the lower bound of the order of edge-girth-
regular graphs of odd girth.

## References

  * [1] G. Araujo-Pardo, D. Leemans, _Edge-girth-regular graphs arising from biaffine planes and Suzuki groups_ , Discrete Mathematics, Volume 345, Issue 10, (2022).
  * [2] N. Biggs. _Algebraic graph theory_. Cambridge University Press, Cambridge, second edition, (1993). Discrete Math. 338 (2015), 2562-2571.
  * [3] A. E. Brouwer, W. H. Haemers, _Spectra of Graphs_. (Universitext). Springer Verlag., (2012)
  * [4] A. A. Bruen, J. W. P. Hirschfeld: _Intersections in Projective Space II: Pencils of Quadrics_ , Europ. J. Combiatorics (1988), 255-270.
  * [5] A. Z. Drglin, S. Filipovski, R. Jajcay, and T. Raiman, Extremal Edge-Girth-Regular Graphs, Graphs and Combin. 37 (2021), 2139–2154.
  * [6] R. Jajcay, Gy. Kiss, Š. Miklavič, _Edge-girth-regular graphs_ , European Journal of Combinatorics 72 (2018), 70–82.
  * [7] Gy. Kiss, Š. Miklavič, T. Szőnyi, _A stability result for girth-regular-graphs with even girth_ , J. Graph Theory. 100 (2022), 163-181.
  * [8] Gy. Kiss, T. Szőnyi, _Finite geometries_ : Chapman and Hall/CRC (2019).
  * [9] S. E. Payne, J. A.Thas, _Finite generalized quadrangles_ , 2nd ed., EMS Publishing House, Zürich, (2009).
  * [10] I. Porupsánszki: _A note on pencils of elliptic quadrics in $PG(3,q)$_, Annales Univ. Sci. Budapest., Sec. Math. Vol. LXIV. (2021), 45–53.