11institutetext: Carnegie Mellon University, Pittsburgh PA 15213, USA
11email<EMAIL_ADDRESS>
# RelPose: Predicting Probabilistic Relative Rotation for Single Objects in
the Wild

Jason Y. Zhang  Deva Ramanan  Shubham Tulsiani

###### Abstract

We describe a data-driven method for inferring the camera viewpoints given
multiple images of an arbitrary object. This task is a core component of
classic geometric pipelines such as SfM and SLAM, and also serves as a vital
pre-processing requirement for contemporary neural approaches (e.g. NeRF) to
object reconstruction and view synthesis. In contrast to existing
correspondence-driven methods that do not perform well given sparse views, we
propose a top-down prediction based approach for estimating camera viewpoints.
Our key technical insight is the use of an energy-based formulation for
representing distributions over relative camera rotations, thus allowing us to
explicitly represent multiple camera modes arising from object symmetries or
views. Leveraging these relative predictions, we jointly estimate a consistent
set of camera rotations from multiple images. We show that our approach
outperforms state-of-the-art SfM and SLAM methods given sparse images on both
seen and unseen categories. Further, our probabilistic approach significantly
outperforms directly regressing relative poses, suggesting that modeling
multimodality is important for coherent joint reconstruction. We demonstrate
that our system can be a stepping stone toward in-the-wild reconstruction from
multi-view datasets. The project page with code and videos can be found at
jasonyzhang.com/relpose.

Figure 1: Probabilistic Camera Rotation Estimation for Generic Objects. Left:
Given two images of the same object, we predict a conditional distribution of
relative camera viewpoint (rotation) that effectively handles symmetries and
pose ambiguities. Right: Given a set of images, our approach outputs a
configuration of camera rotations.

##  1 Introduction

Recovering 3D from 2D images of an object has been a central task in vision
across decades. Given multiple views, structure-from-motion (SfM) based
methods can infer a 3D representation of the underlying instance while also
associating each image with a camera viewpoint. However, these correspondence-
driven methods cannot robustly handle sparsely sampled images that minimally
overlap, and typically require many ($>$20) images for a 360-degree 3D
inference. Unfortunately, this requirement of densely sampled views can be
prohibitive—online marketplaces often have only a few images per instance, and
a user casually reconstructing a novel object would also find capturing such
views tedious. Although the recently emerging neural 3D reconstruction
techniques also typically leverage similarly dense views, some works have
shown promise that a far smaller number of images can suffice for high-quality
3D reconstruction. These successes have however still relied on precisely [60]
or approximately [27, 82, 20] known camera viewpoints for inference. To apply
these methods at scale, we must therefore answer a fundamental question—
_given sparsely sampled images of a generic object, how can we obtain the
associated camera viewpoints_?

Existing methods do not provide a conclusive answer to this question. On the
one hand, bottom-up correspondence-based techniques are not robustly
applicable for sparse-view inference. On the other, recent neural multi-view
methods can optimize already known approximate camera poses but provide no
mechanism to obtain these to begin with. In this work, our goal is to fill
this void and develop a method that, given a small number of unposed images of
a generic object, can associate them with (approximate) camera viewpoints.
Towards this goal, we focus on inferring the camera rotation matrices
corresponding to each input image and propose a top-down approach to predict
these. However, we note that the ‘absolute’ rotation is not well-defined given
an image of a generic object—it assumes a ‘canonical’ pose which is not always
known a-priori (e.g. what is an identity rotation for a pen? or a plant?). In
contrast, the relative rotation between two views is well-defined even if a
canonical pose for the instance is not. Thus, instead of adopting the common
paradigm of single-image based pose prediction, we learn to estimate the
relative pose given a pair of input images. We propose a system that leverages
such pairwise predictions to then infer a consistent set of global rotations
given multiple images of a generic object.

A key technical question that we consider is regarding the formulation of such
pairwise pose estimation. Given two informative views of a rotationally
asymmetric object, a regression-based approach may be able to accurately
predict their relative transformation. The general case however, can be more
challenging—given two views of a cup but with the handle only visible in one,
the relative pose is ambiguous given just the two images. To allow capturing
this uncertainty, we formulate an energy-based relative pose prediction
network that, given two images and a candidate relative rotation, outputs an
energy corresponding to the (unnormalized) log-probability of the hypothesis.
This probabilistic estimation of relative pose not only makes the learning
more stable, but more importantly, provides a mechanism to estimate a _joint
distribution_ over viewpoints given multiple images. We show that optimizing
rotations to improve this joint likelihood yields coherent poses given
multiple images and leads to significant improvements over naive approaches
that do not consider the joint likelihoods.

We train our system using instances from over 40 commonplace object
categories, and find that not only can it infer accurate (relative) poses for
novel instances of these classes, it even generalizes to instances from unseen
categories. Our approach can thus be viewed as a stepping stone toward sparse-
view 3D reconstruction of generic objects; just as classical techniques
provide precise camera poses that (neural) multi-view reconstruction methods
can leverage, our work provides a similar, albeit coarser, output that can be
used to initialize inference in current (and future) sparse-view
reconstruction methods. While our system only outputs camera rotations, we
note that a reasonable corresponding translation can be easily initialized
assuming object-facing viewpoints, and we show that this suffices in practice
for bootstrapping sparse-view reconstruction.

Figure 2: Overview. From a set of images, we aim to recover corresponding
camera poses (rotations). To do this, we train a pairwise pose predictor that
takes in two images and a candidate relative rotation and predicts energy. By
repeatedly querying this network, we recover a probability distribution over
conditional relative rotations (see Sec. 3.1). We use these pairwise
distributions to induce a joint likelihood over the camera transformations
across multiple images, and iteratively improve an initial estimate by
maximizing this likelihood (see Sec. 3.2).

##  2 Related Work

Structure-from-Motion (SfM). At a high level, structure-from-motion aims to
recover 3D geometry and camera parameters from image sets. This is done
classically by computing local image features [21, 30, 2, 66], finding matches
across images [31], and then estimating and verifying epipolar geometry using
bundle adjustment [67]. Later works have scaled up the SfM pipeline using
sequential algorithms, demonstrating results on hundreds or even thousands of
images [58, 18, 55, 54, 52].

The advent of deep learning has augmented various stages of the classical SfM
pipeline. Better feature descriptors [14, 57, 72, 79, 15, 46, 49] and improved
featured matching [53, 9, 29, 68, 16] have significantly outperformed their
hand-crafted counterparts. BA-Net [63] and DeepSFM [75] have even replaced the
bundle-adjustment process by optimizing over a cost volume. Most recently,
Pixel-Perfect SfM [28] uses a featuremetric error to post-process camera poses
to achieve sub-pixel accuracy.

While these methods can achieve excellent localization, all these approaches
are bottom-up: beginning with local features that are matched across images.
However, matching features requires sufficient overlap between images, which
may not be possible given wide baseline views. While our work also aims to
localize camera poses given image sets, our approach fundamentally differs
because it is top-down and does not rely on low-level correspondences.

Simultaneous Localization and Mapping (SLAM). Related is the task of Monocular
SLAM, which aims to localize and map the surroundings from a video stream.
Indirect SLAM methods, similar to SfM, match local features across different
images to localize the camera [51, 5, 38, 37]. Direct SLAM methods, on the
other hand, define a geometric objective function to directly optimize over a
photometric error [87, 56, 11, 17].

There have also been various attempts to introduce deep learning into SLAM
pipelines. As with SfM, learned feature descriptors and matching have helped
improve accuracy on SLAM subproblems and increased robustness. End-to-end deep
SLAM methods [84, 40, 73, 74] have improved the robustness of SLAM compared to
classical methods, but have generally not closed the gap on performance. One
notable exception is the recent DROID-SLAM [64], which combines the robustness
of learning-based SLAM with the accuracy of classical SLAM.

These approaches all assume sequential streams and generally rely on matching
or otherwise incorporating temporal locality between neighboring frames. We do
not make any assumptions about the order of the image inputs nor the amount of
overlap between nearby frames.

Single-view Pose Prediction. The task of predicting a (6-DoF) pose from a
single image has a long and storied history, the surface of which can barely
be scratched in this section. Unlike relative pose between multiple images,
the (absolute) pose given a single image is only well-defined if there exists
a canonical coordinate system. Most single-view pose prediction approaches
therefore deal with a fixed set of categories, each of which has a canonical
coordinate system defined a priori [77, 65, 43, 7, 71, 23, 4, 59, 42, 39, 24,
26]. Other methods that are category-agnostic take in a 3D mesh or point cloud
as input, which provides a local coordinate system [76, 78, 81, 44].

Perhaps most relevant to us are approaches that not only predict pose but also
model inherent uncertainty in the pose prediction [3, 25, 39, 45, 10, 61, 47,
19, 12, 13, 36, 33]. Like our approach, VpDR-Net [41] uses relative poses as
supervision but still predicts absolute pose (with a unimodal Gaussian
uncertainty model). Implicit-PDF [39] is the most similar approach to ours and
served as an inspiration. Similar to our approach, Implicit-PDF uses a neural
network to implicitly represent probability using an energy-based formulation
which elegantly handles symmetries and multimodal distributions. Unlike our
approach, Implicit-PDF (and all other single-view pose prediction methods)
predict absolute pose, which does not exist in general for generic or novel
categories. Instead, we model probability distributions over relative pose
given pairs of images.

Learning-based Relative Pose Prediction. When considering generic scenes,
prior works have investigated the task of relative pose prediction given two
images. However, these supervised [69] or self-supervised [85, 80, 32, 70]
methods typically consider prediction of motion between consecutive frames and
are not easily adapted to wide-baseline prediction. While some approaches have
investigated wide baseline prediction [34, 1], regression-based inference does
not effectively capture uncertainty unlike our energy-based model. Perhaps
most similar to ours is DirectionNet [8] which also predicts a camera
distribution for wide baseline views. While DirectionNet only uses the
expected value of the distribution and thus ignores symmetry, we take
advantage of multimodal distributions to improve our joint pose estimation.

##  3 Method

Figure 3: Predicted conditional distribution of image pairs from unseen
categories. Here, we visualize the predicted conditional distribution of image
pairs. Inspired by [39], we visualize the rotation distribution (Alg. 1) by
plotting yaw as latitude, pitch as longitude, and roll as the color. The size
of each circle is proportional to the probability of that rotation. We omit
rotations with negligible probability. The center of the open circle
represents the ground truth. We can see that network predicts 4 modes for the
couch images, corresponding roughly to 90 degree increments, with the greatest
probability assigned to the correct 90 degree rotation. The relative pose of
the hot dog is unambiguous and thus only has one mode. While the relative pose
for the frisbee has close to no pitch or yaw, the roll remains ambiguous,
hence the variety in colors. See the supplement for a visualization of how to
interpret the relative rotations.

Given a set of $N$ images $\\{I_{1},\ldots I_{N}\\}$ depicting a _generic_
object in-the-wild, we aim to recover a set of $N$ rotation matrices
$\\{R_{1},\ldots,R_{N}\\}$ such that rotation matrix $R_{i}$ corresponds to
the viewpoint of the camera used to take image $i$. Note that while we do not
model translation, it can be easily initialized using object-facing viewpoints
for 3D object reconstruction [27, 82] or a pose graph for SLAM [6]. We are
primarily interested in settings with only sparse views and wide baselines.
While bottom-up correspondence based techniques can reliably recover camera
pose given dense views, they do not adapt well to sparse views with minimal
overlap. We instead propose a prediction-based top-down approach that can
learn and exploit the global structure directly.

The basic building block of our prediction system (visualized in Fig. 3) is a
pairwise pose predictor that infers relative camera orientations given pairs
of images. However, symmetries in objects and possibly uninformative
viewpoints make this an inherently uncertain prediction task. To allow
capturing this uncertainty, we propose an energy-based approach that models
the _multi-modal distribution_ over relative poses given two images.

Given the predicted distributions over pairwise relative rotations, we show
that these can be leveraged to induce a _joint_ distribution over the
rotations. Starting with a greedy initialization, we present a coordinate-
ascent approach that jointly reasons over and improves the set of inferred
rotations. We describe our approach for modeling probability distributions
over relative poses between two images in Sec. 3.1, and build on this in Sec.
3.2 to recover a joint set of poses across multiple images. Finally, we
discuss implementation details in Sec. 3.3.

###  3.1 Estimating Pair-wise Relative Rotations

Algorithm 1 Pseudo-code for recovering a pairwise distribution. We describe
how to recover the distribution of the relative pose given images.

procedure PairwiseDistribution($I_{1}$, $I_{2}$)

queries $\leftarrow$SampleRotationsUnif(50000)

energies $\leftarrow f(I_{1},I_{2},$ queries)

probs $\leftarrow$ SoftMax(energies)

return queries, probs

end procedure

Given a pair of images depicting an arbitrary object, we aim to predict a
distribution over the relative rotation corresponding to the camera
transformation between the two views. As there may be ambiguities when
inferring the relative pose given two images, we introduce a formulation that
can model uncertainty.

Energy-based Formulation. We wish to model the conditional distribution over a
relative rotation matrix $R$ given input images $I_{1}$ and $I_{2}$: $P(R\mid
I_{1},I_{2})$. Inspired by recent work on implicitly representing the
distribution over rotations using a neural network [39], we propose using an
energy-based relative pose estimator. More specifically, we train a network
$f(R,I_{1},I_{2})$ that learns to predict the energy, or the unnormalized
joint log-probability, $P(R,I_{1},I_{2})=\alpha\exp f(R,I_{1},I_{2})$ where
$\alpha$ is the constant of integration. From the product rule, we can recover
the conditional probability as a function of $f$:

$\small{P(R\mid
I_{1},I_{2})=\frac{P(R,I_{1},I_{2})}{P(I_{1},I_{2})}\approx\frac{\alpha\exp
f(R,I_{1},I_{2})}{\sum_{R^{\prime}}\alpha\exp
f(R^{\prime},I_{1},I_{2})}=\frac{\exp f(R,I_{1},I_{2})}{\sum_{R^{\prime}}\exp
f(R^{\prime},I_{1},I_{2})}}$ (1)

We marginalize over rotations to avoid having to compute $\alpha$ (see Alg.
1), but note that the number of sampled rotations should be large for the
approximation to be accurate. It is therefore important to use a lightweight
network $f$ since it is queried once per sampled rotation in the denominator.

Training. We train our network by maximizing the log-likelihood of the
conditional distribution, or equivalently minimizing the negative log-
likelihood:

$\mathcal{L}=-\log P(R_{1}^{\top}R_{2}\mid I_{1},I_{2})$ (2)

where $R_{1}$ and $R_{2}$ are the ground truth poses of $I_{1}$ and $I_{2}$
respectively. Note that while the ‘absolute’ poses $(R_{1},R_{2})$ are in an
arbitrary coordinate system (depending on e.g. SLAM system outputs), the
relative pose $R_{1}^{\top}R_{2}$ between two views is agnostic to this
incidental canonical frame. Following (1), we sample multiple candidate
rotation matrices to compute the conditional probability.

Inference. Recovering the optimal transformation from the pose of $I_{1}$ to
$I_{2}$ amounts to optimizing $f$ over the space of rotations:

$R^{*}=\operatorname*{arg\,max}_{R\in\mathbf{SO}(3)}P(R\mid
I_{1},I_{2})=\operatorname*{arg\,max}_{R\in\mathbf{SO}(3)}f(R,I_{1},I_{2})$
(3)

In practice, the loss landscape of $f$ is often un-smooth, so we find that
sampling and scoring rotations based on $f$ to be more effective than gradient
ascent.

We can also compute the conditional distribution of the relative rotation from
$I_{1}$ to $I_{2}$ by sampling rotations over $\mathbf{SO}(3)$. The
probability associated with each rotation can be computed using a softmax
function, as described Alg. 1 and derived in (1). Inspired by [39], we can
visualize the distribution of rotations by projecting the rotation matrices on
a 2-sphere using pitch and yaw and coloring the rotation based on roll. See
Fig. 3 and the supplement for sample results.

###  3.2 Recovering Joint Poses

Algorithm 2 Pseudo-code for joint inference using relative pose predictor. We
describe how to recover the joint poses given $n$ images via coordinate
ascent.

procedure CoordAsc(Images $\\{I_{i}\\}_{N}$)

$\\{R_{i}\\}_{N}\leftarrow$ InitializeRotations($\\{I_{i}\\}_{N}$)

for $t\in 1,\ldots,$ Num Iterations do

$k\leftarrow$ RandomInteger($N$)

$\triangleright$ $R_{k}^{\prime}$ ($Q$$\times$3$\times$3): $Q$ replacements
for $R_{k}$

$R_{k}^{\prime}\leftarrow$SampleRotationsUnif($Q$=250000)

energs $\leftarrow$ Zeros($Q$)

for $i\in 1,\ldots,N$ and $i\not=k$ do

$R\leftarrow$ Repeat($R_{i}$, $Q$) $\triangleright$
3$\times$3$\rightarrow$$Q$$\times$3$\times$3

energs $\leftarrow$ energs \+ $f(I_{i},I_{k},R^{\top}R_{k}^{\prime})$

energs $\leftarrow$ energs \+ $f(I_{k},I_{i},R_{k}^{\prime\top}R)$

end for

$R_{k}\leftarrow R_{k}^{\prime}$[ArgMax(energs)]

end for

end procedure

In the previous section, we describe an energy-based relative pose predictor
conditioned on pairs of images. Using this network, we recover a coherent set
of rotations when given a set of images.

Greedy Initialization. Given predictions for relative rotations between every
pair of images, we aim to associate each image with an absolute rotation.
However, as the relative poses are invariant up to a global rotation, we can
treat the pose of the first image as the identity matrix: $R_{1}=I$. We note
that the rotations for the other images can be uniquely induced given any
$N-1$ relative rotations that span a tree.

_Sequential Chain_. Perhaps the simplest way to construct such a tree is to
treat the images as part of an ordered sequence. Given $R_{1}=I$, all
subsequent poses can be computed by using the best scoring relative pose from
the previous image: $R_{i}=R_{i-1}R^{*}_{(i-1)\shortrightarrow i}$, denoting
$R_{i\shortrightarrow j}$ as the relative rotation matrix $R_{i}^{\top}R_{j}$.
However, this assumes that the images are captured sequentially (e.g. in a
video) and may not be applicable for settings such as online marketplaces.

_Maximum Spanning Tree_. We improve over the naive linear chain by recognizing
that some pairs of images may produce more confident predictions. Given $N$
images, we construct a directed graph with $N\cdot(N-1)$ edges, where the
weight of edge $(i,j)=P(R^{*}_{i\shortrightarrow j}|I_{i},I_{j})$. We then
construct a Maximum Spanning Tree (MST) that covers all images with the most
confident set of relative rotations.

Reasoning over all images jointly. Both of the previous methods, which select
a subset of edges, do not perform any joint reasoning and discard all but the
highest scoring mode for each pair of images. Instead, we can take advantage
of our energy-based formulation to enforce global consistency.

Given our pairwise conditional probabilities, we can define a joint
distribution over the set of rotations:

$P\left(\\{R_{i}\\}_{i=1}^{N}\mid\\{I_{i}\\}_{i=1}^{N}\right)=\alpha\exp\Big{(}\sum_{(i,j)\in\mathcal{P}}f(R_{i\rightarrow
j}\mid I_{i},I_{j})\Big{)}$ (4)

where $\mathcal{P}=\\{(i,j)\mid(i,j)\in[N]\times[N],i\not=j\\}$ is the
$N(N-1)$ set of pairwise permutations and $\alpha$ is the normalizing
constant. Intuitively, this corresponds to the distribution modeled by a
factor graph with a potential function corresponding to each pairwise edge.

We then aim to find the most likely set of rotations
$\\{R_{1},\ldots,R_{N}\\}$ under this conditional joint distribution (assuming
$R_{1}=I$). While it is not feasible to analytically obtain the global maxima,
we adopt an optimization-based approach and iteratively improve the current
estimate. More specifically, we initialize the set of poses with the greedy
MST solution and at each iteration, we randomly select a rotation $R_{k}$ to
update. Assuming fixed values for $\\{R_{i}\\}_{i\neq k}$, we then search for
the rotation $R_{k}$ under the conditional distribution that maximizes the
overall likelihood. We show in supplementary that this in fact corresponds to
computing the most likely hypothesis under the distribution
$P(R_{k}^{\prime}\mid\\{R_{i}\\}_{i\not=k},\\{I_{i}\\}_{i})$:

$\displaystyle\log
P(R_{k}^{\prime}\mid\\{R_{i}\\}_{i\not=k},\\{I_{i}\\}_{i})=\sum_{i\not=k}\left(f(R_{i\rightarrow
k^{\prime}},I_{i},I_{k})+f(R_{k^{\prime}\rightarrow i},I_{k},I_{i})\right)+C$
(5)

Analogous to our approach for finding the optimal solution for a single
relative rotation, we sample multiple hypotheses for the rotation $R_{k}$, and
select the hypothesis that maximizes (5). We find that this search-based block
coordinate ascent helps us consistently improve over the initial solution
while avoiding the local optima that a continuous optimization is susceptible
to. We provide pseudo-code in Alg. 2 and visualize one iteration of coordinate
ascent in Fig. 4.

Figure 4: Recovering Joint Poses with Coordinate Ascent. Given a set of images
$\\{I_{1},\ldots,I_{N}\\}$, we initialize a set of corresponding poses
$\\{R_{1},\ldots,R_{N}\\}$. During each iteration of coordinate ascent, we: 1)
randomly select one pose $R_{k}$ to update (the red camera in this case); 2)
sample a large number (250k) of candidate poses; 3) score each pose according
to the joint distribution conditioned on the other poses and images (5); and
4) update with the highest scoring pose. See Sec. 3.2 for more detail.

###  3.3 Implementation Details

Network Architecture. We use a ResNet-50 [22] with anti-aliasing [83] to
extract image features. We use a lightweight 3-layer MLP that takes in a
concatenation of 2 sets of image features and a rotation matrix to predict
energy. We use positional encoding [35, 62] directly on flattened $3\times 3$
rotation matrix, similar to [39]. See the supplement for architecture
diagrams.

Number of Rotation Samples. We use the equivolumetric sampling in [39] to
compute query rotations (37k total rotations) during training. For each
iteration of coordinate ascent, we randomly sample 250k rotation matrices. For
visualizing distributions, we randomly sample 50k rotations.

Runtime. We train the pairwise estimator with a batch size of 64 images for
approximately 2 days on 4 NVIDIA 2080TI GPUs. Inference for 20 images takes
around 1-2 seconds to construct an MST and around 2 minutes for 200 iterations
of coordinate ascent on a single 2080TI. Note that the runtime of the
coordinate ascent scales linearly with the number of images.

##  4 Evaluation

Figure 5: Qualitative Comparison of Recovered Camera Poses with Baselines. We
visualize the camera poses (rotations) predicted by DROID-SLAM, COLMAP with
SuperPoint/SuperGlue, and our method given sparse image frames. The black
cameras correspond to the ground truth. We only visualize the rotations
predicted by each method, and set the translation such that the object center
is a fixed distance away along the camera axis. As the poses are agnostic to a
global rotation, we align the predicted cameras across all methods to the
ground truth coordinate system by setting the recovered camera pose for the
first image to the corresponding ground truth (visualized in green). Odd rows
correspond to randomly sampled image frames, while even rows correspond to
uniformly-spaced image frames.  Figure 6: Mean Accuracy on Seen Categories. We
evaluate our approach against competitive SLAM (DROID-SLAM) and SfM (COLMAP
with SuperPoint + SuperGlue) baselines in sparse-view settings. We also train
a direct relative rotation predictor (Pose Regression) that is not
probabilistic and uses the MST generated by our method to recover joint pose.
We consider both randomly sampling and uniformly spacing frames from a video
sequence. We report the proportion of pairwise relative poses that are within
15 and 30 degrees of the ground truth, averaged over all seen categories. We
find that our approach shines with fewer views because it does not rely on
correspondences and thus can handle wide baseline views. Correspondence-based
approach need about 20 images to begin to work.  Figure 7: Accuracy on Subset
of Seen Categories. Here we compare all approaches on a representative subset
of seen categories. We find that direct regression of relative poses (purple)
struggles more on categories with symmetry (Car, Hydrant) than categories
without symmetry (Chair, Plant), suggesting that multimodal prediction is
important for resolving ambiguity.

Figure 8: Mean Accuracy on Unseen Categories. We evaluate our approach on held
out categories from CO3D.

Figure 9: Novel View Registration. Here, we evaluate the task of registering a
new view given previously aligned cameras. We find that adding more views
improves performance, suggesting that additional views reduce ambiguity.

###  4.1 Experimental Setup

Dataset. We train and test on the Common Objects in 3D dataset (CO3D) [48], a
large-scale dataset consisting of turntable-style videos of 51 common object
categories. We train on the subset of the dataset that has camera poses, which
were acquired by running COLMAP [54] over all frames of the video.

To train our network, we sample random frames and their associated camera
poses from each video sequence. We train on 12,299 video sequences (from the
train-known split) from 41 categories, holding out 10 categories to test
generalization. We evaluate on 1,711 video sequences (from the test-known
split) over all 41 trained categories (seen) as well as the 10 held out
categories (unseen). The 10 held out categories are: ball, book, couch,
frisbee, hotdog, kite, remote, sandwich, skateboard, and suitcase. We selected
these categories randomly after excluding some of the categories with the most
training images.

Task and Metrics. We consider the task of sparse-view camera pose estimation
with $N=$ 3, 5, 10, and 20 images, subsampled from a video sequence. This is
highly challenging, especially when $N\leq 10$, because the ground truth
camera poses have wide baselines.

We consider two possible ways to select $N$ frames from a video sequence.
First, we can randomly sample a set of $N$ indices per video sequence
(Random). Alternatively, we can use $N$ uniformly-spaced frame indices
(Uniform). We note that because CO3D video sequences are commonly taken in a
turntable fashion, the uniformly spaced sampling strategy may be more
representative of real world distributions of sparse view image sets. We
report metrics on both task setups.

Because the global transformation of the camera poses is ambiguous, we
evaluate each pair of relative rotations. For each of the $N(N-1)$ pairs, we
compare the angular difference between the relative predicted rotation and the
relative ground truth rotation using Rodrigues’ formula [50]. We report the
proportion of relative rotations that are within 15 and 30 degrees of the
ground truth. We note that rotation errors within this range are relatively
easy to handle by downstream 3D reconstruction tasks (See Fig. 10 for an
example).

Baselines. We compare against DROID-SLAM [64], a current state-of-the-art SLAM
approach that incorporates learning in an optimization framework. Note that
DROID-SLAM requires trajectories and camera intrinsics. Thus, we provide the
DROID-SLAM baseline with sorted frame indices and intrinsics, but do not
provide these to any other method.

We also compare with a state-of-the-art structure-from-motion pipeline that
uses COLMAP [54] with SuperPoint feature extraction [14] and SuperGlue
matching [53]. We used the implementation provided by [52]. For instances for
which COLMAP does not converge or is unable to localize some cameras, we treat
the missing poses as identity rotation for evaluation. We note that DROID-SLAM
also outputs approximate identity rotations when the optimization fails.

Ablations. In the spirit of learning-based solutions that directly regress
pose, we train a network that predicts relative rotation directly given two
images. Similar to our energy-based predictor, we pass the concatenated images
features from a ResNet-50 into an MLP. We double the number of layers from 3
to 6 and add a skip connection to give this network increased capacity.
Rotations are predicted using the 6D rotation representation [86]. See the
supplement for additional architecture details. The relative pose regressor
cannot directly predict poses for more than two images. To recover sets of
poses from sets of images, we use the MST graph recovered by our method to
link the pairs of relative rotations (we find that this performs better than
linking the relative rotations sequentially).

To demonstrate the benefits of joint reasoning, we additionally report the
performance of our method using the greedy Maximum Spanning Tree (MST)
solution. The performance of the sequential solution is in the supplement.

###  4.2 Quantitative Evaluation

We evaluate all approaches on sparse-view camera pose estimation by averaging
over all seen categories in Fig. 6. We find that our approach outperforms all
baselines for $N\leq 10$ images. Correspondence-based approaches (DROID-SLAM
and COLMAP) do not work until roughly 20 images, at which point image frames
have sufficient overlap for local correspondences. However, real world multi-
view data (e.g. marketplace images) typically have much fewer images. We find
that coordinate ascent helps our approach scale with more image frames whereas
the greedy maximum spanning tree accumulates errors with more frames.

Directly predicting relative poses does not perform well, possibly because
pose regression cannot model multiple modes, which is important for
symmetrical objects. We visualize the performance for four categories in Fig.
7. We find that the performance gap between our approach and direct regression
is larger for objects with some symmetry (car, hydrant) than for objects
without symmetry (chair, plant). Moreover, unlike our energy-based approach
that models a joint distribution, a regression-based method does not allow
similar joint reasoning.

We also test the generalization of our approach for _unseen_ categories in
Fig. 8. We still find that our method significantly outperforms all other
approaches with sparse view ($N\leq 10$) even for never-before-seen object
categories, indicating its ability to handle generic objects beyond training.
The per-category evaluation for both seen and unseen categories are in the
supplement.

Novel View Registration. In our standard SfM-inspired task setup, we aim to
recover $N$ camera poses given $N$ images. Intuitively, adding images reduces
ambiguity, but recovering additional cameras is also more challenging. To
disambiguate between the two, we evaluate the task of registering new views
given previously aligned images in Fig. 9. Given $N+1$ images, of which $N$
have aligned cameras, we use our energy-based regressor to recover the
remaining camera (equivalent to one iteration of coordinate ascent). We find
that adding images improves accuracy, suggesting that additional views can
reduce ambiguity.

###  4.3 Qualitative Results

Figure 10: Initializing 3D NeRS Reconstruction using Predicted Cameras. NeRS
[82] is a representative 3D reconstruction approach that takes noisy cameras
as initialization and jointly optimizes object shape, appearance, and camera
poses. We run our method with coordinate ascent on 7 input images of a fire
hydrant and 4 input images of a motorbike to obtain the camera initialization
(green), which we provide to NeRS. NeRS then finetunes the cameras (orange)
and outputs a 3D reconstruction.

We show qualitative results on the outputs of our pairwise predictor in Fig.
3. The visualized distributions suggest that our model is learning useful
information about symmetry and can model multiple modes even for unseen
categories.

We visualize predicted camera poses for DROID-SLAM, COLMAP, and our method
with coordinate ascent in Fig. 5. Unable to bridge the domain gap from narrow
baseline video frames, DROID-SLAM often gets stuck in the trajectory. Although
COLMAP sometimes fails to converge, it performs well for $N$=20. Our approach
consistently outputs plausible interpretations but is unable to achieve
precise localization. See supplementary for visualizations on randomly
selected sequences and more category-specific discussion.

We also validate that our camera pose estimations can be used for downstream
3D reconstruction. We use our camera poses to initialize NeRS [82], a
representative sparse-view surface-based approach that requires a (noisy)
camera initialization. Using our cameras, we successfully reconstruct a 3D
model of a fire hydrant from 7 images and a motorbike from 4 images in Fig.
10. Note that the camera pose initialization in the original NeRS paper was
manually selected.

##  5 Discussion

We presented a prediction-based approach for estimating camera rotations given
(a sparse set of) images of a generic object. Our energy-based formulation
allows capturing the underlying uncertainty in relative poses, while also
enabling joint reasoning over multiple images. We believe our system’s
robustness under sparse views can allow it to serve as a stepping stone for
initializing (neural) reconstruction methods in the wild, but also note that
there are several open challenges. First, our work reasoned about the joint
distribution using only pairwise potentials and developing efficient higher-
order energy models may further improve performance. Moreover, while we
outperform existing techniques given sparse-views, the correspondence-driven
methods are more accurate given a large number of views, and we hope future
efforts can unify the two approaches. Finally, our approach may not be
directly applicable to reasoning about camera transformations for arbitrary
scenes as modeling camera translation would be more important compared to
object-centric images.

Acknowledgements. We would like to thank Gengshan Yang, Jonathon Luiten, Brian
Okorn, and Elliot Wu for helpful feedback and discussion. This work was
supported in part by the NSF GFRP (Grant No. DGE1745016), Singapore DSTA, and
CMU Argo AI Center for Autonomous Vehicle Research.

##  6 Supplementary Materials

In this section, we show that maximizing the conditional distribution of an
update to a hypothesis is equivalent to maximizing the joint likelihood in
Sec. 6.1. We evaluate ablations of our approach to validate the use of
coordinate ascent vs gradient ascent and MST vs sequential loop in Tab. 1. To
test the quality of our SLAM and SfM baselines, we also ran them with more
image frames (narrower baseline) in Fig. 11. We show per-category evaluations
to compare performance across seen and unseen categories of CO3D in Tab. 2. We
provide a visualization of how to interpret the relative rotations in Fig. 12
and discuss the coordinate system in which we compute relative rotations in
Fig. 13. We discuss the learned symmetry modes as well as some failure modes
in Fig. 14. As a proof of concept, we use our energy-based predictor on a
deformable object (cat) in Fig. 15. We include architecture diagrams for our
energy-based pairwise pose predictor in Fig. 16 and the direct pose predictor
baseline in Fig. 17. Finally, we show qualitative comparisons between our
approach and the correspondence-based baselines on randomly selected sequences
on both seen and unseen categories in Fig. 18 and Fig. 19 respectively.

###  6.1 Derivation of Conditional Distribution for Coordinate Ascent

Given our pairwise conditional probabilities, the joint distribution over a
set of rotations can be computed as:

$\small{P\left(\\{R_{i}\\}_{i=1}^{N}\mid\\{I_{i}\\}_{i=1}^{N}\right)\propto
P\left(\\{R_{i},I_{i}\\}_{i=1}^{N}\right)=\alpha\exp\left(\sum_{(i,j)\in\mathcal{P}}f(R_{i\rightarrow
j},I_{i},I_{j})\right)}$ (6)

where $\mathcal{P}=\\{(i,j)\mid(i,j)\in[N]\times[N],i\not=j\\}$.

We are searching for the most likely set of rotations
$\\{R_{1},\ldots,R_{N}\\}$ under this joint distribution given images
$\\{I_{1},\ldots,I_{N}\\}$. For each iteration of coordinate ascent, we have
our current most likely set of rotations $\\{R_{1},\ldots,R_{N}\\}$ and wish
to update $R_{k}$. If we fix all $\\{R_{i}\\}_{i\not=k}$, the only terms in
$\mathcal{P}$ that can change are the ones involving $k$, and the rest can be
folded into a scalar constant. Thus, searching for the rotation $R_{k}$ that
maximizes the overall likelihood is equivalent to finding the most likely
hypothesis under
$P\left(R_{k}^{\prime}\mid\\{R_{i}\\}_{i=1}^{k},\\{I_{i}\\}_{i=1}^{N}\right)$:

$\displaystyle\log P(R_{k}^{\prime}\mid\\{R_{i}\\}_{i\not=k},\\{I_{i}\\}_{i})$
$\displaystyle=\sum_{(i,j)\in\mathcal{P}}f(R_{i\rightarrow
j},I_{i},I_{j})+C_{1}$ (7)
$\displaystyle=\sum_{i\not=k}\left(f(R_{i\rightarrow
k^{\prime}},I_{i},I_{k})+f(R_{k^{\prime}\rightarrow
i},I_{k},I_{i})\right)+C_{2}$ (8)

This simplifies each iteration of coordinate ascent from a
$\mathcal{O}(N^{2})$ sum to a $\mathcal{O}(N)$ sum.

Acc @ $30^{\circ}$ | 3 | 5 | 10 | 20
---|---|---|---|---
Ours (Sequential) | 0.50 | 0.48 | 0.42 | 0.39
Ours (MST) | 0.52 | 0.50 | 0.47 | 0.43
Ours (Grad. Asc.) | 0.52 | 0.51 | 0.49 | 0.47
Ours (Coord. Asc.) | 0.59 | 0.58 | 0.59 | 0.59
Table 1: Ablations on Seen Categories in CO3D (Random Sequence Subsampling).
One way to convert a set of relative pose predictions to a coherent set of
joint poses is by naively linking them together in a sequence (Sequential). We
find that greedily linking them by constructing a maximum spanning tree (MST)
performs slightly better since it incorporates that most confident relative
rotation predictions. To make better use of our energy-based relative pose
predictor, we tried directly running gradient ascent initialized from the MST
solution and maximizing energy using ADAM (Grad. Asc.). Because the loss
landscape is non-smooth, we observe that it does not deviate much from the MST
solution. We found the scoring-based block coordinate ascent (Coord. Asc.) to
be the most effective.

|  | Acc. @ 30° (%)
---|---|---
| Category | 3 | 5 | 10 | 20
Seen Categories | Apple | 59 | 60 | 62 | 61
Backpack | 63 | 58 | 59 | 57
Banana | 67 | 54 | 63 | 55
Baseballbat | 100 | 67 | 70 | 73
Baseballglove | 48 | 56 | 56 | 55
Bench | 69 | 75 | 68 | 66
Bicycle | 62 | 61 | 63 | 62
Bottle | 59 | 57 | 60 | 60
Bowl | 80 | 75 | 77 | 80
Broccoli | 55 | 54 | 51 | 51
Cake | 46 | 47 | 47 | 54
Car | 67 | 71 | 70 | 62
Carrot | 60 | 64 | 63 | 65
Cellphone | 69 | 78 | 72 | 69
Chair | 53 | 55 | 55 | 56
Cup | 55 | 56 | 54 | 51
Donut | 52 | 44 | 51 | 51
Hairdryer | 58 | 56 | 58 | 54
Handbag | 66 | 63 | 62 | 61
Hydrant | 72 | 73 | 68 | 70
Keyboard | 72 | 73 | 74 | 74
Laptop | 88 | 87 | 89 | 89
Microwave | 56 | 65 | 55 | 58
Motorcycle | 59 | 60 | 62 | 61
Mouse | 68 | 70 | 69 | 67
Orange | 52 | 52 | 51 | 49
Parkingmeter | 22 | 27 | 23 | 22

|  | Acc. @ 30° (%)
---|---|---
| Category | 3 | 5 | 10 | 20
Seen Categories | Pizza | 50 | 57 | 57 | 55
Plant | 46 | 47 | 49 | 51
Stopsign | 42 | 49 | 47 | 47
Teddybear | 47 | 52 | 49 | 48
Toaster | 76 | 75 | 71 | 73
Toilet | 76 | 80 | 75 | 77
Toybus | 63 | 70 | 72 | 71
Toyplane | 43 | 57 | 48 | 51
Toytrain | 81 | 73 | 75 | 75
Toytruck | 71 | 69 | 68 | 68
Tv | 78 | 83 | 87 | 86
Umbrella | 58 | 60 | 54 | 55
Vase | 58 | 55 | 55 | 51
Wineglass | 51 | 46 | 46 | 47
Seen Mean | 61 | 62 | 61 | 61
Unseen Categories | Ball | 45 | 41 | 43 | 44
Book | 51 | 49 | 49 | 47
Couch | 42 | 58 | 39 | 35
Frisbee | 55 | 49 | 40 | 38
Hotdog | 58 | 61 | 50 | 49
Kite | 28 | 23 | 27 | 24
Remote | 64 | 58 | 65 | 66
Sandwich | 37 | 41 | 41 | 42
Skateboard | 56 | 64 | 64 | 65
Suitcase | 59 | 61 | 67 | 63
Unseen Mean | 49 | 51 | 48 | 48

Table 2: Per-category Evaluation on CO3D with Random Sequence Sampling. We
find that rotationally symmetric objects (e.g. apple, orange, wineglass) tend
to be challenging. We were surprised to find that bowls worked well, likely
because the bowls in the CO3D dataset tend to have a lot of texture or even
stickers. Objects with distinctive shapes (e.g. toilet, laptop) tend to be
easier to orient. Note that some object categories have few instances for both
training and testing (e.g. baseballbat, parkingmeter). Figure 11: Evaluation
of correspondence-based approaches on large image sets (on “Seen Categories”
Split). We evaluate the DROID-SLAM [64] and COLMAP (with SuperPoint features
and SuperGlue matching) baselines on much longer image sequences (N=30, 40,
50). We verify that these approaches, which rely on correspondences between
images, can achieve good performance when the cameras baselines are narrow.
Nonetheless, the poor performance at $N<20$ suggests that there is a rich
space for improving camera pose estimation in the low data regime, which is
the setting that we target in our work.  Figure 12: Interpreting Relative
Rotations using a 2-Sphere. Given “Image 1”, we show how “Image 2” would have
appeared given different relative rotations. (a), (b), and (c) show relative
rotations with 60°, 120°, and 180° yaw respectively. (d) and (e) show relative
rotations with 45° and -45° pitch respectively. (f) shows a relative rotation
with just roll. (g) shows a relative rotation with all three components. We
use a view-aligned coordinate system (See Fig. 13) when computing relative
rotations. Inspired by [39], we visualize the $\textbf{SO}(3)$ by projecting
rotations onto a 2-sphere, with the x-axis representing yaw, y-axis
representing pitch, and color representing roll. Figure 13: View-aligned vs
Object-centric Coordinate System. We compute relative rotations in a
coordinate system (red axes on left) aligned with the camera (red wireframe on
left). Relative rotations aligned to the camera viewpoint can always be
computed without reasoning about the object’s alignment with respect to the
camera. While possibly more intuitive, relative rotations in the object
coordinate system (blue axes on left) must be defined with respect to a
canonical object pose and thus cannot be computed in general. On the right, we
visualize a 60° yaw relative rotation from Image 1 in the view-aligned
coordinate system (red) and object-centric coordinate system (blue). Figure
14: Learned Pairwise Distributions on Seen Categories (Test Set). Here we
visualize the learned pairwise distributions for various pairs of images. Top
left: The images correspond to opposite sides of the apple, so the relative
pose is ambiguous. Our approach predicts a rotationally symmetric band of
possible rotations. Top middle: The images have sufficient overlap such that
the relative rotation is unambiguous and our method predicts a single mode for
the apples. Top right: For rectangular objects such as microwaves, our
approach often predicts 4 modes corresponding to each of the 90 degree
rotations. Bottom left: Our approach predicts 2 modes for the bicycle because
the first viewpoint is challenging. Bottom-middle: Clashing foreground and
background textures can be a challenge for our pairwise predictor. Even though
the relative pose should be unambiguous, our method places low probability on
the correct pose although it does recognize the rotational symmetry of the cup
category. Bottom-right: Unusual object appearances is another failure mode of
our method, which defaults to placing high probability mass on the identity
matrix. Our method does recognize the rotational symmetry of the cake
category. Figure 15: Deformable Objects. Existing SfM and SLAM pipelines often
make assumptions about rigidity or appearance constancy in order for bundle
adjustment to converge. Our method has no such requirements and can be run
even on deformable objects. While the ground truth poses for these images of a
cat are unknown, the relative rotation of the camera w.r.t the cat is roughly
-90 degrees yaw with negative pitch while the relative rotation of the camera
w.r.t. the couch has no pitch or yaw but some roll in the clockwise direction
(green). Although our training data does not include dynamic or deformable
objects, our network outputs plausible modes. Figure 16: Architecture Diagram
for our Pairwise Energy Predictor. We use a ResNet-50 [22] with anti-aliasing
[83] as our feature extractor. We directly apply positional encoding (8 bases)
[62] to the elements of the $3\times 3$ rotation matrix. We concatenate the
image features and positionally encoded rotations into a feature vector
($2048+2048+2\cdot 8\cdot 9$), which we feed into an MLP that predicts energy
(corresponding to unnormalized log probability). Figure 17: Architecture
Diagram for our Direct Pairwise Rotation Predictor. For the direct rotation
regression baseline, we still input the concatenated image features
($2048+2048$). To make the baseline more competitive, we increase the capacity
of the MLP to have 6 layers and a skip connection. The network predicts the
6-D rotation representation [86]. Figure 18: Randomly selected Qualitative
Results for Seen Categories. Figure 19: Randomly selected Qualitative Results
for Unseen Categories.

## References

  * [1] Balntas, V., Li, S., Prisacariu, V.: RelocNet: Continuous Metric Learning Relocalisation using Neural Nets. In: ECCV (2018)
  * [2] Bay, H., Tuytelaars, T., Gool, L.V.: SURF: Speeded Up Robust Features. In: ECCV (2006)
  * [3] Brachmann, E., Michel, F., Krull, A., Yang, M.Y., Gumhold, S., et al.: Uncertainty-Driven 6D Pose Estimation of Objects and Scenes from a Single RGB Image. In: CVPR (2016)
  * [4] Bukschat, Y., Vetter, M.: EfficientPose: An Efficient, Accurate and Scalable End-to-end 6D Multi Object Pose Estimation Approach. arXiv:2011.04307 (2020)
  * [5] Campos, C., Elvira, R., Gómez, J.J., Montiel, J.M.M., Tardós, J.D.: ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual-Inertial and Multi-Map SLAM. T-RO 37(6), 1874–1890 (2021)
  * [6] Carlone, L., Tron, R., Daniilidis, K., Dellaert, F.: Initialization Techniques for 3D SLAM: A Survey on Rotation Estimation and its Use in Pose Graph Optimization. ICRA (2015)
  * [7] Chen, B., Chin, T.J., Klimavicius, M.: Occlusion-Robust Object Pose Estimation with Holistic Representation. In: WACV (2022)
  * [8] Chen, K., Snavely, N., Makadia, A.: Wide-Baseline Relative Camera Pose Estimation with Directional Learning. In: CVPR (2021)
  * [9] Choy, C.B., Gwak, J., Savarese, S., Chandraker, M.: Universal Correspondence Network. NeurIPS (2016)
  * [10] Corona, E., Kundu, K., Fidler, S.: Pose Estimation for Objects with Rotational Symmetry. In: IROS (2018)
  * [11] Davison, A.J., Reid, I.D., Molton, N.D., Stasse, O.: MonoSLAM: Real-time Single Camera SLAM. TPAMI 29(6), 1052–1067 (2007)
  * [12] Deng, X., Mousavian, A., Xiang, Y., Xia, F., Bretl, T., Fox, D.: PoseRBPF: A Rao-Blackwellized Particle Filter for 6D Object Pose Tracking. In: RSS (2019)
  * [13] Deng, X., Xiang, Y., Mousavian, A., Eppner, C., Bretl, T., Fox, D.: Self-supervised 6D Object Pose Estimation for Robot Manipulation. In: ICRA (2020)
  * [14] DeTone, D., Malisiewicz, T., Rabinovich, A.: SuperPoint: Self-supervised Interest Point Detection and Description. In: CVPR-W (2018)
  * [15] Dusmanu, M., Rocco, I., Pajdla, T., Pollefeys, M., Sivic, J., Torii, A., Sattler, T.: D2-Net: A Trainable CNN for Joint Detection and Description of Local Features. In: CVPR (2019)
  * [16] Dusmanu, M., Schönberger, J.L., Pollefeys, M.: Multi-view Optimization of Local Feature Geometry. In: ECCV (2020)
  * [17] Engel, J., Koltun, V., Cremers, D.: Direct Sparse Odometry. TPAMI (2018)
  * [18] Furukawa, Y., Curless, B., Seitz, S.M., Szeliski, R.: Towards Internet-scale Multi-view Stereo. In: CVPR (2010)
  * [19] Gilitschenski, I., Sahoo, R., Schwarting, W., Amini, A., Karaman, S., Rus, D.: Deep Orientation Uncertainty Learning Based on a Bingham Loss. In: ICLR (2019)
  * [20] Goel, S., Gkioxari, G., Malik, J.: Differentiable Stereopsis: Meshes from Multiple Views Using Differentiable Rendering. In: CVPR (2022)
  * [21] Harris, C., Stephens, M.: A Combined Corner and Edge Detector. In: Alvey Vision Conference (1988)
  * [22] He, K., Zhang, X., Ren, S., Sun, J.: Deep Residual Learning for Image Recognition. In: CVPR (2016)
  * [23] Iwase, S., Liu, X., Khirodkar, R., Yokota, R., Kitani, K.M.: RePOSE: Fast 6D Object Pose Refinement via Deep Texture Rendering. In: ICCV (2021)
  * [24] Kehl, W., Manhardt, F., Tombari, F., Ilic, S., Navab, N.: SSD-6D: Making RGB-based 3D Detection and 6D Pose Estimation Great Again. In: ICCV (2017)
  * [25] Kendall, A., Cipolla, R.: Modelling Uncertainty in Deep Learning for Camera Relocalization. In: ICRA (2016)
  * [26] Kendall, A., Grimes, M., Cipolla, R.: PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization. In: ICCV (2015)
  * [27] Lin, C.H., Ma, W.C., Torralba, A., Lucey, S.: BARF: Bundle-Adjusting Neural Radiance Fields. In: ICCV (2021)
  * [28] Lindenberger, P., Sarlin, P.E., Larsson, V., Pollefeys, M.: Pixel-Perfect Structure-from-Motion with Featuremetric Refinement. In: ICCV (2021)
  * [29] Liu, C., Yuen, J., Torralba, A.: SIFT Flow: Dense Correspondence Across Scenes and Its Applications. TPAMI 33(5), 978–994 (2010)
  * [30] Lowe, D.G.: Distinctive Image Features from Scale-invariant Keypoints. IJCV 60(2), 91–110 (2004)
  * [31] Lucas, B.D., Kanade, T.: An Iterative Image Registration Technique with an Application to Stereo Vision. In: IJCAI (1981)
  * [32] Mahjourian, R., Wicke, M., Angelova, A.: Unsupervised Learning of Depth and Ego-Motion From Monocular Video Using 3D Geometric Constraints. In: CVPR (2018)
  * [33] Manhardt, F., Arroyo, D.M., Rupprecht, C., Busam, B., Birdal, T., Navab, N., Tombari, F.: Explaining the Ambiguity of Object Detection and 6D Pose from Visual Data. In: ICCV (2019)
  * [34] Melekhov, I., Ylioinas, J., Kannala, J., Rahtu, E.: Relative Camera Pose Estimation Using Convolutional Neural Networks. In: ACIVS (2017)
  * [35] Mildenhall, B., Srinivasan, P.P., Tancik, M., Barron, J.T., Ramamoorthi, R., Ng, R.: NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis. In: ECCV (2020)
  * [36] Mohlin, D., Sullivan, J., Bianchi, G.: Probabilistic Orientation Estimation with Matrix Fisher Distributions. NeurIPS (2020)
  * [37] Mur-Artal, R., Montiel, J.M.M., Tardos, J.D.: ORB-SLAM: A Versatile and Accurate Monocular SLAM System. T-RO 31(5), 1147–1163 (2015)
  * [38] Mur-Artal, R., Tardós, J.D.: ORB-SLAM2: An Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras. T-RO 33(5), 1255–1262 (2017)
  * [39] Murphy, K.A., Esteves, C., Jampani, V., Ramalingam, S., Makadia, A.: Implicit-PDF: Non-Parametric Representation of Probability Distributions on the Rotation Manifold. In: ICML (2021)
  * [40] Newcombe, R.A., Lovegrove, S.J., Davison, A.J.: DTAM: Dense Tracking and Mapping in Real-time. In: ICCV (2011)
  * [41] Novotny, D., Larlus, D., Vedaldi, A.: Learning 3D Object Categories by Looking Around Them. In: ICCV (2017)
  * [42] Novotny, D., Ravi, N., Graham, B., Neverova, N., Vedaldi, A.: C3DPO: Canonical 3D Pose Networks for Non-Rigid Structure From Motion. In: ICCV (2019)
  * [43] Oberweger, M., Rad, M., Lepetit, V.: Making Deep Heatmaps Robust to Partial Occlusions for 3D Object Pose Estimation. In: ECCV (2018)
  * [44] Okorn, B., Gu, Q., Hebert, M., Held, D.: ZePHyR: Zero-shot Pose Hypothesis Scoring. In: ICRA (2021)
  * [45] Okorn, B., Xu, M., Hebert, M., Held, D.: Learning Orientation Distributions for Object Pose Estimation. In: IROS (2020)
  * [46] Pautrat, R., Larsson, V., Oswald, M.R., Pollefeys, M.: Online Invariance Selection for Local Feature Descriptors. In: ECCV (2020)
  * [47] Prokudin, S., Gehler, P., Nowozin, S.: Deep Directional Statistics: Pose Estimation with Uncertainty Quantification. In: ECCV (2018)
  * [48] Reizenstein, J., Shapovalov, R., Henzler, P., Sbordone, L., Labatut, P., Novotny, D.: Common Objects in 3D: Large-Scale Learning and Evaluation of Real-life 3D Category Reconstruction. In: ICCV (2021)
  * [49] Revaud, J., De Souza, C., Humenberger, M., Weinzaepfel, P.: R2D2: Reliable and Repeatable Detector and Descriptor. NeurIPS (2019)
  * [50] Rodrigues, O.: Des lois géométriques qui régissent les déplacements d’un système solide dans l’espace, et de la variation des coordonnées provenant de ces déplacements considérés indépendamment des causes qui peuvent les produire. Journal de Mathématiques Pures et Appliquées 5 (1840)
  * [51] Rosinol, A., Abate, M., Chang, Y., Carlone, L.: Kimera: an Open-Source Library for Real-Time Metric-Semantic Localization and Mapping. In: ICRA (2020)
  * [52] Sarlin, P.E., Cadena, C., Siegwart, R., Dymczyk, M.: From Coarse to Fine: Robust Hierarchical Localization at Large Scale. In: CVPR (2019)
  * [53] Sarlin, P.E., DeTone, D., Malisiewicz, T., Rabinovich, A.: SuperGlue: Learning Feature Matching with Graph Neural Networks. In: CVPR (2020)
  * [54] Schönberger, J.L., Frahm, J.M.: Structure-from-Motion Revisited. In: CVPR (2016)
  * [55] Schönberger, J.L., Zheng, E., Pollefeys, M., Frahm, J.M.: Pixelwise View Selection for Unstructured Multi-View Stereo. In: ECCV (2016)
  * [56] Schops, T., Sattler, T., Pollefeys, M.: BAD SLAM: Bundle Adjusted Direct RGB-D SLAM. In: CVPR (2019)
  * [57] Simonyan, K., Vedaldi, A., Zisserman, A.: Learning Local Feature Descriptors Using Convex Optimisation. TPAMI 36(8), 1573–1585 (2014)
  * [58] Snavely, N., Seitz, S.M., Szeliski, R.: Photo Tourism: Exploring Photo Collections in 3D. In: SIGGRAPH. ACM (2006)
  * [59] Song, C., Song, J., Huang, Q.: Hybridpose: 6D Object Pose Estimation under Hybrid Representations. In: CVPR (2020)
  * [60] Sun, X., Wu, J., Zhang, X., Zhang, Z., Zhang, C., Xue, T., Tenenbaum, J.B., Freeman, W.T.: Pix3D: Dataset and Methods for Single-Image 3D Shape Modeling. In: CVPR (2018)
  * [61] Sundermeyer, M., Marton, Z.C., Durner, M., Brucker, M., Triebel, R.: Implicit 3D Orientation Learning for 6D Object Detection from RGB Images. In: ECCV (2018)
  * [62] Tancik, M., Srinivasan, P.P., Mildenhall, B., Fridovich-Keil, S., Raghavan, N., Singhal, U., Ramamoorthi, R., Barron, J.T., Ng, R.: Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains. NeurIPS (2020)
  * [63] Tang, C., Tan, P.: BA-Net: Dense Bundle Adjustment Network. In: ICLR (2019)
  * [64] Teed, Z., Deng, J.: DROID-SLAM: Deep Visual SLAM for Monocular, Stereo, and RGB-D Cameras. NeurIPS (2021)
  * [65] Tekin, B., Sinha, S.N., Fua, P.: Real-Time Seamless Single Shot 6D Object Pose Prediction. In: CVPR (2018)
  * [66] Tola, E., Lepetit, V., Fua, P.: Daisy: An Efficient Dense Descriptor Applied to Wide-baseline Stereo. TPAMI 32(5), 815–830 (2009)
  * [67] Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W.: Bundle Adjustment—A Modern Synthesis. In: International workshop on vision algorithms (1999)
  * [68] Truong, P., Danelljan, M., Timofte, R.: GLU-Net: Global-Local Universal Network for Dense Flow and Correspondences. In: CVPR (2020)
  * [69] Ummenhofer, B., Zhou, H., Uhrig, J., Mayer, N., Ilg, E., Dosovitskiy, A., Brox, T.: DeMoN: Depth and Motion Network for Learning Monocular Stereo. In: CVPR (2017)
  * [70] Vijayanarasimhan, S., Ricco, S., Schmid, C., Sukthankar, R., Fragkiadaki, K.: SfM-Net: Learning of Structure and Motion from Video. arXiv:1704.07804 (2017)
  * [71] Wang, C., Xu, D., Zhu, Y., Martín-Martín, R., Lu, C., Fei-Fei, L., Savarese, S.: DenseFusion: 6D Object Pose Estimation by Iterative Dense Fusion. In: CVPR (2019)
  * [72] Wang, Q., Zhou, X., Hariharan, B., Snavely, N.: Learning Feature Descriptors Using Camera Pose Supervision. In: ECCV (2020)
  * [73] Wang, S., Clark, R., Wen, H., Trigoni, N.: DeepVO: Towards End-to-End Visual Odometry with Deep Recurrent Convolutional Neural Networks. In: ICRA (2017)
  * [74] Wang, W., Hu, Y., Scherer, S.: TartanVO: A Generalizable Learning-based VO. In: CoRL (2020)
  * [75] Wei, X., Zhang, Y., Li, Z., Fu, Y., Xue, X.: DeepSFM: Structure From Motion Via Deep Bundle Adjustment. In: ECCV (2020)
  * [76] Wong, J.M., Kee, V., Le, T., Wagner, S., Mariottini, G.L., Schneider, A., Hamilton, L., Chipalkatty, R., Hebert, M., Johnson, D.M., et al.: SegICP: Integrated Deep Semantic Segmentation and Pose Estimation. In: IROS (2017)
  * [77] Xiang, Y., Schmidt, T., Narayanan, V., Fox, D.: PoseCNN: A Convolutional Neural Network for 6D Object Pose Estimation in Cluttered Scenes. In: RSS (2018)
  * [78] Xiao, Y., Qiu, X., Langlois, P., Aubry, M., Marlet, R.: Pose from Shape: Deep Pose Estimation for Arbitrary 3D Objects. In: BMVC (2019)
  * [79] Yi, K.M., Trulls, E., Lepetit, V., Fua, P.: LIFT: Learned Invariant Feature Transform. In: ECCV (2016)
  * [80] Yin, Z., Shi, J.: GeoNet: Unsupervised Learning of Dense Depth, Optical Flow and Camera Pose. In: CVPR (2018)
  * [81] Zhang, J.Y., Pepose, S., Joo, H., Ramanan, D., Malik, J., Kanazawa, A.: Perceiving 3D Human-Object Spatial Arrangements from a Single Image in the Wild. In: ECCV (2020)
  * [82] Zhang, J.Y., Yang, G., Tulsiani, S., Ramanan, D.: NeRS: Neural Reflectance Surfaces for Sparse-view 3D Reconstruction in the Wild. In: NeurIPS (2021)
  * [83] Zhang, R.: Making Convolutional Networks Shift-Invariant Again. In: ICML (2019)
  * [84] Zhou, H., Ummenhofer, B., Brox, T.: DeepTAM: Deep Tracking and Mapping. In: ECCV (2018)
  * [85] Zhou, T., Brown, M., Snavely, N., Lowe, D.G.: Unsupervised Learning of Depth and Ego-Motion From Video. In: CVPR (2017)
  * [86] Zhou, Y., Barnes, C., Lu, J., Yang, J., Li, H.: On the Continuity of Rotation Representations in Neural Networks. In: CVPR (2019)
  * [87] Zubizarreta, J., Aguinaga, I., Montiel, J.M.M.: Direct Sparse Mapping. T-RO (2020)


# Eschers and Stanley’s chromatic e-positivity conjecture in length-2

Alexandre Rok  Section de mathématiques, Université de Genève
<EMAIL_ADDRESS>and  Andras Szenes  Section de mathématiques,
Université de Genève<EMAIL_ADDRESS>
###### Abstract.

We give a short proof of the chromatic e-positivity conjecture of Stanley for
length-2 partitions.

## 1\. Introduction

Let $G$ be a finite graph, $V(G)$ \- the set of vertices of $G$, $E(G)$ \- the
set of edges of $G$.

######  Definition 1.1.

A proper coloring $c$ of $G$ is a map

$c:V\rightarrow\mathbb{N}$

such that no two adjacent vertices are colored in the same color.

For each coloring $c$ we define a monomial

$x^{c}=\prod_{v\in V}x_{c(v)},$

where $x_{1},x_{2},...,x_{n},...$ are commuting variables. We denote by
$\Pi(G)$ the set of all proper colorings of $G$, and by $\Lambda$ the ring of
symmetric functions in the infinite set of variables $\\{x_{1},x_{2},...\\}.$

In [10], Stanley defined the chromatic symmetric function of a graph as
follows.

######  Definition 1.2.

The chromatic symmetric function $X_{G}\in\Lambda$ of a graph $G$ is the sum
of the monomials $x^{c}$ over all proper colorings of $G$:

$X_{G}=\sum\limits_{c\in\Pi(G)}x^{c}.$

######  Remark 1.3.

We could equally consider a finite, but sufficiently large number colors $r$.
In this case, we would have $X_{G}\in\Lambda_{r}$, the set of symmetric
polynomials in $r$ variables. This would somewhat complicate the notation, but
would not change any of our results.

######  Definition 1.4.

Denote by $e_{m}$ the $m$-th elementary symmetric function:

$e_{m}=\sum\limits_{i_{1}<i_{2}<...<i_{m}}x_{i_{1}}\cdot
x_{i_{2}}\cdot...\cdot x_{i_{m}},$

where $i_{1},..,i_{k}\in\mathbb{N}$. Given a non-increasing sequence of
positive integers (we will call these partitions)

$\lambda=(\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{k}),\
\lambda_{i}\in\mathbb{N},$

we define the elementary symmetric function
$e_{\lambda}=\prod\limits_{i=1}^{k}e_{\lambda_{i}}.$ These functions form a
basis of $\Lambda.$

######  Definition 1.5.

A symmetric function $X\in\Lambda$ is $e$-positive if it has non-negative
coefficients in the basis of the elementary symmetric functions.

######  Definition 1.6.

Denote by $p_{m}$ the $m$-th power sum symmetric function:

$p_{m}=\sum\limits_{i\in\mathbb{N}}x^{m}_{i}.$

Given a partition
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{k})$, we define the
power sum symmetric function
$p_{\lambda}=\prod\limits_{i=1}^{k}p_{\lambda_{i}}.$ These functions also form
a basis of $\Lambda.$

######  Definition 1.7.

Given a partition
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{k})$, we define the
monomial symmetric function

$m_{\lambda}=\sum\limits_{i_{1}<i_{2}<...<i_{k}}\sum\limits_{\lambda^{\prime}\in
S_{k}(\lambda)}x_{i_{1}}^{\lambda_{1}^{\prime}}\cdot
x_{i_{2}}^{\lambda_{1}^{\prime}}\cdot...\cdot
x_{i_{k}}^{\lambda_{k}^{\prime}},$

where the inner sum is taken over the set of all permutations of the sequence
$\lambda$, denoted by $S_{k}(\lambda)$.

######  Example 1.

The chromatic symmetric function of $K_{n}$, the complete graph on $n$
vertices, is $X_{K_{n}}=n!\,e_{n}$; in particular, $X_{K_{n}}$ is
$e$-positive.

######  Definition 1.8.

For a poset $P$, the incomparability graph, $\textnormal{inc}(P)$, is the
graph with elements of $P$ as vertices, where two vertices are connected if
and only if they are not comparable in $P$.

######  Definition 1.9.

Given a pair of natural numbers $a,b\in\mathbb{N}^{2}$, we say that a poset
$P$ is (a+b)-free if it does not contain a length-$a$ and a length-$b$ chain,
whose elements are incomparable.

######  Definition 1.10.

A unit interval order (UIO) is a partially ordered set which is isomorphic to
a finite subset of $U\subset\mathbb{R}$ with the following poset structure:

$\text{for }u,w\in U:\ u\succ w\text{ iff }u\geq w+1.$

Thus $u$ and $w$ are incomparable precisely when $|u-w|<1$ and we will use the
notation $u\sim w$ in this case.

######  Theorem 1.11 (Scott-Suppes [5]).

A finite poset $P$ is a UIO if and only if it is $(2+2)$\- and $(3+1)$-free.

Stanley [10] initiated the study of incomparability graphs of $(3+1)$-free
partially ordered sets. Analyzing the chromatic symmetric functions of these
incomparability graphs, Stanley [10] stated the following positivity
conjecture.

######  Conjecture 1 (Stanley).

If $P$ is a $(3+1)$-free poset, then $X_{\textnormal{inc}(P)}$ is
$e$-positive.

For a graph $G$ let us denote by ${c_{\lambda}}(G)$ the coefficients of
$X_{G}$ with respect to the $e$-basis. We omit the index $G$ whenever this
causes no confusion. The conjecture thus states that in the expansion

$X_{G}=\sum\limits_{\lambda}c_{\lambda}e_{\lambda},$

for the case when $G$ is the incomparability graph of a $(3+1)$-free poset,
the coefficients $c_{\lambda}$ are nonnegative for all partitions $\lambda$.

Conjecture 1 has been verified with the help of computers for up to 20-element
posets [4]. In 2013, Guay-Paquet [4] showed that to prove this conjecture, it
would be sufficient to verify it for the case of $(3+1)$\- and $(2+2)$-free
posets, i.e. for unit interval orders (see Theorem 1.11). More precisely:

######  Theorem 1.12 (Guay-Paquet).

Let $P$ be a $(3+1)$-free poset. Then, $X_{\mathrm{inc}}(P)$ is a convex
combination of the chromatic symmetric functions

$\\{X_{\mathrm{inc}}(P^{\prime})\ |\ P^{\prime}\ \mathrm{is}\ \mathrm{a}\
(3+1)\mathrm{-}\ \mathrm{and}\ (2+2)\mathrm{-free}\ \mathrm{poset}\\}.$

For a long time the strongest general result in this direction was that of
Gasharov [3].

######  Definition 1.13.

For a partition $\lambda=(\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{k})$,
define the Schur functions
$s_{\lambda}=\mathrm{det}(e_{\lambda_{i}^{*}+j-i})_{i,j}$, where $\lambda^{*}$
is the conjugate partition to $\lambda$. The functions $\\{s_{\lambda}\\}$
form a basis of $\Lambda$.

######  Definition 1.14.

A symmetric polynomial $X$ is $s$-positive if it has non-negative coefficients
in the basis of Schur functions.

Obviously, a product of $e$-positive functions is $e$-positive. This also
holds for $s$-positive functions. Thus, the equality $e_{n}=s_{1^{n}}$ implies
that $e$-positive functions are $s$-positive, and thus $s$-positivity is
weaker than $e$-positivity.

######  Theorem 1.15 (Gasharov).

If $P$ is a $(3+1)$-free poset, then $X_{\textnormal{inc}(P)}$ is
$s$-positive.

Gasharov proved $s$-positivity by constructing so-called $P$-tableau and
finding a one-to-one correspondence between these tableau and $s$-coefficients
[3].

The strongest known result on the $e$-coefficients was obtained by Stanley in
[10]. He showed that sums of $e$-coefficients over the partitions of fixed
length are non-negative:

######  Theorem 1.16 (Stanley).

For a finite graph $G$ and $j\in\mathbb{N}$, suppose

$X_{G}=\sum\limits_{\lambda}c_{\lambda}e_{\lambda},$

and let $\text{sink}(G,j)$ be the number of acyclic orientation of $G$ with
$j$ sinks. Then

$\text{sink}(G,j)=\sum\limits_{l(\lambda)=j}c_{\lambda}.$

######  Remark 1.17.

By taking $j=1$, it follows from the theorem that $c_{n}$ is non-negative.

In [8], we introduced a combinatorial device that we called correct sequences
( or corrects).

######  Definition 1.18.

Let U be a UIO. We will call a sequence $w=[w_{1},\dots,w_{k}]$ of elements of
$U$ correct if

  * •

$w_{i}\not\succ w_{i+1}$ for $i=1,2,\dots,k-1$

  * •

and for each $j=2,\dots,k$, there exists $i<j$ such that $w_{i}\not\prec
w_{j}$.

Every sequence of length 1 is correct, and sequence $[w_{1},w_{2}]$ is correct
precisely when $w_{1}\sim w_{2}$. The second condition (supposing that the
first one holds) may be reformulated as follows: for each $j=1,\dots k$, the
subset $\\{w_{1},\dots,w_{j}\\}\subset U$ is connected with respect to the
graph structure ${(U,\sim)}$. Using this notation, we proved the following.

######  Theorem 1.19.

Let $X_{\text{inc}(U)}=\sum\limits_{\lambda}c_{\lambda}e_{\lambda}$ be a
chromatic symmetric function of the $n$-element unit interval order $U$. Then
$c_{n}$ is equal to the number of corrects of length $n$, in which every
element of $U$ is used exactly once.

In particular, we showed that the coefficient $c_{n}$ of the chromatic
polynomial is non-negative for UIOs. This reproduced results by Stanley [11]
and Chow [2], who showed the positivity of $c_{n}$ for $(3+1)$-free posets
using combinatorial techniques, and linked $e$-coefficients with the acyclic
orientations of the incomparability graphs. Using corrects allowed us to go
further, and show the following (see [7]):

######  Theorem 1.20.

Let $X_{\text{inc}(P)}=\sum\limits_{\lambda}c_{\lambda}e_{\lambda}$ be a
chromatic symmetric function of the $(3+1)$-free poset $P$, and
$k\in\mathbb{N}$. Then $c_{n-k,1^{k}}$, $c_{n-2,2}$, $c_{n-3,2,1}$ and
$c_{2^{k},1^{n-2k}}$ are non-negative integers.

In this article, we use an alternative combinatorial presentation of the
coefficient $c_{n}$ introduced by Siegl in [9], where they also showed
$e$-positivity for all partitions with equal parts. We took up this new tool,
and managed to give a very sort, elegant proof of Stanley’s conjecture for all
partitions of length 2: $\lambda=n\geq k$. This approach can be extended to
the case of arbitrary partitions, but this work is somewhat more involved.
Very recently, another proof was announced for the length-2 case by Abreu and
Nigro [1] using substantially more complicated tools which links this
combinatorial problem to the topology of certain algebraic varieties. We hope
that the combination of these approaches will lead to further insights into
the meaning of e-positivity.

This short article is structured as follows: we begin with recalling Stanley’s
homomorphism, which we used in our previous work as well §2. We set up our
notations in §3, and give some initial structural statements in the §4. The
main construction and the proof is presented then in §5.

Acknowledgments. We are grateful to Alexander Paunov for his help, ideas, and
his generous support.

## 2\. Stanley’s $G$-homomorphism

Let $G$ be a finite graph with vertex set $V(G)=\\{v_{1},...,v_{n}\\}$ and
edge set $E(G)$. We will consider the vertices as formal commuting variables
and introduce the polynomial ring $\Lambda_{G}=\mathbb{R}[v_{1},...,v_{n}]$.
Stanley [11, p. 6] defined a ring homomorphism
$\rho_{G}:\Lambda\to\Lambda_{G}$ by setting the images of the free generators
of $\Lambda$, the elementary symmetric polynomials:

$e_{i}^{G}=\sum\limits_{\begin{subarray}{c}S\subset V\\\
S\mathrm{-indep},\,\\#S=i\end{subarray}}\prod\limits_{v\in S}v,$

where the sum is taken over all $i$-element independent subsets $S$ of $V$, in
which no two vertices form an edge, i.e. independent subsets. We set
$e_{0}^{G}=1$, and $e_{i}^{G}=0$ for $i<0$.

The correspondence $e_{i}\mapsto e_{i}^{G}$ then extends to the ring
homomorphism $\rho_{G}:\Lambda\to\Lambda_{G}$, called Stanley’s
$G$-homomorphism. For $f\in\Lambda$, we will use the notation $f^{G}$ for
$\rho_{G}(f)$.

######  Remark 2.1.

Note that the polynomials $f^{G}$ are not necessarily symmetric.

######  Example 2.

Given a partition $\lambda=\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{k},\
k\in\mathbb{N},$ we have

$e_{\lambda}^{G}=\prod\limits_{i=1}^{k}e_{i}^{G},$
$s_{\lambda}^{G}=\mathrm{det}(e_{\lambda_{i}^{*}+j-i}^{G}).$

For an integer function $\alpha:V\rightarrow\mathbb{N}$ define the monomial

$v^{\alpha}=\prod\limits_{v\in V}v^{\alpha(v)},$

and introduce the notation $[v^{\alpha}]f^{G}$ for the coefficient of
$v^{\alpha}$ in the polynomial $f^{G}\in\Lambda_{G}$.

Let $G^{\alpha}$ denote the graph, obtained by replacing every vertex $v$ of
$G$ by the complete subgraph of size $\alpha(v)$: $K_{\alpha(v)}^{v}$. Given
vertices $u$ and $v$ of $G$, a vertex of $K_{\alpha(v)}^{v}$ is connected to a
vertex of $K_{\alpha(u)}^{u}$ if and only if $u$ and $v$ form an edge in $G$.

Stanley [11, p. 6] found the following connection between the $G$-analogues of
symmetric functions and the chromatic polynomial $X_{G}$. Following Stanley
[11].

Let $x$ and $y$ stand for two infinite set of variables. Using the Cauchy
identity, one can prove the well-known identity

$\sum\limits_{\lambda}s_{\lambda}(x)s_{\lambda^{*}}(y)=\sum\limits_{\lambda}m_{\lambda}(x)e_{\lambda}(y)=\sum\limits_{\lambda}e_{\lambda}(x)m_{\lambda}(y)$

Applying the $G$-homomorphism $\rho_{G}$, we obtain the function

(1)
$T(x,v)=\sum\limits_{\lambda}m_{\lambda}(x)e^{G}_{\lambda}(v)=\sum\limits_{\lambda}s_{\lambda}(x)s^{G}_{\lambda^{*}}(v)=\sum\limits_{\lambda}e_{\lambda}(x)m^{G}_{\lambda}(v).$

where the sums are taken over all partitions. Then

(2) $[v^{\alpha}]T(x,v)\prod\limits_{v\in V}\alpha(v)!=X_{G^{\alpha}}.$

An immediate consequence of the formulas (1) and (2) is the following result
of Stanley:

######  Theorem 2.2 (Stanley).

For every finite graph G

  1. (1)

$X_{G^{\alpha}}$ is s-positive for every $\alpha:V(G)\rightarrow\mathbb{N}$ if
and only if $s_{\lambda}^{G}\in\mathbb{N}[V(G)]$ for every partition
$\lambda$.

  2. (2)

$X_{G^{\alpha}}$ is e-positive for every $\alpha:V(G)\rightarrow\mathbb{N}$ if
and only if $m_{\lambda}^{G}\in\mathbb{N}[V(G)]$ for every partition
$\lambda$.

######  Remark 2.3.

If $X_{G^{\alpha}}=\sum\limits_{\lambda}c^{\alpha}_{\lambda}e_{\lambda},$ then
$c_{\lambda}^{\alpha}=[v^{\alpha}]m^{G}_{\lambda}.$ Hence, monomial positivity
of $m^{G}_{\lambda}$ is equivalent to the positivity of $c_{\lambda}^{\alpha}$
for every $\alpha$.

From now on, we will concentrate on the incomparability graphs of UIOs, and we
will use the simplified notation $m_{\lambda}^{U}$ for the relevant
coefficient. Then Theorem 2.2 combined with the reductions cited in §1 leads
to the following simple reformulation of Stanley’s chromatic conjecture in the
language of $G$-polynomials.

######  Proposition 2.4.

Suppose that every UIO $U=\\{v_{1},\dots,v_{n}\\}$, the coefficient of the
monomial $\prod_{j=1}^{n}v_{j}$ in the polynomial
$m^{\mathrm{inc}(U)}_{\lambda}$ is nonnegative. Then Conjecture 1 is true.

We have thus defined for each UIO $U$ of $n$ unit intervals on the real line
and each partition $\lambda$ of $n$ an integer
$[\prod_{j=1}^{n}v_{j}]m^{\mathrm{inc}(U)}_{\lambda}$, which, from now on, we
will simply denote by $m_{\lambda}^{U}$:

$m_{\lambda}^{U}\overset{\mathrm{def}}{=}[\prod_{j=1}^{n}v_{j}]m^{\mathrm{inc}(U)}_{\lambda}$

Our task is to show that this number is nonnegative for all partitions. We
will treat the case of length-2 partitions in this short paper.

## 3\. Preparations

A key idea appeared in , where an alternative definition of correct sequences
was introduced. It will be convenient to set the following notation for
sequences in unit interval orders.

Given two unit intervals $w_{1},w_{2}$ on the real line there is a trichotomy
of possible relative position between them:

  1. (1)

$w_{1}$ intersects $w_{2}$,

  2. (2)

$w_{1}\cap w_{2}=\emptyset$ and $w_{1}$ is left of $w_{2}$,

  3. (3)

$w_{1}\cap w_{2}=\emptyset$ and $w_{1}$ is right of $w_{2}$.

We will use the notation $w_{1}\prec w_{2}$ for case (2), $w_{1}\succ w_{2}$
for case (3) and $w_{1}\rightarrow w_{2}$ if either case (1) or case (2)
holds.

Let $U$ be a UIO, i.e a set of unit intervals on the real line. We will call a
sequence of elements of $U$

$w_{1}\lhd w_{2}\lhd\dots\lhd w_{l-1}\lhd w_{m},$

where, in each place, $\lhd$ is one of the symbols $\prec$ or $\rightarrow$, a
logical sequence, which is, in fact, a statement (which is either true or
not).

We will use the structure of UIOs in the following form then.

######  Lemma 3.1.

Let

$w_{1}\lhd w_{2}\lhd\dots\lhd w_{m-1}\lhd w_{m}$

be a logical sequence, which contains $r$ $\prec$-symbols, and $s$
$\rightarrow$-symbols with $r+s=m-1$ and $r\geq s$. Then this statement is
false.

Informally, we will call such sequences impossible.

We call a sequence $[w_{1},w_{2},\dots,w_{k}]$ of different elements of $U$ a
$k$-Escher if

$w_{1}\rightarrow w_{2}\rightarrow\dots\rightarrow w_{k}\rightarrow w_{1}$

holds. We will denote the operation of cyclic permutation on sequences by
$\zeta$:

$\zeta:[w_{1},w_{2},\dots,w_{k}]\mapsto[w_{k},w_{1},w_{2}\dots,w_{k-1}].$

Then acting by powers of $\zeta$ on an $k$-Escher produces $k-1$ new
$k$-Eschers. As all the $k$ statements we obtain this way are equivalent,
sometimes, we will use the term cyclic Escher for the isomorphism class of
sequences related by $\zeta$. An Escher then is a cyclic Escher with a chosen
initial point. Also, given a $k$-Escher, we will think of the index set as
integers reduced to modulo $k$; thus $w_{0}=w_{k}$, for example.

A key result of is that the number $m_{n}^{U}$ of a UIO is the same as the
number of Eschers of the same length. Combined with our earlier results, this
leads to the following statement.

######  Theorem 3.2.

Let $U=\\{v_{1},\dots,v_{n}\\}$ be a UIO. Then

$m_{n}^{U}=\\#\\{\text{correct sequences of length }n\text{ in
}U\\}=\\#\\{\text{$n$-Eschers in }U\\}.$

This is thus the first instance of the conjecture: it shows that statement for
all "partitions" of length 1.

######  Corollary 3.3.

Since $\\#\\{\text{$n$-Eschers in }U\\}=N\cdot\\#\\{\text{cyclic $n$-Eschers
in }U\\}$, we can conclude that $m_{n}^{U}$ is divisible by $n$.

## 4\. The conjecture in the length-2 case

### 4.1. A reformulation using Eschers

Fix to positive integers $n\geq k$, and set $N=n+k$. In this paper, we will
show that $m_{nk}^{U}\geq 0$ for any UIO $U$ with $N$ elements.

For a positive integer $m$, introduce the notation

$P^{U}_{m}=\\{\text{length-}m\text{ Eschers in }U\\}$

Let us suppose, for simplicity, that $n>k$. To study $m_{nk}^{U}$, we will use
the formula

$m_{nk}=p_{n}\cdot p_{k}-p_{n+k}\text{ in }\Lambda.$

Applying Stanley’s homomorphism, this implies that

$m_{nk}^{U}=\\#P_{n}^{U}\cdot\\#P_{k}^{U}-\\#P^{U}_{n+k}.$

Then the chromatic conjecture for length-2 partitions will follow from the
following statement.

######  Theorem 4.1.

Let $n>k$, and let $U$ be a UIO of $n+k$ intervals. Then

$\\#P_{n}^{U}\cdot\\#P_{k}^{U}\geq\\#P^{U}_{n+k}.$

We will give a more precise statement below. For now, we begin with some
preparatory work.

### 4.2. Sub-Eschers

We introduce a key notion in this paragraph.

######  Lemma 4.2.

Let $U$ be a UIO of $N=n+k$ elements, and let $w=[w_{1},\dots,w_{N}]\in
P_{N}^{U}$ be an Escher in $U$. Then for any value of the index $m$ (all
indices are understood modulo $N$), we have 3 mutually exclusive
possibilities:

  1. (1)

$w_{m+k}\to w_{m+1}$ and $w_{m}\to w_{m+k+1}$

  2. (2)

$w_{m+k}\succ w_{m+1}$ and $w_{m}\to w_{m+k+1}$

  3. (3)

$w_{m+k}\to w_{m+1}$ and $w_{m}\succ w_{m+k+1}$

###### Proof.

Indeed, the last remaining possibility: $w_{m+k}\succ w_{m+1}$ and $w_{m}\succ
w_{m+k+1}$ would create the impossible sequence (cf. Lemma 3.1):

$w_{m}\rightarrow w_{m+1}\prec w_{m+k}\to w_{m+k+1}\prec w_{m}.$

∎

Note that in cases (1) and (3) the sequence $[w_{m+1},\dots,w_{m+k}]$ is a
$k$-Escher, and in cases (1) and (2), the sequence $[w_{m+k+1},\dots,w_{m}]$
is an $n$-Escher. If case (1) holds, then we will call the sequence
$[w_{m+1},\dots,w_{m+k}]$ a valid $k$-subEscher of $w$.

The statement of this Lemma may be strengthened as follows.

######  Lemma 4.3.

Assume that we are in case (2) of Lemma 4.2, and thus the sequence
$[w_{m+1},w_{m+2},\dots,w_{m+k}]$ is not a $k$-Escher. Then the three
sequences

$\displaystyle[w_{m+k},w_{m+k+1},\dots,w_{m+k+n-1}],$
$\displaystyle[w_{m+k+1},w_{m+k+2},\dots,w_{m+k+n}],$
$\displaystyle[w_{m+k+2},w_{m+k+3},\dots,w_{m+k+n+1}].$

are all $n$-Eschers in $U$.

The proof is analogous to the one given above and will be omitted.

Now assume

$w_{0}\to w_{1}\to\dots\to w_{L-1}\to w_{L}.$

We will call such a sequence pure if for all $0<m\leq L-k$, case (2) or (3) of
Lemma 4.2 hold (i.e. there are no valid $k$-subEschers).

Then Lemma 4.3 has the following important

######  Corollary 4.4.

If $w_{0}\to w_{1}\to\dots\to w_{L-1}\to w_{L}$ is pure than either case (2)
holds for all $0\leq m<L-k$ or case (3) holds for all $0\leq m<L-k$.

In the first case, we will call the sequence pure-, while in the second we
will call it pure+. These arguments have imply the following key statement.

######  Proposition 4.5.

Let $U$ be a UIO, and $w\in P^{U}_{N}$ be an Escher. Then there exists an
index $i$ such that
$[w_{i+1},w_{i+2},\dots,w_{i+k}]$ is a valid $k$-Escher, i.e. that such that
$[w_{i+k+1},w_{i+k+2},\dots,w_{i+k+n}]$ is an Escher as well.

###### Proof.

Indeed, assuming the contrary, we would obtain an cyclic (infinite) length-$N$
pure sequence. If this sequence is pure- , then we obtain an infinite logical
sequence

$w_{0}\prec w_{k-1}\prec w_{2(k-1)}\prec\dots,$

which is clearly impossible. The case of a pure+ sequence is similar. ∎

### 4.3. Insertions

Now we pass to a dual notion. Let $u\in P^{U}_{n}$ and $v\in P^{V}_{k}$. We
have a similar set of statements in this case.

######  Lemma 4.6.

For each index $i\in\mathbb{N}$, we have 3 mutually exclusive possibilities:

  1. (1)

$u_{i}\to v_{i+1}$ and $v_{i}\to u_{i+1}$,

  2. (2)

$u_{i}\succ v_{i+1}$ and $v_{i}\to u_{i+1}$,

  3. (3)

$u_{i}\to v_{i+1}$ and $v_{i}\succ u_{i+1}$.

Moreover, between two subsequent indices of type (1), one has always only
indices of same type, (2) or (3).

###### Proof.

The proof is similar to the one given above and will be omitted. ∎

Let us assume for simplicity that $n$ and $k$ are relatively prime. Then the
pair $(u,v)$ gives rise to a cyclic sequence of $n\cdot k$ pairs in
$P^{U}_{n}\times P^{U}_{k}$, related by simultaneous rotations, all reducing
to the same pair of cyclic Eschers, but identified by their starting points at
$u_{i}$ and $v_{i}$, respectively, $i=0,1,\dots,nk-1$. We will call a pair of
subsequent indices $\kappa=(i,i+1)$ a valid insertion if the case (1) above
holds. Visually, we will think of this as

$\begin{pmatrix}\dots v_{i}\\\ \dots
u_{i}\end{pmatrix}\overset{\kappa}{\times}\begin{pmatrix}u_{i+1}\dots\\\
v_{i+1}\dots\end{pmatrix}$

and write $i<\kappa<i+1$.

## 5\. The proof

We fix a UIO $U$ of $N=n+k$ elements. If this causes no confusion, then we
will omit the index "$U$" from our notation. Following the ideas of [8], we
will prove Theorem 4.1 statement by constructing an explicit injection
$\phi=\phi_{nk}:P^{U}_{n+k}\hookrightarrow P_{n}^{U}\times P_{k}^{U}$.

Again, we will think of an element $w\in P^{U}_{m}$ as a cyclic Escher with a
marked starting point indexed by 0. In particular, all indices are understood
modulo $N=n+k$. One subtlety in our conventions: even though the indices are
arranged cyclically, we will still talk about a smallest index satisfying a
certain condition, starting at some point. This will mean starting from a
point, and then moving forward until we reach the index with the required
property.

The map $\phi:P_{n+k}\to P_{n}\times P_{k}$. Assume for simplicity $n>k$.

Then $\phi$ is defined as follows: let $w\in P^{U}_{n+k}$; define $0\leq L\leq
n+k-1$ to be the smallest index $l$, starting from 0, such that

$[w_{l+1},\dots,w_{l+k}]$

is a valid sub-Escher, i.e. $[w_{l+k+1},\dots,w_{l}]$ is also an Escher. We
will denote this index $L$ by $FE(w)$ sometimes We thus ended up with two,
well-defined cyclic Eschers. All is needed then is to fix their initial
points. We define

  * •

we set initial point of the $k$-Escher as the index $q\in[L+1,L+k]$ such that
$q=0\mod k$, and similarly,

  * •

we set initial point of the $n$-Escher as the index $q\in[L+k+1,L]$ such that
$q=0\mod n$.

######  Remark 5.1.

Even though we have this uniform definition, there two distinct situations:

  1. (1)

The ordinary case: $0\notin[L+1,L+k]$.

  2. (2)

The exceptional case : $0\in[L+1,L+k]$.

The "inverse map" $\psi:P_{n}\times P_{k}\to P_{n+k}$. Let us take $v$ and
$u$, a $k$\- and $n$-Escher, respectively. Let $L$ be the smallest integer
$0\leq l$ such that there is a valid insertion after $l$, i.e. $v_{l}\to
u_{l+1}$ and $u_{l}\to v_{l+1}$ (if there is no such $l$, then we define the
map in an arbitrary fashion). We will denote this index $L$ of first valid
insertion by $FI(u,v)$ sometimes. This gives us immediately a cyclic
$n+k$-Escher, and we just need pick a initial point.

  1. (1)

The ordinary case: $L<n$. Then we take $u_{0}$ to be the initial point.

  2. (2)

The exceptional case: $L\geq n$. Then we take $v_{n}$ to be the initial point.

The following theorem is a refinement of Theorem 4.1, and immediately implies
the chromatic conjecture for partitions of length 2.

######  Theorem 5.2.

$\psi\circ\phi\text{ is the identity}$

Let us start with the ordinary case: $w\in P_{n+k}$ and assume that the first
$k$-Escher occurs at $FE(w)=L<n$. It is clear that the pair $\phi(w)=(u,v)$
has a valid insertion right after the index $L$, in principle, recovering $w$.
The danger is, however, that if $FI(u,v)<L$, i.e. there are other valid
insertions of the pair $(u,v)$ before the index $L$, then the map $\psi$ will
not take $\phi(w)$ back to $w$. We thus need to show that $FI(\phi(w))\geq
FE(w)$. This is, essentially the content of the following statement:

######  Proposition 5.3.

Let $\kappa_{1}$ and $\kappa_{2}$ be two consecutive valid insertions of the
pair $(u,v)$:

$j<\kappa_{1}<j+1,\dots,j+r<\kappa_{2}<j+r+1,\dots,\quad r\leq n$

Then the sequence

$u_{j}\to u_{j+1}\to\dots\to u_{j+r}\to v_{j+r+1}\to\dots\to v_{j+r+k}$

is not pure, i.e. has a valid $k$-subEscher.

###### Proof.

For the purposes of the proof, we can set $j=0$, as $j$ simply introduces a
global shift in the arguments. Assume thus, ad absurdum that

$u_{0}\to u_{1}\to\dots\to u_{r}\to v_{r+1}\to\dots\to v_{r+k}$

is pure.

Let us first consider the case when this sequence is pure- . Then by
definition of these pure- sequences, we have

$u_{1}\prec u_{k}\prec\dots\prec u_{(q-1)(k-1)+1}\prec v_{q(k-1)+1}\to
v_{q(k-1)+2}\to\dots\to v_{qk}=v_{0}\to u_{1},$

which is an impossible sequence, because it has $q$ $\prec$ and $q$ $\to$
symbols. If the sequence is pure+ , then, on the other hand, by definition,

$u_{0}\succ u_{k+1}\leftarrow u_{k}\succ\dots\leftarrow u_{(q-1)k}\succ
v_{qk+1}=v_{1}\leftarrow u_{0},$

which is again an impossible sequence with $q$ $\prec$ and $q$ $\to$ symbols.

∎

We have thus shown that $\psi\circ\phi(w)=w$ when $FE(w)=L<n$.

The exceptional case is similar, but requires a little more care. Again, it is
easy to see, that given an exceptional $w\in P_{n+k}^{W}$, the pair
$(u,v)=\phi(w)$ has a valid insertion at $L=FE(w)\geq n$, and the following
statement will suffice.

######  Proposition 5.4.

Let $\kappa_{1}$ and $\kappa_{2}$ be two consecutive valid insertions of the
pair $(u,v)$:

$0<\kappa_{1}<1,\dots,L<\kappa_{2}<L+1,\dots,\quad\text{ where }L\geq n.$

Then the sequence

$v_{n}\to v_{n+1}\to\dots\to v_{L}\to u_{L-n+1}\to\dots\to u_{L}\to
v_{L+1}\to\dots\to v_{L+k}$

is not pure, i.e. has a valid $k$-subEscher.

Note that we have set the starting index $j=0$, as in the proof of the case
above.

###### Proof.

Assuming the sequence is pure- and $L>n$, we obtain the following sequence:

$v_{n+1}\prec u_{k}\prec\dots\prec u_{(q-1)(k-1)+1}\prec
v_{q(k-1)+1}\to\dots{\\\ }\dots\to v_{qk}=v_{0}\to u_{1}=u_{n+1}\prec
v_{n+k}=v_{n}\to v_{n+1},$

which has with $q+1$ $\prec$ and $q+1$ $\to$ symbols. When $L=n$, the sequence
degenerates to the one used in the proof of Proposition 5.3.

Assuming the sequence is pure+ , leads to the impossible sequence

$v_{n}\succ u_{k+1}\leftarrow u_{k}\succ\dots\leftarrow u_{(q-1)k}\succ
v_{qk+1}=v_{1}\leftarrow u_{0}\succ v_{n+k+1}\leftarrow v_{n},$

and this completes the proof. ∎

## References

  * [1] A. Abreu, A. Nigro, _Splitting the cohomology of Hessenberg varieties and e-positivity of chromatic symmetric functions_ , arXiv:2304.10644.
  * [2] T. Chow, _A Note on a Combinatorial Interpretation of the e-Coefficients of the Chromatic Symmetric Function_ , arXiv:math.co/9712230v2 (1995).
  * [3] V. Gasharov, _Incomparability Graphs of (3+1)-free posets are s-positive_ , Discrete Mathematics (1995), 157, 193-197.
  * [4] M. Guay-Paquet, _A modular relation for the chromatic symmetric functions of (3+1)-free posets_ , arXiv:math.co/1306.2400 (2013).
  * [5] D. Scott, P. Suppes _Foundational aspects of theories of measurement_ , Journal of Symbolic Logic (1954), 23, 113–128.
  * [6] A. Paunov _Positivity for Stanley’s chromatic functions_ , Genève University, (2016), available from: http://archive-ouverte.unige.ch/unige:87600
  * [7] A. Paunov _Planar graphs and Stanley’s Chromatic Functions_ , preprint, (2016), arXiv:1702.05787
  * [8] A. Paunov, A. Szenes, _A new approach to e-positivity for Stanley’s chromatic functions_ , arXiv:1702.05791
  * [9] I. Siegl, _Cylindric P-Tableaux for (3+1)-Free Posets_ , arXiv:2211.03953
  * [10] R. Stanley, _A Symmetric Function Generalization of the Chromatic Polynomial of a Graph_ , Advances in Mathematics (1995), 111, 166–194.
  * [11] R. Stanley, _Graph colorings and related symmetric functions: Ideas and Applications_ , MIT (1995).