# Rainbow numbers of $[n]$ for $\sum_{i=1}^{k-1}x_{i}=x_{k}$.

Kean Fallon  Department of Mathematics and Statistics, University of
Wisconsin-La Crosse<EMAIL_ADDRESS>Colin
Giles  Department of Mathematics, Iowa State University<EMAIL_ADDRESS>Hunter Rehm  Department of Mathematics and Statistics, University of Vermont,
<EMAIL_ADDRESS>Simon Wagner  Department of Mathematics and Statistics,
University of Wisconsin-La Crosse,
<EMAIL_ADDRESS>Nathan Warnberg  Department of
Mathematics and Statistics, University of Wisconsin-La Crosse,
<EMAIL_ADDRESS>
(March 19, 2020)

## Abstract

Consider the set $\\{1,2,\dots,n\\}=[n]$ and an equation $eq$. The rainbow
number of $[n]$ for $eq$, denoted $\operatorname{rb}([n],eq)$, is the smallest
number of colors such that for every exact
$\operatorname{rb}([n],eq)$-coloring of $[n]$, there exists a solution to $eq$
with every member of the solution set assigned a distinct color. This paper
focuses on linear equations and, in particular, establishes the rainbow number
for the equations $\sum_{i=1}^{k-1}x_{i}=x_{k}$ for $k=3$ and $k=4$. The paper
also establishes a general lower bound for $k\geq 5$.
Keywords: anti-Ramsey, rainbow, Schur

##  1 Introduction

Let $\\{1,2,\dots,n\\}=[n]$ and $eq$ be any equation. The rainbow number of
$[n]$ for $eq$, denoted $\operatorname{rb}([n],eq)$, is the smallest number of
colors such that for every exact $\operatorname{rb}([n],eq)$-coloring of
$[n]$, there exists a solution to $eq$ with every member of the solution set
assigned a distinct color. Although much of the literature has focused on
linear equations, as does this paper, this definition is general enough to
define rainbow numbers for any set and any equation. The rainbow number is an
anti-Ramsey type function since the key structures are multichromatic (or
rainbow) as opposed to monochromatic. The rainbow number function was inspired
by Schur numbers (see [6] and references therein, the authors originally
thought of the rainbow number as the anti-Schur number) and the anti-van der
Waerden function. The anti-van der Waerden number on $[n]=\\{1,\dots,n\\}$,
denoted $\operatorname{aw}([n],k)$, is the smallest number of colors such that
every exact $\operatorname{aw}([n],k)$-coloring of $[n]$ is guaranteed to have
an arithmetic progression of length $k$ where each element of the progression
is colored distinctly (note that $3$ term arithmetic progressions satisfy the
equation $x_{1}+x_{2}=2x_{3}$). The anti-van der Waerden number was first
defined in [11] and many results on arithmetic progressions on $[n]$, the
cyclic groups $\mathbb{Z}_{n}$, finite abelian groups and graphs have been
considered directly or indirectly (see [1, 2, 3, 5, 8, 10, 12]). Rainbow
results have also been considered for equations of the form
$a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}=b$ over $\mathbb{Z}_{p}$ (see [4, 7, 9]).

An _exact $r$-coloring_ $c$ of the integers $\\{1,2,\dots,n\\}=[n]$, is a
function $c:[n]\rightarrow[r]$ such that $c$ is onto. If $eq$ is any linear
equation on $k$ variables, namely $x_{1},x_{2},\dots,x_{k}$, and non-zero
coefficients, then the set $\\{s_{1},s_{2},\dots,s_{k}\\}$ is a _rainbow
solution_ if substituting $s_{i}=x_{i}$ makes $eq$ true and
$|\\{c(s_{1}),c(s_{2}),\dots,c(s_{k})\\}|=k$. Note that if a solution does not
have distinct elements it cannot be a rainbow solution and such solutions will
be called _degenerate_ , i.e. the only solutions that will be considered are
_non-degenerate_.

The _rainbow number_ of $[n]$ for equation $eq$, denoted
$\operatorname{rb}([n],eq)$, is the smallest $r$ such that every exact
$r$-coloring of $[n]$ is guaranteed to have a rainbow solution to $eq$. A
coloring is _extremal_ , with respect to $eq$ and $[n]$, if it uses
$\operatorname{rb}([n],eq)-1$ colors and avoids rainbow solutions. As a
technical note, if $eq$ has $m$ variables and $m>n$ or there are no solution
sets to $eq$ in $[n]$, define $\operatorname{rb}([n],eq)=n+1$.

Some more notation and a convention about the way $[n]$ is colored are now
introduced. Let $c$ be an exact $r$-coloring on $[n]$. Define
$\mathcal{C}_{i}=\\{a\in[n]\,|\,c(a)=i\\}$ and define
$s_{i}\in\mathcal{C}_{i}$ such that $s_{i}$ is the smallest element of
$\mathcal{C}_{i}$ for each color $i$. Note that for any exact $r$-coloring
$c$, it is always possible to have $s_{i}<s_{j}$ for $i<j$. If that is not the
case, say $s_{i}>s_{j}$ and $i<j$, an isomorphic coloring can be created by
swapping the color of any number with color $i$ to have color $j$ and vice
versa.

Observation 1.1 follows directly from the definition of rainbow numbers and
describes the strategy used throughout the paper to find
$\operatorname{rb}([n],eq)$.

######  Observation 1.1.

If $c$ is an exact $(r-1)$-coloring of $[n]$ that avoids rainbow solutions for
$eq$, then $r\leq\operatorname{rb}([n],eq)$. If every exact $r$-coloring of
$[n]$ guarantees a rainbow solution to $eq$, then
$\operatorname{rb}([n],eq)\leq r$.

######  Example 1.2.

Consider the equation $eq:x_{1}+x_{2}=x_{3}$ over $[5]$. Define $c:[5]\to[3]$
by $c(1)=1$, $c(2)=2$, $c(3)=1$, $c(4)=3$ and $c(5)=1$. Since this is an exact
$3$-coloring that avoids rainbow solutions to $eq$, Observation 1.1 gives
$4\leq\operatorname{rb}([5],eq)$. On the other hand, any exact $4$-coloring of
$[5]$ must either use $4$ distinct colors in $\\{1,2,3,4\\}$ or
$\\{2,3,4,5\\}$. In the former case $\\{1,2,3\\}$ is a rainbow solution, and
in the latter case $\\{2,3,5\\}$ is a rainbow solution. Thus
$\operatorname{rb}([5],eq)\leq 4$.

##  2 The rainbow number of $[n]$ for the equation $x_{1}+x_{2}=x_{3}$

This section focuses on the rainbow number for the equation
$x_{1}+x_{2}=x_{3}$ so for the rest of the section it is assumed that $eq$ is
$x_{1}+x_{2}=x_{3}$. Also, when $\\{a,b,c\\}$ is presented as a solution to
$eq$ it will be recognized that $x_{1}=a$, $x_{2}=b$ and $x_{3}=c$. In order
to discuss the results in this section it is easier if an exact $r$-coloring
uses the color set $\\{0,1,\dots,r-1\\}$. Lemma 2.1 starts with a specific
coloring that avoids rainbow solutions.

######  Lemma 2.1.

For $n\geq 3$,
$\left\lfloor\log_{2}(n)+2\right\rfloor\leq\operatorname{rb}([n],eq)$.

###### Proof.

The number of trailing zeros that an integer has is the number of zeros,
starting from the right, before there is a nonzero digit. Define an exact
$(\left\lfloor\log_{2}(n)+1\right\rfloor)$-coloring of $[n]$ as

$c(x)=\text{the number of trailing zeros in the binary representation of $x$}$

(see Example 2.2). Let $a,b\in[n]$. If $a$ and $b$ are odd, then $c(a)=c(b)=0$
since their binary representation ends with a $1$. This means $\\{a,b,a+b\\}$
is not a rainbow solution. If $a$ is odd and $b$ is even, then $a+b$ is odd so
$c(a)=c(a+b)=0$, thus $\\{a,b,a+b\\}$ is not a rainbow solution. Finally,
consider the case where $a$ and $b$ are both even. If $a$ and $b$ have the
same number of trailing zeros, then $c(a)=c(b)$ meaning $\\{a,b,a+b\\}$ is not
a rainbow solution. If $c(a)\neq c(b)$ assume, without loss of generality,
that $c(a)<c(b)$. Since the number of trailing zeros of $b$ exceeds the number
of trailing zeros of $a$, it follows, via binary arithmetic, that $b+a$ has
the same number of trailing zeros as $a$. Thus, $c(a+b)=c(a)$ and
$\\{a,b,a+b\\}$ is not a rainbow solution. Therefore, no rainbow solutions
exist with this coloring, and
$\left\lfloor\log_{2}(n)+2\right\rfloor\leq\operatorname{rb}([n],eq)$.∎

######  Example 2.2.

A table describing the coloring from Lemma 2.1.

$\begin{array}[]{|c|c|c|}\hline\cr x&x\text{ in binary}&c(x)\\\ \hline\cr
1&1&0\\\ \hline\cr 2&10&1\\\ \hline\cr 3&11&0\\\ \hline\cr 4&100&2\\\
\hline\cr 5&101&0\\\ \hline\cr 6&110&1\\\ \hline\cr 7&111&0\\\ \hline\cr
8&1000&3\\\ \hline\cr\end{array}$

Lemma 2.3 indicates that when attempting to color $[n]$ and avoid rainbow
solutions, there are restrictions on how quickly new colors can be added.

######  Lemma 2.3.

Let $c$ be an exact $r$-coloring of $[n]$, with color set
$\\{0,1,\dots,r-1\\}$, that avoids rainbow solutions, then

  1. 1.

if $s_{i}=\ell$, then $2\ell\leq s_{i+1}$ for $0\leq i\leq r-2$,

  2. 2.

$2^{i}\leq s_{i}$ for $0\leq i\leq r-1$.

###### Proof.

For the first claim, if $\ell=1$, then $i=0$, so the smallest $m$ for which
$s_{2}=m$ is $m=2$. If $\ell\geq 2$, let $1\leq a<\ell$ with $a+\ell\leq n$.
Then $c(a)\neq c(\ell)$, so $c(a+\ell)\in\\{c(a),c(\ell)\\}$. Thus,
$c(a+\ell)\neq i+1$, hence $2\ell\leq s_{i+1}$.

Proving the second claim proceeds by induction on $k$. The base case is easily
observed, in particular, $s_{0}=1=2^{0}$. For the induction hypothesis, assume
$2^{k}\leq s_{k}$ for $0\leq k\leq r-2$. Applying part 1 to our induction
hypothesis yields $2(2^{k})=2^{k+1}\leq s_{k+1}$ which completes the proof.∎

Theorem 2.4 follows almost directly from Lemmas 2.1 and 2.3.

######  Theorem 2.4.

For $n\geq 3$,
$\operatorname{rb}([n],eq)=\left\lfloor\log_{2}(n)+2\right\rfloor$.

###### Proof.

By Lemma 2.1
$\left\lfloor\log_{2}(n)+2\right\rfloor\leq\operatorname{rb}([n],3)$. Let
$r=\left\lfloor\log_{2}(n)+2\right\rfloor$ and $c$ be an exact $r$-coloring,
with color set $\\{0,1,\dots,r-1\\}$, of $[n]$ that avoids rainbow solutions.
Then, by Lemma 2.3, $2^{r-1}\leq s_{r-1}$, so

$2^{r-1}=2^{\left\lfloor\log_{2}(n)+1\right\rfloor}\leq s_{r-1}.$

Thus, $n<s_{r-1}$. So if color $r-1$ appears in a coloring of $[n]$ there must
be a rainbow solution, a contradiction that such a coloring exists. Therefore,
$\operatorname{rb}([n],eq)=\left\lfloor\log_{2}(n)+2\right\rfloor$.∎

##  3 The rainbow number of $[n]$ for the equation $x_{1}+x_{2}+x_{3}=x_{4}$

This section defines $eq:x_{1}+x_{2}+x_{3}=x_{4}$ (except in Theorem 3.2) and
an exact $r$-coloring will use color set $[r]$. Lemma 3.1 is used to define a
coloring on $[n]$ that avoids rainbow solutions which gives a lower bound on
$\operatorname{rb}([n],eq)$. It is interesting to note that the equations in
Section 2 and 3 are similar but one result is logarithmic and the other is
linear.

######  Lemma 3.1.

For $\ell\geq 2$, let {$b_{1},b_{2}\ldots,b_{\ell}\\}\subseteq[n]$, with
$b_{i}<b_{i+1}$ for $1\leq i\leq\ell-1$, such that
$\sum\limits_{i=1}^{\ell}b_{i}\geq n$. The smallest $b_{\ell}$ that satisfies
these conditions gives a corresponding maximum $b_{1}$ value of

$b_{1}=\left\lceil\frac{2n-\ell(\ell-1)}{2\ell}\right\rceil.$

###### Proof.

Notice that by first minimizing $b_{\ell}$ and then maximizing $b_{1}$ gives
$b_{i+1}=b_{i}+1$, for $1\leq i\leq\ell-1$, and $b_{\ell}=b_{1}+\ell-1$.
Observe,

$\sum\limits_{i=1}^{\ell}b_{i}\geq n.$

Well-known facts about triangular numbers gives the equivalent inequality

$\frac{b_{\ell}(b_{\ell}+1)}{2}-\frac{(b_{1}-1)b_{1}}{2}\geq n,$

and solving for $b_{1}$ yields

$b_{1}\geq\frac{2n-\ell(\ell-1)}{2\ell}.$

Since $b_{1}$ is an integer, and the $b_{i}$’s are consecutive, it can be
concluded that

$b_{1}=\left\lceil\frac{2n-\ell(\ell-1)}{2\ell}\right\rceil.$

∎

######  Theorem 3.2.

Let $eq:\sum_{i=1}^{k-1}x_{i}=x_{k}$, $k\geq 4$ and define
$L=\left\lceil\frac{2n-\ell(\ell-1)}{2\ell}\right\rceil$ for $\ell=k-2$. Then

$\operatorname{rb}([n],eq)\geq\left\\{\begin{array}[]{ll}n+1&\text{if
}n<\frac{(k-1)k}{2},\\\ n-L+3&\text{otherwise.}\par\end{array}\right.$

###### Proof.

The lower bound of $n+1$ (which is actually an equality) occurs when $[n]$
does not have any solutions to $eq$ and is based on
$\sum_{i=1}^{k-1}i=\dfrac{(k-1)k}{2}$. Hence every integer in $[n]$ can be
colored distinctly and $\operatorname{rb}([n],eq)=n+1$ by definition. If $[n]$
does have solutions to $eq$, then consider the coloring $c$ on $[n]$ where

$c(x)=\left\\{\begin{array}[]{cc}1&\text{ if $1\leq x\leq L-1$,}\\\ i+2&\text{
if $x=L+i$.}\\\ \end{array}\right.$

This coloring avoids rainbow solutions since any rainbow solution must have at
least $k-1$ elements that are bigger than $L$ and Lemma 3.1 indicates that the
sum of these elements is greater than $n$. Thus, no rainbow solutions exist.

It remains to count how many colors are used. The number of elements that are
not colored $1$ is $n-L+1$, thus $c$ uses $n-L+2$ colors. Since $c$ avoids
rainbow solutions, this gives $n-L+3\leq\operatorname{rb}([n],eq)$. ∎

######  Corollary 3.3.

For $n\geq 5$,
$\left\lfloor\dfrac{1}{2}(n+7)\right\rfloor\leq\operatorname{rb}([n],eq)$.

###### Proof.

As noted in the introduction to Section 3, $eq$ in this problem has $k=4$ and
$\ell=2$, thus so $L=\left\lceil\frac{n-1}{2}\right\rceil$. Applying Theorem
3.2 gives the result. ∎

######  Proposition 3.4.

If $n$ is odd and $n\geq 5$, then
$\operatorname{rb}([n],eq)=\dfrac{1}{2}(n+7)$ and there is a unique extremal
coloring of $[n]$.

###### Proof.

When $n=5$ the result is immediate. When $n=7$ the lower bound is a result of
Corollary 3.3. The upper bound is trivial since the only coloring of $[7]$
with seven colors is to color each number distinctly. If $c^{\prime}$ is an
extremal coloring of $[7]$, then $6$ colors are used. Since $\\{1,2,3,6\\}$
and $\\{1,2,4,7\\}$ are both solutions, $c^{\prime}(1)=c^{\prime}(2)$ and the
coloring is unique.

For the induction hypothesis, assume that for all odd $k$ with $7\leq k\leq
n$, $n$ odd, that $\operatorname{rb}([k],eq)=\dfrac{1}{2}(k+7)$ and there is a
unique extremal coloring of $[k]$, namely the coloring provided in Theorem
3.2. Define $r=\dfrac{1}{2}((n+2)+7)$, $L=\dfrac{n-1}{2}$ and let $c$ be an
exact $r$-coloring of $[n+2]$ with color set $\\{1,\dots,r\\}$. The induction
hypothesis implies that if $r$ or $r-1$ colors appear in $[n]$, then there is
a rainbow solution, so $s_{r}=n+2$ and $s_{r-1}=n+1$. The induction hypothesis
also implies that if $r-2$ colors appear in $[n]$, there is a unique coloring
of $[n]$ with $r-2$ colors that avoids rainbow solutions. However, applying
the unique coloring yields $c(1)=1$, $c(L)=2$, $c(L+1)=3$ and $c(n+1)=r-1>3$,
thus $\\{1,L,L+1,n+1\\}$ is a rainbow solution. Therefore,
$\operatorname{rb}([n+2],eq)\leq\dfrac{1}{2}(n+9)$. Equality comes from the
lower bound in Corollary 3.3.

Now let $c$ be an exact $(r-1)$-coloring of $[n+2]$, with color set
$\\{1,2,\dots,r-1\\}$, that avoids rainbow solutions. If $r-1$ colors appear
in $[n]$ the inductive hypothesis implies there is a rainbow solution, thus
$n+1\leq s_{r-1}\leq n+2$.

If $r-2$ colors appear in $[n]$, then $[n]$ has the coloring from Theorem 3.2.
This means $s_{2}=L$ and $s_{3}=L+1$. Hence, either $\\{1,L,L+1,n+1\\}$ or
$\\{2,L,L+1,n+2\\}$ is a rainbow solution since $n+1\leq s_{r-1}\leq n+2$.
Therefore, $n<s_{r-2}$ which implies $s_{r-2}=n+1$ and $s_{r-1}=n+2$.

Now consider the case where $r-3$ colors appear in $[n]$. If $r-j-1$ colors
appear in $[n-2j+2]$, for $2\leq j\leq\dfrac{n+3}{4}$, then the coloring from
Theorem 3.2 gives $L_{j}=\dfrac{n-2j+2-1}{2}=L-j+1=s_{2}$, $L-j+2=s_{3}$,
$\dots$ ,$n-2j+2=s_{r-j-1}$. However, notice that

$L-j+1\leq L<L+1\leq n-2j+2<n+1,$

thus $\\{1,L,L+1,n+1\\}$ is a rainbow solution which implies $n-2j+3\leq
s_{r-j-1}$.

Combining this with $s_{i}<s_{i+1}$ gives

$n-2j+3\leq s_{r-j-1}\leq n-j+2.$ (*)

Note that Inequality (* ‣ 3) gives $s_{2}=s_{r-(r-3)-1}\leq n-(r-3)+2=L+1$.
The remainder of the proof will show that if $s_{2}\neq L+1$, then there is a
rainbow solution. This then implies that $s_{2}=L+1$ and $c$ must be the
coloring from Theorem 3.2.

Set $[n+2]=\\{1\\}\cup A\cup B\cup\\{n-1,n,n+1,n+2\\}$ with
$A=\\{2,3,\dots,L\\}$ and $B=\\{L+1,L+2,\dots,n-2\\}$. Note that
$|A|=|B|=L-1=\dfrac{n-3}{2}$ and that $s_{2}\in A$. Also, for any $x\in A$,
the set $\\{1,x,n-x,n+1\\}$ is a solution to $eq$ and $c(1)=1\neq r-2=c(n+1)$.
This implies that each element of the pair $\\{x,n-x\\}$ is either the same
color or at least one of them is color $1$. Further, since $x\in A$ and
$n-x\in B$, $|c(A\cup B)|$ uses at most $L-1$ of the remaining
$|\\{2,3,\dots,r-3\\}|=r-4=L+1$ colors. This forces $c(n-2)=r-4$, $c(n-1)=r-3$
and each pair $\\{x,n-x\\}$ contributing one color from $\\{2,3,\dots,r-5\\}$
that is not accounted for among any other $\\{y,n-y\\}$ pair for $y\in A$.
However, now $\\{1,s_{2},n-s_{2}+1,n+2\\}$ is a rainbow solution. To see this,
observe that $c(s_{2}-1)=1$ and if $c(n-s_{2}+1)=2$, then the
$\\{s_{2}-1,n-s_{2}+1\\}$ pair contributes the color $2$ so the
$\\{s_{2},n-s_{2}\\}$ pair must contribute a color that is not $2$. This means
$c(n-s_{2})\neq 2$ which makes $\\{1,s_{2},n-s_{2},n+1\\}$ a rainbow solution.
∎

######  Lemma 3.5.

If $n\geq 5$ is odd, then $\operatorname{rb}([n+1],eq)\leq\dfrac{1}{2}(n+7)$.

###### Proof.

Let $r=\dfrac{1}{2}(n+7)$ and $c$ be an exact $r$-coloring of $[n+1]$. If $r$
colors appear in $[n]$, then, by Proposition 3.6, there exists a rainbow
solution. Thus $c(n+1)=r$ and $r-1$ colors appear in $[n]$. Note that there is
unique extremal coloring of $[n]$ with $r-1$ colors, thus
$\left\\{1,\dfrac{n-1}{2},\dfrac{n+1}{2},n+1\right\\}$ is a rainbow solution
since $c(1)=1$, $c((n-1)/2)=2$, $c((n+1)/2)=3$ and $c(n+1)=r$. Therefore,
$\operatorname{rb}([n+1],eq)\leq\dfrac{1}{2}(n+7)$.∎

Theorem 3.6 follows Proposition 3.4 and Lemma 3.5.

######  Theorem 3.6.

For $n\geq 5$,
$\operatorname{rb}([n],eq)=\left\lfloor\dfrac{1}{2}(n+7)\right\rfloor$.

##  4 Conclusion

It is believed that future work on equations of the form
$\sum_{i=1}^{k-1}x_{i}=x_{k}$, $k\geq 5$ should focus on the coloring
exhibited in Theorem 3.2 and arguments should utilize $s_{i}$. Data indicates
that there are unique colorings, when $k=5$, for $n=9,12,15,\dots$ and
colorings for other values of $n$ are closely related to the unique colorings.
Other questions to consider are more general equations like
$\displaystyle\sum_{i=1}^{k}a_{i}x_{k}=b$. It is not clear which, if any,
techniques from this paper will be applicable in the more general situation.

## Acknowledgements

Thank you to the referees for the helpful comments that have improved the
paper, in particular for the simplification of the proof of Proposition 3.4.
Thanks also to the University of Wisconsin-La Crosses’s Undergraduate Research
and Creativity grants which helped support this research.

## References

  * [1] M. Axenovich and D. Fon-Der-Flaass, On rainbow arithmetic progressions, _Electron. J. Combin._ 11 (2004), no. 1, Research Paper 1, 7pp.
  * [2] Z. Berikkyzy, A. Schulte, E. Sprangel, S. Walker, N. Warnberg and M. Young, Anti-van der Waerden numbers on Graphs, Submitted to _Discrete Math._ , https://arxiv.org/pdf/1802.01509.pdf.
  * [3] Z. Berikkyzy, A. Schulte, and M. Young, Anti-van der Waerden numbers of 3-term arithmetic progressions, _Electron. J. Combin._ 24 (2017), no. 2, Paper 2.39, 9 pp.
  * [4] E. Bevilacqua, A. King, J. Kritschgau, M. Tait, S. Tebon and M. Young, Rainbow numbers for $x_{1}+x_{2}=kx_{3}$ in $\mathbb{Z}_{n}$, https://arxiv.org/abs/1809.04576.
  * [5] S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R.L. Kramer, J. Lin, R.R. Martin, D. Stolee, N. Warnberg and M. Young, Rainbow Arithmetic Progressions, _J. Comb._ 7 (2016), no. 4, 595–626.
  * [6] Marijn J. H. Heule, Schur Number Five, _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence_ (2018), 6598–6606, https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16952.
  * [7] M. Huicochea and A. Montejano, The Structure of Rainbow-Free Colorings For Linear Equations on Three Variables in $\mathbb{Z}_{p}$, _Integers_ 15A (2015), A8.
  * [8] V. Jungić, J. Licht (Fox), M. Mahdian, J. Nes̆etril, and R. Radoic̆ić, Rainbow arithmetic progressions and anti-Ramsey results, _Combinatorics, Probability and Computing_ 12 (2003), no 5-6, 599–620.
  * [9] B. Llano and A. Montejano, Rainbow-free Colorings of $x+y=cz$ in $\mathbb{Z}_{p}$, _Discrete Math._ 312, (2012), 2566–2573.
  * [10] H. Rehm, A. Schulte and N. Warnberg, Anti-van der Waerden numbers on Graph Products, _Austral. J. Combin._ 73(3) (2019), 486–500.
  * [11] K. Uherka, An introduction to Ramsey theory and anti-Ramsey theory on the integers, Master’s Creative Component (2013), Iowa State University.
  * [12] M. Young. Rainbow Arithmetic Progressions in Finite Abelian Groups, _J. Comb._ 9(4) (2018), 619–629..


# GRelPose: Generalizable End-to-End Relative Camera Pose Regression

Fadi Khatib Yuval Margalit11footnotemark: 1 Meirav Galun Ronen Basri
Weizmann Institute of Science, Rehovot, Israel
Project webpage: https://fadikhateeb.github.io/GRelPose Equal contribution.

###### Abstract

This paper proposes a generalizable, end-to-end deep learning-based method for
relative pose regression between two images. Given two images of the same
scene captured from different viewpoints, our algorithm predicts the relative
rotation and translation between the two respective cameras. Despite recent
progress in the field, current deep-based methods exhibit only limited
generalization to scenes not seen in training. Our approach introduces a
network architecture that extracts a grid of coarse features for each input
image using the pre-trained LoFTR network. It subsequently relates
corresponding features in the two images, and finally uses a convolutional
network to recover the relative rotation and translation between the
respective cameras. Our experiments indicate that the proposed architecture
can generalize to novel scenes, obtaining higher accuracy than existing deep-
learning-based methods in various settings and datasets, in particular with
limited training data.

##  1 Introduction

Computing the relative pose (position and orientation) between two cameras
given an image pair is a fundamental computer vision task and an essential
step in multiview structure from motion (SfM) pipelines [32, 43, 42, 51, 52],
with applications to autonomous robot navigation and to virtual and augmented
reality. Classical techniques rely on keypoint extraction and matching using
descriptors such as SIFT [29, 6, 40, 11, 39], followed by robust estimation of
the essential matrix using, e.g., RANSAC [18]. These methods can recover the
relative pose very accurately. However, (1) they only recover five out of the
six degrees of freedom of the relative pose; the distance between the two
camera positions cannot be recovered from point correspondences; (2) they can
be slow due to an exhaustive search of most consistent relative pose model by
RANSAC, and (3) they may fail when the scene includes repetitive structures or
when there are lighting differences.

To overcome these drawbacks, a number of recent papers have explored the use
of deep neural networks for relative pose regression (RPR), see discussion in
Section 2. These new methods use appearance and pose priors to guide the
matching of point features and to select the likely relative pose given an
input image pair. For instance, deep methods are capable of recovering the
distance between two cameras by exploiting priors on the size of the observed
objects. Nevertheless, current deep methods are not as accurate as the
classical approach in many settings, and moreover, they mostly generalize to
new image pairs only within the same scenes used for training.

Inspired partially by the classical techniques, we propose here a new,
generalizable deep architecture for relative pose estimation. Our architecture
includes three modules, a dense feature description module based on a
pretrained LoFTR architecture [44], a matching and warping module, and a pose
regressor. LoFTR is a powerful local feature matching architecture based on
interleaved self- and cross-attention modules that has been shown to
generalize across scenes and even across different datasets. Here we use LoFTR
to produce a semi-dense feature embedding of the two input images. Given these
descriptors and an encoding of the associated image coordinates, our second
module selects and warps the likely point matches. Finally, the pose regressor
uses these warped matches to output the full six degrees of freedom depicting
the relative position and orientation of the two cameras. We test our method
on various datasets and show that it achieves superior performance to
existing, deep-based methods on challenging image pairs, including ones that
depict novel scenes and even unseen datasets, in particular with limited
training data.

##  2 Related Work

The pose between two images with known intrinsic parameters can be recovered
by decomposing the essential matrix [20]. This yields the relative rotation
and a scaleless translation vector. The essential matrix is classically
estimated by matching local features, such as [29, 6, 40, 11, 39], followed by
a numerical scheme, e.g., the 5-point solver [31] inside robust estimator
loop, namely RANSAC [18] and others [4, 5, 34]. Despite the success of this
classical approach, it lacks the ability to utilize priors, for example, to
infer the unknown distance between the two cameras. These shortcomings have
led to the introduction of deep-based approaches, which we review next.

Deep feature extraction and matching. Several studies have utilized deep
networks to detect and match point features in image pairs [36, 16, 7, 41, 48,
53, 46, 45, 47, 44, 23]. Among these, LIFT [53] is an early approach that
additionally assigns an orientation to each feature. Superglue [41] uses a
Graph Neural Network (GNN) to match two sets of interest points; for example,
on top of SuperPoint[14] keypoints and descriptors. A line of works utilizes a
neural network for constructing a differentiable matching module (suggesting
also matching confidence) [46, 45, 47]. The recently proposed works LoFTR [44]
and COTR [23] utilize self- and cross-attention layers and multiscale analysis
to produce semi-dense, near pixel-wise correspondences. Relative pose is then
obtained by applying RANSAC to the extracted correspondences. Those methods
were shown to produce accurate correspondences even in low-texture areas,
demonstrating good generalization ability across scenes and datasets. Still,
those methods are not end-to-end approaches, and the relative position is
recovered up to a scale factor.

Deep RANSAC. Recent works sought to construct a deep network architecture that
can robustly estimate the essential matrix from point matches. Specifically,
DSAC [8] replaces RANSAC’s hypothesis selection with a robust average of
hypotheses, resulting in a differentiable counterpart of RANSAC. [12] utilizes
convolutions in high dimension to recover the essential matrix robustly. [35,
9, 10] propose a deep-based scheme to distinguish between inliers and
outliers, given putative correspondences, for tasks such as fundamental matrix
estimation and camera re-localization.

End-to-end relative pose regression (RPR). A stream of deep learning methods
attempts to predict the relative pose directly from two input images,
circumventing the need to detect 2D putative matches explicitly. Early works
[30, 27] used ResNet34 pre-trained for classification on the Imagenet dataset
to produce holistic feature vectors that describe the two input images. An MLP
module was then applied to these feature vectors to regress the relative
position, with its magnitude, as well as the relative orientation. Subsequent
works [1, 55, 50, 17, 3] utilized a similar approach using modified loss
functions and architectures. All of these methods have a limited cross-scene
generalization ability.

More recently, [38] advocated the use of Vision Transformer (ViT) feature maps
[15, 49] for relative pose regression. They further incorporated quadratic
positional encoding to produce an architecture that mimics the Eight-Point
Algorithm for essential matrix recovery [21]. Lastly, Map-free [2] used a
residual UNet (ResUNet) architecture to produce a feature map for each image.
A soft feature matching was obtained by computing a 4D correlation volume
followed by softmax. This soft matching was then used to warp the features of
one image into their corresponding locations in the other image. A regression
module was finally used to estimate the relative pose. Overall, this pipeline
is similar to ours, except that we replaced the UNet feature extractor with
the more powerful LoFTR architecture and the soft feature matching with a hard
one. These allow us to significantly improve accuracy and achieve cross scene
generalization with limited training data.

##  3 Method

Figure 1: Network architecture. Given an image pair, our network is composed
of three modules (top), LoFTR which produces a coarse grid of features, a
warping module, and a pose regression module. The bottom figure shows a
detailed description of the warping and pose regression modules.

Our goal, given two images of the same scene captured from different
viewpoints, is to predict the relative position and orientation between the
two respective cameras, including the distance between their centers. We
achieve this goal by introducing a 3-module architecture, a feature extraction
module, a matching and warping module, and a pose regression head. Below we
describe the three modules and the loss function. See Fig. 1, describing the
architecture of our model.

###  3.1 Feature extraction

Our first module produces descriptors for each pixel in the two images in a
coarse resolution of $1/8^{th}$ of the original image resolution in each
dimension. For this module we use a sub-network of the LoFTR model [44], pre-
trained on the Scannet dataset [13], depicting indoor scenes. The LoFTR
architecture is applied to both images in parallel. Denote the input images by
$I_{\mathrm{A}}$ and $I_{\mathrm{B}}$. Each image is first fed to a feature
pyramid network [28], producing a pixel-wise feature map at the desired
resolution. Next, a positional encoding is summed to these maps. The obtained
maps are then fed into a sequence of interleaved self- and cross-attention
layers, producing the final feature maps,
$F_{A}(\mathbf{x}_{i}),F_{B}(\mathbf{x}_{j})\in\mathbb{R}^{C}$, where $C$
denotes the number of feature channels, $1\leq i,j\leq n$, $n=WH/64$ and $W$
and $H$ denote the width and height of the input images in their original
resolution. Noted that the cross attention steps modify the feature maps to
account for the features seen in the other image.

###  3.2 Matching and warping

Our next aim is to identify matching points. Given the coarse feature maps
$F_{A}(\mathbf{x}_{i})$ and $F_{B}(\mathbf{x}_{j})$ (expressed as row
vectors), we select for each point $\mathbf{x}_{i}$ in $I_{\mathrm{A}}$ a
corresponding point $\mathbf{x}_{i}^{*}$ in $I_{\mathrm{B}}$ by maximizing the
correlation between their respective feature vectors, $F_{A}(\mathbf{x}_{i})$
and $F_{B}(\mathbf{x}_{i}^{*})$. Specifically, the coordinate
$\mathbf{x}_{i}^{*}$ in $I_{\mathrm{B}}$ is determined by

$\mathbf{x}_{i}^{*}=\operatorname*{argmax}_{j}F_{A}(\mathbf{x}_{i})F_{B}(\mathbf{x}_{j})^{T}$
(1)

Additionally, we use the computed correlation matrix $F_{A}F_{B}^{T}$ to
calculate a confidence score by applying softmax over each row of the 4-D
correlation matrix, namely,

$conf(\mathbf{x}_{i}^{*})=\underset{\mathrm{per\>row}}{\mathrm{softmax}}(F_{A}F_{B}^{T})(x_{i}^{*})$
(2)

We next concatenate corresponding features, append an encoding of their
positions in the two images and the confidence score obtaining, a feature map
of correspondences, namely,

$G(\mathbf{x}_{i})=[F_{A}(\mathbf{x}_{i}),\mathbf{x}_{i},F_{B}(\mathbf{x}_{i}^{*}),\mathbf{x}_{i}^{*},\mathrm{conf}(\mathbf{x}_{i}^{*})]$
(3)

Note that in this feature maps, the features in $F_{b}$ are warped to their
corresponding features in $F_{a}$.

###  3.3 Pose Regression module

Given the warped feature map, $G(\mathbf{x}_{i})$, we apply a residual
convolutional block followed by an MLP, which is then split to produce a
4-dimensional quaternion vector $\hat{\mathbf{q}}$ depicting the relative
orientation and a 3-dimensional vector $\hat{\mathbf{t}}$ depicting the
(scaled) relative position. The magnitude of this 3-vector predicts the
distance in meters between the two camera centers. To depict an orientation,
the quaternion $\hat{\mathbf{q}}$ should be normalized, assuming the form
$(\cos(\theta/2),\mathbf{v}\sin(\theta/2))$, where $\theta$ represents a
rotation angle and $\mathbf{v}$ represents an axis of rotation. Since
$\pm\hat{\mathbf{q}}$ represents the same rotation, we additionally set its
first component to be positive.

###  3.4 Loss Function

We train the network in a supervised manner. Given image pairs with ground
truth orientation specified by a quaternion $\mathbf{q}$ and position
$\mathbf{t}$, we let

$\mathcal{L}_{\mathbf{q}}(I_{\mathrm{A}},I_{\mathrm{B}})=\left\|\frac{\hat{\mathbf{q}}}{\|\hat{\mathbf{q}}\|}-\mathbf{q}\right\|_{1},$
(4)
$\mathcal{L}_{\mathbf{t}}(I_{\mathrm{A}},I_{\mathrm{B}})=\|\hat{\mathbf{t}}-\mathbf{t}\|_{1},$
(5)

and

$\mathcal{L}_{\mathbf{t}_{n}}(I_{\mathrm{A}},I_{\mathrm{B}})=\left\|\frac{\hat{\mathbf{t}}}{\|\hat{\mathbf{t}}\|}-\frac{\mathbf{t}}{\|\mathbf{t}\|}\right\|_{2},$
(6)

where $\mathcal{L}_{\mathbf{q}}$ depicts the orientation error and
$\mathcal{L}_{\mathbf{t}}$ and $\mathcal{L}_{\mathbf{t}_{n}}$ depict the
position error (with the inter-camera distance both un-normalized and
normalized). Balancing these terms can be challenging. Following [24], we use
learned weights as follows:

$\displaystyle\mathcal{L}_{\sigma}(I_{\mathrm{A}},I_{\mathrm{B}})$
$\displaystyle=\exp\left(-s_{\mathbf{q}}\right)\mathcal{L}_{\mathbf{q}}(I_{\mathrm{A}},I_{\mathrm{B}})+s_{\mathbf{q}}$
(7)
$\displaystyle+\exp\left(-s_{\mathbf{t}}\right)\mathcal{L}_{\mathbf{t}}(I_{\mathrm{A}},I_{\mathrm{B}})+s_{\mathbf{t}}$
(8)
$\displaystyle+\exp\left(-s_{\mathbf{t}_{n}}\right)\mathcal{L}_{\mathbf{t}_{n}}(I_{\mathrm{A}},I_{\mathrm{B}})+s_{\mathbf{t}_{n}},$
(9)

where $s_{\mathbf{q}}$, $s_{\mathbf{t}}$, and $s_{\mathbf{t}_{n}}$ are scalars
initialized at zero and optimized with gradient descent during training.

##  4 Experiments

###  4.1 Datasets

We train our network on the 7Scenes indoor dataset [19] and evaluate on the
7Scenes, University indoor [27], and the outdoor Cambridge landmarks [25]
datasets.

7Scenes [19]. Microsoft 7-Scenes dataset is a widely used indoor dataset for
visual relocalization that contains RGB-D images covering seven different
indoor locations (rooms) scanned with KinectFusion. Each scene is provided
with training and testing image sequences. We use the training dataset
provided in [27, 30], consisting of roughly 40K pairs of images and 80K test
pairs. See examples of pairs from this dataset in Fig. 4. We note that the
relative camera positions in this dataset are erroneously set to
$\mathbf{t}_{i}-\mathbf{t}_{j}$ where $\mathbf{t}_{i},\mathbf{t}_{j}$
represent the absolute position of the $i^{\mathrm{th}}$ and $j^{\mathrm{th}}$
cameras, instead of $\mathbf{t}_{i}-R_{ij}^{T}\mathbf{t}_{j}$, where $R_{ij}$
denotes the relative orientation between cameras $i$ and $j$. We rectify this
error in our experiments.

University [27]. University is an indoor dataset consisting of five scenes.
The scenes are organized in a similar way to 7Scenes. The dataset contains
roughly 14K training pairs and 17K test pairs. See examples of pairs from this
dataset in Fig. 4. Ground truth localization is computed with an off-the-shelf
SfM method. To improve the ground truth localization, we recomputed the
absolute position and orientation for each of the five scenes using Colmap
[42] and removed both cross scene image pairs and pairs that involve images
that Colmap failed to register. Note that SfM methods can only solve for
camera positions only up to a global multiplicative scale.

Cambridge Landmarks [25]. An urban localization dataset capturing six outdoor
scenes in Cambridge, UK. The ground truth poses are determined using a
standard SfM method (with positions recovered up to a global scale). The
images were captured at different times, affected by different lighting and
weather condition and containing moving objects including vehicles and
pedestrians. See examples of pairs in Fig. 4.

Scannet[13] Scannet is an indoor dataset consisted of 1613 monocular sequences
with ground truth poses and depth maps. This dataset contains image pairs with
wide baselines and extensive texture-less regions. We use the same train/test
split used by LoFTR[44].

###  4.2 Baselines

We compare our approach to three recent RPR methods:

RelPoseNet [27]. This method utilizes ResNet34 classification network pre-
trained on the Imagenet dataset to extract a feature vector for each image.
The two vectors are then concatenated and fed into an MLP that regresses the
relative pose. The method is trained end-to-end with a ground truth loss. The
training includes color jitter and random crop augmentations.

8-Point [38]. This method produces feature embedding using a pre-trained Res-
Net18 [22] followed by ViT-tiny [15] with an added bi-linear cross attention
layer with a quadratic positional encoding. The output of these is passed
through an MLP to regress the relative position and orientation. The method is
trained end-to-end with a ground truth loss. The training data is augmented
with color jitter and random grey scale.

Map-free RPR. This method is taken from the baselines suggested in [2]. It
uses a residual UNet (ResUNet) architecture to produce a feature map for each
image. A soft feature matching is obtained by computing a 4D correlation
volume followed by softmax. This soft matching is then used to warp the
features of one image into their corresponding locations in the other image. A
regression module is finally used to estimate the relative pose. This method
has no pre-trained parts. We both trained this method from scratch using the
quaternion and scaled translation parameterization (marked as ”Map free rep”
in the tables), and also tested the pre-trained model with weights obtained
with training, using the $3D-3D$ method described in [2], on the large Scannet
dataset (marked as ”Map free Scannet” in the tables)

Our approach: implementation details. Our method is implemented using
Pytorch[33] and Kornia[37]. We initialize the loss hyper-parameters with
$s_{\mathbf{q}}=s_{\mathbf{t}}=s_{\mathbf{t}_{n}}=0$. We train our method for
80 epochs using the ADAM optimizer [26] with a learning rate of $1e^{-3}$ and
StepLR scheduler with step size of 6 and $\gamma=0.9$.

For all methods we use the validation dataset to determine the best set of
weights.

###  4.3 Metrics and Evaluation

For each method we measure the position error as the Euclidean distance
between the predicted and ground truth position:

$t_{err}(\mathbf{t},\hat{\mathbf{t}})=\|\hat{\mathbf{t}}-\mathbf{t}\|_{2}.$
(10)

For the University and Cambridge Landmarks datasets camera positions are known
up to a global scale for each scene. In our experiments, therefore, we
optimize for this scale for each method separately. We measure orientation
error as the angle between the predicted and ground truth quaternion:

$R_{err}(\mathbf{q},\hat{\mathbf{q}})=2\arccos\left(\left|\frac{\hat{\mathbf{q}}^{T}\mathbf{q}}{\|\hat{\mathbf{q}}\|}\right|\right).$
(11)

For both measures we report the median per scene for each method.

Method | Chess | Fire | Heads | Office | Pumpkin | Red kitchen | Stairs | Average
---|---|---|---|---|---|---|---|---
RelPoseNet[30] | 8.149 | 0.261 | 12.327 | 0.382 | 12.414 | 0.234 | 9.045 | 0.307 | 9.362 | 0.352 | 9.636 | 0.407 | 12.259 | 0.367 | 10.456 | 0.342
8Point[38] | 3.338 | 0.123 | 7.819 | 0.270 | 10.384 | 0.172 | 4.059 | 0.181 | 3.682 | 0.187 | 4.145 | 0.210 | 5.018 | 0.263 | 5.492 | 0.214
Map-free rep.[2] | 5.835 | 0.154 | 12.207 | 0.334 | 12.542 | 0.191 | 7.319 | 0.237 | 6.647 | 0.269 | 7.093 | 0.267 | 10.167 | 0.313 | 8.830 | 0.268
Map-free Scannet [2] | 5.445 | 0.144 | 5.110 | 0.149 | 3.406 | 0.112 | 3.518 | 0.13 | 5.506 | 0.266 | 3.754 | 0.185 | 3.817 | 0.152 | 4.365 | 0.166
Ours | 4.463 | 0.147 | 7.206 | 0.195 | 7.254 | 0.128 | 4.653 | 0.167 | 4.797 | 0.225 | 4.543 | 0.203 | 5.840 | 0.238 | 5.537 | 0.186
Ours-Scannet | 3.568 | 0.115 | 4.946 | 0.142 | 6.195 | 0.123 | 3.660 | 0.140 | 3.670 | 0.168 | 4.019 | 0.149 | 6.344 | 0.225 | 4.630 | 0.158

Table 1: 7Scenes experiment. The table shows the result of training and
testing on the entire 7Scenes dataset with the train and test split specified
in the text (except Map-free Scannet and Ours-Scannet, which are trained on
Scannet). Each column shows orientation error in degrees (left) and position
error in meters (right).

Method | Chess | Fire | Heads | Office | Pumpkin | Red kitchen | Stairs | Average
---|---|---|---|---|---|---|---|---
RelPoseNet[30] | 16.129 | 0.388 | 16.070 | 0.378 | 14.091 | 0.341 | 15.947 | 0.364 | 14.940 | 0.365 | 15.705 | 0.471 | 14.341 | 0.353 | 15.318 | 0.380
8Point[38] | 14.785 | 0.372 | 16.591 | 0.347 | 14.913 | 0.339 | 13.238 | 0.360 | 13.224 | 0.382 | 13.154 | 0.419 | 13.977 | 0.372 | 14.269 | 0.370
Map-free rep.[2] | 20.312 | 0.395 | 17.809 | 0.395 | 21.953 | 0.380 | 18.075 | 0.545 | 26.948 | 0.483 | 17.867 | 0.593 | 20.284 | 0.369 | 20.464 | 0.451
Ours | 10.867 | 0.304 | 10.016 | 0.344 | 10.277 | 0.309 | 7.416 | 0.246 | 8.100 | 0.255 | 8.040 | 0.278 | 10.011 | 0.266 | 9.247 | 0.250

Table 2: 7Scenes: single scene training experiment. This table shows the
result of training on one of the seven scenes and testing on the other six
scenes. The title in each column describes the training scene. Each column
shows orientation error in degrees (left) and position error in meters
(right).

Method | Office | Meeting | kitchen | Conference | Average
---|---|---|---|---|---
RelPoseNet[30] | 18.723 | 0.345 | 14.701 | 0.311 | 15.917 | 0.363 | 18.069 | 0.373 | 16.853 | 0.348
8Point[38] | 14.236 | 0.272 | 9.449 | 0.223 | 11.196 | 0.227 | 14.431 | 0.234 | 12.328 | 0.239
Map-free rep.[2] | 12.241 | 0.246 | 10.613 | 0.218 | 11.734 | 0.172 | 12.479 | 0.222 | 11.767 | 0.214
Map-free- Scannet | 5.317 | 0.452 | 3.522 | 0.184 | 3.526 | 0.484 | 4.335 | 0.529 | 4.175 | 0.412
Ours | 7.132 | 0.266 | 5.110 | 0.143 | 6.998 | 0.311 | 5.510 | 0.280 | 6.188 | 0.250
Ours - Scannet | 4.987 | 0.360 | 3.536 | 0.165 | 3.791 | 0.420 | 3.311 | 0.362 | 3.904 | 0.327

Table 3: University experiment. The table shows the result of the methods
trained on the 7Scenes dataset (except Map-free Scannet and Ours-Scannet,
which are trained on Scannet) and tested on the University dataset.

method | KingsCollege | OldHospital | ShopFacade | StMarysChurch | Average
---|---|---|---|---|---
RelPoseNet[30] | 18.629 | 0.268 | 18.235 | 0.298 | 19.364 | 0.314 | 20.158 | 0.399 | 19.097 | 0.320
8point[38] | 7.890 | 0.213 | 9.675 | 0.165 | 11.463 | 0.196 | 12.600 | 0.223 | 10.407 | 0.199
Map-free rep.[2] | 9.312 | 0.175 | 11.929 | 0.194 | 13.324 | 0.281 | 14.166 | 0.245 | 12.183 | 0.224
Map-free- Scannet | 4.506 | 0.296 | 6.746 | 0.246 | 7.018 | 0.542 | 7.404 | 0.284 | 6.418 | 0.342
Ours | 6.842 | 0.145 | 8.168 | 0.115 | 12.218 | 0.289 | 12.502 | 0.195 | 9.933 | 0.186
Ours - Scannet | 4.086 | 0.209 | 6.909 | 0.237 | 7.388 | 0.400 | 7.889 | 0.174 | 6.568 | 0.255

Table 4: Cambridge experiment. The table shows the result obtained for the
methods trained on the 7Scenes dataset (except Map-free Scannet and Ours-
Scannet, which are trained on Scannet) and tested on the Cambridge outdoors
dataset.

###  4.4 Results

In our first experiment, we trained and tested all methods on the 7Scenes
dataset using the train/test split described above. In this setting, when
trained on 7Scenes our method (marked as ”Ours” in the tables) exhibits
similar accuracy as the 8Point network, and both outperform RelPoseNet and
Map-free (marked as ”Map-free rep” in the tables). In addition, for
completeness, we compare our model when trained on the huge Scannet dataset
(marked as ”Ours-Scannet” in the tables) with the pre-trained Map-free model
on Scannet dataset (marked as ”Map-free Scannet” in the tables). In this case,
we are comparable to Map-free. See results in Table 4. Our advantage over all
algorithms becomes evident in the cross-scene and cross-dataset generalization
experiments below.

The next experiment tests cross scene generalization. For this experiment we
trained the methods on a mere single scene from the 7Scenes dataset and tested
on the remaining 6 scenes. Results are shown in Table 4. It can be seen that
in this experiment our method significantly outperforms all the baseline
methods.

The third and fourth experiments test cross dataset generalization. In the
third experiment we train all methods on the 7Scene indoor dataset and test on
the University indoor dataset. We note that the test pairs depict
significantly different scenery and are captured with different cameras under
different lighting setups. Our results are shown in Table 4. When trained on
7Scenes our method produces significantly more accurate orientations than
competing methods trained on the same dataset, and its position estimates are
somewhat inferior to those of Map-free. When trained on Scannet our network
produces the best orientations in comparison to all methods, and orientation
somewhat better than the Map-free trained on Scannet.

In the last experiment we train all methods on either the 7Scene indoor or the
Scannet datasets and test on the Cambridge outdoor dataset. The results are
show in Table 4. The results show that, although our method is trained on
indoor scenes only, it manages to generalize to outdoor scenes as well. Also,
when trained on Scannet, our network predicts camera positions more accurately
than Map-free trained on Scannet and achieves comparable orientation
predictions, and both these methods are significantly superior to the other
methods trained on 7scenes.

Figure 2: Pairs of images from the 7Scenes dataset, including scenes with
repetitive patterns.

Figure 3: Pairs of images from the Office, Kitchen and Meeting scenes from the
University dataset. Notice the texture-less scenes and the middle pair from
the Kitchen scene has no overlap.

Figure 4: Pairs of images from the Kings College, Old Hospital and Shop Facade
from the Cambridge Landmarks dataset. Notice the different lighting
conditions.

###  4.5 Ablation Study

We perform an ablation study to analyze the effect of individual components of
our method. In particular, (1) we replace the feature extraction module (2) we
analyze the importance of the warping module. For (1) we extract the feature
maps from different stages of LoFTR [44]. For (2) we evaluate the impact of
the warping module. These experiments and additional implementation and
datasets details are provided in the supplementary material.

##  5 Conclusion

We presented a deep neural network for relative pose regression. Given an
image pair, our method uses the pre-trained LoFTR network to produce a semi-
dense point feature map, a matching and warping model, and a convolutional
regressor to estimate the six degrees of freedom in the relative position and
orientation of the two cameras. Our experiments indicate that our method
achieves favorable cross scene and cross dataset generalization, in
particular, when the training data is limited, outperforming previous works.

## Acknowledgment

This research is partially supported by the Israeli Council for Higher
Education (CHE) via the Weizmann Data Science Research Center and by research
grants from the Estate of Tully and Michele Plesser and the Anita James Rosen
Foundation. Further support is obtained from the Dan and Betty Kahn Michigan-
Israel Partnership, and the U.S.-Israel Binational Science Foundation, grant
number 2018680.

## References

  * [1] Yehya Abouelnaga, Mai Bui, and Slobodan Ilic.  Distillpose: Lightweight camera localization using auxiliary learning.  In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7919–7924. IEEE, 2021.
  * [2] Eduardo Arnold, Jamie Wynn, Sara Vicente, Guillermo Garcia-Hernando, Áron Monszpart, Victor Adrian Prisacariu, Daniyar Turmukhambetov, and Eric Brachmann.  Map-free visual relocalization: Metric pose relative to a single image.  arXiv preprint arXiv:2210.05494, 2022.
  * [3] Vassileios Balntas, Shuda Li, and Victor Prisacariu.  Relocnet: Continuous metric learning relocalisation using neural nets.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 751–767, 2018.
  * [4] Daniel Barath, Jiri Matas, and Jana Noskova.  Magsac: marginalizing sample consensus.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10197–10205, 2019.
  * [5] Daniel Barath, Jana Noskova, Maksym Ivashechkin, and Jiri Matas.  Magsac++, a fast, reliable and accurate robust estimator.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1304–1312, 2020.
  * [6] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool.  Surf: Speeded up robust features.  In European conference on computer vision, pages 404–417. Springer, 2006.
  * [7] Aritra Bhowmik, Stefan Gumhold, Carsten Rother, and Eric Brachmann.  Reinforced feature points: Optimizing feature detection and description for a high-level task.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4948–4957, 2020.
  * [8] Eric Brachmann, Alexander Krull, Sebastian Nowozin, Jamie Shotton, Frank Michel, Stefan Gumhold, and Carsten Rother.  Dsac-differentiable ransac for camera localization.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6684–6692, 2017.
  * [9] Eric Brachmann and Carsten Rother.  Expert sample consensus applied to camera re-localization.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7525–7534, 2019.
  * [10] Eric Brachmann and Carsten Rother.  Neural-guided ransac: Learning where to sample model hypotheses.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4322–4331, 2019.
  * [11] Michael Calonder, Vincent Lepetit, Christoph Strecha, and Pascal Fua.  Brief: Binary robust independent elementary features.  In European conference on computer vision, pages 778–792. Springer, 2010.
  * [12] Christopher Choy, Junha Lee, René Ranftl, Jaesik Park, and Vladlen Koltun.  High-dimensional convolutional networks for geometric pattern recognition.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11227–11236, 2020.
  * [13] Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5828–5839, 2017.
  * [14] Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  Superpoint: Self-supervised interest point detection and description.  In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 224–236, 2018.
  * [15] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [16] Mihai Dusmanu, Ignacio Rocco, Tomas Pajdla, Marc Pollefeys, Josef Sivic, Akihiko Torii, and Torsten Sattler.  D2-net: A trainable cnn for joint description and detection of local features.  In Proceedings of the ieee/cvf conference on computer vision and pattern recognition, pages 8092–8101, 2019.
  * [17] Sovann En, Alexis Lechervy, and Frédéric Jurie.  Rpnet: An end-to-end network for relative camera pose estimation.  In Proceedings of the European Conference on Computer Vision (ECCV) Workshops, pages 0–0, 2018.
  * [18] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 24(6):381–395, 1981.
  * [19] Ben Glocker, Shahram Izadi, Jamie Shotton, and Antonio Criminisi.  Real-time rgb-d camera relocalization.  In 2013 IEEE International Symposium on Mixed and Augmented Reality (ISMAR), pages 173–179. IEEE, 2013.
  * [20] Richard Hartley and Andrew Zisserman.  Multiple view geometry in computer vision.  Cambridge university press, 2003.
  * [21] Richard I Hartley.  In defense of the eight-point algorithm.  IEEE Transactions on pattern analysis and machine intelligence, 19(6):580–593, 1997.
  * [22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [23] Wei Jiang, Eduard Trulls, Jan Hosang, Andrea Tagliasacchi, and Kwang Moo Yi.  COTR: Correspondence transformer for matching across images.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6207–6217, 2021.
  * [24] Alex Kendall and Roberto Cipolla.  Geometric loss functions for camera pose regression with deep learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5974–5983, 2017.
  * [25] Alex Kendall, Matthew Grimes, and Roberto Cipolla.  Posenet: A convolutional network for real-time 6-dof camera relocalization.  In Proceedings of the IEEE international conference on computer vision, pages 2938–2946, 2015.
  * [26] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [27] Zakaria Laskar, Iaroslav Melekhov, Surya Kalia, and Juho Kannala.  Camera relocalization by computing pairwise relative poses using convolutional neural network.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 929–938, 2017.
  * [28] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [29] David G Lowe.  Distinctive image features from scale-invariant keypoints.  International journal of computer vision, 60(2):91–110, 2004.
  * [30] Iaroslav Melekhov, Juha Ylioinas, Juho Kannala, and Esa Rahtu.  Relative camera pose estimation using convolutional neural networks.  In International Conference on Advanced Concepts for Intelligent Vision Systems, pages 675–687. Springer, 2017.
  * [31] David Nistér.  An efficient solution to the five-point relative pose problem.  IEEE transactions on pattern analysis and machine intelligence, 26(6):756–770, 2004.
  * [32] Onur Özyeşil, Vladislav Voroninski, Ronen Basri, and Amit Singer.  A survey of structure from motion*.  Acta Numerica, 26:305–364, 2017.
  * [33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32, 2019.
  * [34] Rahul Raguram, Jan-Michael Frahm, and Marc Pollefeys.  A comparative analysis of ransac techniques leading to adaptive real-time random sample consensus.  In European conference on computer vision, pages 500–513. Springer, 2008.
  * [35] René Ranftl and Vladlen Koltun.  Deep fundamental matrix estimation.  In Proceedings of the European conference on computer vision (ECCV), pages 284–299, 2018.
  * [36] Jerome Revaud, Cesar De Souza, Martin Humenberger, and Philippe Weinzaepfel.  R2d2: Reliable and repeatable detector and descriptor.  Advances in neural information processing systems, 32, 2019.
  * [37] Edgar Riba, Dmytro Mishkin, Daniel Ponsa, Ethan Rublee, and Gary Bradski.  Kornia: an open source differentiable computer vision library for pytorch.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 3674–3683, 2020.
  * [38] Chris Rockwell, Justin Johnson, and David F Fouhey.  The 8-point algorithm as an inductive bias for relative pose prediction by ViTs.  arXiv preprint arXiv:2208.08988, 2022.
  * [39] Edward Rosten and Tom Drummond.  Machine learning for high-speed corner detection.  In European conference on computer vision, pages 430–443. Springer, 2006.
  * [40] Ethan Rublee, Vincent Rabaud, Kurt Konolige, and Gary Bradski.  Orb: An efficient alternative to sift or surf.  In 2011 International conference on computer vision, pages 2564–2571. Ieee, 2011.
  * [41] Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  SuperGlue: Learning feature matching with graph neural networks.  In CVPR, 2020.
  * [42] Johannes Lutz Schönberger and Jan-Michael Frahm.  Structure-from-motion revisited.  In Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  * [43] Noah Snavely, Steven M Seitz, and Richard Szeliski.  Photo tourism: exploring photo collections in 3d.  In ACM siggraph 2006 papers, pages 835–846. 2006.
  * [44] Jiaming Sun, Zehong Shen, Yuang Wang, Hujun Bao, and Xiaowei Zhou.  LoFTR: Detector-free local feature matching with transformers.  CVPR, 2021.
  * [45] Prune Truong, Martin Danelljan, Luc V Gool, and Radu Timofte.  Gocor: Bringing globally optimized correspondence volumes into your neural network.  Advances in Neural Information Processing Systems, 33:14278–14290, 2020.
  * [46] Prune Truong, Martin Danelljan, and Radu Timofte.  Glu-net: Global-local universal network for dense flow and correspondences.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6258–6268, 2020.
  * [47] Prune Truong, Martin Danelljan, Luc Van Gool, and Radu Timofte.  Learning accurate dense correspondences and when to trust them.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5714–5724, 2021.
  * [48] Michał Tyszkiewicz, Pascal Fua, and Eduard Trulls.  Disk: Learning local features with policy gradient.  Advances in Neural Information Processing Systems, 33:14254–14265, 2020.
  * [49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [50] Dominik Winkelbauer, Maximilian Denninger, and Rudolph Triebel.  Learning to localize in new environments from synthetic training data.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 5840–5846. IEEE, 2021.
  * [51] Changchang Wu.  Visualsfm: A visual structure from motion system.  http://www. cs. washington. edu/homes/ccwu/vsfm, 2011.
  * [52] Changchang Wu.  Towards linear-time incremental structure from motion.  In 2013 International Conference on 3D Vision-3DV 2013, pages 127–134. IEEE, 2013.
  * [53] Kwang Moo Yi, Eduard Trulls, Vincent Lepetit, and Pascal Fua.  Lift: Learned invariant feature transform.  In European conference on computer vision, pages 467–483. Springer, 2016.
  * [54] Kwang Moo Yi, Eduard Trulls, Yuki Ono, Vincent Lepetit, Mathieu Salzmann, and Pascal Fua.  Learning to find good correspondences.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2666–2674, 2018.
  * [55] Qunjie Zhou, Torsten Sattler, Marc Pollefeys, and Laura Leal-Taixe.  To learn or not to learn: Visual localization from essential matrices.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 3319–3326. IEEE, 2020.

## Appendix

##  Appendix A Ablation Study

We perform an ablation study to analyze the role of individual components in
our method. In particular, (1) we evaluate the role of the features obtained
by [44], and (2) we analyze the impact of the warping module. The ablation
study is evaluated in the following setting. Training and testing on the
entire 7Scenes dataset with the train and test split as specified in the main
paper.

As demonstrated in Table 5, replacing the LoFTR[44] features with feature maps
extracted from the CNN block significantly degrades the accuracy. The
performance is improved when the feature maps are extracted from the first
self-attention layer in the $\mathrm{LoFTR}$ backbone. However, the resulting
accuracy (see Table 5) is inferior to the performance obtained by using the
final LoFTR features, i.e., the ones which are the output of the last cross-
attention module.

Regarding the role of the warping module, we conclude that this module has a
significant role and justify it by the degradation in performance when
omitted, see Table 5.

Method | Chess | Fire | Heads | Office | Pumpkin | Red kitchen | Stairs | Average
---|---|---|---|---|---|---|---|---
CNN + Warping | 14.873 | 0.233 | 17.529 | 0.296 | 16.343 | 0.166 | 14.769 | 0.312 | 14.802 | 0.343 | 15.106 | 0.316 | 14.250 | 0.274 | 15.382 | 0.277
Self-attention + Warping | 6.671 | 0.235 | 10.539 | 0.346 | 9.980 | 0.182 | 6.535 | 0.276 | 7.105 | 0.276 | 6.630 | 0.354 | 8.564 | 0.299 | 8.003 | 0.297
Without Warping | 7.388 | 0.259 | 11.098 | 0.374 | 9.354 | 0.166 | 5.947 | 0.229 | 6.461 | 0.375 | 6.637 | 0.340 | 7.043 | 0.343 | 7.704 | 0.298
Our | 4.463 | 0.147 | 7.206 | 0.195 | 7.254 | 0.128 | 4.653 | 0.167 | 4.797 | 0.225 | 4.543 | 0.203 | 5.840 | 0.238 | 5.537 | 0.186
Table 5: Ablation Study. The table shows the result of training and testing on
the entire 7Scenes dataset with the train and test split specified in the main
paper, for the different architectures. Each column shows orientation error in
degrees (left) and position error in meters (right).

##  Appendix B Implementation Details

###  B.1 Network architecture

We reduced the size of the images of the 7Scenes[19] to size of $256\times
341$ following [27]. Therefore, the feature pyramid network [54] in LoFTR[44]
outputs a $256\times 32\times 42$ feature map per image. The resolution is
preserved through the attention layers. The warping module concatenates the
feature maps of matching points in the two images and adds $5$ channels,
including the coordinates of the two matching points and the matching score.
This results in an output of size $517\times 32\times 42$. We further set the
output size of the first MLP in the pose regression module to 1024.

###  B.2 Experimental setting

All models are trained and evaluated using the same strategy. In all the
experiments, we use the Adam optimizer initialized with the default $\beta$s
($\beta_{1}$ = 0.9, $\beta_{2}$ = 0.999). The models are trained over 90
epochs with a batch size of 70, using a linear decay strategy, where the
learning rate is reduced by a factor of 0.9 every 6 epochs, starting with a
learning rate of $1\times 10^{-3}$. Using five NVIDIA A100 GPUs, the training
time of our model on the entire dataset of 7Scenes is roughly 12 hours and 3
hours when trained on a single scene.

##  Appendix C Additional analysis of results from the paper

When trained on all scenes, the (unnormalized) empirical CDFs of the error in
Figure 7 and the histograms in Figure 10 support our conclusions in the paper.
Our method has an accuracy similar to 8point [38] when trained on 7Scenes and
comparable to Map-free[2] when trained on Scannet.

It is also clear that the size of the dataset has an impact on the
performance. To demonstrate the impact, we use Heads scene as a case study for
our single scene training experiment. As we can see from Figures 13 and 16 our
method is substantially better in rotation, accumulating more pairs per error
threshold, and is slightly better in translation.

Figure 5: Rotation error: empirical (unnormalized) CDF

Figure 6: Translation error: empirical (unnormalized) CDF

Figure 7: Rotation and translation errors. The graphs show the empirical
(unnormalized) CDF of the errors. All methods are trained on the entire
7Scenes train set (besides ours-ScanNet and Map-free ScanNet that are trained
on Scannet) and tested on the entire test set. The graph for the rotation
error (left) is cut at 30 degrees accumulating $98.5\%$ of the test set
(contains a total of 84676 pairs).

Figure 8: Rotation error histogram

Figure 9: Translation error histogram

Figure 10: Histograms of rotation and translation errors. All methods are
trained on the entire 7Scenes train set (besides ours-ScanNet and Map-free
ScanNet that are trained on Scannet) and tested on the entire test set.

Figure 11: Rotation error: empirical (unnormalized) CDF

Figure 12: Translation error: empirical (unnormalized) CDF

Figure 13: Rotation and translation errors. The graphs show the empirical
(unnormalized) CDF of the errors. All methods are trained on the Heads scene
from the 7Scenes dataset and tested on the other six scenes. The graph of the
rotation error (left) is cut at 50 degrees accumulating $99\%$ of the test set
(contains a total of 74676 pairs).

Figure 14: Rotation histogram

Figure 15: Translation histogram

Figure 16: Histograms of rotation and translation errors. All methods are
trained on the Heads scene from the 7Scenes dataset and tested on the other
six scenes.